Top ten algorithms
Locked
 
|
Supporting Owen's contention, it looks like the 'science' part of computer
science stopped in the 1960s - only two of the top ten algorithms are dated after 1965. Robert >From http://www.cecm.sfu.ca/personal/jborwein/algorithms.html Algorithms for the Ages "Great algorithms are the poetry of computation," says Francis Sullivan of the Institute for Defense Analyses' Center for Computing Sciences in Bowie, Maryland. He and Jack Dongarra of the University of Tennessee and Oak Ridge National Laboratory have put together a sampling that might have made Robert Frost beam with pride--had the poet been a computer jock. Their list of 10 algorithms having "the greatest influence on the development and practice of science and engineering in the 20th century" appears in the January/February issue of Computing in Science & Engineering. If you use a computer, some of these algorithms are no doubt crunching your data as you read this. The drum roll, please: 1. 1946: The Metropolis Algorithm for Monte Carlo. Through the use of random processes, this algorithm offers an efficient way to stumble toward answers to problems that are too complicated to solve exactly. 2. 1947: Simplex Method for Linear Programming. An elegant solution to a common problem in planning and decision-making. 3. 1950: Krylov Subspace Iteration Method. A technique for rapidly solving the linear equations that abound in scientific computation. 4. 1951: The Decompositional Approach to Matrix Computations. A suite of techniques for numerical linear algebra. 5. 1957: The Fortran Optimizing Compiler. Turns high-level code into efficient computer-readable code. 6. 1959: QR Algorithm for Computing Eigenvalues. Another crucial matrix operation made swift and practical. 7. 1962: Quicksort Algorithms for Sorting. For the efficient handling of large databases. 8. 1965: Fast Fourier Transform. Perhaps the most ubiquitous algorithm in use today, it breaks down waveforms (like sound) into periodic components. 9. 1977: Integer Relation Detection. A fast method for spotting simple equations satisfied by collections of seemingly unrelated numbers. 10. 1987: Fast Multipole Method. A breakthrough in dealing with the complexity of n-body calculations, applied in problems ranging from celestial mechanics to protein folding. >From Random Samples, Science page 799, February 4, 2000. -------------- next part -------------- An HTML attachment was scrubbed... URL: http://constantinople.hostgo.com/pipermail/friam_redfish.com/attachments/20040114/1bf0af57/attachment.htm |
|
|
Top ten algorithmsTake a look at David Berlinski's "Advent of the Algorithm"
(http://www.amazon.com/gp/reader/0156013916/ref=sib_dp_pt/102-9698779-377136 7#reader-link). -----Original Message----- From: [hidden email] [mailto:[hidden email]]On Behalf Of Robert Holmes Sent: Miercoles, 14 de Enero de 2004 08:07 a.m. To: FRIAM Subject: [FRIAM] Top ten algorithms Supporting Owen's contention, it looks like the 'science' part of computer science stopped in the 1960s - only two of the top ten algorithms are dated after 1965. Robert From http://www.cecm.sfu.ca/personal/jborwein/algorithms.html Algorithms for the Ages "Great algorithms are the poetry of computation," says Francis Sullivan of the Institute for Defense Analyses' Center for Computing Sciences in Bowie, Maryland. He and Jack Dongarra of the University of Tennessee and Oak Ridge National Laboratory have put together a sampling that might have made Robert Frost beam with pride--had the poet been a computer jock. Their list of 10 algorithms having "the greatest influence on the development and practice of science and engineering in the 20th century" appears in the January/February issue of Computing in Science & Engineering. If you use a computer, some of these algorithms are no doubt crunching your data as you read this. The drum roll, please: 1.. 1946: The Metropolis Algorithm for Monte Carlo. Through the use of random processes, this algorithm offers an efficient way to stumble toward answers to problems that are too complicated to solve exactly. 2.. 1947: Simplex Method for Linear Programming. An elegant solution to a common problem in planning and decision-making. 3.. 1950: Krylov Subspace Iteration Method. A technique for rapidly solving the linear equations that abound in scientific computation. 4.. 1951: The Decompositional Approach to Matrix Computations. A suite of techniques for numerical linear algebra. 5.. 1957: The Fortran Optimizing Compiler. Turns high-level code into efficient computer-readable code. 6.. 1959: QR Algorithm for Computing Eigenvalues. Another crucial matrix operation made swift and practical. 7.. 1962: Quicksort Algorithms for Sorting. For the efficient handling of large databases. 8.. 1965: Fast Fourier Transform. Perhaps the most ubiquitous algorithm in use today, it breaks down waveforms (like sound) into periodic components. 9.. 1977: Integer Relation Detection. A fast method for spotting simple equations satisfied by collections of seemingly unrelated numbers. 10.. 1987: Fast Multipole Method. A breakthrough in dealing with the complexity of n-body calculations, applied in problems ranging from celestial mechanics to protein folding. From Random Samples, Science page 799, February 4, 2000. -------------- next part -------------- An HTML attachment was scrubbed... URL: http://constantinople.hostgo.com/pipermail/friam_redfish.com/attachments/20040114/ee230002/attachment.htm |
|
|
Top ten algorithmsI think this article is relevant to some recent messages
about odd spam: http://www.wired.com/news/infostructure/0,1377,61886,00.html |
|
|
In reply to this post by Robert Holmes
Offering an opposing view to:
> Supporting Owen's contention, it looks like the 'science' part of computer > science stopped in the 1960s - only two of the top ten algorithms are > dated after 1965. I would suggest that this contention is a bit harsh. If you look at the physics community (my background), a Top 10 Greatest Contributions to Physics might look like Newton (circa 1700): Laws of Motion Copernicus (circa 1500): De Revolutionibus Kepler (circa 1600): Laws of Planetary Motion Avagadro (1811): Atoms and the laws of gases Faraday (1833) : Discovery of electrons Rutherford (1911) : Discovery of compact nuclei Einstein (1920): General Relativity Bernoulli (circa 1700): Fluid Motion Theory of Light The Standard Model of Particle Physics And so many more. My list is surely distorted (and written very quickly), but it is quite difficult to argue that anything from the last 20 years warrants inclusion on a Top 10 list for physics. Even chaos theory (my own background) is too old and not sufficiently important compared to the rest (IMHO). I offer physics as a counter example, because I certainly don't think it is dead -- just that we are standing on the shoulders of giants. I would argue that if simulation and data mining are included in "Computer Science", which they apparently are from reading that Top 10 list, then the field is by no means dead. Joseph L. Breeden, Ph.D. | 3900 Paseo del Sol | (p) 505 438-9501 x101 Strategic Analytics Inc. | Santa Fe, NM 87507 | (f) 775 256-8984 |
|
|
In reply to this post by Robert Holmes
I thought the contention was misguided when Owen first stated it.
I expect there is a lot going on that would be found if you were looking at the relevant publications. E.g., check out the JACM site. You many not see developments that are as obviously big as the items listed in the top 10 algorithms (which are actually not all algorithms), but that does not mean that work (or progress) has stopped. Also, how do you define computer science ? What about cryptography ? that is certainly intimately connected to computers. Parallel computing ? Distributed computing ? Grid computing ? Application areas such as molecular genetics ? It is not even necessarily the case that we are standing on the shoulders of giants. I suspect that although some of the more obvious low-hanging fruit has been plucked, the best is still to come. Like claims that we have reached the end of history or the end of science, I think the contention is premature. -----Original Message----- From: [hidden email] [mailto:[hidden email]] On Behalf Of Joseph L. Breeden Sent: Thursday, January 15, 2004 10:38 AM To: [hidden email] Subject: [FRIAM] RE: Top ten algorithms Offering an opposing view to: > Supporting Owen's contention, it looks like the 'science' part of computer > science stopped in the 1960s - only two of the top ten algorithms are > dated after 1965. I would suggest that this contention is a bit harsh. If you look at the physics community (my background), a Top 10 Greatest Contributions to Physics might look like Newton (circa 1700): Laws of Motion Copernicus (circa 1500): De Revolutionibus Kepler (circa 1600): Laws of Planetary Motion Avagadro (1811): Atoms and the laws of gases Faraday (1833) : Discovery of electrons Rutherford (1911) : Discovery of compact nuclei Einstein (1920): General Relativity Bernoulli (circa 1700): Fluid Motion Theory of Light The Standard Model of Particle Physics And so many more. My list is surely distorted (and written very quickly), but it is quite difficult to argue that anything from the last 20 years warrants inclusion on a Top 10 list for physics. Even chaos theory (my own background) is too old and not sufficiently important compared to the rest (IMHO). I offer physics as a counter example, because I certainly don't think it is dead -- just that we are standing on the shoulders of giants. I would argue that if simulation and data mining are included in "Computer Science", which they apparently are from reading that Top 10 list, then the field is by no means dead. Joseph L. Breeden, Ph.D. | 3900 Paseo del Sol | (p) 505 438-9501 x101 Strategic Analytics Inc. | Santa Fe, NM 87507 | (f) 775 256-8984 ==================== FRIAM Applied Complexity Group listserv Meets Fridays 9AM @ Jane's Cafe Lecture schedule, archives, unsubscribe, etc.: http://www.friam.org |
|
|
In reply to this post by Robert Holmes
Yet another huge area in which I believe research is very active is computer
graphics. -----Original Message----- From: [hidden email] [mailto:[hidden email]] On Behalf Of Joseph L. Breeden Sent: Thursday, January 15, 2004 10:38 AM To: [hidden email] Subject: [FRIAM] RE: Top ten algorithms Offering an opposing view to: > Supporting Owen's contention, it looks like the 'science' part of computer > science stopped in the 1960s - only two of the top ten algorithms are > dated after 1965. I would suggest that this contention is a bit harsh. If you look at the physics community (my background), a Top 10 Greatest Contributions to Physics might look like Newton (circa 1700): Laws of Motion Copernicus (circa 1500): De Revolutionibus Kepler (circa 1600): Laws of Planetary Motion Avagadro (1811): Atoms and the laws of gases Faraday (1833) : Discovery of electrons Rutherford (1911) : Discovery of compact nuclei Einstein (1920): General Relativity Bernoulli (circa 1700): Fluid Motion Theory of Light The Standard Model of Particle Physics And so many more. My list is surely distorted (and written very quickly), but it is quite difficult to argue that anything from the last 20 years warrants inclusion on a Top 10 list for physics. Even chaos theory (my own background) is too old and not sufficiently important compared to the rest (IMHO). I offer physics as a counter example, because I certainly don't think it is dead -- just that we are standing on the shoulders of giants. I would argue that if simulation and data mining are included in "Computer Science", which they apparently are from reading that Top 10 list, then the field is by no means dead. Joseph L. Breeden, Ph.D. | 3900 Paseo del Sol | (p) 505 438-9501 x101 Strategic Analytics Inc. | Santa Fe, NM 87507 | (f) 775 256-8984 ==================== FRIAM Applied Complexity Group listserv Meets Fridays 9AM @ Jane's Cafe Lecture schedule, archives, unsubscribe, etc.: http://www.friam.org |
«
Return to Friam
|
1 view|%1 views
| Free forum by Nabble | Edit this page |