Tesi: "Graphe de code"

1

Bertrand, Sébastien. "Modèle de maintenabilité logicielle par analyse statique du graphe de code du programme". Electronic Thesis or Diss., Bordeaux, 2024. http://www.theses.fr/2024BORD0414.

Testo completo

Abstract (sommario):

Le coût élevé de la maintenance des logiciels exige de travailler sur leur maintenabilité. Bien qu’émergente de la structure du code source, son évaluation est subjective, car elle dépend des développeurs et du contexte. Les modèles de maintenabilité actuels tendent à réduire la maintenabilité à un score unidimensionnel basé sur des métriques, souvent mal définies, qui représentent mal la structure du code. Nos travaux se sont basés sur l’analyse statique des graphes de code pour évaluer la maintenabilité. Ils ont permis de développer Javanalyser, un outil libre qui génère automatiquement le graphe de code d’un programme Java. Ces graphes ont permis de formaliser 33 métriques statiques sous forme de requêtes déclarative et ont permis de reproduire avec succès une étude de Schnappinger et al. Notre extension de l’étude confirme l’importance de la taille du programme comme facteur influençant la maintenabilité, sans toutefois négliger l’impact des autres métriques. Ce travail ouvre la voie à une compréhension plus approfondie de la maintenabilité, grâce à une représentation multidimensionnelle permettant de tenir compte de la variabilité entre les développeurs
The high cost of software maintenance requires a focus on software maintainability. Although it emerges from the structure of the source code, its evaluation is subjective, as it depends on developers and the context. Current maintainability models tend to reduce maintainability to a one-dimensional score based on metrics, often poorly defined, which inadequately represent the structure of the code. Our work is based on the static analysis of code graphs to evaluate maintainability. It led to the development of Javanalyser, an open-source tool that automatically generates the code graph of a Java program. These graphs enabled the formalization of 33 static metrics as declarative queries, and allowed the successful replication of a study by Schnappinger et al. Our extension of the study confirmed the importance of size as a factor influencing maintainability, while also recognizing the impact of other metrics. This work opens the way to a deeper understanding of maintainability through a multidimensional representation that takes into account the variability between developers

Gli stili APA, Harvard, Vancouver, ISO e altri

2

Roux, Antoine. "Etude d’un code correcteur linéaire pour le canal à effacements de paquets et optimisation par comptage de forêts et calcul modulaire". Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS337.

Testo completo

Abstract (sommario):

La transmission fiable de données sur un canal de transmission est un problème récurrent en Informatique. En effet, quel que soit le canal de transmission employé, on observe obligatoirement de la détérioration de l’information transmise, voire sa perte pure et simple. Afin de palier à ce problème, plusieurs solutions ont été apportées, notamment via l’emploi de codes correcteurs. Dans cette thèse, nous étudions un code correcteur développé en 2014 et 2015 pour l’entreprise Thales durant ma deuxième année de Master en apprentissage. Il s’agit d’un code actuellement utilisé par Thales pour fiabiliser une transmission UDP passant par un dispositif réseau, l’Elips-SD. L’Elips-SD est une diode réseau qu’on place sur une fibre optique et qui garantit physiquement que la transmission est unidirectionnelle. Le cas d’utilisation principal de cette diode est de permettre le suivi de la production d’un site sensible, ou encore de superviser son fonctionnement, tout en garantissant à ce site une protection face aux intrusions extérieures. A l’opposé, un autre cas d’utilisation est la transmission de données depuis un ou plusieurs sites non-sécurisés vers un site sécurisé, dont on souhaite s’assurer qu’aucune information ne pourra par la suite fuiter. Le code correcteur que nous étudions est un code correcteur linéaire pour le canal à effacements de paquets, qui a reçu la certification OTAN de la Direction Générale des Armées. Nous l’avons babtisé "Fauxtraut", anagramme de "Fast algorithm using Xor to repair altered unidirectionnal transmissions". Afin d’étudier ce code correcteur, de présenter son fonctionnement et ses performances, et les différentes modifications apportées durant cette thèse, nous établissons tout d’abord un état de l’art des codes correcteurs, en nous concentrant principalement sur les codes linéaires non-MDS, tels que les codes LDPC. Puis nous présentons le fonctionnement de Fauxtraut, et analysons son comportement (complexité, consommation mémoire, performances) par la théorie et par des simulations. Enfin, nous présenterons différentes versions de ce code correcteur développées durant cette thèse, qui aboutissent à d’autres cas d’utilisation, tels que la transmission d’information sur un canal unidirectionnel à erreurs ou sur un canal bidirectionnel, à l’image de ce que permet de faire le protocole H-ARQ. Dans cette partie, nous étudierons notamment le comportement de notre code correcteur via la théorie des graphes : calculer la probabilité de décoder convenablement ou non revient à connaître la probabilité d’apparition de cycles dans le sous-graphe de graphes particuliers, les graphes de Rook et les graphes bipartis complets. Le problème s’énonce simplement et s’avère compliqué, et nous espérons qu’il saura intéresser des chercheurs du domaine. Nous présentons une méthode permettant de calculer exactement cette probabilité pour de petits graphes (qui aboutit à un certain nombre de formules closes), et une fonction tendant asymptotiquement vers cette probabilité pour de plus grands graphes. Nous étudierons aussi la manière de paramétrer automatiquement notre code correcteur par le calcul modulaire et la combinatoire, utilisant la fonction de Landau, qui retourne un ensemble de nombres entiers dont la somme est fixée et le plus commun multiple est maximal. Dans une dernière partie, nous présentons un travail effectué durant cette thèse ayant conduit à une publication dans la revue Theoretical Computer Science. Il concerne un problème non-polynomial de la théorie des graphes : le couplage maximal dans les graphes temporels. Cet article propose notamment deux algorithmes de complexité polynomiale : un algorithme de 2-approximation et un algorithme de kernelisation pour ce problème. L’algorithme de 2- approximation peut notamment être utilisé de manière incrémentale : arêtes du flot de liens nous parviennent les unes après les autres, et on construit la 2-approximation au fur et à mesure de leur arrivée
Reliably transmitting information over a transmission channel is a recurrent problem in Informatic Sciences. Whatever may be the channel used to transmit information, we automatically observe erasure of this information, or pure loss. Different solutions can be used to solve this problem, using forward error correction codes is one of them. In this thesis, we study a corrector code developped in 2014 and 2015 for Thales society during my second year of master of apprenticeship. It is currently used to ensure the reliability of a transmission based on the UDP protocole, and passing by a network diode, Elips-SD. Elip-SD is an optical diode that can be plugged on an optical fiber to physically ensure that the transmission is unidirectional. The main usecase of such a diode is to enable supervising a critical site, while ensuring that no information can be transmitted to this site. At the opposite, another usecase is the transmission from one or multiple unsecured emitters to one secured receiver who wants to ensure that no information can be robbed. The corrector code that we present is a linear corrector code for the binary erasure channel using packets, that obtained the NATO certification from the DGA ("Direction Générale de Armées" in French). We named it Fauxtraut, for "Fast algorithm using Xor to repair altered unidirectional transmissions". In order to study this code, presenting how it works, its performance and the modifications we added during this thesis, we first establish a state of the art of forward error correction, focusing on non-MDS linear codes such as LDPC codes. Then we present Fauxtraut behavior, and analyse it theorically and with simulations. Finally, we present different versions of this code that were developped during this thesis, leading to other usecases such as transmitting reliable information that can be altered instead of being erased, or on a bidirectionnal channel, such as the H-ARQ protocole, and different results on the number of cycles in particular graphs. In the last part, we present results that we obtained during this thesis and that finally lead to an article in the Technical Computer Science. It concerns a non-polynomial problema of Graphs theorie : maximum matching in temporal graphs. In this article, we propose two algorithms with polynomial complexity : a 2-approximation algorithm and a kernelisation algorithm forthis problema

Gli stili APA, Harvard, Vancouver, ISO e altri

3

Richa, Elie. "Qualification des générateurs de code source dans le domaine de l'avionique : le test automatisé des chaines de transformation de modèles". Thesis, Paris, ENST, 2015. http://www.theses.fr/2015ENST0082/document.

Testo completo

Abstract (sommario):

Dans l’industrie de l’avionique, les Générateurs Automatiques de Code (GAC) sont de plus en plus utilisés pour produire des parties du logiciel embarqué. Puisque le code généré fait partie d’un logiciel critique, les standards de sûreté exigent une vérification approfondie du GAC: la qualification. Dans cette thèse en collaboration avec AdaCore, nous cherchons à réduire le coût des activités de test par des méthodes automatiques et efficaces.La première partie de la thèse aborde le sujet du test unitaire qui assure une exhaustivité élevée mais qui est difficile à réaliser pour les GACs. Nous proposons alors une méthode qui garantit le même niveau d’exhaustivité en n’utilisant que des tests d’intégration de mise en œuvre plus facile. Nous proposons tout d’abord une formalisation du langage ATL de définition du GAC dans la théorie des Transformations Algébriques de Graphes. Nous définissons ensuite une traduction de postconditions exprimant l’exhaustivité du test unitaire en des préconditions équivalentes qui permettent à terme de produire des tests d’intégration assurant le même niveau d’exhaustivité. Enfin, nous proposons d’optimiser l’algorithme complexe de notre analyse à l’aide de stratégies de simplification dont nous mesurons expérimentalement l’efficacité.La seconde partie du travail concerne les oracles de tests du GAC, c’est à dire le moyen de valider le code généré par le GAC lors d’un test. Nous proposons un langage de spécification de contraintes textuelles capables d’attester automatiquement de la validité du code généré. Cette approche est déployée expérimentalement à AdaCore pour le projet QGen, un générateur de code Ada/C à partir de Simulink®
In the avionics industry, Automatic Code Generators (ACG) are increasingly used to produce parts of the embedded software. Since the generated code is part of critical software, safety standards require a thorough verification of the ACG called qualification. In this thesis in collaboration with AdaCore, we seek to reduce the cost of testing activities by automatic and effective methods.The first part of the thesis addresses the topic of unit testing which ensures exhaustiveness but is difficult to achieve for ACGs. We propose a method that guarantees the same level of exhaustiveness by using only integration tests which are easier to carry out. First, we propose a formalization of the ATL language in which the ACG is defined in the Algebraic Graph Transformation theory. We then define a translation of postconditions expressing the exhaustiveness of unit testing into equivalent preconditions that ultimately support the production of integration tests providing the same level of exhaustiveness. Finally, we propose to optimize the complex algorithm of our analysis using simplification strategies that we assess experimentally.The second part of the work addresses the oracles of ACG tests, i.e. the means of validating the code generated by the ACG during a test. We propose a language for the specification of textual constraints able to automatically check the validity of the generated code. This approach is experimentally deployed at AdaCore for a Simulink® to Ada/C ACG called QGen

