E n c i c l o p e d i a
de Conocimientos Fundamentales
UNAM ˜ SIGLO XXI
TEMA 2
ALGORÍTMICA
2.1 INTRODUCCIÓN A LA ALGORÍTMICA
2.1.1 Cocinar galletas
2.1.2 Recetas de cocina versus algoritmos
2.1.3 Tipos de algoritmo
2.2 INDUCCIÓN Y GRÁFICAS
2.2.1 El método de inducción
2.2.2 Colorear mapas
2.2.3 Gráficas
La boda de Úrsula
2.2.4 Acertijo de los tróminos
2.2.5 Probando funciones por inducción
Funciones cuadráticas
Función factorial
Función exponencial
2.3 RECURSIVIDAD
2.3.1 Algoritmo para colorear mapas con seis colores
2.3.2 Un problema y un algoritmo: las torres de Hanoi
El problema
El algoritmo
El modelo de cómputo
Las instrucciones
El problema computacional
La complejidad y el modelo de cómputo
Versión recursiva del algoritmo: corrección, complejidad y optimalidad
Recurrencia: un paradigma de diseño de algoritmos
Corrección del algoritmo recursivo
Complejidad del algoritmo recursivo
Memoria: otra medida de complejidad de un algoritmo
2.4 BÚSQUEDA EXHAUSTIVA
2.4.1 Coloración de gráficas
2.4.2 El problema de ordenamiento
Arcadio en la tienda
En busca de todos los ordenamientos
2.4.3 La pareja de puntos más cercanos
2.5 DIVIDE Y VENCERÁS
2.5.1 Ordenamiento por inserción
Corrección
Complejidad
2.5.2 Ordenamiento de burbuja
2.5.3 Búsqueda binaria
2.5.4 Ordenamiento por combinación
2.5.5 Ordenamiento rápido
2.5.6 Parejas de puntos
2.6 ÓRDENES DE CRECIMIENTO
2.7 RESUMEN
