L'informatique comme villégiature
Par David Monniaux le dimanche, octobre 23 2011, 11:42 - Enseignement - Lien permanent
Le cri du cœur d'un étudiant dans le sondage à la fin d'un cours intitulé « Fondements de l'Informatique: Logique, modèles, calculs » :
« Je trouve qu’on ne sait pas assez ce qu’il y a derrière le titre du cours avant de le prendre. Je pensais avoir un cours reposant plus sur de l’algorithmique et non un cours qui ressemble, au final, beaucoup à des maths. »
Bref, les cours d'informatique sont censés être une sorte de villégiature reposante, avec de l'algorithmique niveau débutant. (L'algorithmique avancée a une fâcheuse tendance à contenir des maths.)
Donnez-moi une guitare et un T-shirt à fleur, et je ferai GO !
PS Je précise que ce commentaire était une note dissonante dans les réponses au sondage, exprimant pour la plupart un certain contentement ; il me semble également que la plupart des étudiants travaillaient ce cours. Je le mentionne juste pour son caractère amusant, et parce que ce n'est pas la première fois que j'entends ce genre de réflexions.
Commentaires
L'étudiant en question est en quelle année ?
Il ne s'est manifestement pas donné la peine de lire autre chose que le titre du cours : que ce soit le descriptif qui parle bien de liens entre le calcul et le raisonnement, n'importe quel livre (Dehornoy, Cori-Lascar, Lalement...) sur le sujet, voire une recherche google, on comprend assez vite que ça va être des maths...
Je trouve ça assez désespérant.
Pour être tout à fait honnête je n'ai jamais bien aimé les cours de l'X qui m'ont souvent l'air d'être du saupoudrage à haute voltige mathématique (ils sont souvent publiés ensuite en livre ce qui me permet d'en juger par un échantillon plus ample que ce simple cours). Je pense que c'est dû à la fois au temps limité et à une idée étrange des mathématiques comme garantes de la qualité supérieure d'un cours.
J'ai lu tous les polycopiés de ce cours (en diagonale) et franchement, j'aurais préféré un cours dans le style du bouquin de John Harrison (practical logic and automated reasoning) avec du vrai code Caml à executer pour bien comprendre la partie constructive des résultats.
Ton TD sur le voyageur de commerce est assez caractéristique. La réduction c'est franchement barbant, il faut savoir où se référer, au cas où on aurait besoin d'en faire, mais c'est tout. Ce qui est important en revanche c'est que les inégalités coupe-cycle bien qu'étant en nombre exponentiel peuvent s'ajouter directement sur la solution contenant les cycles avec un algo simple, puis on réoptimise le IP. Donc le problème est tractable malgré tout.
Et c'est quand même une drôle d'idée de prendre le TSP en exemple, c'est un cas hyper particulier étant donné qu'on sait justement exprimer analytiquement l'ensemble des contraintes : si je te donne un problème quelconque, tu sauras sans doute me donner une famille d'inégalités nécessaires (comme les coupe-cycle) mais seras incapable de savoir si elles sont aussi suffisantes. Enfin, tout le monde connaît cette formulation et oublie qu'il y a en a mille autres, dont certaines qui n'ont pas besoin de génération à la volée de contraintes. Or c'est bien ça la leçon de 100 ans de NP complétude, il y a plein de façons équivalentes de décrire un problème mais toutes ne sont pas égales face à la résolution effective.
@Couard Anonyme: Il faut garder à l'esprit qu'il s'agit d'un public particulier, qui, sortant de prépa, trouve rassurant d'avoir le même type d'enseignement (cours, définitions, théorèmes, exercices, démonstrations de nouvelles propriétés...), et dont une partie déteste la programmation (fastidieux, beaucoup de temps perdu sur comment se faire comprendre dans le langage, etc.). Conséquence : la très grande majorité des élèves sont contents de ce cours. :-)
Je n'ai pas lu le livre de John Harrison, merci de le signaler. (C'est un peu la honte, en plus j'ai discuté plusieurs fois avec Harrison à propos de mes histoires de preuves arithmétique.)
Sinon, si tu me donnes un problème NP quelconque, je pourrai construire un problème d'ILP dont il est solution, par codage de SAT sous forme d'inégalités linéaires... mais comme tu le rappelles fort justement, cela ne veut pas dire qu'il sera tractable. Je suis en train de lire un ouvrage d'optimisation combinatoire, j'en saurai plus dans quelques semaines.
(Cher Couard Anonyme, te connaîtrais-je in real life ?)
J'y suis peut-être allé un peu fort dans ma critique, je suis désolé, on se laisse facilement emporter sur la toile.
Le point que je pense vaut la peine d'être défendu c'est que la réduction a un ILP est une réduction au même titre que celle à SAT mais en plus elle est effective (on met dans un moteur et on execute) et on peut recoder à SAT automatiquement (dans des solveurs comme miniSat+ ou Sugar).
On oublie facilement que l'équivalence mathématique est différente de l'équivalence effective : un polynôme développé ou mis sous facteurs de racines c'est équivalent mais dans un sens c'est autrement plus dur à convertir que dans l'autre.
La réduction à SAT a joué un role majeur dans la théorie de la complexité mais aujourd'hui a autant d'intérêt pratique que de coder dans une machine de Turing au lieu d'un langage fonctionnel.
Ce problème de comportement ClubMEd est courant : Lors d'analyses vibratoires, les transformées de Fourier sont courantes (et de base) et un de mes étudiants m'a signalé (à la fin d'un semestre de cours) qu'il avait choisi un module de mécanique et non de maths (visiblement épouvantail à étudiants) afin d'analyser des cas pratiques et non de faire de la théorie non-linéaire et aléatoire
Vous auriez pu commencer par signaler sur l'article principal, et non en commentaire, que la plupart des étudiants (dont moi) étaient contents du cours, car j'étais triste de nous voir taxer en bloc de comportement Club Med.
Contre Couard Anonyme je pense que, puisque la majorité (60% ? plus ?) des élèves n'est pas passée par MP-Info, donc jamais fait autre chose que du Maple et une initiation à Java, cela prendrait trop de temps (sur un cours de seulement 10 semaines) de leur apprendre assez de Caml pour "bien comprendre la partie constructive des résultats". Au contraire, passer un peu de temps sur les machines de Turing permet d'avoir des définitions claires et univoques qui "satisfont" les esprits d'anciens taupins.
Ce cours prend place en parallèle d'un cours de maths sur les EDP très orienté sur l'économie, et on est content, pour une fois, d'avoir un cours qui ne sert qu'à lui-même (hint : je lorgne sur inf431 qui a une réputation de cours de génie logiciel crade).
@Marteo: Dont acte, j'ai rajouté un post-scriptum. :-)
Je ne sais pas si je qualifierais INF 431 de cours de génie logiciel.. vous ne confondez pas avec INF 422 « programmons sur Android » ?
Non, je parle bien du cours d'info long. Je me ferai ma propre opinion - et puis peut-être le cours change-t-il avec les années - mais les retours des anciens se résument en gros à "bah c'est un cours où on fait du Java, et où il faut rendre des projets
contraignantspour avoir une bonne note". Je passe rapidement sur :a) Le fait qu'un "retour d'expérience" d'un X se ramène souvent à des conditions nécessaires et/ou suffisantes pour avoir A (resp. C).
b) Le scepticisme tout personnel que je montre à l'égard de Java pour l'enseignement de l'algorithmique, l'argument classique "les entreprises s'en servent" renforçant le cliché du cours de génie logiciel.
En réalité, au vu du programme du cours, je suis enclin à penser que quelqu'un qui travaille a minima ne fera que programmer, alors que quelqu'un qui creuse le cours fera beaucoup d'algorithmique. D'où cette réputation de "cours de Java".
La question du choix du langage de programmation, comme vous le supposez, revient régulièrement.
- Si on fait du Caml, on se fait écharper par des étudiants qui se plaignent qu'on leur fait apprendre un langage académique et inutile dans la vraie vie. (*)
- C/C++ il y a des pointeurs et de la corruption mémoire, c'est vraiment technique. Ceci dit, les gens qui font ensuite du traitement du signal etc. réclament des programmeurs C.
- Python/PHP/Perl ne sont pas typés statiquement et on voit les erreurs quand ça plante.
- Le Java c'est lourd et plein d'incantations (ah, les public static machin, ah les classes anonymes pour installer des gestionnaires d'évènements dans l'interface graphique), mais au moins il y a un typage statique assez efficace et pas de corruption mémoire.
(*) Quand j'enseignais à Dauphine, un étudiant s'est plaint que nous lui fassions apprendre des « vieux trucs comme Java » alors que « toutes les entreprises travaillent en C++ ». Outre le fait qu'il ne semblait guère connaître la chronologie des langages de programmation et le hype autour de Java pour le Web, son point de vue reflétait un cliché répandu : que les enseignants du supérieur sont inconscients des besoins réels des entreprises...