#balisebooks – Premier trimestre 2014

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

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

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

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

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

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

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

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

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

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

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

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

Algorithmes aléatoires et conflits sur l’échiquier

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

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

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

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

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

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

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

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

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

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

#balisebooks – Décembre 2013

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

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

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

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

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

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

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

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

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

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

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

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

#balisebooks – Novembre 2013

Petit mois probablement pas très intéressant pour les #balisebooks… mon mémoire de master me prend pas mal de neurones, et du coup j’ai tendance à rester dans le « facile », les séries que je connais, et les trucs pas prise de tête. (Et, après avoir vu le résultat dudit mois, c’est effectivement très… thématique :P)

The Atrocity Archives, de Charles Stross (Le Bureau des atrocités, en français), est l’exception qui confirme la règle : c’était plutôt dans le genre prise de tête ;) C’est un machin complètement improbable, croisement de Lovecraft et de XFiles mâtiné de cybertrucs. Typiquement le genre de machins auxquels je suis, en pratique, globalement hermétique. Ce qui me désole par ailleurs, hein, mais quand ça veut pas, ça veut pas. Je pense que c’est du bon, voire du très bon, mais c’est pas ma tasse de thé.

Vampire Academy, de Richelle Mead (Vampire Academy : Sœurs de sang, en français), est le premier tome de la série éponyme. Encore de la littérature-à-vampires, cette fois avec un vague côté Gossip Girl (c’est du lourd). D’une part, les Moroi – des vampires qui, à part leur régime alimentaire particulier, sont… normaux. D’autre part, les Dhampir – mi-humains mi-vampires. Moroi et Dhampir suivent des études appropriées à St Vladimir, le lycée à vampires local ; les Moroi parce qu’il faut bien aller à l’école, les Dhampir parce que les Dhampir sont formés comme gardes du corps des Moroi, c’est comme ça (ou à peu près). Rose est Dhampir, et sa Moroi « attitrée » est Lissa ; on les récupère au moment où elles se font rattraper de deux ans de cavale et ramener au bahut manu militari. Évidemment, le danger qui les a fait fuir au départ est toujours là, d’où, problèmes. C’est pas grand, mais ça se lit.

Frostbite, de Richelle Mead (Vampire Academy : Morsure de glace, en français) est le deuxième tome, lu dans la foulée parce que bon. Il introduit les Strogoi, qui sont les vampires qui ont mal tourné, soit qu’ils aient été changés par un Strogoi, soit qu’ils soient passés volontairement du côté obscur en tuant quelqu’un. Et voilà qu’ils attaquent les familles royales Moroi, parce qu’ils peuvent, apparemment. Pendant ce temps, Rose enquête sur ce qui fait la particularité de Lissa. J’ai été un peu agacée par les indices énormes qui traînent partout à tous les sujets et au temps qu’il faut aux personnages pour faire le lien entre tous. Bref, pas trop prise de tête, ça se lit.

Succubus on Top, de Richelle Mead (Succubus Nights, en français) (c’est aussi le titre au Royaume-Uni, c’est pas complètement gratuit comme changement de titre) est le deuxième tome de la série Succubus que j’ai commencé le mois dernier. Dans ce tome-ci, Georgina, succube du titre, a deux problèmes. D’une part, Doug, son collègue à la librairie, a des sautes d’humeur des plus bizarres (mais son groupe de rock décolle à la vitesse grand V). D’autre part, Bastien, incube de son état, vient de débouler en ville avec pour mission de corrompre une animatrice télé option fondamentaliste homophobe. Ça reste drôle et distrayant, et les persos sont vraiment sympa. Marrant comme les deux séries (Vampire Academy et Succubus) sont différentes…

Kushiel’s Mercy, de Jacqueline Carey (La Grâce de Kushiel, en français) est le dernier tome de la trilogie d’Imriel dont j’ai parlé en septembre et en octobre. Pour pouvoir épouser celle qu’il aime, Imriel doit retrouver sa mère. Mais, avant même qu’il parte, un sort est jeté sur Terre d’Ange : tout le monde est persuadée que ladite dulcinée est partie de son plein gré épouser le prince de Carthage, et qu’Imriel est devenu fou et imagine tout ce qui s’était passé dans les années précédentes. Imriel part donc en quête pour régler tout ça. Une très très chouette conclusion à deux très très chouettes trilogies. Ils vont me manquer, tous.

Succubus Dreams, de Richelle Mead (même titre en français) est le dernier Richelle Mead de ce mois-ci, promis ;) et est… ben le 3e tome de Succubus. Georgina se réveille après des rêves très vivides complètement vidée de son énergie, ce qui est problématique et inquiétant. En plus, on lui a collé une stagiaire succube particulièrement inapte. Et ça reste drôle, donc que demander de plus !

S’il ny en avait qu’un à lire… Kushiel’s Mercy.

#balisebooks – Octobre 2013

Hop, je suis encore à la bourre pour le #balisebooks, mais je pouvais pas, j’avais un rhume. Et puis je savais que ce mois-ci allait être long à écrire parce que j’ai visiblement beaucoup lu… Et puis j’ai migré le blog sur wordpress.com aussi et c’était du boulot (non, ça a été en fait). Bref. J’pouvais pas j’avais piscine.

