Enseignement

Quelques anciens cours. Les nouvelles ressources sont maintenant postées sur Moodle.

Complexité algorithmique (M1, université Paris Descartes, 2014-2015)

Une fiche d'exercices ici sur la NP-complétude, et la correction du dernier exercice ici.

Introduction à la programmation (IP1, L1, université Paris 7, 2014-2015)

Correction du premier test ici. L'énoncé est disponible ici (avec quelques imprécisions corrigées par rapport à l'énoncé original).

Stages et TRE en M1 (université Paris 7, 2010-2012)

Voir cette page.

Cours-TD de probabilités discrètes en L2 (université Paris 7, 2011-2012)

Cours-td avec Jean-Michel Autebert et Matthieu Picantin.
Quelques fiches :

• Fiche d'exercices 1 de Matthieu Picantin, en pdf.
• Fiche d'exercices 2 de Matthieu Picantin, en pdf.
• Première interrogation 2011 en pdf et sa correction.
• Deuxième interrogation 2011 en pdf et sa correction.
• Troisième interrogation 2011 en pdf et sa correction.
• Quatrième interrogation 2011 en pdf et sa correction.

TP de sécurité (cryptologie) en M2 (université Paris 7, 2011-2012)

Cours de Roberto Amadio
Fiches de tp :

• TP 1 et 2 en pdf.
• TP 3 en pdf.
• TP 4 et 5 en pdf.
• TP 6 et 7 en pdf.

Cours d'algorithmique en L3 (université Paris 7, 2011-2012)

Programme : ABR, tas, graphes, NP-complétude.
Correction de l'exercice 1 de l'examen 2012 en pdf.
TD d'Hervé Baumann, Constantin Enea et Fabien de Montgolfier. Fiches de tp :

• TD 1 en pdf.
• TD 2 en pdf.
• TD 3 en pdf.
• TD 4 en pdf.
• DM en pdf.

Cours de 6h en complexité algébrique (école d'hiver de l'ENS Lyon, 2011)

Le cours en pdf : Bornes inférieures sur le calcul de polynômes.

Cours de calculabilité en M1 (université Paris 7, 2009-2011)

2010-2011 : TD de Christian Choffrut.
(2009-2010 : TD de Roberto Mantaci)

• Notes de cours en pdf.
• Examen 2010 en pdf.
• Partiel 2010 en pdf.
• Examen 2009 en pdf.
• Partiel 2009 en pdf.

TD/TP de base de données en L3 (université Paris 7, 2008-2011)

Cours de Wiesław Zielonka.

• TD1 : modélisation. En pdf.
• TP1 : prise en main de PostgreSQL. En pdf.
• TD2 : algèbre relationnelle. En pdf.
• TD3 : dépendances fonctionnelles. En pdf.
• TP2 : requêtes simples. En pdf.
• TP3 : sous-requêtes et requêtes d'agrégation. En pdf. Correction : tp3-cor.txt.
• TD4 : interprétation de requêtes abstraites. En pdf.
• TP4 : requêtes, création et modification de tables. En pdf.

Cours/TD d'algorithmique en L2 (université Paris 7, 2008-2009)

Cours/TD en collaboration avec Yan Jurski et Roberto Mantaci. Quelques éléments :

• Un support de cours pour une séance annulée avec quelques exercices. En pdf.
• Fiche de TD 1. En pdf.
• Fiche de TD 2. En pdf.
• Fiche de TD 3. En pdf.
• Partiel. En pdf.

TD d'automates et langages formels en L3 Bio-info (université Paris 7, 2008-2010)

Cours de Christian Choffrut.

• TD1 : automates déterministes, opérations sur les langages. En pdf.
• TD2 : automates non-déterministes, lemme de l'étoile, langages rationnels, expressions rationnelles. En pdf.
• TD3 : minimisation d'automates. En pdf.
• TD4 : grammaires algébriques. En pdf.

Cours d'introduction à l'informatique en L1 (université Paris 7, 2008-2011)

Voir la page du cours de Jean-Marie Rifflet.

• Un petit DM en pdf et sa correction.
• Première interrogation (45 min) en pdf.
• Seconde interrogation (1h45) en pdf et sa correction.

TD d'algorithmique en L3 Bio-info (université Paris 7, 2008-2010)

Cours de Daniele Varacca.

