Programmes de branchement catalytiques : algorithmes et applications
dc.contributor.advisor | McKenzie, Pierre | |
dc.contributor.author | Côté, Hugo | |
dc.date.accessioned | 2019-06-07T16:19:00Z | |
dc.date.available | NO_RESTRICTION | fr |
dc.date.available | 2019-06-07T16:19:00Z | |
dc.date.issued | 2019-03-13 | |
dc.date.submitted | 2018-08 | |
dc.identifier.uri | http://hdl.handle.net/1866/22123 | |
dc.subject | complexité de la communication | fr |
dc.subject | programme de branchement catalytique | fr |
dc.subject | calcul transparent | fr |
dc.subject | composition de fonction | fr |
dc.subject | gadget | fr |
dc.subject | analyseur | fr |
dc.subject | programme sur un groupe | fr |
dc.subject | fonction symétrique | fr |
dc.subject | produit scalaire | fr |
dc.subject | dag-like communication | fr |
dc.subject | communication complexity | fr |
dc.subject | catalytic branching program | fr |
dc.subject | tranparent computation | fr |
dc.subject | function composition | fr |
dc.subject | analyzer | fr |
dc.subject | program over a group | fr |
dc.subject | symmetric function | fr |
dc.subject | scalar product | fr |
dc.subject.other | Applied Sciences - Computer Science / Sciences appliqués et technologie - Informatique (UMI : 0984) | fr |
dc.title | Programmes de branchement catalytiques : algorithmes et applications | fr |
dc.type | Thèse ou mémoire / Thesis or Dissertation | |
etd.degree.discipline | Informatique | fr |
etd.degree.grantor | Université de Montréal | fr |
etd.degree.level | Maîtrise / Master's | fr |
etd.degree.name | M. Sc. | fr |
dcterms.abstract | Le présent mémoire étudie le modèle de calcul des programmes de branchement k- catalytiques. Un programme de branchement k-catalytique sert à effectuer le calcul de k fonctions booléennes sur une même entrée et représente la contrepartie non uniforme de la notion de machine de Turing catalytique introduite par Buhrman et al. (STOC, 2014). On montre que pour toute fonction booléenne symétrique f il existe un programme de branchement catalytique qui fait le calcul de f un nombre exponentiel de fois avec une taille O(nlgn) par copie. On montre un résultat similaire reliant la complexité de n’importe quelle fonction booléenne f sur n bits se décomposant sous la forme f(x) = h(g(x)) à celle de g et de h, où g est une fonction de {0,1}^n dans G, h une fonction de G dans {0,1} et G est un groupe. On introduit également un ensemble de notions dont celles de gadgets, d’analyseurs et de programmes sur des groupes permettant de montrer comment le calcul catalytique non uniforme peut aller au-delà du calcul transparent. Enfin, le nouveau formalisme introduit révèle le lien jusqu’à maintenant inexploré entre le calcul catalytique et la complexité de la communication. | fr |
dcterms.abstract | The present master’s thesis studies the computational model of k-catalytic branching programs. A k-catalytic branching program is used to carry out the computation of k boolean functions on the same input and represents the nonuniform counterpart to the notion of catalytic Turing machine introduced by Buhrman et al. (STOC, 2014). It is shown that for any boolean symmetric function f there exists a k-catalytic branching program which computes f an exponential number of times and which has size O(nlgn) per copy. We show a similar result linking the complexity of any boolean function f on n bits expressible as f(x) = h(g(x)) to the complexity of g and h, where g is a function from {0,1}^n to G, h a function from G to {0,1} and G is a group. Furthermore, we introduce a set of notions such as gadgets, analyzers and programs over groups allowing us to show how nonuniform catalytic computation can go beyond transparent computation. Lastly, the new formalism introduced reveals the link until now unexplored between catalytic computation and communication complexity. | fr |
dcterms.language | fra | fr |
Fichier·s constituant ce document
Ce document figure dans la ou les collections suivantes
Ce document diffusé sur Papyrus est la propriété exclusive des titulaires des droits d'auteur et est protégé par la Loi sur le droit d'auteur (L.R.C. (1985), ch. C-42). Il peut être utilisé dans le cadre d'une utilisation équitable et non commerciale, à des fins d'étude privée ou de recherche, de critique ou de compte-rendu comme le prévoit la Loi. Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.