From ecf05510045b2ac78b479ae746a43078e22cee4f Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Mon, 8 Dec 2025 14:13:46 +0100 Subject: =?UTF-8?q?Cours=20du=201=20au=205=20d=C3=A9cembre?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- .../architecture des ordinateurs/td/25-12-03.md | 10 + .../tme/tme9/tme9.circ | 758 +++++++++++++++++++++ .../td/5-.md" | 19 +- .../10- Probabilit\303\251s.md" | 8 + ...2- Le langage de la logique propositionnelle.md | 4 +- .../4- Interpr\303\251ter les formules.md" | 3 +- .../logique et notions formelles/td/25-12-01.md | 9 + .../5- Automates finis.pdf" | Bin 0 -> 313508 bytes .../3- Langage et psychologie.md" | 13 +- .../4- Relativisme linguistique.md" | 33 + .../td/7- Putnam.md" | 43 ++ .../td/8- Austin.md" | 17 + semestre 3/philosophie politique/2- Punir.md | 42 +- ...e punissable, faut-il avoir agi librement ?.md" | 34 + ...tition, file de priorit\303\251 fusionnable.md" | 21 + .../6- Arbre binaire de recherche.md" | 67 +- .../9- Arbre rouge-noir.md" | 1 - 17 files changed, 1069 insertions(+), 13 deletions(-) create mode 100644 semestre 3/architecture des ordinateurs/td/25-12-03.md create mode 100644 semestre 3/architecture des ordinateurs/tme/tme9/tme9.circ create mode 100644 "semestre 3/logique et notions formelles/10- Probabilit\303\251s.md" create mode 100644 semestre 3/logique et notions formelles/td/25-12-01.md create mode 100644 "semestre 3/math\303\251matiques discr\303\250tes/5- Automates finis.pdf" create mode 100644 "semestre 3/philosophie g\303\251n\303\251rale/4- Relativisme linguistique.md" create mode 100644 "semestre 3/philosophie g\303\251n\303\251rale/td/7- Putnam.md" create mode 100644 "semestre 3/philosophie g\303\251n\303\251rale/td/8- Austin.md" create mode 100644 "semestre 3/philosophie politique/Punir - Pour \303\252tre punissable, faut-il avoir agi librement ?.md" create mode 100644 "semestre 3/structures des donn\303\251es/10- Ensemble, partition, file de priorit\303\251 fusionnable.md" diff --git a/semestre 3/architecture des ordinateurs/td/25-12-03.md b/semestre 3/architecture des ordinateurs/td/25-12-03.md new file mode 100644 index 0000000..90288aa --- /dev/null +++ b/semestre 3/architecture des ordinateurs/td/25-12-03.md @@ -0,0 +1,10 @@ +--- +tags: + - sorbonne + - informatique + - architecture-des-ordinateurs +semestre: 3 +--- +adresse = adresse de lecture dans la ram -> 5 bits +commande = lecture / écriture -> 3 bits (2 pour le type : word, half, byte et un pour lecture/écriture) +données = data transférées -> 32 bits \ No newline at end of file diff --git a/semestre 3/architecture des ordinateurs/tme/tme9/tme9.circ b/semestre 3/architecture des ordinateurs/tme/tme9/tme9.circ new file mode 100644 index 0000000..f54e14a --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme9/tme9.circ @@ -0,0 +1,758 @@ + + + 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/5-.md" "b/semestre 3/histoire philosophie m\303\251di\303\251vale/td/5-.md" index 2b2cfa1..6081990 100644 --- "a/semestre 3/histoire philosophie m\303\251di\303\251vale/td/5-.md" +++ "b/semestre 3/histoire philosophie m\303\251di\303\251vale/td/5-.md" @@ -31,8 +31,8 @@ Pour Henri de Gand, Dieu nous a donné sa raison |> illumination générale est celle qui provient de Dieu Donc deux connaissances possibles -|> connaissance de nos sens est certaine -> lumière naturelle de la raison, pas de Dieu ici -|> +|> connaissance de nos sens est certaine -> lumière naturelle de la raison, pas de Dieu ici +|> connaissance provenant d'une certaine illumination -> permet de connaître Dieu 1. plus général 2. indéterminé @@ -43,4 +43,17 @@ Le passage de la 2 à la 3 est l'illumination divine pour Henri de Gand Platon, _Timée_ -> construction d'une cosmologie cohérente |> fondée sur les axiomes de la raison -|> cosmologie doit résoudre un pb difficile reposant sur le changement incessant \ No newline at end of file +|> cosmologie doit résoudre un pb difficile reposant sur le changement incessant + +Lire les textes sur Moodle pour le contrôle de la semaine prochaine + +Création par abstraction = voie aristotélicienne +Création par modèle divin = voie théologique (?) +|> ces deux modèles parle de la vérité de la chose + +Les idées abstraites gardent un côté mutable pour Henri de Gand +|> elles ne sont donc pas certaines +-> utilise Augustin pour expliquer pourquoi il faut se détourner des sens + +L'illumination permet d'avoir une connaissance immuable +|> sinon, il manque qlq chose \ No newline at end of file diff --git "a/semestre 3/logique et notions formelles/10- Probabilit\303\251s.md" "b/semestre 3/logique et notions formelles/10- Probabilit\303\251s.md" new file mode 100644 index 0000000..953d4dc --- /dev/null +++ "b/semestre 3/logique et notions formelles/10- Probabilit\303\251s.md" @@ -0,0 +1,8 @@ +--- +tags: + - sorbonne + - philosophie + - logique-notions-formelles +semestre: 3 +--- +... \ No newline at end of file diff --git a/semestre 3/logique et notions formelles/2- Le langage de la logique propositionnelle.md b/semestre 3/logique et notions formelles/2- Le langage de la logique propositionnelle.md index bba380b..925b54a 100644 --- a/semestre 3/logique et notions formelles/2- Le langage de la logique propositionnelle.md +++ b/semestre 3/logique et notions formelles/2- Le langage de la logique propositionnelle.md @@ -8,11 +8,11 @@ semestre: 3 Ce qui définit la forme logique d'un argument sont les mots logiques Il y a deux types de mots logiques : -- les quantifieurs : "tous", "certains" +- les quantificateurs : "tous", "certains" - les connecteurs propositionnelles : "si ..., alors ...", "... ou ..." La logique propositionnelle est celle des connecteurs propositionnelles -La logique du premier ordre (ou des prédicats) est celle des quantifieurs +La logique du premier ordre (ou des prédicats) est celle des quantificateurs On formalise la logique propositionnelle pour les analyser -> permet de dire si les arguments sont valides diff --git "a/semestre 3/logique et notions formelles/4- Interpr\303\251ter les formules.md" "b/semestre 3/logique et notions formelles/4- Interpr\303\251ter les formules.md" index 0d362ff..f994745 100644 --- "a/semestre 3/logique et notions formelles/4- Interpr\303\251ter les formules.md" +++ "b/semestre 3/logique et notions formelles/4- Interpr\303\251ter les formules.md" @@ -16,7 +16,8 @@ Une dvv pour le langage propositionnelle $\{p,q,r,s\}$ est par exemple : $$ d : \{p,q,r,s\} \to \{V,F\} $$ telle que $$ d(p)=V,\quad d(q)=F,\quad d(r)=F,\quad d(s)=V $$ -*rattraper $\bar d$ diapo 8* + +$\bar d$ est extension de $d$ telle que $\bar d$ respecte les définitions des connecteurs La table de vérité est un tableau donnant les différentes valeurs de vérité des différentes dvv existantes diff --git a/semestre 3/logique et notions formelles/td/25-12-01.md b/semestre 3/logique et notions formelles/td/25-12-01.md new file mode 100644 index 0000000..5b65016 --- /dev/null +++ b/semestre 3/logique et notions formelles/td/25-12-01.md @@ -0,0 +1,9 @@ +--- +tags: + - sorbonne + - philosophie + - logique-notions-formelles + - td +semestre: 3 +--- +4/52 diff --git "a/semestre 3/math\303\251matiques discr\303\250tes/5- Automates finis.pdf" "b/semestre 3/math\303\251matiques discr\303\250tes/5- Automates finis.pdf" new file mode 100644 index 0000000..20ef41d Binary files /dev/null and "b/semestre 3/math\303\251matiques discr\303\250tes/5- Automates finis.pdf" differ 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 98c0363..54531e0 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" @@ -93,4 +93,15 @@ Par conséquent, il n'y a rien à rechercher ici |> c'est la grammaire apparente qui complexifie inutilement ici Signification d'un mot est son emploi dans le langage -|> pas possible de comprendre un mot isolément \ No newline at end of file +|> pas possible de comprendre un mot isolément + +Quand on comprend un mot dans le langage, on sait comment il est employé +-> approche pragmatique +|> pendant qu'on prononce une phrase, on ne saurait pas ce qu'elle signifie +|> n'est pas une approche instantanée -> n'est pas un *eureka* +|> signification n'est pas un épisode mental +-> est une capacité/une disposition à savoir employer/à comprendre une phrase d'une manière intelligente +|> ce sont juste des pratiques faites avec le langage +|> c'est donc une règle + +Les critères de la règle ne doivent pas être connues par un seul individu \ No newline at end of file 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" new file mode 100644 index 0000000..f61d206 --- /dev/null +++ "b/semestre 3/philosophie g\303\251n\303\251rale/4- Relativisme linguistique.md" @@ -0,0 +1,33 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-générale +semestre: 3 +--- +Les visions du monde proposées par les langues, sont-elles fondamentalement incompatibles ? + +Hamann, _Métacritique du purisme de la raison_ +|> critique de Kant -> il n'a pas assez parlé du langage + +Herder +|> critique les généalogies du langage +|> suppose que l'être humain peut instituer le langage qui sont apparus à l'aide du langage +-> raisonnement cyclique +|> besoin que le langage soit présent dès l'origine de l'humain +|> besoin d'avoir un lien entre la communauté phonétique et le langage +|> critique que l'universalisation réduit les particularités de chaque langue +-> rien ne peut être universel +|> mène à la construction d'un nationalisme philosophique +|> *weltanschauung* (conception du monde) différent en fonction de chaque langue + +La communication est-elle possible entre plusieurs langues ? +Comment traduire ? + +Humboldt (Wilhelm von), _œuvre à trouver_ +Langue sert à trouver de nouvelles pensées +|> sans les mots, on ne pourrait pas faire grand chose +|> 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 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" new file mode 100644 index 0000000..fdc5541 --- /dev/null +++ "b/semestre 3/philosophie g\303\251n\303\251rale/td/7- Putnam.md" @@ -0,0 +1,43 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-générale + - td +semestre: 3 +--- +Après [[1- Frege]] et [[2- Husserl]] +|> mais ne défend pas un platonisme sémantique +|> défend signification sociologique + +Extension / intention +|> extension d'un concept est l'ensemble des choses touchant le concept +|> intention est le sens + +Étoile du matin / Étoile du soir +|> extension = vénus +|> intention est différente + +Redéfinition par la négative +|> nie les présupposés mentalistes +|> nie que l'intention fixe l'extension +-> défend après une rigidité lexicale, mais pas nécessaire + +Expérience de pensée = il existe une Terre jumelle +|> le mot « eau » est un autre liquide (pas $H_2O$, mais $XYZ$), mais possède la même fonction que l'eau +|> ce mot ne possède pas la même extension + +État psychologique ne détermine pas l'utilisation des mots +-> elles sont extérieures de notre tête + +Différence par rapport à [[6- Kripke]] +|> les deux nient la même chose, mais leurs méthodes et leurs conclusions diffèrent +|> pour Kripke, les descriptions diffèrent -> ce sont les indexicaux au sens logiques qui ne diffèrent pas +|> pour Putnam, il existe un caractère indexical dans tous les mots -> on apprend les choses à l'aide du contexte +|> pour Putnam, sans expert permettant de fixer le sens, il reste indéterminé +-> Putnam en déduit que les significations ne sont pas dans la tête +|> la référence détermine la signification, donc on a besoin de l'avoir en dehors de notre tête +|> présupposé qu'il partage avec Frege +-> est une généralisation de la théorie de Kripke +=> est discutable car elle repose sur le présupposé +|> il prouve une disjonction, pas la généralisation sans le présupposé \ No newline at end of file diff --git "a/semestre 3/philosophie g\303\251n\303\251rale/td/8- Austin.md" "b/semestre 3/philosophie g\303\251n\303\251rale/td/8- Austin.md" new file mode 100644 index 0000000..6fedb8e --- /dev/null +++ "b/semestre 3/philosophie g\303\251n\303\251rale/td/8- Austin.md" @@ -0,0 +1,17 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-générale + - td +semestre: 3 +--- +Parle de la réussite des énoncés performatifs + +Règles pour la réussite d'un énoncé performatif : +- procédure doit véritablement exister -> conventions doit être acceptés +- circonstances doit être appropriées à l'invocation de la procédure + +Le langage ne sert pas qu'à décrire la réalité +|> les énoncés performatifs ne peuvent pas être qualifiés de vrai ou faux +|> ces énoncés fonctionnent grâce au cadre social \ No newline at end of file diff --git a/semestre 3/philosophie politique/2- Punir.md b/semestre 3/philosophie politique/2- Punir.md index ba7aeeb..768a97d 100644 --- a/semestre 3/philosophie politique/2- Punir.md +++ b/semestre 3/philosophie politique/2- Punir.md @@ -40,8 +40,8 @@ Si on fonde le droit de punir sur une infinité, il sera aussi infini, Montesqui Conséquentialisme = justifie la peine par ses bonnes conséquences (*forward looking*) |> utilitarisme = cherche à maximiser le bonheur du plus grand nombre --> Beccaria (_Des délits et des peines_), Bentham (_Rationale of Judicial Evidence, Specially Applied to English Practice_), Platon (_Protagoras_) -|> pour Beccaria, on a besoin d'une proportion, sinon on ne limite pas du les crimes très dangereux (voir aussi Montesquieu, _Esprit des lois_) +-> Beccaria (_Des délits et des peines_), Bentham (_Rationale of Judicial Evidence, Specially Applied to English Practice_), Platon (_Protagoras_) +|> pour Beccaria, on a besoin d'une proportion, sinon on ne limite pas les crimes très dangereux (voir aussi Montesquieu, _Esprit des lois_) Rétributivisme = justifie la peine par la commission de la peine (*backward looking*) -> Kant (_Doctrine du droit_), Hegel (_Principes de la philosophie du droit_) @@ -92,6 +92,7 @@ Hart, _Punishment and Responsibility_ ![[Pasted image 20251127120330.png]] ## B. Quoi punir ? +### Paternalisme, anti-paternalisme Paternalisme = interférence avec la liberté d'action d'une personne se référant exclusivement pour des valeurs bonnes pour la personne concernée (définition de G. Dworkin) |> aucune loi n'est paternaliste en soi |> une loi est paternaliste quand elle vise à protéger les personnes qu'elle contraint @@ -108,6 +109,41 @@ Construction du marché des idées (*market place of ideas*) pour justifier la l |> le vrai émerge toujours du faux |> permet aussi d'éviter de créer un dogme vrai -> on doit croire aux choses vraies pour des bonnes raisons -> les mêmes raisons pour le principe de non-nuisance + +Le paternalisme touche *la manière de justifier une loi* et non son contenu + +Problème de la vision de Mill -> pense que l'humain est rationnel +|> Hart, _Law, liberty, morality_ +|> l'humain n'est pas forcément rationnel et ne sait pas forcément ce qu'il vaut le mieux pour lui +-> le consommateur est très vulnérable par manque de connaissance +|> beaucoup de failles psychologiques dans l'humain + +Préférence adaptative / contre-adaptative +|> préférence adaptative = être content de ce qu'on a, peu importe si on le pense vraiment +|> préférence contre-adaptative = n'être jamais content de ce qu'on a, peu importe si on le pense vraiment +-> choix relevant de ce type de préférence n'est donc pas libre + +Dworkin, _Paternalism_ +>Puisque nous sommes tous conscients de nos propensions irrationnelles, de nos lacunes cognitives et émotionnelles, ainsi que de notre ignorance évitable et inévitable, il est rationnel et prudent de notre part de souscrire à des « polices d'assurance sociale ». Nous pouvons débattre des avantages et des inconvénients des mesures paternalistes proposées en termes de ce que des individus pleinement rationnels accepteraient comme formes de protection. [...] Je suggère que nous considérions l'imposition d'interventions paternalistes dans ce type de situations comme une sorte de police d'assurance que nous souscrivons pour nous prémunir contre des décisions lourdes de conséquences, potentiellement dangereuses et irréversibles. +### Droit et moralité +Le droit doit-il sanctionner l'immoralité ne nuisant pas à autrui ? +|> Devlin, « La morale et le droit pénal » + +Société a besoin d'exprimer un jugement moral pour être une société +|> besoin d'un noyau moral commun pour fonder une société + +Société a le droit d'utiliser la moralité pour préserver son existence + +Ce qui permet de décider la société est le bon sens + +Hart contredit ça +|> le noyau de la moralité dans la société est complexe +|> l'unicité de la moralité est peu évidente +|> la définition entre une société et sa moralité est aussi peu intuitive +-> quelle valeur morale à faire respecter la morale pour de mauvaises raisons ? ## C. Comment punir ? ## D. Qui punir ? -Pour être punissable, faut-il avoir agi librement ? \ No newline at end of file +Pour être punissable, faut-il avoir agi librement ? + +Loi de Hume -> impossible d'obtenir une description normative depuis une description descriptive +|> l'inverse est aussi impossible \ No newline at end of file diff --git "a/semestre 3/philosophie politique/Punir - Pour \303\252tre punissable, faut-il avoir agi librement ?.md" "b/semestre 3/philosophie politique/Punir - Pour \303\252tre punissable, faut-il avoir agi librement ?.md" new file mode 100644 index 0000000..d27ac37 --- /dev/null +++ "b/semestre 3/philosophie politique/Punir - Pour \303\252tre punissable, faut-il avoir agi librement ?.md" @@ -0,0 +1,34 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-politique + - devoir +semestre: 3 +--- +Être punissable +|> il existe une légitimité de se faire punir +|> légitimité = avoir le droit de +|> punir = infliger consciemment de la souffrance à autrui suite à une action + +Avoir agi librement +|> agir par nous-même, sans influence extérieure notable +|> agir selon notre propre volonté (nous ne sommes pas manipulés) + +Présupposé = nous sommes punissables, sauf dans certaines conditions + +--- + +Quand une personne est punissable par une autre, il existe une légitimité de l'autre personne à la punir, c'est-à-dire qu'elle possède le droit d'infliger consciemment de la souffrance à cette personne suite à une de ses actions. Par exemple, en France, si un individu tue quelqu'un d'autre, il devient punissable par l'État à cause de son acte. Cela est particulièrement vrai si elle a agi librement. En effet, si elle n'a pas été manipulée, elle a agi selon sa propre volonté la rendant alors pleinement responsable de son acte. +Ce rôle de la liberté dans la légitimité de la punition est loin d'être évident : un meurtrier reste un meurtrier, peu importe s'il a été manipulé au point de commettre son crime. De plus, cela reviendrait à nier le statut d'être raisonnable l'ayant mené à faire ce choix. Pourtant, sous l'influence de certaines drogues, il devient impossible de distinguer la réalité du rêve et, par conséquent, de pouvoir agir rationnellement. +Ainsi, agir librement est-ce une condition nécessaire pour être punissable ? +Dans une premier temps, nous argumenterons que nous avons besoin d'avoir agi librement pour être punissable. Ensuite, nous verrons que nous sommes toujours libre et que nous sommes toujours responsables de nos actions. Finalement, nous nous demanderons si nous sommes vraiment punissable. + +1) Oui, besoin d'avoir agi librement + 1. Punir une personne manipulée ne permet pas de prévenir les mauvaises conséquences futures -> ne permet pas de prévenir le mal, donc ne permet pas de garantir le bonheur collectif (Bentham, _Rationale of Judicial Evidence, Specially Applied to English Practice_) + 2. Punir une personne qui n'a pas agi librement, c'est créer une disproportion incitant à manipuler pour commettre des actes illégaux, donc c'est risqué (Beccaria, _Des délits et des peines_) + 3. ... +2) Nous sommes toujours libres et responsables de nos actions + 1. On ne peut pas nier la responsabilité de nos actions (Sartre, _L'Existentialisme est un humanisme_) + 2. Nier sa volonté, c'est dénier son statut d'être raisonnable ayant choisi de faire le mal (Hegel, _Principes de la philosophie du droit_) + 3. Dans tous les cas, un meurtrier reste un meurtrier et il doit être puni pour ça (Kant, _Doctrine du droit_) \ No newline at end of file diff --git "a/semestre 3/structures des donn\303\251es/10- Ensemble, partition, file de priorit\303\251 fusionnable.md" "b/semestre 3/structures des donn\303\251es/10- Ensemble, partition, file de priorit\303\251 fusionnable.md" new file mode 100644 index 0000000..32e9a16 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/10- Ensemble, partition, file de priorit\303\251 fusionnable.md" @@ -0,0 +1,21 @@ +--- +tags: + - sorbonne + - informatique + - structure-des-données +semestre: 3 +--- +## Ensemble +Opérations sur les ensembles : +- insertion +- suppression +- vérification +- union +- intersection + +On utilise une hash table sans valeur pour représenter un ensemble non ordonnée +|> permet d'être en $O(1)$ sur la majorité des opérations, l'union est en $O(n)$ et l'intersection en $O(n_1+n_2)$ +|> besoin de réimplémenter la hash table pour enlever la valeur + +On peut utiliser des AVL si on cherche à avoir un ordre +|> plus lent que la hash table (on est 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 d544129..78ef0c9 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" @@ -50,10 +50,73 @@ Lors de la création d'un nœud, on a besoin de calculer la hauteur Insertion/suppression comme dans un ABR |> par contre, si ça déséquilibre, on corrige -|> pour corriger, on utilise des rotations *voir le diapo* +|> pour corriger, on utilise des rotations -> on ne perd pas en complexité, tout reste en $O(h) = O(\log n)$ -*voir le diapo pour le principe précis d'insertion / suppression* +```mermaid +flowchart TB + r --> g + r --> D + g --> U + g --> V +``` +rotation vers la droite -> +```mermaid +flowchart TB + g --> U + g --> r + r --> V + r --> D +``` +(rotation vers la gauche est dans l'autre sens) + +```c title="rotations" +AVL* rotDroite(AVL* racine) { + AVL* r = racine; + AVL* g = r->fg; // fils gauche + AVL* v = g->fd; // fils droit + g->fd = r; + r->fg = v; + majHauteur(r); + majHauteur(g); + return g; +} + +AVL* rotGauche(AVL* racine) { + AVL* g = racine; + AVL* r = g->fg; // fils gauche + AVL* v = r->fd; // fils droit + g->fd = v; + r->fg = r; + majHauteur(r); + majHauteur(g); + return g; +} +``` + +**Insertion** +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$ + 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$ + 2. on fait une rotation à gauche de $A$ +6. On a fini le traitement + +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. +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)$ ## Tableau associatif Les AVL peuvent être pertinent pour les tableaux associatifs 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 621b21e..658c4e1 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" @@ -5,7 +5,6 @@ tags: - structure-des-données semestre: 3 --- - Problème de l'AVL |> besoin de faire des rotations, ce qui transforme tout le graphe |> concurrence impossible, change beaucoup en mémoire -> est très morcelé (donc défaut de page) -- cgit v1.2.3