--------------------

Enseignement

----------- 

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_06.pdf ()
TD8_06.pdf ()
TD9_06.pdf ()
TD10_06.pdf ()
TD11_06.pdf ()
TD12_06.pdf ()

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
TD7_06.pdf ()
TD8_06.pdf ()
TD9_06.pdf ()
TD10_06.pdf ()
TD11_06.pdf ()
TD12_06.pdf ()

Sources : voir les années précédentes

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, parteil_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)
examen_02.ps, examen_02.dvi ()

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
examen_02.ps, examen_02.dvi ()

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

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 .
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.tex (examen)

Sources :


Les cours rédigés par les élèves : voir ici

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/enseign.html
 

Page modifiée en mars 2006