UE — Complexité algorithmique

Licence — L2+L3 | Informatique | 6 ECTS

Unité d'enseignement « Complexité algorithmique » — Informatique (L2, L3). Cette UE permet de construire les bases conceptuelles, méthodologiques et pratiques associées à la thématique.

Informations générales

  • Discipline : Informatique
  • Niveau : Licence — L2+L3
  • Volume horaire : 60h CM/TD
  • ECTS : 6
  • Prérequis : Mathématiques discrètes (ue-mathematiques-discretes)
  • Date de mise à jour : 27 mai 2026

Compétences visées

  • Démontrer les théorèmes fondamentaux relevant de « Complexité algorithmique ».
  • Mettre en œuvre les méthodes de calcul propres à « Complexité algorithmique ».
  • Modéliser un problème en mobilisant les concepts de « Complexité algorithmique ».
  • Communiquer ses résultats de manière claire et structurée.

Vocabulaire clé

complexité O(n) O(n²) O(log n) temps espace efficacité diviser pour régner tri fusion merge sort exponentiation rapide récursivité algorithme boucle liste recherche tri filtrage sélection projection critère tri par insertion tri par sélection comparaison échange invariant dichotomie recherche dichotomique tableau trié logarithme programmation dynamique mémoïsation sous-problème Fibonacci optimal recherche textuelle motif Boyer-Moore automate chaîne de caractères glouton optimisation choix local rendu de monnaie sac à dos parcours en profondeur parcours en largeur DFS BFS arbre Dijkstra plus court chemin cycle graphe

Thèmes abordés

T1. Théorie de la complexité

Étude approfondie : Théorie de la complexité.

T1.1. Notion de complexité algorithmique (temps, espace)
  • Complexité
  • Notation O(n)
  • Notation O(n²)
  • Notation O(log n)
  • Complexité en temps
  • Complexité en espace
  • Efficacité algorithmique

T2. Algorithmes distribués

Étude approfondie : Algorithmes distribués.

Aucun sous-thème défini pour ce thème.

T3. Algorithmes d'optimisation

Étude approfondie : Algorithmes d'optimisation.

T3.1. Algorithmique avancée
  • Algorithme
  • Boucle
  • Liste
  • Recherche
  • Tri
  • Complexité

T3.2. Recherche, tri et filtrage dans une table
  • Recherche
  • Tri
  • Filtrage
  • Sélection
  • Projection
  • Critère de sélection

T3.3. Algorithmes de tri (tri par insertion, tri par sélection)
  • Tri
  • Tri par insertion
  • Tri par sélection
  • Comparaison d'éléments
  • Échange d'éléments
  • Invariant de boucle

T3.4. Recherche dichotomique dans un tableau trié
  • Dichotomie
  • Recherche dichotomique
  • Tableau trié
  • Diviser pour régner
  • Logarithme (complexité)

T3.5. Programmation dynamique (mémoïsation, sous-problèmes optimaux)
  • Programmation dynamique
  • Mémoïsation
  • Sous-problème
  • Suite de Fibonacci
  • Solution optimale
  • Tableau de mémoïsation

T3.6. Recherche textuelle (algorithme naïf, Boyer-Moore)
  • Recherche textuelle
  • Motif à rechercher
  • Algorithme naïf
  • Algorithme de Boyer-Moore
  • Automate fini
  • Chaîne de caractères

T4. Algorithmes de graphes

Étude approfondie : Algorithmes de graphes.

T4.1. Algorithmes gloutons
  • Algorithme glouton
  • Optimisation
  • Choix local optimal
  • Problème du rendu de monnaie
  • Problème du sac à dos

T4.2. Algorithmes sur les arbres (parcours en profondeur, en largeur)
  • Parcours en profondeur (DFS)
  • Parcours en largeur (BFS)
  • Arbre binaire
  • Arbre n-aire
  • Récursivité

T4.3. Algorithmes sur les graphes (parcours, plus court chemin, détection de cycle)
  • Algorithme de Dijkstra
  • Parcours en largeur (BFS)
  • Parcours en profondeur (DFS)
  • Plus court chemin
  • Détection de cycle
  • Graphe orienté
  • Graphe non orienté

Ressources complémentaires