To see the other types of publications on this topic, follow the link: Complexité de circuits.
Dissertations / Theses on the topic 'Complexité de circuits'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Complexité de circuits.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Revol, Nathalie. "Complexité de l'évaluation parallèle de circuits arithmétiques." Grenoble INPG, 1994. http://tel.archives-ouvertes.fr/tel-00005109.
Full textAbstract:
Les algorithmes d'évaluation parallèle des expressions et des circuits arithmétiques peuvent être vus comme des extracteurs du parallélisme intrinsèque contenu dans les programmes séquentiels, parallélisme qui dépasse celui qui peut être lu sur le graphe de précédence et qui tient à la sémantique des opérateurs utilisés. La connaissance des propriétés algébriques, comme l'associativité ou la distributivité, permet une réorganisation des calculs qui n'affecte pas les résultats. Plus la structure algébrique utilisée sera riche en propriétés simples, plus il sera possible d'en tirer parti pour améliorer les algorithmes d'évaluation. Généralisant les algorithmes conçus pour les semi-anneaux, nous proposons un algorithme qui améliore les majorations précédemment connues pour la contraction de circuits arithmétiques dans un treillis. Des simulations de cet algorithme ont permis de mettre en évidence ses qualités de prédicteur automatique de complexité. Réorganiser explicitement les calculs à l'aide de ces algorithmes, c'est-à-dire réaliser un compilateur complet, permet de comparer la réalité des algorithmes parallèles sur machines à mémoire distribuée et la puissance des algorithmes théoriques. Un prototype a été réalisé, basé sur une simplification/extension du langage C. Enfin, l'intérêt de ces techniques dans le domaine de la parallélisation des nids de boucles, pour guider la recherche de réductions cachées dans ces nids, semble prometteuse, parce qu'elle est peu coûteuse à mettre en oeuvre et fournit des informations de qualité. En cela, les recherches en algorithmique parallèle théorique rejoignent les préoccupations de la parallelisation effective
2
Tavenas, Sébastien. "Bornes inférieures et supérieures dans les circuits arithmétiques." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2014. http://tel.archives-ouvertes.fr/tel-01066752.
Full textAbstract:
La complexité arithmétique est l'étude des ressources nécessaires pour calcu- ler des polynômes en n'utilisant que des opérations arithmétiques. À la fin des années 70, Valiant a défini (de manière semblable à la complexité booléenne) des classes de polynômes. Les polynômes, ayant des circuits de taille polyno- miale, considérés faciles forment la classe VP. Les sommes exponentielles de ces derniers correpondent alors à la classe VNP. L'hypothèse de Valiant est la conjecture que VP ̸= VNP.Bien que cette conjecture soit encore grandement ouverture, cette dernière semble toutefois plus accessible que son homologue booléen. La structure algé- brique sous-jacente limite les possibilités de calculs. En particulier, un résultat important du domaine assure que les polynômes faciles peuvent aussi être cal- culés efficacement en paralèlle. De plus, quitte à autoriser une augmentation raisonnable de la taille, il est possible de les calculer avec une profondeur de calcul bornée par une constante. Comme ce dernier modèle est très restreint, de nombreuses bornes inférieures sont connues. Nous nous intéresserons en premier temps à ces résultats sur les circuits de profondeur constante.Bürgisser a montré qu'une conjecture (la τ-conjecture) qui borne supérieu- rement le nombre de racines de certains polynômes univariés, impliquait des bornes inférieures en complexité arithmétique. Mais, que se passe-t-il alors, si on essaye de réduire, comme précédemment, la profondeur du polynôme consi- déré? Borner le nombre de racines réelles de certaines familles de polynômes permetterait de séparer VP et VNP. Nous étudierons finalement ces bornes su- périeures sur le nombre de racines réelles.
3
Aubert, Clément. "Logique linéaire et classes de complexité sous-polynominales." Paris 13, 2013. https://theses.hal.science/tel-00957653.
Full textAbstract:
This research in Theoretical Computer Science extends the gateways between Linear Logic and Complexity Theory by introducing two innovative models of computation. It focuses on sub-polynomial classes of complexity : AC and NC —the classes of efficiently parallelizable problems— and L and NL —the deterministic and non-deterministic classes of problems efficiently solvable with low resources on space. Linear Logic is used through its Proof Net resentation to mimic with efficiency the parallel computation of Boolean Circuits, including but not restricted to their constant-depth variants. In a second moment, we investigate how operators on a von Neumann algebra can be used to model computation, thanks to the method provided by the Geometry of Interaction, a subtle reconstruction of Linear Logic. This characterization of computation in logarithmic space with matrices can naturally be understood as a wander on simple structures using pointers, parsing them without modifying them. We make this intuition formal by introducing Non Deterministic Pointer Machines and relating them to other well-known pointer-like-machines. We obtain by doing so new implicit characterizations of sub-polynomial classes of complexityCette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d’espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s’inspire de la géométrie de l’interaction, une délicate reconstruction de la logique linéaire à l’aide d’opérateurs d’une algèbre de von Neumann. Nous détaillons comment l’interaction d’opérateurs représentant des entiers et d’opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d’autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial
4
Duvillié, Guillerme. "Approximation, complexité paramétrée et stratégies de résolution de problèmes d'affectation multidimensionnelle." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT321/document.
Full textAbstract:
Au cours de la thèse, nous nous sommes intéressés aux problèmes d'empilement de wafers. Ces problèmes apparaissent lors de la fabrication de processeurs en 3 dimensions. Au cours du processus de fabrication, les puces électroniques doivent être empilées les unes sur les autres. Jusqu'à peu, ces dernières, une fois gravées sur des plaques de silicium appelées wafers, étaient découpées, puis triées afin d'écarter les puces défectueuses et enfin assemblées les unes entre elles.Cependant empiler les wafers plutôt que les puces présente de nombreux avantages techniques et financiers. Naturellement, étant impossible d'écarter les puces défectueuses sans découper la plaque de silice, le problème de la superposition d'une puce viable avec une puce défectueuse se pose. Une pile de puces, étant considérées comme défectueuse si elle contient ne serait-ce qu'une puce défectueuse, la superposition non réfléchie des wafers entre eux mènerait à un rendement désastreux.Afin de générer un nombre minimum de piles défectueuses, une "cartographie" de chaque wafer candidat à la superposition est réalisée lors d'une phase de test, permettant de situer les puces défectueuses sur le wafer. Une fois cette cartographie réalisée, l'objectif est de sélectionner les wafers qui seront assemblés ensembles de manière à faire correspondre les défauts de chacun des wafers.Ce problème peut être modélisé à l'aide d'un problème d'affectation multidimensionnelle. Chaque wafer est représenté par un vecteur comportant autant de composantes que de puces sur le wafer qu'il représente. Une composante égale à zéro matérialise une puce défectueuse tandis qu'un un matérialise une puce viable. Chaque lot de wafers est représenté par un lot de vecteurs. Formellement, une instance d'empilement de wafers est représenté par m ensembles de n vecteurs binaires p-dimensionnels. L'objectif est alors de réaliser n m-uplets disjoints contenant exactement un vecteur par ensemble. Ces m-uplets représenteront les piles. Chaque m-uplet peut être représenté par un vecteur binaire p-dimensionnels, chaque composante étant calculée en réalisant le ET binaire des composantes correspondantes des vecteurs qui composent le m-uplet. Autrement dit, une composante du vecteur représentant le m-uplet est égale à un si et seulement si tous les vecteurs ont cette composante égale à un. Et donc une pile de puces est viables si toutes les puces qui la composent sont viables. L'objectif est alors de minimiser le nombre de zéros ou de maximiser le nombre de un.La thèse comporte deux grandes parties. Une partie théorique abordant la complexité des différentes versions du problèmes en fonction de certains paramètres tels que m, n, p ou encore le nombre maximum de zéros par vecteurs. Nous montrons entre autre que ces problèmes peuvent être utilisés pour modéliser des problèmes plus classiques tels que Maximum Clique, Minimum Vertex Cover ou encore k-Dimensional Matching, permettant de prouver un certain nombre de résultats négatifs que ce soit d'un point de vue de la complexité classique, l'approximabilité ou la complexité paramétrée. Nous fournissons également des résultats positifs pour des cas particuliers du problème.Dans un second temps, nous nous intéressons à la résolution pratique du problème en fournissant et comparant un certain nombre de formulations en Programmation Linéaire en Nombres Entiers. Mais nous nous intéressons également aux performances en pratique de certaines heuristiques à garantie de performances détaillées dans la partie théoriqueIn this thesis, we focused in the Wafer-to-Wafer integration problems. These problems come from IC manufacturing. During the production of three-dimensional processors, dies have to be superimposed. Until recent, the dies were engraved on a silicon disk called wafer, then were cut, tested and sorted to suppress faulty dies and lastly superimposed one to each other.However superimposing wafers instead of dies presents several technical and financial advantages. Since faulty dies can only be dismissed when cutting the wafer, superimpose two wafers can lead to superimpose a faulty die with a viable one. In this case, the resulting stack of dies is considered as faulty. It follows that a bad assignment between the wafers can lead to a disastrous yield.In order to minimize the number of faulty dies stacks, a "failure map" of each wafer is generated during a test phase. This map gives location of the faulty dies on the wafers. The objective is then to take advantage of this map to define an assignment of the wafers to each other in order to match as many failures as possible.This problem can be modelized with Multidimensional Assignment problems. Each wafer can be seen as a vector with as many dimensions as the number of dies engraved on it. A coordinate set to zero marks a faulty die while a coordinate set to one indicates a viable one. Each seat of wafers is represented by a set of vector. Formally, an instance of a Wafer-to-Wafer integration problem is represented by m sets of n p-dimensional vectors. The objective is then to partition the vectors into n disjoint m-tuples, each tuple containing exactly one vector per set. An m-tuple represents a stack of wafers. Every m-tuple can be represented by a p-dimensional vector. Each coordinate is computed by performing the bitwise AND between the corresponding coordinates of the vectors that compose the m-tuple. In other words, a coordinate of the representative vector is equal to one if and only if this coordinate is equal to one in every vector composing the tuple. It follows that a dies stack is viable if and only if all the dies composing the stack are viable. The objective is then to maximize the overall number of ones of to minimize the overall number of zeros.The first part of the thesis is a theoretical one. We study the complexity of the considered versions of the problem with regards to natural parameters such as m, n, p or the number of zeros per vector. We show that these problems can encode more classical problems such as Maximum Clique, Minimum Vertex Cover or k-Dimensional Matching. This leads to several negative results from computational complexity, approximability or even parameterized complexity point of view. We also provide several positive results for some specific cases of the problem.In a second part, we focus on the practical solving of the problem. We provide and compare several Integer Linear Programming formulations. We also focus on performances of some approximation algorithms that we detailed in the theoretical part
5
Diguet, Jean-Philippe. "Estimation de complexité et transformations d'algorithmes de traitement du signal pour la conception de circuits VLSI." Rennes 1, 1996. http://www.theses.fr/1996REN10118.
Full textAbstract:
Le cadre de la these est celui de la synthese d'architectures, ce dernier regroupe l'ensemble des techniques mises en uvre pour concevoir de maniere automatique et optimisee des circuits realisant des applications decrites simplement de maniere comportementale. Dans ce domaine est aborde specifiquement le probleme de l'estimation a priori du cout d'une architecture, sous contrainte de temps d'iteration. Deux methodes nouvelles sont presentees, chacune repondant a un objectif different. La premiere est une estimation probabiliste et dynamique, elle fournit au concepteur des metriques lui permettant de juger de la complexite materielle et de la repartition des ressources dans le temps. Son but est de caracteriser les choix de specifications effectues, de maniere a favoriser par la suite le recours a d'eventuelles transformations de types algorithmique, fonctionnel et structurel. Il s'agit d'une etude faisant appel a une notion recente et peu etudiee, celle du guidage dans l'espace des transformations pour l'optimisation de l'adequation algorithme architecture. La seconde technique proposee est consacree a l'estimation precise des ressources materielles requises par l'algorithem traite, pour respecter la contrainte de temps. Elle s'adresse a l'utilisateur et a l'outil de cao. Son originalite provient du calcul dual des besoins en unites fonctionnelles et du pipeline associe, a travers une etude fine des causes de sous et sur-estimation. De cette estimation, ressort egalement une connaissance precise de la mobilite exacte des operations du graphe flot de donnees sans a priori sur l'ordonnancement. Les deux types d'estimations sont integrees dans l'outil de synthese d'architecture gaut
6
Lagarde, Guillaume. "Contributions to arithmetic complexity and compression." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC192/document.
Full textAbstract:
Cette thèse explore deux territoires distincts de l’informatique fondamentale : la complexité et la compression. Plus précisément, dans une première partie, nous étudions la puissance des circuits arithmétiques non commutatifs, qui calculent des polynômes non commutatifs en plusieurs indéterminées. Pour cela, nous introduisons plusieurs modèles de calcul, restreints dans leur manière de calculer les monômes. Ces modèles en généralisent d’autres, plus anciens et largement étudiés, comme les programmes à branchements. Les résultats sont de trois sortes. Premièrement, nous donnons des bornes inférieures sur le nombre d’opérations arithmétiques nécessaires au calcul de certains polynômes tels que le déterminant ou encore le permanent. Deuxièmement, nous concevons des algorithmes déterministes fonctionnant en temps polynomial pour résoudre le problème du test d’identité polynomiale. Enfin, nous construisons un pont entre la théorie des automates et les circuits arithmétiques non commutatifs, ce qui nous permet de dériver de nouvelles bornes inférieures en utilisant une mesure reposant sur le rang de la matrice dite de Hankel, provenant de la théorie des automates. Une deuxième partie concerne l’analyse de l’algorithme de compression sans perte Lempel-Ziv. Pourtant très utilisé, sa stabilité est encore mal établie. Vers la fin des années 90s, Jack Lutz popularise la question suivante, connue sous le nom de « one-bit catastrophe » : « étant donné un mot compressible, est-il possible de le rendre incompressible en ne changeant qu’un seul bit ? ». Nous montrons qu’une telle catastrophe est en effet possible. Plus précisément, en donnant des bornes optimales sur la variation de la taille de la compression, nous montrons qu’un mot « très compressible » restera toujours compressible après modification d’un bit, mais que certains mots « peu compressibles » deviennent en effet incompressiblesThis thesis explores two territories of computer science: complexity and compression. More precisely, in a first part, we investigate the power of non-commutative arithmetic circuits, which compute multivariate non-commutative polynomials. For that, we introduce various models of computation that are restricted in the way they are allowed to compute monomials. These models generalize previous ones that have been widely studied, such as algebraic branching programs. The results are of three different types. First, we give strong lower bounds on the number of arithmetic operations needed to compute some polynomials such as the determinant or the permanent. Second, we design some deterministic polynomial-time algorithm to solve the white-box polynomial identity problem. Third, we exhibit a link between automata theory and non-commutative arithmetic circuits that allows us to derive some old and new tight lower bounds for some classes of non-commutative circuits, using a measure based on the rank of a so-called Hankel matrix. A second part is concerned with the analysis of the data compression algorithm called Lempel-Ziv. Although this algorithm is widely used in practice, we know little about its stability. Our main result is to show that an infinite word compressible by LZ’78 can become incompressible by adding a single bit in front of it, thus closing a question proposed by Jack Lutz in the late 90s under the name “one-bit catastrophe”. We also give tight bounds on the maximal possible variation between the compression ratio of a finite word and its perturbation—when one bit is added in front of it
7
Paperman, Charles. "Circuits booléens, prédicats modulaires et langages réguliers." Paris 7, 2014. http://www.theses.fr/2014PA077258.
Full textAbstract:
La conjecture de Straubing, énoncée dans son livre publié en 1994, suggère qu'un langage régulier définissable par un fragment logique équipé d'une signature arbitraire, est définissable par le même fragment logique mais équipé d'une signature régulière. Les fragments logiques considérés sont des classes de férmules de la logique monadique du second ordre sur les mots finis. Cette thèse est une contribution à l'étude de le conjecture de Straubing. Pour prouver une telle conjecture, il semble nécessaire pour établir cette conjecture de prouver deux résultats de natures différentes : 1. Des caractérisations algébriques de classes de langages réguliers définies par des fragments logiques équipés de prédicats réguliers, 2. Des résultats de non-définissabilité de langages réguliers dans des fragments logiques équipés de prédicats numériques arbitraires. La première partie de cette thèse est dédiée à l'ajout des prédicats réguliers à un fragment logique et en particulier, celui des prédicats modulaires lorsque les fragments logiques disposent de structures algébriques. La seconde partie de cette thèse est dédiée à des résultats de non définissablité, et en particulier l'étude du fragment à deux variables de la logique du premier ordreThe Straubing conjecture, stated in his book published in 1994, suggest that a regular language definable by a fragment of logic and equipped with an arbitrary numerical signature is definable using the same fragment of logic using only regular predicates. The considered fragments of logic are classed of formulas of monadic second order logic over finite words. This thesis is a contribution to the study of the Straubing conjecture. To prove such a conjecture, it seems necessary to obtain two results of two distinct types: 1. Algebraic characterizations of classes of regular languages defined by fragments of logics equipped with regular predicates, 2. Undefinability results of regular languages in fragments of logics equipped with arbitrary numerical predicates. The first part of this thesis is dedicated to the operation of adding regular predicates to a given fragment of logic, with a particular focus on modular predicates in the case where logical fragments have some algebraic structure. The second par of this thesis is dedicated to undefinability results with a particular focus on two-variable first order logic
8
Boumedine, Marc. "Contribution à l'étude et au développement de techniques d'analyse de testabilité de descriptions comportementales de circuits." Montpellier 2, 1991. http://www.theses.fr/1991MON20240.
Full textAbstract:
Ce memoire concerne l'etude et le developpement de techniques d'analyse de testabilite de descriptions comportementales de circuits. Ces techniques ont pour objectif de reduire le cout du processus de generation de sequences de test comportemental. Ce cout etant directement lie a la complexite des descriptions comportementales et a la complexite de la strategie de generation des sequences de test comportemental, les techniques presentees ont ete adaptees des domaines du test du logiciel et du test du materiel. Elles ont ete developpees au sein d'un environnement de testabilite comportementale nomme betie. Ce dernier contient les trois outils suivants: un outil de mesure de complexite de descriptions comportementales, un outil d'identification de fragments de descriptions a ameliorer et un outil de mesure de testabilite de descriptions comportementales
9
Meunier, Pierre-etienne. "Les automates cellulaires en tant que modèle de complexités parallèles." Phd thesis, Université de Grenoble, 2012. http://tel.archives-ouvertes.fr/tel-00770175.
Full textAbstract:
The intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics, such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computation.
10
Aubert, Clément. "Logique linéaire et classes de complexité sous-polynomiales." Phd thesis, Université Paris-Nord - Paris XIII, 2013. http://tel.archives-ouvertes.fr/tel-00957653.
Full textAbstract:
Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d'espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s'inspire de la géométrie de l'interaction, une délicate reconstruction de la logique linéaire à l'aide d'opérateurs d'une algèbre de von Neumann. Nous détaillons comment l'interaction d'opérateurs représentant des entiers et d'opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d'autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial.
11
Ag, Rhissa Anasser. "La conception assistée par ordinateur appliquée au routage dans les circuits intégrés VLSI." Paris 11, 1985. http://www.theses.fr/1985PA112299.
Full textAbstract:
Après avoir rappelé le processus de conception d'un circuit intégré VLSI et parlé des outils C. A. O (Conception Assistée par Ordinateur) qui lui sont nécessaires et de leur complexité, nous présentons dans cette thèse deux algorithmes d'interconnexions dans un canal à deux niveaux de technologie. Ces algorithmes utilisent des concepts de Recherche Opérationnelle. En effet, le premier est basé sur l'optimisation par graphes et le deuxième sur l'optimisation stochastique par recuit simulé ("simulated annealing''). Des exemples d'applications (partition, placement et routage global) du "simulated annealing" à la conception physique des systèmes sont aussi décrits. En général, ces méthodes nous ont permis de réduire le nombre de pistes {nécessaires aux interconnexions), par rapport aux algorithmes classiquesAfter recalling the process of the VLSI integrated circuits design and talking about the C. A. D (Computer Aided-Design) tools which are necessary for it and their complexity, we present in this thesis two algorithms of channel routing with two levels of technology. These algorithms use some concepts of operational Research. In fact, the first one is based on graphs optimization and the second on stochastic optimization by simulated annealing. Some applications (partition, placement and global routing) of simulated annealing to the physical design of systems are also described. Generally, these methods have allowed us to reduce the number of tracks (which are necessary for the interconnections) in comparison with the classical ones
12
Barloy, Corentin. "On the complexity of regular languages." Electronic Thesis or Diss., Université de Lille (2022-....), 2024. http://www.theses.fr/2024ULILB012.
Full textAbstract:
Les langages réguliers, langages calculés par automates finis, sont parmi les objets les plus simples de l'informatique théorique. Cette thèse étudie plusieurs modèles de calculs: le calcul parallèle avec les circuits booléens, le traitement en flot de documents structurés, et la maintenance d'information sur une structure soumise à des mises à jour incrémentales. Pour ce dernier modèle, les structures auxiliaires sont soit stockées en RAM, soit représentées par des bases de données mises à jour par des formules logiques.Cette thèse étudie les ressources nécessaires pour calculer des classes de langages réguliers dans chacun de ces modèles. Les méthodes employées exploitent l'interaction entre algèbre, logique et combinatoire, en mettant notamment à profit la théorie des semigroupes finis. Cette approche de la complexité s'est notamment montrée extrêmement fructueuse dans le cadre des circuits booléens, où les langages réguliers jouent un rôle central. Cette angle de recherche a été cristallisé par Howard Straubing dans son livre "Finite Automata, Formal Logic, and Circuit Complexity'', où il émet la conjecture que tout langage régulier définissable par une formule arbitraire d'un fragment de logique peut être réécrite en utilisant uniquement des prédicats simples, c'est-à-dire réguliers.Le premier but de ce manuscrit est de prouver cette conjecture dans le cas du fragment Sigma2 de la logique du premier-ordre avec une seule alternance de quantification. Un deuxième résultat propose une description de la complexité en espace, dans le modèle de flot, pour vérifier des propriétés régulières sur des arbres. Une attention particulière est portée aux propriétés vérifiables en espace constant et logarithmique. Un troisième objectif est de décrire tous les langages réguliers d'arbres pouvant être maintenus incrémentalement en temps constant en RAM. Enfin, une dernière partie porte sur le développement de formules logiques efficaces pour maintenir tous les langages réguliers dans le modèle relationnelRegular languages, languages computed by finite automata, are among the simplest objects in theoretical computer science. This thesis explores several computation models: parallel computing with Boolean circuits, structured document streaming processing, and information maintenance on a structure subject to incremental updates. For the latter, auxiliary structures are either stored in RAM or represented by databases updated by logical formulae.This thesis investigates the resources required to compute classes of regular languages in each of these models. The methods employed rely on the interaction between algebra, logic, and combinatorics, notably exploiting the theory of finite semigroups. This approach of complexity has proven extremely fruitful, particularly in the context of Boolean circuits, where regular languages play a central role. This research angle was crystallised by Howard Straubing in his book "Finite Automata, Formal Logic, and Circuit Complexity", where he conjectured that any regular language definable by an arbitrary formula from a logic fragment can be rewritten to use only simple, regular predicates.The first objective of this manuscript is to prove this conjecture in the case of the Sigma2 fragment of first-order logic with a single alternation of quantification. A second result provides a description of space complexity, in the streaming model, for verifying regular properties on trees. Special attention is given to properties verifiable in constant and logarithmic space. A third objective is to describe all regular tree languages that can be incrementally maintained in constant time in RAM. Finally, a last part focuses on the development of efficient logical formulae for maintaining all regular languages in the relational model
13
Grenet, Bruno. "Représentations des polynômes, algorithmes et bornes inférieures." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2012. http://tel.archives-ouvertes.fr/tel-00770148.
Full textAbstract:
La complexité algorithmique est l'étude des ressources nécessaires -- le temps, la mémoire, ... -- pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question " VP = VNP ? ", version algébrique de " P = NP ? ", nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables.
14
Dempster, Andrew. "Digital filter design for low-complexity implementation." Thesis, University of Cambridge, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.362967.
Full text
15
Wist, Dominic. "Attacking complexity in logic synthesis of asynchronous circuits." Phd thesis, Universität Potsdam, 2011. http://opus.kobv.de/ubp/volltexte/2012/5970/.
Full textAbstract:
Most of the microelectronic circuits fabricated today are synchronous, i.e. they are driven by one or several clock signals. Synchronous circuit design faces several fundamental challenges such as high-speed clock distribution, integration of multiple cores operating at different clock rates, reduction of power consumption and dealing with voltage, temperature, manufacturing and runtime variations. Asynchronous or clockless design plays a key role in alleviating these challenges, however the design and test of asynchronous circuits is much more difficult in comparison to their synchronous counterparts.
A driving force for a widespread use of asynchronous technology is the availability of mature EDA (Electronic Design Automation) tools which provide an entire automated design flow starting from an HDL (Hardware Description Language) specification yielding the final circuit layout. Even though there was much progress in developing such EDA tools for asynchronous circuit design during the last two decades, the maturity level as well as the acceptance of them is still not comparable with tools for synchronous circuit design. In particular, logic synthesis (which implies the application of Boolean minimisation techniques) for the entire system's control path can significantly improve the efficiency of the resulting asynchronous implementation, e.g. in terms of chip area and performance. However, logic synthesis, in particular for asynchronous circuits, suffers from complexity problems.
Signal Transitions Graphs (STGs) are labelled Petri nets which are a widely used to specify the interface behaviour of speed independent (SI) circuits - a robust subclass of asynchronous circuits.
STG decomposition is a promising approach to tackle complexity problems like state space explosion in logic synthesis of SI circuits. The (structural) decomposition of STGs is guided by a partition of the output signals and generates a usually much smaller component STG for each partition member, i.e. a component STG with a much smaller state space than the initial specification.
However, decomposition can result in component STGs that in isolation have so-called irreducible CSC conflicts (i.e. these components are not SI synthesisable anymore) even if the specification has none of them. A new approach is presented to avoid such conflicts by introducing internal communication between the components.
So far, STG decompositions are guided by the finest output partitions, i.e. one output per component. However, this might not yield optimal circuit implementations. Efficient heuristics are presented to determine coarser partitions leading to improved circuits in terms of chip area.
For the new algorithms correctness proofs are given and their implementations are incorporated into the decomposition tool DESIJ. The presented techniques are successfully applied to some benchmarks - including 'real-life' specifications arising in the context of control resynthesis - which delivered promising results.Moderner Schaltungsentwurf fokussiert hauptsächlich synchrone Schaltungstechnik mit allen inhärenten Problemen. Asynchone (d.h. ungetaktete) Schaltungen zeichnen sich jedoch nicht nur durch das Fehlen der Taktversatzproblematik gegenüber ihren synchronen Pendents aus, sondern auch insbesondere durch geringeren Energieverbrauch, günstigere EMV-Eigenschaften, hohe Performance, Modularität und Robustheit gegenüber Schwankungen in der Spannungsversorgung, im Herstellungsprozess sowie Temperaturunterschieden. Diese Vorteile werden mit höherer Integration sowie höheren Taktraten signifikanter. Jedoch ist der Entwurf und auch der Test asynchroner Schaltungen erheblich schwieriger verglichen mit synchronen Schaltungen. Entwurfswerkzeuge zur Synthese asynchroner Schaltungen aus Hochsprachen-Spezifikationen sind zwar inzwischen verfügbar, sie sind jedoch noch nicht so ausgereift und bei weitem noch nicht so akzeptiert in der Industrie, wie ihre Äquivalente für den synchronen Schaltungsentwurf. Insbesondere fehlt es an Werkzeugunterstützung im Bereich der Logiksynthese komplexer Steuerungen („Controller“), welche kritisch für die Effizienz – z.B. in Bezug auf Chipfläche und Geschwindigkeit – der resultierenden Schaltungen oder Systeme ist. Zur Spezifikation von Steuerungen haben sich Signalflankengraphen („signal transition graphs“, STGs) bewährt, die auch als Entwurfseinstieg für eine Logiksynthese von SI-Schaltungen („speed independent“) verwendet werden. (SI-Schaltungen gelten als sehr robuste asynchrone Schaltungen.) Aus den STGs werden zwecks Logiksynthese Automaten abgeleitet werden, deren Zustandszahl aber oft prohibitiv groß werden kann. Durch sogenannte STG-Dekomposition wird die Logiksynthese einer komplexen Schaltung ermöglicht, was bislang aufgrund von Zustandsexplosion oft nicht möglich war. Dabei wird der Spezifikations-STG laut einer gegebenen Partition von Ausgangssignalen in viele kleinere Teilnetze dekomponiert, wobei zu jedem Partitionsblock ein Teilnetz – mit normalerweise signifikant kleinerem Zustandsraum im Vergleich zur Spezifikation – erzeugt wird. Zu jedem Teilnetz wird dann eine Teilschaltung (Komponente) mittels Logiksynthese generiert. Durch die Anwendung von STG-Dekomposition können jedoch Teilnetze erzeugt werden, die sogenannte irreduzible CSC-Konflikte aufweisen (d.h. zu diesen Teilnetzen kann keine SI-Schaltung erzeugt werden), obwohl die Spezifikation keine solchen Konflikte hatte. Diese Arbeit präsentiert einen neuen Ansatz, welcher die Entstehung solcher irreduziblen Konflikte vermeidet, und zwar durch die Einführung interner Kommunikation zwischen den (zu den Teilnetzen gehörenden) Schaltungskomponenten. Bisher werden STG-Dekompositionen total durchgeführt, d.h. pro resultierender Komponente wird ein Ausgangssignal erzeugt. Das führt gewöhnlich nicht zu optimalen Schaltungsimplementierungen. In dieser Arbeit werden Heuristiken zur Bestimmung gröberer Ausgabepartitionen (d.h. Partitionsblöcke mit mehreren Ausgangssignalen) vorgestellt, die zu kleineren Schaltungen führen. Die vorgestellten Algorithmen werden formal abgesichert und wurden in das bereits vorhandene Dekompositionswerkzeug DESIJ integriert. An praxisrelevanten Beispielen konnten die vorgestellten Verfahren erfolgreich erprobt werden.
16
Williams, Alan John. "Theoretical and empirical studies in VLSI complexity theory." Thesis, University of Leeds, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.329174.
Full text
17
Rappaport, David 1955. "The complexity of computing simple circuits in the plane /." Thesis, McGill University, 1986. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=75339.
Full textAbstract:
As far back as Euclid's ruler and compass constructions, computation and geometry have been domains for the exploration and development of fundamental mathematical concepts and ideas. The invention of computers has spurred new research in computation, and now with a variety of applications couched in the fundamentals of Euclidean geometry, the study of geometric algorithms has again become a popular mathematical pursuit.In this thesis, the computational aspects of a fundamental problem in Euclidean geometry is examined. Given a set of line segments in the Euclidean plane, one is asked to connect all the segments to form a simple closed circuit. It is shown that for some sets of line segments it is impossible to perform this task. The problem of deciding whether a set of line segments admits a simple circuit is proved to be NP-complete. A restriction of the class of permissible input allows a polynomial time solution to the simple circuit decision problem. It is also shown that a polynomial solution can be realized by restricting the class of simple circuit in the output. All the polynomial time decision algorithms exhibited deliver a simple circuit if one exists. Furthermore, in all cases the simple circuit obtained can be optimized with respect to area or perimeter.
18
Remscrim, Zachary (Zachary N. ). "Algebraic methods in pseudorandomness and circuit complexity." Thesis, Massachusetts Institute of Technology, 2016. http://hdl.handle.net/1721.1/106089.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 93-96).
In this thesis, we apply tools from algebra and algebraic geometry to prove new results concerning extractors for algebraic sets, AC⁰-pseudorandomness, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over F₂ of substantially higher degree than the previous state-of-the-art construction. We exhibit a collection of natural functions that behave pseudorandomly with regards to AC⁰ tests. We also exactly determine the F₂-polynomial degree of the recursive Fourier sampling problem and use this to provide new partial results towards a circuit lower bound for this problem. Finally, we answer a question posed in [MR15] concerning VC dimension, interpolation degree and the Hilbert function.
by Zachary Remscrim.
Ph. D.
19
Pehlivanoglu, Serdar. "Rijndael Circuit Level Cryptanalysis." Link to electronic thesis, 2005. http://www.wpi.edu/Pubs/ETD/Available/etd-050505-121816/.
Full textAbstract:
Thesis (M.S.) -- Worcester Polytechnic Institute.Keywords: private-key cryptography; Advanced Encryption Standard; K-secure; hermetic; block cipher; circuit complexity. Includes bibliographical references (p. 75-79).
20
Dickinson, Alex. "Complexity management and modelling of VLSI systems." Title page, contents and abstract only, 1988. http://web4.library.adelaide.edu.au/theses/09PH/09phd553.pdf.
Full text
21
Sengupta, Rimli. "Lower bounds for natural functions in restricted boolean circuits." Diss., Georgia Institute of Technology, 1995. http://hdl.handle.net/1853/8269.
Full text
22
Diouf, Cherif El Valid. "Modélisation comportementale de drivers de ligne de transmission pour des besoins d'intégrité du signal et de compatibilité électromagnétique." Thesis, Brest, 2014. http://www.theses.fr/2014BRES0040/document.
Full textAbstract:
La miniaturisation de circuits intégrés, les hautes fréquences de fonctionnement, la baisse des potentiels d'alimentation, les fortes densités d'intégration rendent les signaux numériques propagés sur les interconnexions très susceptibles à la dégradation voire à la corruption. En vue d’évaluer la compatibilité électromagnétique et l’intégrité du signal il est nécessaire de disposer dès les premières phases de développement de modèles précis de ces interconnexions pour les insérer dans les simulateurs temporels. Nos travaux s'inscrivent dans ce contexte et concernent plus particulièrement la modélisation comportementale des buffers et drivers de ligne de transmission. Ils ont abouti à une approche originale de modélisation notamment basée sur les séries de Volterra-Laguerre. Les modèles boites noires développés disposent d’une implémentation SPICE assez simple autorisant ainsi une très bonne portabilité. Ils sont faciles à identifier et disposent d’une complexité paramétrique permettant un gain important de temps de simulation vis-à-vis des modèles transistors des drivers. En outre les méthodes développées permettent une modélisation dynamique non linéaire plus précise du port de sortie, et une gestion plus générale des entrées autorisant notamment une très bonne prise en compte du régime de sur-cadencement ce que par exemple ne fait pas le standard IBISIntegrated circuits miniaturization, high operating frequencies, lower supply voltages, high-density integration make digital signals propagating on interconnects highly vulnerable to degradation. Assessing EMC and signal integrity in the early stages of the design flow requires accurate interconnect models allowing for efficient time-domain simulations. In this context, our work addressed the issue of behavioral modeling of transmission line buffers, and particularly that of drivers. The main result is an original modeling approach partially based on Volterra-Laguerre series. The black box models we developed have a fairly simple implementation in SPICE thus allowing a very good portability. They are easy to identify and have a parametric complexity allowing a large gain in simulation time with respect to transistor driver models. In addition, the developed methods allow a more accurate output port nonlinear dynamics modeling, and a more general management of inputs. A very good reproduction of driver behaviour in overclocking conditions provides a significant advantage over standard IBIS models
23
Martin, Denis. "Delay computation in switch-level models of MOS circuits." Thesis, McGill University, 1988. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=64038.
Full text
24
Boyd, Mark J. "Complexity analysis of a massive parallel boolean satisfiability implication circuit /." Diss., Digital Dissertations Database. Restricted to UC campuses, 2005. http://uclibs.org/PID/11984.
Full text
25
Rodrigues, M. R. D. "A tree-based algorithm for component placement." Thesis, University of Manchester, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.376139.
Full text
26
Wist, Dominic [Verfasser], and Werner [Akademischer Betreuer] Zorn. "Attacking complexity in logic synthesis of asynchronous circuits / Dominic Wist. Betreuer: Werner Zorn." Potsdam : Universitätsbibliothek der Universität Potsdam, 2012. http://d-nb.info/1022935313/34.
Full text
27
Stockhusen, Christoph [Verfasser]. "On the space and circuit complexity of parameterized problems / Christoph Stockhusen." Lübeck : Zentrale Hochschulbibliothek Lübeck, 2017. http://d-nb.info/1129726657/34.
Full text
28
Contreras, Andres A. "Micronetworking: Reliable Communication on 3D Integrated Circuits." DigitalCommons@USU, 2010. https://digitalcommons.usu.edu/etd/728.
Full textAbstract:
The potential failure in through-silicon vias (TSVs) still poses a challenge in trying to extend the useful life of a 3D integrated circuit (IC). A model is proposed to mitigate the communication problem in 3D integrated circuits caused by the breaks at the TSVs. We provide the details of a low-complexity network that takes advantages of redundant TSVs to make it possible to re-route around breaks and maintain effective communication between layers. Different configurations for the micronetwork are analyzed and discussed. We also present an evaluation of the micronetwork's performance, which turns out to be quite promising, based on several Monte Carlo simulations. Finally, we provide some directions for future research on the subject.
29
Ozgur, Soner. "Reduced Complexity Sequential Monte Carlo Algorithms for Blind Receivers." Diss., Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/10518.
Full textAbstract:
Monte Carlo algorithms can be used to estimate the state of a system given relative observations. In this dissertation, these algorithms are applied to physical layer communications system models to estimate channel state information, to obtain soft information about transmitted symbols or multiple access interference, or to obtain estimates of all of these by joint estimation.
Initially, we develop and analyze a multiple access technique utilizing mutually orthogonal complementary sets (MOCS) of sequences. These codes deliberately introduce inter-chip interference, which is naturally eliminated during processing at the receiver. However, channel impairments can destroy their orthogonality properties and additional processing becomes necessary.
We utilize Monte Carlo algorithms to perform joint channel and symbol estimation for systems utilizing MOCS sequences as spreading codes. We apply Rao-Blackwellization to reduce the required number of particles. However, dense signaling constellations, multiuser environments, and the interchannel interference introduced by the spreading codes all increase the dimensionality of the symbol state space significantly. A full maximum likelihood solution is computationally expensive and generally not practical. However, obtaining the optimum solution is critical, and looking at only a part of the symbol space is generally not a good solution. We have sought algorithms that would guarantee that the correct transmitted symbol is considered, while only sampling a portion of the full symbol space. The performance of the proposed method is comparable to the Maximum Likelihood (ML) algorithm. While the computational complexity of ML increases exponentially with the dimensionality of the problem, the complexity of our approach increases only quadratically.
Markovian structures such as the one imposed by MOCS spreading sequences can be seen in other physical layer structures as well. We have applied this partitioning approach with some modification to blind equalization of frequency selective fading channel and to multiple-input multiple output receivers that track channel changes.
Additionally, we develop a method that obtains a metric for quantifying the convergence rate of Monte Carlo algorithms. Our approach yields an eigenvalue based method that is useful in identifying sources of slow convergence and estimation inaccuracy.
30
Johansson, Kenny. "Low Power and Low Complexity Shift-and-Add Based Computations." Doctoral thesis, Linköping : Department of Electrical Engineering, Linköping University, 2008. http://www.bibl.liu.se/liupubl/disp/disp2008/tek1201s.pdf.
Full text
31
Kim, Jina. "Area and Power Conscious Rake Receiver Design for Third Generation WCDMA Systems." Thesis, Virginia Tech, 2003. http://hdl.handle.net/10919/30972.
Full textAbstract:
A rake receiver, which resolves multipath signals corrupted by a fading channel, is the most complex and power consuming block of a modem chip. Therefore, it is essential to design a rake receiver be efficient in hardware and power. We investigated a design of a rake receiver for the WCDMA (Wideband Code Division Multiple Access) system, which is a third generation wireless communication system. Our rake receiver design is targeted for mobile units, in which low-power consumption is highly important. We made judicious judgments throughout our design process to reduce the overall circuit complexity by trading with the performance. The reduction of the circuit complexity results in low power dissipation for our rake receiver. As the first step in the design of a rake receiver, we generated a software prototype in MATLAB. The prototype included a transmitter and a multipath Rayleigh fading channel, as well as a rake receiver with four fingers. Using the software prototype, we verified the functionality of all blocks of our rake receiver, estimated the performance in terms of bit error rate, and investigated trade-offs between hardware complexity and performance. After the verification and design trade-offs were completed, we manually developed a rake receiver at the RT (Register Transfer) level in VHDL. We proposed and incorporated several schemes in the RT level design to enhance the performance of our rake receiver. As the final step, the RT level design was synthesized to gate level circuits targeting TSMC 0.18 mm CMOS technology under the supply voltage of 1.8 V. We estimated the performance of our rake receiver in area and power dissipation. Our experimental results indicate that the total power dissipation for our rake receiver is 56 mW and the equivalent NAND2 circuit complexity is 983,482. We believe that the performance of our rake receiver is quite satisfactory.Master of Science
32
Elberfeld, Michael [Verfasser]. "Space and circuit complexity of monadic second-order definable problemes on tree-decomposable structures / Michael Elberfeld." Lübeck : Zentrale Hochschulbibliothek Lübeck, 2013. http://d-nb.info/1033201855/34.
Full text
33
Gedin, Emanuel. "Hardness of showing hardness of the minimum circuit size problem." Thesis, KTH, Teoretisk datalogi, TCS, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-232218.
Full textAbstract:
The problem of finding the smallest size of a circuit that computes a given boolean function, usually referred to as the minimum circuit size problem (MCSP), has been studied for many years but it is still unknown whether or not the problem is NP-hard. With this in mind we study properties of potential reductions to this problem. The reductions in focus are local natural reductions which has been common in other well-known proofs of NP-hardness. We present a generalized method that shows the existence of an algorithm solving any problem which has a local natural reduction to MCSP. In particular we show that if the decision problem of distinguishing satisfiable 3-SAT instances from those where at most 7/8 + o(1) of the clauses can be satisfied has a reduction to MCSP where any arbitrary bit of the output can be computed in O(n1 - ε) time for any ε > 0 then k-SAT can be solved by a circuit of depth 3 and size 2o(n).Problemet att finna den minsta storleken på en krets som beräknar en given boolesk funktion, ofta kallat minimum circuit size problem (MCSP), har studerats i många år men det är fortfarande okänt om problemet är NP-svårt eller inte. Med detta i åtankte studerar vi egenskaper hos potentiella reduktioner till det här problemet. Vi fokuserar på naturliga lokala reduktioner som är vanliga i många bevis av NP-svårighet. Vi presenterar en method som visar att det finns en algorithm för att lösa varje problem som har en lokal naturlig reduktion till MCSP. Vi visar att om beslutsproblemet att skilja satisfierbara instanser av 3-SAT från de där som mest 7/8 + o(1) av klausulerna går att satisfiera har en reduktion till MCSP där en godtycklig bit av utdata kan beräknas i O(n1 - ε) tid för varje ε > 0 då kan k-SAT lösas av en krets med djup 3 och storlek 2o(n).
34
Mengel, Stefan Verfasser], Peter [Akademischer Betreuer] Bürgisser, auf der Heide Friedhelm [Akademischer Betreuer] [Meyer, and Luc [Akademischer Betreuer] Segoufin. "Conjunctive queries, arithmetic circuits and counting complexity / Stefan Mengel. Betreuer: Peter Bürgisser ; Friedhelm Meyer auf der Heide ; Luc Segoufin." Paderborn : Universitätsbibliothek, 2013. http://d-nb.info/1038000505/34.
Full text
35
Mengel, Stefan Verfasser], Peter [Akademischer Betreuer] [Bürgisser, auf der Heide Friedhelm [Akademischer Betreuer] Meyer, and Luc [Akademischer Betreuer] Segoufin. "Conjunctive queries, arithmetic circuits and counting complexity / Stefan Mengel. Betreuer: Peter Bürgisser ; Friedhelm Meyer auf der Heide ; Luc Segoufin." Paderborn : Universitätsbibliothek, 2013. http://nbn-resolving.de/urn:nbn:de:hbz:466:2-11944.
Full text
36
Sengupta, Arindam. "Multidimensional Signal Processing Using Mixed-Microwave-Digital Circuits and Systems." University of Akron / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=akron1407977367.
Full text
37
Bouraoui, Mustapha. "Elaboration et implantation sur DSP d'un codeur bas débit de la parole de faible complexité : apport des codes correcteurs parfaits." Grenoble INPG, 1997. http://www.theses.fr/1997INPG0077.
Full textAbstract:
Cette etude a pour objet l'elaboration et l'implantation d'un codeur de parole de type celp. L'application visee concerne le stockage des messages telephoniques dans un repondeur numerique. Etant donnee le contexte industriel de cette etude, une attention particuliere a ete portee a la complexite du codeur a elaborer. C'est ainsi qu'un quantificateur vectoriel algebrique spherique a ete mis au point pour coder le signal de parole residuel. Ce quantificateur est base sur des codes correcteurs d'erreurs parfaits et presente une tres faible complexite de mise en uvre ainsi que de bonnes performances. Un codeur de parole de type celp a 4800 bps, faisant intervenir ce type de quantification, a ete developpe en vue d'une implantion sur un dsp a virgule fixe.
38
MOLTENI, MARIA CHIARA. "ON THE SECURITY OF CRYPTOGRAPHIC CIRCUITS:PROTECTION AGAINST PROBING ATTACKS AND PERFORMANCE IMPROVEMENT OF GARBLED CIRCUITS." Doctoral thesis, Università degli Studi di Milano, 2022. http://hdl.handle.net/2434/920426.
Full textAbstract:
Dealing with secure computation and communication in hardware devices, an attacker that threatens to security of the systems can be of two different types.
The first type of attacker is external to the exchange of secret messages and tries to steal some sensitive information. Probing a circuit is a useful technique through which an attacker can derive information correlated with the secret manipulated by a cryptographic circuit. Probing security is the branch of research that tries to devise models, tools and countermeasures against this type of attacks. We define a new methodology that allows to determine if a gadget (i.e., a portion of a circuit) is secure against probing attacks. Moreover, we reason about composability of gadgets, in such a way that also this composition is probing secure. The reasoning is extended also to the case in which glitches are considered, namely when the attacks are mounted when timing hazards are present. The proposed methodology is based on the construction of the Walsh matrix of a Boolean function that describes the operations of the circuit. This method allows reaching an exact solution, but generally needs a lot of computation’s time (mainly for big gadgets). To overcome the problem, we propose to compute the Walsh matrix exploiting the theory and applications of Algebraic Decision Diagrams (ADDs).
Different is the case when the malicious part is internal: each party is interested in protecting its own sensitive information from all the others. When the parties are only two, from literature the garbled circuit protocol is a solution that allows to reach a result implying some secrets, without sharing them. The cost of this protocol depends on the number of extit{and} gates in the circuit that implements the Boolean function describing the protocol computations. In this context, we work to reduce the number of multiplications in two classes of particular Boolean functions, called autosymmetric and D-reducible. Moreover, in the context of the garbled circuit protocol, we discuss some innovative solutions to further reduce the protocol's costs, as the application of the 3-valued logic. This logic is an extension of the Boolean one, resulting from the addition of a new element to the set Boolean set ${0,1}$.
39
Colledan, Andrea. "On the Hidden Subgroup Problem as a Pivot in Quantum Complexity Theory." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/16112/.
Full textAbstract:
Quantum computing has opened the way to new algorithms that can efficiently solve problems that have always been deemed intractable. However, since quantum algorithms are hard to design, the necessity to find a generalization of these problems arises. Such necessity is satisfied by the hidden subgroup problem (HSP), an abstract problem of group theory which successfully generalizes a large number of intractable problems. The HSP plays a significant role in quantum complexity theory, as efficient algorithms that solve it can be employed to efficiently solve other valuable problems, such as integer factorization, discrete logarithms, graph isomorphism and many others.
In this thesis we give a computational definition of the HSP. We then prove the reducibility of some of the aforementioned problems to the HSP. Lastly, we introduce some essential notions of quantum computing and we present two quantum algorithms that efficiently solve the HSP on Abelian groups.
40
Malod, Guillaume. "Polynômes et coefficients." Phd thesis, Université Claude Bernard - Lyon I, 2003. http://tel.archives-ouvertes.fr/tel-00087399.
Full textAbstract:
Valiant définit des analogues algébriques des classes P et NP. Nous caractérisons les classes VP et VQP, d'où une preuve simplifiée de VNP = VNPe et de la VQP-complétude du déterminant, et la preuve d'une conjecture de Bürgisser. Les classes VPo et VNPo, définies sans constantes arbitraires, donnent facilement un lien entre la complexité d'un polynôme et celle de sa fonction coefficient: VNPo est stable par passage à la fonction coefficient et réciproquement; supposer ce résultat pour VPo est équivalent à VPo = VNPo. Pour traiter le cas du degré non borné, il faut un calcul rapide des coefficients binomiaux, faisable en caractéristique positive et peu probable en caractéristique 0. Nous étudions enfin un problème lié: l'effet de la dérivation sur la complexité. Nous retrouvons le résultat de Kaltofen (le nombre de variables fait exploser la taille plus que l'ordre de dérivation) et donnons un calcul simultané des dérivées partielles.
41
Zhang, Wei Zhang. "Wireless receiver designs from information theory to VLSI implementation /." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/31817.
Full textAbstract:
Thesis (Ph.D)--Electrical and Computer Engineering, Georgia Institute of Technology, 2010.Committee Chair: Ma, Xiaoli; Committee Member: Anderson, David; Committee Member: Barry, John; Committee Member: Chen, Xu-Yan; Committee Member: Kornegay, Kevin. Part of the SMARTech Electronic Thesis and Dissertation Collection.
42
Harwath, Frederik. "On Invariant Formulae of First-Order Logic with Numerical Predicates." Doctoral thesis, Humboldt-Universität zu Berlin, 2018. http://dx.doi.org/10.18452/19609.
Full textAbstract:
Diese Arbeit untersucht ordnungsinvariante Formeln der Logik erster Stufe
(FO) und einiger ihrer Erweiterungen, sowie andere eng verwandte Konzepte der endlichen Modelltheorie. Viele Resultate der endlichen Modelltheorie nehmen an, dass Strukturen mit einer Einbettung ihres Universums in ein Anfangsstück der natürlichen Zahlen ausgestattet sind. Dies erlaubt es, beliebige Relationen (z.B. die lineare Ordnung) und Operationen (z.B. Addition, Multiplikation) von den natürlichen Zahlen auf solche Strukturen zu übertragen.
Die resultierenden Relationen auf den endlichen Strukturen werden als numerische Prädikate bezeichnet. Werden numerische Prädikate in Formeln verwendet, beschränkt man sich dabei häufig auf solche Formeln, deren Wahrheitswert auf endlichen Strukturen invariant unter Änderungen der Einbettung der Strukturen ist. Wenn das einzige verwendete numerische Prädikat eine lineare Ordnung ist, spricht man beispielsweise von ordnungsinvarianten Formeln. Die Resultate dieser Arbeit können in drei Teile unterteilt werden.
Der erste Teil betrachtet die Lokalitätseigenschaften von FO-Formeln mit Modulo-Zählquantoren, die beliebige numerische Prädikate invariant nutzen.
Der zweite Teil betrachtet FO-Sätze, die eine lineare Ordnung samt der zugehörigen Addition auf invariante Weise nutzen, auf endlichen Bäumen. Es wird gezeigt, dass diese dieselben regulären Baumsprachen definieren, wie FO-Sätze ohne numerische Prädikate mit bestimmten Kardinalitätsprädikaten. Für den Beweis wird eine algebraische Charakterisierung der in dieser Logik definierbaren Baumsprachen durch Operationen auf Bäumen entwickelt.
Der dritte Teil der Arbeit beschäftigt sich mit der Ausdrucksstärke und der Prägnanz
von FO und Erweiterungen von FO auf Klassen von Strukturen beschränkter Baumtiefe.This thesis studies the concept of order-invariance of formulae of first-order logic (FO) and some of its extensions as well as other closely related concepts from finite model theory. Many results in finite model theory assume that structures are equipped with an embedding of their universe into an initial segment of the natural numbers. This allows to transfer arbitrary relations (e.g. linear order) and operations (e.g. addition, multiplication) on the natural numbers to structures. The arising relations on the structures are called numerical predicates. If formulae use these numerical predicates, it is often desirable to consider only such formulae whose truth value in finite structures is invariant under changes to the embeddings of the structures. If the numerical predicates include only a linear order, such formulae are called order-invariant. We study the effect of the invariant use of different kinds of numerical predicates on the expressive power of FO and extensions thereof. The results of this thesis can be divided into three parts. The first part considers the locality and non-locality properties of formulae of FO with modulo-counting quantifiers which may use arbitrary numerical predicates in an invariant way. The second part considers sentences of FO which may use a linear order and the corresponding addition in an invariant way and obtains a characterisation of the regular finite tree languages which can be defined by such sentences: these are the same tree languages which are definable by FO-sentences without numerical predicates with certain cardinality predicates. For the proof, we obtain a characterisation of the tree languages definable in this logic in terms of algebraic operations on trees. The third part compares the expressive power and the succinctness of different ex- tensions of FO on structures of bounded tree-depth.
43
Katabira, Joseph. "Groverův algoritmus v kvantovém počítání a jeho aplikace." Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2021. http://www.nusl.cz/ntk/nusl-445458.
Full textAbstract:
Kvantová výpočetní technika je rychle rostoucí obor informatiky, který přenáší principy kvantových jevu do našeho každodenního života. Díky své kvantové podstatě získávají kvantové počítače převahu nad klasickými počítači. V této práci jsme se zaměřili na vysvětlení základů kvantového počítání a jeho implementaci na kvantovém počítači. Zejména se zaměřujeme na popis fungování, konstrukci a implementaci Groverova algoritmu jako jednoho ze základních kvantových algoritmů. Demonstrovali jsme sílu tohoto kvantového algoritmu při prohledávání databáze a porovnávali ho s klasickými nekvantovými algoritmy pomocí implementace prostřednictvím simulačního prostředí QISKit. Pro simulaci jsme použili QASM Simulator a State vector Simulator Aer backends a ukázali, že získané výsledky korelují s dříve diskutovanými teoretickými poznatky. Toto ukazuje, že Groverův algoritmus umožňuje kvadratické zrychlení oproti klasickému nekvantovému vyhledávacímu algoritmu, Použitelnost algoritmu stejně jako ostatních kvantových algoritmů je ale stále omezena několika faktory, mezi které patří vysoké úrovně dekoherence a chyby hradla.
44
Sadi, Muhammad Sheikh. "Towards minimizing the risks of soft errors at the design level of embedded systems." Thesis, Curtin University, 2009. http://hdl.handle.net/20.500.11937/1300.
Full textAbstract:
The risks of soft errors increase with system complexity, reduction in operational voltages, exponential growth in transistors per chip, increases in clock frequencies and device shrinking. Research into techniques to cope with soft errors has mostly focused on post-design phases such as circuit level solutions, logic level solutions, spatial redundancy, temporal redundancy, and/or error correction codes. Clearly, though, it would be better to tackle the issue early in the design process. A novel method is outlined in this research for assigning a criticality ranking to the components in a design at the conceptual phase. The ranking is easily derived with little computational effort. Further, the research flags why the component is critical. The model is then examined by refactoring to lower each component’s criticality until the goal of minimising the risks of soft errors is satisfied and constraints are maintained. The methodology is then tested against real-life systems that must have high reliability.
45
Meunier, Pierre-Etienne. "Les automates cellulaires en tant que modèle de complexités parallèles." Thesis, 2012. http://www.theses.fr/2012GRENM065/document.
Full textAbstract:
The intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics�� such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computationThe intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics, such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computation
46
Pénzes, Paul Ivan. "Energy-delay complexity of asynchronous circuits." Thesis, 2002. https://thesis.library.caltech.edu/6263/1/Penzes_pi_2002.pdf.
Full textAbstract:
In this thesis, a circuit-level theory of energy-delay complexity is developed for asynchronous circuits. The energy-delay efficiency of a circuit is characterized using the metric Et^n , where E is the energy consumed by the computation, t is the delay of the computation, and n is a positive number that reflects a chosen trade-off between
energy and delay. Based on theoretical and experimental evidence, it is argued that for a circuit optimized for minimal Et^n, the consumed energy is independent, in first
approximation, of the types of gates (NAND, NOR, etc.) used by the circuit and is solely dependent on n and the total amount of wiring capacitance switched during computation. Conversely, the circuit speed is independent, in first approximation, of the wiring capacitance and depends only on n and the types of gates used.
The complexity model allows us to compare the energy-delay efficiency of two circuits implementing the same computation. On the other hand, the complexity model itself does not say much about the actual transistor sizes that achieve the optimum. For this reason, the problem of transistor sizing of circuits optimized for Et^n is investigated, as well. A set of analytical formulas that closely approximate the optimal transistor sizes are explored. An efficient iteration procedure that can further
improve the original analytical solution is then studied. Based on these results, a novel transistor-sizing algorithm for energy-delay efficiency is introduced.
It is shown that the Et^n metric for the energy-delay efficiency index n ≥ 0 characterizes any optimal trade-off between the energy and the delay of a computation. For
example, any problem of minimizing the energy of a system for a given target delay can be restated as minimizing Et^n for a certain n. The notion of minimum-energy function is developed and applied to the parallel and sequential composition of circuits in general and, in particular, to circuits optimized through transistor sizing and
voltage scaling. Bounds on the energy and delay of the optimized circuits are computed, and necessary and sufficient conditions are given under which these bounds are
reached. Necessary and sufficient conditions are also given under which components of a design can be optimized independently so as to yield a global optimum when
composed. Through these applications, the utility of the minimum-energy function is demonstrated. The use of this minimum-energy function yields practical insight into
ways of improving the overall energy-delay efficiency of circuits.
47
Jang, Jing-Tang Keith. "The size and depth of Boolean circuits." 2013. http://hdl.handle.net/2152/21370.
Full textAbstract:
We study the relationship between size and depth for Boolean circuits. Over four decades, very few results were obtained for either special or general Boolean circuits. Spira showed in 1971 that any Boolean formula of size s can be simulated in depth O(log s). Spira's result means that an arbitrary Boolean expression can be replaced by an equivalent "balanced" expression, that can be evaluated very efficiently in parallel. For general Boolean circuits, the strongest known result is that Boolean circuits of size s can be simulated in depth O(s / log s). We obtain significant improvements over the general bounds for the size versus depth problem for special classes of Boolean circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth O(sqrt{s log s}). For planar circuits and synchronous circuits of size s, we obtain simulations of depth O(sqrt{s}). Improving any of the above results by polylog factors would immediately improve the bounds for general circuits. We generalize Spira's theorem and show that any Boolean circuit of size s with segregators of size f(s) can be simulated in depth O(f(s)log s). This improves and generalizes a simulation of polynomial-size Boolean circuits of constant treewidth k in depth O(k² log n) by Jansen and Sarma. Since the existence of small balanced separators in a directed acyclic graph implies that the graph also has small segregators, our results also apply to circuits with small separators. Our results imply that the class of languages computed by non-uniform families of polynomial size circuits that have constant size segregators equals non-uniform NC¹. As an application of our simulation of circuits in small depth, we show that the Boolean Circuit Value problem for circuits with constant size segregators (or separators) is in deterministic SPACE (log² n). Our results also imply that the Planar Circuit Value problem, which is known to be P-Complete, is in SPACE (sqrt{n} log n). We also show that the Layered Circuit Value and Synchronous Circuit Value problems, which are both P-complete, are in SPACE(sqrt{n}). Our study of circuits with small separators and segregators led us to obtain space efficient algorithms for computing balanced graph separators. We extend this approach to obtain space efficient approximation algorithms for the search and optimization versions of the SUBSET SUM problem, which is one of the most studied NP-complete problems. Finally we study the relationship between simultaneous time and space bounds on Turing machines and Boolean circuit depth. We observe a new connection between planar circuit size and simultaneous time and space products of input-oblivious Turing machines. We use this to prove quadratic lower bounds on the product of time and space for several explicit functions for input-oblivious Turing machines.text
48
Revol, Nathalie. "Complexite de l'evaluation parallele des circuits arithmetiques." Phd thesis, 1994. http://tel.archives-ouvertes.fr/tel-00005109.
Full textAbstract:
Les algorithmes d'evaluation parallele des expressions et des circuits arithmetiques peuvent etre vus comme des extracteurs du parallelisme intrinseque contenu dans les programmes sequentiels, parallelisme qui depasse celui qui peut etre lu sur le graphe de precedence et qui tient a la semantique des operateurs utilises. La connaissance des proprietes algebriques, comme l'associativite ou la distributivite, permet une reorganisation des calculs qui n'affecte pas les resultats. Plus la structure algebrique utilisee sera riche en proprietes, plus il sera possible d'en tirer parti pour ameliorer les algorithmes d'evaluation. Generalisant les algorithmes concus pour les semi-anneaux, nous proposons un algorithme qui ameliore les majorations precedemment connues pour la contraction de circuits arithmetiques dans un treillis. Des simulations de cet algorithme ont permis de mettre en evidence ses qualites de << predicteur automatique de complexite >>. Reorganiser explicitement les calculs a l'aide de ces algorithmes, c'est-a-dire realiser un compilateur complet, permet de comparer la realite des algorithmes paralleles sur machines a memoire distribuee et la puissance des algorithmes theoriques. Un prototype a ete realise, base sur une simplification/extension du langage C. Enfin, l'interet de ces techniques dans le domaine de la parallelisation des nids de boucles, pour guider la recherche de reductions cachees dans ces nids, semble prometteuse, parce qu'elle est peu couteuse a mettre en oeuvre et fournit des informations de qualite. En cela, les recherches en algorithmique parallele theorique rejoignent les preoccupations de la parallelisation effective.
49
Jansen, Maurice Julien. "Lower bound frontiers in arithmetical circuit complexity." 2006. http://proquest.umi.com/pqdweb?did=1184170821&sid=9&Fmt=2&clientId=39334&RQT=309&VName=PQD.
Full textAbstract:
Thesis (Ph.D.)--State University of New York at Buffalo, 2006.Title from PDF title page (viewed on Feb. 28, 2007) Available through UMI ProQuest Digital Dissertations. Thesis adviser: Regan, Kenneth W.
50
西村, 治道, and Harumichi Nishimura. "Computational Complexity Theory of Quantum Turing Machines and Quantum Circuits." Thesis, 2001. http://hdl.handle.net/2237/15822.
Full text