Enseignement Mathématiques discrètes (L2)

Notes de cours: [PDF]
Feuille de TD et méthodes:
TD1: Premières notions sur les ensembles [PDF]
TD2: Notions sur les langages [PDF]
TD3: Fonctions et applications [PDF]
TD4: Cardinal des ensembles finis [PDF]
TD5: Ensembles dénombrables [PDF]
TD6: Relations [PDF]
TD7: Relations d'ordre [PDF]
TD8: Quelques problèmes sur les graphes [PDF]
Transparents
Slide 1: Notion d'ensemble et de langage [PDF] [TEX]
Slide 2: Fonctions et applications [PDF] [TEX]
Slide 3: Cardinalité [PDF] [TEX]
Slide 4: Relations [PDF] [TEX]
Slide 5: Graphes [PDF] [TEX]

Décidabilité et complexité (L3)

Support pédagogique

Slide
[PDF]
Feuilles d'execices
TD1: Modèles de calcul et complexités en temps et espace [PDF]
TD2: Classes de complexité́ en temps dé́terministe [PDF]
TD3: Classes de complexité́ en temps non dé́terministe [PDF]
TD4: Compétude [PDF]
Bibliographie
Complexité algorithmique Sylvain Perifel (le livre est accessisble gratuitement ici)
Computational Complexity Sanjeev Arora et Boaz Barak
Complexité et Décidabilité Patrick Dehornoy

Contrôle continue

Par groupe de trois vous devez préparer un exposé qui durera 15 min et sera suivi de 5 min de questions. Pour l'exposé, on vous demande de situer le théorème proposé, de donner les idées principales de la démonstration et éventuellement de donner des applications à ce théorème.
Vous devez nous envoyer une liste ordonnée de trois sujet avant vendredi 3 mars aux deux enseignants mais vous pouvez demander des conseils si vous souhaitez être aiguillé:
guillaume.feuillade@irit.fr
msablik@math.univ-toulouse.fr
Sujets d'exposés pour le contrôle continue
Equivalence entre machines à 2 piles et machines de turing: (section 7.3.1 de ici)
Equivalence entre machines à 2 compteurs et machines de turing: (section 7.3.2 de ici)
Indécidabilité des problèmes de Post modifié et Post: (section 3.5 de ici)
Indécidabilité de l'ambiguité d'une grammaire algébrique: (section 3.7.2 de ici)
Temps et espace de calcul utilisé par une machine universelle: (p19 de Complexité algorithmique)
Accélération en temps: (p33 de Complexité algorithmique)
Prime est dans NP et coNP: exercice 4 feuille TD3
Machine non déterministe universelle (p46 de Complexité algorithmique)
Théorème de hiérarchie en temps non déterministe (p52 de Complexité algorithmique)
Trouver un ensemble indépendant dans un graphe est NP-complet (p80 de Complexité algorithmique)
Somme Partielle est NP-complet (p83 de Complexité algorithmique)
1Lit3SAT est NP-complet (p79 de Complexité algorithmique)
Machine non déterministe universelle (p46 de Complexité algorithmique)
Théorème de Ladner: si P≠NP alors il existe un problème A∈NP tel que A∉P et A n'est pas NP-complet (p86 de Complexité algorithmique)
Théorème de Mahaney(p90 de Complexité algorithmique)
Algorithme polynomial pour SAT si P=NP (p93 de Complexité algorithmique)
QBF est PSPACE-complet (p110 de Complexité algorithmique)
Théorème de Savitch (p119 de Complexité algorithmique)
Je rapelle que le livre Complexité algorithmique de Sylvain Perifel est accessisble gratuitement ici.
Attribution des sujets:
Trouver un ensemble indépendant dans un graphe est NP-complet: Laporte Anna, Petitcol Noémie, Roumieu Chloé
Indécidabilité des problèmes de Post modifié et Post: Lary Guillaume, Mevolhon Claire, Vo Michael
Equivalence entre machines à 2 compteurs et machines de turing: Belloncle Renaud, Bigé Mégane, Ferbu Bastien
Temps et espace de calcul utilisé par une machine universelle: Leclerc Corentin, Lopes Christopher
Prime est dans NP et coNP:Cherbeix Clément, Lespagnol Cédric, Seguin Florian
Accélération en temps:Bierman Floris, Bourgois Astrid
Equivalence entre machines à 2 piles et machines de Turing:Andriamiseza Rialy, Dufour Olivier

Enseignements passés

Lien