| 翻訳と辞書 |
algorithm
In mathematics and computer science, an algorithm ( ) is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning.
An algorithm is an effective method that can be expressed within a finite amount of space and time〔"Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).〕 and in a well-defined formal language〔Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).〕 for calculating a function.〔"an algorithm is a procedure for computing a ''function'' (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).〕 Starting from an initial state and initial input (perhaps empty),〔"An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).〕 the instructions describe a computation that, when executed, proceeds through a finite〔"A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5).〕 number of well-defined successive states, eventually producing "output"〔"An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).〕 and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.〔Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2.〕
The concept of ''algorithm'' has existed for centuries, however a partial formalization of what would become the modern ''algorithm'' began with attempts to solve the Entscheidungsproblem (the "decision problem") posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define "effective calculability"〔Kleene 1943 in Davis 1965:274〕 or "effective method";〔Rosser 1939 in Davis 1965:225〕 those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's "Formulation 1" of 1936, and Alan Turing's Turing machines of 1936–7 and 1939. Giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem.
== Word origin ==
'Algorithm' stems from the name of a Latin translation of a book written by al-Khwārizmī, a Persian〔 mathematician, astronomer and geographer. Al-Khwarizmi wrote a book titled ''On the Calculation with Hindu Numerals'' in about 825 AD, and was principally responsible for spreading the Indian system of numeration throughout the Middle East and Europe. It was translated into Latin as ''Algoritmi de numero Indorum'' (in English, "Al-Khwarizmi on the Hindu Art of Reckoning"). The term "Algoritmi" in the title of the book led to the term "algorithm".〔http://www-history.mcs.st-and.ac.uk/HistTopics/Arabic_numerals.html〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「algorithm」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|