Ciencias de la Computación (plan 2013) 2017-2

Optativas, Seminario de Ciencias de la Computación B

Heurı́sticas de Optimización Combinatoria

EL HORARIO PROBABLEMENTE PODAMOS CAMBIARLO.

Es necesario que hayan aprobado las siguientes materias para llevar el seminario:

• Modelado y Programación
• Análisis de Algoritmos
• Inteligencia Artificial
• Ingenierı́a de Software (recomendada)
• Complejidad Computacional (recomendada)

Temario

1. Introducción
   • Complejidad computacional
   • Problemas NP-Completos y NP-Duros
   • Optimización combinatoria
2. Recocido Simulado
   • Recocido simulado en metalurgia
   • Función objetivo
   • Heurı́stica de recocido simulado
   • Aceptación por umbrales
   • Aplicaciones
3. Colonia de Abejas Artificiales
   • Colonias de abejas
   • Abejas empleadas, supervisoras y exploradoras
   • Fuentes de alimento
   • Heurı́stica de colonia de abejas artificiales
   • Aplicaciones
4. Optimización de Colonia de Hormigas
   • Colonias de hormigas
   • Evaporación de feromonas
   • Sistemas elitistas
   • Sistemas máx-min
   • Heurı́stica de optimización de colonia de hormigas
   • Aplicaciones
5. Algoritmos Genéticos
   • Teorı́a de la Evolución
   • Poblaciones y cromosomas
   • Función de reproducción
   • Heurı́stica de algoritmo genético
   • Aplicaciones

Evaluación

El curso se evaluará de la siguiente manera:

Evaluación teórica

Habrá tres exámenes parciales, cada uno de los cuales cubrirá aproximadamente la tercera parte del material visto en clase.

No hay exámenes de reposición ni examen final.

Evaluación práctica

Habrá dos proyectos; el primero se realizará de forma individual, y consistirá en escribir una implementación de recocido simulado. El segundo se realizará en equipo, y consistirá en escribir una implementación de la heurística de optimización combinatoria que el equipo exponga al grupo.

Habrá distintos problemas que se expondrán para que los equipos puedan resolver usando una heurística de optimización combinatoria. Dos distintos equipos pueden resolver el mismo problema con dos distintas heurísticas, o dos problemas distintos con la misma heurística: pero dos equipos distintos no pueden resolver el mismo problema con la misma heurística.

La fecha límite de entrega de los proyectos es inamovible.

Renuncias, NPs y extraordinarios largos

Para alumnos inscritos, la única forma en que se les pondrá NP en actas es si solicitan renunciar al curso mediante un correo electrónico dirigido al profesor, a más tardar en la octava semana de clases. Si no mandan un correo electrónico a más tardar en la octava semana, un alumno escrito tendrá en actas la calificación que obtenga en el curso, no importa cuál sea ésta, y no importa si deja o no de asistir a clases, entregar prácticas y proyectos, y/o realizar exámenes.

No se guardan calificaciones para próximos semestres ni para exámenes extraordinarios. Mucho menos se “pasan” o “reciben” calificaciones a o de otros profesores.