Algorithmique fondamentale, Graphes et Test

Pré-requis nécessaires

Connaissances de base en algorithmique et programmation impérative, en C et en Java, correspondant aux UE “Algorithmique et programmation” (S2) et “Programmation C” (S3).

Compétences visées

• Traduire un énoncé de problème en spécification
• Modéliser les données d’un problème
• Ecrire un algorithme à partir d’une spécification
• Tester unitairement un programme

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, partitionnement 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.

Langue d'enseignement

Français