TPA : Théorème de Ramsey

Je viens de me rendre compte que j’avais pas encore parlé de théorie de Ramsey dans ce blog, ce qui est profondément scandaleux, parce que c’est un sujet très rigolo. Donc, commençons – aujourd’hui, c’est TPA.

Supposons que nous ayons un graphe dit « complet », c’est-à-dire qu’on se donne un ensemble de sommets, et qu’on trace tous les arcs possibles entre tous les sommets. On dénote par K_n le graphe complet sur n sommets - par exemple, je vous présente K_5 :

 

k5-mono

Maintenant, on va colorier les arcs du graphe en rouge et en bleu, de façon arbitraire. On peut par exemple colorier tous les arcs en bleus, tous les arcs en rouge, ou choisir d’autres coloriages :

Et avec ce coloriage, on se pose une première question : est-ce qu’il est possible d’avoir un coloriage tel qu’on ne puisse pas trouver dans la figure un triangle bleu ou un triangle rouge, c’est-à-dire trois sommets reliés uniquement par des arcs bleus ou rouges ? Les deux du haut ne fonctionnent clairement pas (puisque tous les sommets sont reliés par des arcs bleus et rouges respectivement). Le coloriage en bas à gauche ne fonctionne pas non plus : il a un triangle bleu et un triangle rouge (vous les voyez ?). Le coloriage en bas à droite n’a pas de triangle rouge, mais il a un triangle bleu.

Pour 5 points, ce n’est pas très difficile de finir par trouver un coloriage qui ne contient ni triangle bleu ni triangle rouge, et c’est celui-ci :

k5-notriangle

L’étape suivante est de se poser la même question non pas avec un graphe complet sur 5 sommets (K_5) mais avec un graphe complet sur 6 sommets (K_6), comme celui-ci :

k6

Et la réponse est non, ce n’est pas possible : on ne peut pas colorier une K_6 avec deux couleurs en évitant d’avoir un triangle monochromatique (tout bleu ou tout rouge, donc). La première remarque qu’on peut faire, c’est que pour vérifier par force brute que c’est effectivement le cas, ça va prendre un petit peu de temps. Le graphe ci-dessus a 15 arcs, ce qui correspond à 2^{15} coloriages différents. Pour voir ça, on peut choisir un ordre pour les arcs (n’importe quel ordre) et commencer à colorier. Pour le premier arc, on peut choisir rouge ou bleu, ça fait deux choix. Pour le deuxième arc, idem – et on a déjà quatre choix avec deux arcs, puisqu’ils peuvent être tous les deux rouges, tous les deux bleus, rouge-bleu ou bleu-rouge. Le troisième choix multiplie encore ces choix par deux (puisque chaque choix peut correspondre à un troisième arc rouge ou bleu), et ainsi de suite pour les 15 arcs, soit 2×2×2×…×2 = 2^{15}. 2^{15}, ça fait 32768. À la main, ça va faire beaucoup de coloriages à vérifier, mais sur un ordinateur, ça reste encore nettement dans le domaine du faisable.

Avant de programmer le coloriage et de vérifier, on peut se demander s’il y aurait moyen de prouver qu’il y a toujours un triangle monochromatique dans une K_6 coloriée avec 2 couleurs. Donc, on prend un coloriage, n’importe lequel. On prend un sommet, n’importe lequel aussi. Ce sommet, il a 5 arcs qui y sont connectés, et parmi ces cinq arcs, il y en a au moins trois qui sont de la même couleur (parce que si j’ai au plus deux arcs bleus ET au plus deux arcs rouges, ben j’ai au plus 4 arcs). Pour faire simple, je vais supposer que les trois arcs qui sont de la même couleur sont bleus (je peux toujours faire ça, si ce n’est pas le cas il suffit de remplacer rouge par bleu et bleu par rouge dans ce qui suit). Maintenant on fait une petite figure avec des notations.

k6-firstcolors

