Objectifs (en terme de compétences)

Objectifs disciplinaires : être capable
- de choisir, concevoir et utiliser des structures de données fondamentales pour représenter et manipuler les informations associées à un problème,
- de donner une estimation motivée de la complexité temporelle
et spatiale des algorithmes utilisant les structures de données définies,
- de concevoir et d'utiliser des structures récursives,
- de justifier un choix entre plusieurs solutions algorithmiques pour résoudre un problème donné,
- de réaliser des programmes Java de complexité moyenne en mettant en oeuvre les principes fondamentaux de la programmation orientée-objet : généricité, abstraction, composition et réutilisation.

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

- Techniques d'analyse de la complexité calculatoire d'un algorithme.
- Conception et mise en oeuvre d'algorithmes récursifs.
- Piles, files; implémentations en tableaux et listes chaînées.
- Listes; implémentation en listes doublement chaînées.
- Arbres, algorithmes de construction et de parcours.
- Arbres binaires et applications.

Méthodologie
La méthode pédagogique suivie dans ce cours est celle de l'Approche Par Problèmes (voir http://www.fsa.ucl.ac.be/candis/). Les étudiants travaillent en groupes, partiellement encadrés par un tuteur, et individuellement. Ils sont conduits à apprendre majoritairement par eux-mêmes sur base des différentes ressources mises à leur disposition (livre de référence, énoncés des problèmes posés, sites WEB, etc.).
Ils bénéficient également des conseils d'un tuteur (guide lors de l'analyse des nouveaux problèmes, analyse critique des travaux remis,etc.) et de cours magistraux de restructuration.

Résumé : Contenu et Méthodes

- Techniques d'analyse de la complexite calculatoire d'un algorithme
- Conception et mise en oeuvre d'algorithmes récursifs
- Piles, files ; implémentations en tableaux et listes chaînées
- Listes ; implémentation en listes doublement chaînées
- Arbres, algorithmes de construction et de parcours
- Arbres binaires et applications

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

Pré-requis
- FSAC 1150 Informatique
- FSAC 1350 Informatique
- FSAC 1450 Informatique
Ou
- Connaissance de base d'un langage orienté-objet tel que Java
- Connaissance des principes élémentaires de la modélisation orienté-objet
- Capacité à raisonner sur des fragments de programme et écrire des spécifications
- Références :
Ouvrage obligatoire :
- Data Structures and Algorithms in Java, 2nd edition, Goodrich and Tamassia
John Wiley and Sons, 2001, ISBN :0-471-38367-8
Autre ouvrage recommandé :
- Java Software Solutions : Foundations of Program Design, 3rd edition,
John Lewis and William Loftus, Addison-Wesley, 2002
- Evaluation continue individuelle sur base de questionnaires à choix multiples et examen écrit individuel.
- Remarques :
- Site Web du cours : http://www.fsa.ucl.ac.be/candis/T6/info.index.html

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