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