OPTIMIZACION III:OPTIM.EN REDES Y PROGRAMACION LINEAL ENTERA - 525551
- Descripción :Asignatura teorico-practica que trata los problemas de flujos y caminos en redes, y problemas de optimizacion combinatorial en general.
Aporta a las siguientes competencias del perfil de egreso del Ingeniero Civil Matematico:
- Capacidad para identificar, plantear y resolver problemas. - Resultados aprendizaje esperados :El alumno que apruebe la asignatura debera ser capaz de:
1- Describir los algoritmos principales para los problemas de redes y de optimizacion combinatorial en general junto con sus caracteristicas. (1)
2- Estimar la complejdad computacional de un algoritmo. (2)
3- Determinar si un algoritmo dado da el resultado correcto para todas las entradas. (4)
4- Identificar problemas que puedan ser tratados mediante la teoria de flujo en redes. (3)
5- Determinar el algoritmo mas apropiado para resolver un problema combinatorial dado.(4)
6- Discutir la complejdad computacional de un problema de decision en la jerarquia temporal, argumentando matematicamente.(5) - Contenidos :Complejidad Computacional
- Nociones de analisis de algoritmos.
- Clases de complejidad temporal.
- Nocion de reduccion y completitud.
Problemas de redes:
- Camino mas corto. Algoritmo Dijkstra y otros.
- Algoritmo para flujo maximo. Teorema flujo maximo-costo minimo.
- Algoritmo para flujo de costo minimo.
- Modelamiento de diferentes problemas como problemas de redes.
Metodos heuristicos:
- Ramificacion y acotamiento.
- Aplicacion a la programacion lineal entera.
- Otros algoritmos euristicos.
- Metodología :Clases expositivas. Tareas teoricas y practicas. Exposiciones individuales.
- Evaluación :De acuerdo al Reglamento Interno de Docencia de Pregrado de la Facultad de Ciencias Fisicas y Matematicas.
- Facultad :CS FISICAS Y MATEMATICAS
- Departamento :INGENIERIA MATEMATICA
- Creditos :4
- Cupos :30
- Campus :CONCEPCION