Algo et complexité

Algo et complexitéCode de l'UE : HLIN401

Présentation

La première étape consiste à expliciter le rôle et l'importance de l'analyse théorique de la complexité et de fournir les outils mathématiques adéquats (notation asymptotique). Le cours s'intéresse essentiellement à l'analyse dans le pire des cas et les raisons de ce choix seront expliquées. On commencera par regarder les tris, car ils permettent une analyse simple sans structure de données spécifique. On regardera ensuite les traversées d'arborescence, structure de données essentielle en informatique. Ensuite seront étudiés les structures spécifiques de tas (file de priorité) et d'ABR (arbre binaire de recherche). Une présentation succincte des arbres équilibrés sera donnée (pour justifier l'utilisation des ABR). Enfin, on regardera quelques applications de l'analyse de complexité, par exemple la recherche de stable de taille minimum dans un graphe.

Volume horaire

  • CM : 15
  • TD : 18
  • TP : 16.5
Diplômes intégrant cette UE

En bref

Crédits ECTS 5

Nombre d'heures 49 HE

Période de l'année
S4