Mois : juin 2014

Les algorithmes PPZ et PPSZ

Publié le par Balise2 commentaires

Aujourd’hui, on va causer 3-SAT, et on va en particulier causer de deux algorithmes très voisins, les  algorithmes PPZ et son petit frère PPSZ.

Il est plus que temps que je m’attaque à ce billet que j’aurais dû écrire depuis longtemps déjà. C’est un billet qui me tient à cœur parce que ça fait un an et demi que je fais des trucs autour de ces algorithmes, et que je commence à en avoir une assez bonne idée 🙂

Rappelons un peu de formalisme, histoire qu’on sache tous de quoi on est en train de parler. Pour une intro avec un peu plus de détails, voir mon billet sur SAT. J’ai n variables x_1,..., x_n, et j’ai des formules qui sont de ce type:

(x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_3 \vee x_4) \wedge (x_6 \vee x_7 \vee x_8) \wedge ...

et je veux déterminer si, étant donné une telle formule, il existe des valeurs pour les variables x_1 à x_n (on parle d’une affectation) qui permettent d’évaluer la formule à 1 (on dit alors que la formule est satisfaite). Dans le cas général, c’est un problème NP-complet ; on a donc peu de chance de trouver un algorithme efficace qui marche à tous les coups. C’est bien le « à tous les coups » qui m’intéresse ici : je me demande ce que je peux garantir pour mon algorithme, même si je tombe sur la formule la plus difficile du monde. Le « record » actuel pour ce type de garantie est actuellement pour l’algorithme PPSZ, qui est un algorithme aléatoire, et qui est le sujet de ce billet. Comme je parle d’algorithme aléatoire, il me paraît un poil plus intuitif de parler de probabilité de succès que de temps d’exécution même si, on l’a vu, les deux notions sont liées – puisqu’il suffit de répéter un algorithme aléatoire avec une probabilité de succès donnée suffisamment de fois pour être raisonnablement sûr qu’il réussisse. Ça fait un peu Shadok, mais passons. Je vais aussi, dans ce qui suit, supposer que j’ai une formule pour laquelle je sais qu’il existe un ensemble de valeurs qui la satisfont, et que je veux « juste » trouver les valeurs en question. En pratique, les deux problèmes sont liés aussi : je peux supposer que si mon algorithme trouve ces valeurs, ben c’est qu’elles existent, et que si je cherche suffisamment longtemps sans les trouver, ça serait quand même pas de bol qu’elles existent et que je les aie ratées.

L’algorithme aléatoire le plus simple auquel on peut penser est de prendre des valeurs au hasard, de vérifier si elles satisfont la formule, et de recommencer si c’est pas le cas. Toutes les affectations possibles ont la même probabilité (si je les choisis au hasard comme ça) – et j’en ai 2^n – parce que pour chaque variable, j’ai deux possibilités, 0 ou 1. Donc la probabilité de succès de cet algorithme, si j’ai \ell affectations qui satisfont ma formule, est de \ell / 2^n : parmi les 2^n choix que je peux faire, j’en ai \ell qui marchent.

