*Definicin y ejemplo de insercin

*Definicin y ejemplo de insercinEn este tipo de algoritmo los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es INSERTADO en la posicin apropiada con respecto al resto de los elementos ya ordenados.Ejemplo:

4 - 3 - 5 - 2 - 1

Temp toma el valor del segundo elemento, 3. La primera carta es el 4. Ahora comparamos: 3 es menor que 4. Luego desplazamos el 4 una posicin a la derecha y despus copiamos el 3 en su lugar.

4 - 4 - 5 - 2 - 1

3 - 4 - 5 - 2 - 1

El siguiente elemento es 5. Comparamos con 4. Es mayor que 4, as que no ocurren intercambios.

Continuamos con el 2. Es menor que cinco: desplazamos el 5 una posicin a la derecha:

3 - 4 - 5 - 5 - 1

Comparamos con 4: es menor, as que desplazamos el 4 una posicin a la derecha:

3 - 4 - 4 - 5 - 1

Comparamos con 3. Desplazamos el 3 una posicin a la derecha:

3 - 3 - 4 - 5 - 1

Finalmente copiamos el 2 en su posicin final:

2 - 3 - 4 - 5 - 1

El ltimo elemento a ordenar es el 1. Cinco es menor que 1, as que lo desplazamos una posicin a la derecha:

2 - 3 - 4 - 5 - 5

Continuando con el procedimiento la lista va quedando as:

2 - 3 - 4 - 4 - 5

2 - 3 - 3 - 4 - 5

2 - 2 - 3 - 4 - 5

1 - 2 - 3 - 4 - 5

*Definicin y ejemplo de Burbuja.

Consiste en ciclar repetidamente a travs de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que est en la siguiente posicin se intercambian.El mtodo de la burbuja es una comparacin lineal con cada uno de los elementos, el elemento que sea menor contra el que se esta comparado intercambiaran posiciones. Este mtodo no es recomendado para grandes comparaciones, ya que es un proceso muy lento y requiere de una gran cantidad de Memoria Ram.Ejemplo:

Esta es nuestra lista:

4 - 3 - 5 - 2 - 1

Tenemos 5 elementos. Es decir, TAM toma el valor 5. Comenzamos comparando el primero con el segundo elemento. 4 es mayor que 3, as que intercambiamos. Ahora tenemos:

3 - 4 - 5 - 2 - 1

Ahora comparamos el segundo con el tercero: 4 es menor que 5, as que no hacemos nada. Continuamos con el tercero y el cuarto: 5 es mayor que 2. Intercambiamos y obtenemos:

3 - 4 - 2 - 5 - 1

Comparamos el cuarto y el quinto: 5 es mayor que 1. Intercambiamos nuevamente:

3 - 4 - 2 - 1 - 5

Repitiendo este proceso vamos obteniendo los siguientes resultados:

3 - 2 - 1 - 4 - 5

2 - 1 - 3 - 4 - 5

1 - 2 - 3 - 4 - 5

*Definicin y ejemplo de seleccin.

Consiste en lo siguiente: Buscas el elemento ms pequeo de la lista.

Lo intercambias con el elemento ubicado en la primera posicin de la lista.

Buscas el segundo elemento ms pequeo de la lista.

Lo intercambias con el elemento que ocupa la segunda posicin en la lista.

Repites este proceso hasta que hayas ordenado toda la lista.Ejemplo:

Vamos a ordenar la siguiente lista (la misma del ejemplo anterior :-)):

4 - 3 - 5 - 2 - 1

Comenzamos buscando el elemento menor entre la primera y ltima posicin. Es el 1. Lo intercambiamos con el 4 y la lista queda as:

1 - 3 - 5 - 2 - 4

Ahora buscamos el menor elemento entre la segunda y la ltima posicin. Es el 2. Lo intercambiamos con el elemento en la segunda posicin, es decir el 3. La lista queda as:

1 - 2 - 5 - 3 - 4