Kushiel’s Justice, de Jacqueline Carey (en français La Justice de Kushiel) est le deuxième tome de la deuxième trilogie de Kushiel dont j’ai commencé à parler dans le billet précédent. Après ses aventures du premier tome, Imriel rentre chez lui et accepte un mariage politique. Évidemment, le problème est qu’il en aime une autre – et que tout ça va évidemment avoir des conséquences, à la fois sur Imriel lui-même et sur ceux qui l’entourent. Imriel grandit/mûrit, aussi, et doit faire face à son propre héritage et à sa propre nature. Encore une fois, c’est difficile de parler de l’intrigue d’un bouquin sans tout révéler, et c’est encore pire lorsqu’il s’agit d’une suite – parce que même parler du début peut révéler des points importants des bouquins précédents ! Je vais juste me contenter de dire que la série reste très bonne et ne s’essouffle pas. Et je suis contente qu’il me reste un tome de cette trilogie et une autre trilogie encore derrière dans le même univers.

Girl 99, d’Andy P. Jones (pas de traduction) – heu, j’ai lu ce bouquin ya moins de deux mois et je m’en souviens déjà plus. Dispensable, donc. J’ai dû l’attraper sur une offre Kindle à pô cher, et ça valait pô plus.

Carrie, de Stephen King (même titre en français) est un grand classique que je n’avais jamais lu, voilà qui est réparé. L’histoire est celle de Carrie, une adolescente télékinésique dont les pouvoirs ont tendance à se déclencher lorsqu’elle est pas contente. Et, considérant que sa mère est folle à lier et qu’elle est le souffre-douleur de ses petits camarades de classe, ben ça arrive. Une particularité du bouquin est que l’histoire est entrecoupée de citations d’articles divers qui expliquent, assez tôt, le dénouement du bouquin. J’ai bien aimé, parce que ça permet de voir comment on en arrive là, mais je l’ai vu reproché comme « si on sait ce qui se passe à la fin c’est quand même vachement moins intéressant ».

The Immortal Life of Henrietta Lacks, de Rebecca Skoot (en français La Vie immortelle d’Henrietta Lacks) est l’histoire fascinante d’une lignée de cellules qui est très utilisée en biologie – la ligne HeLa (la version anglaise de la Wikipedia est beaucoup plus complète : HeLa, en anglais). C’est à la fois l’histoire d’Henrietta Lacks, dont les cellules sont à l’origine de ladite lignée, et du travail de la journaliste, Rebecca Skoot, pour retracer toute cette histoire et interagir avec la famille Lacks, en particulier la fille d’Henrietta, Deborah. Je ne peux que remercier Susan de m’avoir parlé de ce bouquin, c’était vraiment un truc à lire : en plus de l’histoire des cellules elle-même, on a un aperçu de la médecine hospitalière des années 40-50 aux États-Unis, et une réflexion intéressante sur les questions éthiques, sur le consentement des patients pour les prélèvements à visée de recherche et sur la propriété des prélèvements en question.

The Mystery of Mercy Close, de Marian Keyes (pas encore de traduction) est le dernier Marian Keyes. J’aime beaucoup Marian Keyes qui écrit des bouquins clairement orientés « chick lit », mais en général avec plus de profondeur que la moyenne du domaine. Je m’étais précipitée sur les derniers dès leur parution ; il m’a fallu un peu plus de temps pour attaquer celui-là dont les prémisses m’inspiraient a priori moins. C’est le cinquième « tome » des histoires de la famille Walsh, une famille irlandaise qui contient les parents et les cinq filles - on a vu un tome par fille à présent donc. Allez savoir s’il y en aura d’autres. Dans celui-ci, Helen, la petite dernière, est devenue détective privé et a été engagée pour retrouver le membre manquant d’un boys band sur le retour. Le problème, c’est aussi qu’Helen a un historique de dépression qui l’a déjà envoyée à l’hôpital une fois, et qui semble resurgir pour se venger. Helen part donc à la recherche de sa cible tout en se battant contre elle-même. Le résultat en est un bouquin émouvant et drôle que j’ai eu du mal à lâcher.

Théorème vivant, de Cédric Villani m’a été recommandé par au moins deux personnes, dont une fois dans les commentaires de ce blog – qu’elles en soient remerciées. Cédric Villani a obtenu la médaille Fields en 2010 (la médaille Fields est une des plus hautes récompenses, si ce n’est la plus haute, qu’un mathématicien puisse rêver obtenir), et c’est l’histoire du théorème qui lui a valu ladite médaille. Les maths y sont proprement incompréhensibles – du moins à mon petit niveau (la physique mathématique et l’analyse ne sont VRAIMENT pas mes domaines de prédilection), mais le processus est fascinant : partir d’une question, commencer à prouver des trucs, se rendre compte que ça marche pas, corriger, refaire, ajouter des bouts, en retirer – le bouquin capture vraiment le processus itératif, tout un tas de choses qu’on ne voit pas quand les théorèmes sont finalement enseignés avec leur preuve propre et sans bavure… Très chouette.

