Catégorie : ETHZ

Les algorithmes PPZ et PPSZ

Publié le par Balise2 commentaires

Aujourd’hui, on va causer 3-SAT, et on va en particulier causer de deux algorithmes très voisins, les  algorithmes PPZ et son petit frère PPSZ.

Il est plus que temps que je m’attaque à ce billet que j’aurais dû écrire depuis longtemps déjà. C’est un billet qui me tient à cœur parce que ça fait un an et demi que je fais des trucs autour de ces algorithmes, et que je commence à en avoir une assez bonne idée 🙂

Rappelons un peu de formalisme, histoire qu’on sache tous de quoi on est en train de parler. Pour une intro avec un peu plus de détails, voir mon billet sur SAT. J’ai n variables x_1,..., x_n, et j’ai des formules qui sont de ce type:

(x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_3 \vee x_4) \wedge (x_6 \vee x_7 \vee x_8) \wedge ...

et je veux déterminer si, étant donné une telle formule, il existe des valeurs pour les variables x_1 à x_n (on parle d’une affectation) qui permettent d’évaluer la formule à 1 (on dit alors que la formule est satisfaite). Dans le cas général, c’est un problème NP-complet ; on a donc peu de chance de trouver un algorithme efficace qui marche à tous les coups. C’est bien le « à tous les coups » qui m’intéresse ici : je me demande ce que je peux garantir pour mon algorithme, même si je tombe sur la formule la plus difficile du monde. Le « record » actuel pour ce type de garantie est actuellement pour l’algorithme PPSZ, qui est un algorithme aléatoire, et qui est le sujet de ce billet. Comme je parle d’algorithme aléatoire, il me paraît un poil plus intuitif de parler de probabilité de succès que de temps d’exécution même si, on l’a vu, les deux notions sont liées – puisqu’il suffit de répéter un algorithme aléatoire avec une probabilité de succès donnée suffisamment de fois pour être raisonnablement sûr qu’il réussisse. Ça fait un peu Shadok, mais passons. Je vais aussi, dans ce qui suit, supposer que j’ai une formule pour laquelle je sais qu’il existe un ensemble de valeurs qui la satisfont, et que je veux « juste » trouver les valeurs en question. En pratique, les deux problèmes sont liés aussi : je peux supposer que si mon algorithme trouve ces valeurs, ben c’est qu’elles existent, et que si je cherche suffisamment longtemps sans les trouver, ça serait quand même pas de bol qu’elles existent et que je les aie ratées.

L’algorithme aléatoire le plus simple auquel on peut penser est de prendre des valeurs au hasard, de vérifier si elles satisfont la formule, et de recommencer si c’est pas le cas. Toutes les affectations possibles ont la même probabilité (si je les choisis au hasard comme ça) – et j’en ai 2^n – parce que pour chaque variable, j’ai deux possibilités, 0 ou 1. Donc la probabilité de succès de cet algorithme, si j’ai \ell affectations qui satisfont ma formule, est de \ell / 2^n : parmi les 2^n choix que je peux faire, j’en ai \ell qui marchent.

Après, il y a moyen de faire les choses de manière un peu plus intelligente. Plutôt que d’affecter les variables toutes en même temps, je vais les affecter une à une. Qu’est-ce que ça change ? Ça change que si j’ai un truc qui est trivialement idiot à faire, je peux éviter de le faire. Ce qui veut dire qu’il faut que j’explique ce que ça veut dire « trivialement idiot ». Supposons que j’aie une formule très simple qui soit juste (x_1 \vee x_2 \vee x_3). Si j’ai choisi pour x_1 la valeur 0 et pour x_2 la valeur 0, il est « trivialement idiot » de choisir 0 pour x_3 puisque je n’ai alors aucune chance de satisfaire la formule. Donc par « trivialement idiot », je veux dire qu’il y a une clause qu’il n’y a plus qu’une seule chance de satisfaire, c’est-à-dire qu’on a déjà affecté des valeurs à deux variables sur les trois de la clause, et que la clause n’est toujours pas satisfaite. Si j’utilise mon algorithme précédent, j’ai une probabilité 7/8 de trouver une affectation satisfaisante (parce qu’avec probabilité 1/8 je tombe sur 000 pour mes variables et ma formule n’est pas satisfaite). Si j’essaie d’éviter les trucs trivialement idiots… ben déroulons le truc. Je commence par x_1, il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. Je continue par x_2 ; là encore, il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. J’arrive à x_3, et là j’ai deux possibilités. Si x_1 et x_2 ont été mis tous les deux à 0, j’ai un truc trivialement idiot à éviter, c’est de mettre x_3 à 0, donc j’évite ça, je mets x_3 à 1, et ma formule est satisfaite. Si x_1 ou x_2 a été mis à 1, quoi que je fasse sur x_3 sera valide, donc je ne peux pas me tromper. Sur ce cas spécifique, rien qu’en évitant les trucs trivialement idiots, mon algorithme passe à une probabilité de succès de 1.

