Genetinių algoritmų panaudojimo galimybės ir paplitimas nuolat didėja. Daugelyje nagrinėtų mokslinių darbų, genetiniai algoritmai yra naudojami uždavinių optimizavimui. Optimizavimui naudojama daug skirtingų metodų. Sprendžiant konkretų uždavinį mokslinėje literatūroje paprastai pritaikoma keletas metodų tam, kad būtų pagerinti gauti rezultatai, t.y., išbandoma keletas strategijų. Deja, nepavyko rasti tyrimų, kaip tos pačios genetinės paieškos strategijos gali būti pritaikytos kitoms analogiškoms problemoms spręsti. Šiame darbe pateikiama probleminės srities apžvalga, tyrimo aprašymas bandymų rezultatai ir išvados. / The use of genetic algorithms considerably increases. In some research works GA‘s are investigated to optimize graph problems. There are many different strategies for GA optimization. Unfortunately, there are no investigations if a strategy, suitable for a particular graph problem, will be useful solving other graph problems. In this work I originated, described and developed some GA learning strategy elements. Also I developed some that are available in other research works. These elements are: generation of initial population, selection of individuals, mutation, crossover and some other parameters. All possible strategies (about 300) are tested in this work for three graph problems: shortest path, longest path and traveling salesman problem. Results are summarized and described.

Darbe yra nagrinėjami du paplitę darbo sekų modeliai – BPMN ir Windows Workflow Foundation (WF), bei tiriama, kaip BPMN darbo sekas transformuoti į WF vykdymo modelį. BPMN ir WF yra iš esmės skirtingos kalbos ir pagrindinė transformavimo problema yra susijusi su nestruktūrizuotų ciklų eliminavimu, t.y. jų konvertavimu į proceso atžvilgiu ekvivalenčias struktūrizuotas konstrukcijas. Darbe pasirinktas žinomas algoritmas, skirtas panašioms ciklinėms konstrukcijoms transformuoti naudojant tęstinumo semantiką. Jis buvo adaptuotas BPMN modeliui. Algoritme naudojama tęstinumo semantika buvo praplėsta atsižvelgiant į BPMN ir WF modeliuose esančias konstrukcijas bei patobulinto algoritmo ypatumus. Buvo sukurti nauji algoritmai, skirti nagrinėjamai transformacijai atlikti. Transformavimo algoritmui patikrinti buvo sukurta programa, leidžianti tęstinumo semantika užrašytą BPMN darbo seką transformuoti į pavidalą, nesunkiai konvertuojamą į WF. Atliktos eksperimentinės darbo sekų transformacijos parodė, kad sukurtas algoritmas yra veiksmingas. / This paper analyzes the two most widely used workflow models – BPMN and Windows Workflow Foundation (WF). It also analyzes how a BPMN workflow can be transformed into a WF execution model. BPMN and WF represent two fundamentally different classes of languages and the basic problem is related to convertion of unstructured cycles to their structured equivalents. A known algorithm used for similar cyclic constructions transformations using continuation semantics was chosen. This algorithm was adopted for the BPMN model. The continuation semantics were extended in regards to BPMN and WF model constructions and the specifics of the improved algorithm. Finally, in order to solve the transformation, three new algorithms were created: algorithm for BPMN workflow specification with extended continuation semantics; algorithm for transforming the specification to structured model; algorithm for converting structured model specification to WF model. A specialized program, which transforms extended continuation semantics to a structured model, was written to test the transformation algorithm. Testing this program with exemplary transformations proved that the transformation algorithm was working correctly.

