Algorithmique 2 : Ada - 2009-2010

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette 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.

Laptop.png  Première Année  CDROM.png  Informatique 

Bienvenue sur la page d'Algo 2.

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

2 fois 1h30 de CTD 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.

2 TP en temps libre, à faire en binôme, sont également au programme. L'énoncé du premier sera donné en séance 6 ; il sera à rendre pour jeudi 19 mars. L'énoncé du second sera donné en séance 14 ; il sera à rendre pour jeudi 30 avril.

Travail personnel recommandé

18 heures par étudiant sur le cours, ce qui correspond par exemple à 30 minutes pour chaque séance d'1h30 + 6 heures de révision, ou encore à 45 minutes pour chaque séance d'1h30.

15 heures par étudiant pour les TP temps libre, soit 7h30 par étudiant pour chacun des TP.

Au niveau méthodologique, les recommandations données en Algo 1 restent valables.

Planning

Créneaux horaires

N'oubliez pas de vérifier régulièrement votre emploi du temps sur ADE.

Groupe Horaires des séances Salle Enseignant
1 Mardi 9h45-11h15 et jeudi 8h15-9h45 D109 Franck Hétroy
2 Lundi 9h45-11h15 et mardi 9h45-11h15 D111 Denis Trystram
3 Lundi 11h15-12h45 et mardi 8h15-9h45 H104 Zoltan Szigeti
4 Lundi 11h15-12h45 et jeudi 9h45-11h15 D208 Xavier Nicollin
5 Mardi 8h15-9h45 et jeudi 8h15-9h45 D211 Frédéric Wagner
6 Lundi 9h45-11h15 et vendredi 14h00-15h30 D213 Sylvain Boulmé

Contenu

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

Documents

Voir aussi le Kiosk.

Poly

Attention, il contient par endroits de petites erreurs. Utilisation à vos risques et périls !


Concepts Ada à connaître

  • Arbres binaires de recherche et AVL : voir le TP1 2008-2009, pages 3 à 10.

TPs

  • TP1: à rendre pour le vendredi 26 mars 16h45 dernier délai.
    • Sujet et sources fournies du TP1.
    • Enseignants correcteurs et soutien pour ce TP : Hussein Joumaa et Nassim Jibai.
    • Lire l'introduction aux enregistrements avec discriminants (pages 1-4) qui présente un concept Ada nécessaire au TP1. Par contre, il n'est pas nécessaire de lire en détail l'exemple du codage des arbres d'expression arithmétique, car celui-ci est différent du codage dans le TP1. En particulier, dans le TP1, les feuilles des arbres d'expression sont codées comme des noeuds avec 2 fils vides. Au contraire, dans l'exemple décrit ici, les feuilles sont des noeuds particuliers sans fils (la notion d'arbre vide n'y est pas pertinente).
    • La page du wiki Algorithmique 2 : TP1 est prévue pour corriger/compléter éventuellement le sujet fourni.
    • Le nombre de pages du rapport est limité à 4 (soit 2 feuilles recto-verso), ceci afin d'éviter que vous consacriez tout votre temps sur ce rapport. Le code commenté et les tests ne font pas partie de cette limitation, ajoutez-les en annexe du rapport.
  • TP2: à rendre pour le vendredi 23 avril 17h00 dernier délai.

Galerie de programmes et suggestions d'expérimentation

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

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.

Liens divers

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