diff options
38 files changed, 1564 insertions, 15 deletions
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 new file mode 100644 index 0000000..bbc1631 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/2- Programmation en ASM Mips.md @@ -0,0 +1,157 @@ +--- +tags: + - sorbonne + - informatique + - architecture-des-ordinateurs +semestre: 3 +--- +## Registres +Un registre de $n$ bits est un composant capable de mémoriser un mot binaire de $n$ bits +|> changement de valeur possible uniquement lors de front montant/descendant du signal de l’horloge +|> émission de la valeur contenue dans le registre en continu +|> les registres dépendent du processeur +-> contient toutes les informations utilisées par le processeur + +Tous les registres du Mips font 32 bits et en possèdent 32 +|> les registres sont nommés par leur numéro + +PC (Program Counter) = adresse de l’instruction en cours d’exécution (ou la suivante) +|> modifié après l’exécution de chaque instruction + +IR (Instruction Register) = instruction en cours de traitement + +HI/LO (High/Low) = les registres contenant le résultat d’opérations de multiplication ou de division + +Il y a d'autres registres qu'on n'utilisera pas en cours + +> [!info] L'architecture moderne du Mips est le RISC-V + +Processus d'exécution : +1. Lire une instruction en mémoire (dans IR) +2. Décoder l'instruction +3. Exécuter l'instruction +4. Calculer l'adresse de l'instruction suivante : mettre à jour le PC + +Utilisation des registres : +- `$0` contient la valeur 0 -> est le générateur du 0 +- `$1` registre réservé à l'assembleur (programme qui génère le binaire) +- `$2 - $3` contiennent les résultats des appels de fonction +- `$2` peut aussi contenir le numéro d'appel système +- `$4 - $7` (est aussi appelé de `a0` à `a3`) utilisés pour le passage d'arguments lors des appels de fonctions ou appels systèmes +- `$8 - $15` contiennent les valeurs non persistantes (libre) +- `$16 - $25` contiennent les valeurs persistantes (libre) +- `$26 - $27` contiennent les valeurs OS +-> voir les diapos pour les autres + +Les valeurs persistantes gardent les valeurs avant les appels + +> [!NOTE] Notation des registres +> En Mips, on peut les notés avec `R`, `r` ou `$`, ainsi `R1 = r1 = $1` + +> [!danger] On **doit** respecter les règles d'utilisation +## Jeu d'instruction +La vue externe d'un CPU peut être définie par l'ensemble des instructions qu'il est capable de traiter + +Jeu d'instruction d'un CPU (aussi appelé ISA) est la donnée : +- de l'ensemble des instructions qu'il peut effectuer +- le codage de ces instructions en binaire + +Une instruction, c'est une commande définissant le traitement à effectuer et quelle sera la prochaine instruction à exécuter +-> le traitement séquentiel est implicite + +On peut spécifier quelle autre ligne à utiliser après l'instruction en cours +-> c'est un « saut » + +Le code d'opération définit quelle opération utiliser +|> elle porte sur les opérandes +|> opérandes immédiates sont codées dans l'instruction +|> les autres opérandes sont dans des registres indiqués + +`add $4, $2, $5` signifie `$4 <- $2 + $5` +`ori $4, $2, 0xABCF` signifie `$4 <- $2 | (0x0000 ABCF)` +`addi $4, $2, 0xABCF`signifie `$4 <- $2 + (0xFFFF ABCF)` car, par défaut, les entiers sont considérés comme relatifs +`mult $3, $4` signifie `(HI/LO) <- $3 × $4` +`div $3, $4` signifie `(HI/LO) <- $3 ÷ $4` (`HI` contient le quotient et `LO` le reste) + +On peut définir un label pour savoir où sauter + +4 classes d'instructions : +- arithmétique et logique -> addition, and... +- transfert mémoire -> lire la mémoire... +- rupture de séquence -> faire un saut... +- appels systèmes -> lire un caractère, écrire un entier sur l'écran + +Voir le memento pour la liste des instructions + +L'instruction `ori` permet de placer une certaine valeur dans un registre +|> `ori $2, $0, 0x1234` place `0x1234` dans `$2` + +Les instructions en Mips possèdent 3 formats : +- R -> quand on utilise 3 registres +- I -> quand on fait des calculs avec des immédiats +- J -> quand on fait des sauts + +| Nom\n° de bit | 31 - 26 | 25 - 21 | 20 - 16 | 15 - 11 | 10 - 6 | 5 - 0 | +| ------------- | ------- | ------- | ------- | ------- | ------ | ----- | +| **R** | OPCODE | RS | RT | RD | SH | FUNC | +| **I** | OPCODE | RS | RT | IMM | IMM | IMM | +| **J** | OPCODE | JUMP | JUMP | JUMP | JUMP | JUMP | +OPCODE est spécifié dans un codage normé +|> détecte le format utilisé en fonction de l'OPCODE + +Le codage normé ne contient pas tous les OPCODE +|> s'il n'est pas dedans, l'OPCODE est le "special" et l'opération est dans la case FUNC +|> l'opération dans FUNC est aussi dans un codage normé + +On regarde le memento pour savoir ce que signifie RS, RT et RD +|> j'ai l'impression que le registre contenant le résultat est toujours le dernier affiché, mais c'est à vérifier + +SH permet d'utiliser le shift + +Langage haut niveau : +- $\forall$ ISA +- notions de type +- peut créer des variables +- structure les traitements +- gestions d'erreurs + +Assembleur : +- Allocation des données et gestion mémoire +- Suite d'instructions spécifiques +- Présence d'étiquettes pour désigner les adresses (données ou instructions) + +Un programme de haut niveau peut être : +- natif, i.e. il est compilé pour être exécuté sur la machine cible +- interprété, i.e. un programme natif interprète le programme et l'exécuté + +Nous, on ne regarde que les programmes natifs + +Assemblage = assembleur -> binaire +Désassemblage = binaire -> assembleur + +Un label (ou étiquette) s'écrit comme : `nom: add $4, $4, $3` +|> ici le label `nom` désigne la ligne `add $4, $4, $3` +-> elles ne sont pas conservées par lors de l'assemblage + +En Mips, toujours deux sections différentes : +1. les données du programme +2. la section de code + +Directive `.data` permet de dire que la suite sera des données +Directive `.text` indique que la suite sera des instructions + +On met toujours `.data`, y compris si c'est vide (dans le cadre de cette UE) + +Pour exécuter un programme, on a besoin de le charger +|> le mettre en mémoire +|> mettre dans PC la première adresse à exécuter + +En Mips, les syscall se font à l'aide de `syscall` +|> il cherche toujours le numéro de l'appel dans `$2` +-> se finit donc toujours par +```asm +ori $2, $0, 10 # place 10 dans $2 +syscall # syscall dans $2, i.e. syscall 10, i.e. fin du programme +``` + +On utilise le simulateur Mars pour écrire / exécuter des programmes
\ No newline at end of file diff --git a/semestre 3/architecture des ordinateurs/td/25-09-24.md b/semestre 3/architecture des ordinateurs/td/25-09-24.md new file mode 100644 index 0000000..c00232d --- /dev/null +++ b/semestre 3/architecture des ordinateurs/td/25-09-24.md @@ -0,0 +1,48 @@ +--- +tags: + - sorbonne + - informatique + - architecture-des-ordinateurs + - td +semestre: 3 +--- +## Exercice 1 +e = 8, f = 23 + +| Base 10 | Base 2 | +| ------- | ---------------- | +| 2.5 | 10.1 | +| 1.125 | 1.001 | +| 0.75 | 0.11 | +| 0.1 | 0.00011... | +| 0.2 | 0.0011 | +| 63.8 | 11 111.110011... | +## Exercice 2 + +| Base 10 | Base 2 $m=5$, $n=3$ | Base 2 $m=4$, $n=4$ | Base 2 $m=3$, $n=5$ | +| ------- | ------------------- | ------------------- | ------------------- | +| 2.5 | 00010 100 | 0010 1000 | 010 10000 | +| 1.125 | 00001 001 | 0001 0010 | 001 00100 | +| 0.75 | 00000 110 | 0000 1100 | 000 11000 | +| 0.1 | 00000 000* | 0000 0001* | 000 00011* | +| 0.2 | 00000 001* | 0000 0011* | 000 00111* | +| 63.8 | 11111 110* | non représentable | non représentable | + +| Base 10 | Base 2 $m=5$, $n=3$ | Base 2 $m=6$,$n=2$ | +| ------- | ------------------- | ------------------ | +| -0.5 | 11111 100 | 111111 10 | +| -4.125 | 11011 111 | 111011 11 | +| -16.75 | 10111 010 | 110111 01 | +| -31.5 | 10000 100 | 110000 10 | +| -32.0 | 10000 000 | 110000 00 | +| -32.8 | non représentable | 101111 00 | +## Exercice 3 +$101,01_2 = 1,0101_2\times 2^2$ -> `0b0 010 0101` +$0,01 = 1,00\times 2^{-2}$ -> `0b0 111 0000` + +Plus grand est `0b0 011 1111`, i.e. $1,1111_2\times 2^3 = 1111,1_2 = 15,5$ +|> son pas est $0.5$ + +Plus proche de 0 est `0b0 100 0001`, i.e. $0,0001_2\times 2^{-3} =0,000 0001_2=0,0078125$ +|> on peut représenter 0 avec que des 0 partout +|> on peut représenter un dépassement de capacité en regardant s'il y a une retenue sortante au niveau de l'exponent
\ No newline at end of file diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/exo1/q1.c b/semestre 3/architecture des ordinateurs/tme/tme2/exo1/q1.c new file mode 100644 index 0000000..83f9ece --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/exo1/q1.c @@ -0,0 +1,17 @@ +#include <stdio.h> + +int main(){ + int i; + for(i = 0; i>= 0; i++); + printf("int\nmax: %d\nmin: %d\n\n", i-1, i); + + char j; + for(j = 0; j>= 0; j++); + printf("char\nmax: %d\nmin: %d\n\n", (char) (j-1), j); + + short k; + for(k = 0; k>= 0; k++); + printf("short\nmax: %d\nmin: %d\n\n", (short) (k-1), k); + + return 0; +} diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/exo1/q2.c b/semestre 3/architecture des ordinateurs/tme/tme2/exo1/q2.c new file mode 100644 index 0000000..4350455 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/exo1/q2.c @@ -0,0 +1,12 @@ +#include <stdio.h> + +int main(){ + unsigned int i = 0; + i--; + printf("int\nmax: %u\nmin: %d\n\n", i, 0); + + unsigned char j = 0; + j--; + printf("char\nmax: %u\nmin: %d\n\n", (unsigned char) j, 0); + return 0; +} diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/exo2/main b/semestre 3/architecture des ordinateurs/tme/tme2/exo2/main Binary files differnew file mode 100755 index 0000000..593ca11 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/exo2/main diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/exo2/q1-q2.md b/semestre 3/architecture des ordinateurs/tme/tme2/exo2/q1-q2.md new file mode 100644 index 0000000..d97fd9b --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/exo2/q1-q2.md @@ -0,0 +1,25 @@ +## Question 1 + +S: 0 +E: 1000 0010 +M: 010 0000 0000 0000 0000 0000 + +## Question 2 + +41950e56 + +0100 +0001 +1001 +0101 + +0000 +1110 +0101 +0110 + +S: 0 -> positif +E: 1000 0011 -> -128 + 3 = -125 +M: 001 0101 0000 1110 0101 0110 -> 6 + 5×16 + 14×16^2 + 5×16^4 + 1×16^5 = c'est long +=> 18,632 + diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/exo2/q3.c b/semestre 3/architecture des ordinateurs/tme/tme2/exo2/q3.c new file mode 100644 index 0000000..00e0325 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/exo2/q3.c @@ -0,0 +1,10 @@ +#include <stdio.h> + +/* premier nombre est 1103888384 */ +/* deuxième est */ +int main(){ + int i; + scanf("%d", &i); + printf("%f\n", *((float*) &i)); + return 0; +} diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/exo3/q1 b/semestre 3/architecture des ordinateurs/tme/tme2/exo3/q1 Binary files differnew file mode 100755 index 0000000..7eeefe1 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/exo3/q1 diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/exo3/q1.c b/semestre 3/architecture des ordinateurs/tme/tme2/exo3/q1.c new file mode 100644 index 0000000..cac5209 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/exo3/q1.c @@ -0,0 +1,23 @@ +#include <stdio.h> +float suite(int n){ + if (n == 0) return 1; + return 2*suite(n-1)+1; +} + +unsigned long long int suiteInt(int n){ + if (n==0) return 1; + return 2*suiteInt(n-1)+1; +} + +int main(){ + float val = 1; + int i; + for (i = 0; i < 129 && val > 0; i++) { + val = suite(i); + printf("%d — %f\n", i, val); + printf("%d — %llu\n", i, suiteInt(i)); + } + /* Le code déborde à partir de 127 avec la valeur "inf" + * À partir du 24, la suite devient impaire à cause d'un manque de précision des floats + * */ +} diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/exo4.c b/semestre 3/architecture des ordinateurs/tme/tme2/exo4.c new file mode 100644 index 0000000..0338dec --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/exo4.c @@ -0,0 +1,16 @@ +#include <stdio.h> + +int main(){ + char s[25]; + for (int i = 0; i< 25; i++) s[i] = 0; + scanf("%s", s); + s[24] = '\0'; + for (int i = 0; s[i] != '\0'; i++){ + if (s[i] > 'Z' ) { + printf("%c\n", s[i]); + s[i] = *s - ('a' - 'A'); + } + } + printf("%s\n", s); + return 0; +} diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/exo4.c.bp b/semestre 3/architecture des ordinateurs/tme/tme2/exo4.c.bp new file mode 100644 index 0000000..53259cc --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/exo4.c.bp @@ -0,0 +1,16 @@ +#include <stdio.h> + +int main(){ + char s[25]; + for (int i = 0; i< 25; i++) s[i] = 0; + scanf("%s", s); + s[24] = '\0'; + for (int i = 0; s[i] != '\0'; i++){ + if (s[i] > 'Z' ) { + printf("%c\n", s[i]); + s[i] = (char) ((int) *s - ('a' - 'A')); + } + } + printf("%s\n", s); + return 0; +} diff --git a/semestre 3/architecture des ordinateurs/tme/tme2/main b/semestre 3/architecture des ordinateurs/tme/tme2/main Binary files differnew file mode 100755 index 0000000..781d5c7 --- /dev/null +++ b/semestre 3/architecture des ordinateurs/tme/tme2/main diff --git a/semestre 3/histoire philosophie médiévale/0- Introduction.md b/semestre 3/histoire philosophie médiévale/0- Introduction.md index 6c99411..3b07e5d 100644 --- a/semestre 3/histoire philosophie médiévale/0- Introduction.md +++ b/semestre 3/histoire philosophie médiévale/0- Introduction.md @@ -41,4 +41,50 @@ Enjeux : - 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 +- quel statut donner aux sources antiques ? +## Présentation du scepticisme antique +Scepticisme antique est pluriel +|> le scepticisme n'est pas le pyrrhonisme + +D. Sedley (spécialiste de la philo grecque antique) +|> « abandon du désir de savoir » +-> Socrate n'était donc pas sceptique, même s'il limitait la possibilité de connaissance (« je sais que je ne sais rien ») + +Pourtant, Aristote disait que l'humain cherchait par nature le savoir +|> scepticisme est donc étrange +-> renoncer au désir de savoir devient un idéal philosophique puisqu'il va à l'encontre de la nature +|> sceptique collecte donc une série d'argument montrant qu'on ne peut effectivement rien savoir +|> le discours théorique n'est pas la fin +-> renoncer au désir de savoir revient à arrêter tout discours théorique et donc toute philosophie +|> permet d'arriver au bonheur et à la quiétude pour les sceptiques +|> comme la perfection de l'art arrive quand on y renonce +-> est une manière de vivre + +> [!warning] Ne pas oublier que le scepticisme a un objectif pratique +> La théorie est paradoxale, car c'est son objectif + +Quelques dates : +- 365 (?) - 275 av JC -> Pyrrhon +- 316 (?) - 241 av JC -> Arcésilas +- 214 - 129 av JC -> Carnéade +- Ier siècle av JC -> Enesidème +- IIe - IIIe siècle après JC -> Sextus Empiricus + +Scepticisme : +- négation radicale du sens du monde -> pyrrhonisme +- mise en doute de la possibilité de la connaissance -> Nouvelle Académie (dont Arcésilas et Carnéade) +- l'articulation problématique des deux précédentes ->Néo-pyrrhonisme (dont Enesidème et Sextus Empiricus) + +Pyrrhonisme (Aristoclès de Messène, fragment 53, Declava-Caizzi, traduction de C. Lévy) : +- les choses sont incertaines car elles sont instables et indéterminées +- les sensations et les opinions ne sont ni vraies ni fausses +- doit donc rester sans opinion -> renoncement au discours assertif +- il en résulte d'abord le silence (*aphasia*) puis l'absence de trouble (*ataraxie*) +-> serait un nihilisme + +Nouvelle Académie est celle fondée par Platon, mais elle se détache des idées de Platon +|> évolue vers une forme de scepticisme +|> *épochè peri pentone* est la suspension généralisée du jugement +|> est une réaction à l'optimisme épistémologique des stoïciens (le monde est parfaitement ordonné pour qu'on puisse le connaître) +-> met en doute la possibilité de la connaissance, car ils s'opposent aux stoïciens +|> les stoïciens ont trop simplement accès à la connaissance
\ No newline at end of file diff --git a/semestre 3/histoire philosophie médiévale/td/1-.md b/semestre 3/histoire philosophie médiévale/td/1-.md new file mode 100644 index 0000000..1af546c --- /dev/null +++ b/semestre 3/histoire philosophie médiévale/td/1-.md @@ -0,0 +1,54 @@ +--- +tags: + - sorbonne + - philosophie + - histoire-philosophie-médiévale + - td +semestre: 3 +--- +3/01 - DS + +Université de Paris a été fondé en 1200 +|> la nouvelle Athènes +|> enseigne la rhétorique et la dialectique logique (notamment celle d'Aristote) +|> un cursus dure 7 ans d'étude pour arriver au titre de maître des arts +-> permet d'accéder aux études de théologie + +La dialectique d'Aristote commence à dominer +|> traductions massives provenant des pays arabes et grecs +|> transformation radicale du cursus + +Faculté des arts commencent à dépasser son rôle de préparatoire à l'école de théologie +|> philosophie devient indépendante de la théologie + +7 mars 1277 -> évêque de Paris condamne 279 propositions de l'université de Paris visant à faire fonctionner le christianisme avec la vision aristotélicienne +|> Université de Paris se détache de la théologie +|> philosophie nie l'utilité de la théologie car elle + la dialectique permet de connaître Dieu +-> la théologie est obsolète +|> la raison permet de tout connaître +|> problème de la double vérité : comment gérer une réalité philosophique fausse en théologie ? + +Henri de Gand (1217 - 1293) -> théologien +|> comment utiliser les outils libéraux sans tomber dans l'excès ? + +1210 est la première interdiction d'Aristote -> 10 après la fondation, début des tensions + +1217 dominicains puis 1219 franciscain + +1220 - 1235 sont les premières traductions d'Aristote + +1241 est la première condamnation de la théologie grecque + +1266 et 1277 sont des périodes de crises avec bcp de condamnations + +La mort de Thomas d'Aquin laisse un vide -> début des condamnations (y compris de Thomas d'Aquin, mais après sa morte) + +Prologue du texte d'Henri de Gand, _Somme des questions ordinaires_ +|> annonce l'objet des réflexions de la suite +|> se concentre sur la possibilité des connaissances humaines +-> souhaite sortir du scepticisme + +Selon vous, est-il possible de connaître quelque chose avec certitude ? +|> connaissance touchant le monde est impossible +|> connaissance touchant les choses construites par l'humain est possible +-> connaissance scientifique est possible car la science est une construction humaine pour l'humain
\ 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 new file mode 100644 index 0000000..10a142f --- /dev/null +++ b/semestre 3/logique et notions formelles/2- Le langage de la logique propositionnelle.md @@ -0,0 +1,26 @@ +--- +tags: + - sorbonne + - philosophie + - logique-notions-formelles +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 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 + +On formalise la logique propositionnelle pour les analyser +-> permet de dire si les arguments sont valides + +Un énoncé atomique ne contient pas de connecteurs propositionnelles +|> il n'est pas possible de le décomposer +Les énoncés complexes sont des compositions d'énoncés atomiques connectés avec des connecteurs propositionnelles + +Tout énoncé est soit vrai, soit faux. + +**Rattraper le cours d'énoncé vrai / faux à la fin du cours 2** diff --git a/semestre 3/logique et notions formelles/td/1-.md b/semestre 3/logique et notions formelles/td/1-.md new file mode 100644 index 0000000..2d18fea --- /dev/null +++ b/semestre 3/logique et notions formelles/td/1-.md @@ -0,0 +1,37 @@ +--- +tags: + - sorbonne + - philosophie + - logique-notions-formelles + - td +semestre: 3 +--- +20/10 -> premier DS +08/12 -> deuxième DS + +Email en `@ac-creteil.fr` + +--- + +Métal mercure est signe de planète Mercure +Mercure est symbole de la place publique +Syphilis est contractée sur la place publique +-> Syphilis doit être traitée par du mercure +=> est invalide + +Une semaine avant le vote +Démocrates possèdent une avance de 20 points +Une avance de 20 points une semaine avant le vote ne peut pas être renversée +-> Démocrates vont remporter les élections +=> est valide + +Jean > Marie +Jeanne < Marie +-> Jean > Marie +=> est valide si on n'oublie pas la transitivité + +Pour montrer qu'un argument est invalide, on peut chercher un contre exemple + +A est un gentil et n'est pas beau. D'après l'argument, il est beau. Contradiction. + +Soit un losange qui n'est pas carré. Comme un carré est à la fois un losange et un rectangle, ce losange ne peut pas être rectangle. Par conséquent, tous les losanges ne sont pas des rectangles.
\ No newline at end of file diff --git a/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.pdf b/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.pdf Binary files differnew file mode 100644 index 0000000..58bc88c --- /dev/null +++ b/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.pdf diff --git a/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.tex b/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.tex new file mode 100755 index 0000000..b833d16 --- /dev/null +++ b/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.tex @@ -0,0 +1,248 @@ +\documentclass[a4paper, titlepage]{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} +\usepackage{titlesec} + +\renewcommand{\familydefault}{\sfdefault} + +% figure support +\usepackage{import} +\usepackage{xifthen} +\pdfminorversion=7 +\usepackage{pdfpages} +\usepackage{transparent} +\newcommand{\incfig}[1]{% + \def\svgwidth{\columnwidth} + \import{./figures/}{#1.pdf_tex} +} + +\pdfsuppresswarningpagegroup=1 + +\colorlet{defn-color}{DarkBlue} +\colorlet{props-color}{Blue} +\colorlet{warn-color}{Red} +\colorlet{exemple-color}{Green} +\colorlet{corol-color}{Orange} +\newenvironment{defn-leftbar}{% + \def\FrameCommand{{\color{defn-color}\vrule width 3pt} \hspace{10pt}}% + \MakeFramed {\advance\hsize-\width \FrameRestore}}% + {\endMakeFramed} +\newenvironment{warn-leftbar}{% + \def\FrameCommand{{\color{warn-color}\vrule width 3pt} \hspace{10pt}}% + \MakeFramed {\advance\hsize-\width \FrameRestore}}% + {\endMakeFramed} +\newenvironment{exemple-leftbar}{% + \def\FrameCommand{{\color{exemple-color}\vrule width 3pt} \hspace{10pt}}% + \MakeFramed {\advance\hsize-\width \FrameRestore}}% + {\endMakeFramed} +\newenvironment{props-leftbar}{% + \def\FrameCommand{{\color{props-color}\vrule width 3pt} \hspace{10pt}}% + \MakeFramed {\advance\hsize-\width \FrameRestore}}% + {\endMakeFramed} +\newenvironment{corol-leftbar}{% + \def\FrameCommand{{\color{corol-color}\vrule width 3pt} \hspace{10pt}}% + \MakeFramed {\advance\hsize-\width \FrameRestore}}% + {\endMakeFramed} + +\def \freespace {1em} +\declaretheoremstyle[headfont=\sffamily\bfseries,% + notefont=\sffamily\bfseries,% + notebraces={}{},% + headpunct=,% + bodyfont=\sffamily,% + headformat=\color{defn-color}Définition~\NUMBER\hfill\NOTE\smallskip\linebreak,% + preheadhook=\vspace{\freespace}\begin{defn-leftbar},% + postfoothook=\end{defn-leftbar},% +]{better-defn} +\declaretheoremstyle[headfont=\sffamily\bfseries,% + notefont=\sffamily\bfseries,% + notebraces={}{},% + headpunct=,% + bodyfont=\sffamily,% + headformat=\color{warn-color}Attention~\NUMBER\hfill\NOTE\smallskip\linebreak,% + preheadhook=\vspace{\freespace}\begin{warn-leftbar},% + postfoothook=\end{warn-leftbar},% +]{better-warn} +\declaretheoremstyle[headfont=\sffamily\bfseries,% + notefont=\sffamily\bfseries,% +notebraces={}{},% +headpunct=,% + bodyfont=\sffamily,% + headformat=\color{exemple-color}Exemple~\NUMBER\hfill\NOTE\smallskip\linebreak,% + preheadhook=\vspace{\freespace}\begin{exemple-leftbar},% + postfoothook=\end{exemple-leftbar},% +]{better-exemple} +\declaretheoremstyle[headfont=\sffamily\bfseries,% + notefont=\sffamily\bfseries,% + notebraces={}{},% + headpunct=,% + bodyfont=\sffamily,% + headformat=\color{props-color}Proposition~\NUMBER\hfill\NOTE\smallskip\linebreak,% + preheadhook=\vspace{\freespace}\begin{props-leftbar},% + postfoothook=\end{props-leftbar},% +]{better-props} +\declaretheoremstyle[headfont=\sffamily\bfseries,% + notefont=\sffamily\bfseries,% + notebraces={}{},% + headpunct=,% + bodyfont=\sffamily,% + headformat=\color{props-color}Théorème~\NUMBER\hfill\NOTE\smallskip\linebreak,% + preheadhook=\vspace{\freespace}\begin{props-leftbar},% + postfoothook=\end{props-leftbar},% +]{better-thm} +\declaretheoremstyle[headfont=\sffamily\bfseries,% + notefont=\sffamily\bfseries,% + notebraces={}{},% + headpunct=,% + bodyfont=\sffamily,% + headformat=\color{corol-color}Corollaire~\NUMBER\hfill\NOTE\smallskip\linebreak,% + preheadhook=\vspace{\freespace}\begin{corol-leftbar},% + postfoothook=\end{corol-leftbar},% +]{better-corol} + +\declaretheorem[style=better-defn]{defn} +\declaretheorem[style=better-warn]{warn} +\declaretheorem[style=better-exemple]{exemple} +\declaretheorem[style=better-corol]{corol} +\declaretheorem[style=better-props, numberwithin=defn]{props} +\declaretheorem[style=better-thm, sibling=props]{thm} +\newtheorem*{lemme}{Lemme}%[subsection] +%\newtheorem{props}{Propriétés}[defn] + +\newenvironment{system}% +{\left\lbrace\begin{align}}% +{\end{align}\right.} + +\newenvironment{AQT}{{\fontfamily{qbk}\selectfont AQT}} + +\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}{} + +\newenvironment{lititle}% +{\vspace{7mm}\LobsterTwo \large}% +{\\} + +\renewenvironment{proof}{\par$\square$ \footnotesize\textit{Démonstration.}}{\begin{flushright}$\blacksquare$\end{flushright}\par} + +\title{Relations d'ordre, ensembles ordonnés} +\author{William Hergès\thanks{Sorbonne Université}} + +\begin{document} + \maketitle + \tableofcontents + \newpage + \section{ensemble ordoné} + \begin{defn} + Une relation d'ordre $\preceq$ est une relation binaire sur $E$ si et seulement si~: + \begin{itemize} + \item réflexive + \item anti-symétrique + \item transitive + \end{itemize} + + L'ordre strict $\prec$ est associé à $\preceq$~: c'est la même, sauf qu'elle n'est pas réflexive~: + $$ \prec = \preceq\backslash\mathrm{Id}_E $$ + \end{defn} + \begin{defn} + Une relation d'ordre $\preceq$ est~: + \begin{itemize} + \item totale si et seulement si $\preceq$ permet toujours de comparer deux éléments quelconques de $E$ + \item partielle s'il existe au moins deux éléments de $E$ incomparables avec $\preceq$ + \end{itemize} + \end{defn} + \begin{defn} + $(E,\preceq)$ est un ensemble~: + \begin{itemize} + \item totalement ordonné si $\preceq$ est un ordre total. + \item partiellement ordonné si $\preceq$ est un ordre partiel. + \end{itemize} + \end{defn} + \begin{exemple} + $(\mathbb{N},\leqslant )$ est un ensemble totalement ordonné. + + $(\mathcal{P}(F),\subseteq)$ est un ensemble partiellement ordoné (pour $F$ un ensemble quelconque). + + $(\mathbb{N}^*, |)$ est aussi partiellement ordoné, où + $$ | = \{(a,b)|\exists k\in\mathbb{N}^*, b = na\} $$ + (c'est la relation divise.) + \end{exemple} + \begin{proof} + Preuve du deuxième exemple. + + Soit $F$ un ensemble. + + Montrons que $\subseteq$ est un ordre pour $\mathcal{P}(F)$. + \begin{itemize} + \item Soit $A\in\mathcal{P}(F)$. + Triviallement, $A\subseteq A$. + Alors, $\subseteq$ est réflexive. + \item Soit $(A,B)\in\mathcal{P}(F)^2$. + Supposons que $A\subseteq B$ et que $B\subseteq A$. + Alors, $A=B$ par définition. + \item Soit $(A,B,C)\in\mathcal{P}(F)^3$ avec $A\subseteq B$ et $B\subseteq C$. + Si $A$ est l'ensemble vide, il est inclu dans tous les ensembles. + Donc $A\subseteq C$. + Si $A$ n'est pas l'ensemble vide, tous ses éléments sont dans $B$. + Or, tous les éléments de $B$ sont dans $C$. + Donc, tous les éléments de $A$ sont dans $C$. + Alors, $A\subseteq C$. + \end{itemize} + Ainsi, $\subseteq$ est bien un ordre pour $\mathcal{P}(F)$. + + Montrons que $\subseteq$ est un ordre partiel. + + Supposons que $F$ contient au moins deux éléments. + + Soit $(x,y)\in F^2$, deux éléments différents. + Soient $A=\{x\}$ et $B=\{y\}$. + + On a que $A\not\subseteq B$ et que $B\subseteq A$. + Donc, $\subseteq$ est partiel dans ce cas. + + Si $F$ est vide, alors $\mathcal{P}(F)$ contient un unique élément. + Cet ensemble est totalement ordonné. + + Si $F$ est un singleton, alors $\mathcal{P}(F)$ contient $F$ et l'ensemble vide. + Cet ensemble est totalement ordonné. + + La slide est ainsi fausse, mais les ensembles à moins de deux éléments sont peux intéressants. + \end{proof} + Revoir les slides 4 - 6. + \begin{defn} + Soient $(E_1,\preceq_1)$ et $(E_2,\preceq_2)$ deux ensemble ordonnés. + + L'application $f:E_1\to E_2$ est dite monotone si~: + $$ \forall (x,y)\in E_1^2,\quad x\preceq_1 y \implies f(x)\preceq_2 f(y) $$ + \end{defn} + Une application monotone préserve les relations d'ordre. + \begin{exemple} + On se place dans $(\mathbb{N},\leqslant)$ et dans $(\mathcal{P}(\mathbb{N}))$ + + $f:\mathbb{N}\to \mathcal{P}(\mathbb{N})$ tel que $f(n) = \{k\in\mathbb{N}|k\leqslant n\}$ est monotone. + + $g:\mathbb{N}\to \mathcal{P}(\mathbb{N})$ tel que $g(n)=\{n\}$ ne l'est pas par contre~! + \end{exemple} + \begin{props} + Deux ensembles ordonnés $(E_1,\preceq_1)$ et $(E_2,\preceq_2)$ sont isomorphes s'il existe une bijection + $f:E_1\to E_2$ telle que $f$ et $f^{-1}$ sont monotones. + \end{props} + Slide 8 pour des exemples et pour le retour des graphes. + \begin{warn} + Une bijection $f$ peut être monotone sans que $f^{-1}$ ne le soit~! + \end{warn} + \begin{proof} + Fin de la slide 8 pour la preuve. + \end{proof} +\end{document} diff --git a/semestre 3/mathématiques discrètes/td/25-09-26.pdf b/semestre 3/mathématiques discrètes/td/25-09-26.pdf Binary files differnew file mode 100644 index 0000000..cf667e4 --- /dev/null +++ b/semestre 3/mathématiques discrètes/td/25-09-26.pdf diff --git a/semestre 3/mathématiques discrètes/td/25-09-26.tex b/semestre 3/mathématiques discrètes/td/25-09-26.tex new file mode 100755 index 0000000..15b4909 --- /dev/null +++ b/semestre 3/mathématiques discrètes/td/25-09-26.tex @@ -0,0 +1,101 @@ +\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 6} + \begin{enumerate} + \item Supposons que $R$ soit réflexive. + On a que pour tout $x$ dans $R$, $(x,x)\in R$, ce qui est la définition de l'identité. + + Supposons que $\mathrm{Id}_E\subseteq R$. + On a que pour tout $x$ dans $R$, $(x,x)\in R$ car $(x,x)\in\mathrm{Id}_E$. + \item \begin{align*} + \text{$R$ symétrique} \iff& \forall (x,y)\in E^2, (x,y)\in R \implies (y,x)\in R \\ + \iff& R = \{(x,y) \in R | (y,x)\in R \} \\ + \iff& R = R^{-1} + \end{align*} + \item À faire par équivalence classiquement. + \end{enumerate} + \section*{Exercice 8} + Si $R$ est relation d'équivalence sur $E$, alors la classe d'équivalence de $a\in R$ est l'ensemble~: + $$ \{(a,x)\in R\} $$ + \begin{enumerate} + \item $R$ est réflexive, donc $a\in [a]$ car $(a,a)\in R$ + \item Si $[a] = [b]$, alors pour tout $x$ dans $A$, on a $(a,x)\in R$ et $(b,x)\in R$, donc $(a,b)\in R$ par + symétrie et transitivité. + + Pareil dans l'autre sens. + \item Supposons que $[a]\cap[b]\neq\varnothing$. + Alors, $\exists x\in [a]\cap[b]$ tel que $(a,x)\in R$ et $(b,x)\in R$. + Par symétrie et transitivité, on a $(b,x)\in R \iff (x,b)\in R \iff (a,b)\in R$. + Absurde car si $(a,b)\in R$, on a que $[a] = [b]$, ce qui est faux par hypothèse. + \item $\{[a]|a\in A\}$ est une partition de $A$ car + \begin{itemize} + \item tous les éléments de $[a]$ pour tout $a\in A$ sont dans $A$ par définition; + \item toutes les classes d'équivalence sont disjointes (3); + \item tous les éléments de $A$ sont présents dans cet ensemble car $a\in [a]$ (1). + \end{itemize} + \end{enumerate} + \textbf{Ceci est un résultat important~!} + \section*{Exercice 9} + L'application $\{(a,b), (b,b)\}$ dans $\{a,b\}$ n'est ni injective, ni surjective. + \begin{enumerate} + \item $f_1$ est injective, mais pas surjective, car il n'existe pas d'inverse sur $\mathbb{N}$. + $f_2$ est bijective, car il existe un inverse sur $\mathbb{Q}$. + \item $f$ est surjective, car $f(0) = 0$, $f(1) = 1$, $f(2) = 2$ et $f(3) = 0$. + \item $f$ est surjective, car $\forall x\in\mathbb{N}, f(x, 0) = x$ et $f(1,0) = f(0,1)$. + \item $f$ est bijective, car~: + \begin{itemize} + \item si $f(n)$ est pair, alors son antécédent est $n+1$ + \item si $f(n)$ est impair, alors son antécédent est $n-1$ + \item si $f(n_1) = f(n_2)$, alors $n_1 + 1 = n_2 + 1$ ou $n_1 - 1 = n_2 - 1$, i.e. $n_1=n_2$ + \end{itemize} + \item $f$ n'est pas surjective, car les mots ne finissant par par $b$ ne sont jamais atteint. + $f$ est injective, car $f(u_1) = f(u_2) \implies u_1.b = u_2.b\implies u_1 = u_2$. + \end{enumerate} + Il existe $2^3 = 9$ applications différentes de $\{a,b,c\}$ vers $\{1,2\}$ (pour chaque élément de $\{a,b,c\}$, on + possède deux choix), dont aucune injective, $3\times 2 = 6$ surjectives (on choisit quel élément est le premier et + quel élément est le deuxième, le troisième est libre) et aucune bijective (car aucune n'est injective). + \section*{Exercice 19} + Soit $n\in\mathbb{N}$. + + Si $n$ est pair, alors $n+1$ est impair. + Donc, $$ \exists !p\in\mathbb{N},\quad n+1=2p+1 $$ + On pose $x=0$ et $y=p$, alors $$ n = 2^0 (2p+1) - 1 = 2^x(2y+1) $$ + Par conséquent, les nombres pairs s'écrivent comme~: + $$ g(0,p) $$ + + Si $n$ est impair, il existe un unique $p$ dans $\mathbb{N}$ tel que $n = 2p+1$. + Donc, $$ n+1 = 2p+2 = 2(p+1) $$ + Or, un nombre pair s'écrit d'une manière unique avec $(q,r)\in\mathbb{N}^2$ avec $q$ non nul comme~: + $$ 2^q(2r+1) $$ + On pose $x=q$ et $p=r$, alors $$ n = 2^q(2r+1) - 1 = 2^x(2y+1) - 1 $$ + Par conséquent, les nombres pairs s'écrivent comme~: + $$ g(q,r) $$ +\end{document} +endsnippet diff --git a/semestre 3/mathématiques discrètes/td/template.tex b/semestre 3/mathématiques discrètes/td/template.tex index 23ee891..5bebfd6 100755 --- a/semestre 3/mathématiques discrètes/td/template.tex +++ b/semestre 3/mathématiques discrètes/td/template.tex @@ -23,10 +23,9 @@ \titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{} \title{Titre} -\author{William Hergès\thanks{CPES Science Henri-IV / PSL}} +\author{William Hergès\thanks{Sorbonne Université}} \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 index c726078..f755914 100644 --- a/semestre 3/philosophie générale/0- Introduction.md +++ b/semestre 3/philosophie générale/0- Introduction.md @@ -67,3 +67,36 @@ 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 + +**rattraper le cours** + +Pour Aristote, c'est l'âme qui donne le sens aux symboles +|> sinon, ça ne serait que des signes + +Les animaux n'utilisent que des signes et non des symboles +|> le crie possède une signification naturelle, mais pas conventionnelle +|> la signification du crie ne vient pas d'une institution humaine +|> les animaux n'ont pas d'institutions +-> la convention suppose que l'on s'entende ensemble +|> on appartient à une communauté politique + +On a toujours interprété Aristote de cette manière +|> les mots parlent des concepts et non des choses +-> vision mentaliste + +Pourtant, on n'est pas obligé d'associer à un mot une image mentale + +Il existe aussi des mots avec plusieurs objets -> on doit sélectionner sa référence +|> la référence s'accroche à un type de réalité + +Langage a besoin de : état physique (signes), état psychologique (âme) et choses (réalité) +|> s'il nous manque un de ces éléments, on ne peut pas analyser le langage +-> mais on peut choisir ce qui est le plus important + +Les théories mentalistes choisissent de mettre l'accent sur l'âme +En mettant l'accent sur les choses, on indique que le langage se réfère au monde +Et sur les signes, on crée une sémiotique +## Plan +1. Sémiotique +2. Langage et réalité +3. Langage et psychologie diff --git a/semestre 3/philosophie générale/1- Sémiotique.md b/semestre 3/philosophie générale/1- Sémiotique.md new file mode 100644 index 0000000..0c7d171 --- /dev/null +++ b/semestre 3/philosophie générale/1- Sémiotique.md @@ -0,0 +1,55 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-générale +semestre: 3 +--- +Sémiotique = le langage s'inscrit surtout dans les signes + +Stoïciens développent une théorie générale du signe (résumé par Sextus Empiricus) +|> signe semble montrer qlq chose (sens général/premier) +|> signe semble aussi révéler qlq chose qui n'est pas évident +|> signe joue le rôle de proposition +-> sémiotique apparaît comme une théorie de la logique + +Identification entre ce qu'est un signe et comment on connait ce que le signe signifie +-> l'essence du signe, c'est de connaître qlq chose à partir de qlq chose + +Ne distingue pas la nature propre du signe et comment on l'utilise + +**Augustin, _De Magistro_** +Le signe permet de faire passer ce qu'on a dans la tête à autrui +|> mais le signe existe indépendamment de ça + +Signe naturel est, par exemple, la fumée -> représente un feu +|> pas de convention, pas d'intentionnalité +|> personne ne veut signifier qlq chose + +Signe conventionnel signifie qlq chose +|> on veut dire qlq chose quand on l'utilise +|> n'est pas forcément d'ordre linguistique + +Mot est un signe -> échange inter-subjectif +|> les signes naturels ne résultent pas de ce type d'échange +-> langage n'est pas que des signes naturels, mais est aussi des signes conventionnels utilisés lors d'échange inter-subjectif +|> les signes naturels ne sont que des indices + +Les signes naturels, sont-ils vraiment des signes ? +|> un signe résulte de la volonté de communiquer, n'existe pas dans la nature +|> signe a besoin d'être interprété + +**Problème d'Augustin** +Distinction entre signe naturel et signe linguistique n'est pas fait +|> ne permet pas de bien distinguer les deux + +Seul le langage possède deux axes +|> la sélection des mots (axe paradigmatique) +|> dimension syntaxique permettant de créer un sens (axe syntagmatique) +-> sélection & combinaison, est le propre du langage + +Chaque signe possède un sens uniquement dans le système général qu'est la langue +|> un signe ayant un sens en dehors de la langue, n'est pas un signe de la langue + +Le langage est réflexif -> il peut parler de lui-même +Le langage permet de parler de tous les autres systèmes de signe
\ No newline at end of file diff --git a/semestre 3/philosophie générale/td/0- Introduction.md b/semestre 3/philosophie générale/td/0- Introduction.md new file mode 100644 index 0000000..81369ba --- /dev/null +++ b/semestre 3/philosophie générale/td/0- Introduction.md @@ -0,0 +1,66 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-générale + - td +semestre: 3 +--- +Que des auteurs du XXe siècle + +20/11 est le devoir sur table +|> introduction de dissertation + +Possiblement un autre le 11/12 +## Références +_Frege_, « Sur le sens et la référence », _Philosophie du langage_ (anthologie de texte en deux volumes), I, p. 57-58 +|> de « La référence d'un nom propre » à « Suivre cette piste nous écarterait trop de notre chemin » +|> rupture par rapport aux théories classiques de la signification +|> signification d'un mot n'est pas psychologique car elle n'est pas unique à chacun -> elle n'est pas privée, sinon on ne pourrait pas s'entendre dessus +|> signification est liée à la logique : elle ne peut pas se faire réduire à la psychologie, ne possède pas de référence à notre vision particulière +-> est un anti-psychologiste +|> contre la réduction des lois logiques à celle de l'esprit humain +|> le sens est lié à la vérité -> vérité ne peut pas être relative +|> sens doit donc être universel +|> proposition est le contenu idéal d'un énoncé de phrase -> ne dépend pas du contexte +|> pensée est le sens objectif d'une phrase -> est lié à la proposition de la phrase +|> vrai et faux a un sens au niveau de la pensée et non de la phrase +|> pensée est ce dont on peut demander ce qui est vrai ou faux -> est le sens d'une proposition +-> la logique porte ainsi sur des objets idéaux + +Husserl, _Recherche Logiques_, II, 1, p. 75-76 +|> de « Nous sommes cependant » à la fin du paragraphe (3 ?) +|> Frege a converti Husserl + +Merleau-Ponty, « Le langage indirect et les voies du silence », _Signes_, p. 53-54 +|> de « En ce qui concerne le langage » à « Aucun langage n'aborde le langage » +|> existe-t-il une pensée sans langage ? le langage est-il nécessaire au langage ? +|> défend qu'il n'existe pas de pensée sans langage +|> expression ne rend pas manifeste la pensée car elle prend directement forme dans l'expression + +Heidegger, « La Parole », _Acheminement vers la parole_, p. 36-37 +|> de « Les mortels parlent autant qu'ils écoutent » à « dans le parler de la parole » +|> toute vérité est poétique + +Benjamin (Walter), « La tâche du traducteur », Œuvres, I, p. 256-257 +|> de « Fidélité et liberté » à « le grand désir d'une complémentarité des langues +|> comment bien traduire ? + +Kripke (Saul), _La logique des noms propres_, p. 79 +|> de « Un bébé née, ses parents lui donne un nom » à « J'entendrais l'homme qui a fait tel ou telle chose. » +|> reprend sens / référence de Frege est l'approfondie, notamment au niveau des nom propres +|> comment bien désigner Aristote et pas qlq'un d'autre +|> besoin d'instituer par un acte pour nommer un humain et besoin d'une chaîne causale de transmission +|> référence ne peut pas être lié à ce que nous pensons à propos de qlq'un -> ne dépend des représentations associés à notre nom + +Putnam (Hilary), « Signification et référence », _Philosophie du langage_, I, p. 349-350 +|> de « Si Oscar 1 et Oscar 2 sont » à « ne sont tout simplement pas dans la tête » +|> on peut avoir les mêmes croyances sans que ça ne soit en accord avec la réalité +|> référence ne peut pas être simplement dictée par ses opinions sur les choses +|> signification est extra mental + +Austin, « Les énoncés performatifs », _Philosophie du langage_, II, p. 241-243 +|> de « Ces énoncés performatifs ne sont alors ni vrais, ni faux » à « n'a pas réussi. » + +Grice (Paul), « Logique et conversation », _Communication_, n°30, 1979, p. 64-65 +|> de « Je puis maintenant caractériser » à « Donc, il a implicité Q ».
\ No newline at end of file diff --git a/semestre 3/philosophie politique/.$Introduction - Frise chronologique - Foucault.drawio.bkp b/semestre 3/philosophie politique/.$Introduction - Frise chronologique - Foucault.drawio.bkp new file mode 100644 index 0000000..19e953d --- /dev/null +++ b/semestre 3/philosophie politique/.$Introduction - Frise chronologique - Foucault.drawio.bkp @@ -0,0 +1,58 @@ +<mxfile host="Electron" agent="Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) draw.io/28.1.2 Chrome/138.0.7204.251 Electron/37.5.1 Safari/537.36" version="28.1.2"> + <diagram name="Page-1" id="X79K7lofzxEv4FQFJ-r2"> + <mxGraphModel dx="690" dy="551" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0"> + <root> + <mxCell id="0" /> + <mxCell id="1" parent="0" /> + <mxCell id="tUCCnLt23AtMKclwk9Z5-1" value="" style="shape=flexArrow;endArrow=classic;html=1;rounded=0;endWidth=143;endSize=80.66;width=280;" edge="1" parent="1"> + <mxGeometry width="50" height="50" relative="1" as="geometry"> + <mxPoint x="40" y="260" as="sourcePoint" /> + <mxPoint x="780" y="260" as="targetPoint" /> + <Array as="points"> + <mxPoint x="350" y="260" /> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-2" value="" style="endArrow=none;html=1;rounded=0;" edge="1" parent="1"> + <mxGeometry width="50" height="50" relative="1" as="geometry"> + <mxPoint x="239" y="400" as="sourcePoint" /> + <mxPoint x="239" y="123" as="targetPoint" /> + </mxGeometry> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-3" value="" style="endArrow=none;html=1;rounded=0;" edge="1" parent="1"> + <mxGeometry width="50" height="50" relative="1" as="geometry"> + <mxPoint x="479" y="399" as="sourcePoint" /> + <mxPoint x="479" y="122" as="targetPoint" /> + </mxGeometry> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-7" value="<font style="font-size: 18px;">Grêce archaïque</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="50" y="130" width="180" height="30" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-8" value="<font style="font-size: 18px;">Grêce antique &amp; Moyen-Âge</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="271" y="127" width="180" height="43" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-9" value="<font style="font-size: 18px;">Moderne &amp; contemporaine</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="475" y="128" width="180" height="43" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-10" value="<font style="font-size: 16px;">Épreuve</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="50" y="152" width="180" height="30" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-11" value="<font style="font-size: 16px;">Enquête</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="270" y="164" width="180" height="30" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-12" value="<font style="font-size: 16px;">Examen</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="477" y="165" width="180" height="30" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-13" value="<font style="font-size: 14px;">La personne attaquant lance un défi à l'accusé et si ce dernier le relève, alors l'accusé a raison. Le juge s'occupe de la régularité de la procédure.</font><div><font style="font-size: 14px;"><br></font></div><div><font style="font-size: 14px;">Exemple : l'accusation de Ménélas par Antiloque.</font></div>" style="text;html=1;align=left;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="50" y="200" width="180" height="160" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-14" value="<span style="font-size: 14px;">Création de l'infraction. Elle est forcément commise envers un représentant du pouvoir.</span><div><span style="font-size: 14px;">Procureur représente le pouvoir.</span></div><div><span style="font-size: 14px;">Création de l'amende pour réparer le tort.</span></div><div><span style="font-size: 14px;">Témoignage devient pertinent.</span></div><div><span style="font-size: 14px;"><br></span></div><div><span style="font-size: 14px;">Exemple : Œdipe roi, berger qui rapporte ce qu'il a vu</span></div>" style="text;html=1;align=left;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="250" y="200" width="220" height="160" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-15" value="<span style="font-size: 14px;">AAA.</span>" style="text;html=1;align=left;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="487" y="199" width="220" height="160" as="geometry" /> + </mxCell> + </root> + </mxGraphModel> + </diagram> +</mxfile> diff --git a/semestre 3/philosophie politique/1- Enquêter.md b/semestre 3/philosophie politique/1- Enquêter.md index 30d9e7a..67fd04a 100644 --- a/semestre 3/philosophie politique/1- Enquêter.md +++ b/semestre 3/philosophie politique/1- Enquêter.md @@ -24,6 +24,21 @@ _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 +3. passage à l'examen -> processus devient laïque, besoin de règles (État de droit), crime provoque aussi un dommage social => Bentham souhaite construire le Panoptique + +Bentham est un utilitariste cherchant à changer le système judiciaire pour garantir le bonheur au plus grand monde +|> construit le Panoptique -> tous les prisonniers sont gérés par un gardien et les prisonniers ne peuvent pas savoir si un gardien les surveille +-> pour Foucault, c'est le nouveau mode de procédure judiciaire, c'est le nouveau régime de savoir-pouvoir + +Voir [[Enquêter - Frise chronologique - Foucault.pdf]] > [!NOTE] Vérité et procédure judiciaire > Chaque procédure judiciaire ne donne pas la même vision de la vérité +> -> dépend d'un certain régime de savoir-pouvoir +> |> on ne voit pas le monde de la même manière en fonction de notre savoir +> |> le savoir est toujours lié à un type de pouvoir +> |> le pouvoir possibilise le savoir +> -> est ce que Foucault appelle l'archéologie du savoir + +Une injure à une victime devient une injure au pouvoir +## B. Qui dois enquêter ? diff --git a/semestre 3/philosophie politique/A- Méthodo du commentaire.md b/semestre 3/philosophie politique/A- Méthodo du commentaire.md new file mode 100644 index 0000000..db3b672 --- /dev/null +++ b/semestre 3/philosophie politique/A- Méthodo du commentaire.md @@ -0,0 +1,27 @@ +--- +tags: + - sorbonne + - philosophie + - philosophie-politique +semestre: 3 +--- +On cherche à suivre le texte en le découpant au bon endroit + +Une idée par paragraphe +Partie commence toujours par un chapeau introducteur +## Introduction +Commence par une phrase d'accroche si on en a une bonne + +Déroulement : +1. situation du texte -> on le place dans l'ouvrage, on le présente ; si on ne peut pas, on le place au moins dans une époque intellectuelle +2. objet / thème -> ce dont parle le texte (est souvent un groupe nominal), e.g. évolution des procédures judiciaires occidentales (attention à avoir pile le bon sujet) +3. problème -> la question posée par l'auteur — doit être problématique (doit y avoir une tension) et être ajusté au texte spécifique +4. thèse -> position défendue par l'auteur, sa réponse +5. plan / structure -> comment l'auteur organise sa réflexion +6. enjeu -> pourquoi l'auteur défend-il cette vision ? qu'est-ce qui est en jeu ? + +On évite de griller toutes ses cartouches dans l'introduction +## Corps du texte +À propos de la paraphrase, voir le doc sur Moodle + +Paraphrase = mieux écrire, sauf qu'on cherche à mieux lire !
\ No newline at end of file diff --git a/semestre 3/philosophie politique/Enquêter - Frise chronologique - Foucault.pdf b/semestre 3/philosophie politique/Enquêter - Frise chronologique - Foucault.pdf Binary files differnew file mode 100644 index 0000000..ae09abc --- /dev/null +++ b/semestre 3/philosophie politique/Enquêter - Frise chronologique - Foucault.pdf diff --git a/semestre 3/philosophie politique/Introduction - Frise chronologique - Foucault.drawio b/semestre 3/philosophie politique/Introduction - Frise chronologique - Foucault.drawio new file mode 100644 index 0000000..3ae34a7 --- /dev/null +++ b/semestre 3/philosophie politique/Introduction - Frise chronologique - Foucault.drawio @@ -0,0 +1,58 @@ +<mxfile host="Electron" agent="Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) draw.io/28.1.2 Chrome/138.0.7204.251 Electron/37.5.1 Safari/537.36" version="28.1.2"> + <diagram name="Page-1" id="X79K7lofzxEv4FQFJ-r2"> + <mxGraphModel dx="690" dy="551" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0"> + <root> + <mxCell id="0" /> + <mxCell id="1" parent="0" /> + <mxCell id="tUCCnLt23AtMKclwk9Z5-1" value="" style="shape=flexArrow;endArrow=classic;html=1;rounded=0;endWidth=143;endSize=80.66;width=280;" edge="1" parent="1"> + <mxGeometry width="50" height="50" relative="1" as="geometry"> + <mxPoint x="40" y="260" as="sourcePoint" /> + <mxPoint x="780" y="260" as="targetPoint" /> + <Array as="points"> + <mxPoint x="350" y="260" /> + </Array> + </mxGeometry> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-2" value="" style="endArrow=none;html=1;rounded=0;" edge="1" parent="1"> + <mxGeometry width="50" height="50" relative="1" as="geometry"> + <mxPoint x="239" y="400" as="sourcePoint" /> + <mxPoint x="239" y="123" as="targetPoint" /> + </mxGeometry> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-3" value="" style="endArrow=none;html=1;rounded=0;" edge="1" parent="1"> + <mxGeometry width="50" height="50" relative="1" as="geometry"> + <mxPoint x="479" y="399" as="sourcePoint" /> + <mxPoint x="479" y="122" as="targetPoint" /> + </mxGeometry> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-7" value="<font style="font-size: 18px;">Grêce archaïque</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="50" y="130" width="180" height="30" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-8" value="<font style="font-size: 18px;">Grêce antique &amp; Moyen-Âge</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="271" y="127" width="180" height="43" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-9" value="<font style="font-size: 18px;">Moderne &amp; contemporaine</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="475" y="128" width="180" height="43" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-10" value="<font style="font-size: 16px;">Épreuve</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="50" y="152" width="180" height="30" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-11" value="<font style="font-size: 16px;">Enquête</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="270" y="164" width="180" height="30" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-12" value="<font style="font-size: 16px;">Examen</font>" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="477" y="165" width="180" height="30" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-13" value="<font style="font-size: 14px;">La personne attaquant lance un défi à l'accusé et si ce dernier le relève, alors l'accusé a raison. Le juge s'occupe de la régularité de la procédure.</font><div><font style="font-size: 14px;"><br></font></div><div><font style="font-size: 14px;">Exemple : l'accusation de Ménélas par Antiloque.</font></div>" style="text;html=1;align=left;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="50" y="200" width="180" height="160" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-14" value="<span style="font-size: 14px;">Création de l'infraction. Elle est forcément commise envers un représentant du pouvoir.</span><div><span style="font-size: 14px;">Procureur représente le pouvoir.</span></div><div><span style="font-size: 14px;">Création de l'amende pour réparer le tort.</span></div><div><span style="font-size: 14px;">Témoignage devient pertinent.</span></div><div><span style="font-size: 14px;"><br></span></div><div><span style="font-size: 14px;">Exemple : Œdipe roi, berger qui rapporte ce qu'il a vu</span></div>" style="text;html=1;align=left;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="250" y="200" width="220" height="160" as="geometry" /> + </mxCell> + <mxCell id="tUCCnLt23AtMKclwk9Z5-15" value="<span style="font-size: 14px;">Création de la notion de dangerosité. Un individu peut être dangereux sans n'avoir rien commis.</span><div><span style="font-size: 14px;">Laïcisation des termes et création de règles.</span></div><div><span style="font-size: 14px;">Institutions doivent empêcher les individus dangereux</span></div><div><span style="font-size: 14px;">Société panoptique, société où la règle est la norme</span></div><div><span style="font-size: 14px;"><br></span></div><div><span style="font-size: 14px;">Exemple : Le panoptique</span></div><div><span style="font-size: 14px;">de Bentham</span></div>" style="text;html=1;align=left;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="487" y="204" width="220" height="179" as="geometry" /> + </mxCell> + </root> + </mxGraphModel> + </diagram> +</mxfile> diff --git a/semestre 3/structures des données/3- Hash.md b/semestre 3/structures des données/3- Hash.md new file mode 100644 index 0000000..1a37b83 --- /dev/null +++ b/semestre 3/structures des données/3- Hash.md @@ -0,0 +1,90 @@ +--- +tags: + - sorbonne + - informatique + - structure-des-données +semestre: 3 +--- +## Tableaux associatifs +**Rattraper le cours** + +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}$. + +**Rattraper facteur de charge** + +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 +**Rattraper cours, j'ai trop faim pour bien prendre en note** + +probing quadratic, souvent, $c=d=\frac 12$ +## 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 + +**Rattraper cours pour la même raison** +pb dans l'exemple -> les flèches de w doivent arriver sur que des 1
\ No newline at end of file diff --git a/semestre 3/structures des données/td/td2/LDC.h b/semestre 3/structures des données/td/td2/LDC.h new file mode 100644 index 0000000..78524d3 --- /dev/null +++ b/semestre 3/structures des données/td/td2/LDC.h @@ -0,0 +1,39 @@ +#ifndef LDC_H +#define LDC_H + +typedef struct cell { + struct cell* after; + struct cell* before; + int val; +} Cell; + +typedef struct { + Cell* first; + Cell* last; +} ChainedList; + +Cell* creerElement(int val); + +ChainedList* initialiserListe(ChainedList* list); + +ChainedList* creerListe(); + +int listeVide(ChainedList* list); + +void insererEnTete(ChainedList* list, int val); + +void insererEnFin(ChainedList* list, int val); + +void afficher(ChainedList* list); + +ChainedList* rechercher(ChainedList* list, int val); + +void supprimerElement(ChainedList* list, Cell* el); + +void supprimerTete(ChainedList* list); + +void supprimerFin(ChainedList* list); + +void desalloueListe(ChainedList* list); + +#endif // !LDC_H diff --git a/semestre 3/structures des données/td/td2/Makefile b/semestre 3/structures des données/td/td2/Makefile new file mode 100644 index 0000000..592f4f2 --- /dev/null +++ b/semestre 3/structures des données/td/td2/Makefile @@ -0,0 +1,8 @@ +all: exo3.o exo1.o + gcc -o exo3 exo3.o exo1.o + +exo1.o: LDC.h exo1.c + gcc -c LDC.h exo1.c + +exo3.o: exo3.c + gcc -c exo3.c diff --git a/semestre 3/structures des données/td/td2/exo1.c b/semestre 3/structures des données/td/td2/exo1.c new file mode 100644 index 0000000..752828a --- /dev/null +++ b/semestre 3/structures des données/td/td2/exo1.c @@ -0,0 +1,117 @@ +#include <stdlib.h> +#include <stdio.h> +#include "LDC.h" + +Cell* creerElement(int val){ + Cell* cell = (Cell*) malloc(sizeof(Cell)); + cell->val = val; + cell->after = NULL; + cell->before = NULL; + return cell; +} + +ChainedList* initialiserListe(ChainedList* list){ + list->first = NULL; + list->last = NULL; + return list; +} + +ChainedList* creerListe(){ + ChainedList* list = (ChainedList*) malloc(sizeof(ChainedList)); + return initialiserListe(list); +} + +int listeVide(ChainedList* list){ + /* we assume in this case that first is equal to last */ + return !list->first; +} + +void insererEnTete(ChainedList* list, int val){ + Cell* cell = creerElement(val); + cell->after = list->first; + if (listeVide(list)){ + list->last = cell; + } else { + list->first->before = cell; + } + list->first = cell; +} + +void insererEnFin(ChainedList* list, int val){ + Cell* cell = creerElement(val); + cell->before = list->last; + if (listeVide(list)){ + list->first = cell; + } else { + list->last->after = cell; + } + list->last = cell; +} + +void afficher(ChainedList* list){ + Cell* cell = list->last; + printf("[ "); + while (cell){ + printf("%d ", cell->val); + cell = cell->before; + } + printf("]\n"); +} + +ChainedList* rechercher(ChainedList* list, int val){ + Cell* cell = list->last; + while (cell){ + if (cell->val == val){ + return list; + } + cell = cell->before; + } + return NULL; +} + +void supprimerElement(ChainedList* list, Cell* el){ + if (listeVide(list)){ + return; + } + if (el == list->last){ + list->last = list->last->before; + if (!list->last){ + list->first = NULL; + } + return; + } + if (el == list->first){ + list->first = list->first->after; + if (!list->first){ + list->last = NULL; + } + return; + } + Cell* cell = list->last; + while (cell && cell != el){ + cell = cell->before; + } + if (cell != el){ + return; + } + cell->before->after = cell->after; + free(cell); +} + +void supprimerTete(ChainedList* list){ + supprimerElement(list, list->first); +} + +void supprimerFin(ChainedList* list){ + supprimerElement(list, list->last); +} + +void desalloueListe(ChainedList* list){ + Cell* cell = list->last; + while (cell){ + Cell* before = cell->before; + free(cell); + cell = before; + } + free(list); +} diff --git a/semestre 3/structures des données/td/td2/exo2.c b/semestre 3/structures des données/td/td2/exo2.c new file mode 100644 index 0000000..166616c --- /dev/null +++ b/semestre 3/structures des données/td/td2/exo2.c @@ -0,0 +1,24 @@ +#include "LDC.h" + +/* N is the number of guichet */ +#define N 15 + +ChainedList** creerBureauPoste(){ + ChainedList** postes = (ChainedList**) malloc(N*sizeof(ChainedList)); + return postes; +} + +void afficherPoste(ChainedList** guichets){ + for (int i = 0; i < N; i++){ + afficher(guichets[i]); + } +} + +ChainedList* ajouterAuGuichet(ChainedList* guichet, int id){ + return insererEnFin(guichet, creerElement(id)); +} + +ChainedList* appelerAuGuichet(ChainedList* guichet){ + return supprimerTete(guichet); +} + diff --git a/semestre 3/structures des données/td/td2/exo3 b/semestre 3/structures des données/td/td2/exo3 Binary files differnew file mode 100755 index 0000000..b3ee123 --- /dev/null +++ b/semestre 3/structures des données/td/td2/exo3 diff --git a/semestre 3/structures des données/td/td2/exo3.c b/semestre 3/structures des données/td/td2/exo3.c new file mode 100644 index 0000000..55b9242 --- /dev/null +++ b/semestre 3/structures des données/td/td2/exo3.c @@ -0,0 +1,56 @@ +#include <stdio.h> +#include <stdlib.h> +#include "LDC.h" + +int strToInt(char** s){ + int n = -1; + while (*s && **s != '\0' && **s - '0' < 10 && **s - '0' >= 0){ + if (n == -1) n = 0; + n *= 10; + n += **s - '0'; + (*s)++; + } + // avoid skipping the char is it was not converted + if (n >= 0) (*s)--; + return n; +} + +int algo(char* expr){ + char* c = expr; + ChainedList* stack = creerListe(); + while (c && *c != '\0'){ + if (*c == ')'){ + int o2 = stack->last->val; + supprimerFin(stack); + char op = (char) stack->last->val; + supprimerFin(stack); + int o1 = stack->last->val; + supprimerFin(stack); + + int res = 0; + if (op == '+'){ + res += o1 + o2; + } else if (op == '-'){ + res += o1 - o2; + } else if (op == '*'){ + res += o1 * o2; + } else if (op == '/'){ + res += o1 / o2; + } + insererEnFin(stack, res); + } else if (*c != '(' && *c != ')'){ + int n = strToInt(&c); + insererEnFin(stack, n >= 0 ? n : (int) *c); + } + c++; + } + int res = stack->first->val; + desalloueListe(stack); + return res; +} + +void main(){ + char* s = "(((4+2)-5)*4)"; + int res = algo(s); + printf("%s = %d\n", s, res); +} 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 index 33182ea..19d29cc 100644 --- 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 @@ -14,22 +14,16 @@ int diff_quad(int *t, int n){ /* 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) + * Après diverses simplifications, on obtient que sum(sum(T_i-T_j)^2) est egale à 2 * sum(n*T_i*T_j - T_i^2) * */ int diff_lin(int *t, int n){ - int sum1 = 0; - int sum2 = 0; + int sum = 0; + int sub_sum = 0; for (int i = 0; i < n; i++){ - sum1 += t[i]*t[i]; - sum2 += t[i]; + sum += n*t[i]*t[i]; + sub_sum += t[i]; } - return 2*(2*sum1-sum2*sum2); + return 2 * (sum - sub_sum * sub_sum); } int main(void){ diff --git a/semestre 3/structures des données/tme/tme1-2/exo2/question4-6.c b/semestre 3/structures des données/tme/tme1-2/exo2/question4-6.c new file mode 100644 index 0000000..d75179a --- /dev/null +++ b/semestre 3/structures des données/tme/tme1-2/exo2/question4-6.c @@ -0,0 +1,74 @@ +#include <stdlib.h> +#include <stdio.h> +#include <time.h> + +typedef struct{ + int size; + int* content; +} Matrice; + +Matrice* alloue_matrice(int n){ + int** content = (int**) malloc(n*n*sizeof(int)); + Matrice* m = (Matrice*) malloc(sizeof(Matrice)); + m->content = content; + return m +} + +void desalloue_matrice(Matrice* m){ + free(m->content); + free(m); +} + +void remplir_matrice(Matrice* m, int max){ + srand(time(null)); + for (int i = 0; i < n; i++){ + for (int j = 0; j < n; j++){ + m->content[i][j] = rand()%max; + } + } +} + +void affiche_matrice(Matrice* m){ + printf("["); + for (int i = 0; i < n; i++){ + printf(" ["); + for (int j = 0; j < n; j++){ + printf("%d ", m->content[i][j]); + } + printf("]%c", i != n -1 ? '\n' : ' '); + } + printf("]\n"); +} + +Matrice* produit_matrice(Matrice* m1, Matrice* m2){ + if (m1->size != m2->size){ + return NULL; + } + Matrice* prod = alloue_matrice(m1->size); + for (int i = 0; i < m1->size; i++){ + for (int k = 0; k < m1->size; k++){ + prod->content[i][k] = 0; + for (int j = 0; j < m1->size; j++){ + prod->content[i][k] += m1->content[i][j]*m2->content[j][k]; + } + } + } + return prod; +} + +/* Reste en O(n3), mais est plus rapide que produit_matrice car on arrete les boucles plus tot */ +Matrice* produit_matrice_trian(Matrice* m_sup, Matrice* m_inf){ + if (m_sup->size != m_inf->size){ + return NULL; + } + Matrice* prod = alloue_matrice(m_sup->size); + for (int i = 0; i < m_sup->size; i++){ + for (int k = 0; k < m_sup->size; k++){ + prod->content[i][k] = 0; + for (int j = i; j < m_sup->size; j++){ + prod->content[i][k] = m_sup->content[i][j]*m_inf->content[j][k]; + } + } + } + return prod; +} |