« Et donc, tu fais quoi en ce moment ? » « De l’informatique théorique. Des maths, en gros. »

Ça fait quelques jours que j’ai envie d’écrire des choses un peu plus consistantes que « oh j’ai lu ça, c’était cool ». Plus spécifiquement, il y a une question qu’on me pose relativement souvent : « Et donc, tu fais quoi en ce moment ? ». J’ai beaucoup de mal à y répondre – en général je réponds quelque chose du genre « de l’informatique théorique. Enfin des maths, en gros ». C’est pas très satisfaisant, mais rentrer dans les détails quand on me pose une question « sociale » n’est pas forcément une bonne idée non plus. Mais peut-être qu’il y a des gens qui seraient intéressés par un peu plus de détails, et d’une façon que je pourrais expliquer à quelqu’un qui ne baigne pas dans le domaine depuis un an et demi. Pour donner une idée, j’essaie de viser un niveau « j’ai pas fait de maths depuis le lycée ». Je sais pas trop si je vais y arriver, ça commence à faire un bout de temps que j’ai quitté le lycée, et j’ai fait des maths depuis 🙂

Je vais donc commencer par rédiger un billet très général (celui-ci) pour poser un peu quelques bases ; et après, j’ai la ferme intention de rentrer dans les détails un peu plus. L’idée, c’est que je trouve vachement cool ce que j’étudie en ce moment ; et j’aimerais bien expliquer pourquoi je trouve ça vachement cool. Ça va demander un peu de boulot ; j’hésite limite à faire un premier billet sur « mais, mais, mais… c’est QUOI, un logarithme ? », parce que quand même les logarithmes c’est super utile, mais j’ai peur de faire une insulte à la culture scientifique de mes lecteurs. Je crois que je vais le faire quand même, parce que ça m’amuse moi, et que c’est quand même la raison principale de faire des choses. Et après, je compte faire des billets plus ou moins selon l’humeur du moment. Probablement un peu de complexité, probablement des graphes (j’aime bien les graphes), probablement un peu de probabilités (haha), et les « prérequis » pour tout ça (je suis en train de réfléchir à ce qu’il me faut pour un billet expliquant P/NP, ce qu’est un problème NP-complet, et la grande question de savoir si P = NP, je ne suis pas la première à me frotter à ce genre de billet, mais je pense que l’exercice didactique est intéressant 🙂 )

Je digresse déjà, c’est pas gagné. Revenons à nos moutons. Je suis actuellement en master d’informatique, spécialisation informatique théorique, de l’ETH à Zürich. Les modalités « usuelles » sont de faire 60 crédits de cours, généralement en deux-trois semestres, suivis d’un semestre de projet de recherche (avec rapport et soutenance à la fin, classique). Il se trouve que j’ai pris des chemins un peu détournés pour mon master, et que de fait je vais rentrer dans mon 4e semestre de cours, mais c’est pas vraiment la question ici.

« Mais c’est quoi, l’informatique théorique ? » seriez-vous peut-être tentés de me demander. La première réponse qui me vient à l’esprit, c’est que c’est la théorie de tout ce qu’on peut faire avec un ordinateur. Au cœur de tout ça, il y a la notion d’algorithme. Un algorithme, c’est simplement une suite d’instructions. On peut par exemple penser à une recette de cuisine comme à un algorithme :

  1. Pour faire de la béchamel, il me faut du beurre, de la farine et du lait.
  2. Mesurer des quantités égales de beurre et de lait.
  3. Dans une casserole à feu moyen, faire fondre le beurre et y incorporer la farine jusqu’à obtenir une pâte épaisse.
  4. Tant que la béchamel n’a pas la consistance souhaitée, ajouter du lait et mélanger.
  5. Si on le souhaite, ajouter du sel, du poivre, de la muscade ou du fromage râpé.

On a une suite d’instructions (qui sont numérotées), qui peuvent être répétées (tant que la béchamel n’a pas la consistance souhaitée) ou qui ne sont exécutées que dans certaines conditions (on n’ajoute de la muscade que si on le souhaite).

De façon plus « classique », on peut aussi penser à l’algorithme de la division que tout le monde étudie à l’école primaire.