Gli stili APA, Harvard, Vancouver, ISO e altri

4

Richa, Elie. "Qualification des générateurs de code source dans le domaine de l'avionique : le test automatisé des chaines de transformation de modèles". Electronic Thesis or Diss., Paris, ENST, 2015. http://www.theses.fr/2015ENST0082.

Testo completo

Abstract (sommario):

Dans l’industrie de l’avionique, les Générateurs Automatiques de Code (GAC) sont de plus en plus utilisés pour produire des parties du logiciel embarqué. Puisque le code généré fait partie d’un logiciel critique, les standards de sûreté exigent une vérification approfondie du GAC: la qualification. Dans cette thèse en collaboration avec AdaCore, nous cherchons à réduire le coût des activités de test par des méthodes automatiques et efficaces.La première partie de la thèse aborde le sujet du test unitaire qui assure une exhaustivité élevée mais qui est difficile à réaliser pour les GACs. Nous proposons alors une méthode qui garantit le même niveau d’exhaustivité en n’utilisant que des tests d’intégration de mise en œuvre plus facile. Nous proposons tout d’abord une formalisation du langage ATL de définition du GAC dans la théorie des Transformations Algébriques de Graphes. Nous définissons ensuite une traduction de postconditions exprimant l’exhaustivité du test unitaire en des préconditions équivalentes qui permettent à terme de produire des tests d’intégration assurant le même niveau d’exhaustivité. Enfin, nous proposons d’optimiser l’algorithme complexe de notre analyse à l’aide de stratégies de simplification dont nous mesurons expérimentalement l’efficacité.La seconde partie du travail concerne les oracles de tests du GAC, c’est à dire le moyen de valider le code généré par le GAC lors d’un test. Nous proposons un langage de spécification de contraintes textuelles capables d’attester automatiquement de la validité du code généré. Cette approche est déployée expérimentalement à AdaCore pour le projet QGen, un générateur de code Ada/C à partir de Simulink®
In the avionics industry, Automatic Code Generators (ACG) are increasingly used to produce parts of the embedded software. Since the generated code is part of critical software, safety standards require a thorough verification of the ACG called qualification. In this thesis in collaboration with AdaCore, we seek to reduce the cost of testing activities by automatic and effective methods.The first part of the thesis addresses the topic of unit testing which ensures exhaustiveness but is difficult to achieve for ACGs. We propose a method that guarantees the same level of exhaustiveness by using only integration tests which are easier to carry out. First, we propose a formalization of the ATL language in which the ACG is defined in the Algebraic Graph Transformation theory. We then define a translation of postconditions expressing the exhaustiveness of unit testing into equivalent preconditions that ultimately support the production of integration tests providing the same level of exhaustiveness. Finally, we propose to optimize the complex algorithm of our analysis using simplification strategies that we assess experimentally.The second part of the work addresses the oracles of ACG tests, i.e. the means of validating the code generated by the ACG during a test. We propose a language for the specification of textual constraints able to automatically check the validity of the generated code. This approach is experimentally deployed at AdaCore for a Simulink® to Ada/C ACG called QGen

Gli stili APA, Harvard, Vancouver, ISO e altri

5

Robillard, Benoît. "Verification formelle et optimisation de l’allocation de registres". Electronic Thesis or Diss., Paris, CNAM, 2010. http://www.theses.fr/2010CNAM0730.

Testo completo

Abstract (sommario):

La prise de conscience générale de l'importance de vérifier plus scrupuleusement les programmes a engendré une croissance considérable des efforts de vérification formelle de programme durant cette dernière décennie. Néanmoins, le code qu'exécute l'ordinateur, ou code exécutable, n'est pas le code écrit par le développeur, ou code source. La vérification formelle de compilateurs est donc un complément indispensable à la vérification de code source.L'une des tâches les plus complexes de compilation est l'allocation de registres. C'est lors de celle-ci que le compilateur décide de la façon dont les variables du programme sont stockées en mémoire durant son exécution. La mémoire comporte deux types de conteneurs : les registres, zones d'accès rapide, présents en nombre limité, et la pile, de capacité supposée suffisamment importante pour héberger toutes les variables d'un programme, mais à laquelle l'accès est bien plus lent. Le but de l'allocation de registres est de tirer au mieux parti de la rapidité des registres, car une allocation de registres de bonne qualité peut conduire à une amélioration significative du temps d'exécution du programme.Le modèle le plus connu de l'allocation de registres repose sur la coloration de graphe d'interférence-affinité. Dans cette thèse, l'objectif est double : d'une part vérifier formellement des algorithmes connus d'allocation de registres par coloration de graphe, et d'autre part définir de nouveaux algorithmes optimisants pour cette étape de compilation. Nous montrons tout d'abord que l'assistant à la preuve Coq est adéquat à la formalisation d'algorithmes d'allocation de registres par coloration de graphes. Nous procédons ainsi à la vérification formelle en Coq d'un des algorithmes les plus classiques d'allocation de registres par coloration de graphes, l'Iterated Register Coalescing (IRC), et d'une généralisation de celui-ci permettant à un utilisateur peu familier du système Coq d'implanter facilement sa propre variante de cet algorithme au seul prix d'une éventuelle perte d'efficacité algorithmique. Ces formalisations nécessitent des réflexions autour de la formalisation des graphes d'interférence-affinité, de la traduction sous forme purement fonctionnelle d'algorithmes impératifs et de l'efficacité algorithmique, la terminaison et la correction de cette version fonctionnelle. Notre implantation formellement vérifiée de l'IRC a été intégrée à un prototype du compilateur CompCert.Nous avons ensuite étudié deux représentations intermédiaires de programmes, dont la forme SSA, et exploité leurs propriétés pour proposer de nouvelles approches de résolution optimale de la fusion, l'une des optimisations opéréeslors de l'allocation de registres dont l'impact est le plus fort sur la qualité du code compilé. Ces approches montrent que des critères de fusion tenant compte de paramètres globaux du graphe d'interférence-affinité, tels que sa largeur d'arbre, ouvrent la voie vers de nouvelles méthodes de résolution potentiellement plus performantes
The need for trustful programs led to an increasing use of formal verication techniques the last decade, and especially of program proof. However, the code running on the computer is not the source code, i.e. the one written by the developper, since it has to betranslated by the compiler. As a result, the formal verication of compilers is required to complete the source code verication. One of the hardest phases of compilation is register allocation. Register allocation is the phase within which the compiler decides where the variables of the program are stored in the memory during its execution. The are two kinds of memory locations : a limited number of fast-access zones, called registers, and a very large but slow-access stack. The aim of register allocation is then to make a great use of registers, leading to a faster runnable code.The most used model for register allocation is the interference graph coloring one. In this thesis, our objective is twofold : first, formally verifying some well-known interference graph coloring algorithms for register allocation and, second, designing new graph-coloring register allocation algorithms. More precisely, we provide a fully formally veri ed implementation of the Iterated Register Coalescing, a very classical graph-coloring register allocation heuristics, that has been integrated into the CompCert compiler. We also studied two intermediate representations of programs used in compilers, and in particular the SSA form to design new algorithms, using global properties of the graph rather than local criteria currently used in the litterature

Gli stili APA, Harvard, Vancouver, ISO e altri

6

Robillard, Benoît. "Verification formelle et optimisation de l’allocation de registres". Thesis, Paris, CNAM, 2010. http://www.theses.fr/2010CNAM0730/document.

Testo completo

Abstract (sommario):

