algorithm

from Wikipedia, the free encyclopedia
Al-Chwarizmi , who gave the algorithm its name , on a Soviet postage stamp on the occasion of his 1200th birthday

An algorithm is a clear instruction for the solution of a problem or a class of problems. Algorithms consist of a finite number of well-defined individual steps. So that they can for execution in a computer program implemented , but also in human language are formulated. When solving a problem , a specific input is converted into a specific output.

definition

Turing machines and the term algorithm

The lack of mathematical accuracy of the term algorithm bothered many mathematicians and logicians of the 19th and 20th centuries, which is why a whole series of approaches was developed in the first half of the 20th century that should lead to a precise definition. A central role is played here the concept of Turing machine of Alan Turing one. Further formalizations of the concept of computability are the register machines , the lambda calculus ( Alonzo Church ), recursive functions , Chomsky grammars (see Chomsky hierarchy ) and Markov algorithms .

It was shown - with a significant contribution from Alan Turing himself - that all these methods have the same computational power (are equally powerful ). They can be emulated by a Turing machine , and conversely, they can emulate a Turing machine.

With the help of the term Turing machine, the following formal definition of the term can be formulated:

A calculation rule for solving a problem is called an algorithm if and only if there is a Turing machine that is equivalent to this calculation rule and that stops for every input that has a solution.

The following properties of an algorithm can be derived from this definition:

  1. The procedure must be clearly describable in a finite text (finiteness).
  2. Every step of the procedure must actually be feasible (feasibility).
  3. The method may only require a finite amount of storage space at any point in time (dynamic finiteness, see space complexity ).
  4. The procedure may only require a finite number of steps ( termination , see also time complexity ).

In addition, the term algorithm is often restricted to the following properties in practical areas:

  1. The algorithm must deliver the same result under the same conditions ( determinacy ).
  2. The next rule to be applied in the procedure is clearly defined at each point in time ( determinism ).

Church-Turing thesis

The Church-Turing thesis states that every intuitively calculable problem can be solved by a Turing machine. As a formal criterion for an algorithm, one uses the implementability in any formalism equivalent to a Turing machine, in particular the implementability in a programming language - however, this does not yet provide the termination required by Church .

The concept of calculability is defined in such a way that a problem can be calculated precisely when there is a (terminating) algorithm for the problem, that is, when an appropriately programmed Turing machine could solve the problem in a finite time .

It should be noted that the ambiguity of the term "intuitively computable problem" makes the mathematical proof of this thesis impossible. It is theoretically conceivable that there are intuitively calculable problems that are not considered “calculable” according to this definition. However, no such problem has been found to date.

Abstract automata

Turing machines harmonize well with the abstract mathematical calculable functions , but real problems are much more complex, so other machines have been suggested.

These machines differ in the power of the commands; Instead of the simple operations of the Turing machine, they can sometimes carry out powerful operations, such as Fourier transformations , in one calculation step.

Or they are not limited to one operation per calculation step, but enable parallel operations, such as adding two vectors in one step.

A model of a real machine is the Sequential Abstract State Machine (short seq.ASM ) with the following properties:

An algorithm of a seq. ASM is supposed to

  • can be specified by a finite program text
  • can be performed gradually
  • terminate for certain states, but does not always have to terminate (useful counterexamples for the requirement that termination must always be made would be a program that continuously finds prime numbers, or an operating system)
  • can only change a limited number of states per step (limitation of parallelism)
  • can only inspect a limited number of states per step (limitation of exploration).

Computer science and mathematics

Algorithms are one of the central topics in computer science and mathematics . They are the subject of several specialist areas in theoretical computer science , complexity theory and computability theory , and sometimes a separate department is dedicated to algorithms or algorithm theory . In the form of computer programs and electronic circuits, algorithms control computers and other machines .

Algorithm and programs

There are different formal representations for algorithms. These range from the algorithm as an abstract counterpart to a program specifically tailored to a machine (i.e. the abstraction takes place here by omitting the details of the real machine, the program is a specific form of the algorithm, adapted to the needs and possibilities of the real machine) to to the view that algorithms are precisely the machine programs of Turing machines (whereby here the abstraction takes place in the use of the Turing machine itself, that is, an ideal mathematical machine ).

Algorithms can be graphically represented in program flow charts according to DIN 66001 or ISO 5807 .

First computer algorithm

The first algorithm intended for a computer (for computing Bernoulli numbers ) was recorded in 1843 by Ada Lovelace in her notes on Charles Babbag's Analytical Engine . She is therefore considered to be the first female programmer . Because Charles Babbage could not complete his analytical engine, Ada Lovelace's algorithm was never implemented on it.