C’est pas toujours aussi idyllique, évidemment – là les choses se passent bien parce que j’ai une seule clause, beaucoup d’affectations valides, et qu’on est contents. Maintenant, un cas un peu plus sioux : considérons la formule

(x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee \bar x_3) \wedge (x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_2 \vee \bar x_3) \wedge (\bar x_1 \vee x_2 \vee x_3) \wedge (\bar x_1 \vee x_2 \vee \bar x_3)

Deux affectations satisfont cette formule : x_1 = 1, x_2 = 1, x_3 = 0  et x_1 = 1, x_2 = 1, x_3 = 1. Avec mon algorithme « simple », la probabilité de succès est de 2/8 = 1/4. Avec mon algorithme qui cherche à éviter les trucs « trivialement idiots »… aussi, dans certaines conditions. Si je commence par la variable x_1 et que je la mets à 0, je n’ai aucune chance d’obtenir une affectation satisfaisant la formule. Si je continue par la variable x_2 et que je la mets à 0, idem. Donc il faut que je mette x_1 et x_2 à 1 tous les deux, ce qui arrive avec une probabilité 1/4 ; x_3 peut être mis à n’importe quelle valeur, donc si on n’a pas fait d’erreur jusqu’ici on n’en fera pas non plus à la dernière étape. Dans ce cas, donc, la probabilité de succès avec ou sans la détection de trucs « trivialement idiots » est la même. Sauf que… si on traite les variables non pas dans cet ordre là mais, par exemple, dans l’ordre x_3 x_2 x_1… Pour la première variable, x_3, on ne peut pas faire d’erreur, quelle que soit la valeur d’affectation. Pour x_2, on ne peut pas détecter de truc trivialement idiot, donc on la met à la bonne valeur avec une probabilité 1/2. Mais si cela arrive, la clause (x_1 \vee \bar x_2 \vee \bar x_3) ou la clause (x_1 \vee \bar x_2 \vee x_3) (selon la valeur affectée à x_3) indiquera à l’algorithme que mettre x_1 à 0 est trivialement idiot, ce qu’il faut éviter. Avec cet ordre de variables, la probabilité de succès de notre algorithme amélioré passe à 1/2. Il y a donc de « bons » ordres de variables et de « mauvais » ordres de variables (on parle de permutations). Comme il est difficile de savoir avant de commencer si une permutation est bonne ou mauvaise (ou comment trouver une bonne permutation), on fait comme d’habitude : on prend une permutation au hasard et on espère qu’en moyenne ça marche bien.

C’est exactement ce que fait l’algorithme PPZ (nommé d’après ses trois auteurs, Ramamohan Paturi, Pavel Pudlák et Francis Zane, dans un papier intitulé Satisfiability Coding Lemma) :

  • On part d’une formule F sur n variables, et on commence avec une affectation vide (on n’affecte aucune valeur aux variables pour l’instant).
  • On choisit un ordre aléatoire pour les variables, et on les traite une par une dans cet ordre :
    • Pour la variable courante x_i, si x_i = 0 est trivialement idiot, on affecte 1 à x_i
    • Sinon, si x_i = 1 est trivialement idiot, on affecte 0 à x_i
    • Sinon, on affecte une valeur aléatoire à x_i
    • Et on passe à la variable suivante.
  • Si l’affectation qu’on trouve satisfait la formule, c’est terminé ! Sinon, on recommence au départ.

L’analyse de la probabilité de succès de l’algorithme est relativement simple. Sans rentrer dans les détails, l’idée c’est que si je n’ai pas le choix pour une variable (c’est-à-dire si la mettre à 0 ou à 1 fait que l’affectation ne peut pas être satisfaisante), alors j’ai au moins une clause qui rend ce choix trivialement idiot dans au moins une permutation sur trois (parce que dans un cas sur trois, la variable en question arrivera en dernier dans la clause en question). J’ai toujours des choix aléatoires pour certaines variables, donc l’algorithme peut toujours se vautrer lamentablement, mais la probabilité de ne pas se vautrer est meilleure que si on prend juste une affectation au hasard.