Je suis un peu biaisée sur les catégories de ce qu’on peut faire rentrer dans l’informatique théorique, parce qu’il y a des domaines que je connais bien mieux que d’autres, mais en voici une liste explicitement non exhaustive (si j’oublie votre domaine favori… c’est que je ne sais pas quoi en dire, n’hésitez pas à expliquer en commentaire). Pour une liste un peu plus complète, je vous renvoie sur l’article correspondant de la Wikipedia : Informatique théorique, qui reprend lui-même la liste de SIGACT (une grosse société savante du domaine, en gros). Quant au fait que « je fais des maths », l’informatique théorique est souvent considérée comme une branche des maths discrètes ; et en pratique, prouver qu’un truc marche implique de faire de jolies preuves pleines de jolies maths 🙂 (Ou de moches maths, mais c’est nettement moins satisfaisant.)

Je me permets un certain nombre d’approximations ici (en particulier je fais la confusion entre un problème et une instance d’un problème), j’essaie de faire simple sans faire de paragraphe à rallonges. Ceux qui savent de quoi je cause corrigeront d’eux-mêmes ; pour les autres : c’est une première approximation, qui n’est par définition pas exacte, mais que j’ai l’intention d’affiner dans les billets qui suivront.

  • L’algorithmique. Étant donné un problème, comment le résoudre avec un algorithme, comment prouver que la méthode de résolution (l’algorithme) qu’on propose est effectivement correcte, et combien de temps faut-il pour avoir un résultat ?
  • La théorie de la complexité. Ça inclut, mais pas seulement, le point « combien de temps il faut pour avoir un résultat » du point précédent. On s’intéresse aussi ici à la question : étant donné un problème, quel est le temps minimum et la consommation de mémoire minimum qu’il me faut pour le résoudre ?
  • La théorie des graphes. Un graphe est une structure mathématique composée de points (les « sommets » du graphe) et de traits (les « arcs » du graphe). Un exemple de graphe pourrait être la carte d’un réseau de métro : les stations sont les sommets, les arcs sont les connexions d’une station à une autre par une ligne de métro. En théorie des graphes, on s’intéresse aux propriétés de ces graphes (par exemple : est-ce que je peux aller d’un point à un autre ; quel est le plus court chemin d’un point à un autre ; si je supprime ce sommet là (ou, dans l’analogie précédente, si je ferme ma station de métro), est-ce que je peux toujours aller de mon point A à mon point B), et aux algorithmes pour décider ces propriétés (comment je fais pour déterminer quel est le plus court chemin d’un point à un autre du graphe).
  • Les structures de données. Comment stocker les données du problème qu’on cherche à résoudre, de la façon la plus efficace possible (en temps et en mémoire) pour le problème en question ? Ou, pour reprendre mon exemple précédent, comment stocker la carte du réseau de métro pour faire des calculs dessus ?
  • La géométrie algorithmique. Comment représenter et résoudre avec un ordinateur des problèmes qui touchent à la géométrie ? Un exemple typique est celui du « bureau de poste » : étant donné l’emplacement de tous les bureaux de poste d’une ville, comment déterminer efficacement celui qui est le plus proche de ma maison ? Si je ne cherche que celui qui est le plus proche de ma maison, je peux calculer la distance entre ma maison et tous les bureaux de poste ; mais comment faire ça plus efficacement si je cherche à définir, pour toutes les maisons de la ville, le bureau de poste le plus proche ? Et qu’est-ce que je fais si je veux ajouter/supprimer un bureau de poste ?
  • L’impact de l’aléatoire dans tout ça – pour certains algorithmes, il est intéressant d’ajouter une part de hasard dans les calculs (je lance une pièce, si elle fait pile mon algorithme fait ceci, si elle fait face mon algorithme fait cela). Quel impact ça a sur les algorithmes – en particulier sur le fait qu’ils renvoient le résultat correct ou non, et comment évaluer le temps nécessaire à résoudre (correctement) un problème avec un algorithme aléatoire ? L’étude de certaines structures aléatoires a aussi un intérêt en soi. On peut par exemple définir des graphes aléatoires : on prend un ensemble de points, et on ajoute un arc entre deux points selon une certaine probabilité. Selon la manière dont on définit un graphe aléatoire, il peut s’avérer un assez bon modèle d’un graphe de réseau social (qui est ami avec qui)… ou du cerveau humain.
  • La cryptographie. Si Alice veut envoyer un message à Bob en étant sûre qu’Ève ne puisse pas le lire, et si Bob veut être sûr que le message qu’il vient de recevoir provient bien d’Alice, comment faire ? Et surtout, comment prouver qu’effectivement Ève ne peut pas lire le message, et que Bob peut être sûr de la provenance du message ?
  • [EDIT] La calculabilité, comme on me le signale en commentaire. Il se trouve qu’on ne peut pas tout résoudre avec un algorithme, et qu’on peut même prouver que certaines choses ne peuvent pas être être calculées avec un algorithme. L’exemple le plus célèbre est celui du « problème de l’arrêt », c’est un peu méta, mais j’espère que vous me le pardonnerez. On peut prouver qu’il n’existe pas de programme qui décide si un programme donné finit par s’arrêter et à renvoyer un résultat. La preuve est jolie, même si elle fait un peu mal au crâne la première fois qu’on y est confronté ; j’en ferai peut-être un prochain billet 🙂

