TD Bonus

Ce billet est dédicacé à Pierre Mc Kenzie, professeur à l'Université de Montréal, qui a enseigné l'introduction à l'informatique théorique et m'a donné envie de travailler dans ce domaine. Cet excellent professeur - Il a quand même demandé à faire 5 secondes de silence à la mort de la pile de sa télécommande, et a fait la preuve en cours que le démineur est NP-complet-, durant ces devoirs maisons mettait une question bonus, non noté, plus complexe est hors programme. Et c'était la question la plus intéressante, qui permettait vraiment de discuter. En fait je réalise avec le recul que certaines questions étaient une introduction à la recherche, tellement elles étaient vagues - en particulier la questions: créez une question bonus pour les étudiants de l'année prochaine[1].

J'ai fait une expérience, voic le résultat informel.

Cette année, des étudiants s'ennuyent en cours. Enfin en TD[2]. Ce qui est assez classique. Sauf que là, ils s'ennuyent car le sujet est trop simple - tout le monde n'est pas de leur avis, donc j'estime ne pas pouvoir accélerer.

Ils faut dire que ce sont des étudiants de math-info. Et certains font ce cursus car ils aiment vraiment les mathématiques. Or j'enseigne dans ce qui est pour moi LE cours de math-info, ou plutôt LE cours qui permet l'introduction à l'informatique théorique, autrement dire à considérer l'informatique comme un sujet mathématique à part entière.

Ce cours, c'est «Automate et langages». Les automates finis[3] sont un modèle simple de calcul, qui bénéficie de propriété très intéressantes et sur le plan mathématique et sur son utilisation dans l'informatique. Si tu veux en savoir plus, je te renvoie vers wikipedia.

Le souci, qui n'en est pas un, c'est que ce TD est adapté aux étudiant d'informatiques, majoritaires, et pour des amoureux des maths, c'est assez décevant de faire peu de démonstrations en TD. Ce qui s'en rapproche le plus c'est de créer des algorithmes[4], et c'est souvent en combinant d'autres algorithmes vu en cours. Mais on passe surtout du temps à faire des calculs. Sauf qu'on le sait, un calcul, c'est souvent appliquer un algorithme à la main, c'est pour ça qu'un ordinateur sait le faire. Et même si c'est utile de le faire pour comprendre vraiment ce qu'est un automate, se forger une intuition, ça ne satisfait pas la curiosité intelectuelle des bons étudiants.

Ils finissent rapidement, où alors ne finissent pas car ça les ennuye et ils ont l'impression de faire toujours le même exercice - ce sur quoi ils n'ont pas totalement tort. Et attendent que le temps passent/qu'on corrige en bouquinant, en jouant à la game boy[5] ! Normalement, il ne faut pas laisser un étudiant sans rien faire. Sauf que s'il est facile d'inventer un nouveau calcul à faire faire, il sera toujours fait de la même façon, donc ne deviendra pas plus intéressant.


(J'ouvre une grande parenthèse avant de passer à la suite. Il faut savoir que j'ai eu l'occasion d'avoir des bonnes surprises de la part de ces étudiants.

L'un cherchait à pousser plus loin un exercice[6] . Au point où ça m'a pris une petite minutes pour vérifier qu'ils avaient bons, car leurs résultats n'étaient pas totalement évident - alors que d'habitude j'ai préparé les exos donc peut vérifier leurs réponses en 10 secondes.

Ou encore, un autre cherche a reprouver un résultat, mais par une autre méthode. Ce qui est mathématiquement une démarche extrémement intéressante pour assimiler les concepts. Et enfin, un m'a demandé de l'aide sur un exercice venant d'une feuille de TD de l'ens. Exercice dont une question m'a fait sécher un bon quart d'heure quand même[7] !

Bref, on a longuement discuté après le TD de math-info plus générale, je sais que certains sont fans de logiques - et il se trouve que mon travail de recherche traite de logique ET d'automates. Et qu'un autre s'est dit «C'est des Automate fini ? Et bien, que peut-on bien faire avec des automates infinis ?». Fin de la parenthèse.)


Comme il est dur de vraiment inventer des nouveaux exercices dans le cadre du cours, et que je ne voulais pas simplement leurs donner le TD d'après - que j'aurai corrigé une semaine plus tard, donc ce qui ne serait pas intéressant - j'ai fini par leur préparer une fiche de TD «Bonus» avec deux exercices, chacun introduisant un nouveau concept liés aux automates. Et aussi lié à leurs intérêts. C'est à dire les automates sur les mots infinis, et la complexité descriptive[8], c'est à dire la branche de la logique qui s'applique à la théorie du calcul.

C'est donc là où je voulais en venir, mais je fais des introductions bien trop longue. Vous me direz, ça me change de mes articles de recherches. Ce à quoi je répondrai que je suis surpris que vous les ayez lu !


Je leur distribue le sujet du TD du jour. Puis l'autre, en précisant qu'il est hors sujet, pas au programme, et juste car je sais que certains sont curieux. Donc je ne le donne qu'à ceux qui le demandent explicitement - histoire de montrer qu'il est vraiment différent, qu'ils ne se sentent pas forcé de le regarder. J'ai eu des surprises, je pensais pouvoir deviner qui le prendrait, qui ne le prendrait pas, et j'ai eu tort dans les 2 sens.