Après, le lecteur attentif se sera peut-être dit « ouiiii mais si j’assigne x_1 à 1, j’ai à la fois une clause (\bar x_1, x_2, x_3) et une clause (\bar x_1, x_2, \bar x_3), donc quelque part c’est AUSSI trivialement idiot de mettre x_2 à 0… ». Le lecteur attentif est un petit malin. Et c’est aussi, quelque part, ce que fait l’algorithme PPSZ (nommé d’après les trois auteurs précédents + Michael Saks, dans un papier intitulé An Improved Exponential-Time Algorithm for k-SAT) : plutôt que de regarder les clauses une à une pour voir si par hasard on peut éliminer un choix trivialement idiot, on en regarde beaucoup à la fois (typiquement \log \log n, où n est le nombre de variables de la formule) pour tenter d’en tirer les mêmes conclusions. il y a un nombre sous-exponentiel d’ensembles de \log \log n clauses, et examiner chacun d’entre eux peut se faire en temps sous-exponentiel aussi (on peut se contenter de regarder toutes les valeurs possible pour le sous-ensemble de variables qui interviennent dans ce sous-ensemble de clauses). Les mauvais choix ne peuvent plus nécessairement être qualifiés de « trivialement idiots » mais peut-être de « manifestement idiots » ; le résultat est le même : si on peut les détecter, autant les éviter. Pour le coup, l’analyse de la probabilité de succès de cet algorithme est (beaucoup) plus complexe ; pour la petite histoire, lorsque l’article original a été publié, les auteurs n’avaient établi la probabilité de succès que dans le cas où la formule n’avait qu’une seule affectation satisfaisante (l’analyse du cas général n’arrivait à prouver qu’une probabilité de succès plus basse). La preuve plus générale a été établie par Timon Hertli (3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General), mais il s’est passé plus de dix ans entre l’introduction de l’algorithme et la preuve en question. Une version « lisible » (pour une certaine définition de « lisible, admettons-le) de la preuve en question est disponible dans ma thèse de semestre (chapitre 2) – elle est difficile à résumer en moins de, mettons, 8 pages (heu, déjà 8 pages, c’est challenge, en fait.)

J’ai travaillé autour de ces algorithmes depuis un an et demi (pas complètement par hasard, Timon dont je parle précédemment étant doctorant à l’ETH… et mon superviseur sur tout ce que j’ai fait), et pour le coup c’est probablement LE sujet sur lequel je me sens prête à répondre à BEAUCOUP de questions 🙂

 

Deux mémoires

Publié le par BaliseLaisser un commentaire

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

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

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

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

« Et donc, tu fais quoi en ce moment ? » « De l’informatique théorique. Des maths, en gros. »

Publié le par Balise15 commentaires

Ça fait quelques jours que j’ai envie d’écrire des choses un peu plus consistantes que « oh j’ai lu ça, c’était cool ». Plus spécifiquement, il y a une question qu’on me pose relativement souvent : « Et donc, tu fais quoi en ce moment ? ». J’ai beaucoup de mal à y répondre – en général je réponds quelque chose du genre « de l’informatique théorique. Enfin des maths, en gros ». C’est pas très satisfaisant, mais rentrer dans les détails quand on me pose une question « sociale » n’est pas forcément une bonne idée non plus. Mais peut-être qu’il y a des gens qui seraient intéressés par un peu plus de détails, et d’une façon que je pourrais expliquer à quelqu’un qui ne baigne pas dans le domaine depuis un an et demi. Pour donner une idée, j’essaie de viser un niveau « j’ai pas fait de maths depuis le lycée ». Je sais pas trop si je vais y arriver, ça commence à faire un bout de temps que j’ai quitté le lycée, et j’ai fait des maths depuis 🙂

