Descriptif
Ce cours porte sur des techniques avancées dans la conception et l'analyse des algorithmes. Le cours commence par un parcours rapide de quelques notions fondamentales telles que la programmation linéaire ou la NP-complétude et les réductions polynomiales. Au delà de l'analyse de pire cas, on envisage plusieurs approches possibles de l'analyse d'algorithmes, d'une part au travers des notions de complexités: pire-cas, en moyenne, amortie, lissée, ou paramétrique, et d'autre part au travers de mesures de qualités de sortie: optimalité, facteur d'approximation pour l'optimisation, de compétitivité pour l'algorithmique on-line. Le cours abordera entre autres les notions de potentiel, de noyau issu de prétraitement, de largeur arborescente, d'algorithme primal-dual, SAT solvers.
Modalités d'évaluation : Examen sur table à l'issue du cours.
Langue du cours : English unless all students prefer french.
Ressources pédagogiques : Les ressources sont la page moodle mais une ancienne page permet de se faire une idée du style du cours.
Credits ECTS : 4
Diplôme(s) concerné(s)
- Programmes d'échange internationaux
- M1 CCSN - Maj. CPS - Système Cyber Physique
- Titre d’Ingénieur diplômé de l’École polytechnique
- MSc X-HEC Entrepreneurs
- M1 FODQ - Maj. QMI - Quantique, Mathematiques, Informatique
- M1 FODQ - Maj. MPRI - Fondements de l'Informatique
Parcours de rattachement
Pour les étudiants du diplôme Programmes d'échange internationaux
Les prérequis minimaux sont des éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux; algorithmes gloutons, programmation dynamique, algorithmes de flots) et de complexité des algorithmes (bornes supérieures et inférieures à la complexité dans le pire cas pour les tris), et une bonne familiarité avec l'outil mathématique (preuve par induction, etc).
Règle d'exclusion : UE CSC_51050_EP
Pour les étudiants du diplôme M1 CCSN - Maj. CPS - Système Cyber Physique
Les prérequis minimaux sont des éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux; algorithmes gloutons, programmation dynamique, algorithmes de flots) et de complexité des algorithmes (bornes supérieures et inférieures à la complexité dans le pire cas pour les tris), et une bonne familiarité avec l'outil mathématique (preuve par induction, etc).
Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Les prérequis minimaux sont des éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux; algorithmes gloutons, programmation dynamique, algorithmes de flots) et de complexité des algorithmes (bornes supérieures et inférieures à la complexité dans le pire cas pour les tris), et une bonne familiarité avec l'outil mathématique (preuve par induction, etc).
Règle d'exclusion : UE CSC_51055_EP
Pour les étudiants du diplôme MSc X-HEC Entrepreneurs
Les prérequis minimaux sont des éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux; algorithmes gloutons, programmation dynamique, algorithmes de flots) et de complexité des algorithmes (bornes supérieures et inférieures à la complexité dans le pire cas pour les tris), et une bonne familiarité avec l'outil mathématique (preuve par induction, etc).
Pour les étudiants du diplôme M1 FODQ - Maj. MPRI - Fondements de l'Informatique
Les prérequis minimaux sont des éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux; algorithmes gloutons, programmation dynamique, algorithmes de flots) et de complexité des algorithmes (bornes supérieures et inférieures à la complexité dans le pire cas pour les tris), et une bonne familiarité avec l'outil mathématique (preuve par induction, etc).
Format des notes
Numérique sur 20Littérale/grade américainPour les étudiants du diplôme M1 FODQ - Maj. QMI - Quantique, Mathematiques, Informatique
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 7
- le rattrapage peut être demandé par l'étudiant si :
- 7 ≤ note initiale < 10
- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme Programmes d'échange internationaux
Vos modalités d'acquisition :
Examen sur table à l'issue du cours.
Rattrapage possible si note <10, sous forme d'oral de rattrapage capé à 10.
Le rattrapage est autorisé (Max entre les deux notes)- le rattrapage est obligatoire si :
- Note initiale < 10
- le rattrapage peut être demandé par l'étudiant si :
- Note initiale < 10
- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Vos modalités d'acquisition :
Examen sur table à l'issue du cours.
Rattrapage possible si note <10, sous forme d'oral de rattrapage capé à 10.
Le rattrapage est autorisé (Max entre les deux notes)- le rattrapage est obligatoire si :
- Note initiale < 10
- le rattrapage peut être demandé par l'étudiant si :
- Note initiale < 10
- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme M1 FODQ - Maj. MPRI - Fondements de l'Informatique
Vos modalités d'acquisition :
Examen sur table à l'issue du cours.
Rattrapage possible si note <10, sous forme d'oral de rattrapage capé à 10.
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 7
- le rattrapage peut être demandé par l'étudiant si :
- Note initiale < 7
- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme MSc X-HEC Entrepreneurs
Vos modalités d'acquisition :
Examen sur table à l'issue du cours.
Rattrapage possible si note <10, sous forme d'oral de rattrapage capé à 10.
Le rattrapage est autorisé (Max entre les deux notes)- le rattrapage est obligatoire si :
- Note initiale < 10
- le rattrapage peut être demandé par l'étudiant si :
- Note initiale < 10
- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme M1 CCSN - Maj. CPS - Système Cyber Physique
Vos modalités d'acquisition :
Examen sur table à l'issue du cours.
Rattrapage possible si note <10, sous forme d'oral de rattrapage capé à 10.
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 7
- le rattrapage peut être demandé par l'étudiant si :
- Note initiale < 7
- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.