Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Top 10: Los mejores algoritmos del Siglo XX

Top 10: Los mejores algoritmos del Siglo XX

Elizabeth Ramirez

November 15, 2018
Tweet

More Decks by Elizabeth Ramirez

Other Decks in Programming

Transcript

  1. Algoritmo: Viene de Muhammad ibn Musa al-Khwarizmi El mismo del

    libro “Al-jabr wa'l muqabalah” también conocido como Álgebra.
  2. • Metropolis Algorithm • Simplex for Linear Programming • Krylov

    Subspaces Algorithm • Matrix Decomposition Algorithm • The Fortran Optimizing Compiler • QR Algorithm • Quicksort Algorithm • Fast Fourier Transform Algorithm • Integer Relation Detection • Fast Multipole Method (Los tachados se los quedo debiendo)
  3. 1946: Metropolis Algorithm A.K.A Monte Carlo. John von Neumann, Stan

    Ulam, and Nick Metropolis at Los Alamos National Lab. By the Strong Law of Large Numbers: In general:
  4. 1946: Metropolis Algorithm A.K.A Monte Carlo. Probability Distributions. E.g. Queue

    Theory, single server recursion: S: Service time T: Interarrival time expected delay of the 5th customer.
  5. 1950: Krylov Subspaces Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos,

    from the Institute for Numerical Analysis at the National Bureau of Standards. Solve , A.K.A. most ubiquitous problem in Scientific Computing. Problem: when A is huge. E.g. Gaussian Elimination: Solution: iterative methods! Krylov subspace of dimension k, with
  6. 1951: Matrix Decomposition Alston Householder of Oak Ridge National Laboratory

    One of the most important ideas in Linear Algebra. Fundamental Decompositions: Cholesky, pivoted LU, QR, spectral, Schur, and SVD.
  7. 1959–61: QR Algorithm J.G.F. Francis of Ferranti Ltd., London. Guess

    which problem we’re solving again? Yes, Construct a set of orthonormal vectors that span each of the subspaces
  8. 1959–61: Fast Fourier Transform James Cooley of the IBM T.J.

    Watson Research Center and John Tukey of Princeton University and AT&T Bell Labs. Described by this guy (G. Strang) as “the most important numerical algorithm of our lifetime”. Takes discrete FT from to Given, the DFT is defined as: G