Succubus Blues, de Richelle Mead (même titre en français) est une lecture un peu plus « light » que les précédentes. C’est le premier tome d’une série qui met en scène Georgina Kincaid, succube et libraire. (Sisi.) En tant que succube, son but est de recruter pour le côté sombre de la Force – séduire quelqu’un, l’emmener au lit, lui piquer son âme. Facile. Les choses se compliquent évidemment quand elle rencontre une personne qu’elle aimerait bien emmener au lit mais dont elle aimerait bien aussi préserver l’âme – apparemment, les pouvoirs de succube ne s’éteignent pas. L’accident bête. Plutôt plaisant et drôle, j’ai attaqué le suivant dans la foulée… mais ça sera pour le prochain #balisebooks !

Bon, et tiens, d’ailleurs, j’inaugure une nouvelle rubrique de cet article, le « S’il n’y en avait qu’un à lire… » (et je vais faire les modifications correspondantes sur les billets précédents, paf). Donc :

S’il n’y en avait qu’un à lire… The Immortal Life of Henrietta Lacks.

On a bougé !

Heu, voilà, si vous lisez ce billet, c’est que vous avez trouvé où mon blog habite maintenant, bravo. (Ça veut aussi dire que j’ai pas complètement foiré mes redirections HTTP, ce qui est une bonne nouvelle). Donc, bienvenue dans les nouveaux locaux, j’espère que vous aimez la peinture, n’oubliez pas de mettre vos RSS à jour (NORMALEMENT c’est redirigé depuis l’ancienne adresse, mais je ne sais pas combien de temps ça va rester comme ça, ni même si ça marche "en pratique") et… et voilà !

#balisebooks – Septembre 2013

Kushiel’s Scion, de Jacqueline Carey (L’Héritage de Kushiel, en français) est le premier tome de la deuxième trilogie commencée par la trilogie de Phèdre, dont j’ai causé en juin et en juillet. C’est l’histoire de l’adolescence et du passage à l’âge adulte d’Imriel, dont je ne vais pas dévoiler ici les liens avec les personnages de la première trilogie. Disons que les liens en question sont suffisants pour attirer des gens qui ne lui veulent pas que du bien, y compris quand il se décide à quitter Terre d’Ange pour aller étudier à Tiberium. Un très chouette premier tome de trilogie, avec un bon mélange d’anciens et de nouveaux personnages, et dans la lignée de la trilogie précédente (et comme j’ai bien aimé la précédente, ben j’aime bien celui-ci aussi, voilà.)

Pavilion of Women, de Pearl S. Buck (Pavillion de femmes, en français), se passe en Chine et commence juste avant la seconde guerre mondiale. La maison Wu est une des plus riches et anciennes de Chine et, le jour de ses 40 ans, Madame Wu fait part de sa décision : elle demande à son mari de prendre une seconde épouse, plus jeune qu’elle-même, et va même jusqu’à la choisir. Les conséquences de cette décision ne sont pas exactement celles qu’elle attendait, et forment la trame du livre. Et c’est fort probablement un des meilleurs livres que j’ai jamais lus, toutes catégories confondues. Bon, j’ai appris a posteriori (parce que je manque cruellement de culture) que Pearl Buck avait un Nobel de littérature, donc ya peut-être des raisons.

Little Brother, de Cory Doctorow (même titre en français), ne joue pas vraiment dans la même catégorie (même si j’ai bien aimé aussi, hein). Dans une société un peu trop salement proche de la nôtre, Marcus, un ado de 17 ans, se retrouve au mauvais endroit au mauvais moment, et est accusé de terrorisme, emprisonné et interrogé. Il finit par être relâché, et se bat alors contre la société de surveillance dans laquelle il vit. Plutôt sympathique, techniquement crédible, et même parfois didactique (parfois de façon un peu lourdingue, mais bon). Les événements courants rendent le tout d’autant plus crédible et actuel, et c’est un peu flippant. Note : la version originale de Little Brother est disponible en ligne sous licence CC-NC-SA.

Ender’s Game, d’Orson Scott Card (La Stratégie Ender, en français), est un des « classiques » de SF que je n’avais pas encore lus, voilà qui est corrigé. Ender a six ans, et il est vu comme l’ultime espoir des humains face à l’invasion imminente des aliens (qui ont déjà fait quelques dégâts historiquement). Les enfants prometteurs sont envoyés à l’école de guerre pour en faire des soldats et des officiers : l’école fournit tout un tas de jeux pour apprendre aux enfants la stratégie militaire. Ender gravit les échelons très vite, et on suit son entraînement à partir de son recrutement. C’était plutôt agréable à lire, même si on a parfois du mal à remettre ça dans le contexte de « attends, il a genre 7 ans là ? ».

Aphrodite’s Workshop for Reluctant Lovers, Marika Cobbold, était très nettement le point faible de ce mois-ci. L’idée de base était plutôt sympa – Aphrodite trouve, au vu du taux de divorce courant, que les humains ont besoin d’un coup de main pour réussir à maintenir une vie sentimentale durable – et pour qu’elle-même puisse regagner un minimum de crédibilité sur l’Olympe. La mise en œuvre est poussive, la fin prédictible et ne répond même pas au prédicat initial. Bref, c’était vraiment pas terrible.

S’il n’y en avait qu’un à lire… Pavilion of Women.

