Autres documents d’enseignement

Cette page regroupe des documents préparés dans le cadre de mes enseignements.

Though most documents are in French, exercise sheets about computational complexity are provided in English.

Théorie de l’information

M1 Informatique, U. Montpellier

Contenu : théories de l’information naïve, à la Shannon, à la Kolmogorov, et codes correcteurs. Documents pour la partie sur les codes de Reed-Solomon.

Calcul formel et scientifique

L3 Informatique, U. Montpellier

Cours préparé en binôme avec Pascal Giorgi, en 2021-2022. Contenu : découverte du logiciel SageMath

Représentation de l’information

DIU EIL, U. Montpellier

Mini-cours sur la représentation des nombres, et des images.

Préparations au CAPES

Les documents suivants ont été préparés dans la cadre de la préparation aux CAPES de mathématiques option informatique (2016-2019) ou NSI (2019-2022).

Cours et TD : CAPES de mathématiques option informatique

Introduction à Python : TD de découverte du langage
Complexité algorithmique : le cours, TD1 et TD2
Cryptographie : cours d’initiation
Programmation : deux notebooks Jupyter sur les fonctions et les paradigmes de programmation (le dernier notebook sur la programmation orientée objet n’est pas fourni car trop mauvais…), et un TD de programmation.

Sujets d’écrits blancs

Problèmes pour des écrits blancs du CAPES de mathématiques option informatique :

Sujets complets, constitués de deux problèmes indépendants chacun, pour le CAPES NSI :

TD de Complexité Algorithmique

M1 Informatique, ÉNS Lyon

Contenu : classes de complexité déterministes et non déterministes, en temps et en espace ; hiérarchies entre ces classes ; problèmes complets ; algorithmes et classes probabilistes ; classes de complexité en temps parallèle ; classes non uniformes et circuits.

Responsable du cours : Patrick Baillot (2010) ou Natacha Portier (2011)

Exercise sheets for 2010-2011 are available in English: Time and space complexity classes, determinism, non-determinism, randomized classes, non-uniformity, hierarchies, completeness.