Après, il y a moyen de faire les choses de manière un peu plus intelligente. Plutôt que d’affecter les variables toutes en même temps, je vais les affecter une à une. Qu’est-ce que ça change ? Ça change que si j’ai un truc qui est trivialement idiot à faire, je peux éviter de le faire. Ce qui veut dire qu’il faut que j’explique ce que ça veut dire « trivialement idiot ». Supposons que j’aie une formule très simple qui soit juste (x_1 \vee x_2 \vee x_3). Si j’ai choisi pour x_1 la valeur 0 et pour x_2 la valeur 0, il est « trivialement idiot » de choisir 0 pour x_3 puisque je n’ai alors aucune chance de satisfaire la formule. Donc par « trivialement idiot », je veux dire qu’il y a une clause qu’il n’y a plus qu’une seule chance de satisfaire, c’est-à-dire qu’on a déjà affecté des valeurs à deux variables sur les trois de la clause, et que la clause n’est toujours pas satisfaite. Si j’utilise mon algorithme précédent, j’ai une probabilité 7/8 de trouver une affectation satisfaisante (parce qu’avec probabilité 1/8 je tombe sur 000 pour mes variables et ma formule n’est pas satisfaite). Si j’essaie d’éviter les trucs trivialement idiots… ben déroulons le truc. Je commence par x_1, il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. Je continue par x_2 ; là encore, il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. J’arrive à x_3, et là j’ai deux possibilités. Si x_1 et x_2 ont été mis tous les deux à 0, j’ai un truc trivialement idiot à éviter, c’est de mettre x_3 à 0, donc j’évite ça, je mets x_3 à 1, et ma formule est satisfaite. Si x_1 ou x_2 a été mis à 1, quoi que je fasse sur x_3 sera valide, donc je ne peux pas me tromper. Sur ce cas spécifique, rien qu’en évitant les trucs trivialement idiots, mon algorithme passe à une probabilité de succès de 1.

C’est pas toujours aussi idyllique, évidemment – là les choses se passent bien parce que j’ai une seule clause, beaucoup d’affectations valides, et qu’on est contents. Maintenant, un cas un peu plus sioux : considérons la formule

(x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee \bar x_3) \wedge (x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_2 \vee \bar x_3) \wedge (\bar x_1 \vee x_2 \vee x_3) \wedge (\bar x_1 \vee x_2 \vee \bar x_3)

Deux affectations satisfont cette formule : x_1 = 1, x_2 = 1, x_3 = 0  et x_1 = 1, x_2 = 1, x_3 = 1. Avec mon algorithme « simple », la probabilité de succès est de 2/8 = 1/4. Avec mon algorithme qui cherche à éviter les trucs « trivialement idiots »… aussi, dans certaines conditions. Si je commence par la variable x_1 et que je la mets à 0, je n’ai aucune chance d’obtenir une affectation satisfaisant la formule. Si je continue par la variable x_2 et que je la mets à 0, idem. Donc il faut que je mette x_1 et x_2 à 1 tous les deux, ce qui arrive avec une probabilité 1/4 ; x_3 peut être mis à n’importe quelle valeur, donc si on n’a pas fait d’erreur jusqu’ici on n’en fera pas non plus à la dernière étape. Dans ce cas, donc, la probabilité de succès avec ou sans la détection de trucs « trivialement idiots » est la même. Sauf que… si on traite les variables non pas dans cet ordre là mais, par exemple, dans l’ordre x_3 x_2 x_1… Pour la première variable, x_3, on ne peut pas faire d’erreur, quelle que soit la valeur d’affectation. Pour x_2, on ne peut pas détecter de truc trivialement idiot, donc on la met à la bonne valeur avec une probabilité 1/2. Mais si cela arrive, la clause (x_1 \vee \bar x_2 \vee \bar x_3) ou la clause (x_1 \vee \bar x_2 \vee x_3) (selon la valeur affectée à x_3) indiquera à l’algorithme que mettre x_1 à 0 est trivialement idiot, ce qu’il faut éviter. Avec cet ordre de variables, la probabilité de succès de notre algorithme amélioré passe à 1/2. Il y a donc de « bons » ordres de variables et de « mauvais » ordres de variables (on parle de permutations). Comme il est difficile de savoir avant de commencer si une permutation est bonne ou mauvaise (ou comment trouver une bonne permutation), on fait comme d’habitude : on prend une permutation au hasard et on espère qu’en moyenne ça marche bien.

