AccueilLicence généraleInformatiqueEnseignementsAlgorithmique 2

Licence InformatiqueUE Algorithmique 2

Contenu

Cet enseignement prolonge celui d'Algorithmique 1, en accentuant les aspects de conception des algorithmes à partir de techniques générales.

  • Parcours de graphes, propriétés des parcours de graphes
  • Application des parcours de graphes (notamment tri topologique, composantes fortement connexes)
  • Flots maximum dans un graphe, coupe minimum, algorithme de chemins augmentants
  • Flots de coût minimum
  • Programmation dynamique, principes et exemples (alignement de séquences, distance d'édition, plus court chemin dans un graphe acyclique,…)
  • Diviser-pour-régner, utilisation du master theorem pour le calcul de complexité (on ne démontre pas le théorème)
  • Algorithmes gloutons et algorithmes d'approximation. On montrera des algorithmes gloutons optimaux, non-optimaux, et des algorithmes gloutons trouvant des solutions à ratio d'approximation constant
  • Algorithmes randomisés (sélection, quicksort, collectionneur de vignettes)
  • Recherche de motifs
  • Analyse amortie (exemples : itérateur sur un arbre, incrément binaire, algorithme de Knuth-Morris-Pratt)
  • Géométrie algorithmique (algorithmes par balayage, algorithmes incrémentaux)

Compétences visées

  • Évaluer la complexité et la correction d’une solution algorithmique (15%).
  • Mettre en œuvre des algorithmes et des structures de données (15%).
  • Choisir, sur des critères objectifs, les structures de données et construire ou sélectionner les algorithmes les mieux adaptés à un problème donné (20%).
  • Concevoir un algorithme en utilisant des stratégies algorithmiques adaptées aux problèmes (20%).
  • Modéliser un problème concret sous la forme d'un problème algorithmique connu (15%).
  • Faire preuve d'esprit critique vis-à-vis d'une solution technique pour en vérifier son efficacité, sa fiabilité et sa robustesse dans son contexte d'utilisation (15%).

Langue utilisée

Langue principale utilisée par cet enseignement : Français.

Bibliographie

Pré-requis recommandés

  • Algorithmique 1
  • Probabilités pour l'informatique

Modalités d'organisation

Cours magistraux, TD en groupes, TP de programmation.

Volume des enseignements

  • Cours magistraux : 18 heures
  • Travaux dirigés : 24 heures
  • Travaux pratiques : 18 heures

Les formations qui utilisent cet enseignement