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 --- .../1- Repr\303\251sentation de l'information.md" | 10 +- .../2- Programmation en ASM Mips.md | 24 +- .../architecture des ordinateurs/td/25-11-26.md | 4 + .../architecture des ordinateurs/td/25-12-10.md | 51 ++ .../architecture des ordinateurs/td/25-12-17.md | 95 ++++ .../tme/tme10/TP10_CheminDonneesMarep.circ | 567 +++++++++++++++++++++ .../tme/tme11/pgcd_ne_fonctionnant_pas.circ | 344 +++++++++++++ .../td/CC2.odt" | Bin 0 -> 35481 bytes .../0- Introduction.md" | 2 +- .../1- S\303\251miotique.md" | 2 +- .../2- Langage et \303\251tant.md" | 2 +- .../3- Langage et psychologie.md" | 2 +- .../4- Relativisme linguistique.md" | 27 +- .../td/1- Frege.md" | 3 + .../td/2- Husserl.md" | 3 + .../td/3- Merleau-Ponty.md" | 3 + .../td/4- Heidegger.md" | 5 +- .../td/5- Benjamin.md" | 3 + .../td/6- Kripke.md" | 3 + .../td/7- Putnam.md" | 3 + .../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 ++ 30 files changed, 1395 insertions(+), 148 deletions(-) create mode 100644 semestre 3/architecture des ordinateurs/td/25-12-10.md create mode 100644 semestre 3/architecture des ordinateurs/td/25-12-17.md create mode 100644 semestre 3/architecture des ordinateurs/tme/tme10/TP10_CheminDonneesMarep.circ create mode 100644 semestre 3/architecture des ordinateurs/tme/tme11/pgcd_ne_fonctionnant_pas.circ create mode 100644 "semestre 3/histoire philosophie m\303\251di\303\251vale/td/CC2.odt" 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" diff --git "a/semestre 3/architecture des ordinateurs/1- Repr\303\251sentation de l'information.md" "b/semestre 3/architecture des ordinateurs/1- Repr\303\251sentation de l'information.md" index 6d6d266..bfab1c4 100644 --- "a/semestre 3/architecture des ordinateurs/1- Repr\303\251sentation de l'information.md" +++ "b/semestre 3/architecture des ordinateurs/1- Repr\303\251sentation de l'information.md" @@ -105,11 +105,11 @@ Toute fonction booléenne peut être décrite par une composition des fonctions Soit $A$ un mot binaire de $n$ bits avec la famille $(a_i)_{i\in[0,n-1]}$ qui forme les bits de $A$. Si $p > n-1$, on a que $[p,n-1] = \varnothing$ par abus de langage -$B = A << p$ tel que +$B = A \ll p$ tel que |> $\forall i\in[0,p-1], b_i = 0$ |> $\forall i\in[p,n-1], b_i = a_{i-p}$ -$B = A >> p$ tel que +$B = A \gg p$ tel que |> $\forall i\in[0,p-1], b_i = a_{i+p}$ |> $\forall i\in[p,n-1], b_i = 0$ @@ -119,7 +119,7 @@ $B = A >> p$ tel que > Si $A = 0101$ et qu'on souhaite avoir $10$, on fait $m = 0110$ > |> $A+m = 0100$ > Puis on décale de 1 pour supprimer la valeur inutile -> |> $A >> 1 = 0010$ +> |> $A \gg 1 = 0010$ > [!warning] Comment faire un bon mask ? > Toujours ne mettre que des 1 là où on veut garder des valeurs, sinon on risque de perdre des infos ! @@ -254,8 +254,8 @@ Attention à l'overflow ! |> la retenu est ignorée quand on dépasse -> est de l'arithmétique modulaire sur $2^n$ Décaler à gauche de $n$ revient à multiplier par la base $B^n$ -|> $(a_{p-1}\ldots a_0)_b\times 2^n = (a_{p-1}\ldots a_0)_b << n = (a_{p-1}\ldots a_0\underbrace{0\ldots0}_n)_b$ -|> $(a_{p-1}\ldots a_0)_b/2^n = (a_{p-1}\ldots a_0)_b >> n = (a_{p-1}\ldots a_{n})$ +|> $(a_{p-1}\ldots a_0)_b\times 2^n = (a_{p-1}\ldots a_0)_b \ll n = (a_{p-1}\ldots a_0\underbrace{0\ldots0}_n)_b$ +|> $(a_{p-1}\ldots a_0)_b/2^n = (a_{p-1}\ldots a_0)_b \gg n = (a_{p-1}\ldots a_{n})$ ## Entiers relatifs On les appelle les nombre entiers signés diff --git a/semestre 3/architecture des ordinateurs/2- Programmation en ASM Mips.md b/semestre 3/architecture des ordinateurs/2- Programmation en ASM Mips.md index edc5cd3..568a612 100644 --- a/semestre 3/architecture des ordinateurs/2- Programmation en ASM Mips.md +++ b/semestre 3/architecture des ordinateurs/2- Programmation en ASM Mips.md @@ -395,22 +395,22 @@ int main(){ ```asm .text # prologue -addiu $29, $29, -12 # car on stock 3 mots + addiu $29, $29, -12 # car on stock 3 mots # initialisation des variables -ori $8, $0, 1 -sw $8, 0($29) -ori $8, $0, 2 -sw $8, 4($29) + ori $8, $0, 1 + sw $8, 0($29) + ori $8, $0, 2 + sw $8, 4($29) # corps du main -lw $8, 0($29) -lw $9, 4($29) -addu $8, $8, $9 -sw $9, 8($29) + lw $8, 0($29) + lw $9, 4($29) + addu $8, $8, $9 + sw $9, 8($29) # épilogue -addiu $29, $29, 12 + addiu $29, $29, 12 # exit -ori $2, $0, 10 -syscall + ori $2, $0, 10 + syscall ``` ## Fonction Pour arriver à une fonction, on utilise `jal label` diff --git a/semestre 3/architecture des ordinateurs/td/25-11-26.md b/semestre 3/architecture des ordinateurs/td/25-11-26.md index e72f90a..47555b1 100644 --- a/semestre 3/architecture des ordinateurs/td/25-11-26.md +++ b/semestre 3/architecture des ordinateurs/td/25-11-26.md @@ -73,6 +73,10 @@ $(\bar a.b.c)+(a.\bar b.\bar c)+(a.b.\bar c)+(a.b.c)$ | 1 | 1 | 0 | 0 | 1 | $s=(\bar u_1.\bar u_2.c_{in})+(\bar u_1.u_2.\bar c_{in})+(u_1.\bar u_2.\bar c_{in})+(u_1.u_2.c_{in})=u_1\oplus u_2\oplus c_{in}$ où $\oplus$ est $\mathrm{xor}$ (à refaire) $c_{out}=(\bar u_1.u_2.c_{in})+(u_1.\bar u_2.c_{in})+(u_1.u_2.c_{in})+(u_1.u_2.\bar c_{in})=a.b+a.c_{in}+b.c_{in}=c_{in}.(a\oplus b)+a.b$ (à refaire) + +$s = (\bar a . \bar b . c)+(\bar a.b.\bar c)+(a.\bar b.\bar c)+(a.b.c)$ +$s = (\bar a . (\bar b + (\bar a.b.\bar c)) . c + (\bar a.b.\bar c))$ + | $i_3$ | $i_2$ | $i_1$ | $i_0$ | $a$ | $b$ | $c$ | $d$ | $e$ | $f$ | $g$ | | ----- | ----- | ----- | ----- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | | diff --git a/semestre 3/architecture des ordinateurs/td/25-12-10.md b/semestre 3/architecture des ordinateurs/td/25-12-10.md new file mode 100644 index 0000000..26df476 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/td/25-12-10.md @@ -0,0 +1,51 @@ +--- +tags: + - sorbonne + - informatique + - architecture-des-ordinateurs + - td +semestre: 3 +--- +Un transfert est le déplacement d'une donnée lors d'un cycle + +`LO <- HI or 0` + +`r6 <- r4 or 0` + +`AD <- PC + AD` + +``` +AD <- r[20] +r[8] <- AD + r[18] +``` + +``` +AD <- r[8] +AD <- m[AD] +``` + +``` +IR <- m[PC] +PC <- PC + 4 +AD <- r[5] or 0 +r[3] <- r[7] + AD +``` + +``` +IR <- m[PC] +PC <- PC + 4 +AD <- r[8] + 4 +DT <- m[AD] +r[4] <- DT or 0 +``` + +``` +IR <- m[PC] +PC <- PC + 4 +AD <- r[6] or 0 +m[AD] <- r[9] or 0 +``` + +1. `add $9, $6, $8` +2. `sw $9, 12($10)` +3. `jalr $9, $6` diff --git a/semestre 3/architecture des ordinateurs/td/25-12-17.md b/semestre 3/architecture des ordinateurs/td/25-12-17.md new file mode 100644 index 0000000..f2db8c5 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/td/25-12-17.md @@ -0,0 +1,95 @@ +--- +tags: + - informatique + - sorbonne + - td + - architecture-des-ordinateurs +Semestre: 3 +--- +4 états -> 2 bits +4 + 3 = 7 transitions +|> 0 -> 1, 1 -> 2, 2 -> 3, 3 -> 0, 1 -> 0, 2 -> 0, 0 -> 0 + +RST = reset + +$F_1 = \overline{\text{RST}} . (c_1 \oplus c_2)$ +$F_0 = \overline{\text{RST}} . \bar c_0$ + +```mermaid +flowchart LR + A-- 1 ---A + A-- 0 ---B + B-- 0 ---B + B-- 1 ---C + C-- 1 ---A + C-- 0 ---D + D-- 0 ---B + D-- 1 ---E + E-- 0,1 ---E +``` + +```mermaid +flowchart LR + A-- 0 ---B + B-- 1 ---C + C-- 0 ---D + D-- 1 ---E +``` + +5 états -> 3 bits +4 transitions + +| États | $C_2$ | $C_1$ | $C_0$ | +| ----- | ----- | ----- | ----- | +| A | 0 | 0 | 0 | +| B | 0 | 0 | 1 | +| C | 0 | 1 | 0 | +| D | 0 | 1 | 1 | +| E | 1 | 0 | 0 | + +ext_A = ext_B = ext_C +WE_A = WE_B = WE_C +ext_D = 0 + +ADD = 0 +1. `RA,RB,RC` -> ext_{A,B,C}+WE_{A,B,C} +2. `RD = RA+RB` -> OP_A+OP_B + ADD + WE_D +3. `RD = RD + RC` + +5 états -> 3 bits +6 transitions + +init = chargement dans les registres +s0 = comparaison +s1 = a < b -> a = a, b = b-a +s2 = a > b -> a = a-b, b = a +end = a == b -> met le résultat dans le registre + +| États | Valeur | +| ----- | ------ | +| init | 0 | +| $S_0$ | 1 | +| $S_1$ | 10 | +| $S_2$ | 11 | +| end | 100 | + +| $C_2$ | $C_1$ | $C_0$ | $a>b$ | $a=b$ | $F_2$ | $F_1$ | $F_0$ | +| ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | +| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | +| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | +| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | +| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | +| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | +| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | +| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | +| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | +| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | +| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | +| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | +| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | +| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | +| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | +$F_0 = \overline{S_0.((a + + This file is intended to be loaded by Logisim-evolution v4.0.0(https://github.com/logisim-evolution/). + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/semestre 3/architecture des ordinateurs/tme/tme11/pgcd_ne_fonctionnant_pas.circ b/semestre 3/architecture des ordinateurs/tme/tme11/pgcd_ne_fonctionnant_pas.circ new file mode 100644 index 0000000..70598c7 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme11/pgcd_ne_fonctionnant_pas.circ @@ -0,0 +1,344 @@ + + + This file is intended to be loaded by Logisim-evolution v4.0.0(https://github.com/logisim-evolution/). + + + + + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git "a/semestre 3/histoire philosophie m\303\251di\303\251vale/td/CC2.odt" "b/semestre 3/histoire philosophie m\303\251di\303\251vale/td/CC2.odt" new file mode 100644 index 0000000..294ebb2 Binary files /dev/null and "b/semestre 3/histoire philosophie m\303\251di\303\251vale/td/CC2.odt" differ diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/0- Introduction.md" "b/semestre 3/philosophie g\303\251n\303\251rale/0- Introduction.md" index 1da0b7d..4e99ff8 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/0- Introduction.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/0- Introduction.md" @@ -70,7 +70,7 @@ Sprache = langue -> mais peut aussi avoir un sens concret ressemblant à parole **rattraper le cours** -Triangle d'Aristote : +Triangle d'Aristote (dans Métaphysique) : ```mermaid flowchart LR A[États de l'âme] --- B diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/1- S\303\251miotique.md" "b/semestre 3/philosophie g\303\251n\303\251rale/1- S\303\251miotique.md" index 82dd948..59e22f4 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/1- S\303\251miotique.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/1- S\303\251miotique.md" @@ -78,7 +78,7 @@ Mais les peuvent-ils indiquer qlq chose ? Existe-t-il un système de langage animal ? |> si les animaux poussent un crie spécifique à un moment, il manifeste qlq chose de spécifique (c'est le cas) |> ressemble à un proto-langage -|> il semble manquer un une syntaxe +|> il semble manquer une syntaxe |> le langage humain est libérer de ce contexte Descartes questionne l'existence du langage animal diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/2- Langage et \303\251tant.md" "b/semestre 3/philosophie g\303\251n\303\251rale/2- Langage et \303\251tant.md" index e258794..afe8c69 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/2- Langage et \303\251tant.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/2- Langage et \303\251tant.md" @@ -11,7 +11,7 @@ Quel est le rapport que le langage entretient avec l'être ? *muthos* = Domaine de l’opinion fausse, de la rumeur, du discours de circonstance par opposition au *logos* *logos* = la raison, le discours rationnel, par opposition au *muthos*, le discours irrationnel -Poème de Parménide +_De la nature_, Parménide |> langage (*muthos*/*logos*) ne permet de parler que de ce qui est |> impossible de parler du non être -> impossible de penser le non être diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/3- Langage et psychologie.md" "b/semestre 3/philosophie g\303\251n\303\251rale/3- Langage et psychologie.md" index 54531e0..c5baf81 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/3- Langage et psychologie.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/3- Langage et psychologie.md" @@ -8,7 +8,7 @@ semestre: 3 Boethe en commentant Aristote |> le langage a besoin de passer par les états de l'âme pour qu'il puisse se référer à quelque chose -Augustin +Augustin ([[1- Sémiotique]]) |> signe sert à communiquer à qlq'un ce qu'on a dans l'esprit |> permet de passer d'une intériorité à une autre diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/4- Relativisme linguistique.md" "b/semestre 3/philosophie g\303\251n\303\251rale/4- Relativisme linguistique.md" index f61d206..66a642d 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/4- Relativisme linguistique.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/4- Relativisme linguistique.md" @@ -30,4 +30,29 @@ Langue sert à trouver de nouvelles pensées |> permet aussi d'exprimer des sentiments complexes -> est un organe de la pensée -Besoin de supposer des capacités linguistiques innées, sinon impossible de construire les langues \ No newline at end of file +Besoin de supposer des capacités linguistiques innées, sinon impossible de construire les langues + +[...] + +Comment est-ce possible d'avoir un relativisme linguistique et d'apprendre plusieurs langues ? + +Paul Ricœur, _Sur la traduction_ +|> ne voit pas le mythe de Babel comme étant une catastrophe + +Traduction est une forme d'essai pour retrouver un langage idéal -> le « vrai langage » +|> [[5- Benjamin]] +|> la traduction ne s'occupe pas que du sens, cherche aussi à montrer la musique de la langue (en littérature en tout cas) +|> traduction se rapprochant au maximum du texte original est destiné à ceux qui pourraient le comprendre à l'origine + +Antoine Berman, mauvaises traductions sont +|> ethnocentriques -> ramène l'étranger à notre propre culture, oublie sa différence +|> hypertextuelles -> référence d'un texte à un autre texte (revient à remplacer le modèle stylistique du texte d'origine) +|> platoniciennes -> oublie la matérialité de la langue +=> forme de sur-traduction + +Formes de traduction (pour Goethe) : +1. simple connaissance de l'étranger +2. assimilation transformant l'étranger en familier +3. altération de sa propre langue pour accueillir l'étrangeté de l'autre langue + +Il existe certaines choses intraduisibles, mais rien n'est totalement intraduisible \ No newline at end of file diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/td/1- Frege.md" "b/semestre 3/philosophie g\303\251n\303\251rale/td/1- Frege.md" index fa68102..89fa298 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/td/1- Frege.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/td/1- Frege.md" @@ -6,6 +6,9 @@ tags: - td semestre: 3 --- +Frege, _Sens et Dénotation_ + + Cherche à comprendre comment le langage parle de la pensée |> rapport entre le mot, ce qu'il signifie et le monde diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/td/2- Husserl.md" "b/semestre 3/philosophie g\303\251n\303\251rale/td/2- Husserl.md" index 23d5382..3b6825b 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/td/2- Husserl.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/td/2- Husserl.md" @@ -6,6 +6,9 @@ tags: - td semestre: 3 --- +Husserl, _Recherches logiques_ + + Cherche à étudier le rapport entre signes et rapports mentaux Ici, cherche à montrer que la signification d'un mot ne peut être réduit au mot lui-même ou à une représentation mentale ou à un avis assertif diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/td/3- Merleau-Ponty.md" "b/semestre 3/philosophie g\303\251n\303\251rale/td/3- Merleau-Ponty.md" index 028cb95..f622d1c 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/td/3- Merleau-Ponty.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/td/3- Merleau-Ponty.md" @@ -6,6 +6,9 @@ tags: - td semestre: 3 --- +Merleau-Ponty, _Signes_ + + Locke, _Essai sur l'entendement humain_ -> mots sont des vecteurs permettant de transmettre la pensée Casse la conception commune du "nom = objet" (comme celle de Locke) diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/td/4- Heidegger.md" "b/semestre 3/philosophie g\303\251n\303\251rale/td/4- Heidegger.md" index f53276c..88954c6 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/td/4- Heidegger.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/td/4- Heidegger.md" @@ -6,6 +6,9 @@ tags: - td semestre: 3 --- +Heidegger, _Acheminement vers la parole_ + + Heidegger souhaite montrer qu'on ne fait pas que répondre à la parole C'est la parole qui produit l'humain @@ -58,7 +61,7 @@ Poème est l'endroit où le langage s'exprime le plus |> le poète reconstruit le langage en proposant de nouvelles approches |> les mots normaux du langage sont morts -Nommé, c'est appeler -> on fait venir à la présence grâce aux mots +Nommer, c'est appeler -> on fait venir à la présence grâce aux mots |> parole poétique est une évocation |> invoque les choses (i.e. tout ce qui dans le monde) et leur monde diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/td/5- Benjamin.md" "b/semestre 3/philosophie g\303\251n\303\251rale/td/5- Benjamin.md" index e4f0629..ab54179 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/td/5- Benjamin.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/td/5- Benjamin.md" @@ -6,6 +6,9 @@ tags: - td semestre: 3 --- +Benjamin, _La Tâche du traducteur_ + + Sens est indissociable de la langue |> impossible de faire passer le sens d'une langue à une autre langue -> idée que la traduction garde le sens est impossible diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/td/6- Kripke.md" "b/semestre 3/philosophie g\303\251n\303\251rale/td/6- Kripke.md" index ee7b09f..e8ec6c4 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/td/6- Kripke.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/td/6- Kripke.md" @@ -6,6 +6,9 @@ tags: - td semestre: 3 --- +Kripke, _La Logique des noms propres_ + + N'est pas nécessaire de connaître singulièrement quelqu'un pour pouvoir parler de lui |> on a juste besoin de faire partie de la chaîne de communication pour en parler diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/td/7- Putnam.md" "b/semestre 3/philosophie g\303\251n\303\251rale/td/7- Putnam.md" index fdc5541..b6da0c4 100644 --- "a/semestre 3/philosophie g\303\251n\303\251rale/td/7- Putnam.md" +++ "b/semestre 3/philosophie g\303\251n\303\251rale/td/7- Putnam.md" @@ -6,6 +6,9 @@ tags: - td semestre: 3 --- +Putnam, _The meaning of "meaning"_ + + Après [[1- Frege]] et [[2- Husserl]] |> mais ne défend pas un platonisme sémantique |> défend signification sociologique 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