Introduction à l'algorithmique

lsinc1103  2021-2022  Charleroi

Introduction à l'algorithmique
5.00 crédits
30.0 h + 30.0 h
Q2
Langue
d'enseignement
Français
Préalables
LSINC1101
Thèmes abordés
Toutes les méthodes reposent sur la démarche de spécification formelle, implémentation et preuve. L'évaluation de l'efficacité d'un problème est basée sur un calcul du temps d'éxécution et de consommation de la mémoire (théorie de la complexité) La récursion sert de base à ce cours. Nous utilisons d'abord des structures de données récursives: arbres, arbres rouges-noirs, listes, etc. Ensuite, des méthodes systématiques de construction de programmes efficaces seront présentées: 1- la méthode "diviser pour régner" 2- les méthodes de mémorisation, dont la programmation dynamique 3- la méthodes gloutonne 4- la méthode générer/tester  5- les méthodes heuristiques
Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

.
  • formaliser un problème à partir d'un énoncé ;
  • résoudre le problème de façon systématique pour proposer un programme correct et efficace.
 
Contenu
Partie I.
Spécification par pré et et post-conditions, preuves par invariants et variants. Evaluation du temps d'éxécution. Récursion. Structures de données récursives: arbres, arbres rouges-noirs, listes, etc.
Partie II.
Méthodes de construction de programmes. 1- la méthode "diviser pour régner" 2- les méthodes de mémorisation, dont la programmation dynamique 3- la méthodes gloutonne 4- la méthode générer/tester 5- la méthode des contraintes 6- les méthodes heuristiques
Exercices .
  1. Consolidation des prérequis: - écriture de spécifications; - construction d'algorithmes par la technique de l'invariant; - types abstraits (liste chaînée, liste doublement chaînée, arbre binaire,...).
2- Appropriation des méthodes vues au cours théorique: - construction d'algorithmes par les différentes méthodes; - calcul de la complexité des algorithmes construits.
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. La question principale demande de résoudre efficacement un problème nouveau.
Autres infos
Le cours suit une partie du livre: Introduction à l'algorithmique, de T. Cormen, C. Leiserson, R. Rivest, C. Stein (ed. Dunod).
Faculté ou entité
en charge
EPL


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

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