Projet 1 - Langage C

Benoit Boissinot Eddy Caron Mioara Joldes1

September 23, 2008

1Merci a Domnique Lazure pour avoir inspire certains sujets.

2

Chapter 1

Langage C

1.1 Un automate pour un pretty-buffer

Le but de ce projet est de developper un ”filtre” en langage C. On appelle ”filtre” un programme quilit un texte sur l’entree standard (stdin) et qui sort un texte sur la sortie standard (stdout), aveceventuellement quelques modifications. Le plus simple des filtres est la commande Unix cat qui litstdin et ecrit le meme texte sur stdout.

Le filtre developpe durant ce projet est appele ”pretty-printer” (on nommera le fichier source pp.c).Il permet de mettre en forme un fichier texte contenant un programme C. On se limitera a une versionsimplifiee uniquement de l’indentation et des commentaires.

1.1.1 Caracteristiques

Indentation A chaque accolade ouvrante, on passera a la ligne suivante et on incrementera l’indentationcourante (par defaut, on considerera qu’une indentation vaut 3 blancs). A chaque accolade fer-mante, on ira aussi a la ligne apres avoir decremente l’indentation. Tout debut de ligne se fera auniveau de l’indentation courante (attention a la lecture de blancs ou des tabulations en debut deligne).

Commentaires On placera les commentaires en debut de ligne, au niveau de l’indentation courante.On se limitera a un commentaire par ligne. Quand une fin de ligne apparait dans un commentaire,on fermera ce commentaire et on en ouvrira un second sur la ligne suivante.

Erreur En cas d’erreur (commentaire non ferme ou texte mal ”accolade”), on sortira un message d’erreurstderr, tout en continuant le formatage. En fin de formatage, on pourra afficher un messaged’avertissement si le nombres d’accolades ouvrantes et fermantes ne semblent pas correspondre.

1.1.2 Attention!

• Une accolade dans un commentaire doit etre ignoree.

• Aucune modification ne doit etre faire sur une ligne commencant par une directive de cpp (define,include... ou d’autres lignes commencant par # ).

1.1.3 Example

A partir du fichier file.c suivant:

3

#include <stdio.h>/*Ce programme ne fait pas grand chose*/void main(){int n;

char c;c=getchar(); /*on lit un charactere*/ /*sur stdin*/if (c==’’) {n++; putchar(c);}

else /*sinon,on ne fait rien*/{;}

}

La commande pp file.c monBeauFile.c va creer un fichier monBeauFile.c qui contiendra:

#include <stdio.h>/*Ce programme ne fait pas grand chose*/void main(){

int n;char c;c=getchar();/*on lit un charactere*//*sur stdin*/

if (c==’’){

n++;putchar(c);

}else/*sinon,*//*on ne fait rien*/{

;}

}

1.1.4 Comment faire?

Vous pouvez utiliser un automate. Par example, on ecrit un filtre qui supprime les espaces ou lestabulations en debut de chaque ligne:

DEBUT_LIGNE NORMAL

*

*

’\t’

’\n’

’\n’

entree

4

1.2 Vecteurs creux

On considere dans ce probleme un type de donnees VECTEUR. Les donnees de ce type sont des tableauxde MAX elements. (on pourra prendre MAX=1000 ).

0

0 1

03 8 0 0 6 0 0 4 0 0 0

MAX

On s’appercoit que les objets de type VECTEUR renferment beaucoup d’elements nuls (on pourraconsiderer qu’ils contiennent au maximum MAX SIGNIF elements non nuls). On definit alors un secondtype VEC COMP qui represente les memes objets, mais dont l’occupation memoire est plus faible.

0 1

3 8 6

1 2 5 9

4

MAX_SIGNIF

De plus, pour eviter d’avoir une limite sur le nombre d’elements non nuls, on definit un troisiemetype de donnees VEC LIST qui perment aussi de gerer des vecteurs, mais les implemente sous forme deliste d’elements non nuls avec leur indice dans le vecteur ainsi simule. On veillera a garder un ordrecroissant pour les indices de chaque maillon.

5

6

9

48

21

3

1.2.1 Allocation memoire

Attention aux problemes d’allocation memoire et aux passsages de parametres.

1. Ecrire les definitions des types VECTEUR, VEC COMP et VEC LIST.

