mercredi 3 décembre 2014

AB testing par la pratique


Je vous ai déjà parlé de test AB sur ce  blog, je vais m'essayer à l'exercice sur cet article.
Cela veux dire que tous les internautes visitant cette page ne verront pas la même chose, même s'ils saisissent la même adresse ou suivent le même lien! Cela se fait grâce à l'outil "AB tasty", sans aucune installation, et ça marche sur n'importe quelle site.

Il y a en fait deux versions différentes de cette même page. Vous êtes entrain de voir une des deux versions. Pour vous en rendre compte rechargez cette page (éventuellement plusieurs fois) et vous constaterez qu'il y a une différence...

La variation porte ici sur la photo, soit une femme brune avec une veste noire , soit une femme blonde avec une robe rouge. Les modifications peuvent être de tout type : le texte, l'image, la mise en page, etc...

En pratique, sur un test réel, chaque visiteur ne peut voir qu'une seule version, pour ne pas fausser les résultats, et pour ne pas déstabiliser le visiteur. Ici nous avons désactivé cette fonctionnalité pour que vous puissiez voir les deux versions. L'objectif de cet opération est de mesurer objectivement la performance des deux versions de page. Par performance on entend une mesure de la réussite d'un objectif, par exemple le fait de cliquer sur un lien de cette page ou simplement de rester sur ce blog.

Cette pratique est généralement utilisée par les sites de e-commerce, mais pas seulement. Leur mesure objective de performance est assez directement lié à la vente (ajout de produits au panier par exemple).

À l'issue de la période de test, on garde bien sur la version qui a la meilleur performance, on a ainsi optimisé son site web.


jeudi 20 novembre 2014

C'est quoi le "AB testing" ?

Ayant changé de travail depuis peu, je découvre un nouvel univers, celui du web marchand. En particulier ce qu'on appelle l'"optimisation web",et plus spécifiquement le "test AB" (ou "AB testing" pour les anglophiles).

L'idée du "test AB" est simple, comme beaucoup de donnes idées. Il s'agit tester différentes versions d'une même page web, et de mesurer objectivement, sa performance. Par performance on entend, par exemple, amener un maximum de visiteurs à la page d'achat, ou bien garder le visiteur le plus longtemps possible sur le site. Pour cela, une partie des visiteurs verra une version modifiée du site.

Les différences  de version d'une page peuvent être de toutes natures, changer le texte, les images, la mise en page, les couleurs, etc... Cela peut paraître anodin mais ça ne l'est pas. Le comportement des visiteurs peuvent être très différents en fonction de ces paramètres. Voyez l'exemple d'Etam qui améliore de 10% l'accès de ses visiteurs à la page produit.


Impossible de dire laquelle de ces deux pages est la plus "vendeuse".

Le seul moyen de le savoir c'est de les tester.


Un outil de test AB, comme AB tasty, permet , par l'insertion d'un simple tag (un bout de code HTML/javascript), de modifier une page existante pour en proposer plusieurs versions. Le tag s'occupe aussi de diviser le trafic du site pour les diriger vers les différentes versions de pages.

Il permet aussi d'analyser les différences de comportement des visiteurs pour identifier quelle version est la plus efficace.

Ce qui est intéressant dans cette approche c'est que les résultats, pourtant objectifs, sont parfois contre-intuitif. Cela veux dire que sans ce type d'outils, on peut facilement passer à coté la bonne solution, tout en pensant bien faire.

Si le sujet vous intéresse vous trouverez d'autres exemples d'utilisation des "tests AB" sur le blog d'AB tasty, et un "livre blanc" vous permettant de comprendre plus en profondeur comment optimiser un site web. Ce service possède aussi un tas d'autres outils grâce à un système de plugins qui permettent de réagir aux actions d'un visiteur sur votre site, comme identifier si un visiteur arrive en bas d'une page (on suppose alors qu'il a vraiment lu le contenu de la page) ou identifier si le visiteur utilise "adblock" (un système qui bloque l'affichage de publicité), etc...

Il s'agit aussi d'un travail très intéressant d'analyse de donnés visant à aider les sites marchand à mieux connaître leurs clients.


vendredi 17 octobre 2014

This is the end ...

C'est la fin de 10 ans d'enseignement et de recherche à l'ESIEA... mais c'est aussi un nouveau début.

Merci à tous et toutes, j'ai appris tant de choses, y compris de la part des étudiants.

Chers étudiants je vous dis au revoir, bon courage et bonne chance. Je sais que vous allez "assurer" ;) .

Cher lecteurs je vous dit à bientôt, ce blog continue d'exister, et je continuerai de l'alimenter avec les sujets qui me passionnent (algorithmique, machine learning, traitement du langage, traitement du signal, complexités etc..) comme je le faisais avant.

Vous pouvez aussi me suivre sur Twitter :       sur LinkedIN ou google+ (voir à  droite de cette page.).

La suite professionnelle c'est chez A/B tasty, et j'ai hâte de découvrir de nouveaux challenges.

jeudi 9 octobre 2014

Dernier cours de mise à niveau

Débugger mémoire


Aujourd'hui, pour notre dernier cours, je vais vous montrer pourquoi et comment utiliser un debugger mémoire. Nous utiliserons valgrind.

Pourquoi ?

Le comportement d'un programme qui fait des erreurs mémoire est imprévisible, il est donc très très difficile à débugger. Principalement parce que les erreurs ne seront visible que rarement, et que le message d'erreur sera uniquement "segmentation fault" (sous entendu "erreur de segment mémoire") avec un arrêt prématuré de l'exécution du programme. Tout cela ne vous aidera pas trouver le problème et encore moins à le corriger...
Si vous voulez produire un programme sûr et fiable, vous devez utilisez un debugger mémoire qui surveillera l'utilisation de la mémoire pour identifier les erreurs dès la première exécution du programme.

Comment ?

Valgrind va surveiller l'utilisation de la mémoire faite par votre programme lors de son exécution (ce que ne fait pas le compilateur!).

Pour cela nous allons d'abord devoir ajouter une option lors de la compilation, l'option -g :

       gcc monCode.c -o monExecutable -g

Ceci aura pour effet de garder l'information des numéros de ligne du code source dans l'exécutable.
Ensuite pour l'exécution du programme nous allons préfixer son appel par la commande valgrind :

       valgrind ./monExecutable
     
Le programme se déroule alors exactement comme normalement, sauf que toute utilisation de la mémoire sera pistée, et en cas d'erreur, un rapport sera fait dans le terminal. Ce qui fait que le programme s'exécutera un peu plus lentement. En cas d'erreur, valgrind sera capable de retrouver les numéros de ligne du code source correspondant aux instruction qui posent problème.
Voyez le texte sur cette page : http://valgrind.org/docs/manual/quick-start.html#quick-start.intro
pour comprendre comment interpréter ce rapport.

