AccueilLicence généraleInformatiqueEnseignementsAlgorithmique et applications

Licence InformatiqueUE Algorithmique et applications

Contenu

Objectifs du module :

  • Analyser la complexité des algorithmes.
  • Apprendre les structures des données arborescentes et leur application pour la mémorisation et recherche efficace d’information.
  • Apprendre les notions et les algorithmes fondamentaux sur les graphes et leur application aux problèmes d’ordonnancement et d’optimisation.

Plan :

Complexité des Algorithmes :

  • Introduction à l’étude de la complexité temporelle des algorithmes
  • Notion de complexité asymptotique, ordre de croissance de fonctions, borne inférieure et supérieure des temps d’exécution.
  • Analyse de simples algorithmes récursifs et résolution des relations de récurrence.
  • Cas d’étude : analyse des algorithmes de tri et de recherche dans un tableau.
  • Détermination d’une borne inférieure pour les algorithmes de tri basés sur comparaison

Les Graphes et leurs applications :

  • Introduction aux graphes et leur utilisation pour modéliser des problèmes d’optimisation et d’ordonnancement.
  • Représentation des graphes par listes d’adjacences et par matrices d’adjacences
  • Algorithmes de parcours : parcours en largeur et en profondeur.
  • Applications des algorithmes de parcours : recherche d’un circuit dans un graphe orienté et tri topologique
  • Algorithmes de plus court chemin (PCC) dans un graphe pondéré et sa résolution : algorithmes de Dijkstra et de Bellman-Ford, algorithme de PCC dans un graphe orienté acyclique.
  • Implémentation en C des algorithmes de parcours, tri topologique et de PCC

Les structures arborescentes et leurs applications

  • Les arbres binaires de recherche.
  • Les arbres équilibrés : les arbres AVL
  • Le tas (heap) et applications : algorithme de tri et files de priorité.
  • Les arbres n-aires
  • Les arbres lexicographiques

Compétences visées

A l’issue du module l’étudiant doit être capable de / d’ :

  • expliquer les Algorithmes de Chemin Plus Court (source unique et toute paire de sommets), d’ Arbre Couvrant Minimum et de Flot Maximum pour les graphes
  • utiliser les algorithmes sur les graphes et les implanter dans un langage de programmation
  • expliquer les methodologies de projet d'algorithme : algorithmes gloutons et programmation dynamique
  • expliquer la notion de hashage et la conception d'une fonction d'hachage de qualité, algorithmes de hachage par chainage et par sondage
  • expliquer la structure de tas binaire.
  • utiliser cette structure pour réaliser la structure de file de priorité et l'algorithme de compression de Huffman
  • expliquer les avantages des arbres binaires de recherche équilibrés, les arbres rouges et noirs et les B-arbres

Langue utilisée

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

Bibliographie

  • T. Cormen, C. Lieserson, R. Rivest, C. Stein Introduction à l'algorithmique, ed.Dunod, 2002
  • B.W. Kernighan, D.M. Ritchie, Le langage C, Ed. 2ème édition, Dunod, 2000
  • Support de cours en forme électronique fourni aux étudiants

Pré-requis recommandés

  • Eléments de programmation en C (structures de contrôle, structures des données statiques et dynamiques, récursivité).
  • Structures des données élémentaires (listes chaînes, files, piles).
  • Algorithmes de base de tri et de recherche.

Modalités d'organisation

Méthodes pédagogiques :

Leçons magistrales, exercices en classe, petit projets ou travaux pratiques en salle machines en utilisant le langage C.

Modalités d’évaluation :

(i) évaluation des travaux pratiques réalisés en groupe (3 étudiants max. pour groupe) (ii) contrôle terminal écrit en temps défini.

Volume des enseignements

  • Cours magistraux : 20 heures
  • Travaux dirigés : 20 heures

Les formations qui utilisent cet enseignement