La prise de conscience générale de l'importance de vérifier plus scrupuleusement les programmes a engendré une croissance considérable des efforts de vérification formelle de programme durant cette dernière décennie. Néanmoins, le code qu'exécute l'ordinateur, ou code exécutable, n'est pas le code écrit par le développeur, ou code source. La vérification formelle de compilateurs est donc un complément indispensable à la vérification de code source.L'une des tâches les plus complexes de compilation est l'allocation de registres. C'est lors de celle-ci que le compilateur décide de la façon dont les variables du programme sont stockées en mémoire durant son exécution. La mémoire comporte deux types de conteneurs : les registres, zones d'accès rapide, présents en nombre limité, et la pile, de capacité supposée suffisamment importante pour héberger toutes les variables d'un programme, mais à laquelle l'accès est bien plus lent. Le but de l'allocation de registres est de tirer au mieux parti de la rapidité des registres, car une allocation de registres de bonne qualité peut conduire à une amélioration significative du temps d'exécution du programme.Le modèle le plus connu de l'allocation de registres repose sur la coloration de graphe d'interférence-affinité. Dans cette thèse, l'objectif est double : d'une part vérifier formellement des algorithmes connus d'allocation de registres par coloration de graphe, et d'autre part définir de nouveaux algorithmes optimisants pour cette étape de compilation. Nous montrons tout d'abord que l'assistant à la preuve Coq est adéquat à la formalisation d'algorithmes d'allocation de registres par coloration de graphes. Nous procédons ainsi à la vérification formelle en Coq d'un des algorithmes les plus classiques d'allocation de registres par coloration de graphes, l'Iterated Register Coalescing (IRC), et d'une généralisation de celui-ci permettant à un utilisateur peu familier du système Coq d'implanter facilement sa propre variante de cet algorithme au seul prix d'une éventuelle perte d'efficacité algorithmique. Ces formalisations nécessitent des réflexions autour de la formalisation des graphes d'interférence-affinité, de la traduction sous forme purement fonctionnelle d'algorithmes impératifs et de l'efficacité algorithmique, la terminaison et la correction de cette version fonctionnelle. Notre implantation formellement vérifiée de l'IRC a été intégrée à un prototype du compilateur CompCert.Nous avons ensuite étudié deux représentations intermédiaires de programmes, dont la forme SSA, et exploité leurs propriétés pour proposer de nouvelles approches de résolution optimale de la fusion, l'une des optimisations opéréeslors de l'allocation de registres dont l'impact est le plus fort sur la qualité du code compilé. Ces approches montrent que des critères de fusion tenant compte de paramètres globaux du graphe d'interférence-affinité, tels que sa largeur d'arbre, ouvrent la voie vers de nouvelles méthodes de résolution potentiellement plus performantes
The need for trustful programs led to an increasing use of formal verication techniques the last decade, and especially of program proof. However, the code running on the computer is not the source code, i.e. the one written by the developper, since it has to betranslated by the compiler. As a result, the formal verication of compilers is required to complete the source code verication. One of the hardest phases of compilation is register allocation. Register allocation is the phase within which the compiler decides where the variables of the program are stored in the memory during its execution. The are two kinds of memory locations : a limited number of fast-access zones, called registers, and a very large but slow-access stack. The aim of register allocation is then to make a great use of registers, leading to a faster runnable code.The most used model for register allocation is the interference graph coloring one. In this thesis, our objective is twofold : first, formally verifying some well-known interference graph coloring algorithms for register allocation and, second, designing new graph-coloring register allocation algorithms. More precisely, we provide a fully formally veri ed implementation of the Iterated Register Coalescing, a very classical graph-coloring register allocation heuristics, that has been integrated into the CompCert compiler. We also studied two intermediate representations of programs used in compilers, and in particular the SSA form to design new algorithms, using global properties of the graph rather than local criteria currently used in the litterature

Gli stili APA, Harvard, Vancouver, ISO e altri

7

Stange, Yuri. "Visualization of Code Flow". Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-162108.

Testo completo

Abstract (sommario):

Visual representation of Control Flow Graphs (CFG) is a feature available in many tools, such as decompilers. These tools often rely on graph drawing frameworks which implement the Sugiyama hierarchical style graph drawing method, a well known method for drawing directed graphs. The main disadvantage of the Sugiyama framework, is the fact that it does not take into account the nature of the graph to be visualized, specically loops are treated as second class citizens. The question this paper attempts to answer is; how can we improve the visual representation of loops in the graph? A method based on the Sugiyama framework was developed and implemented in Qt. It was evaluated by informally interviewing test subjects, who were allowed to test the implementation and compare it to the normal Sugiyama. The results show that all test subjects concluded that loops, as well as the overall representation of the graph was improved, although with reservations. The method presented in this paper has problems which need to be adressed, before it can be seen as an optimal solution for drawing Control Flow Graphs.
Visuell representation av flödesscheman (eng. Control Flow Graph, CFG) är en funktion tillgänglig hos många verktyg, bland annat dekompilerare. Dessa verktyg använder sig ofta av grafritande ramverk som implementerar Sugiyamas metod för uppritning av hierarkiska grafer, vilken är en känd metod för uppritning av riktade grafer. Sugiyamas stora nackdelär att metoden inte tar hänsyn till grafens natur, loopar i synnerhet behandlas som andra klassens medborgare. Frågeställningen hos denna rapport är; Hur kan vi förbättra den visuella representationen av loopar i en graf? En metod som bygger vidare på Sugiyama-ramverket utvecklades och implementerades i Qt. Metoden testades genom att hålla informella kvalitativa intervjuer med testpersoner, vilka fick testa implementeringen och jämföra den med den vanliga Sugiyama-metoden. Resultaten visar att alla testpersonerna stämmer in på att loopar, så väl som den overskådliga representionen av grafen förbättrades, dock med vissa reservationer. Metoden som presenteras i denna rapport har vissa problem, vilka bör adresseras innan den kan ses som en optimal lösning för uppritning av flödesscheman.

Gli stili APA, Harvard, Vancouver, ISO e altri

8

Li, Chao. "Semidefinite programming, binary codes and a graph coloring problem". Digital WPI, 2015. https://digitalcommons.wpi.edu/etd-theses/863.

Testo completo

Abstract (sommario):

"Experts in information theory have long been interested in the maximal size, A(n, d), of a binary error-correcting code of length n and minimum distance d, The problem of determining A(n, d) involves both the construction of good codes and the search for good upper bounds. For quite some time now, Delsarte's linear programming approach has been the dominant approach to obtaining the strongest general purpose upper bounds on the efficiency of error-correcting codes. From 1973 forward, the linear programming bound found many applications, but there were few significant theoretical advances until Schrijver proposed a new code upper bound via semidefinite programming in 2003. Using the Terwilliger algebra, a recently introduced extension of the Bose-Mesner algebra, Schrijver formulated a new SDP strengthening of the LP approach. In this project we look at the dual solutions of the semidefinite programming bound for binary error-correcting codes. We explore the combinatorial meaning of these variables for small n and d, such as n = 4 and d = 2. To obtain information like this, we wrote a computer program with both Matlab and CVX modules to get solution of our primal SDP formulation. Our program efficiently generates the primal solutions with corresponding constraints for any n and d. We also wrote a program in C++ to parse the output of the primal SDP problem, and another Matlab script to generate the dual SDP problem, which could be used in assigning combinatorial meaning to the values given in the dual optimal solution. Our code not only computes both the primal and dual optimal variable values, but allows the researcher to display them in meaningful ways and to explore their relationship and dependence on arameters. These values are expected to be useful for later study of the combinatorial meaning of such solutions."

Gli stili APA, Harvard, Vancouver, ISO e altri

9

Saeed, Mohamed Ahmed. "Approche algébrique sur l'équivalence de codes". Thesis, Normandie, 2017. http://www.theses.fr/2017NORMR034/document.

Testo completo

Abstract (sommario):

Le problème d’´équivalence de code joue un rôle important dans la théorie de code et la cryptographie basée sur le code. Cela est dû à son importance dans la classification des codes ainsi que dans la construction et la cryptanalyse des cryptosystèmes à base de codes. Il est également lié à un problème ouvert d’isomorphisme de graphes, un problème bien connu dans le domaine de la théorie de la complexité. Nous prouvons pour les codes ayant un hull trivial qu’il existe une réduction polynomiale de l’équivalence par permutation de codes à l’isomorphisme de graphes. Cela montre que cette sous-classe d’équivalence de permutation n’est pas plus dure que l’isomorphisme de graphes. Nous introduisons une nouvelle méthode pour résoudre le problème d’équivalence de code. Nous développons des approches algébriques pour résoudre le problème dans ses deux versions : en permutation et en diagonale. Nous construisons un système algébrique en établissant des relations entre les matrices génératrices et les matrices de parité des codes équivalents. Nous nous retrouvons avecun système plusieurs variables d’équations linéaires et quadratiques qui peut être résolu en utilisant des outils algébriques tels que les bases de Groebner et les techniques associées. Il est possible en théorie de résoudre l’équivalence de code avec des techniques utilisant des bases de Groebner. Cependant, le calcul en pratique devient complexe à mesure que la longueur du code augmente. Nous avons introduit plusieurs améliorations telles que la linéarisation par bloc et l’action de Frobenius. En utilisant ces techniques, nous identifions de nombreux cas où le problème d’équivalence de permutation peut être résolu efficacement. Notre méthode d’équivalence diagonale résout efficacement le problème dans les corps de petites tailles, à savoir F3 et F4. L’augmentation de la taille du corps entraîne une augmentation du nombre de variables dans notre système algébrique, ce qui le rend difficile à résoudre. Nous nous intéressons enfin au problème d’isomorphisme de graphes en considérant un système algébrique quadratique pour l’isomorphisme de graphes. Pour des instances tirées aléatoirement, le système possède des propriétés intéressantes en termes de rang de la partie linéaire et du nombre de variables. Nousrésolvons efficacement le problème d’isomorphisme de graphes pour des graphes aléatoires avec un grand nombre de sommets, et également pour certains graphes réguliers tels que ceux de Petersen, Cubical et Wagner.123
Code equivalence problem plays an important role in coding theory and code based cryptography.That is due to its significance in classification of codes and also construction and cryptanalysis of code based cryptosystems. It is also related to the long standing problem of graph isomorphism, a well-known problem in the world of complexity theory. We introduce new method for solving code equivalence problem. We develop algebraic approaches to solve the problem in its permutation and diagonal versions. We build algebraic system by establishing relations between generator matrices and parity check matrices of the equivalent codes. We end up with system of multivariables of linear and quadratic equations which can be solved using algebraic tools such as Groebner basis and related techniques. By using Groebner basis techniques we can solve the code equivalence but the computation becomes complex as the length of the code increases. We introduced several improvements such as block linearization and Frobenius action. Using these techniques we identify many cases where permutation equivalence problem can be solved efficiently. Our method for diagonal equivalence solves the problem efficiently in small fields, namely F3 and F4. The increase in the field size results in an increase in the number of variables in our algebraic system which makes it difficult to solve. We introduce a new reduction from permutation code equivalence when the hull is trivial to graph isomorphism. This shows that this subclass of permutation equivalence is not harder than graph isomorphism.Using this reduction we obtain an algebraic system for graph isomorphism with interesting properties in terms of the rank of the linear part and the number of variables. We solve the graph isomorphism problem efficiently for random graphs with large number of vertices and also for some regular graphs such as Petersen, Cubical and Wagner Graphs

