Idées de Projets en théorie des graphes ou autres.

**Iori Yagami** · 12/10/2007, 01h54

Bonjour, je suis étudiant en troisième année dans une institut similaire à INSA Lyon. cependant, pour continuer mes études au cycle ingénieur, je doit dabord passer un concours sur dossier et me préparer un mini-projet.

le problème est que je cherche encore un sujet pour le mini projet.. j'essai de m'ouvrir sur tous les domaines possibles..
J'aime pas le domaine de gestion, mais j'aimerai bien faire quelque chose qui dévoile mes capacité en informatiques.. j'ai pensé à la théorie des graphes, par exemple une application qui gère une réseau de Bus, il peut prédire combien faut il de machines pour un tel circuit ou telle période de la journée etc..
ça m'a l'air une bonne idée, mais elle est un peu difficile.. j'aimerai bien appliquer la théorie des graphes au réseaux informatiques, mais je ne connais pas des informations dans cette idée...

Sinon, Java et 3D ce serait trés sympa.. slp, si vous avez des idée qui peuvent encore développer une idée de projet.. dites le moi et merci d'avance!

**sidahmed** · 12/10/2007, 04h52

Bonjour,

tu peux, par exemple, considérer les villes d'un pays sous forme de carte géographique, voire plusieurs pays, et le visiteur d'un pays choisit deux villes A et B, il aura, par exemple, les 5 à 10 chemins les plus courts menant de la ville A à B, histoire d'économiser son argent pour les déplacements.

Enfin, c'était juste une petite proposition ! Bon courage.

Cordialement,
Sidahmed

**millie** · 12/10/2007, 17h42

Un petit projet qui semble simple mais qui finalement peut se reveler très ardu :

On dispose d'un graphe orienté en entrée. Le but du projet est de permettre d'obtenir le nombre minimal d'arête à ajouter afin que le graphe soit fortement connexe.

Même si ça semble purement théorique, il y a des applications amusantes. Supposons que l'on dispose d'un grand nombre de format d'image (jpg, bmp, svg, gif...) mais que l'on ne dispose que de quelques applications de conversion (jpb->bmp, svg->gif, gif->bmp), on pourrait souhaiter savoir le nombre minimal (et lesquels) de programme à développer pour pouvoir convertir n'importe quoi en n'importe quoi (ce qui est moins évident quand il y a des milliers de format).

On peut se douter que la difficulté principale est de démontrer que notre algorithme fournie effectivement le nombre minimal d'arête.

**Iori Yagami** · 12/10/2007, 23h19

je vous remercie tout les deux pour votre attention. Je voudrai ajouter quelques remarques.
sidahmed, c'est bien comme idée, mais si on doit la prendre au sérieux, on va aboutir à un système de cartes en GRPS.. ce qui est presque impossible vu la periode estimée pour réaliser le mini projet, et le niveau que j'ai. (bac +2 et c'est ma 3ieme année)

millie, merci pour les idées. trés interessante, surtout l'idée de conversion d'images. en fait, c'est ce que je voulais au juste, pas la théorie des graphes en elle meme, mais plutot ses applications.
Mais je voudrai vous poser quelques questions, puisque -apparement- vous vous interessez au sujet des images.
d'abord, pour une telle application, est ce que je dois moi meme programmer les convertisseurs d'un type à un autre, ou est ce que je dois retrouver sur internet des fichiers de conversation qui feront l'affaire, et que je me contente juste d'ordonner la transition d'un type à un autre? dans ce cas, cela devient un peu legers non? et puis, est ce que je peux retrouver des centaines de types de conversations?
merci

**millie** · 13/10/2007, 09h09

En fait, je ne pensais pas à l'application en elle même, mais au problème théorique précédent (à savoir trouver le nombre d'arête minimal pour rendre le graphe fortement connexe). Maintenant, ça ressemble à un petit exercice, mais qui est en fait assez difficile si l'on souhaite être sûr de notre méthode (si tu ne l'avais pas remarqué, tu vas vite tomber dans beaucoup de notion de mathématiques pour faire ça).

