TPA : Mincut, maxflow et réseaux de distribution d’eau

Je viens de regarder une vidéo intitulée Efficient Maximum Flow Algorithms (en anglais), et comme je me demandais depuis quelques jours ce dont je pourrais bien parler dans un TPA, c’est arrivé à point nommé. Donc, aujourd’hui, on va parler de « max flow » ou, en français, « flot maximum ». Commençons par donner un petit exemple. Supposons qu’on veuille trimbaler de l’eau depuis un point A à un point B. Pour cela, on dispose d’un réseau de tuyaux qui ont tous une certaine capacité, en terme de nombre de litres par seconde qui peuvent y circuler, et on se pose la question de savoir combien de litres par seconde peuvent arriver au point A. Faisons un petit dessin :

maxflow1

On a le point A, le point B, quelques points intermédiaires reliés par des tuyaux, et la capacité de chaque tuyau est indiquée sur chaque tuyau. Sur un « petit » réseau comme celui-ci, on peut s’en sortir en regardant très fort le schéma et en tentant de répartir l’eau au maximum dans les tuyaux de façon à ce qu’aucun tuyau ne soit en surcapacité, sinon ça explose et ça fait désordre (spoiler : sauf erreur grossière de ma part, on arrive avec ce réseau à 5600 litres par seconde).

Évidemment, plus le réseau est compliqué, plus le calcul l’est, et au-delà d’une certaine taille ça devient franchement pénible à faire à la main. Beaucoup de gens se sont intéressés au problème, qui est à la fois considéré comme un problème « classique » voire « résolu » (par exemple la bibliothèque C++ Boost a quelques implémentations pour le résoudre), et comme un domaine actif de recherche (il est, par exemple, en couverture du numéro d’août des Communications of the ACM). Au lieu de parler de litres d’eau et de tuyaux, on utilise notre modèle préféré, qui est celui d’un graphe (comme le laisse vaguement sous-entendre mon petit schéma au-dessus) ; le type de graphe qu’on considère a cependant quelques éléments supplémentaires par rapport aux graphes que nous avons manipulés jusqu’ici, par exemple lorsque nous avons parlé du théorème des cinq couleurs. On a, comme d’habitude, des sommets (les points A, B et les points intermédiaires) et des arcs (les tuyaux). Dans les sommets, on a deux sommets « spéciaux », les points A et B, que l’on appelle la source et le puits. Sur les arcs, on a deux informations supplémentaires : la direction, représentée sur le schéma par une flèche (on dit que le graphe est dirigé) et la capacité. Et on veut trimbaler une certaine quantité de trucs, c’est-à-dire un « flot », de A à B. Le problème peut donc être formulé comme « étant donné un graphe dirigé, dont les arcs ont des capacités, et étant donnés une source et un puits, quelle est la quantité maximum de flot qui peut être transportée de A à B ? ». Les algorithmes permettant de répondre à cette question ne sont pas forcément très compliqués, mais ils sont plus longs que ce que j’ai envie de détailler ici. Il en existe plusieurs, et il peut être intéressant de ne pas utiliser les mêmes en fonction du graphe considéré (on n’utilisera par exemple pas forcément le même algorithme pour un graphe ayant peu ou beaucoup d’arcs).

Considérons maintenant un autre problème. Supposons que j’aie une fuite massive d’eau en B, et que je veuille couper l’eau qui arrive en B en coupant la circulation dans des tuyaux, et ce de la manière la plus « efficace » possible. L’efficacité, dans mon exemple imaginaire, se mesure en débit total des tuyaux que je coupe : je veux le minimiser, pour que la reprise du service soit la plus facile possible. Quels tuyaux dois-je couper ? Il faut impérativement que je coupe le tuyau direct à 4000 entre A et B (sinon j’ai forcément de l’eau qui continue à arriver en B). Je peux couper tout ce qui arrive en B : j’ai deux tuyaux à 1000 et un à 900, ça fait un « coût » total de 2900. Mais en regardant d’un peu plus près mon graphe, plutôt que de couper l’arrivée en B, si je coupe les départs en A (hors la ligne à 4000, qui est coupée quoi qu’il arrive), je peux m’en sortir pour 2300, c’est mieux. Et en regardant d’encore plus près, si au lieu de couper le tuyau à 2000 je coupe celui à 500 et celui à 800, je descends à 1600 (300 + 500 + 800). Coïncidence amusante, si je fais la somme de tous les tuyaux que je coupe (4000+300+500+800), j’obtiens le même nombre que le nombre maximum de litres que je peux faire circuler dans mon réseau entre A et B, c’est à dire 5600.

Il se trouve que ce n’est pas une coïncidence. Ce second problème est connu sous le nom de « min cut » ou, en français, « coupe minimum » : étant donné un graphe avec des coûts ou poids sur les arcs, comment déconnecter deux points donnés A et B en supprimant des arcs de manière à ce que la somme de leurs poids soit minimum ? Et étant donné un graphe dirigé avec des capacités/poids, le théorème dit « min cut/max flow » dit que, pour toutes les paires de sommets A et B du graphe, la quantité maximum de flot qui peut aller de A à B est égale au poids minimum des arcs à supprimer pour déconnecter A et B. Pour donner une idée de la preuve, on peut voir qu’une coupe (un ensemble d’arcs qui, lorsqu’on les supprime, déconnecte A et B) est un goulot d’étranglement : il est impossible de faire passer plus de flot entre A et B que la capacité des arcs qui forment cette coupe. Ça permet de déduire que le flot maximum est forcément inférieur (ou égal) au poids de la coupe minimum. L’autre direction (montrer que la valeur de la coupe minimum est effectivement atteinte) est un peu plus délicate. L’idée est que si on a un flot maximum, alors on a des arcs qui sont saturés, c’est-à-dire que pour que le flot puisse passer de A à B, il faut faire passer une valeur de flot égale à la capacité de l’arc par l’arc en question. Si ce n’était pas le cas, on pourrait augmenter le flot, ce qui ne peut pas arriver (puisqu’on considère un flot maximum). On peut aussi voir que tous les chemins de A à B contiennent au moins un arc saturé – sinon, on pourrait augmenter le flot sur le chemin en question. Maintenant, on explore le graphe en partant de A, en avançant sur tous les chemins possibles, et on marque tous les sommets que l’on peut atteindre sans passer par un arc saturé. Si on retire tous les arcs qui partent de cet ensemble de sommets marqués vers l’ensemble des sommets non-marqués, on obtient une coupe (sinon il existerait un chemin de A à B contenant un arc non saturé). De plus, ces arcs sont saturés, et la somme de leur poids est exactement la valeur du flot maximum (puisqu’il s’agit de l’ensemble des arcs qui sortent de l’ensemble des sommets marqués). Donc la valeur de flot maximum est égale à la valeur d’une coupe, elle-même supérieure ou égale à la valeur de la coupe minimum. Tout ceci nous permet de déduire que la valeur de la coupe minimum est égale à la valeur du flot maximum (puisqu’elle lui est à la fois inférieure ou égale et supérieure ou égale), et donc on est contents. Pour une certaine définition de « contents » – l’idée de la preuve que j’ai donnée ici n’est pas des plus rigoureuse (en espérant qu’elle soit correcte, il a fallu que je m’y reprenne à trois ou quatre fois…), mais j’espère en avoir donné tout de même une idée raisonnable !