Gli stili APA, Harvard, Vancouver, ISO e altri

10

Lestringant, Pierre. "Identification d'algorithmes cryptographiques dans du code natif". Thesis, Rennes 1, 2017. http://www.theses.fr/2017REN1S067/document.

Testo completo

Abstract (sommario):

Cette thèse traite de la conception de méthodes automatisées ou semi-automatisées pour détecter et identifier des algorithmes cryptographiques dans des programmes compilés en langage machine. La première méthode proposée a pour but l'identification de primitives symétriques. L'implémentation en langage machine d'une primitive symétrique, assimilée à une suite d'instructions, est représentée par un graphe. Sous cette forme, le code est modifié à l'aide de règles de réécriture tout en préservant une certaine notion de sémantique lors d'une phase dite de normalisation. L'objectif est de faire émerger des expressions communes à différentes implémentations d'une même primitive. Ces expressions servent alors de base à la création de signatures efficaces. La recherche de ces signatures s'effectue à l'aide d'un algorithme énumérant les isomorphismes de sous-graphe. La seconde méthode, conçue en complément de la première, produit une représentation synthétique facilitant l'identification des modes opératoires. Cette représentation se définit comme le plus petit sous-graphe préservant les distances entre des sous-ensembles de nœuds précédemment identifiés comme étant les paramètres d'entrée et de sortie des primitives impliquées
This thesis is about the design of automatic or semi-automatic methods to detect and identify cryptographic algorithms inside programs compiled into machine code. Two methods are presented. The objective of the first method is to identify cryptographic primitives. A machine code implementation of a cryptographic primitive, regarded as a sequence of instructions, is represented by a graph structure. During a normalization phase, a set of rewrite rules is used to modify this graph representation while preserving a specific notion of semantics. The goal is to converge towards expressions which are shared across several implementations of the same primitive. We use these expressions as a basis to create efficient signatures. A subgraph isomorphism enumeration algorithm is used to search for signatures. The second method is built on top of the first one. It produces a synthetic representation designed to help in the identification of modes of operation. This synthetic representation is defined as the smallest subgraph which preserve distances between sets of vertices previously identified as the input and output parameters of the primitives involved within the mode of operation

Gli stili APA, Harvard, Vancouver, ISO e altri

11

De, Roberto Paola. "Information visualization: from petroglyphs to CoDe Graphs". Doctoral thesis, Universita degli studi di Salerno, 2018. http://hdl.handle.net/10556/3083.

Testo completo

Abstract (sommario):

2016 - 2017
Data visualization concerns the communication of data through visual representations and techniques. It aims at enhancing perception and support data-driven decision making so enabling insights otherwise hard to achieve. A good visualization of data makes it possible to identify patterns and enables better understanding of phenomena. In other words, data visualization is related to an innate human ability to quickly comprehend, discern and convert patterns into useful and usable information. Humans have used visual graphical representations as early as 35.000 B.C., through cave drawings. Indeed, human ancestors already reasoned in terms of models or schemata: the visual representation of information is an ancient concept, as witnessed by the rock carvings found. Over the centuries, information visualization has evolved to take into account the changing human needs and its use has become more and more conscious. The first data visualization techniques have been developed to observe and represent physical quantities, geography and celestial positions. Successively, the combined use of euclidean geometry and algebra improved accuracy and complexity of information representation, in different fields, such as astronomy, physics and engineering. Finally, in the last century most modern forms of data representations were invented: starting from charts, histograms, and graphs up to high dimensional data, and dynamic and interactive visualizations of temporal data [41]. Nowadays, the huge amount of information enables more precise interpretation of phenomena so fostering the adoption of infographic techniques, in particular, for supporting managerial decision-making in the business area... [edited by author]
XVI n.s.

Gli stili APA, Harvard, Vancouver, ISO e altri

12

Valicov, Petru. "Problèmes de placement, de coloration et d’identification". Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14549/document.

Testo completo

Abstract (sommario):

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques.La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum ID est n-1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour le paramètre ID dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ID dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits
In this thesis we study three theoretical computer science problems, namely the orthogonal packing problem (OPP for short), strong edge-colouring and identifying codes.OPP consists in testing whether a set of rectangular items can be packed in a rectangular container without overlapping and without exceeding the borders of this container. An additional constraint is that the rotation of the items is not allowed. The problem is NP-hard even when the problem is reduced to packing squares in a square. We propose an exact algorithm for solving OPP efficiently using the characterization of the problem by interval graphs proposed by Fekete and Schepers. For this purpose we use some compact representation of interval graphs - MPQ-trees. We show experimental results of our approach by comparing them to the results of other algorithms known in the literature. we observe promising gains.The study of strong edge-colouring and identifying codes is focused on the structural and computational aspects of these combinatorial problems. In the case of strong edge-colouring we are interested in the families of planar graphs and subcubic graphs. We show optimal upper bounds for the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also show that every planar subcubic graph without induced cycles of length 4 and 5 can be strong edge-coloured with at most nine colours. Finally, we confirm the difficulty of the problem by showing that it remains NP-complete even in some restricted classes of planar subcubic graphs.For the subject of identifying codes we propose a characterization of non-trivial graphs having maximum identifying code number ID, that is n-1, where n is the number of vertices. We study the case of line graphs and prove lower and upper bounds for ID parameter in this class. At last we investigate the complexity of the corresponding decision problem and show the existence of a linear algorithm for computing ID of the line graph L(G) where G has the size of the tree-width bounded by a constant. On the other hand, we show that the identifying code problem is NP-complete in various subclasses of planar graphs

Gli stili APA, Harvard, Vancouver, ISO e altri

13

Mumba, Nephtale Bvalamanja. "Codes, graphs and designs from maximal subgroups of alternating groups". University of the Western Cape, 2018. http://hdl.handle.net/11394/6165.

Testo completo

Abstract (sommario):

Philosophiae Doctor - PhD (Mathematics)
The main theme of this thesis is the construction of linear codes from adjacency matrices or sub-matrices of adjacency matrices of regular graphs. We first examine the binary codes from the row span of biadjacency matrices and their transposes for some classes of bipartite graphs. In this case we consider a sub-matrix of an adjacency matrix of a graph as the generator of the code. We then shift our attention to uniform subset graphs by exploring the automorphism groups of graph covers and some classes of uniform subset graphs. In the sequel, we explore equal codes from adjacency matrices of non-isomorphic uniform subset graphs and finally consider codes generated by an adjacency matrix formed by adding adjacency matrices of two classes of uniform subset graphs.

Gli stili APA, Harvard, Vancouver, ISO e altri

14

Benaddi, Tarik. "Sparse graph-based coding schemes for continuous phase modulations". Phd thesis, Toulouse, INPT, 2015. http://oatao.univ-toulouse.fr/16037/1/Benaddi_Tarik.pdf.

Testo completo

Abstract (sommario):

The use of the continuous phase modulation (CPM) is interesting when the channel represents a strong non-linearity and in the case of limited spectral support; particularly for the uplink, where the satellite holds an amplifier per carrier, and for downlinks where the terminal equipment works very close to the saturation region. Numerous studies have been conducted on this issue but the proposed solutions use iterative CPM demodulation/decoding concatenated with convolutional or block error correcting codes. The use of LDPC codes has not yet been introduced. Particularly, no works, to our knowledge, have been done on the optimization of sparse graph-based codes adapted for the context described here. In this study, we propose to perform the asymptotic analysis and the design of turbo-CPM systems based on the optimization of sparse graph-based codes. Moreover, an analysis on the corresponding receiver will be done.

Gli stili APA, Harvard, Vancouver, ISO e altri

15

Han, Junsheng. "Code representation and performance of graph-Based decoding". Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2008. http://wwwlib.umi.com/cr/ucsd/fullcit?p3297580.

Testo completo

Abstract (sommario):

Thesis (Ph. D.)--University of California, San Diego, 2008.
Title from first page of PDF file (viewed April 28, 2008). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references.

Gli stili APA, Harvard, Vancouver, ISO e altri

16

Moncel, Julien. "Codes Identifiants dans les Graphes". Phd thesis, Université Joseph Fourier (Grenoble), 2005. http://tel.archives-ouvertes.fr/tel-00010293.

Testo completo

Abstract (sommario):

Ce mémoire présente quelques résultats récents sur les codes identifiants. La thèse est structurée en cinq chapitres. Le Chapitre 1 contient les définitions et présente la notion de code identifiant. Dans le Chapitre 2 nous étudions l'aspect algorithmique des codes identifiants. Le Chapitre 3 contient quelques résultats concernant des classes de graphes particulières, à savoir les hypercubes, les grilles, et les cycles. Nous étudions quelques questions extrémales au Chapitre 4. Enfin, le Chapitre 5 présente quelques résultats récents sur les codes identifiants dans les graphes aléatoires. A la fin du document nous résumons les résultats les plus importants que nous avons présentés et nous donnons quelques problèmes ouverts sur le sujet.

Gli stili APA, Harvard, Vancouver, ISO e altri

17

