DIU - Bloc 5
Algorithmique Avancée

Projets

1. Algorithme de Karatsuba
   [diviser pour régner] Multiplication d'entiers longs de $n$ chiffres, plus rapide que $O(n^2)$. Problème abordé dans le chapitre 5 du cours.
2. Plus grande sous-suite croissante
   [programmation dynamique] Etant donnée une suite d'immeubles de différentes étages construits près de la côte, combien faut-il en démolir au minimum pour que les immeubles préservés aient tous vue sur la mer? Ce problème est abordé en détails dans le livre Programmation Efficace page 55 avec un scan ici.
3. Silhouette d'immeubles: lignes des toits
   [diviser pour régner] Il s'agit de calculer le profile (ou lignes des toits), une suite de points à coordonnées entières avec abscisses croissantes, d'un ensemble de $n$ immeubles donné par une liste de rectangles se recouvrant éventuellement et alignés sur une même horizontale (le sol). Chaque rectangle (ou immeuble) pourra être définit par trois entiers: l'abscisse du bord gauche, la hauteur et la largeur. La solution en $O(n\log{n})$ peut s'apparenter au tri fusion de profiles.
4. Rotation d'une image sans mémoire auxilliaire
   [diviser pour régner, défaut de cache] Dans le programme officiel NSI de Terminale, pour la méthode diviser pour règner il est indiqué: "La rotation d’une image bitmap d’un quart de tour avec un coût en mémoire constant est un bon exemple." L'enjeu est d'en proposer une explication convaincante. Il s'agit d'effectuer la rotation en-place d'une image de pixels (bitmap) d'un quart de tour. En-place signifie qu'on utilise un nombre constant de mémoire temporaire. Une technique diviser pour régner permet de le faire en limitant le nombre de défauts de cache (dans le cas où le bitmap est trop gros pour tenir dans le cache). Un des formateurs fournira un programme en python simulant un mécanisme de cache pour illustrer l'algorithme dont l'efficacité semble motivée par une limitation du nombre de fois où chaque ligne de la matrice est chargée dans le cache. Ainsi, on sort du modèle RAM. Il est possible que la motivation des auteurs des programmes soient moins alambiquées. .
5. Emploi du temps
   [recherche exhaustive] Il y a $n$ cours à répartir sur $k$ créneaux avec des contraintes du type: des élèves doivent suivre à la fois le cours $i$ et le cours $j$, qui ne peuvent donc figurer sur le même créneau. On peut se ramener au problème de coloration en $k$ couleurs d'un graphe à $n$ sommets.
6. Distance d'édition de Levenshtein
   [programmation dynamique] Calculer la distance d'édition (ou distance de Levenshtein) entre deux chaînes de caractères, avec un nombre limité d'opérations d'édition (suppression, insertion, substitution). Les pages Wikipédia sont très bien. Voir aussi le livre Programmation Efficace page 52 avec un scan ici.
7. Paire de points les plus proches en temps linéaire
   [programmation dynamique] Il est possible de trouver la paire de points les plus proches en temps moyen $O(n)$, soit mieux que le classique $O(n\log{n})$. L'algorithme consiste à mélanger aléatoirement les $n$ points puis d'appliquer une méthode déterministe. Evoquer dans une parenthèse du cours au chapitre 5, mais aussi dans le livre Programmation Efficace page 164 avec un scan ici.
8. Rendu de monnaie
   [algorithme glouton, programmation dynamique] Problème classique du rendu de pièces de monnaie avec le nombre minimum de pièces. Programmation Efficace page 156 avec un scan ici.
9. Le compte est bon
   [recherche exhaustive] Après un tirage aléatoire, on dispose d'une liste $L$ d'entiers naturels et d'un entier cible $x$. L'objectif est de trouver une expression arithmétique (+,-,/,*) de valeur $x$ et qui utilise au plus une fois chaque entiers de $L$. Une solution basée sur trois "petites" fonctions Python est disponible ici. Voir aussi le livre Programmation Efficace page 204 avec un scan ici.
10. Algorithme de Boyer-Moore
    [algorithme de parcours] Recherche optimisée d'un motif dans un texte au programme NSI. À voir une courte vidéo INRIA et un chapitre de livre (Chp. 10).
11. Algorithme de Knuth-Morris-Pratt
    [algorithme de parcours] Recherche optimisée d'un motif abordé dans le livre Programmation Efficace page 40 avec un scan ici.
12. Tchisla
    [recherche exhaustive, programmation dynamique] Résoudre, au moins partiellement, le problème évoqué dans l'introduction du cours au chapitre 1.
13. Enveloppe convexe
    [géométrie algorithmique] Etant donné un ensemble $P$ de points du plan, construire un polygone convexe, dont les sommets sont des points de $P$, contenant tous les points. Abordé dans le livre Programmation Efficace page 162 avec un scan ici.
14. Diamètre d'un polygone
    [géométrie algorithmique] Calculer en temps $O(n)$ le diamètre d'un polygône pas forcément régulier à $n$ sommets, la recherche exhaustive étant en $O(n^2)$. Dans le chapitre 5 du cours (juste avant la section 5.3), une parenthèse évoque le problème et donne des références.
15. Minimum local
    [diviser pour régner, descente en gradient] Dans une grille $n\times n$ chaque case contient des valeurs réelles de $[a,b[$. On pourra prendre $a=0$ te $b=1$ par exemple. Un minimum local, supposé ne pas être sur le bord qu'on pourra remplir avec la valeur $b$, est la valeur d'une case inférieure ou égale à toutes celles de ses 4 voisines. En découpant la grille récursivement en 4 on peut le trouver en $O(n)$ seulement au lieu d'un parcours naïf (et exhaustif) de la grille en $O(n^2)$. Considérer que le bord ne peut contenir le minimum évite d'avoir à tester la présence des 4 cases voisines. Pour la récurrence, il est important de considérer la "croix séparatrice" qui pourra former le nouveau bord des sous-grilles. NB: Il s'agit de la version 2D de la recherche dichotomique.
16. Files de priorité et tas
    [structure de donnée] Abordé dans le chapitre 4 du cours pour l'implémentation de Dijkstra et/ou A*.
17. Correcteur orthographique
    [arbre] Il s'agit de construire un arbre (basic ou optimisé comme pour les Patricia trie) permettant de stocker tous les mots d'un dictionaire et de pouvoir trouver très rapidement un mot proche, comme les éditeurs de smartphone. Abordé dans le livre Programmation Efficace page 38 avec un scan ici.
18. Laser
    [recherche exhaustive] Une grille rectangulaire est entourée d'un bord comportant deux ouvertures, une entrée et une sortie. Certaines cellules de la grille comportent des mirroirs double-face qui peuvent être placé selon deux orientations: diagonale ou anti-diagonale. Le but est de déterminer les mirroirs de sorte qu'un rayon laser qui entrerait par l'entrée ressorte par la sortie. Le rayon laser traverse les cases vides horizontalement ou verticalement et est dévié de 90 degré à droite ou à gauche quand il arrive sur un mirroir. S'il rencontre le bord de la grille, il est absorbé. Ce problème est abordé dans le livre Programmation Efficace page 191 avec un scan ici.
19. Bin packing
    [programmation dynamique] Problème de remplissage survolée dans le chapitre 3 du cours (3.4.1) et aussi richement détaillée sur Wikipédia.
20. Machine de Turing
    [simulation] Programmer la simulation d'une machine de Turing. Evoquer dans une vidéo annexe.
21. Thème libre
    Un thème rencontré au cours du Bloc 5 ou pas que vous aimeriez développer et faire partager.