2. Ecrire les fonctions de traitements des objets VECTEUR:

void Mise_a_zero(VECTEUR v);int Valeur(VECTEUR v, int indice);void Affecte(VECTEUR v, ind indice, int valeur);

3. Meme question pour les objets de type VEC COMP.

4. Meme question pour les objets de type VEC LIST.

5. Definir les specifications et ecrire les 6 fonctions de conversion d’un vecteur d’un certain type versun vecteur d’un autre type (dans les 3 proposes).

1.2.2 Attention!

• Les elements d’un vecteur peuvent etre des flotants.

• Le passage de parametres sera justifie par des commentaires precis. En particulier, on ne passerapas inutilement des pointeurs.

• Pour chaque fonction de conversion, la complexite doit etre minimisee, et elle apparaıtra en com-mentaire.

5

1.3 Graphe genealogique

On a retrouve a la mairie de Trifouilly-les-Oies un registre de declarations de naissances dont le contenuest un peu sommaire:

Brandon Jihair Saoul-HeleneJessica Jihair Saoul-HeleneJonathan Huggy PamellaBrenda Huggy PamellaJennifer Jihair Saoul-HeleneKevin Huggy PamellaJaques . .Valery Jonathan JenniferGeorges Jonathan JenniferFrancois Jonathan JessicaCharles Kevin Jessica

Apres un gros effort de recherche, on a fini par comprendre l’histoire et une television privee en afait un feuilleton qui dechaıne les passions du village tout entier. Si vous avez rate les 5683 premiersepisodes, vous consultez tele-gaga qui vous resume l’histoire:

• Jihair et Saoul-Helene eurent trois enfants: Brandon, Jessica et Jennifer.

• Jonathan et Jennifer sont les parents de Valery et Georges.

• Jonathan et Jessica ont aussi un enfant: Francois.

• Et ainsi de suite... En attendant l’episode suivant, vous avez deja traduit l’histoire par la figuresuivante.

Entre deux episodes, vous decidez de developper un outil informatique qui vous permettra de suivreen temps reel les evolutions demographigues des 63521 episodes restants. Pour cela, vous resoudrezles problemes suivants:

1. Comprenez le graphe et la signification des 6 pointeurs de chaque nœud.

2. A-t-on besoin de memoriser pour chaque nœud le sexe de la personne correspondante?

3. a quoi sert le chaınage general de tous le nœuds (celui en petits pointilles)?

4. Quel est l’interet d’avoir les chaınages cycliques horizontaux sur le schema?

5. Ecrivez les declarations de types necessaires au probleme.

6. Ecrire une fonction qui prend en parametre un nom et qui renvoie un pointeur sur le nœudconrrespondat (ou null si le nom n’existe pas dans le graphe).

7. Ecrivez une fonction qui cree un nuveau nœud, lui donne un nom passe en parametre, inserele nœud dans la liste de tous les nœuds presents dans le graphe et renvoie un pointeur sur cenœud. Ce nouveau nœud sera consideree (pour l’instant) comme n’ayant pas de parent, pasde frere ni de sœur (comme Jacques par example). On pourra considerer qu’il n’existe pasdeux personnes de meme nom.

8. Ecrivez une fonction qui modifie les differents pointeurs du graphe lors de l’etablissementd’une filiation pere/enfant. Cette fonction prends deux parametres : un pointeur sur l’enfant(que l’on vient de creer avec la fonction precedente) et un pointeur sur le pere; et etablit lafiliation pere/enfant.

9. Meme question avec la filiation mere/enfant.

10. Ecrivez une fonction qui affiche l’etat du graphe a un instant donne. Par example, vous pouvezecrire une fonction qui pour chaque nœud ecrit sur stdout le nom de la personne concerneeet les noms de chacun de ses eventuels voisins. Vous pourriez aussi ecrire une fonction quidessine le graphe avec des liens multicolores.

11. Ecrivez une fonction qui lit un registre de declarations de naissances et cree le graphe corre-spondant.

6

7

12. Ecrivez une fonction qui prend en paramtre un pointeur vers un nœud et qui annule la filiationd’avec son pere.

13. Meme question avec la filiation mere/enfant.

