#balisebooks de printemps

Hop, un petit #balisebooks pour faire un peu de tri dans le backlog. J’ai la vague intention de tenter de bloguer un poil plus souvent que tous les trimestres, donc je vais ptêt revenir à un rythme de #balisebooks un peu plus soutenu plutôt que de faire dans le gros dump a posteriori et quand je me souviens plus de rien. À voir !

Ancillary Sword, d’Ann Leckie (pas encore de traduction en français) est la suite d’Ancillary Justice que j’avais beaucoup aimé. Ancillary Sword se déroule juste après Ancillary Justice, on y retrouve notre protagoniste-vaisseau qui a hérité de son propre vaisseau (et de l’équipage qui va avec), et qui s’en va gérer des soucis à une échelle beaucoup plus locale. Le rythme est plus lent et l’échelle moins planétaire, mais le résultat est néanmoins tout à fait lisible et appréciable. J’attends Ancillary Mercy (le troisième tome) avec impatience.

Dark Debt, de Chloe Neill (pas encore de traduction en français) est le 11e tome des Chicagoland. RÀS, le popcorn habituel.

Fair Game, de Patricia Briggs (Jeu de Piste, en français) est le 3e tome des Alpha&Omega, même remarque.

Alan Turing, the Enigma, d’Andrew Hodges (Alan Turing, en français) est une biographie d’Alan Turing (on l’aurait deviné), et c’est apparemment celle qui aurait servi de base pour le film The Imitation Game. Un livre très intéressant, qui explique énormément de choses sur la vie de Turing (normal), le contexte de l’époque, et sur le travail de Turing. J’ai un peu regretté que ce dernier aspect ne soit pas un peu plus développé – cela dit, c’est déjà une part certaine du bouquin, et il me semble que c’est plutôt bien expliqué. C’est plutôt marrant de voir « inventées » (ou découvertes ?) des choses qui paraissent aujourd’hui « aller de soi » ou presque dès qu’on a deux bases et quart en programmation. Bon, il y avait aussi quelques longueurs, mais je soupçonne que ce que je considère comme des longueurs intéressera peut-être plus un autre lecteur (et vice-versa) – ça me semble inévitable sur un pavé de cette exhaustivité.

Dune et Dune Messiah, de Frank Herbert (Dune et Le Messie de Dune, en français) est un grand classique que je n’avais pas encore lu en VO, voilà qui est corrigé. (Du moins pour les deux premiers tomes du cycle, à suivre :) ). Ça commence par l’arrivée de Paul Atréides et de sa famille sur Arrakis, planète-desert ayant le monopole de la production de l’Épice, pour en prendre le contrôle au nom de l’Empereur. Ça continue par une fresque socio-écolo-politico-religieuse d’ampleur planétaire voire plus, et c’est à lire. J’ai de moins bons souvenirs des tomes suivants, donc je réserve mon jugement pour le reste pour quand je l’aurai relu, mais le début du cycle vaut vraiment le coup. De façon amusante, j’ai lu ça au milieu de SF plus récente et j’ai été assez amusée par la quantité d’exposition et d’explications diverses – j’ai l’impression que la « mode » actuelle est plutôt de plonger le lecteur dans l’univers et qu’il se débrouille, du coup c’était presque reposant ;)

The First 20 hours: How to learn everything fast, de Josh Kaufman (pas encore de traduction en français) était un bouquin assez… motivant. Kaufman explique l’hypothèse suivante : oui, pour devenir « bon » à quoi que ce soit, il faut y passer du temps. MAIS pour y devenir « suffisamment compétent pour avoir une vague idée de ce qu’on fait et y prendre goût », vingt heures de pratique suffisent. Bon, vingt heures de pratique intelligente, ce qui réclame un investissement supplémentaire en temps pour réussir à déterminer ce que « pratique intelligente » veut dire pour l’activité en question, mais bon. L’hypothèse est intéressante, a minima. Il décline dans le reste du bouquin six exemples : le yoga, l’ukulele, la planche à voile, le go, la programmation et la dactylo. J’ai appris des choses dans des domaines dont je n’avais aucune idée, et les exemples sont sympa. Bref, ça se lit vite, j’ai appris des trucs, j’ai trouvé ça plutôt motivant en général – même si je ne me suis pas encore bougé beaucoup plus que faire une liste « où investir mes skillpoints » pour l’instant, et si l’application à d’autres domaines semble un peu intimidante à première vue.

S’il ne fallait en lire qu’un… Dune.

#balisebooks de début d’année

Vu le titre du dernier #balisebooks, je suppose que celui-ci s’impose assez…

