AccueilLicence généraleInformatiqueEnseignementsAlgorithmique et structures discrètes

Licence InformatiqueUE Algorithmique et structures discrètes

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 connu

Langue utilisée

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

Bibliographie

  • Algorithmique (3ème édition). Thomas H. Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, 2010.

Pré-requis recommandés

  • Programmation 1

Volume des enseignements

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

Les formations qui utilisent cet enseignement