Cours du 15 au 19 septembre

22 files changed, 544 insertions, 0 deletions

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;
+}