Naamah’s Curse et Naamah’s Blessing, de Jacqueline Carey (pas encore de traduction en français), sont, respectivement, le 2e et 3e tome de la 3e trilogie de Terre d’Ange (voir le #balisebooks d’il y a un an pour le premier tome). C’est donc la suite des aventures de Moirin, qui s’en va, respectivement, en Mongolie et en Amérique du Sud à la poursuite de son destin (de façon assez littérale). C’est tout à fait lisible, mais rien à voir avec les deux premières trilogies. Le fait que les actions de Moirin sont essentiellement dictées par sa diadh-anam (l’espèce de compas mental qui lui dit quoi faire quand) est un tantinet chafouinant.

The Rosie Project et The Rosie Effect, de Graeme Simsion (Le Théorème du homard pour le premier, pas de traduction pour le deuxième tome pour l’instant) ressemble très fort à ce qu’on obtient si on colle Sheldon Cooper de Big Bang Theory comme héros principal d’une comédie romantique, et qu’on novellise le tout. Le premier est très réussi et très drôle, le deuxième m’a plus « gênée » et était nettement plus dispensable.

Ancillary Justice d’Ann Leckie (pas encore de traduction en français) raconte l’histoire de Breq, qui fut vingt ans plus tôt une partie d’un vaisseau spatial, et qui après la destruction dudit vaisseau s’en retrouve la seule « pièce » restant. Il y a en fait deux histoires – ce qu’il s’est passé vingt ans plus tôt, et ce qu’il se passe « maintenant » (et qui commence lorsque Breq sauve un de ses anciens officiers d’une mort assez certaine… officier porté disparu un bon millénaire auparavant). Ann Leckie fait également un choix intéressant pour le genre de ses personnages – qui s’avère fonctionner à mon avis extrêmement bien. (Tout le monde n’est pas de cet avis ;) ). Ancillary Justice a aussi obtenu le Hugo et le Nebula l’an dernier (et une chiée d’autres récompenses) – j’ai d’ailleurs récemment décidé qu’il fallait que je me fasse tous les Hugos, attendu que j’ai beaucoup aimé l’énorme majorité de ceux que j’ai lus sur la liste. Fin de la parenthèse.

Alpha & Omega, Cry Wolf, Hunting Ground, de Patricia Briggs (Alpha & Omega – L’origine, Le Cri du loup, Terrain de chasse en français) sont les deux tomes-et-demi qui commencent la série Alpha&Omega de Patricia Briggs. La série se passe dans le même univers que les Mercy Thompson, mais côté « deuxième fiston du Marrok », qui s’est trouvé une compagne, Anna, qui s’avère être « loup-garou omega » – hors hierarchie de la meute, et avec un pouvoir d’apaisement sur les loups. Admettons :) Le premier tome était un peu chafouinant, le deuxième est plutôt plus chouette – Anna commence à prendre un peu d’ampleur – d’un point de vue fluff, il est « justifié » que ça prenne un peu de temps, mais j’ai trouvé le mécanisme un peu facile. Tout à fait popcorn, mais on ne gâche pas son plaisir.

J’ai aussi relu avec grand plaisir Kushiel’s Chosen et Kushiel’s Avatar, de Jacqueline Carey, un an et demi après les avoir lus pour la première fois. Je reste sur mon excellente impression de cette trilogie – Phèdre est… Phèdre, Mélisande est phénoménale, et si je voulais écrire de la fanfic je l’écrirais dans cet univers-là, voilà, c’est dit (mais je crois que je vais m’épargner ça :P).

S’il n’y en avait qu’un à lire… Ancillary Justice.

#balisebooks de fin d’année

Bon, chuis complètement paumée sur mon #balisebooks, j’ai plein de retard, donc je crois que je vais abandonner l’idée de faire ça en début de chaque mois, je vais ptêt plutôt faire ça « quand j’y pense » ;) Donc, c’est parti. Évidemment, je me souviens pas de la moitié de ce que j’ai lu, ça va être long à rédiger et probablement pas très intéressant à lire tout ça… :)

The Power of Habit: Why We Do What We Do In Life and Business, de Charles Duhigg (pas de traduction française) parle de la formation des habitudes, avec pas mal d’exemples rigolos. C’était intéressant, mais assez répétitif, et ça m’a pas laissé un souvenir impérissable (voire… j’ai été étonnée de le voir dans la liste des bouquins que j’avais lus ces derniers temps !).

Wild Things et Blood Games, de Chloe Neill (pour le premier, Mords un autre jour, en français, et sans traduction française pour l’instant pour le deuxième) sont les tomes 9 et 10 de la série Chicagoland, respectivement. Le 9 était pas terrible, le 10 était mieux, ça reste lisible, mais c’est de moins en moins mémorable.