Kumwenda, Khumbo. "Codes, graphs and designs related to iterated line graphs of complete graphs". Thesis, University of the Western Cape, 2011. http://etd.uwc.ac.za/index.php?module=etd&action=viewtitle&id=gen8Srv25Nme4_1742_1320645699.

Testo completo

Abstract (sommario):

In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs ôn that are embeddable into the strong product L1(Kn) â K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, ôn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of ôn and Hn and determine their parameters.

Gli stili APA, Harvard, Vancouver, ISO e altri

18

Kindestam, Anton. "Graph-based features for machine learning driven code optimization". Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-211444.

Testo completo

Abstract (sommario):

In this paper we present a method of using the Shortest-Path Graph Kernel, on graph-based features of computer programs, to train a Support Vector Regression model which predicts execution time speedup over baseline given an unseen program and a point in optimization space, based on a method proposed in Using Graph-Based Program Characterization for Predictive Modeling by Park et al. The optimization space is represented by command-line parameters to the polyhedral C-to-C compiler PoCC, and PolyBench is used to generate the data set of speedups over baseline. The model is found to produce results reasonable by some metrics, but due to the large error and the pseudo-random behaviour of the output the method, in its current form, must reluctantly be rejected.
I den här raporten presenterar vi en metod att träna en Stöd-vektor-regressions-modell som givet ett osett program och en punkt i optimeringsrymden kan förutsäga hur mycket snabbare över baslinjen programmet kommer att exekvera förutsatt att man applicerar givna optimeringar. För att representera programmet använder vi en grafstruktur för vilken vi kan använda en grafkärna, Shortest-Path Graph Kernel, vilken kan avgöra hur lika två olika grafer är varandra. Metoden är baserad på en metod presenterad av Park et al. i Using Graph-Based Program Characterization for Predictive Modeling. Optimeringsrymden erhålls genom olika kombinationer av kommandoradsparametrar till den polyhedriska C-till-C-kompilatorn PoCC. Testdatat erhölls genom att förberäkna hastighetsfaktorer för alla optimeringar och alla program i test-algoritms-biblioteket PolyBench. Vi finner att modellen i vissa mått mätt producerar "bra" resultat, men p.g.a. av det stora felet och det slumpmässiga beteendet måste dessvärre metoden, i dess nuvarande form,förkastas.

Gli stili APA, Harvard, Vancouver, ISO e altri

19

Foucaud, Florent. "Aspects combinatoires et algorithmiques des codes identifiants dans les graphes". Phd thesis, Université Sciences et Technologies - Bordeaux I, 2012. http://tel.archives-ouvertes.fr/tel-00766138.

Testo completo

Abstract (sommario):

Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.

Gli stili APA, Harvard, Vancouver, ISO e altri

20

Hong, Changwan. "Code Optimization on GPUs". The Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1557123832601533.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

21

Jeannot, Emmanuel. "Allocation de graphes de taches parametres et generation de code". Lyon, École normale supérieure (sciences), 1999. http://www.theses.fr/1999ENSL0130.

Testo completo

Abstract (sommario):

Le graphe de taches (gdt) est un modele tres utilise pour la prediction de performance et l'optimisation d'applications paralleles. Il presente cependant deux desavantages. La taille d'un gdt depend de la valeur des parametres de l'application qu'il modelise. Un algorithme d'ordonnancement statique prend en entree un gdt et affecte, a chaque tache, un processeur et une date de debut d'execution. La duree du calcul de l'ordonnancement ainsi que le cout memoire dependent de la taille du graphe et donc de la valeur des parametres de l'application. Une telle approche n'est pas extensible car pour les grandes valeurs des parametres le graphe de taches correspondant peut ne pas tenir en memoire. Cette methode n'est pas non plus adaptative car un changement de machine cible ou des parametres du programme impose de recalculer l'ordonnancement. Pour apporter une reponse a ces deux problemes nous avons etudie un modele intermediaire : le graphe de taches parametre (gtp). Un gtp est une representation compacte et symbolique des graphes de taches issus de certaines applications de calcul scientifique. Il utilise les parametres du programme qui doivent etre instancies pour construire le gdt. Nos travaux se decomposent en trois volets. (1) nous avons concu un algorithme d'ordonnancement du gtp. Le cout memoire de l'ordonnancement se trouve alors grandement reduit. Cet algorithme est integre dans un schema dynamique pour permettre la construction de programmes generiques. (2) nous presentons une heuristique d'allocation symbolique du gtp appelee slc. Nous garantissons que cette allocation forme des grappes lineaires. Le temps et le cout memoire de l'allocation sont alors independants de la valeur des parametres. (3) nous avons realise un prototype de generateur de code qui produit un programme multithreade se conformant a l'allocation trouvee par slc. Nous obtenons ainsi un code parallele portable et generique qui fonctionne pour toutes les valeurs des parametres du programme.

Gli stili APA, Harvard, Vancouver, ISO e altri

22

Lang, Julie. "Graphs admitting (1, ≤ 2)-identifying codes". Thesis, Kansas State University, 2014. http://hdl.handle.net/2097/18260.

Testo completo

Abstract (sommario):

Master of Science
Department of Mathematics
Sarah Reznikoff
A (1, ≤ 2)-identifying code is a subset of the vertex set C of a graph such that each pair of vertices intersects C in a distinct way. This has useful applications in locating errors in multiprocessor networks and threat monitoring. At the time of writing, there is no simply-stated rule that will indicate if a graph is (1, ≤ 2)-identifiable. As such, we discuss properties that must be satisfied by a valid (1, ≤ 2)-identifying code, characteristics of a graph which preclude the existence of a (1, ≤ 2)-identifying code, and relationships between the maximum degree and order of (1, ≤ 2)-identifiable graphs. Additionally, we show that (1, ≤ 2)-identifiable graphs have no forbidden induced subgraphs and provide a list of (1, ≤ 2)-identifiable graphs with minimum (1, ≤ 2)-identifying codes indicated.

Gli stili APA, Harvard, Vancouver, ISO e altri

23

Sankaranarayanan, Sundararajan. "Iterative Decoding of Codes on Graphs". Diss., The University of Arizona, 2006. http://hdl.handle.net/10150/194618.

Testo completo

Abstract (sommario):

The growing popularity of a class of linear block codes called the low-density parity-check (LDPC) codes can be attributed to the low complexity of the iterative decoders, and their potential to achieve performance very close to the Shannon capacity. This makes them an attractive candidate for ECC applications in communication systems. This report proposes methods to systematically construct regular and irregular LDPC codes.A class of regular LDPC codes are constructed from incidence structures in finite geometries like projective geometry and affine geometry. A class of irregular LDPC codes are constructed by systematically splitting blocks of balanced incomplete block designs to achieve desired weight distributions. These codes are decoded iteratively using message-passing algorithms, and the performance of these codes for various channels are presented in this report.The application of iterative decoders is generally limited to a class of codes whose graph representations are free of small cycles. Unfortunately, the large class of conventional algebraic codes, like RS codes, has several four cycles in their graph representations. This report proposes an algorithm that aims to alleviate this drawback by constructing an equivalent graph representation that is free of four cycles. It is theoretically shown that the four-cycle free representation is better suited to iterative erasure decoding than the conventional representation. Also, the new representation is exploited to realize, with limited success, iterative decoding of Reed-Solomon codes over the additive white Gaussian noise channel.Wiberg, Forney, Richardson, Koetter, and Vontobel have made significant contributions in developing theoretical frameworks that facilitate finite length analysis of codes. With an exception of Richardson's, most of the other frameworks are much suited for the analysis of short codes. In this report, we further the understanding of the failures in iterative decoders for the binary symmetric channel. The failures of the decoder are classified into two categories by defining trapping sets and propagating sets. Such a classification leads to a successful estimation of the performance of codes under the Gallager B decoder. Especially, the estimation techniques show great promise in the high signal-to-noise ratio regime where the simulation techniques are less feasible.

Gli stili APA, Harvard, Vancouver, ISO e altri

24

Simko, Thomas J. "Cloneless: Code Clone Detection via Program Dependence Graphs with Relaxed Constraints". DigitalCommons@CalPoly, 2019. https://digitalcommons.calpoly.edu/theses/2040.

Testo completo

Abstract (sommario):

Code clones are pieces of code that have the same functionality. While some clones may structurally match one another, others may look drastically different. The inclusion of code clones clutters a code base, leading to increased costs through maintenance. Duplicate code is introduced through a variety of means, such as copy-pasting, code generated by tools, or developers unintentionally writing similar pieces of code. While manual clone identification may be more accurate than automated detection, it is infeasible due to the extensive size of many code bases. Software code clone detection methods have differing degree of success based on the analysis performed. This thesis outlines a method of detecting clones using a program dependence graph and subgraph isomorphism to identify similar subgraphs, ultimately illuminating clones. The project imposes few constraints when comparing code segments to potentially reveal more clones.

Gli stili APA, Harvard, Vancouver, ISO e altri

25

Normann, Per. "Parallel graph coloring : Parallel graph coloring on multi-core CPUs". Thesis, Uppsala universitet, Avdelningen för beräkningsvetenskap, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-227656.

Testo completo

Abstract (sommario):

In recent times an evident trend in hardware is to opt for multi-core CPUs. This has lead to a situation where an increasing number of sequential algorithms are parallelized to fit these new multi-core environments. The greedy Multi-Coloring algorithm is a strictly sequential algorithm that is used in a wide range of applications. The application in focus is on decomposition by graph coloring for preconditioning techniques suitable for iterative solvers like the and methods. In order to perform all phases of these iterative solvers in parallel the graph analysis phase needs to be parallelized. Albeit many attempts have been made to parallelize graph coloring non of these attempts have successfully put the greedy Multi-Coloring algorithm into obsolescence. In this work techniques for parallel graph coloring are proposed and studied. Quantitative results, which represent the number of colors, confirm that the best new algorithm, the Normann algorithm, is performing on the same level as the greedy Multi-Coloring algorithm. Furthermore, in multi-core environments the parallel Normann algorithm fully outperforms the classical greedy Multi-Coloring algorithm for all large test matrices. With the features of the Normann algorithm quantified and presented in this work it is now possible to perform all phases of iterative solvers like and methods in parallel.

