Outils pour utilisateurs

Outils du site


enseignement:masters:master-impairs:resulecalculabilite

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/master-impairs/resulecalculabilite.txt · Dernière modification: 23/10/19 16:11 par Zielonka