Idées de Projets en théorie des graphes ou autres. [Résolu]

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

Citation:

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

Citation:

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,

Citation:

l'idée que propose millie est excellente

oui je le reconnais.

Citation:

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

Citation:

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

Citation:

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,

Citation:

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

Citation:

tu pourras te documenter là-dessus.

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

Citation:

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.

Citation:

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

Citation:

Envoyé par Iori Yagami

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

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

Citation:

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é

Citation:

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

acacia · 21/10/2007, 21h11

Salut!

au fait, je ne suis pas très branchée là-dessus

exemple: les algorithmes de routage

Iori Yagami · 22/10/2007, 11h42

Merci comme même acacia

12/10/2007, 01h54	#1
Iori Yagami Membre du Club Iori Yagami Étudiant Inscription : mai 2007 Messages : 103 Détails du profil Informations personnelles : Nom : Iori Yagami Âge : 25 Informations professionnelles : Activité : Étudiant Informations forums : Inscription : mai 2007 Messages : 103 Points : 50 Points : 50	Idées de Projets en théorie des graphes ou autres. 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!
	00

12/10/2007, 17h42	#3
millie Rédacteur/Modérateur Inscription : juin 2006 Messages : 6 929 Détails du profil Informations personnelles : Localisation : Luxembourg Informations forums : Inscription : juin 2006 Messages : 6 929 Points : 6 714 Points : 6 714	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. __________________ Je ne répondrai à aucune question technique en privé
	00

13/10/2007, 09h09	#5
millie Rédacteur/Modérateur Inscription : juin 2006 Messages : 6 929 Détails du profil Informations personnelles : Localisation : Luxembourg Informations forums : Inscription : juin 2006 Messages : 6 929 Points : 6 714 Points : 6 714	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 __________________ Je ne répondrai à aucune question technique en privé
	00

12/10/2007, 04h52	#2
sidahmed Inactif Inscription : mars 2006 Messages : 353 Détails du profil Informations forums : Inscription : mars 2006 Messages : 353 Points : 241 Points : 241	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
	00

12/10/2007, 23h19	#4
Iori Yagami Membre du Club Iori Yagami Étudiant Inscription : mai 2007 Messages : 103 Détails du profil Informations personnelles : Nom : Iori Yagami Âge : 25 Informations professionnelles : Activité : Étudiant Informations forums : Inscription : mai 2007 Messages : 103 Points : 50 Points : 50	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
	00

13/10/2007, 22h43	#6
Iori Yagami Membre du Club Iori Yagami Étudiant Inscription : mai 2007 Messages : 103 Détails du profil Informations personnelles : Nom : Iori Yagami Âge : 25 Informations professionnelles : Activité : Étudiant Informations forums : Inscription : mai 2007 Messages : 103 Points : 50 Points : 50	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..
	00

14/10/2007, 20h34	#7
acacia En attente de confirmation mail Étudiant Inscription : août 2007 Messages : 419 Détails du profil Informations professionnelles : Activité : Étudiant Informations forums : Inscription : août 2007 Messages : 419 Points : 214 Points : 214	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.
	00

15/10/2007, 00h52	#13
sidahmed Inactif Inscription : mars 2006 Messages : 353 Détails du profil Informations forums : Inscription : mars 2006 Messages : 353 Points : 241 Points : 241	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.
	00

15/10/2007, 11h58	#14
acacia En attente de confirmation mail Étudiant Inscription : août 2007 Messages : 419 Détails du profil Informations professionnelles : Activité : Étudiant Informations forums : Inscription : août 2007 Messages : 419 Points : 214 Points : 214	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
	00

19/10/2007, 13h54	#18
Iori Yagami Membre du Club Iori Yagami Étudiant Inscription : mai 2007 Messages : 103 Détails du profil Informations personnelles : Nom : Iori Yagami Âge : 25 Informations professionnelles : Activité : Étudiant Informations forums : Inscription : mai 2007 Messages : 103 Points : 50 Points : 50	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
	00

21/10/2007, 21h11	#19
acacia En attente de confirmation mail Étudiant Inscription : août 2007 Messages : 419 Détails du profil Informations professionnelles : Activité : Étudiant Informations forums : Inscription : août 2007 Messages : 419 Points : 214 Points : 214	Salut! au fait, je ne suis pas très branchée là-dessus exemple: les algorithmes de routage
	00

22/10/2007, 11h42	#20
Iori Yagami Membre du Club Iori Yagami Étudiant Inscription : mai 2007 Messages : 103 Détails du profil Informations personnelles : Nom : Iori Yagami Âge : 25 Informations professionnelles : Activité : Étudiant Informations forums : Inscription : mai 2007 Messages : 103 Points : 50 Points : 50	Merci comme même acacia
	00

Outils de la discussion
Afficher une version imprimable Envoyer un lien vers cette page par email