Algorithmique et structures de données

lsinf1121  2019-2020  Louvain-la-Neuve

Algorithmique et structures de données
Note du 29 juin 2020
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.
5 crédits
30.0 h + 30.0 h
Q1
Enseignants
Schaus Pierre;
Langue
d'enseignement
Français
Préalables
  • Maîtrise 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écurrence et de complexité calculatoire et spatiale.

Le(s) prérequis de cette Unité d’enseignement (UE) sont précisés à la fin de cette fiche, en regard des programmes/formations qui proposent cette UE.
Thèmes abordés
  • Mesures de complexité d'un algorithme et méthodes d'analyse de complexité.
  • Algorithmes de tris et recherche dichotomiques
  • 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 (union'find, tables de hachage, tas, arbres binaires équilibrés, représentation et manipulation de graphes, traitement de données textuelles, dictionnaires).
Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

1 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,
- concevoir et mettre en oeuvre des variantes des algorithmes étudiés,
- tester des algorithmes et des structures de données,
- utiliser à bon escient les algorithmes et structures de données documentées dans une l'API ,
- abstraire, modéliser et d'implémenter des solutions efficaces à des problèmes de type « puzzle » algorithmiques.

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é,
- tester et debugger des programmes algorithmiques,
- implémenter efficacement des algorithmes courts mais non triviaux.
- apprendre par eux'mêmes dans un ouvrage de référence et dans la documentation technique complémentaire
 

La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».
Contenu
  • 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)
Méthodes d'enseignement
La méthode de pédagogie active suivie dans ce cours est inspirée des classes inversée. Il y a six modules de deux semaines. Chaque module comporte un cours d’introduction à la matière, des exercices théoriques à préparer, des chapitres du livre de référence à lire, un TP de correction des exercices en milieu de modèle, des travaux sur inginious à réaliser (programmes Java) et finalement un cours de restructuration en fin de module. 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.. L'apprentissage proprement dit reste de la responsabilité de chaque étudiant. Pour réussir l’examen il est impératif que l’étudiant programme régulièrement.
Modes d'évaluation
des acquis des étudiants
Examen sur ordinateur à l’aide d’Inginious https://inginious.info.ucl.ac.be.
Un quizz sur deux points peut être organisé lors de la semaine smart et ne compte dans la note de l’étudiant uniquement si il fait remonter celle-ci.
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 algorithmique posé
  • apprendre par eux-mêmes dans un ouvrage de référence et dans la documentation technique complémentaire
  • produire une solution satisfaisante aux problèmes algorithmiques posés en respectant les délais prescrits.
Autres infos
Prerequis:
LEPL1401 et LEPL1402 ou cours équivalents
Bibliographie
Required Textbook:
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional.
ISBN-13: 978-0321573513
ISBN-10: 032157351X

Exercices and documents
 https://lsinf1121.readthedocs.io
Communication with students using moodle http://moodleucl.uclouvain.be/course/view.php?id=7682
Faculté ou entité
en charge
INFO


Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
Approfondissement en statistique et sciences des données

Mineure en statistique, sciences actuarielles et science des données

Mineure en sciences de l'ingénieur : informatique (accessible uniquement pour réinscription)

Master [120] : ingénieur civil en mathématiques appliquées

Master [120] en sciences informatiques

Bachelier en sciences mathématiques

Master [60] en sciences informatiques