http://os-vps418.infomaniak.ch:1250/mediawiki/api.php?action=feedcontributions&feedformat=atom&user=Durandmo 2026-06-10T03:17:56Z Contributions MediaWiki 1.39.4 http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO632_:_algorithmes_de_graphes&diff=6434 2014-05-13T13:43:47Z

<p>Durandmo : /* Algorithmes */</p> <hr /> <div>Cours du semestre 6 de la licence STIC INFO.<br /> <br /> * Responsable pour 2010--2011: Pierre Hyvernat.<br /> * Responsable pour 2011--2012: Xavier Provençal.<br /> * Responsable pour 2012--2013: Xavier Provençal.<br /> * Responsable pour 2013--2014: Xavier Provençal.<br /> * Xavier Provençal (CM/TD/TP).<br /> <br /> <br /> &lt;!-- Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». La participation au wiki est fortement encouragée. <br /> <br /> #Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style ''PrenomNom''...)<br /> <br /> #Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.--&gt;<br /> <br /> <br /> ===TD et TP===<br /> <br /> TD1 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD1.pdf Première feuille de TD]<br /> <br /> TD2 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD2.pdf Deuxième feuille de TD]<br /> <br /> TD3 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD3.pdf Troisième feuille de TD]<br /> <br /> TD4 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD4.pdf Quatrième feuille de TD]<br /> <br /> TD5 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD5.pdf Cinquième feuille de TD]<br /> <br /> TD6 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD6.pdf Sixième feuille de TD]<br /> <br /> TP : [http://www.lama.univ-savoie.fr/~provencal/INFO632/TP/index.html Énoncé des TP]<br /> <br /> <br /> &lt;!--<br /> <br /> ===Compléments de cours / TD / TP===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursProfondeur.pdf Algorithme du parcours en profondeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.]<br /> --&gt;<br /> <br /> ===Algorithmes===<br /> <br /> [https://www.youtube.com/watch?v=vYv8MhxCO00 Parcourt en Profondeur (DFS) 1/2]<br /> <br /> [https://www.youtube.com/watch?v=zEKRCDSxYXg Parcourt en Profondeur (DFS) 2/2]<br /> <br /> <br /> <br /> [https://www.youtube.com/watch?v=JucGeygpzFw Parcourt en Largeur (BFS) 1/2]<br /> <br /> [https://www.youtube.com/watch?v=0rH7OgcM6eA Parcourt en Largeur (BFS) 2/2]<br /> <br /> <br /> [https://www.youtube.com/watch?v=-3YIKISpTsQ Arbres Couvrants Minimum (Prim)]<br /> <br /> <br /> [https://www.youtube.com/watch?v=ocYYUiCTqI8 Algorithme Ford-Fulkerson (avec capacités aux noeuds)]<br /> <br /> <br /> [https://www.youtube.com/watch?v=Z5B_Ruz1woI A* (un algorithme pour super mario); excerpt]<br /> <br /> <br /> [https://www.youtube.com/watch?v=WOTOjbHBEXY Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 1/2 ]<br /> <br /> [https://www.youtube.com/watch?v=c57gOxo4hWo Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 2/2 ]<br /> <br /> <br /> [https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp]<br /> <br /> ===Ouvrage de référence===<br /> <br /> La partie « Algorithmes sur les graphes » du livre « ''Introduction à l'algorithmique'' » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...<br /> <br /> <br /> === Documents remis en classe ===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/parcours.pdf Parcours de graphes, en largeur et en profondeur.]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/algos_minimisation.pdf Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).]<br /> <br /> == Déroulement (2013-2014) ==<br /> <br /> * (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre et forêt. Représentation de graphes ( matrice vs listes ).<br /> * (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): Représentation de graphes (suite et fin). Parcours de graphes, parcours en largeur, parcours en profondeur.<br /> * (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Prim.<br /> * (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.<br /> * (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> <br /> <br /> <br /> == Déroulement (2012-2013) ==<br /> <br /> * (Cours 1): 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes.<br /> * (TD 1): 19 septembre. Représentation de graphes, propriétés élémentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): 25 septembre. Arbres, forêts et arbres couvrants. Parcours en largeur.<br /> * (TD 2): 26 septembre. Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): 2 octobre. Parcours en profondeur, graphes valués, arbres couvrants de poids minimal (I).<br /> * (TD 3): 9 octobre. Parcours en profonder : détection de cycles, tri topologique. Algorithmes de Kruskal (I).<br /> * (Cours 5): 16 octobre. Algorithmes de Prim, Dijkstra et Floyd-Warshall.<br /> * (TP 1): 24 octobre. Familiarisation avec Sagemath et sa bibliothèque de graphes. Conversion de représentations, graphe de dépendances.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> * (TD 6): Misc. ( Recherche guidée, chemin eulériens et clôture transitive )<br /> <br /> &lt;!--<br /> <br /> -----------------<br /> -----------------<br /> <br /> ==Introduction, quelques dates==<br /> <br /> Euler, problèmes des ponts de Königsberg (1736), notion de graphe eulérien<br /> <br /> def : un graphe est eulérien si ...<br /> <br /> def : un graphe est hamiltonien si ...<br /> <br /> problèmes de complexité<br /> <br /> <br /> Kuratowski 1930, notion de graphe planaire, contre exemple : K_5 et K_{3,3}<br /> <br /> exemple des maisons et des usines<br /> <br /> théorème de Kuratowski<br /> <br /> <br /> Appel et Haken 1976, théorème des 4 couleurs (preuve par ordinateur)<br /> <br /> <br /> problématiques de graphes dans les réseaux (Internet, télécommunications, ...)<br /> <br /> ==Graphes et arbres, préliminaires==<br /> <br /> ===Définitions===<br /> <br /> ...<br /> <br /> <br /> :'''Vocabulaire :'''<br /> :* sommets adjacents<br /> :* arêtes adjacentes<br /> :* arête incidente<br /> :* degré d'un sommets, degré entrant / degré sortant<br /> <br /> <br /> ===Arbres===<br /> <br /> ...<br /> <br /> <br /> ===Représentation des graphes===<br /> <br /> listes d'adjacence<br /> <br /> matrice d'adjacence<br /> <br /> <br /> <br /> '''Question :''' quelle est la meilleure représentation ?<br /> <br /> --&gt;</div>

Durandmo http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO632_:_algorithmes_de_graphes&diff=6433 2014-05-13T13:43:38Z