#balisebooks – Juin 2014

Quoi ? Poster le #balisebooks de juin le 1er juillet ? mais tout se perd…

Le mois de mai était peu inspirant, le mois de juin l’est bien plus, sur 6 bouquins lus, j’en ai mis 3 à 5 étoiles sur mon GoodReads - c’est rare.

Gameboard of the Gods, de Richelle Mead (L’Échiquier des dieux, en français) est le premier tome de la série Age of X (L’Ère des miracles, en français). On est balancé sans beaucoup de préliminaires dans une société future séparée en deux gros blocs principaux (en gros l’Amérique du nord (RUNA) et la Chine/Russie (EA)) et les « provinces » considérées comme plus ou moins barbares. Justin March a été exilé à Panama (l’une de ces provinces, donc) suite à des événements qui seront expliqués… plus tard. Mae Koskinen est une super-soldat du RUNA, et sa mission initiale est d’aller rechercher Justin March pour le sortir de son exil, pour des raisons initialement peu claires (mais qui, encore une fois, finissent par s’éclaircir). On ajoute à ça que, sur une base de société a priori très rationnelle et anti-religieuse, les dieux de panthéons divers ont apparemment une certaine tendance à laisser des empreintes de gros doigts partout, et ça donne Gameboard of the Gods. Et ben, c’est chouette. Ça me paraît un niveau au-dessus de Vampire Academy (bon, c’est pas très dur) et de Succubus (déjà plus dur, c’est pas mal, Succubus) et, une fois passé le « choc » du peu d’explications sur l’univers en question, on se retrouve avec un bouquin difficile à lâcher.

Unlocked: An Oral History of Haden’s Syndrome, de John Scalzi (pas encore de traduction en français) est une intro au prochain bouquin de Scalzi, Lock In. C’est l’histoire du syndrome d’Haden, une pandémie qui s’étend dans un futur relativement proche. Beaucoup de morts dans la première vague, et un certain nombre de gens se retrouvent conscients dans un corps presque complètement paralysé (en gros, le cœur et les poumons marchent, mais c’est à peu près tout). Unlocked raconte le début de cette épidémie et les différentes réponses apportées aux problèmes générés, le tout sous la forme de témoignages et d’interviews de gens qui y assistent. Ça se lit tout seul, et c’est super enthousiasmant pour Lock In (qui sort cet été… je sens qu’il va faire partie des trucs que je vais acheter au prix fort dès sa sortie).

The Alloy of Law, de Brandon Sanderson (L’Alliage de la justice, en français) se passe quelque 300 ans après la trilogie Mistborn - en gros, on mélange l’univers de Retour vers le futur III avec celui de Mistborn, on obtient celui de Alloy of Law. On a en gros la ville, Elendel, et le far-west autour. Waxillium « Wax » Landrian est né dans une bonne famille d’Elendel, a été shérif en-dehors de la ville, et revient maintenant à Elendel pour se marier et se ranger. Évidemment, c’est pas aussi simple : des convois de marchandises sont volés, sa fiancée est kidnappée, et Wax se retrouve, aidé par son acolyte Wayne et par la cousine de sa fiancée Marasi, au milieu de tout ce cirque. C’est drôle, les persos sont très chouettes, et en fait je me demande a posteriori pourquoi il a pas gagné ses 5 étoiles. Une suite semble prévue pour la fin de cette année, ça paraît une bonne idée.

Dark Currents, de Jacqueline Carey (pas de traduction française pour l’instant), est le premier tome de la série Agent of Hel. On y rencontre Daisy Johanssen, fille de démon, habitante de Pemkowet (le hub surnaturel du coin) et liaison humains/eldritch de Hel, déesse nordique. Un gamin est mort noyé dans des circonstances pas nettes, et Daisy se retrouve à enquêter. C’est plaisant, ça a clairement un feeling « Sookie Stackhouse », et c’est clairement en-deçà des Kushiel (et oui, c’était le reproche que je faisais aux Saints Astray aussi). Mais bon, on ne boude tout de même pas son plaisir.

A Widow for One Year, de John Irving (Une Veuve de papier, en français), est un des premiers bouquins que je relis depuis que j’ai commencé à écrire les #balisebooks (et/ou à lire sur tablette plutôt que sur papier, la corrélation exacte n’est pas claire). On y suit essentiellement quatre personnages, Ted Cole, Marion Cole, leur fille Ruth Cole, et Eddie O’Hare, embauché comme assistant/chauffeur de Ted alors que Ruth a quatre ans. L’histoire se passe à trois époques, lorsque Ruth a 4 ans, 36 ans et 41 ans, respectivement.  La première partie est centrée autour d’Eddie, la deuxième et la troisième partie sont plutôt centrées autour de Ruth. Il y a juste la bonne dose d’invraisemblance, c’est plutôt drôle, parfois dérangeant – bref, c’est pas mon Irving préféré (parce que c’est Cider House Rules, évidemment), mais ça reste de l’Irving, quoi. Bizarrement, j’avais déjà lu celui-ci il y a plusieurs années, et beaucoup de détails me sont revenus à la lecture, mais l’histoire principale m’avait complètement échappé.

The Martian, d’Andy Weir (pas encore de traduction en français) est, comment dire, absolument phénoménal. C’est l’histoire de Mark Watney qui, par un concours de circonstances idiot, se retrouve échoué tout seul sur Mars. Heureusement, il a quelques ressources à sa disposition, un cerveau en état de fonctionnement et une propension à transformer le désespoir en humour. J’ai éclaté de rire à plusieurs moments, j’ai été émue aux larmes (vraiment), et j’ai frénétiquement tourné les pages pour savoir CE QU’IL ALLAIT SE PASSER AAAAH plus d’une fois. C’est un peu « bon, j’ai ce problème à résoudre, comment résoudre ça ? <intense yak shaving> <problème résolu> et le problème suivant est… » pendant 350 pages, mais c’est très très bien fait. Et puis bon, c’est quand même un type qui résout tout un tas d’emmerdes avec de la SCIENCE et de l’ingénierie (et du duct tape), et ça fait du bien à lire, voilà (d’autant plus que la science est crédible, du moins à mon petit niveau). Très chaudement recommandé.

S’il n’y en avait qu’un à lire… The Martian.

Les algorithmes PPZ et PPSZ

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

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 :P 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

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.

#balisebooks – Avril 2014

Hop, un #balisebooks pour Avril, encore pas en avance, mais moins en retard que les précédents.

