Cours du 15 au 19 septembre

1 files changed, 111 insertions, 0 deletions

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
+```