Je suis pas gamer, mais… 1 – Un historique lourd

Publié le par Balise7 commentaires

Je ne me suis jamais considérée comme « gamer ». J’ai toujours joué « un peu », je n’ai jamais énoncé « jeux vidéos » comme catégorie dans « qu’est-ce que tu fais de ton temps libre ? »… du moins jusqu’à relativement récemment.

Parce qu’il faut bien le dire, je passe quand même une quantité de temps non-nulle et non négligeable à jouer à des trucs plus ou moins crétins. Mais la réalisation que c’est le cas et que ça me manquerait probablement si ça ne l’était pas est plutôt récente. Et pourtant… Juste pour rigoler, une liste vaguement commentée de mes jeux « historiques » marquants, dans un ordre plus ou moins chronologico-thématico-aléatoire. Et avec des liens vers des vidéos aléatoires aussi (j’ai pas regardé l’intégralité de toutes, je l’admets ! Et j’espère ne pas m’être trop vautrée dans les liens.). Attention, ce post a un haut potentiel de procrastination. Déjà, il fait pas 1000 mots et j’ai passé deux bonnes heures à le rédiger, alors… 🙂

  • Night Mission, sur Apple ][ – c’est un flipper, et je crois que c’est le premier truc auquel j’ai joué – du moins de façon « documentée » – y paraît quand j’étais pas bien vieille 😉
  • Dans les flippers, ya eu Tristan aussi, qui était à l’époque seulement sur Mac, et qui est sorti sur PC plus tard. J’ai joué à pas mal d’autres flippers, mais je me souviens plus des noms 😦
  • Super Bunny, sur Apple ][ – un jeu débile avec un lapin qui saute de plate-forme en plate-forme. J’ai passé un nombre d’heures incalculable à faire sauter ce lapin. (Je proteste sur la fin de la vidéo qui dit que c’est really bad. On touche pas à Super Bunny.)
  • Toujours sur Apple ][, le Decathlon, un jeu… Microsoft (sisi). Pareil, des heures à faire 1-2-1-2-1-2-1-2 pour faire avancer un petit T à l’écran plus vite que son voisin.
  • Et la version thématiquement similaire, graphiquement plus évoluée, de Summer Games (avec le plongeon !)
  • Et plus tard, sur PC, Winter Challenge, la version hiver (avec le saut à ski !).
  • Pick-a-Dilly-Pair, sur Apple ][ encore – un jeu de Memory avec plein d’options rigolotes comme un Memory « audio » sans l’affichage des images mais seulement avec la musique (parce que oui, yavait de la musique sur les cartes). Je crois que je me souviens de toutes les musiques.
  • Les jeux auxquels j’ai toujours été nulle : Lode Runner, Conan (foutu piaf), Crisis Mountain.
  • Je me souviens aussi de Dark Designs – ça c’était un RPG rigolo, et Papa me disait au courrier qu’il avait reçu le deuxième quand j’étais en classe de neige 🙂
  • J’ai passé beaucoup (beaucoup) de temps sur les jeux Lucasarts –  Monkey Island I et II (un jour je finirai le III et le IV…), Day of the Tentacle, Sam&Max, Loom (qui est sorti avant mais auquel j’ai joué plus tard, et qui était assez bizarre), Full Throttle (sympa mais trop court) – je ne mets que les intros ici, parce que sinon ça spoile ;).
  • J’ai aussi joué à d’autres jeux dans le même genre – Gobliins 2 et Legend of Kyrandia me viennent en tête.
  • Dans un tout autre genre, Stunts a eu son heure de gloire aussi. Le truc vachement cool avec Stunt Cars, c’était l’éditeur de niveau. Et quand on mettait trois tremplins à la suite, les bagnoles volaient, c’était cool. Me souviens avoir joué à un autre jeu de rallye, mais me souviens plus du titre, ni même de l’époque (à part « il y a longtemps »).
  • Ya eu Diablo, aussi, dans la série des chronophages. C’était bien, Diablo. J’ai peu joué au II et pas du tout au III.
  • Dans la série des trucs où j’ai joué à l’un de la série mais pas du tout aux autres, je voudrais Warcraft II. Zog zog. On y a aussi joué en réseau avec les copains en sup – montage des babasses à la maison, réseau en coax, et tout et tout. Fun times 🙂
  • Dans les trucs auxquels on jouait en réseau, yavait Duke Nukem 3D, aussi. J’ai aussi, incidemment, de bons souvenirs de l’éditeur de niveau de D3D.
  • Duke Nukem, j’ai d’ailleurs joué au I (mais pas au II) du temps où c’étaient des jeux de plateforme. Et dans les jeux de plateforme, on citera aussi Crystal Caves et Cosmo’s Cosmic Adventures (et sa musique… entraînante ?)
  • Bon, évidemment, on peut pas oublier Doom et Doom II. Et, pour les nostalgiques, ya la musique complète de Doom I et Doom II sur YouTube.
  • Et, bien plus tard, limite moderne par rapport au reste de la liste, Quake 3 Arena (j’ai jamais vraiment joué au I ni au II). J’aime bien Q3A parce qu’il y a pas de scénario 😉 Ça, j’ai surtout joué en école et en réseau. Ben j’y suis toujours aussi nulle 😉
  • Pour finir, les jeux dits « à la con », qui existent toujours pour beaucoup sous une forme ou une autre : le Démineur (si je me souviens bien j’ai réussi à taper le 90s sur le gros, j’étais fière de moi), Tetris (argh, je sais plus comment s’appelait la version à laquelle je jouais) et Blockout, Oil Cap.

