Algorithmique et structures de données [ LSINF1121 ]

> https://icampus.uclouvain.be/claroline/course/index.php?cid=sinf1121

Au sein du programme SINF1BA : LSINF1101 et LSINF1103

Au sein du programme FSA1BA : LFSAB1401, LFSAB1101, LFSAB1102, LFSAB1201, LFSAB1202, FSAB1301

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

Eu égard au référentiel AA du programme « Bachelier ingénieur civil », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :

• AA1.1, AA1.2
• AA2.4, AA2.5, AA2.7
• AA3.2
• AA4.3

Eu égard au référentiel AA du programme « Bachelier en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :

• S1.I1, S1.I3
• S2.2, S2.3, S2.4
• S4.3
• S5.4
• S6.1, S6.3

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.

Une note de PARTICIPATION sur les différentes missions et problèmes de programmation (Inginious, etc) compte pour 20 % de la note finale + 80 % pour l'examen final.

La note de participation ne peut pas être réévaluée en seconde session,

mais seul l'examen final compte à 100 % dans la note finale de seconde session.

Note: un étudiant qui présenterait pour la *première* fois l'examen final en juin ou en septembre sera évalué de la même manière qu'en première session (20 % participation + 80 % examen)

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)

Textbook obligatoire :
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional.
ISBN-13: 978-0321573513
ISBN-10: 032157351X

Et plus généralement les documents (énoncés des missions, conseils pour l'examen, ...) disponibles sur : http://moodleucl.uclouvain.be/course/view.php?id=7682

Préalables:

• maîtrîser la programmation dans un langage orienté-objet tel que Java
• connaître et utiliser correctement de structures de données élémentaires (piles, files, listes, etc.)
• avoir des notions en matière de récursion et de complexité calculatoire.