2011-2012 +-
- TD01 - Machinations : Simulations de Machines de Turing entre elles et avec des RAM.
- TD02 - Sat alors ! : Machine de Turing universelle, théorème de Cook-Levin, Sat-solver et langages unaires.
- TD03 - Yet Another Cook Theorem : coNP, fonctions constructibles en temps, théorème de hiérarchie en temps non déterministe.
- TD04 - Soldes : constructibilité en espace, réductions (many-one, par oracle et en espace logarithmique).
- TD05 - Espace-temps : PSPACE-complétude, théorème de hiérarchie en espace, padding, minimisation d'automates non déterministes.
- TD06 - Alternance : définition de NL par certificats, NSPACE(s)=coNSPACE(s), AP=PSPACE, classe DP.
- Partiel : Inclusions connues entre classes de complexité, oracles, langages creux et non-uniformes, padding, théorème de Mahaney, et bonus cryptographique.
- TD07 - Rabool les circuits : NC^k et NC, théorème de Spira, P-Sel.
- TDCirque 08 - Probe Habileté : P-Sel, théorème de hiérarchie non uniforme, réductions des erreurs pour RP, pièces biaisées.
- TD09 - Hé bé, pépé ! : pièces biaisées, réductions probabilistes, classe PP.
- TD10 - Comptons les pépés : classe PP, NP⊆BPP ⇒ NP=RP, médiane probabiliste, problèmes à promesse.
- TD11 - Tout ce que sais, c'est que je ne sais rien : protocoles interactifs (IP, AM et preuve à divulgation nulle).
- TD12 - Interaction permanente : protocole interactif pour le permanent.
2010-2011 +-
- TD01 - Machinations : Simulations de Machines de Turing, algorithme CYK, NP-complétude.
- TD02 - Haine, Paix : NP-complétude, langages unaires.
- TD03 - Respect de la hiérarchie : NP, coNP, caractérisations par certificats, théorèmes de hiérarchie en temps, théorème de Mahaney.
- TD04 - Oracles : Machines à oracles, saut de Turing, réductions Turing et many-one/Karp, théorème de hiérarchie non déterministe en temps.
- TD05 - Satellites : Classes de complexité en espace (dont L et PSPACE), PSPACE-complétude, théorème de hiérarchie en espace déterministe.
- TD06 - Jouons dans l'espace : PSPACE-complétude du jeu Geography et du jeu de Go.
- Partiel (corrigé) : Du cours, la réduction en temps non déterministe polynomial, la classe P-Sel, utilisation des théorèmes de hiérarchie.
- TD07 - Voûte céleste : Séance de cours (Thèorème de Savitch, composition des fonctions implicitement logspace, réductions logspace), un exo sur les fonctions implicitement logspace.
- TD08 - Hiérarchie polynomiale : NSPACE(S(n))=coNSPACE(S(n)), et des exos sur PH.
- TD09 - Bool Lyonnais(e) : Circuits booléens, dont addition binaire, théorème de Spira, existence de fonctions dures (Shannon) et circuits monotones.
- TD10 - Quelques conseils : Classes de complexité non uniformes, circuits booléens, et P-Sel.
- TD11 - Classes probabilistes : BPP, (co)RP, ZPP, PP; test d'identité de polynômes, MAJSAT et
- TD12 - Probablement le dernier : Réduction des erreurs pour BPP et RP, définitions équivalentes de ZPP, pièces biaisées et équilibrées.
- Examen Final (corrigé) : Du cours, la réduction des erreurs pour RP, la NL-complétude de la forte connexité d'un graphe, et un résultat de Hartmanis et Yesha (E ≠ ESPACE ⇔ P ≠ PSPACE ∩ P/poly).
- Tuto 01 - Machinations : Turing machines simulations, CYK algorithm, NP-completeness.
- Tuto 02 - NP : NP-completeness, unary languages.
- Tuto 03 - Respect the hierachy! : NP, coNP, certificate characterizations, time-hierarchy theorems, Mahaney's theorem.
- Tuto 04 - Oracles : Oracle machines, Turing jump, Turing and many-one/Karp reductions, nondeterministic time-hierarchy theorem.
- Tuto 05 - Satellites : Space complexity classes (including L and PSPACE), PSPACE-completeness, deterministic space-hierarchy theorem.
- Tuto 06 - Playing in the space (No English version, sorry!) : PSPACE-completeness of Geography and Go.
- Mid-term exam (French-written correction) : course recitation, exercises on the nondeterministic polynomial-time reduction, the class P-Sel and the use of time-hierarchy theorems.
- Tuto 07 - Voûte céleste : (partly bilingual sheet) only one exercise on implicitely logspace computable functions.
- Tuto 08 - Polynomial hierarchy : NSPACE(S(n))=coNPSPACE(S(n)) and exercises on PH.
- Tuto 09 - Bool Lyonnais(e) : Boolean circuits, including binary addition, Spira's theorem, existence of hard functions (Shannon) and monotone circuits.
- Tuto 10 - Some advice : Non-uniform complexity classes, boolean circuits, and P-Sel.
- Tuto 11 - Probabilistic classes : BPP, (co)RP, ZPP, PP; Polynomial Identity Testing, MAJSAT and
- Tuto 12 - Probably the last one : Error reduction for BPP and RP, characterizations of ZPP, biased and fair coins.
- Final exam (French-written correction) : course recitation, and exercises on error reduction for RP, NL-completeness of the strong connectivity of a graph, and a result of Hartmanis and Yesha (E ≠ ESPACE ⇔ P ≠ PSPACE ∩ P/poly).

Complexité de Turing : notes du cours de Marianne Delorme, suivi à l’automne 2008. Contenu : modèles de calcul, systèmes acceptables de programmation, classes déterministes et non-déterministes, en temps et en espace, hiérarchies.

TD d’Algorithmique

L3 Informatique, ÉNS Lyon

Contenu : paradigmes de programmation (diviser-pour-régner, programmation dynamique, algorithmes gloutons), analyse de complexité (bornes inférieures, supérieures, analyse amortie, séries génératrices), structures de données (listes, tableaux, tables de hachage), NP-complétude et algorithmes d’approximation.

Responsable du cours : Éric Thierry (2011) ou Fleury (2012) ; TD préparés avec Émilie Diot en 2011 et Théophile Trunk en 2012.

