Algorithmique fondamentale, Graphes et Test

Présentation

  • Élaboration d'un schéma de résolution pour un problème donné (aspects données et contrôle).
  • Évaluation de la qualité d'un programme (complexité, test unitaire, preuve d'invariants).
  • Exploitation de la théorie des graphes, algorithmes d’optimisation.

Descriptif

Partie Algorithmique et test : acquisition des bases en algorithmique permettant d'élaborer un schéma de résolution pour un problème donné

  • Représentation des données (modèles formels de données, Types Abstraits de Données, implantation via structures de données associées), spécifications d'algorithmes adaptés.
  • Évaluation de la qualité des programmes produits (complexité, éléments de preuve de programme), test et validation d’une application simple (objectifs et méthodes de test, test unitaire, analyse et interprétation des résultats des tests, arrêt du test).

 Partie Graphes :

  • Introduction aux notions de Relations et Graphes (applications, terminologie et représentation).
  • Résolution de problèmes de cheminement et connexité (chemins eulériens, hamiltoniens, postier chinois, composantes connexes),
  • algorithmes de plus court chemin (Dijkstra, Floyd, Ford-Bellman, A*),
  • modélisation et résolution de problèmes classiques d'optimisation (recouvrement, flots, coloration, ordonnancement).

Bibliographie

  • 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
  • Le test des logiciels, S. Xanthakis, P. Régnier et C. Karapoulios, Hermès, 2000.

Modalités de contrôle des connaissances

Session 1 ou session unique - Contrôle de connaissances

Nature de l'enseignementModalitéNatureDurée (min.)NombreCoefficientRemarques
UECCTravaux Pratiques1/3
UECTEcrit - devoir surveillé12012/3

Session 2 : Contrôle de connaissances

Nature de l'enseignementModalitéNatureDurée (min.)NombreCoefficientRemarques
UECTEcrit - devoir surveillé12011Pas de report de CC, même favorable.