C’est exactement ce que fait l’algorithme PPZ (nommé d’après ses trois auteurs, Ramamohan Paturi, Pavel Pudlák et Francis Zane, dans un papier intitulé Satisfiability Coding Lemma) :

  • On part d’une formule F sur n variables, et on commence avec une affectation vide (on n’affecte aucune valeur aux variables pour l’instant).
  • On choisit un ordre aléatoire pour les variables, et on les traite une par une dans cet ordre :
    • Pour la variable courante x_i, si x_i = 0 est trivialement idiot, on affecte 1 à x_i
    • Sinon, si x_i = 1 est trivialement idiot, on affecte 0 à x_i
    • Sinon, on affecte une valeur aléatoire à x_i
    • Et on passe à la variable suivante.
  • Si l’affectation qu’on trouve satisfait la formule, c’est terminé ! Sinon, on recommence au départ.

L’analyse de la probabilité de succès de l’algorithme est relativement simple. Sans rentrer dans les détails, l’idée c’est que si je n’ai pas le choix pour une variable (c’est-à-dire si la mettre à 0 ou à 1 fait que l’affectation ne peut pas être satisfaisante), alors j’ai au moins une clause qui rend ce choix trivialement idiot dans au moins une permutation sur trois (parce que dans un cas sur trois, la variable en question arrivera en dernier dans la clause en question). J’ai toujours des choix aléatoires pour certaines variables, donc l’algorithme peut toujours se vautrer lamentablement, mais la probabilité de ne pas se vautrer est meilleure que si on prend juste une affectation au hasard.

Après, le lecteur attentif se sera peut-être dit « ouiiii mais si j’assigne x_1 à 1, j’ai à la fois une clause (\bar x_1, x_2, x_3) et une clause (\bar x_1, x_2, \bar x_3), donc quelque part c’est AUSSI trivialement idiot de mettre x_2 à 0… ». Le lecteur attentif est un petit malin. Et c’est aussi, quelque part, ce que fait l’algorithme PPSZ (nommé d’après les trois auteurs précédents + Michael Saks, dans un papier intitulé An Improved Exponential-Time Algorithm for k-SAT) : plutôt que de regarder les clauses une à une pour voir si par hasard on peut éliminer un choix trivialement idiot, on en regarde beaucoup à la fois (typiquement \log \log n, où n est le nombre de variables de la formule) pour tenter d’en tirer les mêmes conclusions. il y a un nombre sous-exponentiel d’ensembles de \log \log n clauses, et examiner chacun d’entre eux peut se faire en temps sous-exponentiel aussi (on peut se contenter de regarder toutes les valeurs possible pour le sous-ensemble de variables qui interviennent dans ce sous-ensemble de clauses). Les mauvais choix ne peuvent plus nécessairement être qualifiés de « trivialement idiots » mais peut-être de « manifestement idiots » ; le résultat est le même : si on peut les détecter, autant les éviter. Pour le coup, l’analyse de la probabilité de succès de cet algorithme est (beaucoup) plus complexe ; pour la petite histoire, lorsque l’article original a été publié, les auteurs n’avaient établi la probabilité de succès que dans le cas où la formule n’avait qu’une seule affectation satisfaisante (l’analyse du cas général n’arrivait à prouver qu’une probabilité de succès plus basse). La preuve plus générale a été établie par Timon Hertli (3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General), mais il s’est passé plus de dix ans entre l’introduction de l’algorithme et la preuve en question. Une version « lisible » (pour une certaine définition de « lisible, admettons-le) de la preuve en question est disponible dans ma thèse de semestre (chapitre 2) – elle est difficile à résumer en moins de, mettons, 8 pages (heu, déjà 8 pages, c’est challenge, en fait.)

J’ai travaillé autour de ces algorithmes depuis un an et demi (pas complètement par hasard, Timon dont je parle précédemment étant doctorant à l’ETH… et mon superviseur sur tout ce que j’ai fait), et pour le coup c’est probablement LE sujet sur lequel je me sens prête à répondre à BEAUCOUP de questions 🙂

 

Hackable numéro 1

Publié le par Balise3 commentaires

Hop, je pique l’idée à Christophe qui fait ça (mieux que moi) plus ou moins régulièrement pour des magazines divers dont Pour La Science : une revue du numéro 1 de Hackable, le petit dernier des éditions Diamond.