L'interprétation de ces message n'est pas chose simple au départ, il faut un peu d'exercice.
Je vous propose donc de faire un petit programme dans lequel vous ferez successivement les différents type d'erreurs mémoire que peut détecter valgrind.
À chaque fois vous compilerez le programme, vous constatez que la nature de l'analyse statique faite par le compilateur est incapable de déceler les erreurs. Puis vous l'exécuterez avec valgrind, et vous chercherez à faire le lien entre le rapport produit par valgrind et l'erreur que vous connaissez (puisque vous l'avez faites exprès.). Voici les différents cas  à tester :
  • Utilisation d'une zone mémoire non-initialisée. Faites un malloc puis affichez le contenu de la zone mémoire en question (sans jamais y avoir mi quelque chose au préalable).
  • Lecture d'une zone mémoire non allouée : utilisez un pointeur jamais alloué et affichez son contenu.
  • Même chose que la question précédente mais en écriture. 
  • Dépassement de tableau : allouez un tableau avec malloc, puis utilisez une case qui est au delà de la zone allouée. Exemple créez un tableau de 10 cases et écrivez dans la case No 12.
    Note : valgrind ne surveille pas les allocations statiques (avec les []), encore une raison supplémentaire pour ne plus les utiliser,et faire des malloc.
  • Mettez l'une des erreurs précédentes dans une boucle. Vous constaterez le coté dynamique de l'analyse proposée par valgrind.
  • Après avoir corrigé l'erreur de la question précédente, essayez de voir où est spécifié dans le rapport que vous n'avez pas fait la désallocation du tableau. (Si vous aviez mis un free, je vous félicite ;) , mais , pour l'expérience, enlevez le.). Cela s'appelle une fuite mémoire, si votre programme en fait trop il peut sérieusement ralentir la machine sur laquelle il tourne. (souvenez vous de l'expérience faites lors d'un cours précédent où nous avions occupé toute la mémoire d'un ordinateur...)

Mise en pratique en situation réelle

Voilà maintenant vous êtes en capacité de tenter un vrai débuggage avec valgrind. Prenez votre programme de jeu de pendu. Je vous rappelle que vous deviez l'avoir finalisé et avoir replacé toutes les allocations [] par des malloc (si ce n'est pas fait il très est urgent de le faire). Testez le avec valgrind, il est assez vraisemblable qu'il y ait des erreurs même si votre programme n'a jamais planté...  Débuggez le !
Pensez aussi à vérifier que vous désallouez bien la mémoire en fin de programme.

Si votre programme ne comporte aucune erreur ni aucune fuite mémoire, demandez à ce qu'un de vos camarades vous passez le sien (comportant des erreurs) et débuggez le.

Il est très important que vous vous soyez entraîné à utiliser cet outil dans un contexte simple, avant de vous retrouver dans la situation de devoir débugger un programme complexe.

Conclusion

Nous n'avons pas pu tout voir dans ce cours de mise à niveau, mais nous aurons vu quelques bases qui vous permettrons d'aborder la suite du programme d'informatique.

Voilà j'espère que vous avez apprécié ces cours. Je vous souhaite bon courage pour la suite.

mercredi 1 octobre 2014

Mise à niveau informatique : cours 5

Preambule

Il nous resterait encore bien des choses à voir ensemble mais on arrive à la fin de cette série de cours. À partir de maintenant nous allons à l'essentiel dans le contexte du projet sur lequel vous allez être noté (LAB3040). Le reste des points théoriques vu en deuxième année seront à travailler en autonomie à partir des support de cours du semestre 1 (que nous avons déjà pas mal utilisé) et semestre 2 (qui est totalement nouveau pour vous!).

Pour ce projet vous aurez besoin de savoir gérer des matrices et lire le contenu d'un fichier, c'est ce que nous allons voir aujourd'hui (mardi 7 octobre).

Les matrices

Les matrices, ou plus généralement les tableaux multidimensionnels, sont une extension de la notion de tableau. Nous allons voir  dans le support de cour du semestre 1 comment les allouer, les utiliser et les désallouer.
Pour vous entraîner faites un (nouveau) programme qui :
  • allouez un tableau à 2 dimensions (10x10 cases) contenant des nombres entiers. (via la fonction malloc bien sûr.)
  • initialisez son contenu, chaque case [i][j] devra contenir la somme i+j. C'est juste histoire d'avoir un contenu pour vérifier que tout marche bien. En partique, dans votre TP par exemple vous y stockerez des informations relative à votre labyrinthe.
  • affichez son contenu
  • désallouez cette matrice

Les fichiers

Vous ne trouverez pas d'information sur les fichiers dans les deux support de cours car ce sujet est vu en TP. Nous allons donc le voir ensemble aujourd'hui.

La première chose à comprendre sur les fichiers c'est qu'il y a 3 étapes principales lors de l'utilisation d'un fichier, un peu comme pour l'utilisation de la mémoire.
  • l'ouverture (c'est l'équivalent de l'allocation pour la mémoire). Cela se fait via l'instruction fopen. Tapez "man fopen" dans un terminal, et voyons cela ensemble.
  • l'utilisation, c'est à dire lire ou écrire dans le fichier
    • en mode texte : fprintf et fscanf
    • en mode binaire : fwrite et fread
  • la fermeture (c'est l'équivalent de la désallocation pour la mémoire), grâce à l'instruction fclose.
Notez que tout programme dispose de deux pointeurs de fichier , sans avoir ni à les déclarer ni à les ouvrir : stdin et stdout. Il s'agit des entrées et sorties standard du programme. Par défaut l'entrée standard d'un programme est le clavier , et la sortie standard est l'affichage dans le terminal.

Ces entrées/sorties peuvent être redirigés vers des fichiers lors de l'exécution du programme.
Par exemple : ./monProgramme < mesDonnes.txt > monResultat.txt
Dans ce cas les appels à scanf lirons les données dans le fichier mesDonnes.txt (au lieu de les attendre sur le clavier), et les appels à printf écriront les données dans le fichier monResultat.txt (au lieu de les afficher dans le terminal).

Mettons cela en pratique :
  • Modifiez votre programme de création de matrice de manière à ce qu'il écrive la matrice dans un fichier au lieu de l'afficher dans le terminal. Pour cela utilisez la fonction fprintf. Regardez le fichier crée.
  • Maintenant modifiez votre programme de manière à enregistrer les données non plus en mode texte mais en binaire via l'instruction fwrite (au lieu de fprintf).  Regardez le fichier crée, pourquoi ne pouvez vous pas le lire?
  • Faites maintenant un autre programme qui ira lire (avec fread) le fichier binaire crée à la question précédente. Faites un affichage des valeurs pour vous assurer que tout fonctionne.