Buffy the Vampire Slayer, Season 8, tomes 1, 2 et 3, par… plein de gens (traduits en français sous le même titre), il faut bien le dire, est le début de la suite de la série Buffy sous forme de comics. J’ai les trois premiers tomes dans ma bibliothèque depuis une éternité ou deux, et je me suis enfin décidée à les lire. J’ai, de manière générale, du mal avec les comics – c’est nettement plus d’effort pour moi de faire attention à l’image que juste au texte, et beaucoup de comics ont la fâcheuse habitude de mettre un mot sur trois en gras, ce qui est très pénible. J’ai fini par attaquer le premier, et j’ai lu les deux autres dans la foulée. L’histoire se passe quelques… mois ? années ? après la saison 7 de Buffy ; le « big bad » de la saison (ou ce qui semble s’en approcher en tous cas) est introduit assez vite, et on suit les histoires plus ou moins parallèles des personnages habituels (un point « mouarf » pour l’arc autour de Dawn). C’est vraiment dans l’esprit de la série, les dialogues sonnent pareil (et sont toujours drôles), et j’ai pas eu de mal à m’y retrouver. Une très bonne surprise, il va falloir que je me procure la suite rapidement.

The Age of Innocence, d’Edith Wharton (Le Temps de l’innocence, en français), dans un tout autre domaine, se passe au XIXe siècle à New York. On y suit l’histoire de Newland Archer, fiancé à May Welland (qui a tout ce qu’il faut pour un mariage socialement acceptable) qui se trouve rencontrer Ellen Olenska, cousine de la susnommée, beaucoup moins socialement acceptable, mais beaucoup plus intéressante. C’était une lecture plutôt plaisante et assez reposante – on prend son temps, il m’a bien fallu une bonne dizaine de jours pour arriver à la fin des 300 pages – le niveau de lecture nécessaire est décidément plus élevé que mes lectures habituelles :) Il ne se passe pas grand-chose dans le livre, mais la représentation de la société y est très intéressante… et très drôle. Wharton est accessoirement devenue grâce à ce livre la première femme à obtenir un Pulitzer…

Santa Olivia, de Jacqueline Carey (pas de traduction française) est un peu décevant. J’ai beaucoup aimé tout ce que j’ai lu de Jacqueline Carey jusqu’à présent (voir un gros tag qui tache), et j’attendais beaucoup de celui-ci qui partait sur des prémisses intéressantes : dans une ville qui a été coupée du monde par le gouvernement US à la suite d’une épidémie grave plusieurs années auparavant, Loup est la fille d’un soldat génétiquement modifié avec des pouvoirs qui rappellent ceux des loups-garous (minus la fourrure et la pleine lune). Et sinon, ça cause de boxe. C’est pas mal, hein, et probablement d’un autre auteur j’aurais plus apprécié… mais là c’est très en-deçà des séries qui se passent à Terre d’Ange. Et ça aurait probablement mérité une relecture de plus – j’ai vu au moins deux "should of/would of" au lieu de "should have/would have"… ça arrive, mais ça devrait pas passer la relecture. Je me suis demandé si c’était voulu (pour représenter l’évolution de la langue ? l’accent local ?), mais je crois vraiment pas, d’autant plus que c’était vraiment des instances limitées…

The Hero of Ages, de Brandon Sanderson (Le Héros des siècles, en français), est le troisième tome de la trilogie Mistborn dont j’ai parlé au premier trimestre. Il se déroule environ un an après les événements du deuxième tome et, essentiellement, c’est à peu près la fin du monde, et heu… ben faut sauver le monde. En espérant même que ce soit faisable. C’est une excellente fin à une excellente série, en gros. Tous les tenants ont des aboutissants, l’ensemble de la série est cohérent et fascinant (je le répète, mais *rha* ce système de magie est grandiose), et le crescendo du début à la fin de la trilogie est mené de main de maître. J’ai eu beaucoup beaucoup de mal à lâcher mon bouquin sur les quelques soirées que j’ai passé avec (« allez, un dernier chapitre ? c’est pas raisonnable… bon, mais c’est le dernier, hein ! bon allez, cette fois-ci c’est vraiment le dernier ! »). La fin est épique, grandiose et émouvante (c’est rare qu’un bouquin me mette les larmes aux yeux tout de même, et ça a été le cas ici). Il y a un "Mistborn #4" qui se passe trois cents ans plus tard, il vient de tomber sur ma pile de trucs à lire.

A Study in Scarlet, de Sir Arthur Conan Doyle (Une Étude en rouge, en français), est la première aventure de Sherlock Holmes. J’ai récupéré une intégrale de Sherlock Holmes récemment, donc je rattrape mon retard en culture sherlockienne (j’ai bien aimé les deux films avec Robert Downey Jr et Jude Law, et j’adore la série de la BBC avec Benedict Cumberbatch et Martin Freeman). On y trouve l’introduction des personnages, l’histoire d’un meurtre (forcément), un gros flashback plein de Mormons (ou tout du moins d’une certaine représentation des Mormons), et de manière générale une chouette histoire (même si la révélation du meurtrier est un peu du type « wait wat? d’où c’est qu’il sort celui-là ? »).

Positron épisodes 1 à 4, de Margaret Atwood (pas encore de traduction en français), est le début d’un « feuilleton littéraire » publié uniquement sous forme électronique sous les titres I’m Starved for You, Choke Collar, Erase Me et The Heart Goes Last. L’histoire se passe dans une société dystopique qui a trouvé le remède ultime au chômage : les habitants de Consiliance passent un mois sur deux en prison en tant que prisonnier, et un mois sur deux hors de la prison en tant que gardes de prison et/ou autres jobs « civils ». Ça permet aussi de résoudre la crise du logement : il suffit d’avoir une maison pour deux couples, qui vivent un mois sur deux chacun dedans, sans jamais croiser les autres habitants de la maison. Facile, je vous dis. D’ailleurs, Stan et Charmaine sont parfaitement satisfaits de la situation. Sauf le jour où Stan tombe, dans sa cuisine, sur un mot doux planqué sous le frigo et signé Jasmine – et de là, tout part en sucette. Les épisodes/chapitres sont un peu inégaux – en particulier l’épisode 3 rame un peu – mais j’attends la suite.

Saints Astray, de Jacqueline Carey (pas encore de traduction en français), est la suite du Santa Olivia dont je parle plus haut. Loup et Pilar ont réussi à partir de Santa Olivia, et se font embaucher comme gardes du corps de luxe. On suit leur entraînement/formation et leurs premiers contrats, jusqu’à ce qu’elles décident de changer le monde parce que bon ça va bien ces conneries. J’ai préféré ce tome-ci au précédent : il est plus drôle, plus léger, et avec moins de boxe. Ça pourrait être niais, ça l’est peut-être un peu, mais j’ai surtout trouvé que c’était un bon moment de bonne humeur. Les persos restent sympa, et même si c’est du popcorn, c’est du bon popcorn :P

