Algorithmique 2

Cette page est maintenue par les enseignants et utilisée par les élèves de la matière concernée. Vos contributions sont les bienvenues, mais merci d'en discuter avant de faire des modifications non triviales de la page, pour être sûr de ne pas perturber le déroulement du cours.

  Première Année    Informatique 

Bienvenue sur la page d'Algo 2. Cette page est un complément de la page Chamilo du cours, qui est la page de référence.

Présentation

Objectifs

Le cours d'Algorithmique et structures de données (Algo 2) fait suite au cours d'Algorithmique et programmation en Ada (Algo 1). Il s’agit de prolonger les acquis du premier semestre en insistant sur la maîtrise du coût d’un algorithme et le choix des structures de données. Voir Algorithmique 2 : Motivation

Les TP en temps libre permettent aux étudiants d’étudier concrètement les notions vues en CTD, ainsi qu’éventuellement d’autres notions d’algorithmique et de programmation.

Fonctionnement

1h30 de CM + 1h30 de TD par semaine. Contrairement à Algo 1, il n'y a pas de séance en salles machines de prévu : c'est à vous de prendre l'initiative de coder certains algorithmes donnés en CTD.

1 TP en temps libre, à faire en binôme, est également au programme.

Travail personnel recommandé

1 heure par semaine sur le cours et les TD + 15 à 20 heures par étudiant pour le TP temps libre.

Contenu

• Analyse des algorithmes : analyses en meilleur et pire cas, en moyenne et coût amorti (séances 1 à 3).
• Structures de données :
  • Arbres (séances 4 à 6)
  • Dictionnaires (séances 7 à 13)
  • Files de priorité (séances 14 à 16)
  • Graphes (séances 21 et 22)
• Programmation récursive ; diviser pour régner et théorème "magique" (séances 17 à 20).

Des révisions sont au programme des séances 23 et 24. Le langage Ada est utilisé comme support.

Documents

Concepts Ada à connaître

• Arbres binaires et leur codage en Ada. Voir aussi le fichier intro_arbres_binaires.adb dans le dépot GitHub.
• Enregistrements avec discriminants et application aux arbres d'expression arithmétique. Le fichier expressionsarith.adb accompagnant le document se trouve dans le dépot GitHub.

Exo interactif

• Algorithmique 2: exo d'introduction au coût en moyenne

Bibliographie indicative

• C. Froidevaux, M.C. Gaudel, M. Soria : "Types de données et algorithmes", McGraw-Hill, 1990.
• T. Cormen, C.E. Leiserson, R. Rivest, C. Stein : "Introduction to algorithms", MIT Press, 2nd edition, 2001.
• A.V. Aho, J.E. Hopcroft, J.D. Ullman : "Data structures and algorithms", Addison-Wesley, 1985.
• R. Graham, D. Knuth, O. Patashnik: "Concrete Mathematics", Addison-Wesley, 2nd edition, 1994.

Liens divers

A compléter : n'hésitez pas à participer !

• Catégorie "Algorithms" sur Wikipédia.
• Catégorie "Data Structures" sur Wikipédia.
• Dictionary of Algorithms and Data Structures (site de la NIST).
• Animation pour comprendre la construction des ABR, AVL, B-arbres, arbres rouges-noirs ...
• Algo-rythmique
• Humour.