Comments on Réflexions à 2 femtozorkmids sur l'informatique en tant que science

(Sinon, vu que j'ai enfin tout lu, sur le propos lui-même je suis assez d'accord :P)

Sur cet aspect (dire quelque chose de rigoureux sur, disons, un chiffre par bloc précis), la crypto symétrique ne me semble pas très différente de la crypto à clef publique : ce n'est pas plus facile de dire quelque chose de rigoureux sur par ex. la difficulté de calculer (concrètement, sur par ex. des FPGAs) le log discret dans un certain groupe explicite, ou d'inverser l'exponentiation dans Z/NZ avec N = ….
(D'ailleurs, les derniers concours en date sont justement pour des algos à clef publique :P)

Certes, certains schémas à clef publique se basent (souvent seulement en partie, avec parfois pas mal de choses parfois cachées sous le tapis) sur des problèmes plus «naturels» que savoir si AES-128 est une bonne PRP, mais au final on n'en regarde jamais que des instances particulières (et le fait que le problème puisse être naturel est (je pense) de toute façon complètement orthogonal à la rigueur)

Bref, on peut travailler en crypto dans un cadre formel assez rigoureux, et les tests d'hypothèses (nécessaires pour instancier les objets qui y sont développés) sortent de ce cadre. Mais ces deux points sont tout aussi vrais en crypto symétrique qu'asymétrique

Je ne vois pas pourquoi il faudrait exprimer les choses de façon asymptotique pour qu'elles soient rigoureuses (et d'ailleurs ce n'est pas la pratique… en symétrique), mais quand-bien même on souhaiterait le faire c'est tout à fait possible en symétrique aussi : il y a plein de résultats qui s'expriment sur des objets qu'on peut asymptotiser si on veut

J'essaye d'illustrer ça avec quelques exemples :

# [one-time-pad] Si A et B connaissent tous deux une chaîne K qui a été tirée uniformément dans {0,1}^n, le système de chiffrement consistant à envoyer (une unique fois) n bits m comme m XOR K a une sécurité IND-CPA «infinie» (la fonction avantage Adv^IND-CPA(q,t) vaut zéro pour tout entier t)

# [PRP/PRF switching] Soit un oracle O distribué comme une permutation OU fonction uniforme sur N éléments, l'avantage de distinguer les deux cas en q requêtes (adaptatives) à l'oracle est majoré par q(q-1)/2N (en majorant la probabilité de collision qui-va-bien) (un de mes résultats favoris : pas complètement trivial mais pas compliqué non plus, et avec des tonnes d'applications)

# [Sécurité PRP de la construction Even-Mansour] Dans le modèle des permutations idéales, la sécurité PRP (pour, disons, des permutations P de {0,1}^n) de EM[P] : (k,x) -> P(x XOR k) XOR k est t.q. Adv^PRP(q,t) <= 2qt/(2^n) (plus précisément, Adv^{(P,Q)/(P,EM[P])}(q,t) <= …, où q et t dénotent le nombre de requête à chacun des deux oracles)

On peut formuler tous ces trucs de façon asymptotique si on le souhaite (par ex. dire que l'avantage d'un adversaire faisant un nombre poly(log(N)) de requêtes dans le jeu PRP/PRF a un avantage négligeable), mais il n'y a même pas besoin de ça pour que ce soit pertinent et rigoureux. On peut par exemple dire des choses très concrètes (hum) en branchant des valeurs fixes, comme par exemple remplacer N par 2^{128} dans le PRP/PRF switching pour récupérer un majorant de l'avantage IND-CPA d'attaquer le mode compteur instancié avec AES-128 (fun fact : c'est aussi quasi un minorant) ; le majorant fera intervenir la fonction d'avantage PRP d'AES-128 (dont on ne connaît pas les valeurs), qui est aussi un objet complètement fini, mais ce n'est pas grave

«La cryptographie symétrique, notamment, ne me semble pas pouvoir être classée dans les maths à cause du critère empirique suivant : on ne dispose pas d'une formulation mathématiquement rigoureuse de ce que signifie « casser » un chiffrement»