TPA : Théorème des cinq couleurs

Aujourd’hui, c’est coloriage. Je vais déjà commencer par vous montrer un petit jeu : ça s’appelle Map, c’est tout con : le jeu vous donne une carte rectangulaire avec des zones à colorier, et quelques couleurs déjà placées ; il faut colorier les autres de façon à ce que deux voisins n’aient pas la même couleur. Allez-y, allez jouer un peu avec, c’est rigolo :P La question théorique derrière ce petit jeu est la suivante : quel est le nombre minimal de couleurs nécessaires pour pouvoir colorier n’importe quelle carte de ce type ? Peut-être que vous vous souvenez, mais j’ai déjà un peu parlé de problèmes de ce genre là : quand j’ai parlé de P vs NP, j’ai parlé de colorabilité de graphes, et de décider si un graphe donné pouvait être colorié avec un nombre donné de couleurs. La question du nombre minimum de couleurs peut revenir à poser la question précédente plusieurs fois : « et avec 2 couleurs, ça passe ? non ? et avec trois ? non plus ? et avec quatre ? ah, cool. » Là, normalement, j’ai deux objections dans la salle. La première, c’est : « minute papillon, tu parlais de cartes et là tu me parles de graphes, c’est pas pareil, si ? ». La deuxième, c’est « heu, dis voir, demander si un graphe peut être colorié avec trois couleurs, on a vu dans le P vs NP que c’était pas trivial comme question… donc on fait quoi, surtout qu’il y a peut-être beaucoup de nombres à considérer ? ». Il se trouve que la première objection permet de répondre à la deuxième. Pour répondre à la première objection, je vais faire un petit dessin. Voilà le petit dessin. map   Le petit dessin en question, il est fait comme suit :

  • j’ai commencé par dessiner la carte – la structure en noir ;
  • j’ai ajouté un point dans chaque zone de la carte (les points rouges) ;
  • j’ai relié deux points (avec les traits rouges) si les zones correspondantes étaient voisines.

NORMALEMENT j’ai vérifié ma construction, mais si elle est bancale (si j’ai des traits en trop ou en pas assez), merci de me le signaler :) Et là, que voit-on apparaître en rouge sous nos yeux ébahis ? Un graphe. Pas n’importe quel graphe, d’ailleurs : il s’agit d’un graphe planaire, c’est à dire qu’on peut le dessiner sur une feuille de papier sans que deux arcs se croisent. J’ai parlé de graphes planaires dans un billet de blog précédent : Planarité, mineurs et donuts. Là, il va falloir que vous me fassiez confiance sur quelques points. Primo, la construction ci-dessus est toujours possible. Deuzio, ça donne toujours un graphe planaire. Tertio, ce graphe planaire est unique pour une carte donnée : il a toujours le même nombre de sommets, et les arcs sont toujours les mêmes. Et c’est là qu’on répond à la deuxième objection. Oui, dans le cas général, décider si un graphe peut être colorié avec 3, 4, 5 ou 12 couleurs est difficile (au stade actuel de nos connaissances). Par contre, dans le cas particulier des graphes planaires, on sait plus de choses. Plus précisément, on connaît le théorème suivant, appelé « théorème des 4 couleurs » :

Tout graphe planaire peut être colorié avec au maximum 4 couleurs.

Et, comme corollaire au point précédent, je peux colorier une carte avec quatre couleurs (il suffit de faire ma petite construction là-haut, de colorier le graphe résultant, et de colorier chaque zone avec la couleur du sommet en question – rappelons que dans le cas qui nous intéresse, un coloriage est valide si deux sommets reliés par un arc n’ont pas la même couleur.) Un petit aparté: je parle de « cartes » ici, mais c’est pas vraiment applicable directement « dans la vraie vie ». Le problème principal, c’est que certains pays ne sont pas « connectés ». Et si on colorie une carte du monde, on s’attend à ce que, par exemple, la Guyane soit de la même couleur que la France. Ce qui ajoute des arcs entre la zone « France » et les zones « Brésil » et « Suriname », et qui risque fort de nuire à la planarité du graphe correspondant. Fin de l’aparté, revenons à nos moutons. Donc, si j’ai un graphe planaire, je peux répondre directement à la question « est-ce que ce graphe peut être colorié avec k couleurs » par « oui », dès que k est supérieur ou égal à 4. La preuve du théorème des quatre couleurs est… compliquée. J’en parlerai dans un prochain billet, mais il faut que je me documente encore un peu avant sur le sujet :)

Un résultat intéressant est que pour trois couleurs, même dans le cas « graphe planaire », le problème reste NP-complet ! (C’est un résultat de Stockmeyer en 1973, dans un article intitulé « Planar 3-colorability is polynomial complete », qui 40 ans plus tard est toujours planqué en tant qu’article payant à l’ACM. Mais je digresse.) Donc, pour 3 couleurs, c’est dur à décider, pour 4 couleurs, on sait qu’on peut le faire, mais c’est dur à prouver. En revanche, le théorème suivant est relativement simple à prouver :

Tout graphe planaire peut être colorié avec au maximum 5 couleurs.

J’ai dit que c’était relativement simple à prouver, et donc je vais le faire. Ça va quand même être probablement un peu long, donc accrochez-vous, et je vais essayer de faire preuve de pédagogie :)

