Last Updated:

5 algorithms that changed the world

An algorithm is the simplest system of actions for solving a problem or class of problems. Algorithms consist of a finite number of well-defined individual steps. Formulated in natural language, they are implemented in computer programs. When solving a problem, specific initial data is converted into specific results.

Here are five algorithms that have had a significant impact on our world.

1. Metropolis algorithm for Monte Carlo method

 

The Metropolis algorithm is a Monte Carlo method with Markov chains that is used to generate system states according to the Boltzmann distribution.

On the basis of this algorithm, a more generalized Metropolis-Hastings algorithm was derived, which allows you to model sequences of random variables, more precisely the Markov chain.

In Markov chains, the target distribution converges with the stationary distribution. This is most often observed in cases where the distributions of random variables cannot be modeled naturally.

2. Simplex method of linear programming

 

The simplex method (also known as the simplex algorithm) is a numerical optimization method for solving linear optimization problems, also known as linear programs (LP). He solves such a problem only after a finite number of steps or determines its insoluble or unlimited.

The main idea of simplex methods was presented by George Danzig in 1947. Since then, they have become the most important methods of solving linear optimization problems in practice due to numerous improvements. Simplex methods are methods of finding a reference plan.

3. Fast Fourier transform

 

The Fast Fourier Transform (FFT) is an algorithm for accelerating the calculation of the discrete Fourier transform (DPF). It can be used to decompose a digital signal into frequency components and then analyze them. Similarly, the inverse fast Fourier transform (OBPF) is used for a discrete inverse Fourier transform. Obpf uses the same algorithms, but with conjugate coefficients.

FFT finds many applications in engineering, natural sciences, and applied mathematics. It is also used in mobile technologies such as UMTS and LTE, and wireless data transmission, such as WLAN.

4. Fast sort algorithm

 

Fast sort algorithm

Quicksort is a fast, recursive, unstable sorting algorithm that works on a divide-and-conquer basis. It was developed around 1960 by C. Anthony R. Hoare and subsequently refined by many researchers.

The advantage of the algorithm is a very short internal loop (which significantly increases the speed of execution). It does not require additional memory (except for the additional space required in the call stack for recursion).

5. QR algorithm for calculating eigenvalues

 

QR algorithm

A QR algorithm is a numerical method for calculating all eigenvalues and often eigenvalues of a quadratic matrix. The QR method, or QR iteration, is based on QR decomposition and was introduced independently by John G. F. Francis and V. N. Kublanovskaya in 1961–1962. The predecessor of the QR algorithm was heinz Rutishauser's LR algorithm (1958), based on LR decomposition and less stable.

Often iterations from the QR algorithm converge to the Shape of the Shura matrix. Therefore, the original procedure is quite complex – even on modern computers – and is not applicable to matrices with hundreds of thousands of rows and columns.

Derived variants such as the multi-shift method of Z. Bai and James Demmel (1989) and the numerically more stable version of K. Brahman, R. Byers and R. Mathias (2002) have operational execution periods with a cubic dependence on the size of the matrix. The latter method is implemented in the LAPACK numerical calculation library, which is used in many computer algebra systems for numerical matrix algorithms.

If I had to choose one of these algorithms, my favorite would be the FFT. The Fast Fourier Transform (FFT) not only finds many applications in engineering, natural sciences and applied mathematics, but also admires its inherent beauty.