Todays situation

Principle of the Rete algorithm for expert systems ; published: 1979; free

Algorithms for computers today are as diverse as the applications they are supposed to enable. Thousands of algorithms can be found, from electronic control units for use in vehicles to spelling and sentence structure control in a word processor to analyzing stock markets . With regard to the ideas and principles on which a computer program is based, an algorithm is usually denied copyright protection . However, depending on the national structure of intellectual property rights, computer science algorithms are accessible to patent protection , so that copyright-free individual works, as the result of one's own intellectual creation, can nevertheless not always be freely exploited economically. This concerns or concerned z. B. algorithms that are based on the mathematics of the Hough transformation (decades old, but repeatedly updated concept with new registration), programs that wanted to read and write the GIF image format , or programs in the field of audio and video processing , since the associated algorithms, as implemented in the associated codecs , are often not freely available. The corresponding savings potential for all users worldwide ( one million USD was once mentioned on DEC XCON for the Rete algorithm ) should today easily exceed the limit of one billion USD per year by a factor of ten.

Differentiation from heuristics

The transition between algorithms and heuristics is fluid: A heuristic is a method of using incomplete input data to achieve results that are as meaningful as possible. Many heuristic approaches are themselves precisely defined and thus algorithms. For some, however, it is not precisely specified in every step how to proceed - the user has to "guess cheaply". They cannot (completely) be formulated as an algorithm.

properties

Determination

An algorithm is determined if it delivers the same results every time it is executed with the same start conditions and inputs.

determinism

An algorithm is deterministic if the next step is clearly defined at each point in time when the algorithm is executed . If there is more than one possibility at at least one point (without a specification which one to choose), then the entire algorithm is nondeterministic .

Examples of deterministic algorithms are bubble sort and the Euclidean algorithm . It applies here that every deterministic algorithm determines, while not every determined algorithm is deterministic. So Quicksort with random choice of the pivot element an example of a deterministic, but not deterministic algorithm, as its result for the same input and unambiguous order is always the same, but there is done the way random.

In general, nondeterministic algorithms cannot be implemented directly with any real machine (not even with quantum computers ) .

An example of a nondeterministic algorithm would be a recipe that describes several variants. It is up to the cook which one he would like to carry out. Even walking through a maze leaves several options at each junction, and in addition to many dead ends, several paths can lead to the exit.

Finiteness

Static Finiteness

The description of the algorithm has a finite length, so the source text must consist of a limited number of characters.

Dynamic finiteness

An algorithm may only require a limited amount of storage space at any point in time during its execution.

Termination

An algorithm ' terminates everywhere ' or 'is terminating' if it stops after a finite number of steps (or stops in a controlled manner) - for every possible input. A non-terminating algorithm (thus not coming to any result) gets into a so-called infinite loop (for some inputs).

For some processes a non-terminating behavior is desired: e.g. control systems, operating systems and programs that are based on interaction with the user. Unless the user issues a command to exit, these programs by design continue to run indefinitely. Donald Knuth suggests in this context, not terminating algorithms and computational methods (Computational Methods) to call.

In addition, the termination of an algorithm (the halt problem ) cannot be decided . That is, the problem of determining whether an (any) algorithm terminates with any input cannot be solved by an algorithm.

effectiveness

The effect of every instruction of an algorithm must be clearly defined.

Examples of (further) properties of algorithms

  • Simple basic operation: "Open the bottle of wine." - Knowledge of how to open it is assumed here.
  • Sequential algorithm: "Beer on wine, let it be." - Both operations have a given sequence.
  • Concurrent algorithm: "Apple juice and soda are drunk." - The order is not specified and can also take place at the same time.
  • Parallel execution: "Toast with champagne" - this can only be carried out simultaneously (parallel) and not one after the other (sequential).
  • Non-deterministic / non-determined algorithm: "Add 200 ml of beer or water to the dough." - The result may differ depending on which alternative you choose.

Algorithm analysis

The research and analysis of algorithms is a main task of computer science and is mostly carried out theoretically (without concrete implementation in a programming language). It is thus similar to the procedure in some mathematical areas, in which the analysis is more focused on the underlying concepts than on concrete implementations. Algorithms are brought into a strongly formalized form for analysis and examined with the means of formal semantics .

