#+TITLE : Prise de notes CM 4I500 ALGAV
Antoine Genitrini (antoine.genitrini@sorbonne-universite.fr) 4I500
UE d’ouverture : fascicule de prérequis
Amphi 45B
Evaluation : 0.2 Examen Réparti 1 + 0.2 Rendu Devoir de programmation + 0.6 Examen réparti 2
Devoir de programmation : Suite du cours avec Binh Minh Bui Xuan
Cours d’ouverture inclus ici
Cours d’algorithmique simple : 3I003 Fanny Pascual
On aura le droit aux slides, plus aux notes sur les slides, plus une copie-double manuscrite.
Il faut connaître :
- Notions de complexité, tri de liste (tri rapide, tri fusion)
- Complexité au pire cas
- Complexité en moyenne
On va surtout voir :
- Complexité en coût amorti
Coût au pire cas n’est plus la mesure à suivre (ça l’était en licence) Coût amorti != coût moyen
Coût de complexité en moyenne
Recherche externe Tries, arbres digitaux (texte)
Problème de collision d’objet.
Fonction de hachage. Permet de récupérer une valeur en temps constant.
Froidevaux, Gaudel, Soria, Types de données et algorithmique (Soria ancienne prof ici)
(Disponicle en ligne) Beauquier, Berstel, Chrétienne, Élements d’algorithmique Crochemore, Hancart, Lecroq, Algorithmique du texte
Ce cours présente un certain nombre d’algorithmes et de concepts d’analyse.
Les algorithmes seront écrits en C plutôt qu’en pseudo-langage.
Cet algorithme n’est pas du type “diviser pour régner”, on parle donc d’algorithme naïf.
#include <stdio.h>
#include <stdlib.h>
void inserer(int T[], int x, int e);
void TriInserRec(int T[], int d, int f);
void TriInserIter(int T[], int d, int f);
void printTableau(int T[], int size);
int main()
{
int T[10] = {0};
// On définit la sentinelle : à défaut de l'infini, on met le plus petit nombre écrivable sur 4 octets
T[0] = -2147483648;
// On peuple le tableau
T[1] = 20;
T[2] = 19;
T[3] = 18;
T[4] = 17;
T[5] = 2;
T[6] = 14;
T[7] = 9;
T[8] = 3;
T[9] = 1;
printTableau(T, 10);
/* TriInserRec(T, 1, 10); */
TriInserIter(T, 1, 10);
printTableau(T, 10);
return 0;
}
void inserer(int T[], int x, int e)
{
int k = e;
while (T[k] > x) {
T[k+1] = T[k];
k--;
}
T[k+1] = x;
}
// On a le choix entre la version récursive et itérative. On se permet d'implémenter les deux
// Même si on ne se permettra pas d'utiliser la récursive
void TriInserRec(int T[], int d, int f)
{
if (d < f) {
TriInserRec(T, d, f - 1);
inserer(T, T[f], f - 1);
}
}
void TriInserIter(int T[], int d, int f)
{
for (int i = d + 1; i < f; ++i) {
inserer(T, T[i], i - 1);
}
}
void printTableau(int T[], int size)
{
for (int i = 0; i < size; ++i) {
printf("%d ", T[i]);
}
printf("\n");
}On part du principe qu’une partie de la liste est déjà triée de 0 à e, sans perte de généralité.
On prend l’élément d’indice e+1, et on le met en place en comparant de manière successive à tous les éléments à sa gauche.
Et on recommence jusqu’à arriver à la fin : e = size - 1.
On a bien un algorithme qui se termine : La boucle while de la fonction inserer a un nombre fini d’itérations (l’incrémentation est vers le bas, la barrière est “en bas”).
La condition d’arrêt de la fonction TriInserRec finit toujours par être remplie : la variable f est décrémentée, la condition d’arrêt est de la forme f > qqch.
La boucle for de la fonction TriInserIter s’arrête forcément : la condition d’arrêt est de la forme i < qqch, et i est incrémentée.
A la fin d’une invocation de la fonction inserer, on a e + 1 éléments triés (si on partait du principe qu’on en avait e avant). A la fin de l’algorithme, e + 1 égale la taille du tableau, ce qui une autre manière de dire que le tableau est totalement trié.
La fonction inserer fait au pire e + 1 comparaisons. e étant itéré de 0 à n-1 (n la taille du tableau), on a le nombre total de comparaisons donné par :
$∑i=2ni$
Ce qui donne :
L’algorithme du tri-insertion est donc au pire quadratique.
Cet algorithme est du type “diviser pour régner” : on se propose de découper un problème en problèmes plus petits, de les résoudre puis de les combiner.
On doit donner un certain nombres de concepts pour pouvoir correctement caractériser le comportement asymptotique d’un algorithme.
Le but de ces concepts est de pouvoir ramener la fonction de complexité asymptotique vers une fonction connue et écrivable, genre n, log(n), n^2, etc…
#include <stdio.h>
#include <stdlib.h>
void swap(int *op1, int *op2);
int rearrangement(int T[], int p, int r);
void quicksort(int T[], int p, int r);
void printTableau(int T[], int size);
int main()
{
int T[10] = {0};
// On définit la sentinelle : à défaut de l'infini, on met le plus petit nombre écrivable sur 4 octets
T[0] = -2147483648;
// On peuple le tableau
T[1] = 20;
T[2] = 19;
T[3] = 18;
T[4] = 17;
T[5] = 2;
T[6] = 14;
T[7] = 9;
T[8] = 3;
T[9] = 1;
printTableau(T, 10);
quicksort(T, 0, 9);
printTableau(T, 10);
return 0;
}
void swap(int *op1, int *op2)
{
int temp = *op1;
*op1 = *op2;
*op2 = temp;
}
int rearrangement(int T[], int p, int r)
{
int v = T[r];
int i = p;
for (int j = p; j < r; ++j) {
if (T[j] <= v) {
swap(T + i, T + j);
++i;
}
}
swap(T + i, T + r);
return i;
}
void quicksort(int T[], int p, int r)
{
if (p < r) {
int q = rearrangement(T, p, r);
quicksort(T, p, q - 1);
quicksort(T, q + 1, r);
}
}
void printTableau(int T[], int size)
{
for (int i = 0; i < size; ++i) {
printf("%d ", T[i]);
}
printf("\n");
}On ne parlera pas des problèmes exponentiels.
Exemples de problèmes polynômiaux : tri, recherche, géométrie, texte, arithmétique.
Il faut définir une notion de taille (pas univoque, on peut en définir plusieurs).
Pour donner une complexité (nlog(n)), il faut donner aussi l’opération effectuée (permutation, etc…)
L’opération fondamentale doit être explicitée pour pouvoir permettre les comparaisons.
Plusieurs choses peuvent être comparées :
- Dans le meilleur des cas : min{ T_A(e) ; e ∈ E_n}
- Dans le pire des cas : max{ T_A(e) ; e ∈ E_n}
- En moyenne : 1 / (|E_n|) * ∑e ∈ E_n T_A(e)
On pourrait à la limite donner une distribution de probabilité (et pas seulement un moment) d’un algorithme.
On introduit une nouvelle notion : complexité amortie, définie comme le coût d’une suite d’opération (donc moyenne des coûts).
On définit les trois notions principales :
Comparaison d’ordres de grandeur asymptotique
Complexité amortie : On est au plus proche de ce qui se passe en pratique.
Interclassement de liste : linéaire en la somme des tailles des deux listes.
Ensemble d’éléments, chaque d’élément identifié par une clé, on veut trouver le minimum des clés. (typiquement une valeur de priorité pour un ordonnanceur)
Il faut un ordre total : on doit pouvoir comparer toujours deux éléments : on doit pouvoir dire cet élément-ci est plus petit/égal/plus grand que celui-là.
Opérations :
- On veut pouvoir ajouter un élément
- Supprimer l’élément de plus petite clé
- Construire une file avec n éléments reçus à la volée
- Union de plusieurs files de priorités
- Modification d’une clé
Un tas minimum : [insérer image]
Ensemble de valeurs distinctes deux à deux sous la forme d’un arbre. Contrainte : si on part de la racine vers les feuilles, tous les chemins possibles sont des suites strictement croissantes.
Trier un tas minimum est non-trivial (pas en temps linéaire).
On peut le construire en temps n, donc on le trie au moins en temps nlog(n)
[expliquer algorithme du tas, insertion]
- Tri par tas (au lieu d’une liste) (heapsort)
- Sur les graphes (plus court chemin : Dijkstra ou A*), (plus court chemin entre tous les couples de sommets : Johnson), (arbre couvrant minimal : Prim)
- Interclassement de listes triées
- Compression de Huffmann
Un arbre binomial est un graphe avec une racine et des sous-branches qui sont aussi des arbres binomiaux.
N’existent que si la taille est une puissance de 2.
Structure dite plane : les fils sont ordonnés de gauche à droite.
On suppose que toutes les clés sont distinctes dans les N files à unir.
- Cas 1, union de 2 tournois (TB_l, TB_k) de tailles différentes :
D’après notre supposition, le cardinal de l’ensemble des clés des 2 tournois est de 2^l + 2^k.
On peut simplement donner F = < TB_l, TB_k >, qui est une file binomiale valable.
- Cas 2, union de 2 tournois de même taille.
On peut faire une file binomiale : F = TBk+1 qui pourra contenir toutes les étiquettes des deux tournois en entrée. Cette file binomiale doit respecter la propriété selon laquelle la racine est le plus petit élément du tournoi : on prend en fils de l’autre celui qui a la plus grande racine.
- Union de 2 files binomiales correspond à une addition binaire.
<TB_2, TB_0> U <TB’_2, TB’_1, TB’_0> = <TB”_3, TB”_2>
En fait, c’est super facile de faire une addition en binaire : on peut se contenter de faire du bit par bit.
1 + 0 = 0 + 1 = 1 0 + 0 = 0 1 + 1 = +1 au bit de gauche (au bit de poids plus fort) (et 0 au bit courant)
Ces primitives des pages 22 et 23 sont utilisables en examen : si on les appelle dans du pseudo-code, le correcteur (notre compilateur humain) saura ce que ça signifie.
On a droit à :
- EstVide(T) : Renvoie vrai si le tournoi T est vide
- Degre(T) : Renvoie le degré (un entier) de la racine du tournoi
- Union2Tid(T) : Renvoie l’union de deux tournois (un tournoi) de même taille
- Decapite(T) : Renvoie la file binomiale (suite de tournois) obtenue en supprimant la racine du tournoi T_k
- File(T) : Renvoie la file binomiale réduite au tournoi
- EstVide(F) : Renvoie vrai si la file F est vide
- MinDeb(F) : Renvoie le tournoi de degré minimal de la file F
- Reste(F) : Renvoie la file privee de son tournoi de degre minimal
- AjoutMin(T, F) : Renvoie la file obtenue en ajoutant le tournoi T comme tournoi de degré inférieur de la file F (ne fonctionne que si T est effectivement de degré plus petit que le degré minimal de la file passée en entrée)
Ces primitives peuvent aussi servir à définir des algorithmes de plus haut niveau. Si on a le temps, on pourrait implémenter ces primitives en C.
On ne prouve pas la correction de l’algorithme (aussi vrai, ni plus ni moins, que la somme binaire).
La complexité de l’union de FB_n et FB_m est en O(log_2(n+m))
Critère de complexité : nombre de comparaisons entre clés (la création de pointeurs, copies de données ne comptent pas).
Idée principale : L’union de deux tournois de même taille nécessite 1 comparaison entre clés et ajoute une arête dans le file résultat. (l’union de deux tournois de taille différente est triviale : tournoi+grand, tournoi-grand, et ne nécessite pas de création d’arête ni de comparaion)
Conséquence : Le nombre de comparaisons égale le nombre d’arêtes de la file union moins le nombre d’arêtes des files de départ (en gros, les arêtes créées).
La meilleure manière, c’est de créer une file binomiale contenant seulement l’élément à ajouter, puis je fais l’union.
La complexité est donc donnée par ν(n) + 1 - ν(n + 1).
La complexité est entre 0 et ν(n) : on a au max ν(n) comparaisons.
La meilleure manière, c’est l’ajout de chacun des éléments un à un.
La complexité de la construction d’une file binomiale est donc donnée par la complexité de l’adjonction successive de ses n éléments.
Soit ici :
$∑i=1n-1 [ν(i) + i - ν(1+i)]$
C’est une somme téléscopique. Après simplification, la quantité totale de comparaisons est donnée par n - ν(n)
Coût de la construction est le coût de la commutation de bits. [à clarifier avec Genetrini : Qu’est-ce que la commutation de bits ?]
On sait par construction que le minimum de la file est à la racine d’un des tournois qui la composent.
La recherche prend donc ν(n) - 1 comparaisons (le nombre de tournois - 1). Ce qui est un grand O de log_2(n).
La suppression consiste en supprimer la racine du tournoi qui porte la racine minimale : ça créé une deuxième file binomiale constituée des fils orphelins de la racine. On fait ensuite l’union de cette nouvelle file avec la file de départ privée du tournoi décapité.
Il reste, entre ces deux files, n - 1 éléments.
La recherche est toujours de complexité log_2(n). L’union des deux files sera aussi de complexité log_2(n) dans le pire des cas (cas particulier de la complexité général des unions de files binomiales).
On suppose un accès direct au noeud dont il faut diminuer la clé.
La meilleure manière, c’est de modifier la clé, puis échanger le noeud avec son père de manière successive jusqu’à ce que l’hypothèse de stricte croissance soit à nouveau respectée. Par construction, il y a forcément un moment où ça arrive. Par construction, on suppose aussi que la nouvelle valeur de la clé est distincte de toutes les autres (hypothèse de stricte distinction).
La complexité au pire cas, donné par le nombre maximum de comparaisons, est donc la hauteur de l’arbre, soit log_2(n) (ou log(n), à vérifier avec Genitrini)
On s’intéresse aux structures qui vont permettre de faire de la recherche, ici des structures arborescentes.
On a l’efficacité en temps (nombre d’opérations) (plus important), et l’efficacité en mémoire (moins important).
On a plusieurs parcours fréquemment utilisés.
Le parcours préfixe :
PREF(B) = [visit(•), PREF(G), PREF(D)]
Le parcours préfixe d’un ABR ne donne aucune information sur l’ordre des clés. Chaque noeud n’est visité qu’une seule fois : coût O(n)
Le parcours infixe :
INF(B) = [INF(G), visit(•), INF(D)]
Le parcours infixe donne a priori renvoie une liste triée des clés. Coût aussi O(n).
Le parcours suffixe :
SUF(B) = [SUF(G), SUF(D), visit(•)]
Chaque parcours envoie en ordre différent la liste.
Peuvent se faire en parcourant seulement une seule branche (c’est pour ça qu’on s’en sert). L’insertion se fait à un unique endroit, facile à déterminer. La suppression d’un noeud interne (pas tout en bas) requiert un peu de travail parmi les sous-arbres.
On a un certain nombre de primitives dont on aura le droit de se servir en examen, pour définir des algorithmes en pseudo-langages de plus haut niveau :
- ArbreVide : renvoie l’arbre vide
- ArbreBinaire(e,G,D) : renvoie l’arbre binaire formé de l’élément e et des sous-arbres G à gauche et D à droite
- EstArbreVide(A) : renvoie vrai sssi l’arbre est vide
- Racine(A) : Renvoie le contenu de la racine de A.
- SousArbreGauche(A) : Renvoie une copie du sous-arbre gauche
- SousArbreDroit(A) : Renvoie une copie du sous-arbre droit
- Pere(A) : Renvoie l’arbre dont A est un des sous-arbre immédiat (un des fils de la racine), ou l’arbre vide, si A n’est pas un sous-arbre.
On peut avoir un ABR très déséquilibré (ici celui de droite, appelé peigne) :
Dans le pire des cas, on a besoin de n comparaisons pour trouver l’entier n.
On a des manières de forcer le rééquilibrage par rotation si l’amplitude (On ne gagne pas en moyenne, mais on diminue la probabilité du pire cas)
On va avoir besoin d’algorithmes sophistiqués pour préserver l’équilibre.
On fait l’insertion, on a dépassé le seuil (par exemple, j’avais des noeuds vides à un étage qui n’est pas le dernier) On remonte au père du noeud vide à remplir en partant de l’étiquette qu’on vient de rajouter. On fait une rotation vers le noeud vide (donc vers la gauche ou la droite) en partant de son père.
En général, il est trop coûteux d’obtenir un ABR parfait.
On se permet alors de relâcher les contraintes : Sur la hauteur, donne la famille des arbres AVL. Sur le remplissage des noeuds d’un étage (la largeur), donne la famille des arbres B.
Structures typiques pour la RAM :
- AVL
- Arbre 2-3-4 (Red-black)
Structures typiques pour le disque (plus de données, base de données) :
- Arbre B
- Arbre auto-adaptatif
A = < q, < p, U, V >, W > → RD(A) = < p, U, < q, V, W > >
Avec U le sous-arbre de hauteur +1.
A = < p, U, < q, V, W >, W > → RG(A) = < q, < p, U, V >, W >
A = < q, < p, U, < r, V1, V2 >, >, W > → RGD(A) = < r, < p, U, V1 >, < q, V2, W > >
Toutes ces rotations sont très peu coûteuses.
A = < q, W, < p, < r, V1, V2 >, U > > → RDG(A) = < r, < q, W, V1 >, < p, V2, U > >
On dispose d’un certain ensemble de primitives sur les AVL :
- Hauteur(A) : Renvoie la hauteur de l’arbre passé en argument.
- Les quatre fonctions de rotation mentionnées plus haut.
- Equilibrage(A) : Suppose que A est un arbre de recherche, que ses sous-arbres sont des AVL, dont les hauteurs diffèrent de 2 au plus. Renvoie l’arbre obtenu en rééquilibrant l’arbre initiale (Détermine laquelle des rotations à appliquer, et l’applique)
- AVL_Ajout(x, A) : Renvoie l’AVL résultant de l’ajout de x à A.
Un cas particulier intéressant, particulièrement souvent utilisé :
On dispose d’un ensemble de primitives utiles, plus pratiques pour les algorithmes plus complexes :
- EstVide(A)
- Degre(A) : l’arité à la racine de A (ou l’arité de A si on considère A le noeud racine de l’arbre plutôt que l’arbre lui-même)
- Contenu(A) : la liste (ordonnée croissante) des éléments de la racine de A (ou la liste de A si on considère A le noeud racine de l’arbre plutôt que l’arbre lui-même)
- EstDans(x, L) : Est-ce que x est dans la liste L
- Elem_i(A) : Renvoie le ième élément de la racine de A (+∞ si i est trop grand : genre on a demandé Elem_3 d’un 2-noeud qui ne contient qu’un élément)
- SsA_i(A) : Renvoie le ième sous-arbre de la racine de A (l’arbre vide si i est trop grand : genre on a demandé SsA_3 d’un 2-noeud qui n’a que 2 sous-arbres)
A partir de ces primitives, on peut donner un algorithme de recherche en pseudo-langage.
On compare l’élément recherché aux éléments du noeud racine. Soit on le trouve, soit on sait au bout de 1-3 comparaisons dans quel sous-noeud on le doit rechercher. Et ainsi de suite.
On comprend aisément que la recherche est meilleure si on a des 4 noeuds (encore qu’on est quand même en O(log(n)) dans tous les cas) :
L’ajout est guidé par la recherche : on met l’élément où on l’aurait trouvé par la recherche. On s’arrête quand ?
Déjà, on ne s’arrête que si le noeud est plein ou si on est arrivé en bas.
Si celui-ci est plein, alors on doit éclater le noeud (version éclatement systématique en descente) :
- On garde un pointeur où on aurait dû mettre l’élément
- L’élément du mileu devient la racine, le plus petit devient le fils gauche, le plus grand devient le fils droit (même niveau donc).
- On met l’élément à sa place en recommençant à chercher au pointeur (qu’on a pris la peine de garder avant), dans l’endroit de plus bas niveau.
Si on a un éclatement sur une feuille du bas, on doit faire remonter la valeur centrale de l’élément à éclater dans un noeud plus haut (dont on sait qu’il n’est pas plein, puisqu’on vient de le traverser).
On se propose de construire par ajout successif un arbre 2-3-4 avec les éléments, en utilisant l’algorithme d’éclatement systématique en descente :
(4, 35, 10, 13, 3, 30, 15, 12, 7, 40, 20, 11, 6)
| 4 |
| 4, 35 |
| 4, 10, 35 |
Eclatement ! On garde le pointeur avant 35
| 10 | ||
| 4 | 35 |
On reprend la recherche à partir du pointeur
| 10 | ||
| 4 | 13,35 | |
| 10 | ||
| 3,4 | 13,35 | |
| 10 | ||
| 3,4 | 13,30,35 |
Eclatement ! On garde le pointeur avant 30
| 10,30 | ||
| 3,4 | 13 | 35 |
On reprend la recherche à partir du pointeur
| 10,30 | ||
| 3,4 | 13,15 | 35 |
| 10,30 | ||
| 3,4 | 12,13,15 | 35 |
| 10,30 | ||
| 3,4,7 | 12,13,15 | 35 |
| 10,30 | ||
| 3,4,7 | 12,13,15 | 35,40 |
Eclatement ! On garde le pointeur après 15
| 10,13,30 | |||
| 3,4,7 | 12 | 15 | 35,40 |
On reprend la recherche à partir du pointeur
| 10,13,30 | |||
| 3,4,7 | 12 | 15,20 | 35,40 |
Eclatement ! On garde le pointeur avant 13
| 13 | ||||||
| 10 | 30 | |||||
| 3,4,7 | 12 | 15,20 | 35,40 |
On reprend la recherche à partir du pointeur
| 13 | ||||||
| 10 | 30 | |||||
| 3,4,7 | 11,12 | 15,20 | 35,40 |
Eclatement ! On garde le pointeur avant 7
| 13 | ||||||
| 4,10 | 30 | |||||
| 3 | 7 | 11,12 | 15,20 | 35,40 |
On reprend la recherche à partir du pointeur
| 13 | ||||||
| 4,10 | 30 | |||||
| 3 | 6,7 | 11,12 | 15,20 | 35,40 |
On a deux manières de déterminer quand faire un éclatement :
- Eclatement systématique en descente (présenté ici : on éclate dès qu’on rencontre un noeud plein)
- Eclatement en remontée (on éclate que si on rencontre un noeud plein tout au bout)
En descente :
- Parcours uniquement de haut en bas (seulement besoin de pointeurs simples) (+)
- Transformation très locale (on éclate un noeud, et on remonte pas plus haut que le père : nécessite un unique pointeur supplémentaire) (+)
- Taux d’occupation plus faible (moins bon pour la recherche) (-)
- Hauteur plus grande (-)
En remontée :
- Parcours dans les deux sens (double pointeurs, empreinte mémoire) (-)
- Transformation en chaîne de proba non-nulle (même de proba 1 en n le nombre d’ajouts) (-)
- Taux d’occupation plus fort (+)
- Hauteur plus petite (+)
Structure ultra-majoritaire des bases de données. Existe depuis 30 ans.
Implémenté en C++ dans la bibliothèque stxxl. Oracle et Google ont aussi des implémentations à eux.
L’idée est de limiter autant qu’il est possible les défauts de page, de manière à éviter les accès disques.
Pour cette raison, on veut blinder les noeuds de données, de manière à ce qu’un noeud occupe à peu près une page mémoire. Et savoir exactement quelle page mémoire aller chercher sur le disque si on a suffisemment peu de chance pour en avoir besoin.
La hauteur diminue énormément en m. La hauteur doit être aussi petite que possible, car passer d’un noeud à un de ses fils consiste précisément en faire cette entrée/sortie disque tant redoutée.
On choisit m tel que le contenu de la racine doit pouvoir être stocké en RAM. Un noeud doit tenir dans une page. Les autres noeuds seront stockés dans le disque.
1 éclatement implique écrire deux pages en disque (très cher)
Intuition : Quand je fais remonter qqch de très profond, l’arbre résultant est plutôt équilibré.
Le coût au pire cas est en O(n), cher. Mais en fait, un opération coûteuse (ramener un truc de tout au fond) accélère grandement les opérations futures, simplement parce qu’on rééquilibre énormément l’arbre.
L’analyse par potentiel permet de monter que pour toute suite de m opérations, le coût est en O(m log(n)).
Structures dont les clés sont des chaînes de caractère. Adaptation des structures précédentes.
Les clés sont définissables caractère par caractère : on peut la voir bit par bit.
L’idée est de partager les préfixes de deux mots par exemple.
Opérations souhaitées :
- On veut effectuer la recherche, insérer, supprimer des clés.
- On veut pouvoir faire la liste en ordre alphanumérique.
- Recherche partiellement spécifiées (regex)
- Recherche du plus long préfixe dans S d’un mot donné.
On a un ensemble de primitives utiles, qui vont permettre de définir des algorithmes de plus haut niveau :
- prem(cle) : renvoie le premier caractère de la clé
- reste(cle) : Renvoie la clé, sans son premier caractère
- car(cle, i) : Renvoie le ième caractère de la clé
- lgueur(cle) : Renvoie le nombre de caractères de la clé
La structure de l’arbre va dépendre de l’ordre d’insertion.
On doit décaler l’espace des caractères à écrire au “centre” de l’espace des caractères pouvant être écrits (en terme de nombre de bits) ou alors s’assurer ce que les éléments encodés sont uniformément répartis sur l’espace d’écriture.
Idéalement, on doit commencer par insérer du milieu d’alphabet (le truc le plus proche de 0b10000000 soit la valeur à égale distance de 0b00000000 et de 0b11111111)
Les clés sont en ordre croissant d’encodage. La hauteur maximale est donnée par le nombre de bits d’encodage.
Notion de Patricia tries : on fusionne les noeuds qui n’ont qu’un fils avec le fils (on doit noter qqpart que l’arête qui va dans ce nouveau noeud est en fait plusieurs arêtes en une, donc plusieurs bits déterminés d’un coup)
Recherche, ajout et suppression se fait par parcours de branche.
Par exemple, un 26-trie peut avoir tous les mots de la langue française en une structure unique (pourvu qu’on n’écrive pas les accents).
Le problème de cette structure vient de son empreinte mémoire. On a besoin de R pointeurs par noeud, la plupart d’entre eux vides. En plus, les langages naturels ne débouchent pas sur des 26-trie équilibrés : on a beaucoup plus de mots qui commencent par a que z.
Cours de Binh-Minh Bui-Xuan
Géométrie algorithmique DirectX, OpenGL Calculs dans les cartes graphiques
Soient deux cercles c1 et c2 de rayon respectif c1.radius et c2.radius dont les centres sont donnés par (c1.x, c1.y) et (c2.x, c2.y). Déterminer une condition nécessaire et suffisante pour que les deux cercles s’intersectent.
Mathématiquement, c’est simple :
Il faut et il suffit que la distance entre les centres soit inférieure à la somme des rayons des deux cercles.
Si on l’exprime de manière formelle, on a :
sqrt((c1.x - c2.x)^2 + (c1.y - c2.y)^2) \leq c1.radius + c2.radius
Le but de l’exercice n’est bien évidemment pas de donner ce résultat évident, mais de voir comment l’implémenter.
Simplement tester la condition (sqrt((c1.x - c2.x)^2 + (c1.y - c2.y)^2) \leq c1.radius + c2.radius) n’est pas la bonne chose à faire, car la racine carrée coûte très cher à calculer.
Cette condition est équivalente à la condition suivante (les distances sont toujours positives) : (c1.x - c2.x)^2 + (c1.y - c2.y)^2) \leq (c1.radius + c2.radius)^2
Et apparemment, on aurait envie de se débarasser du carré (une sombre histoire de bibliothèque Java externe, admettons) :
La bonne manière est de stocker dans une variable la valeur c1.x - c2.x, multiplier cette variable par elle-même, et faire de même pour les autres.
On veut donner le plus petit cercle qui couvre tous les points d’une liste (d(point, centre) \leq rayon)
On dispose de deux résultats mathématiques :
Par contre, on ne peut pas dire que parce qu’un cercle couvre les deux points dont la distance est la plus grande de tous les points du nuage deux à deux, alors il couvre tous les points du nuage.
Le contre-exemple est donné par le triangle équilatéral : si le nuage est réduit à trois points qui constituent les sommets d’un triangle équilatéral, alors un cercle de diamètre d’un des côtés du triangle ne couvrira pas le troisième point.
C’est à ce moment-là qu’on fait intervenir le deuxième lemme.
Le troisième lemme intervient pour les cas où on a plus de trois distances entre deux points dans le nuage.
En gros, on peut s’en servir pour démontrer que quelque soit N le nombre de distances égales entre elles et maximales dans le nuage, alors il existe un unique cercle qui passe par les m points qui définissent ces distances maximales. [Résultat de géométrie non trivial à vérifier et démontrer.]
A-t-on un algorithme qui prouve ce théorème ?
Solution personnelle (je ne me rappelle plus de ce que le cours disait) : On a 2 parmi n couple de points dans le nuage de n points, soit (n^2 - n) / 2.
On constitue ces couples et on calcule leur distance à la volée : O(7n^2) On trie ces distances de la plus à la moins grande (on dit quicksort) : log(n^2) On ne garde que les N strictement plus grandes que toutes les autres : O(cn)
Selon la valeur de N, on construit le cercle, en partant du principe qu’on a toujours une manière fixe de le faire (et en fait c’est le cas, mais j’ai la flemme de le redémontrer).
La complexité en calcul de l’ALU d’une distance est de 3 calculs (2 carrés et une addition), soient 7 additions.
Donc la complexité au pire cas : 7n^2 + log(n^2) + O(cn), soit O(n^2)
Cette solution ne fonctionne pas : le théorème selon lequel la distance maximale entre deux points est toujours le diamètre du
La bonne solution naïve :
- On prend les (n^2 - n)/2 couples de points, on fait le cercle de diamètre. (n^2)
- On vérifie si tous les points sont dans ce cercle (*n). Si j’ai un cercle qui respecte cette propriété, je le garde. Je mets à jour si j’en trouve un plus petit. Si j’ai un cercle à la fin de cette itération, c’est le cercle minimum, on peut d’arrêter.
Si je suis dans ce cas-là, alors l’algorithme est en O(n^3)
Sinon, je dois recommencer :
- On prend n parmi 3 triplets de points (un truc en n^3), pour chaque triplet, on calcule l’unique cercle qui passe par ces trois points.
- Je vérifie que tous les points sont dans ce cercle (*n). Si j’ai un cercle qui respecte cette propriété, je le garde. Je mets à jour si j’en trouve un plus petit. Je sais que j’ai un cercle à la fin de cette itération, si je n’en ai pas trouvé avant (résultat mathématique qu’on ne redémontrera pas ici).
Dans ce deuxième cas, l’algorithme est en O(n^4)
Vu que je fais les deux cas de manière séquentielle, la complexité au pire case est donnée par O(n^3 + n^4), soit O(n^4).
La vraie bonne solution, en O(n) au pire cas, c’est l’algorithme incrémental :
- On trace le cercle de diamètre des deux premiers éléments de la liste : négligeable
- On vérifie si les points suivants sont dans le cercle : 1 comparaison entre une distance carrée et un rayon carré (13 additions) : si oui, on passe au suivant, sinon on remplace le cercle par le cercle :
de rayon = (d(C,S) + ancien rayon) / 2 (un calcul de distance déjà fait et un shift de 1 bit : 1 ALU) et de centre en le point à rayon distance de S sur la droite CS (applique le vecteur, tya compris : 2 ALU, 1 pour les abscisses, 1 pour les ordonnées)
Et tu refais ça jusqu’à arriver jusqu’à la fin de la liste. A la fin de la liste, le cercle que tu as, c’est le cercle minimum qui couvre tous les points.
On a bien une complexité O(n) au pire cas : à chaque comparaison/mise à jour, on a un certain nombre (on va dire C au maximum) d’opérations qui ne dépendent pas de n, ce qui fait une complexité de Cn au pire cas, soit O(n).
La lazy evaluation : Quand on veut tester une condition complexe (c’est-à-dire la résultante d’une opération logique sur des conditions simples), on prend bien garde à mettre la condition la moins coûteuse en premier.
Le compilateur s’arrangera pour produire du code assembleur qui évitera la deuxième condition, si ça vaut le coût bien sûr.
La semaine dernière, on avait vu les cercles pour les tests de collision : en assimilant les objets à un cercle, on peut très facilement décider sans faux négatif si deux objets se touchent.
Mais sur les objets un peu complexes, les cercles crééent plein de faux positifs.
Pour cette raison, on va essayer cette semaine un meilleur conteneur, l’enveloppe convexe.
Tous les côtés peuvent être définis par les couples successifs des contours positifs de l’objet.
Le contour positif est une liste des coins ordonnée.
Tous les couples successifs définissent des côtés.
Si on a n points dans la liste, on a n côtés aussi.
Pour chacun des n côtés défini par le vecteur, on calcule le signe.
On part du principe qu’on a une primitive bien utile qui permet de dire si a d’une part, et s d’autre part, sont dans le même demi-plan donné par la droite bc (en pratique, cette primitive se sert des produits vectoriels et du signe de la coordonnée z du résultat) :
boolean memeCote(Point a, Point b, Point c, Point s);On se propose de simplement itérer sur les points de p1 et p2 : Prendre trois points de p1 (avec un itérateur bien pratique) (en faisant bien attention à ne pas passer past the end), et vérifier pour chaque point de p2 s’ils sont du même côté. S’ils ne le sont pas, on peut break, le côté considéré n’est pas un côté séparant.
Dès qu’on trouve un côté séparant, on peut s’arrêter, on a gagné.
On doit tester les côtés séparants sur les deux objets : un des deux peut très bien ne pas avoir de côté séparant, mais l’autre oui.
Petite implantation en java :
public boolean collision(ArrayList <Point> p1, ArrayList <Point> p2) {
for (int i = 0; i < p1.size(); i++) {
boolean coteTrouve = true;
Point a = p1.get(i);
Point b = p1.get((i+1) % p1.size());
Point c = p1.get((i+2) % p1.size());
for (Point s:p2) {
if (memeCote(a,b,c,s)) {
coteTrouve = false;
break;
}
if (coteTrouve == true) return false;
}
// Refaire la même chose en remplaçant p1 et p2
}
}Complexité au pire cas : p1.size() * p2.size(). En vrai, c’est beaucoup plus rapide : on fait plein de break et de return prematurés : à moins d’avoir vraiment très peu de chance, où c’est systématiquement le dernier point qu’on teste qui “casse” le côté.
Test de ce que qqch est à droite ou à gauche d’une droite : On utilise le produit vectoriel : si la coordonnée z est positive, on est d’un côté, négative on est de l’autre. C’est comme ça que la fonction même côté est implémentée.
On a un objet géométrique complexe défini par la liste de ses points.
On veut une sous-liste de cette liste qui représente le contour positif (liste dans le sens trigo) de l’enveloppe convexe.
La solution naïve, en java :
ArrayList <Point> getEnveloppe(ArrayList <Point> points) {
ArrayList<Point> enveloppe = new ArrayList<Point> ();
for (Point p : points) {
for (Point q : points) {
boolean estCote = true;
int i = 0;
while (crossProduct(p,q,points.get(i)) == 0) i++;
double signeRef = crossProduct(p,q,points.get(i));
for (Point r : points) {
if (crossProduct(p,q,r) * signeRef < 0) {
estCote = false;
break;
}
}
if (estCote) {
enveloppe.add(p);
enveloppe.add(q);
}
}
}
return enveloppe;
}Complexité au pire cas est en n^3 (on se rend compte au dernier point que le segment qu’on regarde n’était en fait pas un côté) En vrai, on est sur du n^2 : on voit très vite si on n’est pas un côté, et on break.
On peut éliminer des points : Si n>3 points ont la même équation de droite, alors au plus deux de ces points appartiennent à l’enveloppe convexe (les deux points avec respectivement la plus petite et la plus grande coordonnée selon la droite.)
Implantation :
On créé deux séries de N buckets (N étant la largeur en pixels de l’écran).
On boucle sur les points : si le point est plus haut que le point de son bucket du haut (en terme d’ordonnées), on remplace ce dernier. Si le point est plus bas que son bucket du bas (en terme d’ordonnées), on remplace ce dernier.
On n’a plus qu’à itérer sur les 2N points, on sait que les côtés se forment nécessairement avec un sous-ensemble de ces 2N points.
Complexité en n
On sait que les 4 points extrêmaux (Nord, Sud, Est, Ouest) sont dans l’enveloppe convexe. Et on sait en plus que tous les points dans le quadrilatère ne peuvent pas être dans l’enveloppe convexe.
Puis on applique l’algorithme du quickhull :
Une fois qu’on a le quadrilatère, on checke s’il reste encore des points de l’autre côté. S’il en reste, on prend le plus loin (produit scalaire), et on fait deux côtés là où il y en avait un seul : on enlève les points du triangle qu’on vient de créer, et on revérifie sur les deux côtés.
Complexité au pire cas n^2. Θ(n^2)
Si on a deux points qui forment un côté, on calcule les angles, et on prend le point qui a l’angle minimal.
Complexité au pire cas en n * h, avec h le nombre de côtés.
Cet algorithme est en Θ(nh)
On coupe la liste en morceaux. On calcule l’enveloppe convexe des morceaux avec un algo en n * log(n), comme Graham : cette partie prend O(n log(m)), avec m le nombre maximum de points dans un sous-groupe.
Ensuite, on applique Jarvis en ne prenant comme candidats que les éléments des enveloppes convexes des sous ensembles : cette partie prend O(n * log(h)) si h est proche de m.
Donc en tout O(n * log(h)), avec h le nombre de côtés.
Support des cours :
Support des cours BMBX :