This thesis focuses on the engineering of algorithms for massive data sets. In recent years, massive data sets have become ubiquitous and existing computing applications, for the most part, cannot handle these data sets efficiently: either they crash or their performance degrades to a point where they take unacceptably long to process the input. Parallel computing and I/O-efficient algorithms provide the means to process massive amounts of data efficiently. The work presented in this thesis makes use of these techniques and focuses on obtaining practically efficient solutions for specific problems in computational geometry and graph theory. We focus our attention first on skyline computations. This problem arises in decision-making applications and has been well studied in computational geometry and also by the database community in recent years. Most of the previous work on this problem has focused on sequential computations using a single processor, and the algorithms produced are not able to efficiently process data sets beyond the capacity of main memory. Such massive data sets are becoming more common; thus, parallelizing the skyline computation and eliminating the I/O bottleneck in large-scale computations is increasingly important in order to retrieve the results in a reasonable amount of time. Furthermore, we address two fundamental problems of graph analysis that appear in many application areas and which have eluded efforts to develop theoretically I/O-efficient solutions: computing the strongly connected components of a directed graph and topological sorting of a directed acyclic graph. To approach these problems, we designed algorithms, developed efficient implementations and, using extensive experiments, verified that they perform well in practice. Our solutions are based on well understood algorithmic techniques. The experiments show that, even though some of these techniques do not lead to provably efficient algorithms, they do lead to practically efficient heuristic solutions. In particular, our parallel algorithm for skyline computation is based on divide-and-conquer, while the strong connectivity and topological sorting algorithms use techniques such as graph contraction, the Euler technique, list ranking, and time-forward processing.

Anthropogenic infrastructure such as roads, ditches and culverts have strong impacts on hydrological processes, particularly surface drainage patterns. Despite this, these structures are often not present in the digital elevation models (DEMs) used to provide surface drainage data to hydrological models, owing to the coarse spatial resolution of many available DEMs. Modelling drainage patterns in human-modified landscapes requires very accurate, high-resolution DEM data to capture these features. Light Detection And Ranging (LiDAR) is a remote sensing technique that is used for producing DEMs with fine resolutions that can represent anthropogenic landscapes features such as human modifications on the landscape such as roadside ditches. In these data, roads act as a barrier to flow and are treated as dams, where on the ground culverts and bridges exist. While possible to locate and manually enforce flow across these roads, there is currently no automated technique to identify these locations and perform flow enforcement. This research improves the modelling of surface drainage pathways in rural anthropogenic altered landscapes by utilizing a novel algorithm that identifies ditches and culverts in LiDAR DEMs and enforces flow through these features by way of breaching. This breaching algorithm was tested on LiDAR datasets for two rural test sites in Southern Ontario. These analyses showed that the technique is an effective tool for efficiently incorporating ditches and culverts into the hydrological analysis of a landscape that has both a gradient associated with it, as well as a lack of densely forested areas. The algorithm produced more accurate representations of both overland flow when compared to outputs that excluded these anthropogenic features all together.

Piezoelectric actuators are resonance systems operating principles based on high-frequency oscillations excitation, are used in structures of robots. Observed piezorobots have no additional motion generating structures, but only direct contact points with the static plane. Piezorobot motion trajectory is broken lines, therefore, the classical trajectory formation methods cannot be applied. The main object is motion trajectory formation methods. The main aim of this work is to create motion trajectory formation methods for precision multidimensional piezorobots. The application of these algorithms is piezorobot motion simulation and control software. / Pjezoelektriniai judesio keitikliai – rezonansinės sistemos, kurių veikimo principas pagrįstas aukšto dažnio virpesių žadinimu. Disertacijoje tiriamieji pjezorobotai neturi papildomų judesį generuojančių struktūrų, o tik tiesioginius kontakto su statine plokštuma taškus. Kadangi judesio trajektorija yra laužyta, klasikiniai trajektorijų formavimo metodai netinka. Pagrindinis tyrimo objektas yra judesio trajektorijų formavimo metodai. Pagrindinis disertacijos tikslas – sukurti precizinių daugiamačių pjezorobotų judesio trajektorijų formavimo algoritmus. Sukurtų algoritmų taikymo sritis – pjezorobotų judesio modeliavimo ir valdymo programinė įranga.

