La complexité de l'enseignement

Concernant le problème TEACH défini ci-dessous, j'ai obtenu un résultat intéressant de complexité.

Problème : TEACH

Exemple : Un groupe d'étudiants E = {e_1, ..., e_n}, un sujet S et un cours C.

Question : Est-ce qu'au moins k étudiants vont passer le cours ?

Le problème est difficile.

Proposition : Le problème TEACH est NP-difficile.

Preuve : La preuve repose sur une réduction à partir du problème de couplage en 3 dimensions (3D-MATCHING). Détails à venir.

Des inspirations transcendantales me font croire que le problème est aussi NP-complet, quoique je n'ai aucune idée de preuve pour appuyer ma conjecture. Toute contribution est la bienvenue.

Conjecture : Le problème TEACH est NP-complet.

Pourquoi les nombres entiers sont parfois essentiels ?

On a tendance à sous-estimer l'utilité et la signification des nombres entiers. Dans cet article du Globe and Mail du 10 mai, on peut lire cette charmante phrase :

Nearly 800 superdelegates will attend the convention. Mr. Obama has endorsements from 275, according to the latest tally by The Associated Press. Ms. Clinton has 271.5.

Hum, j'ignore ce qu'est un demi-superdélégué. Pourquoi madame Clinton a-t-elle l'appui de 271.5 superdélégués ? D'où vient ce demi frauduleux ? On s'imagine qu'il s'agit d'une approximation statistique basée sur un modèle quelconque. Mais, dans ce contexte, l'utilisation de résultats fractionnaires n'a aucun sens.

Parfois, on peut interpréter un résultat fractionnaire comme une proportion. Or, ici, il est question d'un nombre de personnes, pas d'une proportion. Il est donc tout à fait déraisonnable de dire que madame Clinton a l'appui d'un demi-délégué.

La programmation en nombres entiers.

Qu'est-ce qui fait de la programmation en nombres entiers un sujet intéressant ? Pourquoi une poignée de mathématiciens dépensent-ils quelques milliers de dollars pour se réunir et en discuter ? Sans doute en saurais-je un peu plus à mon retour de la session de travail sur la programmation en nombres entiers qui se tient dans une semaine à la Barbade.

D'ici là, voici ce que j'en sais pour vous mettre l'eau à la bouche. Tout d'abord, la programmation en nombres entiers (PNE) est une sous-catégorie de problèmes de la programmation linéaire (PL). En PL, on veut résoudre des problèmes d'optimisation du genre :

minimiser f(x)
sous les contraintes c_i (x) = 0 pour i dans E
c_i (x) <= 0 pour i dans I où E et I sont des ensembles d'indices, les c_i et f sont des fonctions linéaires. En PNE, on rajoute la contrainte que la solution doit être entière. Parfois, on parle de programmation mixte (PM) où certaines variables seulement doivent être entières. Une des applications les plus importantes de la PNE est l'utilisation d'énoncés de type "si ... alors" en PL. Par exemple, si on a un problème qui dit "si x_1 > 10, alors x_2 + x_3 < 5", on peut utiliser une nouvelle variable entière pour écrire cette implication sous forme d'une contrainte linéaire.

La PNE peut aussi servir à résoudre des types de problèmes de transport où on ne peut pas accepter des solutions fractionnaires. Par exemple, si on achemine un produit en petites quantités sur une courte période de temps.

Plus de détails à venir éventuellement !

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...