UE
UE — Complexité algorithmique
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.
Prérequis
- ue-mathematiques-discretes
Théorie de la complexité — Étude approfondie : Théorie de la complexité.
Notion de complexité algorithmique (temps, espace)
- complexité
- O(n)
- O(n²)
- O(log n)
- temps
- espace
- efficacité
Diviser pour régner (tri fusion, exponentiation rapide)
- diviser pour régner
- tri fusion
- merge sort
- exponentiation rapide
- récursivité
Algorithmes distribués — Étude approfondie : Algorithmes distribués.
Algorithmes d'optimisation — Étude approfondie : Algorithmes d'optimisation.
Algorithmique avancée
- algorithme
- boucle
- liste
- recherche
- tri
- complexité
Recherche, tri et filtrage dans une table
- recherche
- tri
- filtrage
- sélection
- projection
- critère
Algorithmes de tri (tri par insertion, tri par sélection)
- tri
- tri par insertion
- tri par sélection
- comparaison
- échange
- invariant
Recherche dichotomique dans un tableau trié
- dichotomie
- recherche dichotomique
- tableau trié
- diviser pour régner
- logarithme
Programmation dynamique (mémoïsation, sous-problèmes optimaux)
- programmation dynamique
- mémoïsation
- sous-problème
- Fibonacci
- optimal
- tableau
Recherche textuelle (algorithme naïf, Boyer-Moore)
- recherche textuelle
- motif
- Boyer-Moore
- automate
- chaîne de caractères
Algorithmes de graphes — Étude approfondie : Algorithmes de graphes.
Algorithmes gloutons
- glouton
- optimisation
- choix local
- rendu de monnaie
- sac à dos
Algorithmes sur les arbres (parcours en profondeur, en largeur)
- parcours en profondeur
- parcours en largeur
- DFS
- BFS
- arbre
- récursivité
Algorithmes sur les graphes (parcours, plus court chemin, détection de cycle)
- Dijkstra
- BFS
- DFS
- plus court chemin
- cycle
- graphe
- parcours
Sources : Référentiel UE Logopoïos (data/ue/ue-disciplines.json) · Programmes types Licence — L2+L3 — Informatique · enrich-real:licence-informatique.yaml · validated:scrape:umontpellier