S’il n’y en avait qu’un à lire… The Hero of Ages.

Deux mémoires

Hier soir, j’ai fait un truc vachement bien : j’ai vaguement mis à jour ma page personnelle. J’en ai profité pour la déplacer sur un autre serveur, pour faire un peu de nettoyage, et surtout pour y publier les deux mémoires sur lesquels j’ai travaillé depuis un peu plus d’un an.

Le premier est un « mémoire de semestre » : on a la possibilité, à l’ETH, d’obtenir des crédits pour un module « Research in Computer Science » (recherche en informatique, donc), qui est en théorie un mini-projet de recherche. Comme je sais pas faire les choses à moitié, le mémoire en question fait une petite centaine de pages et il est possible qu’il explose le record du nombre de pages sur ce genre d’exercice. À ma décharge, ledit projet consistait à reprendre deux mémoires précédents par deux étudiants et à les réintégrer dans un cadre commun avec une notation développée entre temps. Le mémoire s’intitule Understanding the PPSZ algorithm for ClSP.

Le deuxième est mon mémoire de master – i.e. le projet de 6 mois à la fin des études. Celui-ci s’intitule Towards the derandomization of the PPSZ algorithm for the multiple satisfying assignments case, et il a même un zouli DOI (et ça, c’est classe, quand même.) Les deux projets sont liés (d’ailleurs on est en train de faire rentrer des morceaux du deuxième mémoire dans le premier mémoire pour tenter de publier tout ça), au sens où ils tournent tous les deux autour d’un même thème assez spécifique, mais les deux mémoires sont assez différents. Le premier était plus un boulot de lecture / compréhension / vérification / réécriture, avec assez peu de contenu original. Le deuxième mémoire était un boulot nettement plus exploratoire, et contient par ailleurs BEAUCOUP de résultats de type « on a essayé ça, ben ça marche pas. Ou alors pas trivialement. ».

Je ne vais pas rentrer tout de suite dans les détails et les explications de ce que racontent ces deux bidules – je ferai un billet plus tard sur le sujet pour essayer d’expliquer un peu ; pour ceux que ça intéresse, ça a essentiellement à voir avec SAT et avec un algorithme qui s’appelle PPSZ (et il faudrait sans doute que j’écrive la page Wikipedia de PPSZ, ne serait-ce que parce que ça me donnerait un truc à lier ici). Mais c’est une histoire pour une autre fois :)

#balisebooks – Premier trimestre 2014

Bon. Je suis à la bourre sur mon #balisebooks, parce que j’ai rien écrit depuis janvier. La faute à la thèse de master, sans doute (qui est rédigée et rendue, j’en parlerai sans doute un peu plus tard). Rattrapons donc ce retard inacceptable – et paf, vous gagnez trois mois d’un coup. Et probablement des remarques (encore) plus courtes que d’habitude, parce qu’évidemment je ne me souviens pas de tout !
Naamah’s Kiss, de Jacqueline Carey (pas encore de traduction en français) est le premier tome de la trilogie de Moirin. Cette trilogie se passe quelques générations après les trilogies de Phèdre et d’Imriel (voir juin, juilletseptembre, octobre et novembre) et a pour héroïne Moirin, fille d’une magicienne d’Alba et d’un prêtre D’Angeline dédié à Naamah. Ça reste proche des premières trilogies; cette fois-ci Moirin nous emène en Ch’in (oui, c’est la Chine) via Terre d’Ange. C’est très très lisible, j’ai beaucoup aimé (mais j’ai pas encore lu la suite, allez savoir pourquoi).

Spirit Bound et Last Sacrifice, de Richelle Mead (Lien de l’esprit et Sacrifice ultime, en français) sont les dernier tomes des Vampire Academy (voir novembre, décembre). Rose se met à la recherche de Dimitri dans le premier, et se retrouve en prison pour meutre dans le deuxième. Pas grand chose à en dire – c’était tout à fait lisible, c’était à peu près ce qu’il fallait à mon cerveau fatigué à ce moment là, c’est pas une série que je vais relire. La fin était sympa, cela dit.

Mistborn: The Final Empire, de Brandon Sanderson (L’Empire ultime, en français) a probablement gagné une place au panthéon de mes séries préférées. J’avais beaucoup aimé ce que Sanderson avait fait de la fin de Wheel of Time (voir Memory of Light) et je m’étais dit qu’il faudrait que je lise d’autres choses de lui, voilà qui est fait, et voilà qui n’est pas regretté. Le monde de Vin est divisé en gros en deux – les skaa (dont fait partie Vin), qui sont à peu de chose près les esclaves de la classe dominante, gouvernée elle-même par le Lord Ruler depuis un millier d’années ou à peu près. Vin rencontre une bande de voleurs qui ont un projet complètement dingue : renverser ledit Lord Ruler, histoire d’améliorer un peu le quotidien des skaa. On ajoute à ça un système de magie à la fois original, crédible et génial (les magiciens ou "allomanciens" mangent du métal et le "brûlent" pour obtenir différents effets en fonction du métal) – et ça fait un bouquin phénoménal. Vraiment. Hautement recommandé.

Up from the grave, de Jeaniene Frost (pas encore de traduction en français) est le 7e et dernier tome de la série Night Huntress (voir décembre). L’ancienne équipe de Cat a disparu, donc ils partent à leur recherche, ils terminent dans un bâtiment über-secret, ça fighte dans tous les sens, et voilà. C’était une bonne fin, avec à peu près toutes les histoires (primaires et secondaires) achevées, mais c’était pas spécialement mémorable.

Succubus Heat, Succubus Shadows et Succubus Revealed de Richelle Mead (mêmes titres en français) sont les trois tomes suivants de la série Succubus (voir octobre, novembre). Dans le premier, le démon du coin (et le boss de Georgina et du reste de la clique) se fait kidnapper, et les immortels perdent leurs pouvoirs. Ce qui rend le sauvetage plus compliqué, évidemment. Dans le second, Georgina se fait embarquer dans une espèce de longue hallucination qui la torture avec un mélange de flashbacks de son passé et de rêves divers. Dans le troisième, elle se fait transférer à l’insu de son plein gré à Las Vegas, ce qui est assez suspect. Comme pour le dernier tome de Vampire Academy, on dénoue tout ce qui restait à dénouer, et on termine la série plutôt satisfait. Au final une série plutôt chouette – j’ai lu les trois derniers à la suite à cause des cliffhangers de fin de tomes, mais c’était une lecture cool pour reposer le cerveau fatigué. J’ai nettement préféré ceux-ci à Vampire Academy.

The Wise Man’s Fear, de Patrick Rothfuss (La Peur du sage, en français) est le deuxième tome de Name of the Wind (voir décembre). On continue à suivre Kvothe dans son récit; il commence par prendre un semestre sabbatique pour tenter d’obtenir un patronage (et des sous). Et il apprend à se servir d’une épée et à se battre, aussi. Il y a un gros moment (une bonne centaine de pages, peut-être plus) assez bizarre au milieu du bouquin qui fait que j’ai moins aimé ce tome-ci que le précédent. Ça reste très, très bon – mais maintenant il faut attendre le tome 3. Dameunède.