Je sais que j’en oublie. Je suis sûre que j’en oublie. Mais ça commence à faire une longue liste, déjà. Et, au vu de la liste, faut vraiment que je remercie mes parents de nous avoir mis tout ça à disposition, et d’avoir supporté la bande son de tout ça pendant toutes ces années… 🙂 Dans le prochain billet… à quoi je joue en ce moment ?

La fiiiibre !

Publié le par Balise5 commentaires

Ça y est, c’est arrivé ! Après l’inondation, après le remplacement de la canalisation d’eau en bas, on se disait « bon, ils sont pas complètement idiots, tant qu’à faire de percer le bitume, ils vont ptêt en profiter pour passer la fibre… ? ». Les mois passaient, les rafraîchissements de page de disponibilité, mi 2016, mouif… Et puis un beau jour ça a commencé à se débloquer. On a vu des panneaux dans la rue – bon, la page de disponibilité affichait toujours mi 2016, c’était douteux, surtout qu’ils affichaient un délai de seulement quelques mois dans la rue d’à côté, argh.

On a fini par avoir un papier dans l’immeuble : « la société machin fibre l’immeuble, z’inquiétez pas de voir des gens passer des câbles, c’est normal. ». Ça parlait pas encore des logements, mais ça commençait à ressembler vraiment à quelque chose.

Quelques semaines plus tard, un papier sur l’immeuble d’à côté – « la société truc fibre les logements, oubliez pas de gérer les clés si vous êtes pas là ». L’immeuble d’à côté est en fait l’entrée d’à côté du même immeuble, et tous les appartements sont gérés par la même société. Bien bien bien. Plusieurs semaines passent encore, on se demande un peu pourquoi à côté c’est fait et pas chez nous, on calimérote un petit peu parce qu’il faut bien. Mon hypothèse reste qu’ils fibrent les apparts quand la première personne de l’immeuble réclame la prise, mais je n’ai pas d’information ni pour confirmer, ni pour infirmer la chose. On envisage sérieusement de pinguer le fournisseur de fibre qui nous paraît s’imposer histoire de tenter de lancer la machine, quand tout à coup la procrastination paye : « les mecs, on fibre les apparts ! » apparaît sur toutes les portes de l’immeuble. Yaaayyy ! Moins yaaaaay : ils font évidemment ça la semaine où on est en vacances. On gère un copain qui reste à l’appart le jour où ils passent, ça c’est réglé.

