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: NP complétude [PDF]
TD5: Autres classes de complexité [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:
Accélération en temps Manuel Cabarcos Baulina,Damien Guagno
Équivalence entre machine RAM et machine de Turing Nicolas Broders, Clémence Courdy-Bahsoub, Vincent Cousin
Machine non déterministe universelle Sophie RUMIN, Mara Berlow, Romain Grimal
Équivalence entre machines à 2 compteurs et machines de Turing Flavien Clastres-Babou, Sandra Alfaro-Romero et Yann Caminade
Équivalence entre machines à 2 piles et machines à 2 compteurs Théophane Lhommelet et Adrian Roussel-Fayard
Temps et espace de calcul utilisé par une machine universelle Ravfaste, Ales Gubarevich et Mathieu Pont
Somme partielle est NP-complet Matthieu Lenoir et Antoine Bugnicourt
Théorème de Mahaney Loïc Goulefert et Sylvain Durand
Indécidabilité des problèmes de Post modifié et de Post Timothee Thibaut et Jonathan Lao-Kan
Algorithme polynomial pour SAT si P=NP Hugues Freville et Vincent Guillebaud
1Lit3SAT est NP-complet Alary, Bernardino
Théorème de Ladner:Maxime Durand, Kevin Counta et Lucas Clément

Enseignements passés

Lien