Catégorie : Theoretical CS

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

Publié le par Balise15 commentaires

Ç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 🙂

Random insomniac thoughts about sudoku, CSPs and SAT

Publié le par Balise

(Writing in English because for some reason (probably the fact that my courses on the subject are in English) my inner monologue is in English on this subject, so…)

This post will probably be fairly obscure to… err… I’d say anyone but me, but that would be kind of pretentious 😉 Let’s just say that if you haven’t heard the acronyms SAT or CSP before, you can probably skip this post, unless you’re very curious. If you have questions, remarks, don’t hesitate. I have no idea what I’m doing either.

Last night I did some Project Euler problems before going to bed, and I inadvertantly clicked on this one: Problem 96 – Devise an algorithm for solving Su Doku puzzles. And while I know that I shouldn’t go to bed with a problem I’m able to easily formulate in my head, I did anyway (because it was late), and an hour or two of mild insomnia followed, because I was thinking of said problem. Typical. Or, as I put it a while ago, « don’t derive and try to sleep ».

This is a collection of random thoughts on the subject; I obviously didn’t give it A LOT of thought, it’s more of a general interrogation post, because I think the exercise in itself isn’t bad. Also, I haven’t hit the litterature at all – so there’s a fair chance I’m only saying stuff that’s either trivial, stupid or wrong 😉

The problem of regular 9×9 sudoku, per se, is « easy ». Well, it’s not « easy » in that I’d probably need some hours of thought and a some hours of sweat implementing it, but I’m pretty confident I could get there, at least for a decent approximation of a decent algorithm. But anything I’m saying from now on doesn’t have anything to do with the question of solving a given 9×9 sudoku in a « reasonable » amount of time – I’m only interested in the « theoretical » problem.

What’s not obvious to me is the « best » way to model and solve the associated CSP or SAT instance. Again, for a « regular » sudoku, one could argue that the size of the problem is constant and that the « best » way to model and solve doesn’t matter much since it will also be constant. However, since I’m (originally) interested in solving the Project Euler question, the size of the constant actually matters to me – if it’s « gazillions », it’s not good enough for me. Moreover, the Sudoku problem for nxn problems is known to be NP-complete (haven’t read that paper yet, intend to). Also note that I’m not that interested in the decision problem (« is there a solution to this instance of sudoku ») but in finding an assignment that actually solves said puzzle.

There are two straightforward ways to model sudoku:

  • as a regular CSP problem, where each variable represents a cell and can take a value between 1 and n.
  • as a SAT problem where we define n boolean variables for each cell, each of which saying « does this cell take this value? »

A priori, both models have their merits; the CSP has the advantage of compactness and (human) readability, and the SAT has the advantage of being boolean (duh). Note that in any case, any nxn problem can be modelled in same way (by expressing the constraints of the grid, which is very regular), and the particular instance of the puzzle can be seen as an initial partial assignment on the problem (which will remove some constraints and some variables in some constraints). I’m not entirely clear on the number of constraints in both cases, I’d need some time with a pen and paper for that. Also, considering a SAT problem, the exact number of variables in a « reasonable » 3SAT reduction would need some work also. Probably not « hard » work, but « careful » work (and I’m not that good at careful 😉 ).

Now if I consider that I have a model, what are my options? (Again, this is a worst-case analysis – there’s a fair chance that most « real-world » puzzles won’t need that kind of machinery, but some instances ARE hard (the problem IS NP-complete). But by the way, what makes an « easy » sudoku puzzle, and is it possible to decide whether a given instance is easy or not? Anyway, for the general case, the three possibilities that I’m thinking of right now are randomized algorithms, so any runtime I’m talking about is expected runtime.

  • Apply PPSZ (beware, it bites) to the (3-)SAT problem. A bound on the runtime here would be 1.308^k, where k is the number of variables that I haven’t computed yet.
  • Use a PPZ-like approach on the CSP instance – consider a random permutation of the variables and treat them in order; pick, for each variable, a value uniformly at random in those that are not forbidden by the current partial assignment.
  • Use a « random downsampling » approach (for each cell, keep two values uniformly at random) and apply PPZ to the resulting instance.

Those two last approaches were part of an exercise in the latest SAT graded sheet I (tried to) solve(d), so I have some idea on how the analysis would go through in that case. It would still need some work, obviously (especially since the problem is slightly different).

Another question is, since the problem is very structured, can I use this structure to my advantage to make the algorithm faster, prove that the general algorithm is faster in this particular setting, or to get an easier analysis?

Still in the « random questions » – sudoku can be seen as the problem of « rainbow coloring » a n-regular hypergraph where each vertex is part of exactly 3 edges. How would previous algorithms behave on a more general case? (non n-regular and/or with an arbitrary number of edges per vertex). This kind of reflexion gives me the intuition that indeed, the structure of the problem can be used to get better algorithms and/or bounds. But I may obviously be wrong.

Last one, and then I’m leaving you 😉 – this is a more general question regarding SAT vs CSP. SAT domains and constraints and stuff can be represented in a hypercube where every possible assignment is a vertex and two vertices are connected iff there differ by exactly one coordinate. The hypercube model is a nice way to look at the SAT problem from a different perspective, and definitely has its uses. Is there any geometrical structure that would be useful in the same way (or in some way) for CSPs and variables whose domain is not reduced to 2 boolean values?