Modèle géométrique de calcul : fractales et barrières de complexité
Les modèles géométriques de calcul permettent d effectuer des calculs à l aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d illustrer et de dém...
Gardado en:
| Autor Principal: | |
|---|---|
| Outros autores: | |
| Formato: | Thèse numérique |
| Idioma: | Français |
| Publicado: |
2013.
|
| Sujets: | |
| Acceso en liña: | Accès au texte intégral https://theses.univ-orleans.fr/public/2013ORLE2019_va.pdf http://www.theses.fr/2013ORLE2019/abes |
| Nota: |
Titre provenant de l'écran-titre Ecole(s) Doctorale(s) : École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire ; 2012-....) Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) Autre(s) contribution(s) : Géraud Sénizergues (Président du jury) ; Jérôme Durand-Lose, Géraud Sénizergues, Véronique Terrier, Jean-Baptiste Yunès, Denys Duchier (Membre(s) du jury) ; Véronique Terrier, Jean-Baptiste Yunès (Rapporteur(s)) |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | Geometrical model of computation :, fractals and complexity gaps |
| LEADER | 04475nam a22003617a 4500 | ||
|---|---|---|---|
| 001 | 481651 | ||
| 008 | 140909s2013 xxe ||| |||| 00| 0 fre d | ||
| 009 | PPN18040427X | ||
| 041 | 0 | |a fre |b fre |b eng | |
| 084 | |a 004 | ||
| 100 | 1 | |a Senot, Maxime. | |
| 240 | 1 | 0 | |a Geometrical model of computation : |b fractals and complexity gaps |
| 245 | 1 | 0 | |a Modèle géométrique de calcul : |b fractales et barrières de complexité |c Maxime Senot ; sous la direction de Jérôme Durand-Lose. |
| 256 | |a Données textuelles | ||
| 260 | |c 2013. | ||
| 500 | |a Titre provenant de l'écran-titre | ||
| 500 | |a Ecole(s) Doctorale(s) : École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire ; 2012-....) | ||
| 500 | |a Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) | ||
| 500 | |a Autre(s) contribution(s) : Géraud Sénizergues (Président du jury) ; Jérôme Durand-Lose, Géraud Sénizergues, Véronique Terrier, Jean-Baptiste Yunès, Denys Duchier (Membre(s) du jury) ; Véronique Terrier, Jean-Baptiste Yunès (Rapporteur(s)) | ||
| 502 | |a Thèse de doctorat. Informatique. Orléans. 2013 | ||
| 520 | |a Les modèles géométriques de calcul permettent d effectuer des calculs à l aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d abord à travers l étude de fractales que les machines à signaux sont capables d une utilisation massive et parallèle de l espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base les modules munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l application de cette méthode et l utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appelée profondeur de collisions, qui est polynomiale, illustrant ainsi l efficacité et le pouvoir de calcul parallèle des machines a signaux. | ||
| 520 | |a Geometrical models of computation allow to compute by using geometrical elementary operations. Among them, the signal machines model distinguishes itself by its simplicity, along with its power to realize efficiently various computations. We propose here an illustration and a study of this ability, especially in the case of massively parallel processes. We show first, through a study of fractals, that signal machines are able to make a massive and parallel use of space. Then, a framework of geometrical modular programmation is proposed for designing machines from basic geometrical components called modules supplied with given functionnalities. This method fits particulary with the conception of geometrical parallel computations. Finally, the joint use of this method and of fractal structures provides a geometrical resolution of difficult problems such as the boolean satisfiability problems SAT and Q-SAT. These ones, as well as several variants, are solved by signal machines with a model-specific time complexity, called collisions depth, which is polynomial, illustrating thus the efficiency and the parallel computational abilities of signal machines. | ||
| 538 | |a Configuration requise : un logiciel capable de lire un fichier au format : PDF | ||
| 650 | |a Calcul | ||
| 650 | |a Géométrie algorithmique | ||
| 650 | |a Fractales | ||
| 650 | |a Thèses et écrits académiques | ||
| 700 | 1 | |a Durand-Lose, Jérôme, |d 19..- |4 ths |4 opn | |
| 710 | 2 | |a Université d'Orléans. |4 dgg | |
| 856 | 4 | |q PDF |s 3607107 |u http://www.theses.fr/2013ORLE2019/document |z Accès au texte intégral | |
| 856 | 4 | |u https://theses.univ-orleans.fr/public/2013ORLE2019_va.pdf | |
| 856 | 4 | |u http://www.theses.fr/2013ORLE2019/abes | |
| 997 | |0 481651 |1 Thèse numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||