Le prochain cours le 14 octobre , sera notre dernier cours de mise à niveau!
(et accessoirement aussi mon derniers cours à l'ESIEA ! après 10 ans de bons et loyaux services.)

Nous apprendrons à utiliser un debugger mémoire : valgrind. Cet outil est installé sur les machines de TP (et je vous conseille fortement de l'installer sur votre machine). Nous testerons alors tous les programmes que vous aurez écrit jusqu'ici. Vous comprendrez alors qu'il est illusoire de croire qu'on peut écrire un programme sans erreur, si on utilise pas un tel outil... 

jeudi 25 septembre 2014

Mise à niveau informatique : cours 4

Après les listes chaînées, les arbres...

Préambules : complexité & récursivité

Complexité

Nous allons d'abord voir un concept très important : la notion de complexité algorithmique.
Cela est expliqué dans le support de cours de 2A, pages 25 à 31.

Après avoir constaté l'intérêt des listes, on va aussi constater certaines de leur faiblesses, en particulier la complexité algorithmique d'accès aux éléments...

Récursivité

Il nous faudra aussi comprendre le principe de la programmation récursive car les structures de données d'arbres y font constamment référence. Cela est expliqué dans le support de cours de 2A, pages 32 à 33.

Les Arbres

Nous allons voir un type d'arbre (il y en a des tas d'autres) qui permet de contourner le problème de complexité d'accès au élément d'un liste tout en ayant les même propriété de souplesse.
Il s'agit des Arbre Binaire de Recherche (ou ABR) cela est expliqué dans le support de cours de 2A, pages 45 à 49.

Comme pour les listes, pour des raison de manque de temps, nous allons faire le strict minimum :
  • Définir un type permettant de stocker un noeud d'arbre binaire de recherche
  • Écrire la fonction d'insertion (en suivant la logique ABR), et l'utiliser dans le main.
  • Écrire la fonction de recherche d'un élément. La tester en l'appelant dans le main.
  • Écrire la fonction qui permet d'afficher tous les éléments de l'ABR. Réflechissez aux 3 versions différentes de parcours qu'on peut écrire, testez les pour voir leur différence.
  • Écrire la fonction de désallocation. Pour cela identifiez qu'un des ordres de parcours vu à la question précédente offre précisément l'ordre idéal. Rappel : dans les structures chaînées il faut absolument éviter de supprimer un élément dont on a besoin pour supprimer les éléments suivants.

Travail personnel

Il me parait peu vraisemblable qu'on arrive à faire tout cela en une séance. Vous finirez donc chez vous, je répondrai à vos questions la semaine suivante.

jeudi 18 septembre 2014

Mise à niveau informatique : cours 3

Résumé

Dans les cours précédent nous avons vu les bases de l'algorithmique :

  • les instructions
  • les structures de contrôle
  • les variables simples et les tableaux
On a mis cela en pratique avec la réalisation un "jeu de pendu" en langage C.
Ensuite on a vu le mode de gestion "manuel" de la mémoire avec les fonctions malloc et free.

En travail personnel vous deviez modifier votre jeu de pendu pour qu'il fasse de la gestion "manuelle" de la mémoire, et qu'il utilise des fonctions. C'est la première chose que je vérifierai mardi 23 au matin!

ATTENTION : Si ne serait-ce qu'un seul des concepts que je viens de citer ne vous est pas familier, vous ne pourrez pas comprendre la suite!Il est donc important que vous fassiez le travail demandé avant de passer à la suite du cours.

1er cours sur les structures de donnés

Les listes chaînées

Vous avez déjà identifié que les tableaux sont des structures de données simples et pratique, mais pas très efficace. En particulier parce qu'on ne peut pas "retailler" un tableau, or bien souvent on ne connait pas à l'avance la quantité de données qu'on aura à stocker. Nous allons voir dans ce support de cours de 2A, comment on peut trouver une solution élégante à ce problème : les listes chaînées.  Nous regarderons spécifiquement les pages : 16 à 24.

Une fois le principe compris, nous allons le mettre en oeuvre dans un programme qui gérera une liste contenant des nombres entiers. Comme il s'agit d'un programme assez complexe pour des débutants, je vous demande de biens suivre ces étapes. Vous testerez chaque étape avant de passer à la suivante, pour ne pas vous "perdre en route" :
  • Créez un programme vide.
  • Créez la structure (struct) pouvant représenter une "cellule" (juste la définition du type)
  • Créez une fonction d'insertion (insertion en début de liste, c'est la plus simple), que vous appellerez dans le main.
    Vous devez absolument avoir une exécution sans erreur de votre programme avant de passer à la suite.
  • Créez une fonction d'affichage, appelez la sur la liste constitué au point précédent.
  • Ajoutez plusieurs éléments à votre liste et re-testez le tout. Que percevez vous sur l'ordre d'affichage des éléments ? Est-ce normal ? pourquoi ?
  • Écrivez une fonction de désallocation, appellez là (au bon endroit) dans le main.
Pour les plus rapides d'entre vous, vous pouvez essayer d'écrire (et utiliser) la fonction d'insertion en fin de liste.

Travail personnel : pour la prochaine fois vous devrez avoir finaliser le travail sur les listes chaînées. Je vous conseille de faire des fiches qui résument tous les concepts vus jusqu'à présent, car on verra de nouveaux concepts de plus en plus complexe et qui seront basé sur les précédents...





mardi 9 septembre 2014

Mise à niveau informatique (module INF3036) (cours 2)

Fin du jeu de pendu 


Le prochain cours à lieu le 16 septembre. D'ici là vous devrez essayer de finaliser le jeu de pendu par vous même.

Je ne passerai qu'une 1/2 h pour répondre à vos question et présenter le dernier point qui est  "comment déterminer la fin de la partie?".

Maintenant qu'on a revu , par la pratique les éléments de base de la programmation (structure d'un programme, structures de contrôles variables simples et tableaux), nous allons passer au programme de deuxième année.

La leçon d'aujourd'hui portera sur ...

L'allocation mémoire

Pour comprendre la manière dont la mémoire est gérée par l'ordinateur (et en particulier dans un programme en langage C), nous allons faire une série "d'expériences", à l'issue desquelles je vous donnerai des informations permettant d'expliquer les comportements observés.

Expérience 0

Écrivez un programme qui alloue un tableau de 100 cases de valeurs entière et qui met la valeur 12 dans chacune des cases,puis affichez le contenu de la dernière case.
Cette "expérience" ne devrait normalement vous poser aucun problème et le résultat est , normalement, tout à fait prévisible, et sans surprise.

Expérience 1

Augmentez la taille du tableau du programme précédent, passez de 100 cases à 1000, et re-testez le.
Puis 10000, puis 100000, etc.... et testez votre programme à chaque fois.
À un moment ce programme ne marchera plus...
Pourquoi ? (quelle est la taille de la mémoire disponible?)

Après une explication nous verrons le fonctionnement de la fonction malloc.

Expérience 2

Re-écrivez le programme précédent en utilisant la fonction malloc pour faire une allocation "manuelle" en lieu et place de l'allocation "automatique" précédente.
Est-ce que ça marche mieux ? Pourquoi ?

Expérience 3

Maintenant que vous arrivez compris qu'une allocation ne marche pas forcément à tous les coup, écrivez un test vous permettant de savoir si l'allocation à réussi, avant d'écrire en mémoire...

Expérience 4

Maintenant que vous savez réserver des zones mémoire, essayez de vous accaparer  un maximum de mémoire. C'est a dire allouer et utiliser un maximum de mémoire. Pour cela utilisez une boucle infinie. Grâce au programme "top" mesurez quel pourcentage de la mémoire vous arrivez à utiliser. Essayez (par tout les moyens que vous trouverez raisonnable) d'en avoir le plus possible.
Quelle quantité arrivez vous à obtenir ? Que se passe-t-il quand l'ordinateur commence à manquer de mémoire ?

Expérience 5

Vous comprenez maintenant qu'il nous faut donc une instruction pour rendre la mémoire au système, une fois qu'on en a plus besoin... Cela se fait via l'instruction free.
Modifiez votre dernier programme de manière à ce qu'il libère les zones mémoire qu'il n'utilise plus. Voyez la différence de comportement de l'ordinateur lors de l'exécution de cette nouvelle version du programme.
Pour encore mieux percevoir l'état de l'ordinateur, utilisez un "moniteur système" (ou "system load indicator") que vous trouverez via la barre d'applications. Un peu comme le compte tour ou la mesure de température d'un moteur de voiture, un "moniteur système" vous indique votre consommation des ressources de l'ordinateur.
Bien sûr plus un programme est économe, mieux c'est.

Expérience 6

Relancez l'"expérience 4", tout en surveillant votre moniteur système pour mieux comprendre/voir ce qu'il se passe.
À quoi peuvent servir les autres mesures du moniteur système ? ("load", "disk", "net") ?

