Bloc 5 : Algorithmique avancée
La formation et l'évaluation auront lieu entiérement en distanciel.
Retour à la page principale DIU-EIL à Lyon1.
Retour à la page principale Bloc 5.
Présentation
Contenu de l'UE
- 1. Algorithmes classiques
- Algorithmes sur les listes, arbres binaires, arbres binaires de recherche et graphes (notamment parcours en profondeur et en largeur)
- 2. Algorithmes avancés
- Programmation dynamique
- Algorithmes randomisés
- Recherche textuelle
- Introduction à l'intelligence artificielle et à l'apprentissage
- 3. Complexité et calculabilité
- Complexité et classes de problèmes
- Calculabilité, décidabilité et machines de Turing
Adéquation avec le programme de NSI
La partie du programme de NSI de Terminale liée à cette UE s’appelle “Algorithmique” dont voici la description : Le travail de compréhension et de conception d’algorithmes se poursuit en terminale notamment via l’introduction des structures d’arbres et de graphes montrant tout l’intérêt d’une approche récursive dans la résolution algorithmique de problèmes. On continue l’étude de la notion de coût d’exécution, en temps ou en mémoire et on montre l’intérêt du passage d’un coût quadratique à n log n ou de n à log n. Le logarithme en base 2 est ici manipulé comme simple outil de comptage (taille en bits d’un nombre entier).| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Algorithmes sur les arbres binaires et sur les arbres binaires de recherche. | Calculer la taille et la hauteur d’un arbre. Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d’abord). Rechercher une clé dans un arbre de recherche, insérer une clé. | Une structure de données récursive adaptée est utilisée. L’exemple des arbres permet d’illustrer la programmation par classe. La recherche dans un arbre de recherche équilibré est de coût logarithmique. |
| Algorithmes sur les graphes. | Parcourir un graphe en profondeur d’abord, en largeur d’abord. Repérer la présence d’un cycle dans un graphe. Chercher un chemin dans un graphe. | Le parcours d’un labyrinthe et le routage dans Internet sont des exemples d’algorithme sur les graphes. L’exemple des graphes permet d’illustrer l’utilisation des classes en programmation. |
| Méthode « diviser pour régner ». | Écrire un algorithme utilisant la méthode « diviser pour régner ». | La rotation d’une image bitmap d’un quart de tour avec un coût en mémoire constant est un bon exemple. L’exemple du tri fusion permet également d’exploiter la récursivité et d’exhiber un algorithme de coût en n log n dans les pires des cas. |
| Programmation dynamique. | Utiliser la programmation dynamique pour écrire un algorithme. | Les exemples de l’alignement de séquences ou du rendu de monnaie peuvent être présentés. La discussion sur le coût en mémoire peut être développée. |
| Recherche textuelle. | Étudier l’algorithme de Boyer-Moore pour la recherche d’un motif dans un texte. | L’intérêt du prétraitement du motif est mis en avant. L’étude du coût, difficile, ne peut être exigée. |