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

Optativas, Seminario de Ciencias de la Computación B

Horario

Temario

Exceptuando por recocido simulado y el Problema del Agente Viajero, todas las heurísticas en el temario son posibles ejemplos de lo que se verá en el seminario: se espera que los alumnos elijan problemas NP-duros y heurísticas para resoverlos y que vayan exponiendo ambos a lo largo del semestre.

1. Introducción
   • Complejidad computacional
   • Breve repaso de 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. Búsqueda con Cardumen de Peces
   • Cardúmenes de peces
   • Peso de peces
   • Movimiento local
   • Conciencia social
   • Heurística de búsqueda con cardumen de peces
   • Aplicaciones
6. Algoritmo de Optimización con Leones
   • Cooperación de manada
   • Defensa territorial
   • Invasión territorial
   • Apareamiento
   • Heurística algoritmo de optimización con leones
   • Aplicaciones
7. Optimización de Enjambre de Partículas
   • Inteligencia de enjambre
   • Posición y velocidad de partículas
   • Selección de parámetros
   • Comunicación entre partículas
   • Heurística de optimización de enjambre de partículas
   • Aplicaciones
8. Optimización de Ondas de Agua
   • Teoría de onda en aguas poco profundas
   • Propagación, refracción y rompimiento
   • Fondo del océano como espacio de búsqueda
   • Heurística de optimización de ondas de agua
   • Aplicaciones

Evaluación

El curso se evaluará de la siguiente manera:

Evaluación teórica

Los estudiantes expondrán su implementación de recocido simulado para el Problema del Agente Viajero, con actualizaciones pertinentes antes de entregarlo. Además expondrán un problema junto con la heurística y diseño correspondiente para resolverlo. Por último expondrán sus resultados.

Evaluación práctica

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

Habrá distintos problemas que se expondrán para que los alumnos puedan resolver usando una heurística de optimización combinatoria. Dos distintos estudiantes pueden resolver el mismo problema con dos distintas heurísticas, o dos problemas distintos con la misma heurística: pero dos estudiantes 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 o de entregar proyectos.

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.