Expérience 7

Reprenez votre programme de jeu de pendu, et remplacez toutes les allocations "automatique" (avec l'opérateur []), par une allocation "manuelle" (via la fonction malloc). Pensez aussi que pour faire un bon programme vous devrez aussi libérer ces zones mémoire via free (une fois que vous n'avez plus besoin des données correspondantes). Testez à nouveau votre programme pour vérifier que ces modifications n'ont pas généré de bug.

Profitez aussi de cette reprise en main du programme de jeu de pendu pour commenter votre code.
Pour rappel; commenter un code veux dire ajouter des annotations en langage naturel facilitant la compréhension du programme. Pour éviter que le compilateur lise ces information utilisez la suite de symbole // pour signifier au compilateur de ne pas lire ce qui suit.
exemple :  
   printf("hello world!\n"); // ceci est un commentaire

Conclusion

Listez toutes les propriétés et informations importantes concernant la mémoire que vous avez appris aujourd'hui.

Travail personnel

Votre programme de jeu de pendu est fonctionnel, mais très vraisemblablement vous avez mis un certain temps pour faire l'"expérience 7", car vous avez , naturellement mis du temps à comprendre à nouveau ce que fait chaque ligne du programme.

Pour éviter cela il est bon d'organiser son code avec des fonctions. Vous allez donc découper l'ensemble du code du jeu de pendu en fonctions qui s'occuperons de différents aspects du jeu.
Par exemple (il y a des tas de manière différentes de faire ce découpage) :
  • Allocation de tableaux de caractère (utilisé pour le "mot secret" et "le mot masque")
  • Initialisation du mot masque
  • Tester si la lettre proposée est présente, ou non, dans le mot secret (et modification éventuelle du mot masque)
Bien sur une fois ces fonctions crées il vous faudra modifier le code dans le main pour qu'il utilise ces fonctions. Idéalement le code qui reste dans le main n'est plus que des appels de fonctions. Si le nom des fonctions et des variables ont bien été choisit , ce code devient alors très facile à lire.


lundi 8 septembre 2014

Mise à niveau informatique (module INF3036) (cours 1)

(... déstiné aux nouveaux étudiants entrant en 3A)

Le séminaire de pré-rentrée que vous avez suivit visait à vous amener à un niveau de fin de première année. Il reste maintenant vous amener à un niveau de fin de deuxième année, pour cela nous avons une douzaine de séances de TP en salle informatique. C'est évidemment peu pour remplacer toute une année, mais si vous fournissez suffisamment de travail personnel, ça devrait faire l'affaire...

À l'issue de la fin de ce cours vous (ainsi que tous les étudiants de 3A) aurez un travail en C à réaliser en autonomie (LAB3040), qui sera bien sûr noté. Pour vous faire une idée du niveau de difficulté vous pouvez voir la vidéo de débriefing du projet de l'an dernier.

Pour faire le point de là où vous en êtes je vous propose, le 9 septembre, de programmer un petit jeux très simple mais qui permet de revoir tout les points travaillés lors du séminaire. Il s'agit du "jeux de pendu". Vous ne programmerez que les saisies au clavier, les affichages de l'évolution du jeu, mais bien sûr aucun graphisme. Une première saisie spécifiera le mot secret (le mot à deviner), cette saisie est supposée faite par le "maître du jeu". Les saisies suivantes seront faites par le joueur , et c'est le programme qui utilisera ces saisies et les comparera au mot secret, pour indiquer au joueur s'il progresse ou non.

  • Commencez par faire diagramme du jeu,
  • puis une description en pseudo code,
  • et enfin la réalisation en langage C. Quelques conseils : 
    • Vous réaliserez le code étape par étape, en vérifiant que tout fonctionne avant de passer à la suivante.
    • À chaque étape vous devez pouvoir vous situer précisément sur le diagramme global du jeu.

Les 3 heures de temps dont nous disposons devraient normalement suffire pour arriver au bout du problème ou du moins l'avancer suffisamment pour pouvoir le finir en travail personnel.

Les séances de la semaine suivante pourront servir à répondre à vos questions ou pour vous aider à finaliser certain détails, mais ce programme devra être globalement fini pour la séance du 16 septembre.

bon courage, et au travail ;)

lundi 1 septembre 2014

Nouveau Logo !

Voici un "presque-scoop" : l'école change de logo. Il n'est même pas encore mis à jour sur le site officiel ESIEA. Pour cette nouvelle rentrée nous avons maintenant un nouveau logo, dévoilé publiquement aujourd'hui.
On y gagne en sobriété, mais pour moi la vrai nouveauté est qu'on ne décline plus l'acronyme : pas d'explication sur le sens des lettres qui compose le nom de l'école. Mais on y gagne un sous-titre : "école d'ingénieur du monde numérique", ce qui est peut être plus explicite pour les prospects.

Et vous qu'en pensez vous ?

mardi 26 août 2014

séminaire de mise à niveau informatique

Bienvenue aux nouveaux étudiants, entrant en 2A et 3A!

Durant cette semaine vous allez faire une partie du programme d'informatique en accéléré.
L'objectif est de vous mettre au niveau de vos camarades ayant déjà commencé leur formation à l'ESIEA.

Pour cela vous avez des cours en amphi mais aussi des Travaux dirigés ainsi que du travail personnel à fournir.

Pour cela ce document va vous guider.

mardi 10 juin 2014

Transfert réussi !!

Pour des raisons techniques j'ai décidé de faire transférer mon blog professionnel sur Blogspot. Cela ne changera rien à son contenu, vous y trouverez toujours des ressources pour mes cours algorithmique, réseaux neuronaux,  projets étudiants et projets de recherche  ...

Merci aux étudiants : Serre Kevin, Al Hakawati Mouaz et Fabbro Alexis pour leur travail.

dimanche 1 juin 2014

Analyse Sémantique Automatique



Analyse Semantique automatique from Hubert Wassner on Vimeo.


La sémantique est la science qui s'intéresse au sens des mots. C'est un défi majeur des technologies de l'information, tout simplement parce que la notion de sens attaché à un mot est implicite lors de n'importe quelle requête d'un utilisateur. Le problème est qu'informatiquement c'est difficile à gérer. Heureusement, dans de nombreux cas, on peut se satisfaire d'une mesure de distance sémantique. C'est à dire mesurer la similarité de sens de deux mots. Il est possible de mesurer automatiquement ce type de distance. (Cf. L'article original : « Automatic Meaning Discovery using Google » , Paul Vitanyi et Rudi Cilibrasi). Ainsi, pour une liste de mots donnés on peut mesurer les distances qu'ils ont les uns par rapport aux autres, et créer une « carte ». ...
Cette technique nous a déjà permis de générer deux cartes, une cartographie de bloggeurs, et une cartographie d'auteurs. Aujourd'hui nous avons réalisé une cartographie sémantique de métiers, pour le compte de Meteojob (nouveau site d'offres d'emplois). L'objectif est de faire un système de « intelligent » capable de « comprendre » la similarité entre deux intitulés de métier tels que : « marbrier » et « tailleur de pierre ».


Si cet article vous a plus merci de voter (sur le site wikio) en cliquant sur cette icone.

1er TD sur les réseaux neuronaux



L'objectif de ce TD est de faire une première prise en main intuitive de l'utilisation de réseaux neuronaux (simpliste) avec une interface graphique puis une première mise en pratique via un programme en langage C.