<p>Durandmo : /* Algorithmes */</p> <hr /> <div>Cours du semestre 6 de la licence STIC INFO.<br /> <br /> * Responsable pour 2010--2011: Pierre Hyvernat.<br /> * Responsable pour 2011--2012: Xavier Provençal.<br /> * Responsable pour 2012--2013: Xavier Provençal.<br /> * Responsable pour 2013--2014: Xavier Provençal.<br /> * Xavier Provençal (CM/TD/TP).<br /> <br /> <br /> &lt;!-- Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». La participation au wiki est fortement encouragée. <br /> <br /> #Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style ''PrenomNom''...)<br /> <br /> #Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.--&gt;<br /> <br /> <br /> ===TD et TP===<br /> <br /> TD1 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD1.pdf Première feuille de TD]<br /> <br /> TD2 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD2.pdf Deuxième feuille de TD]<br /> <br /> TD3 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD3.pdf Troisième feuille de TD]<br /> <br /> TD4 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD4.pdf Quatrième feuille de TD]<br /> <br /> TD5 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD5.pdf Cinquième feuille de TD]<br /> <br /> TD6 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD6.pdf Sixième feuille de TD]<br /> <br /> TP : [http://www.lama.univ-savoie.fr/~provencal/INFO632/TP/index.html Énoncé des TP]<br /> <br /> <br /> &lt;!--<br /> <br /> ===Compléments de cours / TD / TP===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursProfondeur.pdf Algorithme du parcours en profondeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.]<br /> --&gt;<br /> <br /> ===Algorithmes===<br /> <br /> [https://www.youtube.com/watch?v=vYv8MhxCO00 Parcourt en Profondeur (DFS) 1/2]<br /> <br /> [https://www.youtube.com/watch?v=zEKRCDSxYXg Parcourt en Profondeur (DFS) 2/2]<br /> <br /> [https://www.youtube.com/watch?v=JucGeygpzFw Parcourt en Largeur (BFS) 1/2]<br /> <br /> [https://www.youtube.com/watch?v=0rH7OgcM6eA Parcourt en Largeur (BFS) 2/2]<br /> <br /> <br /> [https://www.youtube.com/watch?v=-3YIKISpTsQ Arbres Couvrants Minimum (Prim)]<br /> <br /> <br /> [https://www.youtube.com/watch?v=ocYYUiCTqI8 Algorithme Ford-Fulkerson (avec capacités aux noeuds)]<br /> <br /> <br /> [https://www.youtube.com/watch?v=Z5B_Ruz1woI A* (un algorithme pour super mario); excerpt]<br /> <br /> <br /> [https://www.youtube.com/watch?v=WOTOjbHBEXY Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 1/2 ]<br /> <br /> [https://www.youtube.com/watch?v=c57gOxo4hWo Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 2/2 ]<br /> <br /> <br /> [https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp]<br /> <br /> ===Ouvrage de référence===<br /> <br /> La partie « Algorithmes sur les graphes » du livre « ''Introduction à l'algorithmique'' » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...<br /> <br /> <br /> === Documents remis en classe ===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/parcours.pdf Parcours de graphes, en largeur et en profondeur.]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/algos_minimisation.pdf Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).]<br /> <br /> == Déroulement (2013-2014) ==<br /> <br /> * (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre et forêt. Représentation de graphes ( matrice vs listes ).<br /> * (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): Représentation de graphes (suite et fin). Parcours de graphes, parcours en largeur, parcours en profondeur.<br /> * (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Prim.<br /> * (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.<br /> * (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> <br /> <br /> <br /> == Déroulement (2012-2013) ==<br /> <br /> * (Cours 1): 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes.<br /> * (TD 1): 19 septembre. Représentation de graphes, propriétés élémentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): 25 septembre. Arbres, forêts et arbres couvrants. Parcours en largeur.<br /> * (TD 2): 26 septembre. Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): 2 octobre. Parcours en profondeur, graphes valués, arbres couvrants de poids minimal (I).<br /> * (TD 3): 9 octobre. Parcours en profonder : détection de cycles, tri topologique. Algorithmes de Kruskal (I).<br /> * (Cours 5): 16 octobre. Algorithmes de Prim, Dijkstra et Floyd-Warshall.<br /> * (TP 1): 24 octobre. Familiarisation avec Sagemath et sa bibliothèque de graphes. Conversion de représentations, graphe de dépendances.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> * (TD 6): Misc. ( Recherche guidée, chemin eulériens et clôture transitive )<br /> <br /> &lt;!--<br /> <br /> -----------------<br /> -----------------<br /> <br /> ==Introduction, quelques dates==<br /> <br /> Euler, problèmes des ponts de Königsberg (1736), notion de graphe eulérien<br /> <br /> def : un graphe est eulérien si ...<br /> <br /> def : un graphe est hamiltonien si ...<br /> <br /> problèmes de complexité<br /> <br /> <br /> Kuratowski 1930, notion de graphe planaire, contre exemple : K_5 et K_{3,3}<br /> <br /> exemple des maisons et des usines<br /> <br /> théorème de Kuratowski<br /> <br /> <br /> Appel et Haken 1976, théorème des 4 couleurs (preuve par ordinateur)<br /> <br /> <br /> problématiques de graphes dans les réseaux (Internet, télécommunications, ...)<br /> <br /> ==Graphes et arbres, préliminaires==<br /> <br /> ===Définitions===<br /> <br /> ...<br /> <br /> <br /> :'''Vocabulaire :'''<br /> :* sommets adjacents<br /> :* arêtes adjacentes<br /> :* arête incidente<br /> :* degré d'un sommets, degré entrant / degré sortant<br /> <br /> <br /> ===Arbres===<br /> <br /> ...<br /> <br /> <br /> ===Représentation des graphes===<br /> <br /> listes d'adjacence<br /> <br /> matrice d'adjacence<br /> <br /> <br /> <br /> '''Question :''' quelle est la meilleure représentation ?<br /> <br /> --&gt;</div>

Durandmo http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO632_:_algorithmes_de_graphes&diff=6432 2014-05-13T13:43:15Z

<p>Durandmo : </p> <hr /> <div>Cours du semestre 6 de la licence STIC INFO.<br /> <br /> * Responsable pour 2010--2011: Pierre Hyvernat.<br /> * Responsable pour 2011--2012: Xavier Provençal.<br /> * Responsable pour 2012--2013: Xavier Provençal.<br /> * Responsable pour 2013--2014: Xavier Provençal.<br /> * Xavier Provençal (CM/TD/TP).<br /> <br /> <br /> &lt;!-- Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». La participation au wiki est fortement encouragée. <br /> <br /> #Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style ''PrenomNom''...)<br /> <br /> #Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.--&gt;<br /> <br /> <br /> ===TD et TP===<br /> <br /> TD1 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD1.pdf Première feuille de TD]<br /> <br /> TD2 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD2.pdf Deuxième feuille de TD]<br /> <br /> TD3 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD3.pdf Troisième feuille de TD]<br /> <br /> TD4 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD4.pdf Quatrième feuille de TD]<br /> <br /> TD5 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD5.pdf Cinquième feuille de TD]<br /> <br /> TD6 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD6.pdf Sixième feuille de TD]<br /> <br /> TP : [http://www.lama.univ-savoie.fr/~provencal/INFO632/TP/index.html Énoncé des TP]<br /> <br /> <br /> &lt;!--<br /> <br /> ===Compléments de cours / TD / TP===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursProfondeur.pdf Algorithme du parcours en profondeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.]<br /> --&gt;<br /> <br /> ===Algorithmes===<br /> <br /> [https://www.youtube.com/watch?v=vYv8MhxCO00 Parcourt en Profondeur (DFS) 1/2]<br /> [https://www.youtube.com/watch?v=zEKRCDSxYXg Parcourt en Profondeur (DFS) 2/2]<br /> <br /> [https://www.youtube.com/watch?v=JucGeygpzFw Parcourt en Largeur (BFS) 1/2]<br /> [https://www.youtube.com/watch?v=0rH7OgcM6eA Parcourt en Largeur (BFS) 2/2]<br /> <br /> [https://www.youtube.com/watch?v=-3YIKISpTsQ Arbres Couvrants Minimum (Prim)]<br /> <br /> [https://www.youtube.com/watch?v=ocYYUiCTqI8 Algorithme Ford-Fulkerson (avec capacités aux noeuds)]<br /> <br /> [https://www.youtube.com/watch?v=Z5B_Ruz1woI A* (un algorithme pour super mario); excerpt]<br /> <br /> [https://www.youtube.com/watch?v=WOTOjbHBEXY Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 1/2 ]<br /> [https://www.youtube.com/watch?v=c57gOxo4hWo Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 2/2 ]<br /> <br /> [https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp]<br /> <br /> ===Ouvrage de référence===<br /> <br /> La partie « Algorithmes sur les graphes » du livre « ''Introduction à l'algorithmique'' » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...<br /> <br /> <br /> === Documents remis en classe ===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/parcours.pdf Parcours de graphes, en largeur et en profondeur.]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/algos_minimisation.pdf Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).]<br /> <br /> == Déroulement (2013-2014) ==<br /> <br /> * (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre et forêt. Représentation de graphes ( matrice vs listes ).<br /> * (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): Représentation de graphes (suite et fin). Parcours de graphes, parcours en largeur, parcours en profondeur.<br /> * (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Prim.<br /> * (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.<br /> * (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> <br /> <br /> <br /> == Déroulement (2012-2013) ==<br /> <br /> * (Cours 1): 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes.<br /> * (TD 1): 19 septembre. Représentation de graphes, propriétés élémentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): 25 septembre. Arbres, forêts et arbres couvrants. Parcours en largeur.<br /> * (TD 2): 26 septembre. Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): 2 octobre. Parcours en profondeur, graphes valués, arbres couvrants de poids minimal (I).<br /> * (TD 3): 9 octobre. Parcours en profonder : détection de cycles, tri topologique. Algorithmes de Kruskal (I).<br /> * (Cours 5): 16 octobre. Algorithmes de Prim, Dijkstra et Floyd-Warshall.<br /> * (TP 1): 24 octobre. Familiarisation avec Sagemath et sa bibliothèque de graphes. Conversion de représentations, graphe de dépendances.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> * (TD 6): Misc. ( Recherche guidée, chemin eulériens et clôture transitive )<br /> <br /> &lt;!--<br /> <br /> -----------------<br /> -----------------<br /> <br /> ==Introduction, quelques dates==<br /> <br /> Euler, problèmes des ponts de Königsberg (1736), notion de graphe eulérien<br /> <br /> def : un graphe est eulérien si ...<br /> <br /> def : un graphe est hamiltonien si ...<br /> <br /> problèmes de complexité<br /> <br /> <br /> Kuratowski 1930, notion de graphe planaire, contre exemple : K_5 et K_{3,3}<br /> <br /> exemple des maisons et des usines<br /> <br /> théorème de Kuratowski<br /> <br /> <br /> Appel et Haken 1976, théorème des 4 couleurs (preuve par ordinateur)<br /> <br /> <br /> problématiques de graphes dans les réseaux (Internet, télécommunications, ...)<br /> <br /> ==Graphes et arbres, préliminaires==<br /> <br /> ===Définitions===<br /> <br /> ...<br /> <br /> <br /> :'''Vocabulaire :'''<br /> :* sommets adjacents<br /> :* arêtes adjacentes<br /> :* arête incidente<br /> :* degré d'un sommets, degré entrant / degré sortant<br /> <br /> <br /> ===Arbres===<br /> <br /> ...<br /> <br /> <br /> ===Représentation des graphes===<br /> <br /> listes d'adjacence<br /> <br /> matrice d'adjacence<br /> <br /> <br /> <br /> '''Question :''' quelle est la meilleure représentation ?<br /> <br /> --&gt;</div>