J’ai besoin d’un premier résultat pour ma preuve :

Tout graphe planaire contient au moins un sommet de degré au plus 5.

Le degré d’un sommet, c’est le nombre d’arcs qui y sont connectés. Comme un arc connecte exactement deux sommets, si je fais la somme des degrés de tous les sommets, j’obtiens deux fois le nombre d’arcs (parce qu’un arc donné est compté exactement deux fois, une fois à chacune de ses extrémités). Maintenant, je vais vous demander d’admettre encore un truc, c’est qu’on connaît le nombre maximal d’arcs d’un graphe planaire, en fonction de son nombre de sommets, n : il y a au plus 3n-6 arcs, dès qu’il y a plus de deux sommets (comme on me l’a fait remarquer en commentaire). Je pourrais aussi le démontrer, mais ça implique encore un résultat intermédiaire, et ce billet va finir par être vraiment beaucoup trop long (dit-elle au bout de deux pages). Comme j’ai au plus 3n-6 arcs, la somme des degrés de tous les arcs d’un graphe planaire est inférieure ou égale à 6n-12. Par conséquent, il y a au moins un sommet de degré au plus 5 : si ce n’est pas le cas, la somme des degrés de tous les arcs est supérieure ou égale à 6n (6 arcs, multipliés par n sommets), et ce n’est pas possible pour un graphe planaire.

Revenons à nos moutons initiaux : on veut maintenant démontrer que tout graphe planaire peut être colorié avec au maximum 5 couleurs. On va faire un raisonnement par récurrence sur le nombre de sommets du graphe. J’ai interrompu la rédaction de ce billet pour aller faire un billet sur le raisonnement par récurrence, allez le lire si le terme ne vous est pas ou plus clair :) Donc, on commence par traiter l’hypothèse de base. Si mon graphe n’a qu’un seul sommet, je peux le colorier avec au maximum 5 couleurs : j’en choisis une pour mon sommet, et voilà.

Maintenant, je suppose que l’hypothèse de récurrence suivante est vraie : tout graphe planaire à (n-1) sommets peut être colorié avec au maximum 5 couleurs. Le but du jeu est maintenant de déduire, à partir de ça, que tout graphe planaire à n sommets peut être colorié avec au maximum 5 couleurs. Pour ça, on considère un graphe à n sommets, n’importe lequel (si je démontre que ça marche pour n’importe quel graphe, je montre que ça marche pour tous les graphes). Par le résultat intermédiaire que j’ai prouvé au-dessus, le graphe à n sommets étant planaire, il a un sommet de degré inférieur ou égal à 5, qu’on va appeler v dans la suite pour aller vite. On peut prendre v, et le retirer temporairement (on retire aussi tous les arcs qui y sont connectés). Le graphe sans v est un graphe planaire à (n-1) sommets. Donc, on peut le colorier avec au maximum 5 couleurs. Maintenant, on remet v (et les arcs qu’on a retirés aussi) : on obtient un graphe à n sommets dont (n-1) sommets sont coloriés avec au maximum 5 couleurs, et un sommet, v, n’a pas encore de couleur.

Là, on a deux possibilités. Si les voisins de v (les sommets auxquels v est connecté) utilisent moins de 5 couleurs, on peut utiliser une des couleurs non utilisées pour colorier v, et le graphe initial est colorié avec au maximum cinq couleurs.

Sinon, si on prend une représentation plane du graphe planaire, on est dans la situation suivante :

fiveneighbors Je n’ai dessiné ici que six sommets, v et ses cinq voisins. Le graphe peut contenir plus de sommets et plus d’arcs, mais il contient forcément cette structure.

Sur ma représentation plane, je choisis arbitrairement un voisin de v, je l’appelle v1, et je numérote les autres dans le sens des aiguilles d’une montre (v2 à v5). Les sommets v1 à v5 sont de cinq couleurs différentes. Je vais maintenant prouver que je peux soit colorier v1 et v3 de la même couleur, soit colorier v2 et v4 de la même couleur.

Je regarde d’abord v1 et v3, et plus précisément je m’intéresse au sous-graphe colorié avec les couleurs de v1 et de v3, c’est-à-dire que je prends tous les sommets de la couleur de v1 (gris, sur la figure) et tous les sommets de la couleur de v3 (bleu, sur la figure), et tous les arcs du graphe initial qui relient ces sommets entre eux. Un exemple sur un petit graphe :

subgraphÀ droite, j’ai représenté le sous-graphe du graphe de gauche en ne prenant que les sommets bleus et gris (j’ai supprimé les sommets rouges et violets, et les arcs qui y étaient attachés). Sur ma figure, j’ai quatre sommets entre lesquels j’ai des chemins (une suite d’arcs qui me permettent de passer de l’un à l’autre), et un sommet qui n’a de chemin vers aucun autre.