Partie 1
Nous allons tout d'abord, utiliser cet applet : http://www.sund.de/netze/applets/BPN/bpn2/ochre.html de manière classique, c'est à dire, ce pour quoi il a été construit : reconnaître les chiffres de 0 à 9.
Dans un deuxième temps (une fois que vous aurez compris ce que ça fait et comment ça marche), vous allez modifier les donnés d'apprentissage pour que le réseau apprenne à reconnaître une croix (x) d'un rond (o). Vous pouvez modifier les données d'apprentissage en cliquant dessus (clic gauche ajoute un point, clic droit en supprime, 'c' remet le digit à 0. Voici les concepts qui seront illustré par cet exercice.
  • Notion d'apprentissage, et de mesure d'erreur via matrice de confusion
  • Notion de de généralisation. (essayer de faire reconnaître différent type de digit)
  • Notion de différent type de variabilité des données. (inter et intra-personnelle)
Partie 2
Nous allons ensuite apprendre à réaliser un apprentissage de réseau de neurone à partir d'un programme en langage C, utilisant une librairie. La librairie que nous allons utiliser FANN , elle est déjà installée dans les salles de TP. Pour commencer avec un exemple de base vous trouverez, presque tout, sur cette page. Une fois que vous aurez réussi à entraîner (et tester) un réseau sur la fonction XOR à 2 entrés, modifiez ces codes de manière a le faire avec un XOR à 3 entrés.
À l'issue de cet exercice vous aurez normalement compris ce qui est nécessaire pour construire un réseau, l'entrainer, et l'utiliser.