Je vais donc commencer par rédiger un billet très général (celui-ci) pour poser un peu quelques bases ; et après, j’ai la ferme intention de rentrer dans les détails un peu plus. L’idée, c’est que je trouve vachement cool ce que j’étudie en ce moment ; et j’aimerais bien expliquer pourquoi je trouve ça vachement cool. Ça va demander un peu de boulot ; j’hésite limite à faire un premier billet sur « mais, mais, mais… c’est QUOI, un logarithme ? », parce que quand même les logarithmes c’est super utile, mais j’ai peur de faire une insulte à la culture scientifique de mes lecteurs. Je crois que je vais le faire quand même, parce que ça m’amuse moi, et que c’est quand même la raison principale de faire des choses. Et après, je compte faire des billets plus ou moins selon l’humeur du moment. Probablement un peu de complexité, probablement des graphes (j’aime bien les graphes), probablement un peu de probabilités (haha), et les « prérequis » pour tout ça (je suis en train de réfléchir à ce qu’il me faut pour un billet expliquant P/NP, ce qu’est un problème NP-complet, et la grande question de savoir si P = NP, je ne suis pas la première à me frotter à ce genre de billet, mais je pense que l’exercice didactique est intéressant 🙂 )

Je digresse déjà, c’est pas gagné. Revenons à nos moutons. Je suis actuellement en master d’informatique, spécialisation informatique théorique, de l’ETH à Zürich. Les modalités « usuelles » sont de faire 60 crédits de cours, généralement en deux-trois semestres, suivis d’un semestre de projet de recherche (avec rapport et soutenance à la fin, classique). Il se trouve que j’ai pris des chemins un peu détournés pour mon master, et que de fait je vais rentrer dans mon 4e semestre de cours, mais c’est pas vraiment la question ici.

« Mais c’est quoi, l’informatique théorique ? » seriez-vous peut-être tentés de me demander. La première réponse qui me vient à l’esprit, c’est que c’est la théorie de tout ce qu’on peut faire avec un ordinateur. Au cœur de tout ça, il y a la notion d’algorithme. Un algorithme, c’est simplement une suite d’instructions. On peut par exemple penser à une recette de cuisine comme à un algorithme :

  1. Pour faire de la béchamel, il me faut du beurre, de la farine et du lait.
  2. Mesurer des quantités égales de beurre et de lait.
  3. Dans une casserole à feu moyen, faire fondre le beurre et y incorporer la farine jusqu’à obtenir une pâte épaisse.
  4. Tant que la béchamel n’a pas la consistance souhaitée, ajouter du lait et mélanger.
  5. Si on le souhaite, ajouter du sel, du poivre, de la muscade ou du fromage râpé.

On a une suite d’instructions (qui sont numérotées), qui peuvent être répétées (tant que la béchamel n’a pas la consistance souhaitée) ou qui ne sont exécutées que dans certaines conditions (on n’ajoute de la muscade que si on le souhaite).

De façon plus « classique », on peut aussi penser à l’algorithme de la division que tout le monde étudie à l’école primaire.

Je suis un peu biaisée sur les catégories de ce qu’on peut faire rentrer dans l’informatique théorique, parce qu’il y a des domaines que je connais bien mieux que d’autres, mais en voici une liste explicitement non exhaustive (si j’oublie votre domaine favori… c’est que je ne sais pas quoi en dire, n’hésitez pas à expliquer en commentaire). Pour une liste un peu plus complète, je vous renvoie sur l’article correspondant de la Wikipedia : Informatique théorique, qui reprend lui-même la liste de SIGACT (une grosse société savante du domaine, en gros). Quant au fait que « je fais des maths », l’informatique théorique est souvent considérée comme une branche des maths discrètes ; et en pratique, prouver qu’un truc marche implique de faire de jolies preuves pleines de jolies maths 🙂 (Ou de moches maths, mais c’est nettement moins satisfaisant.)

