v2.11.0 (5648)

Programme d'approfondissement - CSC_51050_EP : Algorithmique avancée

Domaine > Informatique.

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 uns des paradigmes principaux de l'algorithmique, notamment flots et couplages et programmation linéaire. Il revient ensuite rapidement sur la NP-complétude et notamment sur l'importance des 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. Ce sera l'occasion de présenter entre autres les notions de potentiel, de noyau, de largeur arborescente.


Modalités d'évaluation : Examen sur table à l'issue du cours.
Langue du cours : Français
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

-

Niveau requis : Les prérequis minimaux sont quelques éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux) 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).

Avoir suivi INF423, INF431 ou des cours d'informatique de niveau équivalent est utile.

Pour les étudiants du diplôme Programmes d'échange internationaux

Les prérequis minimaux sont quelques éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux) 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). Avoir suivi INF423, INF431 ou des cours d'informatique de niveau équivalent est utile.

Règle d'exclusion : UE CSC_51050_EP

Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique

Niveau requis : Les prérequis minimaux sont quelques éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux) 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).

Avoir suivi INF423, INF431 ou des cours d'informatique de niveau équivalent est utile.

Règle d'exclusion : UE CSC_51055_EP

Pour les étudiants du diplôme M1 MPRI - Fondements de l'Informatique

Niveau requis : Les prérequis minimaux sont quelques éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux) 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).

Avoir suivi INF423, INF431 ou des cours d'informatique de niveau équivalent est utile.

Format des notes

Numérique sur 20

Littérale/grade réduit

Pour les étudiants du diplôme MSc X-HEC Entrepreneurs

Vos modalités d'acquisition :

Modalités d'évaluation : Examen sur table à l'issue du cours.

Pour les étudiants du diplôme M1 CPS - Système Cyber Physique

L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 5 ECTS

Pour les étudiants du diplôme Programmes d'échange internationaux

Le rattrapage est autorisé (Note de rattrapage conservée)
    L'UE est acquise si note finale transposée >= C
    • 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

    Le rattrapage est autorisé (Note de rattrapage conservée)
      L'UE est acquise si note finale transposée >= C
      • Crédits ECTS acquis : 5 ECTS

      La note obtenue rentre dans le calcul de votre GPA.

      Pour les étudiants du diplôme M1 MPRI - Fondements de l'Informatique

      Le rattrapage est autorisé (Note de rattrapage conservée)
        L'UE est acquise si Note finale >= 10
        • Crédits ECTS acquis : 5 ECTS
        Veuillez patienter