Voilà, tout ça, c’est des trucs dans lesquels j’ai au moins des notions de base. L’informatique théorique regroupe encore pas mal de choses dans lesquelles mon niveau de connaissance est à peu près nul : la théorie de l’information (à ma grande honte), l’apprentissage automatique (ou comment réussir à faire reconnaître des photos de chat à un ordinateur), les méthodes formelles (ou comment réussir à prouver que mon programme n’a pas de bug), l’informatique quantique (sait-elle mieux reconnaître une photo de chat que l’informatique classique), la bio-informatique (comment déterminer si deux séquences ADN sont proches ou non) et j’en oublie encore probablement un peu.

Notons accessoirement que faire rentrer ceci ou cela dans le domaine de l’informatique théorique peut toujours prêter à débat. Je ne suis par exemple pas convaincue de la présence de l’apprentissage automatique dans l’informatique théorique, parce que ça me paraît encore très expérimental (on a modifié ce paramètre là et par conséquent l’ordinateur reconnaît 2.2% de plus de chats). La Wikipedia parle d’informatique distribuée et concurrente (l’art d’utiliser plusieurs ordinateurs à la fois pour exécuter des programmes) comme faisant partie de l’informatique théorique. Je suis d’accord que l’intersection n’est pas nulle – mais je ne considérerais pas l’informatique distribuée comme un sous-ensemble de l’informatique théorique. Idem pour la bio-informatique ; certains éléments en font partie (l’exemple des chaînes ADN par exemple), mais je ne suis pas sûre que tous les bio-informaticiens se définissent comme des informaticiens théoriques 🙂

Je pensais que ce billet serait relativement court ; je crois que c’est un échec cuisant de ce point de vue. J’espère qu’il était cependant vaguement intéressant ; et s’il y a des choses que vous pensez que je peux traiter dans un futur billet de cette catégorie… ben n’hésitez pas 🙂