Buscamos el menor elemento entre la tercera posicin (s, adivinaste:-D) y la ltima. Es el 3, que intercambiamos con el 5:

1 - 2 - 3 - 5 - 4

El menor elemento entre la cuarta y quinta posicin es el 4, que intercambiamos con el 5:

1 - 2 - 3 - 4 - 5

*Definicin y ejemplo de Algoritmo.

Un algoritmo es, una secuencia de instrucciones que realizan una tarea en un periodo de tiempo finito. Normalmente los algoritmos se asocian con estructuras de datos.El algoritmo recibe cero o ms entradas, produce al menos una salida, consiste en Instrucciones claras y poco ambiguas, termina despus de un nmero finito de pasos, y es lo suficientemente bsico que una persona puede llevar a cabo el algoritmo utilizando lpiz y papel. Por el contrario, un programa no es necesariamente finito: el programa, como un servidor Web, podra no terminar nunca si no hay intervencin externa. Algunos ejemplos de algoritmos asociados con estructuras de datos son:

Bsqueda-lineal, ordenacin-de-burbuja, bsqueda-binaria, concatenacin-de-listas enlazadas,

etc.

Ejemplo:

Problema: preparar una taza de t.

Entrada: tetera, taza, bolsa de t.

Salida: taza de t.

Inicio

Tomar la tetera

Llenarla de agua

Encender el fuego

Poner la tetera en el fuego

Esperar a que hierva el agua

Tomar la bolsa de t

Introducirla en la tetera

Esperar a que est hecho el t

Echar el t en la tazaFin*Cuando un problema puede resolverse usando varios tipos de algoritmos Cmo se decide que algoritmo es el mejor?

Para resolver un problema pueden existir varios algoritmos. Por tanto, es lgico elegir el mejor.

Si el problema es sencillo o no hay que resolver muchos casos se podra elegir el ms fcil.

Si el problema es complejo o existen muchos casos habra que elegir el algoritmo que menos recursos utilice.

Los recursos ms importantes son el tiempo de ejecucin y el espacio de almacenamiento.

Generalmente, el ms importante es el tiempo.

Al hablar de la eficiencia de un algoritmo nos referiremos a lo rpido que se ejecuta.

La eficiencia de un algoritmo depender, en general, del tamao de los datos de entrada.

La eficiencia de los algoritmos siempre vendr dada en funcin de dichos tamaos:

Algoritmos con vectores en funcin del nmero de componentes.

Algoritmos con matrices en funcin del nmero de filas y columnas.

La eficiencia adems depende del tamao de los ejemplares depende de la naturaleza de los mismos: caso mejor, caso peor y caso medio.

Caso mejor: se trata de aquellos ejemplares del problema en los que el algoritmo es ms eficiente; por ejemplo: multiplicar un nmero por cero, insertar en una lista vaca, ordenar un vector que ya est ordenado, etc. Generalmente no nos interesa.

Caso peor: se trata de aquellos ejemplares del problema en los que el algoritmo es menos eficiente (no siempre existe el caso peor). Ejemplos: insertar al final de una lista, ordenar un vector que est ordenado en orden inverso, etc. Nos interesa mucho.

Caso medio: se trata del resto de ejemplares del problema. Por ejemplo: multiplicar dos nmeros enteros distintos de cero, insertar en a de una lista que no sea el principio ni el final, ordenar un vector que no est ordenado ni en orden directo ni inverso, etc. Es el caso que ms nos debera preocupar puesto que ser el ms habitual, sin embargo no siempre se puede calcular (habra que saber cules son las probabilidades de los distintos ejemplares).*Cualidades deseables de un algoritmo.Para cualquier problema dado no existe una nica solucin algortmica; es tarea de la persona que disea un algoritmo encontrar la solucin ms ptima, sta no es otra que aquella que cumple ms fielmente las cualidades deseables de todo algoritmo bien diseado:

Finitud. Un algoritmo siempre tiene que finalizar tras un nmero finito de acciones.