Je me permets un certain nombre d’approximations ici (en particulier je fais la confusion entre un problème et une instance d’un problème), j’essaie de faire simple sans faire de paragraphe à rallonges. Ceux qui savent de quoi je cause corrigeront d’eux-mêmes ; pour les autres : c’est une première approximation, qui n’est par définition pas exacte, mais que j’ai l’intention d’affiner dans les billets qui suivront.

  • L’algorithmique. Étant donné un problème, comment le résoudre avec un algorithme, comment prouver que la méthode de résolution (l’algorithme) qu’on propose est effectivement correcte, et combien de temps faut-il pour avoir un résultat ?
  • La théorie de la complexité. Ça inclut, mais pas seulement, le point « combien de temps il faut pour avoir un résultat » du point précédent. On s’intéresse aussi ici à la question : étant donné un problème, quel est le temps minimum et la consommation de mémoire minimum qu’il me faut pour le résoudre ?
  • La théorie des graphes. Un graphe est une structure mathématique composée de points (les « sommets » du graphe) et de traits (les « arcs » du graphe). Un exemple de graphe pourrait être la carte d’un réseau de métro : les stations sont les sommets, les arcs sont les connexions d’une station à une autre par une ligne de métro. En théorie des graphes, on s’intéresse aux propriétés de ces graphes (par exemple : est-ce que je peux aller d’un point à un autre ; quel est le plus court chemin d’un point à un autre ; si je supprime ce sommet là (ou, dans l’analogie précédente, si je ferme ma station de métro), est-ce que je peux toujours aller de mon point A à mon point B), et aux algorithmes pour décider ces propriétés (comment je fais pour déterminer quel est le plus court chemin d’un point à un autre du graphe).
  • Les structures de données. Comment stocker les données du problème qu’on cherche à résoudre, de la façon la plus efficace possible (en temps et en mémoire) pour le problème en question ? Ou, pour reprendre mon exemple précédent, comment stocker la carte du réseau de métro pour faire des calculs dessus ?
  • La géométrie algorithmique. Comment représenter et résoudre avec un ordinateur des problèmes qui touchent à la géométrie ? Un exemple typique est celui du « bureau de poste » : étant donné l’emplacement de tous les bureaux de poste d’une ville, comment déterminer efficacement celui qui est le plus proche de ma maison ? Si je ne cherche que celui qui est le plus proche de ma maison, je peux calculer la distance entre ma maison et tous les bureaux de poste ; mais comment faire ça plus efficacement si je cherche à définir, pour toutes les maisons de la ville, le bureau de poste le plus proche ? Et qu’est-ce que je fais si je veux ajouter/supprimer un bureau de poste ?
  • L’impact de l’aléatoire dans tout ça – pour certains algorithmes, il est intéressant d’ajouter une part de hasard dans les calculs (je lance une pièce, si elle fait pile mon algorithme fait ceci, si elle fait face mon algorithme fait cela). Quel impact ça a sur les algorithmes – en particulier sur le fait qu’ils renvoient le résultat correct ou non, et comment évaluer le temps nécessaire à résoudre (correctement) un problème avec un algorithme aléatoire ? L’étude de certaines structures aléatoires a aussi un intérêt en soi. On peut par exemple définir des graphes aléatoires : on prend un ensemble de points, et on ajoute un arc entre deux points selon une certaine probabilité. Selon la manière dont on définit un graphe aléatoire, il peut s’avérer un assez bon modèle d’un graphe de réseau social (qui est ami avec qui)… ou du cerveau humain.
  • La cryptographie. Si Alice veut envoyer un message à Bob en étant sûre qu’Ève ne puisse pas le lire, et si Bob veut être sûr que le message qu’il vient de recevoir provient bien d’Alice, comment faire ? Et surtout, comment prouver qu’effectivement Ève ne peut pas lire le message, et que Bob peut être sûr de la provenance du message ?
  • [EDIT] La calculabilité, comme on me le signale en commentaire. Il se trouve qu’on ne peut pas tout résoudre avec un algorithme, et qu’on peut même prouver que certaines choses ne peuvent pas être être calculées avec un algorithme. L’exemple le plus célèbre est celui du « problème de l’arrêt », c’est un peu méta, mais j’espère que vous me le pardonnerez. On peut prouver qu’il n’existe pas de programme qui décide si un programme donné finit par s’arrêter et à renvoyer un résultat. La preuve est jolie, même si elle fait un peu mal au crâne la première fois qu’on y est confronté ; j’en ferai peut-être un prochain billet 🙂

Voilà, tout ça, c’est des trucs dans lesquels j’ai au moins des notions de base. L’informatique théorique regroupe encore pas mal de choses dans lesquelles mon niveau de connaissance est à peu près nul : la théorie de l’information (à ma grande honte), l’apprentissage automatique (ou comment réussir à faire reconnaître des photos de chat à un ordinateur), les méthodes formelles (ou comment réussir à prouver que mon programme n’a pas de bug), l’informatique quantique (sait-elle mieux reconnaître une photo de chat que l’informatique classique), la bio-informatique (comment déterminer si deux séquences ADN sont proches ou non) et j’en oublie encore probablement un peu.

