Introduction à la calculabilitée et à la complexité

Introduction à la calculabilitéet à la complexitéCours de M1, premier semestre 2010–2011Université Paris Diderot – Paris 7Cours : Sylvain Perifel, TD : Christian Choffrut1 IntroductionDans ce cours :– Formaliser la notion de calcul : qu’est-ce qu’une « méthode effective de calcul »? Qu’est-ce qu’unalgorithme? (peut-on se contenter des automates finis — nos ordinateurs ont un nombre fini d’états— ou des automates à pile p.ex.?) Un programme en C, en Caml (est-ce équivalent?)?– Peut-on tout calculer? Il y a des limites aux automates finis, aux automates à pile (lemme del’étoile, etc.) : y en a-t-il à nos ordinateurs? Existe-t-il un algorithme qui décide si un programmeen C affiche toujours « Hello world! »?– Enfin, que peut-on calculer efficacement? Qu’est-ce que ça veut dire? P. ex., existe-t-il un algo-rithme « efficace » pour décider si un graphe est 3-coloriable?2 Calculabilité2.1 Algorithmes« Processus de résolution d’un problème par le calcul », « méthode effective de calcul » — notionintuitive.2.1.1 Histoire– Premières traces chez les Babyloniens (actuel Irak), 2ème millénaire avant JC, pour le commerceet les impôts.– Chez les Grecs : algorithme d’Euclide (3ème siècle avant JC) pour le calcul du pgcd.– Étymologie : mathématicien perse (actuel Iran) Al Khuwarizmi au 9ème siècle après JC (a aussidonné algèbre). Étude systématique des algorithmes.– Machines et automates des 17ème et 18ème siècles (Pascaline 1642, Leibniz 1673, etc.).– Algorithmes pour ...