新书推介:《语义网技术体系》
作者:瞿裕忠,胡伟,程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
  •   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] 计算机科学论坛计算机理论与工程『 算法理论与分析 』 → The Best of the 20th Century : Editors Name Top 10 Algorithms 查看新帖用户列表

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 34484 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子 浏览下一篇主题
     * 贴子主题: The Best of the 20th Century : Editors Name Top 10 Algorithms 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     Logician 帅哥哟,离线,有人找我吗?天蝎座1984-10-28
      
      
      威望:9
      头衔:逻辑爱好者
      等级:研三(收到IBM CRL的Offer了)(版主)
      文章:1219
      积分:10357
      门派:IEEE.ORG.CN
      注册:2005/3/12

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客楼主
    发贴心情 The Best of the 20th Century : Editors Name Top 10 Algorithms

    The Best of the 20th Century : Editors Name Top 10 Algorithms
    By Barry A. Cipra

                                                                SIAM NEWS MAY 2000

    Algos is the Greek word for pain.  Algor is Latin, to be cold.  Neither is the root for algorithm, which stems instead from al-Khwarizmi, the name of the ninth-century Arab scholar whose book al-jabr wa'l muqabalah developed into today's high school algebra textbooks.  Al-Khwarizmi stressed the importance of methodical procedures for solving problems.  Were he around today, he'd no doubt be impressed by the advances in his eponymous approach.

    Some of the very best algorithms of the computer age are highlighted in the January/February 2000 issue of Computing in Science & Engineering, a joint publication of the American Institute of Physics and the IEEE Computer Society.  Guest editors Jack Dongarra of the University of Tennessee and Oak Ridge National Laboratory and Francis Sullivan of the Center for Computing Sciences at the Institute of Defense Analyses put together a list they call the "Top Ten Algorithms of the Century".

    "We tried to assemble the 10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century,"  Dongarra and Sullivan write.  As with any top-10 list, their selections - and non-selections - are bound to be controversial, they acknowledge.  When it comes to picking the algorithmic best, there seems to be no best algorithm.

    Without further ado, here's the CiSE top-10 list, in chronological order.  (Dates and names associated with the algorithms should be read as first-order approximations.  Most algorithms take shape over time, with many contributors.)

    1946 : John von Neumann, Stan Ulam, and Nick Metropolis all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo Method.

    The Metropolis algorithm aims to obtain approximate solutions to numerical problems with unmanageably many degrees of freedom and to combinatorial problems of factorial size, by mimicking a random process.  Given the digital computer's reputation for deterministic calculation, it's fitting that one of its earliest applications was the generation of random numbers.

    1947 : George Dantzig, at the RAND Corporation, creates the simplex method for linear programming.  

    In terms of widespread application, Dantzig's algorithm is one of the most successful of all time : Linear programming dominates the world of industry, where economic survival depends on the ability to optimize within budgetary and other constraints.  (Of course, the "real" problems of industry are often nonlinear ; the use of linear programming is sometimes dictated by the computational budget.)  The simplex method is an elegant way of arriving at optimal answers.  Although theoretically susceptible to exponential delays, the algorithm in practice is highly efficient - which in itself says something interesting about the nature of computation.

    1950 : Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos, all from the Institute for Numerical Analysis at the National Bureau of Standards, initiate the development of Krylov subspace iteration methods.

    These algorithms address the seemingly simple task of solving equations of the form .  The catch, of course, is that A is a huge  matrix, so that the algebraic answer is not so easy to compute.  (Indeed, matrix "division" is not a particularly useful concept.)  Iterative methods - such as solving equations of the form with a simpler matrix K that's ideally "close" to A - lead to the study of Krylov subspaces.  Named for the Russian mathematician Nikolai Krylov, Krylov subspaces are spanned by powers of a matrix applied to an initial "remainder" vector .  Lanczos found a nifty way to generate an orthogonal basis for such a subspace when the matrix is symmetric.  Hestenes and Stiefel proposed an even niftier method, known as the conjugate gradient method, for systems that are both symmetric and positive definite.  Over the last 50 years, numerous researchers have improved and extended these algorithms.  The current suite includes techniques for non-symmetric systems, with acronyms like GMRES and Bi-CGSTAB.  (GMRES and Bi-CGSTAB premiered in SIAM Journal of Scientific and Statistical Computing, in 1986 and 1992, respectively.)

    1951 : Alston Householder of Oak Ridge National Laboratory formalizes the decompositional approach to matrix computations

    The ability to factor matrices into triangular, diagonal, orthogonal, and other special forms has turned out to be extremely useful.  The decompositional approach has enabled software developers to produce flexible and efficient matrix packages.  It also facilitates the analysis of rounding errors, one of the big bugbears of numerical linear algebra.  (In 1961, James Wilkinson of the National Physical Laboratory in London published a seminal paper in the Journal of the ACM, titled "Error Analysis of Direct Methods of Matrix Inversion," based on the LU decomposition of a matrix as a product of lower and upper triangular factors.)

    1957 : John Backus leads a team at IBM in developing the Fortran optimizing compiler.

    The creation of Fortran may rank as the single most important event in the history of computer programming : Finally, scientists (and others) could tell the computer what they wanted it to do, without having to descent into the netherworld of machine code.  Although modes by modern compiler standards - Fortran I consisted of a mere 23.500 assembly-language instructions - the early compiler was nonetheless capable of surprisingly sophisticated computations.  As Backus himself recalls in a recent history of Fortran I, II and III, published in 1998 in the IEEE Annals of the History of Computing, the compiler "produced code of such efficiency that its output would startle the programmers who studied it."

    1959-61 : J.G.F. Francis of Ferranti Ltd., London, finds a stable method for computing eigenvalues, known as the QR algorithm.

    Eigenvalues are arguable the most important numbers associated with matrices - and they can be the trickiest to compute.  It's relatively easy to transform a square matrix into a matrix that's "almost" upper triangular, meaning one with a single extra set of nonzero entries just below the main diagonal.  But chipping away those final nonzeros, without launching an avalanche error, is nontrivial.  The QR algorithm is just the ticket.  Based on the QR decomposition, which writes A as the product of an orthogonal matrix Q and an upper triangular matrix R, this approach iteratively changes into , with a few bells and whistles for accelerating convergence to upper triangular form.  By the mid-1960s, the QR algorithm had turned once-formidable eigenvalue problems into routine calculations.

    1962 : Tony Hoare of Elliott Brothers, Ltd., London, presents Quicksort.

    Putting N things in numerical or alphabetical order is mind-numbingly mundane.  The intellectual challenge lies in devising ways of doing so quickly.  Hoare's algorithm used the age-old recursive strategy of divide and conquer to solve the problem : Pick one element as a "pivot", separate the rest into piles of "big" and "small" elements (as compared with the pivot), and the repeat this procedure on each pile.  Although it's possible to get stuck doing all  comparisons (especially if you use as your pivot the first item on a list that's already sorted !), Quicksort runs on average with  efficiency.  Its elegant simplicity has made Quicksort the posterchild of computational complexity.

    1965 : James Cooley of the IBM T.J. Watson Research Center and John Tukey of Princeton University ant AT&T Bell Laboratories unveil the fast Fourier transform.

    Easily the most far-reaching algorithm in applied mathematics, the FFT revolutionized signal processing.  The underlying idea goes back to Gauss (who needed to calculate orbits of asteroids), but it was the Cooley-Tukey paper that made it clear how easily Fourier transforms can be computed.  Like Quicksort, the FFT relies on a divide-and-conquer strategy to reduce an ostensibly  chore to an  frolic.  But unlike Quicksort, the implementation is (at first sight) nonintuitive and less than straightforward.  This in itself gave computer science an impetus to investigate the inherent complexity of computational problems and algorithms.

    1977 : Helaman Ferguson and  Rodney Forcade of Brigham Young University advance an integer relation detection algorithm.

    The problem is an old one : Given a bunch of real numbers, say , are their integers (not all 0)for which ?  For n=2, the venerable Euclidean algorithm does the job, computing terms in the continued-fraction expansion of .  If  is rational, the expansion terminates and, with proper unraveling, given the "smallest" integers a1 and a2.  If the Euclidean algorithm doesn't terminate - or if you simply get tired of computing it - then the unraveling procedure at least provides lower bounds on the size of the smallest integer relation.  Ferguson and Forcade's generalization, although much more difficult to implement (and to understand), is also more powerful.  Their detection algorithm, for example, has been used to find the precise coefficients of the polynomials satisfied by the third and fourth bifurcation points, B3 = 3.544090 and B4 = 3.564407, of the logistic map.  (The latter polynomial is the degree of 120 ; its largest coefficient if 25730.)  It has also proved useful in simplifying calculations with Feynman diagrams in quantum field theory.

    1987 : Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipole algorithm.

    This algorithm overcomes one of the biggest headaches of N-body simulations : the fact that accurate calculations of the motions of N particles interacting via gravitational or electrostatic forces (think stars in a galaxy, or atoms in a protein) would seem to require  computations - one for each pair of particles.  The fast multipole algorithm gets by with  computations.  It does so by using multipole expansions (net charge or mass, dipole moment, quadrupole, and so forth) to approximate the effects of a distant group of particles on a local group.  A hierarchical decomposition of space is used to define everlarger groups as distances increase.  One of the distinct advantages of the fast multipole algorithm is that it comes equipped with rigorous error estimates, a feature that many methods lack.

    What new insights and algorithms will the 21st century bring ?  The complete answer obviously won't be known for another hundred years.  One thing seems certain, however.  As Sullivan writes in the introduction of the top-10 list, "The new century is not going to be very restful for us, but is not going to be dull either !"

    Barry A. Cipra is a mathematician and writer based in Northfield, Minnesota


       收藏   分享  
    顶(0)
      




    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/2/23 13:31:00
     
     toniee 帅哥哟,离线,有人找我吗?
      
      
      等级:大一新生
      文章:4
      积分:71
      门派:XML.ORG.CN
      注册:2006/7/10

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给toniee发送一个短消息 把toniee加入好友 查看toniee的个人资料 搜索toniee在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看toniee的博客2
    发贴心情 
    哪里可以下载楼主的这本书呢?谢谢!

    zwfchuan@21cn.com

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/7/10 15:04:00
     
     pansy 美女呀,离线,快来找我吧!射手座1984-12-6
      
      
      等级:大一新生
      文章:5
      积分:75
      门派:IEEE.ORG.CN
      注册:2006/12/4

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给pansy发送一个短消息 把pansy加入好友 查看pansy的个人资料 搜索pansy在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看pansy的博客3
    发贴心情 
    up

    ----------------------------------------------
    [Nanjing -> Lille]

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/12/4 14:39:00
     
     Angelo.j63 帅哥哟,离线,有人找我吗?
      
      
      等级:大一新生
      文章:3
      积分:71
      门派:XML.ORG.CN
      注册:2006/5/23

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给Angelo.j63发送一个短消息 把Angelo.j63加入好友 查看Angelo.j63的个人资料 搜索Angelo.j63在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看Angelo.j63的博客4
    发贴心情 
    It's Great!
    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2007/4/24 21:16:00
     
     L-Corporal 帅哥哟,离线,有人找我吗?魔羯座1986-12-25
      
      
      等级:大一新生
      文章:5
      积分:77
      门派:XML.ORG.CN
      注册:2008/4/27

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给L-Corporal发送一个短消息 把L-Corporal加入好友 查看L-Corporal的个人资料 搜索L-Corporal在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看L-Corporal的博客5
    发贴心情 
    好难哦

    ----------------------------------------------
    好好学习

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2008/4/28 12:02:00
     
     jsmlbl 帅哥哟,离线,有人找我吗?
      
      
      等级:大一(猛啃高等数学)
      文章:14
      积分:107
      门派:XML.ORG.CN
      注册:2008/7/2

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给jsmlbl发送一个短消息 把jsmlbl加入好友 查看jsmlbl的个人资料 搜索jsmlbl在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看jsmlbl的博客6
    发贴心情 
    没看懂!
    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2008/7/3 8:43:00
     
     yw168 帅哥哟,离线,有人找我吗?
      
      
      等级:大一新生
      文章:1
      积分:54
      门派:XML.ORG.CN
      注册:2008/10/21

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给yw168发送一个短消息 把yw168加入好友 查看yw168的个人资料 搜索yw168在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看yw168的博客7
    发贴心情 
    很难啊
    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2008/10/21 11:23:00
     
     GoogleAdSense
      
      
      等级:大一新生
      文章:1
      积分:50
      门派:无门无派
      院校:未填写
      注册:2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/3/28 21:42:02

    本主题贴数8,分页: [1]

    管理选项修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 解固 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    109.375ms