Algorithmique II (INFO602_INFO)

Présentation

Ce module présente de nouveaux éléments d'algorithmique, qui font suite à l'étude des structures de données linéaires et arborescentes, tout en restant assez indépendant des algorithmes sur les graphes. Les notations asymptotiques et la complexité en pire cas est rappelée. Le module donne alors les outils pour calculer la complexité des algorithmes récursifs, notamment ceux qui ont une stratégie de type divide-and-conquer. Ensuite sont présentés des techniques pour déterminer les temps d'exécution des algorithmes dans les cas où l'analyse en pire cas échoue, notamment l'analyse amortie. Dans la deuxième partie, nous nous intéressons plus à de nouveaux algorithmes pour traiter des problèmes classiques. D'une part, les structures efficaces pour l'union disjointe sont exposées. D'autre part, nous

décrivons des algorithmes simples de géométrie algorithmique, ainsi que les structures de localisation spatiale.

Plan du cours

Les outils présentés au début du cours sont utilisés pour justifier l'efficacité des algorithmes décrits.

TDs : Chacun des TDs permet de mettre en pratique les différents concepts d'algorithmique vus en cours. Les premiers TDs font travailler les notations asymptotiques, puis font calculer les complexités d'algorithmes récursifs. Ensuite, des exercices sur l'analyse amortie sont proposés. Ils terminent par un exemple complet sur les structures de données dynamique par doublement de taille. Les derniers TDs font travailler les étudiants sur de petits problèmes géométriques et leur résolution algorithmique.

TPs : Le premier TP montre l'intérêt des structures d'union disjointe lorsque l'on cherche à segmenter une image. Ces structures rendent les approches bottom-up extrêmement efficaces. Le deuxième TP porte sur le calcul de l'enveloppe convexe d'un nuage de point. Le troisième TP montre l'intérêt des structures de localisation spatiale lorsque l'on veut faire un programme de simulation temps réel où de multiples objets se déplacent en même temps et peuvent collisionner avec des obstacles. Les structures k-d-tree sont alors très efficaces pour détecter les collisions lorsque des milliers de particules se déplacent en même temps. Les TPs sont réalisés en C, avec la bibliothèque GTK pour la partie graphique/interface.

Volume horaire

  • CM : 7.5
  • TD : 7.5
  • TP : 12.0

Diplômes intégrant ce cours

En bref

Crédits ECTS : 3

Langue d'enseignement
Français

Contact(s)

UFR, Écoles, Instituts

Lieu(x)

  • Le Bourget-du-Lac (73)