Si je ne regarde que les sous-graphe bleu/gris de mon graphe initial, j’ai deux possibilités : soit v1 et v3 ne sont plus connectés, soit ils le sont encore ; et par « connectés », j’entends qu’il y a un chemin entre v1 et v3. S’il n’y a pas de chemin, v1 et v3 sont dans des composants différents (un composant, c’est un ensemble de sommets qui sont reliés les uns aux autres par des chemins). Dans ce cas là, je regarde le composant qui contient v3 (il se peut que ce soit v3 tout seul, mais sinon c’est un ensemble de sommets bleus et gris qui ont tous un chemin connecté à v3). Dans ce composant-là, le fait que les sommets soient bleus ou gris est arbitraire : je peux inverser les deux couleurs sans que ça ait un impact sur le fait que le graphe est correctement colorié. Si je ne fais ça que dans ce composant là, v1 (qui n’est pas dans composant en question) reste gris, et v3 (qui était bleu) devient gris. Maintenant, je peux remettre le « reste » du graphe (les sommets rouges, violets, verts, et le sommet v qui n’est pas encore colorié) : comme je n’ajoute pas de sommets bleus ou gris, le coloriage reste valide. Et j’ai « libéré » le bleu pour mon sommet v : donc, je peux colorier v en bleu. La vie est belle.

Enfin, presque. Parce qu’il se peut aussi que v1 et v3 soient dans le même composant « bleu/gris ». Donc là, si j’inverse le bleu et le gris, ben je me retrouve avec v1 en bleu, et v3 en gris, et je peux toujours rien faire avec v. Donc, il faut trouver une autre astuce.

Je regarde maintenant le sous-graphe composé des sommets coloriés avec les couleurs de v2 (rouge) et v4 (vert) : je retire tout ce qui n’est pas rouge ou vert du graphe, et je regarde ce qui reste. Si v2 et v4 ne sont pas dans le même composant rouge/vert, je peux inverser le rouge et le vert dans le composant de v4. v2 reste rouge, v4 devient rouge, et je peux colorier v en vert. Là, j’ai peut-être quelqu’un qui me dit « oui, mais si v2 et v4 sont aussi dans le même composant, tu as le même raisonnement et donc le même problème que pour le composant bleu/gris ! ». Oui, mais. Regardons un peu ce qui se passe sur la figure. Comme v1 et v3 sont dans le même composant bleu/gris (sinon, on n’aurait pas besoin de regarder ce qui se passe dans le composant rouge/vert), il y a un chemin entre v1 et v3 composé de sommets bleus et gris.

bluegreypath

Si je veux faire un chemin composé de sommets verts et rouges entre v2 et v4 (ce qui est la condition pour que v2 et v4 soient dans le même composant rouge/vert), ça bloque : soit je dois croiser l’arc entre v et v3, soit je dois croiser un des arcs du chemin bleu/gris entre v1 et v3. Et comme mon graphe est plan… ben j’ai pas de croisement entre mes arcs. Donc, v2 et v4 ne peuvent pas être dans le même composant, donc je peux bien inverser les couleurs du composant de v4, et colorier v en vert.

J’ai donc regardé tous les cas possibles pour mon graphe, et dans tous les cas, je peux colorier le sommet v de façon valide. Donc, si un graphe avec (n-1) sommets peut être colorié avec au maximum 5 couleurs, alors un graphe avec n sommets peut être colorié avec au maximum 5 couleurs, ce qui termine mon étape de récurrence et donc la preuve du théorème des cinq couleurs. Ouf.

J’avais initialement prévu de parler du théorème des 4 couleurs plus en détail dans ce billet, mais je crois que je vais arrêter là pour ne pas fumer plus de neurones de mon lectorat (en espérant qu’il y en ait quand même une partie qui soit arrivée jusqu’ici…). Comme d’habitude, pour les questions, typos, remarques, etc., c’est dans les commentaires que ça se passe :)

Raisonnement par récurrence et raisonnement par l’absurde

Pouf pouf, un petit billet vite fait pour pouvoir y faire référence plus tard – je suis en train de faire un autre monstro-billet, et je me suis rendue compte que j’avais besoin des éléments suivants pour faire un truc qui tienne à peu près debout, donc hop, un deuxième billet ! Je vais causer ici de deux outils fondamentaux dans la « boîte à outils » nécessaire pour prouver des trucs : le raisonnement par récurrence et le raisonnement par l’absurde. Ce sont des outils qui sont présentés et utilisés au moins au lycée (du moins de mon temps ;) ), et qu’on retrouve à longueur de temps, partout, donc autant expliquer comment ça marche.

Le raisonnement par récurrence

Le principe du raisonnement par récurrence, c’est les dominos. Pas ceux avec des points, ceux qu’on fait tomber. On sait que si on fait tomber un domino, le suivant tombe aussi. Et on fait tomber le premier domino. Du coup, tous les dominos tombent.

Pour le raisonnement par récurrence, c’est pareil. On a une propriété qui dépend d’un entier, et on veut prouver qu’elle est vraie pour n’importe quel entier. Donc ce qu’on fait, c’est qu’on commence par montrer qu’elle est vraie pour un petit entier, genre 0, 1, 2 (parfois les cas pour 0 ou 1 n’ont pas beaucoup de sens). Et on montre que si elle est vraie pour un entier k, alors elle est vraie aussi pour un entier k+1. Du coup, on a le « départ » des dominos (« c’est vrai pour 0 ») et le « chaînage » des dominos (« si c’est vrai pour n, c’est vrai pour n+1 ») ; et si ces deux conditions là sont vraies, alors tous les dominos se cassent la gueule (« la propriété est vraie pour tous les entiers à partir de celui qu’on utilise comme cas de base »).

