Embedded Files
Algoritmo
Un algoritmo, es un procedimiento(conjunto de pasos bien definidos), que toma un valor o conjunto de valores de entrada y produce otro valor o conjunto de valores de salida.
El planteamiento del problema, deberá especificar en términos generales, los datos de entrada que se necesiten y los datos de salida que se deben producir.
Ejemplo:
El problema de ordenar una secuencia de números de forma creciente.
Entrada: La secuencia de n números (a1, a2, a3,..., an)
Salida: Otra secuencia de n números (a'1, a'2, a'3,..., a'n), donde se cumple a'1 <= a'2 <= a'3 <= ... <= a'n
Así, si tendríamos la secuencia de números (31, 41, 59, 26, 41, 58) como entrada nuestro algoritmo de ordenamiento debería producir la siguiente secuencia de números (26, 31, 41, 41, 58, 59).
La secuencia de números como entrada es llamada la instancia del problema de ordenamiento.
Ejercicios
Resuelva los ejercicios 1.1-1, 1.1-2, 1.1-3, 1.1-4 y 1.1-5 del libro.
Eficiencia
El computador tiene recursos preciados(Memoria, Procesador) los cuales debemos tomar en cuenta al momento de la elaboración de un algoritmo. Un algoritmo eficiente será aquél, que sabiamente haga uso de estos recursos.
Diferentes algoritmo, abocados a resolver el mismo problema, difieren dramáticamente en su eficiencia.
Ejemplo:
Se tiene dos computadoras. Computadora A(la más rápida) y computadora B(la más lenta). La computadora A ejecutara el algoritmo de ordenamiento por inserción(Insertion Sort) y la computadora B el algoritmo de ordenamiento por mezcla(Merge Sort).
Cada uno de ellos debe ordenar un arreglo de 10 millones de números enteros (se necesita 80000000 bytes para almacenar el arreglo o 76.29395 Megabytes).
La computadora A ejecuta 10 billones de instrucciones por segundo y es mil veces más rápido que la computadora B. Un MIPS es un millón de instrucciones por segundo.
Ademas se sabe que el coste del algoritmo de ordenamiento por inserción es 2n2 y del algoritmo de ordenamiento por mezcla es 50nlgn instrucciones para ordenar los 10 millones de números.
Entonces, la computadora A necesitaría, 5.56 horas para ordenar 10 millones de números:
2n2 instrucciones = 2(10 000 000)2 instrucciones = 20 000 segundos
10 000 000 000 instrucciones/segundo 10 000 000 000 instrucciones/segundo
A su vez, la computadora B necesitaría, 19.37 minutos para ordenar los 10 millones de números:
50nlgn instrucciones = 50(10 000 000)lg(10 000 000) instrucciones = 1162.67 seg
10 000 000 000 instrucciones/segundo 10 000 000 instrucciones/segundo
Notas:
lgn es igual a lg2n, es un caso particular de logaritmos en el que la base es 2. Esta base tiene su importancia en informática (donde se lo representa comúnmente como lg n, o ld n que proviene del Latín logarithmus dualis), dada la codificación binaria que se utiliza.
y = log2(x) significa a que valor y hay que elevar 2 para obtener x
Entonces: y = log2(10 000 000) , y=
Una forma simple para calcular el log2(n) en una calculadora que no posee la función log2 es utilizar el logaritmo natural (base e, indicado como ln) o el logaritmo común (base 10, indicado como log), los cuales se encuentran en la mayoría de las calculadoras científicas. La fórmula para esto es:
Si hacemos una primera simulación de considerando de 2 a 20 números para ordenar y observamos cuanto tarda en segundos, notamos que Inserción es más eficiente que el de mezcla.
Sin embargo, la situación cambia a medida que incrementamos la cantidad de número a ordenar y es exactamente a partir de 190 que se observa este cambio.
A partir de cantidades mayores a 189 números el algoritmo de ordenamiento por mezcla es mucho mas eficiente en su tiempo de ejecución.
Ejercicios
Resuelva los ejercicios 1.2-1, 1.2-2 y 1.2-3 del libro.
Problemas para resolver
Para cada función f(n) y tiempo t de la siguiente tabla, determinar el mayor tamaño de n, donde un problema que puede ser resuelto en un tiempo t. Asumiendo que el algoritmo para resolver el problema tarda f(n) microsegundos.
Page updated
Google Sites
Report abuse