Descripción del proyecto

Curso Online

Curso sobre Problemas NP-Complete

Visión general del curso sobre Problemas NP-Complete

Ingrese al área de problemas más complejos y aprenda algoritmos avanzados para ayudar a resolverlos.

Este curso, que forma parte del programa MicroMasters de algoritmos y estructuras de datos, analiza problemas intrínsecamente difíciles con los que se encontrará en el mundo real y que no tienen un algoritmo comprobable conocido como problemas NP-Complete.

Practicará la resolución de grandes casos de algunos de estos problemas a pesar de su dureza utilizando software especializado y técnicas algorítmicas muy eficientes, que incluyen:

  • Solucionadores de SAT
  • Algoritmos aproximados
  • Casos especiales de problemas NP-hard
  • Algoritmos heurísticos

Lo que aprenderás en este curso

  • NP-completitud y cómo lidiar con ella
  • Cómo aproximar algoritmos
  • Cómo utilizar algoritmos heurísticos para resolver un problema más rápidamente cuando los métodos clásicos son demasiado lentos

Plan de estudio del curso

Semana 1: Problemas NP-Complete

  • Aunque muchos de los algoritmos que ha aprendido hasta ahora se aplican mucho en la práctica, resulta que el mundo está dominado por problemas del mundo real sin un algoritmo conocido que demuestre su eficacia. Muchos de estos problemas pueden reducirse a uno de los problemas clásicos llamados problemas NP-completos que o no pueden ser resueltos por un algoritmo polinomial o resolver cualquiera de ellos te haría ganar un millón de dólares (ver Problemas del Premio Millenium) y la eterna fama mundial por resolviendo el principal problema de la informática denominado P vs NP.
  • Es bueno saber esto antes de intentar resolver un problema antes de la fecha límite de mañana 🙂 Aunque es muy poco probable que estos problemas se puedan resolver de manera eficiente en un futuro cercano, la gente siempre encuentra varias soluciones.
  • En este módulo estudiarás los problemas NP-completos clásicos y las reducciones entre ellos.
  • También practicará la resolución de grandes casos de algunos de estos problemas a pesar de su dureza utilizando un software especializado muy eficiente basado en toneladas de investigación en el área de problemas NP-complete.

Semana 2: Hacer frente a NP-completitud: casos especiales

  • Después del módulo anterior, es posible que esté triste: acaba de pasar por 5 cursos en Algoritmos y descubrió que no son adecuados para la mayoría de los problemas del mundo real.
  • Sin embargo, ¡no te rindas todavía! Las personas son creativas y necesitan resolver estos problemas de todos modos, por lo que en la práctica a menudo hay formas de hacer frente a un problema NP completo.
  • Mostramos que algunos casos especiales en problemas NP-completos pueden, de hecho, resolverse en tiempo polinomial.

Semana 3: Hacer frente a NP-completitud: algoritmos exactos y aproximados

  • Consideramos algoritmos exactos que encuentran una solución mucho más rápido que el algoritmo de fuerza bruta.
  • Concluimos con algoritmos de aproximación que funcionan en tiempo polinomial y encontramos una solución cercana a la óptima.

Curso Online sobre Problemas NP-Complete. Inscribete ya!

  • Curso Online sobre Problemas NP-Complete. Inscribete ya!
  • Institución: San Diego
  • Costo: Gratis
  • Certificado: Incluye
  • Modalidad: Online
  • Inicio: Ver Fechas
  • Duración: 3 semanas
  • Dedicación: 8 a 10 horas por semana
  • Idioma: Inglés
  • Subtítulos: Inglés
  • Ir al curso

Etiquetas: