Presentación de la Algoritmia

ALGORITMIA

• En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, unalgoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persaAl-Juarismi)1 es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite llevar a cabo una actividad mediante pasos sucesivos que no generen dudas a quien deba hacer dicha actividad.2 Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia
• 

Diseño y Análisis de Algoritmos

• 
• Algoritmia
• Legenda: A continuación encontraremos el enlace en donde Ricardo Baeza Yates nos da una introducción de lo que es la algoritmia.

Búsqueda Secuencial

• Veamos un primer ejemplo. Supongamos que hemos comprado el número x de una rifa en que se
• sortean n premios. El día del sorteo estamos presentes mientras se escogen los números ganadores.
• ¿Cuánto tiempo esperaremos para saber si hemos ganado algún premio? Analicemos el modelo.
• Podemos decir que el tiempo es proporcional a cada número premiado, así que nuestra operación
• básica será comparar x con cada número premiado. Enumeraremos la secuencia de números
• premiados de 1 a n y usaremos la notación número(j) para el j-ésimo número premiado.
• El diseño
• de la solución es inmediato: comparamos x con cada número premiado hasta que ganamos o no
• quedan más números. Veamos el análisis del peor caso: compararemos n veces, ya sea cuando
• ganamos con el último número o si el sorteo termina y no obtenemos ningún premio. Esto no es
• muy realista, pues si x es un número premiado, terminaremos antes. Para el caso promedio,
• supongamos que ganaremos un premio (esto no siempre es cierto pero simplifica los cálculos) y
• que la probabilidad de que x sea premiado es la misma para cada número, es decir p(x) = 1/n es la
• probabilidad de que x sea igual a número(j) para cualquier j. Por lo tanto, con probabilidad 1/n
• compararemos j números, para cualquier j. Luego tenemos la suma de j/n desde j igual 1 hasta n,
• que es igual a (n+1)/2, aproximadamente la mitad de los números, lo que debiera coincidir con
• nuestra intuición. Este algoritmo se dice que es en línea (on-line) porque los datos (números) no se
• conocen de antemano, lo que es frecuente en la realidad. En el modelo usado este algoritmo es
• óptimo en el peor caso, pues siempre podemos no obtener un premio y realizar n comparaciones.
• Este algoritmo se llama búsqueda secuencial.

Clasificación