Notes sur le Cours Langages et Concepts de Programmation

*
Eniac *


-=-

Le cours

Les encadrants

Petits problèmes informatiques amusants

Recherche opérationnelle

Autres documents


-=-

Le cours

Support de cours

Le polycopié (format PDF)

Séance 1

Commencer les exercices du chapitre 1 (pages 33 et 34) : 1.3.1, 1.3.2, 1.3.3.

Le corrigé des trois premiers exercices en PDF, en HTML, et les programmes sources affarg.c, strcmp.c et atoi.c .

Séance 2

Suite (et fin) des exercices du chapitre 1 (pages 34 et 35) : 1.3.4, 1.3.5.
Si vous avez fini, lisez l'énoncé de l'exercice 2.3.1 (page 55) ; puis téléchargez le fichier de voitures voitures.txt.
Ecrivez un programme qui admet un argument qui est le nom d'un fichier conforme au format indiqué et qui extrait le nom du modèle le plus cher.
Note : votre programme devra présenter un minimum de robustesse ; par exemple, il pourra ignorer les lignes non conformes au format, mais continuer son analyse du reste du fichier.

Et s'il reste encore du temps, regarder les exercices 1.4.1, 1.4.2 et 1.4.3 (récupérer le fichier matmult.c).

Le corrigé des exercices 1.3.4 et 1.3.5 : en PDF, en HTML.

Les codes sources des programmes correspondants : affint-v2.c, comptecl.c.

Séance 3

On commence par l'exercice 2.3.1 (manipulation de fichiers de voitures), dont l'énoncé est aux pages 55 et 56 du polycopié.
On trouvera ici un exemple de fichier de voitures : voitures.txt.
Voici un premier programme qui contient un exemple de structure de données pour stocker une voiture, ainsi qu'une procédure qui permet de trier un tableau de telles structures : voitures.c.
Pour ne pas rester bloqué...
Quelques indications : en HTML, en PDF.
Un corrigé pour cet exercice est disponible : en HTML, en PDF.
Le programme source correspondant est disponible ici.

Séance 4

