los algoritmos

A continuación se listan los temas que se pretenden cubrir (no necesariamente en el orden en que se listan).

Elementos de Algoritmia:
Definiciones básicas. Medidas de complejidad. El peor caso,el caso promedio, análisis amortizado. Notación asintótica. Corrección de algoritmos.

Métodos de la Matemática:
Sumas, recurrencias, combinatoria y su uso en el análisis de algoritmos.

Elementospara el Diseño de Algoritmos.
Estructuras de Datos:
heaps, heaps binomiales, Arboles AVL, estructuras para conjuntos de conjuntos, etc.
Estrategias:
"Greedy", "Backtracking", divide yconquistarás, programación dinámica, "Brach-and-Bound".
Popurrí de Algoritmos.
Dependiendo del número de semanas que tengamos antes de finalizar el trimestre, estudiaremos y analizaremos algunos o todos de lossiguientes tipos de algoritmos: Algoritmos de Optimización Combinatoia, algoritmos paralelos, algoritmos probabilí­sticos ,Heurísticas y algoritmos de Aproximació.n

Complejidad Computacional:
Lasclases P, NP, PESPACIO y otras. Problemas NP-completos, NP-Hard. Reducciones.
Indice
EL ENFOQUE DIVIDE Y VENCERÁS
1. Enfoque Divide y Vencerás para el Diseño de Algoritmos
1.1. Introducción1.2. Ejemplo: Multiplicación de Enteros Muy Grandes
2. Método General DV
2.1. Procedimiento General
2.2. Condiciones para que DV sea ventajoso
2.3. Análisis del Orden de los Algoritmos DV
3. LaDeterminación del Umbral
APLICACIONES DE LA TÉCNICA DIVIDE Y VENCERÁS
„ Algoritmos de Ordenación
„ Multiplicación de Matrices
„ Viajante de Comercio1. El Enfoque Divide y Venceras
Introducción
Latécnica Divide y Vencerás (DV) consiste en:
ƒ Descomponer el caso a resolver en un cierto
número de subcasos más pequeños del mismo
problema.
ƒ Resolver sucesiva e independientemente todos
estossubcasos.
ƒ Combinar las soluciones obtenidas para obtener la
solución del caso original.
Cuestiones:
¿Por qué hacer esto?
¿Cómo se resuelven los subcasos?
Ejemplo: Multiplicación de...