Mais sur internet, normalement, il y a déjà des logiciels ou des bibliothèques qui convertissent à peu près n'importe quoi en n'importe quoi, donc je ne pensais pas particulièrement porter l'attention là dessus, je donnais juste un exemple

**Iori Yagami** · 13/10/2007, 22h43

J'ai compris millie, je vous remercie pour votre idée. elle est interessante. je vais essayé de chercher plus. cependant, je vais laisser le sujet ouvert (n'est résolu) juste pour laisser la porte ouverte à de nouvelles idées..

**acacia** · 14/10/2007, 20h34

l'idée que propose millie est excellente, seulement tu n'as pas à te soucier de l'application qui convertit un bmp->jpg ou autre chose, ce qui t'intéresse dans le cadre de la théorie des graphes est de trouver le plus court chemin,essaye de voir avec l'algorithme de Dijkstra.

**millie** · 14/10/2007, 20h50

Envoyé par acacia

l'idée que propose millie est excellente, seulement tu n'as pas à te soucier de l'application qui convertit un bmp->jpg ou autre chose, ce qui t'intéresse dans le cadre de la théorie des graphes est de trouver le plus court chemin,essaye de voir avec l'algorithme de Dijkstra.

Non, dans le mini projet que je propose, il n'y a pas de recherche de plus court chemin

**acacia** · 14/10/2007, 21h02

Envoyé par millie

Non, dans le mini projet que je propose, il n'y a pas de recherche de plus court chemin

oui c'est vrai!

ça pourrait être une idée aussi

**Iori Yagami** · 14/10/2007, 21h15

Bonjour Cacia,

l'idée que propose millie est excellente

oui je le reconnais.

ce qui t'intéresse dans le cadre de la théorie des graphes est de trouver le plus court chemin,essaye de voir avec l'algorithme de Dijkstra

Je le sais, d'ailleurs je ne sais pas pourquoi millie n'est pas d'accord avec ça.

Mais je crois avoir trouvé une idée plus interessante : Un administrateur réseau. il peut reconnaitre tous les clients du réseaux et modéliser un schemas approprié. il peut bien évidement gérer tous les clients selon une interface assez simple. et peut aussi donner des sollutions concernant des problemes de connexion ou de conception. Qu'est ce que vous en pensez?

**acacia** · 14/10/2007, 21h34

Envoyé par Iori Yagami

Bonjour Cacia,

oui je le reconnais.

Je le sais, d'ailleurs je ne sais pas pourquoi millie n'est pas d'accord avec ça.

Mais je crois avoir trouvé une idée plus interessante : Un administrateur réseau. il peut reconnaitre tous les clients du réseaux et modéliser un schemas approprié. il peut bien évidement gérer tous les clients selon une interface assez simple. et peut aussi donner des sollutions concernant des problemes de connexion ou de conception. Qu'est ce que vous en pensez?

oui c'est une bonne idée aussi d'orienter tes connaissance en théorie des graphes vers le domaine des réseaux, c'est très important, et tu as pas mal de ressources tu pourras te documenter là-dessus.

**millie** · 14/10/2007, 21h46

Envoyé par Iori Yagami

Je le sais, d'ailleurs je ne sais pas pourquoi millie n'est pas d'accord avec ça.

Je dis juste que l'algorithme du plus court chemin est totalement inutile pour l'idée de mon mini projet. Il n'y a aucune recherche du plus court chemin, on cherche juste à rendre le graphe fortement connexe, sans forcement chercher à minimiser les chemins

**sidahmed** · 15/10/2007, 00h52

Bonjour,

C'est vrai que dans l'idée de milie, y a pas de recherche de chemins minimas, il faut peut-être jeter un coup d'œuil sur les points d'articulation, isthmes, composante connexe, composante fortement connexe et graphe réduit.

