GoupillWiki - nsi:tds:graphes

classification_hierarchique_ascendante

Anonymous (anonymous@undisclosed.example.com) — 2022-04-03T13:40:37+00:00

Classification hiérarchique ascendante Considérons une population d'individus. Pour chaque individu, nous avons prélevé deux attributs que l'on notera x et y. Cela nous permet de représenter les individus par un nuage de points dans un repère Oxy.$\frac{n_1\cdot n_2}{n_1 + n_2} C_1C_2$$C_1C_2$$C_1$$C_2$

codage_de_huffman

Anonymous (anonymous@undisclosed.example.com) — 2022-04-03T13:37:20+00:00

Codage de Huffman Compression Exemple simple Considérons le texte ha ha ho ho qui comporte n = 11 caractères -- en comptant les espaces. On souhaite coder ce texte pour en faire un fichier. On pourrait choisir le codage iso-8859-1. Dans ce codage,$2^1 < 4 \leqslant 2^2$$\frac{414}{1496} \simeq 28\,\%$

codage_de_prufer

Anonymous (anonymous@undisclosed.example.com) — 2023-02-26T17:11:56+00:00

Codage de Prüfer Page Wikipedia Prenons un arbre dont les sommets de taille $n$ dont les sommets sont étiquetés de $0$ à $n-1$. Le codage de Prüfer ne pourra contenir que des nombres entiers de $0$ à $n-1$ et il formera une séquence de $n-2$ nombres. Partant d'un arbre, on peut établir le code de Prüfer. Dans l'autre sens, partant du code, on peut reconstruire l'arbre.$0$$7$$n = 8$$(1, 2, 0, 4, 1, 2)$$n-2$$8^6 = 262\,144$$n^{n-2}$$n$$T$$n$$0$$n-1$$P$$(1, 2, 0, 4, 1, 2)$$P$$n-2$$0$$n-1$$T$$n$$…

coloration_antennes

Anonymous (anonymous@undisclosed.example.com) — 2023-02-08T20:41:06+00:00

Attribution de fréquences - Coloration Dans une ville on place des antennes GSM. Ces antennes sont plus ou moins puissantes et elles sont placées au gré des accords avec les résidents des immeubles où elles sont implantées. Elles ne sont donc pas placées avec la régularité d'un quadrillage. De plus, on peut être amené à placer plus d'antennes dans les zones de forte affluence.$$x = (longitude_1 - longitude_2)\cdot\cos\left(\frac{latitude_1 + latitude_2}{2}\cdot \frac{2\pi}{360}\right) \cdot 111…

implementation_abr

Anonymous (anonymous@undisclosed.example.com) — 2022-10-17T08:45:33+00:00

Annuaire avec Arbre Binaire de Recherche On souhaite créer une application d'annuaire qui permettrait : * d'insérer des individus * modifier leurs informations, * supprimer des individus, Tout cela avec l'efficacité permise par les arbres binaires de recherche : ABR.$data \mapsto key$

plus_court_chemin

Anonymous (anonymous@undisclosed.example.com) — 2022-11-28T08:56:34+00:00

Plus court chemin sur une carte Problème posé Vous disposez de données décrivant les routes du 13e arrondissement de Paris. On souhaite se donner un point de départ, un point d'arrivée et calculer un plus court chemin respectant les routes indiquées dans les fichiers.$$distance = 111\,120 \cdot \sqrt{\left[(lng_1 - lng_2)\cdot\cos\left(\frac{lat_1 + lat_2}{360}\cdot\pi\right) \right]^2 + \left[lat_1 - lat_2\right]^2}$$

probleme_des_deux_recipients

Anonymous (anonymous@undisclosed.example.com) — 2022-04-03T13:43:33+00:00

Problème des deux récipients Présentation d'un exemple On considère le problème classique de deux récipients de 7 litres et 5 litres, à côté d'un source d'eau. Les récipients ne sont pas gradués. Tout ce qu'on peut faire ses les remplir à ras-bord, les vider, les transvaser l'un dans l'autre.$d$$d = 1$$k\cdot d$

regex_automate

Anonymous (anonymous@undisclosed.example.com) — 2022-04-03T13:39:10+00:00

Automate reconnaissant une expression Présentation Il est fréquent que l'on doive reconnaître dans un texte la présence d'expressions respectant un certain modèle. Le cas typique est la reconnaissance d'une adresse mail : On voudrait reconnaître quelque chose comme :