Unité d'enseignement M02 :

« Complexité »

contenu mis à jour le 2007/10/11 15:06

Description

Crédits : 6

Lieu :  U.F.R. Sciences de Luminy et U.F.R. M.I.M.

Pré-requis : Algorithmique 2 (C30INF9), Fondements de l'Informatique

Semestre :  S1

Cours/TD/TP : 24h/24h/12h

Code APOGEE (U2) : C51IN02

Code APOGEE (U1) : 2INF12

Responsables :

Résumé : L'objectif de cours est de traiter de la Complexité des Algorithmes, c'est à dire de la difficulté pour programmer ces algorithmes de manière "efficace". On abordera tout d'abord le problème de manière générale en montrant qu'il existe des classes d'algorithmes de complexité équivalente (P et NP par exemple). Dans une deuxième partie on montrera comment calculer la complexité des programmes (par ex : prévoir son temps d'exécution en fonction de la taille des données), et les méthodes pour l'améliorer. La dernière partie abordera les principales classes de complexité.

Plan :

Ressources pédagogiques fournies : Polycopié, page web, La deuxième partie de ce cours est disponible en video sur le web Une partie de ce cours est disponible sur le site eCUME de l'Université de la Méditerranée (accessible via l'ENT ou en partie ici : http://ecume.univmed.fr/course/view.php?id=800) et sur le site des enseignants.

Site Web  : http://ecume.univmed.fr/course/view.php?id=800

Apparaît dans les parcours