From 20fc727d4f954eb2109b71a7686c3107fdfa4bbf Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Fri, 21 Nov 2025 18:37:48 +0100 Subject: Cours du 3 au 21 novembre ce qui fait 3 semaines en philo et une semaine en info --- .../8- Parcours de graphe.md" | 97 +++++++++++++++++++++ .../structures des donn\303\251es/td/td2/exo3" | Bin 16160 -> 16184 bytes .../structures des donn\303\251es/td/td2/exo3.c" | 4 +- .../structures des donn\303\251es/td/td3/exo4.c" | 5 +- .../structures des donn\303\251es/td/td7/exo1.c" | 90 +++++++++++++++++++ .../structures des donn\303\251es/td/td7/exo2.c" | 39 +++++++++ .../tme/tme3-5/exo1/entreeSortieLC.c" | 1 - .../tme/tme6-11/00014_burma.cha" | 10 +++ .../tme/tme6-11/Chaine.c" | 54 ++++++++++++ .../tme/tme6-11/Chaine.h" | 31 +++++++ .../tme/tme6-11/Makefile" | 11 +++ .../tme/tme6-11/ReconstitueReseau.c" | 36 ++++++++ .../tme/tme6-11/Reseau.c" | 53 +++++++++++ .../tme/tme6-11/Reseau.h" | 41 +++++++++ 14 files changed, 467 insertions(+), 5 deletions(-) create mode 100644 "semestre 3/structures des donn\303\251es/8- Parcours de graphe.md" create mode 100644 "semestre 3/structures des donn\303\251es/td/td7/exo1.c" create mode 100644 "semestre 3/structures des donn\303\251es/td/td7/exo2.c" create mode 100644 "semestre 3/structures des donn\303\251es/tme/tme6-11/00014_burma.cha" create mode 100644 "semestre 3/structures des donn\303\251es/tme/tme6-11/Chaine.c" create mode 100644 "semestre 3/structures des donn\303\251es/tme/tme6-11/Chaine.h" create mode 100644 "semestre 3/structures des donn\303\251es/tme/tme6-11/Makefile" create mode 100644 "semestre 3/structures des donn\303\251es/tme/tme6-11/ReconstitueReseau.c" create mode 100644 "semestre 3/structures des donn\303\251es/tme/tme6-11/Reseau.c" create mode 100644 "semestre 3/structures des donn\303\251es/tme/tme6-11/Reseau.h" (limited to 'semestre 3/structures des données') diff --git "a/semestre 3/structures des donn\303\251es/8- Parcours de graphe.md" "b/semestre 3/structures des donn\303\251es/8- Parcours de graphe.md" new file mode 100644 index 0000000..4bfab39 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/8- Parcours de graphe.md" @@ -0,0 +1,97 @@ +--- +tags: + - sorbonne + - informatique + - structure-des-données +semestre: 3 +--- +On cherche à apprendre à parcourir tous les chemins possibles +|> permet de savoir si un sommet $r$ est accessible depuis un sommet $s$ +Pires cas : +- $r$ n'est pas accessible +- trouver $r$ en dernier +## Sous-parcours +On appelle la racine du parcours est l'endroit où on commence + +Un algorithme de « sous-parcours » est un algorithme de parcours commençant à la racine du parcours (noté $r$) +|> formellement, il retourne $L=(s_1,\ldots,s_k)$ telle que : +- $s_1 = r$ +- $s1,\ldots,s_k$ est l'ensemble des sommets accessibles à partir de $r$ +- pour tout $i\in\{2,\ldots,k\}$, il existe $j\in\{1,\ldots,i-1\}$ telle que $(s_j,s_i)$ est un arc (ou une arête) du graphe (on parlera de bordure) + +**Vocabulaire** +- **Sommet visité** = un sommet qui a été ajouté au sous-parcours +- **Sommet non-visité** = un sommet qui n’a pas (encore) été ajouté au sous-parcours +- **Sommet ouvert** = un sommet visité dans un cadre dont tous les descendants (ou sommets accessibles) n’ont pas encore été visités +- **Sommet fermé** = un sommet visité dont tous les descendants (ou sommets accessibles) ont été visités +- **Bordure d’une liste de sommet** = étant donné une liste L de sommets visités, la bordure B(L) est l’ensemble des sommets non-visités qui sont successeurs (ou voisins) d’au moins un sommet dans la liste ; formellement, dans le graphe $G = (S, A)$, on a : + $$ B(L) = \{s\in S\backslash L| \exists t \in L, (t,s)\in A\}~\text{en orienté} $$ + $$ B(L) = \{s\in S\backslash L| \exists t \in L, \{t,s\}\in A\}~\text{en non-orienté} $$ + +``` +L = Liste(r) +Tant que B(L) n'est pas vide : + Choisir un sommet s dans B(L) + Ajouter s à la fin de la liste L +Fin Tant que +``` +À la fin de ce parcours +|> tous les sommets visités sont fermés +|> un sommet non-visité est inaccessible depuis $r$ + +Cette algo est en $O(n^2)$ car $B(L)$ est en $O(n)$ +|> pas ouf +-> pour éviter d'être aussi lent, on peut facilement mettre à jour B(L) à chaque itération +|> transforme l'algo en $O(n)$ +## Parcours +Un algorithme de « parcours » doit parcourir tous les nœuds +|> besoin de relancer l'algo de sous-parcours quand il s'arrête +|> les racines de tous les sous-parcours sont des points de régénération + +``` +L=Liste(r) +Tant qu’il existe un sommet non-visité : + Si B(L) est non vide: + Choisir un sommet s dans B(L) + Sinon: + Choisir un sommet s non visité <--- il n'existe pas de bon choix + Fin Si + Ajouter s à la fin de la liste L +Fin Tant que +``` +## Stratégie de parcours +Quand on choisit un sommet, on a plusieurs possibilités : +- aléatoire +- profondeur -> va le plus loin possible dans le chemin courant +- largeur -> évite d'aller le plus loin possible +- le plus proche (au sens d'une distance) +- etc + +Elles permettent toutes de trouver les sommets accessibles depuis $r$ +|> mais les trois dernières donnent des informations sur le graphe ! +### Parcours en profondeur +Parcours en profondeur (ou DFS, *deep first search*) est le fait de choisir systématiquement d'explorer un successeur (ou un voisin) du dernier sommet visité ouvert + +``` +L=Liste(r) +Tant que B(L) n'est pas vide : + Choisir un sommet s dans B(L) qui est successeur (ou voisin) du dernier sommet ouvert de L + L = union de L et {s} +Fin Tant que +``` + +Dans ce type de parcours, la bordure est... une pile ! +|> version récursive n'a pas besoin de pile explicite +|> version itérative a besoin d'expliciter la pile (et donc de construire une struct pour) + +**voir le code sur les diapos** + +Complexité temporelle, chaque ligne de code est exécuté : +- une fois +- au maximum une fois par sommet ($n$) +- au maximum une fois par arcs ou arêtes ($m$ ou $2m$) +-> $O(n+m)$ + +Occupation mémoire est similaire pour itérative et récursive pour des $n$ pas trop grand +|> par contre, comme récursive n'est pas terminal, elle prendra plus de place pour des $n$ très grands +### Parcours en largeur diff --git "a/semestre 3/structures des donn\303\251es/td/td2/exo3" "b/semestre 3/structures des donn\303\251es/td/td2/exo3" index b3ee123..d2f0aed 100755 Binary files "a/semestre 3/structures des donn\303\251es/td/td2/exo3" and "b/semestre 3/structures des donn\303\251es/td/td2/exo3" differ diff --git "a/semestre 3/structures des donn\303\251es/td/td2/exo3.c" "b/semestre 3/structures des donn\303\251es/td/td2/exo3.c" index 55b9242..d94c8dc 100644 --- "a/semestre 3/structures des donn\303\251es/td/td2/exo3.c" +++ "b/semestre 3/structures des donn\303\251es/td/td2/exo3.c" @@ -1,5 +1,4 @@ #include -#include #include "LDC.h" int strToInt(char** s){ @@ -49,8 +48,9 @@ int algo(char* expr){ return res; } -void main(){ +int main(){ char* s = "(((4+2)-5)*4)"; int res = algo(s); printf("%s = %d\n", s, res); + return 0; } diff --git "a/semestre 3/structures des donn\303\251es/td/td3/exo4.c" "b/semestre 3/structures des donn\303\251es/td/td3/exo4.c" index 02134c8..09d6d4a 100644 --- "a/semestre 3/structures des donn\303\251es/td/td3/exo4.c" +++ "b/semestre 3/structures des donn\303\251es/td/td3/exo4.c" @@ -1,12 +1,13 @@ +#include typedef struct cell{ int val; int key; - cell* next; + struct cell* next; } Cell; typedef struct hashMap{ int size; - cell** map; + struct cell** map; } HashMap; void mapInsert(HashMap* map, int val){ diff --git "a/semestre 3/structures des donn\303\251es/td/td7/exo1.c" "b/semestre 3/structures des donn\303\251es/td/td7/exo1.c" new file mode 100644 index 0000000..ba5d6a4 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/td/td7/exo1.c" @@ -0,0 +1,90 @@ +#include +#include + +typedef struct Road{ + int u, v; + double dist; +} Road; + +typedef struct RoadCell{ + Road* road; + struct RoadCell* next; +} RoadCell; + +typedef struct City{ + int id; + int x, y; + RoadCell* roads; +} City; + +City** init_cities(int n){ + City** cities = (City**) malloc(sizeof(City)*n); + for (int i = 0; i < n; i++){ + cities[i] = (City*) malloc(sizeof(City)); + cities[i]->id = i; + cities[i]->x = 0; + cities[i]->y = 0; + cities[i]->roads = NULL; + } + return cities; +} + +void update_city(City* city, int x, int y){ + city->x = x; + city->y = x; +} + +void add_route(City* c1, City* c2, double dist){ + Road* road = (Road*) malloc(sizeof(Road)); + road->u = c1->id; + road->v = c2->id; + road->dist = dist; + + RoadCell* road_1 = (RoadCell*) malloc(sizeof(RoadCell)); + road_1->road = road; + road_1->next = c1->roads; + c1->roads = road_1; + + RoadCell* road_2 = (RoadCell*) malloc(sizeof(RoadCell)); + road_2->road = road; + road_2->next = c2->roads; + c2->roads = road_2; +} + +void print(City** cities, int n){ + printf("Cities len: %d\n", n); + for (int i = 0; i < n; i++){ + printf("city %d: {x: %d, y: %d}, roads [", i, cities[i]->x, cities[i]->y); + RoadCell* roads = cities[i]->roads; + while (roads){ + Road* road = roads->road; + printf("{from: %d, to: %d, dist: %f},", road->u, road->v, road->dist); + roads = roads->next; + } + printf("]\n"); + } +} + +void free_cities(City** cities, int n){ + for (int i = 0; i < n; i++) { + City* city = cities[i]; + while (city->roads){ + //TODO: free(city->roads->road) + RoadCell* old = city->roads; + city->roads = city->roads->next; + free(old); + } + free(city); + } + free(cities); +} + +int main(){ + City** cities = init_cities(4); + add_route(cities[0], cities[1], 3); + add_route(cities[1], cities[2], 4); + add_route(cities[0], cities[2], 8); + add_route(cities[3], cities[1], 4.5); + print(cities, 4); + return 0; +} diff --git "a/semestre 3/structures des donn\303\251es/td/td7/exo2.c" "b/semestre 3/structures des donn\303\251es/td/td7/exo2.c" new file mode 100644 index 0000000..3e67451 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/td/td7/exo2.c" @@ -0,0 +1,39 @@ +// complexite = O(2n) = O(n) +void degre_matrice(int** M, int n, int u, int* deg_e, int* deg_s){ + for (int i = 0; i < n; i++) if (M[u][i]) (*deg_e)++; + for (int i = 0; i < n; i++) if (M[i][u]) (*deg_s)++; +} + +typedef struct Cell{ + int to; + struct Cell* next; +} Cell; + +typedef struct List{ + int val; + Cell* linked; +} List; + +// complexite = O(degre max de n) +int degre_entrant_LA(List** l, int n, int u){ + int acc = 0; + Cell* c = l[u]->linked; + while (c){ + acc++; + c = c->next; + } + return acc; +} + +// complexite = O(n+(degre max de n)) +int degre_sortant_LA(List** l, int n, int u){ + int acc = 0; + for (int i = 0; i < n; i++){ + Cell* c = l[i]->linked; + while (c){ + if (c->to == u) acc++; + c = c->next; + } + } + return acc; +} diff --git "a/semestre 3/structures des donn\303\251es/tme/tme3-5/exo1/entreeSortieLC.c" "b/semestre 3/structures des donn\303\251es/tme/tme3-5/exo1/entreeSortieLC.c" index 178b7a8..6a3741b 100644 --- "a/semestre 3/structures des donn\303\251es/tme/tme3-5/exo1/entreeSortieLC.c" +++ "b/semestre 3/structures des donn\303\251es/tme/tme3-5/exo1/entreeSortieLC.c" @@ -1,6 +1,5 @@ #include "entreeSortieLC.h" #include -#include #include Biblio* charger_n_entrees(char* nomfic, int n){ diff --git "a/semestre 3/structures des donn\303\251es/tme/tme6-11/00014_burma.cha" "b/semestre 3/structures des donn\303\251es/tme/tme6-11/00014_burma.cha" new file mode 100644 index 0000000..74c69a2 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/tme/tme6-11/00014_burma.cha" @@ -0,0 +1,10 @@ +NbChain: 8 +Gamma: 3 +0 3 25.23 97.24 14.05 98.12 16.47 94.44 +1 3 14.05 98.12 16.47 96.1 20.09 92.54 +2 3 16.3 97.38 16.53 97.38 25.23 97.24 +3 4 16.47 96.1 20.09 94.55 22.39 93.37 25.23 97.24 +4 4 22.39 93.37 20.09 94.55 17.2 96.29 16.3 97.38 +5 5 14.05 98.12 16.47 94.44 20.09 92.54 22.39 93.37 21.52 95.59 +6 5 14.05 98.12 16.47 94.44 20.09 92.54 22.39 93.37 22 96.05 +7 3 22.39 93.37 20.09 92.54 16.47 96.1 diff --git "a/semestre 3/structures des donn\303\251es/tme/tme6-11/Chaine.c" "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Chaine.c" new file mode 100644 index 0000000..d25f38e --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Chaine.c" @@ -0,0 +1,54 @@ +#include "Chaine.h" +#include +#include +#include + +Chaines* lectureChaines(FILE* f){ + char s[256]; + char* err = fgets(s, 256, f); + if (!err) return NULL; + int nbChain; + sscanf(s, "NbChain: %d", &nbChain); + + err = fgets(s, 256, f); + if (!err) return NULL; + int gamma; + sscanf(s, "Gamma: %d", &gamma); + + Chaines* chains = (Chaines*) malloc(sizeof(Chaines)); + chains->nbChaines = nbChain; + chains->gamma = gamma; + + for (int i = 0; i < nbChain; i++){ + err = fgets(s, 256, f); + if (!err) { + free(chains); // avoiding a memory leak + return NULL; + } + CellChaine* chain = (CellChaine*) malloc(sizeof(CellChaine)); + chain->points = NULL; + chain->suiv = chains->chaines; + chains->chaines = chain; + int nbPoints; + sscanf(s, "%d %d %s", &chain->numero, &nbPoints, s); + for (int j = 0; j < nbPoints; j++){ + CellPoint* point = (CellPoint*) malloc(sizeof(CellPoint)); + point->suiv = chain->points; + chain->points = point; + if (j < nbPoints-1) sscanf(s, "%lf %lf %s", &point->x, &point->y, s); + else sscanf(s, "%lf %lf", &point->x, &point->y); + } + } + return chains; +} + +void ecrireChaines(Chaines* c, FILE* f){ + fprintf(f, "NbChain: %d\n", c->nbChaines); + fprintf(f, "Gamma: %d\n", c->gamma); + CellChaine** chains = (CellChaine**) malloc(sizeof(CellChaine)*c->nbChaines); + CellChaine* chain = c->chaines; + for (int i = 0; i < c->nbChaines; i++){ + chains[i - c->nbChaines - 1] = chain; + chain = chain->suiv; + } +} diff --git "a/semestre 3/structures des donn\303\251es/tme/tme6-11/Chaine.h" "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Chaine.h" new file mode 100644 index 0000000..3539be7 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Chaine.h" @@ -0,0 +1,31 @@ +#ifndef __CHAINE_H__ +#define __CHAINE_H__ +#include + +/* Liste chainee de points */ +typedef struct cellPoint{ + double x,y; /* Coordonnees du point */ + struct cellPoint *suiv; /* Cellule suivante dans la liste */ +} CellPoint; + +/* Celllule d une liste (chainee) de chaines */ +typedef struct cellChaine{ + int numero; /* Numero de la chaine */ + CellPoint *points; /* Liste des points de la chaine */ + struct cellChaine *suiv; /* Cellule suivante dans la liste */ +} CellChaine; + +/* L'ensemble des chaines */ +typedef struct { + int gamma; /* Nombre maximal de fibres par cable */ + int nbChaines; /* Nombre de chaines */ + CellChaine *chaines; /* La liste chainee des chaines */ +} Chaines; + +Chaines* lectureChaines(FILE *f); +void ecrireChaines(Chaines *C, FILE *f); +void afficheChainesSVG(Chaines *C, char* nomInstance); +double longueurTotale(Chaines *C); +int comptePointsTotal(Chaines *C); + +#endif diff --git "a/semestre 3/structures des donn\303\251es/tme/tme6-11/Makefile" "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Makefile" new file mode 100644 index 0000000..b79e199 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Makefile" @@ -0,0 +1,11 @@ +build: Chaine.o Reseau.o ReconstitueReseau.o + gcc -o main Chaine.o Reseau.o ReconstitueReseau.o + +ReconstitueReseau.o: + gcc -c ReconstitueReseau.c + +Chaine.o: + gcc -c Chaine.h Chaine.c + +Reseau.o: + gcc -c Reseau.h Reseau.c diff --git "a/semestre 3/structures des donn\303\251es/tme/tme6-11/ReconstitueReseau.c" "b/semestre 3/structures des donn\303\251es/tme/tme6-11/ReconstitueReseau.c" new file mode 100644 index 0000000..449f534 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/tme/tme6-11/ReconstitueReseau.c" @@ -0,0 +1,36 @@ +#include "Chaine.h" +#include "Reseau.h" +#include +#include + +int main(int argc, char** argv){ + if (argc != 3){ + printf("nombre d'argument invalide, besoin de 3\n"); + return 1; + } + char* file = argv[1]; + int id = atoi(argv[2]); + if (id > 2 || id < 0){ + printf("le deuxième argument doit être entre 0 et 2 inclus\n"); + return 1; + } + FILE* f = fopen(file, "r"); + if (!f){ + printf("impossible d'ouvrir le fichier '%s'\n", file); + return 2; + } + Chaines* C = lectureChaines(f); + if (!C){ + printf("erreur lors du parsing\n"); + return 3; + } + switch (id) { + case 0: + Reseau* res = reconstitueReseauListe(C); + break; + default: + printf("opération pas implémentée\n"); + return 4; + } + return 0; +} diff --git "a/semestre 3/structures des donn\303\251es/tme/tme6-11/Reseau.c" "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Reseau.c" new file mode 100644 index 0000000..cbdaa88 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Reseau.c" @@ -0,0 +1,53 @@ +#include "Chaine.h" +#include +#include "Reseau.h" + +CellNoeud* initNode(Reseau* R, double x, double y){ + CellNoeud* node = (CellNoeud*) malloc(sizeof(CellNoeud)); + node->nd = (Noeud*) malloc(sizeof(Noeud)); + node->nd->num = ++R->nbNoeuds; + node->nd->x = x; + node->nd->y = y; + node->suiv = R->noeuds; + R->noeuds = node; + return node; +} + +Noeud* rechercheCreeNoeudListe(Reseau *R, double x, double y){ + CellNoeud* node = R->noeuds; + while (node && (node->nd->x != x || node->nd->y != y)) node = node->suiv; + if (node) return node->nd; + return initNode(R, x, y)->nd; +} + +Reseau* reconstitueReseauListe(Chaines *C){ + Reseau* R = (Reseau*) malloc(sizeof(Reseau)); + CellChaine* chain = C->chaines; + while (chain){ + CellPoint* points = chain->points; + CellNoeud* before; + CellNoeud* beforeTwice; + while (points){ + Noeud* node = rechercheCreeNoeudListe(R, points->x, points->y); + // represents voisins of node + CellNoeud* cellNode = (CellNoeud*) malloc(sizeof(CellNoeud)); + cellNode->nd = node; + cellNode->suiv = NULL; + if (beforeTwice){ + CellNoeud* cell = (CellNoeud*) malloc(sizeof(CellNoeud)); + cell->nd = node; + cell->suiv = NULL; + beforeTwice->suiv = cell; // link beforeTwice to current + before->nd->voisins = beforeTwice; // set before voisins + } + beforeTwice = before; + before = cellNode; + points = points->suiv; + } + if (beforeTwice && before){ + before->nd->voisins = beforeTwice; // set before voisins + } + chain = chain->suiv; + } + return R; +} diff --git "a/semestre 3/structures des donn\303\251es/tme/tme6-11/Reseau.h" "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Reseau.h" new file mode 100644 index 0000000..dc618a1 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/tme/tme6-11/Reseau.h" @@ -0,0 +1,41 @@ +#ifndef __RESEAU_H__ +#define __RESEAU_H__ +#include "Chaine.h" + +typedef struct noeud Noeud; + +/* Liste chainee de noeuds (pour la liste des noeuds du reseau ET les listes des voisins de chaque noeud) */ +typedef struct cellnoeud { + Noeud *nd; /* Pointeur vers le noeud stock\'e */ + struct cellnoeud *suiv; /* Cellule suivante dans la liste */ +} CellNoeud; + +/* Noeud du reseau */ +struct noeud{ + int num; /* Numero du noeud */ + double x, y; /* Coordonnees du noeud*/ + CellNoeud *voisins; /* Liste des voisins du noeud */ +}; + +/* Liste chainee de commodites */ +typedef struct cellCommodite { + Noeud *extrA, *extrB; /* Noeuds aux extremites de la commodite */ + struct cellCommodite *suiv; /* Cellule suivante dans la liste */ +} CellCommodite; + +/* Un reseau */ +typedef struct { + int nbNoeuds; /* Nombre de noeuds du reseau */ + int gamma; /* Nombre maximal de fibres par cable */ + CellNoeud *noeuds; /* Liste des noeuds du reseau */ + CellCommodite *commodites; /* Liste des commodites a relier */ +} Reseau; + +Noeud* rechercheCreeNoeudListe(Reseau *R, double x, double y); +Reseau* reconstitueReseauListe(Chaines *C); +void ecrireReseau(Reseau *R, FILE *f); +int nbLiaisons(Reseau *R); +int nbCommodites(Reseau *R); +void afficheReseauSVG(Reseau *R, char* nomInstance); +#endif + -- cgit v1.2.3