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.