Cette remise à niveau en C prend la forme de séances de TP dans lesquelles trois types d’activités sont à considérer :

1. lecture et compréhension du cours du semestre précédent ;
2. réflexion sur des exercices du semestre précédent ;
3. réalisation de quelques TP du semestre précédent.

Les explications et les corrections se font sur demande.

Au moindre doute, ne pas hésiter à poser des questions.

Cours

Voici le matériel de cours proposé au second semestre de la L2 d’informatique. Il donne une bonne idée du niveau attendu pour continuer l’apprentissage du C en L3. Il faut travailler en priorité les chapitres

• “1. Bases” ;
• “2. Habitudes” ;
• “3. Modules” ;
• “9. Opérateurs > Opérateurs bit à bit” ;
• “10. Pointeurs de fonction”.

Et voici quelques remarques issues des examens des années précédentes.

Exercices

Voici un ensemble d’exercices partitionné selon les thèmes les plus saillants. Il est n’est pas demandé de tout faire mais il faut avoir une idée précise de ce qui est demandé, exercice par exercice.

Les exercices les plus importants sont les

• 1.4. (représentation des entiers) ;
• 2.1. (expressions, instructions, effets de bord) ;
• 2.2. (fonctions à effets de bord) ;
• 5.1. (pré-assertions) ;
• 5.2. (fonctions à gestion d’erreurs) ;
• 6.1. (compilation séparée) ;
• 7.1. (pointeurs) ;
• 7.6. (valeurs en mémoire) ;
• 7.7. (lecture de zones mémoire) ;
• 8.2. (pointeurs de fonctions et tableaux) ;
• 8.3. (pointeurs de fonctions et tris) ;
• 9.2. (test d’égalité générique) ;
• 9.3. (tableaux génériques).

Il est aussi possible de travailler sur le sujet d’examen de l’année dernière.

Sujets de TP

Voici une sélection de cinq sujets de TP.

La bibliothèque ncurses est utilisée en L2 pour construire des applications et des interfaces graphiques. Ici, il est parfaitement autorisé d’utiliser d’autres bibliothèques graphiques comme la MLV ou encore la SDL. Des versions de ce qui est attendu simplement en mode texte sont par ailleurs parfaitement acceptables.

Contrairement à ce qui peut être indiqué dans les énoncés de ces TP, il est demandé ici d’utiliser toutes les méthodes de bonne conduite de projet : modularisation, documentation, pré-assertions, etc.

1. Partir sur de bonnes bases (pdf) — Cette fiche contient divers exercices de base qu’il est impératif de de maîtriser avant de passer aux suivantes.

2. Introduction aux outils de débogage (pdf) — Cette fiche présente les outils de débogage simple à mettre en place pour déboguer un programme C. Il est important de les avoir dans sa trousse à outils pour diagnostiquer aisément un large spectre de problèmes couramment rencontrés quand on programme en C.

3. Le jeu du Chomp (pdf) — L’objectif est de programmer pas à pas un jeu à deux joueurs au tout par tour.

4. Le jeu du serpent (pdf) — L’objectif est de programmer pas à pas le célèbre jeu du serpent. Le jeu est cette fois-ci en temps réel Il s’agit aussi de respecter les bonnes méthodes de modularisation et d’écriture de programmes

5. Compter les mots (pdf) — L’objectif est de programmer un utilitaire permettant de poser des questions sur un fichier texte comme par exemple le nombre d’occurrences d’un mot qu’il contient.

Mini-projets

En complément des sujets de TP, voici quelques mini-projets réalisable pendant les séances de remise à niveau.

Ces sujets sont peu spécifiés (à différents niveaux), il est donc important de commencer par une phase de modélisation avant de se plonger dans l’écriture de code. De manière générale, il faut :

• déterminer les objets et données abstraites que le programme va manipuler
• définir les opérations qui seront effectuées avec ces objets
• écrire et documenter les fichiers d’entêtes
• coder les opérations

Signature 2D de fichier

L’objectif est de produire à partir d’un fichier une image en niveau de gris de 256×256 pixels telle que plus la séquence de deux octets 0xXX 0xYY est fréquente dans le fichier, plus le pixel aux coordonnées (0xXX,0xYY) est clair dans l’image.

Par exemple, dans un fichier source, la majorité des octets correspond à des caractères ASCII, donc compris entre 0 et 127. L’image obtenue sera claire sur un petit carré dans le coin supérieur gauche, et globalement noire ailleurs.

Travail demandé

Écrire un programme prenant en argument deux noms de fichier, réalise la signature du premier fichier et l’écrit sous la forme d’une image PGM dans le second fichier.

Notes

Le fichier PBM sera sous la forme :

P2 # Format niveau de gris ASCII
# Dimensions Largeur Hauteur
256 256
# Valeur maximum : Noir=0, Blanc=255
255
0 0 142 6 255 ...
...

Améliorations possibles

• Nommer automatiquement le fichier PGM en fonction du nom du fichier d’entrée
• Permettre de lire le fichier sur le flux standard d’entrée

Compétences mobilisées

