Une citation mémorable du film Proof

Avant que quiconque ne m'envoie des messages haineux, je tiens à dire que je n'ai pas aimé ce film. La performances des acteurs est mauvaise, l'histoire, peu enivrante. Certaines personnes ont comparé ce film à A Beautiful Mind, ce que je n'arrive pas à comprendre. Outre le fait que les deux films parlent de mathématiciens un peu cinglés, il n'y a rien en commun entre eux : un est un chef-d'oeuvre, l'autre est un film dont on aurait pu se passer.

Les seuls points positifs de Proof sont la présence, toujours réjouissante, de Anthony Hopkins (ou devrais-je dire Sir Anthony Hopkins) dont la performance est merveilleuse, et cette citation du mathématicien fou :

Let X equal the quantity of all quantities of X. Let X equal the cold. It is cold in December. The months of cold equal November through February. There are four months of cold, and four of heat, leaving four months of indeterminate temperature. In February it snows. In March the Lake is a lake of ice. In September the students come back and the bookstores are full. Let X equal the month of full bookstores. The number of books approaches infinity as the number of months of cold approaches four. I will never be as cold now as I will in the future. The future of cold is infinite. The future of heat is the future of cold. The bookstores are infinite and so are never full except in September...

Le problème du contrôle de groupes d'ascenseurs

Ceux qui ont déjà eu à prendre un ascenseur pour se rendre sur leur lieu de travail quotidiennement savent à quel point il peut y avoir de l'achalandage pour monter dans ces machines. Aux heures de pointe, il peut y avoir des gens qui veulent monter du rez-de-chaussée à presque tous les étages et des gens déjà à des étages supérieurs qui veulent changer d'étage.

Lorsqu'il n'y a qu'un ascenseur, il est assez facile de gérer ses déplacements. Une façon de faire assez répandue est de donner la priorité au demandes faites dans la cabine (c'est-à-dire par les personnes qui sont déjà dans l'ascenseur) et de s'arrêter aux étages où une demande de service dans la même direction (monter ou descendre) a été faite. Si personne n'est dans l'ascenseur, on répond en priorité à la première demande faite.

S'il y a plusieurs ascenseurs, comme c'est le cas dans les grandes tours à bureaux, la situation est différente. On peut gérer chaque ascenseur indépendamment, mais cela est loin d'être optimal. Une personne qui veut monter fera une demande de service à chaque ascenseur et monopolisera ainsi tous les ascenseurs. Pour éviter cela, on doit contrôler le groupe d'ascenseur comme un seul et unique système. Cependant, ce système est très complexe et il est difficile à optimiser.

Entre autres difficultés, l'arrivée des demandes est aléatoire de même que les destinations. Il faut minimiser le temps de transit de chaque passager de même que le temps d'attente. On peut aussi demander à minimiser certains paramètres reliés à l'usure ou aux coûts d'opération.

Plusieurs approches algorithmiques différentes ont été prises pour aborder le problème. Une simple recherche sur Google donne de nombreux liens vers des articles qui proposent des approches évolutives, neuronales, et autres. Je vous tiendrez au courant de mes lectures...

Résolution du problème des ponts de Königsberg

D'abord, on doit définir ce qu'est un graphe (en fait, ce qu'on va définir ici est appelé par certains un multigraphe). Un graphe G est simplement un ensemble de n points qu'on appelle des sommets S = {x_1, x_2, ..., x_n} reliés par des arrêtes A = {(x_i x_j, 1), (x_i x_j, 2), (x_k x_l, 1), ..., (x_n x_m, 3)}. On remarque que chaque arrête est spécifiée par deux points (les points qui forment les extrémités de l'arrête) et un entier qui identifie uniquement l'arrête dans les cas où il y a plus d'une arrête entre deux même points. En somme, pour produire un graphe, il suffit de tracer des points sur une feuille et de les relier par autant de ligne qu'on veut.

Maintenant, on peut facilement s'imaginer que le graphe constitue un ensemble de routes entre différents villages. Alors, on peut marcher le long de ces routes pour aller d'un village x_1 à un village x_11. On peut spécifier le chemin qu'on a pris en donnant la liste des routes qu'on a suivit. Par exemple on peut décrire le chemin comme étant la suite d'arrêtes (x_1 x_4, 2), (x_4 x_8, 1), (x_8 x_5, 1), (x_5 x_11, 3). Si on fait un trajet qui nous ramène au village d'où nous étions partis, on dit que ce chemin est un tour. Un tour est eulérien (oui, vous avez deviné, en l'honneur de Euler) s'il passe par toutes les arrêtes une et une seule fois.

Le problème des ponts de Königsberg peut donc être reformulé en terme d'un graphe et de la possibilité de trouver un tour eulérien sur ce graphe. Chaque lopin de terre devient un sommet de notre graphe et chaque pont devient une arrête. Des sommets sont adjacents (i.e. : ont un lien entre eux) si les lopins de terre sont reliés par un pont. On a donc un graphe constitué de quatre sommets et de sept arrêtes. Alors, est-il possible de trouver un tour eulérien sur un tel graphe ?

Le degré d'un sommet est simplement le nombre d'arrêtes qui sont attachées à ce sommet. Si un graphe admet un tour eulérien, que peut-on dire du degré de ses sommets ? Le tour eulérien passe par toutes les arrêtes donc aussi par tous les sommets. Puisque chaque arrête est utilisée une seule fois, quand le tour "arrive" à un sommet, il doit en "repartir" par une autre arrête. Donc chaque sommet a un nombre pair d'arrêtes (une pour l'arrivée et une pour le départ) et donc un degré pair.

Par conséquent, si un graphe a des sommets qui n'ont pas un degré pair, il est impossible de trouver un tour eulérien sur ce graphe. Un petit coup d'oeil à l'image de Königsberg et on trouve tout de suite des sommets de degré impair. Donc il est impossible de trouver un tour eulérien et la solution au problème des ponts de Königsberg est que c'est impossible.

Les ponts de Königsberg

Maintenant que j'ai un blogue, voyons ce que je peux en faire.

Un des problèmes qui est à l'origine de la théorie des graphes est celui des ponts de Königsberg. Cette ville de Prusse (au temps où la Prusse existait) est aujourd'hui Kaliningrad en Russie. Elle est composée de quatre lopins de terre reliés par sept ponts. La question qui intriguait les gens à l'époque (on est en 1736) était de savoir s'il était possible de partir d'un des lopins de terre et de traverser chaque pont une seule fois pour revenir au même lopin. En essayant un peu, on peut se convaincre assez facilement que c'est impossible. Néanmoins, il est un peu plus compliqué de le démontrer (rigoureusement, on s'entend).

C'est ce qu'à réussi Leonhard Euler, un des plus grands mathématiciens de tous les temps. La preuve est assez simple mais nécessite quelques notions élémentaires de théorie des graphes. Maintenant que je vous ai mis l'eau à la bouche et que vous mourrez tous d'envie de connaître la preuve, je vais aller me coucher. La preuve viendra dans un futur rapproché.

Mais qu'est-ce qu'un blogue?

Il semble qu'il y ait un engouement énorme pour les blogues à travers le monde. Étant moi-même un inapte technologique, je n'arrive toujours pas à bien comprendre ce qu'est un blogue. Pour tenter de me réconforter dans mon ignorance, je tente une définition.

Définition : Un blogue est une paire (U, C) constituée d'une adresse internet U et d'un ensemble de commentaires C. Ici, un commentaire c est une suite de caractères d'un alphabet A.

Ah! Voilà que je me sens mieux.