- Le th\u00e9or\u00e8me de correction Cours 4<\/strong><\/li>
- Le th\u00e9or\u00e8me de compl\u00e9tude Cours 5<\/strong><\/li><\/ol><\/li>
- Le th\u00e9or\u00e8me de compacit\u00e9.<\/strong> Quelques applications. <\/em> <\/li>
- L\u2019arithm\u00e9tique de Peano <\/strong>Cours 6<\/strong>
- <\/ol><\/li>
- Les th\u00e9or\u00e8mes d\u2019incompl\u00e9tude de G\u00f6del Cours 7 et 8<\/strong>
- L\u2019arithm\u00e9tisation de la syntaxe<\/li>
- Les th\u00e9or\u00e8mes de Tarski, G\u00f6del<\/li><\/ol><\/li>
- La th\u00e9orie des ensembles Cours 9 \u00e0 11<\/strong>
- La th\u00e9orie na\u00efve des ensembles et la d\u00e9finition des ordinaux<\/li>
- Les axiomes de Zermelo-Fraenkel<\/li>
- L\u2019axiome du choix et l\u2019axiome de fondation<\/li><\/ol><\/li>
- Applications <\/strong>selon le temps qu\u2019il reste<\/em>
- L\u2019\u00e9limination des quantificateurs dans les corps r\u00e9els clos Cours 12<\/strong><\/li>
- L\u2019\u00e9limination des quantificateurs dans les corps alg\u00e9briquement clos Cours 13<\/strong><\/li><\/ol><\/li><\/ol>\n\n\n\n
Bibliographie pour le cours:<\/p>\n\n\n\n
- Logique math\u00e9matique, Ren\u00e9 Cori et Daniel Lascar, deux tomes chez Dunod (et premi\u00e8re \u00e9dition Axiomes). Cours et exercices. Plusieurs exemplaires \u00e0 la biblioth\u00e8que. Dans le premier tome : Calcul propositionnel, Alg\u00e8bre de Boole, Calcul des pr\u00e9dicats, Th\u00e9or\u00e8mes de compl\u00e9tude. Second tome : R\u00e9cursivit\u00e9 (inclus les machines de Turing) , Formalisation de l’arithm\u00e9tique, th\u00e9or\u00e8mes de G\u00f6del, th\u00e9orie des ensembles, un peu de th\u00e9orie des mod\u00e8les. (\u00e0 la Bib)<\/li>
- Introduction \u00e0 la logique, Th\u00e9orie de la d\u00e9monstration, Ren\u00e9 David, Karim Nour et Christophe Raffalli, Dunod (\u00e0 la Bib)<\/li>
- cours de Zoe Chatzidakis (cours de logique, automne 2014<\/a>)<\/li>
- Jean-Louis Krivine, th\u00e9orie des ensembles (chez Cassini, ou la vieille version aux PUF)<\/li>
- Le cours<\/a> sur le th\u00e9or\u00e8me de G\u00f6del d\u2019Alexandre Miquel<\/li>
- Quantifier Elimination following Muchnik<\/a>, Christian Michaux et Adem Ozturk<\/li><\/ul>\n\n\n\n
Bibliographie pour la plage :<\/p>\n\n\n\n
- Logicomix : an epic search for the truth (roman graphique disponible en fran\u00e7ais et en anglais \u00e0 la biblioth\u00e8que)<\/li>
- La logique, Gilles Dowek, Dominos Flammarion<\/li>
- et pourtant… ils ne remplissent pas N ! Claude Lobry (\u00e0 la bib)<\/li>
- Le th\u00e9or\u00e8me de G\u00f6del, point sciences, Ernest Nagel\/James R. Newman, Kurt G\u00f6del\/Jean-Yves Girard<\/li><\/ul>\n\n\n\n
Physique et Calcul Quantique :\u00a0accessible pour les \u00e9tudiants de l\u2019ENS Lyon sur\u00a0http:\/\/etudes.ens-lyon.fr\/<\/a>, Sciences de la mati\u00e8re, L3 SdM, Deuxi\u00e8me semestre, Physique , Information et Calcul<\/p>\n\n\n\n
2013-2014<\/h1>\n\n\n\n
Logique, cours de L3, second semestre : partiel<\/a>, examen<\/a><\/p>\n\n\n\n
Physique et Calcul Quantique : accessible pour les \u00e9tudiants de l\u2019ENS Lyon sur http:\/\/etudes.ens-lyon.fr\/<\/a>, Sciences de la mati\u00e8re, L3 SdM, Deuxi\u00e8me semestre, Physique , Information et Calcul<\/p>\n\n\n\n
Complexit\u00e9 Algorithmique,\u00a0cours de base de Master, premier semestre<\/p>\n\n\n\n
2012-2013<\/h1>\n\n\n\n
Complexit\u00e9 Algorithmique, cours de base de Master, premier semestre<\/p>\n\n\n\n
Cours 1, mardi 11 septembre : Rappels sur les machines de Turing, DTIME, P et NP
Cours 2, mardi 18 septembre : le th\u00e9or\u00e8me de Cook et les codages des calculs de machines de Turing
Cours 3 vendredi 21 septembre :co-NP , EXP, NEXP, th\u00e9or\u00e8me de hi\u00e9rarchie en temps d\u00e9terministe, machine de Turing non-d\u00e9terministe universelle
Cours 4 vendredi 28 septembre : th\u00e9or\u00e8me de hi\u00e9rarchie en temps non d\u00e9terministe, th\u00e9or\u00e8me de Ladner (preuve en TD), machines \u00e0 oracle et th\u00e9or\u00e8mes de relativisation de P=NP
Cours 5 vendredi 5 octobre : complexit\u00e9 en espace, graphe de configuration, th\u00e9or\u00e8me de hi\u00e9rarchie en espace, TQBF est PSPACE, th\u00e9or\u00e8me de Savitch (preuve en TD)
Cours 6 vendredi 26 octobre : NL-compl\u00e9tude, NL=co-NL
Cours 7, vendredi 9 novembre : Deux d\u00e9finitions de la hi\u00e9rarchie polynomiale, \u00e9nonc\u00e9 du th\u00e9or\u00e8me de compromis espace-temps pour SAT
Cours 8, vendredi 16 novembre : preuve du th\u00e9or\u00e8me de compromis espace-temps pour SAT, d\u00e9finition de la hi\u00e9rarchie polynomiale avec les oracles, d\u00e9but des classes de complexit\u00e9 d\u00e9finies avec les circuits
Cours 9, vendredi 23 novembre : P\/poly, th\u00e9or\u00e8me de Karp-Lipton (NP \\subset P\/poly implies PH=\\Sigma_2^p), th\u00e9or\u00e8me de Meyer (EXP \\subset P\/poly implies EXP=\\Sigma_2^p)
Cours 10, vendredi 30 novembre : classes de complexit\u00e9 probabilistes (BPP, polynomial identity testing, RP, ZPP)
Cours 11, vendredi 7 d\u00e9cembre : suite des classes probabilistes ( th\u00e9or\u00e8me de r\u00e9duction des erreurs, esp\u00e9rance du temps de calcul, BPP inclus dans P\/poly, BPP inclus dans Sigma_2^p inter Pi_2^p, simulation de pi\u00e8ce biais\u00e9e, r\u00e9duction probabiliste, AM)
Cours 12, vendredi 21 d\u00e9cembre : quelques notions sur les classes de comptage
<\/p>\n\n\n\nTD : S\u00e9bastien Tavenas
TD1 vendredi 14 septembre\u00a0: r\u00e9duction \u00e0 2 rubans et \u00e0 1 ruban
DM1\u00a0: r\u00e9duction de l\u2019alphabet, passage \u00e0 un demi-ruban
TD2\u00a0:<\/p>\n\n\n\n2011-2012<\/h1>\n\n\n\n
FDI : Fondements de l’informatique, premier semestre du L3<\/p>\n\n\n\n
cours : Pascal Koiran<\/a>
TD : S\u00e9bastien Tavenas et Natacha Portier<\/p>\n\n\n\nComplexit\u00e9 Algorithmique, cours de base de Master, premier semestre
TD : Bruno Grenet<\/a><\/p>\n\n\n\npartiel_11.pdf<\/a><\/p>\n\n\n\n
examen_11.pdf<\/a><\/p>\n\n\n\n
Bibliographie :<\/p>\n\n\n\n
- Sanjeev Arora et Boaz Barak :\u00a0Complexity Theory: A Modern Approach<\/a><\/li>
- C.H. Papadimitriou,\u00a0Computational Complexity<\/em>, Addison-Wesley(1994)<\/li>
- Michael Sipser,\u00a0Introduction to the theory of computation<\/em><\/li>
- Jos\u00e9 L. Balcazar, Josep Diaz, Joaquim Gabarro,\u00a0Structural Complexity <\/em><\/li><\/ul>\n\n\n\n
Physique et information quantique, cours d\u2019option du M1 de physique (cours avec Pascal Degiovanni)<\/p>\n\n\n\n
2008-2009<\/h1>\n\n\n\n
SIESTE<\/a><\/p>\n\n\n\n
![\"\"\/](\"http:\/\/perso.ens-lyon.fr\/natacha.portier\/enseign\/lignbleu.gif\")
<\/figure>\n\n\n\nFDI2 : Fondements de l’informatique, second semestre du L3
TD : Ivan Morel et Ir\u00e9n\u00e9e Briquel
Cours 1, mardi 27 janvier : les machines de Turing
Cours 2, mardi 3 f\u00e9vrier : les Random Access Machines
Cours 3, mardi 10 f\u00e9vrier : les fonctions r\u00e9cursives primitives
Cours 4, mardi 24 f\u00e9vrier : les fonctions r\u00e9cursives
Cours 5, mardi 3 mars : les syst\u00e8mes acceptables de programmation et leurs propri\u00e9t\u00e9s : codage de machines et de configurations, th\u00e9or\u00e8me de l’arr\u00eat, machines universelles, th\u00e9or\u00e8me smn, th\u00e9or\u00e8me de Rice, th\u00e9or\u00e8mes du point fixe de Kleene
Cours 6, mardi 10 mars : d\u00e9finition des syst\u00e8mes acceptables de programmation, th\u00e9or\u00e8me de l’isomorphisme de Rogers, ensembles d’entier \u00e9num\u00e9rables et r\u00e9cursivement \u00e9num\u00e9rables
Cours 7, mardi 17 mars : le calcul propositionnel, le th\u00e9or\u00e8me de compacit\u00e9 du calcul propositionnel
Cours 8, mardi 24 mars : le calcul des pr\u00e9dicats, le th\u00e9or\u00e8me de compl\u00e9tude et le th\u00e9or\u00e8me de compacit\u00e9 du calcul des pr\u00e9dicats
partiel le 31 mars
Cours \u00e0 la maison : ce cours<\/a>
Cours 9, mardi 7 avril : Le th\u00e9or\u00e8me de Tarski : dans le langage de l’arithm\u00e9tique avec exponentielle, la th\u00e9orie de N n’est pas d\u00e9finissable (d’apr\u00e8s Smullyan)
Cours 10, mardi 21 avril : Le th\u00e9or\u00e8me de G\u00f6del pour l’arithm\u00e9tique avec l’exponentielle (d’apr\u00e8s Smullyan)
Cours 11, mardi 28 avril : Le th\u00e9or\u00e8me de G\u00f6del pour l’arithm\u00e9tique sans l’exponentielle (d’apr\u00e8s Smullyan)
Cours 12, mardi 5 mai : l’ind\u00e9cidabilit\u00e9 du probl\u00e8me de Post (d’apr\u00e8s le Hopcroft, Motwani, Ullman)
Sur le 10\u00e8me pb de Hilbert : voir wikipedia et le livre de Matiiassevitch (voir la bibliographie)
Cours 13, mardi 12 mai : l’\u00e9limination des quanteurs dans les corps r\u00e9els clos, d’apr\u00e8s l’article de Christian Michaux et Adem Ozturk (voir la biblio).
mardi 26 mai 9h-12h : exam
TD1_09.pdf<\/a> : machines de Turing
TD2_09.pdf<\/a> : RAM
TD3_09.pdf<\/a> : fonctions r\u00e9cursives
TD4_09.pdf<\/a> : Ackermann et fonctions r\u00e9cursives
TD5_09.pdf<\/a> : Turing, le retour, et SAP
TD6_09.pdf<\/a> : Sur Kleene, snm et ensembles r\u00e9cursivement \u00e9num\u00e9rables
TD7_09.pdf<\/a> : Calcul propositionnel
Partiel_09.pdf<\/a> , correction<\/a> des exos 1 et 4
TD8_09.pdf<\/a> : Calcul des pr\u00e9dicats
TD9_09.pdf<\/a> : Th\u00e9orie des mod\u00e8les
TD10_09.pdf<\/a> : Peano et ses mod\u00e8les
TD11_09.pdf<\/a> : re-Peano, G\u00f6del, …
TD12_09.pdf<\/a> : castor affair\u00e9, ambiguit\u00e9 des grammaires alg\u00e9briques, tuiles de Wang
TD13_09.pdf<\/a> : r\u00e9visions
examen_09.pdf<\/a>
Bibliographie :<\/p>\n\n\n\n- celle de l’ann\u00e9e derni\u00e8re<\/li>
- La bibliographie pour l’option info de l’agreg, \u00e0 voir par ici<\/a>.<\/li>
- Raymond M. Smullyan, Godel’s Incompleteness Theorems<\/em>, 1992, Les th\u00e9or\u00e8mes d’incompl\u00e9tude de G\u00f6del<\/em>, Dunod, 2000<\/li>
- Logique et fondements de l’informatique, Hermes, Lassaigne et Rougemont<\/li>
- Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addison Wesley (trouvable \u00e0 la bib)<\/li>
- Youri Matiiassevitch<\/a> Le dixi\u00e8me probl\u00e8me de Hilbert: Son ind\u00e9cidabilit\u00e9<\/em>, Masson, (1995), ISBN<\/a> : 2225848351<\/li><\/ul>\n\n\n\n
Calcul quantique, cours de recherche de Master, premier semestre<\/p>\n\n\n\n
Complexit\u00e9 Algorithmique, cours de base de Master, premier semestre
TD : Ir\u00e9n\u00e9e Briquel et Laurent Jouhet<\/p>\n\n\n\nCours 0 : relire le cours de FDI2
Cours 1, mardi 16 septembre : classes de complexit\u00e9 Turing en temps
Cours 2, jeudi 18 septembre : NP, le th\u00e9or\u00e8me de Cook (voir chap 2 du Arora Barak)
Cours 3, jeudi 25 septembre : diagonalisation : th\u00e9or\u00e8mes de hi\u00e9rarchie d\u00e9terministe et non d\u00e9terministe en temps et th\u00e9or\u00e8me de Ladner (voir chap 3 du Arora Barak)
Cours 4, jeudi 9 octobre : les machines \u00e0 oracle et la question P=NP relativis\u00e9e, classes de complexit\u00e9 en espace, th de hierarchie
Cours 5, jeudi 16 octobre : Pspace, TQBF, th\u00e9or\u00e8me de Savitch, NL-complet
Cours 6, jeudi 23 octobre : NL=coNL, def de PH avec une g\u00e9n\u00e9ralisation des certificats, def de machine alternante
Cours 7 jeudi 30 octobre : compromis espace temps pour SAT (\u00e0 compl\u00e9ter), d\u00e9finition de PH avec les machines \u00e0 Oracle ; d\u00e9but des circuits bool\u00e9ens : P inclus strictement dans P\/poly.
Partiel : jeudi 6 novembre
Cours 8, jeudi 13 novembre : classes de circuit uniformes, machines de Turing avec conseil, NP inclus dans P\/poly implique PH=Sigma_2^p
Cours 9, jeudi 20 novembre : fin du chapitre sur les circuits (si EXP inclus dans P\/poly alors EXP = Sigma_2^p) et d\u00e9but des classes de complexit\u00e9 probabilistes (BPP, polynomial identity testing)
Cours 10, jeudi 27 novembre : fin du chapitre sur les classes probabilistes : RP, ZPP, th\u00e9or\u00e8me de r\u00e9duction des erreurs, esp\u00e9rance du temps de calcul, BPP inclus dans P\/poly, BPP inclus dans Sigma_2^p inter Pi_2^p
Cours 11, jeudi 4 d\u00e9cembre : d\u00e9but du chapitre sur les protocoles interactifs, d\u00e9finition des protocoles d\u00e9terministes et probabilistes, dIQ=NP, lemme de r\u00e9duction des erreur, graphe non isomorphisme et r\u00e9sidu non quadratique sont dans IP[2], bla bla sur 01-NP_C dans AM
Cours 12, jeudi 11 d\u00e9cembre : d\u00e9but de la preuve IP=PSPACE
Cours 13, jeudi 18 d\u00e9cembre : fin de la preuve IP=PSPACE
Examen pour ceux qui partent au second semestre : jeudi 18 d\u00e9cembre de 15h \u00e0 18h dans la salle de conseil du LIP (320 bis) au troisi\u00e8me \u00e9tage, un peu apr\u00e8s l’amphi B. Attention : la salle n’est pas tr\u00e8s bien chauff\u00e9e.
Cours 14, jeudi 8 janvier : quelques id\u00e9es sur le th\u00e9or\u00e8me PCP
Examen :<\/p>\n\n\n\nTD1_08.pdf<\/a>\u00a0: algo de Markov
TD2_08.pdf<\/a>\u00a0: PRIMES, simulation efficace par une machine de Turing universelle, machine oblivious
TD3_08.pdf<\/a>\u00a0: Ladner, simulation efficace par une machine de Turing non d\u00e9terministe universelle
TD4_08.pdf<\/a>\u00a0: fonctions constructibles en temps, langages unaires, langages creux
TD5_08.pdf<\/a>\u00a0: reprend le TD4 et rajoute des exercices sur la constructibilit\u00e9 en temps et en espace
TD6_08.pdf<\/a>\u00a0: le jeu de GO est PSPACE-complet
TD7_08.pdf\u00a0: machines alternantes
TD8_08.pdf\u00a0: des circuits et des cailloux
TD9_08.pdf<\/a>\u00a0: des circuits et des cailloux, suite
TD10_08.pdf<\/a>\u00a0: P\/poly
TD11_08.pdf<\/a>\u00a0: probl\u00e8mes P-complets et P-SEL
TD12_08.pdf<\/a>\u00a0: pi\u00e8ces biais\u00e9es, BPL, RL, r\u00e9ductions randomis\u00e9s, th de r\u00e9duction des erreurs pour RP
TD13_08.pdf<\/a>\u00a0: IP et permanent
TD14_08.pdf<\/a>\u00a0: IP, AM, zero-knowledge<\/p>\n\n\n\nPartiel.pdf<\/a>
examen.pdf<\/a><\/p>\n\n\n\n
Bibliographie :<\/p>\n\n\n\n- Sanjeev Arora et Boaz Barak : Complexity Theory: A Modern Approach<\/a><\/li>
- C.H. Papadimitriou, Computational Complexity<\/em>, Addison-Wesley(1994)<\/li>
- Michael Sipser, Introduction to the theory of computation<\/em><\/li>
- Jos\u00e9 L. Balcazar, Josep Diaz, Joaquim Gabarro, Structural Complexity I<\/em><\/li><\/ul>\n\n\n\n
2007-2008<\/h1>\n\n\n\n
groupe de lecture<\/a> sur le calcul quantique<\/p>\n\n\n\n
FDI2 : Fondements de l’informatique, second semestre du L3
TD : Florent Becker et Romain Demangeon
Cours 1, mercredi 30 janvier 2008 : Les machines de Turing
Cours 2, mercredi 6 f\u00e9vrier 2008 : RAM
Cours 3, mercredi 13 f\u00e9vrier : fonctions r\u00e9cursives primitives
Cours 4, lundi 25 f\u00e9vrier : fonctions r\u00e9cursives, le probl\u00e8me de l’arr\u00eat
Cours 5, lundi 3 mars : th\u00e9or\u00e8me de l’arr\u00eat, machines universelles, th\u00e9or\u00e8me smn, th\u00e9or\u00e8me de Rice, premier th\u00e9or\u00e8me du point fixe de Kleene, syst\u00e8me acceptable de programmation
Cours 6, mercredi 12 mars : th\u00e9or\u00e8me de l’isomorphisme de Rogers, ensemble d’entiers r\u00e9cursifs et r\u00e9cursivement \u00e9num\u00e9rables
Cours 7, lundi 17 mars : le th\u00e9or\u00e8me de compacit\u00e9 du calcul des proposition, premi\u00e8res d\u00e9finitions du calcul des pr\u00e9dicats
partiel : lundi 24 mars
Cours 8, mercredi 26 mars : le th\u00e9or\u00e8me de compacit\u00e9 du calcul des pr\u00e9dicats, un peu de compl\u00e9tude
Cours 9, lundi 7 avril : le th\u00e9or\u00e8me de compl\u00e9tude du calcul des pr\u00e9dicats, construction des structures \u00e9galitaires
Cours 10, lundi 21 avril : Peano
Cours 11, lundi 28 avril : th\u00e9or\u00e8me de repr\u00e9sentation, arithm\u00e9tisation de la syntaxe
Cours 12, lundi 5 mai : codage des preuves, th\u00e9ories r\u00e9cursives
Cours 13, mercredi 7 mai (qui est un lundi de cours, pour remplacer le 12 mai) : les th\u00e9or\u00e8mes de G\u00f6del
Cours 14, lundi 19 mai : l’\u00e9limination des quanteurs dans les corps r\u00e9els clos, d’apr\u00e8s l’article de Christian Michaux et Adem Ozturk (voir la biblio ci-dessous).
examen vendredi 23 mai :
Bibliographie :<\/p>\n\n\n\n- Christian Michaux et Adem Ozturk, Quantifier Elimination following Muchniks<\/a> et une impl\u00e9mentation A Proof-Producing Decision Procedure for Real Arithmetic de Sean McLaughlin et John Harrison<\/li>
- Le cours<\/a> d’Elisabeth Bouscaren<\/li>
- Logique math\u00e9matique, Ren\u00e9 Cori et Daniel Lascar, deux tomes chez Dunod (et premi\u00e8re \u00e9dition Axiomes). Cours et exercices. Plusieurs exemplaires \u00e0 la biblioth\u00e8que.Dans le premier tome : Calcul propositionnel, Alg\u00e8bre de Boole, Calcul des pr\u00e9dicats, Th\u00e9or\u00e8mes de compl\u00e9tude. Second tome : R\u00e9cursivit\u00e9 (inclus les machines de Turing) , Formalisation de l’arithm\u00e9tique, th\u00e9or\u00e8mes de G\u00f6del, th\u00e9orie des ensembles, un peu de th\u00e9orie des mod\u00e8les. (\u00e0 la Bib)<\/li>
- Math\u00e9matiques de l’informatique, cours et exercices corrig\u00e9s (licence, maitrise, agr\u00e9gation), Patrick Dehornoy, chez Dunod. Il y en a 3 \u00e0 la biblioth\u00e8que. Il y a aussi d’autres livres du m\u00eame auteur, que je ne connais pas dont les titres sont proches des sujets du cours (\u00e0 la Bib)<\/li>
- Histoire d\u2019algorithmes : du caillou \u00e0 la puce ; Belin. A la bib aussi. Pour votre culture g\u00e9n\u00e9rale sur le sujet.<\/li>
- Langages formels, calculabilit\u00e9 et complexit\u00e9 : Licence et Master de math\u00e9matiques ou d’informatique, option informatique de l’agr\u00e9gation de math\u00e9matiques, Olivier Carton, Vuibert. (\u00e0 la Bib)<\/li>
- C.H. Papadimitriou, Computational Complexity<\/em>, Addison-Wesley(1994) (pour les machines de Turing principalement) (\u00e0 la Bib)<\/li>
- Introduction to the theory of Computation, Michael Sipser, PWS Publishing Company (\u00e0 la Bib)<\/li>
- le th\u00e9or\u00e8me de G\u00f6del, points sciences, \u00e9ditions du seuil (pour lire le texte de G\u00f6del, traduit)<\/li>
- La machine de Turing, points sciences, \u00e9ditions du seuil (pour lire le texte de Turing, traduit)<\/li>
- Une histoire de l’informatique, Philippe Breton, points sciences, \u00e9ditions du seuil (pour votre culture g\u00e9n\u00e9rale)<\/li><\/ul>\n\n\n\n
SIESTE<\/a><\/p>\n\n\n\n2006-2007<\/h1>\n\n\n\n
Calcul quantique
Master 2
Pour les \u00e9tudiants inscrits, voir le site formation de l’ENS Lyon<\/p>\n\n\n\n
SIESTE<\/a><\/p>\n\n\n\n2005-2006<\/h1>\n\n\n\n
Logique et complexit\u00e9 (th\u00e9orie des mod\u00e8les et complexit\u00e9 alg\u00e9brique)
Second semestre du master 1 de math\u00e9matiques approfondies de Lyon et du M1 d’informatique fondamentale
Cours : Franck Wagner<\/a> et
TD : Natacha Portier<\/p>\n\n\n\nTD1_06.pdf<\/a> (formules)
TD2_06.pdf<\/a> (morphisme)
TD3_06.pdf<\/a> (extension \u00e9l\u00e9mentaire)
TD4_06.pdf<\/a> (compacit\u00e9)
TD5_06.pdf<\/a> (saturation)(fait jusqu\u00e0 la fin de l’exo 2)
TD6_06.pdf<\/a> (\u00e9limination des quanteurs et mod\u00e8le compl\u00e9tion)
TD7 (partiel.ps<\/a> 2003)
partiel_06.pdf<\/a>
TD8_06.pdf<\/a> (d\u00e9but de la complexit\u00e9)
TD9_06.pdf<\/a> (autour de Spira)
TD10_06.pdf<\/a> (probl\u00e8mes bool\u00e9ens)
examen_06.ps<\/a><\/p>\n\n\n\nSources : voir les ann\u00e9es pr\u00e9c\u00e9dentes<\/p>\n\n\n\n
Probabilit\u00e9s et applications \u00e0 l’algorithmique
Second semestre du L3 d’informatique fondamentale
Cours : Pascal Koiran<\/a>
TD : Natacha Portier<\/a><\/p>\n\n\n\nTD1_06.pdf<\/a> (on r\u00e9vise les probas du lyc\u00e9e)(jusqu’\u00e0 l’exo 5 inclus)
TD2_06.pdf<\/a> (le collectionneur d’images)(jusqu’\u00e0 l’exo 3 inclus)
TD3_06.pdf<\/a> (th\u00e9or\u00e8me de Hardy Weinberg,corde de Bertrand, probl\u00e8me des menteurs, loi de succession de Laplace)(jusqu’\u00e0 l’exo 5 inclus)
TD4_06.pdf<\/a> (diverses lois discr\u00e8tes)(jusqu’\u00e0 l’exo 5 inclus sauf question 1)
TD5_06.pdf<\/a> (th\u00e9or\u00e8me des \u00e9v\u00e9nements rares de Poisson)(question 3 pas termin\u00e9e)
TD6_06.pdf<\/a> (entropie et codage)(jusqu’\u00e0 la fin de la question 2)
partiel<\/a> le 28 mars 2006, repouss\u00e9 \u00e0 la semaine suivante et remplac\u00e9 par des r\u00e9visions (fin des TD 2 et 5)
TD7_06.pdf<\/a> (le principe de Yao)
TD8_06.pdf<\/a> (fonctions g\u00e9n\u00e9ratrices)
TD9_06.ps<\/a> (cha\u00eenes de Markov, collectionneur de figurines) 9 mai
TD10_06.ps<\/a> (graphes al\u00e9atoires) TD virtuel le 16 mai
TD11_06.pdf<\/a> (marches al\u00e9atoire, processus de branchement de Galton-Watson) 23 mai
examen_06.ps<\/a><\/p>\n\n\n\nSources : voir les ann\u00e9es pr\u00e9c\u00e9dentes
partiel : http:\/\/www.les-mathematiques.net\/f\/p\/b\/node1.php3 (voir le fichier ici<\/a>)<\/p>\n\n\n\nCours Interdisciplinaire d’Information Quantique
Cours annuel propos\u00e9 aux L3 informaticiens, math\u00e9maticiens, biologistes et g\u00e9ologues
Cours : Pascal Degiovanni et Natacha Portier<\/p>\n\n\n\n2004-2005<\/h1>\n\n\n\n
Calcul quantique
Master 2 Premier semestre 2003-2004
<\/p>\n\n\n\nLogique et complexit\u00e9 (th\u00e9orie des mod\u00e8les et complexit\u00e9 alg\u00e9brique)
Second semestre du master 1 de math\u00e9matiques approfondies de Lyon
Cours et TD : Franck Wagner<\/a> et Natacha Portier<\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- Cours et exercices des ann\u00e9es pr\u00e9c\u00e9dentes se trouvent sur la page de Frank Wagner<\/a><\/li>
- TD 93-94, Anatole Kh\u00e9lif<\/li>
- Logique math\u00e9matique tomes 1 et 2, Ren\u00e9 Cori et Daniel Lascar, Dunod<\/li>
- Cours de Th\u00e9orie des mod\u00e8les, B. Poizat, et la version anglaise (version russe ici<\/a>)<\/li>
- B. Poizat, Les petits cailloux<\/em>, ALEAS<\/li><\/ul>\n\n\n\n
Groupe de lecture de Calcul quantique du L3 de math\u00e9matiques<\/p>\n\n\n\n
2003-2004<\/h1>\n\n\n\n
Complexit\u00e9 descriptive et mod\u00e8les finis
Premier semestre 2003-2004 du MIM2
(cours de base du futur Master)
Cours : Jacques Mazoyer
TD : Natacha Portier<\/a><\/p>\n\n\n\nTD1_03.ps<\/a>, TD1_03.dvi<\/a> (formules et logique du premier ordre)
TD2_03.ps<\/a>, TD2_03.dvi<\/a> (La logique du premier ordre exprime des propri\u00e9t\u00e9s locales)
TD3_03.ps<\/a>, TD3_03.dvi<\/a> (Une loi z\u00e9ro-un \u00e9tiquet\u00e9e)
TD4_03.ps<\/a>, TD4_03.dvi<\/a> (loi z\u00e9ro-un non \u00e9tiquet\u00e9e, deux s\u00e9ances)
TD5_03.ps<\/a>, TD5_03.dvi<\/a> (description logique d’un calcul)
TD6_03.ps<\/a>, TD6_03.dvi<\/a> (description logique d’un calcul, suite)
partiel_03.ps<\/a>, partiel_03.dvi<\/a>
TD7_03.ps<\/a>, TD7_03.dvi<\/a> (description logique d’un calcul, r\u00e9ciproque du th\u00e9or\u00e8me)
TD8_03.ps<\/a>, TD8_03.dvi<\/a> (pos TC=TC)
TD9_03.ps<\/a>, TD9_03.dvi<\/a> (capture et capture forte)
TD10_03.ps<\/a>, TD10_03.dvi<\/a> (optimisation)<\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- Les TD de Herv\u00e9 Fournier<\/a><\/li>
- Finite Model Theory, Ebbinghaus Flum, Springer<\/li>
- Descriptive complexity and Finite Models, Immerman and Kolaitis Editors, AMS, 1997<\/li>
- Descriptive complexity, Immerman, Springer, 1998<\/li><\/ul>\n\n\n\n
Calcul quantique
DEA Premier semestre 2003-2004
(cours de recherche du futur Master)<\/p>\n\n\n\n2002-2003<\/h1>\n\n\n\n
Logique et complexit\u00e9 (th\u00e9orie des mod\u00e8les et complexit\u00e9 alg\u00e9brique)
Second semestre 2002-2003 de la ma\u00eetrise de maths de Lyon I
Cours : Bruno Poizat
TD : Natacha Portier<\/a><\/p>\n\n\n\nTD1_03.ps<\/a>,\u00a0TD1_03.dvi<\/a>\u00a0(formules et logique du premier ordre)
TD2_03.ps<\/a>,\u00a0TD2_03.dvi<\/a>
TD3_03.ps<\/a>,\u00a0TD3_03.dvi<\/a>
TD4_03.ps<\/a>,\u00a0TD4_03.dvi<\/a>\u00a0(application du th\u00e9or\u00e8me de compacit\u00e9, th\u00e9or\u00e8me de Vaught)
TD5 : petite introduction \u00e0 la th\u00e9orie des ensembles.\u00a0 Je me suis appuy\u00e9e sur le cours trouv\u00e9\u00a0d’Alexandre Rambaud\u00a0(voir sources):\u00a0fichier1.pdf<\/a>,\u00a0fichier2.pdf<\/a>,\u00a0fichier3.pdf<\/a>,\u00a0fichier4.pdf<\/a>. On pourra \u00e9galement consulter les notes enrichies d’Emmanuel Jaendel (voir sources).
TD6_03.ps<\/a>,\u00a0TD6_03.dvi<\/a>
TD7_03.ps<\/a>,\u00a0TD7_03.dvi<\/a>\u00a0(les corps r\u00e9els clos)
partiel_03.ps<\/a>,\u00a0partiel_03.dvi<\/a>
8, cours et TD : les machines de Turing et les circuits sur une structure alg\u00e9brique quelconque
TD9_03.ps<\/a>,\u00a0TD9_03.dvi<\/a>\u00a0 : grande feuille sur le cours pr\u00e9c\u00e9dent
TD10_03.ps<\/a>,\u00a0TD10_03.dvi<\/a>\u00a0 : les probl\u00e8mes bool\u00e9ens dans diverses structures
vacances, 1er mai, 8 mai
examen le jeudi 15 mai de 14h \u00e0 17h amphi B ens Lyon
\u00a0<\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- Cours et exercices 2000-2001 et 2001-2002 se trouvent sur la page de Frank Wagner<\/li>
- Notes enrichies<\/a> du cours pr\u00e9c\u00e9dent, par Emmanuel Jeandel<\/li>
- TD 93-94, Anatole Kh\u00e9lif<\/li>
- Logique math\u00e9matique tomes 1 et 2, Ren\u00e9 Cori et Daniel Lascal, Dunod<\/li>
- Page d’Alexandre Rambaud pour le cours de th\u00e9orie des ensembles, fait \u00e9galement par Julien Page.<\/li>
- Jean-Louis Krivine, Th\u00e9orie des ensembles, Cassini<\/li>
- Cours de Th\u00e9orie des mod\u00e8les, B. Poizat, et la version anglaise<\/li>
- B. Poizat, Les petits cailloux<\/em>, ALEAS<\/li><\/ul>\n\n\n\n
DEA : Calcul quantique, voir\u00a0ici<\/p>\n\n\n\n
2001-2002<\/h1>\n\n\n\n
Probabilit\u00e9s et applications \u00e0 l’algorithmique
Second semestre 2001-2002 du MIM premi\u00e8re ann\u00e9e.
Cours : Pascal Koiran<\/a>
TD : Natacha Portier<\/a><\/p>\n\n\n\nTD1_02.ps<\/a>, TD1_02.dvi<\/a>(combinatoire)
TD2_02.ps<\/a>, TD2_02.dvi<\/a>(probabilit\u00e9s conditionnelles)
TD3_01.ps<\/a> , TD3_02.dvi<\/a> (encore un peu des deux)
TD4_02.ps<\/a> , TD4_02.dvi<\/a>(variables al\u00e9atoires discr\u00e8tes)
TD5_02.ps<\/a> , TD5_02.dvi<\/a>(variables al\u00e9atoires discr\u00e8tes)
TD6_02.ps<\/a> , TD6_02.dvi<\/a>(entropie de Shannon et codages)
TD7_02.ps<\/a> , TD7_02.dvi<\/a>(suite et th\u00e9orie des questionnaires)
TD8_02.ps<\/a> , TD8_02.dvi<\/a>(s\u00e9ries g\u00e9n\u00e9ratrices)
TD9_02.ps<\/a> , TD9_02.dvi<\/a>(cha\u00eenes de Markov)
partiel_02.ps<\/a> , partiel_02.dvi<\/a>(tables de hachage, marche au hasard en dimension plus que 3)
TD10_02.ps<\/a> , TD10_02.dvi<\/a>(processus de Galton-Watson)
TD11_02.ps<\/a> , TD11_02.dvi<\/a>(la ruine du joueur)
TD12_02 : correction du partiel, examen de l’ann\u00e9e derni\u00e8re
TD13_02.ps<\/a>, TD13_02.dvi<\/a> (le principe de Yao)
examen02.ps<\/a><\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- celles des ann\u00e9es pr\u00e9c\u00e9dentes;<\/li>
- Game Theory, Guillermo Owen, second edition, Academic Press, 1982<\/li><\/ul>\n\n\n\n
Mod\u00e8les de calcul et complexit\u00e9
Second semestre 2001-2002 du MIM premi\u00e8re ann\u00e9e.
Cours : Marianne Delorme
TD : Natacha Portier<\/a><\/p>\n\n\n\nTD1_02.ps<\/a>, TD1_02.dvi<\/a> (algorithmes de Markov)
TD2_02.ps<\/a>, TD2_02.dvi<\/a> (RAM)
TD3_02.ps<\/a> , TD3_02.dvi<\/a> (syst\u00e8mes de programmation acceptables, fonctions bool\u00e9ennes),
TD4_02.ps<\/a> , TD4_02.dvi<\/a> (r\u00e9visions de calculabilit\u00e9),
TD5_02.ps<\/a> , TD5_02.dvi<\/a> (circuits booleens),
TD6_02.ps<\/a> , TD6_02.dvi<\/a> (un probl\u00e8me P-complet),
TD7_02.ps<\/a> , TD7_02.dvi<\/a> (probl\u00e8mes espaceP-complet),
TD8_02.ps<\/a> , TD8_02.dvi<\/a> (suites de circuits),
TD9_02.ps<\/a> , TD9_02.dvi<\/a> (relativisations de P=NP avec des oracles),
partiel_02.ps<\/a> , partiel_02.dvi<\/a> (P-sel)
TD10_02.ps<\/a> , TD10_02.dvi<\/a> (fonctions constructibles en espace, compressions, fonctions constructibles en temps),
TD11_02.ps<\/a> , TD11_02.dvi<\/a> (classes de complexit\u00e9 probabilistes)
TD12_02 : correction du partiel et examen 2001
TD13_02 : examen 2000<\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- Hemaspandra, Ogihara The complexity Theory Companion<\/em>,<\/li>
- Celles des ann\u00e9es pr\u00e9c\u00e9dentes ;<\/li><\/ul>\n\n\n\n
Algorithmique
Premier semestre 2001-2002 du MIM premi\u00e8re ann\u00e9e.
Cours : Yves Robert<\/a>
TD : Olivier Bodini<\/a>, Natacha Portier<\/a><\/p>\n\n\n\nTD1_01.dvi<\/a>, TD1_01.ps<\/a> (recherche du plus grand, du plus petit et du plus grand simultan\u00e9ment, optimalit\u00e9)
TD2_01.dvi<\/a>, TD2_01.ps<\/a> (recherche de l’\u00e9l\u00e9ment majoritaire)
TD3_01.dvi<\/a>, TD3_01.ps<\/a> (optimalit\u00e9 pour la recherche du majoritaire, matrices de Toeplitz, location de skis)
DM1_01.ps<\/a> ( quelle est la bonne clef ?)
TD4_01.dvi<\/a>, TD4_01.ps <\/a>(programmation dynamique)
TD5_01.dvi<\/a>, TD5_01.ps <\/a>(recherche du m\u00e9dian)
partiel : le 24 octobre \u00e0 l’heure du cours
TD6 : correction du partiel
DM2_01.dvi<\/a>, DM2_01.ps<\/a> (le fromage)
TD7_01.dvi<\/a>, TD7_01.ps <\/a>(codage de Huffman)
TD8_01.dvi<\/a>, TD8_01.ps <\/a>(recherche de motifs avec des automates finis et Rabin-Karp)
TD9_01.dvi<\/a>, TD9_01.ps <\/a>(recherche de motifs avec Knuth-Morris-Pratt et Boyer-Moore)
TD10_01.ps <\/a>(tables de hachage)
TD11_01.dvi<\/a>, TD11_01.ps <\/a>(algorithme de Sturm, NP-compl\u00e9tude : 2-SAT, NAE, OIT)
TD12_01.dvi<\/a>, TD12_01.ps <\/a>(somme d’un sous-ensemble, partition)
TD13_01.ps <\/a>(examen 2000-2001)
examen_01.ps<\/a><\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- Celles des ann\u00e9es pr\u00e9c\u00e9dentes ;<\/li>
- Math\u00e9matiques pour le langage formel, Maurice Mignotte, PUF 1989 ;<\/li><\/ul>\n\n\n\n
s\u00e9minaire du MIM 2001-2002<\/p>\n\n\n\n
2000-2001<\/h1>\n\n\n\n
Probabilit\u00e9s et applications \u00e0 l’algorithmique
Second semestre 2000-2001 du MIM premi\u00e8re et deuxi\u00e8me ann\u00e9e.
Cours : Pascal Koiran<\/a>
TD : Natacha Portier<\/a><\/p>\n\n\n\nTD1_01.ps<\/a>\u00a0(combinatoire)
TD2_01.ps<\/a>\u00a0(probabilit\u00e9s conditionnelles)
TD3_01.ps<\/a>\u00a0(encore un peu des deux)
TD4_01.ps<\/a>\u00a0(variables al\u00e9atoires discr\u00e8tes)
TD5_01.ps<\/a>\u00a0(variables al\u00e9atoires discr\u00e8tes, suite)
TD6_01.ps<\/a>\u00a0(th\u00e9orie de l’information et entropie de Shannon)
partiel_01.ps<\/a>
L’article original de Shannon.
Le probl\u00e8me des douze pi\u00e8ces \u00e0 regarder\u00a0sur www.ac-orleans-tours.fr (le lien n’existe plus)
TD7_01.ps<\/a>\u00a0(th\u00e9orie des questionnaires)
TD8_01.ps<\/a>\u00a0(marches al\u00e9atoires et chaines de Markov)
TD9_01.ps<\/a>\u00a0(fonctions g\u00e9n\u00e9ratrices)
TD10_01.ps<\/a>\u00a0(processus de branchement : Galton-Watson ; souris ; jeu de Tennis)
TD11_01.ps<\/a>\u00a0(la ruine du joueur)
exam_01.ps<\/a><\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- Introduction aux probabilit\u00e9s, P. Br\u00e9maud, Springer-Verlag 1984<\/li>
- Markov Chains, Gibbs Fields, Monte-Carlo Simulation and queues, P. Br\u00e9maud, Springer 1999 <\/li>
- exercices de probabilit\u00e9s, Marie Cottrell, Valentine Genon-Catalot, Christian Duhamel, Thierry Meyre, Cassini 1999<\/li>
- exercices ordinaires de probabilit\u00e9s, G\u00e9rard Frugier, ellipses<\/li>
- An introduction to probability theory and its applications, vol. 1, William Feller, Jon Wiley & Sons<\/li><\/ul>\n\n\n\n
Mod\u00e8les de calcul et complexit\u00e9
Second semestre 2000-2001 du MIM premi\u00e8re ann\u00e9e.
Cours : Marianne Delorme
TD : Natacha Portier<\/a><\/p>\n\n\n\nTD1_01.ps<\/a> (algorithmes de Markov)
TD2_01.ps<\/a>(RAM)
TD3_01.ps<\/a>(syst\u00e8mes de programmation acceptables, r\u00e9cursivit\u00e9)
TD4_01.ps<\/a> (les circuits bool\u00e9ens)
TD5_01.ps<\/a> (probl\u00e8mes ESPACE-P-complets)
partiel_01.ps<\/a>
TD6_01.ps<\/a> (probl\u00e8mes P-complets)
TD7_01.ps<\/a> (fonctions constructibles en espace, compressions, fonctions constructibles en temps)
TD8_01.ps<\/a> (relativisations de P=NP avec oracles)
TD9_01.ps<\/a> (classes probabilistes)
examen<\/a> (p-isomorphisme)<\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- Celles de l’ann\u00e9e 1999-2000 ;<\/li><\/ul>\n\n\n\n
Algorithmique
Premier semestre 2000-2001 du MIM premi\u00e8re ann\u00e9e.
Cours : Yves Robert<\/a>
TD : Daniel Hirschkoff<\/a>, Natacha Portier<\/a><\/p>\n\n\n\nTD1_00.dvi<\/a>,\u00a0TD1_00.ps<\/a>\u00a0(recherche du plus grand, du plus petit et du plus grand simultan\u00e9ment, optimalit\u00e9)
TD2_00.dvi<\/a>,\u00a0TD2_00.ps<\/a>\u00a0(algorithme de majorit\u00e9 : quadratique, nlogn et lin\u00e9aire)
TD3_00.dvi<\/a>,\u00a0TD3_00.ps<\/a>\u00a0(algorithme de majorit\u00e9 : l’optimal ; recherche du deuxi\u00e8me plus grand ; matrices de Toeplitz)
TD4_00.dvi<\/a>,\u00a0TD4_00.ps<\/a>(programmation dynamique)
Devoir(.dvi)<\/a>,\u00a0Devoir(.ps)<\/a>\u00a0en temps libre (Mariages) et sa\u00a0correction(.ps)<\/a>.
TD5_00.dvi<\/a>,\u00a0TD5_00.ps<\/a>\u00a0(arbres binaires de recherche, rouges et noirs, B-arbres), une partie du corrig\u00e9\u00a0rbtrees.ml<\/a>
TD6 : correction du\u00a0partiel<\/a>, une partie du\u00a0corrig\u00e9(.ps)<\/a>
TD7_00.dvi<\/a>,\u00a0TD7_00.ps<\/a>\u00a0(Recherche du quanti\u00e8me, m\u00e9dian pond\u00e9r\u00e9, bureau de poste et champ p\u00e9trolier), une partie du\u00a0corrig\u00e9(.ps)<\/a>
TD8_00.dvi<\/a>,\u00a0TD8_00.ps<\/a>\u00a0(codage de Huffman)
TD9_00.ps<\/a>\u00a0(coloriages et p\u00e9rim\u00e8tres, partiel 99)
TD10_00.ps<\/a>\u00a0(nombre de coloriages, variantes de SAT)
TD11_00.ps<\/a>\u00a0(NP-compl\u00e9tude de coloriages)
TD12_00.ps<\/a>\u00a0(Couverture des sommets d’un graphe, somme d’un sous-ensemble, partition)
TD13_00.ps<\/a>\u00a0(Recherche de motifs : automates finis, algorithme de Knuth, Morris, Pratt et algorithme de Rabin-Karp)
examen00.ps<\/a>(tas d-aire, i plus grands \u00e9l\u00e9ments tri\u00e9s, vertex cover avec degr\u00e9 pair, 2-partition avec meme cardinal, clique pour graphe r\u00e9gulier, approximation du sac \u00e0 dos)<\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- Celles de l’ann\u00e9e 1999-2000 ;<\/li>
- Pour les algorithmes de majorit\u00e9 : sujet d’oral d’\u00a0Al<\/a>ain Darte<\/a>, article de Fischer et Salzberg, Journal of Algorithms, Vol. 3, pages 376-379, 1982.<\/li>
- Pour le devoir sur les mariages : sujet d’oral de\u00a0Pascal Koiran<\/a>, d’apr\u00e8s\u00a0Introduction to Graph Theory<\/em>\u00a0de D. West<\/li><\/ul>\n\n\n\n
s\u00e9minaire du MIM 2000-2001<\/p>\n\n\n\n
1999-2000<\/h1>\n\n\n\n
Algorithmique
Premier semestre 1999-2000 du MIM premi\u00e8re ann\u00e9e.
Cours : Yves Robert<\/a>
TD : Daniel Hirschkoff<\/a>, Natacha Portier<\/a><\/p>\n\n\n\nTD1_99.dvi<\/a>,\u00a0TD1_99.ps<\/a>\u00a0(recherche du plus grand, du deuxi\u00e8me plus grand, du plus petit et du plus grand simultan\u00e9ment)
TD2_99.dvi<\/a>,\u00a0TD2_99.ps<\/a>\u00a0(m\u00e9thode de l’oracle pour l’algorithme pr\u00e9c\u00e9dent, r\u00e9solution de r\u00e9currences)
TD3_99.dvi<\/a>,\u00a0TD3_99.ps<\/a>\u00a0(programmation dynamique)
TD4_99.dvi<\/a>,\u00a0TD4_99.ps<\/a>\u00a0(codage de Huffman)
TD5_99.ps\u00a0<\/a>(B-arbres)
TD6_99.dvi<\/a>,\u00a0TD6_99.ps<\/a>\u00a0(coloriages)
TD7_99.dvi<\/a>,\u00a0TD7_99.ps<\/a>\u00a0(Tas de Fibonacci, analyse amortie)
TD8_99.dvi<\/a>,\u00a0TD8_99.ps<\/a>\u00a0(Recherche du quanti\u00e8me, m\u00e9dian pond\u00e9r\u00e9, bureau de poste et champ p\u00e9trolier)
TD9_99.dvi<\/a>,\u00a0TD9_99.ps<\/a>\u00a0(composantes fortement connexes d’un graphe, 2-SAT, SAT-2)
TD10_99.ps<\/a>\u00a0(coloriages de graphes)
cours(.dvi)<\/a>,\u00a0cours(.ps)<\/a>\u00a0du 14-12-1999 (Le th\u00e9or\u00e8me de Stockmeyer et Meyer)
TD11_99.dvi<\/a>,\u00a0TD11_99.ps<\/a>\u00a0(Couverture des sommets d’un graphe, somme d’un sous-ensemble, partition)
TD12_99.dvi<\/a>,\u00a0TD12_99.ps<\/a>\u00a0(Recherche de motifs : Rabin-Karp et automates finis)
TD13_99.dvi<\/a>,\u00a0TD13_99.ps<\/a>\u00a0(Algorithme de Knuth, Morris, Pratt pour la recherche de motifs)
Devoir(.dvi)<\/a>,\u00a0Devoir(.ps)<\/a>\u00a0en temps libre (bases de Gr\u00f6bner)
partiel(.ps)<\/a>
Examen(.ps)
\u00a0<\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- Les fiches des TDmen de l’ann\u00e9e pr\u00e9c\u00e9dente Matthieu Exbrayat et Codrin Nichitiu, et les notes d’Yves Robert<\/a>.<\/li>
- Les documents qui ont servi de base de travail pour faire passer l’\u00e9preuve orale d’Informatique commune aux trois ENS Cachan, Lyon, et Ulm en 1999 (\u00e0 r\u00e9cup\u00e9rer ici<\/a>).<\/li>
- T. Cormen et al., Introduction \u00e0 l’algorithmique<\/em>, Dunod<\/li>
- …<\/li><\/ul>\n\n\n\n
Mod\u00e8les de calcul et complexit\u00e9
Second semestre 1999-2000 du MIM premi\u00e8re ann\u00e9e.
Cours : Marianne Delorme
TD : Natacha Portier<\/a><\/p>\n\n\n\nTD1.dvi<\/a> (algorithmes de Markov),
TD2.dvi<\/a> (RAM),
TD3.dvi<\/a> (syst\u00e8mes de programmation acceptables, fonctions bool\u00e9ennes),
TD4.dvi<\/a> (r\u00e9cursivit\u00e9, parall\u00e9lisation de l’addition),
TD5.dvi<\/a> (les circuits bool\u00e9ens),
TD6.dvi<\/a> (les circuits r\u00e9els),
TD7.dvi<\/a> (le jeu de la g\u00e9ographie),
TD8.dvi<\/a> (jeu de GO, autres probl\u00e8mes ESPACE-P-complets),
partiel.dvi <\/a>(probl\u00e8mes p\u00e9riodiques ESPACE-P-complets),
TD9.dvi<\/a> (fonctions constructibles en espace, compression de l’espace, des rubans, du temps),
TD10.dvi<\/a> (compression en temps des rubans, fonctions constructibles en temps),
TD11.dvi<\/a> (suite de circuit uniforme polynomiale, classe NC),
TD12.dvi<\/a> (classes probabilistes RP, PP, BPP)
exam00.ps<\/a> (examen)<\/p>\n\n\n\nSources :<\/p>\n\n\n\n
- C.H. Papadimitriou, Computational Complexity<\/em>, Addison-Wesley(1994)<\/li>
- B. Poizat, Les petits cailloux<\/em>, ALEAS<\/li>
- J.E. Hopcroft et J.D. Ullman, Introduction to Automata Theory, languages, and Computation<\/em><\/li>
- M. Machtey, P. Young, An Introduction to the General Theory of Algorithms<\/em><\/li>
- Daniel Pierre Bovet, Pierluigi Crescenzi, Introduction to the Theory of Complexity<\/em><\/li>
- …<\/li><\/ul>\n\n\n\n
- B. Poizat, Les petits cailloux<\/em>, ALEAS<\/li>
- Les documents qui ont servi de base de travail pour faire passer l’\u00e9preuve orale d’Informatique commune aux trois ENS Cachan, Lyon, et Ulm en 1999 (\u00e0 r\u00e9cup\u00e9rer ici<\/a>).<\/li>
- Pour le devoir sur les mariages : sujet d’oral de\u00a0Pascal Koiran<\/a>, d’apr\u00e8s\u00a0Introduction to Graph Theory<\/em>\u00a0de D. West<\/li><\/ul>\n\n\n\n
- Celles de l’ann\u00e9e 1999-2000 ;<\/li><\/ul>\n\n\n\n
- Celles des ann\u00e9es pr\u00e9c\u00e9dentes ;<\/li><\/ul>\n\n\n\n
- Hemaspandra, Ogihara The complexity Theory Companion<\/em>,<\/li>
- Le cours<\/a> d’Elisabeth Bouscaren<\/li>
- C.H. Papadimitriou, Computational Complexity<\/em>, Addison-Wesley(1994)<\/li>
- Raymond M. Smullyan, Godel’s Incompleteness Theorems<\/em>, 1992, Les th\u00e9or\u00e8mes d’incompl\u00e9tude de G\u00f6del<\/em>, Dunod, 2000<\/li>
- C.H. Papadimitriou,\u00a0Computational Complexity<\/em>, Addison-Wesley(1994)<\/li>
- Sanjeev Arora et Boaz Barak :\u00a0Complexity Theory: A Modern Approach<\/a><\/li>
- L\u2019\u00e9limination des quantificateurs dans les corps alg\u00e9briquement clos Cours 13<\/strong><\/li><\/ol><\/li><\/ol>\n\n\n\n
- L\u2019\u00e9limination des quantificateurs dans les corps r\u00e9els clos Cours 12<\/strong><\/li>
- Le th\u00e9or\u00e8me de compl\u00e9tude Cours 5<\/strong><\/li><\/ol><\/li>