Programacion C

Algoritmos y Estructuras de Datos
dreams_eater April 10, 2012

Abstract El Documento es tan solo una parte de los temas que me dictaron en clase, de Algoritmos y Estructuras de Datos, en algunos lados (Algoritmos y Estructuras de Datos 2). Por lo que el verdadero autor son mis profesores, foreros y los autores de los libros donde copie descaradamente imágenes.

Contents
I Algoritmos yCrecimiento de las Funciones. 3
4 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 6 7 8

1 Algoritmos. 2 Análisis de los Algoritmos. 3 Crecimiento. 3.1 Notación Asintótica . . . . . . . . . . . . . 3.2 Ejemplos de calculo de T(N) . . . . . . . . 3.3 Notaciónasintótica (eficiencia asintótica) 3.4 ejemplo de notación asintótica . . . . . . .

II

Recursividad

10
10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 11 12 12 12 13 13 14 15 15

4 Probar matemáticamente queun bucle funciona: 5 Recursividad: 5.1 Repaso de inducción matemática . . . . . . . . . . . . . . 5.2 ¿Cómo funciona la recursión? . . . . . . . . . . . . . . . . 5.3 4 Reglas: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Divide-and-conquer . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Cota superior para el algoritmo divide y vencerás 5.5 Tail-Recursion . . . . . . . . . . . .. . . . . . . . . . . . . 5.6 Coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6.1 Las Coroutinas de python desde la versión 2.5: . . 5.6.2 Las corutinas en C . . . . . . . . . . . . . . . . . .

1

6 Recursividad y el Problema de la Solución Óptima 6.1 Algoritmo de vuelta atrás o Algoritmos de Backtracking . . . . . . . . . . . . . 6.2 Algoritmos Greedy o AlgoritmosDevoradores o codiciosos. . . . . . . . . . . . . 7 Recursividad y Programación dinámica. 7.1 Memoización enfoque Top-down de la programación dinámica. . . . . . . . . . . 7.2 Un ejemplo de Bottom-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16 16 16 18 18 20 21

III

Algoritmos deOrdenación
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22
22 22 24 26 26 29 29 30 33 33 34

8 Ordenación mediante comparación 8.1 Insert-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Shell-Sort . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 MergeSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Operación Merge . . . . . . . . . . . . . . . . . . . . . 8.4 Quick-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.1 Selección Del Pivote . . . . . . . . . . . . . . . . . . . . 8.4.2 Estrategia de la Partición . . . . . . . . . . . . . . . . 8.5Cota inferior para los Algoritmos basados en comparaciones 8.6 Counting-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7 RadixSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

IV

Repazo avanzado (Pila, Cola y Lista)

35
35 36

9 Pilas(Stacks) 10 Colas (Queues) 11 Lista Enlazada 11.1 Lista Enlazada Simple (Linked list) . . . . 11.2 Lista Enlazada Doble(DoubleLinked List) 11.3 Lista Enlazada Circular . . . . . . . . . . . 11.4 Nodos Dummy . . . . . . . . . . . . . . . . . 11.5 Implementación de las listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37 37 37 38 38...