Algorithmique et structures de données [ LSINF1121 ]

• Maîtrîse de la programmation dans un langage orienté-objet tel que Java
• Connaissance de structures de données élémentaires (piles, files, listes, etc.)
• Notions de récursion et de complexité calculatoire.

• 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.
• 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).

Les étudiants ayant suivi avec fruit ce cours seront capables de

• faire un choix argumenté sur l'utilisation des principales structures de données utilisées pour représenter des collections,
• utiliser à bon escient les algorithmes existants pour manipuler ces structures de données et analyser leur performance,
• appliquer les principes de la programmation orientée-objet tels que généricité, abstraction, composition et réutilisation,
• concevoir et mettre en oeuvre des variantes des algorithmes étudiés dans des programmes Java de haute qualité.

Les étudiants auront développé des compétences méthodologiques et opérationnelles.  En particulier, ils auront développé leur capacité à :

• analyser de façon critique un problème posé
• apprendre par eux-mêmes dans un ouvrage de référence et dans la documentation technique complémentaire
• travailler efficacement en groupe pour l'analyse d'un problème posé, la conception, l'implémentation et la documentation des programmes produits
• équilibrer le travail individuel et le travail en groupe
• gérer le temps d'apprentissage et produire une solution satisfaisante aux problèmes posés en respectant les délais prescrits.

La note pour ce cours repose sur une double évaluation :

1. La participation effective de chaque étudiant durant les séances tutorées et le respect des échéances (20 %, évalué par chaque tuteur et le titulaire).
2. La note à l'examen final (80 %, évalué par le titulaire).

En cas de seconde session, seule la note à l'examen final en seconde session sera prise en compte (pour 100 % de la note finale donc).

La matière obligatoire pour l'examen final est constituée du contenu de tous les documents disponibles sur le site iCampus de ce cours, des informations communiquées oralement lors des séances tutorées hebdomadaires, ainsi que tous les chapitres du livre de référence mentionnés dans l'énoncé d'au moins une des missions. Le livre de référence est la seule ressource dont la consultation est autorisée durant l'examen final.

La méthode de pédagogie active suivie dans ce cours est inspirée de l'Approche Par Problèmes (APP). Cette méthode repose sur plusieurs phases de travail, certaines encadrées par des tuteurs. Outre les séances tutorées, une des composantes essentielles de cette pédagogie consiste à faire apprendre chaque étudiant par lui-même. La réussite du processus d'apprentissage présuppose donc une implication significative de chaque étudiant. Le rôle du travail en groupe est principalement de débattre des concepts étudiés et, secondairement, d'organiser le travail de chacun. L'apprentissage proprement dit reste de la responsabilité de chaque étudiant.

Le travail est organisé en missions que chaque groupe d'étudiants doit accomplir dans un délai strict (typiquement de 2 semaines par mission). Ces missions comportent des questions auxquelles il faut apporter les meilleurs réponses possibles et des problèmes de programmation, pour lesquels il faut produire des programmes Java.

Les missions ont pour but principal de créer un contexte et une motivation pour l'apprentissage de la matière et des capacités méthodologiques à développer. Arriver au bout d'une mission n'est donc pas une fin en soi. Il importe d'y être arrivé en ayant profité de l'occasion pour développer les objectifs d'apprentissage explicités dans l'énoncé de chaque mission.

• Complexité calculatoire,
• Arbres, arbres binaires de recherche,
• Arbres équilibrés,
• Dictionnaires et tables de hachage,
• Files de priorité et tas,
• Graphes
• Manipulation de données textuelles (pattern matching et de compression)

Ouvrage de référence (obligatoire):

• Goodrich and Tamassia, Data structures and algorithms in Java, 5th edition, John Wiley and suns, 2011, ISBN: 978-0-470-39880-7

Ouvrages recommandés:

• Cormen T.H. et al. , "Introduction to Algorithms, Second Edition" , MIT Press, 2001.
• Brassard G. & Bratley P., "Fundamentals of Algorithms" , Prentice Hall, 1996.

Et plus généralement les documents (énoncés des missions, conseils pour l'examen,...) disponibles sur: http://www.icampus.ucl.ac.be/claroline/course/index.php?cid=SINF1121