Algorithmes et Structures de Données

Dernière mise à jour le 27 février 2024

Présentation

Le but de cette UE est de rappeler les éléments d’algorithmique essentiels pour la programmation impérative, et ainsi acquérir ou renforcer les pré-requis aux autres UE de l’année.

Il fournit des bases en algorithmique permettant de traiter des collections de données

Principes d'induction/récurrence, preuve par récurrence,
Application pour la définition de types inductifs (introduction des principales structures de données : listes et arbres, piles, files) et l'écriture d'algorithmes récursifs (parcours, tris),
Itération et tableaux : écriture d'algorithmes itératifs sur des tableaux (parcours, tris). Comparaison avec les versions récursives.
Introduction à la complexité sur les algorithmes de tri classiques.

Pré-requis nécessaires

Pour aborder ce cours, il est utile d'avoir déjà programmé dans un langage de programmation impérative et d'avoir un minimum de connaissances sur :

les types, les variables, les opérateurs
les instructions de contrôle (appels, boucles, conditionnelles, fonctions, procédures)

Compétences visées

écrire un algorithme impératif itératif ou récursif répondant à un problème simple
tracer l’exécution d’un algorithme/programme
évaluer la complexité d’un algorithme/programme