No description available.

Three-dimensional computer graphics enjoys a wide range of applications of which games and movies are only few examples. By incorporating three-dimensional computer graphics in to a simulator the simulator is able to provide the operator with visual feedback during a simulation. Simulators come in many different flavors where flight and radar simulators are two types in which three-dimensional rendering of large terrains constitutes a central component. Ericsson Microwave Systems (EMW) in Skövde is searching for an algorithm that (a) can handle terrain data that is larger than physical memory and (b) has an adjustable error metric that can be used to reduce terrain detail level if an increase in load on other critical parts of the system is observed. The aim of this paper is to identify and evaluate existing algorithms for terrain rendering in order to find those that meet EMW: s requirements. The objectives are to (i) perform a literature survey over existing algorithms, (ii) implement these algorithms and (iii) develop a test environment in which these algorithms can be evaluated form a performance perspective. The literature survey revealed that the algorithm developed by Lindstrom and Pascucci (2001) is the only algorithm of those examined that succeeded to fulfill the requirements without modifications or extra software. This algorithm uses memory-mapped files to be able to handle terrain data larger that physical memory and focuses on how terrain data should be laid out on disk in order to minimize the number of page faults. Testing of this algorithm on specified test architecture show that the error metric used could be adjusted to effectively control the terrains level of detail leading to a substantial increase in performance. The results also reveal the need for both view frustum culling as well a level of detail algorithm to achieve fast display rates of large terrains. Further the results also show the importance of how terrain data is laid out on disk especially when physical memory is limited.

Technology has a major role in today’s world. The development and massive access to information technology has enabled the use of computers to provide assistance on a wide range of tasks, from the most trivial daily ones to the most complex challenges we face as human kind. In particular, optimisation algorithms assist us in taking decisions, improving processes, designing solutions and they are successfully applied in several contexts such as industry, health, entertainment, and so on. The design and development of effective and efficient computational algorithms is, thus, a need in modern society.Developing effective and efficient optimisation algorithms is an arduous task that includes designing and testing of several algorithmic components and schemes, and requires considerable expertise. During the design of an algorithm, the developer defines parameters, that can be used to further adjust the algorithm behaviour depending on the particular application. Setting appropriate values for the parameters of an algorithm can greatly improve its performance. This way, most high-performing algorithms define parameter settings that are “finely tuned”, typically by experts, for a particular problem or execution condition.The process of finding high-performing parameter settings, called algorithm configuration, is commonly a challenging, tedious, time consuming and computationally expensive task that hinders the application and design of algorithms. Nevertheless, the algorithm configuration process can be modelled as an optimisation problem itself and optimisation techniques can be applied to provide high-performing configurations. The use of automated algorithm configuration procedures, called configurators, allows obtaining high-performing algorithms without requiring expert knowledge and it enables the design of more flexible algorithms by easing the definition of design choices as parameters to be set. Ultimately, automated algorithm configuration could be used to fully automatise the algorithm development process, providing algorithms tailored to the problem to be solved.The aim of the work presented in this thesis is to study the automated configuration of algorithms. To do so, we formally define the algorithm configuration problem and analyse its characteristics. We study the most prominent algorithm configuration procedures and identify relevant configuration techniques and their applicability. We contribute to the field by proposing and analysing several configuration procedures, being the most prominent of these the irace configurator. This work presents and studies several modifications of the configuration process implemented by irace, which considerably improve the performance of irace and broaden its applicability. In a general context, we provide insights about the characteristics of the algorithm configuration process and techniques by performing several analyses configuring different types of algorithms under varied situations. And, finally, we provide practical examples of the usage of automated configuration techniques showing its benefits and further uses for the application and design of efficient and effective algorithms. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Abstract In this thesis, iterative detection and estimation algorithms for digital communications systems in the presence of parametric uncertainty are explored and further developed. In particular, variational methods, which have been extensively applied in other research fields such as artificial intelligence and machine learning, are introduced and systematically used in deriving approximations to the optimal receivers in various channel conditions. The key idea behind the variational methods is to transform the problem of interest into an optimization problem via an introduction of extra degrees of freedom known as variational parameters. This is done so that, for fixed values of the free parameters, the transformed problem has a simple solution, solving approximately the original problem. The thesis contributes to the state of the art of advanced receiver design in a number of ways. These include the development of new theoretical and conceptual viewpoints of iterative turbo-processing receivers as well as a new set of practical joint estimation and detection algorithms. Central to the theoretical studies is to show that many of the known low-complexity turbo receivers, such as linear minimum mean square error (MMSE) soft-input soft-output (SISO) equalizers and demodulators that are based on the Bayesian expectation-maximization (BEM) algorithm, can be formulated as solutions to the variational optimization problem. This new approach not only provides new insights into the current designs and structural properties of the relevant receivers, but also suggests some improvements on them. In addition, SISO detection in multipath fading channels is considered with the aim of obtaining a new class of low-complexity adaptive SISOs. As a result, a novel, unified method is proposed and applied in order to derive recursive versions of the classical Baum-Welch algorithm and its Bayesian counterpart, referred to as the BEM algorithm. These formulations are shown to yield computationally attractive soft decision-directed (SDD) channel estimators for both deterministic and Rayleigh fading intersymbol interference (ISI) channels. Next, by modeling the multipath fading channel as a complex bandpass autoregressive (AR) process, it is shown that the statistical parameters of radio channels, such as frequency offset, Doppler spread, and power-delay profile, can be conveniently extracted from the estimated AR parameters which, in turn, may be conveniently derived via an EM algorithm. Such a joint estimator for all relevant radio channel parameters has a number of virtues, particularly its capability to perform equally well in a variety of channel conditions. Lastly, adaptive iterative detection in the presence of phase uncertainty is investigated. As a result, novel iterative joint Bayesian estimation and symbol a posteriori probability (APP) computation algorithms, based on the variational Bayesian method, are proposed for both constant-phase channel models and dynamic phase models, and their performance is evaluated via computer simulations.