14. Ecrivez une fonction qui detecte les eventuelles anomalies genealogiques d’un graphe (parexample, avoir son pere comme fils ou comme frere).

15. Ecrivez une fonction qui ordonne le chaınage general de tous les nœuds suivant l’ordre al-phabetique des noms. Que faire de tous les autres pointeurs?

16. Ecrivez une fonction qui affiche les ascendants successifs d’un nœud (son arbre genealogique).

17. Ecrivez une fonction qui affiche les descendants d’une personne, pour une generation dont lenumero sera passe en second parametre.

18. Ecrivez une fonction qui affiche les descendants d’une personne, jusqu’a une generation donnee,generation par generation.

19. Ecrivez la fonction qui fait place nette en memoire.

20. Ecrivez la fonction qui sauvegarde la structure en ficher.

21. Ecrivez la fonction qui cree le graphe a partir d’un fichier.

8

1.4 Le masque jetable (One time pad)

Le masque jetable est l’un des plus simples algorithmes de cryptographie. Le chiffrement consiste acombiner le message en clair avec une cle qui est une suite de caracteres aussi longue que le message achiffrer et qui ne doit etre utilisee qu’une seule fois; les caracteres composant la cle doivent etre choisisde facon totalement aleatoire. Pour combiner le message et la cle, on va utiliser l’operation binaire”XOR“(⊕), definie ainsi :A B C0 0 00 1 11 0 11 1 0

Pour chiffrer on calcule donc C = A ⊕ B. Le resultat C est le chiffre de A. L’operation est effectueepour chaque bit du clair avec le bit correspondant de la cle. Le dechiffrement s’effectue en combinant lechiffre C avec le bit de cle B par la simple operation : A = C ⊕B. Par example,

10011100⊕ 11010001 = 01001101En supposant que vous avez a votre disposition un fichier assez grand, secret.key, et que vous voulez

chiffrer votre donnees tres importantes,

• Ecrivez une fonction simple qui prend comme arguments un caractere a chiffrer et un caractere cle,en vous retournant le caractere chiffre (ou sa valeur ASCII).

• Ecrivez une fonction similaire pour dechiffrement.

• Ecrivez une fonction qui peut vous donner la phrase chiffree, ayant comme parametres la phraseen clair et la cle. Attention! La cle doit etre au mois aussi longue que le phrase en clair.

• Ecrivez la fonction similaire, pour obtenir la phrase en clair, en sachant la cle et la phrase chiffre.

• Passez au choses un peu plus compliques, pour obtenir ”a fully fledged program”, qui peut chiffrerun ficher complet (on va le nommer, par example, fClair.txt), ayant au disposition le fichier clesecret.key. Pour ne pas utiliser la meme cle plusieurs fois (ca cassera la securite), mais toutefois,pour pouvoir dechiffrer votre donnes (en supposant que vous en avez besoin encore), penser astocker au debut du fichier cle un idice de position qui peut vous aider a utiliser pour chaquechiffrement une cle nouvelle. De plus, pensez a une solution similaire pour pouvoir dechiffrer votredonnees, apres plusieurs fichiers ont ete chiffres, “ en devorant” votre ficher cle.

• Offrez aux utilisateurs la possiblite de savoir quelle est la dimension disponible pour enchiffrer, etaussi les ”Warnings” imminents quand la dimension du fichier cle n’est pas suffisante.

9

10

Chapter 2

Langage Python

2.1 Poker Texas Hold’em

L’objectif de ce projet est de realiser un jeu de poker Texas Hold’em. Il estconseille de realiser des versions succesives afin de jalonner les etapes du projets.Il n’est pas indispensable de fournir toutes les versions. Vous pouvez privilegierla qualite de certaines versions au detriment du nombre de versions realisees.Ou vous pouvez privilegier le nombre de versions et aller le plus loin possiblemais en realisant le minimum demande pour chaque version. A vous de choisirvotre approche.

2.1.1 Les regles

Premiere etape comprendre les regles que vous trouverez a cette adresse http://fr.wikipedia.org/wiki/Texas_hold%27em.

2.1.2 Versions mode texte

Vous commencerez par une version en mode texte (non graphique).

v0.1 : 2 joueurs “Heads-Up”. Avec simplement la distribution des cartes, la carte brulee et l’etalementdu flop.

