Outils pour utilisateurs

Outils du site


enseignement:masters:resume_calc

Introduction à la calculabilité et la complexité

  • Un modèle de calcul simple: les automates
  • Les machines de Turing. nodéterminisme, universalité
  • Décidabilité et calculabilité, réductions entre problèmes
  • Complexité en temps, P et NP
  • Complexité en espace
  • Théorèmes d’hiérarchie
enseignement/masters/resume_calc.txt · Dernière modification: 24/10/19 13:21 par Zielonka