Un homomorphisme est une fonction entre deux structures, par exemple des graphes, qui respecte certaines contraintes. Dans ce mémoire, on étudie la complexité des problèmes d'homomorphisme, c'est-à-dire des problèmes où l'on doit décider s'il existe une telle fonction entre deux structures. On présentera des propriétés sur ces structures qui permettent de déterminer cette complexité. On s'intéressera particulièrement aux problèmes d'homomorphisme qui appartiennent à la classe de complexité NL, une classe contenant des problèmes dont la résolution par un algorithme non déterministe nécéssite peu d'espace mémoire.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/25015 |
| Date | 20 April 2018 |
| Creators | Bédard, Catherine |
| Contributors | Tesson, Pascal |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | mémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise |
| Format | 1 ressource en ligne (vii, 90 pages), application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0025 seconds