Gli stili APA, Harvard, Vancouver, ISO e altri

26

Khandekar, Aamod McEliece Robert J. "Graph-based codes and iterative decoding /". Diss., Pasadena, Calif. : California Institute of Technology, 2003. http://resolver.caltech.edu/CaltechETD:etd-06202002-170522.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

27

Noriega, Alexandra. "Matlab Implementation of a Tornado Forward Error Correction Code". Thesis, University of North Texas, 2011. https://digital.library.unt.edu/ark:/67531/metadc84260/.

Testo completo

Abstract (sommario):

This research discusses how the design of a tornado forward error correcting channel code (FEC) sends digital data stream profiles to the receiver. The complete design was based on the Tornado channel code, binary phase shift keying (BPSK) modulation on a Gaussian channel (AWGN). The communication link was simulated by using Matlab, which shows the theoretical systems efficiency. Then the data stream was input as data to be simulated communication systems using Matlab. The purpose of this paper is to introduce the audience to a simulation technique that has been successfully used to determine how well a FEC expected to work when transferring digital data streams. The goal is to use this data to show how FEC optimizes a digital data stream to gain a better digital communications systems. The results conclude by making comparisons of different possible styles for the Tornado FEC code.

Gli stili APA, Harvard, Vancouver, ISO e altri

28

Chu, Lei. "Colouring Cayley Graphs". Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1125.

Testo completo

Abstract (sommario):

We will discuss three ways to bound the chromatic number on a Cayley graph. 1. If the connection set contains information about a smaller graph, then these two graphs are related. Using this information, we will show that Cayley graphs cannot have chromatic number three. 2. We will prove a general statement that all vertex-transitive maximal triangle-free graphs on n vertices with valency greater than n/3 are 3-colourable. Since Cayley graphs are vertex-transitive, the bound of general graphs also applies to Cayley graphs. 3. Since Cayley graphs for abelian groups arise from vector spaces, we can view the connection set as a set of points in a projective geometry. We will give a characterization of all large complete caps, from which we derive that all maximal triangle-free cubelike graphs on 2ⁿ vertices and valency greater than 2ⁿ/4 are either bipartite or 4-colourable.

Gli stili APA, Harvard, Vancouver, ISO e altri

29

Coupechoux, Pierre. "Codes et jeux de soustraction et de poursuite dans les graphes". Thesis, Toulouse, INSA, 2018. http://www.theses.fr/2018ISAT0016/document.

Testo completo

Abstract (sommario):

Les codes identifiants ont été introduits en 1998 par Karpovsky, Chakrabarty et Levitin. Un code identifiant est un sous-graphe tel que chaque sommet est identifié de manière unique par les sommets du code qui l'entourent. Il existe plusieurs variantes de ces codes, dont notamment une version colorée dans laquelle les sommets sont identifiés par les couleurs dans leur voisinage. Dans cette thèse, nous cherchons en particulier à construire un cycle le plus grand possible qui admette une coloration identifiante, étant donné un nombre de couleurs fixé. Nous avons aussi étudié le problème des codes identifiants sur une classe particulière de graphes orientés : les tournois. Dans une seconde partie, nous avons aussi étudié deux jeux particuliers. Le premier est une généralisation des jeux octaux - qui se jouent normalement sur un tas - aux graphes. Plus précisemment, le jeu 0.33 ; chaque joueur peut retirer un ou deux sommets voisins d'un graphe, sans déconnecter ce dernier. Le premier qui ne peut plus jouer perd. Nous avons été capable de caractériser les issues de ce jeu dans des classes de graphes particulières, les étoiles subdivisées et les bi-étoiles subdivisées. Le second jeu est appelé le jeu du Pompier (Firefighter). Il consiste à arrêter un feu qui se propage dans un graphe en protégeant des sommets à chaque tour. Nous avons résolu une conjecture sur ce jeu, et introduit la version online, pour laquelle nous avons pu donner des résultats d'approximation
Identifying codes were introduced in 1998 by Karpovsky, Chakrabarty and Levitin. An identifying code is a subgraph such that each vertex is uniquely identified by the vertices in its neighborhood. There are several variants of these codes, including a colored version where the vertices are identified by the colors in their neighborhood. In this phd, we want to build an identifying coloring of a large cycle, given a fixed number of colors. We also studied identified codes in a certain class of oriented graphs: tournaments. We have also studied some topics in the game theory. The first one is a generalization of octal games, where we play on a graph instead of a heap. More precisely, the 0.33 game; each player can remove one or two vertices in a graph, with no disconnection allowed. The first player who cannot play loses. We studied this game in some graph classes: subdivided stars and subdivided bistars. The other game is called the Firefighter game. It's a one player game, where this one wants to contain a spreading fire in a graph. We solved a conjecture about this game, and introduced the online version of the game, for which we found some approximation results

Gli stili APA, Harvard, Vancouver, ISO e altri

30

Vico, Oton Albert. "Collected results on semigroups, graphs and codes". Doctoral thesis, Universitat Rovira i Virgili, 2012. http://hdl.handle.net/10803/97214.

Testo completo

Abstract (sommario):

In this thesis we present a compendium of _ve works where discrete mathematics play a key role. The _rst three works describe di_erent developments and applications of the semigroup theory while the other two have more independent topics. First we present a result on semigroups and code e_ciency, where we introduce our results on the so-called Geil-Matsumoto bound and Lewittes' bound for algebraic geometry codes. Following that, we work on semigroup ideals and their relation with the Feng-Rao numbers; those numbers, in turn, are used to describe the Hamming weights which are used in a broad spectrum of applications, i.e. the wire-tap channel of type II or in the t-resilient functions used in cryptography. The third work presented describes the non-homogeneous patterns for semigroups, explains three di_erent scenarios where these patterns arise and gives some results on their admissibility. The last two works are not as related as the _rst three but still use discrete mathematics. One of them is a work on the applications of coding theory to _ngerprinting, where we give results on the traitor tracing problem and we bound the number of colluders in a colluder set trying to hack a _ngerprinting mark made with a Reed-Solomon code. And _nally in the last work we present our results on scientometrics and graphs, modeling the scienti_c community as a cocitation graph, where nodes represent authors and two nodes are connected if there is a paper citing both authors simultaneously. We use it to present three new indices to evaluate an author's impact in the community.

Gli stili APA, Harvard, Vancouver, ISO e altri

31

Reznik, Alexander 1974. "Iterative decoding of codes defined on graphs". Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/9949.

Testo completo

Abstract (sommario):

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998.
Includes bibliographical references (leaves 56-58).
by Alexander Reznik.
M.S.

Gli stili APA, Harvard, Vancouver, ISO e altri

32

Anthapadmanabhan, Nagaraj Prasanth. "Random codes and graphs for secure communication". College Park, Md.: University of Maryland, 2009. http://hdl.handle.net/1903/9293.

Testo completo

Abstract (sommario):

Thesis (Ph. D.) -- University of Maryland, College Park, 2009.
Thesis research directed by: Dept. of Electrical and Computer Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

Gli stili APA, Harvard, Vancouver, ISO e altri

33

Davison, Benjamin Kenneth. "Universal graph literacy: understanding how blind and low vision students can satisfy the common core standards with accessible auditory graphs". Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/47621.

Testo completo

Abstract (sommario):

Auditory graphs and active point estimation provide an inexpensive, accessible alternative for low vision and blind K-12 students using number lines and coordinate graphs. In the first phase of this research program, a series of four psychophysics studies demonstrated an interactive auditory number line that enables blind, low vision, and sighted people to find small targets with a laptop, headphones, and a mouse or a keyboard. The Fitts' Law studies showed that, given appropriate auditory feedback, blind people can use a mouse. In addition, auditory feedback can generate target response patterns similar to when people use visual feedback. Phase two introduced SQUARE, a novel method for building accessible alternatives to existing education technologies. The standards-driven and teacher-directed approach generated 17 graphing standards for sixth grade mathematics, all of which emphasized point estimation. It also showed that how only few basic behavioral components are necessary for these graphing problems. The third phase evaluated active point estimation tools in terms of training, classroom situations, and a testing situation. This work shows that students can learn to graph in K-12 environments, regardless of their visual impairment. It also provides several technologies used for graphing, and methods to further develop education accessibility research.

Gli stili APA, Harvard, Vancouver, ISO e altri

34

Holma, Niklas. "Program Dependence Graph Generation and Analysis for Source Code Plagiarism Detection". Thesis, Linköpings universitet, Institutionen för datavetenskap, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-87446.

Testo completo

Abstract (sommario):