Precisin. Todas las acciones de un algoritmo deben estar bien definidas, esto es, ninguna accin puede ser ambigua, sino que cada una de ellas slo se debe poder interpretar de una nica manera. Dicho de otra forma, si el programa que resulta de un algoritmo se ejecuta varias veces con los mismos datos de entrada, en todos los casos se obtendrn los mismos datos de salida.

Claridad. Lo normal es que un problema se pueda resolver de distintas formas. Por tanto, una de las tareas ms importantes del diseador de un algoritmo es encontrar la solucin ms legible, es decir, aquella ms comprensible para el ser humano.

Generalidad. Un algoritmo debe resolver problemas generales. Por ejemplo, un programa que realice sumas de nmeros enteros deber servir para realizar sumas de dos nmeros enteros cualesquiera, y no, solamente, para sumar dos nmeros determinados, como pueden ser el 3 y el 5.

Eficiencia. La ejecucin del programa resultante de codificar un algoritmo deber consumir lo menos posible los recursos disponibles del ordenador (memoria, tiempo de CPU, etc.).

Sencillez. A veces, encontrar la solucin algortmica ms eficiente a un problema puede llevar a escribir un algoritmo muy complejo, afectando a la claridad del mismo. Por tanto, hay que intentar que la solucin sea sencilla, aun a costa de perder un poco de eficiencia, es decir, se tiene que buscar un equilibrio entre la claridad y la eficiencia. Escribir algoritmos sencillos, claros y eficientes se consigue a base de prctica.

Modularidad. Nunca hay que olvidarse del hecho de que un algoritmo puede formar parte de la solucin a un problema mayor. Pero, a su vez, dicho algoritmo debe descomponerse en otros, siempre y cuando, esto favorezca a la claridad del mismo.

La persona que disea un algoritmo debe ser consciente de que todas las propiedades de un algoritmo se transmitirn al programa resultante.*Factores que afectan el tiempo de ejecucin de un programa.El tiempo de ejecucin de un algoritmo es quiz el aspecto ms importante a analizar. Algunos factores que afectan el tiempo de ejecucin de un programa son: los algoritmos utilizados.

la naturaleza de los datos de entrada (e.g. tamao).

el compilador empleado (fuera del alcance de nuestro modelo)

el tipo de computador (fuera del alcance de nuestro modelo) *Naturaleza y tamao de los datos de entrada.La entrada de datos a un programa afecta el tiempo de ejecucin del programa. El tamao de la entrada de datos tienen los efectos que pueden observase ms fcilmente en el tiempo de ejecucin de los algoritmos.

Por ejemplo, un programa que genera nmeros primos desde 1 a n, donde n es un nmero entero positivo dado de entrada. Claramente, cuando la entrada de datos es 1000, el algoritmo tomar menos tiempo para ejecutarse que cuando la entrada es 32767. Otro caso, es un algoritmo que ordena un arreglo de enteros en orden ascendente. El algoritmo tendr un tiempo de ejecucin muy grande cuando los datos de entrada requieren ordenar un arreglo que contiene 500.000 elementos en comparacin si el valor de entrada requiere ordenar apenas 1500 elementos.

As, el tamao de los datos de entrada afecta el tiempo de ejecucin de los algoritmos, especialmente en los algoritmos de bsqueda y ordenamiento. La naturaleza de los datos de entrada tambin puede afectar el tiempo de ejecucin de los programas.*Naturaleza y velocidad de ejecucin de instrucciones.En la mayora de las computadoras, las operaciones de adicin y sustraccin se ejecutan relativamente ms rpido que las operaciones de multiplicacin y divisin. Por lo tanto, un algoritmo que usa predominantemente las operaciones de adicin y sustraccin tendr un tiempo de ejecucin relativamente menor que uno donde predominan las multiplicaciones y divisiones.