The analysis is divided into different areas:

  • For example, the behavior of algorithms with regard to resource requirements such as computing time and memory requirements is dealt with in complexity theory ; the results are usually given asymptotically (e.g. as an asymptotic running time ). The resource requirement is generally determined depending on the length of the input, that is, the resource requirement mostly depends on how many input values ​​have to be processed, "how 'big' the input (quantity) is".
  • The behavior with regard to the termination, i.e. whether the algorithm can ever be successfully completed, is dealt with by the theory of computability .

Types and examples

The solution for the game Towers of Hanoi with three pieces - a simple algorithm

The oldest known non-trivial algorithm is the Euclidean algorithm . Special algorithm types are the randomized algorithm (with a random component), the approximation algorithm (as an approximation method), the evolutionary algorithms (based on a biological model) and the greedy algorithm .

The list of algorithms and the category Algorithm provides a further overview .

Everyday forms of algorithms

Calculation rules are a subgroup of the algorithms. They describe instructions in mathematics with regard to numbers. Other algorithm subgroups are e.g. B. (Cooking) recipes, laws, rules, contracts, assembly instructions.

Word origin

Page from a Latin translation (Cambridge manuscript) beginning with "Dixit algorizmi"

The word algorithm is a modification or corruption of the name of the Persian arithmetic master and astronomer Abu Dschaʿfar Muhammad ibn Musa al-Chwārizmī , whose part of the name ( Nisba ) al-Chwarizmi means "the Choresmier" and refers to the origin of the bearer from Choresmia . His textbook On the Indian Numerals (written around 825 in the House of Wisdom in Baghdad ) was translated from Arabic into Latin in the 12th century and thus became the most important source of knowledge and dissemination of the Indian language in the western world alongside Leonardo Pisanos Liber Abaci. Arabic number system and written arithmetic. With the Latin translation al-Chwārizmī, the name of the author was also Latinized, based on the first words of the oldest version of this translation ( Dixit Algorismi "Algorismi has said"). Al-Chwārizmī became Middle High German algorismus, alchorismus or algoarismus - a word that was translated from Latin almost simultaneously and identically into Old French ( algorisme , argorisme) and Middle English ( augrim , augrym ). Algorism was used to describe textbooks that introduced the use of finger numbers, abacus, zero, Indian-Arabic numbers and written arithmetic up to around 1600. Written arithmetic only gradually gained acceptance. For example, at the end of the 14th century, the English poet Geoffrey Chaucer describes an astrologer in his Canterbury Tales who kept “augrym stones” at the head of his bed:

This clerk was cleped hende Nicholas. / His augrym stones layen faire apart, / On shelves couched at his beddes heed;

In medieval tradition, the word was soon felt in need of explanation and then since the 13th century mostly interpreted as a combination of a personal name Algus and a word component -rism borrowed from the Greek ῥυσμσς ( subsidiary form of ῥυθμθς ) meaning "number" .

Algus, the supposed inventor of this art of arithmetic, was regarded by some as an Arab, by others as a Greek or at least an author who wrote in Greek, and occasionally also as the "King of Castile" (John of Norfolk). In the vernacular tradition, this "master Algus" sometimes appears in a row with great ancient thinkers such as Plato , Aristotle and Euclid , as in the old French novel de la Rose , while the old Italian poem Il Fiore even equates him with the builder of the ship Argo , with which Jason went in search of the Golden Fleece.

On the para-etymological tracing back of the second component -rism to Greek ῥυσμός , ῥυθμός , the more precise Latin word form algorithm is based , which since the early modern times , initially also with the spelling algorythmus , has gained greater popularity and finally the word meaning commonly used today as a technical term for regulated procedures for solving defined problems.

History of the algorithm

historical development

Even with the development of language, people came up with rules of conduct, commandments, laws - the simplest algorithms - for living together in larger groups. Language is also a suitable way to pass on procedures and skills - more complex algorithms. The first professions arose from the specialization of individual group members in certain skills.

The concept of algorithm as an abstract view of problem-solving paths first entered people's consciousness in the context of mathematics, logic and philosophy. An example of a mathematical algorithm from ancient times is the Euclidean algorithm .

Ancient Greece

Although the etymological origin of the word is Arabic, the first algorithms arose in ancient Greece . The most important examples include the sieve of Eratosthenes for finding prime numbers , which was described in the book Introduction to Arithmetic by Nicomachus and the Euclidean algorithm for calculating the greatest common divisor of two natural numbers from the work " The Elements ". One of the oldest algorithms that deal with a real number is Archimedes' algorithm for the approximation of , which is also one of the oldest numerical methods .

