Dynamic verification is a new approach to formal verification, applicable to generic algorithms such as those found in the Standard Template Library (STL, part of the Draft ANSI/ISO C++ Standard Library). Using behavi...
详细信息
Dynamic verification is a new approach to formal verification, applicable to generic algorithms such as those found in the Standard Template Library (STL, part of the Draft ANSI/ISO C++ Standard Library). Using behavioral abstraction and symbolic execution techniques, verifications are carried out at an abstract level such that the results can be used in a variety of instances of the generic algorithms without repeating the proofs. This is achieved by substituting for type parameters of generic algorithms special data types that model generic concepts by accepting symbolic inputs and deducing outputs using inference methods. By itself, this symbolic execution technique supports testing of programs with symbolic values at an abstract level. For formal verification we also need to generate multiple program execution paths and use assertions (to handle while loops, for example), but we show how this can be achieved via directives to a conventional debugger program and an analysis database. The assertions must still be supplied, but they can be packaged separately and evaluated as needed by appropriate transfers of control orchestrated via the debugger. Unlike all previous verification methods, the dynamic verification method thus works without having to transform source code or process it with special interpreters. We include an example of the formal verification of an STL generic algorithm.
This bachelor thesis analyses algorithms working with the volume data, especially the triangle or polygon mesh. The results of the analysis are applied in the design of the generic library which can be templated with ...
详细信息
This bachelor thesis analyses algorithms working with the volume data, especially the triangle or polygon mesh. The results of the analysis are applied in the design of the generic library which can be templated with any implementa- tion of mesh satisfying requirements of the library. The library is written in C++ using the norm C++11 with assistance of the boost library. The choice of the programming language is supported by the strong emphasis on the run-time per- formance as well as the capabilities of C++ to analyze a templated code during the compile-time. Later in thesis is described the implemenation of the library, usage of the algorithms and their concepts, the purpose of the adapters - tools that allow to run algorithms over such an implementation of the mesh that is not properly designed for the algorithm. The technique used in the development of this library can be later applied in the library developement, thus adding new algorithms to the library.
The halting problem is undecidable - but can it be solved for "most" inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of ...
详细信息
The halting problem is undecidable - but can it be solved for "most" inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered in algorithmic information theory) using the notion of Kolmogorov complexity. We also consider some related questions about this framework and about asymptotic properties of the halting problem. In particular, we show that the fraction of terminating programs cannot have a limit, and all limit points are Martin-Lof random reals. We then consider mass problems of finding an approximate solution of halting problem and probabilistic algorithms for them, proving both positive and negative results. We consider the fraction of terminating programs that require a long time for termination, and describe this fraction using the busy beaver function. We also consider approximate versions of separation problems, and revisit Schnorr's results about optimal numberings showing how they can be generalized.
The Tau method is an accurate and efficient method for the numerical solution of ordinary differential equation (O.D.E) with polynomial coefficients. In [1] Adeniyi et al., we derived a recursive formula for a fast re...
详细信息
The Tau method is an accurate and efficient method for the numerical solution of ordinary differential equation (O.D.E) with polynomial coefficients. In [1] Adeniyi et al., we derived a recursive formula for a fast reliable computational error estimate of Tau method. In the present work, we present the generic algorithms for solving O.D.E. using the Tau method. The pseudocodes describing the algorithms are in C-like language. The algorithms are assembled into a reusable Tau objects' Class Hierarchy (TOCH) with specification given in the interface definition language (IDL) representation and implemented using the C+ + Programming language.
The research on generic algorithms is usually focused on software implement, which is always restricted in terms of high real-time by computer system because it is a serial calculation. This paper introduces a hardwar...
详细信息
ISBN:
(纸本)9781424417339
The research on generic algorithms is usually focused on software implement, which is always restricted in terms of high real-time by computer system because it is a serial calculation. This paper introduces a hardware structure on FPGA-Based generic algorithms, which programmed by VEDL language. All modules compilation and simulation were performed by Altera Quartus square 5.0 and were tested on EPIK100QC208-3. The experimental results show that the design achieves the required functions. At the end of this paper, a new idea of paralleled and pipelined hardware structure based on FPGA is presented.
In this research study the topic of Artificial Intelligence and Business is examined. AI methodologies and their usage in several organizations in various applications concerning staffing, careers etc. and hiring pred...
详细信息
ISBN:
(纸本)9781728155845
In this research study the topic of Artificial Intelligence and Business is examined. AI methodologies and their usage in several organizations in various applications concerning staffing, careers etc. and hiring predictions are discussed. The concept of genetic and generic algorithms with their several important aspects are discussed and various related applications in a wide spectrum of topics are presented. Various genetic programming implementations with the corresponding related software products are given and several AI software packages, genetic algorithmic methodologies and related applications are presented.
In this paper we consider generic algorithms for computational problems in cyclic groups. The model of a generic algorithm was proposed by Shoup at Eurocrypt '97. A generic algorithm is a general-purpose algorithm...
详细信息
ISBN:
(纸本)3540645187
In this paper we consider generic algorithms for computational problems in cyclic groups. The model of a generic algorithm was proposed by Shoup at Eurocrypt '97. A generic algorithm is a general-purpose algorithm that does not make use of any particular property of the representation of the group elements. Shoup proved the hardness of the discrete logarithm problem and the Diffie-Hellman problem with respect to such algorithms for groups whose order contains a large prime factor. By extending Shoup's technique we prove lower bounds on the complexity of generic algorithms solving different problems in cyclic groups, and in particular of a generic reduction of the discrete logarithm problem to the Diffie-Hellman problem. It is shown that the two problems are not computationally equivalent in a generic sense for groups whose orders contain a multiple large prime factor. This complements earlier results which stated this equivalence for all other groups. Furthermore, it is shown that no generic algorithm exists that computes p-th roots efficiently in a group whose order is divisible by p(2) if p is a large prime.
In this study, Genetic algorithms (GA) [1] in conjunction with network parallelization technique are utilized for the design and optimization of mobile phone antennas in a CAD derived environment. On the basis of a co...
详细信息
ISBN:
(纸本)9781424449682
In this study, Genetic algorithms (GA) [1] in conjunction with network parallelization technique are utilized for the design and optimization of mobile phone antennas in a CAD derived environment. On the basis of a commercial mobile phone CAD model, three types of internally embedded multi-band antenna are designed and optimized within a fixed volume. Through the use of network parallelization, optimization time can be significantly reduced.
The paper presents genetic algorithms, their properties and capabilities in solving computational problems. Using a genetic algorithm an optimization task of transportation - production regard to the transport and pro...
详细信息
ISBN:
(纸本)9783319453774;9783319453781
The paper presents genetic algorithms, their properties and capabilities in solving computational problems. Using a genetic algorithm an optimization task of transportation - production regard to the transport and processing of milk will be investigated. For the network of collection centers and processing plants (factories) the cost-optimal transportation plan regarding to raw materials to the relevant factories will be established. It is assumed that the functions defining the costs of processing are polynomials of the second degree. To solve the problem the program that uses genetic algorithms written in MATLAB will be used.
This paper presents a methodology for solving interdependent, multidomain networks with generic algorithms. The methodology enables modelling of very large systems. generic algorithms enable the system solver to be wr...
详细信息
This paper presents a methodology for solving interdependent, multidomain networks with generic algorithms. The methodology enables modelling of very large systems. generic algorithms enable the system solver to be written such that it is independent of the system type. The solution of the system equations is implemented with Graph Trace Analysis (GTA), where traces through the directed graph of the system are implemented with iterators. The solution technique incorporates a binary search algorithm for the solution of looped systems. Example electrical and fluid systems are solved.
暂无评论