Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Discrete Sequences.
Дисертації з теми "Discrete Sequences"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-46 дисертацій для дослідження на тему "Discrete Sequences".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Bastos, Antonio Josefran de Oliveira. "Convergent Sequences of Discrete Structures and Testability." Universidade Federal do CearÃ, 2012. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=7654.
Повний текст джерелаАнотація:
FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico<br>In this work, we studied the recent theory of convergent graph
sequences and its extensions to permutation and partially ordered sets with fix dimension. Weâve conjectured a lemma of weak regularity on intervals that, if this conjecture is true, we can extend this theory to ordered graphs, which are graphs such that there is a total order on its vertices. We show some interesting relations on permutation and partially ordered sets with ordered graphs. Then, we obtain another proof to the existence of limit objects for all convergent permutation sequences. We also proved that all hereditary property of either permutation or ordered graph is testable.<br>Neste trabalho, estudamos a teoria recente de convergÃncia de
sequÃncias de grafos e suas extensÃes para permutaÃÃes e ordens parciais de dimensÃo fixa. Conjecturamos um lema de regularidade fraca de grafos em intervalos que, se for verdadeira, nos possibilita estender essa teoria para grafos ordenados, que sÃo grafos tais que existe uma ordem total entre os vÃrtices. Mostramos algumas relaÃÃes interessantes de permutaÃÃes e ordens parciais com grafos ordenados. Com isso, conseguimos uma prova alternativa para a existÃncia de objetos limites de qualquer sequÃncia convergente de permutaÃÃes. Provamos tambÃm que toda propriedade hereditÃria de permutaÃÃes ou grafos ordenados à testÃvel.
2
Adams, David Bruce. "Optimization Frameworks for Discrete Composite Laminate Stacking Sequences." Diss., Virginia Tech, 2005. http://hdl.handle.net/10919/28631.
Повний текст джерелаАнотація:
Composite panel structure optimization is commonly decomposed into panel optimization
subproblems, with specied local loads, resulting in manufacturing incompatibilities
between adjacent panel designs. Using genetic algorithms to optimize local panel stacking
sequences allows panel populations of stacking sequences to evolve in parallel and send
migrants to adjacent panels, so as to blend the local panel designs globally. The blending
process is accomplished using the edit distance between individuals of a population and
the set of migrants from adjacent panels. The objective function evaluating the tness of
designs is modied according to the severity of mismatches detected between neighboring
populations. This lays the ground work for natural evolution to a blended global solution
without leaving the paradigm of genetic algorithms. An additional method applied here
for constructing globally blended panel designs uses a parallel decomposition antithetical
to that of earlier work. Rather than performing concurrent panel genetic optimizations, a
single genetic optimization is conducted for the entire structure with the parallelism solely
within the tness evaluations. A guide based genetic algorithm approach is introduced to
exclusively generate and evaluate valid globally blended designs, utilizing a simple masterslave
parallel implementation, implicitly reducing the size of the problem design space and
increasing the quality of discovered local optima.<br>Ph. D.
3
Nickson, Thomas. "Pattern formations with discrete waves and broadcasting sequences." Thesis, University of Liverpool, 2013. http://livrepository.liverpool.ac.uk/9817/.
Повний текст джерелаАнотація:
This thesis defines the Broadcasting Automata model as an intuitive and complete method of distributed pattern formation, partitioning and distributed geometric computation. The system is examined within the context of Swarm Robotics whereby large numbers of minimally complex robots may be deployed in a variety of circumstances and settings with goals as diverse as from toxic spill containment to geological survey. Accomplishing these tasks with such simplistic machines is complex and has been deconstructed in to sub-problems considered to be signif- icant because, when composed, they are able to solve much more complex tasks. Sub-problems have been identified, and studied as pattern formation, leader elec- tion, aggregation, chain formation, hole avoidance, foraging, path formation, etc. The Broadcasting Automata draws inspiration from a variety of sources such as Ad-Hoc radio networks, cellular automata, neighbourhood sequences and nature, employing many of the same pattern forming methods that can be seen in the superposition of waves and resonance. To this end the thesis gives an in depth analysis of the primitive tools of the Broadcasting Automata model, nodal patterns, where waves from a variety of transmitters can in linear time construct partitions and patterns with results per- taining to the numbers of different patterns and partitions, along with the number of those that differ, are given. Using these primitives of the model a variety of algorithms are given including leader election, through the location of the centre of a discrete disc, and a solution to the Firing Squad Synchronisation problem. These problems are solved linearly.An exploration of the ability to vary the broadcasting radius of each node leads to results of categorisations of digital discs, their form, composition, encodings and generation. Results pertaining to the nodal patterns generated by arbitrary transmission radii on the plane are explored with a connection to broadcasting sequences and approximation of discrete metrics of which results are given for the approximation of astroids, a previously unachievable concave metric, through a novel application of the aggregation of waves via a number of explored functions. Broadcasting Automata aims to place itself as a robust and complete linear time and large scale system for the construction of patterns, partitions and geometric computation. Algorithms and methodologies are given for the solution of problems within Swarm Robotics and an extension to neighbourhood sequences. It is also hoped that it opens up a new area of research that can expand many older and more mature works.
4
Knight, James Robert. "Discrete pattern matching over sequences and interval sets." Diss., The University of Arizona, 1993. http://hdl.handle.net/10150/186432.
Повний текст джерелаАнотація:
Finding matches, both exact and approximate, between a sequence of symbols A and a pattern P has long been an active area of research in algorithm design. Some of the more well-known byproducts from that research are the diffprogram and grep family of programs. These problems form a sub-domain of a larger area of problems called discrete pattern matching which has been developed recently to characterize the wide range of pattern matching problems. This dissertation presents new algorithms for discrete pattern matching over sequences and develops a new sub-domain of problems called discrete pattern matching over interval sets. The problems and algorithms presented here are characterized by three common features: (1) a "computable scoring function" which defines the quality of matches; (2) a graph based, dynamic programming framework which captures the structure of the algorithmic solutions; and (3) an interdisciplinary aspect to the research, particularly between computer science and molecular biology, not found in other topics in computer science. The first half of the dissertation considers discrete pattern matching over sequences. It develops the alignment-graph/dynamic-programming framework for the algorithms in the sub-domain and then presents several new algorithms for regular expression and extended regular expression pattern matching. The second half of the dissertation develops the sub-domain of discrete pattern matching over interval sets, also called super-pattern matching. In this sub-domain, the input consists of sets of typed intervals, defined over a finite range, and a pattern expression of the interval types. A match between the interval sets and the pattern consists of a sequence of consecutive intervals, taken from the interval sets, such that their corresponding sequence of types matches the pattern. The name super-pattern matching comes from those problems where the interval sets corresponds to the sets of substrings reported by various pattern matching problems over a common input sequence. The pattern for the super-pattern matching problem, then, represents a "pattern of patterns," or super-pattern, and the sequences of intervals matching the super-pattern correspond to the substring of the original sequence which match that larger "pattern."
5
Spadaro, Santi Gruenhage Gary F. "Discrete sets, free sequences and cardinal properties of topological spaces." Auburn, Ala, 2009. http://hdl.handle.net/10415/1757.
Повний текст джерела
6
Biyikoglu, Türker, Marc Hellmuth, and Josef Leydold. "Largest Eigenvalues of the Discrete p-Laplacian of Trees with Degree Sequences." Department of Statistics and Mathematics, WU Vienna University of Economics and Business, 2009. http://epub.wu.ac.at/390/1/document.pdf.
Повний текст джерелаАнотація:
We characterize trees that have greatest maximum p-Laplacian eigenvalue among all trees with a given degree sequence. We show that such extremal trees can be obtained by breadth-first search where the vertex degrees are non-increasing. These trees are uniquely determined up to isomorphism. Moreover, their structure does not depend on p.<br>Series: Research Report Series / Department of Statistics and Mathematics
7
Hollander, Michael Israel. "Linear numeration systems, finite beta expansions, and discrete spectrum of substitution dynamical systems /." Thesis, Connect to this title online; UW restricted, 1996. http://hdl.handle.net/1773/5747.
Повний текст джерела
8
Queiros, Julie. "Analyse des réseaux d'ordre supérieur consruits à partir de séquences historio-géographiques." Electronic Thesis or Diss., Nantes Université, 2024. http://www.theses.fr/2024NANU4018.
Повний текст джерелаАнотація:
L’analyse de réseaux permet d’extraire de l’information sur un système à partir des relations existantes entre ses entités. Ces relations peuvent correspondre à des flux tirés de séquences d’états (i.e. des trajectoires d’agents entre ces entités). La représentation de ces données sous la forme de graphes suppose généralement que ces trajectoires respectent la propriété de Markov ; seul l’état courant est suffisant pour déterminer l’état futur d’un agent. De nombreux travaux ont remis en cause cette hypothèse et proposé d’autres modèles permettant de passer outre : les réseaux d’ordre supérieur ou HON. Dans les HON, un état peut être représenté par différents nœuds-mémoires encodant les états précédemment visités avant d’aboutir à l’état courant. Une première problématique traitée dans cette thèse est la construction des HON, qui est un problème de modélisation statistique : on cherche un bon compromis entre taille et qualité du modèle. Nous proposons un modèle de réseaux d’ordre variable plus parcimonieux que les modèles existants. Une deuxième problématique est l’analyse des HON. Un avantage souvent mis en avant est que les algorithmes classiques de graphes peuvent être utilisés avec peu de modifications. Nous montrons, dans le cas de mesures de centralité ou de clustering de graphes, que ce n’est pas le cas. Nous affirmons qu’il faut au contraire adapter les algorithmes aux modèles<br>Network analysis extracts information about a system from the relationships between its actors. These relationships can correspond to flows drawn from sequences of states (i.e. agent trajectories between these entities). Representing these data as graphs generally assumes that these trajectories respect the Markov property; only the current state is sufficient to determine an agent’s future state. Numerous studies have challenged this assumption and proposed other models that allow us to overcome it: higher-order networks or HON. In it, a state can be represented by different memory nodes encoding the states previously visited before arriving at the current state. A first problem addressed in this thesis is the construction of HON, which is a statistical modeling problem: finding a good compromise between model size and quality. We propose here a model of variable-order networks that is more parsimonious than ex- isting models. A second problem is the analysis of HON. An advantage often put forward is that classical graph algorithms can be used with few modifications. We show, in the case of centrality measures or graph clustering, that this is not the case and argue that algorithms should be adapted to models
9
Alli, Idd Pazi. "Channel estimation in mobile wireless systems." Thesis, KTH, Signalbehandling, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-98754.
Повний текст джерелаАнотація:
The demands of multimedia services from mobile user equipment (UE) for achieving high data rate, high capacity and reliable communication in modern mobile wireless systems are continually ever-growing. As a consequence, several technologies, such as the Universal Mobile Telecommunications System (UMTS) and the 3rd Generation Partnership Project (3GPP), have been used to meet these challenges. However, due to the channel fading and the Doppler shifts caused by user mobility, a common problem in wireless systems, additional technologies are needed to combat multipath propagation fading and Doppler shifts. Time-variant channel estimation is one such crucial technique used to improve the performance of the modern wireless systems with Doppler spread and multipath spread. One of vital parts of the mobile wireless channel is channel estimation, which is a method used to significantly improve the performance of the system, especially for 4G and Long Term Evolution (LTE) systems. Channel estimation is done by estimating the time-varying channel frequency response for the OFDM symbols. Time-variant channel estimation using Discrete Prolate Spheroidal Sequences (DPSS) technique is a useful channel estimation technique in mobile wireless communication for accurately estimating transmitted information. The main advantage of DPSS or Slepian basis expansion is allowing more accurate representation of high mobility mobile wireless channels with low complexity. Systems such as the fourth generation cellular wireless standards (4G), which was recently introduced in Sweden and other countries together with the Long Term Evolution, can use channel estimation techniques for providing the high data rate in modern mobile wireless communication systems. The main goal of this thesis is to test the recently proposed method, time-variant channel estimation using Discrete Prolate Spheroidal Sequences (DPSS) to model the WINNER phase II channel model. The time-variant sub-carrier coefficients are expanded in terms of orthogonal DPS sequences, referred to as Slepian basis expansions. Both Slepian basis expansions and DPS sequences span the low-dimensional subspace of time-limited and band-limited sequences as Slepian showed. Testing is done by using just two system parameters, the maximum Doppler frequency Dmax v and K, the number of basis functions of length N = 256. The main focus of this thesis is to investigate the Power spectrum and channel gain caused by Doppler spread of the WINNER II channel model together with linear fitting of curves for both the Slepian and Fourier basis expansion models. In addition, it investigates the Mean Square Error (MSE) using the Least Squares (LS) method. The investigation was carried out by simulation in Matlab, which shows that the spectrum of the maximum velocity of the user in mobile wireless channel is upper bounded by the maximum normalized one-sided Doppler frequency. Matlab simulations support the values of the results. The value of maximum Doppler bandwidth vDmax of the WINNER model is exactly the same value as DPS sequences. In addition to the Power spectrum of the WINNER model, the fitting of Slepian basis expansion performs better in the WINNER model than that of the Fourier basis expansion.
10
Antonini, Gianluca. "A discrete choice modeling framework for pedestrian walking behavior with application to human tracking in video sequences /." [S.l.] : [s.n.], 2006. http://library.epfl.ch/theses/?nr=3382.
Повний текст джерела
11
Ozakin, Cigdem. "On The Expected Value Of The Linear Complexity Of Periodic Sequences." Master's thesis, METU, 2004. http://etd.lib.metu.edu.tr/upload/12605541/index.pdf.
Повний текст джерелаАнотація:
In cryptography, periodic sequences with terms in F2 are used almost everywhere. These sequences should have large linear complexity to be cryptographically strong. In fact, the linear complexity of a sequence should be close to its period. In this thesis, we study the expected value for N-periodic sequences with terms in the finite field Fq. This study is entirely devoted to W. Meidl and Harald Niederreiter&rsquo<br>s paper
which is &ldquo<br>On the Expected Value of the Linear Complexity and the k-Error Linear Complexity of Periodic Sequences&rdquo<br>We only expand this paper, there is no improvement. In this paper there are important theorems and results about the expected value of linear complexity of periodic sequences.
12
Castro, Fabiano José de. "Matemática discreta: tópicos de recorrências lineares e suas aplicações." Universidade Federal da Paraíba, 2016. http://tede.biblioteca.ufpb.br:8080/handle/tede/9339.
Повний текст джерелаАнотація:
Submitted by ANA KARLA PEREIRA RODRIGUES (anakarla_@hotmail.com) on 2017-08-29T16:22:32Z
No. of bitstreams: 1
arquivototal.pdf: 1866226 bytes, checksum: e3b8717f65b0ca3de6fc9c38cc41f7e2 (MD5)<br>Approved for entry into archive by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2017-08-30T11:44:43Z (GMT) No. of bitstreams: 1
arquivototal.pdf: 1866226 bytes, checksum: e3b8717f65b0ca3de6fc9c38cc41f7e2 (MD5)<br>Made available in DSpace on 2017-08-30T11:44:43Z (GMT). No. of bitstreams: 1
arquivototal.pdf: 1866226 bytes, checksum: e3b8717f65b0ca3de6fc9c38cc41f7e2 (MD5)
Previous issue date: 2016-05-27<br>I show this thesis linear recurrences starting with a brief historical review of the
main authors of some problems of linear recurrences. Analyze elementary sequences,
positional formulas, recursive methods, arithmetic and geometric progressions.
Later, I will distinguish what are relations of relapses and recurrences following
equations with the explanation of the solution of a recurrence, exposed in some instances
and also the rst recurrence settings and second orders with their ratings.
Soon after I'll discuss brie y the respect of some types of third-order recurrences and
also see some generalizations to higher order. Treat, nishing this work, applications
of recurrences using the foundations mentioned above and problems involving
combinatorial.<br>Mostrarei nesta dissertação as recorrências lineares começando com um breve
comentário histórico sobre os principais autores de alguns problemas de recorrências
lineares. Analisarei sequências elementares, fórmulas posicionais, métodos recursivos,
progressões aritméticas e geométricas. Posteriormente, diferenciarei o que são
relações de recorrências e equações de recorrências seguindo com a explicação da
solução de uma recorrência, exposta em alguns exemplos e também as de nições de
recorrências de primeira e segunda ordens com suas classi cações. Logo após discorrerei,
brevemente, à respeito de alguns tipos de recorrências de terceira ordem e
veremos também algumas generalizações para ordem superior. Tratarei, nalizando
neste trabalho, aplicações das recorrências utilizando as fundamentações referidas
anteriormente e problemas envolvendo combinatória.
13
PICOZZI, MARTA ANNA ELENA. "Ordinal knowledge and spatial coding of continuous and discrete quantities in infancy." Doctoral thesis, Università degli Studi di Milano-Bicocca, 2010. http://hdl.handle.net/10281/7794.
Повний текст джерелаАнотація:
An important issue in human cognition concerns the origins and nature of the capacity to represent number. A great deal of research has focused on infants’ comprehension of the cardinal properties of number but another essential component of the concept of number is ordinality, which refers to the inherent “greater than” or “less than” relationships between numbers. Until recently, the development of this aspect of human numerical cognition in infancy had received little attention. while little is know. The aim of the current series of studies was to investigate whether the ability to appreciate ordinal relationships between numerical magnitudes is present in preverbal infants at an earlier age than previously reported. The current investigation thus includes a series of 6 experiments conducted with infants of 4 and 7 months of age and provides evidence for the debate about functional affordances of infants’ numerical representation, demonstrating that, under certain conditions, the ability to detect and grasp ordinal information embedded in non-numerical and numerical sequences of visual stimuli could be present early in infancy, at respectively 4 months and 7 months of age. Importantly, this study provided also evidence that account for the existence of a basic mapping of number to space the presence, showing that 7-month-old infants are able to link oriented spatial codes to representations of numerical magnitude.
14
Wang, Qianxue. "Création et évaluation statistique d'une nouvelle de générateurs pseudo-aléatoires chaotiques." Thesis, Besançon, 2012. http://www.theses.fr/2012BESA2031.
Повний текст джерелаАнотація:
Dans cette thèse, une nouvelle manière de générer des nombres pseudo-aléatoires est présentée.La proposition consiste à mixer deux générateurs exitants avec des itérations chaotiquesdiscrètes, qui satisfont à la définition de chaos proposée par Devaney. Un cadre rigoureux estintroduit, dans lequel les propriétés topologiques du générateur résultant sont données. Deuxréalisations pratiques d’un tel générateur sont ensuite présentées et évaluées. On montre que lespropriétés statistiques des générateurs fournis en entrée peuvent être grandement améliorées enprocédant ainsi. Ces deux propositions sont alors comparées, en profondeur, entre elles et avecun certain nombre de générateurs préexistants. On montre entre autres que la seconde manièrede mixer deux générateurs est largement meilleure que la première, à la fois en terme de vitesseet de performances.Dans la première partie de ce manuscrit, la fonction d’itérations considérée est la négation vectorielle.Dans la deuxième partie, nous proposons d’utiliser des graphes fortement connexescomme critère de sélection de bonnes fonctions d’itérations. Nous montrons que nous pouvonschanger de fonction sans perte de propriétés pour le générateur obtenu. Finalement, une illustrationdans le domaine de l’information dissimulée est présentée, et la robustesse de l’algorithmede tatouage numérique proposé est évalué<br>In this thesis, a new way to generate pseudorandom numbers is presented. The propositionis to mix two exiting generators with discrete chaotic iterations that satisfy the Devaney’sdefinition of chaos. A rigorous framework is introduced, where topological properties of theresulting generator are given, and two practical designs are presented and evaluated. It is shownthat the statistical quality of the inputted generators can be greatly improved by this way, thusfulfilling the up-to-date standards. Comparison between these two designs and existing generatorsare investigated in details. Among other things, it is established that the second designedtechnique outperforms the first one, both in terms of performance and speed.In the first part of this manuscript, the iteration function embedded into chaotic iterations isthe vectorial Boolean negation. In the second part, we propose a method using graphs havingstrongly connected components as a selection criterion.We are thus able to modify the iterationfunction without deflating the good properties of the associated generator. Simulation resultsand basic security analysis are then presented to evaluate the randomness of this new family ofpseudorandom generators. Finally, an illustration in the field of information hiding is presented,and the robustness of the obtained data hiding algorithm against attacks is evaluated
15
Profe, Jörn [Verfasser], Bernd [Akademischer Betreuer] Zolitschka, Bernd [Gutachter] Zolitschka, and Markus [Gutachter] Fuchs. "X-ray fluorescence scanning of discrete samples - a new tool for the geochemical characterization of loess-paleosol sequences / Jörn Profe ; Gutachter: Bernd Zolitschka, Markus Fuchs ; Betreuer: Bernd Zolitschka." Bremen : Staats- und Universitätsbibliothek Bremen, 2018. http://d-nb.info/1165772167/34.
Повний текст джерела
16
Chrysostomou, Charalambos. "Characterisation and classification of protein sequences by using enhanced amino acid indices and signal processing-based methods." Thesis, De Montfort University, 2013. http://hdl.handle.net/2086/9895.
Повний текст джерелаАнотація:
Protein sequencing has produced overwhelming amount of protein sequences, especially in the last decade. Nevertheless, the majority of the proteins' functional and structural classes are still unknown, and experimental methods currently used to determine these properties are very expensive, laborious and time consuming. Therefore, automated computational methods are urgently required to accurately and reliably predict functional and structural classes of the proteins. Several bioinformatics methods have been developed to determine such properties of the proteins directly from their sequence information. Such methods that involve signal processing methods have recently become popular in the bioinformatics area and been investigated for the analysis of DNA and protein sequences and shown to be useful and generally help better characterise the sequences. However, there are various technical issues that need to be addressed in order to overcome problems associated with the signal processing methods for the analysis of the proteins sequences. Amino acid indices that are used to transform the protein sequences into signals have various applications and can represent diverse features of the protein sequences and amino acids. As the majority of indices have similar features, this project proposes a new set of computationally derived indices that better represent the original group of indices. A study is also carried out that resulted in finding a unique and universal set of best discriminating amino acid indices for the characterisation of allergenic proteins. This analysis extracts features directly from the protein sequences by using Discrete Fourier Transform (DFT) to build a classification model based on Support Vector Machines (SVM) for the allergenic proteins. The proposed predictive model yields a higher and more reliable accuracy than those of the existing methods. A new method is proposed for performing a multiple sequence alignment. For this method, DFT-based method is used to construct a new distance matrix in combination with multiple amino acid indices that were used to encode protein sequences into numerical sequences. Additionally, a new type of substitution matrix is proposed where the physicochemical similarities between any given amino acids is calculated. These similarities were calculated based on the 25 amino acids indices selected, where each one represents a unique biological protein feature. The proposed multiple sequence alignment method yields a better and more reliable alignment than the existing methods. In order to evaluate complex information that is generated as a result of DFT, Complex Informational Spectrum Analysis (CISA) is developed and presented. As the results show, when protein classes present similarities or differences according to the Common Frequency Peak (CFP) in specific amino acid indices, then it is probable that these classes are related to the protein feature that the specific amino acid represents. By using only the absolute spectrum in the analysis of protein sequences using the informational spectrum analysis is proven to be insufficient, as biologically related features can appear individually either in the real or the imaginary spectrum. This is successfully demonstrated over the analysis of influenza neuraminidase protein sequences. Upon identification of a new protein, it is important to single out amino acid responsible for the structural and functional classification of the protein, as well as the amino acids contributing to the protein's specific biological characterisation. In this work, a novel approach is presented to identify and quantify the relationship between individual amino acids and the protein. This is successfully demonstrated over the analysis of influenza neuraminidase protein sequences. Characterisation and identification problem of the Influenza A virus protein sequences is tackled through a Subgroup Discovery (SD) algorithm, which can provide ancillary knowledge to the experts. The main objective of the case study was to derive interpretable knowledge for the influenza A virus problem and to consequently better describe the relationships between subtypes of this virus. Finally, by using DFT-based sequence-driven features a Support Vector Machine (SVM)-based classification model was built and tested, that yields higher predictive accuracy than that of SD. The methods developed and presented in this study yield promising results and can be easily applied to proteomic fields.
17
Ekvall, Linus. "Airborne Radar Ground Clutter Suppression Using Multitaper Spectrum Estimation : Comparison with Traditional Method." Thesis, Luleå tekniska universitet, Institutionen för system- och rymdteknik, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-70934.
Повний текст джерелаАнотація:
During processing of data received by an airborne radar one of the issues is that the typical signal echo from the ground produces a large perturbation. Due to this perturbation it can be difficult to detect targets with low velocity or a low signal-to-noise ratio. Therefore, a filtering process is needed to separate the large perturbation from the target signal. The traditional method include a tapered Fourier transform that operates in parallel with a MTI filter to suppress the main spectral peak in order to produce a smoother spectral output. The difference between a typical signal echo produced from an object in the environment and the signal echo from the ground can be of a magnitude corresponding to more than a 60 dB difference. This thesis presents research of how the multitaper approach can be utilized in concurrence with the minimum variance estimation technique, to produce a spectral estimation that strives for a more effective clutter suppression. A simulation model of the ground clutter was constructed and also a number of simulations for the multitaper, minimum variance estimation technique was made. Compared to the traditional method defined in this thesis, there was a slight improvement of the improvement factor when using the multitaper approach. An analysis of how variations of the multitaper parameters influence the results with respect to minimum detectable velocity and improvement factor have been carried out. The analysis showed that a large number of time samples, a large number of tapers and a narrow bandwidth provided the best result. The analysis is based on a full factorial simulation that provides insight of how to choose the DPSS parameters if the method is to be implemented in a real radar system.
18
Gudjonsen, Ludvik. "Combining Probabilistic and Discrete Methods for Sequence Modelling." Thesis, University of Skövde, Department of Computer Science, 1999. http://urn.kb.se/resolve?urn=urn:nbn:se:his:diva-390.
Повний текст джерелаАнотація:
<p>Sequence modelling is used for analysing newly sequenced proteins, giving indication of the 3-D structure and functionality. Current approaches to the modelling of protein families are either based on discrete or probabilistic methods. Here we present an approach for combining these two approaches in a hybrid model, where discrete patterns are used to model conserved regions and probabilistic models are used for variable regions. When hidden Markov models are used to model the variable regions, the hybrid method gives increased classification accuracy, compared to pure discrete or probabilistic models.</p>
19
Temirkhanova, Ainur. "Estimates for Discrete Hardy-type Operators in Weighted Sequence Spaces." Doctoral thesis, Luleå tekniska universitet, Matematiska vetenskaper, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-18222.
Повний текст джерелаАнотація:
This PhD thesis consists of an introduction and eight papers, which deal with questions of the validity of some new discrete Hardy type inequalities in weighted spaces of sequences and on the cone of non-negative monotone sequences, and their applications. In the introduction we give an overview of the area that serves as a frame for the rest of the thesis. In particular, a short description of the development of Hardy type inequalities is given. In Paper 1 we find necessary and sufficient conditions on weighted sequences $\omega_i$, $i=1, 2,...,n-1$, $u$ and $v$, for which the operator $$ (S_{n}f)_i=\sum\limits_{k_1=1}^i\omega_{1,k_1}\cdots\sum\limits_{k_{n-1}=1}^{k_{n-2}} \omega_{n-1,k_{n-1}}\sum\limits_{j=1}^{k_{n-1}}f_j,~~ i\geq 1,~~~~~(1) $$ is bounded from $l_{p,v}$ to $l_{q,u}$ for $1<p\leq q<\infty$. In Paper 2 we prove a new discrete Hardy-type inequality $$ \|Af\|_{q,u}\leq C\|f\|_{p,v},~~~~1<p\leq q<\infty,~~~~~~~~~~~(2) $$ where the matrix operator $A$ is defined by $\left(Af\right)_i:=\sum\limits_{j=1}^ia_{i,j}f_j,$ ~$a_{i, j}\geq 0$, where the entries $a_{i, j}$ satisfy less restrictive additional conditions than studied before. Moreover, we study the problem of compactness for the operator $A$, and also the dual result is stated, proved and discussed. In Paper 3 we derive the necessary and sufficient conditions for inequality (2) to hold for the case $1<q<p<\infty$. In Papers 4 and 5 we obtain criteria for the validity of the inequality (2) for slightly more general classes of matrix operators $A$ defined by $\left(Af\right)_j:=\sum\limits_{i=j}^\infty a_{i,j}f_i,$ ~$a_{i, j}\geq 0$, when $1<p, q<\infty$. Moreover, we study the problem of compactness for the operator $A$ for the case $1<p\leq q<\infty$, also the dual result is established and here we also give some applications of the main results. In Paper 6 we state boundedness for the operator of multiple summation with weights (1) in weighted sequence spaces for the case $1<q<p<\infty$. Paper 7 deals with new Hardy-type inequalities restricted to the cones of monotone sequences. The case $1<q<p<\infty$ is considered. Also some applications related to H\"{o}lder's summation method are pointed out. In Paper 8 we obtain necessary and sufficient conditions for which three-weighted Hardy type inequalities hold.<br><p>Godkänd; 2015; 20151021 (aintem); Nedanstående person kommer att disputera för avläggande av teknologie doktorsexamen. Namn: Ainur Temirkhanova Ämne: Matematik/Mathematics Avhandling: Estimates for Discrete Hardy-type Operators in Weighted Sequence Spaces Opponent: Professor Mikhail Goldman, Dept of Nonlinear Analysis and Optimization, Peoples’Friendship University of Russia, Moscow, Russia. Ordförande: Professor Peter Wall, Avd för matematiska vetenskaper, Institutionen för teknikvetenskap och matematik, Luleå tekniska universitet, Luleå. Tid: Tisdag 8 december kl 10.00 Plats: E246, Luleå tekniska universitet</p>
20
Akhtar, Mahmood Electrical Engineering & Telecommunications Faculty of Engineering UNSW. "Genomic sequence processing: gene finding in eukaryotes." Publisher:University of New South Wales. Electrical Engineering & Telecommunications, 2008. http://handle.unsw.edu.au/1959.4/40912.
Повний текст джерелаАнотація:
Of the many existing eukaryotic gene finding software programs, none are able to guarantee accurate identification of genomic protein coding regions and other biological signals central to pathway from DNA to the protein. Eukaryotic gene finding is difficult mainly due to noncontiguous and non-continuous nature of genes. Existing approaches are heavily dependent on the compositional statistics of the sequences they learn from and are not equally suitable for all types of sequences. This thesis firstly develops efficient digital signal processing-based methods for the identification of genomic protein coding regions, and then combines the optimum signal processing-based non-data-driven technique with an existing data-driven statistical method in a novel system demonstrating improved identification of acceptor splice sites. Most existing well-known DNA symbolic-to-numeric representations map the DNA information into three or four numerical sequences, potentially increasing the computational requirement of the sequence analyzer. Proposed mapping schemes, to be used for signal processing-based gene and exon prediction, incorporate DNA structural properties in the representation, in addition to reducing complexity in subsequent processing. A detailed comparison of all DNA representations, in terms of computational complexity and relative accuracy for the gene and exon prediction problem, reveals the newly proposed ?paired numeric? to be the best DNA representation. Existing signal processing-based techniques rely mostly on the period-3 behaviour of exons to obtain one dimensional gene and exon prediction features, and are not well equipped to capture the complementary properties of exonic / intronic regions and deal with the background noise in detection of exons at their nucleotide levels. These issues have been addressed in this thesis, by proposing six one-dimensional and three multi-dimensional signal processing-based gene and exon prediction features. All one-dimensional and multi-dimensional features have been evaluated using standard datasets such as Burset/Guigo1996, HMR195, and the GENSCAN test set. This is the first time that different gene and exon prediction features have been compared using substantial databases and using nucleotide-level metrics. Furthermore, the first investigation of the suitability of different window sizes for period-3 exon detection is performed. Finally, the optimum signal processing-based gene and exon prediction scheme from our evaluations is combined with a data-driven statistical technique for the recognition of acceptor splice sites. The proposed DSP-statistical hybrid is shown to achieve 43% reduction in false positives over WWAM, as used in GENSCAN.
21
Olivieri, Julia. "Drawing DNA Sequence Networks." Oberlin College Honors Theses / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1466511242.
Повний текст джерела
22
Said, Karim A. "Prolate Spheroidal Sequence Based Transceivers for Time-Frequency Dispersive Channels." Diss., Virginia Tech, 2017. http://hdl.handle.net/10919/86594.
Повний текст джерелаАнотація:
Most existing transceivers are Fourier-centric where complex sinusoids play a central role in the internals of the core building blocks. From the channel perspective, complex sinusoids constitute the fundamental effects in the wireless baseband equivalent channel model; exemplified by the time-invariant and time-varying transfer functions in static and time-varying channel conditions respectively. In addition, complex sinusoids are used as signaling waveforms for data transmission through the channel.
The dominant mode of transmission in modern communications is in the form of finite time duration blocks having approximately finite bandwidth. As a result, the time-frequency space becomes projected to a time-frequency subspace having essentially limited support where complex sinusoids suffer from leakage effects due to the finite time extent of a block. In addition, Kronecker delta signals (duals of complex sinusoids) suffer from the same vulnerability due to the finite extent bandwidth. Gabor signaling bases using non-rectangular pulse shapes can attain good confinement in the time-frequency space, however, at the expense of completeness which reduces the utilization efficiency of the time-frequency signaling resources.
Over a signaling block period, a doubly dispersive (DD) channel is projected onto an essentially limited time-frequency subspace. In this subspace, the Discrete Prolate Spheroidal (DPS) basis matched to the channel parameters is known to be optimally compact in representing the channel using a basis expansion decomposition. Unlike the Discrete Fourier Transform (DFT) basis which lacks compactness due to the leakage effect.
Leakage in the expansion coefficients of a particular channel using the DFT basis has a direct correspondence with the Inter-Symbol Interference (ISI) between the DFT signaling components when transmitted through the same channel. For the DPS basis, however, the correspondence is not as obvious. Nevertheless, DPS when used for signaling results in ISI compactness in the form of an exponential decay of distant ISI components.
The efficacy of DPS signaling in DD channels in addition to its efficiency in modeling DD channels motivates the investigation of a new transceiver baseband architecture where DFT is supplanted by DPS.<br>Ph. D.
23
Matoug, Mahmoud M. "An investigation of misinformation and production control implementation sequence using discrete linear control." Thesis, Loughborough University, 1990. https://dspace.lboro.ac.uk/2134/19487.
Повний текст джерелаАнотація:
Discrete linear control theory is used in this research to examine the effects of system choice and data errors on the performance of production control systems. Two common information flow systems are modelled. These are the Reorder Cycle (ROC) and the Material Requirements Planning (MRP) systems. System choices include the choice of forecasting method, the choice of delivery policy, and the choice of inventory rule. The source of data errors include stock recording errors, delay in stock recording, incorrect bills of material. The other part of the research examines the sequence of implementing a new production control system. Different ways of moving from a Reorder Cycle to a Material Requirements Planning system are studied. Guidelines for an implementation sequence are produced.
24
Aitken, Victor C. (Victor Charles) Carleton University Dissertation Engineering Systems and Computer. "Sliding mode state estimation for nonlinear discrete-time systems; applications in image sequence analysis." Ottawa, 1995.
Знайти повний текст джерела
25
Riggle, Matthew. "Runs of Identical Outcomes in a Sequence of Bernoulli Trials." TopSCHOLAR®, 2018. https://digitalcommons.wku.edu/theses/2451.
Повний текст джерелаАнотація:
The Bernoulli distribution is a basic, well-studied distribution in probability. In this thesis, we will consider repeated Bernoulli trials in order to study runs of identical outcomes. More formally, for t ∈ N, we let Xt ∼ Bernoulli(p), where p is the probability of success, q = 1 − p is the probability of failure, and all Xt are independent. Then Xt gives the outcome of the tth trial, which is 1 for success or 0 for failure. For n, m ∈ N, we define Tn to be the number of trials needed to first observe n consecutive successes (where the nth success occurs on trial XTn ). Likewise, we define Tn,m to be the number of trials needed to first observe either n consecutive successes or m consecutive failures.
We shall primarily focus our attention on calculating E[Tn] and E[Tn,m]. Starting with the simple cases of E[T2] and E[T2,2], we will use a variety of techniques, such as counting arguments and Markov chains, in order to derive the expectations. When possible, we shall also provide closed-form expressions for the probability mass function, cumulative distribution function, variance, and other values of interest. Eventually we will work our way to general formulas for E[Tn] and E[Tn,m]. We will also derive formulas for conditional averages, and discuss how famous results from probability such as Wald’s Identity apply to our problem. Numerical examples will also be given in order to supplement the discussion and clarify the results.
26
Shinjo, Masato. "Studies on Non-autonomous Discrete Hungry Integrable Systems Associated with Some Eigenvalue Problems." Kyoto University, 2017. http://hdl.handle.net/2433/227662.
Повний текст джерела
27
Lora, Roque. "Unmanned Aerial Vehicle Tracking System with Out-Of-Sequence Measurement in a Discrete Time-Delayed Extended Kalman Filter." DigitalCommons@USU, 2017. https://digitalcommons.usu.edu/etd/5441.
Повний текст джерелаАнотація:
The goal of this thesis is to extend the delayed Kalman filter so it can be used with non-linear systems and that it can handle randomized delays on the measurements. In the particular case of this study, the filter is used to estimates the states of an unmanned aerial system. The outputs of the filter are used to point an antenna and a camera towards a UAS. Different scenarios are simulated for the purpose of comparing the efficiency of this technique in various situations.
28
Fransson, Linnea. "Tribonacci Cat Map : A discrete chaotic mapping with Tribonacci matrix." Thesis, Linnéuniversitetet, Institutionen för matematik (MA), 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-104706.
Повний текст джерелаАнотація:
Based on the generating matrix to the Tribonacci sequence, the Tribonacci cat map is a discrete chaotic dynamical system, similar to Arnold's discrete cat map, but on three dimensional space. In this thesis, this new mapping is introduced and the properties of its matrix are presented. The main results of the investigation prove how the size of the domain of the map affects its period and explore the orbit lengths of non-trivial points. Different upper bounds to the map are studied and proved, and a conjecture based on numerical calculations is proposed. The Tribonacci cat map is used for applications such as 3D image encryption and colour encryption. In the latter case, the results provided by the mapping are compared to those from a generalised form of the map.
29
Gicquel, Céline. "MIP models and exact methods for the Discrete Lot-sizing and Scheduling Problem with sequence-dependent changeover costs and times." Phd thesis, Ecole Centrale Paris, 2008. http://tel.archives-ouvertes.fr/tel-00375964.
Повний текст джерелаАнотація:
Le dimensionnement des lots de production est une des nombreuses activités survenant dans le cadre de la planification de production. Il a pour objet de déterminer quand et combien produire de façon à réaliser le meilleur compromis possible entre la minimisation des coûts liés à la production (coûts fixes de reconfiguration de la ressource, coûts de stockage...) et la satisfaction de la demande des clients Nous nous intéressons ici un problème de planification de production par lots connu sous le nom de "Discrete Lot-sizing and Scheduling Problem" ou "DLSP". Plus précisément, nous étudions plusieurs variantes de ce problème dans lesquelles les coûts et/ou les temps de changement de produits sur la ressource sont dépendant de la séquence et nous proposons diverses extensions d'une méthode disponible dans la littérature pour la résolution exacte du problème mono-niveau, mono-ressource. Nos contributions portent à la fois sur la modélisation du problème et sur l'implémentation de méthodes efficaces de résolution. En ce qui concerne la modélisation, nous étudions l'intégration de divers aspects opérationnels dans le modèle de base afin d'en améliorer la pertinence industrielle. Ainsi nous considérons les extensions suivantes : la prise en compte d'une structure de produits "multi-attributs" qui permet de diminuer la taille du problème d'optimisation à résoudre, l'intégration de temps de changement positifs afin de mieux modéliser la perte de production causée par une reconfiguration de la ressource et la présence de plusieurs ressources parallèles dont la production doit être planifiée simultanément. En ce qui concerne la résolution du problème, nous présentons pour chacune des extensions du modèle de base une approche de résolution visant à fournir des solutions optimales exactes. En général, les résultats de nos expériences numériques montrent l'utilité pratique de ces algorithmes pour la résolution d'instances de moyenne et grande taille en des temps de calcul compatibles avec une application industrielle
30
Ngo, Thoi-Nhan. "Contrôle optimal en temps discret et en horizon infini." Thesis, Paris 1, 2016. http://www.theses.fr/2016PA01E062/document.
Повний текст джерелаАнотація:
Cette thèse contient des contributions originales à la théorie du Contrôle Optimal en temps discret et en horizon infini du point de vue de Pontryagin. Il y a 5 chapitres dans cette thèse. Dans le chapitre 1, nous rappelons des résultats préliminaires sur les espaces de suites à valeur dans et des résultats de Calcul Différentiel. Dans le chapitre 2, nous étudions le problème de Contrôle Optimal, en temps discret et en horizon infini avec la contrainte asymptotique et avec le système autonome. En utilisant la structure d'espace affine de Banach de l'ensemble des suites convergentes vers 0, et la structure d'espace vectoriel de Banach de l'ensemble des suites bornées, nous traduisons ce problème en un problème d'optimisation statique dam des espaces de Banach. Après avoir établi des résultats originaux sur les opérateurs de Nemytskii sur les espaces de suites et après avoir adapté à notre problème un théorème d'existence de multiplicateurs, nous établissons un nouveau principe de Pontryagin faible pour notre problème. Dans le chapitre 3, nous établissons un principe de Pontryagin fort pour les problèmes considérés au chapitre 2 en utilisant un résultat de Ioffe-Tihomirov. Le chapitre 4 est consacré aux problèmes de Contrôle Optimal, en temps discret et en horizon infini, généraux avec plusieurs critères différents. La méthode utilisée est celle de la réduction à l'horizon fini, initiée par J. Blot et H. Chebbi en 2000. Les problèmes considérés sont gouvernés par des équations aux différences ou des inéquations aux différences. Un nouveau principe de Pontryagin faible est établi en utilisant un résultat récent de J. Blot sur les multiplicateurs à la Fritz John. Le chapitre 5 est consacré aux problèmes multicritères de Contrôle Optimal en temps discret et en horizon infini. De nouveaux principes de Pontryagin faibles et forts sont établis, là-aussi en utilisant des résultats récents d'optimisation, sous des hypothèses plus faibles que celles des résultats existants<br>This thesis contains original contributions to the optimal control theory in the discrete-time framework and in infinite horizon following the viewpoint of Pontryagin. There are 5 chapters in this thesis. In Chapter 1, we recall preliminary results on sequence spaces and on differential calculus in normed linear space. In Chapter 2, we study a single-objective optimal control problem in discrete-time framework and in infinite horizon with an asymptotic constraint and with autonomous system. We use an approach of functional analytic for this problem after translating it into the form of an optimization problem in Banach (sequence) spaces. Then a weak Pontyagin principle is established for this problem by using a classical multiplier rule in Banach spaces. In Chapter 3, we establish a strong Pontryagin principle for the problems considered in Chapter 2 using a result of Ioffe and Tihomirov. Chapter 4 is devoted to the problems of Optimal Control, in discrete time framework and in infinite horizon, which are more general with several different criteria. The used method is the reduction to finite-horizon initiated by J. Blot and H. Chebbi in 2000. The considered problems are governed by difference equations or difference inequations. A new weak Pontryagin principle is established using a recent result of J. Blot on the Fritz John multipliers. Chapter 5 deals with the multicriteria optimal control problems in discrete time framework and infinite horizon. New weak and strong Pontryagin principles are established, again using recent optimization results, under lighter assumptions than existing ones
31
Meyer, Marie. "Polytopes Associated to Graph Laplacians." UKnowledge, 2018. https://uknowledge.uky.edu/math_etds/54.
Повний текст джерелаАнотація:
Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, PG, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, PD.
Basic properties of both families of simplices, PG and PD, are established using techniques from Ehrhart theory. Motivated by a well-known conjecture in the field, our investigation focuses on reflexivity, the integer decomposition property, and unimodality of Ehrhart h*-vectors of these polytopes. A systematic investigation of PG for trees, cycles, and complete graphs is provided, which is enhanced by an investigation of PD for cyclic digraphs. We form intriguing connections with other families of simplices and produce G and D such that the h*-vectors of PG and PD exhibit extremal behavior.
32
Santana, Jailson Santos. "O ensino dos modelos probabilísticos discretos no ensino médio." Universidade Federal de Sergipe, 2016. https://ri.ufs.br/handle/riufs/6483.
Повний текст джерелаАнотація:
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES<br>This work aims to support Basic Education teachers by providing a detailed materials for teaching Combinatorial Analysis, Probability and Probabilistic Models, taking into account aspects related to day-to- day using mathematical concepts in problem situations. We also propose a teaching sequence on the topics mentioned above for the Basic Education teachers to broaden and diversify their strategies education.<br>Este trabalho tem como objetivo dar suporte ao professor da Educação Básica fornecendo um material detalhado para o ensino da Análise Combinatória, Probabilidade e Modelos Probabilísticos, levando-se em consideração aspectos relacionados ao dia-a-dia, utilizando conceitos matemáticos em situações problemas. Propomos ainda uma sequência didática sobre os temas acima citados para que os professores da Educação Básica possam ampliar e diversificar as suas estratégias de ensino.
33
Bitondi, Fernanda Rizzi. "Variabilidade comportamental e a seleção de uma sequência de baixa probabilidade inicial: comparando dois procedimentos." Pontifícia Universidade Católica de São Paulo, 2012. https://tede2.pucsp.br/handle/handle/16687.
Повний текст джерелаАнотація:
Made available in DSpace on 2016-04-29T13:17:45Z (GMT). No. of bitstreams: 1
Fernanda Rizzi Bitondi.pdf: 1390449 bytes, checksum: c3d88238b2946cc2655e04fd9337cc96 (MD5)
Previous issue date: 2012-05-25<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>The aim of this study was to evaluate the effectiveness of two procedures, Discrete Trial (DT) and Discrete Trial with Interresponse Interval (DT/IRI), on the production of behavioral variability in different conditions (directly reinforced and induced) and determine what condition, in each procedure, would facilitate the selection of an initial sequence of low probability. Were selected 18 college students with baseline performance measured by U-valeu, that was equal or less than 0,5. They were divided into the two procedures and subdivided into three groups with three participants (VAR, YOKE and CON). The task was to form images on the computer screen by pressing two keys (left and right) on lateral keyboards. The unit was four responses to the keys. In both procedures, a piece of the image, a tone and 0,5 seconds was used to reinforce sequences that attended the contingency s criterion, and a timeout of 1,0 second, if not. Only the DT/IRI had a 0,5 second interval after the first three responses of the sequence. The experiment had three phases. In Phase I, baseline, sequences was continuous reinforced (CRF). For two groups (DT- VAR and DT/IRI-VAR) in Phase 2, variability was direct reinforced on 15 sequences, mean that the less frequent and less recent sequence had more probability of been reinforced than the others, and a target sequence (less frequent sequence at baseline) was reinforced in CRF. In Phase 3, the distribution of reinforcement of the prior phase was yoked for the 15 sequences and another target sequence was reinforced in CRF. For the groups DT-YOKE and DT/IRI-YOKE, the phase s exposure was reversed, whereas in Phase 2 the distribution of reinforcement was yoked to the performance of the VAR groups. In groups DT-CON and DT/IRI-CON, only the target sequence was reinforced in both phases. The results showed that variability increased in the first session of Phase 2 for all participants. The DT-YOKE group showed the highest levels of variability within this procedure. In the DT/IRI procedure, this was true for the group DT/IRI-VAR. With regard to the selection of the target sequence the groups that had higher percentages of selection in all sessions were DT-CON and DT/IRI-VAR, respectively within each procedure. It was noted that both procedures produced the selection of the target sequence, but is seems that the use of IRI produced a more variable performance, when it was directly reinforced, allowing the selection of the target sequence to occur more rapidly<br>O objetivo do estudo foi avaliar a efetividade de dois procedimentos, Tentativa Discreta (TD) e Tentativa Discreta com Intervalo entre as Respostas (TD/IRI), na produção da variabilidade comportamental em diferentes condições (diretamente reforçada e induzida) e averiguar que condição, em cada procedimento, mais facilitaria a seleção de uma sequência de baixa probabilidade inicial. Selecionou-se 18 universitários com um desempenho na linha de base, medido pelo índice U, igual ou inferior a 0,5. Estes foram divididos nos dois procedimentos e subdivididos em três grupos com três participantes (VAR, ACO e CON). A tarefa consistia em formar figuras na tela do computador pressionando duas teclas (direita e esquerda) de teclados laterais. A unidade comportamental era quatro respostas às teclas. Nos dois procedimentos apresentava-se um pedaço da figura, um tom e 0,5 segundo, caso a sequência fosse passível de reforço, e um timeout de 1,0 segundo, caso não fosse. Somente no TD/IRI havia um IRI de 0,5 segundo após as três primeiras respostas da sequência. O experimento continha três fases. Na Fase 1, linha de base, vigorava o reforçamento contínuo (CRF) das 16 sequências. Para dois grupos (TD-VAR e TD/IRI-VAR) na Fase 2 havia o reforçamento direto da variabilidade, para 15 sequências, no qual a sequência menos frequente e menos recente teria maior probabilidade de ser reforçada, e CRF de uma sequência alvo (sequência menos frequente na linha de base). Na Fase 3, havia a distribuição acoplada dos reforços da fase anterior para as 15 sequências e CRF de outra sequência alvo. Para os grupos TD-ACO e TD/IRI-ACO a ordem de exposição às fases foi inversa, visto que na Fase 2 a distribuição de reforços foi acoplada ao desempenho dos participantes dos grupos VAR. Nos grupos TD-CON e TD/IRI-CON havia somente o CRF da sequência alvo nas duas fases. Os resultados mostraram que a variabilidade aumentou na primeira sessão da Fase 2 para todos os participantes. O grupo TD-ACO foi o que apresentou maior índices de variabilidade dentro deste procedimento. Já no TD/IRI, isto foi verdadeiro para o grupo TD/IRI-VAR. Com relação à seleção da sequência alvo, os grupos que apresentaram maiores porcentagens de seleção em todas as sessões foram TD-CON e TD/IRI-VAR, respectivamente dentro de cada procedimento. Notou-se que os dois procedimentos produziram seleção da sequência alvo, mas parece que o uso do IRI produziu um responder mais variável, quando este foi diretamente reforçado, o que possibilitou que a seleção da sequência alvo ocorresse mais rapidamente
34
Lundberg, Mattias, and Johan Söderlund. "Flow simulation of Body In White : Optimization of the production sequence and identification of bottlenecks at Volvo Trucks plant in Umeå." Thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-136584.
Повний текст джерелаАнотація:
In this study, a discrete event model was created and used in combination with an optimization method to find the optimal production sequence at Volvo Group’s cab plant in Umeå. The optimization was performed with a heuristic approach combined with a genetic search algorithm. The result provides an optimized production sequence with an increased production performance. Potential improvements in the production flow were identified to significantly increase the throughput. Volvo Group Trucks Operations plant in Umeå is a part of Volvo Group AB and is one of the world’s largest manufacturers of heavy duty trucks. The plant in Umeå produces cab bodies and consists of Stamping and Part production, Body In White and the Paint Shop. As of today, the plant produces about XXX produced cabs per week with the goal to achieve the invested capacity of 1666 produced cabs per week. The production is structured with a daily scheduling of the cab production. Today cabs are produced in the same sequence as the orders are received. There has been an investigation regarding the production capacity in the past but further investigation was required due to insufficient data available at the time. Volvo wants to investigate the potential improvements in the BIW unit, increase the production rate and reach the level of invested capacity. Therefore, this project was introduced which led to the following problem definition: “What is the optimal production sequence in the BIW unit?” To further find potential improvements, a secondary problem definition got formulated: “How would the production sequence be affected if the current biggest bottleneck were removed?” The objective was achieved with Discrete Event Simulation, where heuristic based sequences were optimized in a genetic search algorithm. This resulted in identified sequence patterns, which were used to improve the production sequence. When analyzing the model, the floor subflow was identified as the biggest bottleneck in the production. A general suggestion would be to avoid large batches due to significant risk of limiting the throughput. Results suggest that sequences should be in cycles of 3FH-1FM with segments of batches as long as the floor buffer does not run out of parts. This resulted in a potential increased throughput of 3.2-3.7% for the Body In White. If the biggest bottleneck were to be removed, there would be a potential production increase by roughly 10% compared to the production today.<br>I den här studien skapades en diskret händelsestyrd modell som användes i kombination med en optimeringsmetod för att ta reda på den optimala produktionssekvensen i Volvokoncernens hyttfabrik i Umeå. Optimeringen utfördes genom heuristiker i kombination med en genetisk sökalgoritm. Detta resulterade i en optimerad produktionssekvens med en ökad takt gentemot dagsläget. Potentiella förbättringar i produktionsflödet kunde identifieras för att signifikant öka genomströmningen av hytter. Volvo Group Trucks Operations hyttfabrik i Umeå är en del av Volvo Group AB och är en världsledande tillverkare av tunga lastbilar. Fabriken i Umeå tillverkar lastbilshytter med plåtbearbetning, presshall, sammansättning och måleri. I dagsläget producerar fabriken ungefär XXX hytter i veckan med målsättningen att komma upp i den investerade kapaciteten: 1666 producerade hytter i veckan. Produktionen är upplagd med planering av hyttproduktion på daglig basis. Idag produceras hytterna inte i någon specifik sekvens utan produceras enligt samma ordning som ingående orderkö. En studie kring produktionskapaciteten har tidigare utförts, dock finns behovet av ytterligare undersökning då tillgängligheten av väsentlig data för att kunna utföra studien varit begränsad vid tidigare skeden. Av den anledningen vill Volvo utföra en undersökning för att hitta potentiella förbättringar i BIW enheten, för att således uppnå den investerade kapaciteten. Därav introducerades detta projekt med följande problemdefinition: “Vad är den optimala produktionssekvensen i BIW enheten?” För att hitta ytterligare förbättringar, så formulerades en sekundär problemdefinition: “Hur skulle produktionssekvensen påverkas om den största flaskhalsen eliminerades?” Målet nåddes med diskret händelsestyrd simulering, där optimering utfördes genom heuristiskt baserade sekvenser tillsammans med en genetisk sökalgoritm. Identifierade mönster användes sedan för att förbättra produktionssekvensen. Vid analysering av modellen identifierades floor-flödet som den största flaskhalsen i produktionen. Ett generellt förslag är att undvika stora batcher då detta innebär en signifikant risk att begränsa genomströmningen av hytter. Resultatet indikerar att sekvenser bör bestå av cykler om 3FH-1FM, med segment av batcher så länge floor-buffrarna inte är tomma. Detta resulterade i en potentiellt ökad genomströmning med 3,2-3,7% per vecka för BIW enheten. Om den största flaskhalsen i floor-flödet skulle elimineras så kan produktionen potentiellt öka med 10% jämfört mot dagens produktionstakt.
35
Grymel, Martin-Thomas. "Error control with binary cyclic codes." Thesis, University of Manchester, 2013. https://www.research.manchester.ac.uk/portal/en/theses/error-control-with-binary-cyclic-codes(a5750b4a-e4d6-49a8-915b-3e015387ad36).html.
Повний текст джерелаАнотація:
Error-control codes provide a mechanism to increase the reliability of digital data being processed, transmitted, or stored under noisy conditions. Cyclic codes constitute an important class of error-control code, offering powerful error detection and correction capabilities. They can easily be generated and verified in hardware, which makes them particularly well suited to the practical use as error detecting codes.A cyclic code is based on a generator polynomial which determines its properties including the specific error detection strength. The optimal choice of polynomial depends on many factors that may be influenced by the underlying application. It is therefore advantageous to employ programmable cyclic code hardware that allows a flexible choice of polynomial to be applied to different requirements. A novel method is presented in this thesis to realise programmable cyclic code circuits that are fast, energy-efficient and minimise implementation resources.It can be shown that the correction of a single-bit error on the basis of a cyclic code is equivalent to the solution of an instance of the discrete logarithm problem. A new approach is proposed for computing discrete logarithms; this leads to a generic deterministic algorithm for analysed group orders that equal Mersenne numbers with an exponent of a power of two. The algorithm exhibits a worst-case runtime in the order of the square root of the group order and constant space requirements.This thesis establishes new relationships for finite fields that are represented as the polynomial ring over the binary field modulo a primitive polynomial. With a subset of these properties, a novel approach is developed for the solution of the discrete logarithm in the multiplicative groups of these fields. This leads to a deterministic algorithm for small group orders that has linear space and linearithmic time requirements in the degree of defining polynomial, enabling an efficient correction of single-bit errors based on the corresponding cyclic codes.
36
Krejčí, Michal. "Komprese dat." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2009. http://www.nusl.cz/ntk/nusl-217934.
Повний текст джерелаАнотація:
This thesis deals with lossless and losing methods of data compressions and their possible applications in the measurement engineering. In the first part of the thesis there is a theoretical elaboration which informs the reader about the basic terminology, the reasons of data compression, the usage of data compression in standard practice and the division of compression algorithms. The practical part of thesis deals with the realization of the compress algorithms in Matlab and LabWindows/CVI.
37
Kornfeil, Vojtěch. "Soubor úloh pro kurs Sběr, analýza a zpracování dat." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2008. http://www.nusl.cz/ntk/nusl-217707.
Повний текст джерелаАнотація:
This thesis proposes tasks of exercises for mentioned course and design and creation of automated evaluation system for these exercises. This thesis focuses on discussion and exemplary solutions of possible tasks of each exercise and description of created automated evaluation system. For evaluation program are made tests with chosen special data sets, which will prove it’s functionality in general data sets.
38
Arulalan, M. R. "Some Applications Of Integer Sequences In Digital Signal Processing And Their Implications On Performance And Architecture." Thesis, 2011. https://etd.iisc.ac.in/handle/2005/2126.
Повний текст джерелаАнотація:
Contemporary research in digital signal processing (DSP) is focused on issues of computational complexity, very high data rate and large quantum of data. Thus, the success in newer applications and areas hinge on handling these issues. Conventional ways to address these challenges are to develop newer structures like Multirate signal processing, Multiple Input Multiple Output(MIMO), bandpass sampling, compressed domain sensing etc. In the implementation domain, the approach is to look at floating point over fixed point representation and / or longer wordlength etc., related to number representations and computations. Of these, a simple approach is to look at number representation, perhaps with a simple integer. This automatically guarantees accuracy and zero quantization error as well as longer wordlength. Thus, it is necessary and interesting to explore viable DSP alternatives that can reduce complexity and yet match the required performance. The main aim of this work is to highlight the importance, use and analysis of integer sequences. Firstly, the thesis explores the use of integer sequences as windowing functions. The results of these investigations show that integer sequences and their convolution, indeed, outperform many of the classical real valued window functions in terms of mainlobe width, sidelobe attenuation etc. Secondly, the thesis proposes techniques to approximate discrete Gaussian distribution using integer sequences. The key idea is to convolve symmetrized integer sequences and examine the resulting profiles. These profiles are found to approximate discrete Gaussian distribution with a mean square error of the order of 10−8 or less. While looking at integer sequences to approximate discrete Gaussian, Fibonacci sequence was found to exhibit some interesting properties. The third part of the thesis proves certain fascinating optimal probabilistic limit properties (mean and variance) of Fibonacci sequence. The thesis also provides complete generalization of these properties to probability distributions generated by second order linear recurrence relation with integer coefficients and any kth order linear recurrence relation with unit coefficients. In addition to the above, the thesis also throws light on possible architectural implications of using integer sequences in DSP applications and ideas for further exploration.
39
Arulalan, M. R. "Some Applications Of Integer Sequences In Digital Signal Processing And Their Implications On Performance And Architecture." Thesis, 2011. http://etd.iisc.ernet.in/handle/2005/2126.
Повний текст джерелаАнотація:
Contemporary research in digital signal processing (DSP) is focused on issues of computational complexity, very high data rate and large quantum of data. Thus, the success in newer applications and areas hinge on handling these issues. Conventional ways to address these challenges are to develop newer structures like Multirate signal processing, Multiple Input Multiple Output(MIMO), bandpass sampling, compressed domain sensing etc. In the implementation domain, the approach is to look at floating point over fixed point representation and / or longer wordlength etc., related to number representations and computations. Of these, a simple approach is to look at number representation, perhaps with a simple integer. This automatically guarantees accuracy and zero quantization error as well as longer wordlength. Thus, it is necessary and interesting to explore viable DSP alternatives that can reduce complexity and yet match the required performance. The main aim of this work is to highlight the importance, use and analysis of integer sequences. Firstly, the thesis explores the use of integer sequences as windowing functions. The results of these investigations show that integer sequences and their convolution, indeed, outperform many of the classical real valued window functions in terms of mainlobe width, sidelobe attenuation etc. Secondly, the thesis proposes techniques to approximate discrete Gaussian distribution using integer sequences. The key idea is to convolve symmetrized integer sequences and examine the resulting profiles. These profiles are found to approximate discrete Gaussian distribution with a mean square error of the order of 10−8 or less. While looking at integer sequences to approximate discrete Gaussian, Fibonacci sequence was found to exhibit some interesting properties. The third part of the thesis proves certain fascinating optimal probabilistic limit properties (mean and variance) of Fibonacci sequence. The thesis also provides complete generalization of these properties to probability distributions generated by second order linear recurrence relation with integer coefficients and any kth order linear recurrence relation with unit coefficients. In addition to the above, the thesis also throws light on possible architectural implications of using integer sequences in DSP applications and ideas for further exploration.
40
Vivek, Srinivas V. "On A Cubic Sieve Congruence Related To The Discrete Logarithm Problem." Thesis, 2010. https://etd.iisc.ac.in/handle/2005/1996.
Повний текст джерелаАнотація:
There has been a rapid increase interest in computational number theory ever since the invention of public-key cryptography. Various attempts to solve the underlying hard problems behind public-key cryptosystems has led to interesting problems in computational number theory. One such problem, called the cubic sieve congruence problem, arises in the context of the cubic sieve method for solving the discrete logarithm problem in prime fields.
The cubic sieve method requires a nontrivial solution to the Cubic Sieve Congruence (CSC)x3 y2z (mod p), where p is a given prime. A nontrivial solution must satisfy
x3 y2z (mod p), x3 ≠ y2z, 1≤ x, y, z < pα ,
where α is a given real number ⅓ < α ≤ ½. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC.
This thesis is concerned with the CSC problem. Recently, the parametrization x y2z (mod p) and y υ3z (mod p) of CSC was introduced. We give a deterministic polynomial-time (O(ln3p) bit-operations) algorithm to determine, for a given υ, a nontrivial solution to CSC, if one exists. Previously it took Õ(pα) time to do this. We relate the CSC problem to the gap problem of fractional part sequences. We also show in the α = ½ case that for a certain class of primes the CSC problem can be solved deterministically Õ(p⅓) time compared to the previous best of Õ(p½). It is empirically observed that about one out of three primes are covered by this class, up to 109
41
Vivek, Srinivas V. "On A Cubic Sieve Congruence Related To The Discrete Logarithm Problem." Thesis, 2010. http://etd.iisc.ernet.in/handle/2005/1996.
Повний текст джерелаАнотація:
There has been a rapid increase interest in computational number theory ever since the invention of public-key cryptography. Various attempts to solve the underlying hard problems behind public-key cryptosystems has led to interesting problems in computational number theory. One such problem, called the cubic sieve congruence problem, arises in the context of the cubic sieve method for solving the discrete logarithm problem in prime fields.
The cubic sieve method requires a nontrivial solution to the Cubic Sieve Congruence (CSC)x3 y2z (mod p), where p is a given prime. A nontrivial solution must satisfy
x3 y2z (mod p), x3 ≠ y2z, 1≤ x, y, z < pα ,
where α is a given real number ⅓ < α ≤ ½. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC.
This thesis is concerned with the CSC problem. Recently, the parametrization x y2z (mod p) and y υ3z (mod p) of CSC was introduced. We give a deterministic polynomial-time (O(ln3p) bit-operations) algorithm to determine, for a given υ, a nontrivial solution to CSC, if one exists. Previously it took Õ(pα) time to do this. We relate the CSC problem to the gap problem of fractional part sequences. We also show in the α = ½ case that for a certain class of primes the CSC problem can be solved deterministically Õ(p⅓) time compared to the previous best of Õ(p½). It is empirically observed that about one out of three primes are covered by this class, up to 109
42
Chang, Chih-Yang, and 張智揚. "Digital Filter Design Using Discrete Prolate Spheroidal Sequence." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/x9735y.
Повний текст джерелаАнотація:
碩士<br>國立高雄第一科技大學<br>電子與資訊工程研究所<br>96<br>In many communication and signal processing applications, the discrete prolate spheroidal sequences are optimum waveforms that are time-limited sequences with maximum energy concentration in a finite frequency interval. In this thesis ,we use the characterization of discrete prolate spheroidal sequences to design all-pole IIR filter and discrete prolate spheroidal FIR filter. Moreover the discrete prolate spheroidal window is optimum window whose mainlobe has maximum energy concentration in the frequency domain and the mainlobe bandwidth can be adjustable. And its sidelobe has large attenuation. The discrete prolate spheroidal windows can be extended to N-dimensional(N-D) case. The N-D windows have maximum energy concentration in a general nonseparable N-D passband. These windows can be applited to design multidimensional filter and optimal convolution functions. In this thesis, we also use the discrete prolate spheroidal windows to design 1-D and 2-D FIR filters.
43
Talaei, Farnoosh. "Wireless channel estimation and channel prediction for MIMO communication systems." Thesis, 2017. https://dspace.library.uvic.ca//handle/1828/8923.
Повний текст джерелаАнотація:
In this dissertation, channel estimation and channel prediction are studied for wireless communication systems. Wireless communication for time-variant channels becomes more important by the fast development of intelligent transportation systems which motivates us to propose a reduced rank channel estimator for time-variant frequency-selective high-speed railway (HSR) systems and a reduced rank channel predictor for fast time-variant flat fading channels. Moreover, the potential availability of large bandwidth channels at mm-wave frequencies and the small wavelength of the mm-waves, offer the mm-wave massive multiple-input multiple-output (MIMO) communication as a promising technology for 5G cellular networks. The high fabrication cost and power consumption of the radio frequency (RF) units at mm-wave frequencies motivates us to propose a low-power hybrid channel estimator for mm-wave MIMO orthogonal frequency-division multiplexing (OFDM) systems.
The work on HSR channel estimation takes advantage of the channel's restriction to low dimensional subspaces due to the time, frequency and spatial correlation of the channel and presents a low complexity linear minimum mean square error (LMMSE) estimator for MIMO-OFDM HSR channels. The channel estimator utilizes a four-dimensional (4D) basis expansion channel model obtained from band-limited generalized discrete prolate spheroidal (GDPS) sequences. Exploiting the channel's band-limitation property, the proposed channel estimator outperforms the conventional interpolation based least square (LS) and MMSE estimators in terms of estimation accuracy and computational complexity, respectively. Simulation results demonstrate the robust performance of the proposed estimator for different delay, Doppler and angular spreads.
Channel state information (CSI) is required at the transmitter for improving the performance gain of the spatial multiplexing MIMO systems through linear precoding.
In order to avoid the high data rate feedback lines, which are required in fast time-variant channels for updating the transmitter with the rapidly changing CSI, a subframe-wise channel tracking scheme is presented. The proposed channel predictor is based on an assumed DPS basis expansion model (DPS-BEM) for exploiting the variation of the channel coefficients inside each sub-frame and an autoregressive (AR) model of the basis coefficients over each transmitted frame. The proposed predictor properly exploits the channel's restriction to low dimensional subspaces for reducing
the prediction error and the computational complexity. Simulation results demonstrate
that the proposed channel predictor out-performs the DPS based minimum energy (ME) predictor for different ranges of normalized Doppler frequencies and has better performance than the conventional Wiener predictor for slower time-variant channels and almost the similar performance to it for very fast time-variant channels with the reduced amount of computational complexity.
The work on the hybrid mm-wave channel estimator considers the sparse nature of
the mm-wave channel in angular domain and leverages the compressed sensing (CS)
tools for recovering the angular support of the MIMO-OFDM mm-wave channel. The angular channel is treated in a continuous framework which resolves the limited
angular resolution of the discrete sparse channel models used in the previous CS based
channel estimators. The power leakage problem is also addressed by modeling the
continuous angular channel as a multi-band signal with the bandwidth of each sub-band
being proportional to the amount of power leakage. The RF combiner is designed
to be implemented using a network of low-power switches for antenna subset selection
based on a multi-coset sampling pattern. Simulation results validate the effectiveness
of the proposed hybrid channel estimator both in terms of the estimation accuracy
and the RF power consumption.<br>Graduate
44
Ali, Akbarian Mohammad Sadegh. "Deep sequence learning for video anticipation: from discrete and deterministic to continuous and stochastic." Phd thesis, 2020. http://hdl.handle.net/1885/213305.
Повний текст джерелаАнотація:
Video anticipation is the task of predicting one/multiple future representation(s) given limited, partial observation. This is a challenging task due to the fact that given limited observation, the future representation can be highly ambiguous. Based on the nature of the task, video anticipation can be considered from two viewpoints: the level of details and the level of determinism in the predicted future. In this research, we start from anticipating a coarse representation of a deterministic future and then move towards predicting continuous and fine-grained future representations of a stochastic process. The example of the former is video action anticipation in which we are interested in predicting one action label given a partially observed video and the example of the latter is forecasting multiple diverse continuations of human motion given partially observed one.
In particular, in this thesis, we make several contributions to the literature of video anticipation. Firstly, we introduce a general action anticipation framework in which, given very limited observation, the goal is to predict the action label as early as possible. This task is highly critical in scenarios where one needs to react before the action is finalized. This is, for instance, the case of automated driving, where a car needs to, e.g., avoid hitting pedestrians and respect traffic lights. Our work builds on the following observation: a good anticipation model requires (i) a good video representation that is discriminative enough even in presence of partial observation; and (ii) a learning paradigm that not only encourages correct predictions as early as possible, but also accounts for the fact that the future is highly ambiguous. On publicly available action recognition datasets, our proposed method is able to predict markedly accurate action categories given very limited observation, e.g., less than 2\% of the videos of UCF-101, outperforming the state of the art methods by a large margin.
Secondly, we proposed an action anticipation in driving scenarios. Since there was no anticipation-specific dataset covering generic driving scenarios, as part of our second contribution, we introduced a large-scale video anticipation dataset, covering 5 generic driving scenarios, with a total of 25 distinct action classes. It contains videos acquired in various driving conditions, weathers, daytimes and environments, complemented with a common and realistic set of sensor measurements. .
We then focus on the continuous future prediction problem on tasks that are stochastic in nature; given one observation, multiple plausible futures are likely. In particular, we target the problem of human motion prediction, i.e., the task of predicting future3D human poses given a sequence of observed ones. To this end, in our third contribution, we propose a novel diverse human motion prediction framework based on variational autoenecoders (VAEs). In this approach, we particularly propose a novel stochastic conditioning scheme that is well-suited for scenarios where we are dealing with a deterministic datasets, with strong conditioning signals, and expressive decoders. Through extensive experiments, we show that our approach performs much better than existing approaches and standard practices in training a conditional VAE.
Finally, in the fourth contribution, we propose a conditional VAE framework that solves two main issues of a standard conditional VAE: (i) conditioning and sampling the latent variables are two independent processes, and (ii) the prior distribution is set to be unconditional in practice, however, it should be conditioned on the conditioning signal as elaborated in the evidence lower bound of the data likelihood. In our proposed approach, we address both of these issues that leads to substantial improvement in the quality of generated samples.
45
曾仁文. "A study of the discrete prolate spheroidal sequence and its applications in digital signal processing." Thesis, 1990. http://ndltd.ncl.edu.tw/handle/92327663155828354149.
Повний текст джерела
46
Williams, Aaron Michael. "Shift gray codes." Thesis, 2009. http://hdl.handle.net/1828/1966.
Повний текст джерелаАнотація:
Combinatorial objects can be represented by strings, such as 21534 for the permutation (1 2) (3 5 4), or 110100 for the binary tree corresponding to the balanced parentheses (()()). Given a string s = s1 s2 sn, the right-shift operation shift(s, i, j) replaces the substring si si+1..sj by si+1..sj si. In other words, si is right-shifted into position j by applying the permutation (j j−1 .. i) to the indices of s. Right-shifts include prefix-shifts (i = 1) and adjacent-transpositions (j = i+1). A fixed-content language is a set of strings that contain the same multiset of symbols. Given a fixed-content language, a shift Gray code is a list of its strings where consecutive strings differ by a shift. This thesis asks if shift Gray codes exist for a variety of combinatorial objects. This abstract question leads to a number of practical answers.
The first prefix-shift Gray code for multiset permutations is discovered, and it provides the first algorithm for generating multiset permutations in O(1)-time while using O(1) additional variables. Applications of these results include more efficient exhaustive solutions to stacker-crane problems, which are natural NP-complete traveling salesman variants. This thesis also produces the fastest algorithm for generating balanced parentheses in an array, and the first minimal-change order for fixed-content necklaces and Lyndon words.
These results are consequences of the following theorem: Every bubble language has a right-shift Gray code. Bubble languages are fixed-content languages that are closed under certain adjacent-transpositions. These languages generalize classic combinatorial objects: k-ary trees, ordered trees with fixed branching sequences, unit interval graphs, restricted Schr oder and Motzkin paths, linear-extensions of B-posets, and their unions, intersections, and quotients. Each Gray code is circular and is obtained from a new variation of lexicographic order known as cool-lex order.
Gray codes using only shift(s, 1, n) and shift(s, 1, n−1) are also found for multiset permutations. A universal cycle that omits the last (redundant) symbol from each permutation is obtained by recording the first symbol of each permutation in this Gray code. As a special case, these shorthand universal cycles provide a new fixed-density analogue to de Bruijn cycles, and the first universal cycle for the "middle levels" (binary strings of length 2k + 1 with sum k or k + 1).