Forum général »
Travail théorie des graphes
1

Forums de discussion
Forum général
FPS

Bonjour à tous !

Le topic de Noldor m´a donné une petite idée ! en effet j´ai moi aussi un travail de recherche à faire au cours de l´année et à présenter à un concours, et même si toute la partie théorique est bouclée (définitions explications preuves... ) il est bien vu de coder ensuite entièrement les algorithmes cités.

Le sujet est la théorie des graphes, et plus précisément tout ce qui concerne les problèmes de flux pouvant transiter à travers un graphe avec une entrée et une sortie, et les algorithmes sont dikjtra (mal orthographié, mais c´est juste du parcours en largeur) et Ford-Fulkerson (résolution de flot max ).

Si quelqu´un se sent altruiste, non pas pour me le coder, il faut de toute façon que je le fasse moi-même et que je le maitrise, mais pour me guider un peu dans ma démarche je suis preneur :)

Biz !
Je vois pas trop comment te "guider", mais vu que j´ai eu cette matière le semestre passé je suis assez à jour sur les concepts, et je peux donc t´aider
Interprète ? interprète ? Couillère !

- Error 404, Hiryuu´s brain not found -
L´algorithme de Dijkstra est beaucoup plus documenté sur le web.
Je ne sais pas trop ce que tu souhaites comme infos sur la "démarche". En effet dans un premier temps il faut juste comprendre la méthode (purement logique) sans se préoccuper de l´aspect informatique.

Ensuite il faut écrire la méthode en "pseudo-code" (c´est à dire à base de conditions, boucles, etc... bref avec les briques essentielles de l´informatique indépendamment du langage de programmation).

Ou sinon tu récupères le pseudo code directement sur wikipedia ou ailleurs....

Après pour le codage il faudrait des questions un peu plus précises car là je ne sais pas trop ce dont tu as besoin...
Justement en fait pour l´instant j´ai tout l´aspect méthode, la logique, les preuves qu´il marche bien... mais je n´ai aucune idée de comment partir pour le coder ! C´est vrai qu´en me relisant ma question était assez vague ...

En fait j´ai compris le fonctionnement, à peu près le pseudo code mais j´aimerai savoir si il y a un langage privilégié pour le coder (en gros entre le caml, le maple et le C ) car un prof m´avait notamment dit que le C convenait assez bien pour gérer les files de priorité et dans quel ordre parcourir le graphe, ce que maple ne faisait pas (et donc que le code devenait beaucoup plus lourd), et justement si il y avait des manières "jolies" de l´implémenter autres que les grosses itérations successives bourrines (notamment pour ford-fulkerson ).

En fait, là ou je sèche c´est que je me débrouille dans tout ce qui est justement briques essentielles avec boucles tout ça mais à part traduire ces briques mot à mot dans un langage je pourrai difficilement faire autre chose, dans l´idéal ce serait donc voir comment utiliser de manière optimale le langage choisi.

Enfin, si j´arrive à boucler ceci convenablement et assez vite, coder une dernière partie, qui résoudrait d´elle-même le problème (peut-on augmenter la capacité max en ne modifiant qu´un seul arc), pour laquelle je n´ai trouvé aucun pseudo-code car c´est la partie "apport personnel" à proprement parler (en fait le principe est de gérer la notion de coupes "nulles" et de voir si leur intersection est réduite à un seul arc ou pas, ensuite on le balance sur le dernier graphe résiduel de Ford-Fulkerson et paf, ca fait des chocapics )
Les familles de langages :

Concernant le langage à privilégier, ce n´est pas tout à fait la bonne question. A savoir peu importe le langage en lui-même, ce qui a de l´importance c´est la "famille" de langages.

J´en distingue 3 principales :

1) Les langages procéduraux : tel le C
2) Les langages objets : tel le C++
3) Les langages d´IA : tel Prolog

NB : Tout ne rentre pas dans ces trois catégories comme l´assembleur par exemple (mais je doute que tu sois fou au point d´en faire ^^), cependant cela couvre plus de 90% des cas.

Te concernant seules les deux premières te concernent, toutefois la seconde n´a d´intérêt que pour un programmeur qui a de l´expérience et comprend la notion d´objets en programmation. Je parle en connaissance de cause, plein d´ingés sortis d´école ne savent toujours pas coder en "vrai" objet et font du procédural ...

Bref pour un débutant autant partir sur du procédural car tu n´explloiteras vraisemblablement pas correctement les avantages du codage en objets.

Choix du langage :

Pour avoir touché de nombreux langages, il y a peu de différences entre les langages d´une même famille. Cela reste avant tout de la syntaxe et par conséquent il n´y a pas de "meilleur" langage. Toutefois il y a des paramètres importants au moment de choisir, voici ceux qui me viennent en tête.