The origin of the word

The word “algorithm” comes from the 9th century and is derived from the name of the chorzmic mathematician Al-Chwarizmi , who built on the work of the 7th century Indian mathematician Brahmagupta . In its original meaning, an algorithm only referred to the observance of the arithmetic rules using the Indian-Arabic numerals . The original definition evolved with translation into Latin.

Mathematics in the 19th and 20th centuries

The logicians of the 19th century did important work. George Boole , who created the first algebraic logic calculus in his book The Mathematical Analysis of Logic , thus founded modern mathematical logic, which differs from traditional philosophical logic through consistent formalization. Gottlob Frege was the first to develop a formal language and the resulting formal evidence . Giuseppe Peano reduced arithmetic to a sequence of symbols manipulated by symbols. He dealt with the axiomatics of natural numbers. This is where the Peano axioms emerged .

Frege's work was greatly elaborated and simplified by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica . Before that, Bertrand Russell had formulated the famous Russell antinomy , which led to the collapse of naive set theory . The result also led to the work of Kurt Gödel .

David Hilbert precisely formulated the decision problem in his research program around 1928 . Alan Turing and Alonzo Church found the problem unsolvable in 1936.

literature

Web links

Wiktionary: algorithm  - explanations of meanings, word origins, synonyms, translations

Footnotes

  1. ↑ Hartley Rogers, Jr .: Theory of Recursive Functions and Effective Computability , p. 2.
  2. ^ Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Algorithms - An Introduction . Oldenbourg Verlag, Munich 2010, ISBN 978-3-486-59002-9 , p. 5 .
  3. ↑ Hromkovič, Juraj, 1958-: Theoretical Computer Science, Formal Languages, Computability, Complexity Theory, Algorithmics, Communication and Cryptography / Juraj Hromkovič . 5th, revised. Edition Springer Vieweg, Wiesbaden 2014, ISBN 978-3-658-06432-7 .
  4. ↑ Sequential Abstract State Machine (seq. ASM) .
  5. ↑ Germany: § 69a Paragraph (2) UrhG.
  6. ^ Clifford A. Pickover: The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics . Sterling Publishing Company, Inc., 2009, ISBN 978-1-4027-5796-9 ( limited preview in Google Book Search).
  7. ↑ MHMC.htm. Retrieved May 26, 2018 .
  8. ↑ Al-Khwarizmi Persian Mathematician, Astronomer and Geographer part one: Persian Heritage. Retrieved May 26, 2018 .
  9. ↑ Muḥammad Ibn-Mūsā al-H̱wārizmī: The oldest Latin script on Indian arithmetic according to al-Ḫwārizmī . Ed .: Menso Folkerts, Paul Kunitzsch. Publishing house of the Bavarian Academy of Sciences, Munich 1997.
  10. ↑ Kurt Vogel : Der Trienter Algorismus von 1475. In: Nova Acta Leopoldina , New Series, Volume 27, 1963, pp. 183-200.
  11. ^ Roger L. Cooke: The History of Mathematics: A Brief Course , Wiley 2005, p. 166.
  12. ↑ http://aleph0.clarku.edu/~djoyce/elements/bookVII/propVII2.html
  13. ↑ http://itech.fgcu.edu/faculty/clindsey/mhf4404/archimedes/archimedes.html .
  14. ↑ http://www.andyborne.com/math/downloads/AL-Kwarazmi.pdf .
  15. ↑ Brahmagupta biography .
  16. ^ History of Algorithms and Algorithmics. In: Scriptol.com. Retrieved November 7, 2012 .
  17. ^ Project Gutenberg's The Mathematical Analysis of Logic, by George Boole .
  18. ↑ Gottlob Frege - An introduction to his work ( PDF )
  19. ^ Peano: Arithmetices principia nova methodo exposita , Turin 1889.
  20. ↑ http://name.umdl.umich.edu/AAT3201.0001.001 Principia Mathematica. 1st edition. 1910–1913, in the University of Michigan online version.
  21. ↑ Tapp, Christian: At the limits of the finite. The Hilbert program in the context of formalism and finitism. Springer, Heidelberg 2013, ISBN 978-3-642-29654-3 .
  22. ↑ cf. footnote in Alonzo Church 1936a in Davis 1965: 90 and 1936b in Davis 1965: 110.
  23. ↑ Dagmar Röhrlich : The new world power. In: Deutschlandfunk.de , Wissenschaft im Brennpunkt , March 20, 2016, accessed on March 28, 2016.