2.1.5 AL/Complejidad Computacional Avanzada
Temas:
Electivo
- Revisión de las clases P y NP; introducir spacio P y EXP.
- Jerarquía polimonial.
- NP completitud (Teorema de Cook).
- Problemas NP completos clásicos.
- Técnicas de reducción.
Objetivos de Aprendizaje:
Elective:
- Define las clases P y NP (También aparece en AL / Automata Básico, Computalidad y Complejidad) [Familiarizarse]
- Define la clase P-Space y su relación con la clase EXP [Familiarizarse]
- Explique el significado de NP-Completo (También aparece en AL / Automata Básico, Computalidad y Complejidad) [Familiarizarse]
- Muestre ejemplos de problemas clásicos en NP - Completo [Familiarizarse]
- Pruebe que un problema es NP- Completo reduciendo un problema conocido como NP-Completo [Usar]
Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, basado en el modelo de la Computing Curricula de IEEE-CS/ACM