1) Ton expérience personnelle :

Si tu as codé beaucoup plus dans un langage plutôt que dans un autre, tu as acquis au fil de tes tests de l´expérience. Oui, oui un peu comme dans un MMORPG où tu montes les levels de ton perso ... Par conséquent si tu te sens plus à l´aise dans un langage c´est essentiel pour bien coder, car quand on débute sur un langage on "bidouille" pour faire tourner la solution, mais bien souvent on ignore les méthodes efficaces pour parvenir au résultat.

Petite anecdote : pas plus tard qu´il y a une semaine j´ai codé pour mon boulot un script PHP. Et pourtant aucun projet sur lequel je bosse n´utilise ce langage. Alors pourquoi un tel choix ? Tout simplement parce que c´était du code "jetable" pour accomplir une tâche technique. Et même si le PHP n´était pas le langage le plus adapté je savais que ce serait celui qui me demanderait le moins de temps pour coder.

2) La popularité :

Evites les langages "exotiques" du style caml, maple etc... Pourquoi alors que j´ai dit que les langages se valaient ? Et bien tout simplement parce que n´étant pas expert dans ces langages, tu buteras forcément à un moment ou à un autre sur un problème. A ce stade tu chercheras de l´aide, notamment sur le net. Et pas de bol pour les langages exotiques tu ne trouveras quasi rien en matière d´exemples, de préconisations ou encore de forums francophones avec des développeurs pour te répondre.

=> Bref pour le point numéro 2 mon conseil va directement vers le C !
=> Toutefois tu dois aussi tenir compte du premier point dans ton choix et là je ne peux pas répondre à ta place...

La morale de l´histoire :

Crois-moi on peut faire un code propre dans tous les langages. Et la réciproque est vraie et bien souvent c´est le code pourri qu´on voit partout y compris dans les applications professionnelles qui coûtent des millions.

Le langage objet est à première vue le plus adapté pour modéliser avec un code court et structué des problèmes complexes. Toutefois pour les novices mieux vaut dans un premier temps apprendre à bien coder en procédural.

Alors attention quand je parle de procédural, cela ne veut pas dire qu´on code tout d´un bloc comme un gros sale ^^ ... On fait des sous-fichiers avec des fonctions, des procédures etc...

Comment coder proprement ?

Difficile de résumer cela en quelques lignes d´autant qu´il n´y a pas de vérité absolue. Mais un code propre, c´est un code qui lorsqu´il est lu par un autre développeur que son auteur, parait compréhensible en quelques minutes.

Pour aider à bien coder :

1) Des commentaires, encore et toujours !
Avantage : même pour le développeur il peut se relire facilement et comprendre la logique du programme sans même regarder les instructions du code

2) Une décomposition de tous les problèmes en sous-problèmes aussi petits que possibles (chacun au final correspondant à une fonction ou une procédure).
Avantage : en cas de modification on se concentre sur une partie bien ciblée du code ce qui permet une meilleure abstraction de ce qui se passe autour. C´est donc plus simple à coder, à maintenir et surtout : à tester !

3) Faire des tests
Je sais que comme tout développeur débutant tu ne le feras pas, mais c´est une erreur... Car au début ça ira beaucoup plus vite sans, mais une fois le code ayant atteint un degré avancé de maturité tu feras la connaissance de "THE BUG" ! Oui cette bébête sournoise qui n´arrive que dans des cas étranges que l´on ne comprend pas... Et tu passeras des semaines à le chercher à coup de rustines pour faire tourner ton code, tout ça pour t´apercevoir d´une bétise qui serait parue évidente en ayant testé correctement ta fonction...
Je viendrais en complément de RavAge. Je suis d´accord sur le langage, je partirais aussi sur du C. Pourquoi ?

- Parce que non seulement il est procédural, ce qui correspond à ton problème, mais en plus il est en général rapide d´exécution (j´ai récemment codé un bout de programme qui faisait la même chose en C++ et en C, et en gros j´avais au moins un facteur 10 entre les deux sur le temps d´exécution...)

- Parce qu´il est assez simple à mettre en place. Il n´y a pas besoin de maîtriser des concepts comme la programmation objet pour l´utiliser.

- Au niveau de la popularité, ben, il est le langage le plus utilisé selon l´indice TIOBE, et pourtant il a 40 ans cette année...

Au niveau de la décomposition et des tests, apprends rapidement à faire des sous fonctions que tu pourras directement inclure dans un programme test, où tu pourras vérifier que la sortie est bonne par rapport à l´entrée que tu lui as donné (ça, c´est valable pour tous les langages procéduraux)