v0.2 : Detection des mains gagnantes.

v0.3 : Table pouvant aller jusqu’au “Full Ring”.

v0.4 : Gestion des mises.

2.1.3 Versions graphiques

Les etapes ci-dessous peuvent etre faites apres la v0.4 ou alors etre entrelacees.

v1.1 : 2 joueurs “Heads-Up”. Avec simplement la distribution des cartes, la carte brulee et l’etalementdu flop.

v1.2 : Table pouvant aller jusqu’au “Full Ring”.

v1.3 : Gestion des mises.

2.1.4 Versions reseau

Et pourquoi pas une version reseau ?

11

2.2 Du jeux de la vie au recif corallien

2.2.1 Le jeu de la vie

Les regles du jeu de la vie sont relativement simples au depart : Les cellules evoluent dans un environ-nement simplifie : en l’occurrence une grille rectangulaire. Dans un tel environnement, une cellule peutavoir 8 voisins

Figure 2.1: Voisinage d’une cellule sur une grille rectangulaire

Chaque cellule vit, meurt, ou bien genere une nouvelle cellule (division cellulaire) en fonction dunombre de cellules qui l’environnent. La vie de ces cellules est donc simulee par une boucle infinie. Achaque tour de boucle, on evalue la condition de chaque cellule pour determiner si elle doit survivre,mourir ou bien generer une nouvelle cellule au prochain tour de boucle.

Par exemple, le comportement typique tel que l’a defini John Conway (inventeur du jeu de la vie) estle suivant :

• Naissance d’une nouvelle cellule : Si un emplacement inoccupe possede 3 emplacements voisinsoccupes par des cellules, il devient occupe par une nouvelle cellule.

• Vie d’une cellule : Si une cellule possede 2 ou 3 voisines, cette cellule peut survivre.

• Mort d’une cellule : si une cellule ne possede que 0 ou 1 voisine, elle meurt (de solitude). Et si elleplus de 5 voisins (jusqu’a 8), elle meurt egalement (de surpopulation).

2.2.2 Recif Corallien

Il existe une infinite de variantes a ce comportement de base, il suffit de changer le comportement associea chaque nombre de voisins, par exemple.

12

Dans le cadre de ce projet on va envisager une variante qui consiste lorsqu’une cellule meurt a laisserson squelette en place. Ce comportement rend les cellules similaires a de colonies coralliennes1 ou seulela couche externe des coraux est vivante, l’interieur n’est fait que de cellules mortes. On peut de la mememaniere prevoir l’essaimage des nouvelles cellules dans certaines conditions.

On peut aussi imposer des conditions supplementaires quant a la naissance d’une nouvelle cellule.Par exemple on peut favoriser la direction de croissance des nouvelles cellules, de maniere a creer desstructures ramifiees, etc.

2.2.3 Methode

• Tout d’abord construire les cellules et leur environnement, avec leurs parametres d’evolution.

• Ensuite, faire evoluer une ou plusieurs population dans un meme espace.

• Pour la representation du jeu de la vie deux solutions sont possibles :

– on peut faire simplement une representation sous forme de caracteres dans un terminal (texte);

– ou bien une representation graphique de votre choix.

Votre programme devra permettre la simulation pas a pas (presser une touche ou un bouton pourpasser a l’etat suivant) et la simulation animee (prevoir un delais entre l’affichage d’un etat et celui dusuivant).

1Longement etudiees de facon non officielle par l’equipe GRAAL dans le cadre de son equipe associee avec l’Universited’Hawai‘i a Manoa.

13

2.3 GGP

Gnuplot est un logiciel ”libre”, permettant de tracer tres rapidement des courbes a partir d’une equation,ou bien de releves des mesures, telle qu’une simulation en fournit. Le maniement de gnuplot necessitede maıtriser de nombreuses commandes et de connaıtre de nombreeuses options. Ce projet proposede realiser un GGP (GUI for Gnuplot in Python). Vous pouvez vous inspirer de projet comme xgfe(http://www.uni-koeln.de/rrzk/software/grafik/visualization/xgfe/xgfe.html) qui proposait ce genre d’outilmais qui n’a pas evolue depuis 1998 ou encore JGNUplot (http://jgp.sourceforge.net/) une version ecriteen java.

14