Enseignement

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 :



2008-2009

SIESTE

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 :



Calcul quantique, cours de recherche de Master, premier semestre
Pour les étudiants inscrits, voir  ICI

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-knoxledge

Partiel.pdf
examen.pdf


Bibliographie :



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 :


SIESTE



2006-2007

Calcul quantique
Master 2
Pour les étudiants inscrits, voir  ICI


SIESTE



 

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 (voir l'UFR) 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

Pour les étudiants inscrits, voir  ICI

 2004-2005

Calcul quantique
Master 2 Premier semestre 2003-2004
Pour les étudiants inscrits, voir  ICI



Logique et complexité (théorie des modèles et complexité algébrique)
Second semestre du master 1 de mathématiques approfondies de Lyon (voir l'UFR)
Cours et TD : Franck Wagner et Natacha Portier

Sources :


Groupe de lecture de Calcul quantique du L3 de mathématiques
Pour les étudiants inscrits, voir  ICI

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 :

Calcul quantique
DEA Premier semestre 2003-2004
(cours de recherche du futur Master)

voir ICI

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 (voir l'UFR)
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é ici (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 :

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 :

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 :

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 :



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 à récupérer ici.
Le problème des douze pièces à regarder là.
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 :

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 :

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 :

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 :



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 :



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...

Vous êtes à l'adresse :

http://perso.ens-lyon.fr/natacha.portier/enseign/index.html
 

Page modifiée en septembre 2011