Si tu as besoin de conseils, n´hésite pas à demander, je serai content de te répondre ! (et je ne serai sûrement pas le seul)
Je ne dirais qu´une chose... (de pas vraiment objectif)

Le C c?est mal ... ça fait beaucoup mal à mes petits neurones !

Donc un bon conseil : Python ! Le Python c?est la vie ! Le Python c?est simple =D
Je ne dirais qu´une chose, d´encore moins objective que le post d´au dessus, change de voie avant de devenir fou...
Merci beaucoup pour toutes vos réponses :)

Après vous avoir relu je pense effectivement m´orienter vers du C "procédural" comme tu le dis Ravage, avec aussi l´avantage qu´il a l´air d´être assez universel, que j´ai déjà un peu codé dedans et que ça ne peut être que bien d´avoir de l´expérience en C !

Merci aussi pour les astuces à propos du code "clair" (commentaires etc ) car en fait, ce que je n´ai pas dit et qui est assez... absurde, mais qui vient du fait que très peu de gens choisissent l´info et que la plupart partent sur des maths pures ou de la physique pures, c´est que le code n´est pas testé et ne tourne jamais. Pour certaines écoles il faut le rendre dans un dossier qui est étudié à l´avance, mais je doute vraiment qu´ils s´amusent à recopier le code pour vérifier son fonctionnement, et dans d´autres il faut juste le donner à l´examinateur le jour de l´oral, il a donc 3 minutes pour se faire son idée dessus.

En résumé le plus important est vraiment de privilégier la lisibilité, et un code lisible sur support papier... A votre avis mieux vaut présenter tout d´un bloc à la suite (même si je ne le coderai pas comme ça chez moi ) ou alors se rapprocher de la présentation habituelle, en mettant les fonctions sur des annexes ?
tu me le donnerais a moi, ce que je préfèrerais c´est d´avoir le truc en global, avec un schémas de principe qui montre les interactions entre fonctions (du style uml) et une doc style javadoc (je connais pas l´équivalent en C) pour tes fonctions.

Comme ca quoi qu´il cherche, il sauras où le trouver, et rapidement.
Après, attends l´avis des autres, je suis loin d´être celui qui s´y connait le mieux.
Il n´y a pas d´équivalent à javadoc en C, en tout cas rien de standard. Le plus simple revient donc à ajouter pas mal de commentaires dans ton code pour décrire ce que fait chaque partie.

L´avantage de faire ça, c´est que celui qui lira ton code saura ce que tu souhaites faire dans ton code, même s´il n´est pas juste.

Pour ton code, créer des fonctions qui vont porter des noms explicites est toujours beaucoup plus clair que mettre ton code directement, surtout pour quelqu´un qui ne s´y connait pas forcément beaucoup.

Exemple tout bête, appeler une fonction de tri, qui est un truc classique en info, peut devenir difficilement compréhensible pour un non initié. Par exemple, cet algorithme :
      pour i de 2 à n
x ← T[i]
j ← i
tant que j > 1 et T[j - 1] > x
T[j] ← T[j - 1]
j ← j - 1
fin tant que
T[j] ← x
fin pour
C´est plus difficile de voir immédiatement qu´il s´agit d´un algo de tri par insertion si le code est directement collé dans ton programme plutôt que s´il est placé dans une fonction qui s´appelle triParInsertion().
Comme Ravage l´a dit, il faudrait dans un premier temps voir et bien comprendre le pseudo-code.

Ensuite pour passer dans le code lui-même (j´approuve pour le choix du C, je pense pas que l´orienté-objet soit vraiment nécessaire pour un tel problème), il te faut d´abord voir quel genre de données tu reçois (input) et quel genre de données tu veux renvoyer (output), quel genre de structures de données tu vas utiliser, si tu as besoin de code additionnel pour celles-ci, etc.

Une fois que tu as une bonne idée de comment tu veux mettre ces choses en place, tu peux commencer à coder en t´aidant du pseudo-code. Un bon conseil toutefois que je vois trop de monde ne pas faire :Sauve ton code régulièrement, COMPILE dès que tu peux et teste le plus souvent possible. Je vois trop de personnes pondre des centaines de lignes de code et ensuite passer 2 journées à debugger.

Et autrement, comme l´a bien dit Rav, beaucoup de commentaires, de façon à ce que ton code puisse être compréhensible par d´autres personnes
Pour un équivalent de javadoc en C il y a Doxygen qui a sa propre syntaxe mais qui comprend aussi la syntaxe de javadoc pour les habitués.

Un outils très pratique à prendre en main très tôt pour avoir une bonne et belle doc.

https://fr.wikipedia.org/wiki/Doxygen