Random Acts of Senseless Violence, de Jack Womack (Journal de nuit, en français) se passe dans un New York dystopique où on lit le journal de Lola, 12 ans. Au début du livre, Lola fait plutôt partie de la frange aisée de la population ; sa famille se fait expulser de son appartement, déménage à Harlem, et tout part en sucette très très vite. Très chouette, mais assez déprimant (probablement la marque d’une bonne dystopie ? :) )

Winter of the World et Edge of Eternity de Ken Follett (L’Hiver du monde et Aux Portes de l’éternité, en français) sont les deux derniers tomes de la Century trilogy commencée avec Fall of Giants. Les deux tomes se déroulent respectivement pendant la seconde guerre mondiale et pendant la guerre froide (jusqu’à la chute du Mur, en gros), et le tout reste assez phénoménal. Les personnages de Follett côtoient des personnages « réels » (JFK et MLK font bien plus qu’une apparition…), et le tout est, sinon réaliste (je serais bien incapable de me prononcer là-dessus), du moins crédible. C’est un peu bordélique parce qu’on suit les générations suivantes des personnages du premier bouquin, et j’ai eu parfois du mal à recadrer qui était qui exactement, mais c’est un problème que j’ai souvent dans les trucs avec vraiment beaucoup de personnages. Je me demande si je commence pas à développer un goût pour la fiction historique, ce qui changerait un peu de l’urban fantasy ;)

Operating Systems: Three Easy Pieces, de Remzi H. Arpaci-Dusseau et Andrea C. Arpaci-Dusseau (pas de traduction en français), dans un tout autre style, explique de façon très claire les concepts de base d’un système d’exploitation – gestion du processeur, de la mémoire, de la concurrence, des disques. J’en savais beaucoup plus sur le sujet après l’avoir lu qu’avant (ce qui était pas bien dur, je l’avoue), et la lecture elle-même en était agréable. Bonus : il est dispo gratuitement (et légalement) sur http://pages.cs.wisc.edu/~remzi/OSTEP/.

Passage, de Connie Willis (même titre en français)… m’a beaucoup agacée. C’est l’histoire de Joanna Lander, psychologue de son état, qui cherche à comprendre ce qu’il se passe exactement quand on meurt. Richard Wright arrive dans le même hôpital, et il a trouvé un moyen de simuler des « near-death experience » (expérience de mort imminente), et voilà donc nos deux protagonistes qui se lancent dans une étude du sujet. Le thème et le traitement sont intéressants/amusants, mais SÉRIEUSEMENT ce bouquin aurait probablement dû faire la moitié de sa longueur. Joanna semble tourner en rond frénétiquement pendant au moins le tiers du bouquin, et c’est un peu usant. Quelques bonnes surprises cependant. Ah, et pour information, de nombreuses critiques dévoilent pas mal de l’intrigue du bouquin, et ça peut être à éviter si on veut se garder la surprise. Vous êtes prévenus.

River Marked et Frost Burned, de Patricia Briggs (La Marque du fleuve et La Morsure du givre, en français) sont les tomes 6 et 7 des Mercy Thompson. J’étais sceptique avant de commencer la série, j’avais tort : c’est hautement lisible. Le tome 6 était un peu bizarre, j’ai moins aimé, mais le tome 7 repart sur les chapeaux de roue. Les prochains sont sur la liste (et les autres séries de Patricia Briggs… aussi.).

The Slow Regard of Silent Things, de Patrick Rothfuss (La Musique du silence, en français) est peut-être le truc le plus bizarre que j’ai lu depuis longtemps. C’est un livre avec un personnage tout seul (Auri, dont on fait la connaissance dans les Kingkiller Chronicle) qui vit dans sa « maison », et auquel il n’arrive essentiellement rien. Dans la postface, Rothfuss décrit Slow Regard comme « une vignette de 150 pages », et c’est pas forcément une mauvaise description. C’est très… contemplatif, comme lecture, et j’ai presque envie d’appeler ça « un livre d’enfants pour adultes ». Et heu… c’est très joli, voilà. Et ça change.

Kushiel’s Dart, de Jacqueline Carey (La Marque, en français), est une relecture. J’avais beaucoup aimé à la première lecture, j’ai apprécié à nouveau à la deuxième lecture. C’est, je crois, la première fois que je relis un livre électronique – il est très clair que mes habitudes de lecture ont changé depuis que je n’ai plus besoin de « commander/acheter » des livres physiques…

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