Ben… bien sûr que si ?? Il y en a même plusieurs (elles sont d'ailleurs très informatiques dans leur formalisme) ?? Et on peut prouver (sous hypothèses plus ou moins standard) que certaines constructions ont un niveau de sécurité non trivial relativement à ces définitions ??

Ou alors, qu'est-ce que tu ne trouves pas rigoureux avec good ol' IND-CPA ??

J'ai passé l'agreg d'informatique l'an dernier, et je débute en lycée cette année avec des secondes (en SNT) et des premières (NSI).

Il me semble en effet très difficile de définir l'informatique comme une science à part entière. En étant taquin, on peut rattacher le moindre concept de l'informatique à une science préexistante. Le transistor = physique quantique, la complexité, etc. sont des maths, le pixel lui-même est une somme de signaux optiques.

Cependant, concernant l'aspect scolaire du billet : l'élan donné depuis 5 ans (ou 10 ans, avec la spécialité ISN en Terminale) à l'informatique dans le secondaire ne me semble pas vouloir asseoir l'informatique comme science, mais bien comme **discipline**, ce qui a du sens : de la théorie de la compilation à la logique linéaire, en passant par les architectures parallèles, l'informatique forme bien un tout cohérent, une somme de domaines interconnectés par des liens divers. De ce point de vue-là, je pense que la création d'un CAPES, d'une agrégation, d'une filière prépa en informatique est la bienvenue.

Les élèves en informatique n'apprendront pas QUE l'informatique. Rappelons que 95% (doigt mouillé) des lycéens qui prennent NSI au bac ont aussi pris maths, et qu'en MPI (la nouvelle filière "informatique" de prépa), il y a bien 12h de maths par semaine, 8h de physique, et 6h d'info. Pas l'inverse.

Il y a (je schématise) deux visions de l'info en France aujourd'hui :
1) L'informaticien, c'est celui qui répare ta Freebox (vision de quelqu'un d'extérieur au monde des sciences),
2) L'informaticien, c'est un mathématicien appliqué (vision et état de fait jusqu'à il y a peu dans l'enseignement secondaire français).

En faveur de l'assertion 2, on peut dire que les lauréats de l'agrégation d'info sont pour la grande plupart des normaliens qui ont fait des maths, et on s'en sort mieux au concours si on connait le lambda-calcul et qu'on touche de semi-loin aux ordinateurs, que si on a 20 ans d'ingénierie réseau derrière soi. Mais au moins, l'accès à l'enseignement de l'informatique en prépa ne sera plus évalué sur des compétences en informatique théorique (en plus de devoir maîtriser le reste du fondement des maths), ce qui était le cas avec l'option info de l'agreg de maths, mais sur une discipline qui inclut l'info théorique, des notions de Web, de réseau, d'architecture des ordinateurs, d'OS. Et toutes ces nouvelles choses n'étant présentes auparavant dans aucune discipline précédemment définie par l'enseignement secondaire, j'affirme qu'on a gagné au change.

P.S. Je confirme que les Zoomers ont une connaissance très superficielle de l'informatique pratique ; l'enseignement de la technologie au collège est censée fournir des notions de base (traitement de texte / tableur, gestion de fichiers…), mais je suis tombé de haut quand j'ai découvert qu'une bonne partie des néo-lycéens me faisait des gros yeux quand j'ai demandé de faire un copier-coller. Mention spéciale aux extensions de fichiers qu'ils ne comprennent pas du tout, merci à l'hégémonie de Windows dans l'Education Nationale… L'environnement technologique actuel ne forme pas du tout à l'informatique, car comme le billet le dit bien, les smartphones et le reste n'incitent pas à regarder sous le capot, au contraire, de multiples couches de complexité existent pour rendre l'interface la plus magique et minimaliste possible en apparence. C'est bien l'inverse de l'informatique de papa.

P.P.S Quant à savoir s'il est pertinent d'apprendre la programmation dès le lycée, voire le collège, c'est un autre débat…

@jeanas: metadevinette Demande à un matheux de définir un moyen de distinguer un mathématicien d'un informaticien et il fera probablement ta réponse…

Mais je suspecte que l'ingénieur informaticien parlera de "fichier journal d'événements" 😉