J’ai vu passer l’annonce du magazine il y a quelques semaines, et je me suis abonnée sur un mélange de coup de tête et de « de toute façon si je veux voir ce truc à Zürich j’ai pas le choix il faut que je l’importe moi-même ». Ça tombait bien parce que je venais de ressortir l’Arduino qui traînait dans un placard (et qui traîne maintenant sur mon bureau), de me faire expédier un fer à souder digne de ce nom et de faire mes premières commandes chez Farnell. Le positionnement du magazine me paraissait à peu près à mon niveau (à la différence d’OpenSilicium du même éditeur qui me fait un peu peur tout de même), et donc voilà. Le premier numéro est arrivé dans ma boîte aux lettres aujourd’hui, un peu en avance sur ce à quoi je m’attendais, mais on va pas se plaindre. Et dans une enveloppe manuscrite, sisi.

Au sommaire de ce premier numéro :

  • un long édito qui présente le concept du magazine et qui fait un peu de philosophie sur la récupération d’équipements électroniques divers – bon, c’est un édito, j’ai pas trop d’avis sur la question
  • une rubrique « Actualités » qui présente les bidules « bientôt à la mode » – plutôt sympa, ça permet d’avoir une vague idée de ce qui se fait sans pour autant traquer l’info
  • un article qui discute des choses auxquelles faire attention quand on achète son fer à souder^W^W^W^Wsa station de soudage. Le débat soudure avec ou sans plomb me paraît bien moins clair que ce qui est expliqué dans l’article ; cela dit je soude au sans plomb et je rame, alors je sais pas 😛 Il y manque aussi à mon avis le conseil évident (mais pas plus que de pas manger le fil d’étain :P) de ne pas laisser un fer allumé quand on quitte la pièce, mais c’est aussi vrai pour un fer à repasser, alors… 🙂
  • un article pour faire de l’Arduino sans Arduino (ou de manière générale faire mumuse avec des micro-contrôleurs autres qu’Arduino) : j’ai à peine parcouru, c’est du matos que j’ai pas, et l’article tient du tutoriel « hands-on » (ce qui est pas un mal en soi, juste c’est moins intéressant quand on a pas le matos)
  • trois articles qui visent clairement à poser les bases Arduino pour commencer à faire des machins marrants par la suite – l’ensemble forme un tutoriel sympa et accessible :
    • un article qui présente l’Arduino Starter Kit, ce qu’il y a dedans et comment le préparer pour pouvoir commencer à faire des trucs
    • un article d’intro à Arduino lui-même : histoire d’Arduino, ce qu’il y a sur la carte, et comment installer l’IDE
    • un article d’intro au langage de programmation Arduino
  • un article sur la loi d’Ohm, bien fichu et avec un bon mélange théorie/pratique
  • un article qui explique comment ajouter une horloge RTC à un Raspberry Pi pour qu’il puisse retrouver l’heure même quand il a pas de réseau – j’ai pas de RasPi, mais l’article était sympa du point de vue de l’explication des composants et de la mise en œuvre du bidule
  • un projet en deux parties de « sonnette intelligente » à base d’Arduino, que j’ai l’intention de mettre en œuvre bientôt parce que pourquoi pas ; la deuxième partie est une intro à l’utilisation d’afficheur LCD, c’est plutôt choupi – je regrette que la liste de composants ne soit pas un peu plus détaillée : « un bouton poussoir » ou « un buzzer » me paraissent un peu léger, surtout quand on s’adresse à des débutants qui risque d’être vite paumés devant le site de leur revendeur de composants favoris ; il semble que ce soit des composants standard du starter kit Arduino, mais je ne suis pas complètement sûre (et sauf erreur ce n’est pas précisé)
  • un article sur le démontage d’une cigarette électronique, plutôt rigolo même si on n’est pas familier du bidule du tout
  • un article sur la PWM, ou Pulse-Width Modulation, qui explique comment ça marche à grands coups de pizza aux olives (véridique).

