Remarques sur la page (ou le sujet) : contact.
mentions légales
,
,
Dernière révision: le 08-12-2010 à 21:12.
Le TP est à rendre (par email) pour le dimanche 12 décembre à 23h59
Pour des raisons évidentes de météo, le TP ne pourra pas se dérouler normalement. Pour des raisons d'emploi du temps chargé, il semble difficile de déplacer le TP. Nous allons donc essayer de faire le TP à distance (pour ceux qui peuvent).
Le sujet étant en ligne, vous devriez pouvoir y accéder.
Pour nous contacter, vous pouvez utiliser
pierre.hyvernat@im.apinc.org ou xavierprovencal@gmail.com.
Pour utiliser Jabber, le plus simple est d'utiliser le logiciel Pidgin (paquet Ubuntu) et de se créer un compte Jabber / XMPP :
im.apinc.org
Si vous disposez d'une adresse @gmail.com, vous pouvez l'utiliser directement...
Je ne peux malheureusement pas vérifier si Pidgin est installé en Mauriennes, et pour des raisons évidentes de météo, la DSI fonctionne avec un personnel très réduit...
Les autres clients possibles pour utiliser Jabber / XMPP sont :
Pidgin
Gajim
Empathy (Gnome)
Kopete (KDE)
Coccinella
Si aucun de ces logiciels n'est installé dans les salles du bâtiment Mauriennes et que vous n'avez pas de portable accessible, utilisez alors l'email pour vos questions...
Pour ce TP comme pour les suivants, la pièce la plus importante sera un fichier tp1-nom-prenom.c contenant votre programme. Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront également pris en compte :
Les réponses aux questions posées dans le TP (complexité de vos fonctions par exemple) seront insérées comme commentaires dans votre fichier principal.
Si vous le souhaitez, vous pouvez aussi envoyer un rapport de TP. Le format de ce rapport sera au choix, mais par ordre de préférence :
.odt),
Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :
-Wall -Werror -Wextra -pedantic -std=c99
Téléchargez l'archive du TP1. Après un
$ tar xvf info505-tp1.tar
vous devriez avoir un répertoire info505-tp1 contenant plusieurs fichiers :
graphes.h : les entêtes et les types pour les fonctions prédéfinies sur les graphes,
graphes.o : le fichier objet correspondant,
tp1.h : le fichier d'entêtes pour les fonctions que vous devrez faire pour le TP1,
tp1-hyvernat-pierre.c : le fichier squelette pour le TP1,
test.c : une fonction main minimale pour tester vos fonctions,
Makefile : mon fichier Makefile,
G1, G2, G3 et G4 : des petits exemples de graphes.
Vous ne devez pas modifier les fichiers graphes.h ou tp1.h. Le fichier sur lequel vous travaillerez est tp1-nom-prenom.c. Un exemple de tels fichier est inclus dans l'archive : tp1-hyvernat-pierre.c. Vous pouvez l'utiliser comme point de départ.
Pour la compilation, le plus simple est d'utiliser le fichier Makefile fourni. Il suffit de l'ouvrir dans un éditeur de texte et de modifier la ligne
NOM = tp1-hyvernat-pierre
tp1-nom-prenom.c.) Ensuite, il suffit d'utiliser la commande
$ make
pour recompiler tout votre TP.
Votre fichier tp1-nom-prenom.c ne contient pas de fonction main() : celle ci se trouve dans le fichier test.c. Pour tester vos fonctions au fur et à mesure, vous pouvez :
main du fichier test.c,
main()) et modifier la ligne
TEST = test
Makefile.
Le fichier Makefile produit automatiquement un exécutable test qui contient le code de la fonction main().
Avant d'envoyer votre fichier tp1-nom-prenom.c, n'oubliez pas d'ajouter les options de compilation dans le fichier Makefile (voir les consignes) et de testez sur la fonction de test originale. (C'est ce que je ferais...)
Lisez le début du fichier graphes.h pour voir un peu quelles fonctionnalités vous sont fournies.
La bibliothèque propose deux types de données pour les graphes :
GrapheListe pour un graphe représenté sous forme de listes d'adjacences,
GrapheMatr pour un graphe représenté sous forme de matrice d'adjacence.
Dans les deux cas, si G est un graphe, vous avez accès au nombre de sommets avec G->nb_sommets. Pour accéder au tableau de listes d'adjacences, il faut faire G->Adj et pour accéder à la matrice, il faut faire G->Matr.
Les listes d'adjacences sont des listes chaînées :
NILL (une macro pour le pointeur NULL),
L est une liste, le premier sommet de L est L->but, et la suite de L est L->suivant.
Pour accéder à un élément de la matrice, on utilise G->Matr[i][j].
On stocke également un poids (nombre entier) pour chaque arc. Dans le cas d'une matrice d'adjacence, le poids est stocké directement dans la matrice ; dans le cas d'une liste d'adjacence, on stocke le poids du premier arc dans L->poids.
Vous avez du voir la notation G.Adj pour accéder au champs Adj dans G. La notation G->Adj fait la même chose quand G est un pointeur. C'est donc un synonyme de (*G).Adj.
Vous devriez voir tout ça dans votre cours de C...
Le fichier graphes.h vous donne également les prototypes de quelques fonctions pour manipuler ces types :
ajoute() pour ajouter un arc dans une liste,
grapheListeVide() pour initialiser un graphe vide (listes d'adjacences),
grapheMatrVide() pour initialiser un graphe vide (matrice d'adjacence),
grapheListeAleatoire() pour créer un graphe aléatoire,
lireGrapheListe() pour lire la description d'un graphe dans un fichier.
Reportez-vous aux commentaires dans ce fichier pour savoir comment utiliser ces fonctions.
Attention : un graphe contient des données mutables (modifiables). Vous ne devez pas modifier un graphe lorsque vous le donnez en argument à une fonction.
Le fichier contient également un type de données Tile, qui permet de faire des piles ou des files d'arcs :
tileEstVide(),
entile(),
defile(),
depile().
Pour le moment, vous n'avez besoin que de files de sommets (nombres entiers). Les tiles sont des listes chaînées d'arcs, avec une origine, un but et un poids. Vous n'avez donc qu'à utiliser un des champs des tiles et vous pouvez ignorer les autres. D'autre part, la fonction defile() utilise un pointeur. Vous utiliserez donc les files de la manière suivante :
Tile F = tileVide() ;
t dans la file F :
entile(t, 0, 0, F) ;
0 en arguments 2 et 3 car je n'en ai pas besoin. (Je pourrais tout aussi bien mettre 42...)
F dans la variable t (de type int) :
defile(F, &t, NULL, NULL) ;
& » devant le t vient du fait que l'on veut récupérer la valeur dans la variable t : on doit donc passer l'adresse de t. Pour les arguments 3 et 4, on peut passer le pointeur NULL car on ne demande pas leurs valeurs.
Vous n'avez pas encore vu les pointeurs, ni le lien entre pointeurs et tableaux dans le langage C. Pour ce TP, vous pouvez considérer que le type int* veut dire tableau d'entiers de taille inconnue. Par exemple, le prototype
int* distances (GrapheListe G, int a);
Pour allouer un tableau dynamique (dont la taille n'est pas connue à la compilation) non local à une fonction (sur lequel on veut faire un return), il faut utiliser la syntaxe suivante :
int *sommets = malloc(n * sizeof(int));
n entiers dans le tas. Ce tableau a donc une durée de vie supérieure à la fonction dans lequel il est défini.
Une déclaration int sommets[n] déclarerait le tableau dans la pile, et disparaîtrait donc hors de la fonction... (Ceci n'est valide qu'à partir de la norme C99.)
Écrivez une fonction de prototype
void afficheGrapheListe (GrapheListe) ;
Par exemple :
$ ./test Le graphe a 8 sommets : 0 ---> 3 0 ---> 2 0 ---> 1 4 ---> 5 5 ---> 5 Le graphe a 5 arcs.
Écrivez les deux fonctions de conversion
GrapheMatr listeVersMatrice(GrapheListe) ; GrapheListe matriceVersListe(GrapheMatr) ;
N'oubliez pas de tester vos fonctions...
Écrivez une fonction
GrapheListe transpose(GrapheListe) ;
Qu'elle est la complexité de votre fonction, en fonction de n (nombre de sommets) et m (nombre d'arc) ?
Programmez l'algorithme du parcours en largeur vu en cours.
Pour changer un peu, au lieu de renvoyer un tableau pere[] contenant la foret du parcours, renvoyez un graphe Pere. (Une foret est un type particulier de graphe...)
Le prototype de votre fonction est donc
GrapheListe parcoursLargeur (GrapheListe G) ;
Programmez une fonction
int* distances(GrapheListe G, int a) ;
a vers tous les autres sommets (ou -1 s'il n'y a pas de chemin approprié.)
Déduisez-en une fonction
int distance(GrapheListe G, int a, int b) ;
a et b dans le graphe G.
Qu'elle est la complexité de votre fonction, en fonction de n (nombre de sommets) et m (nombre d'arc) ?
Le diametre d'un graphe, c'est le maximum de toutes les distances entre les sommets du graphes...
Écrivez une fonction
int diametre(GrapheListe G, int *a, int *b) ;
a et b.
Qu'elle est la complexité de votre fonction, en fonction de n (nombre de sommets) et m (nombre d'arc) ?
Cette fonction prend en argument deux pointeurs vers des entiers. Elle n'utilise pas les valeurs entières correspondantes mais les modifie pour donner les numéros des sommets.
Votre fonction se terminera donc probablement par quelque chose comme :
int diametre(GrapheListe G, int *a, int *b) { ... ... *a = s1 ; *b = s2 ; return(d) ; }
... int d, s, t ; d = diametre(G, &s, &t) ; printf("Le graphe a un diamètre de %i ; %i et %i sont deux sommets éloignés de cette distance.\n", d, s, t) ; ...
scanf().)
Un labyrinthe peut être vu comme un graphe non-orienté : chaque sommet est une pièce et les arêtes sont des portes.
Si on impose qu'il y ait exactement un chemin entre chaque pièce, le graphe du labyrinthe est en fait un arbre...
Écrivez une fonction
int* resoudLabyrinthe(GrapheListe G, int entree, int sortie) ;
G à partir du sommet entree et cherche un chemin vers le sommet sortie.
Votre fonction renverra le morceau du tableau pere[] créé par le parcours.
Écrivez une petite fonction afficheChemin(int *pere, int entree, int sortie) qui affiche les sommets pour aller de entree à sortie en utilisant l'information contenue dans le tableau pere. Par exemple :
- départ du sommet 12, - aller au sommet 5, - aller au sommet 6, - aller au sommet 22, - aller au sommet 0, - arrivée au somme 42 !
Que pensez-vous de cette méthode pour résoudre un labyrinthe « à la main » ?
Pour tester votre fonction, vous pouvez aussi utiliser les fonctions un peu plus visuelles suivantes :
labyrintheRect() et afficheGrilleRect(),
labyrintheHex() et afficheGrilleHex(),
qui permettent de créer et d'afficher un labyrinthe sur une grille rectangulaire ou hexagonale :
+--+--+--+--+--+--+--+--+--+--+ __ __ __ __ __
| | | | | | / \__/ \__/ \__/ \__/ \__
+ + + +--+ +--+--+--+ + + \ / \ / __/ __ \
| | | | / __ \__/ \__ __/ \__/
+ +--+ +--+ + +--+ +--+--+ \__/ \__/ \ __ \
| | | | | | | / \__/ \__ \ \__/ \__/
+ +--+--+ + +--+--+ +--+ + \__ __ \ / \__/ __ \
| | | | | | / __/ \__/ __/ \ / __/
+ + +--+--+--+--+ + + + + \__/ __ __/ \ / \__ \
| | | | | | | / \__ \__ \__/ \ /
+ +--+ +--+ +--+--+--+--+ + \__/ \__/ \__/ __/ \__ \
| | | | | | | / __ / __/ \ / /
+--+--+ + + +--+ +--+ +--+ \__/ \__/ __/ \ / \__/ \
| | | / __ \ / __/ \ /
+ + +--+--+--+--+--+--+--+ + \__/ \__ \__/ __/ __ \
| | | | | / \__ \__/ __/ \ /
+ +--+--+--+ +--+--+ +--+--+ \__ __ \__/ \__ \ / \
| | | / __/ __/ \__/ \__ \ /
+--+ +--+ + +--+--+ +--+ + \__/ __/ __ __ __/ \
| | | | | / / __ \ / \ / \ /
+--+--+--+--+--+--+--+--+--+--+ \__/ __/ __/ __/ __/ \
\__/ \__/ \__/ \__/ \__/
Écrivez une fonction
char *transformePere(GrapheListe G, int *pere, int a, int b) ;
S[] utilisable par les fonctions afficheGrilleRect() et afficheGrilleHex().
Par exemple, si votre fonction test contient
depart = 0; arrivee = 90; G = labyrintheHex(10,10); pere = resoudLabyrinthe(G, depart, arrivee); S = transformePere(G, pere, arrivee, depart); afficheGrilleRect(G,10,10,S);
$ ./test __ __ __ __ __ __ __ __ __ __ / @\__/ \__/ \__/ \__/ \__/ .\__/ .\__/ \__/ \__/ \__ \ / . __/ .\ / / / $\ . __ . __/ \__ __ \ / . / .\ .\ / \__/ \__ .\ / / \__ \__/ \ / \ / . __ .\ / \__ __ \__/ \__/ .\ __ / \ / \__/ \__/ . __ \ \__ \__/ / \ \__/ __/ \__/ \__ \__ .\__/ \__/ \__/ \__/ . / \__/ \__/ \ / __/ \__ .\ / __ __ . __/ \__/ \ / / \ \__/ \ / . __/ \__/ \__/ . / \__ \__ __/ \ / \__ \__/ . / \__/ __ .\ / \ / \__ / \ / \ \__ . __/ \ / \ / \ .\__/ __/ \ / \__ \ / \__/ / .\__/ . __/ \ / .\ / __/ \ / \__/ / \__/ / .\ . / .\__/ \ / \__ \__ \__/ __/ \ / \__/ \ .\__/ . / / .\__/ \__ \__ \__/ \__/ \__ / \__/ __/ .\__/ . __ __/ \ \ / \__ \ / \__/ \ / \__/ .\ \__ \ / \__ __ \ / \ / \__/ \ / \__/ \ .\ / \__ / \__/ __/ \ / \__ \ \ / __/ \__/ \__ __/ \__ __ \ / \ \ \__/ \__/ __/ \__/ __/ / \ / __ \ / \ \ __/ / __ \ / \__/ / \ / __/ \__/ \__/ \__/ __/ __ \__/ __ \__/ \__/ \__ \ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/
(bonus)
Les questions 4, 5 et 7 utilisent toutes un parcours en largeur. Programmez un parcours en largeur générique qui permette de définir les fonctions parcoursLargeur(), distances(), distance() et resoudLabyrinthe().
Redéfinissez ces fonctions pour utiliser votre nouveau parcours.
Remarques sur la page (ou le sujet) : contact.
mentions légales
,
,
Dernière révision: le 08-12-2010 à 21:12.