diff options
| author | Anhgelus Morhtuuzh <william@herges.fr> | 2025-09-19 12:16:41 +0200 |
|---|---|---|
| committer | Anhgelus Morhtuuzh <william@herges.fr> | 2025-09-19 12:16:41 +0200 |
| commit | 5a08a4e1e055a0a702a54cfa867d7fdebf2c1ad7 (patch) | |
| tree | 470e9aeb90b79f61beaab352fa0e394b9e76b11f | |
| parent | cac7f3e868e98281f9f2b841101b09f02cf664fd (diff) | |
Cours du 15 au 19 septembre
37 files changed, 1634 insertions, 6 deletions
diff --git a/Informatique.base b/Informatique.base new file mode 100644 index 0000000..78be862 --- /dev/null +++ b/Informatique.base @@ -0,0 +1,19 @@ +formulas: + Untitled: "" +views: + - type: table + name: Table + filters: + and: + - file.tags.contains("sorbonne") + - file.tags.contains("informatique") + order: + - file.name + - tags + - Semestre + sort: + - property: file.folder + direction: ASC + columnSize: + file.name: 284 + note.tags: 445 diff --git a/Philosophie.base b/Philosophie.base new file mode 100644 index 0000000..e0c3f93 --- /dev/null +++ b/Philosophie.base @@ -0,0 +1,18 @@ +views: + - type: table + name: Table + filters: + and: + - file.tags.contains("sorbonne") + - file.tags.contains("philosophie") + order: + - file.name + - tags + - Semestre + sort: + - property: file.folder + direction: ASC + columnSize: + file.name: 284 + note.tags: 445 + imageFit: "" diff --git a/semestre 3/architecture des ordinateurs/.gitignore b/semestre 3/architecture des ordinateurs/.gitignore new file mode 100644 index 0000000..a136337 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/.gitignore @@ -0,0 +1 @@ +*.pdf diff --git a/semestre 3/architecture des ordinateurs/1- Représentation de l'information.md b/semestre 3/architecture des ordinateurs/1- Représentation de l'information.md index ee2a51c..8ef0fc2 100644 --- a/semestre 3/architecture des ordinateurs/1- Représentation de l'information.md +++ b/semestre 3/architecture des ordinateurs/1- Représentation de l'information.md @@ -135,6 +135,9 @@ Le codage est la correspondance entre le représentation externe de l'informatio |> c'est comment on souhaite utiliser l'information qui définit quel codage on utilise ! -> est ce qui définit les grandes classes de processeur (Intel, ARM, RISC...) +> [!NOTE] Les bases $B$ sont toujours strictement supérieures à 1 ! +> Sinon, on ne peut représenter que $0$ + Tout entier naturel $N$ peut être exprimé comme une somme de multiples de puissance de la base $B$ |> $N = \sum_{i}a_iB^i$ avec $\forall i, a_i < B$ -> permet de convertir une notation dans la base $B$ vers $N$ |> notation condensée est $a_{n-1}\ldots a_0$ @@ -161,8 +164,7 @@ L'hexadécimal (de 0 à F) permet de compacter le binaire > [!danger] Interprétation > Le codage ne permet toujours pas d'interpréter les données brutes ! -## Entiers -### Entiers naturels +## Entiers naturels Comme les mots sont de taille bornée, il n'est pas possible de tout représenter Sur $p$ symboles en base $B$, on peut représenter tous les entiers dans $[0,B^p-1]$ @@ -248,10 +250,13 @@ Les additions / soustractions sont triviales Attention à l'overflow ! |> arrive quand on dépasse la taille du bit -|> est détectable à l'aide de la retenu -> revoir le moodle pour ça +|> est détectable à l'aide de la toute dernière retenu -> si elle est présente, on dépasse ! +|> la retenu est ignorée quand on dépasse -> est de l'arithmétique modulaire sur $2^n$ -Les décalages servent à multiplier / diviser (voir le diapo) -### Entiers relatifs +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})$ +## Entiers relatifs On les appelle les nombre entiers signés La représentation classique en signe/module (i.e. un bit pour le signe, le reste pour le module) @@ -265,6 +270,10 @@ où $(k_i)$ sont les bits représentés -> s'appelle représentation des entiers relatifs en complément à deux |> avec $n$ bits on peut donc représenter $[2^{n-1},2^{n-1}-1]$ +Exemples : +- $-1$ = `0b111` +- 1 = `0b001` + Pour prendre l'opposer, on prend son complémentaire et on lui ajoute 1 |> est appelé le complément à deux |> le complémentaire de `0b1001` est `0b0110` @@ -276,4 +285,69 @@ $$ = \mathrm{0b}1\ldots1 = -1 $$ Donc, on a que $\bar N$ doit être décalé de 1, d'où le plus 1 |> cela est dû au fait que l'intervalle ne soit pas symétrique -Voir le moodle pour la suite +Pour étendre un mot relatif de $p$ bits à $n$ bits ($n > p$), on doit : +- ne pas toucher aux $p$ bits +- on recopie le $p-1$ bits (bit de poids fort) sur tous les bits "vides" + +Exemples : +- `0b01` devient `0b0001` +- `0b10` devient `0b1110` + +**Preuve :** +$$ N_p = -a_{p-1}2^{p-1}+\sum^{p-2}_{i=0}a_i2^i $$ +$$ N_{p+1} -a_{p-1}2^p+a_{p-1}2^{p-1}+\sum^{p-2}_{i=0}a_i2^i = a_{p-1}(-2^p+2^{p-1})+\sum^{p-2}_{i=0}a_i2^i $$ +$$ N_{p+1} = -a_{p-1}2^{p-1}+\sum^{p-2}_{i=0}a_i2^i = N_p $$ +car $-2^p + 2^{p-1} = -2^{p-1}$. + +L'addition fonctionne de la même manière que pour les entiers naturels +La soustraction est l'addition de l'opposé + +Pour détecter le débordement sur entier relatif, on regarde les deux dernières retenues +|> si $C_{out,n-1}$ est différent de $C_{out,n-2}$, alors il y a un débordement + +Exemples : +- `0b0110` + `0b0011` = `0b1001` avec $C_{out,n-1} = 0$ et $C_{out,n-2} = 1$, donc débordement en relatif ! (besoin de poser le calcul pour s'en rendre compte) +- `Ob110` + `0b1011` = `0b1001` avec $C_{out,n-1} = C_{out,n-2} = 1$, donc pas de débordement en relatif ! +## Chaînes de caractères +Elles sont majoritairement codées à l'aide de l'ASCII et de l'UTF-8 +|> ASCII est le plus vieux + +ASCII n'est que sur 7 bits (et non sur 8) +|> le bit de poids fort vaut toujours 0 +|> est représenté dans un tableau à double entrée -> colonne = quartet de poids faible, ligne = quartet de poids fort +|> `0x0A` en ASCII est l'équivalent de `LF`et `0x0D` est le `CR` +-> besoin d'étendre le code ASCII pour représenter les autres tables +|> le bit de poids fort sert à ça, mais c'est peu pratique car n'est pas universel + +Une chaîne de caractère est une succession de caractère se terminant par `\0` qui est `0x00` en ASCII +-> **ne pas oublier le `\0` à la fin** + +> [!warning] `"123"` $\neq 123_d$ +## Rationnels +Un rationnel est $\frac ab$ où $a\in\mathbb{Z}$ et $b\in\mathbb{Z}^*$ +|> contient une partie entière et une partie fractionnaire -> est le développement décimale + +Pour représenter d'une manière exacte un rationnel dans une base $B$, on fait : +$$ \sum^{\infty}_{i=-\infty}a_iB^i $$ +Les $(a_i)$ sont les coefficients dans la base $B$. +|> on n'est pas obligé de mettre les 0 non significatifs +**Cette représentation n'est pas bornée** + +La partie entière est $(a_i)_{i\in\mathbb{N}}$ +La partie fractionnaire est $(a_i)_{i\in\mathbb{Z}^*_-}$ + +Si $a>0$ et $a,b$ premier entre eux, alors $a/b$ est unique +|> son développement décimal est toujours fini ou infini périodique +|> est vrai dans toutes les bases $B$ + +Voir le moodle pour la méthode par multiplications successives + +Deux manières de représenter : virgule fixe et virgule flottante + +Voir le moodle pour le codage en virgule fixe + +Virgule fixe est très simple à utiliser : il suffit de rajouter un facteur lors des opérations +|> les opérations fonctionnent pareilles que pour les autres représentations +|> les détections de l'overflow fonctionnent aussi + +Voir le moodle pour la représentation en virgule flottante
\ No newline at end of file diff --git a/semestre 3/architecture des ordinateurs/td/25-09-17.md b/semestre 3/architecture des ordinateurs/td/25-09-17.md new file mode 100644 index 0000000..cf81253 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/td/25-09-17.md @@ -0,0 +1,70 @@ +--- +tags: + - sorbonne + - informatique + - architecture-des-ordinateurs + - td +semestre: 3 +--- +$127_d$ prend 7 bits +$32_d$ prend 6 bits (car le nombre max dans $n$ bits est $2^n-1$ !) + +Un mot hexa de taille $n$ permet de coder $16^n$ valeurs, soit toutes les valeurs entières dans $[0;16^n-1]$ + +| Mot binaire de 8 bits | Décimal | Mot hexa de 8 bits | +| --------------------- | ------- | ------------------ | +| `0b0000 1010` | 10 | `0x0A` | +| `0b0000 0010` | 2 | `0x02` | +| `0b0001 0000` | 16 | `0x10` | +| `0b0011 1001` | 57 | `0x3B` | +| `0b1000 0001` | 127 | `0x81` | +| `0b0001 0111` | 23 | `0x17` | +| `0b0101 1011` | 91 | `0x5B` | +| `0b0010 1001` | 41 | `0x29` | +| `0b1010 1010` | 170 | `0xAA` | +$5B_h+17_h = 72_h$ -> 7 bits +$71_h+B5_h = 126_h$ -> 9 bits + +`0x2B` + `0x95` = `0xC0` -> pas de dépassement en interprétation « entier naturel » +`0xC8` + `0x6D` = `0x35` -> dépassement en interprétation « entier naturel » +`0x8B57` + `0xA34F` = `0x2EA6` -> dépassement en interprétation « entier naturel » + +`0b1001 0011` - `0b1010 0011` = `0b1111 0000` -> dépassement en interprétation « entier naturel » +`0b1100 1111` - `0b1011 0011` = `0b0001 1100` -> pas de dépassement en interprétation « entier naturel » + +`M1 & M2` = `0b1000` +`M1 | M2` = `0b1101` +`~M1` = `0b0110` +`M1 ^ M2` = `0b0101` + +`M3 & 0x0000 FF00` +`M3 ^ M3 = 0x0000 0000` +`M3 ^ 0x0000 00FF` -> permet d'inverser les bits 0 à 7 (i.e. les 8 premiers) + +`M7` = `0b01010011` +`M7 << 1` = `0b10100110` +`M7 << 2`= `0b01001100` +`M7 >> 4`= `0b00000101` + +`<<` réduit le nombre entier naturel et `>>` l'augmente ! + +| Base 16 | Signe | Base 2 | Opposé base 2 | Opposé base 16 | +| -------- | ----- | ----------------------- | ----------------------- | -------------- | +| `0x0B24` | + | `0b0000 1011 0010 0100` | `Ob0111 0100 1101 1100` | `0x74DC` | +| `0xABCD` | - | `0b1010 1011 1100 1101` | `0b0101 0100 0011 0011` | `0x5433` | +| `0xFFFF` | - | `0b1111 1111 1111 1111` | `Ob0000 0000 0000 0001` | `0x0001` | +`0b01101001` + `0b10000000` = `0b11101001` +|> est valide pour des naturels (pas de retenu sortante) +|> est valide pour des relatifs (les deux dernières retenues sont identiques) + +`0b0110` + `0b0100` est valide en naturel, mais pas en relatif + +`127 - 128 = -1` -> pas de dépassement +`120 - (- 150) = 270 > 127` -> dépassement de capacité +`-64 + 127 + 1 = 64` -> pas de dépassement de capacité +|> on n'aurait pas pu réaliser `-64 + 128` directement car 128 ne rentre pas sur 8 bits +|> si on avait fait `opposer(64 - 128)`, on aurait pu le faire + +`0xFF` sur 32 bits, c'est `0xFFFFFFFF` +|> sa valeur en décimal (relatif en complément à 2), c'est $-1_d$ +|> si c'est un naturel, c'est plus du tout la même chose ! diff --git a/semestre 3/histoire philosophie médiévale/0- Introduction.md b/semestre 3/histoire philosophie médiévale/0- Introduction.md new file mode 100644 index 0000000..6c99411 --- /dev/null +++ b/semestre 3/histoire philosophie médiévale/0- Introduction.md @@ -0,0 +1,44 @@ +--- +tags: + - sorbonne + - philosophie + - histoire-philosophie-médiévale +semestre: 3 +--- +Examen écrit en janvier est l'explication d'un texte +|> peut être dans la brochure (mais pas obligatoire) +## Objet du cours et enjeux +Introduction à la philosophie du moyen-âge latin +|> parle légèrement de l'antiquité et un peu d'arabe + +Point de départ est le travail de l'historien Richard Popkin +|> rôle central du scepticisme de Sextus Empiricus dans la naissance de la modernité intellectuelle +|> la redécouverte de cela est une crise pyrrhonienne +|> « pyrrhonisme est la source la plus importante de la pensée moderne » (Pierre Bayle) +|> affrontement de la crise sceptique et l'effort pour la dépasser est le travail de la modernité + +Scepticisme est un discours critique du dogmatisme (prétention à constituer les connaissances) +|> défiance fondamentale envers les sens et la raison -> doute radical +|> impossible de trouver un critère de vérité rationnellement incontestable + +Qu'est-ce qui mène à cette crise ? +|> faut-il dire que le problème sceptique est-il purement étranger au Moyen-Âge ? -> ils ne se réclament pas du scepticisme +|> Moyen-Âge a souvent été perçu comme un ère optimiste +|> réévaluation du Moyen-Âge comme sceptique, n'est-ce pas ce qui conduit au XVIIe siècle ? (avec Descartes par exemple) + +Grellard explique qu'il n'y a pas de sceptique au Moyen-Âge +|> n'existe pas d'écoles sceptiques +|> mais il y a un *problème* sceptique +|> il y a usage médiéval du scepticisme +-> défi pour la théorie de la connaissance + +Moyen-Âge utilise le scepticisme comme point de départ de toute épistémologie +|> est totalement ce que fait Descartes +-> est l'objet de ce cours + +Enjeux : +- que puis-je savoir ? -> peut-on distinguer vérité et croyance ? +- le doute sceptique est-il viable ? +- fondement de la métaphysique de l'optimisme épistémologique médiéval +- quel statut donner aux textes théologiques ? -> souvent, les philosophes sont des scolastiques +- quel statut donner aux sources antiques ?
\ No newline at end of file diff --git a/semestre 3/logique et notions formelles/1- Introduction.md b/semestre 3/logique et notions formelles/1- Introduction.md new file mode 100644 index 0000000..ccd40bd --- /dev/null +++ b/semestre 3/logique et notions formelles/1- Introduction.md @@ -0,0 +1,93 @@ +--- +tags: + - philosophie + - sorbonne + - logique-notions-formelles +Semestre: 3 +--- +Cherche à obtenir des compétences de logiques formelles +|> manipulation d'objets formelles -> les TD servent à résoudre les exos typiques +|> présente des notions ou idées spécialisées qui sont utilisées en philosophie contemporaine + +Sous-domaines du domaine formelle : +- logique +- ensembles +- probabilités + +Bibliographie : +- Lepage, _Éléments de logique contemporaine_, Les Presses de l'Université de Montréal +- Papineau, _Philosophical devices : Proofs, probabilites, possibilities and sets_, Oxford University Press +- Wagner, _Logique et philosophie. Manuel d'introduction pour les étudiants du supérieur_, Ellipses +## Histoire +Durant l'antiquité, ils théorisent les paradoxes, les propositions, syllogismes et les connecteurs logiques +|> distinction entre les types de phrases (proposition / syllogisme, universelle / particulière) provient d'Aristote + +Kant pense que les mathématiques ne sont pas indépendantes de l'expérience mais n'est pas totalement dépendante de l'expérience +|> est entre le rationalisme de Leibniz et l'empirisme de Mills +-> passe à un nouveau rationalisme : le logicisme + +Frege propose de réduire l'arithmétique à la logique +|> construit une langue auxiliaire pour exprimer les rapports entre les propositions -> est l'idéographie (_Begriffsschrift_) (cf Frege, _Idéographie_) +|> continue dans _Fondements de l'arithmétique_ +|> termine avec _Lois fondamentales de l'arithmétique_ +-> mène au paradoxe de Russell + +> [!NOTE] Paradoxes en logique +> Ils ont souvent été les moteurs du développement de la logique, comme le paradoxe du menteur, de Russell ou le théorème d'incomplétude de Gödel +> +> Quine, _Les voies du paradoxe_ -> est une bonne introduction aux paradoxes +> |> est accessible +### La logique comme branche des mathématiques +Effondrement du système de Frege mènent les mathématiciens à penser la logique +|> souhaitent à sauver le système de Frege +|> théorie des types (Russell) +|> théorie des ensembles (Zermelo) +|> logique du premier ordre (Peano) + +D'autres cherchent aux propriétés des systèmes logiques pour comprendre comment ça marche +|> théorie de la calculabilité +|> théorie de la démonstration +|> théorie des modèles +### La logique comme théorie du raisonnement +Développement des théories formelles et normatives du raisonnement +|> est de la logique en un sens large + +Ces théories permettent de prendre en charge des raisonnements de complexité variée : +- raisonnement certain -> logique « classique » +- raisonnement incertain -> logique inductive, théorie des probabilités +- raisonnement pratique -> théorie de la décision +- raisonnement dans des situations qui impliquent plusieurs sujets -> théorie des jeux, théorie de l'agrégation des jugements +### La logique comme toolbox +Permet de comprendre les relations entre les propositions en jeu + +Permet d'analyser formellement des concepts pour clarifier des débats philosophiques +|> philo du langage, théorie de la connaissance, philo des sciences, métaphysique + +**Ce cours ne choisit pas quelle conception est valide** +|> on va commencer en pensant que c'est une théorie normative du raisonnement certain +-> est dans la lignée de la [[0- Présentation & Introduction|pensée critique]] +## Argument, validité +Argument est constitué de prémisses et d'une conclusion reliées par des expressions +|> prémisses et conclusions sont des énoncés, i.e. elles peuvent être vraies ou fausses + +> [!warning] Tous les arguments ne se valent pas +> Les [[3- Charge de la preuve & sophismes|sophismes]] sont des arguments ! + +Validité ici est la *validité déductive* et non inductive + +Un argument est dit correct si les prémisses sont vraies et si l'argument est correct + +Il existe un lien entre validité et vérité +|> validité dépend pourtant du rapport entre prémisses et conclusion et non de la valeur de vérité des énoncés + +Les arguments valides permettent de construire d'autres arguments en utilisant le même schema +|> validité est préserver par la substitution +-> ⚠ il faut bien tout substituer correctement + +Forme logique ne contient pas de termes sur un sujet spécifique +|> généralise les arguments, e.g. +>Si $\phi$ alors $\psi$. On a $\phi$ donc $\psi$. + +**Un argument est valide si, et seulement si, sa forme logique est valide** + +Pour montrer qu'un argument n'est pas valide, on montre que sa forme logique n'est pas valide
\ No newline at end of file diff --git a/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md b/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md index b0066aa..8d7ceec 100644 --- a/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md +++ b/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md @@ -125,3 +125,123 @@ Une partition de $E$ est une famille $(A_i)_{i\in I}$ de parties de $E$ telle qu - $E=\bigcup_{i\in I} A_i$ > [!warning] Une partition de $E$ n'est pas unique dans le cas générale ! +## Relation +**Définition** +Relation binaire $R$ d'un ensemble $E$ vers $F$ est un sous-ensemble de $E\times F$, i.e. +$$ R\subseteq E\times F $$ +On peut la noter $(x,y)\in R$, $x R y$, $R(x,y)$. +Lorsque $E=F$, on dit que $R$ est une relation binaire sur $E$. + +Exemple : +- $\mathrm{Id}_E$ est la relation identité de $E$ est une relation binaire sur $E$ telle que $\{(e,e)|e\in E\}$ +- $\mathrm{Id}_{\mathbb{N}} = \{(n,n)|n\in\mathbb{N}\}$ +- $\leqslant$ sur $\mathbb{N}$ est aussi une relation binaire : $\{(n_1,n_2)\in\mathbb{N}^2|n_1\leqslant n_2\}$ +- $<$ sur $\mathbb{N}$ est aussi une relation binaire (elle est incluse dans $\leqslant$) + +> [!NOTE] Opérations sur les relations +> Comme une relation est un ensemble, on peut appliquer les opérations ensemblistes dessus 🎉 + +**Définition** +Relation $n$-aire est un sous-ensemble du produit cartésien $E_1\times\ldots\times E_n$ + +**Définition** +Une relation unaire est un sous-ensemble d'un ensemble $E$. + +Définir par compréhension permet d'énoncer la propriété caractéristique de l'ensemble +|> on peut avoir une même relation pour des propriétés caractéristiques différentes +Définir par extension permet de lister les éléments + +**Définition** +La relation inverse $R^{-1}$ d'une relation $R\subseteq E\times F$ est la relation de $F$ vers $E$ contenant tous les couples $(x,y)$ tels que $(y,x)\in R$, i.e. +$$ R^{-1} = \{(x,y)\in F\times E|(y,x)\in R\} $$ + +**Définition** +Un produit de relation est quand on applique plusieurs relations à la suite. + +Le produit de $R_1\subseteq E\times F$ et de $R_2\subseteq F\times G$ est définie par : +$$ R_1R_2 = \left\{(x,y)\in E\times G\quad|\quad\exists z, (x,z)\in R_1\quad\land\quad(z,y)\in R_2\right\} $$ -> revoir le cours pour cette expression, ça me semble chelou +On la note $R_1\circ R_2$ ou $R_1\cdot R_2$. +```mermaid +flowchart LR + A -- R1⋅R2 ---C + A-- R1 ---B + B-- R2 ---C +``` + +Par exemple, on peut définir $<$ comme $S\cdot\leqslant$ où $S$ est la relation successeur (i.e. $S=\{(x,y)|x+1=y\}$) + +> [!warning] Commutativité +> Le produit de relation n'est pas commutatif + +> [!warning] $R\cdot R^{-1}\neq\mathrm{Id}_E$ +> De même dans l'autre sens + +**Propriétés** +$\varnothing$ est un élément est absorbant des relations : $R\cdot\varnothing = \varnothing\cdot R = R$ +Le produit est associatif : $R_1\cdot(R_2\cdot R_3) = (R_1\cdot R_2)\cdot R_3$ +$\mathrm{Id}$ est l'élément neutre : $R\cdot\mathrm{Id}_F = \mathrm{Id}_ER=R$ (si $R$ est dans $E\times F$) +|> ⚠ faire bien attention à la modification de l'identité en fonction qu'on soit à droite ou à gauche + +**Notations** +Si $R$ est une relation sur $E$, on note : +$$ R^n = \underbrace{R\ldots R}_n = \left\{\begin{matrix} + \mathrm{Id}_E&\text{si}&n=0\\ + R\cdot R^{n-1}&\text{sinon} +\end{matrix}\right. $$ + +***Revoir les diapos 23 à 29*** + +**Définition** +Une relation est dite d'équivalence si, et seulement si, elle est : +- réflexive +- symétrique +- transitive + +Une relation est dite d'ordre si, et seulement si, elle est : +- réflexive +- anti-symétrique +- transitive + +Par exemple : +- $\equiv$ (congruence) est une relation d'équivalence +- $\leqslant$ est une relation d'ordre +- $<$ n'est pas une relation d'ordre car elle n'est pas anti-symétrique ! + +**Définition** +Soit $R$ une relation d'équivalence sur $E$. +La classe d'équivalence d'un élément $e\in E$ pour $R$ est noté $[e]_R$ et : +$$ [e]_R = \{e'\in E|(e,e')\in R\} $$ +Remarque : $e\in[e]_R$ car $R$ est réflexive + +**Définition** +On note $E_{/R}$ l'ensemble des quotients de $E$ par $R$ +***J'AI PAS EU LE TEMPS DE NOTER (diapo 31)*** +## Fonctions +**Définition** +Une relation de $E$ vers $F$ est dite déterministe (ou fonctionnelle) si, et seulement si, tout élément de $E$ est en relation avec au plus un élément de $F$, i.e. +$$ \forall e\in E,\quad\forall(e_1,e_2)\in F^2,\quad(e,e_1)\in R\quad\land\quad(e,e_2)\in R \implies e_1=e_2 $$ + +Exemples : +- $S$ est fonctionnelle +- $S^{-1}$ l'est aussi +- $\leqslant$ ne l'est pas par contre + +**Proposition** +Une relation déterministe est une fonction $f$. + +Si $f$ n'est pas définie pour tout l'ensemble de départ, on dit qu'elle est partielle. + +Preuves : +- relation déterministe ne donne qu'une unique image + +**Définition** +Une relation $R$ de $E$ vers $F$ est dite totale à gauche si, et seulement si, chaque élément de $E$ est en relation avec au moins un élément de $F$ : +$$ \forall e_1\in E,\quad\exists e_2\in F,\quad (e_1,e_2)\in R $$ + +**Définition** +Une application est une relation déterministe et totale à gauche, on la note : +$$ f : E\to F $$ +i.e. tout élément de $E$ possède une (unique) image. +On dit parfois qu'elle est une fonction totale. + +***Voir diapo 36 à 45 car j'ai pas le temps de noter***
\ No newline at end of file diff --git a/semestre 3/mathématiques discrètes/td/.gitignore b/semestre 3/mathématiques discrètes/td/.gitignore new file mode 100644 index 0000000..c5d2f98 --- /dev/null +++ b/semestre 3/mathématiques discrètes/td/.gitignore @@ -0,0 +1,316 @@ +# Created by https://www.toptal.com/developers/gitignore/api/latex +# Edit at https://www.toptal.com/developers/gitignore?templates=latex + +### LaTeX ### +## Core latex/pdflatex auxiliary files: +*.aux +*.lof +*.log +*.lot +*.fls +*.out +*.toc +*.fmt +*.fot +*.cb +*.cb2 +.*.lb + +## Intermediate documents: +*.dvi +*.xdv +*-converted-to.* +# these rules might exclude image files for figures etc. +# *.ps +# *.eps +# *.pdf + +## Generated if empty string is given at "Please type another file name for output:" +.pdf + +## Bibliography auxiliary files (bibtex/biblatex/biber): +*.bbl +*.bcf +*.blg +*-blx.aux +*-blx.bib +*.run.xml + +## Build tool auxiliary files: +*.fdb_latexmk +*.synctex +*.synctex(busy) +*.synctex.gz +*.synctex.gz(busy) +*.pdfsync + +## Build tool directories for auxiliary files +# latexrun +latex.out/ + +## Auxiliary and intermediate files from other packages: +# algorithms +*.alg +*.loa + +# achemso +acs-*.bib + +# amsthm +*.thm + +# beamer +*.nav +*.pre +*.snm +*.vrb + +# changes +*.soc + +# comment +*.cut + +# cprotect +*.cpt + +# elsarticle (documentclass of Elsevier journals) +*.spl + +# endnotes +*.ent + +# fixme +*.lox + +# feynmf/feynmp +*.mf +*.mp +*.t[1-9] +*.t[1-9][0-9] +*.tfm + +#(r)(e)ledmac/(r)(e)ledpar +*.end +*.?end +*.[1-9] +*.[1-9][0-9] +*.[1-9][0-9][0-9] +*.[1-9]R +*.[1-9][0-9]R +*.[1-9][0-9][0-9]R +*.eledsec[1-9] +*.eledsec[1-9]R +*.eledsec[1-9][0-9] +*.eledsec[1-9][0-9]R +*.eledsec[1-9][0-9][0-9] +*.eledsec[1-9][0-9][0-9]R + +# glossaries +*.acn +*.acr +*.glg +*.glo +*.gls +*.glsdefs +*.lzo +*.lzs +*.slg +*.slo +*.sls + +# uncomment this for glossaries-extra (will ignore makeindex's style files!) +# *.ist + +# gnuplot +*.gnuplot +*.table + +# gnuplottex +*-gnuplottex-* + +# gregoriotex +*.gaux +*.glog +*.gtex + +# htlatex +*.4ct +*.4tc +*.idv +*.lg +*.trc +*.xref + +# hyperref +*.brf + +# knitr +*-concordance.tex +# TODO Uncomment the next line if you use knitr and want to ignore its generated tikz files +# *.tikz +*-tikzDictionary + +# listings +*.lol + +# luatexja-ruby +*.ltjruby + +# makeidx +*.idx +*.ilg +*.ind + +# minitoc +*.maf +*.mlf +*.mlt +*.mtc[0-9]* +*.slf[0-9]* +*.slt[0-9]* +*.stc[0-9]* + +# minted +_minted* +*.pyg + +# morewrites +*.mw + +# newpax +*.newpax + +# nomencl +*.nlg +*.nlo +*.nls + +# pax +*.pax + +# pdfpcnotes +*.pdfpc + +# sagetex +*.sagetex.sage +*.sagetex.py +*.sagetex.scmd + +# scrwfile +*.wrt + +# svg +svg-inkscape/ + +# sympy +*.sout +*.sympy +sympy-plots-for-*.tex/ + +# pdfcomment +*.upa +*.upb + +# pythontex +*.pytxcode +pythontex-files-*/ + +# tcolorbox +*.listing + +# thmtools +*.loe + +# TikZ & PGF +*.dpth +*.md5 +*.auxlock + +# titletoc +*.ptc + +# todonotes +*.tdo + +# vhistory +*.hst +*.ver + +# easy-todo +*.lod + +# xcolor +*.xcp + +# xmpincl +*.xmpi + +# xindy +*.xdy + +# xypic precompiled matrices and outlines +*.xyc +*.xyd + +# endfloat +*.ttt +*.fff + +# Latexian +TSWLatexianTemp* + +## Editors: +# WinEdt +*.bak +*.sav + +# Texpad +.texpadtmp + +# LyX +*.lyx~ + +# Kile +*.backup + +# gummi +.*.swp + +# KBibTeX +*~[0-9]* + +# TeXnicCenter +*.tps + +# auto folder when using emacs and auctex +./auto/* +*.el + +# expex forward references with \gathertags +*-tags.tex + +# standalone packages +*.sta + +# Makeindex log files +*.lpz + +# xwatermark package +*.xwm + +# REVTeX puts footnotes in the bibliography by default, unless the nofootinbib +# option is specified. Footnotes are the stored in a file with suffix Notes.bib. +# Uncomment the next line to have this generated file ignored. +#*Notes.bib + +### LaTeX Patch ### +# LIPIcs / OASIcs +*.vtc + +# glossaries +*.glstex + +# End of https://www.toptal.com/developers/gitignore/api/latex + +TD*.pdf diff --git a/semestre 3/mathématiques discrètes/td/25-09-19.pdf b/semestre 3/mathématiques discrètes/td/25-09-19.pdf Binary files differnew file mode 100644 index 0000000..0e744c5 --- /dev/null +++ b/semestre 3/mathématiques discrètes/td/25-09-19.pdf diff --git a/semestre 3/mathématiques discrètes/td/25-09-19.tex b/semestre 3/mathématiques discrètes/td/25-09-19.tex new file mode 100755 index 0000000..d256e24 --- /dev/null +++ b/semestre 3/mathématiques discrètes/td/25-09-19.tex @@ -0,0 +1,167 @@ +\documentclass[a4paper]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage{textcomp} +\usepackage[french]{babel} +\usepackage{amsmath, amssymb} +\usepackage{amsthm} +\usepackage[svgnames]{xcolor} +\usepackage{thmtools} +\usepackage{lipsum} +\usepackage{framed} +\usepackage{parskip} + +\renewcommand{\familydefault}{\sfdefault} + +\newenvironment{AQT}{{\fontfamily{qbk}\selectfont AQT}} + +\usepackage{titlesec} +\usepackage{LobsterTwo} +\titleformat{\section}{\newpage\LobsterTwo \huge\bfseries}{\thesection.}{1em}{} +\titleformat{\subsection}{\vspace{2em}\LobsterTwo \Large\bfseries}{\thesubsection.}{1em}{} +\titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{} + +\title{TD Maths discrètes} +\author{William Hergès\thanks{Sorbonne Université}} + +\begin{document} + \maketitle + \section*{Exercice 1} + \begin{enumerate} + \item $S_1\times S_1 = \{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)\}$ + \item Pour $S=S_1$, on a~: + $$ \mathcal{P}(S) = \{\varnothing, \{0\}, \{1\}, \{2\}, \{0,1\},\{0,2\},\{1,2\},S\} $$ + Pour $S=S_2$, on a~: + $$ \mathcal{P}(S) = \{\varnothing, \{1\}, \{\{1,4\}\}, S\} $$ + Pour $S=S_3$, on a~: + $$ \mathcal{P}(S) = \{\varnothing, \{\varnothing\},\{1\}, S\} $$ + \item Les partitions possibles de $\{1,2,3\}$ sont~: + $$ \{\{1\},\{2\},\{3\}\} $$ + $$ \{\{1\},\{2, 3\}\} $$ + $$ \{\{2\},\{1, 3\}\} $$ + $$ \{\{1\},\{1, 2\}\} $$ + $$ \{\{1, 2, 3\}\} $$ + \end{enumerate} + \section*{Exercice 2} + \subsection*{Question 1} + Montrons que $x\in A\cap\overline{A \cap B}$ est dans $A\cap\bar B$. + + Soit $x$ dans $A\cap\overline{A\cap B}$, alors $x$ est dans $A$ et $\overline{A\cap B}$. + Comme $x$ n'est pas dans $\bar A$ (il est dans $A$), il est forcément dans $\bar B$, ainsi on obtient que $x$ + est bien dans $A$ et $\bar B$. + Alors, $x\in A\cap\bar B$. + + Montrons que $x\in A\cap\bar B$ est dans $A\cap\overline{A\cap B}$. + + Soit $x$ dans $A\cap\bar B$, alors $x$ est dans $A$ et $\bar B$. + D'après la loi de De Morgan, on a~: + $$ A\cap\overline{A\cap B} = A\cap(\bar A\cup \bar B) $$ + Or, comme $x$ est dans $A$, il ne peut pas être dans $\bar A$ par définition. + Donc $x$ est forcément dans $\bar B$. + Ainsi, $x\in A\cap\bar B$. + + Par conséquent, $$A\cap\bar B = A\cap\overline{A\cap B}$$ + \subsection*{Question 4} + $$ A\cup B\subseteq A\cup C\quad\land\quad A\cap B\subseteq A\cap C $$ + Soit $x$ dans $B$. + + Si $x$ n'est pas dans $A$, il est dans $C$ (car $A\cup B\subseteq A\cup C$). + + Si $x$ est dans $A$, il est dans $A\cap C$, donc il est aussi dans $C$. + + Alors, $x$ est toujours dans $C$. + Ainsi $B\subseteq C$. + + Pour avoir $B=C$, on a besoin d'avoir $A\cup C\subseteq A\cup B$ en plus. + \subsection*{Question 6} + Si $A=\{0, 1, 3\}$ et $B=\{1, 2\}$, alors + $$ \{3,2\}\in\mathcal{P}(A\cup B) $$ + Pourtant, $$\{3,2\}\not\in \mathcal{P}(A)\cup\mathcal{P}(B)$$ + Donc, $\mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)$ est faux. + + \begin{align*} + & E\subseteq \mathcal{P}(A\cup B) \\ + \iff & E\subseteq A\cup B \\ + \iff & E\subseteq A\cup B \\ + \iff & E\subseteq A \land E\subseteq B \\ + \iff & E\subseteq \mathcal{P}(A) \land E\subseteq \mathcal{P}(B) \\ + \iff & E\subseteq \mathcal{P}(A)\cup\mathcal{P}(B) + \end{align*} + \section*{Exercice 3} + $$ S = \{(a,b,c)\in D^3|c=a+b\} $$ + \section*{Exercice 4} + \subsection*{Question 1} + $R$ n'est pas réflexive, car $R(2,2)$ est faux. + + $R$ est symétrique, car on a $R(1,1)$, $R(2,3)$ et $R(3,2)$. + Elle ne peut donc pas être antisymétrique. + + Elle n'est pas transitive, car on a $R(2,3) \land R(3,2)$ qui n'implique pas $R(2,2)$. + \subsection*{Question 4} + On a~: + $$ (x_1,x_2) \preceq (y_1,y_2) $$ + si, et seulement si, $x_1\leqslant y_1$ et $x_2\leqslant y_2$. + + Une relation d'ordre est une relation réflexive, antisymétrique et transitive. + + $$ (x,y)\preceq (x,y) \iff x\leqslant x \land y \leqslant y $$ + est vraie, donc $\preceq$ est réflexive. + + \begin{align*} + & (x_1,x_2) \preceq (y_1,y_2) \land (y_1,y_2) \preceq (x_1,x_2)\\ + \iff & (x_1 \leqslant y_1 \land x_2\leqslant y_2) \land (y_2 \leqslant x_2 \land y_1\leqslant x_1) + \end{align*} + Alors, on a que $x_1=y_1$ et que $x_2=y_2$, i.e. $(x_1,x_2)=(y_1,y_2)$ dans ce cas. + $\preceq$ est donc antisymétrique. + + \begin{align*} + & (x_1,x_2) \preceq (y_1,y_2) \land (y_1,y_2) \preceq (z_1,z_2)\\ + \iff & (x_1 \leqslant y_1 \land x_2\leqslant y_2) \land (y_2 \leqslant z_2 \land y_1\leqslant z_1) \\ + \iff & (x_1 \leqslant z_1 \land x_2\leqslant z_2) \\ + \iff & (x_1,x_2)\preceq (z_1,z_2) + \end{align*} + Alors, elle est transitive. + Ainsi, il s'agit d'une relation d'ordre. + + Elle n'est pas totale car $(0,1)$ et $(1,0)$ ne sont pas comparables. + \subsection*{Question 5} + Une relation est dite d'ordre si elle est réflexive, symétrique et transitive. + + Soit $\varepsilon$ dans $\mathbb{R}$. + On pose $x = 0$ et $z = 2\varepsilon$. + + On a que $R(x,\varepsilon)$ est vraie (trivial). + On a que $R(\varepsilon, 2\varepsilon$ est vraie (trivial). + On a que $R(x,2\varepsilon)$ est faux, car~: + $$ |0-2\varepsilon| > \varepsilon $$ + + Ainsi, $R$ n'est pas une relation d'ordre. + \section*{Exercice 5} + \subsection*{Question 1} + $$ R = \{ + (1, 3), (1, 5), + (2, 3), (2, 5), + (3, 5), + (4, 5) + \} $$ + $$ R^{-1} = \{ + (3, 1), (5, 1), + (3, 2), (5, 2), + (5, 3), + (5, 4) + \}$$ + $$ R^{-1}.R = \{(3,3), (3, 5), (5,5), (5,3)\} $$ + $$ R.R^{-1} = \{(1,1), (1,2), (1,3), (1,4), (1,5), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)\} $$ + \subsection*{Question 2} + On a~: + $$ R.S = \{(x,z)\in X\times Z | \exists y\in Y, R(x,y)\land S(y,z)\} $$ + Donc~: + $$ (R.S)^{-1} = \{(z,x)\in Z\times X | \exists y\in Y, R(x,y)\land S(y,z)\} $$ + Or~: + \begin{align*} + S^{-1}.R^{-1} &= \{(z,x)\in Z\times X | \exists y\in Y, R(x,y)\land S(y,z)\} \\ + &= (R.S)^{-1} \\ + \end{align*} + (Ici il y a juste une étape cachée qui transforme $R^{-1}(y,x)$ en $R(x,y)$, mais elle est triviale. Idem pour $S$.) +\end{document} diff --git a/semestre 3/mathématiques discrètes/td/template.tex b/semestre 3/mathématiques discrètes/td/template.tex new file mode 100755 index 0000000..23ee891 --- /dev/null +++ b/semestre 3/mathématiques discrètes/td/template.tex @@ -0,0 +1,32 @@ +\documentclass[a4paper]{article} + +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage{textcomp} +\usepackage[french]{babel} +\usepackage{amsmath, amssymb} +\usepackage{amsthm} +\usepackage[svgnames]{xcolor} +\usepackage{thmtools} +\usepackage{lipsum} +\usepackage{framed} +\usepackage{parskip} + +\renewcommand{\familydefault}{\sfdefault} + +\newenvironment{AQT}{{\fontfamily{qbk}\selectfont AQT}} + +\usepackage{titlesec} +\usepackage{LobsterTwo} +\titleformat{\section}{\newpage\LobsterTwo \huge\bfseries}{\thesection.}{1em}{} +\titleformat{\subsection}{\vspace{2em}\LobsterTwo \Large\bfseries}{\thesubsection.}{1em}{} +\titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{} + +\title{Titre} +\author{William Hergès\thanks{CPES Science Henri-IV / PSL}} + +\begin{document} + \maketitle + $0 +\end{document} +endsnippet diff --git a/semestre 3/philosophie générale/0- Introduction.md b/semestre 3/philosophie générale/0- Introduction.md new file mode 100644 index 0000000..c726078 --- /dev/null +++ b/semestre 3/philosophie générale/0- Introduction.md @@ -0,0 +1,69 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-générale +semestre: 3 +--- +## Pourquoi s'intéresser au langage en philosophie ? +Le XXe siècle replace le langage au centre de l'investigation +|> ne possède pas vraiment d'équivalent si on regarde l'histoire de la philosophie + +Deux traditions en philosophie l'ont fait +|> philosophie analytique +|> philosophie continentale + +Philosophie analytique -> _The Linguistic Turn_, Rorty +|> il n'y a jamais eu d'accord sur la méthode -> accepter une méthode est une forme de pétition de principe (on accepte la méthode car on est d'accord avec la philosophie derrière) +|> les méthodes oublient souvent le langage -> elles partent toujours d'une théorie métaphysique +|> ils cherchent de s'intéresser au langage à l'aide de la méthode linguistique (Frege, Wittgenstein, Russell, Carnap et le cercle de Vienne) -> les problèmes philosophiques touchent d'abord au langage +|> cherche à traduire les idées philosophiques dans un langage idéal (logique formelle) +|> on ne peut pas donner des réponses satisfaisantes dans le langage naturel +-> Russell et Wittgenstein, _Tractatus logico-philosophicus_ +|> tous les problèmes métaphysiques dérivent d'une absence de compréhension du langage +|> la métaphysique est donc une entreprise vaine +-> tous les auteurs analytiques souhaitent rejeter la métaphysique +|> critique de _Qu'est-ce que la métaphysique_ de Heidegger : ils trouvent qu'elle ne possède pas de sens logique + +Plus tard, les philosophes analytiques ont créé une métaphysique dite analytique +|> _La métaphysique analytique_ chez Vrin + +Philosophe classique (de Platon à Husserl) +|> défiance envers le langage -> sont contre la confusion du langage +|> il faudrait construire un langage plus parfait pour le remplacer (Descartes) +|> recourir à une analyse sans mot (Berkeley) +|> philosophe aurait un langage plus précis car il définit plus rigoureusement (Spinoza), mais pour Kant c'est impossible car on ne construit pas des concepts +-> on ne peut pas ignorer le langage + +Une autre vision du rôle du langage stipule que la philosophie doit être pensée comme de la poésie +|> la forme doit être liée au fond -> plus la philosophie est poétique, plus elle est vraie +|> ce pov est celui des philosophes romantiques et est la source de l'idéalisme allemand +-> même idée chez Heidegger + +Dans tous les cas, on a besoin du langage pour construire une métaphysique +## Qu'est-ce que le lexique même du langage ? +Mais qu'est-ce que le langage ? + +En Grec, il n'y a pas un unique mot pour parler du langage +|> *muthos* désigne l'acte de parole +|> *epos* désigne la parole en tant qu'acte adressé à qlq'un +|> *logos* n'est que très peu utilisé et ne peut pas se traduire par langage -> est toujours lié aux effets sur l'humain qui l'entend +|> *logos* est langage, langue (unité), parole, énoncés, faculté de calculer, faculté de raisonnement... +|> *glossa* est la langue qu'on entend par langue organe ou système de signe (bref, nos deux significations de langue) + +La définition de l'humain comme animal possédant la raison est une mauvaise traduction d'Aristote +|> on devrait plutôt dire que l'humain est un animal ayant une langue +-> cette ambiguïté provient de *logos* + +En latin, l'idée de langage et de rationalité se sépare + +En français, on a : +Langue = système de signes (code) +Langage = faculté de parler +Parole = l'acte d'utiliser le langage (mise en œuvre du code) +-> trois distinctions + +Dans les langues germaniques, il y en a deux (ici en allemand) : +Rede = parole -> mais peut aussi avoir un sens plus théorique ressemblant à langage +Sprache = langue -> mais peut aussi avoir un sens concret ressemblant à parole +-> deux distinctions diff --git a/semestre 3/philosophie politique/0- Introduction.md b/semestre 3/philosophie politique/0- Introduction.md new file mode 100644 index 0000000..3c11ee5 --- /dev/null +++ b/semestre 3/philosophie politique/0- Introduction.md @@ -0,0 +1,32 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-politique +Semestre: 3 +--- +Permanence en 505 le jeudi de 14h à 16h. +Pas là jeudi 23 octobre. + +Objectifs du cours : +1. dénaturaliser le droit pénal +2. développer vos capacités analytiques et argumentatives +3. allier la compréhension concrète de l'objet et la capacité à l'analyser de manière subtile +4. développer votre aisance à l'oral -> cherche à compenser les khôlles + +Moyens : +1. plan par questions +2. éléments d'histoire du droit, de la sociologie du droit +3. sortie au tribunal +4. exercices variés, au-delà des exercices canoniques + +Bibliographie : +- _Juger en Amérique et en France_, Antoine Garapon et Ioannis Papadopoulos + +Aristote introduit les types de justice +|> relire l'exemplier et prise de note quand il sera à jour + +Proportion géométrique (dans le cas de la justice distributive) chez Aristote = gestion proportionnelle des choses +Proportion arithmétique chez Aristote (dans le cas de la justice corrective) = doit rectifier l'égalité en effaçant l'inégalité + +Le juge pénal, pour Aristote, doit appliquer la proportion arithmétique
\ No newline at end of file diff --git a/semestre 3/philosophie politique/1- Enquêter.md b/semestre 3/philosophie politique/1- Enquêter.md new file mode 100644 index 0000000..30d9e7a --- /dev/null +++ b/semestre 3/philosophie politique/1- Enquêter.md @@ -0,0 +1,29 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-politique +semestre: 3 +--- +## A. Pourquoi enquêter ? +FOUCAULT, « La vérité et les formes juridiques », _Dits et Écrits_ tome II, texte n°139 + +Ça semble évident de chercher le coupable et la vérité +|> ça n'a pas toujours été le cas +-> histoire de l'enquête pénal pour relativiser cette vision + +Pour l'approche traditionnelle, l'histoire se fait sur une ligne et les humains ne sont pas touchés par leur période +Pour Foucault, chaque époque façonne les sujets +|> un type de savoir, un type de pouvoir, un type de subjectivité +|> ce qu'on sait du monde change notre vision de voir le monde + +Les sciences humaines sont une création du XIXe siècle +|> n'existaient pas avant +_Les Mots et les Choses_, Foucault + +Les trois formes de la procédure judiciaire : +1. l'épreuve -> la vérité arrive après avoir demandé à l'accusé de relever un défi (époque romaine, Moyen-Âge avec l'ordalie — jugement de Dieu), l'autorité vérifie uniquement que la procédure est régulière +2. début de l'enquête -> continue avec l'épreuve, mais l'enquête commence avec l'apparition d'un nouveau tiers pour compléter l'épreuve ; elle apparaît suite à une concentration du pouvoir économique et militaire ce qui mène au besoin de contrôler le pouvoir judiciaire => ce n'est pas un processus rationnel + +> [!NOTE] Vérité et procédure judiciaire +> Chaque procédure judiciaire ne donne pas la même vision de la vérité diff --git a/semestre 3/structures des données/1- Notions élémentaires.md b/semestre 3/structures des données/1- Notions élémentaires.md index 06005d8..b8bfffa 100644 --- a/semestre 3/structures des données/1- Notions élémentaires.md +++ b/semestre 3/structures des données/1- Notions élémentaires.md @@ -2,6 +2,7 @@ tags: - sorbonne - informatique + - structure-des-données semestre: 3 --- Comment gérer les structures de données ? diff --git a/semestre 3/structures des données/2- Éléments de base.md b/semestre 3/structures des données/2- Éléments de base.md new file mode 100644 index 0000000..d2178c6 --- /dev/null +++ b/semestre 3/structures des données/2- Éléments de base.md @@ -0,0 +1,111 @@ +--- +tags: + - sorbonne + - informatique + - structure-des-données +semestre: 3 +--- +## Matrices +***Rattraper Matrice*** + +En mémoire, un tableau à deux entrées alloué statiquement est en réalité un tableau à une ligne -> les lignes sont les unes à la suite des autres +|> un tableau à deux entrées est de type `T**` où `T` est le type du pointeur + +Un tableau à double entrée alloué dynamiquement est utile quand c'est trop compliqué d'avoir assez de place pour le mettre d'une manière contiguë +```c title="Allocation dynamique d'un tableau [2][3]" +int **m = (int **) malloc(2*sizeof(int)); +for (int i = 0; i < 2; i++){ + m[i] = (int *) malloc(3*sizeof(int)); +} +``` +Ici, les lignes ne sont pas les unes à la suite des autres + +> [!warning] Allocation dynamique +> Dès qu'on a une allocation dynamique, on ne doit pas oublier de faire un `free` pour libérer la mémoire +> |> on doit avoir un `free` par `malloc`, i.e. un `free` par ligne puis un `free` pour le tableau contenant les tableaux +> +> En cas d'erreur (i.e. `malloc` renvoie `NULL`), on doit tous désallouer +> |> besoin de check après chaque `malloc` et si c'est pas bon, on doit désallouer tout ce qu'on a fait avant +### Complexité des opérations usuelles sur les tableaux +Accéder à un case dans un tableau, se fait en $\mathcal{O}(1)$ en C +La recherche dans un tableau est en $\mathcal{O}(n)$, mais s'il est trié, elle se fait en $\mathcal{O}(\log n)$ +Suppression est en $\mathcal{O}(n)$ +Insertion est en $\mathcal{O}(1)$ si le tableau possède de la place, sinon c'est $\mathcal{O}(n)$ +## Listes +Une liste est une suite finie possédant chacun un élément pointant vers un autre de manière à créer une chaîne linéaire en mémoire +|> quand on parle de liste simplement chaînée (elle possède un lien qu'avec l'élément suivant), on parle de son implémentation +|> une liste doublement chaînée possède un lien avec l'élément suivant et le précédent + +On implémente les listes avec une structure : +```c title="Implémentation standard d'une liste simplement chaînée" +typedef struct cellule{ + int value; + struct cellule *next; +} Cellule; +``` +### Complexité des opérations usuelles sur les listes +Insérer se fait en $\mathcal{O}(1)$ car on insère au début +Le reste est en $\mathcal{O}(n)$ +## Files +Une file est un ensemble de données homogènes fondé sur le principe du « first in, first out » (FIFO) +|> permet d'insérer facilement et d'accéder facilement à la toute fin + +File est doublement chaînée +### Complexité des opérations usuelles sur les files +Enfiler (rajouter un élément au début) et défiler (enlever l'élément de fin) sont en $\mathcal{O}(1)$ +Les autres sont en $\mathcal{O}(n)$ +## Piles +Une pile est un ensemble de données homogènes fondé sur le principe du « last in, first out » (LIFO) +|> permet d'insérer facilement et d'accéder facilement au dernier élément + +Piles peuvent être représentés par des tableaux en C +|> on rajoute les éléments à la fin +### Complexité des opérations usuelles sur les piles +Empiler (rajouter un élément au début) et dépiler (enlever l'élément au début) sont en $\mathcal{O}(1)$ +Les autres sont en $\mathcal{O}(n)$ +## Allocation mémoire +Le stack contient les variables qui ne sont allouées par `malloc` +|> est une pile, d'où son nom en français « pile d'exécution » + +La mémoire n'est libérée que quand la fonction finit de s'exécuter +|> pose problème pour les fonctions récursives + +Une fonction récursive terminale est quand elle s'appelle elle-même à la fin de l'appel +|> permet de limiter les appels récursifs +|> permet d'optimiser la mémoire + +> [!warning] Récursivité terminale +> Une fonction récursive terminale doit bien être de la forme `return fonction()` et non `return expression` (où expression fait appel à la fonction) ! +> Une « mauvaise » fonction récursive n'est pas optimisée + +```c title="Une fonction récursive NON terminale" +int somme(int n){ + if (n < 2){ + return n; + } + return n+somme(n-1); +} +``` + +```c title="Une fonction récursive terminale" +int somme(int n, int s){ + if (n == 0){ + return s; + } + return somme(n-1, s+n); +} +``` + +```elixir title="car c'est plus beau" +def somme(n) do + somme(n, 0) +end + +defp somme(n, a) when n > 0 do + somme(n-1, a+n) +end + +defp somme(0, a) do + a +end +``` diff --git a/semestre 3/structures des données/td/.gitignore b/semestre 3/structures des données/td/.gitignore new file mode 100644 index 0000000..ca1cd41 --- /dev/null +++ b/semestre 3/structures des données/td/.gitignore @@ -0,0 +1,60 @@ +main + +# Created by https://www.toptal.com/developers/gitignore/api/c +# Edit at https://www.toptal.com/developers/gitignore?templates=c + +### C ### +# Prerequisites +*.d + +# Object files +*.o +*.ko +*.obj +*.elf + +# Linker output +*.ilk +*.map +*.exp + +# Precompiled Headers +*.gch +*.pch + +# Libraries +*.lib +*.a +*.la +*.lo + +# Shared objects (inc. Windows DLLs) +*.dll +*.so +*.so.* +*.dylib + +# Executables +*.exe +*.out +*.app +*.i*86 +*.x86_64 +*.hex + +# Debug files +*.dSYM/ +*.su +*.idb +*.pdb + +# Kernel Module Compile Results +*.mod* +*.cmd +.tmp_versions/ +modules.order +Module.symvers +Mkfile.old +dkms.conf + +# End of https://www.toptal.com/developers/gitignore/api/c diff --git a/semestre 3/structures des données/td/td1/exo1.c b/semestre 3/structures des données/td/td1/exo1.c new file mode 100644 index 0000000..669589b --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo1.c @@ -0,0 +1,15 @@ +#include <stdio.h> + +/* factorielle récursive */ +int xy(int n){ + if (n) { + /* warum nicht ? */ + return n*(xy(n-1)); + } else { + return 1; + } +} + +void main(void){ + printf("%d", xy(5)); +} diff --git a/semestre 3/structures des données/td/td1/exo2.c b/semestre 3/structures des données/td/td1/exo2.c new file mode 100644 index 0000000..7b3acf7 --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo2.c @@ -0,0 +1,23 @@ +#include <stdio.h> +#include <stdlib.h> + +/* incremente de 1 la valeur de 'p' */ +/* passer un arg en pointeur permet à une fonction de faire des effets de bord, comme retourner plusieurs valeurs */ +void incrementer(int *p){ + (*p)++; +} + +void main(void){ + int *p; + int i = 1; + + p = &i; + printf("%d\n", *p); + + /* Cette suite de est illogique car on ne connait pas la valeur de 'p' avant l'affectation */ + p = (int *) malloc(sizeof(int)); + incrementer(p); + printf("%d\n", *p); + + free(p); +} diff --git a/semestre 3/structures des données/td/td1/exo3.c b/semestre 3/structures des données/td/td1/exo3.c new file mode 100644 index 0000000..1a790ad --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo3.c @@ -0,0 +1,15 @@ +#include <stdlib.h> + +void main(void){ + /* le cast est très important pour le compilateur et le linter */ + int *t = (int *) malloc(sizeof(int)*5) // car on souhaite un tableau de taille 5 + /* acces à la 4e valeur */ + int four = *(t+3) + free(t) + + /* pour recuperer la taille d'un tableau, on est oblige de la garder qlq part en memoire + * on peut stocker la taille du tableau dans la premiere case (pas une bonne idee) + * on rajoute un caractere de fin (pas une bunne idee non plus, de mon pov en tout cas) + * on construit un struct contenant le tableau et sa taille + */ +} diff --git a/semestre 3/structures des données/td/td1/exo4.md b/semestre 3/structures des données/td/td1/exo4.md new file mode 100644 index 0000000..ea4e5b8 --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo4.md @@ -0,0 +1,17 @@ +--- +tags: + - sorbonne + - informatique + - structure-des-données + - td +Semestre: 3 +--- +Code 1 est en $\Theta (1)$. + +Code 2 est en $\mathcal{O} (n)$ et en $\Omega(1)$. + +Code 3 est en $\mathcal{O} (n\times m)$ et en $\Omega(\min\{n,m\})$ car : +- `equals_tab` renvoie 0 car elle a fait $1$ tours, donc on fait $n$ tours dans `equals_one_line` +- `equals_tab` renvoie 1 car elle a fait $m$ tours, donc on fait $1$ tours dans `equals_one_line` + + diff --git a/semestre 3/structures des données/td/td1/exo5/.gitignore b/semestre 3/structures des données/td/td1/exo5/.gitignore new file mode 100644 index 0000000..ea17491 --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo5/.gitignore @@ -0,0 +1 @@ +prog diff --git a/semestre 3/structures des données/td/td1/exo5/A.c b/semestre 3/structures des données/td/td1/exo5/A.c new file mode 100644 index 0000000..a18d17b --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo5/A.c @@ -0,0 +1,6 @@ +#include "A.h" + +int f(int n){ + /* do some funky stuff */ + return n; +} diff --git a/semestre 3/structures des données/td/td1/exo5/A.h b/semestre 3/structures des données/td/td1/exo5/A.h new file mode 100644 index 0000000..5e5fa02 --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo5/A.h @@ -0,0 +1,7 @@ +#ifndef A_H +#define A_H + +int f(int); + +#endif + diff --git a/semestre 3/structures des données/td/td1/exo5/B.c b/semestre 3/structures des données/td/td1/exo5/B.c new file mode 100644 index 0000000..2fd27ef --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo5/B.c @@ -0,0 +1,6 @@ +#include "B.h" +#include "A.h" + +void g(int p){ + /* do some funky stuff again */ +} diff --git a/semestre 3/structures des données/td/td1/exo5/B.h b/semestre 3/structures des données/td/td1/exo5/B.h new file mode 100644 index 0000000..a863ca7 --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo5/B.h @@ -0,0 +1,7 @@ +#ifndef B_H +#define B_H +#include "A.h" + +void g(int); + +#endif diff --git a/semestre 3/structures des données/td/td1/exo5/Makefile b/semestre 3/structures des données/td/td1/exo5/Makefile new file mode 100644 index 0000000..691f09b --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo5/Makefile @@ -0,0 +1,12 @@ +all: prog.o A.o B.o + gcc -o prog A.o B.o prog.o + +prog.o: prog.c + gcc -c prog.c + +A.o: A.h A.c + gcc -c A.h A.c + +B.o: B.h B.c + gcc -c B.h B.c + diff --git a/semestre 3/structures des données/td/td1/exo5/prog.c b/semestre 3/structures des données/td/td1/exo5/prog.c new file mode 100644 index 0000000..f015ccc --- /dev/null +++ b/semestre 3/structures des données/td/td1/exo5/prog.c @@ -0,0 +1,8 @@ +#include "A.h" +#include "B.h" + +void main(void){ + int n; + n = f(n); + g(n); +} diff --git a/semestre 3/structures des données/tme/.gitignore b/semestre 3/structures des données/tme/.gitignore new file mode 100644 index 0000000..ca1cd41 --- /dev/null +++ b/semestre 3/structures des données/tme/.gitignore @@ -0,0 +1,60 @@ +main + +# Created by https://www.toptal.com/developers/gitignore/api/c +# Edit at https://www.toptal.com/developers/gitignore?templates=c + +### C ### +# Prerequisites +*.d + +# Object files +*.o +*.ko +*.obj +*.elf + +# Linker output +*.ilk +*.map +*.exp + +# Precompiled Headers +*.gch +*.pch + +# Libraries +*.lib +*.a +*.la +*.lo + +# Shared objects (inc. Windows DLLs) +*.dll +*.so +*.so.* +*.dylib + +# Executables +*.exe +*.out +*.app +*.i*86 +*.x86_64 +*.hex + +# Debug files +*.dSYM/ +*.su +*.idb +*.pdb + +# Kernel Module Compile Results +*.mod* +*.cmd +.tmp_versions/ +modules.order +Module.symvers +Mkfile.old +dkms.conf + +# End of https://www.toptal.com/developers/gitignore/api/c diff --git a/semestre 3/structures des données/tme/tme1-2/exo1/tme1_exo1p1.c b/semestre 3/structures des données/tme/tme1-2/exo1/tme1_exo1p1.c new file mode 100644 index 0000000..51b6d92 --- /dev/null +++ b/semestre 3/structures des données/tme/tme1-2/exo1/tme1_exo1p1.c @@ -0,0 +1,23 @@ +#include<stdio.h> +#include<stdlib.h> + +const static int len = 10; + +int main(void) { + int *tab; + /* etait en unsigned */ + int i; + + tab = (int*)malloc(len*sizeof(int)); + + /* quand etait en unsigned, on avait un overflow a cause du i--, ce qui le remettait en positif + * ainsi, la boucle ne s'arretait jamais + */ + for (i=len-1; i>=0; i--) { + tab[i] = i; + } + + free(tab); + return 0; +} + diff --git a/semestre 3/structures des données/tme/tme1-2/exo1/tme1_exo1p2.c b/semestre 3/structures des données/tme/tme1-2/exo1/tme1_exo1p2.c new file mode 100644 index 0000000..fb99ee7 --- /dev/null +++ b/semestre 3/structures des données/tme/tme1-2/exo1/tme1_exo1p2.c @@ -0,0 +1,33 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +typedef struct adresse { + int numero; + char* rue; + int code_postal; +} Adresse; + +Adresse* creer_adresse(int n, char* r, int c) { + Adresse* new = (Adresse*) malloc(sizeof(Adresse)); + + new->numero = n; + /* l'erreur dans ce code etait que new->rue n'etait pas assez grand pour contenir 'r' + * de plus, le pointeur n'allait pas etre persistant, donc on a besoin de rajouter un malloc + * pour la regler, je l'ai donc initialisee + */ + new->rue = (char*) malloc(sizeof(char)*strlen(r)); + strcpy(new->rue, r); + new->code_postal = c; + + return new; +} + +int main(void) { + Adresse* maison = creer_adresse(12, "manoeuvre", 15670); + + printf("Adresse courante : %d rue %s %d France\n", maison->numero, maison->rue, maison->code_postal); + + return 0; +} + diff --git a/semestre 3/structures des données/tme/tme1-2/exo1/tme1_exo1p3.c b/semestre 3/structures des données/tme/tme1-2/exo1/tme1_exo1p3.c new file mode 100644 index 0000000..577721c --- /dev/null +++ b/semestre 3/structures des données/tme/tme1-2/exo1/tme1_exo1p3.c @@ -0,0 +1,45 @@ +#include <stdio.h> +#include <stdlib.h> + +typedef struct tableau{ + int* tab; + int maxTaille; + int position; +}Tableau; + +void ajouterElement(int a, Tableau *t){ + t->tab[t->position]=a; + t->position++; +} + +Tableau* initTableau(int maxTaille){ + Tableau* t = (Tableau*)malloc(sizeof(Tableau)); + t->position=0; + t->maxTaille=maxTaille; + /* les 400 bytes repeperes par valgrind proviennent d'ici : 400/4 = 100, 4 etant la taille d'un int ici */ + t->tab=(int*)malloc(sizeof(int)*maxTaille); + return t; +} + +void affichageTableau(Tableau* t){ + printf("t->position = %d\n",t->position); + printf("[ "); + for (int i=0; i < (t->position); i++){ + printf("%d ",t->tab[i]); + } + printf("]\n"); +} + +int main(){ + Tableau* t; + t = initTableau(100); + ajouterElement(5,t); + ajouterElement(18,t); + ajouterElement(99999,t); + ajouterElement(-452,t); + ajouterElement(4587,t); + affichageTableau(t); + /* ce programme provoquait un leak car il ne liberait jamais tab */ + free(t->tab); + free(t); +} diff --git a/semestre 3/structures des données/tme/tme1-2/exo2/Makefile b/semestre 3/structures des données/tme/tme1-2/exo2/Makefile new file mode 100644 index 0000000..d7fd00b --- /dev/null +++ b/semestre 3/structures des données/tme/tme1-2/exo2/Makefile @@ -0,0 +1,12 @@ +all: question2.o question1.o + gcc -ggdb -o main question1.o question2.o + +question2.o: question2.c + gcc -c question2.c + +question1.o: question1.c question1.h + gcc -c question1.h question1.c + +clean: + rm *.o + rm *.gch diff --git a/semestre 3/structures des données/tme/tme1-2/exo2/question1.c b/semestre 3/structures des données/tme/tme1-2/exo2/question1.c new file mode 100644 index 0000000..9341440 --- /dev/null +++ b/semestre 3/structures des données/tme/tme1-2/exo2/question1.c @@ -0,0 +1,28 @@ +#include <stdlib.h> +#include <stdio.h> +#include <time.h> +#include "question1.h" + +/* j'ai fait le choix d'allouer un tableau et de le renvoyer, car ca me semble plus naturel de proceder comme ça */ +int *alloue_tableau(int n){ + return (int *)malloc(sizeof(int)*n); +} + +int *desalloue_tableau(int *t, int n){ + free(t); +} + +void remplir_tableau(int *t, int n, int V){ + srand(time(NULL)); + for (int i = 0; i < n; i++){ + t[i] = rand()%V; + } +} + +void afficher_tableau(int *t, int n){ + printf("["); + for (int i = 0; i < n; i++){ + printf("%d ", t[i]); + } + printf("]\n"); +} diff --git a/semestre 3/structures des données/tme/tme1-2/exo2/question1.h b/semestre 3/structures des données/tme/tme1-2/exo2/question1.h new file mode 100644 index 0000000..4c450a4 --- /dev/null +++ b/semestre 3/structures des données/tme/tme1-2/exo2/question1.h @@ -0,0 +1,9 @@ +#ifndef QUESTION_1_H +#define QUESTION_1_H + +int *alloue_tableau(int n); +int *desalloue_tableau(int *t, int n); +void remplir_tableau(int *t, int n, int V); +void afficher_tableau(int *t, int n); + +#endif // QUESTION_1_H diff --git a/semestre 3/structures des données/tme/tme1-2/exo2/question2.c b/semestre 3/structures des données/tme/tme1-2/exo2/question2.c new file mode 100644 index 0000000..33182ea --- /dev/null +++ b/semestre 3/structures des données/tme/tme1-2/exo2/question2.c @@ -0,0 +1,45 @@ +#include "question1.h" +#include <stdio.h> + +/* Calcule la somme des carrés des différences entre les éléments des tableaux pris deux à deux (version quadratique) */ +int diff_quad(int *t, int n){ + int sum = 0; + for (int i = 0; i < n; i++){ + for (int j = 0; j < n; j++){ + sum += (t[i] - t[j])*(t[i] - t[j]); + } + } + return sum; +} + +/* Calcule la somme des carrés des différences entre les éléments des tableaux pris deux à deux (version linéaire) + * + * On a que sum(sum(x_ix_j)) = (sum(x_i))^2. + * En developpant, on obtient : sum(sum(T_i^2-2*T_i*T_j+T_j^2)) + * i.e. : sum(sum(T_i^2))-sum(sum(2*T_i*T_j))+sum(sum(T_j^2)) + * i.e. : sum(sum(T_i^2))-2*sum(sum(T_i*T_j))+sum(sum(T_j^2)) + * i.e. : 2*sum(T_i^2)-2*sum(sum(T_i*T_j))+2*sum(T_j^2) + * i.e. : 2*sum(T_i^2)-2*(sum(T_i))^2+2*sum(T_j^2) + * Ainsi : 2*(2*sum(T_i^2)-(sum(T_i))^2) + * */ +int diff_lin(int *t, int n){ + int sum1 = 0; + int sum2 = 0; + for (int i = 0; i < n; i++){ + sum1 += t[i]*t[i]; + sum2 += t[i]; + } + return 2*(2*sum1-sum2*sum2); +} + +int main(void){ + int n = 10; + int *t = alloue_tableau(n); + remplir_tableau(t, n, 100); + afficher_tableau(t, n); + + printf("quadratique: %d\n",diff_quad(t,n)); + printf("linéaire: %d\n",diff_lin(t,n)); + + return 0; +} |
