20世纪10个最好的算法

1、20世纪10个最好的算法human beings produced 10 famous algorithms in the 20th century. what is the algorithm?here is an article about the 10 algorithms that american scientists have come up with to take a lookthe top 10 algorithms of the 20th centurythree mirror mr.the origin of the word algorithmalgos is a gr

2、eek word meaning "pain algor is a latin word meaning coo 1 the two words are not algorithm (algorithm) the root of the word, the word algorithm is associated with the al - khwarizmi arab scholars of the 9th century, his books-'al muqabalah jabr w (algebra) evolved into the algebra textbook

3、of the middle school now.ad-khwarizmi stresses the systematic process of solving problems if he had lived to this day, he would be moved by the progress of his namethe best algorithm of the 20th centurythe best algorithm of the 20th century, the selection criteria of the computer age, was the most i

4、nfluential in the research and practice of science and engineering.here are the top 10 algorithms of the 20th century in chronological order.1. the monte carlo methodin 1946, john von neumann, who worked at the los alamos science laboratory, developed the metropolis algorithm, also known as the mont

5、e carlo method, by stan ulam and nick metropolismetropolis algorithm to stochastic process by imitation, to get a numerical problem and difficult to control a large number of degrees of freedom of combination with factorial scale approximate solution of the problem digital computer is a powerful too

6、l, calculation of uncertainty for randomness (uncertainty) the problem how to did not know at that time, metropolis algorithm is first used to generate random numbers, one of the algorithm to solve the problem of uncertainty.the simplex method of linear programmingin 1947, the rand corporation，s gro

7、rge dantzig created a simple form of linear programmingthe dantzig algorithm is one of the most successful algorithms for its extensive applications linear programming for those who want to stand on the economy, and also depends on whether the budget and other constraints to optimize the ability of

8、the industry, has a decisive influence (of course, the "real" problems in industry is often non-linear; sometimes, using the linear prograinining is the estimate of the budget, so as to simplify the model and precipitate) simplex method is a subtle method that achieves optimal solution. al

9、though in theory, the effect is exponential decay, but in practice the algorithm is highly effective - it itself shows some interesting things about the nature of the computingthe krylov subspace methodin 1950, magnus hestenes, eduard stiefel and cornelius lanczos, from the national bureau of standa

10、rds for numerical analysis, pioneered the development of the krylov subspacethese algorithms deal with the seemingly simple equation of the equation ax 二 b hidden, of course, the difficulty is that the n * n matrix a is a giant, the algebraic solution of x = b/a is not easy to calculate, indeed, &qu

11、ot;division" of the matrix is not a really useful concepts) iterative method, such as solving the shape of a kx (k + 1)二 kx (k) + b - ax (k) equation, the k is an ideal to "close" to a relatively simple matrix - led to the research of krylov subspace the krylov subspace, named after t

12、he russian mathematician nikolai krylov, was created by the matrix powers of the initial "residual" vector r (0)二 b-ax (0). when a is a symmetric matrix, lanczos finds an excellent way to generate an orthonormal basis for the seed space for the equations of symmetry, hestenes and stiefel p

13、ropose a better method called the conjugate gradient method over the past 50 years, many researchers have refined and expanded these algorithms a current set of methods includes the technique of solving asymmetric equations, such as gmres and bi-cgstab(gmres and bi-cgstab were first reported in the

14、1986 and 1992 siam journal on scientific and statistical computing)the decomposition method of matrix calculationin 1951, the alston householder system at oak ridge national laboratory explained the decomposition of matrix computing the research proves that it is extremely useful to decompose matrix

15、 factors into triangles, angles, orthogonal and other special forms of matrices this decomposition enables software researchers to produce flexible and efficient matrix packages this also promotes the rounding error analysis problem of one of the big problems in numerical linear algebra, (national p

16、hysical laboratory in london in 1961, james wilkinson based on the matrix is decomposed into and upper triangular matrix factor under the lu decomposition of the product, in the american journal of computer association (acm) published an article entitled ''matrix inverse error analysis of th

17、e direct method of important articles)fortran，s best compilerin 1957, john backus led a team at ibm to develop fortran，s best compiler the creation of the fortran is likely to be unique is the most important event in the history of computer programming: scientists (and others) can finally do not nee

