Algorithmique et structures de données

5 crédits

30.0 h + 30.0 h

Cette unité d'enseignement n'est pas dispensée en 2018-2019

Langue
d'enseignement

Français

Préalables

Ce cours suppose acquises la maîtrîse de la programmation et de la conception de programmes dans un langage orienté-objet tel que Java, la connaissance de structures de données élémentaires et des notions de récursion et de complexité calculatoire telles que visées par le cours LEPL1402.

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 :

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-3.4, AA2-3.5, AA2-3.7
AA4.2
AA5.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.M1, S1.3
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,
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) ».

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

Bachelier en sciences informatiques

SINF1BA

LEPL1402

Bachelier en sciences de l'ingénieur, orientation ingénieur civil

FSA1BA

LINFO1225