2014-2015
Logique, cours de L3, second semestre
Plan du cours (les numéros de cours ne sont pas toujours respectés à la lettre)
- Le calcul propositionnel et son théorème de compacité. Cours 1
- La syntaxe de la logique du premier ordre et les preuves en déduction naturelle Cours 2
- La sémantique de la logique du premier ordre : interprétation (modèle), vérité, morphismes Cours 3
- Le théorème de complétude de Gödel Lien entre la syntaxe et la sémantique.
- Le théorème de correction Cours 4
- Le théorème de complétude Cours 5
- Le théorème de compacité. Quelques applications.
- L’arithmétique de Peano Cours 6
- Les théorèmes d’incomplétude de Gödel Cours 7 et 8
- L’arithmétisation de la syntaxe
- Les théorèmes de Tarski, Gödel
- La théorie des ensembles Cours 9 à 11
- La théorie naïve des ensembles et la définition des ordinaux
- Les axiomes de Zermelo-Fraenkel
- L’axiome du choix et l’axiome de fondation
- Applications selon le temps qu’il reste
- L’élimination des quantificateurs dans les corps réels clos Cours 12
- L’élimination des quantificateurs dans les corps algébriquement clos Cours 13
Bibliographie pour le cours:
- Logique mathématique, René Cori et Daniel Lascar, deux tomes chez Dunod (et première édition Axiomes). Cours et exercices. Plusieurs exemplaires à la bibliothèque. Dans le premier tome : Calcul propositionnel, Algèbre de Boole, Calcul des prédicats, Théorèmes de complétude. Second tome : Récursivité (inclus les machines de Turing) , Formalisation de l’arithmétique, théorèmes de Gödel, théorie des ensembles, un peu de théorie des modèles. (à la Bib)
- Introduction à la logique, Théorie de la démonstration, René David, Karim Nour et Christophe Raffalli, Dunod (à la Bib)
- cours de Zoe Chatzidakis (cours de logique, automne 2014)
- Jean-Louis Krivine, théorie des ensembles (chez Cassini, ou la vieille version aux PUF)
- Le cours sur le théorème de Gödel d’Alexandre Miquel
- Quantifier Elimination following Muchnik, Christian Michaux et Adem Ozturk
Bibliographie pour la plage :
- Logicomix : an epic search for the truth (roman graphique disponible en français et en anglais à la bibliothèque)
- La logique, Gilles Dowek, Dominos Flammarion
- et pourtant… ils ne remplissent pas N ! Claude Lobry (à la bib)
- Le théorème de Gödel, point sciences, Ernest Nagel/James R. Newman, Kurt Gödel/Jean-Yves Girard
Physique et Calcul Quantique : accessible pour les étudiants de l’ENS Lyon sur http://etudes.ens-lyon.fr/, Sciences de la matière, L3 SdM, Deuxième semestre, Physique , Information et Calcul
2013-2014
Logique, cours de L3, second semestre : partiel, examen
Physique et Calcul Quantique : accessible pour les étudiants de l’ENS Lyon sur http://etudes.ens-lyon.fr/, Sciences de la matière, L3 SdM, Deuxième semestre, Physique , Information et Calcul
Complexité Algorithmique, cours de base de Master, premier semestre
2012-2013
Complexité Algorithmique, cours de base de Master, premier semestre
Cours 1, mardi 11 septembre : Rappels sur les machines de Turing, DTIME, P et NP
Cours 2, mardi 18 septembre : le théorème de Cook et les codages des calculs de machines de Turing
Cours 3 vendredi 21 septembre :co-NP , EXP, NEXP, théorème de hiérarchie en temps déterministe, machine de Turing non-déterministe universelle
Cours 4 vendredi 28 septembre : théorème de hiérarchie en temps non déterministe, théorème de Ladner (preuve en TD), machines à oracle et théorèmes de relativisation de P=NP
Cours 5 vendredi 5 octobre : complexité en espace, graphe de configuration, théorème de hiérarchie en espace, TQBF est PSPACE, théorème de Savitch (preuve en TD)
Cours 6 vendredi 26 octobre : NL-complétude, NL=co-NL
Cours 7, vendredi 9 novembre : Deux définitions de la hiérarchie polynomiale, énoncé du théorème de compromis espace-temps pour SAT
Cours 8, vendredi 16 novembre : preuve du théorème de compromis espace-temps pour SAT, définition de la hiérarchie polynomiale avec les oracles, début des classes de complexité définies avec les circuits
Cours 9, vendredi 23 novembre : P/poly, théorème de Karp-Lipton (NP \subset P/poly implies PH=\Sigma_2^p), théorème de Meyer (EXP \subset P/poly implies EXP=\Sigma_2^p)
Cours 10, vendredi 30 novembre : classes de complexité probabilistes (BPP, polynomial identity testing, RP, ZPP)
Cours 11, vendredi 7 décembre : suite des classes probabilistes ( théorème de réduction des erreurs, espérance du temps de calcul, BPP inclus dans P/poly, BPP inclus dans Sigma_2^p inter Pi_2^p, simulation de pièce biaisée, réduction probabiliste, AM)
Cours 12, vendredi 21 décembre : quelques notions sur les classes de comptage
TD : Sébastien Tavenas
TD1 vendredi 14 septembre : réduction à 2 rubans et à 1 ruban
DM1 : réduction de l’alphabet, passage à un demi-ruban
TD2 :
2011-2012
FDI : Fondements de l’informatique, premier semestre du L3
cours : Pascal Koiran
TD : Sébastien Tavenas et Natacha Portier
Complexité Algorithmique, cours de base de Master, premier semestre
TD : Bruno Grenet
Bibliographie :
- Sanjeev Arora et Boaz Barak : Complexity Theory: A Modern Approach
- C.H. Papadimitriou, Computational Complexity, Addison-Wesley(1994)
- Michael Sipser, Introduction to the theory of computation
- José L. Balcazar, Josep Diaz, Joaquim Gabarro, Structural Complexity
Physique et information quantique, cours d’option du M1 de physique (cours avec Pascal Degiovanni)
2008-2009
FDI2 : Fondements de l’informatique, second semestre du L3
TD : Ivan Morel et Irénée Briquel
Cours 1, mardi 27 janvier : les machines de Turing
Cours 2, mardi 3 février : les Random Access Machines
Cours 3, mardi 10 février : les fonctions récursives primitives
Cours 4, mardi 24 février : les fonctions récursives
Cours 5, mardi 3 mars : les systèmes acceptables de programmation et leurs propriétés : codage de machines et de configurations, théorème de l’arrêt, machines universelles, théorème smn, théorème de Rice, théorèmes du point fixe de Kleene
Cours 6, mardi 10 mars : définition des systèmes acceptables de programmation, théorème de l’isomorphisme de Rogers, ensembles d’entier énumérables et récursivement énumérables
Cours 7, mardi 17 mars : le calcul propositionnel, le théorème de compacité du calcul propositionnel
Cours 8, mardi 24 mars : le calcul des prédicats, le théorème de complétude et le théorème de compacité du calcul des prédicats
partiel le 31 mars
Cours à la maison : ce cours
Cours 9, mardi 7 avril : Le théorème de Tarski : dans le langage de l’arithmétique avec exponentielle, la théorie de N n’est pas définissable (d’après Smullyan)
Cours 10, mardi 21 avril : Le théorème de Gödel pour l’arithmétique avec l’exponentielle (d’après Smullyan)
Cours 11, mardi 28 avril : Le théorème de Gödel pour l’arithmétique sans l’exponentielle (d’après Smullyan)
Cours 12, mardi 5 mai : l’indécidabilité du problème de Post (d’après le Hopcroft, Motwani, Ullman)
Sur le 10ème pb de Hilbert : voir wikipedia et le livre de Matiiassevitch (voir la bibliographie)
Cours 13, mardi 12 mai : l’élimination des quanteurs dans les corps réels clos, d’après l’article de Christian Michaux et Adem Ozturk (voir la biblio).
mardi 26 mai 9h-12h : exam
TD1_09.pdf : machines de Turing
TD2_09.pdf : RAM
TD3_09.pdf : fonctions récursives
TD4_09.pdf : Ackermann et fonctions récursives
TD5_09.pdf : Turing, le retour, et SAP
TD6_09.pdf : Sur Kleene, snm et ensembles récursivement énumérables
TD7_09.pdf : Calcul propositionnel
Partiel_09.pdf , correction des exos 1 et 4
TD8_09.pdf : Calcul des prédicats
TD9_09.pdf : Théorie des modèles
TD10_09.pdf : Peano et ses modèles
TD11_09.pdf : re-Peano, Gödel, …
TD12_09.pdf : castor affairé, ambiguité des grammaires algébriques, tuiles de Wang
TD13_09.pdf : révisions
examen_09.pdf
Bibliographie :
- celle de l’année dernière
- La bibliographie pour l’option info de l’agreg, à voir par ici.
- Raymond M. Smullyan, Godel’s Incompleteness Theorems, 1992, Les théorèmes d’incomplétude de Gödel, Dunod, 2000
- Logique et fondements de l’informatique, Hermes, Lassaigne et Rougemont
- Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addison Wesley (trouvable à la bib)
- Youri Matiiassevitch Le dixième problème de Hilbert: Son indécidabilité, Masson, (1995), ISBN : 2225848351
Calcul quantique, cours de recherche de Master, premier semestre
Complexité Algorithmique, cours de base de Master, premier semestre
TD : Irénée Briquel et Laurent Jouhet
Cours 0 : relire le cours de FDI2
Cours 1, mardi 16 septembre : classes de complexité Turing en temps
Cours 2, jeudi 18 septembre : NP, le théorème de Cook (voir chap 2 du Arora Barak)
Cours 3, jeudi 25 septembre : diagonalisation : théorèmes de hiérarchie déterministe et non déterministe en temps et théorème de Ladner (voir chap 3 du Arora Barak)
Cours 4, jeudi 9 octobre : les machines à oracle et la question P=NP relativisée, classes de complexité en espace, th de hierarchie
Cours 5, jeudi 16 octobre : Pspace, TQBF, théorème de Savitch, NL-complet
Cours 6, jeudi 23 octobre : NL=coNL, def de PH avec une généralisation des certificats, def de machine alternante
Cours 7 jeudi 30 octobre : compromis espace temps pour SAT (à compléter), définition de PH avec les machines à Oracle ; début des circuits booléens : 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ébut des classes de complexité probabilistes (BPP, polynomial identity testing)
Cours 10, jeudi 27 novembre : fin du chapitre sur les classes probabilistes : RP, ZPP, théorème de réduction des erreurs, espérance du temps de calcul, BPP inclus dans P/poly, BPP inclus dans Sigma_2^p inter Pi_2^p
Cours 11, jeudi 4 décembre : début du chapitre sur les protocoles interactifs, définition des protocoles déterministes et probabilistes, dIQ=NP, lemme de réduction des erreur, graphe non isomorphisme et résidu non quadratique sont dans IP[2], bla bla sur 01-NP_C dans AM
Cours 12, jeudi 11 décembre : début de la preuve IP=PSPACE
Cours 13, jeudi 18 décembre : fin de la preuve IP=PSPACE
Examen pour ceux qui partent au second semestre : jeudi 18 décembre de 15h à 18h dans la salle de conseil du LIP (320 bis) au troisième étage, un peu après l’amphi B. Attention : la salle n’est pas très bien chauffée.
Cours 14, jeudi 8 janvier : quelques idées sur le théorème PCP
Examen :
TD1_08.pdf : algo de Markov
TD2_08.pdf : PRIMES, simulation efficace par une machine de Turing universelle, machine oblivious
TD3_08.pdf : Ladner, simulation efficace par une machine de Turing non déterministe universelle
TD4_08.pdf : fonctions constructibles en temps, langages unaires, langages creux
TD5_08.pdf : reprend le TD4 et rajoute des exercices sur la constructibilité en temps et en espace
TD6_08.pdf : le jeu de GO est PSPACE-complet
TD7_08.pdf : machines alternantes
TD8_08.pdf : des circuits et des cailloux
TD9_08.pdf : des circuits et des cailloux, suite
TD10_08.pdf : P/poly
TD11_08.pdf : problèmes P-complets et P-SEL
TD12_08.pdf : pièces biaisées, BPL, RL, réductions randomisés, th de réduction des erreurs pour RP
TD13_08.pdf : IP et permanent
TD14_08.pdf : IP, AM, zero-knowledge
Bibliographie :
- Sanjeev Arora et Boaz Barak : Complexity Theory: A Modern Approach
- C.H. Papadimitriou, Computational Complexity, Addison-Wesley(1994)
- Michael Sipser, Introduction to the theory of computation
- José L. Balcazar, Josep Diaz, Joaquim Gabarro, Structural Complexity I
2007-2008
groupe de lecture sur le calcul quantique
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évrier 2008 : RAM
Cours 3, mercredi 13 février : fonctions récursives primitives
Cours 4, lundi 25 février : fonctions récursives, le problème de l’arrêt
Cours 5, lundi 3 mars : théorème de l’arrêt, machines universelles, théorème smn, théorème de Rice, premier théorème du point fixe de Kleene, système acceptable de programmation
Cours 6, mercredi 12 mars : théorème de l’isomorphisme de Rogers, ensemble d’entiers récursifs et récursivement énumérables
Cours 7, lundi 17 mars : le théorème de compacité du calcul des proposition, premières définitions du calcul des prédicats
partiel : lundi 24 mars
Cours 8, mercredi 26 mars : le théorème de compacité du calcul des prédicats, un peu de complétude
Cours 9, lundi 7 avril : le théorème de complétude du calcul des prédicats, construction des structures égalitaires
Cours 10, lundi 21 avril : Peano
Cours 11, lundi 28 avril : théorème de représentation, arithmétisation de la syntaxe
Cours 12, lundi 5 mai : codage des preuves, théories récursives
Cours 13, mercredi 7 mai (qui est un lundi de cours, pour remplacer le 12 mai) : les théorèmes de Gödel
Cours 14, lundi 19 mai : l’élimination des quanteurs dans les corps réels clos, d’après l’article de Christian Michaux et Adem Ozturk (voir la biblio ci-dessous).
examen vendredi 23 mai :
Bibliographie :
- Christian Michaux et Adem Ozturk, Quantifier Elimination following Muchniks et une implémentation A Proof-Producing Decision Procedure for Real Arithmetic de Sean McLaughlin et John Harrison
- Le cours d’Elisabeth Bouscaren
- Logique mathématique, René Cori et Daniel Lascar, deux tomes chez Dunod (et première édition Axiomes). Cours et exercices. Plusieurs exemplaires à la bibliothèque.Dans le premier tome : Calcul propositionnel, Algèbre de Boole, Calcul des prédicats, Théorèmes de complétude. Second tome : Récursivité (inclus les machines de Turing) , Formalisation de l’arithmétique, théorèmes de Gödel, théorie des ensembles, un peu de théorie des modèles. (à la Bib)
- Mathématiques de l’informatique, cours et exercices corrigés (licence, maitrise, agrégation), Patrick Dehornoy, chez Dunod. Il y en a 3 à la bibliothèque. Il y a aussi d’autres livres du même auteur, que je ne connais pas dont les titres sont proches des sujets du cours (à la Bib)
- Histoire d’algorithmes : du caillou à la puce ; Belin. A la bib aussi. Pour votre culture générale sur le sujet.
- Langages formels, calculabilité et complexité : Licence et Master de mathématiques ou d’informatique, option informatique de l’agrégation de mathématiques, Olivier Carton, Vuibert. (à la Bib)
- C.H. Papadimitriou, Computational Complexity, Addison-Wesley(1994) (pour les machines de Turing principalement) (à la Bib)
- Introduction to the theory of Computation, Michael Sipser, PWS Publishing Company (à la Bib)
- le théorème de Gödel, points sciences, éditions du seuil (pour lire le texte de Gödel, traduit)
- La machine de Turing, points sciences, éditions du seuil (pour lire le texte de Turing, traduit)
- Une histoire de l’informatique, Philippe Breton, points sciences, éditions du seuil (pour votre culture générale)
2006-2007
Calcul quantique
Master 2
Pour les étudiants inscrits, voir le site formation de l’ENS Lyon
2005-2006
Logique et complexité (théorie des modèles et complexité algébrique)
Second semestre du master 1 de mathématiques approfondies de Lyon et du M1 d’informatique fondamentale
Cours : Franck Wagner et
TD : Natacha Portier
TD1_06.pdf (formules)
TD2_06.pdf (morphisme)
TD3_06.pdf (extension élémentaire)
TD4_06.pdf (compacité)
TD5_06.pdf (saturation)(fait jusquà la fin de l’exo 2)
TD6_06.pdf (élimination des quanteurs et modèle complétion)
TD7 (partiel.ps 2003)
partiel_06.pdf
TD8_06.pdf (début de la complexité)
TD9_06.pdf (autour de Spira)
TD10_06.pdf (problèmes booléens)
examen_06.ps
Sources : voir les années précédentes
Probabilités et applications à l’algorithmique
Second semestre du L3 d’informatique fondamentale
Cours : Pascal Koiran
TD : Natacha Portier
TD1_06.pdf (on révise les probas du lycée)(jusqu’à l’exo 5 inclus)
TD2_06.pdf (le collectionneur d’images)(jusqu’à l’exo 3 inclus)
TD3_06.pdf (théorème de Hardy Weinberg,corde de Bertrand, problème des menteurs, loi de succession de Laplace)(jusqu’à l’exo 5 inclus)
TD4_06.pdf (diverses lois discrètes)(jusqu’à l’exo 5 inclus sauf question 1)
TD5_06.pdf (théorème des événements rares de Poisson)(question 3 pas terminée)
TD6_06.pdf (entropie et codage)(jusqu’à la fin de la question 2)
partiel le 28 mars 2006, repoussé à la semaine suivante et remplacé par des révisions (fin des TD 2 et 5)
TD7_06.pdf (le principe de Yao)
TD8_06.pdf (fonctions génératrices)
TD9_06.ps (chaînes de Markov, collectionneur de figurines) 9 mai
TD10_06.ps (graphes aléatoires) TD virtuel le 16 mai
TD11_06.pdf (marches aléatoire, processus de branchement de Galton-Watson) 23 mai
examen_06.ps
Sources : voir les années précédentes
partiel : http://www.les-mathematiques.net/f/p/b/node1.php3 (voir le fichier ici)
Cours Interdisciplinaire d’Information Quantique
Cours annuel proposé aux L3 informaticiens, mathématiciens, biologistes et géologues
Cours : Pascal Degiovanni et Natacha Portier
2004-2005
Calcul quantique
Master 2 Premier semestre 2003-2004
Logique et complexité (théorie des modèles et complexité algébrique)
Second semestre du master 1 de mathématiques approfondies de Lyon
Cours et TD : Franck Wagner et Natacha Portier
Sources :
- Cours et exercices des années précédentes se trouvent sur la page de Frank Wagner
- TD 93-94, Anatole Khélif
- Logique mathématique tomes 1 et 2, René Cori et Daniel Lascar, Dunod
- Cours de Théorie des modèles, B. Poizat, et la version anglaise (version russe ici)
- B. Poizat, Les petits cailloux, ALEAS
Groupe de lecture de Calcul quantique du L3 de mathématiques
2003-2004
Complexité descriptive et modèles finis
Premier semestre 2003-2004 du MIM2
(cours de base du futur Master)
Cours : Jacques Mazoyer
TD : Natacha Portier
TD1_03.ps, TD1_03.dvi (formules et logique du premier ordre)
TD2_03.ps, TD2_03.dvi (La logique du premier ordre exprime des propriétés locales)
TD3_03.ps, TD3_03.dvi (Une loi zéro-un étiquetée)
TD4_03.ps, TD4_03.dvi (loi zéro-un non étiquetée, deux séances)
TD5_03.ps, TD5_03.dvi (description logique d’un calcul)
TD6_03.ps, TD6_03.dvi (description logique d’un calcul, suite)
partiel_03.ps, partiel_03.dvi
TD7_03.ps, TD7_03.dvi (description logique d’un calcul, réciproque du théorème)
TD8_03.ps, TD8_03.dvi (pos TC=TC)
TD9_03.ps, TD9_03.dvi (capture et capture forte)
TD10_03.ps, TD10_03.dvi (optimisation)
Sources :
- Les TD de Hervé Fournier
- Finite Model Theory, Ebbinghaus Flum, Springer
- Descriptive complexity and Finite Models, Immerman and Kolaitis Editors, AMS, 1997
- Descriptive complexity, Immerman, Springer, 1998
Calcul quantique
DEA Premier semestre 2003-2004
(cours de recherche du futur Master)
2002-2003
Logique et complexité (théorie des modèles et complexité algébrique)
Second semestre 2002-2003 de la maîtrise de maths de Lyon I
Cours : Bruno Poizat
TD : Natacha Portier
TD1_03.ps, TD1_03.dvi (formules et logique du premier ordre)
TD2_03.ps, TD2_03.dvi
TD3_03.ps, TD3_03.dvi
TD4_03.ps, TD4_03.dvi (application du théorème de compacité, théorème de Vaught)
TD5 : petite introduction à la théorie des ensembles. Je me suis appuyée sur le cours trouvé d’Alexandre Rambaud (voir sources): fichier1.pdf, fichier2.pdf, fichier3.pdf, fichier4.pdf. On pourra également consulter les notes enrichies d’Emmanuel Jaendel (voir sources).
TD6_03.ps, TD6_03.dvi
TD7_03.ps, TD7_03.dvi (les corps réels clos)
partiel_03.ps, partiel_03.dvi
8, cours et TD : les machines de Turing et les circuits sur une structure algébrique quelconque
TD9_03.ps, TD9_03.dvi : grande feuille sur le cours précédent
TD10_03.ps, TD10_03.dvi : les problèmes booléens dans diverses structures
vacances, 1er mai, 8 mai
examen le jeudi 15 mai de 14h à 17h amphi B ens Lyon
Sources :
- Cours et exercices 2000-2001 et 2001-2002 se trouvent sur la page de Frank Wagner
- Notes enrichies du cours précédent, par Emmanuel Jeandel
- TD 93-94, Anatole Khélif
- Logique mathématique tomes 1 et 2, René Cori et Daniel Lascal, Dunod
- Page d’Alexandre Rambaud pour le cours de théorie des ensembles, fait également par Julien Page.
- Jean-Louis Krivine, Théorie des ensembles, Cassini
- Cours de Théorie des modèles, B. Poizat, et la version anglaise
- B. Poizat, Les petits cailloux, ALEAS
DEA : Calcul quantique, voir ici
2001-2002
Probabilités et applications à l’algorithmique
Second semestre 2001-2002 du MIM première année.
Cours : Pascal Koiran
TD : Natacha Portier
TD1_02.ps, TD1_02.dvi(combinatoire)
TD2_02.ps, TD2_02.dvi(probabilités conditionnelles)
TD3_01.ps , TD3_02.dvi (encore un peu des deux)
TD4_02.ps , TD4_02.dvi(variables aléatoires discrètes)
TD5_02.ps , TD5_02.dvi(variables aléatoires discrètes)
TD6_02.ps , TD6_02.dvi(entropie de Shannon et codages)
TD7_02.ps , TD7_02.dvi(suite et théorie des questionnaires)
TD8_02.ps , TD8_02.dvi(séries génératrices)
TD9_02.ps , TD9_02.dvi(chaînes de Markov)
partiel_02.ps , partiel_02.dvi(tables de hachage, marche au hasard en dimension plus que 3)
TD10_02.ps , TD10_02.dvi(processus de Galton-Watson)
TD11_02.ps , TD11_02.dvi(la ruine du joueur)
TD12_02 : correction du partiel, examen de l’année dernière
TD13_02.ps, TD13_02.dvi (le principe de Yao)
examen02.ps
Sources :
- celles des années précédentes;
- Game Theory, Guillermo Owen, second edition, Academic Press, 1982
Modèles de calcul et complexité
Second semestre 2001-2002 du MIM première année.
Cours : Marianne Delorme
TD : Natacha Portier
TD1_02.ps, TD1_02.dvi (algorithmes de Markov)
TD2_02.ps, TD2_02.dvi (RAM)
TD3_02.ps , TD3_02.dvi (systèmes de programmation acceptables, fonctions booléennes),
TD4_02.ps , TD4_02.dvi (révisions de calculabilité),
TD5_02.ps , TD5_02.dvi (circuits booleens),
TD6_02.ps , TD6_02.dvi (un problème P-complet),
TD7_02.ps , TD7_02.dvi (problèmes espaceP-complet),
TD8_02.ps , TD8_02.dvi (suites de circuits),
TD9_02.ps , TD9_02.dvi (relativisations de P=NP avec des oracles),
partiel_02.ps , partiel_02.dvi (P-sel)
TD10_02.ps , TD10_02.dvi (fonctions constructibles en espace, compressions, fonctions constructibles en temps),
TD11_02.ps , TD11_02.dvi (classes de complexité probabilistes)
TD12_02 : correction du partiel et examen 2001
TD13_02 : examen 2000
Sources :
- Hemaspandra, Ogihara The complexity Theory Companion,
- Celles des années précédentes ;
Algorithmique
Premier semestre 2001-2002 du MIM première année.
Cours : Yves Robert
TD : Olivier Bodini, Natacha Portier
TD1_01.dvi, TD1_01.ps (recherche du plus grand, du plus petit et du plus grand simultanément, optimalité)
TD2_01.dvi, TD2_01.ps (recherche de l’élément majoritaire)
TD3_01.dvi, TD3_01.ps (optimalité pour la recherche du majoritaire, matrices de Toeplitz, location de skis)
DM1_01.ps ( quelle est la bonne clef ?)
TD4_01.dvi, TD4_01.ps (programmation dynamique)
TD5_01.dvi, TD5_01.ps (recherche du médian)
partiel : le 24 octobre à l’heure du cours
TD6 : correction du partiel
DM2_01.dvi, DM2_01.ps (le fromage)
TD7_01.dvi, TD7_01.ps (codage de Huffman)
TD8_01.dvi, TD8_01.ps (recherche de motifs avec des automates finis et Rabin-Karp)
TD9_01.dvi, TD9_01.ps (recherche de motifs avec Knuth-Morris-Pratt et Boyer-Moore)
TD10_01.ps (tables de hachage)
TD11_01.dvi, TD11_01.ps (algorithme de Sturm, NP-complétude : 2-SAT, NAE, OIT)
TD12_01.dvi, TD12_01.ps (somme d’un sous-ensemble, partition)
TD13_01.ps (examen 2000-2001)
examen_01.ps
Sources :
- Celles des années précédentes ;
- Mathématiques pour le langage formel, Maurice Mignotte, PUF 1989 ;
séminaire du MIM 2001-2002
2000-2001
Probabilités et applications à l’algorithmique
Second semestre 2000-2001 du MIM première et deuxième année.
Cours : Pascal Koiran
TD : Natacha Portier
TD1_01.ps (combinatoire)
TD2_01.ps (probabilités conditionnelles)
TD3_01.ps (encore un peu des deux)
TD4_01.ps (variables aléatoires discrètes)
TD5_01.ps (variables aléatoires discrètes, suite)
TD6_01.ps (théorie de l’information et entropie de Shannon)
partiel_01.ps
L’article original de Shannon.
Le problème des douze pièces à regarder sur www.ac-orleans-tours.fr (le lien n’existe plus)
TD7_01.ps (théorie des questionnaires)
TD8_01.ps (marches aléatoires et chaines de Markov)
TD9_01.ps (fonctions génératrices)
TD10_01.ps (processus de branchement : Galton-Watson ; souris ; jeu de Tennis)
TD11_01.ps (la ruine du joueur)
exam_01.ps
Sources :
- Introduction aux probabilités, P. Brémaud, Springer-Verlag 1984
- Markov Chains, Gibbs Fields, Monte-Carlo Simulation and queues, P. Brémaud, Springer 1999
- exercices de probabilités, Marie Cottrell, Valentine Genon-Catalot, Christian Duhamel, Thierry Meyre, Cassini 1999
- exercices ordinaires de probabilités, Gérard Frugier, ellipses
- An introduction to probability theory and its applications, vol. 1, William Feller, Jon Wiley & Sons
Modèles de calcul et complexité
Second semestre 2000-2001 du MIM première année.
Cours : Marianne Delorme
TD : Natacha Portier
TD1_01.ps (algorithmes de Markov)
TD2_01.ps(RAM)
TD3_01.ps(systèmes de programmation acceptables, récursivité)
TD4_01.ps (les circuits booléens)
TD5_01.ps (problèmes ESPACE-P-complets)
partiel_01.ps
TD6_01.ps (problèmes P-complets)
TD7_01.ps (fonctions constructibles en espace, compressions, fonctions constructibles en temps)
TD8_01.ps (relativisations de P=NP avec oracles)
TD9_01.ps (classes probabilistes)
examen (p-isomorphisme)
Sources :
- Celles de l’année 1999-2000 ;
Algorithmique
Premier semestre 2000-2001 du MIM première année.
Cours : Yves Robert
TD : Daniel Hirschkoff, Natacha Portier
TD1_00.dvi, TD1_00.ps (recherche du plus grand, du plus petit et du plus grand simultanément, optimalité)
TD2_00.dvi, TD2_00.ps (algorithme de majorité : quadratique, nlogn et linéaire)
TD3_00.dvi, TD3_00.ps (algorithme de majorité : l’optimal ; recherche du deuxième plus grand ; matrices de Toeplitz)
TD4_00.dvi, TD4_00.ps(programmation dynamique)
Devoir(.dvi), Devoir(.ps) en temps libre (Mariages) et sa correction(.ps).
TD5_00.dvi, TD5_00.ps (arbres binaires de recherche, rouges et noirs, B-arbres), une partie du corrigé rbtrees.ml
TD6 : correction du partiel, une partie du corrigé(.ps)
TD7_00.dvi, TD7_00.ps (Recherche du quantième, médian pondéré, bureau de poste et champ pétrolier), une partie du corrigé(.ps)
TD8_00.dvi, TD8_00.ps (codage de Huffman)
TD9_00.ps (coloriages et périmètres, partiel 99)
TD10_00.ps (nombre de coloriages, variantes de SAT)
TD11_00.ps (NP-complétude de coloriages)
TD12_00.ps (Couverture des sommets d’un graphe, somme d’un sous-ensemble, partition)
TD13_00.ps (Recherche de motifs : automates finis, algorithme de Knuth, Morris, Pratt et algorithme de Rabin-Karp)
examen00.ps(tas d-aire, i plus grands éléments triés, vertex cover avec degré pair, 2-partition avec meme cardinal, clique pour graphe régulier, approximation du sac à dos)
Sources :
- Celles de l’année 1999-2000 ;
- Pour les algorithmes de majorité : sujet d’oral d’ Alain Darte, article de Fischer et Salzberg, Journal of Algorithms, Vol. 3, pages 376-379, 1982.
- Pour le devoir sur les mariages : sujet d’oral de Pascal Koiran, d’après Introduction to Graph Theory de D. West
séminaire du MIM 2000-2001
1999-2000
Algorithmique
Premier semestre 1999-2000 du MIM première année.
Cours : Yves Robert
TD : Daniel Hirschkoff, Natacha Portier
TD1_99.dvi, TD1_99.ps (recherche du plus grand, du deuxième plus grand, du plus petit et du plus grand simultanément)
TD2_99.dvi, TD2_99.ps (méthode de l’oracle pour l’algorithme précédent, résolution de récurrences)
TD3_99.dvi, TD3_99.ps (programmation dynamique)
TD4_99.dvi, TD4_99.ps (codage de Huffman)
TD5_99.ps (B-arbres)
TD6_99.dvi, TD6_99.ps (coloriages)
TD7_99.dvi, TD7_99.ps (Tas de Fibonacci, analyse amortie)
TD8_99.dvi, TD8_99.ps (Recherche du quantième, médian pondéré, bureau de poste et champ pétrolier)
TD9_99.dvi, TD9_99.ps (composantes fortement connexes d’un graphe, 2-SAT, SAT-2)
TD10_99.ps (coloriages de graphes)
cours(.dvi), cours(.ps) du 14-12-1999 (Le théorème de Stockmeyer et Meyer)
TD11_99.dvi, TD11_99.ps (Couverture des sommets d’un graphe, somme d’un sous-ensemble, partition)
TD12_99.dvi, TD12_99.ps (Recherche de motifs : Rabin-Karp et automates finis)
TD13_99.dvi, TD13_99.ps (Algorithme de Knuth, Morris, Pratt pour la recherche de motifs)
Devoir(.dvi), Devoir(.ps) en temps libre (bases de Gröbner)
partiel(.ps)
Examen(.ps)
Sources :
- Les fiches des TDmen de l’année précédente Matthieu Exbrayat et Codrin Nichitiu, et les notes d’Yves Robert.
- Les documents qui ont servi de base de travail pour faire passer l’épreuve orale d’Informatique commune aux trois ENS Cachan, Lyon, et Ulm en 1999 (à récupérer ici).
- T. Cormen et al., Introduction à l’algorithmique, Dunod
- …
Modèles de calcul et complexité
Second semestre 1999-2000 du MIM première année.
Cours : Marianne Delorme
TD : Natacha Portier
TD1.dvi (algorithmes de Markov),
TD2.dvi (RAM),
TD3.dvi (systèmes de programmation acceptables, fonctions booléennes),
TD4.dvi (récursivité, parallélisation de l’addition),
TD5.dvi (les circuits booléens),
TD6.dvi (les circuits réels),
TD7.dvi (le jeu de la géographie),
TD8.dvi (jeu de GO, autres problèmes ESPACE-P-complets),
partiel.dvi (problèmes périodiques ESPACE-P-complets),
TD9.dvi (fonctions constructibles en espace, compression de l’espace, des rubans, du temps),
TD10.dvi (compression en temps des rubans, fonctions constructibles en temps),
TD11.dvi (suite de circuit uniforme polynomiale, classe NC),
TD12.dvi (classes probabilistes RP, PP, BPP)
exam00.ps (examen)
Sources :
- C.H. Papadimitriou, Computational Complexity, Addison-Wesley(1994)
- B. Poizat, Les petits cailloux, ALEAS
- J.E. Hopcroft et J.D. Ullman, Introduction to Automata Theory, languages, and Computation
- M. Machtey, P. Young, An Introduction to the General Theory of Algorithms
- Daniel Pierre Bovet, Pierluigi Crescenzi, Introduction to the Theory of Complexity
- …
DENIF – Documents d’Enseignement Numériques en Informatique Fondamentale
Finissons par une citation :
Les exercices qui précèdent sont exceptionnellement originaux, c’est-à-dire qu’ils ne sont originaux qu’exceptionnellement. (un algébriste)
C’est pour cela que j’ai essayé d’indiquer les sources dont nous nous sommes inspirés pour ces fiches. Pour les oublis et omissions soyez indulgents et envoyez-moi un petit mot…