AccueilLicence généraleInformatiqueEnseignementsAlgorithmique 1

Licence InformatiqueUE Algorithmique 1

Contenu

L'objectif de cette unité est d'introduire les structures de données et les techniques de conception de bases de l'algorithmique, et d'étudier les outils d'analyse et de preuve de corrections des algorithmes.

  • Notions de bases pour l'analyse des algorithmes ; algorithmes de tris
  • Algorithmes de tris, optimalité asymptotique (notamment preuve de borne inférieure) ; tris linéaires
  • Tas binaire ; tri par tas binaire
  • Dictionnaire ; arbre binaire de recherche non-équilibré, insertion et suppression de clés
  • Équilibrage des arbres binaires de recherche ; files de priorité (hors tas binaire)
  • Tables de hachage, chainage simple ; nombre de collisions ; extension : filtre de Bloom ou table coucou
  • Énumération et algorithmes par rebroussement (SAT, sac-à-dos, problèmes logiques)
  • Programmation dynamique, principe et exemples (ordonnancement sur une machine, sous-séquence monotone la plus longue)
  • Graphes et représentation par liste d'incidences ; plus court chemins, algorithme de Dijkstra
  • Algorithmes de plus courts chemins : Bellman-Ford et Floyd-Warshall
  • Arbres couvrants de poids minimum, algorithmes de Prim, de Kruskal ; structure d'union-find.

Compétences visées

  • Évaluer la complexité et la correction d’une solution algorithmique (20%).
  • Mettre en œuvre des algorithmes et des structures de données (20%).
  • 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é (15%).
  • Concevoir un algorithme en utilisant des stratégies algorithmiques adaptées aux problèmes (15%).
  • 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

  • Programmation 2
  • Structures discrètes

Modalités d'organisation

Cours magistraux, TD en groupes, TP de programmation.

Volume des enseignements

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

Les formations qui utilisent cet enseignement