Introduction à l'algorithmique

lsinc1103  2022-2023  Charleroi

Introduction à l'algorithmique
5.00 crédits
30.0 h + 30.0 h
Q2

  Cette unité d’enseignement n’est pas accessible aux étudiants d’échange !

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


Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
Bachelier en sciences informatiques