2012-2013 +-
- TD01 - Bricolage tragique à Hollywood : méthodes de dichotomie et bornes inférieures.
- TD02 - ÷ ⇒ ♔ : diviser pour régner.
- TD03 - Master de tennis : utilisation du Master Theorem.
- TD04 - Fonctions génératrices ordinaires
- TD05 - Programmation dynamique
- TD06 - Programmation dynamique : suite...
- TD07 - Carcajon (Gulo gulo) : algorithmes gloutons & matroïdes.
- TD08 - Boucherie : tables de hachage.
- Partiel
- TD09 - Suspensions : analyse amortie.
- TD10 - Maman j’ai rétréci les élèves : NP-complétude.
- TD11 - Encore un peu de NP-complétude
- TD12⁴ : quelques révisions (programmation dynamique, analyse amortie, bornes inférieures).
- TD13 - Tout en douceur : algorithmes d'approximation.
- TD14 - Révisions : NP-complétude, programmation dynamique, glouton, approximation.
2011-2012 +-
- TD01 - Star, boulons et sauts : méthodes de dichotomie et bornes inférieures.
- TD02 - Tullius Detritus : diviser pour régner.
- TD03 - Top 50 : diviser pour régner et Master Theorem.
- TD04 - En mémoire de Ph. Flajolet (1948-2011) : des séries génératrices.
- TD05 - Programmation dynamique : Allocation de skis aux skieurs, triangulation de polygones.
- TD06 - Carrément impressionnant : (programmation dynamique) Détection du plus grand carré de 1, impression équilibrée.
- TD07 - Mammifère carnivore de la famille des mustélidés : Algorithmes gloutons, matroïdes.
- Partiel
- TD08 - Steacks de calcul : Tables de hachage.
- TD09 - Suspensions : Analyse amortie.
- TD10 - Maman j'ai rétréci les élèves : NP-complétude.
- TD11 - La philanthropie de l'ouvrier charpentier : NP-complétude.
- TD12 - Tout en douceur : Algorithmes d'approximation.
- TD13 : Révisions (sujet d'examen de janvier 2010).
- TD14 - Fourres-y tout : Un peu de tout ce qui a été vu dans le semestre.

TD de Fondements de l’Informatique

L3 Informatique, ÉNS Lyon

Contenu : réécriture (de chaînes, de termes, de tresses), grammaires (contextuelles, hors-contexte, monotones, pseudo-contextuelles) et hiérarchie de Chomsky, automates (finis, à pile), relations entre grammaires et automates.

Responsable du cours : Guillaume Hanrot. TDs préparés avec Kevin Perrot

2010-2011 +-
- TD01 - Réécriture abstraite : Dénombrabilité, ordres, lemmes de König et de Higman, confluence.
- TD02 - Des chaînes : Réécriture des chaînes, paires critiques, lemme de Higman, réécriture de tresses.
- TD03 - Mettons un terme à la réécriture : Lemme de Higman, réécriture de chaînes, réécriture de termes.
- TD04 - Recettes de grammaires : Grammaires (contextuelles, hors-contexte, monotones, pseudo-contextuelles), lemme de structure des dérivations pour les grammaires hors-contexte.
- TD05 - Forme Normale Supérieure : Formes normales de Chomsky, Greibach et Kuroda, autoenchâssements et langage miroir.
- TD06 - Régulièrement hors-contexte : Stabilité par homomorphisme, substitution et miroir des langages réguliers et hors-contextes, autoenchâssement, ambigüité et forme normale de Kuroda.
- TD07 - Révisions : Un zeste de réécriture, de la hiérarchie de Chomsky et d'autres amusements autour des langages formels.
- TD08 - Salade d'automates : Equivalence grammaires régulières, automates finis non déterministes, expressions régulières. Exercices sur les automates finis.
- TD09 - Automates farcis : Algorithmes de Berry-Sethi et Knuth-Morris-Pratt.
- TD10 - Automate appeal : Pile vide vs. état final, mélange de langages.
- TD11 - D'après un article de Minsky et Papert (1965) : comment prouver qu'un ensemble d'entier n'est pas rationnel ?
- TD12 - Happy New International Year of Forests : Automates à pile déterministes.
- DM1 : A rendre la semaine du 4 octobre.
- DM2 : A rendre la semaine du 18 octobre.
- DM3 : A rendre la semaine du 15 novembre.
- DM4 : A rendre la semaine du 13 décembre.
- DM5 : A rendre la semaine du 10 janvier.

Médiation

Quelques exposés de médiation scientifique.

L'ordinateur est-il tout puissant ?, Lycéens, Cité Scolaire internationale de Lyon, 12 octobre 2011.
Du Dobble aux codes correcteurs d'erreurs, L3 de l'ÉNS de Lyon, LIRMM, décembre 2015 & novembre 2016.

Dernière modification : 2 janvier 2023