Semestre 7 – Algorithmique et complexité

Objectifs

  • Étude des méthodes pour la construction des algorithmes efficaces.
  • Étude de quelques méthodes fondamentales pour traiter des problèmes NP-difficiles.
  • Capacité a construire et analyser des algorithmes pour résoudre des problèmes NP-complets.
  • Connaissance d’une collection des problèmes NP-complets.
  • Connaissance des éléments fondamentaux de la complexité : NP-complétude et le problème « P=NP? ».
  • Choix des problèmes algorithmiques à étudier dans des domaines divers (graphes, réseaux, ordonnancement, géométrie, biologie, etc.) pour illustrer l’applicabilité des méthodes étudiés.

Prérequis

Algorithmique avancée (Licence informatique de l’UL) ou une unité d’algorithmique équivalente

Notation « grand-O », Conception et analyse des algorithmes (niveau L3), quelques algorithmes tri et algorithmes de graphes efficaces, Structures de données.

Contenu pédagogique de l’UE

  • Conception et analyse des algorithmes efficaces : diviser pour régner, programmation dynamique, algorithme glouton ;
  • Algorithmes randomisés : type Monte Carlo, type Las Vegas, variable aléatoire, espérance, temps attendu ;
  • Structures de données aléatoires : skip-listes, treaps ;
  • Algorithmes d’approximation : rapport d’approximation, analyse de rapport d’approximation d’un
    algorithme, types de qualité d’approximation ;
  • Introduction à la complexité : classes de complexité P et NP, question fondamentale P=NP?, conséquences algorithmiques, NP-complétude, réductions polynomiales ;