Là, je suis un peu embêtée, parce que j’ai un exemple qui marche, mais la preuve est assez nulle par rapport à une autre, qui est plus jolie. Donc je vais montrer les deux :) Je veux démontrer que la somme des entiers de 1 à n est égale à n(n+1)/2, pour n’importe quel n. Je commence par n = 1 : j’ai bien 1(1+1)/2 = 2/2 = 1, donc l’hypothèse de base est vraie.

Ensuite, je suppose que c’est vrai pour un entier k, c’est à dire que la somme des entiers de 1 à k est égale à k(k+1)/2. Maintenant, je calcule la somme des entiers de 1 à k+1 : 1 + 2 + 3 + … + (k-1) + k + (k+1), c’est égal à la somme des entiers de 1 à k, plus (k+1). Par hypothèse de récurrence, c’est égal à k(k+1)/2 + k+1 = (k² + k + 2k + 2)/2 = (k² + 3k + 2)/2. Pour que ma preuve fonctionne, je veux que la somme des entiers de 1 à k+1 soit égale à (k+1)(k+2)/2. Et il se trouve que (k+1)(k+2), ça fait précisément k² + 3k + 2.

J’ai donc mon hypothèse de base, mon étape de récurrence, et j’ai prouvé ce que je voulais prouver.

Pour le fun, la preuve que je préfère sur cette égalité, c’est celle-ci : on considère un tableau à deux lignes et n colonnes :

1  2   3   4 ... n-2 n-1 n
n n-1 n-2 n-3     3   2  1

et on additionne les deux lignes. Chaque colonne vaut n+1 : c’est le cas pour la première colonne, et à chaque étape, on ajoute 1 à la première ligne et on enlève 1 à la deuxième ligne, donc la somme reste identique. (Quelque part, ici, je fais du raisonnement par récurrence sans vraiment le dire !). J’ai n colonnes, donc si j’additionne tous ces résultats, ça fait n(n+1). Et si je fais la somme dans l’autre sens, la première ligne est égale à la somme des entiers de 1 à n, la deuxième ligne aussi… donc mon n(n+1), c’est aussi deux fois la somme des entiers de 1 à n.

Le raisonnement par l’absurde

Le raisonnement par l’absurde est parfois un peu dangereux/délicat, parce qu’il est parfois utilisé à tort et à travers. Admettons que je veuille prouver qu’une phrase A est vraie. L’idée du raisonnement par l’absurde, c’est de partir du principe que A est faux, de dérouler une suite d’arguments impliqués par le fait que A est faux, et d’arriver à quelque chose qu’on sait être impossible. Si le fait que A est faux implique que quelque chose d’impossible arrive, c’est que A est vrai, sinon l’univers se casse la gueule et ça fait désordre.

Mon exemple préféré, c’est de démontrer que \sqrt 2 est irrationnel, c’est à dire qu’on ne peut pas l’écrire sous la forme \frac p q avec p et q des nombres entiers.

J’ai besoin d’une toute petite preuve au passage : j’affirme que si un entier n est pair, alors son carré n² est pair, et que si n² est pair, alors n est pair. Si n est pair, je peux l’écrire comme n = 2k, et donc n² = 4k² = 2 × 2k², donc n² est pair. Si n est impair, je peux l’écrire comme n = 2k+1, donc n² = 4k² + 2k + 1 = 2(2k² + k) + 1, donc n² est impair. Donc si n² est pair, il ne peut pas arriver que n soit impair (parce que sinon n² serait impair aussi), donc n est pair.

Donc, supposons qu’on puisse écrire \sqrt 2 = \frac p q. On peut aussi supposer que la fraction est irréductible, parce que si elle ne l’est pas, on peut la réduire pour qu’elle le soit (rappel : une fraction \frac p q est irréductible s’il n’existe pas d’entier k tel que p et q soient tous les deux divisibles par k. Si k existe, on divise p et q par k, et on considère la fraction \frac{p/k}{q/k}). Donc, je peux écrire que \sqrt 2 \times q = p. Je mets tout au carré, et j’obtiens que 2q² = p². Comme q est entier, q² est entier aussi, et donc p² est pair (puisque c’est deux fois un nombre entier). Mais si p² est pair, alors p est pair aussi, d’après ma preuve auxiliaire. Donc je peux écrire p = 2k, et donc p² = 4k². Mais du coup, comme 2q² = p² = 4k², je peux écrire que q² = 2k², et donc q² est pair, et q est pair. Mais ça, c’est pas possible : la fraction \frac p q est irréductible, donc p et q ne peuvent pas être pairs en même temps ! Donc, j’ai un truc qui ne va pas dans mon raisonnement, et ce truc, c’est mon hypothèse initiale, c’est-à-dire que \sqrt 2 est rationnel. Donc, \sqrt 2 est irrationnel. Joli, non ?

#balisebooks – Août 2013

Tiens, je suis en retard pour mon #balisebooks. Étonnant, non ? Non. Sans plus attendre, donc…