Šio darbo uždavinys – sukurti internetinę programą, vaizduojančią trimatį fraktalą. Tam tikslui buvo išnagrinėti esami metodai ir technologijos trimatei grafikai internete vizualizuoti. Palyginus išnagrinėtus metodus ir technologijos,buvo parinktas tinkamas užduočiai realizuoti metodas, pateiktos išvados. Padaryta programavimo kalbų skirtu programavimui internete apžvalga, aprašytos jų savybės, principai ir palygintos jų teikiamos galimybės ir tinkamumas šiam darbui. Sukurtoje programoje vaizduojamas fraktalas-Mengerio kempinė. Pateiktas fraktalo konstravimo rekursinis algoritmas. Pateiktose programose realizuoti aprašytas rekursinis algoritmas ir algoritmas, kuriame naudojama Kronekerio daugyba ir šablonas matricos pavidalu konstruojant fraktalą. Bandant pagerinti programą, sukurta ir pateikta antrojo algoritmo modifikacija, kurioje bandoma saugoti tik matricos dalį. / The main purpose of this work is to create an internet program, which depicts the three-dimensional fractal. Striving to meet the main objective of this work the existing methods and technologies for the three-dimensional graphics were explored and visualized in the internet. After comparing analyzed methods and technologies, the appropriate method for realizing the task was selected and findings were proposed. Moreover for choosing the programming language: the review of programming languages was made, their characteristics and principles were described, and their provided opportunities were compared. The fractal – Menger Sponge is depicted in the created program, and the recursive algorithm of the fractal construction is proposed and described in the given programs. The Kronecker Multiplication and the pattern in the matrix form are used for constructing the fractal. For trying to improve the program the second algorithm modification was created and introduced, in which was making attempt to protect just the part of matrix.

The problem of finding the convex hull of a set of points in the plane is one of the fundamental and well-studied problems in Computational Geometry. However, for a set of imprecise points, the convex hull problem has not been thoroughly investigated. By imprecise points, we refer to a region in the plane inside which one point may lie. We are particularly interested in finding a minimum perimeter convex hull of a set of imprecise points, where the imprecise points are modelled as line segments. Currently, the best known algorithm that solves the minimum perimeter convex hull problem has an exponential running time in the worst case. It is still unknown whether this problem is NP-hard. We explore several approximation algorithms for this problem. Finally we propose a constant factor approximation algorithm that runs in O(nlogn) time. / Thesis (Master, Computing) -- Queen's University, 2008-11-28 14:47:15.169

Research indicates that multiprocessor-based architectures will provide a flexible alternative to hard-wired application-specific integrated circuits (ASICs) suitable to implement the multitude of wireless standards required by mobile devices, while meeting their strict area and power requirements. This shift in design philosophy has led to the software-defined radio (SDR) paradigm, where a significant portion of a wireless standard's physical layer is implemented in software, allowing multiple standards to share a common architecture. Turbo codes offer excellent error-correcting performance, however, turbo decoders are one of the most computationally complex baseband tasks of a wireless receiver. Next generation wireless standards such as Worldwide Interoperability for Microwave Access (WiMAX), support enhanced double-binary turbo codes, which offer even better performance than the original binary turbo codes, at the expense of additional complexity. Hence, the design of efficient double-binary turbo decoder software is required to support wireless standards in a SDR environment. This thesis describes the optimization, parallelization, and simulated performance of a software double-binary turbo decoder implementation supporting the WiMAX standard suitable for SDR. An adapted turbo decoder is implemented in the C language, and numerous software optimizations are applied to reduce its overall computationally complexity. Evaluation of the software optimizations demonstrated a combined improvement of at least 270% for serial execution, while maintaining good bit-error rate (BER) performance. Using a customized multiprocessor simulator, special instruction support is implemented to speed up commonly performed turbo decoder operations, and is shown to improve decoder performance by 29% to 40%. The development of a flexible parallel decoding algorithm is detailed, with multiprocessor simulations demonstrating a speedup of 10.8 using twelve processors, while maintaining good parallel efficiency (above 89%). A linear-log-MAP decoder implementation using four iterations was shown to have 90% greater throughput than a max-log-MAP decoder implementation using eight iterations, with comparable BER performance. Simulation also shows that multiprocessor cache effects do not have a significant impact on parallel execution times. An initial investigation into the use of vector processing to further enhance performance of the parallel decoder software reveals promising results. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2009-09-25 16:22:47.288

No description available.

No description available.