diff options
Diffstat (limited to 'semestre 3/structures des données')
| -rw-r--r-- | semestre 3/structures des données/3- Hash.md | 90 | ||||
| -rw-r--r-- | semestre 3/structures des données/td/td2/LDC.h | 39 | ||||
| -rw-r--r-- | semestre 3/structures des données/td/td2/Makefile | 8 | ||||
| -rw-r--r-- | semestre 3/structures des données/td/td2/exo1.c | 117 | ||||
| -rw-r--r-- | semestre 3/structures des données/td/td2/exo2.c | 24 | ||||
| -rwxr-xr-x | semestre 3/structures des données/td/td2/exo3 | bin | 0 -> 16160 bytes | |||
| -rw-r--r-- | semestre 3/structures des données/td/td2/exo3.c | 56 | ||||
| -rw-r--r-- | semestre 3/structures des données/tme/tme1-2/exo2/question2.c | 18 | ||||
| -rw-r--r-- | semestre 3/structures des données/tme/tme1-2/exo2/question4-6.c | 74 |
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 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; +} |