Cours du 22 au 26 septembre

9 files changed, 414 insertions, 12 deletions

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