A veces el uso de las operaciones de multiplicacin y divisin (as como el operador mdulo) es inevitable. En tales casos, si uno de los multiplicandos o divisores es un nmero que es expresable como una potencia de dos, entonces el algoritmo puede tener un tiempo de ejecucin que es menor que otros casos. Esto es porque una operacin de multiplicacin que involucra un multiplicando expresable en trminos de potencias de dos puede hacer uso del operador de desplazamiento de bits. En casi todas las computadoras las instrucciones de desplazamiento de bits se ejecutan ms rpido que la instruccin de multiplicacin. En forma similar, cuando se necesita dividir k por 16, se puede desplazar el patrn binario para k a la derecha 4 bits. As el uso de ciertas instrucciones puede disminuir el tiempo de ejecucin mientras que el uso de otras puede incrementarlo.

Algunas computadoras realizan operaciones para evaluar funciones trigonometras como seno, coseno y tangente, usando un algoritmo de software. Otras computadoras evalan estas operaciones directamente usando el hardware. Un algoritmo que usa tales operaciones se puede evaluar ms rpido en una computadora donde tales instrucciones son ejecutadas en el hardware.*Complejidad en tiempo de algoritmo.Para resolver un problema es necesaria, adems del algoritmo adecuado, la enumeracin de los datos que intervienen en dicho problema y la descripcin de cmo se relacionan dichos datos con los distintos pasos del algoritmo. El conjunto de estas tres cosas constituyen un programa y se plantea la siguiente igualdad:PROGRAMA = DATOS + ALGORITMO + SUS RELACIONES.

Grfica del tiempo de ejecucin para mcd (x, y). El rojo indica un clculo rpido, mientras los puntos eventualmente azules indican tiempos de ejecucin ms grandes.

Si se considera que las operaciones aritmticas son operaciones elementales, sin prdida de generalidad se supone que , entonces la complejidad del algoritmo est en el orden de donde . Para ver esto, primero se considera que para cualesquiera dos enteros a, b tales que , siempre se cumple

Esto es porque:

Si , entonces , por lo tanto , lo cual implica que Si entonces Como se considera que las operaciones aritmticas son operaciones elementales, entonces la complejidad del algoritmo es del orden exacto del nmero de veces que se usa el ciclo mientras de la versin iterativa. Considrese a y b despus de pasar dos veces por el ciclo suponiendo que el algoritmo no se detiene antes. Sean a0 y b0 los valores de entrada al algoritmo. Despus de la primera iteracin y seguidamente, en la segunda iteracin b toma ese valor.

De lo anterior, b se ha vuelto ms pequeo que . Es decir que b se dividido al menos por dos despus de dos pasadas por el ciclo. Adems sigue siendo cierto que y por lo tanto se puede aplicar el mismo razonamiento. La conclusin es que a lo mucho, se pasar por el ciclo aproximadamente veces.

Por lo tanto, la complejidad de con est en orden de .

Sin embargo, si se considera que las operaciones aritmticas no son operaciones elementales, entonces el nmero de operaciones est acotado por O (n2) - inferior a An2 con A una constante - donde n es el nmero de cifras del ms pequeo entre a y b.*Tcnica de bsqueda.Las tcnicas de bsqueda en el ajedrez han sido probablemente la parte ms desarrollada en trminos de investigacin para la mejora de algoritmos dentro del proceso del juego. Es ac en donde el programa realiza el mayor esfuerzo en recolectar informacin suficiente para decidir por un movimiento.

Los algoritmos desarrollados para este fin han sido variados. La primera propuesta, presentada por Shannon, fue la bsqueda por fuerza bruta a profundidad fija, examinando todas las continuaciones posibles hasta cierto lmite de movimientos. Esta bsqueda se realizara mediante el algoritmo Minimax.

