Licence informatique
INVALIDE-Algorithmique fondamentale et graphes
Code apogéeDIFO4AFOStructurexxDernière mise à jour le04 Juillet 2017
Responsable pédagogiqueLEMARCHAND Laurent (Maître de conférences, 27ème section)
Intervenants
Parcours
  • INVALIDE-Licence 2 - parcours informatique
  • INVALIDE-Licence 2 - parcours mathématiques et calcul scientifique
TypeObligatoire
Semestre4Volume horaire60Crédits ECTS6
Nombre d'heures Cours magistraux (CM)22 Travaux dirigés (TD)22 Travaux pratiques (TP)16 
Pré-requisAlgorithmique et Programmation (S2), langages de programmation (S3)
Co-requis 
Objectif Terminal 
Objectif Pédagogique 
Contenu détaillé de l'enseignement
  • 30h Algorithmique Fondamentale (12 h CM, 12h TD, 6h TP) :

    • D’un problème posé à un schéma de résolution.

Caractérisation et définition d’éléments intervenant dans un schéma de résolution à partir de l’expression d’un problème:

  1. modèles formels de données (ensembliste, vectoriel, matriciel).

  2. Spécification de Types Abstraits de Données.

  3. Utilisation de types génériques à partir de leurs spécifications

  4. Spécifications de procédures et/ou de fonctions abstraites

    • D’un schéma de résolution à une mise en œuvre algorithmique efficace. Composants de cette mise en œuvre :

  1. Définition d’un langage algorithmique lien avec des approches en programmation (impératif, objet). Utilisation de structures de données linéaires : Tableaux, listes. Exemples de mise en œuvre algorithmique à partir d’un schéma de résolution (algorithmes récursifs, itératifs, éléments de preuve de programme,)

  2. Eléments de complexité d’un algorithme : notations de Landau, règles pratiques pour la détermination de la complexité d’un algorithme, résolution de certaines équations de récursion (une ou deux heuristiques). Exemples de choix d’algorithmes en fonction de leur complexité.

  3. Test d’algorithmes et algorithmique de tests.

  • 30h algorithmique dans les graphes (10h CM, 10h TD, 10h TP):
    • Relations et Graphes : introduction, applications, terminologie et représentation.
    • Quelques problèmes élémentaires dont les solutions utlisent les graphes: cheminement et connexité (chemins euleriens, hamiltonnien, postier chinois, composantes connexes),
    • algorithme de plus court chemin (Dijkstra).
    • modélisation de problèmes d'optimisation à l'aide des graphes et algorithmes de résolution de problèmes classiques : recouvrement, flots, coloration, ordonnancement. graphes planaires.
    • Structures de données associées aux graphes et applications en TP

Méthodes d'enseignement

Algorithmique:CM/TD/TP étude de cas
Graphes : CM/TD/TP

Les TP pourront avoir comme langage de mise en oeuvre C.

dispensé en anglais dans le parcours international 

Evaluation session 1

CC algorithmique (2/10) + CC graphes (2/10) + Ecrit de synthèse 3h (3/10 + 3/10)

Evaluation session 2

Oral, sous réserve de décision du jury

ecrit de synthèse 2h (1/2+1/2)

Références Bibliographiques
  • Concepts fondamentaux de l'informatique: A. AHO, J. ULLMAN ed: DUNOD
  • Optimisation combinatoire T2: programmation discrète, M. Sakarovitch, Hermann, 1984
  • Méthodes d'optimisation, I. Charon et al., Masson, 1996
  • Introduction à l'algorithmique, T.H. CORMEN, C.E. LEISERSON & R.L. RIVEST, Dunod