Théories des graphes et applications
NPcomplet
-
mpmp93 Messages postés 6648 Date d'inscription Statut Membre Dernière intervention -
mpmp93 Messages postés 6648 Date d'inscription Statut Membre Dernière intervention -
Bonsoir à tous !
Dans le cadre d'un dossier que je dois faire, je souhaite m'intéresser à la théorie des graphes et surtout au côté probabiliste de certains algorithmes.
Je souhaite partir d'un problème assez concret que même quelqu'un qui n'a aucune connaissance en Mathématiques/Informatique peut comprendre (un problème de la vie réelle par exemple, ou quelque chose d'assez compréhensible), pour à partir de là développer mon exposé sur comment traiter ce problème, et faire mes recherches.
Seulement, je ne vois pas les problèmes utiles auxquels je peux m'intéresser et auxquels la théorie des graphes peut répondre. En fait, je ne sais pas de quel problème je peux partir. Quels sont les problèmes courants/originaux pratiques auxquels la théorie des graphes peut répondre ?
Merci d'avance et bonne soirée !
Paul.
Dans le cadre d'un dossier que je dois faire, je souhaite m'intéresser à la théorie des graphes et surtout au côté probabiliste de certains algorithmes.
Je souhaite partir d'un problème assez concret que même quelqu'un qui n'a aucune connaissance en Mathématiques/Informatique peut comprendre (un problème de la vie réelle par exemple, ou quelque chose d'assez compréhensible), pour à partir de là développer mon exposé sur comment traiter ce problème, et faire mes recherches.
Seulement, je ne vois pas les problèmes utiles auxquels je peux m'intéresser et auxquels la théorie des graphes peut répondre. En fait, je ne sais pas de quel problème je peux partir. Quels sont les problèmes courants/originaux pratiques auxquels la théorie des graphes peut répondre ?
Merci d'avance et bonne soirée !
Paul.
A voir également:
- Théorie des graphes applications
- Application pour cacher des applications - Guide
- Comment regrouper des applications sur android - Accueil - Guide Android
- Comment installer des applications sans google play store - Guide
- Comment mettre en veille des applications sur pc - Guide
- Faut-il vider le cache des applications - Guide
2 réponses
Il y a les problèmes de cheminement par exemple utilisés par les GPS ou des sites qui calcule les itinéraires comme Google Maps. Le problème de tournées de véhicules est également assez simple à comprendre, il peut par exemple s'appliquer à un livreur de journaux.
Il y en a bien sûr d'autres, je donne ces deux là car ils sont vraiment faciles à comprendre pour un néophyte, mais il y en a d'autres.
Il y en a bien sûr d'autres, je donne ces deux là car ils sont vraiment faciles à comprendre pour un néophyte, mais il y en a d'autres.
Bonjour,
Un très bon exemple, les problèmes liés aux "workflow", les flux de tâches. Un bon exemple c'est les graphes de tâches concurrentes, par exemple dans la construction d'un immeuble:
- on fait les fondations: délai, coûts, moyens
- ensuite, on fait les murs: ....idem ci-dessus...
Une fois les murs faits, on peut poser la plomberie et les murs.
Dans mon exemple, il est évident qu'on en peut pas poser les fenêtres avant d'avoir les murs. De même, il est physiquement impossible de construire les murs avant d'avoir les fondations.
Dans l'ordonnancement de la construction, il y a donc des contraintes de précédence:
- quelle activité doit être achevée avant de passer à la suivante,
- quelles activités peuvent être exécutées simultanément,
Ensuite, il y a le problème des ressources: si les ouvriers sont multi-compétents mas pas assez nombreux, ils ne pourront pas faire la plomberie et poser les fenêtres. A l'inverse, si on fait appel à des sous-traitants, ils peuvent travailler simultanément. Ces contraintes ont une incidence directe sur les délais d'achèvement à chaque phase de la construction, donc sur la date d'achèvement des travaux...
Une autre incidence est le coût global qui sera la somme des coûts de chaque phase.
JE vous laisse cogiter sur ce type de problème qui peut exploiter la théorie des graphes.
Cdlt
Un très bon exemple, les problèmes liés aux "workflow", les flux de tâches. Un bon exemple c'est les graphes de tâches concurrentes, par exemple dans la construction d'un immeuble:
- on fait les fondations: délai, coûts, moyens
- ensuite, on fait les murs: ....idem ci-dessus...
Une fois les murs faits, on peut poser la plomberie et les murs.
Dans mon exemple, il est évident qu'on en peut pas poser les fenêtres avant d'avoir les murs. De même, il est physiquement impossible de construire les murs avant d'avoir les fondations.
Dans l'ordonnancement de la construction, il y a donc des contraintes de précédence:
- quelle activité doit être achevée avant de passer à la suivante,
- quelles activités peuvent être exécutées simultanément,
Ensuite, il y a le problème des ressources: si les ouvriers sont multi-compétents mas pas assez nombreux, ils ne pourront pas faire la plomberie et poser les fenêtres. A l'inverse, si on fait appel à des sous-traitants, ils peuvent travailler simultanément. Ces contraintes ont une incidence directe sur les délais d'achèvement à chaque phase de la construction, donc sur la date d'achèvement des travaux...
Une autre incidence est le coût global qui sera la somme des coûts de chaque phase.
JE vous laisse cogiter sur ce type de problème qui peut exploiter la théorie des graphes.
Cdlt