From 42e9569176360b5e1881d317c74ce8522a2af6d1 Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Tue, 20 Jan 2026 13:55:21 +0100 Subject: Derniers cours du S3 --- .../3- Hash table.md" | 107 +++++++++++++++++++++ .../structures des donn\303\251es/3- Hash.md" | 107 --------------------- .../5- File de priorit\303\251.md" | 16 ++- .../6- Arbre binaire de recherche.md" | 20 ++-- .../structures des donn\303\251es/7- Graphe.md" | 4 +- .../8- Parcours de graphe.md" | 13 +++ .../9- Arbre rouge-noir.md" | 38 +++++++- .../contenu feuille exam.txt" | 41 ++++++++ .../structures des donn\303\251es/td/td10/exo1.md" | 10 ++ .../structures des donn\303\251es/td/td8/exo2.c" | 34 +++++++ 10 files changed, 265 insertions(+), 125 deletions(-) create mode 100644 "semestre 3/structures des donn\303\251es/3- Hash table.md" delete mode 100644 "semestre 3/structures des donn\303\251es/3- Hash.md" create mode 100644 "semestre 3/structures des donn\303\251es/contenu feuille exam.txt" create mode 100644 "semestre 3/structures des donn\303\251es/td/td10/exo1.md" create mode 100644 "semestre 3/structures des donn\303\251es/td/td8/exo2.c" (limited to 'semestre 3/structures des données') diff --git "a/semestre 3/structures des donn\303\251es/3- Hash table.md" "b/semestre 3/structures des donn\303\251es/3- Hash table.md" new file mode 100644 index 0000000..c659419 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/3- Hash table.md" @@ -0,0 +1,107 @@ +--- +tags: + - sorbonne + - informatique + - structure-des-données +semestre: 3 +--- +## Tableaux associatifs +Tableau associatif (aussi appelé dictionnaire) associe une valeur à une clé +|> chaque clé est associée à *au plus* une valeur + +Tableaux associatifs peuvent être implémentés à l'aide de deux structures de données : +- les tables de hachage +- arbres binaires de recherche équilibré (cf le futur cours 6) + +Ces deux implémentations possèdent chacune leurs avantages + +Une table de hachage est une structure de données permettant d'implémenter un tableau associatif par un tableau +|> l'univers $U$ n'est pas forcément que des entiers +|> une fonction de hachage $h:U\to \{0,\ldots,m-1\}$ permet de transformer les $m$ clés en indice du tableau +### Fonction de hachage +Une fonction de hachage peut engendrer des collisions ! +|> besoin de bien choisir $h$ +|> besoin de choisir un mécanisme de gestion de collisions adapté +|> en pratique, il est impossible d'éviter les collisions car, souvent, $|U| \gg m$ + +Une fonction de hachage est une bonne fonction quand : +- elle se calcule rapidement +- les collisions sont rares + +Une fonction de hachage $h$ se fait souvent en deux étapes : +1. une fonction $f$ de $U$ vers $\mathbb{N}$ +2. une fonction $g$ de $\mathbb{N}$ vers $\{0,\ldots,m-1\}$ +3. $h$ est ainsi $g\circ f$ + +Méthodes classiques : +- hachage par division -> $g(x)=x \% m$ (où $m$ est premier pas trop proche d'une puissance de 2) +- hachage par multiplication -> $g(x)=\lfloor m(xA-\lfloor xA\rfloor)\rfloor$ où $A\in]0,1[$ — si $A$ est irrationnel, les clés se répartissent presque uniformément, on dit que le choix de $m$ est non critique ; souvent, on choisit le nombre d'or $A=\varphi-1=\frac{\sqrt 5 - 1}{2}$ +### Collision par liste chaînée +Comment gérer les collisions ? +-> on peut faire une liste chaînée +|> au lieu de contenir une unique valeur, on contient une liste chaînée avec toutes les collisions +|> on a besoin de stocker la clé pour pouvoir trouver la bonne valeur +#### Complexité +Soit $m$ la taille de la table de hachage et $n$ est le nombre d'éléments qu'elle contient. + +On suppose que $h(k)$ est en $O(1)$. +On suppose que $h$ est uniforme simple -> chaque case de la table a la même chance de recevoir un élément tiré au hasard +On suppose que la table est bien dimensionnée -> $\exists c>0,\quad m=c\times n$ + +> [!NOTE] Pourquoi ces hypothèses ? +> Si on ne suppose pas que $h(k)$ est uniforme, on se retrouve avec le même comportement qu'une liste chaînée +> +> Si $h(k)$ n'est pas en $O(1)$, on augmente énormément la complexité. + +À cause de ces hypothèses, on a des complexités en moyenne, que l'on note $0_{moy}$. + +Facteur de charge est $\alpha=\frac nm$ où $n$ est le nombre de pairs et $m$ est la taille du tableau sous-jacent +|> est un indicateur de ses performances +|> quand devient supérieur à $0.5$, les collisions deviennent fréquentes + +La recherche d'un élément possédant une clé $k$ est en $O_{moy}(1)$ +|> $O_{moy}(1+\alpha)=O_{moy}(\alpha)$ car $\alpha$ est la taille moyenne de la liste gérant les collisions et que $O_{moy}(1)$ provient de la complexité de $h$ +|> Or, comme $\alpha=\frac{n}{m}$, on a que $O_{moy}\left(\frac{n}{m}\right)=O_{moy}\left(\frac{n}{cn}\right)=O_{moy}(1)$ + +L'insertion d'un élément (clé $k$, valeur $v$) est en $O_{moy}(1)$ +|> on vérifie que l'élément existe dans la liste, ce qui est en $O_{moy}(1)$ +|> puis on l'ajoute en tête de liste, ce qui est en $O(1)$ + +La suppression est aussi en $O(1)$ si la liste est doublement chaînée +|> si elle est simplement chaînée, on est en $O_{moy}(1)$ +#### Problème +On a besoin de stocker le pointeur +|> augmente la taille des données +|> mauvaise localité de cache (mémoire pas forcément contiguë) +### Collision par adressage ouvert +Cherche à résoudre les problèmes des listes chaînées + +Maintenant, une case ne contient qu'un élément +|> quand une case contient déjà un élément, on en cherche une autre à l'aide d'une méthode de *probing* + +*Probing* détermine une nouvelle case à partir de l'ancienne +|> linéaire = $h(k,i) = (h(k)+i)\%m$ +|> quadratic = $h(k,i) = (h(k)+ci+di^2)\%m$ avec $c\geqslant 0$ et $d>0$ (souvent $c=d=\frac 12$) +|> double hachage = $h(k,i)=(h_1(k)+ih_2(k))\%m$ où $h_1$ et $h_2$ sont deux fonctions de hachage +-> $i$ est toujours le nombre de raté (i.e. $i=0$ pour le premier, $i=1$ pour le deuxième...) + +Quand on supprime un élément, on casse la chaîne -> besoin de réorganiser le tout +La recherche d'un élément ne dépend plus que de $\alpha$ +|> besoin que $\alpha$ soit inférieur à 1 (souvent, on a $\alpha \leqslant 0.8$) + +La recherche fructueuse et infructueuse sont en $O_{moy}(1)$, mais recherche fructueuse est plus rapide +|> suppression est aussi en $O_{moy}(1)$ + +Quand la supposition sur $\alpha$ est fausse (on se rapproche de 1), alors le $O_{moy}(1)$ n'est plus assuré -> besoin d'agrandir la table +## Filtre de Bloom +Permet de tester efficacement si un élément est dans un ensemble +|> permet d'éviter beaucoup de recherches non fructueuses + +Structure probabiliste permet de savoir +|> avec certitude si un élément n'est pas présent +|> avec une certaine probabilité si un élément est présent +-> peut donner des faux positifs, mais ne donne pas de faux négatif +![[Pasted image 20251014102252.png]] +On hash à l'aide de plusieurs fonctions les valeurs et on indique que la valeur est présente dans le tableau +|> pour vérifier si une valeur est dans le tableau, on la hash on vérifie si les valeurs indiquent toutes qu'elle est présente ! +-> peut se tromper sur la présence à cause des collisions, mais jamais sur l'absence \ No newline at end of file diff --git "a/semestre 3/structures des donn\303\251es/3- Hash.md" "b/semestre 3/structures des donn\303\251es/3- Hash.md" deleted file mode 100644 index d200204..0000000 --- "a/semestre 3/structures des donn\303\251es/3- Hash.md" +++ /dev/null @@ -1,107 +0,0 @@ ---- -tags: - - sorbonne - - informatique - - structure-des-données -semestre: 3 ---- -## Tableaux associatifs -Tableau associatif (aussi appelé dictionnaire) associe une valeur à une clé -|> chaque clé est associée à *au plus* une valeur - -Tableaux associatifs peuvent être implémentés à l'aide de deux structures de données : -- les tables de hachage -- arbres binaires de recherche équilibré (cf le futur cours 6) - -Ces deux implémentations possèdent chacune leurs avantages - -Une table de hachage est une structure de données permettant d'implémenter un tableau associatif par un tableau -|> l'univers $U$ n'est pas forcément que des entiers -|> une fonction de hachage $h:U\to \{0,\ldots,m-1\}$ permet de transformer les $m$ clés en indice du tableau -### Fonction de hachage -Une fonction de hachage peut engendrer des collisions ! -|> besoin de bien choisir $h$ -|> besoin de choisir un mécanisme de gestion de collisions adapté -|> en pratique, il est impossible d'éviter les collisions car, souvent, $|U| \gg m$ - -Une fonction de hachage est une bonne fonction quand : -- elle se calcule rapidement -- les collisions sont rares - -Une fonction de hachage $h$ se fait souvent en deux étapes : -1. une fonction $f$ de $U$ vers $\mathbb{N}$ -2. une fonction $g$ de $\mathbb{N}$ vers $\{0,\ldots,m-1\}$ -3. $h$ est ainsi $g\circ f$ - -Méthodes classiques : -- hachage par division -> $g(x)=x \% m$ (où $m$ est premier pas trop proche d'une puissance de 2) -- hachage par multiplication -> $g(x)=\lfloor m(xA-\lfloor xA\rfloor)\rfloor$ où $A\in]0,1[$ — si $A$ est irrationnel, les clés se répartissent presque uniformément, on dit que le choix de $m$ est non critique ; souvent, on choisit le nombre d'or $A=\varphi-1=\frac{\sqrt 5 - 1}{2}$ -### Collision par liste chaînée -Comment gérer les collisions ? --> on peut faire une liste chaînée -|> au lieu de contenir une unique valeur, on contient une liste chaînée avec toutes les collisions -|> on a besoin de stocker la clé pour pouvoir trouver la bonne valeur -#### Complexité -Soit $m$ la taille de la table de hachage et $n$ est le nombre d'éléments qu'elle contient. - -On suppose que $h(k)$ est en $O(1)$. -On suppose que $h$ est uniforme simple -> chaque case de la table a la même chance de recevoir un élément tiré au hasard -On suppose que la table est bien dimensionnée -> $\exists c>0,\quad m=c\times n$ - -> [!NOTE] Pourquoi ces hypothèses ? -> Si on ne suppose pas que $h(k)$ est uniforme, on se retrouve avec le même comportement qu'une liste chaînée -> -> Si $h(k)$ n'est pas en $O(1)$, on augmente énormément la complexité. - -À cause de ces hypothèses, on a des complexités en moyenne, que l'on note $0_{moy}$. - -Facteur de charge est $\alpha=\frac nm$ où $n$ est le nombre de pairs et $m$ est la taille du tableau sous-jacent -|> est un indicateur de ses performances -|> quand devient supérieur à $0.5$, les collisions deviennent fréquentes - -La recherche d'un élément possédant une clé $k$ est en $O_{moy}(1)$ -|> $O_{moy}(1+\alpha)=O_{moy}(\alpha)$ car $\alpha$ est la taille moyenne de la liste gérant les collisions et que $O_{moy}(1)$ provient de la complexité de $h$ -|> Or, comme $\alpha=\frac{n}{m}$, on a que $O_{moy}\left(\frac{n}{m}\right)=O_{moy}\left(\frac{n}{cn}\right)=O_{moy}(1)$ - -L'insertion d'un élément (clé $k$, valeur $v$) est en $O_{moy}(1)$ -|> on vérifie que l'élément existe dans la liste, ce qui est en $O_{moy}(1)$ -|> puis on l'ajoute en tête de liste, ce qui est en $O(1)$ - -La suppression est aussi en $O(1)$ si la liste est doublement chaînée -|> si elle est simplement chaînée, on est en $O_{moy}(1)$ -#### Problème -On a besoin de stocker le pointeur -|> augmente la taille des données -|> mauvaise localité de cache (mémoire pas forcément contiguë) -### Collision par adressage ouvert -Cherche à résoudre les problèmes des listes chaînées - -Maintenant, une case une ne contient qu'un élément -|> quand une case contient déjà un élément, on en cherche une autre à l'aide d'une méthode de *probing* - -*Probing* détermine une nouvelle case à partir de l'ancienne -|> linéaire = $h(k,i) = (h(k)+i)\%m$ -|> quadratic = $h(k,i) = (h(k)+ci+di^2)\%m$ avec $c\geqslant 0$ et $d>0$ (souvent $c=d=\frac 12$) -|> double hachage = $h(k,i)=(h_1(k)+ih_2(k))\%m$ où $h_1$ et $h_2$ sont deux fonctions de hachage --> $i$ est toujours le nombre de raté (i.e. $i=0$ pour le premier, $i=1$ pour le deuxième...) - -Quand on supprime un élément, on casse la chaîne -> besoin de réorganiser le tout -La recherche d'un élément ne dépend plus que de $\alpha$ -|> besoin que $\alpha$ soit inférieur à 1 (souvent, on a $\alpha \leqslant 0.8$) - -La recherche fructueuse et infructueuse sont en $O_{moy}(1)$, mais recherche fructueuse est plus rapide -|> suppression est aussi en $O_{moy}(1)$ - -Quand la supposition sur $\alpha$ est fausse (on se rapproche de 1), alors le $O_{moy}(1)$ n'est plus assuré -> besoin d'agrandir la table -## Filtre de Bloom -Permet de tester efficacement si un élément est dans un ensemble -|> permet d'éviter beaucoup de recherches non fructueuses - -Structure probabiliste permet de savoir -|> avec certitude si un élément n'est pas présent -|> avec une certaine probabilité si un élément est présent --> peut donner des faux positifs, mais ne donne pas de faux négatif -![[Pasted image 20251014102252.png]] -On hash à l'aide de plusieurs fonctions les valeurs et on indique que la valeur est présente dans le tableau -|> pour vérifier si une valeur est dans le tableau, on la hash on vérifie si les valeurs indiquent toutes qu'elle est présente ! --> peut se tromper sur la présence à cause des collisions, mais jamais sur l'absence \ No newline at end of file diff --git "a/semestre 3/structures des donn\303\251es/5- File de priorit\303\251.md" "b/semestre 3/structures des donn\303\251es/5- File de priorit\303\251.md" index b1987a5..acad05f 100644 --- "a/semestre 3/structures des donn\303\251es/5- File de priorit\303\251.md" +++ "b/semestre 3/structures des donn\303\251es/5- File de priorit\303\251.md" @@ -5,8 +5,11 @@ tags: - structure-des-données semestre: 3 --- -**Rattraper la définition** - +Les files de priorité servent à trouver le minimum/maximum d'un ensemble +|> clé/valeur avec la clé donnant le niveau de priorité +|> ajout doit être simple +|> recherche/extraction du min (resp. max) doit aussi être simple +## Implémentation naïve Implémentation naïve en liste chaînée, son extraction est en $O(n)$ pour récupérer la valeur minimum |> utilisation d'une liste chaînée triée permet d'éviter ça, mais on se retrouve à être en $O(n)$ pour l'insertion -> on fait sûrement des opérations en trop car à chaque fois on trie tout @@ -56,10 +59,13 @@ int indiceFilsDroit(int i){ Voir le diapo pour les tests d'existence Pour ajouter un élément, on : -1. ajoute l'élément tout en bas -2. tant que l'élément est plus grand que son père, on les échange +1. ajoute l'élément tout en bas (i.e. le plus au fond du tableau) +2. tant que l'élément est plus petit (resp. plus grand) que son père, on les échange -> elle est en $O(\log_2 n)$ (car au pire on remonte à la racine) Voir le diapo pour la fonction d'ajout implémenté -Voir le diapo pour l'extraction \ No newline at end of file +Pour extraire le plus petit (resp. max) élément, on : +1. remplace la racine par son plus grand (resp. plus petit) fils +2. tant que l'élément est plus grand (resp. plus petit) qu'un de ses fils, on les échange +-> elle est aussi en $O(\log n)$ \ No newline at end of file diff --git "a/semestre 3/structures des donn\303\251es/6- Arbre binaire de recherche.md" "b/semestre 3/structures des donn\303\251es/6- Arbre binaire de recherche.md" index 78ef0c9..5213da7 100644 --- "a/semestre 3/structures des donn\303\251es/6- Arbre binaire de recherche.md" +++ "b/semestre 3/structures des donn\303\251es/6- Arbre binaire de recherche.md" @@ -15,8 +15,8 @@ On note $h$ sa hauteur Il s'agit de la même implémentation que pour les btree. min et max sont plus simples -|> pour le min, on regarde à gauche -> $O(\log n)$ -|> pour le max, on regarde à droite -> $O(\log n)$ +|> pour le min, on regarde à gauche -> $O(h)$ +|> pour le max, on regarde à droite -> $O(h)$ **Voir diapo pour toutes les implémentations standards** @@ -37,7 +37,7 @@ Quand on supprime, on doit remonter une valeur Cette structure cherche à équilibrer l'ABR pour avoir une relation entre $n$ et $h$ |> besoin de gérer l'insertion et la suppression -> est compliqué de gérer ça -On a donc créer l'AVL qui est un ABR équilibré +On a donc créer l'AVL qui esqqqqqqt un ABR équilibré |> propriété d'équilibre = la différence des hauteurs des fils gauche et droit de tout nœud ne peut excéder 1 |> on a donc $h=\log n$ -> tout devient en $\log n$ 🎉 @@ -98,11 +98,11 @@ AVL* rotGauche(AVL* racine) { 1. comme dans un ABR 2. tant que la diff de hauteur entre les fils gauche et droit ne dépassent pas 1, on continue de remonter 3. on note $A$ le premier ancêtre où cette différence dépasse 1 -4. Si $h(G) - h(D) = 2$, alors - 1. si $h(G) < h(D)$, on fait une rotation à gauche de $G$ +4. Si $h(G) - h(D) = 2$, alors ($g$ et $d$ sont les sous-arbres de $G$) + 1. si $h(g) < h(d)$, on fait une rotation à gauche de $G$ 2. on fait une rotation à droite de $A$ -5. Si $h(G)-h(D)=-2$, alors - 1. si $h(D) < h(G)$, on fait une rotation à droite de $D$ +5. Si $h(G)-h(D)=-2$, alors ($g$ et $d$ sont les sous-arbres de $G$) + 1. si $h(d) < h(g)$, on fait une rotation à droite de $D$ 2. on fait une rotation à gauche de $A$ 6. On a fini le traitement @@ -110,13 +110,15 @@ Insertion est en $O(\log n)$ **Suppression** 1. comme dans un ABR -2. Si le nœud supprimé n'a pas été remplacé par un autre nœud, ou s’il a été remplacé par son unique fils, on examine ses ancêtres en remontant jusqu’à la racine -3. S’il a été remplacé par le max de son fils gauche (ou le min de son fils droit), alors on examine tous les ancêtres de ce dernier en remontant jusqu’à la racine. +2. Si le nœud supprimé n'a pas été remplacé par un autre nœud, ou s’il a été remplacé par son unique fils, on examine ses ancêtres en remontant jusqu'à la racine +3. S’il a été remplacé par le max de son fils gauche (ou le min de son fils droit), alors on examine tous les ancêtres de ce dernier en remontant jusqu'à la racine. 4. Durant la remonté 1. si la différence est inférieur ou égal à 1, on met à jour la hauteur 2. si la différence est supérieure à 1, on applique les mêmes transformations que pour l'insertion Suppression est en $O(\log n)$ + +Étape 2 ou 3 permet de choisir à partir d'où remonter ## Tableau associatif Les AVL peuvent être pertinent pour les tableaux associatifs diff --git "a/semestre 3/structures des donn\303\251es/7- Graphe.md" "b/semestre 3/structures des donn\303\251es/7- Graphe.md" index 6c2e56b..d817917 100644 --- "a/semestre 3/structures des donn\303\251es/7- Graphe.md" +++ "b/semestre 3/structures des donn\303\251es/7- Graphe.md" @@ -33,6 +33,4 @@ Deux implémentations classiques |> liste d'adjacence -> $O(n)$, mais prend peu de places -> d'autres implémentations existent et peuvent être préférables lors de certains algo -**Voir le diapo pour la def de matrices et listes d'adjacence** - -:( \ No newline at end of file +**Voir le diapo pour la def de matrices et listes d'adjacence** \ No newline at end of file diff --git "a/semestre 3/structures des donn\303\251es/8- Parcours de graphe.md" "b/semestre 3/structures des donn\303\251es/8- Parcours de graphe.md" index 4bfab39..f813dc1 100644 --- "a/semestre 3/structures des donn\303\251es/8- Parcours de graphe.md" +++ "b/semestre 3/structures des donn\303\251es/8- Parcours de graphe.md" @@ -95,3 +95,16 @@ Complexité temporelle, chaque ligne de code est exécuté : Occupation mémoire est similaire pour itérative et récursive pour des $n$ pas trop grand |> par contre, comme récursive n'est pas terminal, elle prendra plus de place pour des $n$ très grands ### Parcours en largeur +``` +L = Liste(r) +Tant que B(L) n'est pas vide + Choisir un sommet s dans B(L) qui est successeur (ou voisin) du premier sommet ouvert de L + L = union de L et {s} +Fin Tant que +``` + +Le code *itératif* est similaire au parcours en profondeur +|> on remplace juste la pile par une file + +1. Comme dans un ABR +2. Si nœud est remplacé par \ No newline at end of file diff --git "a/semestre 3/structures des donn\303\251es/9- Arbre rouge-noir.md" "b/semestre 3/structures des donn\303\251es/9- Arbre rouge-noir.md" index 658c4e1..58629f8 100644 --- "a/semestre 3/structures des donn\303\251es/9- Arbre rouge-noir.md" +++ "b/semestre 3/structures des donn\303\251es/9- Arbre rouge-noir.md" @@ -15,9 +15,45 @@ Arbre rouge-noir |> AVL demandant moins de rotations |> racine est noire |> fils d'un rouge est noir -**voir le diapo pour les autres specs** +|> si un nœud a moins de deux fils, on considère que les fictifs sont noirs +|> le nombre de nœuds noirs sur un chemin de la racine vers une feuille est toujours le même + +Hauteur est toujours en $O(\log n)$ (on l'appelle *hauteur noire*) +-> les preuves sont sur le diapo Problème de ces arbres |> beaucoup de cas à gérer + +```mermaid +flowchart TB + GP[Grand-père] --- P[Père] + GP --- O[Oncle] + P --- X + P --- Frère +``` + +**Insertion** -> le nœud est rouge +1. Si père est noir, on termine +2. Si c'est la racine, on le met en noir et on termine +3. Si père est rouge *et* oncle est rouge, alors + - père devient noir + - oncle devient noir + - grand-père devient rouge + - on fait un appel récursif sur grand-père +4. Dans tous les autres cas + 1. Si père est un fils gauche + - seulement si c'est un fils droit, rotation gauche (X et père inversent leurs places) + - père devient noir + - grand-père devient noir + - rotation droite de grand-père + 2. Si père est un fils droit + - seulement si c'est un fils gauche, rotation droite (X et père inversent leurs places) + - père devient noir + - grand-père devient rouge + - rotation gauche de grand-père + +Est en $O(\log n)$ + +**Rattraper la suppression** ## Skip lists -> ici, on s'occupe des la concurrence \ No newline at end of file diff --git "a/semestre 3/structures des donn\303\251es/contenu feuille exam.txt" "b/semestre 3/structures des donn\303\251es/contenu feuille exam.txt" new file mode 100644 index 0000000..7878e17 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/contenu feuille exam.txt" @@ -0,0 +1,41 @@ +Hash +|> complexité +|> facteur de charge + +ABR +|> vérif rapide +|> insertion (rapide) +|> suppression (rapide) + +AVL +|> maj hauteur +|> insertion (rapide) +|> suppression + +Graphe +|> defs +|> parcours + +Tas +|> indices et existence +|> insertion (rapide) +|> supression (rapide) + +Skip list +|> insertion (rapide) +|> supression (rapide) + +ARN +|> insertion +|> supression (début) + +Partition via Hash +|> principe (rapide) + +Forêt +|> principe (rapide) +|> heuristique (rapide) + +Tas binomial +|> principe (rapide) +==================================== diff --git "a/semestre 3/structures des donn\303\251es/td/td10/exo1.md" "b/semestre 3/structures des donn\303\251es/td/td10/exo1.md" new file mode 100644 index 0000000..de1467a --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/td/td10/exo1.md" @@ -0,0 +1,10 @@ +--- +tags: + - sorbonne + - informatique + - structure-des-données + - td +semestre: 3 +--- +Pour récupérer les compostes connexes naïvement, durant un parcours, on liste par où on passe +|> à chaque fois qu'on a besoin de régénérer un parcours, on crée une nouvelle composante connexe \ No newline at end of file diff --git "a/semestre 3/structures des donn\303\251es/td/td8/exo2.c" "b/semestre 3/structures des donn\303\251es/td/td8/exo2.c" new file mode 100644 index 0000000..e0cb279 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/td/td8/exo2.c" @@ -0,0 +1,34 @@ +#include +typedef struct arc { + int v; + struct arc *suiv; +} Arc; + +typedef struct sommet { + int u; + Arc *L_succ; + Arc *L_prec; +} Sommet; + +typedef struct { + int nbsom; + Sommet *t_som; +} Graphe; + +void creeGraphe(Graphe *G, int n){ + G->nbsom = n; + G->t_som = (Sommet*) malloc(sizeof(Graphe)*n); +} + +void ajoutArc(Graphe *G, int i, int j){ + Arc *arcIn = (Arc*) malloc(sizeof(Arc)); + arcIn->v = i; + Arc *arcOut = (Arc*) malloc(sizeof(Arc)); + arcIn->v = j; + Sommet a = G->t_som[i]; + Sommet b = G->t_som[j]; + arcIn->suiv = a.L_succ; + a.L_succ = arcIn; + arcOut->suiv = b.L_prec; + a.L_prec = arcOut; +} -- cgit v1.2.3