Bon courage et à bientôt.

Cordialement,
Sidahmed.

**acacia** · 15/10/2007, 11h58

je pensais avoir corrigé mon erreur en pensant que dans l'idée de millie il y avait une recherche du plus court chemin, donc maintenant, je sais que dans l'idée de millie il n'y a aucune recherche du plus court chemin et pas besoin d'algo de Djikstra

même si je trouve l'idée de travailler avec l'algorithme de Djikstra bonne

**sidahmed** · 15/10/2007, 16h16

Bonjour,

Envoyé par acacia

je pensais avoir corrigé mon erreur en pensant que dans l'idée de millie il y avait une recherche du plus court chemin, donc maintenant, je sais que dans l'idée de millie il n'y a aucune recherche du plus court chemin et pas besoin d'algo de Djikstra

même si je trouve l'idée de travailler avec l'algorithme de Djikstra bonne

Si l'auteur veut appliquer l'algorithme de Dijkstra voire de Ford, il n'a qu'à implémenter l'idée que j'avais proposée !

Cordialement,
Sidahmed

**Iori Yagami** · 16/10/2007, 11h36

tu pourras te documenter là-dessus.

Connaissez vous des liens interessants? j'en serais reconnaissant.

Je dis juste que l'algorithme du plus court chemin est totalement inutile pour l'idée de mon mini projet. Il n'y a aucune recherche du plus court chemin, on cherche juste à rendre le graphe fortement connexe, sans forcement chercher à minimiser les chemins

Si, par exemple, je peux trouver deux solutions pour convertir une image TIFF en GIF, je dois chercher laquelle me prends le moins de conversions intermediaires possibles non? et puis pour la collecte des conversions directes, c'est vrai, je dois assurer un graphe fortement connexe de sorte que je peux convertir n'importe quoi en n'importe quoi.

même si je trouve l'idée de travailler avec l'algorithme de Djikstra bonne

Elle n'est bonne que lorsqu'elle est executée par une machine, et non pas par mon stylo! On nous a tué d'exercices d'application de cet algorithme :s

**acacia** · 16/10/2007, 17h51

Envoyé par Iori Yagami

Connaissez vous des liens interessants? j'en serais reconnaissant.

il faut d'abord préciser ce que tu veux faire.

Envoyé par Iori Yagami

Si, par exemple, je peux trouver deux solutions pour convertir une image TIFF en GIF, je dois chercher laquelle me prends le moins de conversions intermediaires possibles non? et puis pour la collecte des conversions directes, c'est vrai, je dois assurer un graphe fortement connexe de sorte que je peux convertir n'importe quoi en n'importe quoi.

c'était exactement l'idée à laquelle j'ai pensé

Envoyé par Iori Yagami

Elle n'est bonne que lorsqu'elle est executée par une machine, et non pas par mon stylo! On nous a tué d'exercices d'application de cet algorithme :s

tu ne vas tout de même pas présenter tout ton projet seulement par ton stylo

à mon avis, tu dois prendre le facteur temps en considération, plus tu as du temps, plus tu pourras t'élargir et exposer divers algorithmes

**Iori Yagami** · 19/10/2007, 13h54

Bjr!

Acacia, tu m'a dis que je pourrai me documenter la dessus, tu veux dire à propos de l'administration réseaux non? c'est pour ça je t'avais demandé si tu connais des liens utiles.

Bon, je me suis fixé une idée. Un administrateur réseau qui peut scanner tout le réseau et le modéliser graphiquement. L'interface graphique doit être aussi simple que possible, et doit fournir le plus possible de services, comme par exemple explorer tout les clients, les controler, voir leurs activités, etc.
Il doit aussi gérer le flux des données transmis et s'il le faut priver un client d'un certain service (ftp par exemple ou accès internet).

voila, si vous avez des suggestions a propos du sujet, j'en serai ravi