Todo

Escuela Universitaria de Ing. Industrial, Informática y Sistemas Universidad de Tarapacá

Programa de Asignatura
Identificación Nombre: Carrera: Horas semanales: Horario: Profesor: Semestre:Diseño y Análisis de Algoritmos Ingeniería Civil en Computación e Informática

M.Sc. Héctor Beck Fernández Primero 2.011

Objetivos Generales Al término de la asignatura el alumno deberá ser capaz de:1. Comprender y utilizar, adecuadamente, los principios teóricos y empíricos que son usados en el análisis y diseño de algoritmos. 2. Describir y utilizar correctamente los algoritmos que sedescribirán en el curso. Temario 1. Introducción y motivación 1.1. Eficiencia de los algoritmos 1.2. Análisis del caso promedio y del peor caso. 1.3. En busca de la eficiencia 2. Análisis de algoritmos 2.1.Notación asintótica 2.2. Resolución de recurrencias 3. Técnicas de diseño de algoritmos 3.1. Algoritmos golosos 3.2. Dividir y conquistar 3.3. Programación dinámica 4. Grafos 4.1. Grafos y juegos4.2. Recorrido en profundidad; grafos no dirigidos 4.3. Recorrido en profundidad; grafos dirigidos 4.4. Recorrido en anchura 4.5. Vuelta atrás 5. Introducción a los algoritmos probabilistas 5.1.Generación de números pseudoaleatorios 5.2. Algoritmos de Monte Carlo 6. Introducción a la complejidad computacional 6.1. Las clases P y NP 6.2. Problemas NP-Completos 7. Introducción a los algoritmosheurísticos y aproximados 7.1. Coloreando un grafo 7.2. El problema del vendedor viajero

Análisis y Diseño de Algoritmos

1

Escuela Universitaria de Ing. Industrial, Informática y SistemasUniversidad de Tarapacá

7.3. El problema de la mochila Evaluaciones Tres evaluaciones teóricas, según el calendario dado por la Jefatura de Carrera, nt trabajos prácticos y nl lecturas. Calculo de lanota final:
1 3 1 nt 1 nl Nota _ final = 0,50 * * ∑ nota _ pruebai + 0,25 * ∑ nota _ trabajoi + 0,25 ∑ nota _ lectura i 3 i =1 nt i =1 nl i =1

Bibliografía 1. Guilles Brassard and Paul Bratley;...