An O(ND) diffrerence algorithm and its variations Myers E.W.
Myers E.W.
Количество страниц: 15
Язык: Английский
Формат: PDF / RAR
Формат файла: RAR
The problems of finding a longest common subsequence of two sequences A and В and a shortest edit script for transforming A into В have long been known to be dual problems. In this paper, they are shown to be equivalent to finding a shortest/longest path in an edit graph. Using this perspective, a simple O(ND) time and space algorithm is developed where N is the sum of the lengths of A and В and D is the size of the minimum edit script for A and B. The algorithm performs well when differences are small (sequences are similar) and is consequently fast in typical applications. The algorithm is shown to have 0(N + D2) expected-time performance under a basic stochastic model. A refinement of the algorithm requires only O(N) space, and the use of suffix trees leads to an 0(NlgN + D2) time variation.
- Random number generators Marsaglia G.
The author discusses some promising new random number generators, as well as formulates the mathematical basis that makes them random variables in the same sense as more familiar ones in probability and statistics, emphasizing his view that randomness exists only in the sense of mathematics - Principles of floating point computation Qiao S.
Before investigating numerical software engineering, we must research the principles of finite precision computing - Discrete mathematics. Elementary and beyond Lovasz L., Pelikan J., Vesztergombi K.
For most students, the first and often only course in college mathematics is calculus It is true that calculus is the single most important field of mathematics, whose emergence in the seventeenth century signaled the birth of modern mathematics and was the key to the successful applications of mathematics in the sciences and engineering - Termination of a floating point computations Serebrenik A.
Numerical computations form an essential part of almost any real-world program Traditional approaches to termination of logic programs are restricted to domains isomorphic to (N, >), more recent works study termination of integer computations where the lack of well-foundness of the integers has to be taken into account