Hasta principios de los 70 los programas de ajedrez seguan basndose en los modelos de Shannon para realizar su proceso de bsqueda. Hasta ese momento el diseo de programas de ajedrez se focalizaba principalmente en el orden de los movimientos con tal de lograr la mejor "poda" de variantes: jaques, capturas, "movidas asesinas", amenazas y avances de peones pasados. Categorizando los movimientos en distintos grupos mediante amenazas tcticas (de corto plazo) o estratgicas (de largo plazo) se poda asegurar el que las variantes "forzadas" seran analizadas primero. Esta tcnica lograba generar cortes o reducciones en el rbol de bsqueda para aquellas variantes que se clasificaban como innecesarias de analizar.

*Diferencia entre bsqueda interna y externa.

Existen dos categoras bsicas de tcnicas de ordenamiento: los mtodos de ordenamiento interno (los cuales se aplican cuando el conjunto de datos a clasificar es lo suficientemente pequeo, los algoritmos mas simples de ordinario requieren un tiempo o (n2 para clasificar n objetos) de tal forma que pueda caber dentro de la memoria principal. El tiempo requerido para escribir o leer registros de estructuras no se considera significativo para la evaluacin del rendimiento de las tcnicas de ordenamiento interno.) Y ordenamiento externo (este mtodo se aplica a gran cantidad de datos que residen parcial o totalmente en dispositivos de almacenamiento secundario, tales como discos o cintas magnticas. Aqu, el tiempo de acceso a lectura y escritura influye en la determinacin de la eficiencia del ordenamiento.)*Bsqueda lineal o secuencial.Es la tcnica de bsqueda mas simple comenzando por la cabeza de la lista se busca un determinado registro examinando cada registro secuencialmente hasta que se encuentra o la lista es agotada.

Este algoritmo es adecuado tanto para listas secuenciales como para listas enlazadas. La lista no tiene que estar ordenada aunque la eficiencia de la bsqueda puede mejorarse si lo esta. *Bsqueda binaria.Es uno de los algoritmos ms rpidos que usan los programadores .A diferencia de la bsqueda secuencial que examina elementos sucesivos de la matriz, la bsqueda binaria reduce el nmero de elementos que deben ser examinados.

Con un factor de dos en cada iteracin hasta que se encuentra el registro deseado .La disminucin de los tiempos de ejecucin se hace ms importante al aumentar el tamao de la matriz.

La primera iteracin de la bsqueda examina toda la matriz. Supongamos que las variables bajas y altas en el siguiente ejemplo reciben los valores de 0 y 9. La variable ndice medio es el elemento medio del intervalo de bsqueda. Valores de [ndice _ medio] contiene el valor que se va a comparar con el valor deseado.

Valor a buscar =jelipendice _ medio = (Alto + Bajo) div 2(9+0) div 2=4(9+4) div2= 6(6+4) div2 =5Si el valor determinado en valores (ndice medio) es igual al valor deseado la bsqueda se completa dando un valor verdadero a la variable encontrada. Si el valor contenido en valores (ndice Medio) es mayor que el valor deseado el algoritmo de bsqueda se modific, ya que el valor indica que no hay razn para seguir buscando en ese punto la lista.*Comparacin entre bsqueda secuencial y binaria.Ambos procedimientos de bsqueda lineal y binaria tienen sus ventajas y desventajas. Se compararn los dos procedimientos en trminos de eficiencia al realizar la bsqueda.

En la bsqueda lineal, no es posible conocer de antemano el nmero de comparaciones que sern realizadas antes que se encuentre el elemento bsqueda.

Suponga que el elemento que se busca est en la primera posicin. En tal caso, solo se realiza una comparacin antes de encontrar el elemento. Si el elemento que se est buscando est en la segunda posicin, entonces se necesitan dos comparaciones antes de encontrar el elemento.

Similarmente, si el elemento que se est buscando est en la posicin n-sima, se requieren comparaciones. As, en el peor caso, ejecutando n comparaciones se puede encontrar al elemento buscado en la posicin n de la lista. Se puede decir que la bsqueda no ha tenido xito slo si el elemento buscado no es encontrado despus de las n comparaciones.