Notons accessoirement que faire rentrer ceci ou cela dans le domaine de l’informatique théorique peut toujours prêter à débat. Je ne suis par exemple pas convaincue de la présence de l’apprentissage automatique dans l’informatique théorique, parce que ça me paraît encore très expérimental (on a modifié ce paramètre là et par conséquent l’ordinateur reconnaît 2.2% de plus de chats). La Wikipedia parle d’informatique distribuée et concurrente (l’art d’utiliser plusieurs ordinateurs à la fois pour exécuter des programmes) comme faisant partie de l’informatique théorique. Je suis d’accord que l’intersection n’est pas nulle – mais je ne considérerais pas l’informatique distribuée comme un sous-ensemble de l’informatique théorique. Idem pour la bio-informatique ; certains éléments en font partie (l’exemple des chaînes ADN par exemple), mais je ne suis pas sûre que tous les bio-informaticiens se définissent comme des informaticiens théoriques 🙂

Je pensais que ce billet serait relativement court ; je crois que c’est un échec cuisant de ce point de vue. J’espère qu’il était cependant vaguement intéressant ; et s’il y a des choses que vous pensez que je peux traiter dans un futur billet de cette catégorie… ben n’hésitez pas 🙂

TOEFL, résultat des courses

Publié le par Balise3 commentaires

(Je résiste lourdement à la tentation d’intituler ce billet « Bref, j’ai passé le TOEFL ».)

J’ai passé le TOEFL le 23 juin, et j’ai reçu un mail le 29 juin pour m’indiquer que mes résultats étaient disponibles. Sans trop de surprise (mais avec un soulagement non dissimulé), j’ai eu largement assez de points pour mon inscription en master.

J’avais dit que je ferais une mise à jour de mon billet précédent Préparation au TOEFL à propos des conditions précises de l’examen – je crois qu’il est temps 😉 Je ne peux pas, contractuellement (m’ont fait recopier 4 lignes à la main et signer pour être sûrs que je comprenne), donner les détails spécifiques au contenu de l’épreuve que j’ai passée, mais je peux donner quelques détails supplémentaires sur le déroulement lui-même.

Les quatre parties sont bien telles que je les ai décrites; il peut visiblement arriver que la partie compréhension orale joue 9 bandes audio et pas 6 (croyez-moi : c’est CHIANT). À noter aussi que la partie compréhension écrite permet de revenir sur ses réponses et de faire une relecture rapide, ce n’est PAS le cas de la partie compréhension orale (une réponse validée est une réponse validée, point).

J’avais un peu peur que l’examen soit prévu de sorte que « ok, tout le monde commence à 10h, tout le monde passe à la partie 2 à 11h, tout le monde passe à la partie 3 à midi 10 et tout le monde passe à la partie 4 à 13h » mais non – une fois le test lancé, on peut bosser à son rythme (dans les limites prévues par l’exam évidemment). L’avantage, c’est que j’ai pu sortir tôt et sans temps mort (parce que le temps mort sans avoir droit à un bouquin, bof quoi). L’inconvénient, c’est que les parties sont ordonnées comme suit : compréhension écrite, compréhension orale, expression orale, expression écrite. Du coup, quand on va un poil plus vite que le reste de la salle, on se retrouve à composer pendant que le reste de la salle est en train de marmonner dans un micro, c’est un peu pénible. Le bruit furieux des claviers quand tout le monde est en train de composer est assez marrant par contre 🙂

Niveau préparation de l’examen, j’avais potassé sur The Official Guide to the TOEFL Test, qui est le machin édité par l’ETS (la boîte qui fait passer le TOEFL) – une nouvelle édition est prévue en octobre. Il permet de voir ce à quoi ressemblent les questions, et le CD fourni (dans cette édition) permet de lire les pistes audio sans avoir à lancer l’interface Windows 😉

Comme prévu, j’ai fait un bon score partout, et j’ai surtout perdu des points sur la partie d’expression orale (bon, j’ai suffisamment fait la maline sur les réseaux sociaux avec mon score pour pas le répéter ici 😉 ). Pour moi c’est LA partie qui nécessite vraiment de l’entraînement et pour laquelle l’entraînement fait la différence, à niveau d’anglais égal. Le reste, savoir à quoi ressemble l’épreuve et être raisonnablement attentive/prudente pendant l’épreuve m’a suffi (YMMV).

Voilà, un petit retour d’expérience, pas forcément très utile à mon lectorat habituel, mais sait-on jamais !

Préparation au TOEFL

Publié le par BaliseLaisser un commentaire

