Información General

 
Asignatura:Tecnicas Avanzadas de Programacion
Código:6226
Tipo:electiva
Créditos:5
Requisitos:Lenguaje de Programacion

ObjetivosContenido TemáticoEvaluaciónBibliografía
 

Objetivos

1. Al terminar el curso el estudiante debe ser capaz de: - Aplicar algoritmos avanzados a soluciones de problemas reales. - Implementar estructuras de datos avanzadas. - Reconocer el tipo de solución apropiada para un problema aplicando soluciones conocidas. - Comparar soluciones en cuanto a eficiencia tanto en tiempo de ejecución como en espacio requerido. - Reconocer cuando un problema es intratable y en consecuencia no se pueden aplicar técnicas de solución tradicionales.

Ir al tope 
 

Contenido Temático

1. Estructuras de Datos Avanzadas: Heaps y heapsort. Colas de prioridad. Conjuntos Disjuntos. Hashing. Estructuras para representación de grafos. Ordenamiento topológico. Recorridos en profundidad y amplitud. Componentes conexos
2. Técnica básica de diseño.: QuickSort. Método de Strassen para multiplicación de matrices.
3. Algoritmos voraces.: Método general. Problema de “dar vuelto”. Algoritmo de Dijkstra. Árboles recubridores mínimales. Algoritmos de Prim y Kruskal. Problema de la mochila.
4. Programación dinámica: Principio de optimalidad. Demostración geométrica. Grafos multietapa. Caminos más cortos. Problema de la mochila. Árboles de búsqueda binarios óptimos. Problema del agente viajero. Multiplicación encadenada de matrices.
5. Backtracking: Método general. Suma de subconjuntos. Coloramiento de g rafos. Ciclos hamiltonianos. Problema de las 8 reinas.
6. Ramificación y acotamiento: Método general. Problema de la mochila 0/1. Problema del agente viajero.
7. Programación Probabilística.: Generadores de números Pseudo-aleatorios. Algoritmos de las Vegas. Problema de las 8 reinas. Método de Monte Carlo. Integración de Monte Carlo. Estimación de Pi.

Ir al tope 
 

Evaluación
EvaluaciónTipoValor
TeoríaNo editado por el profesor
1%

Ir al tope 
 

Bibliografía

  •  Aho, Hopcroft, Ullman, "The Design and Analysis of Computer Algorithms"

  •  Aho, Hopcroft, Ullman, "Data Structures & Algorithms"

  •  Brassard G., Bratley P, "Fundamentos de Algoritmia"

    •

     
     
     
    Ir al tope