Contenu

L'objectif de cette unité d'enseignement est d'étudier les structures de données principales et leurs algorithmes, ainsi que les outils d'analyse de complexité et de preuve de correction et de terminaison des algorithmes.

  • Algorithmes sur les tableaux et les matrices : recherche dans un tableau trié (recherche dichotomique), multiplication matricielle.
  • Algorithmes de tris et borne inférieure de complexité pour les tris par comparaison. 
  • Files de priorité,
  • Dictionnaires,
  • arbres binaires de recherche et stratégie d'équilibrage
  • Tables de hachage
  • Graphes et théorème de caractérisation des arbres
  • Algorithmes d'arbres couvrants de poids minimum.

Compétences visées

  • Utiliser les concepts fondamentaux de l'informatique (langages formels, logique, et graphes) pour la programmation et la modélisation
  • Rédiger de manière synthétique et rigoureuse des preuves
  • Évaluer la complexité et la correction d’une solution algorithmique
  • Se servir aisément des bases de la logique pour valider ou réfuter un raisonnement
  • Mettre en œuvre des algorithmes et des structures de données
  • Modéliser un problème concret sous la forme d'un problème algorithmique conn