Durandmo http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO632_:_algorithmes_de_graphes&diff=6430 2014-05-13T13:37:59Z

<p>Durandmo : /* Compléments */</p> <hr /> <div>Cours du semestre 6 de la licence STIC INFO.<br /> <br /> * Responsable pour 2010--2011: Pierre Hyvernat.<br /> * Responsable pour 2011--2012: Xavier Provençal.<br /> * Responsable pour 2012--2013: Xavier Provençal.<br /> * Responsable pour 2013--2014: Xavier Provençal.<br /> * Xavier Provençal (CM/TD/TP).<br /> <br /> <br /> &lt;!-- Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». La participation au wiki est fortement encouragée. <br /> <br /> #Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style ''PrenomNom''...)<br /> <br /> #Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.--&gt;<br /> <br /> <br /> ===TD et TP===<br /> <br /> TD1 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD1.pdf Première feuille de TD]<br /> <br /> TD2 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD2.pdf Deuxième feuille de TD]<br /> <br /> TD3 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD3.pdf Troisième feuille de TD]<br /> <br /> TD4 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD4.pdf Quatrième feuille de TD]<br /> <br /> TD5 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD5.pdf Cinquième feuille de TD]<br /> <br /> TD6 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD6.pdf Sixième feuille de TD]<br /> <br /> TP : [http://www.lama.univ-savoie.fr/~provencal/INFO632/TP/index.html Énoncé des TP]<br /> <br /> <br /> &lt;!--<br /> <br /> ===Compléments de cours / TD / TP===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursProfondeur.pdf Algorithme du parcours en profondeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.]<br /> --&gt;<br /> <br /> ===Algorythmes===<br /> [https://www.youtube.com/watch?v=ocYYUiCTqI8 Algorithme Ford-Fulkerson (avec capacités aux noeuds)]<br /> <br /> [https://www.youtube.com/watch?v=Z5B_Ruz1woI A* (un algorithme pour super mario); excerpt]<br /> <br /> [https://www.youtube.com/watch?v=WOTOjbHBEXY Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 1/2 ]<br /> <br /> [https://www.youtube.com/watch?v=c57gOxo4hWo Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 2/2 ]<br /> <br /> [https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp]<br /> <br /> ===Ouvrage de référence===<br /> <br /> La partie « Algorithmes sur les graphes » du livre « ''Introduction à l'algorithmique'' » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...<br /> <br /> <br /> === Documents remis en classe ===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/parcours.pdf Parcours de graphes, en largeur et en profondeur.]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/algos_minimisation.pdf Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).]<br /> <br /> == Déroulement (2013-2014) ==<br /> <br /> * (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre et forêt. Représentation de graphes ( matrice vs listes ).<br /> * (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): Représentation de graphes (suite et fin). Parcours de graphes, parcours en largeur, parcours en profondeur.<br /> * (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Prim.<br /> * (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.<br /> * (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> <br /> <br /> <br /> == Déroulement (2012-2013) ==<br /> <br /> * (Cours 1): 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes.<br /> * (TD 1): 19 septembre. Représentation de graphes, propriétés élémentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): 25 septembre. Arbres, forêts et arbres couvrants. Parcours en largeur.<br /> * (TD 2): 26 septembre. Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): 2 octobre. Parcours en profondeur, graphes valués, arbres couvrants de poids minimal (I).<br /> * (TD 3): 9 octobre. Parcours en profonder : détection de cycles, tri topologique. Algorithmes de Kruskal (I).<br /> * (Cours 5): 16 octobre. Algorithmes de Prim, Dijkstra et Floyd-Warshall.<br /> * (TP 1): 24 octobre. Familiarisation avec Sagemath et sa bibliothèque de graphes. Conversion de représentations, graphe de dépendances.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> * (TD 6): Misc. ( Recherche guidée, chemin eulériens et clôture transitive )<br /> <br /> &lt;!--<br /> <br /> -----------------<br /> -----------------<br /> <br /> ==Introduction, quelques dates==<br /> <br /> Euler, problèmes des ponts de Königsberg (1736), notion de graphe eulérien<br /> <br /> def : un graphe est eulérien si ...<br /> <br /> def : un graphe est hamiltonien si ...<br /> <br /> problèmes de complexité<br /> <br /> <br /> Kuratowski 1930, notion de graphe planaire, contre exemple : K_5 et K_{3,3}<br /> <br /> exemple des maisons et des usines<br /> <br /> théorème de Kuratowski<br /> <br /> <br /> Appel et Haken 1976, théorème des 4 couleurs (preuve par ordinateur)<br /> <br /> <br /> problématiques de graphes dans les réseaux (Internet, télécommunications, ...)<br /> <br /> ==Graphes et arbres, préliminaires==<br /> <br /> ===Définitions===<br /> <br /> ...<br /> <br /> <br /> :'''Vocabulaire :'''<br /> :* sommets adjacents<br /> :* arêtes adjacentes<br /> :* arête incidente<br /> :* degré d'un sommets, degré entrant / degré sortant<br /> <br /> <br /> ===Arbres===<br /> <br /> ...<br /> <br /> <br /> ===Représentation des graphes===<br /> <br /> listes d'adjacence<br /> <br /> matrice d'adjacence<br /> <br /> <br /> <br /> '''Question :''' quelle est la meilleure représentation ?<br /> <br /> --&gt;</div>