Note : ce billet a été écrit AVANT mon passage du TOEFL et a pour base le matériau de préparation que j’ai sous la main. J’essaierai de le mettre à jour ou de faire un billet sur les conditions précises de l’examen… quand je l’aurai passé 🙂

Mise à jour : j’ai publié un deuxième billet intitulé « TOEFL, résultat des courses » avec les impressions post-examen.

J’ai appris avec une joie non dissimulée (ahem) qu’il fallait que je passe un examen d’anglais (on me laisse le choix entre l’IELTS, le TOEFL et le CAE) pour attester d’un niveau C1 d’ici au 18 septembre, début des cours de master à l’ETH.

J’ai déjà passé l’IELTS il y a 10 ans et c’était chiant. Il n’est plus valide parce que ces machins sont valides que deux ans – c’est une rente… Je PEUX comprendre la justification de refaire certifier « régulièrement » si nécessaire. Évidemment, le niveau en langues évolue avec le temps. Mais bon, par exemple, à titre personnel, j’ai beaucoup plus l’occasion de pratiquer mon anglais que, disons, ma conduite automobile. Mon permis de conduire est valable à vie, ma certif d’anglais non. Et pourtant… je risque nettement moins, disons, de tuer quelqu’un avec mon niveau d’anglais. Je crois que je garde mon argument précédent : c’est une rente 🙂

Bref, plutôt par défaut qu’autre chose, je me suis inscrite au TOEFL pour dans deux semaines (et demie). Du coup, je potasse l’examen ; je SAIS que j’ai un niveau d’anglais suffisant pour justifier un C1, mais encore faut il arriver à le faire certifier sur un test qui a ses propres aléas. Et il me faut 100 points sur 120, ce qui est plutôt élevé.

Le TOEFL, de nos jours, est surtout passé dans sa version dite « iBT » (Internet Based Test) – qu’il faut quand même aller passer dans un centre d’examen évidemment – est noté sur 120 points, 30 points par section : compréhension écrite, compréhension orale, expression écrite, expression orale. Donc, en moyenne, il faut que je fasse 25 points sur 30 dans les quatre catégories.

Compréhension écrite

3 à 4 textes d’environ 700 mots à lire, et 36 à 56 questions auxquelles répondre. Les textes sont de type « académique » dans divers domaines qui vont de l’histoire de l’art à la biologie. Après avoir jeté un œil à quelques examens type, je sais qu’il va falloir que je fasse très attention là : les questions sont souvent ambiguës, parfois carrément traîtres. Par contre, la bonne nouvelle, c’est que je viens de voir qu’il y avait plus de questions que de points ; je pensais avoir « droit » à 5 erreurs sur 30 questions pour valider le 25, mais en fait j’ai « droit » à plus d’erreurs que ça. (Plus de questions où se bananer aussi, évidemment, mais j’estime que le nombre de bananages est raisonnablement constant, donc j’augmente ma note si le nombre de questions augmente. Quoi, ça marche pas comme ça ?)

Compréhension orale

De ce que j’ai vu, 6 bandes audio qui varient du « j’ai peur de pas avoir assez de sous pour aller à l’université, qu’est-ce que je peux faire ? » à l’extrait de cours sur n’importe quel sujet académique, et en tout 34 à 51 questions (donc, pareil que pour la compréhension écrite, c’est mis à l’échelle).

De manière générale, J’AIME PAS les tests de compréhension orale. Déjà parce que, de mon point de vue, ils tiennent plus de tests de mémoire/prise de note du bon détail au bon moment que de tests de… ben de compréhension orale, quoi. C’est évidemment particulièrement le cas si les questions ne sont pas données avant la lecture de la bande audio, ce qui est le cas pour le TOEFL.

Et là, mon problème, c’est que je suis pas très douée en prise de notes. Enfin, plus spécifiquement, je suis pas très douée en prise de notes sur un support oral uniquement. S’il y a des slides, un tableau, bref, des trucs comme il y a dans la vraie vie dans la majeure partie des cours et des conférences, ça va plutôt mieux, mais support oral uniquement, j’ai du mal à ne pas perdre le fil. Là où c’est « drôle », c’est qu’en pratique, la seule situation où je me retrouve dans ce genre de cas de « prise de notes à l’oral uniquement », c’est… les tests de compréhension orale en langues. C’est probablement pour ça que je déteste l’exercice qui me paraît probablement le plus artificiel et pénible. Et peut-être le plus aléatoire, aussi. Ce qui est con, parce que j’ai vraiment aucun problème sur le contenu des bandes audio en général.

