To see the other types of publications on this topic, follow the link: Algorithmic structures.
Dissertations / Theses on the topic 'Algorithmic structures'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Algorithmic structures.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Li, Quan Ph D. Massachusetts Institute of Technology. "Algorithms and algorithmic obstacles for probabilistic combinatorial structures." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/115765.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 209-214).<br>We study efficient average-case (approximation) algorithms for combinatorial optimization problems, as well as explore the algorithmic obstacles for a variety of discrete optimization problems arising in the theory of random graphs, statistics and machine learning. In particular, we consider the average-case optimization for three NP-hard combinatorial optimization problems: Large Submatrix Selection, Maximum Cut (Max-Cut) of a graph and Matrix Completion. The Large Submatrix Selection problem is to find a k x k submatrix of an n x n matrix with i.i.d. standard Gaussian entries, which has the largest average entry. It was shown in [13] using non-constructive methods that the largest average value of a k x k submatrix is 2(1 + o(1) [square root] log n/k with high probability (w.h.p.) when k = O(log n/ log log n). We show that a natural greedy algorithm called Largest Average Submatrix LAS produces a submatrix with average value (1+ o(1)) [square root] 2 log n/k w.h.p. when k is constant and n grows, namely approximately [square root] 2 smaller. Then by drawing an analogy with the problem of finding cliques in random graphs, we propose a simple greedy algorithm which produces a k x k matrix with asymptotically the same average value (1+o(1) [square root] 2log n/k w.h.p., for k = o(log n). Since the maximum clique problem is a special case of the largest submatrix problem and the greedy algorithm is the best known algorithm for finding cliques in random graphs, it is tempting to believe that beating the factor [square root] 2 performance gap suffered by both algorithms might be very challenging. Surprisingly, we show the existence of a very simple algorithm which produces a k x k matrix with average value (1 + o[subscript]k(1) + o(1))(4/3) [square root] 2log n/k for k = o((log n)¹.⁵), that is, with asymptotic factor 4/3 when k grows. To get an insight into the algorithmic hardness of this problem, and motivated by methods originating in the theory of spin glasses, we conduct the so-called expected overlap analysis of matrices with average value asymptotically (1 + o(1))[alpha][square root] 2 log n/k for a fixed value [alpha] [epsilon] [1, fixed value a E [1, [square root]2]. The overlap corresponds to the number of common rows and common columns for pairs of matrices achieving this value. We discover numerically an intriguing phase transition at [alpha]* [delta]= 5[square root]2/(3[square root]3) ~~ 1.3608.. [epsilon] [4/3, [square root]2]: when [alpha] < [alpha]* the space of overlaps is a continuous subset of [0, 1]², whereas [alpha] = [alpha]* marks the onset of discontinuity, and as a result the model exhibits the Overlap Gap Property (OGP) when [alpha] > [alpha]*, appropriately defined. We conjecture that OGP observed for [alpha] > [alpha]* also marks the onset of the algorithmic hardness - no polynomial time algorithm exists for finding matrices with average value at least (1+o(1)[alpha][square root]2log n/k, when [alpha] > [alpha]* and k is a growing function of n. Finding a maximum cut of a graph is a well-known canonical NP-hard problem. We consider the problem of estimating the size of a maximum cut in a random Erdős-Rényi graph on n nodes and [cn] edges. We establish that the size of the maximum cut normalized by the number of nodes belongs to the interval [c/2 + 0.47523[square root]c,c/2 + 0.55909[square root]c] w.h.p. as n increases, for all sufficiently large c. We observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved multi-dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as c increases and use it to obtain an improved upper bound on the Max-Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value c/2 + 0.47523[square root]c. We also obtain an improved lower bound of 1.36000n on the Max-Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of 1.33773n. Matrix Completion is the problem of reconstructing a rank-k n x n matrix M from a sampling of its entries. We propose a new matrix completion algorithm using a novel sampling scheme based on a union of independent sparse random regular bipartite graphs. We show that under a certain incoherence assumption on M and for the case when both the rank and the condition number of M are bounded, w.h.p. our algorithm recovers an [epsilon]-approximation of M in terms of the Frobenius norm using O(nlog² (1/[epsilon])) samples and in linear time O(nlog² (1/[epsilon])). This provides the best known bounds both on the sample complexity and computational cost for reconstructing (approximately) an unknown low-rank matrix. The novelty of our algorithm is two new steps of thresholding singular values and rescaling singular vectors in the application of the "vanilla" alternating minimization algorithm. The structure of sparse random regular graphs is used heavily for controlling the impact of these regularization steps.<br>by Quan Li.<br>Ph. D.
2
Vialette, Stéphane. "Algorithmic Contributions to Computational Molecular Biology." Habilitation à diriger des recherches, Université Paris-Est, 2010. http://tel.archives-ouvertes.fr/tel-00862069.
Full text
3
King, Stephen. "Higher-level algorithmic structures in the refinement calculus." Thesis, University of Oxford, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.300129.
Full text
4
Hashemolhosseini, Sepehr. "Algorithmic component and system reliability analysis of truss structures." Thesis, Stellenbosch : Stellenbosch University, 2013. http://hdl.handle.net/10019.1/85710.
Full textAbstract:
Thesis (MScEng)-- Stellenbosch University, 2013.<br>ENGLISH ABSTRACT: Most of the parameters involved in the design and analysis of structures are of stochastic nature.
This is, therefore, of paramount importance to be able to perform a fully stochastic analysis of
structures both in component and system level to take into account the uncertainties involved
in structural analysis and design. To the contrary, in practice, the (computerised) analysis of
structures is based on a deterministic analysis which fails to address the randomness of design
and analysis parameters. This means that an investigation on the algorithmic methodologies for
a component and system reliability analysis can help pave the way towards the implementation
of fully stochastic analysis of structures in a computer environment. This study is focused
on algorithm development for component and system reliability analysis based on the various
proposed methodologies. Truss structures were selected for this purpose due to their simplicity
as well as their wide use in the industry. Nevertheless, the algorithms developed in this study
can be used for other types of structures such as moment-resisting frames with some simple
modi cations.
For a component level reliability analysis of structures different methods such as First Order
Reliability Methods (FORM) and simulation methods are proposed. However, implementation
of these methods for the statistically indeterminate structures is complex due to the implicit
relation between the response of the structural system and the load effect. As a result, the
algorithm developed for the purpose of component reliability analysis should be based on the
concepts of Stochastic Finite Element Methods (SFEM) where a proper link between the finite
element analysis of the structure and the reliability analysis methodology is ensured. In this
study various algorithms are developed based on the FORM method, Monte Carlo simulation,
and the Response Surface Method (RSM). Using the FORM method, two methodologies are
considered: one is based on the development of a finite element code where required alterations
are made to the FEM code and the other is based on the usage of a commercial FEM package.
Different simulation methods are also implemented: Direct Monte Carlo Simulation (DMCS),
Latin Hypercube Sampling Monte Carlo (LHCSMC), and Updated Latin Hypercube Sampling
Monte Carlo (ULHCSMC). Moreover, RSM is used together with simulation methods. Throughout the thesis, the effciency of these methods was investigated. A Fully Stochastic
Finite Element Method (FSFEM) with alterations to the finite element code seems the fastest
approach since the linking between the FEM package and reliability analysis is avoided. Simulation methods can also be effectively used for the reliability evaluation where ULHCSMC seemed
to be the most efficient method followed by LHCSMC and DMCS. The response surface method
is the least straight forward method for an algorithmic component reliability analysis; however,
it is useful for the system reliability evaluation.
For a system level reliability analysis two methods were considered: the ß-unzipping method
and the branch and bound method. The ß-unzipping method is based on a level-wise system
reliability evaluation where the structure is modelled at different damaged levels according to its
degree of redundancy. In each level, the so-called unzipping intervals are defined for the identification of the critical elements. The branch and bound method is based on the identification
of different failure paths of the structure by the expansion of the structural failure tree. The
evaluation of the damaged states for both of the methods is the same. Furthermore, both of
the methods lead to the development of a parallel-series model for the structural system. The
only difference between the two methods is in the search approach used for the failure sequence
identification.
It was shown that the ß-unzipping method provides a better algorithmic approach for evaluating
the system reliability compared to the branch and bound method. Nevertheless, the branch and
bound method is a more robust method in the identification of structural failure sequences. One
possible way to increase the efficiency of the ß-unzipping method is to define bigger unzipping
intervals in each level which can be possible through a computerised analysis. For such an
analysis four major modules are required: a general intact structure module, a damaged structure
module, a reliability analysis module, and a system reliability module.
In this thesis different computer programs were developed for both system and component
reliability analysis based on the developed algorithms. The computer programs are presented
in the appendices of the thesis.<br>AFRIKAANSE OPSOMMING: Meeste van die veranderlikes betrokke by die ontwerp en analise van strukture is stogasties in
hul aard. Om die onsekerhede betrokke in ontwerp en analise in ag te neem is dit dus van
groot belang om 'n ten volle stogastiese analise te kan uitvoer op beide komponent asook stelsel
vlak. In teenstelling hiermee is die gerekenariseerde analise van strukture in praktyk gebaseer
op deterministiese analise wat nie suksesvol is om die stogastiese aard van ontwerp veranderlikes
in ag te neem nie. Dit beteken dat die ondersoek na die algoritmiese metodiek vir komponent en
stelsel betroubaarheid analise kan help om die weg te baan na die implementering van ten volle
rekenaarmatige stogastiese analise van strukture. Di e studie se fokus is op die ontwikkeling van
algoritmes vir komponent en stelsel betroubaarheid analise soos gegrond op verskeie voorgestelde
metodes. Vakwerk strukture is gekies vir die doeleinde as gevolg van hulle eenvoud asook hulle
wydverspreide gebruik in industrie. Die algoritmes wat in die studie ontwikkel is kan nietemin
ook vir ander tipes strukture soos moment-vaste raamwerke gebruik word, gegewe eenvoudige
aanpassings.
Vir 'n komponent vlak betroubaarheid analise van strukture word verskeie metodes soos die
"First Order Reliability Methods" (FORM) en simulasie metodes voorgestel. Die implementering
van die metodes vir staties onbepaalbare strukture is ingewikkeld as gevolg van die implisiete
verband tussen die gedrag van die struktuur stelsel en die las effek. As 'n gevolg, moet die algoritme
wat ontwikkel word vir die doel van komponent betroubaarheid analise gebaseer word
op die konsepte van stogastiese eindige element metodes ("SFEM") waar 'n duidelike verband
tussen die eindige element analise van die struktuur en die betroubaarheid analise verseker is. In
hierdie studie word verskeie algoritmes ontwikkel wat gebaseer is op die FORM metode, Monte
Carlo simulasie, en die sogenaamde "Response Surface Method" (RSM). Vir die gebruik van die
FORM metode word twee verdere metodologieë ondersoek: een gebaseer op die ontwikkeling
van 'n eindige element kode waar nodige verandering aan die eindige element kode self gemaak
word en die ander waar 'n kommersiële eindige element pakket gebruik word. Verskillende simulasie
metodes word ook geïmplimenteer naamlik Direkte Monte Carlo Simulasie (DMCS),
"Latin Hypercube Sampling Monte Carlo" (LHCSMC) en sogenaamde "Updated Latin Hypercube
Sampling Monte Carlo" (ULHCSMC). Verder, word RSM tesame met die simulasie
metodes gebruik. In die tesis word die doeltreffendheid van die bostaande metodes deurgaans ondersoek. 'n Ten volle stogastiese eindige element metode ("FSFEM") met verandering aan die eindige element
kode blyk die vinnigste benadering te wees omdat die koppeling tussen die eindige element
metode pakket en die betroubaarheid analise verhoed word. Simulasie metodes kan ook effektief
aangewend word vir die betroubaarheid evaluasie waar ULHCSMC as die mees doeltre end
voorgekom het, gevolg deur LHCSMC en DMCS. The RSM metode is die mees komplekse
metode vir algoritmiese komponent betroubaarheid analise. Die metode is egter nuttig vir
sisteem betroubaarheid analise.
Vir sisteem-vlak betroubaarheid analise is twee metodes oorweeg naamlik die "ß-unzipping"
metode and die "branch-and-bound" metode. Die "ß-unzipping" metode is gebaseer op 'n
sisteem-vlak betroubaarheid ontleding waar die struktuur op verskillende skade vlakke gemodelleer
word soos toepaslik vir die hoeveelheid addisionele las paaie. In elke vlak word die
sogenaamde "unzipping" intervalle gedefinieer vir die identifikasie van die kritiese elemente. Die
"branch-and-bound" metode is gebaseer op die identifikasie van verskillende faling roetes van
die struktuur deur uitbreiding van die falingsboom. The ondersoek van die skade toestande vir
beide metodes is dieselfde. Verder kan beide metodes lei tot die ontwikkeling van 'n parallelserie
model van die strukturele stelsel. Die enigste verskil tussen die twee metodes is in die
soek-benadering vir die uitkenning van falingsmodus volgorde.
Dit word getoon dat die "ß-unzipping" metode 'n beter algoritmiese benadering is vir die ontleding
van sisteem betroubaarheid vergeleke met die "branch-and-bound" metode. Die "branch-and-
bound" metode word nietemin as 'n meer robuuste metode vir die uitkenning van die falings
volgorde beskou. Een moontlike manier om die doeltre endheid van die "ß-unzipping" metode
te verhoog is om groter "unzipping" intervalle te gebruik, wat moontlik is vir rekenaarmatige
analise. Vir so 'n analise word vier hoof modules benodig naamlik 'n algemene heel-struktuur
module, 'n beskadigde-struktuur module, 'n betroubaarheid analise module en 'n sisteem betroubaarheid analise module.
In die tesis word verskillende rekenaar programme ontwikkel vir beide sisteem en komponent
betroubaarheid analise. Die rekenaar programme word in die aanhangsels van die tesis
aangebied.
5
Breuils, Stéphane. "Structures algorithmiques pour les opérateurs d'algèbre géométrique et application aux surfaces quadriques." Thesis, Paris Est, 2018. http://www.theses.fr/2018PESC1142/document.
Full textAbstract:
L'algèbre géométrique est un outil permettant de représenter et manipuler les objets géométriques de manière générique, efficace et intuitive. A titre d'exemple, l'Algèbre Géométrique Conforme (CGA), permet de représenter des cercles, des sphères, des plans et des droites comme des objets algébriques. Les intersections entre ces objets sont incluses dans la même algèbre. Il est possible d'exprimer et de traiter des objets géométriques plus complexes comme des coniques, des surfaces quadriques en utilisant une extension de CGA. Cependant due à leur représentation requérant un espace vectoriel de haute dimension, les implantations de l'algèbre géométrique, actuellement disponible, n'autorisent pas une utilisation efficace de ces objets. Dans ce manuscrit, nous présentons tout d'abord une implantation de l'algèbre géométrique dédiée aux espaces vectoriels aussi bien basses que hautes dimensions. L'approche suivie est basée sur une solution hybride de code pré-calculé en vue d'une exécution rapide pour des espaces vectoriels de basses dimensions, ce qui est similaire aux approches de l'état de l'art. Pour des espaces vectoriels de haute dimension, nous proposons des méthodes de calculs ne nécessitant que peu de mémoire. Pour ces espaces, nous introduisons un formalisme récursif et prouvons que les algorithmes associés sont efficaces en termes de complexité de calcul et complexité de mémoire. Par ailleurs, des règles sont définies pour sélectionner la méthode la plus appropriée. Ces règles sont basées sur la dimension de l'espace vectoriel considéré. Nous montrons que l'implantation obtenue est bien adaptée pour les espaces vectoriels de hautes dimensions (espace vectoriel de dimension 15) et ceux de basses dimensions. La dernière partie est dédiée à une représentation efficace des surfaces quadriques en utilisant l'algèbre géométrique. Nous étudions un nouveau modèle en algèbre géométrique de l'espace vectoriel $mathbb{R}^{9,6}$ pour manipuler les surfaces quadriques. Dans ce modèle, une surface quadrique est construite par l'intermédiaire de neuf points. Nous montrerons que ce modèle permet non seulement de représenter de manière intuitive des surfaces quadriques mais aussi de construire des objets en utilisant les définitions de CGA. Nous présentons le calcul de l'intersection de surfaces quadriques, du vecteur normal, du plan tangent à une surface en un point de cette surface. Enfin, un modèle complet de traitement des surfaces quadriques est détaillé<br>Geometric Algebra is considered as a very intuitive tool to deal with geometric problems and it appears to be increasingly efficient and useful to deal with computer graphics problems. The Conformal Geometric Algebra includes circles, spheres, planes and lines as algebraic objects, and intersections between these objects are also algebraic objects. More complex objects such as conics, quadric surfaces can also be expressed and be manipulated using an extension of the conformal Geometric Algebra. However due to the high dimension of their representations in Geometric Algebra, implementations of Geometric Algebra that are currently available do not allow efficient realizations of these objects. In this thesis, we first present a Geometric Algebra implementation dedicated for both low and high dimensions. The proposed method is a hybrid solution that includes precomputed code with fast execution for low dimensional vector space, which is somehow equivalent to the state of the art method. For high dimensional vector spaces, we propose runtime computations with low memory requirement. For these high dimensional vector spaces, we introduce new recursive scheme and we prove that associated algorithms are efficient both in terms of computationnal and memory complexity. Furthermore, some rules are defined to select the most appropriate choice, according to the dimension of the algebra and the type of multivectors involved in the product. We will show that the resulting implementation is well suited for high dimensional spaces (e.g. algebra of dimension 15) as well as for lower dimensional spaces. The next part presents an efficient representation of quadric surfaces using Geometric Algebra. We define a novel Geometric Algebra framework, the Geometric Algebra of $mathbb{R}^{9,6}$ to deal with quadric surfaces where an arbitrary quadric surface is constructed by merely the outer product of nine points. We show that the proposed framework enables us not only to intuitively represent quadric surfaces but also to construct objects using Conformal Geometric Algebra. In the proposed framework, the computation of the intersection of quadric surfaces, the normal vector, and the tangent plane of a quadric surface are provided. Finally, a computational framework of the quadric surfaces will be presented with the main operations required in computer graphics
6
Raymond, Jean-Florent. "Structural and algorithmic aspects of partial orderings of graphs." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT289.
Full textAbstract:
Le thème central à cette thèse est l'étude des propriétés des classes de graphes définies par sous-structures interdites et leurs applications.La première direction que nous suivons a trait aux beaux ordres. À l'aide de théorèmes de décomposition dans les classes de graphes interdisant une sous-structure, nous identifions celles qui sont bellement-ordonnées. Les ordres et sous-structures considérés sont ceux associés aux notions de contraction et mineur induit. Ensuite, toujours en considérant des classes de graphes définies par sous-structures interdites, nous obtenons des bornes sur des invariants comme le degré, la largeur arborescente, la tree-cut width et un nouvel invariant généralisant la maille.La troisième direction est l'étude des relations entre les invariants combinatoires liés aux problèmes de packing et de couverture de graphes. Dans cette direction, nous établissons de nouvelles relations entre ces invariants pour certaines classes de graphes. Nous présentons également des applications algorithmiques de ces résultats<br>The central theme of this thesis is the study of the properties of the classes of graphs defined by forbidden substructures and their applications.The first direction that we follow concerns well-quasi-orders. Using decomposition theorems on graph classes forbidding one substructure, we identify those that are well-quasi-ordered. The orders and substructures that we consider are those related to the notions of contraction and induced minor.Then, still considering classes of graphs defined by forbidden substructures, we obtain bounds on invariants such as degree, treewidth, tree-cut width, and a new invariant generalizing the girth.The third direction is the study of the links between the combinatorial invariants related to problems of packing and covering of graphs. In this direction, we establish new connections between these invariants for some classes of graphs. We also present algorithmic applications of the results
7
Bessy, Stéphane. "Some problems in graph theory and graphs algorithmic theory." Habilitation à diriger des recherches, Université Montpellier II - Sciences et Techniques du Languedoc, 2012. http://tel.archives-ouvertes.fr/tel-00806716.
Full textAbstract:
This document is a long abstract of my research work, concerning graph theory and algorithms on graphs. It summarizes some results, gives ideas of the proof for some of them and presents the context of the different topics together with some interesting open questions connected to them The first part precises the notations used in the rest of the paper; the second part deals with some problems on cycles in digraphs; the third part is an overview of two graph coloring problems and one problem on structures in colored graphs; finally the fourth part focus on some results in algorithmic graph theory, mainly in parametrized complexity.
8
Mohan, Rathish. "Algorithmic Optimization of Sensor Placement on Civil Structures for Fault Detection and Isolation." University of Cincinnati / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1353156107.
Full text
9
Ballage, Marion. "Algorithmes de résolution rapide de problèmes mécaniques sur GPU." Thesis, Toulouse 3, 2017. http://www.theses.fr/2017TOU30122/document.
Full textAbstract:
Dans le contexte de l'analyse numérique en calcul de structures, la génération de maillages conformes sur des modèles à géométrie complexe conduit à des tailles de modèles importantes, et amène à imaginer de nouvelles approches éléments finis. Le temps de génération d'un maillage est directement lié à la complexité de la géométrie, augmentant ainsi considérablement le temps de calcul global. Les processeurs graphiques (GPU) offrent de nouvelles opportunités pour le calcul en temps réel. L'architecture grille des GPU a été utilisée afin d'implémenter une méthode éléments finis sur maillage cartésien. Ce maillage est particulièrement adapté à la parallélisation souhaitée par les processeurs graphiques et permet un gain de temps important par rapport à un maillage conforme à la géométrie. Les formulations de la méthode des éléments finis ainsi que de la méthode des éléments finis étendue ont été reprises afin d'être adaptées à notre méthode. La méthode des éléments finis étendus permet de prendre en compte la géométrie et les interfaces à travers un choix adéquat de fonctions d'enrichissement. Cette méthode discrétise par exemple sans mailler explicitement les fissures, et évite surtout de remailler au cours de leur propagation. Des adaptations de cette méthode sont faites afin de ne pas avoir besoin d'un maillage conforme à la géométrie. La géométrie est définie implicitement par une fonction surfaces de niveau, ce qui permet une bonne approximation de la géométrie et des conditions aux limites sans pour autant s'appuyer sur un maillage conforme. La géométrie est représentée par une fonction surfaces de niveau que nous appelons la densité. La densité est supérieure à 0.5 à l'intérieur du domaine de calcul et inférieure à 0.5 à l'extérieur. Cette fonction densité, définie par ses valeurs aux points noeuds du maillage, est interpolée à l'intérieur de chaque élément. Une méthode d'intégration adaptée à cette représentation géométrique est proposée. En effet, certains éléments sont coupés par la fonction surfaces de niveau et l'intégration de la matrice de raideur ne doit se faire que sur la partie pleine de l'élément. La méthode de quadrature de Gauss qui permet d'intégrer des polynômes de manière exacte n'est plus adaptée. Nous proposons d'utiliser une méthode de quadrature avec des points d'intégration répartis sur une grille régulière et dense. L'intégration peut s'avérer coûteuse en temps de calcul, c'est pour cette raison que nous proposons une technique d'apprentissage donnant la matrice élémentaire de rigidité en fonction des valeurs de la fonction surfaces de niveau aux sommets de l'élément considéré. Cette méthode d'apprentissage permet de grandes améliorations du temps de calcul des matrices élémentaires. Les résultats obtenus après analyse par la méthode des éléments finis standard ou par la méthode des éléments finis sur maillage cartésien ont une taille qui peut croître énormément selon la complexité des modèles, ainsi que la précision des schémas de résolution. Dans un contexte de programmation sur processeurs graphiques, où la mémoire est limitée, il est intéressant d'arriver à compresser ces données. Nous nous sommes intéressés à la compression des modèles et des résultats éléments finis par la transformée en ondelettes. La compression mise en place aidera aussi pour les problèmes de stockage en réduisant la taille des fichiers générés, et pour la visualisation des données<br>Generating a conformal mesh on complex geometries leads to important model size of structural finite element simulations. The meshing time is directly linked to the geometry complexity and can contribute significantly to the total turnaround time. Graphics processing units (GPUs) are highly parallel programmable processors, delivering real performance gains on computationally complex, large problems. GPUs are used to implement a new finite element method on a Cartesian mesh. A Cartesian mesh is well adapted to the parallelism needed by GPUs and reduces the meshing time to almost zero. The novel method relies on the finite element method and the extended finite element formulation. The extended finite element method was introduced in the field of fracture mechanics. It consists in enriching the basis functions to take care of the geometry and the interface. This method doesn't need a conformal mesh to represent cracks and avoids refining during their propagation. Our method is based on the extended finite element method, with a geometry implicitly defined, wich allows for a good approximation of the geometry and boundary conditions without a conformal mesh.To represent the model on a Cartesian grid, we use a level set representing a density. This density is greater than 0.5 inside the domain and less than 0.5 outside. It takes 0.5 on the boundary. A new integration technique is proposed, adapted to the geometrical representation. For the element cut by the levet set, only the part full of material has to be integrated. The Gauss quadrature is no longer adapted. We introduce a quadrature method with integration points on a cartesian dense grid.In order to reduce the computational effort, a learning approach is then considered to form the elementary stiffness matrices as function of density values on the vertices of the elements. This learning method reduces the stiffness matrices time computation. Results obtained after analysis by finite element method or the novel finite element method can have important storage size, dependant of the model complexity and the resolution scheme exactitude. Due to the limited direct memory of graphics processing units, the data results are compressed. We compress the model and the element finite results with a wavelet transform. The compression will help for storage issue and also for data visualization
10
Bricage, Marie. "Modélisation et Algorithmique de graphes pour la construction de structures moléculaires." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLV031/document.
Full textAbstract:
Dans cette thèse, nous présentons une approche algorithmique permettant la génération de guides de construction de cages moléculaires organiques. Il s'agit d'architectures semi-moléculaires possédant un espace interne défini capable de piéger une molécule cible appelée substrat. De nombreuses œuvres proposent de générer des cages organiques moléculaires obtenues à partir de structures symétriques, qui ont une bonne complexité, mais elles ne sont pas spécifiques car elles ne prennent pas en compte des cibles précises. L'approche proposée permet de générer des guides de construction de cages moléculaires organiques spécifiques à un substrat donné. Afin de garantir la spécificité de la cage moléculaire pour le substrat cible, une structure intermédiaire, qui est une expansion de l'enveloppe du substrat cible, est utilisée. Cette structure définie la forme de l'espace dans lequel est piégé le substrat. Des petits ensembles d'atomes, appelés motifs moléculaires liants, sont ensuite intégrés à cette structure intermédiaire. Ces motifs moléculaires sont les ensembles d'atomes nécessaires aux cages moléculaires pour leur permettre d’interagir avec le substrat afin de le capturer<br>In this thesis, we present an algorithmic approach allowing the generation of construction guides of organic molecular cages. These semi-molecular architectures have a defined internal space capable of trapping a target molecule called substrate. Many works propose to generate molecular organic cages obtained from symmetrical structures, which have a good complexity, but they are not specific because they do not take into account precise targets. The proposed approach makes it possible to generate guides for the construction of organic molecular cages specific to a given substrate. In order to ensure the specificity of the molecular cage for the target substrate, an intermediate structure, which is an expansion of the envelope of the target substrate, is used. This structure defines the shape of the space in which the substrate is trapped. Small sets of atoms, called molecular binding patterns, are then integrated into this intermediate structure. These molecular patterns are the sets of atoms needed by molecular cages to allow them to interact with the substrate to capture it
11
Gaillard, Anne-Laure. "Identification de motifs au sein des structures biologiques arborescentes." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2011. http://tel.archives-ouvertes.fr/tel-00652227.
Full textAbstract:
Avec l'explosion de la quantité de données biologiques disponible, développer de nouvelles méthodes de traitements efficaces est une problématique majeure en bioinformatique. De nombreuses structures biologiques sont modélisées par des structures arborescentes telles que les structures secondaires d'ARN et l'architecture des plantes. Ces structures contiennent des motifs répétés au sein même de leur structure mais également d'une structure à l'autre. Nous proposons d'exploiter cette propriété fondamentale afin d'améliorer le stockage et le traitement de tels objets. En nous inspirant du principe de filtres sur les séquences, nous définissons dans cette thèse une méthode de filtrage sur les arborescences ordonnées, permettant de rechercher efficacement dans une base de données, un ensemble d'arborescences ordonnées proches d'une arborescence requête. La méthode se base sur un découpage de l'arborescence en graines et sur une recherche de graines communes entre les structures. Nous définissons et résolvons le problème de chaînage maximum sur des arborescences. Nous proposons dans le cas des structures secondaires d'ARN une définition de graines (l−d) centrées. Dans un second temps, en nous basant sur des techniques d'instanciations utilisées, par exemple, en infographie et sur la connaissance des propriétés de redondances au sein des structures biologiques, nous présentons une méthode de compression permettant de réduire l'espace mémoire nécessaire pour le stockage d'arborescences non-ordonnées. Après une détermination des redondances, nous utilisons une structure de données plus compacte pour représenter notamment l'architecture de la plante, celle-ci pouvant contenir des informations topologiques mais également géométriques.
12
Pimenta, Tales Cleber. "Optimal design of VLSI structures with built-in self test based on reduced pseudo-exhaustive testing." Ohio : Ohio University, 1992. http://www.ohiolink.edu/etd/view.cgi?ohiou1173755841.
Full text
13
Kropf, Carsten. "Efficient Reorganisation of Hybrid Index Structures Supporting Multimedia Search Criteria." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-216425.
Full textAbstract:
This thesis describes the development and setup of hybrid index structures. They are access methods for retrieval techniques in hybrid data spaces which are formed by one or more relational or normalised columns in conjunction with one non-relational or non-normalised column. Examples for these hybrid data spaces are, among others, textual data combined with geographical ones or data from enterprise content management systems. However, all non-relational data types may be stored as well as image feature vectors or comparable types.
Hybrid index structures are known to function efficiently regarding retrieval operations. Unfortunately, little information is available about reorganisation operations which insert or update the row tuples. The fundamental research is mainly executed in simulation based environments. This work is written ensuing from a previous thesis that implements hybrid access structures in realistic database surroundings. During this implementation it has become obvious that retrieval works efficiently. Yet, the restructuring approaches require too much effort to be set up, e.g., in web search engine environments where several thousands of documents are inserted or modified every day. These search engines rely on relational database systems as storage backends. Hence, the setup of these access methods for hybrid data spaces is required in real world database management systems.
This thesis tries to apply a systematic approach for the optimisation of the rearrangement algorithms inside realistic scenarios. Thus, a measurement and evaluation scheme is created which is repeatedly deployed to an evolving state and a model of hybrid index structures in order to optimise the regrouping algorithms to make a setup of hybrid index structures in real world information systems possible. Thus, a set of input corpora is selected which is applied to the test suite as well as an evaluation scheme.
To sum up, it can be said that this thesis describes input sets, a test suite including an evaluation scheme as well as optimisation iterations on reorganisation algorithms reflecting a theoretical model framework to provide efficient reorganisations of hybrid index structures supporting multimedia search criteria.
14
Keyhani, Ali. "A Study On The Predictive Optimal Active Control Of Civil Engineering Structures." Thesis, Indian Institute of Science, 2000. http://hdl.handle.net/2005/223.
Full textAbstract:
Uncertainty involved in the safe and comfort design of the structures is a major concern of civil engineers. Traditionally, the uncertainty has been overcome by utilizing various and relatively large safety factors for loads and structural properties. As a result in conventional design of for example tall buildings, the designed structural elements have unnecessary dimensions that sometimes are more than double of the ones needed to resist normal loads. On the other hand the requirements for strength and safety and comfort can be conflicting. Consequently, an alternative approach for design of the structures may be of great interest in design of safe and comfort structures that also offers economical advantages. Recently, there has been growing interest among the researchers in the concept of structural control as an alternative or complementary approach to the existing approaches of structural design. A few buildings have been designed and built based on this concept. The concept is to utilize a device for applying a force (known as control force) to encounter the effects of disturbing forces like earthquake force. However, the concept still has not found its rightful place among the practical engineers and more research is needed on the subject. One of the main problems in structural control is to find a proper algorithm for determining the optimum control force that should be applied to the structure.
The investigation reported in this thesis is concerned with the application of active control to civil engineering structures. From the literature on control theory. (Particularly literature on the control of civil engineering structures) problems faced in application of control theory were identified and classified into two categories: 1) problems common to control of all dynamical systems, and 2) problems which are specially important in control of civil engineering structures. It was concluded that while many control algorithms are suitable for control of dynamical systems, considering the special problems in controlling civil structures and considering the unique future of structural control, many otherwise useful control algorithms face practical problems in application to civil structures. Consequently a set of criteria were set for judging the suitability of the control algorithms for use in control of civil engineering structures. Various types of existing control algorithms were investigated and finally it was concluded that predictive optimal control algorithms possess good characteristics for purpose of control of civil engineering structures. Among predictive control algorithms, those that use ARMA stochastic models for predicting the ground acceleration are better fitted to the structural control environment because all the past measured excitation is used to estimate the trends of the excitation for making qualified guesses about its coming values. However, existing ARMA based predictive algorithms are devised specially for earthquake and require on-line measurement of the external disturbing load which is not possible for dynamic loads like wind or blast. So, the algorithms are not suitable for tall buildings that experience both earthquake and wind loads during their life. Consequently, it was decided to establish a new closed loop predictive optimal control based on ARMA models as the first phase of the study.
In this phase it was initially established that ARMA models are capable of predicting response of a linear SDOF system to the earthquake excitation a few steps ahead. The results of the predictions encouraged a search for finding a new closed loop optimal predictive control algorithm for linear SDOF structures based on prediction of the response by ARMA models. The second part of phase I, was devoted to developing and testing the proposed algorithm The new developed algorithm is different from other ARMA based optimal controls since it uses ARMA models for prediction of the structure response while existing algorithms predict the input excitation. Modeling the structure response as an AR or ARMA stochastic process is an effective mean for prediction of the structure response while avoiding measurement of the input excitation. ARMA models used in the algorithm enables it to avoid or reduce the time delay effect by predicting the structure response a few steps ahead. Being a closed loop control, the algorithm is suitable for all structural control conditions and can be used in a single control mechanism for vibration control of tall buildings against wind, earthquake or other random dynamic loads. Consequently the standby time is less than that for existing ARMA based algorithms devised only for earthquakes. This makes the control mechanism more reliable.
The proposed algorithm utilizes and combines two different mathematical models. First model is an ARMA model representing the environment and the structure as a single system subjected to the unknown random excitation and the second model is a linear SDOF system which represents the structure subjected to a known past history of the applied control force only. The principle of superposition is then used to combine the results of these two models to predict the total response of the structure as a function of the control force. By using the predicted responses, the minimization of the performance index with respect to the control force is carried out for finding the optimal control force.
As phase II, the proposed predictive control algorithm was extended to structures that are more complicated than linear SDOF structures. Initially, the algorithm was extended to linear MDOF structures. Although, the development of the algorithm for MDOF structures was relatively straightforward, during testing of the algorithm, it was found that prediction of the response by ARMA models can not be done as was done for SDOF case. In the SDOF case each of the two components of the state vector (i.e. displacement and velocity) was treated separately as an ARMA stochastic process. However, applying the same approach to each component of the state vector of a MDOF structure did not yield satisfactory results in prediction of the response. Considering the whole state vector as a multi-variable ARMA stochastic vector process yielded the desired results in predicting the response a few steps ahead. In the second part of this phase, the algorithm was extended to non-linear MDOF structures. Since the algorithm had been developed based on the principle of superposition, it was not possible to directly extend the algorithm to non-linear systems. Instead, some generalized response was defined. Then credibility of the ARMA models in predicting the generalized response was verified. Based on this credibility, the algorithm was extended for non-linear MDOF structures. Also in phase II, the stability of a controlled MDOF structure was proved. Both internal and external stability of the system were described and verified.
In phase III, some problems of special interest, i.e. soil-structure interaction and control time delay, were investigated and compensated for in the framework of the developed predictive optimal control. In first part of phase III soil-structure interaction was studied. The half-space solution of the SSI effect leads to a frequency dependent representation of the structure-footing system, which is not fit for control purpose. Consequently an equivalent frequency independent system was proposed and defined as a system whose frequency response is equal to the original structure -footing system in the mean squares sense. This equivalent frequency independent system then was used in the control algorithm. In the second part of this phase, an analytical approach was used to tackle the time delay phenomenon in the context of the predictive algorithm described in previous chapters. A generalized performance index was defined considering time delay. Minimization of the generalized performance index resulted into a modified version of the algorithm in which time delay is compensated explicitly. Unlike the time delay compensation technique used in the previous phases of this investigation, which restricts time delay to be an integer multiplier of the sampling period, the modified algorithm allows time delay to be any non-negative number. However, the two approaches produce the same results if time delay is an integer multiplier of the sampling period. For evaluating the proposed algorithm and comparing it with other algorithms, several numerical simulations were carried during the research by using MATLAB and its toolboxes. A few interesting results of these simulations are enumerated below:
ARM A models are able to predict the response of both linear and non-linear structures to
random inputs such as earthquakes.
The proposed predictive optimal control based on ARMA models has produced better
results in the context of reducing velocity, displacement, total energy and operational cost
compared to classic optimal control.
Proposed active control algorithm is very effective in increasing safety and comfort. Its
performance is not affected much by errors in the estimation of system parameters (e.g.
damping).
The effect of soil-structure interaction on the response to control force is considerable.
Ignoring SSI will cause a significant change in the magnitude of the frequency response
and a shift in the frequencies of the maximum response (resonant frequencies).
Compensating the time delay effect by the modified version of the proposed algorithm
will improve the performance of the control system in achieving the control goal and
reduction of the structural response.
15
Tchvagha, Zeine Ahmed. "Contribution à l’optimisation multi-objectifs sous contraintes : applications à la mécanique des structures." Thesis, Normandie, 2018. http://www.theses.fr/2018NORMIR13/document.
Full textAbstract:
L’objectif de cette thèse est le développement de méthodes d’optimisation multi-objectif pour la résolution de problèmes de conception des structures mécaniques. En effet, la plupart des problèmes réels dans le domaine de la mécanique des structures ont plusieurs objectifs qui sont souvent antagonistes. Il s’agit, par exemple, de concevoir des structures en optimisant leurs poids, leurs tailles, et leurs coûts de production. Le but des méthodes d’optimisation multi-objectif est la recherche des solutions de compromis entre les objectifs étant donné l’impossibilité de satisfaire tout simultanément. Les métaheuristiques sont des méthodes d’optimisation capables de résoudre les problèmes d’optimisation multi-objective en un temps de calcul raisonnable sans garantie de l’optimalité de (s) solution (s). Au cours des dernières années, ces algorithmes ont été appliqués avec succès pour résoudre le problème des mécaniques des structures. Dans cette thèse deux métaheuristiques ont été développées pour la résolution des problèmes d’optimisation multi-objectif en général et de conception de structures mécaniques en particulier. Le premier algorithme baptisé MOBSA utilise les opérateurs de croisement et de mutation de l’algorithme BSA. Le deuxième algorithme nommé NNIA+X est une hybridation d’un algorithme immunitaire et de trois croisements inspirés de l’opérateur de croisement original de l’algorithme BSA. Pour évaluer l’efficacité et l’efficience de ces deux algorithmes, des tests sur quelques problèmes dans littérature ont été réalisés avec une comparaison avec des algorithmes bien connus dans le domaine de l’optimisation multi-objectif. Les résultats de comparaison en utilisant des métriques très utilisées dans la littérature ont démontré que ces deux algorithmes peuvent concurrencer leurs prédécesseurs<br>The objective of this thesis is the development of multi-objective optimization methods for solving mechanical design problems. Indeed, most of the real problems in the field of mechanical structures have several objectives that are often antagonistic. For example, it is about designing structures by optimizing their weight, their size, and their production costs. The goal of multi-objective optimization methods is the search for compromise solutions between objectives given the impossibility to satisfy all simultaneously. Metaheuristics are optimization methods capable of solving multi-objective optimization problems in a reasonable calculation time without guaranteeing the optimality of the solution (s). In recent years, these algorithms have been successfully applied to solve the problem of structural mechanics. In this thesis, two metaheuristics have been developed for the resolution of multi-objective optimization problems in general and of mechanical structures design in particular. The first algorithm called MOBSA used the crossover and mutation operators of the BSA algorithm. The second one named NNIA+X is a hybridization of an immune algorithm and three crossover inspired by the original crossover operator of the BSA algorithm. To evaluate the effectiveness and efficiency of these two algorithms, tests on some problems in literature have been made with a comparison with algorithms well known in the field of multi-objective optimization. The comparison results using metrics widely used in the literature have shown that our two algorithms can compete with their predecessors
16
Hachimi, Hanaa. "Hybridations d'algorithmes métaheuristiques en optimisation globale et leurs applications." Phd thesis, INSA de Rouen, 2013. http://tel.archives-ouvertes.fr/tel-00905604.
Full textAbstract:
L'optimisation des structures est un processus essentiel dans la conception des systèmes mécaniques et électroniques. Cette thèse s'intéresse à la résolution des problèmes mono-objectifs et multi-objectifs des structures mécaniques et mécatroniques. En effet, les industriels ne sont pas seulement préoccupés à améliorer les performances mécaniques des pièces qu'ils conçoivent, mais ils cherchent aussi à optimiser leurs poids, leurs tailles, ainsi que leurs coûts de production. Pour résoudre ce type de problème, nous avons fait appel à des métaheuristiques robustes qui nous permettent de minimiser le coût de production de la structure mécanique et de maximiser le cycle de vie de la structure. Alors que des méthodes inappropriées de l'évolution sont plus difficiles à appliquer à des modèles mécaniques complexes en raison de temps calcul exponentiel. Il est connu que les algorithmes génétiques sont très efficaces pour les problèmes NP-difficiles, mais ils sont très lourds et trop gourmands quant au temps de calcul, d'où l'idée d'hybridation de notre algorithme génétique par l'algorithme d'optimisation par essaim de particules (PSO) qui est plus rapide par rapport à l'algorithme génétique (GA). Dans notre expérimentation, nous avons obtenu une amélioration de la fonction objectif et aussi une grande amélioration de la minimisation de temps de calcul. Cependant, notre hybridation est une idée originale, car elle est différente des travaux existants. Concernant l'avantage de l'hybridation, il s'agit généralement de trois méthodes : l'hybridation en série, l'hybridation en parallèle et l'hybridation par insertion. Nous avons opté pour l'hybridation par insertion par ce qu'elle est nouvelle et efficace. En effet, les algorithmes génétiques se composent de trois étapes principales : la sélection, le croisement et la mutation. Dans notre cas, nous remplaçons les opérateurs de mutation par l'optimisation par essaim de particules. Le but de cette hybridation est de réduire le temps de calcul ainsi que l'amélioration la solution optimale.
17
Saleh, Amgad. "Parallel algorithms for integrated structural/control optimization of large structures /." The Ohio State University, 1996. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487940308432707.
Full text
18
Bae, Sung Eun. "Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem." Thesis, University of Canterbury. Computer Science and Software Engineering, 2007. http://hdl.handle.net/10092/1202.
Full textAbstract:
The maximum subarray problem (MSP) involves selection of a segment of consecutive array elements that has the largest possible sum over all other segments in a given array. The efficient algorithms for the MSP and related problems are expected to contribute to various applications in genomic sequence analysis, data mining or in computer vision etc. The MSP is a conceptually simple problem, and several linear time optimal algorithms for 1D version of the problem are already known. For 2D version, the currently known upper bounds are cubic or near-cubic time. For the wider applications, it would be interesting if multiple maximum subarrays are computed instead of just one, which motivates the work in the first half of the thesis. The generalized problem of K-maximum subarray involves finding K segments of the largest sum in sorted order. Two subcategories of the problem can be defined, which are K-overlapping maximum subarray problem (K-OMSP), and K-disjoint maximum subarray problem (K-DMSP). Studies on the K-OMSP have not been undertaken previously, hence the thesis explores various techniques to speed up the computation, and several new algorithms. The first algorithm for the 1D problem is of O(Kn) time, and increasingly efficient algorithms of O(K² + n logK) time, O((n+K) logK) time and O(n+K logmin(K, n)) time are presented. Considerations on extending these results to higher dimensions are made, which contributes to establishing O(n³) time for 2D version of the problem where K is bounded by a certain range. Ruzzo and Tompa studied the problem of all maximal scoring subsequences, whose definition is almost identical to that of the K-DMSP with a few subtle differences. Despite slight differences, their linear time algorithm is readily capable of computing the 1D K-DMSP, but it is not easily extended to higher dimensions. This observation motivates a new algorithm based on the tournament data structure, which is of O(n+K logmin(K, n)) worst-case time. The extended version of the new algorithm is capable of processing a 2D problem in O(n³ + min(K, n) · n² logmin(K, n)) time, that is O(n³) for K ≤ n/log n For the 2D MSP, the cubic time sequential computation is still expensive for practical purposes considering potential applications in computer vision and data mining. The second half of the thesis investigates a speed-up option through parallel computation. Previous parallel algorithms for the 2D MSP have huge demand for hardware resources, or their target parallel computation models are in the realm of pure theoretics. A nice compromise between speed and cost can be realized through utilizing a mesh topology. Two mesh algorithms for the 2D MSP with O(n) running time that require a network of size O(n²) are designed and analyzed, and various techniques are considered to maximize the practicality to their full potential.
19
Bonichon, Nicolas. "Quelques algorithmes entre le monde des graphes et les nuages de points." Habilitation à diriger des recherches, Université Sciences et Technologies - Bordeaux I, 2013. http://tel.archives-ouvertes.fr/tel-00922501.
Full text
20
Lopes, Rodrigo Aranha Pereira. "Computational strategies applied to product design." Master's thesis, Universidade de Lisboa, Faculdade de Arquitetura, 2018. http://hdl.handle.net/10400.5/17993.
Full textAbstract:
Dissertação de Mestrado em Design, com a especialização em Design de Produto apresentada na Faculdade de Arquitetura da Universidade de Lisboa para obtenção do grau de Mestre.<br>Em diferentes ocasiões, Richard Sennett e Vilém
Flusser descreveram que a prática e a teoria, a
técnica e a expressão, a arte e a tecnologia, o
criador e o usuário, antes compartilhavam a mesma
raíz. Ao longo da história, no entanto, estes
conceitos se dividiram com o design posicionado ao
centro.
Esta proposta de pesquisa visa, em primeiro lugar,
contribuir para a diminuição desta herdada separação.
Isso, por meio do uso de estratégias computacionais
aplicadas ao design. O presente estudo aplicará essa
abordagem ao projeto e construção de uma prancha de
surfe.
Um dos objetivos é desenvolver uma plataforma de codesign
que permita aos usuários gerarem suas próprias
pranchas de surf, por meio de modelagem algorítmica /
paramétrica (Grasshopper e ShapeDiver).
Um segundo aspecto considera criticamente os materiais
utilizados na indústria do surf, com o objetivo de
desenvolver produtos que utilizem materiais menos
nocivos ao meio ambiente e com maior capacidade de
controle e alteração em relação às capacidades de
desempenho. Em particular, esta proposta visa
desenvolver um algoritmo para gerar objetos com seus
núcleos internos compostos por estruturas de papel. O
objeto específico a ser gerado neste caso é uma
prancha de surf.<br>ABSTRACT: As pointed out on different occasions by both Richard
Sennett and Villém Flusser, practice and theory,
technique and expression, art and technology, maker
and user, once shared a common ground. Throughout
history, however, they have become divided. Design
stands in between.
This research proposal firstly aims to contribute to
the diminishing of this historical inheritance. This,
by means of providing a workflow for designers with
the use of computational strategies. The present study
will apply this approach to the design and building of
a surfboard.
The goal is to develop a co-designing platform
allowing users to generate their own tailor-made
surfboard by means of algorithmic/parametric modeling
(Grasshopper and Shapediver).
A second aspect critically considers the materials
used in the surf industry, with the objective of
developing products using materials that are less
harmful to the environment and with a greater capacity
of control and alteration with regards to performance
capabilities. In particular, this proposal aims to
develop an algorithm that can be used to generate
objects of paper structures composing their inner
core. The specific object to be generated in this
case, is a surfboard.<br>N/A
21
Pham, Hong Phong. "Studies on Optimal Colorful Structures in Vertex-Colored Graphs." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS528.
Full textAbstract:
Dans cette thèse, nous étudions des problèmes différents de coloration maximale dans les graphes sommet-colorés. Nous nous concentrons sur la recherche des structures avec le nombre maximal possible de couleurs par des algorithmes en temps polynomial, nous donnons aussi la preuve des problèmes NP-difficiles pour des graphes spécifiques. En particulier, nous étudions d’abord le problème de l’appariement coloré maximum. Nous montrons que ce problème peut être résolu efficacement en temps polynomial. En plus, nous considérons également une version spécifique de ce problème, à savoir l’appariement tropical, qui consiste à trouver un appariement contenant toutes les couleurs du graphe original. De même, un algorithme de temps polynomial est également fourni pour le problème de l’appariement tropical avec la cardinalité minimale et le problème de l’appariement tropical maximum avec la cardinalité minimale. Ensuite, nous étudions le problème des chemins colorés maximum. Il existe deux versions pour ce problème: le problème de plus court chemin tropical, c’est-à-dire de trouver un chemin tropical avec le poids total minimum et le problème de plus longue chemin coloré, à savoir, trouver un chemin avec un nombre maximum possible de couleurs. Nous montrons que les deux versions de ce problème sont NP-difficile pour un graphe orienté acyclique, graphes de cactus et graphes d'intervalles où le problème de plus long chemin est facile. De plus, nous fournissons également un algorithme de paramètre fixe pour le premier dans les graphes généraux et plusieurs algorithmes de temps polynomiaux pour le second dans les graphes spécifiques, y compris les graphes des chaîne bipartites, graphes de seuil, arborescences, graphes des blocs et graphes d'intervalles appropriés. Ensuite, nous considérons le problème des cycles colorés maximum. Nous montrons d'abord que le problème est NP-difficile même pour des graphes simples tels que des graphes divisés, des graphes bi-connecteurs et des graphes d'intervalles. Nous fournissons ensuite des algorithmes de temps polynomial pour les classes de graphes de seuil et graphes des chaîne bipartites et graphes d'intervalles appropriés. Plus tard, nous étudions le problème des cliques colorées maximum. Nous montrons tout d’abord que le problème est NP-difficile même pour plusieurs cas où le problème de clique maximum est facile, comme des graphes complémentaires des graphes de permutation bipartite, des graphes complémentaires de graphes convexes bipartites et des graphes de disques unitaires, et aussi pour des graphes sommet-colorées appropriés. Ensuite, nous proposons un algorithme paramétré XP et des algorithmes de temps polynomial pour les classes de graphes complémentaires de graphes en chaîne bipartites, des graphes multipartites complets et des graphes complémentaires de graphes cycles. Enfin, nous nous concentrons sur le problème des stables (ensembles indépendants) colorés maximum. Nous montrons d’abord que le problème est NP-difficile même dans certains cas où le problème de stable maximum est facile, tels que les co-graphes et les graphes des P₅-gratuit. Ensuite, nous fournissons des algorithmes de temps polynomial pour les graphes de grappes, et les arbres<br>In this thesis, we study different maximum colorful problems in vertex-colored graphs. We focus on finding structures with the possible maximum number of colors by efficient polynomial-time algorithms, or prove these problems as NP-hard for specific graphs. In particular, we first study the maximum colorful matching problem. We show that this problem can be efficiently solved in polynomial time. Moreover, we also consider a specific version of this problem, namely tropical matching, that is to find a matching containing all colors of the original graph, if any. Similarly, a polynomial time algorithm is also provided for the problem of tropical matching with the minimum cardinality and the problem of maximal tropical matching with the minimum cardinality. Then, we study the maximum colorful paths problem. There are two versions for this problem: the shortest tropical path problem, i.e., finding a tropical path with the minimum total weight, and the maximum colorful path problem, i.e., finding a path with the maximum number of colors possible. We show that both versions of this problem are NP-hard for directed acyclic graphs, cactus graphs and interval graphs where the longest path problem is easy. Moreover, we also provide a fixed parameter algorithm for the former in general graphs and several polynomial time algorithms for the latter in specific graphs, including bipartite chain graphs, threshold graphs, trees, block graphs, and proper interval graphs. Next we consider the maximum colorful cycles problem. We first show that the problem is NP-hard even for simple graphs such as split graphs, biconnected graphs, interval graphs. Then we provide polynomial-time algorithms for classes of threshold graphs and bipartite chain graphs and proper interval graphs. Later, we study the maximum colorful cliques problem. We first show that the problem is NP-hard even for several cases where the maximum clique problem is easy, such as complement graphs of bipartite permutation graphs, complement graphs of bipartite convex graphs, and unit disk graphs, and also for properly vertex-colored graphs. Next, we propose a XP parameterized algorithm and polynomial-time algorithms for classes of complement graphs of bipartite chain graphs, complete multipartite graphs and complement graphs of cycle graphs. Finally, we focus on the maximum colorful independent set problem. We first prove that the problem is NP-hard even for some cases where the maximum independent set problem is easy, such as cographs and P₅-free graphs. Next, we provide polynomial time algorithms for cluster graphs and trees
22
Bliven, Spencer Edward. "Structure-Preserving Rearrangements| Algorithms for Structural Comparison and Protein Analysis." Thesis, University of California, San Diego, 2015. http://pqdtopen.proquest.com/#viewpdf?dispub=3716489.
Full textAbstract:
<p> Protein structure is fundamental to a deep understanding of how proteins function. Since structure is highly conserved, structural comparison can provide deep information about the evolution and function of protein families. The Protein Data Bank (PDB) continues to grow rapidly, providing copious opportunities for advancing our understanding of proteins through large-scale searches and structural comparisons. In this work I present several novel structural comparison methods for specific applications, as well as apply structure comparison tools systematically to better understand global properties of protein fold space. </p><p> Circular permutation describes a relationship between two proteins where the N-terminal portion of one protein is related to the C-terminal portion of the other. Proteins that are related by a circular permutation generally share the same structure despite the rearrangement of their primary sequence. This non-sequential relationship makes them difficult for many structure alignment tools to detect. Combinatorial Extension for Circular Permutations (CE-CP) was developed to align proteins that may be related by a circular permutation. It is widely available due to its incorporation into the RCSB PDB website. </p><p> Symmetry and structural repeats are common in protein structures at many levels. The CE-Symm tool was developed in order to detect internal pseudosymmetry within individual polypeptide chains. Such internal symmetry can arise from duplication events, so aligning the individual symmetry units provides insights about conservation and evolution. In many cases, internal symmetry can be shown to be important for a number of functions, including ligand binding, allostery, folding, stability, and evolution. </p><p> Structural comparison tools were applied comprehensively across all PDB structures for systematic analysis. Pairwise structural comparisons of all proteins in the PDB have been computed using the Open Science Grid computing infrastructure, and are kept continually up-to-date with the release of new structures. These provide a network-based view of protein fold space. CE-Symm was also applied to systematically survey the PDB for internally symmetric proteins. It is able to detect symmetry in ~20% of all protein families. Such PDB-wide analyses give insights into the complex evolution of protein folds. </p>
23
Maria, Clément. "Algorithmes et structures de données en topologie algorithmique." Thesis, Nice, 2014. http://www.theses.fr/2014NICE4081/document.
Full textAbstract:
La théorie de l'homologie généralise en dimensions supérieures la notion de connectivité dans les graphes. Étant donné un domaine, décrit par un complexe simplicial, elle définit une famille de groupes qui capturent le nombre de composantes connexes, le nombre de trous, le nombre de cavités et le nombre de motifs équivalents en dimensions supérieures. En pratique, l'homologie permet d'analyser des systèmes de données complexes, interprétés comme des nuages de points dans des espaces métriques. La théorie de l'homologie persistante introduit une notion robuste d'homologie pour l'inférence topologique. Son champ d'application est vaste, et comprend notamment la description d'espaces des configurations de systèmes dynamiques complexes, la classification de formes soumises à des déformations et l'apprentissage en imagerie médicale. Dans cette thèse, nous étudions les ramifications algorithmiques de l'homologie persistante. En premier lieu, nous introduisons l'arbre des simplexes, une structure de données efficace pour construire et manipuler des complexes simpliciaux de grandes dimensions. Nous présentons ensuite une implémentation rapide de l'algorithme de cohomologie persistante à l'aide d'une matrice d'annotations compressée. Nous raffinons également l'inférence de topologie en décrivant une notion de torsion en homologie persistante, et nous introduisons la méthode de reconstruction modulaire pour son calcul. Enfin, nous présentons un algorithme de calcul de l'homologie persistante zigzag, qui est une généralisation algébrique de la persistance. Pour cet algorithme, nous introduisons de nouveaux théorèmes de transformations locales en théorie des représentations de carquois, appelés principes du diamant. Ces algorithmes sont tous implémentés dans la librairie de calcul Gudhi<br>The theory of homology generalizes the notion of connectivity in graphs to higher dimensions. It defines a family of groups on a domain, described discretely by a simplicial complex that captures the connected components, the holes, the cavities and higher-dimensional equivalents. In practice, the generality and flexibility of homology allows the analysis of complex data, interpreted as point clouds in metric spaces. The theory of persistent homology introduces a robust notion of homology for topology inference. Its applications are various and range from the description of high dimensional configuration spaces of complex dynamical systems, classification of shapes under deformations and learning in medical imaging. In this thesis, we explore the algorithmic ramifications of persistent homology. We first introduce the simplex tree, an efficient data structure to construct and maintain high dimensional simplicial complexes. We then present a fast implementation of persistent cohomology via the compressed annotation matrix data structure. We also refine the computation of persistence by describing ideas of homological torsion in this framework, and introduce the modular reconstruction method for computation. Finally, we present an algorithm to compute zigzag persistent homology, an algebraic generalization of persistence. To do so, we introduce new local transformation theorems in quiver representation theory, called diamond principles. All algorithms are implemented in the computational library Gudhi
24
Gilardet, Mathieu. "Étude d'algorithmes de restauration d'images sismiques par optimisation de forme non linéaire et application à la reconstruction sédimentaire." Phd thesis, Université de Pau et des Pays de l'Adour, 2013. http://tel.archives-ouvertes.fr/tel-00952964.
Full textAbstract:
Nous présentons une nouvelle méthode pour la restauration d'images sismiques. Quand on l'observe, une image sismique est le résultat d'un système de dépôt initial qui a été transformé par un ensemble de déformations géologiques successives (flexions, glissement de la faille, etc) qui se sont produites sur une grande période de temps. L'objectif de la restauration sismique consiste à inverser les déformations pour fournir une image résultante qui représente le système de dépôt géologique tel qu'il était dans un état antérieur. Classiquement, ce procédé permet de tester la cohérence des hypothèses d'interprétations formulées par les géophysiciens sur les images initiales. Dans notre contribution, nous fournissons un outil qui permet de générer rapidement des images restaurées et qui aide donc les géophysiciens à reconnaître et identifier les caractéristiques géologiques qui peuvent être très fortement modifiées et donc difficilement identifiables dans l'image observée d'origine. Cette application permet alors d'assister ces géophysiciens pour la formulation d'hypothèses d'interprétation des images sismiques. L'approche que nous introduisons est basée sur un processus de minimisation qui exprime les déformations géologiques en termes de contraintes géométriques. Nous utilisons une approche itérative de Gauss-Newton qui converge rapidement pour résoudre le système. Dans une deuxième partie de notre travail nous montrons différents résultats obtenus dans des cas concrets afin d'illustrer le processus de restauration d'image sismique sur des données réelles et de montrer comment la version restaurée peut être utilisée dans un cadre d'interprétation géologique.
25
Salikhov, Kamil. "Algorithmes et structures de données efficaces pour l’indexation de séquences d’ADN." Thesis, Paris Est, 2017. http://www.theses.fr/2017PESC1232/document.
Full textAbstract:
Les volumes des données générées par les technologies de séquençage haut débit augmentent exponentiellement ce dernier temps. Le stockage, le traitement et le transfertdeviennent des défis de plus en plus sérieux. Pour les affronter, les scientifiques doivent élaborer des approches et des algorithmes de plus en plus efficaces.Dans cette thèse, nous présentons des structures de données efficaces etdes algorithmes pour des problèmes de recherche approchée de chaînes de caractères, d'assemblagedu génome, de compression de séquences d’ADN et de classificationmétagénomique de lectures d’ADN.Le problème de recherche approchée a été bien étudié, avec un grandnombre de travaux publiés. Dans ledomaine de bioinformatique, le problème d’alignement de séquences peut être considéré comme unproblème de recherche approchée de chaînes de caractères. Dans notre travail, nousétudions une stratégie de recherche basée sur une structure d'indexation ditebidirectionnelle. D’abord, nous définissons un formalisme des schémas de recherche pour travailleravec les stratégies de recherche de ce type, ensuite nous fixons une mesure probabiliste del’efficacité de schémas de recherche et démontrons quelques propriétés combinatoires de schémasde recherche efficaces. Finalement, nous présentons des calculs expérimentaux quivalident la supériorité de nos stratégies. L’assemblage du génome est un des problèmes clefs en bioinformatique.Dans cette thèse, nous présentons une structure de données — filtre de Bloom en Cascade— qui améliore le filtre de Bloom standard et peut être utilisé pour larésolution de certains problèmes, y compris pour l’assemblage du génome. Nousdémontrons ensuite des résultats analytiques et expérimentaux sur les propriétés du filtre deBloom en Cascade. Nous présentons également comment le filtre de Bloom en Cascade peut être appliqué au problèmede compression de séquences d’ADN.Un autre problème que nous étudions dans cette thèse est la classificationmétagénomique de lectures d’ADN. Nous présentons une approche basée sur la transforméede Burrows-Wheeler pour la recherche efficace et rapide de k-mers (mots de longueur k).Cette étude est centrée sur les structures des données qui améliorent lavitesse et la consommation de mémoire par rapport à l'index classique de Burrows-Wheeler, dans le cadre de notre application<br>Amounts of data generated by Next Generation Sequencing technologies increase exponentially in recent years. Storing, processing and transferring this data become more and more challenging tasks. To be able to cope with them, data scientists should develop more and more efficient approaches and techniques.In this thesis we present efficient data structures and algorithmic methods for the problems of approximate string matching, genome assembly, read compression and taxonomy based metagenomic classification.Approximate string matching is an extensively studied problem with countless number of published papers, both theoretical and practical. In bioinformatics, read mapping problem can be regarded as approximate string matching. Here we study string matching strategies based on bidirectional indices. We define a framework, called search schemes, to work with search strategies of this type, then provide a probabilistic measure for the efficiency of search schemes, prove several combinatorial properties of efficient search schemes and provide experimental computations supporting the superiority of our strategies.Genome assembly is one of the basic problems of bioinformatics. Here we present Cascading Bloom filter data structure, that improves standard Bloom filter and can be applied to several problems like genome assembly. We provide theoretical and experimental results proving properties of Cascading Bloom filter. We also show how Cascading Bloom filter can be used for solving another important problem of read compression.Another problem studied in this thesis is metagenomic classification. We present a BWT-based approach that improves the BWT-index for quick and memory-efficient k-mer search. We mainly focus on data structures that improve speed and memory usage of classical BWT-index for our application
26
Borges, André de Ávila. "Otimização de forma e paramétrica de estruturas treliçadas através dos métodos meta-heurísticos Harmony Search e Firefly Algorithm." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2013. http://hdl.handle.net/10183/96635.
Full textAbstract:
Otimização estrutural é uma área relativamente nova que vem sendo cada vez mais explorada. Existem muitos métodos clássicos, e outros mais recentes vem surgindo para disputar em eficiência, confiabilidade e rapidez na obtenção de um resultado ótimo. Os algoritmos são classificados em algoritmos determinísticos, que utilizam a informação do gradiente, ou seja, usam os valores das funções e suas derivadas, e os meta-heurísticos, algoritmos de otimização aleatórios que são métodos probabilísticos não baseados em gradiente, ou seja, usam somente a avaliação da função objetivo. São apresentados dois algoritmos meta-heurísticos relativamente recentes: o Harmony Search, baseado na improvisação musical em busca da harmonia perfeita, e o Firefly Algorithm, que é inspirado no comportamento da luz dos vagalumes. Vários exemplos clássicos de treliças 2-D e 3-D considerando otimização paramétrica e de forma, com restrições de tensão, deslocamento, flambagem e frequência natural, são apresentados para demonstrar a eficiência dos métodos. Os resultados são comparados aos de outros autores usando diferentes métodos encontrados na literatura. Os resultados indicam que os algoritmos de otimização estudados neste trabalho são melhores ou tão eficientes quanto os demais. Por fim, os métodos são aplicados à estrutura de um projeto de engenharia adaptado.<br>Structural optimization is a relatively new area that has been increasingly exploited. There are many classical methods, and newer are emerging to compete on efficiency, reliability and speed in obtaining an optimal result. The algorithms are classified into deterministic algorithms, which use the gradient information, i.e., use the values of the functions and their derivatives, and meta-heuristic algorithms, random optimization methods which are probabilistic methods not based on gradient, i.e., they use only objective function evaluation. Two relatively recent meta-heuristics algorithms are presented, Harmony Search, based on musical improvisation in search of the perfect harmony, and Firefly Algorithm, which is inspired by the behavior of the light of fireflies. Several benchmarks of 2-D and 3-D trusses considering size and shape optimization, with stress, displacement, buckling and natural frequency constraints, are presented to demonstrate the effectiveness of the methods. The results are compared to the others authors using different methods found in the literature. The results indicate that optimization algorithms studied in this work are better than or as efficient as others. Finally, the methods are applied to the structure of an adapted engineering design.
27
Sigrist, Zoé. "Contribution à l'identification de systèmes non-linéaires en milieu bruité pour la modélisation de structures mécaniques soumises à des excitations vibratoires." Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14655/document.
Full textAbstract:
Cette thèse porte sur la caractérisation de structures mécaniques, au travers de leurs paramètres structuraux, à partir d'observations perturbées par des bruits de mesure, supposés additifs blancs gaussiens et centrés. Pour cela, nous proposons d'utiliser des modèles à temps discret à parties linéaire et non-linéaire séparables. La première permet de retrouver les paramètres recherchés tandis que la seconde renseigne sur la non-linéarité présente. Dans le cadre d'une modélisation non-récursive par des séries de Volterra, nous présentons une approche à erreurs-dans-les-variables lorsque les variances des bruits ne sont pas connues ainsi qu'un algorithme adaptatif du type LMS nécessitant la connaissance de la variance du bruit d'entrée. Dans le cadre d'une modélisation par un modèle récursif polynomial, nous proposons deux méthodes à partir d'algorithmes évolutionnaires. La première inclut un protocole d'arrêt tenant compte de la variance du bruit de sortie. Dans la seconde, les fonctions fitness sont fondées sur des fonctions de corrélation dans lesquelles l'influence du bruit est supprimée ou compensée<br>This PhD deals with the caracterisation of mechanical structures, by its structural parameters, when only noisy observations disturbed by additive measurement noises, assumed to be zero-mean white and Gaussian, are available. For this purpose, we suggest using discrete-time models with distinct linear and nonlinear parts. The first one allows the structural parameters to be retrieved whereas the second one gives information on the nonlinearity. When dealing with non-recursive Volterra series, we propose an errors-in-variables (EIV) method to jointly estimate the noise variances and the Volterra kernels. We also suggest a modified unbiased LMS algorithm to estimate the model parameters provided that the input-noise variance is known. When dealing with recursive polynomial model, we propose two methods using evolutionary algorithms. The first includes a stop protocol that takes into account the output-noise variance. In the second one, the fitness functions are based on correlation criteria in which the noise influence is removed or compensated
28
Renaud, Yoan. "Quelques aspects algorithmiques sur les systèmes de fermeture." Phd thesis, Université Blaise Pascal - Clermont-Ferrand II, 2008. http://tel.archives-ouvertes.fr/tel-00731341.
Full textAbstract:
Nous présentons dans cette thèse les définitions et notations liées aux systèmes de fermeture et montrons leur relation avec les théories de Horn. Nous nous intéressons ensuite à trois opérations sur les systèmes de fermeture : la borne supérieure, la borne inférieure et la différence. Nous proposons une caractérisation de ces différentes opérations selon la représentation des systèmes de fermeture que nous considérons. On s'intéresse ensuite au problème de génération d'une base d'implications mixtes d'un contexte formel. Nous étudions ce problème lorsque la donnée prise en considération est constituée des bases d'implications génériques positives et négatives de ce contexte. Trois résultats majeurs sont présentés : l'apport de propriétés et de règles d'inférence pour déduire des implications mixtes, l'impossibilité de générer une base d'implications mixtes juste et complète à partir de ces données dans le cas général, et la faisabilité dans le cas où le contexte est considéré réduit.
29
Kakani, Naveen Kumar. "Algorithms for Efficient Utilization of Wireless Bandwidth and to Provide Quality-of-Service in Wireless Networks." Thesis, University of North Texas, 2000. https://digital.library.unt.edu/ark:/67531/metadc2635/.
Full textAbstract:
This thesis presents algorithms to utilize the wireless bandwidth efficiently and at the same time meet the quality of service (QoS) requirements of the users. In the proposed algorithms we present an adaptive frame structure based upon the airlink frame loss probability and control the admission of call requests into the system based upon the load on the system and the QoS requirements of the incoming call requests. The performance of the proposed algorithms is studied by developing analytical formulations and simulation experiments. Finally we present an admission control algorithm which uses an adaptive delay computation algorithm to compute the queuing delay for each class of traffic and adapts the service rate and the reliability in the estimates based upon the deviation in the expected and obtained performance. We study the performance of the call admission control algorithm by simulation experiments. Simulation results for the adaptive frame structure algorithm show an improvement in the number of users in the system but there is a drop in the system throughput. In spite of the lower throughput the adaptive frame structure algorithm has fewer QoS delay violations. The adaptive call admission control algorithm adapts the call dropping probability of different classes of traffic and optimizes the system performance w.r.t the number of calls dropped and the reliability in meeting the QoS promised when the call is admitted into the system.
30
Mirza, Shemila. "Algorithms for finite structures." Thesis, Royal Holloway, University of London, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.369096.
Full text
31
Robert, Michel. "Contribution au développement du compilateur structurel P.R.I.N.T. algorithmes d'évaluation des performances temporelles des structures CMOS /." Grenoble 2 : ANRT, 1987. http://catalogue.bnf.fr/ark:/12148/cb376094250.
Full text
32
Kosová, Barbora. "Design parametrické ortézy horní končetiny." Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2017. http://www.nusl.cz/ntk/nusl-319490.
Full textAbstract:
This thesis deals with the design and manufacturing of custom-made immobilization orthosis for the upper limb. Emphasis is put on the digitization of the approach and integration of additive manufacturing in the workflow of splint production. The solution proposes automatic model construction based on a 3D scan. Such a model is further parametrized in order to provide splinting practitioners with customization abilities. Particular attention is paid to the changes of limb volume due to swell, where the use of auxetic structures is suggested.
33
Vera, Antonio. "Analyses de l'algorithme de Gauss : applications à l'analyse de l'algorithme LLL." Phd thesis, Université de Caen, 2009. http://tel.archives-ouvertes.fr/tel-01073359.
Full textAbstract:
Cette thèse est dédiée à l'analyse probabiliste d'algorithmes de réduction des réseaux euclidiens. Un réseau euclidien est l'ensemble de combinaisons linéaires à coefficients entiers d'une base (b_1,..., b_n ) \subset R^n. La réduction d'un réseau consiste a en trouver une base formée de vecteurs assez courts et assez orthogonaux, à partir d'une base donnée en entrée. Le célèbre algorithme LLL résout ce problème de manière efficace en dimension arbitraire. Il est très utilisé, mais mal compris. Nous nous concentrons sur son analyse dans le cas n = 2, où LLL devient l'algorithme de Gauss, car cette instance est une brique de base pour le cas n>= 3. Nous analysons précisément l'algorithme de Gauss, tant du point de vue de son exécution (nombre d'itérations, complexité binaire, coûts "additifs") que de la géométrie de la base de sortie (défaut d'Hermite, premier minimum et deuxième minimum orthogonalisé). Nous travaillons dans un modèle probabiliste très général, qui permet d'étudier aussi bien les instances faciles que les instances difficiles. Ce modèle nous a permis d'étudier la transition vers l'algorithme d'Euclide, qui correspond au cas où les vecteurs de la base d'entrée sont colinéaires. Nous utilisons des méthodes dynamiques : les algorithmes sont vus comme des systèmes dynamiques, et les séries génératrices concernées s'expriment en fonction de l'opérateur de transfert. Ces résultats très précis en dimension 2 sont une première étape pour l'analyse de l'algorithme LLL dans le cas général.
34
Do, Viet Phuong. "Développement et applications de méthodes bioinformatiques pour l'identification des répétitions en tandem dans les structures des protéines." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT072.
Full textAbstract:
Les structures protéiques peuvent être divisées en répétitives et apériodiques, les structures apériodiques correspondant pour la plupart à des protéines globulaires. Les protéines répétitives (PRs) contiennent des unités de répétitions adjacentes, appelées séquences répétées en tandem (TRs). Les PRs sont abondantes et ont une importance fonctionnelle fondamentale. De plus de nombreuses études ont démontré l'implication des TRs dans les pathologies humaines. Ainsi, la découverte des PRs et la compréhension de leur relation séquence-structure-fonction, offrent des perspectives de recherche prometteuses.Le développement d’initiatives en génomique structurale, combiné à une meilleure adaptation des techniques de cristallographie et de RMN à l’étude des protéines non globulaires, a permis d’élucider la structure d’un nombre croissant de PRs, d’où la nécessité de mettre en place un système de classification. Les structures répétitives ont été réparties en cinq classes, principalement fondées sur la longueur des TRs: Classe I - agrégats cristallins; Classe II - structures fibreuses; Classe III - structures allongées, dont la stabilité dépend des interactions qui s’établissent entre les motifs répétés. Classe IV - structures répétitives fermées ; Classe V - structures en collier de perles. Les efforts de ces dernières années ont abouti au développement d’outils bioinformatiques utiles à la détection et l'analyse d'éléments répétitifs présents au sein des structures protéiques (3D TRs). En fonction des caractéristiques des répétitions, certaines méthodes fonctionnent mieux que d'autres, mais, jusqu’à présent, aucune ne permettait de couvrir toute la gamme des répétitions. Ce constat nous a incités à développer une nouvelle méthode, appelée détecteur de protéines en tandem (TAPO). TAPO exploite les périodicités des coordonnées atomiques ainsi que d'autres types de représentation structurale, comprenant les chaînes générées par un alphabet conformationnel, les cartes de contact entre résidus, et les arrangements en vecteurs d'éléments de structure secondaire. Actuellement, sept scores, issus des caractéristiques analysées par TAPO, sont combinés à l’aide d’une Machine à Vecteur Support pour produire un score final permettant de différencier les protéines renfermant ou non des 3D TRs. En atteignant 94% de sensibilité et 97% de spécificité pour la référence actuelle, TAPO présente des performances améliorées par rapport aux autres méthodes de pointe. Le développement de TAPO offre de nouvelles opportunités pour l’analyse à grande échelle des protéines renfermant des 3D TRs. Ainsi, notre analyse de la base de données PDB, à l’aide de TAPO, a montré que 19% des protéines contiennent des 3D TRs. L'analyse à grande échelle des structures 3D TRs dans PDB nous a également permis de découvrir plusieurs nouveaux types de structures répétitives, absents de la classification existante et dont certains sont décrits ici.Nous avons entrepris une analyse complète des 3D TRs constitutifs du Rossmann Fold (RF). Notre intérêt pour les RFs a été suscité par le fait que de nombreuses protéines RFs représentent un cas ambigüe vis à vis des structures répétitives et non répétitives. A priori, les unités hélice α - feuillet β des RFs devraient avoir une forte tendance à s’empiler et donc, à former des structures répétitives. Afin de déterminer la fréquence à laquelle les RFs forment de longues unités de répétition empilées, nous avons sélectionné, à l’aide de TAPO, des structures contenant des RFs et les avons classées. Notre analyse montre que les RFs typiques ne peuvent pas être clairement définis comme des structures répétitives mais plutôt comme des unités de structures globulaires, comptant au plus trois répétitions α-β. Des éléments de discussion seront proposés pour tenter d’expliquer cette observation surprenante<br>In general, protein structures can be divided into: repetitive and aperiodic structures. Most of the aperiodic structures are globular proteins. The repetitive proteins contain arrays of repeats that are adjacent to each other, called Tandem Repeats (TRs). Proteins containing TRs are abundant and have fundamental functional importance. Numerous studies demonstrated the involvement of such TR-containing proteins in human diseases. Furthermore, genetic instability of these regions can lead to emerging infection threats. Additionally, TR-containing structures have generated significant interest with respect to protein design as they can make excellent scaffolds for specific recognition of target molecules. Therefore, the discovery of these domains, understanding of their sequence–structure–function relationship promises to be a fertile direction for research.The growth of structural genomics initiatives, in combination with improvements in crystallographic and NMR techniques aimed at non-globular proteins, has resulted in an increase in structurally elucidated TR proteins. This has necessitated the development of classification schemes. Structural repeats were broadly divided into five classes mainly based on repeat length; Class I – crystalline aggregates; Class II – fibrous structures such as collagen; Class III – elongated structures where the repetitive units require each other for structural stability such as solenoid proteins; Class IV – closed repetitive structures, such as TIM-barrels and Class V – bead on a string structures such as tandems of Ig-fold domains. Despite this progress, the majority of bioinformatics approaches have focused on non-repetitive globular proteins.In recent years, efforts have been made to develop bioinformatics tools for the detection and analysis of repetitive elements in protein structures (3D TRs). Depending on the size and character of the repeats, some methods perform better than others, but currently no best approach exists to cover the whole range of repeats. This served as a motivation for the development of our method called the TAndem PrOtein detector (TAPO). TAPO exploits, periodicities of atomic coordinates and other types of structural representation, including strings generated by conformational alphabets, residue contact maps, and arrangements of vectors of secondary structure elements. Currently, seven feature based scores produced by TAPO are combined using a Support Vector Machine, producing a score to enable the differentiation between proteins with and without 3D TRs. TAPO shows an improved performance over other cutting edge methods, achieving 94% sensitivity and 97% specificity on the current benchmark. The development of TAPO provided new opportunities for large scale analysis of proteins with 3D TRs. In accordance with our analysis of PDB using TAPO, 19% of proteins contain 3D TRs. The large scale analysis of the 3D TR structures in PDB also allows us to discover several new types of TR structures that were absent in the existing classification. Some of them are described in the thesis manuscript. This suggests that TAPO can be used to regularly update the collection and classification of existing repetitive structures. In particular, a comprehensive analysis of 3D TRs related to Rossmann Fold (RF) was undertaken. Our special interest in RFs was based on the observation that many proteins with RFs represent borderline cases between repetitive and non-repetitive structures. In principle, α-helix-β-strand units of RFs should have a strong potential to stack one over the other, forming repetitive structures. To probe the question of how frequently RFs form long arrays of stacked repeats, we selected by using TAPO known RF-containing structures and classified them. Our analysis shows that typical RFs cannot be clearly defined as repetitive, rather they are part of globular structures with up to 3 αβ-repeats. We provide some explanations for this surprising observation
35
Benbernou, Nadia M. "Geometric algorithms for reconfigurable structures." Thesis, Massachusetts Institute of Technology, 2011. http://hdl.handle.net/1721.1/68480.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2011.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (p. 159-163).<br>In this thesis, we study three problems related to geometric algorithms of reconfigurable structures. In the first problem, strip folding, we present two universal hinge patterns for a strip of material that enable the folding of any integral orthogonal polyhedron of only a constant factor smaller surface area, and using only a constant number of layers at any point. These geometric results offer a new way to build programmable matter that is substantially more efficient than what is possible with a square N x N sheet of material, which can achieve all integral orthogonal shapes only of surface area O(N) and may use E(N 2) layers at one point [BDDO1O]. To achieve these results, we develop new approximation algorithms for milling the surface of an integral orthogonal polyhedron of genus 0, which simultaneously give a 2-approximation in tour length and an 8/3-approximation in the number of turns. Both length and turns consume area when folding strip, so we build on previous approximation algorithms for these two objectives from 2D milling. In the second problem, maxspan, the goal is to maximize the distance between the endpoints of a fixed-angle chain. We prove a necessary and sufficient condition for characterizing maxspan configurations. The condition states that a fixed-angle chain is in maxspan configuration if and only if the configuration is line-piercing (that is, the line through each of the links intersects the line segment through the endpoints of the chain in the natural order). We call this the Line-Piercing Theorem. The Line-Piercing Theorem was originally proved by [BSO8] using Morse-Bott theory and Mayer-Vietoris sequences, but we give an elementary proof based on purely geometric arguments. The Line-Piercing Theorem also leads to efficient algorithms for computing the maxspan of fixed-angle chains. In the third problem, efficient reconfiguration of pivoting tiles, we present an algorithmic framework for reconfiguring a modular robot consisting of identical 2D tiles, where the basic move is to pivot one tile around another at a shared vertex. The robot must remain connected and avoid collisions throughout all moves. For square tiles, and hexagonal tiles on either a triangular or hexagonal lattice, we obtain optimal O(n 2)-move reconfiguration algorithms. In particular, we give the first proofs of universal reconfigurability for the first two cases, and generalize a previous result for the third case. We also consider a model analyzed by Dumitrescu and Pach [DP06] where tiles slide instead of pivot (making it easier to avoid collisions), and obtain an optimal O(n2)-move reconfiguration algorithm, improving their 0(n') bound.<br>by Nadia M. Benbernou.<br>Ph.D.
36
Chen, Calvin Ching-Yuen. "Efficient Parallel Algorithms and Data Structures Related to Trees." Thesis, University of North Texas, 1991. https://digital.library.unt.edu/ark:/67531/metadc332626/.
Full textAbstract:
The main contribution of this dissertation proposes a new paradigm, called the parentheses matching paradigm. It claims that this paradigm is well suited for designing efficient parallel algorithms for a broad class of nonnumeric problems. To demonstrate its applicability, we present three cost-optimal parallel algorithms for breadth-first traversal of general trees, sorting a special class of integers, and coloring an interval graph with the minimum number of colors.
37
Wang, Wei. "Alignement pratique de structure-séquence d'ARN avec pseudonœuds." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS563/document.
Full textAbstract:
Aligner des macromolécules telles que des protéines, des ADN et des ARN afin de révéler ou exploiter, leur homologie fonctionnelle est un défi classique en bioinformatique, qui offre de nombreuses applications, notamment dans la modélisation de structures et l'annotation des génomes. Un certain nombre d'algorithmes et d'outils ont été proposés pour le problème d'alignement structure-séquence d'ARN. Cependant, en ce qui concerne les ARN complexes, comportant des pseudo-noeuds, des interactions multiples et des paires de bases non canoniques, de tels outils sont rarement utilisés dans la pratique, en partie à cause de leurs grandes exigences de calcul, et de leur incapacité à supporter des types généraux de structures. Récemment, Rinaudo et al. ont donné un algorithme paramétré général pour la comparaison structure-séquence d'ARN, qui est capable de prendre en entrée n'importe quel type de structures comportant des pseudo-noeuds. L'algorithme paramétré est un algorithme de programmation dynamique basée sur la décomposition arborescente. Nous avons développé plusieurs variantes et extensions de cet algorithme. Afin de l'accélérer sans perte sensible de précision, nous avons introduit une approche de programmation dynamique par bandes. De plus, trois algorithmes ont été développés pour obtenir des alignements sous-optimaux. De plus, nous introduisons dans ce contexte la notion de MEA (Maximum-expected Structure-Alignment) pour calculer un alignement avec la précision maximale attendue sur un ensemble d'alignements. Tous ces algorithmes ont été implémentés dans un logiciel nommé LiCoRNA (aLignment of Complex RNAs). Les performances de LiCoRNA ont été évaluées d'abord sur l'alignement des graines des familles de de la base de données RFAM qui comportent des pseudo-noeuds. Comparé aux autres algorithmes de l'état de l'art, LiCoRNA obtient généralement des résultats équivalents ou meilleurs que ses concurrents. Grâce à la grande précision démontrée par LiCoRNA, nous montrons que cet outil peut être utilisé pour améliorer les alignements de certaines familles de RFAM qui comportent des pseudo-noeuds<br>Aligning macromolecules such as proteins, DNAs and RNAs in order to reveal, or conversely exploit, their functional homology is a classic challenge in bioinformatics, with far-reaching applications in structure modelling and genome annotation. In the specific context of complex RNAs, featuring pseudoknots, multiple interactions and non-canonical base pairs, multiple algorithmic solutions and tools have been proposed for the structure sequence alignment problem. However, such tools are seldom used in practice, due in part to their extreme computational demands, and because of their inability to support general types of structures. Recently, Rinaudo et al. gave a fully general parameterised algorithm for structure-sequence comparison, which is able to take as input any type of pseudoknotted structures. The parameterised algorithm is a tree decomposition based dynamic programming. To accelerate the dynamic programming algorithm without losing two much accuracy, we introduced a banded dynamic programming. Then three algorithms are introduced to get the suboptimal structure-sequence alignments. Furthermore, we introduce the notation Maximum Expected structure-sequence Alignment (MEA) to compute an alignment with maximum expected accuracy over a set of alignments. The Boltzmann match probability are computed based on the inside-outside algorithm. The algorithms are implemented in a software named LiCoRNA (aLignment of Complex RNAs). We first evaluate the performance of LiCoRNA on the seed alignment in the pseudoknotted RFAM families. Compared to the state-of-the-art algorithms, LiCoRNA shows generally equivalent or better results than its competitors. With the high accuracy showed by LiCoRNA, we further curate RFAM full pseudoknotted alignment. The reason why we realign full alignments is that covariance model does not support pseudoknot which may lead to misalign when building the full alignment
38
Jenatton, Rodolphe. "Structured sparsity-inducing norms : statistical and algorithmic properties with applications to neuroimaging." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2011. http://tel.archives-ouvertes.fr/tel-00668379.
Full textAbstract:
Numerous fields of applied sciences and industries have been recently witnessing a process of digitisation. This trend has come with an increase in the amount digital data whose processing becomes a challenging task. In this context, parsimony, also known as sparsity, has emerged as a key concept in machine learning and signal processing. It is indeed appealing to exploit data only via a reduced number of parameters. This thesis focuses on a particular and more recent form of sparsity, referred to as structured sparsity. As its name indicates, we shall consider situations where we are not only interested in sparsity, but where some structural prior knowledge is also available. The goal of this thesis is to analyze the concept of structured sparsity, based on statistical, algorithmic and applied considerations. To begin with, we introduce a family of structured sparsity-inducing norms whose statistical aspects are closely studied. In particular, we show what type of prior knowledge they correspond to. We then turn to sparse structured dictionary learning, where we use the previous norms within the framework of matrix factorization. From an optimization viewpoint, we derive several efficient and scalable algorithmic tools, such as working-set strategies and proximal-gradient techniques. With these methods in place, we illustrate on numerous real-world applications from various fields, when and why structured sparsity is useful. This includes, for instance, restoration tasks in image processing, the modelling of text documents as hierarchy of topics, the inter-subject prediction of sizes of objects from fMRI signals, and background-subtraction problems in computer vision.
39
Scholefield, Adam. "Quadtree structured approximation algorithms." Thesis, Imperial College London, 2014. http://hdl.handle.net/10044/1/18900.
Full textAbstract:
The success of many image restoration algorithms is often due to their ability to sparsely describe the original signal. Many sparse promoting transforms exist, including wavelets, the so called ‘lets’ family of transforms and more recent non-local learned transforms. The first part of this thesis reviews sparse approximation theory, particularly in relation to 2-D piecewise polynomial signals. We also show the connection between this theory and current state of the art algorithms that cover the following image restoration and enhancement applications: denoising, deconvolution, interpolation and multi-view super resolution. In [63], Shukla et al. proposed a compression algorithm, based on a sparse quadtree decomposition model, which could optimally represent piecewise polynomial images. In the second part of this thesis we adapt this model to image restoration by changing the rate-distortion penalty to a description-length penalty. Moreover, one of the major drawbacks of this type of approximation is the computational complexity required to find a suitable subspace for each node of the quadtree. We address this issue by searching for a suitable subspace much more efficiently using the mathematics of updating matrix factorisations. Novel algorithms are developed to tackle the four problems previously mentioned. Simulation results indicate that we beat state of the art results when the original signal is in the model (e.g. depth images) and are competitive for natural images when the degradation is high.
40
Thiebaut, Jocelyn. "Algorithmic and structural results on directed cycles in dense digraphs." Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS059.
Full textAbstract:
Dans cette thèse, nous nous intéressons à quelques problèmes algorithmiques et structurels du packing de cycles (orientés) dans les graphes orientés denses. Ces problèmes sont notamment motivés par la compréhension de la structure de tels graphes, mais également car de nombreux problèmes algorithmiques sont faciles (résolubles en temps polynomial) sur des graphes orientés acycliques alors qu'il sont NP-difficiles sur les graphes orientés en général.Plus spécifiquement, nous étudions dans un premier temps le packing de cycles et le packing de triangles dans les tournois. Ces problèmes sont les duaux (d'un point de vue programmation linéaire) des problèmes de feedback arc/vertex set qui ont reçu beaucoup d'attention dans la littérature. Nous montrons entre autres qu'il n'y a pas d'algorithme polynomial pour trouver une collection maximale de cycles (respectivement triangles) sommet ou arc-disjointe dans les tournois, sauf si P = NP. Nous nous intéressons également aux algorithmes d'approximations et de complexité paramétrée de ces différents problèmes.Nous étudions ensuite plus en détail ces problèmes dans le cas spécifique où le tournoi admet un feedback arc set qui est un couplage, appelé sparse. Étonnamment, le problème reste difficile dans le cas des triangles sommet-disjoints, mais devient polynomial pour les triangles et cycles arc-disjoints. Ainsi, nous explorons l'approximation et la complexité paramétrée du cas sommet-disjoints dans les tournois sparses.Enfin, nous répondons positivement à une conjecture structurelle sur les bipartis complets k-réguliers par Manoussakis, Song et Zhang datant de 1994. En effet, nous démontrons que tous les digraphes de cette classe non isomorphes à un digraphe particulier possèdent pour tout p pair avec 4 leq p leq |V(D)| - 4 un cycle C de taille p tel que D V(C) est hamiltonien<br>In this thesis, we are interested in some algorithmic and structural problems of (oriented) cycle packing in dense digraphs. These problems are mainly motivated by understanding the structure of such graphs, but also because many algorithmic problems are easy (i.e. resolvable in polynomial time) on acyclic digraphs while they are NP-difficult in the general case.More specifically, we first study the packing of cycles and the packing of triangles in tournaments. These problems are the two dual problems (from a linear programming point of view) of feedback arc/vertex set that have received a lot of attention in literature. Among other things, we show that there is no polynomial algorithm to find a maximum collection of cycles (respectively triangles) vertex or arc-disjoint in tournaments, unless P = NP. We are also interested in algorithms of approximations and parameterized complexity of these different problems.Then, we study these problems in the specific case where the tournament admits a feedback arc set which is a matching. Such tournaments are said to be sparse. Surprisingly, the problem remains difficult in the case of vertex-disjoint triangles, but the packing of triangles and the packing of arc-disjoint cycles become polynomial. Thus, we explore the approximation and parameterized complexity of the vertex-disjoint case in sparse tournaments.Finally, we answer positively to a structural conjecture on k-regular bipartite tournaments by Manoussakis, Song and Zhang from 1994. Indeed, we show that all digraphs of this non-isomorphic class to a particular digraph have for every p even with 4 leq p leq |V(D)| - 4 a C cycle of size p such that D V(C) is Hamiltonian
41
Correa, Leonardo de Lima. "Uma proposta de algoritmo memético baseado em conhecimento para o problema de predição de estruturas 3-D de proteínas." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2017. http://hdl.handle.net/10183/156640.
Full textAbstract:
Algoritmos meméticos são meta-heurísticas evolutivas voltadas intrinsecamente à exploração e incorporação de conhecimentos relacionados ao problema em estudo. Nesta dissertação, foi proposto um algoritmo memético multi populacional baseado em conhecimento para lidar com o problema de predição de estruturas tridimensionais de proteínas voltado à modelagem de estruturas livres de similaridades conformacionais com estruturas de proteínas determinadas experimentalmente. O algoritmo em questão, foi estruturado em duas etapas principais de processamento: (i) amostragem e inicialização de soluções; e (ii) otimização dos modelos estruturais provenientes da etapa anterior. A etapa I objetiva a geração e classificação de diversas soluções, a partir da estratégia Lista de Probabilidades Angulares, buscando a definição de diferentes grupos estruturais e a criação de melhores estruturas a serem incorporadas à meta-heurística como soluções iniciais das multi populações. A segunda etapa consiste no processo de otimização das estruturas oriundas da etapa I, realizado por meio da aplicação do algoritmo memético de otimização, o qual é fundamentado na organização da população de indivíduos em uma estrutura em árvore, onde cada nodo pode ser interpretado como uma subpopulação independente, que ao longo do processo interage com outros nodos por meio de operações de busca global voltadas a características do problema, visando o compartilhamento de informações, a diversificação da população de indivíduos, e a exploração mais eficaz do espaço de busca multimodal do problema O algoritmo engloba ainda uma implementação do algoritmo colônia artificial de abelhas, com o propósito de ser utilizado como uma técnica de busca local a ser aplicada em cada nodo da árvore. O algoritmo proposto foi testado em um conjunto de 24 sequências de aminoácidos, assim como comparado a dois métodos de referência na área de predição de estruturas tridimensionais de proteínas, Rosetta e QUARK. Os resultados obtidos mostraram a capacidade do método em predizer estruturas tridimensionais de proteínas com conformações similares a estruturas determinadas experimentalmente, em termos das métricas de avaliação estrutural Root-Mean-Square Deviation e Global Distance Total Score Test. Verificou-se que o algoritmo desenvolvido também foi capaz de atingir resultados comparáveis ao Rosetta e ao QUARK, sendo que em alguns casos, os superou. Corroborando assim, a eficácia do método.<br>Memetic algorithms are evolutionary metaheuristics intrinsically concerned with the exploiting and incorporation of all available knowledge about the problem under study. In this dissertation, we present a knowledge-based memetic algorithm to tackle the threedimensional protein structure prediction problem without the explicit use of template experimentally determined structures. The algorithm was divided into two main steps of processing: (i) sampling and initialization of the algorithm solutions; and (ii) optimization of the structural models from the previous stage. The first step aims to generate and classify several structural models for a determined target protein, by the use of the strategy Angle Probability List, aiming the definition of different structural groups and the creation of better structures to initialize the initial individuals of the memetic algorithm. The Angle Probability List takes advantage of structural knowledge stored in the Protein Data Bank in order to reduce the complexity of the conformational search space. The second step of the method consists in the optimization process of the structures generated in the first stage, through the applying of the proposed memetic algorithm, which uses a tree-structured population, where each node can be seen as an independent subpopulation that interacts with others, over global search operations, aiming at information sharing, population diversity, and better exploration of the multimodal search space of the problem The method also encompasses ad-hoc global search operators, whose objective is to increase the exploration capacity of the method turning to the characteristics of the protein structure prediction problem, combined with the Artificial Bee Colony algorithm to be used as a local search technique applied to each node of the tree. The proposed algorithm was tested on a set of 24 amino acid sequences, as well as compared with two reference methods in the protein structure prediction area, Rosetta and QUARK. The results show the ability of the method to predict three-dimensional protein structures with similar foldings to the experimentally determined protein structures, regarding the structural metrics Root-Mean-Square Deviation and Global Distance Total Score Test. We also show that our method was able to reach comparable results to Rosetta and QUARK, and in some cases, it outperformed them, corroborating the effectiveness of our proposal.
42
Clément, Julien. "Algorithmes, mots et textes aléatoires." Habilitation à diriger des recherches, Université de Caen, 2011. http://tel.archives-ouvertes.fr/tel-00913127.
Full textAbstract:
Dans ce mémoire, j'examine différents aspects d'un objet simple mais omniprésent en informatique: la séquence de symboles (appelée selon le contexte mot ou chaîne de caractères). La notion de mot est au carrefour de domaines comme la théorie de l'information et la théorie des langages. S'il est simple, il reste fondamental: nous n'avons, au plus bas niveau, que cela à disposition puisqu'il arrive toujours un moment où une donnée doit être encodée en symboles stockables en mémoire. La quantité d'information croissante de données mise à disposition et qu'on peut stocker, par exemple des génomes d'individus ou des documents numérisés, justifie que les algorithmes et les structures de données qui les manipulent soient optimisés. En conséquence, les besoins d'analyse se font sentir pour guider le choix et la conception des programmes qui manipulent ces données. L'analyse en moyenne est ici particulièrement adaptée puisque les données atteignent une variété et des volumes tellement importants que c'est le cas typique qui traduit le mieux la complexité et non pas le cas le pire. Cela évidemment pose le problème de la modélisation de données qui reste encore très épineux. En effet on souhaite deux choses contradictoires: un modèle au plus près des données, qui traduise vraiment leurs spécificités, mais aussi un modèle permettant de donner des résultats, c'est-à-dire de prédire les performances (et on comprend vite que le modèle doit donc rester relativement simple pour qu'il subsiste un espoir de le traiter!). Les méthodes sont le plus souvent celles de la combinatoire analytique et font appel à un objet mathématique, les séries génératrices, pour mener les analyses à bien.
43
Ceolin, Celina. "A equação unidimensional de difusão de nêutrons com modelo multigrupo de energia e meio heterogêneo : avaliação do fluxo para problemas estacionários e de cinética." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2014. http://hdl.handle.net/10183/96762.
Full textAbstract:
Na presente tese é resolvida a equação de difusão de nêutrons estacionária, bem como problemas de cinética, em geometria unidimensional cartesiana multi-região considerando o modelo de multigrupos de energia. Um dos objetivos e inovação neste trabalho é a obtenção de uma solução aproximada com estimativa de erro, controle de precisão e na forma de uma expressão analítica. Com esse tipo de solução não há a necessidade de recorrer a esquemas de interpolação, geralmente necessários em caso de discretizações do domínio. O fluxo de nêutrons é expandido em uma série de Taylor cujos coeficientes são encontrados utilizando a equação diferencial e as condições de contorno e interface. O domínio é dividido em várias células, cujo tamanho e o grau do polinômio são ajustáveis de acordo com a precisão requerida. Para resolver o problema de autovalor é utilizado o método da potência. A metodologia é aplicada em um benchmark que consiste na solução da equação de difusão como condição inicial e na solução de problemas de cinética para diferentes transientes. Os resultados são comparados com sucesso com resultados da literatura. A convergência da série é garantida pela aplicação de um raciocínio baseado no critério de Lipschitz para funções contínuas. Cabe ressaltar que a solução obtida, em conjunto com a análise da convergência, mostra a solidez e a precisão dessa metodologia.<br>In the present dissertation the one-dimensional neutron diffusion equation for stationary and kinetic problems in a multi-layer slab has been solved considering the multi-group energy model. One of the objectives and innovation in this work is to obtain an approximate solution with error estimation, accuracy control and in the form of an analytical expression. With this solution there is no need for interpolation schemes, which are usually needed in case of discretization of the domain. The neutron flux is expanded in a Taylor series whose coefficients are found using the differential equation and the boundary and interface conditions. The domain is divided into several layers, whose size and the polynomial order can be adjusted according to the required accuracy. To solve the eigenvalue problem the conventional power method has been used. The methodology is applied in a benchmark problem consisting of the solution of the diffusion equation as an initial condition and solving kinetic problems for different transients. The results are compared successfully with the ones in the literature. The convergence of the series is guaranteed by applying a criterion based on the Lipschitz criterion for continuous functions. Note that the solution obtained, together with the convergence analysis, shows the robustness and accuracy of this methodology.
44
Lévêque, Benjamin. "Coloration de graphes : structures et algorithmes." Phd thesis, Université Joseph Fourier (Grenoble), 2007. http://tel.archives-ouvertes.fr/tel-00187797.
Full textAbstract:
De nombreux problèmes appliqués peuvent être modélisés par le problème de la coloration des sommets d'un graphe, qui est NP-complet en général mais polynomial sur la classe des graphes parfaits introduite par Berge. L'algorithme de coloration des graphes parfaits, de Grötschel, Lovasz et Schrijver, n'est pas réellement efficace d'un point de vue pratique et il est toujours intéressant de trouver un algorithme ''purement'' combinatoire permettant de colorier les graphes parfaits en temps polynomial. Dans cette thèse, nous donnons plusieurs algorithmes simples et rapides permettant de colorier des sous-classes de graphes parfaits. Ces algorithmes utilisent en particulier la notion de contraction de paire d'amis, introduite par Fonlupt et Uhry, à propos de laquelle plusieurs conjectures sont encore ouvertes. Nous utilisons aussi des algorithmes de parcours comme LexBFS, de Rose, Tarjan et Lueker, pour prouver des résultats structuraux sur les graphes considérés.
45
Durand, de gevigney Olivier. "Orientations des graphes : structures et algorithmes." Phd thesis, Université de Grenoble, 2013. http://tel.archives-ouvertes.fr/tel-00989808.
Full textAbstract:
Orienter un graphe c'est remplacer chaque arête par un arc de mêmes extrémités. On s'intéresse à la connexité du graphe orienté ainsi obtenu. L'orientation avec des contraintes d'arc-connexité est maintenant comprise en profondeur mais très peu de résultats sont connus en terme de sommet-connexité. La conjecture de Thomassen avance que les graphes suffisament sommet-connexes ont une orientation k-sommet-connexe. De plus, la conjecture de Frank propose une caractérisation des graphes qui admettent une telle orientation. Les résultats de cette thèse s'articulent autour des notions d'orientation, de packing, de connexité et de matroïde. D'abord, nous infirmons une conjecture de Recski sur la décomposition d'un graphe en arbres ayant des orientations avec degrés entrants prescrits. Nous prouvons également un nouveau résultat sur le packing d'arborescences enracinées avec contraintes de matroïdes. Ceci généralise un résultat fondamental d'Edmonds. Enfin, nous démontrons un nouveau théorème de packing sur les bases des matroïdes de dénombrement qui nous permet d'améliorez le seul résultat connu sur la conjecture de Thomassen. D'autre part, nous donnons une construction et un théorème d'augmentation pour une famille de graphes liée à la conjecture de Frank. En conclusion, nous réfutons la conjecture de Frank et prouvons que, pour tout entier k >= 3, décider si un graphe a une orientation k-sommet-connexe est un problème NP-complet.
46
Durand, de Gevigney Olivier. "Orientations des graphes : structures et algorithmes." Thesis, Grenoble, 2013. http://www.theses.fr/2013GRENM027/document.
Full textAbstract:
Orienter un graphe c'est remplacer chaque arête par un arc de mêmes extrémités. On s'intéresse à la connexité du graphe orienté ainsi obtenu. L'orientation avec des contraintes d'arc-connexité est maintenant comprise en profondeur mais très peu de résultats sont connus en terme de sommet-connexité. La conjecture de Thomassen avance que les graphes suffisament sommet-connexes ont une orientation k-sommet-connexe. De plus, la conjecture de Frank propose une caractérisation des graphes qui admettent une telle orientation. Les résultats de cette thèse s'articulent autour des notions d'orientation, de packing, de connexité et de matroïde. D'abord, nous infirmons une conjecture de Recski sur la décomposition d'un graphe en arbres ayant des orientations avec degrés entrants prescrits. Nous prouvons également un nouveau résultat sur le packing d'arborescences enracinées avec contraintes de matroïdes. Ceci généralise un résultat fondamental d'Edmonds. Enfin, nous démontrons un nouveau théorème de packing sur les bases des matroïdes de dénombrement qui nous permet d'améliorez le seul résultat connu sur la conjecture de Thomassen. D'autre part, nous donnons une construction et un théorème d'augmentation pour une famille de graphes liée à la conjecture de Frank. En conclusion, nous réfutons la conjecture de Frank et prouvons que, pour tout entier k >= 3, décider si un graphe a une orientation k-sommet-connexe est un problème NP-complet<br>Orienting an undirected graph means replacing each edge by an arc with the same ends. We investigate the connectivity of the resulting directed graph. Orientations with arc-connectivity constraints are now deeply understood but very few results are known in terms of vertex-connectivity. Thomassen conjectured that sufficiently highly vertex-connected graphs have a k-vertex- connected orientation while Frank conjectured a characterization of the graphs admitting such an orientation. The results of this thesis are structures around the concepts of orientation, packing, connectivity and matroid. First, we disprove a conjecture of Recski on decomposing a graph into trees having orientations with specified indegrees. We also prove a new result on packing rooted arborescences with matroid constraints. This generalizes a fundamental result of Edmonds. Moreover, we show a new packing theorem for the bases of count matroids that induces an improvement of the only known result on Thomassen's conjecture. Secondly, we give a construction and an augmentation theorem for a family of graphs related to Frank's conjecture. To conclude, we disprove the conjecture of Frank and prove that, for every integer k >= 3, the problem of deciding whether a graph admits a k-vertex-orientation is NP-complete
47
Cledat, Romain. "Programming models for speculative and optimistic parallelism based on algorithmic properties." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/42749.
Full textAbstract:
Today's hardware is becoming more and more parallel. While embarrassingly parallel codes, such as high-performance computing ones, can readily take advantage of this increased number of cores, most other types of code cannot easily scale using traditional data and/or task parallelism and cores are therefore left idling resulting in lost opportunities to improve performance. The opportunistic computing paradigm, on which this thesis rests, is the idea that computations should dynamically adapt to and exploit the opportunities that arise due to idling resources to enhance their performance or quality.
In this thesis, I propose to utilize algorithmic properties to develop programming models that leverage this idea thereby providing models that increase and improve the parallelism that can be exploited. I exploit three distinct algorithmic properties: i) algorithmic diversity, ii) the semantic content of data-structures, and iii) the variable nature of results in certain applications.
This thesis presents three main contributions: i) the N-way model which leverages algorithmic diversity to speed up hitherto sequential code, ii) an extension to the N-way model which opportunistically improves the quality of computations and iii) a framework allowing the programmer to specify the semantics of data-structures to improve the performance of optimistic parallelism.
48
Rinaudo, Philippe. "Algorithmique de l'alignement structure-séquence d'ARN : une approche générale et paramétrée." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00847745.
Full textAbstract:
L'alignement de macromolécules biologiques comme les protéines, l'ADN ou encore l'ARN est une problématique biologique et bio-informatique qui a pour but de révéler une partie des mystères du fonctionnement des cellules, constituants des êtres vivants. Les ARN non-codant sont des macromolécules intervenant dans le métabolisme de tout être vivant et les deux problématiques majeurs les concernant sont: la prédiction de leur structure pour mieux comprendre leur fonctionnement et leur détection dans des bases de données ou des génomes. L'une des approches: l'alignement structure-séquence d'ARN, répond à ces deux problématiques. Le problème d'alignement structure-séquence consiste à aligner une structure connue d'un premier ARN avec la séquence d'un deuxième ARN.La structure est représentée sous la forme d'un graphe ou de façon équivalente sous la forme d'une séquence arc-annotées et la séquence représente la suite des nucléotides de l'ARN.Pour résoudre ce problème, nous cherchons à optimiser l'alignement selon une fonction de coût. C'est donc un problème d'optimisation, qui malheureusement se révèle NP-Difficile.En conséquence différents travaux définissent des classes d'instances réduites pour lesquelles ils proposent des algorithmes spécifiques mais à complexités polynomiales.Les travaux de ma thèse unifient et la généralisent les approches précédentes par la construction d'un algorithme à complexité paramétrée non spécifique à une classe d'instances. En utilisant cet algorithme, il est possible de résoudre le problème d'alignement structure-séquence pour toutes les instances possibles, et aussi efficacement que les précédentes approches sur leur domaine de résolution respectif. Cet algorithme utilise une technique empruntée à la théorie des graphes: la décomposition arborescente, c'est-à-dire qu'il transforme la structure donnée en une décomposition arborescente et c'est ensuite cette décomposition qui est alignée avec la séquence donnée. L'alignement entre une décomposition arborescente et une séquence se fait par programmation dynamique.Sa mise en place a nécessité une reformulation du problème ainsi qu'une modification importante de l'utilisation classique de la programmation dynamique pour les décompositions arborescentes. Au final, cela conduit à un algorithme paramétré dont le paramètre est entièrement lié à la décomposition arborescente. La construction des décompositions arborescentes pour lesquelles l'alignement s'effectuera plus le efficacement possible est malheureusement un problème lui aussi NP-Difficile. Néanmoins, nous avons créé une heuristique de construction de décompositions adaptée aux structures d'ARN.Nous avons alors défini des nouvelles classes de structures pour lesquelles notre algorithme (décomposition et alignement) possède une faible complexité. Ces classes incluent notamment toutes les autres classes précédemment définies et la complexité de notre algorithme est au moins aussi faible que celles des algorithmes spécifiques sur leurs classes de structures respectives. Ces classes de structures représentent la majorité des structures connues et contiennent de nombreux éléments importants jusqu'alors non pris en compte (tel que les motifs tertiaires d'ARN). Le problème de l'alignement structure-séquence tente de répondre aux problématiques de prédictions de structures et de recherche d'ARN. Néanmoins, la qualité des résultats obtenus par sa résolution dépendent de la fonction de coût utilisée. Durant ma thèse j'ai commencé la mise place de la construction par apprentissage d'une nouvelle fonction de coût, adaptée aux nouvelles classes de structures que nous avons défini. Enfin de par la nature de l'algorithme, le travail réalisé permet des améliorations non négligeables, en terme de qualité des résultats et de rapidité de calcul comme la recherche de solution sous-optimales ou l'utilisation de l'algorithme au sein d'heuristiques dérivées d'heuristiques classiques.
49
Abbas, Boushra. "Méthode de Newton régularisée pour les inclusions monotones structurées : étude des dynamiques et algorithmes associés." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS250/document.
Full textAbstract:
Cette thèse est consacrée à la recherche des zéros d'un opérateur maximal monotone structuré, à l'aide de systèmes dynamiques dissipatifs continus et discrets. Les solutions sont obtenues comme limites des trajectoires lorsque le temps t tend vers l'infini. On s'intéressera principalement aux dynamiques obtenues par régularisation de type Levenberg-Marquardt de la méthode de Newton. On décrira aussi les approches basées sur des dynamiques voisines.Dans un cadre Hilbertien, on s'intéresse à la recherche des zéros de l'opérateur maximal monotone structuré M = A + B, où A est un opérateur maximal monotone général et B est un opérateur monotone Lipschitzien. Nous introduisons des dynamiques continues et discrètes de type Newton régularisé faisant intervenir d'une façon séparée les résolvantes de l'opérateur A (implicites), et des évaluations de B (explicites). A l'aide de la représentation de Minty de l'opérateur A comme une variété Lipschitzienne, nous reformulons ces dynamiques sous une forme relevant du théorème de Cauchy-Lipschitz. Nous nous intéressons au cas particulier où A est le sous différentiel d'une fonction convexe, semi-continue inférieurement, et propre, et B est le gradient d'une fonction convexe, différentiable. Nous étudions le comportement asymptotique des trajectoires. Lorsque le terme de régularisation ne tend pas trop vite vers zéro, et en s'appuyant sur une analyse asymptotique de type Lyapunov, nous montrons la convergence des trajectoires. Par ailleurs, nous montrons la dépendance Lipschitzienne des trajectoires par rapport au terme de régularisation.Puis nous élargissons notre étude en considérant différentes classes de systèmes dynamiques visant à résoudre les inclusions monotones gouvernées par un opérateur maximal monotone structuré M = $partialPhi$+ B, où $partialPhi$ désigne le sous différentiel d'une fonction convexe, semicontinue inférieurement, et propre, et B est un opérateur monotone cocoercif. En s'appuyant sur une analyse asymptotique de type Lyapunov, nous étudions le comportement asymptotique des trajectoires de ces systèmes. La discrétisation temporelle de ces dynamiques fournit desalgorithmes forward-backward (certains nouveaux ).Finalement, nous nous intéressons à l'étude du comportement asymptotique des trajectoires de systèmes dynamiques de type Newton régularisé, dans lesquels on introduit un terme supplémentaire de viscosité évanescente de type Tikhonov. On obtient ainsi la sélection asymptotique d'une solution de norme minimale<br>This thesis is devoted to finding zeroes of structured maximal monotone operators, by using discrete and continuous dissipative dynamical systems. The solutions are obtained as the limits of trajectories when the time t tends towards infinity.We pay special attention to the dynamics that are obtained by Levenberg-Marquardt regularization of Newton's method. We also revisit the approaches based on some related dynamical systems.In a Hilbert framework, we are interested in finding zeroes of a structured maximal monotone operator M = A + B, where A is a general maximal monotone operator, and B is monotone and locally Lipschitz continuous. We introduce discrete and continuous dynamical systems which are linked to Newton's method. They involve separately B and the resolvents of A, and are designed to splitting methods. Based on the Minty representation of A as a Lipschitz manifold, we show that these dynamics can be formulated as differential systems, which are relevant to the Cauchy-Lipschitz theorem. We focus on the particular case where A is the subdifferential of a convex lower semicontinuous proper function, and B is the gradient of a convex, continuously differentiable function. We study the asymptotic behavior of trajectories. When the regularization parameter does not tend to zero too rapidly, and by using Lyapunov asymptotic analysis, we show the convergence of trajectories. Besides, we show the Lipschitz continuous dependence of the solution with respect to the regularization term.Then we extend our study by considering various classes of dynamical systems which aim at solving inclusions governed by structured monotone operators M = $partialPhi$+ B, where $partialPhi$ is the subdifferential of a convex lower semicontinuous function, and B is a monotone cocoercive operator. By a Lyapunov analysis, we show the convergence properties of the orbits of these systems. The time discretization of these dynamics gives various forward-backward splittingmethods (some new).Finally, we focus on the study of the asymptotic behavior of trajectories of the regularized Newton dynamics, in which we introduce an additional vanishing Tikhonov-like viscosity term.We thus obtain the asymptotic selection of the solution of minimal norm
50
Fischer, Johannes. "Data Structures for Efficient String Algorithms." Diss., lmu, 2007. http://nbn-resolving.de/urn:nbn:de:bvb:19-75053.
Full text