Algorithmes et Structures de Données

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