Cours
Les cours en ligne sont les transparents de présentation, ils ne remplacent pas les cours en amphi.
- introduction : motivation, représentation en machine, algorithmes de parcours (transparents de présentation). Vidés : boids et graphe d'interactions des boids
- tour eulérien et problème du postier chinois.
- Quelques notes de cours sur le plus court chemin (bientôt). Un code en C pour le calcul des plus courts chemins par l'algorithme de Floyd. Cette implémentation utilise le fichier d'entête manipulation-matrice.h. N'oubliez pas de lier la bibliothèque mathématique (-lm) lors de la compilation.
- Quelques notes de cours sur les algorithmes de détermination des arbres couvrants.
- Quelques notes de cours sur les flots dans les réseaux de transport. L'archive fordfulkerson.jar permet d'exécuter cet algorithme sur des réseaux générés aléatoirement. Pour l'utiliser, lancez-le directement java org.miv.graphstream.enseignement.FordFulkerson ou bien avec des paramètres : java org.miv.graphstream.enseignement.FordFulkerson 3 5 1 20 où 3 correspond au nombre de colonnes du réseau, 5 au nombre de lignes, 1 à la capacité minimum des liens et 20 à leur capacité maximum.
Travaux pratiques
Les séances de travaux pratiques privilégient deux langages : C et java. En C nous verrons comment manipuler des matrices et des structures de voisinage. Les TP en java s'appuieront sur une bibliothèque développée au LITIS. Si vous désirez avoir cette bibliothèque disponible sur votre propre ordinateur, il suffit d'installer GraphStream. Pour cela, rendez-vous sur graphstream.sourceforge.net.
TP
- Première séance : codage en C des matrices d'adjacence, et des structures de voisinage. Langage utilisé : C, sujet et données. Une aide à la programmation en C
- La seconde séance de travaux pratiques est dédiée à l'étude et au codage de quelques algorithmes de graphes fondamentaux : les algorithmes de parcours en largeur et en profondeur. Si vous éprouvez quelques difficultés en C, vous pouvez vous inspirer des codes sources proposés dans l'archive du TP pour le codage des structures de pile et de file en C. sujet, données et codes. sujet seul en pdf
- Séance de travaux pratiques numéro 3 :
- Parcours maths et maths-info : codage de l'algorithme du tour eulérien. Attention à vérifier la connexité du graphe et quelques autres petites subtilités discutées en cours.
- Parcours info : installation de la bibliothèque GraphStream. Installation sur votre compte (cette étape fait partie du TP). Application : codage de l'algorithme du tour eulérien.
TP : éléments de correction
- Quelques éléments de correction pour le tp1. Les codes qui vous sont proposés fonctionnent. Ils ont été testés, toutefois il se peut que quelques coquilles aient déjouées ma vigilance. Si vous en découvrez une, avertissez-moi que je fasses le nécessaire pour l'éliminer. Tous les codes qui vous sont proposés sont, au mieux, des exemples de codes fonctionnels, ils ne prétendent pas être les mieux écrits, ni les plus efficaces.
Foire aux questions
Cette rubrique est pour vous. Si vous avez des questions sur le cours de graphes ou sur les séances de travaux pratiques, envoyez-moi un courriel et je poste la réponse ICI.
Manipulation d'une archive :
- lorsque vous récupérez un fichier toto.tgz, il s'agit d'une archive (tar) compressée (gz).
Pour récupérer le contenu, il convient de le décompresser et d'extraire les fichiers de l'archive :
- pour décompresser : gunzip toto.tgz (le résultat est un fichier toto.tar)
- pour extraire les fichiers de l'archive tar xvf toto.tar (le résultat est un ensemble de fichiers qui sont maintenant utilisables. En général, un répertoire est créé du même nom que l'archive)
- en une fois il est possible à la fois de décompresser et d'extraire les fichiers de l'archive : tar xvfz toto.tgz
- pour une archive compressé du type toto.tar.bz2 :
- pour décompresser : bunzip2 toto.bz2 (le résultat est un fichier toto.tar)
- pour extraire les fichiers de l'archive tar xvf toto.tar (le résultat est un ensemble de fichiers qui sont maintenant utilisables. En général, un répertoire est créé du même nom que l'archive)
- en une fois il est possible à la fois de décompresser et d'extraire les fichiers de l'archive : tar xvfj toto.tgz
Aides
Langage C : aide à la programmation.
Fichiers DGS
Quelques grilles en dgs : ICI