18、d to rely on as terrible as hell machine code, can tell a computer what they want to do. although the standard of modern compiler is not too much - fortran i only contains 23500 assembly language instructions - early compiler can still complete surprisingly complex calculations it's like backus

19、in 1998, in the days of ieee annals of thethe history of computing on fortran i, ii, iii's recent history of article recalls: compiler "produced so efficient code, making the output to research its programmers were startled"the qr algorithm of matrix eigenvaluesfrom 1959 to 61, j. g f

20、francis of ferranti ltd in london found a way to calculate the value of the eigenvalues called qr algorithms the eigenvalues are probably the most important numbers associated with the matrix, and calculating them maybe the most tricky. - a square matrix transform into an upper triangular matrix is

21、almost'7 - meaning under the next to the main diagonal matrix of possible nonzero elements - on a diagonal line is relatively easy, but to produce a large number of error elimination, put the non-zero elements, it is not coimnon things qr algorithm is able to achieve this purpose, the method of

22、based on qr decomposition, a can be written as orthogonal matrix q and the product of a triangular matrix r, the iterative method to a = q (k) (k) into ra (k + 1)二=q (k) r (k) will accelerate to the upper triangular matrix in a little bit of a failure in the mid-1960s, the qr algorithm was once diff

23、icultthe problem of this eigenvalue problem becomes the calculation of routine proceduresfast classificationelliott: 1962 london brothers, ltd tony hoeire fast (in size) classification is proposed the n order of things according to the number or letters, in the mind is not what touches the monotony

24、of ordinary matter the challenge of intelligence is to invent a way of doing things quickly. hoare algorithm using the old division and control of the recursion strategy to solve the problem: pick an element as a "principal", put the rest of the elements is divided into "big" and

25、 "small" two heap (when compared to principal component), and then repeat this process in each pile though is likely to be severely scolded finished all n (n - 1) / 2 times more (in particular, if you put the principal as previously by size classification table column the first element of

26、the word!) the average number of times a fast taxonomy runs is 0 (nlog (n), and its elegant simplicity makes it a famous example of computational complexityfast fourier transformin 1965, ibm，s t. j.james cooley of the watson research center and john tukey at princeton university and at&t bell la

27、bs have revealed the rapid fourier transform (fft) to the public the most far-reaching algorithm in applied mathematics is undoubtedly the fft that makes the signal processing breakthrough the basic idea goes back to gauss (he needs to calculate the orbit of an asteroid), but cooley-tukey's pape

28、r makes clear how easy it is to calculate the fourier transform like fast taxonomies, fft relies on a strategy of splitting up and controlling, reducing the seemingly obnoxious 0 (n * n) to a delightful (nlog (n) but unlike fast classification, its execution (first glance) is nonintuitive and not st

29、raightforward it itself gives computer science a push to study the inherent complexity of computing problems and algorithms.integer relation detection algorithmin 1977, helaman ferguson and rodney forcade of brighamyoung university proposed an integer relationship detection algorithmthis is an age-o

30、ld question: given a group of real numbers, such as x (1), x (2), x (n), is there an integer a (1), a (2), a (n) (not all zero), so a (1) x (1) + a (2) x (2) + plus a (n), x (n)二 0 for n = 2, the long history of euclid's algorithm can do the work, calculate the various points in the expansion of

31、 x (l)/x (2). if x (l)/x (2) is rational, the expansion will terminate, and the "smallest" integer a (1) and a (2) will be given as appropriate. euclidean algorithm is not terminated, or if you simply because tired of computing - so in the process at least provide the size of the smallest

32、integer relationship of lower bound ferguson and forcade are more powerful, though this is harder to implement (and understand) for example, their detection algorithm is used to obtain logistic (logistic) mapping of the third and fourth bifurcation, b 二 3 544090 (3) and b (4)二 3. 564407 meet the acc

33、uracy coefficient of polynomial, (the latter is 120 order polynomial: it's the biggest coefficient is 257 八 30.) the algorithm has been shown to be useful in simplifying the calculation of feynman graphs in quantum field theory.fast multipolar algorithmin 1987, yale，s leslie greengard and vladimir rokhlin invented the rapid multipolar alg