Systems and tools that finds similarities among essays and reports are widely used by todays universities and schools to detect plagiarism. Such tools are however insufficient when used for source code comparisons since they are fragile to the most simplest forms of diguises. Other methods that analyses intermediate forms such as token strings, syntax trees and graph representations have shown to be more effective than using simple textual matching methods. In this master thesis report we discuss how program dependence graphs, an abstract representation of a programs semantics, can be used to find similar procedures. We also present an implementation of a system that constructs approximated program dependence graphs from the abstract syntax tree representation of a program. Matching procedures are found by testing graph pairs for either sub-graph isomorphism or graph monomorphism depending on whether structured transfer of control has been used. Under a scenario based evaluation our system is compared to Moss, a popular plagiarism detection tool. The result shows that our system is more or least as effective than Moss in finding plagiarized procedured independently on the type of modifications used.
System och verktyg som hittar likheter mellan uppsatser och rapporter används i stor omfattning av dagens universitet och skolor för att hitta plagiat bland studenters inlämningar. Sådana verktyg är dock otillräckliga när de används för att jämföra programkod eftersom de är svaga mot de enklaste formerna av modifikationer. Andra metoder som analyserar mellanstegsformer såsom tokensträngar, syntaxträd och grafrepresentationer har visat sig vara mer effektiva än att använda sig av enkla textuella metoder. I denna examensuppsats diskuterar vi hur programberoendegrafer, en abstrakt representation av en programs semantik, kan användas för att hitta jämförelsevis liknande procedurer. Vi presenterar också ett system som konstruerar approximerade programberoendegrafer från det abstrakta syntaxträdet av ett program. Matchande procedurer hittas genom att testa grafpar för antingen sub-graf isomorfism eller monomorfism beroende på om strukturerad byte av kontrolflöde har använts. I en scenariobaserad utvärdering jämför vi vårt system mot Moss, ett populärt verktyg för att detektera plagiat. Resultaten visar att vårt system är lika eller mer effektivt som Moss att detektera plagierade procedurer oberoende av de typer av modifikationer som använts.

Gli stili APA, Harvard, Vancouver, ISO e altri

35

Andriyanova, Iryna. "Etude d'une certaine construction des codes definis par les graphes: codes TLDPC". Phd thesis, Télécom ParisTech, 2006. http://pastel.archives-ouvertes.fr/pastel-00002465.

Testo completo

Abstract (sommario):

