Mathématiques bases 1
- Feuille de TD:
- TD1: Langage mathématique [PDF]
- TD2 Suites numériques [PDF]
- TD3.1: Fonction: limte et continuité [PDF]
Agrégation: Anneaux et corps
- Feuille de TD:
- TD1: Arithmétique [PDF]
- TD2: Anneaux [PDF]
- TD3: Arithmétique dans les anneaux [PDF]
- TD4: Polynôme [PDF]
- TD5: Corps [PDF]
Graphes
- Notes de cours: [PDF]
- Feuille de TD et méthodes:
- TD1: Techniques de dénombrement[PDF]
- TD2: Premières notions sur les graphes [PDF]
- TD3: Connectivité [PDF]
- TD4: Chemin eulérien et hamiltonien [PDF]
- TD5: Arbres [PDF]
- TD6: Jeux [PDF]
- TD7: Coloriages [PDF]
- TD8: Graphes planaires [PDF]
- TD9: Ramsey [PDF]
- TD10: Théorie algébrique (dose homéoptatique) [PDF]
Enseignement Mathématiques discrètes (L1)
- 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]
- Slide 2: Fonctions et applications [PDF]
- Slide 3: Cardinalité [PDF]
- Slide 4: Relations [PDF]
- Slide 5: Graphes [PDF]
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