Durandmo http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO632_:_algorithmes_de_graphes&diff=6429 2014-05-13T13:37:42Z

<p>Durandmo : /* Compléments */</p> <hr /> <div>Cours du semestre 6 de la licence STIC INFO.<br /> <br /> * Responsable pour 2010--2011: Pierre Hyvernat.<br /> * Responsable pour 2011--2012: Xavier Provençal.<br /> * Responsable pour 2012--2013: Xavier Provençal.<br /> * Responsable pour 2013--2014: Xavier Provençal.<br /> * Xavier Provençal (CM/TD/TP).<br /> <br /> <br /> &lt;!-- Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». La participation au wiki est fortement encouragée. <br /> <br /> #Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style ''PrenomNom''...)<br /> <br /> #Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.--&gt;<br /> <br /> <br /> ===TD et TP===<br /> <br /> TD1 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD1.pdf Première feuille de TD]<br /> <br /> TD2 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD2.pdf Deuxième feuille de TD]<br /> <br /> TD3 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD3.pdf Troisième feuille de TD]<br /> <br /> TD4 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD4.pdf Quatrième feuille de TD]<br /> <br /> TD5 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD5.pdf Cinquième feuille de TD]<br /> <br /> TD6 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD6.pdf Sixième feuille de TD]<br /> <br /> TP : [http://www.lama.univ-savoie.fr/~provencal/INFO632/TP/index.html Énoncé des TP]<br /> <br /> <br /> &lt;!--<br /> <br /> ===Compléments de cours / TD / TP===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursProfondeur.pdf Algorithme du parcours en profondeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.]<br /> --&gt;<br /> <br /> ===Compléments===<br /> [https://www.youtube.com/watch?v=ocYYUiCTqI8 Algorithme Ford-Fulkerson (avec capacités aux noeuds)]<br /> <br /> [https://www.youtube.com/watch?v=Z5B_Ruz1woI A* (un algorithme pour super mario); excerpt]<br /> <br /> [https://www.youtube.com/watch?v=WOTOjbHBEXY Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 1/2 ]<br /> <br /> [https://www.youtube.com/watch?v=c57gOxo4hWo Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 2/2 ]<br /> <br /> [https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp]<br /> <br /> ===Ouvrage de référence===<br /> <br /> La partie « Algorithmes sur les graphes » du livre « ''Introduction à l'algorithmique'' » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...<br /> <br /> <br /> === Documents remis en classe ===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/parcours.pdf Parcours de graphes, en largeur et en profondeur.]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/algos_minimisation.pdf Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).]<br /> <br /> == Déroulement (2013-2014) ==<br /> <br /> * (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre et forêt. Représentation de graphes ( matrice vs listes ).<br /> * (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): Représentation de graphes (suite et fin). Parcours de graphes, parcours en largeur, parcours en profondeur.<br /> * (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Prim.<br /> * (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.<br /> * (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> <br /> <br /> <br /> == Déroulement (2012-2013) ==<br /> <br /> * (Cours 1): 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes.<br /> * (TD 1): 19 septembre. Représentation de graphes, propriétés élémentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): 25 septembre. Arbres, forêts et arbres couvrants. Parcours en largeur.<br /> * (TD 2): 26 septembre. Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): 2 octobre. Parcours en profondeur, graphes valués, arbres couvrants de poids minimal (I).<br /> * (TD 3): 9 octobre. Parcours en profonder : détection de cycles, tri topologique. Algorithmes de Kruskal (I).<br /> * (Cours 5): 16 octobre. Algorithmes de Prim, Dijkstra et Floyd-Warshall.<br /> * (TP 1): 24 octobre. Familiarisation avec Sagemath et sa bibliothèque de graphes. Conversion de représentations, graphe de dépendances.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> * (TD 6): Misc. ( Recherche guidée, chemin eulériens et clôture transitive )<br /> <br /> &lt;!--<br /> <br /> -----------------<br /> -----------------<br /> <br /> ==Introduction, quelques dates==<br /> <br /> Euler, problèmes des ponts de Königsberg (1736), notion de graphe eulérien<br /> <br /> def : un graphe est eulérien si ...<br /> <br /> def : un graphe est hamiltonien si ...<br /> <br /> problèmes de complexité<br /> <br /> <br /> Kuratowski 1930, notion de graphe planaire, contre exemple : K_5 et K_{3,3}<br /> <br /> exemple des maisons et des usines<br /> <br /> théorème de Kuratowski<br /> <br /> <br /> Appel et Haken 1976, théorème des 4 couleurs (preuve par ordinateur)<br /> <br /> <br /> problématiques de graphes dans les réseaux (Internet, télécommunications, ...)<br /> <br /> ==Graphes et arbres, préliminaires==<br /> <br /> ===Définitions===<br /> <br /> ...<br /> <br /> <br /> :'''Vocabulaire :'''<br /> :* sommets adjacents<br /> :* arêtes adjacentes<br /> :* arête incidente<br /> :* degré d'un sommets, degré entrant / degré sortant<br /> <br /> <br /> ===Arbres===<br /> <br /> ...<br /> <br /> <br /> ===Représentation des graphes===<br /> <br /> listes d'adjacence<br /> <br /> matrice d'adjacence<br /> <br /> <br /> <br /> '''Question :''' quelle est la meilleure représentation ?<br /> <br /> --&gt;</div>

Durandmo http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO632_:_algorithmes_de_graphes&diff=6428 2014-05-13T13:31:09Z

