Descriptif et objectifs :
Ce module s'intéresse aux derniers algorithmes fondamentaux en
informatique. Nous poursuivons la liste des problèmes pour lesquels
nous savons qu'il existe un algorithme de complexité polynomiale (voir
cours Analyse d'algorithmes). Nous allons également étudier la notion
de problèmes intrinsèquement difficile via la théorie de la complexité
qui s'intéresse à classifier les problèmes selon l'existence ou non
d'un algorithme de complexité polynomial. Nous allons, en dernier lieu,
caractériser la notion de fonctions calculables au sens mathématiques.
Public visé : Ce module s'adresse aux étudiants de Master M1 en Informatique de l'université de
Montpellier II.
Le contenu de ce module est le suivant en algorithmique.
- Le problème du flot maximum
- Quelques applications combinatoires du problème du flot maximum
- Les problème de flots compatible et flot maximum de coût minimum.
- La résolution du problème d'offres et de demandes par le problème du flot maximum.
- Le problème du couplage maximum de poids minimum dans un graphe
- Le
problème de coloration (arêtes et sommets) dans les graphes
(premier problème dit NP-complet. Cette notion de complextié sera
détaillé dans la partie Théorie de la complexité).
Le contenu de ce module est le suivant en Complexité.
- Définition de la notion réduction entre deux problèmes
- Présentation de quelques classes de complexité (P, NP, Co-NP, NP-complet,...)
- Le premier problème NP-complet, le problème de Satisfaisabilité dit SAT
- Exemples de transformations polynomiales entre deux problèmes NP-complets
Le contenu de ce module est le suivant en Calculabilité.
- Modèle de calculs
- Diagonalisation de Cantor
- Théorème de Rice
Répartition des cours :Partie algorithmique :*lundi 20/09 à 15H00
*jeudi 23/09 à 9H45
*Jeudi 7/10 à 9H45
*Jeudi 14/10 à 9H45
Partie complexité :*lundi 27/09 à 15H00 (problème d'amphi) A récupérer
*lundi 4/10 à 15H00
*lundi 11/10 à 15H00
*Lundi 18/10 à 15H00 (a confirmer)ƒ
Partie calculabilité :*jeudi 21/10 à 9H45
*jeudi 4/11 à 9H45
*jeudi 18/11 à 9H45
*jeudi 25/11 à 9H45
Répartition des Travaux dirigés :*les lundis à 16H30 et les jeudis à 11H30
*les mardis de 9H30 à 13H00
Documents à télégharger : Le cours : le cours complet
Les travaux dirigés : l'ensemble des travaux dirigés
Les travaux pratiques : le tp pour l'année 10-11Les corrections des travaux dirigés :Correction du travaux DirigésLes corrections des travaux pratiques : Résolution de problèmes NP-difficiles
Descriptif et objectifs : ce module consiste à étudier du
point de vue de la résolution des problèmes qui sont classifiés comme
NP-complets. Nous proposerons plusieurs stratégies pour tenter de les
résoudre au mieux.
Public visé : Ce module s'adresse aux étudiants de Master M1 en Informatique et en Mathématiques-Informatique de l'université de
Montpellier II.
Le contenu de ce module est le suivant :
- Méthodes approchées sans garantie de performance
- Programmation linéaire & Programamtion linéir een nombres entiers
- Méthodes exactes (programmation dynamique, branch and bound, branch and cut)
- Méthodes apporchées avec garantie de performance
- Classes d'approximation