Moi, je connais un moyen très simple de savoir si un scientifique est mathématicien ou informaticien. Demandez-lui ce que veut dire pour lui « log ». S'il répond le log en base 2, c'est un informaticien. S'il répond le log en base e, c'est un mathématicien. Et d'ailleurs, s'il répond base 10, c'est un physicien. :)

L’informarique théorique faite aujourd’hui a des applications concrètes notamment en complexité qui classent les problèmes qu’on peut résoudre avec des algorithmes plus ou moins rapides ou efficaces. Et trouver ces algorithmes ou montrer qu’ils n’existent pas est l’objet de cette discipline en vogue aujourd’hui. Ce qui est significatif, c’est d’étudier ou de produire des choses intéressantes que ça s’appelle math ou informatique appliquées ou pas peu importe.

@Ruxor: certes, c'est une difficulté. Mais je ne pense pas qu'il faille la refuser. Après, quand deux disciplines s'intéressent au même sujet, elle peut le faire avec des points de vue différents. Même si l'objet d'étude est rigoureusement le même, on peut en principe y faire à la fois de l'informatique et des mathématiques de manière clairement délimitée (peut-être que l'algèbre linéaire est un exemple?).

Mais bon, plutôt que refuser la difficulté on peut l'affronter en se posant la question: qu'est-ce qui fait qu'un groupe social constitue une discipline (je n'ai pas la réponse à cette question). Peut-être que de bons critères vont rejeter le cas dégénéré où deux disciplines ont exactement le même sujet d'étude. En tout cas, je n'ai pas d'exemple de disciplines qui sont essentiellement identiques, donc on est au moins pas trop mauvais, en tant qu'espèce, pour ne pas nommer n'importe quoi “discipline”.

@Thomas

Oui bien sur, tout le monde peut se remettre à niveau et se former sur le tas, c'est même une obligation en informatique tant la discipline évolue rapidement. D'ailleurs, on trouve bien des physiciens qui bossent dans les gafam par exemple. Mais j'ai qq amis normaliens qui me disaient qu'ils pensaient avoir des lacunes par rapport à leurs amis qui étaient passés par des écoles d'ingénieurs, et que leur enseignement théorique ne les avaient pas particulièrement bien préparé à l'informatique.

D'ailleurs c'est un peu mon cas. Je n'ai pas fait une ENS, mais après mon école j'ai fait une thèse très théorique qui d'un point de vue pratique ne m'est d'aucune utilité, vraiment zéro. Et la pression et la diversité des choses à faire dans mon nouveau boulot est telle que je n'ai pas toujours le temps de former. Si c'était à refaire, je ferais une thèse sur un sujet plus appliqué.

Bref, tout ça est un peu anecdotique, mais je continue de penser que la théorie en informatique c'est quand même un peu une niche et que les "diminishing returns" sont vite atteints.

Je pense que j'ai déjà partagé mon point de vue avec toi sur la question, mais c'est l'occasion de réitérer. L'informatique est ce que font les informaticien. Est informaticien qui se dit informaticien. Ça n'interdit absolument pas de tenter de décrire ladite science, bien-sûr. Mais, à mon sens, les limites sont contingentes, et mouvantes; et il n'y a pas de définition essentielle à l'informatique (ou aux mathématiques ou la physique <URL: https://twitter.com/aspiwack/status/1744848743654977558 >).

Je pense que tu mets le doigt sur un point intéressant en notant un certain complexe des informaticiens théoriques envers les mathématiques. On voit même pas mal de gens qu'on considérerait naturellement comme informaticiens qui se considèrent comme mathématiciens. Mais ça concerne plutôt les vieilles générations. Les gens de mon âge et plus jeune n'hésitent plus à se considérer comme informaticiens. Bon après, je suis un mauvaise exemple, me définissant moi-même comme un peu des deux, mais je suis tout de même nettement plus informaticien que mathématicien. Et je le sais parce que, circulairement (mais pas meaninglessly), je fais surtout de l'informatique.