• TD1 : tri par sélection. En pdf.
• TD2 : entraînement sur le pseudo-code. En pdf.
• TD3 : ordre de grandeur des fonctions. En pdf.
• TD4 : récursion. En pdf.
• TD5 : listes (2 séances). En pdf.
• TD6 : arbres binaires de recherche. En pdf.
• TD7 : tas et AVL. En pdf.
• TD8 : tables de hachage. En pdf.
• TD9 : révisions (annales d'examens). En pdf.

TD d'algorithmique en L3 (université Paris 7, 2008-2011)

Cours de François Laroussinie, TD en collaboration avec Grégoire Henry et Fabien de Montgolfier.

• TD1 : arbres binaires de recherche. En pdf.
• TD2 : arbres binaires de recherche, suite. En pdf.
• TD3 : arbres binaires de recherche, suite et fin. En pdf.
• TD4 : arbres AVL. En pdf.
• TD5 : résolution de récurrences. En pdf.
• TD6 : graphes non-orientés. En pdf.
• TD7 : parcours dans les graphes. En pdf.
• TD8 : arbres couvrants de poids minimum. En pdf.
• TD9 : plus courts chemins. En pdf.
• TD10 : examen de l'année 2007-2008. En pdf.

Cours : algorithmes probabilistes (ENS Lyon, L3, 2008)

Cours de 2 heures sur les algorithmes probabilistes et la dérandomisation, notamment les liens avec les bornes inférieures non-uniformes. Transparents disponibles en pdf.

TD Algorithmique et programmation (université Lyon 1, L1, 2007-2008)

Cours d'Elodie Dessérée en L1, licence Sciences et Technologies (voir ici).
11 séances de TD de 2 heures. Fiches de TD disponibles là.

• Première interrogation surprise (15min lors de la troisième séance de TD) en pdf. Une correction est également disponible ici.
• Deuxième interrogation surprise (30min lors de la septième séance de TD) en pdf. Une correction est également disponible ici.
• Troisième interrogation surprise (30min lors de la onzième séance de TD) en pdf. Une correction est également disponible ici.

TP Programmation en C (université Lyon 1, L1, 2007-2008)

TP du cours précédent.
8 séances de 3 heures. Fiches de TP disponibles ici.

TD Complexité Turing (ENS Lyon, M1, 2007-2008)

Cours de Marianne Delorme. TD en collaboration avec Sylvain Chevillard.

• TD1 : machines RAM, simulation par machine de Turing ; nombre de rubans d'une machine de Turing. En pdf.
• TD2 : fonctions booléennes, circuits booléens, systèmes de programmation acceptables. En pdf.
• TD3 : circuits booléens (suite), systèmes de programmation acceptables (suite). En pdf. Deux documents de Sylvain Chevillard sur les systèmes de programmation acceptables : ici et là.
• TD4 : P-complétude, équivalence avec famille uniforme de circuits de taille polynomiale. En pdf.
• TD5 : classes non-uniformes (en particulier P/poly), classes probabilistes (en particulier RP). En pdf.
• TD6-7 : classe probabiliste RP (reprise d'un exercice du TD5), classe P-sel (langages P-sélectifs). En pdf.
• TD8 : théorème de Mahaney (s'il existe un langage creux NP-dur alors P=NP). En pdf.
• Partiel : théorèmes de Spira (parallélisation des formules), de Ladner (si P est différent de NP alors il existe des langages ni P ni NP-durs), de Mahaney (non traité au td8). En pdf.
• TD9 : conseils, théorèmes de hiérarchie en temps déterministe et non-déterministe. En pdf.
• TD10 : changement d'échelle, padding. En pdf.
• TD11 : problèmes PSPACE-complet : géographie. En pdf.
• TD12 : hiérarchie polynomiale, théorème de Karp-Lipton. En pdf.

Organisation des stages L3 (ENS Lyon, 2006-2007)

Les élèves de l'ENS Lyon doivent effectuer un stage de recherche de 6 semaines à la fin de leur première année. Plus de détails, dont les sujets de stage et le planning des soutenances, ici.
On pourra trouver quelques rapports de stage sur le serveur des élèves.

TD Fondements de l'informatique (ENS Lyon, L3, 2006-2007)

Cours de Michel Morvan en 3 parties : langages rationnels, langages algébriques, réécriture. TD en collaboration avec Victor Poupet.

• TD1 : automates finis et mots. En pdf. Une correction est disponible ici en pdf (profitez-en, ce sera une des seules...).
• TD2 : automates finis. En pdf.
• TD3 : langages rationnels. En pdf. On trouvera ici un exercice concernant la caractérisation des fonctions f telles que f(L) est rationnel pour tout langage rationnel L (en référence à l'exercice 3 du td 3).
• TD4 : un résultat de Minsky et Papert. En pdf. Une correction est disponble ici en pdf.
• Partiel : langages rationnels. En pdf.
• TD5 : mots prédictibles et mots univers. En pdf.
• TD6 : grammaires algébriques et automates à pile. En pdf.
• TD7 : automates à pile et langages algébriques. En pdf.
• TD8 : lemme d'Ogden (généralisation du lemme de l'étoile pour les langages algébriques). En pdf.
• TD9 : équivalence grammaires algébriques / automates à piles. En pdf.
• TD10 : terminaison de systèmes de réécriture, lemme de König, lemme de Higman. En pdf.
• TD11 : lemme de Higman (fin), lemme de Newman, jeu de Nim. En pdf.
• TD12 : divers (partiel 2004 de Romain Kervarc, merci à lui). En pdf.
• TD13 : ordinaux. En pdf.

TP Initiation OCaml (ENS Lyon, L3, 2006-2007)

Un TP d'initiation à OCaml pour les nouveaux élèves (cours de Daniel Hirschkoff).
Le sujet est ici : td1.pdf. Les exemples du début du td sont là : td1.ml. Merci à Jérémie Detrey pour ce sujet.
Enfin, le ficher d'exemples du prof est là : cours.ml.

TD Complexité algébrique (atelier de formation de théorie des modèles ModNet, juin 2006, université Lyon 1)

3 TD d'une heure, en anglais (cours de Pascal Koiran). Lien vers l'atelier de formation : http://math.univ-lyon1.fr/~logicum/francais/modnetlyonfr.htm
Lien vers ModNet : http://www.logique.jussieu.fr/modnet/

• TD1 : problèmes NP-complets sur R et C (HN, 4FEAS). En pdf.
• TD2 : élimination des quantificateurs, machine de Turing algébrique. En pdf.
• TD3 : non-déterminisme booléen, parties booléennes, théorème de transfert. En pdf.

TD/TP Algorithmique effective (ENS Lyon, L3/M1, 2005-2006)

Cours de Nicolas Schabanel. La plupart des problèmes viennent du site d'entraînement UVa online judge. Un petit mémento pour débuter en C++ est disponible ici en ps.

• TD1 : bases, entrées et sorties. Disponible en dvi ou ps. Un exemple de correction est disponible en zip.
• DM1. Disponible en dvi ou ps.
• TD2, DM2 : backtracking, branch & bound. Disponible en dvi ou ps. Un exemple de correction est disponible en zip.
• TD3, DM3 : couplage max dans un biparti, flots dans un graphe. Disponible en dvi ou ps. Un exemple de correction est disponible en zip.
• Partiel 1 : 5 problèmes divers. Disponible en pdf. Un exemple de correction est disponible en zip.
• TD4, DM4 : de la géométrie. Disponible en pdf. Un exemple de correction est disponible en zip.
• TD5 : géométrie, suite (et reprise de deux exercices du TD4). Disponible en pdf. Un exemple de correction est disponible en zip. DM5 : étude d'une transition de phase dans 3-SAT. Voir la section 4 du TD5, et voir le lien UVa 565 ("Pizza anyone?").
• TD6 : géométrie algorithmique (enveloppe convexe). Disponible en dvi et ps. Un exemple de correction est disponible en zip.
• TD7 : géométrie algorithmique, suite (plus petit cerlce englobant, points les plus proches). Disponible en dvi et ps.
• DM6.1 (facultatif) : "triangle partition" (voir le lien UVa 691).
• Partiel 2 : 5 problèmes divers. Disponible en pdf. Un exemple de correction est disponible en zip.
• TD8 : correction du partiel 2.
• DM6 : 2 exercices divers. Disponible en pdf. Un exemple de correction est disponible en zip.
• TD9, DM7 : graphes, flots et coupes. Disponible en pdf.
• DM8 : 5 exercices divers. Disponible en pdf.
• TD10, DM9 : arithmétique. Disponible en dvi et ps. Un exemple de correction est disponible en zip.
• TD11 : divers. Disponible en dvi et ps.
• TD12 : Hachage et exhaustif. Disponible en pdf.
• Examen : 7 exercices divers. Disponible en pdf.

TD Complexité structurelle (ENS Lyon, M1, 2005-2006)

Cours de Pascal Koiran.

• TD1 : oracles et la hiérarchie polynomiale. En dvi ou ps.
• TD2 : la hiérarchie polynomiale (reprise de deux exercice du TD1), la classe DP, classes avec conseil. En dvi ou ps.
• TD3 : langages creux et langages unaires. En dvi ou ps.
• TD4 : diagonalisation, utilisation des théorèmes de hiérarchie. En dvi ou ps.
• TD5 : classes probabilistes 1 (RP principalement). En dvi ou ps.
• TD6 : classes probabilistes 2 (BPP principalement), et reprise d'un exercice du TD5. En dvi ou ps.
• TD7 : classes probabilistes et de comptage (RP, BPP, PP, #P). En dvi ou ps.
• Partiel (langages unaires, langages p-sélectifs, conseil de taille 1). En dvi ou ps. Correction disponible en dvi ou ps.
• TD8 : classes de comptage (PP, #P, parity-P). En dvi ou ps.
• TD9 : classes de comptage, suite (#P, parity-P) ; reprise d'un exercice du TD précédent. En dvi ou ps. Les "figures jointes" dont il est question proviennent du livre Computational complexity de Papadimitriou.
• TD10 : protocoles interactifs (IP, MIP). En dvi ou ps.
• TD11 : protocoles interactifs (IP, AM). En dvi ou ps.
• TD12 : PCP (probabilistically checkable proofs). En dvi ou ps.