J’ai au moins trois arcs bleus qui partent de mon sommet initial, j’en choisis exactement trois (les deux autres peuvent être rouges ou bleus). Ces arcs définissent trois points sur le graphe, qui sont les autres extrémités des trois arcs ; je nomme ces points u, v et w. Et là, il peut se passer plusieurs choses. Si l’arc entre u et v est bleu, alors j’ai un triangle bleu. Si l’arc entre v et w est bleu, alors j’ai un triangle bleu. Si l’arc entre u et w est bleu, alors j’ai un triangle bleu. Et si rien de tout ça ne se passe…

k6-plusred

ben l’arc entre u et v est rouge, l’arc entre v et w est rouge, et l’arc entre w et u est rouge aussi, donc le triangle défini par u, v, w est tout rouge. Tout ce que j’ai raconté là s’applique à n’importe quel coloriage (même s’il faut éventuellement changer rouge en bleu et bleu en rouge), et donc on ne peut pas trouver de coloriage qui n’ait ni triangle bleu, ni triangle rouge.

La remarque suivante, c’est que n’importe quelle K_n (c’est-à-dire un graphe complet sur n sommets), pour n \geq 6, contient une K_6. Donc si on ne peut pas colorier une K_6 sans avoir de triangle monochromatique, on ne peut pas non plus colorier une K_n, n\geq 6 sans triangle monochromatique.

Donc, pour les triangles, on sait ce qu’il se passe : pour n\leq 5, on peut trouver un coloriage tel qu’on ne trouve pas de triangle monochromatique, et pour n \geq 6, on a prouvé qu’il n’existait pas.

La question suivante est : maintenant qu’on a des choses pour les triangles, est-ce qu’on peut avoir le même genre de résultat pour plus de points ? Plus spécifiquement, si je considère une K_n, est-ce que je peux la colorier avec deux couleurs de manière à éviter d’y trouver une K_4, K_5, K_6, K_{42} de la même couleur (remarquons qu’un triangle est une K_3 ;) )? Et ben, c’est une question compliquée. Pour être sûr de trouver une K_4, il a été prouvé qu’on a besoin de 18 points. Ce qui veut dire qu’on peut colorier ce bidule-là avec 2 couleurs et ne pas y trouver de K_4 monochromatique:

K17

Si on rajoute un sommet et qu’on le connecte à tous les autres, par contre, on est sûr de trouver une K_4 monochromatique si on colorie avec deux couleurs. Là, pour le coup, si on veut réellement vérifier tous les coloriages possibles, il va vraiment falloir faire des progrès sur la puissance informatique. Une K_{18} (un graphe complet sur 18 sommets, donc) a 153 arcs, donc si on se mettait en tête de vérifier tous les coloriages, il faudrait en vérifier 2^{153}. Si on est capable de vérifier un coloriage par nanoseconde (ce qui n’est pas franchement réaliste), il faudrait plus de 3 000 000 000 000 000 000 000 000 000 (3 suivi de 27 zéros) SIÈCLES pour tout vérifier… on est pas rendu :)

Là où ça devient VRAIMENT amusant, c’est quand on se pose la question de trouver des K_5 et supérieur (qui soient monochromatiques, donc). Pour la K_5, on sait que pour plus de 49 sommets, on la trouvera nécessairement. On sait aussi qu’on peut construire un coloriage sur 42 sommets sans K_5 monochromatique. Le lecteur attentif aura remarqué qu’on ne sait pas ce qu’il se passe entre 43 et 49 sommets… La situation est de moins en moins claire au fur et à mesure : pour la K_{10} monochromatique, on sait que le seuil se situe quelque part entre 798 (pour 797 sommets on sait qu’on peut colorier sans avoir de K_{10} monochromatique) et… 23556 (pour un graphe complet sur 23556 sommets colorié avec deux couleurs, on sait qu’on aura toujours une K_{10} monochromatique).