On commence par la fin de l'exercice sur le tri d'un fichier de voitures (lire le fichier d'indications ci-dessus).
Et s'il reste encore un peu de temps, le sujet du jour (application de gestion de comptes bancaires) est dans le polycopié, page 56. Commencer par le liminaire, en récupérant le programme source basebank.c (utiliser le téléchargement de fichier en cliquant sur le bouton de droite de la souris, pas le copier-coller !).

Quelques indications pour avancer : en HTML, en PDF.

Un corrigé pour la gestion des comptes bancaires : en HTML, en PDF.
Et le programme source correspondant : bank.c.

Séance 5 (listes)

Commencer par télécharger le programme source list_entier.c qui reprend les morceaux de code du polycopié (chapitre 3) : définition de la structure de données list_entier et procédures list_print(), list_length(), elem_new(), elem_free(), list_push(), list_insert(), list_append().
Puis entamer les exercices du chapitre 3 : 3.2.1 (création de liste), 3.2.2 (recherche d'un nombre dans une liste), 3.2.3 (suppression d'un élément).

Un exemple de programme qui implémente les procédures demandées : tp5.c.
On y compare (en termes de temps de calcul) la création d'une liste à un million d'éléments par insertion en tête et la création d'une liste à cent mille éléments par insertion en queue.

Séance 6

On termine les exercices du chapitre 3.

On commence par l'exercice 3.2.4 (création de liste triée).

Et on poursuit par l'exercice 3.2.5 (gestion d'ensembles d'entiers).

Voici un corrigé possible pour ces exercices : en PDF, en HTML.
Et le programme source correspondant est disponible ici : iset.c.

Séance 7

Implémenter le tri par fusion (voir le paragraphe 4.1.1.3) d'une liste d'entiers.

Voici un corrigé possible pour ces exercices : en PDF (désolé, pas de version HTML).
Et le programme source correspondant est disponible ici : trifus.c.

L'équipe pédagogique


Michel BEIGBEDER
Bureau 406 (Espace Fauriel)

Yann GAVET
Bureau J2.05b (CIS, 158)

Jean-Jacques GIRARDOT
Bureau 408 (Espace Fauriel)

Mihaela MATHIEU
Bureau 412 (Espace Fauriel)

Antoine PAUZE
Bureau 429 (Espace Fauriel)

Marc ROELENS
Bureau D2.11 (DFG, 158)

Xavier SERPAGGI
Bureau 425 (Espace Fauriel)

Antoine ZIMMERMANN
Bureau 422 (Espace Fauriel)

Petits problèmes informatiques (et mathématiques)

Remarques, questions, commentaires... sont à adresser à
Marc Roelens

Une petite colle arithmétique

Un enseignant choisit deux nombres entiers distincts entre 2 et 100 (inclus) : à l'un des élèves (Paul), il confie le produit des deux nombres ; à un autre élève (Serge), il confie la somme des deux nombres.
Puis il demande : quels sont ces deux nombres ?
Paul dit : je ne peux pas les deviner !
Serge dit : je le savais !
Paul dit : alors, je les connais !
Serge dit : et bien moi aussi !
Sauriez-vous déterminer ces deux nombres ?
Indication : il pourra être utile d'écrire (après pertinente réflexion mathématique) un ou deux petits programmes en C...

Mais que fait donc ce programme ? (informatique expérimentale)

Voici un petit programme très simple (4 lignes, 108 octets) : biz.c.
Sa syntaxe peut surprendre : il est en fait écrit selon l'ancienne syntaxe du langage C, dite K&R pour Kerningham et Ritchie, du nom des deux créateurs du langage (avant la normalisation ANSI).
Il suffit de savoir qu'un paramètre de procédure non typé est implicitement de type int.
Arriveriez-vous à comprendre en le lisant ce que fait ce programme ?
Arriveriez-vous à comprendre en l'exécutant ce que fait ce programme ?

Un grand classique

La SCI (Société Chaotique d'Investissement) propose le placement suivant : Déterminer la valeur de l'action au bout de 40 ans.
Indication : essayer d'abord de faire des calculs avec des flottants de type float, puis de type double, puis de type long double (extension non normalisée).
Essayer ensuite de résoudre le problème mathématiquement.

Des francs et des euros

Dans le cours d'introduction à l'informatique, on a programmé la conversion entre francs et euros. On a vu que cette conversion pouvait poser des problèmes de précision (voir par exemple le programme euro.c).
Pourriez-vous écrire une fonction en C qui convertit une somme en francs (connue par un nombre entier de francs et un nombre entier de centimes) en une somme en euros (connue par un nombre entier d'euros et un nombre entier de cents) en respectant à la lettre la règle officielle de conversion ?

Un consommateur encore peu habitué aux euros effectue avant chaque achat une conversion de la somme en euros vers une somme en francs. Alors qu'il s'apprête à acheter un produit dont le prix est inférieur à 100 euros et entier, il a la surprise de constater que la somme exprimée en francs est aussi entière ! Quel est donc le prix du produit ?

Question subsidiaire : ce résultat était-il prévisible mathématiquement ?

Recherche opérationnelle

Travaux pratiques 2013

Le sujet du TP : le calcul de cycles eulériens dans un graphe non orienté, en utilisant l'algorithme de Rosenstiehl. Quelques documents utiles :
Pour commencer
Récupérer le fichier suivant : gr_test.c.
Il contient : Vous pouvez télécharger le fichier (ainsi que les fichiers associés), le compiler, le tester sur le fichier ro-td1-1314.txt.
Pour rendre votre travail
Si vous le souhaitez, vous pouvez envoyer le programme réalisé : il sera évalué, cette évaluation se traduisant par des points de bonus sur la note de l'examen écrit de RechOp.
L'envoi du travail réalisé se fait par mail, en respectant strictement les instructions suivantes :

Travaux pratiques 2012

Le sujet du TP : le calcul de plus courts chemins dans un graphe orienté valué positif, en utilisant l'algorithme de Dijkstra. Quelques documents utiles :
Pour commencer
Récupérer le fichier suivant : gr_test.c.
Il contient : Vous pouvez télécharger le fichier (ainsi que les fichiers associés), le compiler, le tester sur le fichier ro-td2-1213.txt.
Pour continuer
Les étapes suivantes du travail (programmation de l'algorithme de Dijkstra qui calcule les plus courts chemins à partir du sommet X) consistent à :
Des solutions
Voici quatre implémentations de l'algorithme de Dijkstra, à partir du programme d'exemple fourni. Ces solutions diffèrent par la technique utilisée pour représenter les ensembles de sommets : Ces quatre fichiers sont identiques sur une grande partie (jusqu'à la ligne 346).

Travaux pratiques 2011

Le sujet du TP : un problème de réseau autoroutier optimal, utilisant la notion d'arbre recouvrant minimal, et l'algorithme de Kruskal. Quelques documents utiles :
Pour commencer
Récupérer le fichier suivant : gr_test.c.
Il contient : Vous pouvez télécharger le fichier (ainsi que les fichiers associés), le compiler, le tester sur le fichier ro-td2.txt.
Pour continuer
Les étapes suivantes du travail (programmation de l'algorithme de Kruskal) consistent à : On peut commencer par implémenter l'algorithme en utilisant comme méthode d'union-find un simple tableau des classes. Puis on peut essayer des méthodes plus rusées (voir le document sur la technologie union-find).
Correction des travaux pratiques
Un corrigé est disponible : en format HTML, en format PDF.
Le code source correspondant est disponible : ici.
Pour le compiler : Quelques fichiers de données (comprimés avec gzip) :

Travaux pratiques 2010

Le sujet du TP : un problème de constitution d'équipes. Un énoncé et un corrigé (algorithmique) sont disponibles ici.
Les données du problème sont accessibles sous forme d'un fichier texte simple. Voici trois fichiers correspondant au TD (6 personnes) : td1-1.txt, td1-2.txt et td1-3.txt.
Un exemple de programme qui traite ces fichiers est disponible ici (cliquer avec le bouton droit, plus choisir Télécharger le fichier).
Quelques explications pour réaliser le programme voulu sont disponibles ici.
Nouveau (pour ne pas rester bloqué) Quelques explications complémentaires sont disponibles ici.
Des fichiers de données pour des tailles de problème plus importantes sont disponibles : Il peuvent servir à mettre en évidence le temps de calcul par l'algorithme de force brute.
Une fois l'algorithme de bicoloriage programmé, on peut traiter des problèmes encore plus importants :

Travaux pratiques 2009

Le sujet du TP : un problème d'emploi du temps. Un énoncé et un corrigé (algorithmique) sont disponibles ici.
Les données du problème sont accessibles sous forme d'un fichier texte simple. Voici un fichier correspondant au TD (4 profs, 5 classes) : pb04x05.txt.
Voici un fichier correspondant au TD initial (5 profs, 8 classes) : ro-td1.txt.
Voici un fichier avec un exemple plus important (8 profs et 16 classes) : pb08x16.txt.
Et pour finir un fichier encore plus gros (24 profs et 40 classes) : pb24x40.txt.

Pour commencer, voici un petit programme C qui teste la validité d'un fichier de données. On y définit une structure pour stocker un emploi du temps. Vous pouvez le télécharger et vous en servir de base pour votre propre programme (après l'avoir lu et compris !).
Pour ne pas rester bloqué
Voici un nouveau programme : edt-naif.c.
Ce programme implémente deux algorithmes simples : Encore une fois, vous pouvez télécharger ce programme et vous en servir de base pour votre propre programme (après l'avoir lu et compris !).
Pour rendre votre travail
Le travail réalisé est à envoyer par mail, en respectant strictement les instructions suivantes :
Un corrigé
Voici un programme qui implémente l'algorithme de König, permettant de trouver un emploi du temps avec un nombre de couleurs égal au degré maximal du graphe biparti : edt-konig.c.
Ce programme est assez verbeux (il détaille arc par arc son travail) ; vous pouvez le tester sur un fichier de taille importante (50 professeurs, 60 classes) : pb50x60.txt.

Travaux pratiques 2008

Le sujet du TP : en HTML, en PDF.
Les fichiers fournis : le programme planning.c, le fichier de tâches planex.tch.

Pour ne pas rester bloqué, un document pour avancer : en HTML, en PDF.

Cours 2008

Un corrigé pour l'exercice de localisation de dépôts (Branch and Bound) : en PDF, en HTML.

Examen 2007

Un corrigé : en PDF, en HTML.

Sujet 2007 : problème de transfèrement

Le sujet : en HTML, en PDF

Un corrigé : en HTML, en PDF

Un petit guide pour démarrer le TP : en HTML, en PDF

Quelques fichiers utiles :

Pour avancer : quelques indications supplémentaires.

Et le fichier source qui intè la lecture des donnés, l'affichage du problème, l'affiche d'une solution : step1.c.

Sujet 2006 : localisation de dépôts (méthode SEP)

Un petit guide méthodologique pour programmer une recherche SEP en C : en format PDF, en format HTML.

On y détaille l'implémentation d'une recherche SEP pour le problème du voyageur de commerce : voici le programme source babtsp.c correspondant.

Voici également un fichier de données correspondant au problème traité dans le poly : tsp.txt.

Voici un fichier de données correspondant au problème de la tournée des préfectures de région (21 sommets, 63 arêtes) : pref2.txt.

Autres documents

Améliorer l'interface d'un programme

Pour avoir un peu mieux que l'interface ligne habituelle, on peut utiliser la bibliothèque de fonctions ncurses : le terminal devient alors adressable, et on peut écrire des caractères n'importe où (pas seulement en bas du terminal). Voici un exemple d'utilisation de ces fonctions : curs_ex.c.
Sous Linux, pour compiler un programme utilisant ces fonctions, il suffit d'ajouter une option sur la ligne de compilation :
  $ gcc -Wall -ansi -pedantic monprog.c -lncurses -o monprog

Pour faire du graphique simple (créer une fenêtre graphique pour y tracer des lignes, des textes, des cercles), on peut utiliser la bibliothèque Vogle (Very Ordinary Graphic Learning Environment). Voici un package précompilé pour Linux, les instructions d'installation, et un petit exemple vex1.c.
Les amateurs de la marque à la pomme pourront trouver ici un package précompilé pour MacOS Snow Leopard (Intel), en mode 32 bits (utilisez l'option -m32 pour le compilateur gcc).
On trouvera ici une version du code source, avec des Makefiles pour Linux et Darwin.
On peut utiliser Vogle pour saisir des clics de souris et améliorer encore l'interface avec le programme (attention : on est encore loin d'une véritable interface graphique avec menus, boutons, etc.). Un programme d'exemple est fourni : vex2.c.

Divers

Une courte Foire aux Questions à propos de C

Un document décrivant les différents modes de fonctionnement des fenêtres de type terminal, et expliquant en particulier comment lire individuellement des caractères. Au format HTML ou au format PDF.

Un document sur la compilation séparée et la modularité des programmes C. Au format HTML ou au format PDF.

Un document sur les caractères et les chaînes de caractères en C : format HTML, format PDF.