Magic Bites, d’Ilona Andrews (Morsure magique, en français) est le premier tome de la série Kate Daniels – une mercenaire qui vit dans un monde plus ou moins post-apocalyptique, où "apocalypse" est le retour de la magie – la magie va et vient, et quand la magie est là, la technologie est complètement inutile ou à peu près. Au milieu de tout ça, on a des nécromanciens qui contrôlent des vampires, et un pack de garous. Le gardien de Kate s’est fait tuer, et Kate se met à la recherche de son assassin. J’avoue, j’ai pas vraiment accroché, mais je sais pas trop pourquoi. Peut-être l’impression que c’était un peu bordélique (on est balancé dans le monde en question sans beaucoup de préliminaires), peut-être le fait que j’ai pas réussi à cerner Kate Daniels… bref, j’ai pas accroché.

Machine of Death, de Ryan North et de plein d’autres gens (pas encore de traduction en français) est un recueil de nouvelles qui ont toutes le même point de départ : il existe une machine qui, sur une simple prise de sang au bout du doigt, est capable de prédire comment vous allez mourir (et qui vous le dit). Évidemment, la machine en question est souvent complètement cryptique et parfois auto-prophétique. C’est un recueil de nouvelles, donc il y a évidemment du bon et du moins bon, mais de manière générale c’est plutôt chouette. Il y a un deuxième tome sur les mêmes prémisses – je vais probablement me lire ça à l’occasion.

Disclosure, de Michael Crichton (Harcèlement, en français) est un bon gros thriller qui tache. C’est l’histoire de Tom, qui bosse dans une boîte high-tech qui fabrique entre autres des lecteurs CD-ROM – et dont le prochain produit promet d’enfoncer la concurrence parce qu’il est tellement plus rapide. (Lire tout ça vingt ans après l’écriture rend les choses assez rigolotes, il faut le dire). Il se fait piquer une promotion par une ex qui se fait plus ou moins parachuter – et qui l’accuse rapidement de harcèlement sexuel – ce qui est 1/ faux 2/ difficile à contrer. Plutôt chouette – et la fin était vraiment sympa.

The Well of Ascension, de Brandon Sanderson (Le Puits de l’ascension, en français) est le deuxième tome de Mistborn (voir plus haut). Nos héros se remettent des événements du premier tome tandis que la société s’adapte aux nouvelles circonstances. Manque de pot, la ville de Luthadel est bientôt assiégée par non pas une, non pas deux, mais trois armées. Une ancienne légende refait surface – peut-être un moyen de sauver tout le monde. Ça reste très très solide – j’ai résisté violemment à l’envie d’attaquer le troisième tout de suite. Et RHA cette fin. Sérieusement. Phénoménal.

