diff options
Diffstat (limited to 'semestre 2/informatique')
6 files changed, 211 insertions, 5 deletions
diff --git a/semestre 2/informatique/10- Compression LZW.md b/semestre 2/informatique/10- Compression LZW.md new file mode 100644 index 0000000..d6956ae --- /dev/null +++ b/semestre 2/informatique/10- Compression LZW.md @@ -0,0 +1,30 @@ +--- +tags: + - sorbonne + - informatique +semestre: 2 +--- +LZW raisonne sur les syllables +|> les strings sont remplacés par des codes plus court stocker dans une map +|> n'a pas besoin d'analyser les strings pour compresser et n'a pas besoin de connaître la map pour décompresser + +Algo : +- lit la chaîne la plus longue dans la map +- remplace la chaîne lue par son code dans le fichier de sortie +- insère une nouvelle chaîne composée du préfixe lu et du caractère suivant dans le fichier dans la map + + En gros, ça fait ça pour `"ABCDABCD"` : + - `"A"` -> 65 (d'après la valeur initiale dans la map) + - `"AB"` -> 256 (d'après l'algo de la map) + - on enlève le préfixe `"A"` et on avance : `"BC"` -> 257 (toujours d'après l'algo) + - on enlève le préfixe `"B"` et on avance : `"CD"` -> 258 (...) + - on enlève le préfixe `"C"` et on avance : `"DA"` -> 259 (...) + - on enlève le préfixe `"D"` et on avance :`"AB"` -> déjà dans le dictionnaire, donc 256 ; on insère `"ABC"` + - on avance : `"ABCD"` -> déjà dans le dictionnaire, donc 258 ; on insère `"ABCD"` + -> si la valeur est déjà dans la map, alors on l'utilise comme préfixe pour le prochain, sinon on garde le plus grand + +Le fichier de sortie vaut donc : `65 66 67 68 256 258` +|> on ne rajoute pas de suite `257` pour remplacer `65 66` car ça pourrait augmenter la taille + +Quand on décompresse, on a besoin d'utiliser le dictionnaire de base +|> quand on arrive sur une séquence compresser, on a besoin de faire le raisonnement inverse de la compression : on détermine la chaîne qui aurait donné la valeur
\ No newline at end of file diff --git a/semestre 2/informatique/9- Utilisation des listes.md b/semestre 2/informatique/9- Utilisation des listes.md index 8e8e093..db4e182 100644 --- a/semestre 2/informatique/9- Utilisation des listes.md +++ b/semestre 2/informatique/9- Utilisation des listes.md @@ -48,7 +48,7 @@ fifo *new_fifo(){ int is_empty(fifo f){ assert((f.last && f.first) || (!f.last && !f.first)); // permet de faire une vérification et de faire en sorte que le programme s'arrête proprement - return !f.first && !f.last + return !f.first && !f.last; } void add(fifo *f, int val){ @@ -56,14 +56,14 @@ void add(fifo *f, int val){ cell *c = malloc(sizeof(cell)); c->suivant = NULL; c->donnee = val; - if (is_empty(f)) f->first = c; + if (is_empty(*f)) f->first = c; else f->last->suivant = c; f->last = c; } int pop(fifo *f){ if (!f || is_empty(f)) return 0; - cell c = f->first; + cell *c = f->first; int d = c->donnee; f->first = c->suivant; free(c); @@ -76,10 +76,10 @@ void print_fifo(fifo *f){ printf("\n"); return; } - cell *first = fifo->first; + cell *first = f->first; printf("{"); while (first){ - printf("%d, ", f->donnee); + printf("%d, ", first->donnee); first = first->suivant; } printf("}\n"); diff --git a/semestre 2/informatique/tme/semaine9/Makefile b/semestre 2/informatique/tme/semaine9/Makefile new file mode 100644 index 0000000..e961ede --- /dev/null +++ b/semestre 2/informatique/tme/semaine9/Makefile @@ -0,0 +1,4 @@ +build-run: + gcc -o app multi_ensembles.c multi_ensembles.h test_multi_ensembles.c + ./app + rm app diff --git a/semestre 2/informatique/tme/semaine9/multi_ensembles.c b/semestre 2/informatique/tme/semaine9/multi_ensembles.c new file mode 100644 index 0000000..64a8a34 --- /dev/null +++ b/semestre 2/informatique/tme/semaine9/multi_ensembles.c @@ -0,0 +1,132 @@ +#include <stdio.h> +#include <stdlib.h> +#include "multi_ensembles.h" + + +/* Retourne un pointeur sur le premier element de valeur val, retourne NULL si aucun élément n'a la valeur val */ +element_t * Recherche_val(element_t *ensemble, int val) { + while (ensemble){ + if (ensemble->valeur == val) return ensemble; + ensemble = ensemble->suivant; + } + return NULL; +} + +/* Ajoute l'element val en tete de l'ensemble s'il n'apparait pas dans l'ensemble, augmente sa frequence de 1 sinon */ +element_t * Ajout_tete_ensemble(element_t *ensemble, int val, int freq) { + element_t *f = Recherche_val(ensemble, val); + if (f) { + f->frequence += freq; + return ensemble; + } + element_t *el = malloc(sizeof(element_t)); + el->suivant = ensemble; + el->frequence = freq; + el->valeur = val; + return el; +} + + +/* Affche tous les elements d'un ensemble avec leur frequence */ +void Affiche_ensemble(element_t *ensemble) { + element_t *ptr = ensemble; + + while (ptr != NULL) { + printf("val : %d, frequence : %d\n",ptr->valeur,ptr->frequence); + ptr=ptr->suivant; + } +} + +/* Saisie des n elements d'un ensemble */ +element_t * Creation_ensemble(int n) { + element_t *ensemble=NULL; + + int i = 0; + int val; + + for (i=0; i < n; i++) { + printf("Saisie d'un entier: "); + scanf("%d",&val); + ensemble=Ajout_tete_ensemble(ensemble,val,1); + } + return ensemble; +} + +element_t *Supprime_total_element_ensemble(element_t *ensemble, int val){ + element_t *head = ensemble; + element_t *before = NULL; + while (ensemble){ + element_t *toDelete = NULL; + if (ensemble->valeur == val){ + if (before) before->suivant = ensemble->suivant; + else head = ensemble->suivant; + toDelete = ensemble; + } else before = ensemble; + ensemble = ensemble->suivant; + if (toDelete) free(toDelete); + } + return head; +} + +element_t *Supprime_element_ensemble(element_t *ensemble, int val){ + element_t *head = ensemble; + element_t *before = NULL; + while (ensemble){ + element_t *toDelete = NULL; + if (ensemble->valeur == val){ + ensemble->frequence--; + if (ensemble->frequence < 1){ + if (before) before->suivant = ensemble->suivant; + else head = ensemble->suivant; + toDelete = ensemble; + } + } else before = ensemble; + ensemble = ensemble->suivant; + if (toDelete) free(toDelete); + } + return head; +} + +element_t *Ajout_ensemble_trie(element_t *ensemble, int val, int freq){ + if (!ensemble || ensemble->valeur > val) { + element_t *el = malloc(sizeof(element_t)); + el->suivant = ensemble; + el->frequence = freq; + el->valeur = val; + return el; + } + element_t *head = ensemble; + while (ensemble && ensemble->valeur <= val){ + if (ensemble->valeur == val) ensemble->frequence += freq; + else if (!ensemble->suivant || ensemble->suivant->valeur > val){ + element_t *new = malloc(sizeof(element_t)); + new->valeur = val; + new->frequence = freq; + new->suivant = ensemble->suivant; + ensemble->suivant = new; + ensemble = new; // empêche de passer deux fois sur la même valeur + } + ensemble = ensemble->suivant; + } + return head; +} + +int Inclus(element_t *sub, element_t *ens){ + while (ens && sub && ens->valeur <= sub->valeur){ + if (sub->valeur == ens->valeur){ + if (sub->frequence > ens->frequence) return 0; + else sub = sub->suivant; + } + ens = ens->suivant; + } + return sub == NULL; +} + +int Intersection_vide(element_t *e1, element_t *e2){ + while (e1 && e2){ + if (e1->valeur == e2->valeur) return 0; + if (e1->valeur < e2->valeur) e1 = e1->suivant; + else e2 = e2->suivant; + } + return 1; +} diff --git a/semestre 2/informatique/tme/semaine9/multi_ensembles.h b/semestre 2/informatique/tme/semaine9/multi_ensembles.h new file mode 100644 index 0000000..63c13aa --- /dev/null +++ b/semestre 2/informatique/tme/semaine9/multi_ensembles.h @@ -0,0 +1,16 @@ +typedef struct _element_t element_t; +struct _element_t{ + int valeur; + int frequence; + element_t *suivant; +}; + +element_t *Recherche_val(element_t *ensemble, int val); +element_t *Ajout_tete_ensemble(element_t *ensemble, int val, int freq); +element_t *Ajout_ensemble_trie(element_t *ensemble, int val, int freq); +element_t *Supprime_total_element_ensemble(element_t *ensemble, int val); +element_t *Supprime_element_ensemble(element_t *ensemble, int val); +void Affiche_ensemble(element_t *ensemble); +element_t * Creation_ensemble(int n); +int Inclus(element_t* sub, element_t *ens); +int Intersection_vide(element_t *e1, element_t *e2); diff --git a/semestre 2/informatique/tme/semaine9/test_multi_ensembles.c b/semestre 2/informatique/tme/semaine9/test_multi_ensembles.c new file mode 100644 index 0000000..d141210 --- /dev/null +++ b/semestre 2/informatique/tme/semaine9/test_multi_ensembles.c @@ -0,0 +1,24 @@ +#include <stdio.h> +#include "multi_ensembles.h" + +element_t *CreationMultiEnsemble(int deb, int n, int freq){ + element_t *liste=NULL; + int i; + + for (i=deb+n-1; i >=deb; i--) { + liste=Ajout_tete_ensemble(liste,i,freq); + } + return liste; +} + +int main() { + element_t *ensemble1= CreationMultiEnsemble(1,20,1); + element_t *ensemble2= CreationMultiEnsemble(5,10,2); + Affiche_ensemble(ensemble1); + printf("====\n"); + Affiche_ensemble(ensemble2); + printf("====\n"); + printf("%d\n",Intersection_vide(ensemble1, ensemble2)); + printf("%d\n",Intersection_vide(ensemble2, ensemble1)); + return 0; +} |