D'abord, ça fait plaisir de voir des étudiants se réveiller - presque littéralement, il est pas 9 heures du matin et certains sont affalés - et sourire quand j'annonce quand je prononce le mot «logique». C'est presque paradoxale d'être remercié - car je n'étais pas forcé de faire ça - quand je dis que ces exercices sont particulièrement dur, et que je ne m'attend pas à ce qu'il résolvent tout, d'autant que j'y ai caché une question ouverte.

Et puis surtout, c'est cool de les voir chercher. Et là c'est vraiment de la recherche, car dans une certaines mesure je leur laisse se poser les questions, et même les définitions. Je leur dis: On voudrait faire ceci, comment vous définiriez formellement un objet mathématique qui le fait. Étudiez le, et regardez ce que vous pouvez en dire.

Là je vais commencer à rentrer dans les détails techniques - je veux dire encore plus y rentrer. Car ce qui m'intéresse est de documenter leurs progressions. Le premier exercice s'attaque aux mots infinis. Sauf que je ne leur donne ni Buchi, ni Muller, je leur demande: comment changer l'automate fini. L'un pense qu'on accepte si on reste dans un état acceptant. Mais un seul état, ça limite, donc si à partir d'un moment tous les états visités sont acceptant. Il discute avec son voisin pour décider si l'automate ne doit accepter que des mots infinis, ou aussi les mots finis. Je les laisse avec cette définition, voir ce qu'ils trouvent.

J'avais suggéré quelques langages, comme celui des mots avec un nombre fini/infini de «a», ou avec moins de «a» que de «b» dans tout préfixe. Pour le 2ème il a l'intuition qu'il n'a pas d'automate déterministe pour le faire, et cherche à comprendre pourquoi. Pour le 3ème il propose de rajouter des compteurs. Là je lui dit quand même qu'il vaut mieux éviter de complexifier encore plus le modèle. De même qu'il est normal qu'il ait des langages intéressant qui ne soient pas reconnus par les automates. Il réalise aussi qu'il ne semble pas pouvoir reconnaitre les langages périodique, ce sur quoi il a totalement raison, et trouve la preuve assez vite. Par contre, il voit aussi qu'il peut accepter les k-périodique pour tout entier k.

Il retourne sur la question évoquée plus haut. Un automate infini. Je lui indique donc pourquoi tout langage fini est accepté par un automate à une infinité d'état. Mais pas découragé, il voit que ce n'est plus le cas sur les mots infinis, mais que quand même, ça lui permet de reconnaitre les mots périodiques. (De mon coté, j'évoque rapidement la notion d'uniformité, qui peut permettre de justifier l'utilisation de l'infini en restraignant sa puissance.)


Il regarde aussi la seconde question. Il faut savoir que la complexité descriptive est une notion étudié normalement en master 1 (4ème année après le bac, 2 ans après leur année). Et bien il réussit quand même à me signaler que j'ai fait une faute dans un des exemples que j'ai mis. Ce qui est assez rassurant, car ça indique qu'il comprend ce que j'ai écrit !

Un point m'attriste, cet étudiant a deviné quel était la question ouverte. C'était la seule que je posais vraiment de manière neutre, sans donner de réponses, ou de pistes de réponses, dans la question d'après. Je me suis mal débrouillé. Et comme la question est suffisament connu pour avoir sa propre page wikipédia francophone, j'aurai préféré voir s'il était capable de reformuler lui même, et trouver cette question. Tant pis.

Sinon, d'autres ont dit qu'ils regarderont chez eux. Et puis pour le coup, je n'ai plus eu beaucoup d'autres nouvelles.

Notes

[1] J'ai guetté l'année suivante, et n'ait jamais vu ma question. Ni de question bonus d'ailleurs. Il m'a dit plus tard qu'il les mettait si des étudiants sont suffisament motivé - et je l'étais. Mais il n'y en avait pas l'année d'après.

[2] Travaux dirigé, i.e. une scéance d'exercice

[3] Je dirai automate pour raccourcir, mais on précise toujours fini quand on est formel.

[4] i.e. explique en français comment un programme fonctionnerait sans vraiment le coder

[5] et là on se prend un coup de vieux quand l'étudiant fait du rétro gaming sur un jeu qu'on a eu à sa sortie, car il s'agit de game boy même pas color !

[6] Soit deux expressions à une inconnu A et B, on demande de prouver que A=B ou de trouver un contre exemple. L'un a en plus chercher l'ensemble des valeurs qui vérifient l'équation, ce qui est autrement plus complexe dans certains cas

[7] Chez moi, je ne pouvais pas faire une pause de 15 minutes sur le TD

[8] FO(<)

Commentaires

1. Le mardi 7 avril 2015, 13:06 par LCF, bon-pointeur

Un bon point LCF, pour aller au-delà des enseignements du cours et proposer des activités motivantes.

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.

Fil des commentaires de ce billet