Reste un léger problème : ils disent de laisser le passage « à côté de la prise télé et téléphone du salon ». À côté de la prise télé du salon, ya une Expedit pleine de jeux de société (c’est lourd, le carton et les cubenbois) et contre l’Expedit, ya le buffet à vaisselle (c’est lourd, la porcelaine). Et pour tout dire, ça fait un peu chier de déplacer tout ça, surtout que techniquement, ya la place. La boîte qui s’occupe du fibrage a laissé une adresse mail : j’envoie des photos, un « dites, ça passe, d’après vous, ou faut que je bouge l’étagère qui pèse un âne mort ? ». La réponse tombe « ya pas la place, ça serait bien de la bouger, ou au moins de la vider histoire qu’on puisse la bouger nous. » Pierre bouge les meuble, déplace le buffet à vaisselle de l’autre côté de la porte (ça a son importance), déplace l’Expedit, et nous voilà partis en vacances en laissant les clés et du thé au copain qui se charge de réceptionner l’électricien. Ledit copain nous envoie un mail dans la soirée de l’intervention, tout s’est bien passé, youpi.

Retour à la maison, grattage de crâne – pas de prise fibre en vue. Je conclus un peu rapidement qu’ils ont collé ça dans le boîtier existant – je sais pas à quoi ça ressemble une prise fibre, je sais pas à quoi ressemblait le boîtier avant que je parte mais il me semblait qu’il était plus poussiéreux que ça, bon. Bizarre, admettons. Jusqu’à ce que je remarque, derrière le buffet à vaisselle poussé de l’autre côté de la porte (mais vachement contre le mur quand même) un machin qui était pas là avant. Aha, me dis-je en mon for intérieur, c’est là qu’ils l’ont mise ! Et effectivement, ils ont visiblement tiré le buffet, posé la prise, et remis le buffet contre la prise là où il était. Pas contrariants, les mecs.

La prise est donc de l’autre côté de la pièce par rapport à la prise télé, et de l’autre côté du mur par rapport à la prise téléphone. Admettons.

Une fois la prise posée, on a donc contacté Fiber7, qui a le bon goût de proposer du giga symétrique. À Zürich (et peut-être plus généralement), le truc standard est qu’ils posent quatre fibres en même temps : une pour EWZ (le fournisseur d’électricité qui se trouve être fournisseur de fibre aussi, c’est eux qui ont posé a priori chez nous), une pour Swisscom, et les deux autres libres. On doit techniquement pouvoir faire du redondant sur deux fournisseurs différents 😉

On a envoyé le formulaire lundi dernier en soirée. Mercredi, yavait un modem dans la boîte aux lettres, ce soir le modem affichait autre chose que « no link ». Le temps de brancher une babasse dessus, ça donne ça :

4336880009

Bon, la première observation, c’est évidemment « mouahahahahahahahahah ». La deuxième observation c’est qu’on est un peu loin du giga, quand même. Fiber7 a tout un tas d’explications en allemand qui vont de « oui mais alors c’est pas impossible que ça sature EN FACE » à « si votre câble réseau est moisi ou si vous faites ça sur wifi, FORCÉMENT ça marche moins bien » en passant par « au fait, le modem qu’on vous refile et dans la config qu’on vous refile, au mieux il tape le 600M. Ça reste un bon bidule et si vous voulez vraiment taper plus collez-le en bridge et basta ». En pratique, je vois pas bien ce que je ferais avec 1G symétrique que je pourrais pas faire avec 300M symétrique (ce qui est quand même pas loin de vingt fois ce qu’on avait en down jusqu’ici…), alors j’ai pas trop investigué pour l’instant. Ni testé beaucoup, il faut le dire, pour de basses raisons matérielles.

Le truc très con, c’est que la prise fibre est dans le salon. Les babasses, elles sont dans le bureau. Passer du câble depuis le salon vers le bureau, c’est pas un problème trivial. Trouver un endroit où poser le modem, non plus. Va falloir se creuser un peu la tête pour faire marcher tout ça proprement… Mais bon, on a la fiiiiiibre !

#balisebooks de printemps

Publié le par BaliseLaisser un commentaire

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

Publié le par Balise1 commentaire

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

Publié le par Balise1 commentaire

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

Publié le par Balise2 commentaires

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

Publié le par Balise3 commentaires

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

Publié le par Balise1 commentaire

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

Publié le par Balise2 commentaires

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

Publié le par Balise5 commentaires

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.