14 commentaires sur « « Et donc, tu fais quoi en ce moment ? » « De l’informatique théorique. Des maths, en gros. » »

  1. Salut,

    Billet très intéressant ; j’aurais apprécié dans ton listing de catégories de domaines en informatique théorique la calculabilité, ce qui t’aurait permis d’expliquer à tes lecteurs qu’il y a des problèmes qu’on ne peut pas résoudre par un algorithme (et tant qu’à faire en donner un exemple 🙂 ).

    Bon courage pour la suite.

  2. C’est pas gentil de se moquer des vieux qui s’obstinent depuis trente ans à rater la Béchamel. Je dois avoir un neurone qui fait un blocage. Krkrkr…

    1. J’avoue que je vois pas bien comment louper une béchamel à répétition. En louper une (genre en voulant gagner du temps et en se retrouvant avec du lait aux grumeaux, et encore), passe encore (ça m’est arrivé une fois), mais à répétition…

  3. Pour les logarithmes, maintenant c’est réglé, tu commences par ça :

    Maintenant je vais lire ton billet au-delà de l’intro, ça m’intéresse effectivement de savoir ce que tu fais, et avoir un peu de théorie dans mon métier alors que j’ai fait des études d’autres choses ça peut pas faire de mal.

    1. Je suis pas sûre que la culture théorique des informaticiens « de formation » dépasse pour beaucoup le « vernis culturel »… Bon, j’ai peu fait d’info en école, donc je sais pas trop. Mais j’espère que ça sera intéressant 🙂

  4. Salut Balise,

    En lisant ton blog je me dis que tu aurais du venir poser tes balises (haha) dans ma contrée auvergnate, tu te ferais plaisir avec mes projets 🙂 Où comment se trouver en face de chercheurs assez fous pour te sortir des projets sur lesquels tu ne commences pas par te demander « quel framework je prends » mais « est-ce que c’est NP-complet? » C’est rigolo n’empêche, tous ces cours d’algo, d’optim, de théorie des graphes, qui m’ont passionné peut être autant que toi… je n’aurai jamais pensé les appliquer à ce point dans un milieu industriel. Datastage est tellement loin 🙂

    1. Tiens, un Poussin. C’est fou ça 🙂
      Tu me vois ravie de voir qu’il y a des gens en dehors de l’académie qui se posent ce genre de questions – ça rassure un peu 🙂 C’est bien, tu me corrigeras dans les billets suivants si je dis des conneries plus grosses que moi 😛
      (Et quand à Datastage, j’y ai échappé et je m’en plains pas 😛 Mais oui, je vois ce que tu veux dire…)

  5. Lu, intéressant, alléchant (on voit la synergie avec le blog de cuisine), j’attends la suite.

    Remarques :
    >Notons accessoirement que faire rentrer ceci ou cela dans
    >le domaine de l’informatique peut toujours prêter à débat.

    Il y a dans le dernier Pour la Science (ou çui d’avant N-?) un article sur l’« information » que certains voient comme la matière ultime de l’univers (pas faux si nous sommes dans la Matrice). L’informatique étant la science de la manipulation de l’information, tout peut donc être soumis à l’informatique.
    (Certains comme moi disant plutôt que l’informatique ce sont les maths moins l’infini, plus du vaudou, ou Murphy.)

    1. Je note donc que j’ai oublié un adjectif (genre le « théorique » après « informatique », ça a plus de sens), et je m’en vais corriger ça de ce pas. J’aime beaucoup ta définition, cela dit 🙂

  6. 2è remarque :

    >l’apprentissage automatique dans l’informatique théorique,
    >parce que ça me paraît encore très expérimental (on a
    >modifié ce paramètre là et par conséquent l’ordinateur
    >reconnaît 2.2% de plus de chats)

    C’est comme toute l’intelligence artificielle, au départ un rêve mirobolant, et à la fin une bête collection d’algorithmes avec leur mode d’emploi pour ingénieur, et on se dit « ben non c’est pas de l’intelligence, juste un bête algo ». Nos systèmes de reconnaissances de forme ne sont peuêtre pas plus subtils, juste sélectionnés par la sélection naturelle (mauvais paramètre = sujet dévoré par un prédateur avant l’âge de la reproduction).

    1. J’ai une image très frustrante de l’apprentissage automatique et de l’AI en général. Je sais pas si elle est valide, parce que j’ai pas vraiment étudié le sujet, parce que j’en ai une image frustrante (poule, œuf, tout ça). C’est l’image d’un mec qui tourne des potentiomètres pour que son algo fasse ce qu’il veut, et qui après sort des stats de résultats sur son réglage de potentiomètres. Je me dis que c’est forcément plus subtil que ça, mais j’avoue un préjugé violent sur la question. Et le préjugé est que ça manque violemment de science et de maths et de preuves, leurs trucs. Et en même temps, il faut bien admettre qu’il y a des résultats « pratiques » qui sont très jolis. Les résultats de ce genre de choses : http://rtw.ml.cmu.edu/rtw/ m’éclatent profondément. Le process derrière, pas du tout 🙂

      1. Ça peut donner des résultats sans avoir de fondement, ça s’appelle du bricolage, de la bidouille, de l’expérimentation, du tâtonnement… On a bien utilisé les flèches, les canons, les catapultes tout en ayant une conception totalement fausse (Aristote…) de la physique sous-jacente.

        Pareil en médecine. Le corps humain est tellement complexe qu’on marche par essai-erreur. Pour chercher des médicaments, on teste parfois de manière automatisée des milliers de variantes d’une molécule, et on regarde celle que les microbes aiment le moins.

        Je pourrais généraliser à la Vie tout entière. Un corps humain est un gigantesque bricolage, mais ça se voit que Mère Nature théorisait que dalle.

      2. > mais ça se voit que Mère Nature théorisait que dalle.

        Ouais, ya qu’à voir les ornithorynques…

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s