Bref, un premier numéro solide, que j’ai apprécié, et dont j’ai l’intention de mettre en œuvre un projet (et si j’avais pas déjà fait un tuto Arduino, ça aurait été l’occasion) ; un peu de théorie, un peu d’actualité et d’articles plus généralistes : plutôt un bon mix, le tout didactique et à un niveau qui me va bien. La valeur ajoutée me paraît particulièrement intéressante pour les non-anglophones : la doc du starter kit Arduino recoupe probablement une bonne partie du dossier Arduino au milieu. J’aurais apprécié un projet de plus, je crois, surtout pour un bimestriel - ça va pas m’occuper deux mois cette affaire - mais globalement c’est chouette. Un très, très gros bémol pour finir cela dit : l’ensemble aurait VRAIMENT mérité une relecture ortho-typo digne de ce nom. Il y a littéralement plusieurs fautes (de grammaire souvent) par page, ça déconcentre parfois brutalement le lecteur… (j’ai une réaction allergique aux participes passés utilisés à la place des infinitifs et inversement).

#balisebooks – Mai 2014

Publié le par Balise1 commentaire

Hop, c’est l’heure d’écrire le #balisebooks de mai, attendu qu’on est mi-juin… Pas grand chose d’hyper-folichon ce mois-ci, j’ai aussi assez peu lu, ça aide pas.

Delirium, de Lauren Oliver (même titre en français) est assez classique dans le concept « dystopie YA ». À leurs 18 ans, tous les habitants sont opérés pour les libérer d’un terrible fléau : « amor deliria nervosa ». Plus d’amour, plus de problème, en gros. Évidemment, Lena, quelques semaines avant sa procédure, rencontre Alex – et les ennuis commencent. Lisible, sans plus. La fin était relativement peu usuelle, mais un mois après avoir fini de le lire je ne m’en souvenais plus…

Blackbirds, de Chuck Wendig (même titre en français) part d’un postulat intéressant : l’héroïne, Miriam, sait quand et comment les gens qu’elle touche vont mourir. Du coup, ceux qui vont mourir bientôt, elle les trace histoire de pouvoir en profiter pour leur piquer des trucs, tant qu’à faire, ça permet de bouffer. Et puis un jour, elle rencontre quelqu’un qui, visiblement, au moment de mourir dans un mois, dit son nom. L’accident bête. C’était pas mal et c’était plutôt drôle, mais c’était pas vraiment mémorable, beaucoup de longueurs, et un peu trop de gore gratuit.

Moon Called, de Patricia Briggs (L’Appel de la Lune, en français) est le premier tome des aventures de Mercedes « Mercy » Thompson, mécano et coyote-garou de son état. Le gros événement du tome, c’est quand Mercy trouve un cadavre sur le seuil de sa porte, et que l’Alpha du pack de loup-garous local, Adam, se fait kidnapper sa fille. Et, heu, voilà. C’était une lecture plutôt sympa, Mercy est chouette (j’aime bien le fait qu’elle soit mécano), les dialogues ont une vague saveur Buffy-esque, bref, plaisant. Et du coup j’ai attaqué le suivant dans la foulée.

Blood Bound, de Patricia Briggs (Les Liens du sang, en français), est donc le deuxième tome du précédent. Là, tout commence lorsque Mercy a l’idée saugrenue de rendre service à son copain vampire Stefan et de l’accompagner rendre visite à un autre vampire qui vient d’arriver dans le coin, histoire de lui expliquer un peu la vie. Il y a un peu plus de détails sur l’univers dans ce tome-ci que dans le précédent, ce qui est toujours sympa. Et j’ai eu du mal à le lâcher, celui-ci, je dois dire.

S’il ne fallait en lire qu’un… Moon Called, parce que c’est le premier d’une série prometteuse, je suppose.