Partie 3
(Selon votre vitesse d'avancement , cette partie pourra être repoussée au TD suivant).
Attention : une erreur s'était glissé dans le lien vers les donnés, téléchargez à nouveau les donnés pour être sur d'avoir les bonnes valeurs.
En utilisant la libraire FANN, faites un programme qui détecte des cellules cancéreuse.Voir le contexte de l'étude ici, ainsi que la description des donnés. Vous trouverez les données nécessaire ici. Il y aura bien sûr une discussion pour savoir comment transformer ces données de manières à ce qu'elles soient utilisable par un réseau de neurones. Avec cet exercice vous aurez compris (normalement) la formalisation exigé par l'utilisation de réseaux de neurones.

Conclusion
à l'issue de de ce TD j'espère que avez une idée plus précise de ce qu'est un réseau de neurones par la pratique. Vous aurez peut être l'impression d'avoir tout vu, mais attention c'est une illusion car pour le moment on n'a pas encore réellement aborder les points critiques de cette technique : l'analyse d'erreur. Soyez en sûr les réseaux que nous avons crées ici sont finalement très très imprécis, malgré nos tests. Nous avons sauté un tas d'étapes qui sont primordiales à la création d'un réseau de neurone réellement fonctionnel. Nous verrons cela en cours et dans les TD suivants...

Annexe(s) :

(Le compte Twitter de) Bixenté Lizarazu mis à nu



J'ai testé mon nouvel algorithme sur un échantillonnage de plus de 900 followers du compte Twitter de Bixenté Lizarazu, et j'en ai produit une cartographie. Assez naturellement il y a beaucoup de followers qui sont des fans de foot, mais il y a aussi beaucoup de fans de "peoples". Grâce à cette cartographie on peut on répondre quantitativement à la question : « Bixenté Lizarazu, footballeur ou people ? »...
Dans cet article je me contenterai de décrire les résultats produits sur le compte Twitter de Bixenté Lizarazu. Si vous êtes curieux de la méthode employée, voyez cet autre article qui fait une analyse du compte Twitter de Korben (blogueur geek "connu") et qui explique un peu plus l'algorithme de construction de la carte.

Cliquez sur l'image pour l'agrandir Cliquez ici pour télécharger la carte en PDF 



Première chose étonnante c'est que l'algorithme dispatche les fans de foot sur 5 zones différentes....

"Les Footeux"
Je comprend le sens d'une partie de ce découpage, il y a ceux qui suivent d'abord les journalistes de foot et leur émissions , c'est le plus gros regroupement : 18% (en haut à droite sur la carte).
Voici les lectures caractéristique de ce groupe : PierreMenes CanalFootClub MATUIDIBlaise lequipe MathouxHerve BafGomis kevingameiro9
Puis il y a les 4 zones qui occupent la partie du milieux et inférieure droite de la carte, 3.2% + 9% + 3.9% + 15.1% = 31.2% les lecteurs semblent chercher leur informations directement auprès des comptes Twitter des joueurs.. Voici les lectures caractéristique de ce groupe :

10Ronaldinho DaniAlvesD2 Carles5puyol andresiniesta8 3gerardpique XabiAlonso DiegoForlan7

FCBayern dante_bonfim David_Alaba ToniKroos LGustavo_30 Javi8martinez XS_11official
IAmJermainDefoe premierleague rioferdy5 21LVA usainbolt WayneRooney GNev2
kobebryant KingJames lequipe VincentKompany CP3 hazardeden10 nicolas88batum

C'est peut être pour cette raison que le lectorat est « divisé » en fonction des équipes pour lesquelles ils jouent. Je ne m'y connais pas en foot, je ne peux donc pas tester cette hypothèse. Si vous avez un avis sur la question n'hésitez pas à en faire part via les commentaires. Ou directement via Twitter
Et voici le dernier groupe relié à la thématique foot, les « footeux modérés », ils sont 22.6%. Ils ont en commun ces lectures : PierreMenes gadelmaleh Cyrilhanouna debbouzejamel MichaelYoun dubosc_franck lequipe. En regardant en détail, on voit que c'est des gens intéressés par le foot, mais pas uniquement. Le foot n'est pas l'unique thématique de leur compte.
On arrive donc à total de ~72% de followers du compte de Bixenté Lizarazu qui sont fan de foot, mais alors qui sont les autres ?

Les autres...
« les multisport », (dont Bixenté fait lui même parti), ils représentent 12.1% du total, ils lisent les sujets suivants : lemondefr michel_denisot stephaneguillon Bruce_Toussaint lequipe sebchabal PierreMenes
Les « pur people » 15,9%
La thématique de ces comptes n'est pas uniquement « people » mais, en tout cas c'est l'unique point commun des gens dans ce groupe. L'algorithme a séparé ce groupe en deux, les « peoples » français, et les américains.
10.8 % suivent : EmoireOff JeniferOfficiel KarineFerri Arthur_Officiel LorieOfficiel AudreyLamy amel_bent
5.1% suivent OfficialAdele justinbieber taylorswift13 aliciakeys katyperry jtimberlake CodySimpson
Il est intéressant de remarquer qu'il y a beaucoup de filles dans ces groupes (en tout cas plus que dans le groupe des "footeux").

Conclusion
Assez naturellement une vaste majorité des followers de Bixenté Lizarazu sont des fans de foot, environ 70%, cependant ils sont hétérogènes pour le reste de leur lectures. Le plus intéressant c'est les autres... Un total de 28% qui ne sont pas à proprement parler des fans de foot, en tout cas 15.9% ne sont probablement jamais allé voir un match, et sont clairement plus centré "people" que "footeux".
Pour simplifier, Bixenté Lizarazu, est en partie, vu sur Twitter comme un "people" ou tout du moins 15% des gens qui s'intéressent à lui sur Twitter ne s'intéressent pas du tout au foot.
Annexe(s) :

L'algorithme pagerank comment ça marche ?


Pourquoi est-ce important ? La plupart des gens utilisent des moteurs de recherche pour trouver ce qu'ils cherchent sur internet. Tout site internet se doit donc d'être bien être référencé, sinon il n'aura aucun visiteur. Choisir les bon mots clés est relativement facile, par contre avoir un indice pagerank élevé est plus compliqué. L'indice pagerank est ce qui définit la position dans les page de résultat des moteur de recherche (pour google évidement, mais les autres moteurs utilisent maintenant plus ou moins le même genre d'algorithme). Il est donc très important de bien comprendre le fonctionnement de ce type d'algorithme pour espérer apparaître sur la première page de résultat (la seule lue dans 95% des cas) ou au moins figurer parmi les premiers. Je vous propose dans ce billet d'éclairer le fonctionnement de cet algorithme ainsi qu'un applet Java permettant d'expérimenter ce type d'analyse. Il s'agit bien sur d'une version simplifiée, mais cela permet de comprendre quand même beaucoup de choses...

(Pagerank du blog : PageRank Actuel )
Normalement est apparu une fenêtre contenant la démo' interactive, si ce n'est pas le cas activez Java sur votre navigateur.(Java 1.5)
Pour directement voir la documentation d'utilisation du programme cliquez ici.


Voici une superbe démo en ligne, faite par Vincent Marquet un de mes étudiants : cliquez ici.


Petit historique
Les premiers moteurs (altavista ou yahoo) ne faisaient qu'indexer, c'est à dire trouver toutes les pages contenant le ou les mots clés recherchés. On pouvait retrouver les pages contenant un mot clé donné mais les résultats n'étaient pas triés efficacement. Le nombre de fois où apparaissait le mot clé faisait apparaître la page en haut de la liste de résultat, ce qui n'est pas pertinent. Le nombre de répétions du mot clé n'est pas un critère intéressant car aisément falsifiable. Il faut faire une analyse plus fine du web pour être capable de mesurer automatiquement l'importance de chaque site. Sergey Brin et Lawrence Page, étudiants à standford on trouvé une solution aussi originale que simple : utiliser l'information des liens entre les pages pour mesurer l'importance des sites, et être alors capable de classer correctement les résultat d'une recherche de mots clés. Cet algorithme s'appelle le « pagerank », il est finalement assez simple (niveau deuxième année d'étude supérieure, je le propose d'ailleurs dans mon cours). Sergey et Lawrence ont créé l'entreprise Google qui est alors le meilleur moteur de recherche du web. Google est devenu très rapidement (et sans aucune publicité) un des moteurs les plus influant du web, les autres (yahoo etc...) on rapidement suivit, mais bien sur cette avancé technologique leur à a permis d'être les « first to market » et donc de prendre une longueur d'avance sur la concurrence... Google essaye de garder cet avantage, en proposant toujours de réelles avancées technologiques, et bien sûr en améliorant l'algorithme pagerank qui est devenu un secret industriel aussi bien gardé que la fameuse recette exacte du coca-cola. La version que j'expose ici reste est une approche à la fois simple et instructive pour comprendre les bases du référencement vu que maintenant tous les moteurs de recherche utilisent des variantes de cet algorithme.

Le pagerank, comment ça marche ...
L'algorithme pagerank calcule un indice de popularité associé à chaque page web. C'est cet indice qui est utilisé pour trier le résultat d'une recherche de mot clé. L'indice est définit ainsi : L'indice de popularité d'une page est d'autant plus grand quelle à un grand nombre de pages populaires la référençant (ayant un lien vers elle). Cette définition est autoréférente car pour connaître le l'indice d'une page il faut d'abord connaître l'indice des pages ayant un lien vers elle... Il existe cependant un moyen assez simple d'approcher une valeur numérique de l'indice.
Tout d'abord il faut voir le web comme un graphe. Chaque page est un noeud du graphe, chaque lien entre page est un arc entre deux noeuds.


Un manière commode pour représenter de telles relations est d'utiliser une matrice (= un tableau) : chaque ligne et colonne représentant un noeud (donc un site) et chaque case de la matrice représente la présence d'un lien entre les 2 pages correspondantes.
Voici un exemple de graphe :

Voici la matrice correspondante au graphe ci-dessus.


Site No 0
Site No 1
Site No 2
Site No 3
Site No 0
0
0
0
0
Site No 1
1
0
0
0
Site No 2
1
0
0
0
Site No 3
1
0
1
0
Note : Pour savoir si il y a un lien entre 2 sites A et B, il suffit de regarder le contenu de la case positionné en ligne A et colonne B : 0 signifie qu'il n'y a pas de lien, 1 qu'il y en a un.
Nous allons appeler cette matrice M. On représente la probabilité de présence d'un internaute sur tous les noeuds de notre graphe par un vecteur V. Dire que l'internaute est sur la page « 1 » s'écrit : V = (0 1 0 0). (attention on commence à compter les pages par 0 c'est donc bien la deuxième valeur qui est à 1 dans ce vecteur).
V' = V*M
on obtient un vecteur V' = (1 0 0 0), c'est justement la probabilité de présence de l'internaute sur les pages : après un clic, l'internaute se retrouve forcement sur la page « 0 ». Il a suivit l'unique lien sortant de la page « 1 », allant vers la page « 0 ». On peut alors re-itérer l'opération et multiplier ce vecteur résultat par M pour voir où se situera l'internaute lors du clic suivant, et ainsi de suite...
Si on faisait partir notre internaute de la page « 3 » : V = (0 0 0 1) le produit V par M donne (1 0 1 0), la somme des composante fait alors 2, c'est gênant pour représenter une probabilité de présence... . Dans la mesure où il impossible de savoir quel liens aura le plus de succès on va considérer qu'il ont tous la même probabilité d'être suivit, cela revient à normaliser la matrice (diviser chaque composante par la somme des valeur de la ligne correspondante), le problème est résolut. La matrice devient alors :


Site No 0
Site No 1
Site No 2
Site No 3
Site No 0
0
0
0
0
Site No 1
1
0
0
0
Site No 2
1
0
0
0
Site No 3
1/2
0
1/2
0
Notez que la somme de chaque ligne fait bien 1, et que le produit V * M donne alors V' = (½ 0 ½ 0) et représente alors correctement les probabilités de présence de l'internaute, partant de la page « 3 » et après avoir suivit un lien (« 1clic »). Si on re-itère l'opération , c'est à dire V'*M on obtient (1 0 0 0) au bout du deuxième « clic » de l'internaute. Si on continue on voit bien que le résultat ne changera plus... L'internaute est bloqué sur la page « 0 ». Cela n'est pas très réaliste, on considérera alors que l'internaute repart sur une autre pas, choisie au hasard. Cela revient à ajouter aux pages « cul de sac » des liens vers toutes les autres pages. Du point de vu de la matrice cela revient à trouver les lignes qui n'ont que des 0 et les replacer par des lignes avec 1/3 (dans ce cas précis) dans toutes les cases sauf sur la diagonale (lien d'une page vers elle même). Pourquoi 1/3 ? Tout simplement par ce qu'il y a 4 pages et qu'on considère que l'internaute reprendra son parcours aléatoirement sur n'importe quelle autre page (4(toutes les page) – 1 (celle ou il est actuellement « bloqué ») = 3).
Le processus tel qu'on la définit permet, maintenant, de modélisé raisonnablement un déplacement aléatoire d'internautes sur le réseau de page, modélisé par un graphe. Pour obtenir une vision globale et impartiale de la popularité des pages en fonction des liens qu'elles ont entre elles, il suffit maintenant de supposer que les internautes se répartissent initialement uniformément sur tout le réseau et on les laisse se déplacer jusqu'à ce que leur répartition (le vecteur V) se stabilise au fur et à mesure des itération de multiplication avec M. Dit autrement on commence avec un vecteur V dont toutes les composantes sont égales a 1/N, N étant le nombre total de pages (ou noeuds du graphe). Ensuite on multiplie itérativement V par M jusqu'à ce que le valeur du vecteur V n'évolue plus. On regarde alors la répartition des internautes sur le graphe, cela nous donne l'indice pagerank, plus il est élevé plus il y a d'internautes sur la page, donc plus la page est populaire...
Une recherche se décompose alors en deux étapes :
  • la sélection des pages contenant les mots clés de la requête.
  • Le classement , par ordre décroissant, des pages concernées en fonction de leur valeur de pagerank. Cette valeur aura bien sur été calculée précédemment et n'est pas recalculé à chaque requête.
Ces deux actions combinées font un moteur de recherche plutôt efficace...
On voit que algorithme pagerank (simplifié) est finalement assez simple:
  1. initialisez toutes les composantes de V à 1/N (N étant le nombre de pages ou noeud du graphe)
  2. calculer V'= V*M, (où M est la matrice représentant le graphe)
  3. copier le contenu de V' dans V
  4. reprendre en 2 sauf si les deux vecteurs V et V' sont très proche, dans ce cas l'algorithme est terminé
V ou V' (puisqu'il sont proche la fin de l'algorithme) contiennent les indices pagerank de chaque page. En pratique les valeurs de pagerank sont modifiés pour donner des valeurs entre 0 et 10, pour que cela soit plus « parlant ». Cela n'a que peu d'importance en pratique dans la mesure où on utilise cette valeur uniquement pour la comparaison entre les différents sites concerné par une recherche de mot clé.

Essayez vous même ...

La fenêtre qui s'est ouverte quand vous êtes arrivé sur cette page est une démonstration de cet algorithme réalisé par deux étudiants de deuxième année dans le cadre d'un TP de deuxième année (Vincent GERMAIN & Steevy MONTOUT).
Si vous avez fermée cette fenêtre, cliquez sur le bouton pour recharger la page, elle devrait re-apparaître. (Il faut que Java soit activé sur votre navigateur)
Ce démonstrateur est très simple d'utilisation :
  • Cliquez avec le bouton gauche de la souris, quelque part dans le cadre vide pour créer des noeuds (représentation d'une page web).
  • Faite un « drag&drop » (« glissé déplacé ») pour créer des liens entre les pages
  • appuyez sur bouton gauche de la souris près du noeud de départ
  • déplacez la souris vers le noeud d'arrivé en laissant le bouton enfoncé.
  • Relâchez le bouton près du noeud d'arrivé. Le lien est alors crée.
  • Pour supprimer des noeuds ou liens, faite la même opération que pour la création (clic ou drag&drop) mais avec le bouton de droite.
  • Le bouton du milieu permet de déplacer un noeud.
  • Cliquez sur le bouton «  Pagerank » pour lancer le calcul « pagerank » sur le graphe ainsi constitué.
Le résultat du pagerank est matérialisé en changeant la taille des noeuds et leur couleur : plus le noeud est grand et tend vers le rouge plus ce noeud regroupera des internautes (=plus sont indice pagerank est grand). Plus précisément le site avec le plus grand pagerank est affiché en rouge avec un grand rayon, tous les autres pages auront ,proportionnellement des cercles plus petits et un rouge moins marqué tendant progressivement vers le jaune plus le pagerank sera faible... Les exemples du paragraphe suivant vous aideront à comprendre la signalétique utilisée dans ce démonstrateur.

Quelques exemples d'analyse pagerank
Tout d'abord il est à noter que cette analyse n'est pas aussi intuitive qu'on puisse le penser. Voyez l'exemple de graphe ci-dessous :

Le résultat du pagerank n'est pas si simple à imaginer ...

Et des modifications simples peuvent amener à des résultats difficilement prédictible...

Un seul liens de plus entre 2 noeuds (qui est la seule différence entre les 2 graphes précédents) modifie considérablement le résultat.
Bref tout cela n'est pas si simple mais ce démonstrateur vous permettra quand même de comprendre quelques règles simples pour augmenter le pagerank d'un site...

Conseils pour augmenter le pagerank d'un site ...

Les liens entrants : toujours positifmais à des dégrés variables

Il est inutile de multiplier les liens provenant de sites avec un faible pagerank. Voir la partie droite du graphe ci-dessous, malgré 3 liens entrant, le site de de droite à un pagerank faible...


Un seul lien entrant, provenant d'un site ayant un pagerank élevé, est beaucoup plus efficace : voir l'exemple ci-dessous.

Notez que la page « donnant » le lien (en bas au milieu) ne perd pas vraiment d'indice pagerank (en tout cas proportionnellement aux autres, et c'est cela qui compte).
Ces liens entrant sont d'autant plus intéressant que le nombre de liens sortant de la page d'origine sont peu nombreux.

La page en bas à droite bénéficie moins du lien entrant provenant de la page qui est a sa gauche (par rapport à la figure précédente) car cette page à maintenant plus de liens sortant.

Les liens sortant : positif ou négatif, selon la topologie

Négatif (si si c'est possible...)

Contrairement à ce qui est souvent cru, certain liens sortant peuvent faire baiser l'indice pagerank d'une page, en tout cas d'un point de vue théorique. Voyez l'exemple ci-dessous :

et après l'ajout d'un lien sortant :

La page en bas à droite à perdu une bonne partie de son indice pagerank... Il est à noter qu'il s'agit là d'un cas un peu particulier et qu'en général un lien sortant a peu de chance de réellement faire baiser le pagerank d'une page. Les exemples simplistes des deux figures précédentes sont peu représentatifs de la topologie du réseau des pages web.

Positif

Avant la création du lien :

après : Notez la différence de taille de la page à laquelle on a ajouté un lien sortant. Sont pagerank a bien augmenté, tout simplement parce que ce lien, retourne sur cette page après un court détour. Il est donc bon qu'un site relie bien ses pages entre elle (ce qui evidement en plus rend le parcours de l'internautre (réél) plus pratique. Cependant attention de ne pas en abuser et de ne pas générer une « link farm »

Les « link farm »

Des « link farm »sont parfois artificiellement crées pour accumuler artificiellement du pagerank. Il s'agit de pages reliées entre elles mais qui n'ont aucun liens vers d'autres pages, et aucune page « cul de sac ». Tout internaute (simulé par l'algorithme pagerank) y pénétrant n'en sort pas. Mettre un lien ver une telle page peu grandement faire baisser le pagerank d'une page et de celles qui y amène. Dans le schéma ci-dessous le réseau de gauche est un réseau « normal », celui de droite une « link farm » :
Avant le lien vers la « linkfarm »

après ...

Notez que cette configuration de « link farm » est artificielle (générée par des webmaster peu scrupuleux), pour des pages réelle il y a toujours des liens sortant vers le reste du réseau. Dans l'exemple ci-dessous, un seul lien sortant de la « link farm » retablit la situation.

C'estpourquoi les moteurs de recherche identifient ces sous-réseau particuliers (en remarquant qu'il sont isolé du reste du web) pour les pénaliser.

En résumé

Il est évidement malsain de faire des pages web sans aucun lien sortant ou ne reliant que des pages du même site, car cela forme ce qu'on appelle des « link farm » ce qui est fortement pénalisé par les moteur de recherche (si bien entendu ils s'en rendent compte...). En pratique il n'y a donc pas besoin d'avoir une réelle politique technique de liens sortants si ce n'est que ces liens soient intéressant pour l'internaute. Pour les liens entrant, plus il y en a mieux c'est. Il ne sont cependant pas tous aussi facile à générer et ils n'apportent pas tous le même gain cela dépend du pagerank de la page originaire du lien ainsi que du nombre de lien sortant de cette page.

