Objectifs (en termes de compétences)

- Concevoir et réaliser un algorithme correct et efficace pour un problème donné.

- Faire un choix argumenté sur l'utilisation de telle ou telle structure de données ainsi que sur l'algorithme qui la manipule.

- Mettre en oeuvre des structures de données et les algorithmes associés dans des programmes Java de qualité professionnelle.

- Appliquer à bon escient les principes de la programmation orientée-objet tels que généricité, abstraction, composition et réutilisation.

- Travailler efficacement en équipe pour l'analyse du problème posé, la conception, l'implémentation et la documentation des programmes résolvant les problèmes posés.

Objet de l'activité (principaux thèmes à aborder)

- Mesures de complexité d'un algorithme et méthodes d'analyse de complexité.
- Méthodes de conception de programmes : spécifications et conception orientée-objet.
- Structures de données de base (listes, arbres, arbres binaires de recherche) : étude de leurs propriétés abstraites, de leurs représentations concrètes, de leur application et des principaux algorithmes qui les manipulent.
- Introduction aux Design Patterns liés à la manipulation de structures de données.
- Structures de données avancées (tables de hachage, tas, arbres binaires équilibrés, représentation et manipulation de graphes, traitement de données textuelles, dictionnaires).

Résumé : Contenu et Méthodes

- Complexité calculatoire.
- Arbres, arbres binaires de recherche, arbres AVL, 2-4 Trees.
- Dictionnaires et tables de hachage.
- Files de priorité et tas.
- Graphes (représentations, algorithmes de parcours, plus court chemin).
- Manipulation de données textuelles (arbres de suffixes, pattern matching, compression).
- Design patterns en Java.

Autres informations (Pré-requis, Evaluation, Support, ...)

- Pré-requis:
(1) Maîtrise de la programmation dans un langage orienté-objet tel que Java et connaissance de structures de données élémentaires (piles, files, listes, etc.)

OU

(1) LINF1150 Introduction à l'algorithmique et la programmation: 1ère partie B. LeCharlier
(2) LINF1251 Introduction à l'algorithmique et à la programmation : 2ème partie P. VanRoy

OU

(1) FSAC1650 Informatique T6

- Références
Ouvrage(s) obligatoire(s)
(1) Goodrich et Tamassia, "Data Structures and Algorithms in Java, Third Edition" , John Wiley & Sons, 2004.

Ouvrage(s) recommandé(s)
(2) Cormen T.H. et al. , "Introduction to Algorithms, Second Edition" , MIT Press, 2001. Brassard G. & Bratley P., "Fundamentals of Algorithms" , Prentice Hall, 1996.

- Modalités d'organisation
(1) La méthode pédagogique suivie dans ce cours est celle de l'Approche par Problèmes (APP) décrite à l'adresse http://www.fsa.ucl.ac.be/candis. Les étudiants travaillent alternativement en groupe (analyse du problème, point sur les connaissances théoriques à acquérir, définition des tâches de chacun, mise en commun de solutions partielles, analyse critique des résultats, etc.) et individuellement (étude et acquisition personnelle du contenu théorique, prise en charge d'une partie de la programmation et de la documentation des programmes, réflexion personnelle sur les questions posées, etc.). La majorité des séances de travail en groupe sont encadrées par un tuteur (le titulaire ou un assistant).

(2) Evaluation continue des travaux de groupes (réponses aux questions relatives à chaque problème donné, programme résultat et sa documentation).

(3) Examen écrit individuel

- Remarques:
Site WEB du cours: http://www.info.ucl.ac.be/notes_de_cours/LINF2121/

Autres crédits de l'activité dans les programmes