| Titre : | Sur la coloration de certains hypergraphes : application aux problèmes d'emploi du temps | | Type de document : | texte imprimé | | Auteurs : | Lauriere, Jean-Louis, Auteur ; Faure, R., Directeur de thèse | | Editeur : | Université Paris VI | | Année de publication : | 1971 | | Importance : | 130 f. | | Présentation : | ill. | | Format : | 30 cm. | | Note générale : | Thèse de doctorat : Informatique : Paris, Université Paris VI : 1971
Bibliogr. f. 131 - 139 | | Langues : | Français (fre) | | Mots-clés : | Notion d'algorithme
Emploi du temps
Coloration d'hypergraphes
Traitement
Description | | Index. décimale : | D000271 | | Résumé : | Le but du présent travail est d'apporter une solution utilisable sur ordinateur au problème de la détermination d'une bonne coloration des sommets d'un hypergraphe.
Une coloration est réputée bonne si elle satisfait un ensemble R de critères donnés, tels que coloration en couleurs toutes différentes des sommets d'une même arête, respect de certaines distances, etc...
Ce problème généralise des problèmes combinatoires connus en Recherches Opérationnelle comme problèmes d'affectation, de recouvrement ou d'ordonnancement.
C'est aussi une formulation possible (Partie II, chapitre 1) du problème de la construction des "emplois du temps", qui est à l'origine de ces recherches et sur lequel nous avons testé l'applicabilité des résultats obtenus.
Nous avons comparé ces différentes méthodes et étudié les prolongements possibles dans la Partie II (thèorèmes II.1 et III.1).
Nous constatons cependant que leur application se heurte à la grande dimension combinatoire des problèmes réels et, en outre, à la variété des critères R: elles sont le plus souvent incapables de prendre en considération tous les éléments qui interviennent dans un cas concret.
La coloration des hypergraphes (Partie II, chapitre 4) parait dès lors une approche originale beaucoup plus satisfaisante.
Nous construisons ainsi un nouvel algorithme (I.1, page 21) qui améliore un résultat de WELSH et POWELL.
Son utilisation conduit à définir une nouvelle classe d'hypergraphes, étudiés en Partie II chapitre 3, et permet finalement d'écrire le programme de la dernière partie.
D'autre part, nous avons constaté la nécessité d'introduire dans la résolution de ce problème de Recherche Opérationnelle des techniques développées en Intelligence Artificielle.
Un plan général est ainsi donné (Partie I, Chapitre 4); il étend le cadre formel de ces procédures qui, construisant la solution de façon progressive, sont habituellement utilisées dans les jeux et la démonstration automatique de théorèmes.
Le programme décrit en dernière (Partie III, Chapitre 2 et 3) résout effectivement des problèmes concrets d'emploi du temps (Chapitre 4).
On conclut enfin par une extension à toute une classe de problèmes de nature combinatoire. |
Sur la coloration de certains hypergraphes : application aux problèmes d'emploi du temps [texte imprimé] / Lauriere, Jean-Louis, Auteur ; Faure, R., Directeur de thèse . - [S.l.] : Université Paris VI, 1971 . - 130 f. : ill. ; 30 cm. Thèse de doctorat : Informatique : Paris, Université Paris VI : 1971
Bibliogr. f. 131 - 139 Langues : Français ( fre) | Mots-clés : | Notion d'algorithme
Emploi du temps
Coloration d'hypergraphes
Traitement
Description | | Index. décimale : | D000271 | | Résumé : | Le but du présent travail est d'apporter une solution utilisable sur ordinateur au problème de la détermination d'une bonne coloration des sommets d'un hypergraphe.
Une coloration est réputée bonne si elle satisfait un ensemble R de critères donnés, tels que coloration en couleurs toutes différentes des sommets d'une même arête, respect de certaines distances, etc...
Ce problème généralise des problèmes combinatoires connus en Recherches Opérationnelle comme problèmes d'affectation, de recouvrement ou d'ordonnancement.
C'est aussi une formulation possible (Partie II, chapitre 1) du problème de la construction des "emplois du temps", qui est à l'origine de ces recherches et sur lequel nous avons testé l'applicabilité des résultats obtenus.
Nous avons comparé ces différentes méthodes et étudié les prolongements possibles dans la Partie II (thèorèmes II.1 et III.1).
Nous constatons cependant que leur application se heurte à la grande dimension combinatoire des problèmes réels et, en outre, à la variété des critères R: elles sont le plus souvent incapables de prendre en considération tous les éléments qui interviennent dans un cas concret.
La coloration des hypergraphes (Partie II, chapitre 4) parait dès lors une approche originale beaucoup plus satisfaisante.
Nous construisons ainsi un nouvel algorithme (I.1, page 21) qui améliore un résultat de WELSH et POWELL.
Son utilisation conduit à définir une nouvelle classe d'hypergraphes, étudiés en Partie II chapitre 3, et permet finalement d'écrire le programme de la dernière partie.
D'autre part, nous avons constaté la nécessité d'introduire dans la résolution de ce problème de Recherche Opérationnelle des techniques développées en Intelligence Artificielle.
Un plan général est ainsi donné (Partie I, Chapitre 4); il étend le cadre formel de ces procédures qui, construisant la solution de façon progressive, sont habituellement utilisées dans les jeux et la démonstration automatique de théorèmes.
Le programme décrit en dernière (Partie III, Chapitre 2 et 3) résout effectivement des problèmes concrets d'emploi du temps (Chapitre 4).
On conclut enfin par une extension à toute une classe de problèmes de nature combinatoire. |
|
Affiner la rechercheSur la coloration de certains hypergraphes / Lauriere, Jean-Louis
