[A2A]
- Reducciones de problemas, cómo modelar una aplicación en términos de optimización combinatoria (establecer un gráfico, etc.).
- El concepto general de NP-completitud y problemas comunes que son NP-hard (variantes de SAT, TSP, cubierta de vértice y conjunto independiente, cubierta de vértice, partición de gráfico equilibrado). Ser capaz de reconocerlos en aplicaciones.
- Reconocer problemas que son significativamente más difíciles que NP (síntesis óptima de circuitos, problemas de conteo, juegos como el ajedrez).
- Optimización combinatoria usando Branch-and-bound.
- Comprender por qué tener muchos procesadores paralelos no le permite resolver automáticamente problemas NP-hard en tiempo polinómico en la práctica (mucha gente no entiende esto).
- Problemas comunes de optimización combinatoria que no son NP-hard, y se pueden resolver en un tiempo de polinomio bajo (coincidencia, algunas formas de partición de gráficos, problemas de flujo de red, programación lineal). Ser capaz de reconocer estos problemas en las aplicaciones. No es necesario recordar todas las soluciones con todo detalle, pero al menos saber cómo encontrarlas.
- Heurística rápida (y metaheurística) para escalar colinas para problemas difíciles de NP, como la optimización codiciosa, la búsqueda local aleatoria, el recocido simulado y la búsqueda tabú (también metaheurística).
- Aleatoriedad y algoritmos de optimización aleatoria.
Temas adicionales:
- Aproximación de las soluciones: algunos problemas son aproximables (como el TSP), mientras que otros no lo son (camarilla máxima).
- Varios trucos en el uso de solucionadores SAT para resolver otros problemas.
- Agrupación de gráficos y optimización multinivel para problemas relevantes (como la partición de gráficos).
- MILP: programación mixta de enteros y lineal.
- ¿La informática distribuida siempre sigue el modelo maestro esclavo?
- ¿Por qué no podemos transformar datos grandes en algo simple como pi o resolviendo una ecuación?
- ¿Es posible desarrollar aplicaciones a tiempo completo sin un título?
- ¿Qué beneficios ofrece Oracle Identity Manager?
- ¿Podría alguien en el futuro hacer un chip de inteligencia artificial de computadora que mejore el atractivo?