Allegiant, de Veronica Roth (Divergente tome 3, en français) est le troisième et dernier tome de la série Divergent (voir… bin voir rien, en fait, les deux précédents sont passés dans la période sans #balisebooks, visiblement). La série Divergent commence dans un Chicago dystopique où les gens sont divisés en cinq factions qui représentent leurs traits de caractère. À leurs 16 ans, les adolescents doivent choisir leur faction. Pour les aider dans ce choix, ils passent un test qui les "classe" dans l’une ou l’autre des factions – ils peuvent alors choisir de rester dans leur faction ou être transférés dans une autre faction qui leur correspondrait mieux. Les résultats de Tris sont rares et peu concluants – le test la classe dans trois factions à la fois. Tris choisit d’être transférée de la faction Abnegation dont fait partie sa famille à la faction Dauntless ; le premier tome est celui de son initiation dans cette faction (et c’est pas de la tarte). Les tomes suivants racontent l’évolution de la société en question – y compris, dans le troisième tome, le pourquoi du comment de la société en question. Une trilogie plutôt sympa, j’irai peut-être voir les films au cinéma quand ils sortiront.

S’il ne fallait en lire qu’un… ou trois… Mistborn: The Final Empire, The Well of Ascension et The Wise Man’s Fear.

Algorithmes aléatoires et conflits sur l’échiquier

J’avais dit que je ferais un billet sur les algorithmes aléatoires, et je ne l’ai toujours pas fait. Une petite part de flemme, et une grosse part d’infusion – mais je viens enfin de trouver l’exemple raisonnablement rigolo et abordable que je cherchais depuis longtemps…

Le principe de l’algorithme aléatoire, c’est essentiellement « boah, on va faire n’importe quoi, et puis si on fait n’importe quoi suffisamment de fois, on finira bien par tomber sur une solution qui marche ». Le « n’importe quoi » consiste à faire un choix au hasard quand on ne sait pas quoi faire, et le « suffisamment de fois » dépend du « n’importe quoi ». L’idée, c’est que quand on fait les choses au hasard, on a normalement au moins une chance, même infime, de tomber sur une solution. Mais si j’ai, par exemple, une chance sur 1000 de tomber sur la solution à mon problème, si j’exécute la même procédure aléatoire indépendamment 1000 fois, j’ai de bonnes chance de tomber sur ce que je veux. Je ne peux pas garantir à 100% que je vais trouver la solution, mais… Tiens, d’ailleurs, quelle est la probabilité que ça marche en faisant 1000 essais ? C’est un petit exercice assez facile, peut-être qu’un petit rappel de probabilités peut être utile (voir la partie 1 et la partie 2)… Je vais tout de même donner la solution. La probabilité que l’algorithme retourne le bon résultat est 0.001. La probabilité qu’après 1000 fois ça ait réussi au moins une fois, c’est 1 – la probabilité que ça ait échoué toutes les fois. La probabilité que ça échoue, c’est 0.999. Comme mes exécutions sont indépendantes, je peux multiplier les probabilités de tous ces essais entre elles : ça fait 0.999^1000, c’est à dire environ 0.368. Donc, la probabilité que ça ait réussi après 1000 essais est de 0.623. Ce qui peut paraître assez faible, ça fait moins de trois chances sur quatre. Mais si je répète, non pas 1000 fois, mais 3000 fois, j’obtiens une probabilité de succès de 1 – 0.999^3000, soit environ 0.95… Et on peut continuer à répéter pour avoir la probabilité de succès que l’on souhaite obtenir, même avec des probabilités de succès initiales très faibles. Si l’algorithme lui-même n’est pas trop violent en terme de calculs, n’importe quel ordinateur est tout à fait capable d’exécuter ça en un temps correct. Et les algorithmes aléatoires peuvent souvent se permettre d’être très simples – plutôt que de calculer un machin compliqué à calculer, pouf, on met une valeur au hasard et on espère que ça marche.

Ça peut paraître un peu fou comme approche, mais comme j’ai essayé de l’expliquer dans le paragraphe qui précède, on peut en fait faire des choses tout à fait rigoureuses dans le domaine. On prend un algorithme, on calcule la probabilité qu’il renvoie une réponse correcte, de là on déduit combien de fois il faudra le répéter pour avoir une probabilité de succès qui convient, et on est content. Et de là, il y a deux grosses difficultés. La première, c’est d’arriver à un algorithme qui ne soit pas complètement débile. Si l’espace de solutions est immense et qu’on se contente de prendre un élément de l’espace de solutions au pif, ça va rarement donner des choses intéressantes. Par contre, si on arrive à avoir une approche semi-intelligente, ça permet souvent d’avoir des algorithmes qui ont une espérance de temps d’exécution meilleure que les algorithmes déterministes pour un problème donné. La deuxième grosse difficulté, c’est parfois de calculer/prouver la probabilité de succès d’un algorithme (ce qui permet d’avoir une idée du nombre de répétitions à prévoir et donc du temps d’exécution). Il y a une troisième difficulté, qui n’est pas vraiment liée directement à l’algorithme aléatoire lui-même. On ne sait pas, à l’heure qu’il est, si l’ajout d’une composante aléatoire permet toujours d’avoir des algorithmes plus performants. Il existe des gens (j’en fais partie en ce moment) qui s’intéressent à la question de savoir si un algorithme aléatoire donné peut être transformé de façon magique en un algorithme déterministe (sans hasard, donc) en gardant des performances équivalentes. Il y a aussi des gens qui s’intéressent à la question générale de savoir si l’aléatoire peut apporter quelque chose, ou si la classe des problèmes qui se résolvent « facilement » avec des éléments aléatoires est la même que celle des problèmes qui se résolvent « facilement » de façon déterministe – pour une certaine définition de facilement. (Notons d’ailleurs que les deux questions n’ont pas le même sens, en dehors de la distinction « un algorithme donné / une classe de problèmes » – dans le premier cas on cherche à avoir les mêmes performances, dans le second cas, on est plus souples et on pourrait par exemple se contenter d’un « si je peux résoudre un problème en temps t avec de l’aléatoire, je peux le résoudre en temps t³ sans aléatoire »).

Après ces longs paragraphes introductifs et vaguement philosophiques, je vais donner un exemple à partir d’un problème connu, celui des 8 reines. Ça rappellera sans doute des choses à ceux qui ont joué à The 7th Guest il y a 20 ans. On suppose qu’on dispose d’un échiquier – donc une grille 8×8 – et de 8 pions qui peuvent se déplacer comme une reine aux échecs, c’est-à-dire en ligne horizontale ou verticale, et en diagonale, d’un nombre arbitraire de cases. On dit que deux reines sont en conflit lorsqu’elles peuvent s’attaquer - c’est-à-dire qu’elles sont sur la même ligne horizontale, verticale ou diagonale. On veut placer huit reines sur l’échiquier de façon à ce qu’aucune d’elles ne soit en conflit avec aucune autre. C’est pas complètement trivial comme problème, comme on peut s’en rendre compte en essayant de le résoudre à la main (ça se fait, mais c’est pas immédiat). Là, le problème reste relativement simple, au sens où la grille reste assez petite. Faire le même genre de choses avec 50 reines sur un échiquier 50×50, il y a de bonnes chances de ne pas s’en sortir à la main. Et puis construire un algorithme déterministe pour ce machin, c’est pénible, ça backtracke dans tous les sens, et moi le backtracking ça me fout mal au crâne (c’est pas complètement vrai, il y a un algorithme récursif qui existe aussi, mais bon). Donc, voyons ce qu’on peut faire de manière aléatoire. Je vais me limiter dans certains cas aux 8 reines, parce que ça fait des nombres « gérables ». Et je vais tricher un peu, je vais dégainer la Wikipedia sur le sujet Problème des huit dames, et je vais affirmer qu’il existe 92 solutions au problème – ça me sera utile pour donner certains nombres.

On peut prendre une approche vraiment bourrine – on numérote les cases de l’échiquier de 1 à 64, on tire huit numéros de 1 à 64, et on place une reine sur chaque case. Si ça marche, ben on a fini ; si ça marche pas, on reprend les reines de l’échiquier et on recommence. La probabilité de succès de cet algorithme, elle est pas bien élevée – il y a 4 426 165 368 manières de choisir 8 chiffres parmi 64, ce qui nous donne une probabilité de succès d’environ 2.07 × 10^-8. C’est peu.

Donc, on regarde d’un peu plus près le problème, et on fait une observation facile : si je veux avoir la moindre chance qu’une solution marche, une chose est sûre, c’est que je n’aurai qu’une seule reine par colonne de mon échiquier. Donc, plutôt que de prendre huit numéros de 1 à 64, je prends, pour chaque reine, un nombre au hasard de 1 à 8, et je place la reine numéro k sur la colonne k et sur la ligne correspondant au nombre qu’on a pris au hasard. C’est sensiblement meilleur – ça correspond à 8^8 = 16 777 216 possibilités, soit une probabilité de succès qui tourne autour de 5.48 × 10^-6. C’est mieux, mais c’est toujours pas top.

On fait alors l’observation facile suivante : je n’aurai aussi qu’une seule reine par ligne de mon échiquier. Bon, d’accord, j’aurais probablement pu faire l’observation en même temps que la précédente, mais faut pas me brusquer, on est dimanche matin et j’ai mangé de la raclette hier soir. Donc, plutôt que de prendre un nombre au hasard de 1 à 8 pour chaque reine, je prends une permutation au hasard (c’est à dire que je prends un nombre de huit chiffres dans lequel tous les chiffres de 1 à 8 apparaissent), et je pose mes reines en fonction de cette permutation (la première reine sur la ligne du premier chiffre, la deuxième sur la ligne du deuxième, et ainsi de suite). Ça améliore encore un peu les choses – il y a 8! = 40 320 permutations possibles, soit une probabilité de succès de 2.28×10^-3, soit 0.02%. Ça commence à rentrer dans la catégorie des machins « faisables »… mais uniquement pour des petites valeurs de la taille de l’échiquier. Si on monte, mettons, ne serait-ce qu’à 16 reines sur un échiquier de 16×16 cases, la séquence OEIS kivabien nous permet d’évaluer la probabilité de succès à 14 772 512/16!, soit environ 7.06×10^-7. Le problème, c’est que la factorielle, là, ben elle est quand même encore très moche.

On peut encore améliorer les choses. Il y a trois sources de conflits pour les reines sur l’échiquier : les lignes horizontales, les lignes verticales, et les diagonales. L’approche par permutations permet de gérer les deux premières, mais y ajouter la gestion des diagonales commence à filer VRAIMENT mal au crâne (on se retrouve à faire des machins du genre « si j’ai deux chiffres qui sont dans des positions qui diffèrent de k, ils ne peuvent pas différer eux-mêmes de k », et c’est imbitable). Par contre, ce qu’on peut faire assez facilement, c’est générer la permutation petit à petit. L’idée, c’est qu’on place les reines une par une au hasard dans une colonne, en supprimant toutes les lignes qui sont en conflit avec une reine placée précédemment.  Donc, on place la première reine au hasard sur la première colonne, la deuxième reine au hasard, mais de façon à ce qu’elle ne soit pas sur la ligne de la première ni sur ses diagonales, et ainsi de suite. Et si on ne peut pas trouver une position sans conflit dans la colonne, c’est que la solution courante ne marche pas – on vire tout et on recommence du début. Je n’ai pas trouvé d’analyse rigoureuse de ce machin, et j’ai la flemme de la tenter moi-même (je soupçonne accessoirement ne pas être capable de m’en sortir, du moins pas dans un temps qui me permette de publier ce billet rapidement), mais il y a au moins une implémentation qui a été testée sur 1000 reines avec des temps d’exécution raisonnables (variant apparemment de 39 secondes à 25 minutes). L’idée, cela dit, c’est qu’on élimine beaucoup de permutations de l’espace de recherche : par exemple, on supprime toutes celles qui commencent par « 12 » – ce qui correspond, pour un problème de 8 reines, à 720 permutations, ce qui n’est pas énorme, mais si on multiplie ça par 14 (parce qu’on supprime aussi celles qui commencent par « 23 », « 34 »,…, « 78 », « 21 », « 32 »,…,« 87 »), à 10 080 permutations, soit déjà un quart de l’espace de recherche ! Plus l’échiquier est grand, moins ces deux premières étapes seront significatives (et plus le « un quart » va tendre vers 0, si vous me passez l’expression), mais l’idée reste la même : on réduit l’espace de recherche, et la probabilité de succès augmente.

Toutes ces approches ont la même base : on recherche une combinaison qui fonctionne dans tout l’ensemble des combinaisons, en essayant de supprimer les combinaisons qui ne marchent pas le plus tôt possible. Il existe un autre type d’approche, qui est celle de la « réparation ». L’idée, c’est que pour une permutation donnée, on n’est peut-être pas loin d’une solution qui marche. Donc, plutôt que d’explorer l’espace de combinaisons entier, on peut peut-être explorer autour d’une permutation en essayant de se rapprocher d’une solution. Une solution, par définition, c’est une combinaison qui a zéro conflit. Donc, on peut supposer qu’on se « rapproche » d’une solution quand on diminue le nombre de conflits. C’est l’idée du dernier algorithme que je vais présenter dans ce billet. On commence par prendre une permutation aléatoire qui « a une bonne tête » en utilisant l’algorithme précédent et, au lieu de s’arrêter lorsqu’on rencontre un conflit, en plaçant une reine au hasard sur l’une des cases présentant le nombre minimum de conflits de la colonne. Si elle marche, tant mieux, on a fini. Sinon, on choisit une colonne au hasard, et on compte, pour chaque case, le nombre de conflits auquel elle correspond, en ne comptant qu’un seul conflit si plusieurs reines génèrent ce conflit (parce de toute façon elles sont alors en conflit entre elles, et il faudra gérer ça). S’il existe une case pour laquelle la reine de la colonne courante aurait moins de conflits, on la déplace (en choisissant au hasard la case si plusieurs d’entre elles ont le même nombre de conflits). Et on recommence. Il n’y a en revanche pas de garantie que cet algorithme va toujours renvoyer une solution : si on n’a pas de chance, on peut se retrouver dans un minimum local, ne pouvoir améliorer le nombre de conflits sur aucune colonne, et boucler infiniment. Il faut prendre ce genre de cas en compte, et arrêter/recommencer l’algorithme si le nombre d’étapes commence à exploser vraiment trop violemment. Là, vraiment, je sais que l’analyse de cet algorithme va au-delà de ce que je veux présenter sur ce blog (j’avoue ne pas l’avoir lue, surtout qu’il manque des figures sur le papier). Le papier qui présente la méthode indique que le nombre de conflit réparés reste à peu près constant quel que soit la taille de la grille, et qu’ils arrivent à résoudre le problème sur un échiquier d’un million de cases de côté en 4 minutes. Sur une SPARCstation 1, en 1991.

Bref, les algorithmes aléatoires, c’est rigolo et utile. Je pense qu’un prochain billet discutera des algorithmes aléatoires pour SAT, parce que c’est quand même ce sur quoi je passe beaucoup de temps en ce moment. J’ai quand même passé un truc assez fondamental sous le tapis, c’est que générer des nombres aléatoires, c’est hautement non-trivial. En pratique, ce que j’ai présenté ici fonctionne aussi avec des nombres « à peu près aléatoires » tels qu’un ordinateur est capable de les générer. Mais ceci est une autre histoire, que nous vous raconterons une prochaine fois… ou pas, parce que là, j’ai pas le niveau :P

#balisebooks – Décembre 2013

Le début de l’année étant aussi un début de mois, j’ai deux choses à faire : souhaiter à mes lecteurs une bonne année, et écrire un #balisebooks. Donc, bonne année, et voici le #balisebooks de décembre.

Home for the Holidays, de Jeaniene Frost (pas encore traduit en français), est « l’épisode de Noël » de la série Night Huntress dont j’ai… *gasp* pas encore parlé. Donc, les Night Huntress, c’est Natacha qui m’en a parlé, et qui en parle d’ailleurs longuement (et mieux que moi) dans ses billets de critique de Halfway to the Grave, de One Foot in the Grave, et de At Grave’s End. La recette de la série est classique mais marche diaboliquement bien – dans un univers qui ressemble vachement au nôtre à ceci près qu’il contient des créatures surnaturelles genre des vampires et des fantômes, nos héros Cat and Bones, plutôt du côté « vampire et assimilables », font face aux « emmerdes du tome ». Les personnages sont chouettes, et en particulier les personnages secondaires récurrents sont de ceux qu’on apprécie de revoir surgir ici ou là. L’univers me parle moins que celui des Chicagoland (dont j’ai parlé en août), mais c’est sans doute une question de goût. Dans l’épisode de Noël sus-cité, le frère de Bones (qui était inconnu au bataillon jusqu’alors) déboule, et tout le monde commence à se comporter de façon bizarre. Je soupçonne qu’il y aurait limite eu matière à faire un tome complet et pas un « demi-tome », mais on va pas bouder son plaisir.

Digital Fortress, de Dan Brown (Forteresse Digitale en français), m’a fait hurler plus d’une fois. Dan, mon petit, la crypto, ça marche pas comme ça. Vraiment pas. Et ça m’agace profondément, parce que j’ai quand même voulu savoir ce qui se passait dans ton bouquin, parce que visiblement, mener un suspense, tu sais faire, mais rontudju, il aurait probablement pas fallu grand chose pour que ton bouquin soit raisonnablement lisible par des gens qui ont des notions de base (vraiment, de base) en crypto. Très agaçant. Et tout ça pour hurler la réponse à l’énigme finale quinze pages avant que des mecs qui sont censés être des dieux vivants ou presque finissent par la trouver. Le bouquin part du postulat que la NSA sait déchiffrer tout ce qui lui passe par les mains, sauf qu’un petit malin arrive et prétend qu’il a un algorithme incassable. Bon, après, le problème, c’est que comme dit plus haut, les éléments techniques sont tellement mal foutus que ça part complètement en sucette à partir de là, et que le reste du scénario ne tient plus. Un gros gâchis, parce que sinon ça serait probablement un chouette thriller. Scrogneugneu.

Shadow Kiss, de Richelle Mead (Baiser de l’ombre en français), est le troisième tome de la série Vampire Academy que j’ai commencée le mois dernier. On y retrouve Rose, salement traumatisée par les événements de la fin du tome 2, et qui en particulier voit des fantômes, ce qui est plutôt mauvais signe pour sa santé mentale. C’est aussi l’époque du « stage de fin d’études » pour les gardiens de la promo de Rose – chaque gardien est assigné à un étudiant Moroi, qu’il doit protéger « comme en vrai » face aux attaques planifiées mais néanmoins réelles des instructeurs de l’Académie. Une ambiance « Buffy rencontre Harry Potter » pour ce tome, j’ai bien aimé.

REAMDE, de Neal Stephenson (apparemment pas encore traduit en français), était ma tentative de me rattraper de l’énervement de Digital Fortress. C’est raté : j’ai abandonné au milieu, j’en avais marre. Ça partait pourtant plutôt pas mal. On fait la connaissance de Richard Forthrast, créateur du jeu vidéo T’Rain, un meuporgue qui a pour particularité d’avoir été conçu avec les « farmers » d’or en tête et d’y avoir adapté son monde. Richard a une nièce, Zula, qui à la suite d’un concours de circonstances malheureux, se retrouve enlevée par la mafia russe, trimbalée en Chine, et j’ai fini par abandonner quand les terroristes et le MI6 ont commencé à faire leur apparition aussi. Malgré ce casting qui prend des proportions, c’est _lent_ et verbeux. J’ai la vague impression qu’avec les 1000 pages+ de ce bouquin, il y aurait moyen de faire deux bouquins de 300 pages, et que j’en apprécierais un mais pas l’autre. Bref, exactement le défaut inverse de Digital Fortress. La construction du monde et les aspects techniques sont impeccables et très bien foutus (j’ai envie de jouer à T’Rain, rontudju), mais le développement de l’histoire me va pas. Je commence à me dire que je devrais écrire mes propres techno-thriller-trucs si je veux en trouver un qui m’aille. Je pense cela dit que REAMDE est pas mal, objectivement, mais c’est pas ma came.

Astérix chez les Pictes, de Jean-Yves Ferri et Didier Conrad… ben c’est le dernier Astérix. Beaucoup de calembours affreux (c’est un compliment) au service d’un scénario un peu faiblard.

The Call of Cthulhu, d’H.P. Lovecraft (L’Appel de Cthulhu, en français), fait partie des trucs qu’il fallait que je lise à l’occasion, et voilà, c’est fait. J’ai pas mal joué à des jeux sur le thème (Elder Sign, Arkham Horror et Mansions of Madness), et le moins qu’on puisse dire c’est que c’est pas dépaysant, pour le coup. Call of Cthulhu est l’histoire de la mise en relation d’événements a priori indépendants – des cauchemars, un culte à la Nouvelle Orleans, un naufrage dans le pacifique. La construction, par petites touches, de la révélation de l’existence de Cthulhu et de son réveil… À lire, ne serait-ce que d’un point de vue culturel.

The Name of the Wind, de Patrick Rothfuss (Le Nom du vent, en français), est le premier tome de la trilogie Kingkiller Chronicle. J’ai « fait la connaissance » de Patrick Rothfuss par le même biais que celle de Jacqueline Carey – c’est lui qui animait la série Story Board sur YouTube, et il est aussi passé dans l’épisode Lords of Waterdeep de Tabletop. Il a aussi monté un truc très rigolo au moment où il est arrivé sur Twitter. Bref, j’avais une bonne opinion de l’auteur a priori, et j’ai fini par ouvrir un de ses bouquins, en l’occurrence The Name of the Wind. C’est l’histoire de Kvothe qui, à ce qui nous est présenté comme la fin de sa vie, raconte ladite vie à un public assez limité. La narration durera trois jours ; le premier tome correspond au premier jour (fou). Kvothe commence donc par raconter son enfance et le début de sa formation d’arcaniste à l’université. Le personnage principal est parfois un peu agaçant, parce qu’il est présenté comme un demi-dieu dans à peu près tout ce qu’il entreprend ; dans le contexte où c’est Kvothe lui-même qui raconte, ma foi, ça passe. Et j’ai eu beaucoup, beaucoup de mal à lâcher le bouquin - il m’a même emmenée à des heures pas catholiques quand je l’ai terminé. Le concept du « je suis pas bien réveillée parce que j’ai fini un bouquin à 2h du mat hier », c’est pas une bonne idée, mais ça donne une certaine idée de la qualité du bouquin susnommé (enfin je trouve :) ).

