Algorithmique et programmation

Pré-requis nécessaires

Même si les notions sont reprises, il est préférable d'avoir suivi un UE d'informatique au premier semestre (portail MPMEI ou ISI).

Objectifs

A la fin de ce cours, l'étudiant doit:

• connaitre et savoir utiliser les bases de la programmation impérative (structures de contrôles, fonctions) ; être familiarisé avec des éléments avancés (récursivité)
• connaitre les bases du typage et de la vérification des types, savoir utiliser les types de base et quelques structures de données (tableaux, enregistrements)
• être familiarisé avec la notion de complexité d'un algorithme
• connaitre et savoir implémenter une ou plusieurs solutions pour résoudre un problème algorithmique simple (jusqu'aux algorithmes de tris) ; pouvoir appliquer une analyse descendante sur un problème
• appliquer de bonnes pratiques de programmation : décomposer en fonction, commenter, spécifier ; pouvoir utiliser un langage de programmation impératif dans ce contexte.

Compétences visées

A la fin de ce cours, l'étudiant doit:

• connaitre et savoir utiliser les bases de la programmation impérative (structures de contrôles, fonctions) ; être familiarisé avec des éléments avancés (récursivité)
• connaitre les bases du typage et de la vérification des types, savoir utiliser les types de base et quelques structures de données (tableaux, enregistrements)
• être familiarisé avec la notion de complexité d'un algorithme
• connaitre et savoir implémenter une ou plusieurs solutions pour résoudre un problème algorithmique simple (jusqu'aux algorithmes de tris) ; pouvoir appliquer une analyse descendante sur un problème
• appliquer de bonnes pratiques de programmation : décomposer en fonction, commenter, spécifier ; tester, corriger un code ; pouvoir utiliser un langage de programmation impératif dans ce contexte.

Descriptif

• Notion d'algorithme
• Les différentes catégories d'instructions algorithmiques. Structures de contrôle (conditionnelles, boucles).
• Définitions de fonctions, spécification et appels de fonctions. Fonctions récursives.
• Variables. Types de données de base. Structures de données.
• Apprentissage d'un langage impératif classique.
• Algorithmes classiques : recherche séquentielle, par dichotomie. Tris (à bulle, fusion, insertion, sélection, rapide, par tas).
• Une introduction aux types abstraits pourra également être faite.

Bibliographie

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein (trad. de l'anglais par Xavier Cazin et Georges-Louis Kocher), Algorithmique : cours avec 957 exercices et 158 problèmes, Paris, Dunod, 2010