Introduction à l'algorithmique

Langue
d'enseignement

Français

Préalables

LSINC1101

Thèmes abordés

Le cours vise à introduire l’étudiant·e aux principales méthodes de construction d’algorithmes sur base d’une spécification répondant à un problème identifié. La récursion sert de base et l'évaluation de l’efficacité repose sur le calcul du temps d'exécution (théorie de la complexité). Nous utilisons des structures de données récursives : listes, arbres binaires, arbres rouges-noirs, etc. Ainsi que des méthodes systématiques de construction de programmes efficaces : la méthode "diviser pour régner", la mémoïsation, la programmation dynamique, la méthodes gloutonne et la méthode générer/tester.

Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :
.	A la fin de cette unité d’enseignement, l’étudiant·e est capable de :         formaliser une solution récursive à partir de l’énonce d’un problème donné ; calculer la complexité théorique d’un algorithme (récursif ou non) simple ; définir et utiliser une structure de données récursive ; résoudre le problème de façon systématique pour proposer un programme correct et efficace.

Contenu

Le cours aborde les points suivants :

• Spécification par pré- et post-conditions
• Évaluation du temps d'exécution
• Récursion
• Structures de données récursives: listes, arbres binaires, arbres rouges-noirs
• Méthodes de construction de programmes : "diviser pour régner", mémoïsation, programmation dynamique, méthode gloutonne, générer/tester

Méthodes d'enseignement

Un cours magistral illustré de nombreux exemples, plus des travaux pratiques. Les étudiants sont également invités à faire des exercices à domicile.

Modes d'évaluation
des acquis des étudiants

Examen écrit.

Autres infos

Le cours suit une partie du livre: Hetland, Magnus Lie. Python Algorithms: mastering basic algorithms in the Python Language. Apress, 2014.

Faculté ou entité
en charge

SINC