De ce point de vue, je pense qu'il ne fait aucun doute que l'étude des modèles de calcul non physiquement réalisable fait partie de l'informatique (sans l'exclure du giron d'autres matières, bien-sûr). Ce n'est vraiment pas un soucis qui rebute les informaticien, et on trouve ici où là des travaux. Ce n'est pas une priorité, je pense, parce qu'il y a encore beaucoup de questions naturelles plus élémentaires, et qu'elles ont tendance à prendre précédence. Toutes ces questions sont finalement assez jeunes: il reste vraiment beaucoup de chemin à défricher. (cela dit, pour ton point, j'ai déjà modélisé une fonction de hash cryptographique comme une fonction injective d'un ensemble infini vers un ensemble fini, et ça fait beaucoup grincer les dents tout de même). Après, aussi beaucoup de hasard: il suffit qu'un chercheur très fort et charismatique s'intéresse à un sujet pour que ce sujet s'installe durablement.

Je ne sais pas trop où j'avais prévu d'aller avec cette tirade, du coup, je vais l'arrêter sans vraiment qu'elle est de conclusion. Mais une question: point taken sur les coûts de limites administratives entre sciences. Mais sont elles significativement plus fortes que les limites sociales entre sous-sujet de ces sciences? Genre si quelqu'un fait de la théorie des catégories pour étudier les systèmes dynamiques, ne va-t-on pas user des mêmes arguments et préjugés chacun pour le renvoyer à l'autre? Même si c'est la même section CNU?

@Ivo: "où ils se plaignaient de leur manque de compétences générales en info"

Je n'ai peut-être pas bien compris la phrase mais j'ai croisé plein de gens avec un profil "recherche" (genre thèse, ou Agreg/enseignement puis entreprise) qui sont tout à fait compétents pour écrire du code dans les conditions d'une entreprise.

Ce qui arrive parfois en revanche, c'est que des gens aient du mal avec le fait qu'en entreprise ce qui marche est privilégié sur ce qui est beau théoriquement (ce qui est bien sous certains aspects, mais peut être problématique parfois).

Je verrais l'informatique théorique comme une branche des mathématiques. A partir du moment où l'on fait des théories et on prouve des théorèmes, on fait des mathématiques. En "informatique théorique", on s'intéresse simplement à une classe particulière de problèmes mathématiques. De la même manière, Hugo Duminil-Copin est un mathématicien même s'il est inspiré par des processus physiques.

A l'inverse, l"informatique" est une discipline beaucoup plus vaste qui recouvre beaucoup de choses très différentes. Développer des compilateurs, des algorithmes de cohérence de cache, des moteurs de recherche, faire de l'optimisation, des réseaux de neurones… tout ça n'a pas grand chose à voir. Il y a parfois des fondations théoriques (calculabilité, logique, théorie de la concurrence, théorie des langage) ou des outils théoriques (théorie des graphes etc…), plus ou moins utiles mais pas vraiment de fondements indispensables qui formeraient le socle nécessaire pour aborder tout le reste. En particulier, je ne sais pas si on peut vraiment extraire l'ingénierie de tout ça.

Au passage, je ne suis pas sur qu'il y a ait beaucoup de place pour un "enseignement de la science informatique" déconnecté de l'ingénierie. Peut-être que c'est ce qu'essayent de faire les ENS ? je me souviens avoir rencontré des normaliens lyon/cachan avec des profils hyper théoriques (genre théorie des automates), et certains ne trouvaient ni leur place dans la recherche (manque de postes, notamment sur leurs thématiques), ni dans le privé (où ils se plaignaient de leur manque de compétences générales en info).

Le même genre de débats existe avec la géographie (en tant que science, pas la géographie utilitaire) : impossible de déterminer exactement ce qui en fait partie ou non. Son objet est assez vague : l'espace, la terre, des trucs assez vagues. Dans les faits, elle regroupe un paquet de trucs, dont des sciences dures et des sciences humaines. La géographie physique est un mélange de sciences de la terre et de l'environnement assez bordélique, la géographie humaine mélange sociologie, économie, et un paquet de sciences humaines, avec pas mal de modèles mathématiques et de stats dans le tas.