Quelques exemples
En appliquant ces règles voici le résultat de recherches de mots clés sur google-france. Ces mots clés correspondent à des articles de ce blog, cependant vous pourrez noter que nombre de ces requêtes pourraient assez légitimement ne pas donner ces articles en premier. Il est aussi à noter que, très certainement, une partie du pagerank de ce blog est en partie héritée du site « www.esiea.fr ».
Voici une liste de requêtes sur Google où ce blog est très bien classé alors qu'il existe des pages certainement plus légitimes :
Merci de voter pour cet article, qu'il vous ai plu ... ou non...

Projet 3A en autonomie


Sujet du projet de programmation (3A) en langage C : L'agencement de graphes.
Lisez la suite pour voir une courte vidéo d'introduction au projet.
Voici une vidéo vous présentant la problématique d'agencement de graphes et la solution que je vous propose d'implémenter...

Le sujet est attaché à cet article, ainsi qu'un code de base pour l'affichage graphique ("fenetre.c"), et des exemples de graphes.
Je communiquerai sur cette page les réponses aux questions que vous me poserez par mail. Pensez donc à y revenir de temps en temps , et surtout avant de poser une question ;)
Le plus simple est de l'installer via "apt-get" :
sudo apt-get install libcsfml-dev libgl1-mesa-dev libglu1-mesa-dev
Si vous utilisez les ordinateurw de salle de TP, la librairie est déjà installée, vous n'avez donc rien à faire.
[EDIT] On m'a signalé qu'il y a un problème à l'exécution sur les machines de TP... Il y a apparemment eu des mises à jour, entre mes derniers tests fait avant l'été, et maintenant... Nous travaillons à trouver une solution.
[EDIT #2] Le problème semblerai avoir lieu en salle I12b et E08, mais pas en I22, si vous travaillez à l'école, utilisez la salle I22, et vous n'aurez pas de problèmes... En attendant qu'on résolve le problème et que ça marche dans toutes les salles...
[EDIT #3 fait le 25 octobre] bizarrement certains étudiants m'on rapporté que la ligne de compilation ne marchais pas chez eux. Dans ce cas essayer comme ceci (en mettant le "-lm" à la fin de la ligne). 
gcc -Wall -g fenetre.c -lcsfml-graphics  -o fenetre -lm
J'ai reçu un certain nombre de questions par mail, en voici les réponses :
  • Vous aurez besoin d'ajouter la librairie mathématique (#include ", d'où le "-lm" dans la librairie qui y est associée), mais c'est tout, vous n'utilisez pas d'autres bibliothèque que celles déjà utilisée dans le code de base ("fenetre.c"). Je vous rappelle que je vais devoir corriger un très grand nombre de codes, et je vais donc essayer d'automatiser un certain nombre de tâches, dont la compilation.
  • Une question m'a souvent été demandée sur le poids à associer à chaque noeud. La réponse est dans la formule vous permettant de simuler les forces du ressort correspondant aux liens. Quand vous voulez appliquer la force correspondant au ressort, il vous faut spécifier une masse correspondant aux noeuds. Vous prenez donc la même masse pour tous les noeuds. Cela peut donc être tout à fait une constante du programme, ou une valeur dans la structure représentant les noeuds, c'est comme vous voulez. Cette valeur de masse dépend de la raideur du ressort que vous aurez choisit pour représenter les liens. Si la raideur est importante, vous devez mettre une masse élevée, et si vous mettez une raideur faible, il vaut mieux mettre une masse faible sinon la simulation ne bouge tout simplement pas... C'est à vous de faire des essais et de trouver un compromis qui fonctionne. Comme précisé lors de la présentation, ce principe de simulation ne vous assure pas de trouver une disposition optimale à tous les coups, essayez de trouver des paramètres qui fonctionnent bien, je n'exige pas quelque chose de parfait. Les vidéos (il y en a deuxième en dessous) vous donne un aperçu de ce qui est possible de réaliser (et aussi de certaines imperfections dont il est difficile de se débarrasser.).
  • Si vous désirez aller plus loin que le sujet de base, faites le et envoyez moi la vidéo (sous linux, le logiciel recordMyDesktop fonctionne plutôt bien pour faire cela.) et je publierai vos exploits ici comme ce que m'a envoyé Michel Remise. (Voir la vidéo ci-dessous). Mais pour la notation, rendez moi un code qui suit toutes les recommandations de base, car pour la correction, la plupart des étapes seront automatisées, donc ne cherchez pas à faire quelque chose de différent, ça risque de ne pas passer !
[EDIT #4] fait le 6 novembre. Je repousse la date de rendu du projet au 5 jeudi décembre (minuit au plus tard). Cela pour plusieurs raisons, tout d'abord il y a eu un problème pour faire fonctionner ce programme en salle de TP (cela vous a peut etre fait perdre du temps). J'ai vu aussi un certain nombre d'étudiants ayant un peu de difficulté avec le projet, mais qui faisaient des efforts et qui progressaient. Je pense donc que ce délais supplémentaire sera bénéfique. De plus je vous propose une séance supplémentaire le jeudi 28 novembre, en salle de TP, à laquelle je serai présent pour répondre à vos questions. Cette séance est bien sur facultative (car toute la promo ne rentrera pas dans une seule salle info' ;) ) , seul les étudiants en difficulté sont réellement convié à cette séance.
[EDIT #5] les machines de toutes les salles ont été mises à jour, vous pouvez donc maintenant travailler sur ce projet dans toutes les salles (site de Vésale y compris).
Bon courage et bon travail...

Voici les réalisations de certains étudiants ...
Qui on réalisé bien plus que ce qui était attendu. Un grand bravo pour ces réalisations.
Voici ce qu'à réussi à faire Michel Remise, c'est une suite d'exemple de graphes de plus en plus compliqué, et qui va nettement au delà de mes espérances ;) bravo! Ayez la patience de voir la vidéo jusqu'au bout car les derniers exemples sont très intéressant. Si vous avez aussi envie de pousser


Voici encore un autre travail d'étudiant qui mérite le détour. Vincent Marquet à utilisé le logiciel Baldr (production ESIEA!) qui permet d'étudier les similarité de fichiers, principalement utilisé pour de l'analyse de similarité de code, dans le but de détecter du plagiat en TP. Il a utilisé ce logiciel pour analyser des histoires écrites par Raymond Queneau. Il s'agit de la même histoire mais raconté dans des styles différents. Baldr produit des mesure de distances entres ces histoires, ces distances sont utilisées dans le programme de Vincent pour produire l'agencement d'un graphe illustrant les liens de proximité entre les histoires. Le résultat est surprenant puisqu'on constate qu'un programme (prévu pour de l'analyse de code) est capable de faire de l'analyse littéraire !! 

Si vous avez réalisé, vous aussi, un programme qui va au delà de ce qui était demandé, n'hésitez pas à faire une vidéo, me l'envoyer, et je la publierai ici.