Durée
26h Th, 20h Pr, 40h Proj.
Nombre de crédits
Enseignant
Suppléant(s)
Langue(s) de l'unité d'enseignement
Langue française
Organisation et évaluation
Enseignement au deuxième quadrimestre
Horaire
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...)
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.
Savoirs et compétences prérequis
Le cours suivant est pré-requis:
- INFO2009: Introduction à l'Informatique (http://progcours.ulg.ac.be/cocoon/cours/INFO2009-2.html)
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 ; enseignement à distance)
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
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 suppléant: Pascal Fontaine, +32 4 366 28 75, Pascal.Fontaine@uliege.be
- Assistants: Jean-Michel Begon, +32 4 366 29 72, jm.begon@ulg.ac.be Romain Mormont, r.mormont@uliege.be
- Moyens de contact privilégiés: courrier électronique ou contact personnel après le cours ou sur rendez-vous
Adaptation des engagements pédagogiques suite à la pandémie de COVID-19 pour la session de mai-juin
Méthodes d'apprentissage mises en œuvre : enseignement à distance
Des podcasts sont mis à disposition des étudiants sur eCampus, avec des petits questionnaires QCM. Pendant le quadrimestre, une séance de réponses aux questions est organisée chaque semaine.
Une séance de réponses aux questions sera aussi organisée avant l'examen.
Matière de l'évaluation
La matière pour l'examen est l'ensemble de la matière vue avant la période de confinement en présentiel, ainsi que la matière des podcasts.
Méthodes d'évaluation
L'évaluation sera basée sur un questionnaire de type QCM/réponses courtes en ligne via eCampus. Le questionnaire est à pénalité (une réponse erronée donne lieu à des points négatifs, il est possible d'avoir des réponses correctes, et quand même avoir un total de 0 au questionnaire). Les étudiants ayant plus de 12/20 au questionnaire, et ayant une note supérieure à 10/20 aux projets ont validé le cours sans autre examen nécessaire.
La note finale est la moyenne pondérée à 50% pour le projet, et à 50% pour l'examen QCM.
On se réserve la possibilité d'organiser un oral de rattrapage en première session pour les étudiants hors critères pour la dispense (moins de 12/20 au questionnaire, ou moins de 10/20 aux projets), mais dont la moyenne ci-dessus est supérieure à 8/20.
Contact
Voir les contacts ci-dessus.
Adaptation des engagements pédagogiques suite à la pandémie de COVID-19 pour la session août-sept
Matière de l'évaluation
La matière pour l'examen est l'ensemble de la matière vue avant la période de confinement en présentiel, ainsi que la matière des podcasts.
Méthodes d'évaluation (et plateforme utilisée)
Les étudiants ayant obtenu moins de 10/20 pour les projets devront les refaire pour la seconde session. Si le résultat est toujours sous 10/20, cela constituera la note finale.
Sinon, il y aura un examen où les étudiants pourront préparer par écrit et sur ordinateur les quelques questions qui leur seront attribuées. Il y aura ensuite un court examen oral pour discuter des réponses. Toutes les interactions auront lieu via eCampus. La note finale sera composée à 50% de la note de projet et 50% de la note de l'examen.
Il y aura une séance de réponses aux questions avant l'examen.
Contact(s)
Voir les contacts ci-dessus.
Notes en ligne
Page web du cours
Cette page web contient les transparents du cours, les exercices de répétitions et les détails sur les projets.