Et l'informatique a le même problème que la géographie : un paquet de trucs qu'on classe dans l'informatique sont en fait assez transdisciplinaires. Par exemple, tout ce qui a trait au calcul, à l'automatisation, l'information, des données, de la communication, se retrouve dans des domaines comme l'électronique, mais d'une manière totalement différente. Un truc tout bête : tout ce qui a trait à la "circuit complexity", c'est l'étude de circuits électroniques numériques idéalisés. Et on peut aussi citer l'étude de modèles de calculabilité purement analogiques, qui étudient en fait des idéalisations proches des circuits que je voyais en BTS électronique et qu'aucun informaticien ne connait (sauf pour la culture générale). Pareil pour la crypto, la détection/correction d'erreur, tout ce qui a trait aux codage/décodage des information, le traitement du signal, la partie basse des cours de réseau, l'architecture des ordinateurs : enseigné dans les cursus d'électronique et d'informatique, certains dans les cours de télécommunication. Et je parie qu'on peut en trouver d'autres.

Pour moi, l'informatique est l'étude de la programmation et de tout ce qui est programmable. Donc, la science des ordinateurs, programme et de tout ce qui va avec. Quelqu'un qui fait du traitement de signal avec des ampli op et des transistors ne fait pas de l'informatique : y a pas d'algorithme proprement dit dans le tas. Pareil avec les calculateurs analogiques, les circuits simplement configurables, et j'en passe. Par contre, dès qu'un truc peut être programmé, c'est de l'informatique. Et ca colle pas mal avec la division que j'ai observée entre mon BTS d'électronique et mes 4 ans en licence/master d'informatique : des trucs partagés, mais les trucs distincts se rangeaient bien dans la catégorie "lien avec la programmation/pas de lien". Les trucs partagés, typiquement le codage de l'information (crypto, détection d'erreur et autres), c'est des maths appliquées qui vlent bien la physique appliquée qui faisait la moitié de mon cursus d'electronique. L'informatique n'a rien de spécial de ce point de vue.