<p>Durandmo : </p> <hr /> <div>Cours du semestre 6 de la licence STIC INFO.<br /> <br /> * Responsable pour 2010--2011: Pierre Hyvernat.<br /> * Responsable pour 2011--2012: Xavier Provençal.<br /> * Responsable pour 2012--2013: Xavier Provençal.<br /> * Responsable pour 2013--2014: Xavier Provençal.<br /> * Xavier Provençal (CM/TD/TP).<br /> <br /> <br /> &lt;!-- Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». La participation au wiki est fortement encouragée. <br /> <br /> #Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style ''PrenomNom''...)<br /> <br /> #Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.--&gt;<br /> <br /> <br /> ===TD et TP===<br /> <br /> TD1 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD1.pdf Première feuille de TD]<br /> <br /> TD2 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD2.pdf Deuxième feuille de TD]<br /> <br /> TD3 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD3.pdf Troisième feuille de TD]<br /> <br /> TD4 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD4.pdf Quatrième feuille de TD]<br /> <br /> TD5 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD5.pdf Cinquième feuille de TD]<br /> <br /> TD6 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD6.pdf Sixième feuille de TD]<br /> <br /> TP : [http://www.lama.univ-savoie.fr/~provencal/INFO632/TP/index.html Énoncé des TP]<br /> <br /> <br /> &lt;!--<br /> <br /> ===Compléments de cours / TD / TP===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/parcoursProfondeur.pdf Algorithme du parcours en profondeur]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO526/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.]<br /> --&gt;<br /> <br /> ===Compléments===<br /> [https://www.youtube.com/watch?v=ocYYUiCTqI8 Algorithme Ford-Fulkerson (avec capacités aux noeuds)]<br /> <br /> [https://www.youtube.com/watch?v=Z5B_Ruz1woI A* (un algorithme pour super mario); excerpt]<br /> <br /> [https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp]<br /> <br /> <br /> ===Ouvrage de référence===<br /> <br /> La partie « Algorithmes sur les graphes » du livre « ''Introduction à l'algorithmique'' » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...<br /> <br /> <br /> === Documents remis en classe ===<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/parcours.pdf Parcours de graphes, en largeur et en profondeur.]<br /> <br /> [http://lama.univ-savoie.fr/~provencal/INFO632/algos_minimisation.pdf Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).]<br /> <br /> == Déroulement (2013-2014) ==<br /> <br /> * (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre et forêt. Représentation de graphes ( matrice vs listes ).<br /> * (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): Représentation de graphes (suite et fin). Parcours de graphes, parcours en largeur, parcours en profondeur.<br /> * (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Prim.<br /> * (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.<br /> * (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> <br /> <br /> <br /> == Déroulement (2012-2013) ==<br /> <br /> * (Cours 1): 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.<br /> * (Cours 2): 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes.<br /> * (TD 1): 19 septembre. Représentation de graphes, propriétés élémentaires de graphes, modélisation par des graphes.<br /> * (Cours 3): 25 septembre. Arbres, forêts et arbres couvrants. Parcours en largeur.<br /> * (TD 2): 26 septembre. Parcours en largeur : connexité, graphes bipartis, détection de cycles.<br /> * (Cours 4): 2 octobre. Parcours en profondeur, graphes valués, arbres couvrants de poids minimal (I).<br /> * (TD 3): 9 octobre. Parcours en profonder : détection de cycles, tri topologique. Algorithmes de Kruskal (I).<br /> * (Cours 5): 16 octobre. Algorithmes de Prim, Dijkstra et Floyd-Warshall.<br /> * (TP 1): 24 octobre. Familiarisation avec Sagemath et sa bibliothèque de graphes. Conversion de représentations, graphe de dépendances.<br /> * (TD 4): Chemins de longueur minimales.<br /> * (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.<br /> * (TD 5): Réseaux de tarnsport et flot maximal.<br /> * (TD 6): Misc. ( Recherche guidée, chemin eulériens et clôture transitive )<br /> <br /> &lt;!--<br /> <br /> -----------------<br /> -----------------<br /> <br /> ==Introduction, quelques dates==<br /> <br /> Euler, problèmes des ponts de Königsberg (1736), notion de graphe eulérien<br /> <br /> def : un graphe est eulérien si ...<br /> <br /> def : un graphe est hamiltonien si ...<br /> <br /> problèmes de complexité<br /> <br /> <br /> Kuratowski 1930, notion de graphe planaire, contre exemple : K_5 et K_{3,3}<br /> <br /> exemple des maisons et des usines<br /> <br /> théorème de Kuratowski<br /> <br /> <br /> Appel et Haken 1976, théorème des 4 couleurs (preuve par ordinateur)<br /> <br /> <br /> problématiques de graphes dans les réseaux (Internet, télécommunications, ...)<br /> <br /> ==Graphes et arbres, préliminaires==<br /> <br /> ===Définitions===<br /> <br /> ...<br /> <br /> <br /> :'''Vocabulaire :'''<br /> :* sommets adjacents<br /> :* arêtes adjacentes<br /> :* arête incidente<br /> :* degré d'un sommets, degré entrant / degré sortant<br /> <br /> <br /> ===Arbres===<br /> <br /> ...<br /> <br /> <br /> ===Représentation des graphes===<br /> <br /> listes d'adjacence<br /> <br /> matrice d'adjacence<br /> <br /> <br /> <br /> '''Question :''' quelle est la meilleure représentation ?<br /> <br /> --&gt;</div>

Durandmo http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO622_:_Syst%C3%A8mes_de_synchronisation_et_Processus&diff=6251 2014-02-21T15:34:14Z

