Dans la vie j'aime écrire. Et j'aime les maths. Bon, ça dépend quels domaines en particuliers (détails à venir).
Les maths sont pleines de choses bizarres. Vraiment bizarres. Donc marrantes. Intrigantes. Stupéfiantes. Renversantes. Bouleversifiant...
Gudule : ce ne serait pas nécessaire si vous n'aviez pas mangé Alcibiade, maître. Notre dernier yaourt. Pffff.
Parce que je suis très exigeant, Gudule doit passer par un certain nombre de magasins différents. La vitesse de Gudule quand il va d'un magasin A à un magasin B est constante (nous supposons que Gudule est un larbin parfait, et que même chargé comme un mulet, cela n'influe pas sur ses capacités physiques). Par ailleurs, à la fin de son parcours, il doit revenir à la maison, et j'exige qu'il fasse tout ça en un temps limité (mettons deux heures).
Gudule : je suis exploité. Signez la pétition pour me libérer.
---------
Libérez Gudule
Bonjour, je m'appelle Gudule. Vous me connaissez sans doute parce que je vous fais rire dans PJAM. Mais sachez que j'ai beau être un personnage fictif actuellement transformé en tubercule par une manipulation ratée du Flying Tortellini Monster, je suis comme vous. J'ai soif de liberté. Aidez-moi à accomplir mon rêve. Aidez-moi à me libérer définitivement du rôle de larbin dans lequel je suis enfermé, et à devenir écrivain.
En signant cette pétition, vous permettrez à mon combat d'être reconnu auprès de la classe politique. Vos donations me permettront aussi de me faire un max de thunes et de publier ma chronique en format broché.
Je compte sur vous.
Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.
Comme Gudule est intelligent, il va essayer d'optimiser son parcours à l'aide d'un algorithme. Les magasins sont les sommets d'un graphe, et les arêtes entre eux sont les rues, pondérées selon le temps mis à les parcourir.
(Gudule commence à calculer)
Gudule : il doit forcément exister un algorithme sympa pour résoudre ce problème d'optimisation.
FTM(regarde par terre – il aurait regardé ses pieds s'il en avait) : hem, hem.
Ce problème dit « du voyageur de commerce » peut être posé de la manière suivante : étant donné le graphe des magasins, et une longueur D, existe-t-il un chemin de longueur totale inférieure à D ? Il est possible de le résoudre, bien sûr : prenez tous les chemins possibles et regardez. Mais est-il possible de faire mieux ? Disons, de faire beaucoup mieux ? Meh... c'est une question ouverte...
La théorie de la complexité classe les problèmes comme celui-ci selon l'existence ou non d'algorithmes permettant de les résoudre en un certain nombre d'opérations. Par exemple, le problème :
Étant donné n nombres, ces nombres sont-ils triés ?
Est « dans P », parce qu'il existe un algorithme avec un nombre polynomial d'opérations, moins de n au carré, pour le résoudre (vous savez trier les nombres rapidement).
Gudule : bien sûr, il faut définir proprement ce que sont les « opérations » considérées. En l'occurrence, quand vous triez des nombres, vous les comparez entre eux, et vous comptez le nombre de comparaisons faites. Quant à « polynomial », c'est juste une somme de puissances de n, la « taille » de l'entrée, au sens rigoureusement informatique du terme.
Tu m'enlèves les mots de la bouche, Gudule.
Gudule : nous sommes dans la même tête, maître.
Ah, j'avais oublié ce détail.
En revanche, le problème de Gudule faisant les courses :
Étant donné le graphe des magasins, Gudule peut-il faire les courses en moins de deux heures ?
Ben, on sait pas s'il est « dans P ». Et on a de fortes présomptions que non.
Un jour, un informathug vous dira que « dans P » équivaut à « efficace » ; bien sûr ce n'est pas vrai. Sur une entrée de taille n, faire n à la puissance 1000 opérations, c'est « dans P », mais ce n'est PAS efficace. À titre d'exemple, il existe des algorithmes qui testent si un nombre est premier, qui ne sont pas « polynomiaux », mais qui marchent très bien, et le jour où on en a trouvé un qui était polynomial, en fait, il était pas pratique. L'intérêt de la chose était surtout théorique.
Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.
Gudule : et qu'est-ce qui n'est pas polynomial, maître ?
Eh bien par exemple, un algorithme qui prend deux à la puissance n opérations, c'est pas polynomial, c'est exponentiel.
Gudule : on n'a pas encore vu l'exponentielle.
Dès qu'il y a « puissance n », c'est exponentiel, voilà. Et en tout cas c'est le mal.
