TEORÍA AVANZADA DE ALGORITMOS Y COMPLEJIDAD
GRADUADO EN INGENIERÍA DEL SOFTWARE
Curso 2011/12
Tipo: Optativa

Profesores:

Curso:
Semestre:
ECTS: 4

Objetivos

CÓDIGO RESULTADOS DE APRENDIZAJE DE LA ASIGNATURA
RA1 Conocer y aplicar algoritmos clásicos de optimización en redes de transporte, emparejamientos en grafos y geométricos en el plano.
RA2 Analizar la corrección y complejidad de los algoritmos presentados.
RA3 Reconocer la NP-completitud de problemas notorios en grafos.
RA4 Construir modelos matemáticos para la resolución de problemas.

Subir

Programa

CONTENIDOS ESPECÍFICOS (TEMARIO)
TEMA APARTADOS
Tema 1. CAMINOS MÍNIMOS EN GRAFOS PONDERADOS
1.1 Problema del camino mínimo.
1.2 Algoritmo de Dijkstra
1.3 Algoritmo de Floyd-Warshall.
1.4 Algoritmo de Bellman-Ford.
1.5 Aplicaciones.
Tema 2. FLUJO MÁXIMO EN REDES DE TRANSPORTE
2.1 Flujos en redes básicas de transporte.
2.2 Problema del flujo máximo y del corte mínimo.
2.3 Caminos aumentadores de flujo.
2.4 Algoritmo de Ford-Fulkerson.
2.5 Algoritmo de Edmonds-Karp.
2.6 Flujo en redes no básicas.
Tema 3. FLUJO DE COSTE MÍNIMO
3.1 Problema del flujo de coste mínimo. Simplificación del modelo general.
3.2 Algoritmo del camino de menor coste (Busaker-Gowen).
3.3 Algoritmo de eliminación de ciclos de peso negativo (Klein).
Tema 4. EMPAREJAMIENTOS EN GRAFOS
4.1 Emparejamientos maximales y caminos aumentadores.
4.2 Emparejamientos en grafos bipartitos.
4.3 Emparejamientos en grafos no bipartitos.
4.4 Aplicaciones.
Tema 5. ALGORITMOS GEOMÉTRICOS EN EL PLANO
5.1 Intersección de segmentos. Técnica de barrido.
5.2 Cierres convexos de puntos.
5.3 Par de puntos más próximo y más lejano.
Tema 6. INTRODUCCIÓN A LA INTRATABILIDAD COMPUTACIONAL
6.1 Complejidad computacional. Problemas P y NP.
6.2 Reducción de problemas.
6.3 NP-completitud.

Subir

Evaluación

EVALUACIÓN SUMATIVA
BREVE DESCRIPCIÓN DE LAS ACTIVIDADES QUE SE EVALÚAN MOMENTO LUGAR PESO EN LA CALIFICACIÓN
Resolución y exposición de problemas Ver cronograma AULA 40%
Pruebas escritas Ver cronograma AULA 40%
Elaboración y presentación de un trabajo Fin de curso AULA 20%

Criterios de Evaluación

Resolución y exposición de problemas:

Los alumnos dispondrán de una colección de problemas para ir resolviendo conforme se desarrolle la teoría. En las clases de problemas todos los alumnos saldrán a la pizarra a exponer su solución. El profesor valorará la calidad de la solución y de la exposición y calificará acorde a su criterio. El peso total de esta actividad será del 40% de la nota final.

Pruebas escritas:

Habrá cuatro y constarán de test con tres opciones de las cuales solo una es correcta (acertadas=1, fallo=-0’5, blanco=0) y cuestiones. Cada prueba pesará un 10% de la nota final.

Elaboración y exposición de un trabajo:

Los alumnos, posiblemente por parejas, podrán elegir un trabajo relacionado con los temas de la asignatura de los ofrecidos en una lista. Se les facilitará la documentación y la orientación necesarias para realizarlo y se expondrán al final del curso. El profesor valorará la calidad del trabajo y de la exposición y calificará. El peso total de esta actividad será del 20% de la nota final.

Prueba de evaluación final para los que no hayan realizado o superado la evaluación continua: constará de dos partes:

  •  Examen escrito con test, cuestiones y problemas (80%).
  •  Elaboración y presentación de un trabajo (20%).

  Subir