Rockleader a écrit:A l'époque où j'ai passé mon bac il y a 4 ans en Ts, lalgorithmique avait été inclus au programme en math, donc je ne pense pas que l'on puisse les dissocier l'un de l'autre à présent.
Je trouve que ce sont des démarches très différentes intellectuellement. L'algorithmique, on tâtonne, on réajuste, les mathématiques, on émet des conjectures et on démontre (mais je ne connais pas trop l'algorithmique qui n'était pas au programme il y a 15 ans).
Rockleader a écrit:Pour ce qui est des définition, j'ai jamais trop aimé ce genre de principe ou on donne des définitions fausses.
Je peux comprendre l'idée d'avoir des définition incomplète, par exemple, dire qu'il n'y a aucune solution à une équation lorsque le discriminant est négatif, tant que les élèves ont pas vu les complexes, c'est tout à fait légitime. Mais, pas de définition comme celle là, arc, arrête, et bien disons que je vois pas ce que ça apporte de ne pas donner une définition complète.
Pour prendre un exemple simple. Définition d'un graphe complet tiré d'un livre de TeES : "un graphe est dit complet si tous les sommets de ce graphe sont adjacents."
Mais alors : cette définition s'applique-t-elle aux graphes orientés, non orientés, les 2 ?, le graphe peut-il être multigraphe (plusieurs arêtes entre 2 sommets) ? un graphe avec un seul sommet est-il considéré complet ?... Il faut aller à la pêche aux exemples et exercices pour trancher.
L'enseignement en ES est plus intuitif qu'en S, mais quand même... ce n'est pas très satisfaisant.
Autre exemple : "une chaîne est une liste ordonnée de sommets telle que chaque sommet de la liste soit adjacent au suivant". Mais si le graphe est multigraphe, on peut emprunter plusieurs arêtes entre 2 sommets, ce n'est plus la même chaîne ou c'est la même ?
Un prof doit savoir répondre aux questions qu'il se pose lui-même.
Rockleader a écrit:Je vois pas vraiment la différence en fait, je n'ai peut être pas compris l'analogie des portes et des salles.
Disons que pour moi une arrête, ou un arc représentera un couloir. Un état du graphe représentera les salles.
Le genre de problème que je traitais l'an dernier nous faisait déterminer comment passer dans tous les états avec un coup minimal. Donc passer dans chaque salle en faisant le moins de pas possible ce qui est pour le coup je trouve plus logique.
Ici, on évite les cycles, donc on passe pas plus d'une fois par une salle.
Il me semble que dans un graphe tiré de la vie courante (le plus fréquent en ES), on est plus intéressé par les sommets que par les arêtes (qui ne sont que des moyens d'accéder aux sommets). Mais ce n'est peut-être effectivement pas le cas pour des problèmes d'optimisation.
Rockleader a écrit:Ici, on évite les cycles, donc on passe pas plus d'une fois par une salle.
Une autre vision du problème autoriserait les cycles à conditions qu'ils déterminent le plus court chemin. On a pas travaillé là dessus, mais je vois pas en quoi c'est pas possible, ce doit pas être bien sorcier de pondérer le coup d'un arc par deux pour prendre l'allez retour et d'estimer la moyenne de pas en fonction de chaque situation. Je veux dire par là, il n'y a pas de définition bien préscise là dessus c'est vrai, mais mathématiquement parlant c'est absolument pas un problème de trouver un résultat de ce genre, au final ce n'est ni plus ni moins que faire la moyenne des plus court chemins sans cycles, et de comparer cette moyenne avec les pires cas contenant des cycles, à ce moment là il faut simplement prendre l'hypothèse qu'une personne ne vas pas passer plusieurs fois dans un cycle si cela ne lui permet pas d'arriver dans une salle plus rapidement.
Mais les plus courts chemins sont déterminés par l'algorithmique, donc la moyenne des plus courts chemins aussi, tant qu'à faire ?
Enfin, il me semble que la théorie des graphes se coupe d'une grande partie des problèmes, en considérant qu'une arête ne peut avoir que 2 extrémités (et pas 3 ou plus). Dès lors, les arêtes et les sommets seraient interchangeables, et ne seraient que les 2 faces du même problème.