• la lecture/écriture de fichier

Jeu de la vie et autres automates cellulaires.

L’objectif de ce mini-projet est de réaliser un programme implémentant un automate cellulaire. Un des automates cellulaires les plus connus est celui du Jeu de la vie de Conway.

Principe

On dispose d’une grille de cellules de dimensions Largeur x Hauteur où chacune des cellules est soit vivante, soit morte (il s’agit de l’état de la cellule). L’état de ces cellules évoluent simultanément suivant la règle locale suivante, pour chaque cellule

• on compte le nombre de ces 8 voisines qui sont vivantes
• si ce nombre est 2, la cellule conserve son état
• s’il est 3, la cellule devient vivante
• sinon la cellule devient morte.

On peut décrire cette règle aussi sous la forme :

• une cellule meurt si elle est isolée ou bien en cas de surpopulation
• une cellule naît si elle est entourée d’exactement 3 cellules vivantes.

À chaque étape, toutes les cellules évoluent en même temps (en changeant d’état ou en conservant leur état précédent).

Travail demandé

Écrire un programme qui prend en argument les dimensions de la grille, puis simule le jeu de la vie en affichant la grille étape par étape toutes les secondes. La grille initiale pourra être tirée aléatoirement.

Notes et conseils

• il peut être nécessaire d’allouer plusieurs tableaux
• isoler la fonction de transition (état de la cellule + états des cellules voisines -> nouvel état) permet d’envisager d’autres automates cellulaires

Améliorations possible

Le programme peut être enrichi avec différentes fonctionnalités :

• affichage graphique via ncurses ou MLV
• configuration initiale depuis un fichier
• changement d’état d’une cellule par un clic de souris
• choix du délai entre deux étapes
• implémentation d’autres automates cellulaires (plus d’états)

Compétences mobilisées

• la ligne de commande
• l’allocation dynamique
• les tableaux à deux dimensions

Convertisseur d’images dans les formats Portable pixmap

Il existe 6 variations de ce format correspondant à une combinaison d’un choix parmi noir/blanc, niveau de gris et couleur, avec un choix parmi textuel et binaire.

Travail demandé

Écrire un programme convertissant un fichier depuis un format vers un autre. Les options du programme seront contrôlées par les arguments dans la ligne de commande.

Notes

• On pourra supposer qu’aucun commentaire n’est présent dans le fichier
• Le format binaire noir/blanc P4 est plus exigeant que les autres.

Compétences mobilisées

• la ligne de commande
• la lecture/écriture de fichier
• l’allocation dynamique
• la manipulation de bits pour le format noir et blanc en binaire

Taille de fichier en UTF8

On souhaite déterminer si un fichier utilise l’encodage UTF-8 et combien de caractère Unicode il comporte le cas échéant.

Compétences mobilisées

• la lecture/écriture de fichier
• les opérations bits à bits

Arbre binaire de hachage

L’objectif est de créer un module permettant de représenter une structure d’ensemble (tel le premier TP d’algorithmique des arbres) en utilisant un arbre binaire de recherche. Les opérations devant être raisonnablement efficace, on utilisera le hachage des chaines de caractères dans les comparaisons plutôt que d’utiliser la chaine de caractère directement.

On pourra utiliser la fonction de hachage présentée dans le cours d’algorithmique et des structures de données du S3.

La suppression n’est pas demandé mais on s’attachera a libéré la mémoire allouée avant la fin du programme.

Compétences mobilisées

• la modélisation
• les opérations bits à bits
• l’allocation dynamique et la manipulation de pointeurs

Moteur physique pour particules

L’objectif est de proposer une simulation de déplacement de particules interagissant entre elles et avec la souris.

Une particule est caractérisé par sa position et sa vitesse. Une force peut être appliqué à une particule et impacte alors sa vitesse. La force exercée sur une particule peut provenir de la souris ou d’autres particules.

Par exemple, deux particules trop proches pourraient exercer l’une sur l’autre une force de répulsion. On pourrait avoir plusieurs types de particules (positive et négative, poule/renard/vipère…).

Formellement, le moteur fonctionne alors ainsi. À chaque mise à jour de l’affichage :

• Soit t le temps écoulé depuis le dernier affichage
• Pour chaque particule p :
  • force = interaction de la souris sur p
  • Pour chaque particule q :
    • force += interaction de q sur p
  • p.vitesse += force * t
• Pour chaque particule p :
  • p.position += p.vitesse * t

Compétences mobilisées

• la modélisation
• l’utilisation d’une bibliothèque externe (MLV, SDL, OpenGL)

Table de hachage

L’objectif est proche de celui du TP Compteur les mots (voir plus bas) mais est axé sur l’implémentation (guidée) d’une table de hachage.

Le sujet se trouve ici et les fichiers complémentaires sont dans l’archive suivante.

Compétences mobilisées

• la modularisation
• l’allocation dynamique
• les pointeurs de fonction
• la lecture de fichier

Compléments

1. Introduction à Ncurses (pdf) — Cette fiche contient divers exercices de découverte de la bibliothèque ncurses.