Tesis sobre el tema "Dynamic programming"
Siga este enlace para ver otros tipos de publicaciones sobre el tema: Dynamic programming.
Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros
Consulte los 50 mejores tesis para su investigación sobre el tema "Dynamic programming".
Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.
También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.
Explore tesis sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.
1
Zhang, Yan. "Dynamic programming speedups /". View abstract or full-text, 2007. http://library.ust.hk/cgi/db/thesis.pl?CSED%202007%20ZHANGY.
Texto completo
2
Weimann, Oren. "Accelerating dynamic programming". Thesis, Massachusetts Institute of Technology, 2009. http://hdl.handle.net/1721.1/53302.
Texto completoResumen
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.Cataloged from PDF version of thesis.
Includes bibliographical references (p. 129-136).
Dynamic Programming (DP) is a fundamental problem-solving technique that has been widely used for solving a broad range of search and optimization problems. While DP can be invoked when more specialized methods fail, this generality often incurs a cost in efficiency. We explore a unifying toolkit for speeding up DP, and algorithms that use DP as subroutines. Our methods and results can be summarized as follows. - Acceleration via Compression. Compression is traditionally used to efficiently store data. We use compression in order to identify repeats in the table that imply a redundant computation. Utilizing these repeats requires a new DP, and often different DPs for different compression schemes. We present the first provable speedup of the celebrated Viterbi algorithm (1967) that is used for the decoding and training of Hidden Markov Models (HMMs). Our speedup relies on the compression of the HMM's observable sequence. - Totally Monotone Matrices. It is well known that a wide variety of DPs can be reduced to the problem of finding row minima in totally monotone matrices. We introduce this scheme in the context of planar graph problems. In particular, we show that planar graph problems such as shortest paths, feasible flow, bipartite perfect matching, and replacement paths can be accelerated by DPs that exploit a total-monotonicity property of the shortest paths. - Combining Compression and Total Monotonicity. We introduce a method for accelerating string edit distance computation by combining compression and totally monotone matrices.
(cont.) In the heart of this method are algorithms for computing the edit distance between two straight-line programs. These enable us to exploits the compressibility of strings, even if each string is compressed using a different compression scheme. - Partial Tables. In typical DP settings, a table is filled in its entirety, where each cell corresponds to some subproblem. In some cases, by changing the DP, it is possible to compute asymptotically less cells of the table. We show that [theta](n³) subproblems are both necessary and sufficient for computing the similarity between two trees. This improves all known solutions and brings the idea of partial tables to its full extent. - Fractional Subproblems. In some DPs, the solution to a subproblem is a data structure rather than a single value. The entire data structure of a subproblem is then processed and used to construct the data structure of larger subproblems. We suggest a method for reusing parts of a subproblem's data structure. In some cases, such fractional parts remain unchanged when constructing the data structure of larger subproblems. In these cases, it is possible to copy this part of the data structure to the larger subproblem using only a constant number of pointer changes. We show how this idea can be used for finding the optimal tree searching strategy in linear time. This is a generalization of the well known binary search technique from arrays to trees.
by Oren Weimann.
Ph.D.
3
Wong, K. H. "Dynamic programming in pattern recognition". Thesis, University of Cambridge, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.383059.
Texto completo
4
Moor, Oege de. "Categories, relations and dynamic programming". Thesis, University of Oxford, 1991. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.305600.
Texto completo
5
Hinchliffe, Mark. "Dynamic modelling using genetic programming". Thesis, University of Newcastle Upon Tyne, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.391407.
Texto completo
6
Gallia, Jason. "Protein identification by dynamic programming". Diss., Online access via UMI:, 2009.
Buscar texto completo
7
Batra, Jatin. "Dynamic programming for scheduling problems". Thesis, IIT Delhi, 2019. http://eprint.iitd.ac.in:80//handle/2074/8050.
Texto completo
8
Evers, Dirk J. "RNA folding via algebraic dynamic programming". [S.l. : s.n.], 2003. http://deposit.ddb.de/cgi-bin/dokserv?idn=968564844.
Texto completo
9
Archer, Grant R. "Seismic velocity analysis using dynamic programming /". Title page, contents and abstract only, 1987. http://web4.library.adelaide.edu.au/theses/09S.B/09s.ba671.pdf.
Texto completo
10
Sung, Joo-Ho. "Dynamic programming approaches to pension funding". Thesis, City University London, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.361860.
Texto completo
11
Khalaf, Rania Y. (Rania Yousef) 1978. "Multi-person tracking using dynamic programming". Thesis, Massachusetts Institute of Technology, 2001. http://hdl.handle.net/1721.1/16768.
Texto completoResumen
Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001.Includes bibliographical references (p. 75-77).
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
by Rania Y. Khalaf.
M.Eng.
12
Sadiq, Mohammad. "Approximate Dynamic Programming Methods in HEVs". Thesis, KTH, Maskinkonstruktion (Inst.), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-182762.
Texto completoResumen
Hybrid Electric Vehicles (HEV) have been gaining popularity worldwide for their efficient fuel consumption and therefore an overall reduction in the oil demand. This greatly benefits the environment since this leads to lesser emissions and hence lower greenhouse effect. Therefore research in this field is very active with a demand for new and better fuel consumption strategies. Many different methods for the energy management of HEV are being used, one particular method which promises global optimality is Dynamic Programming. Dynamic Programming yields a global optimum results but suffers from high computation cost. Among the different methods to counter this curse of dimensionality one of the popular is Approximate Dynamic Programming (ADP). This thesis investigates the literature on the different methods of ADP applied to HEV and an implementation showing a reduction in the computation time for a specific HEV energy management problem.Elhybridfordon (HEV) har ökat i popularitet över hela världen pga sin låga bränsleförbrukning, vilket har minskat efterfrågan på olja. Detta gynnar i hög grad miljön, eftersom detta leder till mindre utsläpp och följaktligen en lägre växthuseffekt. Därför pågår aktiv forskning inom detta område med en ökad efterfrågan på nya och bättre strategier för bränsleförbrukning. Många olika metoder för energihantering av HEV använder en särskild metod; dynamisk programmering. Dynamisk programmering ger ett optimalt globalt resultat men på bekostnad av längre beräkningstider. Den mest använda metoden för att motverka denna typ av problematik i högdimensionella system är Approximate Dynamic Programming (ADP). Denna avhandling undersöker och beskriver litteraturen på de olika metoderna för ADP tillämpade på HEV samt en genomförandefas som visar en minskning av beräkningstiden för ett HEV-problem gällande energihantering.
13
Ramalingam, Mohan Kumar. "Moving Horizon Estimation with Dynamic Programming". Cleveland State University / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=csu1386778712.
Texto completo
14
Gaddoni, Giacomo. "Modeling of Evolutionary Cancer Dynamics and Optimal Treatment via Dynamic Programming". Master's thesis, Alma Mater Studiorum - Università di Bologna, 2021.
Buscar texto completoResumen
Cancer is one of the biggest challenges in healthcare. Fast diagnosis and personalized pharmacological therapies are essential for lowering the mortality rate. In this thesis, we propose a general-purpose model for cancer and an optimal control strategy to minimize its volume. Firstly, we analyze the literature about cancer in the System and Control community and produce a taxonomy of cancer typologies. We identify four main behaviors arising in these models: growth, mutation, migration, and drug response. After this preliminary analysis, we propose a cancer treatment model based on Ordinary Differential Equations (ODEs) and Evolutionary Game Theory, that captures these dynamics more generally. ODEs provide a framework for lumped-parameters representations, and Evolutionary Game Theory provides tools to describe competitive behaviors typical of these cell populations. Starting from this taxonomy, we chose a model representable with a 2-node graph that expressed all the dynamics of cancer processes. We studied the model, discretized it, and applied an optimal control method based on Differential Dynamic Programming (DDP). Bounded and unbounded DDP were ineffective. It was necessary to introduce regularized DDP via adaptive shift. With this algorithm, the results are promising: the system is successfully stabilized in the origin. It is also possible to control the system, driving it between two equilibria, tracking a demanded trajectory. Most of the testing was done in MATLAB. Then, the project was ported to Python. This was done to facilitate future expansion of the model and control strategies through scientific analysis toolboxes and frameworks.
15
Diep, Vivian Chan. "Me.TV : a visual programming language and interface for dynamic media programming". Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/101844.
Texto completoResumen
Thesis: S.M., Massachusetts Institute of Technology, School of Architecture and Planning, Program in Media Arts and Sciences, 2015.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 59-60).
The culture of televised media experiences has changed very little since the time it began in the 1930s, but new internet technologies, like Netflix, Hulu, and Youtube, are now quickly forcing major change. Although these new internet technologies have given the viewer more control than the historical dial, they have also left behind some of the greatest contributions of traditional television. These contributions include not just the well-favored simplicity of use, but also the sense of social experience and connectedness, the ease and continuity of scheduled programming, and the understanding that television is now, current, and pulsing. This thesis presents Me.TV, a web platform that combines the benefits of traditional television and on-demand viewing for a new experience that allows us to let go, watch the same channels as our friends, flip our preferences around, get constant, current content, and still have control over the type and timing of content. To make this experience possible, we present a visual programming language at the center of the Me.TV platform that enables users to create complex rules with simple interactions. The visual language constructs allow users to create static preferences, such as genre constraints, and plan for non-static ones, such as a current mood, in as many channels as they want. To support the Me.TV programming language, the platform comprises of an editor, translation engine, application programming interface, video player and navigation dashboard, which we prototype in this thesis as a javascript web application. Work reported herein was funded by the Media Lab Consortium and the Ultimate Media Program.
by Vivian Chan Diep.
S.M.
16
Kaminsky, Andrew D. "Dynamic channel allocation". Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2003. http://library.nps.navy.mil/uhtbin/hyperion-image/03sep%5FKaminsky.pdf.
Texto completo
17
Mekarapiruk, Wichaya. "Simultaneous optimal parameter selection and dynamic optimization using iterative dynamic programming". Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/NQ58926.pdf.
Texto completo
18
Calvo, Diego R. y Michail Musatov. "Pricing American Style Asian OptionsUsing Dynamic Programming". Thesis, Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-9880.
Texto completoResumen
The objective of this study is to implement a Java applet for calculating Bermudan/American-Asian call option prices and to obtain their respective optimal exercise strategies. Additionally, the study presents a computational time analysis and the effect of the variables on the option price.
19
Lamond, Bernard Fernand. "Matrix methods in queueing and dynamic programming". Thesis, University of British Columbia, 1985. http://hdl.handle.net/2429/27124.
Texto completoResumen
We investigate some modern matrix methods for the solution of finite state stochastic models with an infinite time horizon. Markov and semi-Markov decision processes and finite queues in tandem with exponential service times are considered. The methods are based on the Drazin generalized inverse and use matrix decomposition.
Unlike the related Jordan canonical form, the decompositions considered are numerically tractable and use real arithmetic when the original matrix has real entries. The spectral structure of the transition matrix of a Markov chain, deduced from non-negative matrix theory, provides a decomposition from which the limiting and deviation matrices are directly obtained.
The matrix decomposition approach to the solution of Markov reward processes provides a new, simple derivation of the Laurent expansion of the resolvent. Many other basic results of dynamic programming are easily derived in a similar fashion and the extension to semi-Markov decision processes is straightforward. Further, numerical algorithms for matrix decomposition can be used efficiently in the policy iteration method, for evaluating the terms of the Laurent series.
The problem of finding the stationary distribution of a system with two finite queues in tandem, when the service times have an exponential distribution, can also be expressed in matrix form. Two numerical methods, one iterative and one using matrix decomposition, are reviewed for computing the stationary probabilities. Job-local-balance is used to derive some bounds on the call congestion. A numerical investigation of the bounds is included. It suggests that the bounds are insensitive to the distribution of the service times.Business, Sauder School of
Graduate
20
Axelsson, Nils. "Dynamic Programming Algorithms for Semantic Dependency Parsing". Thesis, Linköpings universitet, Interaktiva och kognitiva system, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-138594.
Texto completoResumen
Dependency parsing can be a useful tool to allow computers to parse text. In 2015, Kuhlmann and Jonsson proposed a logical deduction system that parsed to non-crossing dependency graphs with an asymptotic time complexity of O(n3), where “n” is the length of the sentence to parse. This thesis extends the deduction system by Kuhlmann and Jonsson; the extended deduction system introduces certain crossing edges, while maintaining an asymptotic time complexity of O(n4). In order to extend the deduction system by Kuhlmann and Jonsson, fifteen logical item types are added to the five proposed by Kuhlmann and Jonsson. These item types allow the deduction system to intro-duce crossing edges while acyclicity can be guaranteed. The number of inference rules in the deduction system is increased from the 19 proposed by Kuhlmann and Jonsson to 172, mainly because of the larger number of combinations of the 20 item types. The results are a modest increase in coverage on test data (by roughly 10% absolutely, i.e. approx. from 70% to 80%), and a comparable placement to that of Kuhlmann and Jonsson by the SemEval 2015 task 18 metrics. By the method employed to introduce crossing edges, derivational uniqueness is impossible to maintain. It is hard to defien the graph class to which the extended algorithm, QAC, parses, and it is therefore empirically compared to 1-endpoint crossing and graphs with a page number of two or less, compared to which it achieves lower coverage on test data. The QAC graph class is not limited by page number or crossings. The takeaway of the thesis is that extending a very minimal deduction system is not necessarily the best approach, and that it may be better to start off with a strong idea of to which graph class the extended algorithm should parse. Additionally, several alternative ways of extending Kuhlmann and Jonsson are proposed.Dependensparsning kan vara ett användbart verktyg för att få datorer att kunna läsa text. Kuhlmann och Jonsson kom 2015 fram till ett logiskt deduktionssystem som kan parsa till ickekorsande grafer med en asymptotisk tidskomplexitet O(n3), där "n" är meningens som parsas längd. Detta arbete utökar Kuhlmann och Jonssons deduktionssystem så att det kan introducera vissa korsande bågar, medan en asymptotisk tidskomplexitet O(n4) uppnås. För att tillåta deduktionssystemet att introducera korsande bågar, introduceras 15 nya logiska delgrafstyper, eller item. Dessa item-typer tillåter deduktionssystemet att introducera korsande bågar på ett sådant sätt att acyklicitet bibehålls. Antalet logiska inferensregler tags från Kuhlmanns och Jonssons 19 till 172, på grund av den större mängden kombinationer av de nu 20 item-typerna. Resultatet är en mindre ökning av täckning på testdata (ungefär 10 procentenheter, d v s från cirka 70% till 80%), och jämförbar placering med Kuhlmann och Jonsson enligt måtten från uppgift 18 från SemEval 2015. Härledningsunikhet kan inte garanteras på grund av hur bågar introduceras i det nya deduktionssystemet. Den utökade algoritmen, QAC, parsar till en svårdefinierad grafklass, som jämförs empiriskt med 1-endpoint-crossing-grafer och grafer med pagenumber 2 eller mindre. QAC:s grafklass har lägre täckning än båda dessa, och har ingen högre gräns i pagenumber eller antal korsningar. Slutsatsen är att det inte nödvändigtvis är optimalt att utöka ett mycket minimalt och specifikt deduktionssystem, och att det kan vara bättre att inleda processen med en specifik grafklass i åtanke. Dessutom föreslås flera alternativa metoder för att utöka Kuhlmann och Jonsson.
21
Babu, George Jithin. "Look-Ahead Platooning through Guided Dynamic Programming". Thesis, KTH, Reglerteknik, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-121540.
Texto completo
22
Dai, Peng. "FASTER DYNAMIC PROGRAMMING FOR MARKOV DECISION PROCESSES". UKnowledge, 2007. http://uknowledge.uky.edu/gradschool_theses/428.
Texto completoResumen
Markov decision processes (MDPs) are a general framework used by Artificial Intelligence (AI) researchers to model decision theoretic planning problems. Solving real world MDPs has been a major and challenging research topic in the AI literature. This paper discusses two main groups of approaches in solving MDPs. The first group of approaches combines the strategies of heuristic search and dynamic programming to expedite the convergence process. The second makes use of graphical structures in MDPs to decrease the effort of classic dynamic programming algorithms. Two new algorithms proposed by the author, MBLAO* and TVI, are described here.
23
SKYRME, ALEXANDRE RUPERT ARPINI. "SAFE RECORD SHARING IN DYNAMIC PROGRAMMING LANGUAGES". PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2015. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=25871@1.
Texto completoResumen
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
PROGRAMA DE EXCELENCIA ACADEMICA
Linguagens de programação dinâmicas estão cada vez mais populares e já foram utilizadas para desenvolver uma ampla gama de aplicações. Enquanto isso, processadores multi-núcleo se tornaram padrão, mesmo em computadores pessoais e dispositivos móveis. Dessa forma, os programadores precisam recorrer ao paralelismo para aprimorar o desempenho de seus programas. Entretanto, a programação concorrente permanece difícil. Adicionalmente, a despeito de avanços em linguagens estáticas, avaliamos que linguagens dinâmicas ainda carecem de suporte adequado à concorrência. Nesta tese argumentamos que o principal problema da programação concorrente é a imprevisibilidade - comportamentos inesperados de programas, tais como retornar valores descabidos. Observamos que a imprevisibilidade é mais provável quando memória compartilhada é utilizada. Consequentemente, propomos um modelo de comunicação para concorrência que visa disciplinar o compartilhamento de memória em linguagens dinâmicas. O modelo é baseado nos padrões emergentes de concorrência de não compartilhar dados por padrão, imutabilidade de dados e tipos e efeitos (que transformamos em capacidades). Ele demanda a utilização de objetos compartilháveis para compartilhar dados e utiliza troca de mensagens para comunicação entre fluxos de execução. Objetos compartilháveis podem ser compartilhados apenas para leitura ou para leitura e escrita, o que permite acesso individual de escrita e acessos paralelos de leitura. Implementamos um protótipo em Lua para experimentar com o modelo na prática, bem como para conduzir uma avaliação geral de desempenho. A avaliação demonstra que há benefícios na utilização de memória compartilhada, mas ao mesmo tempo revela que os controles utilizados para assegurar a disciplina ocasionam um impacto de desempenho.
Dynamic programming languages have become increasingly popular and have been used to implement a range of applications. Meanwhile, multicore processors have become the norm, even for desktop computers and mobile devices. Therefore, programmers must turn to parallelism as a means to improve performance. However, concurrent programming remains difficult. Besides, despite improvements in static languages, we find dynamic languages are still lacking in concurrency support. In this thesis, we argue that the main problem with concurrent programming is unpredictability - unexpected program behaviors, such as returning out-of-thin-air values. We observe that unpredictability is most likely to happen when shared memory is used. Consequently, we propose a concurrency communication model to discipline shared memory in dynamic languages. The model is based on the emerging concurrency patterns of not sharing data by default, data immutability, and types and effects (which we turn into capabilities). It mandates the use of shareable objects to share data. Besides, it establishes that the only means to share a shareable object is to use message passing. Shareable objects can be shared as read-write or read-only, which allows both individual read-write access and parallel read-only access to data. We implemented a prototype in Lua, called luashare, to experiment with the model in practice, as well as to carry out a general performance evaluation. The evaluation showed us that safe data sharing makes it easier to allow for communication among threads. Besides, there are situations where copying data around is simply not an option. However, enforcing control over shareable objects has a performance cost, in particular when working with nested objects.
24
Eslinger, Gregory John. "Dynamic programming applied to electromagnetic satellite actuation". Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/82480.
Texto completoResumen
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2013.This electronic version was submitted and approved by the author's academic department as part of an electronic thesis pilot project. The certified thesis is available in the Institute Archives and Special Collections.
"June 2013." Cataloged from department-submitted PDF version of thesis
Includes bibliographical references (p. 135-140).
Electromagnetic formation flight (EMFF) is an enabling technology for a number of space mission architectures. While much work has been done for EMFF control for large separation distances, little work has been done for close-proximity EMFF control, where the system dynamics are quite complex. Dynamic programming has been heavily used in the optimization world, but not on embedded systems. In this thesis, dynamic programming is applied to satellite control, using close-proximity EMFF control as a case study. The concepts of dynamic programming and approximate dynamic programming are discussed. Several versions of the close-proximity EMFF control problem are formulated as a dynamic programming problems. One of the formulations is used as a case study for developing and examining the cost-to-go. Methods for implementing an approximate dynamic programming controller on a satellite are discussed. Methods for resolving physical states and dynamic programming states are presented. Because the success of dynamic programming depends on the system model, a novel method for finding the mass properties of a satellite, which would likely be used in the dynamic programming model, is introduced. This method is used to characterize the mass properties of three satellite systems: SPHERES, VERTIGO, and RINGS. Finally, a method for position and attitude estimation for systems that use line-of-sight measurements that does not require the use of a model is developed. This method is useful for model validation of the models used in the dynamic programming formulation.
by Gregory John Eslinger.
S.M.
25
Vyzas, Elias. "Approximate dynamic programming for some queueing problems". Thesis, Massachusetts Institute of Technology, 1997. http://hdl.handle.net/1721.1/10282.
Texto completoResumen
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Mechanical Engineering, 1997, and Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering, 1997.Includes bibliographical references (p. 81-82).
by Elias Vyzas.
M.S.
26
Zhao, Mengyao. "Genomic variation detection using dynamic programming methods". Thesis, Boston College, 2014. http://hdl.handle.net/2345/bc-ir:104357.
Texto completoResumen
Thesis advisor: Gabor T. MarthBackground: Due to the rapid development and application of next generation sequencing (NGS) techniques, large amounts of NGS data have become available for genome-related biological research, such as population genetics, evolutionary research, and genome wide association studies. A crucial step of these genome-related studies is the detection of genomic variation between different species and individuals. Current approaches for the detection of genomic variation can be classified into alignment-based variation detection and assembly-based variation detection. Due to the limitation of current NGS read length, alignment-based variation detection remains the mainstream approach. The Smith-Waterman algorithm, which produces the optimal pairwise alignment between two sequences, is frequently used as a key component of fast heuristic read mapping and variation detection tools for next-generation sequencing data. Though various fast Smith-Waterman implementations are developed, they are either designed as monolithic protein database searching tools, which do not return detailed alignment, or they are embedded into other tools. These issues make reusing these efficient Smith-Waterman implementations impractical. After the alignment step in the traditional variation detection pipeline, the afterward variation detection using pileup data and the Bayesian model is also facing great challenges especially from low-complexity genomic regions. Sequencing errors and misalignment problems still influence variation detection (especially INDEL detection) a lot. The accuracy of genomic variation detection still needs to be improved, especially when we work on low- complexity genomic regions and low-quality sequencing data. Results: To facilitate easy integration of the fast Single-Instruction-Multiple-Data Smith-Waterman algorithm into third-party software, we wrote a C/C++ library, which extends Farrar's Striped Smith-Waterman (SSW) to return alignment information in addition to the optimal Smith-Waterman score. In this library we developed a new method to generate the full optimal alignment results and a suboptimal score in linear space at little cost of efficiency. This improvement makes the fast Single-Instruction-Multiple-Data Smith-Waterman become really useful in genomic applications. SSW is available both as a C/C++ software library, as well as a stand-alone alignment tool at: https://github.com/mengyao/Complete- Striped-Smith-Waterman-Library. The SSW library has been used in the primary read mapping tool MOSAIK, the split-read mapping program SCISSORS, the MEI detector TAN- GRAM, and the read-overlap graph generation program RZMBLR. The speeds of the mentioned software are improved significantly by replacing their ordinary Smith-Waterman or banded Smith-Waterman module with the SSW Library. To improve the accuracy of genomic variation detection, especially in low-complexity genomic regions and on low-quality sequencing data, we developed PHV, a genomic variation detection tool based on the profile hidden Markov model. PHV also demonstrates a novel PHMM application in the genomic research field. The banded PHMM algorithms used in PHV make it a very fast whole-genome variation detection tool based on the HMM method. The comparison of PHV to GATK, Samtools and Freebayes for detecting variation from both simulated data and real data shows PHV has good potential for dealing with sequencing errors and misalignments. PHV also successfully detects a 49 bp long deletion that is totally misaligned by the mapping tool, and neglected by GATK and Samtools. Conclusion: The efforts made in this thesis are very meaningful for methodology development in studies of genomic variation detection. The two novel algorithms stated here will also inspire future work in NGS data analysis
Thesis (PhD) — Boston College, 2014
Submitted to: Boston College. Graduate School of Arts and Sciences
Discipline: Biology
27
Höner, zu Siederdissen Christian, Sonja J. Prohaska y Peter F. Stadler. "Algebraic dynamic programming over general data structures". Universitätsbibliothek Leipzig, 2016. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-206280.
Texto completoResumen
Background: Dynamic programming algorithms provide exact solutions to many problems in computational biology, such as sequence alignment, RNA folding, hidden Markov models (HMMs), and scoring of phylogenetic trees. Structurally analogous algorithms compute optimal solutions, evaluate score distributions, and perform stochastic sampling. This is explained in the theory of Algebraic Dynamic Programming (ADP) by a strict separation of state space traversal (usually represented by a context free grammar), scoring (encoded as an algebra), and choice rule. A key ingredient in this theory is the use of yield parsers that operate on the ordered input data structure, usually strings or ordered trees. The computation of ensemble properties, such as a posteriori probabilities of HMMs or partition functions in RNA folding, requires the combination of two distinct, but intimately related algorithms, known as the inside and the outside recursion. Only the inside recursions are covered by the classical ADP theory. Results: The ideas of ADP are generalized to a much wider scope of data structures by relaxing the concept of parsing. This allows us to formalize the conceptual complementarity of inside and outside variables in a natural way. We demonstrate that outside recursions are generically derivable from inside decomposition schemes. In addition to rephrasing the well-known algorithms for HMMs, pairwise sequence alignment, and RNA folding we show how the TSP and the shortest Hamiltonian path problem can be implemented efficiently in the extended ADP framework. As a showcase application we investigate the ancient evolution of HOX gene clusters in terms of shortest Hamiltonian paths. Conclusions: The generalized ADP framework presented here greatly facilitates the development and implementation of dynamic programming algorithms for a wide spectrum of applications.
28
Wang, Xia. "Applications of genetic algorithms, dynamic programming, and linear programming to combinatorial optimization problems". College Park, Md.: University of Maryland, 2008. http://hdl.handle.net/1903/8778.
Texto completoResumen
Thesis (Ph. D.) -- University of Maryland, College Park, 2008.Thesis research directed by: Applied Mathematics & Statistics, and Scientific Computation Program. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
29
Burrows, Richard B. P. "Dynamic load balancing". Thesis, University of Oxford, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.363886.
Texto completo
30
Steffen, Peter. "Compiling a domain specific language for dynamic programming". [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=983062382.
Texto completo
31
Ardi, Shanai. "A Nonlinear Programming Approach for Dynamic Voltage Scaling". Thesis, Linköping University, Department of Computer and Information Science, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-2774.
Texto completoResumen
Embedded computing systems in portable devices need to be energy efficient, yet they have to deliver adequate performance to the often computationally expensive applications. Dynamic voltage scaling is a technique that offers a speed versus power trade-off, allowing the application to achieve considerable energy savings and, at the same time, to meet the imposed time constraints.
In this thesis, we explore the possibility of using optimal voltage scaling algorithms based on nonlinear programming at the system level, for a complex multiprocessor scheduling problem. We present an optimization approach to the modeled nonlinear programming formulation of the continuous voltage selection problem excluding the consideration of transition overheads. Our approach achieves the same optimal results as the previous work using the same model, but due to its speed, can be efficiently used for design space exploration. We validate our results using numerous automatically generated benchmarks.
32
Christofides, Elina. "Dynamic programming for asset, liability and risk management". Thesis, Imperial College London, 2004. http://hdl.handle.net/10044/1/8371.
Texto completo
33
Zhu, Hong. "Dynamic programming algorithm for segmentation of CVC syllables". Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/tape15/PQDD_0001/MQ29004.pdf.
Texto completo
34
Lévesque, Moren. "Models of entrepreneurial decisions, a dynamic programming approach". Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp02/NQ34577.pdf.
Texto completo
35
Sauré, Antoine. "Approximate dynamic programming methods for advance patient scheduling". Thesis, University of British Columbia, 2012. http://hdl.handle.net/2429/43448.
Texto completoResumen
This dissertation studies an advance multi-priority patient scheduling problem. Patrick et al. (2008) formulated a version of this problem as a discounted infinite-horizon Markov decision process (MDP) and studied it using a linear programming method based on an affine value function approximation. This thesis starts by presenting an alternative solution approach for this problem based on the use of simulation, a policy iteration framework and a non-linear value function approximation. It then extends the dynamic multi-priority patient scheduling model and solution approach developed by Patrick et al. by considering patients who receive service across multiple days and for irregular lengths of time, and by allowing the possibility of using overtime on different days of the booking horizon. The research described in this dissertation is based on the hypothesis that some patients can be booked further into the future allowing the appointments for urgent patients to be scheduled earlier, and it seeks to identify effective policies for allocating available service capacity to incoming demand while reducing patient wait times in a cost-effective manner. Through the use of approximate dynamic programming techniques, it illustrates the importance of adequately assessing the future impact of today's decisions in order to more intelligently allocate capacity. Chapter 1 provides an overview of the multi-priority patient scheduling problem and a review of the literature relevant to it. Chapter 2 describes a simulation-based algorithm for solving a version of this problem and compares the performance of the resulting appointment scheduling policies against the performance of four other policies, including the one derived from the linear programming method. Chapter 3 extends the dynamic multi-priority patient scheduling model and solution approach developed by Patrick et al. It presents a discounted infinite-horizon MDP model for scheduling cancer treatments in radiation therapy units and a linear programming method for solving it. The benefits from the proposed method are evaluated by simulating its performance for a practical example based on data provided by the British Columbia Cancer Agency. Chapter 4 describes a teaching tool developed to illustrate advance patient scheduling practices to health care professionals and students. Finally, this dissertation concludes with additional discussion, extensions and further applications.
36
Yoshimoto, Yui, Yoshiyuki Karuno y Shinji Imahori. "Dynamic Programming Algorithms for Duplex Food Packing Problems". IEEE, 2010. http://hdl.handle.net/2237/14459.
Texto completo
37
Child, Christopher H. T. "Approximate dynamic programming with parallel stochastic planning operators". Thesis, City University London, 2011. http://openaccess.city.ac.uk/1109/.
Texto completoResumen
This thesis presents an approximate dynamic programming (ADP) technique for environment modelling agents. The agent learns a set of parallel stochastic planning operators (P-SPOs) by evaluating changes in its environment in response to actions, using an association rule mining approach. An approximate policy is then derived by iteratively improving state value aggregation estimates attached to the operators using the P-SPOs as a model in a Dyna-Q-like architecture. Reinforcement learning and dynamic programming are powerful techniques for automated agent decision making in stochastic environments. Dynamic programming is effective when there is a known environment model, while reinforcement learning is effective when a model is not available. The techniques derive a policy: a mapping from each environment state to an action which optimizes the long term reward the agent receives. The standard methods become less effective as the state space for the environment increases because they require values to be associated with each state, the storage and processing of which is exponential to the number of state variables. Resolving this “curse of dimensionality” is an important topic of research amongst all communities working on this problem. Two key methods are to: (i) derive an estimate of the value (approximate dynamic programming) using function approximation or state aggregation; or (ii) build a model of the environment from experience. This thesis presents a method of combining these approaches by exploiting structure in the state transition and value functions captured in a set of planning operators which are learnt through experience in the environment. Standard planning operators define the deterministic changes that occur in an environment in response to an action. This work presents Parallel Stochastic Planning Operators (P-SPOs), a novel form of planning operator providing a structured model of the state transition function in environments which are both non-deterministic and for which changes can occur outside the influence of actions. Next, an automated method for extracting P-SPOs from observations in an environment is explored using an adaptation of association rule mining. Finally, methods of relating the state transition structure encapsulated in the P-SPOs to state values, using the operators to store state value aggregation estimates, are evaluated. The framework described provides a method by which approximate dynamic programming can be applied by designers of AI agents and AI planning systems for which they have minimal prior knowledge. The framework and P-SPO based implementations are tested against standard techniques in two bench-mark stochastic environments: a “slippery gripper” block painting robot; and a “predator-prey” agent environment. Experimental results show that an agent using a P-SPO-based approach is able to learn an accurate model of its environment if successor state variables exhibit conditional independence, and an approximate model in the non-independent case. Results also demonstrate that the agent’s ability to generalise to previously unseen states using the model allow it to form an improved policy over an agent employing a standard Dyna-Q based technique. Finally, an approximate policy stored in state aggregation estimates attached to operators is shown to be optimal in experiments for which the P-SPO set contains sufficient information for effective aggregations to be formed.
38
Liu, Ning. "Approximate dynamic programming algorithms for production-planning problems". Thesis, Wichita State University, 2013. http://hdl.handle.net/10057/10636.
Texto completoResumen
The capacitated lot-sizing problem (CLSP) is a core problem for successfully reducing overall costs in any production process. The exact approaches proposed for solving the CLSP are based on two major methods: mixed-integer programming and dynamic programming. This thesis provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the CLSP. In the proposed method, by using only a partial dynamic process, the inventory cost function is approximated, and then the resulting approximate cost function is used as a value function in each stage of the approximate dynamic program. In this thesis, six different algorithms are developed for the CLSP, based on three different types of approximate dynamic programming approaches. The general methodology combines dynamic programming with data fitting and approximation techniques to estimate the inventory cost function at each stage of the dynamic program. Furthermore, three main algorithmic frameworks to compute a piecewise linear approximate inventory cost function for the CLSP are provided. The first approach integrates regression models into an approximate dynamic program. The second approach uses the information obtained by a partial dynamic process to approximate the piecewise linear inventory cost function. The third approach uses slope-check and bisection techniques to locate the breakpoints of the piecewise linear function in order to approximate the inventory cost function for the CLSP. The effectiveness of the proposed methods are analyzed on various types of CLSP instances with different cost and capacity characteristics. Computational results show that approximation approaches could considerably decrease the computational time required by the dynamic program and the integer program for different CLSP instances. Furthermore, in most cases, some of the proposed approaches can accurately capture the optimal solution of the problem.Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Industrial and Manufacturing Engineering
39
Van, Roy Benjamin. "Feature-based methods for large scale dynamic programming". Thesis, Massachusetts Institute of Technology, 1994. http://hdl.handle.net/1721.1/11865.
Texto completo
40
Demir, Ramazan. "An approximate dynamic programming approach to discrete optimization". Thesis, Massachusetts Institute of Technology, 2000. http://hdl.handle.net/1721.1/9137.
Texto completoResumen
Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2000.Includes bibliographical references (leaves 181-189).
We develop Approximate Dynamic Programming (ADP) methods to integer programming problems. We describe and investigate parametric, nonparametric and base-heuristic learning approaches to approximate the value function in order to break the curse of dimensionality. Through an extensive computational study we illustrate that our ADP approach to integer programming competes successfully with existing methodologies including state of art commercial packages like CPLEX. Our benchmarks for comparison are solution quality, running time and robustness (i.e., small deviations in the computational resources such as running time for varying instances of same size). In this thesis, we particularly focus on knapsack problems and the binary integer programming problem. We explore an integrated approach to solve discrete optimization problems by unifying optimization techniques with statistical learning. Overall, this research illustrates that the ADP is a promising technique by providing near-optimal solutions within reasonable amount of computation time especially for large scale problems with thousands of variables and constraints. Thus, Approximate Dynamic Programming can be considered as a new alternative to existing approximate methods for discrete optimization problems.
by Ramazan Demir.
Ph.D.
41
Al-Dujaily, Ra'ed. "Embedded dynamic programming networks for networks-on-chip". Thesis, University of Newcastle upon Tyne, 2013. http://hdl.handle.net/10443/1884.
Texto completoResumen
Relentless technology downscaling and recent technological advancements in three dimensional integrated circuit (3D-IC) provide a promising prospect to realize heterogeneous system-on-chip (SoC) and homogeneous chip multiprocessor (CMP) based on the networks-onchip (NoCs) paradigm with augmented scalability, modularity and performance. In many cases in such systems, scheduling and managing communication resources are the major design and implementation challenges instead of the computing resources. Past research efforts were mainly focused on complex design-time or simple heuristic run-time approaches to deal with the on-chip network resource management with only local or partial information about the network. This could yield poor communication resource utilizations and amortize the benefits of the emerging technologies and design methods. Thus, the provision for efficient run-time resource management in large-scale on-chip systems becomes critical. This thesis proposes a design methodology for a novel run-time resource management infrastructure that can be realized efficiently using a distributed architecture, which closely couples with the distributed NoC infrastructure. The proposed infrastructure exploits the global information and status of the network to optimize and manage the on-chip communication resources at run-time. There are four major contributions in this thesis. First, it presents a novel deadlock detection method that utilizes run-time transitive closure (TC) computation to discover the existence of deadlock-equivalence sets, which imply loops of requests in NoCs. This detection scheme, TC-network, guarantees the discovery of all true-deadlocks without false alarms in contrast to state-of-the-art approximation and heuristic approaches. Second, it investigates the advantages of implementing future on-chip systems using three dimensional (3D) integration and presents the design, fabrication and testing results of a TC-network implemented in a fully stacked three-layer 3D architecture using a through-silicon via (TSV) complementary metal-oxide semiconductor (CMOS) technology. Testing results demonstrate the effectiveness of such a TC-network for deadlock detection with minimal computational delay in a large-scale network. Third, it introduces an adaptive strategy to effectively diffuse heat throughout the three dimensional network-on-chip (3D-NoC) geometry. This strategy employs a dynamic programming technique to select and optimize the direction of data manoeuvre in NoC. It leads to a tool, which is based on the accurate HotSpot thermal model and SystemC cycle accurate model, to simulate the thermal system and evaluate the proposed approach. Fourth, it presents a new dynamic programming-based run-time thermal management (DPRTM) system, including reactive and proactive schemes, to effectively diffuse heat throughout NoC-based CMPs by routing packets through the coolest paths, when the temperature does not exceed chip’s thermal limit. When the thermal limit is exceeded, throttling is employed to mitigate heat in the chip and DPRTM changes its course to avoid throttled paths and to minimize the impact of throttling on chip performance. This thesis enables a new avenue to explore a novel run-time resource management infrastructure for NoCs, in which new methodologies and concepts are proposed to enhance the on-chip networks for future large-scale 3D integration.
42
Cai, C. "Adaptive traffic signal control using approximate dynamic programming". Thesis, University College London (University of London), 2010. http://discovery.ucl.ac.uk/20164/.
Texto completoResumen
This thesis presents a study on an adaptive traffic signal controller for real-time operation. An approximate dynamic programming (ADP) algorithm is developed for controlling traffic signals at isolated intersection and in distributed traffic networks. This approach is derived from the premise that classic dynamic programming is computationally difficult to solve, and approximation is the second-best option for establishing sequential decision-making for complex process. The proposed ADP algorithm substantially reduces computational burden by using a linear approximation function to replace the exact value function of dynamic programming solution. Machine-learning techniques are used to improve the approximation progressively. Not knowing the ideal response for the approximation to learn from, we use the paradigm of unsupervised learning, and reinforcement learning in particular. Temporal-difference learning and perturbation learning are investigated as appropriate candidates in the family of unsupervised learning. We find in computer simulation that the proposed method achieves substantial reduction in vehicle delays in comparison with optimised fixed-time plans, and is competitive against other adaptive methods in computational efficiency and effectiveness in managing varying traffic. Our results show that substantial benefits can be gained by increasing the frequency at which the signal plans are revised. The proposed ADP algorithm is in compliance with a range of discrete systems of resolution from 0.5 to 5 seconds per temporal step. This study demonstrates the readiness of the proposed approach for real-time operations at isolated intersections and the potentials for distributed network control.
43
Häring, Thomas W. "Optimizing loblolly pine management with stochastic dynamic programming". Diss., Virginia Tech, 1993. http://hdl.handle.net/10919/39478.
Texto completoResumen
This study examines effects of unpredictable price fluctuations and possible catastrophic losses on the optimal site preparation intensity of un thinned loblolly pine plantations under the assumption of lisk aversion. It concentrates exclusively on financial motives and does not take non-market values and portfolio considerations into account. The results should be interpreted with these limitations in mind.
Two approaches are taken to compare site preparation intensities: a quasideterministic approach, where expected cash flows are discounted with risk-adjusted discount rates, and a stochastic approach, where probability functions of cash flows are used to maximize expected utility from net present values. The stochastic approach is further divided into non-adaptive scenarios and adaptive scenarios, where the investor can gather additional price information during the life of a stand to optimize the harvest decision. The adaptive management problem is solved with stochastic dynamic programming. For each possible harvest age, an optimal reservation price below which the forest landowner should not sell the stumpage is calculated.
The study shows that the use of a single risk-adjusted discount rate is generally inadequate to compare different management intensities. The stochastic approaches reveal that the optimal management intensity depends on the degree of risk aversion, with increasing risk aversion leading to a lower intensity level. Given the possibility of catastrophic losses, the adoption of a feedback harvesting policy strengthens the already dominant influence of risk aversion and does not generally lead to an increase in management intensity.
The study's results suggest that even if the landowner is managing the forest solely for financial reasons, some of the reluctance to invest in intensive forestry may not indicate a lack of interest or information but simply an economic reaction to risk, especially in regions with a high potential danger of catastrophic losses.Ph. D.
44
Häring, Thomas W. "Optimizing loblolly pine management with stochastic dynamic programming /". This resource online, 1993. http://scholar.lib.vt.edu/theses/available/etd-10022007-144537/.
Texto completo
45
Elshqeirat, Basima Ahmad Haroun. "Optimizing reliable network topology design using dynamic programming". Thesis, Curtin University, 2015. http://hdl.handle.net/20.500.11937/823.
Texto completoResumen
This thesis addresses four reliable network topology design problems that consider reliability, cost, and/or bandwidth performance metrics. The optimization problems include one or two objectives and one constraint, each of which is known NP-hard. All problems consider all-terminal and/or two-terminal reliability measures. Four heuristic dynamic programming approaches are proposed, and 10 order criteria are used to improve their optimality and time efficiency. Simulations on hundreds of networks show the merits of the proposed methods.
46
Zetka, Petr. "Programový systém pro řešení úloh dynamického programování". Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2011. http://www.nusl.cz/ntk/nusl-229701.
Texto completoResumen
This work deals with building a program system for solving dynamic programming problems on a computer. The theoretical part describes dynamic programming as a tool used for optimizing multistage decision processes and dynamic programming problems implemented in the program system. The practical part describes the design and implementation of the program system and verification of its functionality.
47
Piveropoulos, Giannis. "Dynamic object-oriented systems". Thesis, University of York, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.298492.
Texto completo
48
Chang, Chia-Yuan y 張嘉元. "Fuzzy Multiobjective Dynamic Programming". Thesis, 1998. http://ndltd.ncl.edu.tw/handle/61755792753239392383.
Texto completoResumen
碩士國立臺灣大學
化學工程學系
86
The dynamic optimization for chemical processes usually has the following properties : (1) highly nonlinear (2) containing complex and discontinuous constraints and (3) delay arguments. The conventional maximum principle approaches often encounter som problems such as unstable integration and difficulties in obtaining global optimum. In this study, the use of iterative dynamic programming(IDP) presents the advantages of obtaining global optimum, solving problem without transformation, and in itself constituting a simple concept. In stead of the conventional penalty function method, the modified Powell's multiplier algorithm is incorporated to handle each constraint. As far as the optimization of multiobjective dynamic systems, the conventional multiobjective optimization usually requires the adjustment of parameters to generate many Pareto optimum from which are to be chosen by the decision maker. In a complex optimization problem, this approach takes rather high computational effort. In the current stydy, the use of IDP along with fuzzy decision making procedure can directly approach the desired solution of the decision maker. In the multiobjective dynamic optimization of the Nylon-6 batch reactor and the Penicillin G fed-batch fermentation process, the efficiency of the method is verified.
49
Węgrzycki, Karol. "Provably optimal dynamic programming". Doctoral thesis, 2021. https://depotuw.ceon.pl/handle/item/3869.
Texto completoResumen
In this thesis we study an application of dynamic programming technique to graph problems and approximation algorithms. We improve upon
state-of-the-art algorithms for All-Nodes Shortest Cycles, distance oracles, approximate algorithm for Partition, weak approximation for Subset Sum and others.
We also present equivalence classes for certain problems, that admit algorithms based on dynamic programming. Namely:
• (min, +)-convolution and knapsack problem,
• (min, max)-convolution and strongly polynomial approximate (min, max) - convolution,
• (min, max)-product and strongly polynomial approximate all-pairs shortest path.W rozprawie przedstawiamy nowe techniki analizy algorytmów opartych na programowaniu dynamicznym. Używamy ich do rozwiązywania problemów na grafach i przyśpieszeniu wybranych algorytmów aproksymacyjnych. Zaproponowane przez nas metody pozwalają na usprawnienie obecnie znanych algorytmów dla znajdywania najkrótszych cykli, wyroczni odległości, problemów aproksymacyjnych związanych z problemem plecakowym i innych. W rozprawie proponujemy także klasy równoważności dla wybranych problemów, które mają efektywne algorytmy oparte na programowaniu dynamicznym. W szczególności: • (min, +)-konwolucji i problemu plecakowego, • (min, max)-konwolucji i silnie wielomianowej aproksymacji dla (min, +)-konwolucji, • (min, max)-produktu i silnie wielomianowej aproksymacji dla znajdywania najkrótszych ścieżek w grafie.
50
Ozaki, Hiroyuki. "Biconvergent stochastic dynamic programming". 1992. http://catalog.hathitrust.org/api/volumes/oclc/28405066.html.
Texto completo