Добірка наукової літератури з теми "Complexité de circuits"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Complexité de circuits".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Complexité de circuits"
1
Poizat, Bruno. "A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant." Journal of Symbolic Logic 73, no. 4 (December 2008): 1179–201. http://dx.doi.org/10.2178/jsl/1230396913.
Повний текст джерелаАнотація:
RésuméNous définissons une classe de suites de polynômes, calculés par des circuits de complexité polynomiale comprenant des additions, des soustractions. des multiplications et des sommations de Valiant. Nous montrons que cette classe est close pour la prise de la fonction-coefficient. définie au paragraphe 3 de cet article; nous en déduisons l'existence d'un circuit de complexité 72.n2, calculant le coefficient binomial de deux nombres de n chiffres, donnés en base 2. Il est par ailleurs facile de construire un circuit de complexité 17.n + 2 calculant la factorielle d'un nombre de n chiffres. La présence de 2.n sommations d'effet exponentiel dans chacun de ces circuits en affecte gravement l'intérêt pratique. II est peu probable, ou du moins peu souhaitable. qu'on puisse éliminer ces sommations sans explosion, car cela provoquerait la catastrophe cryptographique que redoutent tous les banquiers; néanmoins, nous ne savons pas séparer la classe définie ici de celle des suites de polynômes calculables en un nombre polynomial d'opérations arithmétiques. Cela n'a rien de surprenant, vu la très grande affinité qu'elle a avec la classe PSPACE: nous montrons en effet que cette classe est identique à la classe VPSPACE, définie antérieurement par Koiran et Perifel, qui apparaît ici sous une forme bien plus maniable que l'originale.
2
Raton, Gwenaëlle. "Les circuits courts alimentaires." Multitudes 92, no. 3 (September 21, 2023): 79–85. http://dx.doi.org/10.3917/mult.092.0079.
Повний текст джерелаАнотація:
Cet article illustre de façon concrète et détournée les relations villes-campagnes. Les circuits courts alimentaires sont considérés comme vertueux (réduction des intermédiaires et des distances, « locavorisme »), mais qu’en est-il vraiment de leur durabilité, compte-tenu de leur complexité logistique ? Pour le producteur, premier maillon de la chaîne, la commercialisation et le transport représentent travail et coûts supplémentaires. Les circuits courts ne sont pas moins énergivores : flux entre fermes et points de vente fragmentés en une multitude de petits volumes. L’auteur propose plusieurs formes d’organisation pour pallier à ces inconvénients : mutualiser le transport entre producteurs partenaires et promouvoir une coopération logistique territoriale, consolider le transfert de flux en le déléguant à un prestataire extérieur. L’enjeu de la logistique et le rôle des intermédiaires non commerciaux sont clé.
3
Berthoz, Alain, Jean-Pierre Benoit, and Alexandrine Saint-Cast. "Penser son corps : quand le cerveau simplifie la complexité." Enfances & Psy N° 97, no. 3 (October 30, 2023): 15–28. http://dx.doi.org/10.3917/ep.097.0015.
Повний текст джерелаАнотація:
Comment le corps est-il intégré ? Les travaux des neurosciences et de la neurophysiologie révèlent aujourd’hui les circuits cérébraux qui permettent de passer du corps à sa pensée. Ces phénomènes pluriels d’une grande complexité se réalisent grâce à la simplexité qui intègre aussi l’inhibition et l’oubli. L’unification corps-cerveau participe à l’identité. Elle s’inscrit dans l’intersubjectivité par empathie et sympathie. La recherche, différentes expériences neurophysiologiques, confirment ces descriptions et permettent de mieux comprendre les troubles psychomoteurs.
4
Basso Fossali, Pierluigi. "La complexité régulatrice des discours programmateurs. Circuits sociaux de la modalisation et instances critiques." Langue française N°206, no. 2 (2020): 45. http://dx.doi.org/10.3917/lf.206.0045.
Повний текст джерела
5
Clément, Camille. "Le lieu agricole périurbain : un analyseur de la complexité des constructions territoriales entre actions politiques, débats publics et pratiques spatiales." Nouvelles perspectives en sciences sociales 10, no. 1 (February 4, 2015): 27–57. http://dx.doi.org/10.7202/1028436ar.
Повний текст джерелаАнотація:
Cet article a pour objectif d’éclairer la complexité des constructions et appropriations territoriales à partir de l’étude croisée des actions politiques, débats publics et pratiques spatiales de la communauté de communes du Pays de Lunel (Languedoc). En cours de périurbanisation, ce territoire mise sur son ancrage agricole et rural pour se différencier des agglomérations en expansion de Montpellier et de Nîmes. C’est donc par la thématique agricole qu’une étude qualitative du SCOT (Schéma de Cohérence Territoriale), d’un projet de circuits courts et d’un pôle oenotouristique (actions politiques) ont été étudiés afin de saisir cinq débats publics (étude de la presse régionale et intercommunautaire) qui sont directement en lien avec les choix politiques réalisés par cette instance territoriale. Au final, l’étude montre que ces actions politiques et débats publics doivent être mis en relation avec les pratiques spatiales observées dans le territoire. Ce n’est qu’à l’échelle du lieu agricole périurbain que ces trois notions s’alimentent mutuellement afin de montrer la complexité des appropriations territoriales, appropriations par le politique (actions politiques et débats publics) et appropriations par la pratique.
6
Poizat, Bruno. "Une dualité entre fonctions booléennes." Journal of the Institute of Mathematics of Jussieu 9, no. 3 (April 26, 2010): 633–52. http://dx.doi.org/10.1017/s1474748010000083.
Повний текст джерелаАнотація:
RésuméSi k est un corps fini, toute fonction f(x1, … , xm) de {0, 1}m dans k s'écrit de manière unique comme un polynôme, à coefficients dans k, de degré un ou zéro en chacune de ses variables ; on peut donc lui associer une fonction f*(x1, … , xm), sa duale inverse, qui exprime les coefficients de son polynôme canonique. Nous considérons l'improbable hypothèse que la classe P(k), formée des suites de fonctions calculables en un nombre d'opérations (additions et multiplications) de croissance polynomialement bornée, soit close par dualité ; nous montrons qu'elle équivaut à une hypothèse bien connue en Théorie de la Complexité sous le nom de P = #pP, où p est la caractéristique de k.Dans une première section, nous exposons ce résultat lorsque k = ℤ/2ℤ, c'est-à-dire dans le cadre des calculs booléens classiques ; sa démonstration évite l'emploi d'un polynôme universel comme le hamiltonien : ses ingrédients sont d'une part la réduction parcimonieuse des circuits aux termes, et d'autre part la constatation que les expressions arithmétiques ont une duale très facile à calculer.Dans la deuxième section, nous traitons le cas général, en introduisant une classe SP(k) obtenue par sommation à partir de la classe P(k) ; nous vérifierons dans la quatrième section l'équivalence des hypothèses SP(k) = P(k) et #pP = P. Nous y définissons également une notion de transformation, dont la dualité est un cas particulier. Les transformations forment un groupe isomorphe à GL2(k), avec un sous-groupe B(k) de transformations que nous qualifions de bénignes, car elles n'ont que peu d'effet sur la complexité des fonctions ; nous montrons que toutes les transformations non-bénignes ont à peu près la même influence sur la complexité des fonctions, sauf si k = F3 ou k = F5 ; dans ces deux cas exceptionnels, la transformation de Fourier joue un rôle particulier.Dans la troisième section, nous considérons des fonctions de km dans k ; nous n'y trouvons pas des classes de complexité vraiment nouvelles, mais seulement un groupe de transformations plus riche.La quatrième section introduit l'égalité #P = P dans le paysage ; quant à la cinquième et dernière, elle examine le lien entre nos résultats et ceux de Guillaume Malod concernant la clôture par fonction-coefficient de diverses classes de complexité pour le calcul des polynômes à la manière de Valiant.Nous nous sommes efforcés de rédiger cet article de manière à ce qu'il puisse être lu par des personnes non spécialisées en algorithmie.
7
Coureau, Didier. "The Brain’s Cinematic Metaphors (Images of Thought, Thinking Forms)." IRIS, no. 36 (June 30, 2015): 85–101. http://dx.doi.org/10.35562/iris.1574.
Повний текст джерелаАнотація:
Cet article s’inscrit dans le prolongement d’une recherche que je mène depuis une vingtaine d’années sur les rapports entre cinéma et pensée. En m’appuyant en particulier sur les réflexions de Gilles Deleuze, Félix Guattari, Edgar Morin, j’ai ainsi pu créer les concepts de « complexité esthétique », « noosphère filmique », « cinématographie des flux ». Suite à l’évocation de créateurs-penseurs du cinéma muet d’avant-garde (Epstein, Dulac, Artaud), sont ici abordés des films d’Amos Gitaï, Chris Marker, Jean-Luc Godard, Alain Resnais et Andreï Tarkovski. L’intitulé, « Les métaphores filmiques du cerveau » indique que l’approche de la relation cinéma-cerveau est d’ordre philosophique, mais également d’ordre poétique. Si le cinéma est à même de donner forme à la pensée, il invente aussi des circuits cérébraux — sonores et visuels — qui lui permettent de devenir forme « pensante ».
8
Coureau, Didier. "The Brain’s Cinematic Metaphors (Images of Thought, Thinking Forms)." IRIS, no. 36 (June 30, 2015): 85–101. http://dx.doi.org/10.35562/iris.1574.
Повний текст джерелаАнотація:
Cet article s’inscrit dans le prolongement d’une recherche que je mène depuis une vingtaine d’années sur les rapports entre cinéma et pensée. En m’appuyant en particulier sur les réflexions de Gilles Deleuze, Félix Guattari, Edgar Morin, j’ai ainsi pu créer les concepts de « complexité esthétique », « noosphère filmique », « cinématographie des flux ». Suite à l’évocation de créateurs-penseurs du cinéma muet d’avant-garde (Epstein, Dulac, Artaud), sont ici abordés des films d’Amos Gitaï, Chris Marker, Jean-Luc Godard, Alain Resnais et Andreï Tarkovski. L’intitulé, « Les métaphores filmiques du cerveau » indique que l’approche de la relation cinéma-cerveau est d’ordre philosophique, mais également d’ordre poétique. Si le cinéma est à même de donner forme à la pensée, il invente aussi des circuits cérébraux — sonores et visuels — qui lui permettent de devenir forme « pensante ».
9
Hirata, Yuichi, Masaki Nakanishi, Shigeru Yamashita, and Yasuhiko Nakashima. "An efficient conversion of quantum circuits to a linear nearest neighbor architecture." Quantum Information and Computation 11, no. 1&2 (January 2011): 142–66. http://dx.doi.org/10.26421/qic11.1-2-10.
Повний текст джерелаАнотація:
Several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only. Therefore, several specific circuits have been designed on an LNN architecture. However, a general and efficient conversion method for an arbitrary circuit has not been established. Therefore, this paper gives an efficient conversion technique to convert quantum circuits to an LNN architecture. When a quantum circuit is converted to an LNN architecture, the objective is to reduce the size of the additional circuit added by the conversion and the time complexity of the conversion. The proposed method requires less additional circuitry and time complexity compared with naive techniques. To develop the method, we introduce two key theorems that may be interesting on their own. In addition, the proposed method also achieves less overhead than some known circuits designed from scratch on an LNN architecture.
10
Uchizawa, Kei, Rodney Douglas, and Wolfgang Maass. "On the Computational Power of Threshold Circuits with Sparse Activity." Neural Computation 18, no. 12 (December 2006): 2994–3008. http://dx.doi.org/10.1162/neco.2006.18.12.2994.
Повний текст джерелаАнотація:
Circuits composed of threshold gates (McCulloch-Pitts neurons, or perceptrons) are simplified models of neural circuits with the advantage that they are theoretically more tractable than their biological counterparts. However, when such threshold circuits are designed to perform a specific computational task, they usually differ in one important respect from computations in the brain: they require very high activity. On average every second threshold gate fires (sets a 1 as output) during a computation. By contrast, the activity of neurons in the brain is much sparser, with only about 1% of neurons firing. This mismatch between threshold and neuronal circuits is due to the particular complexity measures (circuit size and circuit depth) that have been minimized in previous threshold circuit constructions. In this letter, we investigate a new complexity measure for threshold circuits, energy complexity, whose minimization yields computations with sparse activity. We prove that all computations by threshold circuits of polynomial size with entropy O(log n) can be restructured so that their energy complexity is reduced to a level near the entropy of circuit states. This entropy of circuit states is a novel circuit complexity measure, which is of interest not only in the context of threshold circuits but for circuit complexity in general. As an example of how this measure can be applied, we show that any polynomial size threshold circuit with entropy O(log n) can be simulated by a polynomial size threshold circuit of depth 3. Our results demonstrate that the structure of circuits that result from a minimization of their energy complexity is quite different from the structure that results from a minimization of previously considered complexity measures, and potentially closer to the structure of neural circuits in the nervous system. In particular, different pathways are activated in these circuits for different classes of inputs. This letter shows that such circuits with sparse activity have a surprisingly large computational power.
Дисертації з теми "Complexité de circuits"
1
Revol, Nathalie. "Complexité de l'évaluation parallèle de circuits arithmétiques." Grenoble INPG, 1994. http://tel.archives-ouvertes.fr/tel-00005109.
Повний текст джерелаАнотація:
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.
Повний текст джерелаАнотація:
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.
Повний текст джерелаАнотація:
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.
Повний текст джерелаАнотація:
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.
Повний текст джерелаАнотація:
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.
Повний текст джерелаАнотація:
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.
Повний текст джерелаАнотація:
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.
Повний текст джерелаАнотація:
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.
Повний текст джерелаАнотація:
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.
Повний текст джерелаАнотація:
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.
Книги з теми "Complexité de circuits"
1
Jukna, Stasys. Tropical Circuit Complexity. Cham: Springer International Publishing, 2023. http://dx.doi.org/10.1007/978-3-031-42354-3.
Повний текст джерела
2
Vollmer, Heribert. Introduction to Circuit Complexity. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. http://dx.doi.org/10.1007/978-3-662-03927-4.
Повний текст джерела
3
Håstad, Johan. Computational limitations of small-depth circuits. Cambridge, Mass: MIT Press, 1987.
Знайти повний текст джерела
4
Vollmer, Heribert. Introduction to Circuit Complexity: A Uniform Approach. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999.
Знайти повний текст джерела
5
Straubing, Howard. Finite Automata, Formal Logic, and Circuit Complexity. Boston, MA: Birkhäuser Boston, 1994. http://dx.doi.org/10.1007/978-1-4612-0289-9.
Повний текст джерела
6
Straubing, Howard. Finite automata, formal logic, and circuit complexity. Boston: Birkhäuser, 1994.
Знайти повний текст джерела
7
Subramanian, Ashok. The computational complexity of the circuit value and network stability problems. Stanford, Calif: Dept. of Computer Science, Stanford University, 1990.
Знайти повний текст джерела
8
Sridharan, K., B. Srinivasu, and Vikramkumar Pudi. Low-Complexity Arithmetic Circuit Design in Carbon Nanotube Field Effect Transistor Technology. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-50699-5.
Повний текст джерела
9
IEEE, Conference on Computational Complexity (11th 1996 Philadelphia Penn ). Proceedings, Eleventh Annual IEEE Conference on Computational Complexity: May 24-27, 1996, Philadelphia, Pennsylvania. Los Alamitos, Calif: IEEE Computer Society Press, 1996.
Знайти повний текст джерела
10
Myasnikov, Alexei G. Non-commutative cryptography and complexity of group-theoretic problems. Providence, R.I: American Mathematical Society, 2011.
Знайти повний текст джерелаЧастини книг з теми "Complexité de circuits"
1
Straubing, Howard. "Circuit Complexity." In Finite Automata, Formal Logic, and Circuit Complexity, 127–53. Boston, MA: Birkhäuser Boston, 1994. http://dx.doi.org/10.1007/978-1-4612-0289-9_8.
Повний текст джерела
2
Chen, Yu-Fang, Philipp Rümmer, and Wei-Lun Tsai. "A Theory of Cartesian Arrays (with Applications in Quantum Circuit Verification)." In Automated Deduction – CADE 29, 170–89. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-38499-8_10.
Повний текст джерелаАнотація:
AbstractWe present a theory of Cartesian arrays, which are multi-dimensional arrays with support for the projection of arrays to sub-arrays, as well as for updating sub-arrays. The resulting logic is an extension of Combinatorial Array Logic (CAL) and is motivated by the analysis of quantum circuits: using projection, we can succinctly encode the semantics of quantum gates as quantifier-free formulas and verify the end-to-end correctness of quantum circuits. Since the logic is expressive enough to represent quantum circuits succinctly, it necessarily has a high complexity; as we show, it suffices to encode the k-color problem of a graph under a succinct circuit representation, an NEXPTIME-complete problem. We present an NEXPTIME decision procedure for the logic and report on preliminary experiments with the analysis of quantum circuits using this decision procedure.
3
Brzozowski, Janusz A., and Carl-Johan H. Seger. "Complexity of Race Analysis." In Asynchronous Circuits, 167–85. New York, NY: Springer New York, 1995. http://dx.doi.org/10.1007/978-1-4612-4210-9_9.
Повний текст джерела
4
Chen, Yanbin, and Yannick Stade. "Quantum Constant Propagation." In Static Analysis, 164–89. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-44245-2_9.
Повний текст джерелаАнотація:
AbstractA quantum circuit is often executed on the initial state where each qubit is in the zero state. Therefore, we propose to perform a symbolic execution of the circuit. Our approach simulates groups of entangled qubits exactly up to a given complexity. Here, the complexity corresponds to the number of basis states expressing the quantum state of one entanglement group. By doing that, the groups need neither be determined upfront nor be bound by the number of involved qubits. Still, we ensure that the simulation runs in polynomial time - opposed to exponential time as required for the simulation of the entire circuit. The information made available at gates is exploited to remove superfluous controls and gates. We implemented our approach in the tool quantum constant propagation (QCP) and evaluated it on the circuits in the benchmark suite MQTBench. By applying our tool, only the work that cannot be carried out efficiently on a classical computer is left for the quantum computer, hence exploiting the strengths of both worlds.
5
Paterson, Mike. "Boolean circuit complexity." In Algorithms and Computation, 187. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/3-540-56279-6_71.
Повний текст джерела
6
Pudlák, P. "AC0 circuit complexity." In Fundamentals of Computation Theory, 106–20. Berlin, Heidelberg: Springer Berlin Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-57163-9_7.
Повний текст джерела
7
Balcázar, José Luis, Josep Díaz, and Joaquim Gabarró. "Uniform Circuit Complexity." In Structural Complexity II, 97–118. Berlin, Heidelberg: Springer Berlin Heidelberg, 1990. http://dx.doi.org/10.1007/978-3-642-75357-2_5.
Повний текст джерела
8
Vourkas, Ioannis, and Georgios Ch Sirakoulis. "Memristor-Based Logic Circuits." In Emergence, Complexity and Computation, 61–100. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-22647-7_4.
Повний текст джерела
9
Raz, Ran. "Circuit and Communication Complexity." In Computational Complexity Theory, 159–55. Providence, Rhode Island: American Mathematical Society, 2004. http://dx.doi.org/10.1090/pcms/010/06.
Повний текст джерела
10
Roberts, Nic, and Andrew Adamatzky. "Mining Logical Circuits in Fungi." In Emergence, Complexity and Computation, 311–21. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-38336-6_21.
Повний текст джерелаТези доповідей конференцій з теми "Complexité de circuits"
1
Concas, Roberto, Riccardo Meucci, Alessio Montori, Alessio Perinelli, and Leonardo Ricci. "Electronic circuits for chaos and synchronization in laser physics." In 2024 IEEE Workshop on Complexity in Engineering (COMPENG), 1–5. IEEE, 2024. http://dx.doi.org/10.1109/compeng60905.2024.10741481.
Повний текст джерела
2
Valdmanis, J. A. "Progress in electrooptic sampling of highspeed devices and integrated circuits." In OSA Annual Meeting. Washington, D.C.: Optica Publishing Group, 1988. http://dx.doi.org/10.1364/oam.1988.tue2.
Повний текст джерелаАнотація:
The rapidly increasing speed and complexity of current and future electronic circuitry has in many cases exceeded the capabilities of conventional all-electronic testing techniques. The need for high-speed noninvasive testing of integrated circuits is on us. By turning to optically based techniques, we can exploit the availability of picosecond and subpicosecond laser pulses to make electrical measurements. This paper reviews the latest refinements and applications of the electrooptic sampling technique, which utilizes optical pulses directly as sampling gates in electrooptic materials. It is currently the fastest (<300-fs resolution, >1-THz bandwidth) measurement technique available for electronic circuits and does not require vacuum for operation. Electrooptic sampling can be applied to a wide variety of circuits and devices and, when configured as an optical probe, can noninvasively interrogate internal nodes of complex integrated circuits. We discuss many measurement applications ranging from the basic physics of subpicosecond electrical pulse generation and the high-speed properties of high T c superconductors to integrated circuit probing on GaAs, silicon, and ceramic substrates.
3
He, Qing, Duo Chen, and Dan Jiao. "A First-Principle Guided Circuit Simulator of Linear Complexity and its Linear Speedup for Die-Package Co-Design." In ASME 2011 Pacific Rim Technical Conference and Exhibition on Packaging and Integration of Electronic and Photonic Systems. ASMEDC, 2011. http://dx.doi.org/10.1115/ipack2011-52276.
Повний текст джерелаАнотація:
In this work, guided by electromagnetics-based first principles, we develop a circuit simulator that allows for the simulation of a circuit including both nonlinear devices and the linear network in linear complexity. Moreover, it permits an almost embarrassingly parallel implementation on a many-core computing platform, and hence achieving linear speedup. The proposed circuit simulator rigorously captures the coupling between nonlinear circuits and the linear network. In addition, it bypasses the step of extraction, producing an RLC (resistor-inductor-capacitor) representation of the linear network without any numerical computation. Application to die-package co-simulation as well as simulation of very large-scale on-chip circuits involving over 800,000 CMOS transistors and interconnects having hundreds of millions of unknowns has demonstrated the superior performance of the proposed first-principle-guided circuit simulator.
4
Brown, J. J., J. T. Gardner, and S. R. Forrest. "Optically powered monolithically integrated logic circuits." In Integrated Photonics Research. Washington, D.C.: Optica Publishing Group, 1991. http://dx.doi.org/10.1364/ipr.1991.tuc5.
Повний текст джерелаАнотація:
Optical powering of optoelectron integrated circuits (OEICs) significantly improves their performance in high density photonic systems as compared to conventional designs employing electrical powering of circuits.1 Here optical powering replaces the dc bias lines with integrated photovoltaic (PV) cells in each pixel. The PV cell is illuminated with an external light source (e.g. laser) and converts this optical power beam into electrical power which subsequently drives the circuitry within that pixel. The total absence of the parasitic capacitances and inductances in the optical beam reduces inter-pixel cross-talk as compared with conventional dc bias lines. This leads to significantly increased bandwidths in the optically powered case. In addition, optical powering reduces interconnection complexity associated with routing bias lines to each pixel in a high-density, two dimensional array. An optically powered interconnection system has already been demonstrated in hybrid form.2,3 In this present work, we discuss an integrated optoelectronic logic circuit in which the power and control are both provided using optical sources.
5
Gaber, Lamya, Aziza I. Hussein, and Mohammed Moness. "Incremental Automatic Correction for Digital VLSI Circuits." In 10th International Conference on Advances in Computing and Information Technology (ACITY 2020). AIRCC Publishing Corporation, 2020. http://dx.doi.org/10.5121/csit.2020.101508.
Повний текст джерелаАнотація:
The impact of the recent exponential increase in complexity of digital VLSI circuits has heavily affected verification methodologies. Many advances toward verification and debugging techniques of digital VLSI circuits have relied on Computer Aided Design (CAD). Existing techniques are highly dependent on specialized test patterns with specific numbers increased by the rising complexity of VLSI circuits. A second problem arises in the form of large sizes of injecting circuits for correction and large number of SAT solver calls with a negative impact on the resultant running time. Three goals arise: first, diminishing dependence on a given test pattern by incrementally generating compact test patterns corresponding to design errors during the rectification process. Second, to reduce the size of in-circuit mutation circuit for error-fixing process. Finally, distribution of test patterns can be performed in parallel with a positive impact on digital VLSI circuits with large numbers of inputs and outputs. The experimental results illustrate that the proposed incremental correction algorithm can fix design bugs of type gate replacements in several digital VLSI circuits from ISCAS'85 with high speed and full accuracy. The speed of proposed Auto-correction mechanism outperforms the latest existing methods around 4.8x using ISCAS'85 benchmarks. The parallel distribution of test patterns on digital VLSI circuits during generating new compact test patterns achieves speed around 1.2x compared to latest methods.
6
Williams, Ryan. "Algorithms for Circuits and Circuits for Algorithms." In 2014 IEEE Conference on Computational Complexity (CCC). IEEE, 2014. http://dx.doi.org/10.1109/ccc.2014.33.
Повний текст джерела
7
Daems, Walter, Georges Gielen, and Willy Sansen. "Circuit complexity reduction for symbolic analysis of analog integrated circuits." In the 36th ACM/IEEE conference. New York, New York, USA: ACM Press, 1999. http://dx.doi.org/10.1145/309847.310106.
Повний текст джерела
8
Seo, Kuhn, Brent Wahl, Myrna Mayonte, and Young Gon Kim. "Methodologies for Isolating Faults in Multi Chip Fiber Optic Transceivers That Use GHz Mixed Signal ICs." In ISTFA 2002. ASM International, 2002. http://dx.doi.org/10.31399/asm.cp.istfa2002p0251.
Повний текст джерелаАнотація:
Abstract This paper outlines a methodology which accurately identifies fault locations in Mixed Signal Integrated Circuits (ICs). The architecture of Mixed Signal ICs demands more attention during failure analysis because of the complexity of measuring both the analog and digital signals in a compact circuit. In this paper, the GHz range of data signal or radio frequency (RF) signal from an internal IC circuit will be extracted by a high-impedance active single probe in order to find the internal IC circuit failure locations. The advantages of using a single probe is that it can maneuver to extract data almost anywhere in the circuit, providing ranges of bandwidth in GHz with no loading effect on the circuits during measurement. The process of preparing a sample and extracting a signal will be described.
9
Kombarov, Yury Anatolievich. "Improvement of circuit complexity lower bound for parity function in one infinite basis." In Academician O.B. Lupanov 14th International Scientific Seminar "Discrete Mathematics and Its Applications". Keldysh Institute of Applied Mathematics, 2022. http://dx.doi.org/10.20948/dms-2022-14.
Повний текст джерелаАнотація:
We consider circuits of functional elements in a basis of generalized conjunctors (that is, conjunctors with an arbitrary number of inputs, any input of which can be inverted). It is proved that any circuit that implements a linear Boolean function of n variables consists of at least 2.125n + С elements.
10
Lall, Pradeep, Jinesh Narangaparambil, and Scott Miller. "Development of Multi-Layer Circuitry Using Electrically Conductive Adhesive and Low-Temperature Solder Material for Surface-Mount Component Attachment." In ASME 2021 International Technical Conference and Exhibition on Packaging and Integration of Electronic and Photonic Microsystems. American Society of Mechanical Engineers, 2021. http://dx.doi.org/10.1115/ipack2021-74086.
Повний текст джерелаАнотація:
Abstract The increased versatility in the design and manufacturing of components in low volumes, as well as the shorter time between design and prototype, has increased interest in the field of additively printed electronics. The ability to directly print on a variety of substrates, whether rigid, flexible, or conformable, provides several benefits over conventional electronics fabrication methods. Furthermore, the growing complexity of flexible electronics necessitates the development of multilayered circuits similar to traditional PCBs to decrease the volumetric and gravimetric effect of the underlying electronics. Using z-axis interconnections with dielectric materials, which may allow or prevent the connection between two layers, is one method of reaching several layers of circuits. In this paper, a working multilayer circuitry test vehicle is designed and additively printed using the direct-write method. The circuit model involves conductive and dielectric ink printing, as well as passive and active component attachments using an electrically conductive adhesive (ECA) and low-temperature solder (LTS). The study also shows details about the process of developing dielectric printing parameters for microvias for multilayer z-axis interconnections.
Звіти організацій з теми "Complexité de circuits"
1
Schueller, Kriss A., and Jon T. Butler. Complexity Analysis of the Cost-Table Approach to the Design of Multiple-Valued Logic Circuits. Fort Belvoir, VA: Defense Technical Information Center, October 1995. http://dx.doi.org/10.21236/ada605390.
Повний текст джерела
2
Cao, Zhengjun, Lihua Liu, and Andreas Christoforides. A Note on One Realization of a Scalable Shor Algorithm. Web of Open Science, December 2020. http://dx.doi.org/10.37686/qrl.v1i2.81.
Повний текст джерелаАнотація:
Very recently, Monz, et al. have reported the demonstration of factoring 15 using a scalable Shor algorithm with an ion-trap quantum computer. In this note, we remark that the report is somewhat misleading because there are three flaws in the proposed circuit diagram of Shor algorithm. We also remark that the principles behind the demonstration have not been explained properly, including its correctness and complexity.