Partager cette page :

Algorithmique 1 : méthodes algorithmiques et algorithmique des graphes

Semestre Semestre 1
Type Obligatoire
Nature UE
Crédits ECTS 6
Volume horaire total 40
Volume horaire CM 20
Volume horaire TD 20

Pré-requis

Mathématiques élémentaires (démonstrations).
Notions d'algorithmiques de base (boucles, conditionnelles, etc.). Algorithmique du tri. Quelques notions en algorithmique des graphes.

Objectifs

  • À la fin du cours, les étudiants savent concevoir des algorithmes à partir des paradigmes algorithmiques classiques. Ils savent adapter des structures de données à leur besoin.
  • Ils savent écrire un invariant et un variant d'un algorithme.
  • Ils savent démontrer la terminaison, la complexité, la correction d'un algorithme.

Contenu

Description du cours

Ce cours traite des paradigmes algorithmiques classiques (algorithmes gloutons, programmation dynamique et programmation linéaire), des structures de données classiques (files de priorité, tables de hachage) et de l’algorithmique des graphes.

 


Références

Lien du site du cours : http://www.emmanuelcaruyer.com/algo1.php

 

Bibliographie

• Algorithms de S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.
• Algorithms, R. Sedgewick, Addison-Wesley.
• Éléments d’algorithmique, D. Beauquier, J. Berstel, Ph. Chrétienne, Masson.
• Types de données et algorithmes, C. Froidevaux, M.-C. Gaudel, M. Soria, McGraw-Hill-InterEditions.
• Algorithmics, The Spirit of Computing. David Harel.
• Algorithm design, Jon KIeinberg et Eva Tardos.

Contrôles des connaissances

• Une note de contrôle continu (CC) : un devoir à la maison et un devoir sur table de deux heures
• En session de rattrapage, un examen oral (O).
Tous documents/matériels sont autorisés.
Note finale en session 1 : CC
Note finale en session 2 : O

Mise à jour le 3 mai 2018