 | | |
| INFO0902-1 | Structures des données et algorithmes
|
|
| Durée : | 30h Th, 30h Pr |
|
| Nombre de crédits : |
| Bachelier en sciences de l'ingénieur, orientation ingénieur civil, 2e année | | Deuxième quadrimestre | | 5 |
|
| Bachelier en sciences informatiques, 1re année | | Deuxième quadrimestre | | 6 |
|
| Master en ingénieur civil en informatique, à finalité approfondie, 1re année | | Deuxième quadrimestre | | 5 |
|
| Master en ingénieur civil en informatique, à finalité spécialisée en gestion, 1re année | | Deuxième quadrimestre | | 5 |
|
| Master en bioinformatique et modélisation, à finalité approfondie, 1re année | | Toute l'année | | 6 |
|
| Master en bioinformatique et modélisation, à finalité approfondie, 1re année | | Deuxième quadrimestre | | 6 |
|
| Master en sciences mathématiques, à finalité approfondie, 1re année | | Deuxième quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité didactique, 1re année | | Deuxième quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée en gestion, 1re année | | Deuxième quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée en informatique, 1re année | | Deuxième quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée en informatique, 2e année | | Deuxième quadrimestre | | 6 |
|
| Master en sciences mathématiques, à finalité spécialisée en statistiques, 1re année | | Deuxième quadrimestre | | 8 |
|
| Master en sciences mathématiques, à finalité spécialisée, 1re année | | Deuxième quadrimestre | | 8 |
|
| Master en sciences mathématiques | | Deuxième quadrimestre | | 8 |
|
|
|
| Nom du professeur : | Pierre Geurts |
|
Langue(s) du cours :
|
| Langue française |
|
Contenus du cours :
|
| La résolution de problèmes complexes consiste en grande partie en leur décomposition en sous-problèmes standards pour lesquelles 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:
- structures de données élémentaires (piles, queues, files à priorité, tas)
- arbres binaires
- tables de hachage
- méthodes de résolution de problèmes: diviser pour régner, algorithmes gloutons, programmation dynamique
- algorithmes de tris
- algorithmes sur les graphes: parcours, recherche de 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) du cours :
|
| A 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 structures les plus appropriés étant donné les contraintes liés au problème. Ils seront également capables de mettre en oeuvre les principaux outils théoriques d'analyse de performance des algorithmes. |
|
Prérequis et corequis / Modules de cours optionnels recommandés :
|
| Connaissances de base en algorithmique et en programmation, et en particulier du langage de programmation C (telles que fournies par le cours INFO2009-1). |
|
Activités d'apprentissage prévues et méthodes d'enseignement :
|
| L'apprentissage se fera au travers de cours théoriques hebdomadaires de 2h et par le 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 est facultative mais vivement conseillée. La réalisation des projets est obligatoire. |
|
Mode d'enseignement (présentiel ; enseignement à distance) :
|
| Cours en présentiel. |
|
Lectures recommandées ou obligatoires et notes de cours :
|
| Plusieurs ouvrages de référence seront recommandés aux étudiants, mais non nécessaires. Les transparents utilisés pour le cours, les énoncés et solutions des exercices et autres matériels seront accessibles sur la page web du cours. |
|
Modalités d'évaluation et critères :
|
| L'évaluation finale se fera sous la forme d'un examen écrit. La cote des projets interviendra dans la cote finale du cours et leur réalisation est requise pour avoir accès à l'examen. |
|
Contacts :
|
| Enseignant: Pierre Geurts - Tel: 04/366.48.15 - e-mail: p.geurts@ulg.ac.be
Assistant: Gilles Louppe - e-mail:g.louppe@ulg.ac.be
Moyens de contact privilégiés: e-mail ou contact personnel après le cours ou sur rendez-vous |
|
|
|
| Notes en ligne : |
|
| Notes en ligne |
| Disponible sur la page web du professeur. |
|
|
