4.18.2.2 Complejidad Computacional Avanzada (20 horas) [Habilidades a,b]

Referencias Bibliográficas: [Martin, 2010,Linz, 2011,Sipser, 2012,Hopcroft and Ullman, 1993] Temas
  1. Revisión de las clases P y NP; introducir spacio P y EXP.
  2. Jerarquía polimonial.
  3. NP completitud (Teorema de Cook).
  4. Problemas NP completos clásicos.
  5. Técnicas de reducción.
Objetivos de Aprendizaje
  1. Define las clases P y NP (También aparece en AL / Automata Básico, Computalidad y Complejidad) [Evaluar]
  2. Define la clase P-Space y su relación con la clase EXP [Evaluar]
  3. Explique el significado de NP-Completo (También aparece en AL / Automata Básico, Computalidad y Complejidad) [Evaluar]
  4. Muestre ejemplos de problemas clásicos en NP - Completo [Evaluar]
  5. Pruebe que un problema es NP- Completo reduciendo un problema conocido como NP-Completo [Evaluar]



Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, basado en el modelo de la Computing Curricula de IEEE-CS/ACM