2023-2024 / INFO0902-1

Structures des données et algorithmes

Durée

26h Th, 20h Pr, 40h Proj.

Nombre de crédits

 Bachelier en sciences de l'ingénieur, orientation ingénieur civil5 crédits 
 Bachelier en sciences informatiques5 crédits 
 Master en science des données, à finalité5 crédits 
 Master : ingénieur civil en informatique, à finalité5 crédits 
 Master : ingénieur civil en science des données, à finalité5 crédits 
 Master en sciences informatiques, à finalité5 crédits 
 Master en ingénieur de gestion, à finalité5 crédits 
 Master en bioinformatique et modélisation, à finalité5 crédits 
 Master en sciences géographiques, orientation géomatique, à finalité6 crédits 
 Master en sciences mathématiques, à finalité6 crédits 

Enseignant

Pierre Geurts

Langue(s) de l'unité d'enseignement

Langue française

Organisation et évaluation

Enseignement au deuxième quadrimestre

Horaire

Horaire en ligne

Unités d'enseignement prérequises et corequises

Les unités prérequises ou corequises sont présentées au sein de chaque programme

Contenus de l'unité d'enseignement

La résolution de problèmes complexes consiste en grande partie en leur décomposition en sous-problèmes standards pour lesquels existent des algorithmes et des structures de données efficaces et bien étudiés. Ce cours présente une introduction au fonctionnement et à l'emploi des principales structures de données et aux algorithmes associés.
Le cours abordera notamment les éléments suivants:

  • Outils d'analyse d'algorithmes (correction d'algorithmes, notations asymptotiques)
  • Algorithmes de tris (tri par fusion, tri rapide, tri par tas...)
  • Structures de données élémentaires (piles, files, vecteurs, ensembles, files à priorité, tas, graphes...)
  • Structures de données de type dictionnaire (arbres binaires de recherche, tables de hachage, tries...)
  • Méthodes de résolution de problèmes (force brute, diviser pour régner, algorithmes gloutons, programmation dynamique...)
  • Algorithmes sur les graphes (parcours, recherche du plus court chemin, arbre recouvrant...)
L'approche se voudra scientifique: nous tenterons de déterminer systématiquement des bornes sur le temps d'exécution et d'exprimer les comportements asymptotiques de nos algorithmes.

Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement

À l'issue du cours, les étudiants maîtriseront les bases de l'algorithmique et auront une bonne connaissance des principales structures de données. Face à un nouveau problème d'implémentation, ils seront capables de faire un choix argumenté sur la structure et sur les algorithmes de manipulation de cette structure les plus appropriés étant donné les contraintes liées au problème. Ils seront également capables de mettre en œuvre les principaux outils théoriques d'analyse de performance des algorithmes.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, III.1, III.2, IV.1, IV.2, VI.1, VI.2, VII.2 du programme de bachelier ingénieur civil.

Savoirs et compétences prérequis

Le cours suivant est pré-requis:

Activités d'apprentissage prévues et méthodes d'enseignement

L'apprentissage se fera au travers de cours théoriques hebdomadaires de deux heures, par des répétitions (presque) hebdomadaires de deux heures également et par la réalisation de projets. Ces projets viseront à mettre en pratique les notions théoriques vues au cours. Ils nécessiteront d'analyser un problème, déterminer le meilleur algorithme pour le résoudre et les structures de données associées, et d'implémenter la solution en langage C.
La participation au cours théorique et aux répétitions est facultative mais vivement conseillée. La réalisation des projets est obligatoire.

Mode d'enseignement (présentiel, à distance, hybride)

Le cours se donne au deuxième quadrimestre en présentiel, en français.

Lectures recommandées ou obligatoires et notes de cours

Plusieurs ouvrages de référence seront recommandés aux étudiants, mais leur lecture est non nécessaire. Les transparents utilisés pour le cours, les énoncés et solutions des exercices et autres matériels seront accessibles sur l'espace eCampus du cours.

Modalités d'évaluation et critères

Modalités d'examen:

  • 1ère session (juin): 3 projets (30%), examen écrit (70%).
  • 2ème session: 1 projet de rattrapage si l'étudiant n'a pas réalisé les projets de l'année (10%), examen écrit (90%).
  • La réalisation des projets est requise pour avoir accès à l'examen. Un étudiant ayant réalisé les projets pendant l'année peut conserver sa cote de projet pour la seconde session.

Stage(s)

Remarques organisationnelles et modifications principales apportées au cours

Les contenus du cours théorique et des répétitions seront disponibles sur l'espace eCampus du cours, ainsi que les projets et autres informations utiles.

Contacts

  • Enseignant: Pierre Geurts, +32 4 366 28 75, p.geurts@uliege.be
  • Assistants: TBD
  • Moyens de contact privilégiés: courrier électronique (info0902@uliege.be) ou contact personnel après le cours ou sur rendez-vous

Association d'un ou plusieurs MOOCs

Notes en ligne

Support de cours sur Ecampus
Les notes de cours, les exercices de travaux pratiques et les énoncés de projet sont disponibles sur Ecampus