Expression orale

6 questions, auxquelles il faut répondre en 45 à 60 secondes selon la question. Deux types de questions : deux questions « bateau », heu, pardon, « independent questions » et quatre questions « integrated » : deux « listening/reading/speaking » et deux « listening/speaking ».

La première question demande une description d’un truc « personnel » (thème allant des vacances idéales au prof préféré).
La deuxième propose deux alternatives sur une situation donnée et demande une réponse argumentée sur ce qu’on préfère (« je m’en fous » n’étant probablement pas une réponse valide).
La troisième affiche un petit texte et fait écouter une conversation ; de manière générale le thème tourne autour des réglements ou procédures universitaires, et il faut résumer la position d’une des personnes qui cause et les raisons pour lesquelles la personne en question a l’opinion en question.
La quatrième question porte sur un sujet académique et, là encore, ya un petit texte suivi d’une bande audio, et une question derrière (« expliquez pourquoi, au vu du texte, ce que le prof raconte semble avoir un sens »).
La question 5 passe une bande audio de gens qui causent d’un souci universitaire quelconque, proposent deux solutions, et la tâche est de décrire la situation et d’expliquer ce qui nous paraît la meilleure solution.
La sixième question joue d’abord un extrait de cours dans un domaine quelconque et pose ensuite une question sur le contenu de l’extrait en question (donner les points majeurs, résumer, ce genre de choses).

De manière générale, c’est probablement sur cette partie (la partie orale dans son ensemble) qu’il faut que je bosse le plus : m’entraîner à avoir une opinion sur les trucs dont je me fous 😉 (heu, ça, ça fait 30 ans, c’est pas gagné…), avoir une idée de ce que j’ai le temps de dire en 45 et en 60 secondes, éventuellement préparer quelques trucs pour les sujets « bateau ».

Expression écrite

2 textes à rédiger : une « integrated task » et une « independent writing task ».

L’integrated présente un texte académique, un bout de cours oral, et demande de faire la relation entre les deux, éventuellement de contrer l’un avec l’autre.
L’independent est un « Est-ce que vous êtes d’accord avec l’énoncé suivant », ce à quoi bien évidemment ma première réponse instinctive est « Bin, ça dépend… » et/ou « Oui enfin c’est ptêt un peu plus subtil que ça… » – bref, il va peut-être falloir que je m’entraîne un peu sur des sujets blancs là aussi 🙂 20 minutes pour la première question, 30 pour la deuxième question, et ils attendent apparemment de l’ordre de 300 mots par réponse.

Ça me fait plutôt moins peur que la partie orale, parce qu’au moins il y a le temps de penser, de corriger et de rectifier, c’est pas du « one shot », c’est plus confortable en ce qui me concerne. Ça reste relativement court pour pondre 300 mots, mais ça devrait tout de même aller.

Et le pire de tout sur ce truc là, c’est qu’il faut passer l’expression écrite sur un clavier QWERTY. Et que donc… ben va falloir que je me remette au QWERTY. Et à regarder mon clavier et pas mon écran. Et ça, ÇA, ça fait vraiment chier.

Mon formulaire d’examen

Publié le par Balise3 commentaires

Puisqu’il suffit visiblement d’écrire pour avoir des choses à écrire, je viens de mettre en ligne la version courante de mon « formulaire d’examen » – le truc qui me sert de « doudou » et de référence rapide pour les trucs que je suis susceptible d’utiliser et d’avoir oubliés (parce que j’ai pas de mémoire ou parce que je panique). C’est évidemment relativement personnel, et je pense être la seule personne au monde à mettre une table de multiplication sur ce genre de trucs, mais, bon, je trouve ça rigolo de manière générale de voir ce genre de choses, donc peut-être que ça peut en amuser d’autres.

Le machin est là : formulaire d’examens, en anglais et en maths dans le texte 🙂

(Pour la petite histoire sur les tables de mult’, je me souviens avoir eu beaucoup de mal à les apprendre. J’ai aussi comme souvenir, mais c’est peut-être du souvenir regénéré a posteriori, d’avoir codé un machin en Basic pour m’interroger sur mes tables de mult’ :P)

Bon, et peut-être plus utile, mon collègue Haffi vient de me signaler une Theoretical Computer Science Cheat Sheet, qui est un peu très amour, en fait. Voilà, pour la complétude de la chose 🙂