<p>Durandmo : </p> <hr /> <div>* Responsable pour 2012--2013: [http://www.lama.univ-savoie.fr/~provencal Xavier Provençal]<br /> * Xavier Provençal (CM/TD/TP) &lt;!--, Pierre-Étienne Meunier (TP), Florian Hatat (TP) --&gt;<br /> <br /> == Ouvrage de référence ==<br /> <br /> # Andrew Tanenbaum, Systèmes d'exploitation<br /> <br /> == Documentation remise en classes ==<br /> - Entêtes de fonctions POSIX (I) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_1.pdf fonctions_POSIX_1.pdf.]<br /> - Entêtes de fonctions POSIX (II) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_2.pdf fonctions_POSIX_2.pdf.]<br /> - Entêtes de fonctions POSIX (III) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_3.pdf fonctions_POSIX_3.pdf.]<br /> - Entêtes de fonctions POSIX (IV) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_4.pdf fonctions_POSIX_4.pdf.]<br /> &lt;!--<br /> - Entêtes de fonctions POSIX (V) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_5.pdf fonctions_POSIX_5.pdf.]<br /> --&gt;<br /> <br /> <br /> == Systèmes de synchronisation et processus ==<br /> <br /> <br /> <br /> == TP ==<br /> <br /> - TP1 : <br /> [http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp1.pdf Énoncé du TP.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/TP/info622-tp1.tgz code fourni.]<br /> <br /> == Déroulement (2013-2014) ==<br /> <br /> CM1 : Introduction à la multiprogrammation, condition de concurrence et section critique.<br /> - Banque virtuelle : exemple de condition de concurrence.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM1/banqueVirtuelle.c programme ``banqueVirtuelle.c``.]<br /> <br /> <br /> TD1 : <br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1.pdf Énoncé du TD1 (effectuée en salle machine).]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q1a.c Solution question 1a)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q2a.c Solution question 2a)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q2b.c Solution question 2b)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q3a.c Solution question 3a)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q3d.c Solution question 3d)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q3e.c Solution question 3e)]<br /> <br /> <br /> CM2 : Processus et threads, utilisation des fonctions : fork, wait, waitpid, pthread_create, pthread_exit, pthread_join. Méthodes d'exclusion mutuelle : désactivation des interruptions et attente active.<br /> <br /> <br /> TD2 : <br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD2.pdf Énoncé du TD2.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2_q6.c Implémentation du code de la question 6.] (à compiler avec l'option -lm )<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2_q6-sol.c Implémentation de la solution de la question 6.] (à compiler avec les options -lm -lpthread )<br /> Utilisez la commande &quot;time&quot; pour observer un gain de vitesse sur une machine à plusieurs coeurs. <br /> Pour cela il vous faudra de grands nombres premiers. En voici un : 1000000000000039723<br /> <br /> CM3 : Producteur/Consommateur et Sémaphores<br /> - Exemple d'utilisation d'un sémaphore non nommé par des threads (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM3/semThread.c programme ``semThread.c``.]<br /> - Exemple erroné d'utilisation d'un sémaphore non nommé par des processus apparenté ( fork() ) (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM3/semFork-bug.c programme ``semFork-bug.c``.]<br /> <br /> TD3 : <br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD3.pdf Énoncé du TD3.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td3_q2.c Implémentation du code de la question 2.] (à compiler avec les options -lpthread -lcurses )<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td3_q2-sol.c Implémentation de la solution de la question 2.] (à compiler avec les options -lpthread -lcurses )<br /> <br /> CM4 : Sémaphores nommés et mémoire partagée<br /> - Sémaphores nommés avec processus distincs (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/createur.c programme ``createur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/destructeur.c programme ``destructeur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/gestionnaire.c programme ``gestionnaire.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/parleur.c programme ``parleur.c``.]<br /> - Exemple simplissime de manipulation d'un entier situé en mémoire partagée (compiler avec l'option -lrt) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_1.c programme ``mp_1.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_2.c programme ``mp_2.c``.]<br /> - Exemple d'utilisation d'un sémaphore non-nommé situé en mémoire partagée (compiler avec l'option -lrt) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_maStruct.h fichier entête ``mp_maStruct.h``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_lecture.c programme ``mp_lecture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_affichage.c programme ``mp_affichage.c``.]<br /> <br /> TD4 : <br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD4.pdf Énoncé du TD4.]<br /> <br /> CM5 : Variables de condision et implémentation du problème &quot;producteurs/consommateurs&quot;.<br /> - Solution au devoir :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/sol_devoir.c Programme qui teste le comportement par défaut le la mémoire partagée lors d'un fork. ]<br /> - Exemple d'utilisation d'une variable de condition.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_naif.c Implémentation naïve (non-fonctionnelles) ]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_sem.c Implémentation avec des sémaphores ]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_cnd.c Implémentation avec des variables de conditions ]<br /> <br /> <br /> &lt;!--<br /> CM4 : Sémaphores POSIX et mémoire partagée<br /> - Sémaphores nommés avec processus distincs (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/createur.c programme ``createur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/destructeur.c programme ``destructeur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/gestionnaire.c programme ``gestionnaire.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/parleur.c programme ``parleur.c``.]<br /> - Mémoire partagée (compiler avec l'option -lrt) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_maStruct.h fichier entête ``mp_maStruct.h``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_lecture.c programme ``mp_lecture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_affichage.c programme ``mp_affichage.c``.]<br /> <br /> CM5 : Variables de condition et barrières de synchronisation<br /> - Exemple producteur/consommateur implémenté avec des sémaphores.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_sem.c Programme ``prodCons_sem.c``.]<br /> - Exemple producteur/consommateur implémenté avec des variables de conditions et un mutex.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_cnd.c Programme ``prodCons_cnd.c``.]<br /> - Exemple d'utilisation d'une barrière de synchronisation.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/barriere.c Programme ``barriere.c``.]<br /> <br /> CM6 : Tubes<br /> - Exemple d'utilisation d'un tube non-nommé entre processus père et fils.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/tubeFork.c Programme ``tubeFork.c``.]<br /> - Exemnple d'utilisation d'un fifo entre deux processus non-apparentés.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/fifoEcriture.c Programme ``fifoEcriture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/fifoLecture.c Programme ``fifoLecture.c``.]<br /> <br /> <br /> CM7 : Interblocages et famine<br /> - Exemple de programme créant un interblocage.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/banqueVirtuelle2.c Programme ``banqueVirtuelle2.c``.]<br /> --&gt;<br /> <br /> <br /> &lt;!--<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD2.pdf TD2.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/rsa.c programme ``rsa.c``.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/exCleRSA.txt exemples de clés RSA valides au format ( n, d, e ) ``exCleRSA.txt``.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2-q1-solution.c Solution question 1.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2-q2-solution.c Solution question 2.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2-q3-solution.c Solution question 3.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD3/poste.c TD3 - Programme ``poste.c``]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD3/makefile Fichier ``makefile`` pour compiler ``poste.c``]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD4.pdf TD4.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD5.pdf TD5.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD6.pdf TD6.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD7.pdf TD7.]<br /> <br /> <br /> <br /> TP :<br /> - TP1 : Tri rapide en parallèle<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp1.pdf Énoncé du TP1.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/info622-tp1.tgz Archive contenant les sources nécessaires au TP1 ( format tgz ).]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/info622-tp1.zip Archive contenant les sources nécessaires au TP1 ( format zip ).]<br /> - TP2 : Tubes<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp2.tar Archive contenant les sources nécessaires au TP2.]<br /> - TP3 : Simulation de physique<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp3.pdf Énonpcé du TP3.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp3_code.tar Sources nécessaires à la réalisation du TP3.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp3_donnees.tar Données pour exécuter le programme du TP3.]<br /> --&gt;<br /> <br /> &lt;!--<br /> CM4 : Sémaphores POSIX et mémoire partagée<br /> - Entêtes de fonctions POSIX (III) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/fonctions_POSIX_III.pdf fonctions_POSIX_3.pdf.]<br /> - Sémaphores non nommés avec threads (compiler avcec l'i:<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/semThread.c programme ``semThread.c``.]<br /> - Sémaphores nommés avec processus distincs (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/createur.c programme ``createur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/destructeur.c programme ``destructeur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/gestionnaire.c programme ``gestionnaire.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/parleur.c programme ``parleur.c``.]<br /> - Mémoire partagée (compiler avec l'option -lrt) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_lecture.c programme ``mp_lecture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_affichage.c programme ``mp_affichage.c``.]<br /> <br /> CM5 : Interblocages<br /> - Banque virtuelle 2 : exemple d'interblocage (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/banqueVirtuelle2.c programme ``banqueVirtuelle.c``.]<br /> <br /> CM6 : Variables de condition et barrières de synchronisation<br /> - Implémentation du problème producteur/consommateur avec variables de condition (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/prodCons_cnd.c programme ``prodCons_cnd.c``.]<br /> - Exemple simple d'utilisation d'une barrière de synchronisation (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/barriere.c programme ``barriere.c``.]<br /> <br /> CM 7 : Tubes (pipe et fifo), fonction select<br /> - Utilisation typique d'un tube non-nommé (pipe) par un père et son fils :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/tubeFork.c programme ``tubeFork.c``.]<br /> - Exemple de programmes communicant à l'aide d'une tube nommé (fifo), créez d'abord la fifo avec la commande ``mkfifo`` :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/fifoLecture.c programme ``fifoLecture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/fifoEcriture.c programme ``fifoEcriture.c``.]<br /> - Exemple d'utilisation de la fonction select pour surveiller en même temps les tubres &quot;fifo1&quot; et &quot;fifo2&quot; ::w<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/fifo2Lecture.c programme ``fifo2Lecture.c``.]<br /> <br /> TD : <br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1.pdf Première feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD2.pdf Deuxième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD3.pdf Troisième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD4.pdf Quatrième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD5.pdf Cinquième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD6.pdf Sixième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD7.pdf Septième feuille de TD.]<br /> <br /> <br /> <br /> <br /> Exercices personnels<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/exo/devoir1.pdf Exercice personnel #1.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/exo/sol_devoir1.c Une solution de l'exercice personnel #1.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/exo/devoir2.pdf Exercice personnel #2.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/exo/sol_devoir2.c Une solution de l'exercice personnel #2.]<br /> <br /> Entêtes de fonctions<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_1.pdf Fork et création de threads.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_2.pdf Sémaphores et mutex.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_3.pdf Mémoire partagée.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_4.pdf Variables de condition et barrières de synchronisation.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_5.pdf Tube.]<br /> <br /> TP1 : Tri rapide en parallel<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/tp1.pdf Énoncé du TP.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/genAleat.c Programme pour la génération de suite de nombres.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/testTri.sh script permettant de comparer votre tri à la commande sort.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/triRapide.h Entêtes de fonctions relatives au tri rapide.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/triRapide.c Version séquentielle du tri rapide, à modifier.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/tri.c Lis des nombres sur l'entrée standard, appele triRapide et affiche le résultat. ]<br /> <br /> TP2 : Implémentation de tubes simplifiés<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP2/info622-tp2.c Fichier source principal et énoncé du TP.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP2/monTube.h Entêtes de fonctions relatives aux tube monTube.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP2/monTube.c Implémentation des fonctions relatives aux tubes monTube.]<br /> <br /> TP3 : Pizzéria<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/tp3.pdf Énoncé du TP.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/clients.o Fichier objet pour recompiler le programme 'clients'.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/synchroPizza.h Entêtes des fonctions utilisées pour préparer les pizzas.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/synchroPizza.c Implémentation des fonctions utilisées pour préparer les pizzas.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/pizzeria.c Source du programme implémentant une pizzéria virtuelle (à compléter).]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/makefile Makefile (optionnel).]<br /> --&gt;</div>

Durandmo http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO622_:_Syst%C3%A8mes_de_synchronisation_et_Processus&diff=6246 2014-02-19T12:21:04Z

<p>Durandmo : </p> <hr /> <div>* Responsable pour 2012--2013: [http://www.lama.univ-savoie.fr/~provencal Xavier Provençal]<br /> * Xavier Provençal (CM/TD/TP) &lt;!--, Pierre-Étienne Meunier (TP), Florian Hatat (TP) --&gt;<br /> <br /> == Ouvrage de référence ==<br /> <br /> # Andrew Tanenbaum, Systèmes d'exploitation<br /> <br /> == Documentation remise en classes ==<br /> - Entêtes de fonctions POSIX (I) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_1.pdf fonctions_POSIX_1.pdf.]<br /> - Entêtes de fonctions POSIX (II) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_2.pdf fonctions_POSIX_2.pdf.]<br /> - Entêtes de fonctions POSIX (III) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_3.pdf fonctions_POSIX_3.pdf.]<br /> - Entêtes de fonctions POSIX (IV) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_4.pdf fonctions_POSIX_4.pdf.]<br /> &lt;!--<br /> - Entêtes de fonctions POSIX (V) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_5.pdf fonctions_POSIX_5.pdf.]<br /> --&gt;<br /> <br /> <br /> == Systèmes de synchronisation et processus ==<br /> <br /> <br /> <br /> Multiprogrammation :<br /> <br /> <br /> Exécuter plusieurs programmes simultanément sur le même CPU.<br /> <br /> On divise l’écriture des programmes dans 3 espace mémoires différents donc cela permet de faire<br /> <br /> marcher le CPU en non-stop les programme sont exécuter en simultané avec le CPU.<br /> <br /> <br /> <br /> == Processus : ==<br /> <br /> <br /> Un programme en cours d’exécution. Deux composantes d’un processus :<br /> <br /> * Espace d’adressage. (mémoire) (code, donnée, piles des appels, etc...)<br /> * Des registres.<br /> <br /> Préemption :<br /> <br /> <br /> <br /> Action d’interrompre un processus avec l’intention d’un reprendre l’exécution plus tard.<br /> <br /> Note : la coopération du processus n’est pas requise.<br /> <br /> <br /> Principales causes de préemption :<br /> <br /> <br /> * A la demande du processus. (ex : sleep)<br /> * Lors d’un appel système bloquant. (ex : utilisation d’un périphérique)<br /> * Déclenchement d’une interruption. (signal envoyé au CPU ex : horloge, périph, etc...)<br /> &lt;br/&gt; <br /> <br /> <br /> Observation :<br /> <br /> <br /> <br /> <br /> <br /> Solde = solde + 1000 ;<br /> Solde = solde + (Solde * 0.01/365.0) ;<br /> <br /> <br /> # Copie Solde dans R2<br /> # « Arithmétique » sur des registres<br /> # Copier R2 dans Solde<br /> <br /> <br /> Les deux processus partage une variable, si il se mette pas d’accord le solde est peut-être pas mis a<br /> <br /> jours au bon moment.<br /> <br /> <br /> On passe d’un solde de 2000 à un solde à 1000.90 ...<br /> <br /> <br /> Condition de concurrence :<br /> <br /> <br /> <br /> Situation ou au moins deux processus écrivent des données partagées et où le résultat final dépend<br /> <br /> de l’ordre d’exécution.<br /> <br /> <br /> Ex : spool d’impression :<br /> <br /> <br /> <br /> <br /> Prochain_libre = 10<br /> <br /> <br /> # Lire prochain_libre<br /> # Ecrire le doc dans la case « prochain_libre »<br /> # Incrémenter prochain_libre<br /> <br /> Section critique :<br /> <br /> <br /> <br /> Partie du code dans laquelle on doit jamais avoir 2 processus en même temps.<br /> <br /> Deux objectifs :<br /> <br /> <br /> * Identifier les sections critiques<br /> * Assurer l’exclusion mutuelle<br /> <br /> Les quatre règles d’or de la gestion des sert critiques :<br /> <br /> <br /> # Deux processus ne doivent jamais se trouver simultanément en section critique.<br /> # On ne peut faire aucune supposition quant à la vitesse ou au nombre de processus en œuvre.<br /> # Aucun processus s’exécutant hors de sa section critique ne doit bloquer un autre processus.<br /> # Aucun processus ne doit attendre indéfiniment longtemps avant d’entrer en section critique.<br /> <br /> <br /> <br /> <br /> == TP ==<br /> <br /> - TP1 : <br /> [http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp1.pdf Énoncé du TP.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/TP/info622-tp1.tgz code fourni.]<br /> <br /> == Déroulement (2013-2014) ==<br /> <br /> CM1 : Introduction à la multiprogrammation, condition de concurrence et section critique.<br /> - Banque virtuelle : exemple de condition de concurrence.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM1/banqueVirtuelle.c programme ``banqueVirtuelle.c``.]<br /> <br /> <br /> TD1 : <br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1.pdf Énoncé du TD1 (effectuée en salle machine).]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q1a.c Solution question 1a)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q2a.c Solution question 2a)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q2b.c Solution question 2b)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q3a.c Solution question 3a)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q3d.c Solution question 3d)]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1-sol/q3e.c Solution question 3e)]<br /> <br /> <br /> CM2 : Processus et threads, utilisation des fonctions : fork, wait, waitpid, pthread_create, pthread_exit, pthread_join. Méthodes d'exclusion mutuelle : désactivation des interruptions et attente active.<br /> <br /> <br /> TD2 : <br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD2.pdf Énoncé du TD2.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2_q6.c Implémentation du code de la question 6.] (à compiler avec l'option -lm )<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2_q6-sol.c Implémentation de la solution de la question 6.] (à compiler avec les options -lm -lpthread )<br /> Utilisez la commande &quot;time&quot; pour observer un gain de vitesse sur une machine à plusieurs coeurs. <br /> Pour cela il vous faudra de grands nombres premiers. En voici un : 1000000000000039723<br /> <br /> CM3 : Producteur/Consommateur et Sémaphores<br /> - Exemple d'utilisation d'un sémaphore non nommé par des threads (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM3/semThread.c programme ``semThread.c``.]<br /> - Exemple erroné d'utilisation d'un sémaphore non nommé par des processus apparenté ( fork() ) (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM3/semFork-bug.c programme ``semFork-bug.c``.]<br /> <br /> TD3 : <br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD3.pdf Énoncé du TD3.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td3_q2.c Implémentation du code de la question 2.] (à compiler avec les options -lpthread -lcurses )<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td3_q2-sol.c Implémentation de la solution de la question 2.] (à compiler avec les options -lpthread -lcurses )<br /> <br /> CM4 : Sémaphores nommés et mémoire partagée<br /> - Sémaphores nommés avec processus distincs (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/createur.c programme ``createur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/destructeur.c programme ``destructeur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/gestionnaire.c programme ``gestionnaire.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/parleur.c programme ``parleur.c``.]<br /> - Exemple simplissime de manipulation d'un entier situé en mémoire partagée (compiler avec l'option -lrt) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_1.c programme ``mp_1.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_2.c programme ``mp_2.c``.]<br /> - Exemple d'utilisation d'un sémaphore non-nommé situé en mémoire partagée (compiler avec l'option -lrt) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_maStruct.h fichier entête ``mp_maStruct.h``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_lecture.c programme ``mp_lecture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_affichage.c programme ``mp_affichage.c``.]<br /> <br /> TD4 : <br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD4.pdf Énoncé du TD4.]<br /> <br /> CM5 : Variables de condision et implémentation du problème &quot;producteurs/consommateurs&quot;.<br /> - Solution au devoir :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/sol_devoir.c Programme qui teste le comportement par défaut le la mémoire partagée lors d'un fork. ]<br /> - Exemple d'utilisation d'une variable de condition.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_naif.c Implémentation naïve (non-fonctionnelles) ]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_naif.c Implémentation avec des sémaphores ]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_naif.c Implémentation avec des variables de conditions ]<br /> <br /> <br /> &lt;!--<br /> CM4 : Sémaphores POSIX et mémoire partagée<br /> - Sémaphores nommés avec processus distincs (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/createur.c programme ``createur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/destructeur.c programme ``destructeur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/gestionnaire.c programme ``gestionnaire.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/parleur.c programme ``parleur.c``.]<br /> - Mémoire partagée (compiler avec l'option -lrt) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_maStruct.h fichier entête ``mp_maStruct.h``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_lecture.c programme ``mp_lecture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_affichage.c programme ``mp_affichage.c``.]<br /> <br /> CM5 : Variables de condition et barrières de synchronisation<br /> - Exemple producteur/consommateur implémenté avec des sémaphores.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_sem.c Programme ``prodCons_sem.c``.]<br /> - Exemple producteur/consommateur implémenté avec des variables de conditions et un mutex.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/prodCons_cnd.c Programme ``prodCons_cnd.c``.]<br /> - Exemple d'utilisation d'une barrière de synchronisation.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/barriere.c Programme ``barriere.c``.]<br /> <br /> CM6 : Tubes<br /> - Exemple d'utilisation d'un tube non-nommé entre processus père et fils.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/tubeFork.c Programme ``tubeFork.c``.]<br /> - Exemnple d'utilisation d'un fifo entre deux processus non-apparentés.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/fifoEcriture.c Programme ``fifoEcriture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/fifoLecture.c Programme ``fifoLecture.c``.]<br /> <br /> <br /> CM7 : Interblocages et famine<br /> - Exemple de programme créant un interblocage.<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/banqueVirtuelle2.c Programme ``banqueVirtuelle2.c``.]<br /> --&gt;<br /> <br /> <br /> &lt;!--<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD2.pdf TD2.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/rsa.c programme ``rsa.c``.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/exCleRSA.txt exemples de clés RSA valides au format ( n, d, e ) ``exCleRSA.txt``.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2-q1-solution.c Solution question 1.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2-q2-solution.c Solution question 2.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/td2-q3-solution.c Solution question 3.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD3/poste.c TD3 - Programme ``poste.c``]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD3/makefile Fichier ``makefile`` pour compiler ``poste.c``]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD4.pdf TD4.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD5.pdf TD5.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD6.pdf TD6.]<br /> - [http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD7.pdf TD7.]<br /> <br /> <br /> <br /> TP :<br /> - TP1 : Tri rapide en parallèle<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp1.pdf Énoncé du TP1.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/info622-tp1.tgz Archive contenant les sources nécessaires au TP1 ( format tgz ).]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/info622-tp1.zip Archive contenant les sources nécessaires au TP1 ( format zip ).]<br /> - TP2 : Tubes<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp2.tar Archive contenant les sources nécessaires au TP2.]<br /> - TP3 : Simulation de physique<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp3.pdf Énonpcé du TP3.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp3_code.tar Sources nécessaires à la réalisation du TP3.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP/tp3_donnees.tar Données pour exécuter le programme du TP3.]<br /> --&gt;<br /> <br /> &lt;!--<br /> CM4 : Sémaphores POSIX et mémoire partagée<br /> - Entêtes de fonctions POSIX (III) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/fonctions_POSIX_III.pdf fonctions_POSIX_3.pdf.]<br /> - Sémaphores non nommés avec threads (compiler avcec l'i:<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/semThread.c programme ``semThread.c``.]<br /> - Sémaphores nommés avec processus distincs (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/createur.c programme ``createur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/destructeur.c programme ``destructeur.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/gestionnaire.c programme ``gestionnaire.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/parleur.c programme ``parleur.c``.]<br /> - Mémoire partagée (compiler avec l'option -lrt) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_lecture.c programme ``mp_lecture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM4/mp_affichage.c programme ``mp_affichage.c``.]<br /> <br /> CM5 : Interblocages<br /> - Banque virtuelle 2 : exemple d'interblocage (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM5/banqueVirtuelle2.c programme ``banqueVirtuelle.c``.]<br /> <br /> CM6 : Variables de condition et barrières de synchronisation<br /> - Implémentation du problème producteur/consommateur avec variables de condition (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/prodCons_cnd.c programme ``prodCons_cnd.c``.]<br /> - Exemple simple d'utilisation d'une barrière de synchronisation (compiler avec l'option -lpthread) :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM6/barriere.c programme ``barriere.c``.]<br /> <br /> CM 7 : Tubes (pipe et fifo), fonction select<br /> - Utilisation typique d'un tube non-nommé (pipe) par un père et son fils :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/tubeFork.c programme ``tubeFork.c``.]<br /> - Exemple de programmes communicant à l'aide d'une tube nommé (fifo), créez d'abord la fifo avec la commande ``mkfifo`` :<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/fifoLecture.c programme ``fifoLecture.c``.]<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/fifoEcriture.c programme ``fifoEcriture.c``.]<br /> - Exemple d'utilisation de la fonction select pour surveiller en même temps les tubres &quot;fifo1&quot; et &quot;fifo2&quot; ::w<br /> [http://lama.univ-savoie.fr/~provencal/INFO622/CM7/fifo2Lecture.c programme ``fifo2Lecture.c``.]<br /> <br /> TD : <br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD1.pdf Première feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD2.pdf Deuxième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD3.pdf Troisième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD4.pdf Quatrième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD5.pdf Cinquième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD6.pdf Sixième feuille de TD.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TD/TD7.pdf Septième feuille de TD.]<br /> <br /> <br /> <br /> <br /> Exercices personnels<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/exo/devoir1.pdf Exercice personnel #1.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/exo/sol_devoir1.c Une solution de l'exercice personnel #1.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/exo/devoir2.pdf Exercice personnel #2.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/exo/sol_devoir2.c Une solution de l'exercice personnel #2.]<br /> <br /> Entêtes de fonctions<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_1.pdf Fork et création de threads.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_2.pdf Sémaphores et mutex.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_3.pdf Mémoire partagée.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_4.pdf Variables de condition et barrières de synchronisation.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/fct_posix/fonctions_POSIX_5.pdf Tube.]<br /> <br /> TP1 : Tri rapide en parallel<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/tp1.pdf Énoncé du TP.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/genAleat.c Programme pour la génération de suite de nombres.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/testTri.sh script permettant de comparer votre tri à la commande sort.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/triRapide.h Entêtes de fonctions relatives au tri rapide.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/triRapide.c Version séquentielle du tri rapide, à modifier.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP1/tri.c Lis des nombres sur l'entrée standard, appele triRapide et affiche le résultat. ]<br /> <br /> TP2 : Implémentation de tubes simplifiés<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP2/info622-tp2.c Fichier source principal et énoncé du TP.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP2/monTube.h Entêtes de fonctions relatives aux tube monTube.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP2/monTube.c Implémentation des fonctions relatives aux tubes monTube.]<br /> <br /> TP3 : Pizzéria<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/tp3.pdf Énoncé du TP.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/clients.o Fichier objet pour recompiler le programme 'clients'.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/synchroPizza.h Entêtes des fonctions utilisées pour préparer les pizzas.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/synchroPizza.c Implémentation des fonctions utilisées pour préparer les pizzas.]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/pizzeria.c Source du programme implémentant une pizzéria virtuelle (à compléter).]<br /> - [ http://lama.univ-savoie.fr/~provencal/INFO622/TP3/makefile Makefile (optionnel).]<br /> --&gt;</div>

Durandmo