Title: Generating polynomials for number field sieve Author: Anežka Pejlová Department: Department of Algebra Supervisor: prof. RNDr. Aleš Drápal, CSc., DSc., Department of Algebra Abstract: The topic of this thesis is mainly focused on Kleinjung algorithm for generating polynomials within the General Number Field Sieve, which is the most efficient factorization algorithm nowadays. Commonly used consecu- tions are explained with respect to the fact whether they can be rigorously proven or they are based only on heuristic assumptions. Another contribution of this thesis is the attached implementation of Kleinjung algorithm develo- ped as a part of the Number Field Sieve project led by the Department of Algebra. The appropriateness of some heuristics used in the theory beyond the Kleinjung algorithm is supported by empirical data obtained from this implementation. Keywords: Number field sieve, Kleinjung algorithm

This thesis deals with the problem of TV commercials planning. This problem is getting more difficult as the number of different TV stations grows and naive algorithms become unable to scale with this number. In this work, we deal with the possibility to use evolutionary algorithms to solve this problem. The work also contains an implementation of a software, which is capable of testing the various versions of the algorithm and comparing them to a naive one. The results indicate that evolutionary algorithms are a suitable technique to solve the problem at hand. Powered by TCPDF (www.tcpdf.org)

Decision trees are recognized and widely used technique for processing and analyzing data. These trees are designed with typical and generally known inductive techniques (such as ID3, C4.5, C5.0, CART, CHAID, MARS). Predictive power of created trees is not always perfect and they often provide a room for improvement. Induction of trees with difficult criterias is hard and sometime impossible. In this paper we will deal with decision trees, namely their creation. We use the mentioned room for improvement by metaheuristic, genetic algorithms, which is used in all types of optimalization. The work also includes an implementation of a new proposed algorithm in the form of plug-in into Weka environment. A comparison of the proposed method for induction of decision trees with known algorithm C4.5 is an integral part of this thesis. Powered by TCPDF (www.tcpdf.org)

The main focus of this thesis are hypercubes. In the first part, we introduce hypercubes, which form an interesting class of graphs that has practical uses in networks and distributed computing. Because of their varied applications, the thesis describes the graph-theory problems related to hypercubes such as searching for detour spanners, minimizing their maximal degree and finding multiple edge- disjoint spanners. It also overviews current results on selected hypercube problems and proposes a solution using a genetic algorithm. The genetic algorithm is designed, implemented and its performance is evaluated. The conclusion is that applying a genetic algorithm to some hypercube problems is a viable, but not the most effective method.

Efficient unification is considered within the context of logic programming. Unification is explained in terms of equivalence classes made up of terms, where there is a constraint that no equivalence class may contain more than one function term. It is demonstrated that several well-known "efficient" but nonlinear unification algorithms continually maintain the said constraint as a consequence of their choice of data structure for representing equivalence classes. The linearity of the Paterson-Wegman unification algorithm is shown largely to be a consequence of its use of unbounded lists of pointers for representing equivalences between terms, which allows it to avoid the nonlinearity of "union-find".

Abstract In industry there is a high demand for algorithms that can efficiently solve search problems. Evolutionary Computing (EC) belonging to a class of heuristics are proven to be well suited to solve search problems, especially optimization tasks. They arrived at that location because of their flexibility, scalability and robustness. However, despite their advantages and increasing popularity, there are numerous opened questions in this research area, many of them related to the design and tuning of the algorithms. A neutral technique called Pseudo Redundancy and related concepts such as Updated Objective Grid (UOG) is proposed to tackle the mentioned problem making an evolutionary approach more suitable for ''real world'' applications while increasing its robustness and efficiency. The proposed UOG technique achieves neutral search by objective function transformation(s) resulting several advantageous features. (a) Simplifies the design of an evolutionary solver by giving population sizing principles and directions to choose the right selection operator. (b) The technique of updated objective grid is adaptive without introducing additional parameters, therefore no parameter tuning required for UOG to adjust it for different environments, introducing robustness. (c) The algorithm of UOG is simple and computationally cheap. (d) It boosts the performance of an evolutionary algorithm on high dimensional (constrained and unconstrained) problems. The theoretical and experimental results from artificial test problems included in this thesis clearly show the potential of the proposed technique. In order to demonstrate the power of the introduced methods under "real" circumstances, the author additionally designed EAs and performed experiments on two industrial optimization tasks. Although, only one project is detailed in this thesis while the other is referred. As the main outcome of this thesis, the author provided an evolutionary method to compute (optimal) daily water pump schedules for the water distribution network of Sopron, Hungary. The algorithm is currently working in industry.