Serenity: The Shepherd’s Tale, de Zack Whedon, est un comic book dans l’univers de Firefly, qui raconte le passé du Shepherd Book. J’ai peu lu de comics de manière générale, et c’est un truc avec lequel j’ai du mal - la forme graphique me donne parfois l’impression de ne pas savoir lire et de déchiffrer. Les comics Firefly me sont plutôt plus motivants (parce que je veux savoir ce qu’il y a d’autre dans l’histoire – idem pour les Buffy), mais je crois qu’il faut que je persévère un peu, et que je relise celui-ci (parce que j’ai pas tout pigé, probablement parce que j’ai lu trop vite.) Mais sinon c’était bien :P

Blood Promise, de Richelle Mead (Promesse de sang, en français), est le quatrième tome de Vampire Academy. Rose s’en va toute seule en mission en Russie pour aller tatanner du Strogoi, et ça se passe plus ou moins bien. Divertissant, avec des passages plus dérangeants que ce à quoi je me serais attendue dans cette série.

Quiet, de Susan Cain (La force des discrets, en français), faisait les têtes de gondoles de toutes les librairies la dernière fois que je suis allée aux US. C’est un bouquin qui tente de convaincre que « dans un monde d’extrovertis, les introvertis ont aussi leur place et voici pourquoi/comment ». En pratique, beaucoup de « brossage dans le sens du poil du public probablement attiré par ce bouquin », peu de science, pas mal de raccourcis (en général associés à du « non mais bon c’est évidemment plus compliqué que ça, mais quand même »). J’aurais pu m’en passer.

S’il n’y en avait qu’un à lire… The Name of the Wind.