Le théorème de Ramsey qui donne son nom à ce billet de blog dit que quelque soit r, on peut trouver un n tel que tout coloriage avec deux couleurs d’une K_n contienne nécessairement une K_r monochromatique. Ledit théorème est plus général que ça : il dit que pour tout r_1, r_2, r_3... r_\ell on peut trouver un n tel que tout coloriage de K_n avec \ell couleurs c_1, c_2,..., c_\ell contient ou bien une K_{r_1} de couleur c_1, ou bien une K_{r_2} de couleur c_2, …, ou bien une K_{r_\ell} de couleur c_\ell. Et on dénote n par R(r_1, r_2,..., r_\ell). (Pour rattacher aux trucs précédents, j’ai démontré que R(3,3) = 6, et j’ai indiqué que R(4,4) = 18, 43 \leq R(5,5) \leq 49 et que 798 \leq R(10,10) \leq 23556.

On peut exprimer ça de façon plus « philosophique » en disant qu’une structure suffisamment grande aura toujours un peu d’ordre local quelque part. Ce que je trouve personnellement assez fascinant.

Le mot de la fin revient à Joel Spencer: « Erdős nous a demandé d’imaginer une force d’extraterrestres, beaucoup plus puissante que nous, qui atterrit sur Terre et nous demande la valeur de R(5,5), ou bien ils détruisent la planète. Dans ce cas, dit-il, nous devrions combiner la puissance de tous nos ordinateurs et de tous nos mathématiciens pour tenter de trouver la valeur. Mais supposons qu’ils demandent R(6,6). Dans ce cas, il pense qu’il faudrait détruire les extraterrestres. » (traduction personnelle).

#balisebooks – Août 2014

On aurait pu penser qu’un mois où j’ai 12h d’avion aurait été un mois faste pour le #balisebooks, mais on aurait visiblement eu tort. Et en plus c’était un mois assez peu enthousiasmant sur les bouquins que j’ai lus (après, si c’est un problème d’humeur générale ou la faute à pas de chance… allez savoir.)

Bone Crossed, de Patricia Briggs (en français ), est le 4e tome des Mercy Thompson,  qui s’en va chasser des fantômes à Spokane. Toujours dans la lignée.

Spring MVC: Beginner’s Guide, d’Amuthan G (pas de traduction française) est un gros tutoriel sur le framework Java Spring MVC. Plutôt bien fichu, j’ai appris beaucoup de choses (et je suis capable de les appliquer à mes bidules courants), quelques problèmes de cohérence ici et là mais rien d’insurmontable. Un peu plus de profondeur aurait été appréciée par moments (sur les mécanismes d’injection par exemple).

Fall of Giants, de Ken Follett (La Chute des géants, en français) est le premier tome de la Century Trilogy. On y suit l’histoire de plusieurs personnages au début du XXe siècle jusqu’à quelques années après la fin de la première guerre mondiale – au Royaume-Uni, en Allemagne, aux États-Unis et en Russie. Je l’ai trouvé long – il m’a fallu trois semaines pour le finir (en ne lisant que ça), ce qui est rare, mais plutôt chouette. Et comme je suis nulle en histoire, j’y ai même appris des choses (genre, par exemple, l’histoire des taxis de la Marne).

Vivien’s Heavenly Ice Cream Shop, d’Abby Clements (La Merveilleuse boutique de crèmes glacées de Viviane, en français) est l’histoire de deux sœurs qui héritent de la boutique de glaces de leur grand-mère. C’est meugnon, c’est plein de bons sentiments et de décisions stupides, vite lu, vite oublié. Mais je mangerais bien de la glace.

Lock In, de John Scalzi (pas encore de traduction en français) est à la fois un bon bouquin et la déception de ce mois-ci. J’avais lu Unlocked, la grosse nouvelle d’intro, en juin, et j’avais été très enthousiaste ; Lock In m’a moins enthousiasmée. Dans le monde décrit dans Unlocked, Chris est un des patients Haden – il est paralysé dans son lit, mais il peut se balader librement grâce à un « threep » – un genre de robot contrôlé par la pensée, en gros. C’est son premier jour au FBI – et le voilà à enquêter sur la mort violente de quelqu’un, mort pour laquelle le seul témoin et suspect est un Intégrateur (une personne qui peut mettre à disposition son corps pour les Haden), ce qui pose évidemment quelques problèmes sur l’identité « réelle » du coupable. J’ai l’impression que Lock In aurait gagné à être un peu plus long. Ça reste très sympa : le feeling est un peu celui des Cavernes d’Acier d’Asimov ; mais j’attendais exceptionnel.

S’il ne fallait en lire qu’un… Fall of Giants.

#balisebooks – Juillet 2014

Hop, on arrive à la fin du mois de juillet, il est donc temps d’attaquer la rédaction du #balisebooks si je veux avoir une chance de le publier début août :) (EDIT : bon, on est le 4 août, ça va encore…) J’ai aussi décidé que j’allais arrêter d’essayer de donner beaucoup de détails sur les bouquins de séries (à part le premier de la série), parce que c’est inconfortable et que ça n’apporte probablement pas grand chose (et qu’en pratique c’est déjà probablement le cas, en fait).

Blackout/All Clear de Connie Willis (en français Black-out / All Clear), en deux tomes, part sur la même base qu’un de mes livres préférés par le même auteur, Doomsday Book (Le Grand livre) : le voyage dans le temps existe, et il est principalement utilisé par les historiens pour aller observer l’Histoire par eux-mêmes. On suit dans Blackout / All Clear trois historiens envoyés pendant la seconde guerre mondiale : Polly, qui s’en va voir le Blitz, Eileen, qui s’en va voir l’évacuation des enfants dans le nord de l’Angleterre, et Mike, qui s’en va voir l’évacuation de Dunkerque. Leurs trois histoires sont initialement disjointes, mais il ne me semble pas que ce soit un gros indice de dire qu’elles finissent par se rejoindre. Le voyage dans le temps tel qu’utilisé par Connie Willis a a priori beaucoup de « règles » : le continuum est solide, il « sait » se protéger de l’interférence des historiens, et il n’est physiquement pas possible d’altérer l’histoire. Sauf que visiblement, ces règles sont peut-être beaucoup moins solides que ce que l’on pensait auparavant - et c’est ce qui est au cœur de Blackout/All Clear. Le début est très lent, les personnages principaux ne sont pas forcément très distinguables les uns des autres (les personnages secondaires ont plus de caractère – ou sont peut-être plus cliché ?). La fin du premier tome est très abrupte, et le premier tome n’est vraiment pas lisible « tout seul », il faut lire le second. Bref, globalement, un « pas mal, mais » – c’est chouette, c’est historiquement intéressant (pour une certaine définition (romancée probablement) d’historiquement), ça se lit, mais ça aurait probablement gagné à être nettement plus court.

Iron Kissed, de Patricia Briggs (Le Baiser du fer) est le troisième tome des Mercy Thompson, mécano-coyote. Dans ce tome, elle s’en va investiguer un meurtre chez les fae, meurtre dont son mentor (lui-même fae) a été accusé. Évidemment, c’est pas l’idée du siècle, d’autant plus que les fae sont très protecteurs de leur territoire et de leurs secrets, et qu’essentiellement, faut pas les faire chier. Dans la lignée des précédents.

Larkspur, de VM. Jaskiernia… est un machin bizarre, j’ai lu, j’ai rien compris, et ça m’a laissé un vague sentiment de malaise.

Little Women, de Louisa May Alcott (en français Les Quatre filles du Docteur March) est un grand classique que j’étais sûre d’avoir déjà lu. Donc oui, mais pas tout à fait. Je suis raisonnablement sûre que l’édition que j’en ai lue (et re-lue, et re-re-lue) quand j’étais gamine était une édition abrégée (parce que je me souvenais vraiment de beaucoup, beaucoup de choses, sauf de certains passages complets qui ne me rapperaient rien du tout ; d’autre part la version que j’ai lue là en version originale a visiblement été traduite en deux tomes en France (c’était à l’origine deux tomes, mais qui ont visiblement été fusionnés en un seul livre de nos jours). Bref, c’est l’histoire de la famille March, qui commence pendant la Guerre de Sécession alors que le père est au front ; on suit le quotidien des « quatre filles » depuis leurs adolescences jusqu’à leurs mariages. C’est très clairement plein de bons sentiments et parfois un peu prêchi-prêcha, mais je suis contente de l’avoir (re ?)lu, apprécié, et d’en avoir eu une suite par rapport à ce que j’avais lu il y a longtemps.

The Dirty streets of Heaven, de Tad Williams (en français Ange impur) est le premier tome de la série Bobby Dollar. Bobby est un ange et, en tant qu’ange, son boulot est de jouer les avocats du Paradis en face des avocats de l’Enfer (j’évite avec brio l’avocat du diable) pour récupérer les âmes des récents défunts. Le Paradis ressemble fortement à une bureaucratie immonde (mais où tout le monde est content alors ça va). Ça se passe dans une Californie parallèle, qui a un San Francisco mais aussi un Saint-Judas (dont Palo Alto est un district), ce qui est un peu déroutant au démarrage, et ça commence par un problème intéressant : Bobby et son alter-ego de l’enfer arrivent sur la scène d’un suicide, et là… pas d’âme (j’évite avec brio le « pas âme qui vive »). Évidemment, le problème remonte rapidement, les deux factions s’accusent l’une l’autre de piquer les âmes, ce qui ne résout pas le problème initial… L’enquête de Bobby est parsemée de personnages plus ou moins étranges et plus ou moins du « bon » côté (en ce qui concerne Bobby du moins), et l’ensemble est très dur à lâcher à des heures raisonnables pour aller dormir. Très chouette.

Broken, de David H. Burton, est un machin dont j’ai parcouru la deuxième moitié au rythme d’une page par 5 secondes pour avoir une vague idée de ce qui se passait à la fin. C’était assez nul.

Blind Faith, de Ben Elton (pas de traduction en français) se passe dans un futur dystopique pas vraiment daté. La religion globale est l’Amour, il est fortement recommandé de partager sur Internet absolument tout de sa vie (y compris les vidéos de naissance) à défaut d’être qualifié d’antisocial, voire d’hérétique, et les maladies infantiles tuent la moitié des enfants avant l’âge de 5 ans. Le protagoniste, Trafford, se rebelle vaguement, d’abord en évitant de poster la vidéo de naissance de sa fille, Caitlin HappyMeal (oui, ils ont aussi des noms rigolos), puis en envisageant de la faire *gasp* vacciner (alors que tout le monde sait que les vaccins empoisonnent les enfants). Prédictible, mais relativement amusant.

The First Fifteen Lives of Harry August, de Claire North (en français Les Quinze premières vies d’Harry August) part d’un point intéressant : il existe dans le monde des gens qui re-vivent leur vie encore et encore, avec la connaissance de leurs vies précédentes. Lorsqu’ils meurent, ils re-naissent là où et quand ils étaient nés, et ils prennent peu à peu conscience (autour de 5-6 ans) de leurs vies précédentes. Le héros, Harry August, est une de ces personnes. À la fin de sa onzième vie, une petite fille vient lui rendre visite alors qu’il va mourir, pour lui expliquer que la fin du monde est proche à moins qu’il n’y fasse quelque chose. On suit donc Harry dans ses quinze premières vies, ses histoires, et la manière dont il va essayer d’éviter la fin du monde. C’est assez bizarre comme bouquin, notamment parce qu’il y a une notion de voyage dans le temps qui est clairement pas classique, et pas vraiment expliquée ; essayer de réfléchir aux tenants et aboutissants de tout ça file mal au crâne (je sais, j’ai essayé). Mais c’est très, très bien fait et très, très chouette, j’ai vraiment beaucoup aimé. Il a été traduit en français par Armalite, qui le qualifie de « meilleur bouquin sur lequel [elle a] bossé en 20 ans de carrière » – tout un programme :)

S’il ne fallait en lire qu’un… The First Fifteen Lives of Harry August.

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 :

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