Sinon, les jeunes générations ont bel et bien du mal avec les ordinateurs. La plupart ont un smartphone, une console de jeu, mais pas forcément d'ordi. Ou alors, il arrive assez tard, vers l'adolescence. Le résultat est assez clair : la plupart de mes anciens élèves (j'étais prof contractuel en informatique dans une ancienne vie) avaient du mal avec tout ce qui a trait aux fichiers ou au système de fichiers. La notion de hiérarchie de répertoire ne leur est pas acquise, car complètement cachée sur leur smartphone. Pareil pour des trucs comme les mises à jour des pilotes de périphériques (un peu compliqué, je sais), l'usage du menu démarrer (si si), trouver et DL des logiciels sur le net, et plein d'autres trucs de geek que tous les ados de mon âge géraient facilement. Pas mal sont perdus dès qu'il faut faire autre chose que cliquer sur un truc sur le bureau…

Schutzenberger avait fait une thèse de maths après ses études de médecine, ce qui ne cesse de m'épater même si les exigences étaient peut-être un peu plus basses à l'époque (?)

Sur les grammaires non-contextuelles, il est bon de rappeler qu'elles sont le fruit de la collaboration entre Chomsky et Marcel-Paul "Marco" Schützenberger, et la hiérarchie des langages formels qu'on appelle d'après Chomsky devrait sans doute porter leurs deux noms.

Chomsky n'a d'ailleurs plus guère fait de contribution en informatique après cet épisode de collaboration et ce sont d'autres gens (Je crois Jackendoff dans les années 80 et Stabler dans les années 2000) qui se sont chargés de formaliser un tant soit peu ses théories.

<URL: https://www.persee.fr/doc/lgge_0458-726x_1968_num_3_9_2362 >

Ruxor: j'aurais plutôt dû citer le programme de M1, plus technique: https://formations.pantheonsorbonne.fr/plugins/odf-web/odf/_content/subprogram-subprogram1-master-parcours-logique-et-philosophie-des-sciences-fr/Master%20parcours%20Logique%20et%20philosophie%20des%20sciences.pdf
https://www.zebrascrossing.net/t8790-question-orientation-l2-sorbonne :
"J'ai le sentiment que cette formation attire des personnes de très haut niveau intellectuel. […] Rencontres de qualité garanties à mon avis."

La maîtrise de logique qui est son ancêtre comportait presque uniquement des cours de maths et informatique: Prolog, Scheme, calculabilité, théorie des modèles, théorie des ensembles, calcul des séquents, lambda-calcul.

Puisque ça parle de logique, je mentionne que le 14 janvier a été déclaré par l'UNESCO journée mondiale de la logique : https://www.unesco.org/en/days/world-logic.

@Denis: n'oublions pas les philosophes:
https://formations.pantheonsorbonne.fr/fr/catalogue-des-formations/licence-L/licence-philosophie-KBTH7F5U/licence-philosophie-parcours-logique-et-culture-scientifique-KBTHIP71.html

@Ruxor: "Extrait d'un texte de Dieudonné (je n'ai pas la référence précise, c'est recopié depuis une photo trouvée en ligne":

extrait de _Penser les mathématiques_.

Tu commences par mentionner l'informatique, mais en lisant plus en détail tu sembles ne parler que d'informatique théorique, ou en tout cas que de la partie de l'informatique qui a clairement une intersection avec les maths (et de la même façon, tu parles essentiellement de physique théorique).

Dans l'enseignement de l'informatique, n'y a-t-il pas aussi des questions autour de l'architecture des ordinateurs ?

Par exemple, je pense que plein de gens seraient très intéressés de voir comment concevoir un ordinateur à partir de porte logiques.

De façon plus générale, il y a des gens qui accrochent bien aux approches pratiques et d'autres aux approches théories. À mon sens, ça pourrait être une façon de réorganiser un peu les filières (par ex. en prépa) et l'enseignement de l'informatique : il me semble assez important que tout le monde fasse de l'informatique, mais cet enseignement pourrait être plus axé sur la pratique en PSI/PC (ou autre filières mentionnées par Héhéhé ci-dessous) et sur la théorie en MP.

Il y a même un "paradoxe" supplémentaire: une proportion significative de ce qui est fait dans les départements de maths traite de problèmes venant directement de la physique (c'est frappant si on regarde les thématiques récompensées par la médaille Fields par exemple), tandis que les problématiques autour des fondements des maths me semblent plus présents dans les départements d'info que dans ceux de maths. D'un certain point de vue (partial) on pourrait dire que les informaticiens sont "plus matheux que les matheux".

"Je suis certainement favorable à cette évolution, et au fait que l'informatique soit traitée comme une vraie manière autonome et pas une sorte d'excroissance des maths ni une distraction proposée en marge des cours".

C'est bien gentil mais il manque une composante fondamentale pour le cadre ayant une culture scientifique (certains appellent ça un "ingenieur"):
Savoir récolter, traiter, stocker et diffuser des données. Bref la culture de la data.
Je parle ici d'un savoir concert. Prétendre faire de la physique expérimentale sans savoir faire ça est un mauvais gag.
C'est une partie "utilitaire" de l'informatique.
C'est assez bien couvert par l'enseignement actuel en prépa même si les questions sur ce thème dans les sujets de physique sont souvent à pleurer.

Pour ce qui est de la physique, on peut jouer à Étienne Klein et en parler longtemps pour ne rien dire tant qu'on ne définit la chose.
Proposition : dire que c'est de la physique si c'est une théorie testable et testée. Par exemple, le mécanisme de Higgs n'était pas plus de la physique que certaines variantes de suzy aux énergies du LHC avant qu'il ne soit testé positivement). Bref, les théories qui ne correspondent pas à notre univers sont des maths. Seules celles qui passent le cut de l'expérience deviennent de la physique. On peut maintenant se demander ce que sont les théories physiques qui marchent mais qui sont mal fondées mathématiquement parlant. J'aime à penser que si ça marche pour décrire le monde alors il en existe une version mathématiquement rigoureuse. Trouvez moi des maths fausses (donc pas des maths :)) qui décrivent correctement le monde. Je n'en connais pas mais je serais très intéressé si qlqn a un exemple non trivial.

Tu cites les filières MP et PC en plus de la nouvelle filière MPI, n'oublions pas qu'il y a d'autres filières en CPGE scientifique: PSI, BCPST et PT (pour citer celles après un bac général), TSI, TPC et TB après un bac techno et enfin ATS après un BTS/DUT. Toutes ces filières incorporent de façon plus ou moins prononcée un enseignement de l'informatique.