circuitos

7pFQLFDV GH $QiOLVLV GH $OJRULWPRV
Hermosillo, Sonora
Febrero de 2000
Miguel Angel Norzagaray Cosío
2EMHWLYR
Presentar las técnicas más ampliamente utilizadas en el estudio del desempeño de algoritmos.

7HPDULR
6HVLyQ 

6HVLyQ 

¿Qué es un algoritmo?
El análisis de un algoritmo
¿Para qué hacer el análisis de un algoritmo?
Notación asintótica.

Algoritmos recursivos
Ecuacionesde recurrencia
Método iterativo
Método de sustitución
Merge Sort, QuickSort
Mínimo número de comparaciones

6HVLyQ 
Correctitud de algoritmos
Algoritmos iterativos
Consideraciones especiales
Ordenamientos y búsquedas
Árboles binarios de búsqueda
Conjuntos disjuntos: Unión por rango por
compresión de camino

6HVLyQ 
Heaps binomiales
Heaps de Fibonacci
Análisis amortizadoContador binario
Splay trees

Para estudiar algoritmos es necesario tener en consideración la computadora donde este será utilizado. Sin embargo,
existen muchos modelos formales muy difundidos sobre los que se realizan investigaciones con la intención de
conocer los alcances de las computadoras (o de los algoritmos) como las que se conocen hoy. La máquina RAM,
PRAM, Quantum o la de Turing sonalgunos de los modelos más difundidos y con ellos se han obtenido resultados
muy importantes, como la identificación de problemas que no son solubles con las limitaciones actuales (teóricas o
prácticas).

7pFQLFDV GH $QiOLVLV GH $OJRULWPRV
Miguel Angel Norzagaray Cosío
Universidad Autónoma de Baja California Sur
manc@uabcs.mx
5HVXPHQ
Se presentan en las siguientes notas los aspectos teóricosy metodológicos que se utilizan para
analizar una amplia variedad de algoritmos, tanto iterativos como recursivos. Estas notas son
sólo una guía para el curso del mismo nombre y no consideran con la misma profundidad las
técnicas de diseño de algoritmos, en aras de detallar mejor las técnicas de análisis en sí. Debido a
que cada algoritmo posee una estructura de datos implícita (y viceversa),se presentarán algunas
estructuras que son ilustrativas por el modo como son analizadas. Ejercicios y ejemplos se
presentan durante las sesiones del curso.
3DODEUDV FODYH: Algoritmo, análisis, recursivo, iterativo, amortizado.
 ,QWURGXFFLyQ
Los algoritmos existen desde épocas muy antiguas. Pero es hasta este siglo cuando son
estudiados más detalladamente por el importante papel que jueganen el mundo de las
computadoras.
La primera vez que alguien se enfrenta con el estudio de los algoritmos le “platican” que un
algoritmo es una secuencia lógica de pasos encaminada a resolver un problema específico. Esta
dista mucho de ser una definición formal y cualquiera con pretensiones formales diría que sobre
esa escasa base no se puede construir mucho.
En lo que sí se está de acuerdoal momento de definir un algoritmo es en las características que
debe reunir:
• &RUUHFWLWXG: Obvio es que lo primero es asegurar que el algoritmo realiza la tarea para la que
se ha diseñado.
• )LQLWXG: Siempre debe terminar en una cantidad finita de pasos, es decir, garantizar que no
se ejecutará eternamente.
• 'HILQLELOLGDG: Los pasos que describen al algoritmo deben estar exentos decualquier
ambigüedad.
• (QWUDGD \ VDOLGD: Consistiendo en la información con que se trabajará desde el principio y el
resultado que se desea obtener.
• (IHFWLYLGDG: Cada paso del algoritmo debe consistir en una operación básica de ejecución
exacta y finita, es decir, que cada paso sea realizable por una persona y que siempre se
obtengan los mismo resultados de manera exacta.

Estas soncaracterísticas igualmente empíricas aunque de lo más deseables. Presentar un modelo
tan completo como el de una máquina de Turing para poder definir algoritmo de manera formal
ocuparía mucho espacio, pero podemos establecer la siguiente definición más breve:
Llamaremos PpWRGR GH FiOFXOR a una cuaterna (4,2I) donde , y 2 son subconjuntos de 4,
I4Æ4 y I([) [ si [ está en 2. [ define la VHFXHQFLD...