The Ghost Brigades, de John Scalzi (en français Les Brigades fantômes) – deuxième tome qui se passe dans l’univers du Vieil homme et la guerre (Old Man’s War), dont je parle dans un autre #balisebooks. Entre temps, Scalzi a gagné le Hugo pour Redshirts - j’ai donc eu le plaisir hipster d’avoir lu le Hugo avant qu’il soit attribué, ça, c’est fait. Bref, Ghost Brigades. Je l’ai trouvé nettement en deçà de Old Man’s War, ça, c’est un fait. On suit l’histoire de Jared Dirac, qui fait partie desdites brigades fantômes – une force spéciale de l’armée composée de gens-qui-sont-morts-dont-on-a-récupéré-l’ADN-pour-faire-des-supersoldats. Et là-dessus, la guerre approche, et Dirac se retrouve (complètement pas par hasard) à être le dernier espoir de l’éviter. Les brigades fantômes faisaient clairement partie des choses laissées en suspens dans Old Man’s War ; Ghost Brigades vise au moins en partie à expliquer tout ça. Et c’est plutôt bien fait, c’est crédible (dans l’univers en question), c’est bien écrit, tout ça – mais ça reste décevant par rapport à Old Man’s War. Évidemment, c’est peut-être injuste de comparer les deux - peut-être que sans le premier, j’aurais trouvé le deuxième plus chouette, allez savoir. Dans tous les cas, ça reste une lecture agréable, hein - mais vaguement décevante.

Biting Bad, de Chloe Neill (pas encore de titre français) - huitième tome de Chicagoland, qui est possiblement ma série de littérature-à-vampires préférée et dont, apparemment sauf erreur de ma part, je n’ai pas encore parlé dans #balisebooks (ils ont dû tomber dans le trou noir sans #balisebooks). La série Chicagoland se passe, de façon hyper prévisible, à Chicago. Merit, l’héroïne, est transformée en vampire à l’insu de son plein gré dans le premier tome, et est enrôlée au sein de la maison Cadogan, une des trois maisons de vampires établies à Chicago. Elle devient Sentinelle de ladite maison, et dans la grande tradition de série de littérature-à-vampires, se tatane l’ennemi-de-l’année-du-tome dans chaque tome. J’aime particulièrement cette série-là parce que je trouve les personnages vraiment sympa ; j’aime aussi le fait que les vampires, ben ils mangent (de la « vraie » nourriture), et qu’ils ont l’air de bien bouffer. C’est aussi une série qui me fait dire que j’irais bien à Chicago, à l’occasion (en partie pour la raison sus-citée, il faut l’admettre.) Dans ce huitième tome, que j’avais précommandé et que j’ai lu dans la semaine suivant sa publication, une série d’émeutes anti-vampires secoue Chicago. Qui se cache derrière et comment les arrêter ? Et c’est un bon tome de la série - c’est plutôt bon signe, je trouve, si le huitième tome reste à un bon niveau. Vivement le neuvième ! (Février 2014… bon :) )

The Perks of Being a Wallflower, de Stephen Chbosky (Le Monde de Charlie, en français), est l’histoire de Charlie, un lycéen un peu bizarre, timide, introverti, et tout ce qui s’en suit. Le livre est composé de « lettres » de Charlie à un lecteur non nommé. C’est assez bizarre, comme bouquin, parce que l’histoire en soi est assez peu crédible (Charlie a une quinzaine d’années mais on a parfois l’impression qu’il en a huit), mais les détails de l’histoire sont plutôt chouettes. Globalement, j’ai bien aimé, mais je suis pas exactement sûre de savoir pourquoi.

Death’s Daughter, d’Amber Benson (pas traduit à ma connaissance) est un bouquin que j’ai acheté à cause de son auteur, qui joue Tara dans Buffy. Il raconte l’histoire de Calliope Reaper-Jones qui, on l’apprend assez vite et on le devine dans le titre, se trouve être la fille de la Mort (Death, en anglais). Le truc gênant, c’est que Death (le papa de Calliope, donc) s’est fait enlever, et que Calliope hérite par conséquent de l’entreprise familiale le temps que tout revienne à sa place. Calliope n’ayant aucune envie de se retrouver dans cette situation, elle se met à la recherche de son père (et de sa sœur qui a eu le mauvais goût de se faire enlever en même temps). Verdict : ça se lit, mais c’est pas grand. J’ai pas détesté, mais bon, vite lu vite oublié, je pense.

Queen Unseen: My Life with the Greatest Rock Band of the 20th Century, de Peter Hince, est exactement ce que le titre dit ;) J’ai trouvé ça par hasard sous un petit pois en promo sur Amazon l’autre jour, me suis dit « boah pourquoi pas », et donc j’ai lu ça en août. Peter Hince a été « roadie » (la wikipédia me suggère « machiniste itinérant » comme traduction, admettons - bref, un mec qui bosse sur les tournées, quoi) de Queen pendant des années, et c’est son autobiographie. Plutôt sympa d’avoir une idée de ce à quoi peuvent ressembler les coulisses d’un machin pareil – un peu bordélique, comme bouquin, mais finalement assez drôle.

Voilà, c’est tout pour le mois d’août !

S’il n’y en avait qu’un à lire… Biting Bad.