Algoritmos
Páginas: 31 (7660 palabras)
Publicado: 22 de marzo de 2013
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
Algoritmosy Crecimiento de las Funciones.
3
1 Algoritmos.
4
2 Análisis de los Algoritmos.
5
3 Crecimiento.
3.1 Notación Asintótica . . . . . . . . . . . . .
3.2 Ejemplos de calculo de T(N) . . . . . . . .
3.3 Notación asintótica (eficiencia asintótica)
3.4 ejemplo de notación asintótica . . . . . . .
II
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Recursividad
6
6
6
7
8
10
4 Probar matemáticamente que un 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
10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
12
12
12
13
13
14
15
15
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 Algoritmos Devoradores o codiciosos. . . . . . . . . . . . .
16
16
16
7Recursividad 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
18
20
21
III
22
Algoritmos de Ordenación
8 Ordenación mediante comparación8.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.5 Cota inferior para los Algoritmos basados en comparaciones
8.6 Counting-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.7 RadixSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
IV
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Repazo avanzado (Pila, Cola y Lista)
22
22
24
26
26
29
29
30
33
33
34
35
9 Pilas(Stacks)
35
10 Colas...
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
Algoritmosy Crecimiento de las Funciones.
3
1 Algoritmos.
4
2 Análisis de los Algoritmos.
5
3 Crecimiento.
3.1 Notación Asintótica . . . . . . . . . . . . .
3.2 Ejemplos de calculo de T(N) . . . . . . . .
3.3 Notación asintótica (eficiencia asintótica)
3.4 ejemplo de notación asintótica . . . . . . .
II
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Recursividad
6
6
6
7
8
10
4 Probar matemáticamente que un 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
10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
12
12
12
13
13
14
15
15
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 Algoritmos Devoradores o codiciosos. . . . . . . . . . . . .
16
16
16
7Recursividad 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
18
20
21
III
22
Algoritmos de Ordenación
8 Ordenación mediante comparación8.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.5 Cota inferior para los Algoritmos basados en comparaciones
8.6 Counting-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.7 RadixSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
IV
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Repazo avanzado (Pila, Cola y Lista)
22
22
24
26
26
29
29
30
33
33
34
35
9 Pilas(Stacks)
35
10 Colas...
Leer documento completo
Regístrate para leer el documento completo.