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

7bd6154a-5a06-4bc1-9306-9e900dfb3cd0 (image/jpg)

c4c1c808-b373-4201-8ff9-c3f58d2a22ce.gif (image/gif)

• Algoritmia

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

Diseño y Análisis de Algoritmos

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.

238358a8-26c0-4b1f-ac35-9da40a1bb9ed (image/jpg)

Clasificación