Ce travail est consacr'e `a l'analyse et la construction de codes d´efinis par des graphes dans le but d'obtenir des familles de codes ayant, pour une complexit´e de d´ecodage faible, de tr`es bonnes performances pour une large plage de rapports signal-`a-bruit. Nous nous int´eressons `a une famille de codes que nous appelons TLDPC (pour Tailbiting Trellis Low-Density Parity Check) qui contient, comme sous-familles, `a la fois les Turbo codes de Berrou et Glavieux et les codes de Gallager appel´es aussi codes LDPC. La premi`ere partie de cette th`ese est consacr´ee `a l'´etude des codes TLDPC binaires. Nous nous sommes int´eress´es au caract`ere asymptotiquement bon de ces codes et avons obtenus des conditions n´ecessaires ou suffisantes en ´etudiant les polyn

Gli stili APA, Harvard, Vancouver, ISO e altri

36

Andriyanova, Iryna. "Etude d'une certaine construction des codes définis par les graphes : codes TLDPC". Paris, ENST, 2006. http://www.theses.fr/2006ENST0042.

Testo completo

Abstract (sommario):

Ce travail est consacré à l’analyse et à la construction de codes définis par des graphes dans le but d’obtenir des familles de codes ayant, pour une complexité de décodage faible, de trés bonnes performances pour une large plage de rapports signal-à-bruit. Nous nous intéressons à une famille de codes TLDPC (Tail-biting Trellis Low-Density Parity Check) qui contient, comme sous-familles, à la fois les Turbo codes de Berrou et Glavieux et les codes de Gallager appelés aussi codes LDPC. La première partie de la thèse est consacrée à l'étude du caractère asymptotiquement bon des codes TLDPC binaires. Nous avons obtenu des conditions nécessaires et suffisantes sur ce caractère qui nous ont donné des bornes sur la proportion des noeuds de degré 2. Nous avons ensuite optimisé la distribution des noeuds des autres variables et nous obtenons de trés bonnes performances. Dans la deuxième partie, nous étudions certains codes LDPC et TLDPC non-binaires. Nous y présentons une famille de codes TLDPC non-binaires, avec une structure simple dont la pente des courbes de taux d'erreur dans la région de faible rapport signal-à-bruit est plus forte que pour les codes binaires correspondants. Notons qu’un code LDPC ayant au moins deux symboles de degré 2 par équation de parité peut être vu et décodé comme un code TLDPC avec des symboles de degré 1. Pour les codes de cycles d’un graphe, cette façon de faire nécessite beaucoup moins d'itérations de décodage. En introduisant dans la structure des codes de cycles d’un graphe des noeuds de degré 1, nous obtenons pour le canal à effacements en autorisant une petite fraction de symboles effacés aprés décodage, une famille de codes dont les performances se rapprochent encore des limites théoriques de Shannon
This study is dedicated to the analysis and the design of sparse-graph codes in order to construct codes having high performances both in waterfall and error-floor regions under an iterative decoding algorithm of low complexity. In particular, we explore a class of Tail-biting trellis LDPC (TLDPC) codes involving the class of turbo codes of Berrou and Glavieux as well as the class of codes of Gallager known as LDPC codes. In the first part of the thesis, binary TLDPC codes are investigated. We found sufficient and necessary conditions to ensure that they are asymptotically good by calculating their average weight enumerator and studying a certain graph in which the cycles correspond to potentially low weight codewords. These conditions give us an upper bound on the fraction of degree-2 nodes in the Tanner graph. By keeping the fraction of degree-2 nodes below the upper bound, we optimised the degree distribution of other variable nodes by EXIT chart techniques and thus we obtained good performances under standard iterative decoding algorithm (belief propagation). In the second part of the thesis, some non-binary TLDPC and LDPC codes are investigated. We propose a family of non-binary TLDPC codes with a very simple structure and a steep waterfall region. We also noticed that any LDPC code with at least two degree-2 symbols per parity-check equation can be represented as a TLDPC code with symbols in degree 1 in its structure. Thus, it can be decoded like a TLDPC code. In the case of cycle codes, such a decoding decreases significantly the number of iterations while the iterative decoding threshold does not seem to change. Moreover, by allowing a constant fraction of degree 1 symbols for this class of codes and a small fraction of erased bits after decoding over binary erasure channel, we obtained codes with improved iterative decoding performances

Gli stili APA, Harvard, Vancouver, ISO e altri

37

Andriyanova, Iryna. "Étude d'une certaine construction des codes définis par les graphes : codes TLDPC /". Paris : École nationale supérieure des télécommunications, 2007. http://catalogue.bnf.fr/ark:/12148/cb41087138x.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

38

Jiang, Wen. "Maximum Codes with the Identifiable Parent Property". Diss., Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/14072.

Testo completo

Abstract (sommario):

We study codes that have identifiable parent property. Such codes are called IPP codes. Research on IPP codes is motivated by design of schemes that protect against piracy of digital products. Construction and decoding of maximum IPP codes have been studied in rich literature. General bounds on F(n,q), the maximum size of IPP codes of length n over an alphabet with q elements, have been obtained through the use of techniques from graph theory and combinatorial design. Improved bounds on F(3,q) and F(4,q) are obtained. Probabilistic techniques are also used to prove the existence of certain IPP codes. We prove a precise formula for F(3,q), construct maximum IPP codes with size F(3,q), and give an efficient decoding algorithm for such codes. The main techniques used in this thesis are from graph theory and nonlinear optimization. Our approach may be used to improve bounds on F(2k+1, q). For example, we characterize the associated graphs of maximum IPP codes of length 5, and obtain bounds on F(5,q).

Gli stili APA, Harvard, Vancouver, ISO e altri

39

Martínez, Barona Berenice. "(1, ≤ ℓ)-identifying codes in digraphs and graphs". Doctoral thesis, Universitat Politècnica de Catalunya, 2020. http://hdl.handle.net/10803/669726.

Testo completo

Abstract (sommario):

The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs.
El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos

Gli stili APA, Harvard, Vancouver, ISO e altri

40

Fish, Washiela. "Codes from uniform subset graphs and cycle products". Thesis, University of the Western Cape, 2007. http://etd.uwc.ac.za/index.php?module=etd&action=viewtitle&id=gen8Srv25Nme4_6789_1249271085.

Testo completo

Abstract (sommario):

In this thesis only Binary codes are studied. Firstly, the codes overs the field GF(2) by the adjacency matrix of the complement T(n), ofthe triangular graph, are examined. It is shown that the code obtained is the full space F2 s(n/2) when n= 0 (mod 4) and the dual code of the space generated by the j-vector when n= 2(mod 4). The codes from the other two cases are less trivial: when n=1 (mod 4) the code is [(n 2), (n 2 ) - n + 1, 3] code, and when n = 3 (mod 4) it is an [(n 2), (n 2) - n, 4 ] code.

Gli stili APA, Harvard, Vancouver, ISO e altri

41

Seneviratne, Padmapani. "Permutation decoding of codes from graphs and designs". Connect to this title online, 2007. http://etd.lib.clemson.edu/documents/1193079265/.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

42

Rombach, Michaela Puck. "Colouring, centrality and core-periphery structure in graphs". Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:7326ecc6-a447-474f-a03b-6ec244831ad4.

Testo completo

Abstract (sommario):

Krivelevich and Patkós conjectured in 2009 that χ(G(n, p)) ∼ χ=(G(n, p)) ∼ χ∗=(G(n, p)) for C/n < p < 1 − ε, where ε > 0. We prove this conjecture for n−1+ε1 < p < 1 − ε2 where ε1, ε2 > 0. We investigate several measures that have been proposed to indicate centrality of nodes in networks, and find examples of networks where they fail to distinguish any of the vertices nodes from one another. We develop a new method to investigate core-periphery structure, which entails identifying densely-connected core nodes and sparsely-connected periphery nodes. Finally, we present an experiment and an analysis of empirical networks, functional human brain networks. We found that reconfiguration patterns of dynamic communities can be used to classify nodes into a stiff core, a flexible periphery, and a bulk. The separation between this stiff core and flexible periphery changes as a person learns a simple motor skill and, importantly, it is a good predictor of how successful the person is at learning the skill. This temporally defined core-periphery organisation corresponds well with the core- periphery detected by the method that we proposed earlier the static networks created by averaging over the subjects dynamic functional brain networks.

Gli stili APA, Harvard, Vancouver, ISO e altri

43

Muthivhi, Thifhelimbilu Ronald. "Codes Related to and Derived from Hamming Graphs". University of the Western Cape, 2013. http://hdl.handle.net/11394/4091.

Testo completo

Abstract (sommario):

Masters of Science
Codes Related to and Derived from Hamming Graphs T.R Muthivhi M.Sc thesis, Department of Mathematics, University of Western Cape For integers n; k 1; and k n; the graph 􀀀k n has vertices the 2n vectors of Fn2 and adjacency de ned by two vectors being adjacent if they di er in k coordinate positions. In particular, 􀀀1 n is the classical n-cube, usually denoted by H1(n; 2): This study examines the codes (both binary and p-ary for p an odd prime) of the row span of adjacency and incidence matrices of these graphs. We rst examine codes of the adjacency matrices of the n-cube. These have been considered in [14]. We then consider codes generated by both incidence and adjacency matrices of the Hamming graphs H1(n; 3) [12]. We will also consider codes of the line graphs of the n-cube as in [13]. Further, the automorphism groups of the codes, designs and graphs will be examined, highlighting where there is an interplay. Where possible, suitable permutation decoding sets will be given.

Gli stili APA, Harvard, Vancouver, ISO e altri

44

Bouznif, Marwane. "Algorithmes génériques en temps constant pour la résolution de problèmes combinatoires dans la classe des rotagraphes et fasciagraphes. Application aux codes identifiants, dominants-localisateurs et dominants-total-localisateurs". Phd thesis, Université de Grenoble, 2012. http://tel.archives-ouvertes.fr/tel-00744488.

Testo completo

Abstract (sommario):

Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle.

Gli stili APA, Harvard, Vancouver, ISO e altri

45

Perez, Cervantes Marco Polo. "Static methods to check low-level code for a graph reduction machine". Thesis, University of York, 2013. http://etheses.whiterose.ac.uk/6248/.

Testo completo

Abstract (sommario):

This thesis is about checking code for a graph-reduction machine computing by template instantiation. An equation-based static checking method for low-level code is proposed in this thesis. The checking can be performed without requiring any extra code annotations. Most ill-behaved programs can be rejected and most well-behaved programs can be accepted. The template code has no explicit information about data types but the static checker works by inferring low-level recursive types. We show compatibility between high-level and low-level type systems. We evaluate empirically the eff�ectiveness of checking to prevent failures. We investigate the low-level implementation of the static checker and how it can be made efficient.

Gli stili APA, Harvard, Vancouver, ISO e altri

46

Pedersen, Daniel. "Development of a Kinetic Monte Carlo Code". Thesis, Uppsala universitet, Materialteori, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-202711.

Testo completo

Abstract (sommario):

A framework for constructing kinetic monte carlo (KMC) simulations of diffusive events on a lattice was developed. This code was then tested by running simulations of Fe adatom diffusion on graphene and graphene-boron nitride surfaces. The results from these simulations was then used to show that the modeled diffusion adheres to the laws of brownian motion and generates results similar to recent research findings.

Gli stili APA, Harvard, Vancouver, ISO e altri

47

Papin, Jean-Charles. "A Scheduling and Partitioning Model for Stencil-based Applications on Many-Core Devices". Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLN032/document.

Testo completo

Abstract (sommario):

La puissance de calcul des plus grands calculateurs ne fait qu'augmenter: de quelques centaines de cœurs de calculs dans les années 1990, on en est maintenant à plusieurs millions! Leur infrastructure évolue aussi: elle n'est plus linéaire, mais complètement hiérarchique. Les applications de calcul intensif, largement utilisées par la communauté scientifique, doivent donc se munir d'outils permettant d'utiliser pleinement l'ensemble de ces ressources de manière efficace. La simulation numérique repose bien souvent sur d'importants calculs dont le coût, en termes de temps et d'accès mémoire, peut fortement varier au cours du temps: on parle de charge de calcul variable. Dans cette Thèse, on se propose d'étudier les outils actuels de répartition des données et des calculs, afin de voir les raisons qui font que de tels outils ne sont pas pleinement adaptés aux fortes variations de charge ainsi qu'à la hiérarchie toujours plus importante des nouveaux calculateurs. Nous proposerons alors un nouveau modèle d'ordonnancement et de partitionnement, basé sur des interactions physiques, particulièrement adapté aux applications basées sur des maillages réguliers et présentant de fortes variations de charge au cours du temps. Nous validerons alors ce modèle en le comparant à des outils de partitionnement de graphes reconnus et largement utilisés, et verrons les raisons qui le rendent plus performant pour des applications aussi bien parallèles que distribuées. Enfin, nous proposerons une interface nous permettant d'utiliser cette méthode d'ordonnancement dans des calculateurs toujours plus hiérarchiques
Computing capability of largest computing centers is still increasing: from a few hundred of cores in the90's, they can now exceed several million of cores! Their infrastructure also evolves: it is no longerlinear, but fully hierarchical.High Performance applications, well used by the scientific community, require on tools that allow themto efficiently and fully use computing resources.Numerical simulations mostly rely on large computations chains for which the cost (computing load), either acomputing time or a memory access time, can strongly vary over time: it is referred to as dynamic computing loadevolution.In this thesis, we propose to study actual data partitioning and computing scheduling tools, and to explore theirlimitations with regards to strong and repetitive load variation as well as the still increasing cluster hierarchy.We will then propose a new scheduling and partitioning model, based on physical interactions, particularlysuitable to regular mesh based applications that produce strong computing load variations over time.We will then compare our model against well-known and widely used graph partitioning tools and we will see thereasons that make this model more reliable for such parallel and distributed applications.Lastly, we will propose a multi-level scheduling interface that is specially designed to allow to use ourmodel in even more hierarchical clusters

Gli stili APA, Harvard, Vancouver, ISO e altri

48

Dumont, François. "Identification des objets dans un code procédural basée sur la décomposition de graphes". Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp03/MQ35670.pdf.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

49

Dumont, François. "Identification des objets dans un code procédural basée sur la décomposition de graphes". Mémoire, Université de Sherbrooke, 1997. http://savoirs.usherbrooke.ca/handle/11143/4361.

Testo completo

Abstract (sommario):

Les systèmes informatiques à forte entropie, développés avec une approche procédurale, ont subi beaucoup de modifications au cours des années. Par conséquent, ils sont devenus complexes et très mal documentés. De plus, la maintenance de ces systèmes est difficile à assurer et très coûteuse. Afin de pallier ces difficultés, plusieurs organisations orientent leurs systèmes vers de nouvelles technologies. Dans ces systèmes à forte entropie, l'identification des objets est essentielle pour conduire ceux-ci vers la technologie orientée objet. Cette technologie favorise la réutilisation, l'extension, la flexibilité, l'encapsulation, la modularité et la maintenance. Dans ce mémoire, nous présentons une approche automatique permettant d'identifier les objets dans un code procédural. L'identification des objets est la première phase de la migration d'un code source procédural vers un code source orienté objet. L'approche suggérée est basée sur la décomposition de graphes bipartites. Notre approche consiste à identifier des sous-graphes connexes à l'intérieur du graphe d'un système. Chacun des sous-graphes connexes est composé d'un n¶ud représentant les données, et d'un ou plusieurs n¶uds représentant les méthodes de l'objet.Les sous-graphes connexes représentent des candidats objet du système procédural. Cette approche est une amélioration de celle présentée par Canfora, Cimitile et Munro. Nous avons appliqué notre approche d'identification des objets sur des systèmes de grandes et moyennes tailles.Les résultats démontrent que l'approche est capable d'identifier des objets. De plus, un exemple connu illustre l'approche. Finalement, nous suggérons des pistes pour de futurs travaux.

Gli stili APA, Harvard, Vancouver, ISO e altri

50

Olifer, Maksim. "Architectural model synthesis from source code using Simulink and Hierarchical Function Call-Graphs". Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-296883.

Testo completo

Abstract (sommario):

Modern software systems developed in the automotive industry are very complex. In order to analyze, understand, and document these software systems, architectural models of the systems at different abstraction levels are used. However, these models are typically ambiguous and inconsistent with the implementation. This thesis presents an approach to construct an unambiguous model of C code in an automatic manner, with a focus on architecture consistency by employing the Simulink environment extended by an external custom GUI. Such approach also facilitates compliance with the functional safety standard ISO 26262 that requires models of software systems (including legacy code), where the models capture both its behavior and structure. More specifically, we develop a method for hierarchical modelling in Simulink and describe mapping to the actual C code architecture expressed by distinct abstraction levels (e.g. layers, modules, functions). Although Simulink is capable of handling modular structures, there is a lack of proper visual representation support, which at the moment can reflect only inter-functional dependencies in terms of caller-to-callee relations, omitting any hierarchical view of abstraction layers. An attempt to extend graphical features of Simulink had several drawbacks and performance issues. As an enhanced solution, external GUI was developed for enabling a "complete" representation of the code architecture. For that purpose, reverse engineering approaches were employed with a help of LLVM compiler infrastructure and poolalloc project. A further analysis of LLVM IR allowed extracting a function call graph, including indirect function calls with a satisfactory precision (which can be possibly improved). For a better performance, the resulting graph was placed in a database, which allowed to dynamically select particular parts and relations of the graph. The developed tool-chain was evaluated on a two production software system called COO7 and GMS. This thesis was done at Scania CV AB in Södertälje, Sweden.

Gli stili APA, Harvard, Vancouver, ISO e altri

Tesi sul tema "Graphe de code"

Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili