はじめによんでください

アルゴリズム

Algorithm

池田光穂

☆ 数学や計算機科学において、アルゴリズム[algorithm] （/ˈælɡərɪðəm/ ⓘ）とは、数学的に厳密な指示の有限な列であり、通常、特定の種類の問題を解決したり、計算を実行したりするために用いられる。[1] アルゴリズムは、計算やデータ処理を行うための仕様として用いられる。より高度なアルゴリズムでは、条件分岐を用いてコードの実行を様々な経路へ分岐させ たり（自動意思決定と呼ばれる）、有効な推論を導き出したり（自動推論と呼ばれる）することができる。 対照的に、ヒューリスティックとは、明確に定義された正解や最適解が存在しない問題を解決するための手法である。[2] 例えば、ソーシャルメディアのレコメンデーションシステムは一般に「アルゴリズム」と呼ばれるが、真に「正しい」推奨というものは存在しないため、実際に はヒューリスティックに依存している。 効果的な手法として、アルゴリズムは有限の空間と時間[3]の範囲内で、かつ関数を計算するための明確に定義された形式言語[4]を用いて表現できる。 [5] 初期状態と初期入力（空の場合もある）[6] から始まり、その指示は、実行されると、明確に定義された有限[7] 個の連続する状態を経て進行し、最終的に「出力」[8] を生成し、最終的な終了状態で終了する計算を記述する。ある状態から次の状態への遷移は必ずしも決定論的ではない。ランダム化アルゴリズムとして知られる 一部のアルゴリズムは、ランダムな入力を組み込んでいる[9]。

In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ ⓘ) is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation.[1] Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning). In contrast, a heuristic is an approach to solving problems without well-defined correct or optimal results.[2] For example, although social media recommender systems are commonly called "algorithms", they actually rely on heuristics as there is no truly "correct" recommendation. As an effective method, an algorithm can be expressed within a finite amount of space and time[3] and in a well-defined formal language[4] for calculating a function.[5] Starting from an initial state and initial input (perhaps empty),[6] the instructions describe a computation that, when executed, proceeds through a finite[7] number of well-defined successive states, eventually producing "output"[8] 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.[9]	数学や計算機科学において、アルゴリズム[algorithm] （/ˈælɡərɪðəm/ ⓘ）とは、数学的に厳密な指示の有限な列であり、通常、特定の種類の問題を解決したり、計算を実行したりするために用いられる。[1] アルゴリズムは、計算やデータ処理を行うための仕様として用いられる。より高度なアルゴリズムでは、条件分岐を用いてコードの実行を様々な経路へ分岐させ たり（自動意思決定と呼ばれる）、有効な推論を導き出したり（自動推論と呼ばれる）することができる。 対照的に、ヒューリスティックとは、明確に定義された正解や最適解が存在しない問題を解決するための手法である。[2] 例えば、ソーシャルメディアのレコメンデーションシステムは一般に「アルゴリズム」と呼ばれるが、真に「正しい」推奨というものは存在しないため、実際に はヒューリスティックに依存している。 効果的な手法として、アルゴリズムは有限の空間と時間[3]の範囲内で、かつ関数を計算するための明確に定義された形式言語[4]を用いて表現できる。 [5] 初期状態と初期入力（空の場合もある）[6] から始まり、その指示は、実行されると、明確に定義された有限[7] 個の連続する状態を経て進行し、最終的に「出力」[8] を生成し、最終的な終了状態で終了する計算を記述する。ある状態から次の状態への遷移は必ずしも決定論的ではない。ランダム化アルゴリズムとして知られる 一部のアルゴリズムは、ランダムな入力を組み込んでいる[9]。
Etymology Around 825 AD, Persian scientist and polymath Muḥammad ibn Mūsā al-Khwārizmī wrote kitāb al-ḥisāb al-hindī ("Book of Indian computation") and kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī ("Addition and subtraction in Indian arithmetic"). In the early 12th century, Latin translations of these texts involving the Hindu–Arabic numeral system and arithmetic appeared, for example Liber Alghoarismi de practica arismetrice, attributed to John of Seville, and Liber Algoritmi de numero Indorum, attributed to Adelard of Bath.[10] Here, alghoarismi or algoritmi is the Latinization of Al-Khwarizmi's name;[1] the text starts with the phrase Dixit Algoritmi, or "Thus spoke Al-Khwarizmi".[2] Muḥammad ibn Mūsā al-Khwārizmī: The 9th-century mathematician whose name is the origin of the word 'algorithm'. The word algorism in English came to mean the use of place-value notation in calculations; it occurs in the Ancrene Wisse from circa 1225.[11] By the time Geoffrey Chaucer wrote The Canterbury Tales in the late 14th century, he used a variant of the same word in describing augrym stones, stones used for place-value calculation.[12][13] In the 15th century, under the influence of the Greek word ἀριθμός (arithmos, "number"; cf. "arithmetic"), the Latin word was altered to algorithmus.[14] By 1596, this form of the word was used in English, as algorithm, by Thomas Hood.[15]	語源 西暦825年頃、ペルシャの科学者であり博学者であるムハンマド・イブン・ムーサ・アル＝フワリズミーは、『キターブ・アル＝ヒサブ・アル＝ヒンディー』 （「インドの計算法」）および『キターブ・アル＝ジャム・ワル＝タフリク・アル＝ヒサブ・アル＝ヒンディー』（「インド算術における加法と減法」）を著し た。12世紀初頭、ヒンドゥー・アラビア数字体系と算術に関するこれらのテキストのラテン語訳が登場した。例えば、セビリアのヨハネスに帰せられる 『Liber Alghoarismi de practica arismetrice』や、バースのアデラードに帰せられる『Liber Algoritmi de numero Indorum』などである。[10] ここで、alghoarismi または algoritmi は、アル＝フワリズミの名をラテン語化したものである[1]。この書物は、Dixit Algoritmi（「アル＝フワリズミはこう述べた」）という一節で始まる。[2] ムハンマド・イブン・ムーサ・アル＝フワリズミー：9世紀の数学者で、その名が「アルゴリズム」という言葉の由来となっている。 英語の「algorism」という言葉は、計算における位取り表記法の使用を意味するようになった。これは1225年頃の『アンクレーン・ウィッセ』に見 られる。[11] 14世紀後半にジェフリー・チョーサーが『カンタベリー物語』を執筆した頃には、彼は同じ言葉の変種を用いて、位取り計算に用いられる「augrym stones（アウグリム・ストーンズ）」を記述していた。[12] [13] 15世紀には、ギリシャ語のἀριθμός（arithmos、「数」；「算術」を参照）の影響を受け、ラテン語の語形はalgorithmusへと変化 した。[14] 1596年までに、この語形はトマス・フッドによって、algorithmとして英語で用いられるようになった。[15]
Definition For a detailed presentation of the various points of view on the definition of "algorithm", see Algorithm characterizations. One informal definition is "a set of rules that precisely defines a sequence of operations",[16] which would include all computer programs (including programs that do not perform numeric calculations), and any prescribed bureaucratic procedure[17] or cook-book recipe.[18] In general, a program is an algorithm only if it stops eventually[19]—even though infinite loops may sometimes prove desirable. Boolos, Jeffrey & 1974, 1999 define an algorithm to be an explicit set of instructions for determining an output, that can be followed by a computing machine or a human who could only carry out specific elementary operations on symbols.[20]	定義 「アルゴリズム」の定義に関する様々な見解の詳細については、「アルゴリズムの特性」を参照のこと。 ある非公式な定義として、「一連の操作を厳密に規定する規則の集合」[16]というものがあり、これにはすべてのコンピュータプログラム（数値計算を行わ ないプログラムを含む）や、あらゆる所定の官僚的手続き[17]、あるいは料理本のレシピなどが含まれる。[18] 一般に、プログラムがアルゴリズムであるのは、最終的に停止する場合に限られる[19]—たとえ無限ループが望ましい場合もあるとしても。Boolos, Jeffrey & 1974, 1999は、アルゴリズムを、出力を決定するための明示的な指示の集合であり、記号に対して特定の初等操作しか実行できない計算機または人間によって実行 可能なものと定義している。[20]
History icon This section is missing information about 20th and 21st century development of computer algorithms. Please expand the section to include this information. Further details may exist on the talk page. (October 2023) Ancient algorithms Step-by-step procedures for solving mathematical problems have been recorded since antiquity. This includes in Babylonian mathematics (around 2500 BC),[21] Egyptian mathematics (around 1550 BC),[21] Indian mathematics (around 800 BC and later),[22][23] the Ifa Oracle (around 500 BC),[24] Greek mathematics (around 240 BC),[25] Chinese mathematics (around 200 BC and later),[26] and Arabic mathematics (around 800 AD).[27] The earliest evidence of algorithms is found in ancient Mesopotamian mathematics. A Sumerian clay tablet found in Shuruppak near Baghdad and dated to c. 2500 BC describes the earliest division algorithm.[21] During the Hammurabi dynasty c. 1800 – c. 1600 BC, Babylonian clay tablets described algorithms for computing formulas.[28] Algorithms were also used in Babylonian astronomy. Babylonian clay tablets describe and employ algorithmic procedures to compute the time and place of significant astronomical events.[29] Algorithms for arithmetic are also found in ancient Egyptian mathematics, dating back to the Rhind Mathematical Papyrus c. 1550 BC.[21] Algorithms were later used in ancient Hellenistic mathematics. Two examples are the Sieve of Eratosthenes, which was described in the Introduction to Arithmetic by Nicomachus,[30][25]: Ch 9.2  and the Euclidean algorithm, which was first described in Euclid's Elements (c. 300 BC).[25]: Ch 9.1 Examples of ancient Indian mathematics included the Shulba Sutras, the Kerala School, and the Brāhmasphuṭasiddhānta.[22] In the 9th century, Muḥammad ibn Mūsā al-Khwārizmī revolutionized the field by establishing the algorithm as a systematic, finite sequence of logical steps to solve mathematical problems. In his influential work, The Compendious Book on Calculation by Completion and Balancing, he moved beyond specific numerical solutions to introduce general procedures for algebraic reduction and balancing. This transformed mathematics into a 'mechanical' process of well-defined rules—a fundamental shift that laid the groundwork for modern algorithmic theory. The Latin translation of his arithmetic treatise, titled Algoritmi de numero Indorum, led to the term algorithm being derived from the Latinization of his name, Algoritmi, specifically to describe this new rule-based approach to [31]. The first cryptographic algorithm for deciphering encrypted code was developed by Al-Kindi, a 9th-century Arab mathematician, in A Manuscript On Deciphering Cryptographic Messages. He gave the first description of cryptanalysis by frequency analysis, the earliest codebreaking algorithm.[27]	歴史 アイコン この節には、20世紀および21世紀におけるコンピュータアルゴリズムの発展に関する情報が欠けている。この情報を含めるよう、節を拡充してほしい。詳細 についてはトークページに記載されている可能性がある。（2023年10月） 古代のアルゴリズム 数学的問題を解くための段階的な手順は、古代から記録されている。これには、バビロニア数学（紀元前2500年頃）[21]、エジプト数学（紀元前 1550年頃）[21]、インド数学（紀元前800年頃以降）[22][23]、イファ神託（紀元前500年頃）[24]、ギリシャ数学（紀元前240年 頃） [25] 中国の数学（紀元前200年頃以降）[26]、およびアラビアの数学（西暦800年頃）[27] アルゴリズムの最も古い証拠は、古代メソポタミアの数学に見られる。バグダッド近郊のシュルッパクで発見され、紀元前2500年頃と年代測定されたシュ メールの粘土板には、最古の除法アルゴリズムが記述されている。[21] 紀元前1800年頃～紀元前1600年頃のハンムラビ王朝時代、バビロニアの粘土板には定式を導出するためのアルゴリズムが記述されていた。[28] アルゴリズムはバビロニアの天文学でも用いられた。バビロニアの粘土板には、重要な天文現象の発生時刻や場所を計算するためのアルゴリズム的手順が記述さ れ、実際に用いられている。[29] 算術のためのアルゴリズムは、紀元前1550年頃の『リンド数学パピルス』にまで遡る古代エジプトの数学にも見られる。[21] アルゴリズムは後に古代ヘレニズム期の数学でも用いられた。その例として、ニコマコスの『算術序論』[30] [25]: 第9.2章 、およびユークリッドの『原論』（紀元前300年頃）で初めて記述されたユークリッドのアルゴリズムである。[25]: 第 9.1章 古代インド数学の例としては、『シュルバ・スートラ』、ケララ学派、および『ブラフマシュプタ・シッダーンタ』が挙げられる。[22] 9世紀、ムハンマド・イブン・ムーサー・アル＝フワリズミーは、数学的問題を解決するための体系的で有限の論理的ステップの連鎖としてアルゴリズムを確立 し、この分野に革命をもたらした。彼の影響力ある著作『計算の要約：完成と均衡による』において、彼は特定の数値解を超え、代数的な簡約と均衡のための一 般的な手順を導入した。これにより、数学は明確に定義された規則に基づく「機械的」なプロセスへと変容した。これは、現代のアルゴリズム理論の基礎を築い た根本的な転換であった。彼の算術論著のラテン語訳『Algoritmi de numero Indorum』により、アルゴリズムという用語が彼の名前のラテン語化である「Algoritmi」に由来するようになった。これは特に、[31]に対 するこの新しい規則に基づくアプローチを記述するために用いられた。 暗号化されたコードを解読するための最初の暗号アルゴリズムは、9世紀のアラブ人数学者アル＝キンディによって『暗号文解読に関する手稿』の中で開発され た。彼は、最も初期の暗号解読アルゴリズムである頻度分析による暗号解読について、初めて記述した[27]。
Computers Weight-driven clocks David Bolter credits the invention of the weight-driven clock as "the key invention [of Europe in the Middle Ages]," specifically the verge escapement mechanism[32] producing the tick and tock of a mechanical clock. "The accurate automatic machine"[33] led immediately to "mechanical automata" in the 13th century and "computational machines"—the difference and analytical engines of Charles Babbage and Ada Lovelace in the mid-19th century.[34] Lovelace designed the first algorithm intended for processing on a computer, Babbage's analytical engine, which is the first device considered a real Turing-complete computer instead of just a calculator. Although the full implementation of Babbage's second device was not realized for decades after her lifetime, Lovelace has been called "history's first programmer". Electromechanical relay Bell and Newell (1971) write that the Jacquard loom, a precursor to Hollerith cards (punch cards), and "telephone switching technologies" led to the development of the first computers.[35] By the mid-19th century, the telegraph, the precursor of the telephone, was in use throughout the world. By the late 19th century, the ticker tape (c. 1870s) was in use, as were Hollerith cards (c. 1890). Then came the teleprinter (c. 1910) with its punched-paper use of Baudot code on tape. Telephone-switching networks of electromechanical relays were invented in 1835. These led to the invention of the digital adding device by George Stibitz in 1937. While working in Bell Laboratories, he observed the "burdensome" use of mechanical calculators with gears. "He went home one evening in 1937 intending to test his idea... When the tinkering was over, Stibitz had constructed a binary adding device".[36][37]	コンピュータ 重り式時計 デビッド・ボルターは、重り式時計の発明を「（中世ヨーロッパにおける）鍵となる発明」と位置づけており、特に機械式時計の「チクタク」という音を生み出 すバージ脱進機[32]を挙げている。「正確な自動機械」[33]は、13世紀には直ちに「機械式オートマタ」へとつながり、19世紀半ばにはチャール ズ・バベッジとエイダ・ラブレスによる「計算機械」——異なる機関と解析機関——へと発展した。[34] ラブレスは、コンピュータ上で処理することを意図した最初のアルゴリズムを設計した。それはバベッジの解析機関であり、単なる計算機ではなく、真のチュー リング完全なコンピュータと見なされる最初の装置である。バベッジの2番目の装置の完全な実装は、彼女の死後数十年を経てようやく実現されたものの、ラブ レスは「歴史上最初のプログラマー」と呼ばれている。 電気機械式リレー ベルとニューウェル（1971）は、ジャカード織機、ホレリス・カード（パンチカード）の先駆け、そして「電話交換技術」が、最初のコンピュータの開発に つながったと記している。[35] 19世紀半ばまでに、電話の先駆けである電信は世界中で使用されていた。19世紀後半には、ティッカーテープ（1870年代頃）やホレリスカード （1890年頃）が使用されていた。その後、テープ上のボードー符号を用いたパンチ紙式のテレプリンター（1910年頃）が登場した。 電気機械式リレーを用いた電話交換網は1835年に発明された。これらがきっかけとなり、1937年にジョージ・スティビッツによってデジタル加算装置が 発明された。ベル研究所に勤務していた彼は、歯車を用いた機械式計算機の「煩雑な」使用状況を目の当たりにしていた。「1937年のある晩、彼は自分のア イデアを試すつもりで帰宅した……試行錯誤が終わったとき、スティビッツは2進法加算装置を完成させていた」。[36][37]
Formalization Ada Lovelace's diagram from "Note G", the first published computer algorithm In 1928, a partial formalization of the modern concept of algorithms began with attempts to solve the Entscheidungsproblem (decision problem) posed by David Hilbert. Later formalizations were framed as attempts to define "effective calculability"[38] or "effective method".[39] 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–37 and 1939. Modern Algorithms Algorithms have evolved and improved in many ways as time goes on. Common uses of algorithms today include social media apps like Instagram and YouTube. Algorithms are used as a way to analyze what people like and push more of those things to the people who interact with them. Quantum computing uses quantum algorithm procedures to solve problems faster. More recently, in 2024, NIST updated their post-quantum encryption standards, which includes new encryption algorithms to enhance defenses against attacks using quantum computing.	形式化 「注記G」に掲載されたエイダ・ラブレスによる図、史上初の公開されたコンピュータアルゴリズム 1928年、デヴィッド・ヒルベルトが提起した「決定問題（Entscheidungsproblem）」の解決に向けた試みにより、現代的なアルゴリズ ム概念の部分的な形式化が始まった。その後の形式化は、「有効計算可能性」[38] あるいは「有効な方法」を定義しようとする試みとして位置づけられた。[39] これらの形式化には、1930年、1934年、1935年のゲーデル・ヘルブランド・クリーネの再帰関数、1936年のアロンゾ・チャーチのラムダ計算、 1936年のエミール・ポストの定式化1、そして1936～37年および1939年のアラン・チューリングのチューリングマシンが含まれる。 現代のアルゴリズム アルゴリズムは、時が経つにつれて様々な形で進化し、改良されてきた。今日、アルゴリズムの一般的な用途には、InstagramやYouTubeのよう なソーシャルメディアアプリが含まれる。アルゴリズムは、人々が何を好むかを分析し、それらと関わる人々に、そのようなコンテンツをより多く提示する手段 として用いられている。量子コンピューティングは、量子アルゴリズムの手法を用いて問題をより高速に解決する。さらに最近では、2024年にNISTがポ スト量子暗号化規格を更新し、量子コンピューティングを用いた攻撃に対する防御を強化するための新しい暗号化アルゴリズムが含まれている。
Representations Algorithms can be expressed in many kinds of notation, including natural languages, pseudocode, flowcharts, drakon-charts, programming languages or control tables (processed by interpreters). Natural language expressions of algorithms tend to be verbose and ambiguous and are rarely used for complex or technical algorithms. Pseudocode, flowcharts, drakon-charts, and control tables are structured expressions of algorithms that avoid common ambiguities of natural language. Programming languages are primarily for expressing algorithms in a computer-executable form but are also used to define or document algorithms. Turing machines There are many possible representations and Turing machine programs can be expressed as a sequence of machine tables (see finite-state machine, state-transition table, and control table for more), as flowcharts and drakon-charts (see state diagram for more), as a form of rudimentary machine code or assembly code called "sets of quadruples", and more. Algorithm representations can also be classified into three accepted levels of Turing machine description: high-level description, implementation description, and formal description.[40] A high-level description describes the qualities of the algorithm itself, ignoring how it is implemented on the Turing machine.[40] An implementation description describes the general manner in which the machine moves its head and stores data to carry out the algorithm, but does not give exact states.[40] In the most detail, a formal description gives the exact state table and list of transitions of the Turing machine.[40] Flowchart representation The graphical aid called a flowchart offers a way to describe and document an algorithm (and a computer program corresponding to it). It has four primary symbols: arrows showing program flow, rectangles (SEQUENCE, GOTO), diamonds (IF-THEN-ELSE), and dots (OR-tie). Sub-structures can "nest" in rectangles, but only if a single exit occurs from the superstructure.	表現 アルゴリズムは、自然言語、擬似コード、フローチャート、ドラコンチャート、プログラミング言語、あるいは（インタプリタによって処理される）制御表な ど、さまざまな表記法で表現できる。自然言語によるアルゴリズムの表現は、冗長で曖昧になりがちであり、複雑または技術的なアルゴリズムにはめったに使わ れない。擬似コード、フローチャート、ドラコンチャート、および制御表は、自然言語にありがちな曖昧さを回避した、構造化されたアルゴリズムの表現であ る。プログラミング言語は、主にコンピュータが実行可能な形式でアルゴリズムを表現するためのものであるが、アルゴリズムを定義したり文書化したりするた めにも用いられる。 チューリングマシン 表現方法は多岐にわたり、チューリングマシンのプログラムは、マシンテーブルの列（詳細は有限状態マシン、状態遷移表、制御表を参照）、フローチャートや ドラコンチャート（詳細は状態図を参照）、「4元組の集合」と呼ばれる初歩的なマシンコードやアセンブリコードの形式などとして表現できる。アルゴリズム の表現は、チューリングマシンの記述において一般的に認められている3つのレベル、すなわち高レベル記述、実装記述、および形式記述に分類することもでき る。[40] 高レベル記述は、チューリングマシン上での実装方法を無視し、アルゴリズム自体の性質を記述するものである。[40] 実装記述は、アルゴリズムを実行するために機械がヘッドを移動させ、データを格納する一般的な方法を記述するが、正確な状態は示さない。[40] 最も詳細な形式記述は、チューリングマシンの正確な状態遷移表と遷移リストを示す。[40] フローチャートによる表現 フローチャートと呼ばれる図解ツールは、アルゴリズム（およびそれに対応するコンピュータプログラム）を記述・文書化する方法を提供する。これには4つの 主要な記号がある：プログラムの流れを示す矢印、長方形（SEQUENCE、GOTO）、ひし形（IF-THEN-ELSE）、および点（OR- tie）。サブ構造は長方形内に「ネスト」できるが、それは親構造から出口が1つだけある場合に限られる。
Algorithmic analysis Main article: Analysis of algorithms Formal versus empirical Main articles: Empirical algorithmics, Profiling (computer programming), and Program optimization The analysis, and study of algorithms is a discipline of computer science. Algorithms are often studied abstractly, without referencing any specific programming language or implementation. Algorithm analysis resembles other mathematical disciplines as it focuses on the algorithm's properties, not implementation. Pseudocode is typical for analysis as it is a simple and general representation. Most algorithms are implemented on particular hardware/software platforms and their algorithmic efficiency is tested using real code. The efficiency of a particular algorithm may be insignificant for many "one-off" problems but it may be critical for algorithms designed for fast interactive, commercial, or long-life scientific usage. Scaling from small n to large n frequently exposes inefficient algorithms that are otherwise benign. Empirical testing is useful for uncovering unexpected interactions that affect performance. Benchmarks may be used to compare before/after potential improvements to an algorithm after program optimization. Empirical tests cannot replace formal analysis, though, and are non-trivial to perform fairly.[41] Execution efficiency Main article: Algorithmic efficiency To illustrate the potential improvements possible even in well-established algorithms, a recent significant innovation, relating to FFT algorithms (used heavily in the field of image processing), can decrease processing time up to 1,000 times for applications like medical imaging.[42] In general, speed improvements depend on special properties of the problem, which are very common in practical applications.[43] Speedups of this magnitude enable computing devices that make extensive use of image processing (like digital cameras and medical equipment) to consume less power. Best Case and Worst Case Main article: Best, worst and average case The best case of an algorithm refers to the scenario or input for which the algorithm or data structure takes the least time and resources to complete its tasks.[44] The worst case of an algorithm is the case that causes the algorithm or data structure to consume the maximum period of time and computational resources.[45]	アルゴリズム解析 主な記事：アルゴリズム解析 形式的 versus 経験的 主な記事：経験的アルゴリズム学、プロファイリング（コンピュータプログラミング）、およびプログラム最適化 アルゴリズムの分析と研究は、コンピュータ科学の一分野である。アルゴリズムは、特定のプログラミング言語や実装に言及することなく、抽象的に研究される ことが多い。アルゴリズム解析は、実装ではなくアルゴリズムの性質に焦点を当てる点で、他の数学分野に似ている。擬似コードは、単純かつ一般的な表現であ るため、解析において一般的である。ほとんどのアルゴリズムは特定のハードウェア／ソフトウェアプラットフォーム上で実装され、そのアルゴリズム的効率は 実際のコードを用いてテストされる。特定のアルゴリズムの効率は、多くの「単発的な」問題では重要ではないかもしれないが、高速な対話型、商用、あるいは 長期にわたる科学的な用途向けに設計されたアルゴリズムにとっては極めて重要となる場合がある。nが小さい場合から大きい場合へのスケーリングを行うと、 それ以外では問題のないアルゴリズムであっても、非効率なものが露呈することが頻繁にある。 実証的なテストは、パフォーマンスに影響を与える予期せぬ相互作用を明らかにするのに有用である。ベンチマークは、プログラム最適化後のアルゴリズムの潜 在的な改善点について、改善前後の比較を行うために使用されることがある。しかし、実証的テストは形式的な解析に代わるものではなく、公平に実施するのは 容易ではない。[41] 実行効率 主な記事：アルゴリズムの効率 確立されたアルゴリズムであっても改善の余地があることを示す例として、FFTアルゴリズム（画像処理の分野で多用される）に関連する最近の重要な革新に より、医療画像処理のようなアプリケーションにおいて処理時間を最大1,000倍短縮できる。[42] 一般的に、速度の向上は問題の特殊な性質に依存するが、これは実用的なアプリケーションでは非常に一般的である。[43] これほどの速度向上により、画像処理を多用するコンピューティングデバイス（デジタルカメラや医療機器など）の消費電力を低減できる。 最良ケースと最悪ケース 主な記事：最良ケース、最悪ケース、平均ケース アルゴリズムの最良ケースとは、そのアルゴリズムやデータ構造がタスクを完了するのに最小限の時間とリソースしか必要としないシナリオや入力を指す。 [44] アルゴリズムの最悪ケースとは、そのアルゴリズムやデータ構造が最大の時間と計算リソースを消費するケースである。[45]
Design See also: Algorithm § By design paradigm Algorithm design is a method or mathematical process for problem-solving and engineering algorithms. The design of algorithms is part of many solution theories, such as divide-and-conquer or dynamic programming within operation research. Techniques for designing and implementing algorithm designs are also called algorithm design patterns,[46] with examples including the template method pattern and the decorator pattern. One of the most important aspects of algorithm design is resource (run-time, memory usage) efficiency; the big O notation is used to describe e.g., an algorithm's run-time growth as the size of its input increases.[47] Structured programming Per the Church–Turing thesis, any algorithm can be computed by any Turing complete model. Turing completeness only requires four instruction types—conditional GOTO, unconditional GOTO, assignment, HALT. However, Kemeny and Kurtz observe that, while "undisciplined" use of unconditional GOTOs and conditional IF-THEN GOTOs can result in "spaghetti code", a programmer can write structured programs using only these instructions; on the other hand "it is also possible, and not too hard, to write badly structured programs in a structured language".[48] Tausworthe augments the three Böhm-Jacopini canonical structures:[49] SEQUENCE, IF-THEN-ELSE, and WHILE-DO, with two more: DO-WHILE and CASE.[50] An additional benefit of a structured program is that it lends itself to proofs of correctness using mathematical induction.[51]	設計 関連項目：アルゴリズム § 設計パラダイム アルゴリズム設計とは、問題解決やアルゴリズムの構築を行うための手法、あるいは数学的プロセスである。アルゴリズムの設計は、オペレーションズ・リサー チにおける分割統治法や動的計画法など、多くの解法理論の一部を成している。アルゴリズムの設計および実装のための技法は、アルゴリズム設計パターンとも 呼ばれる[46]。その例には、テンプレートメソッドパターンやデコレータパターンなどがある。アルゴリズム設計において最も重要な側面の一つは、リソー ス（実行時間、メモリ使用量）の効率性である。ビッグオー表記は、例えば入力のサイズが増加するにつれてアルゴリズムの実行時間がどのように増加するかを 記述するために用いられる。[47] 構造化プログラミング チャーチ＝チューリングの定理によれば、あらゆるアルゴリズムは、あらゆるチューリング完全なモデルによって計算可能である。チューリング完全性には、条 件付きGOTO、無条件GOTO、代入、HALTの4種類の命令のみが必要とされる。しかし、ケメニーとカーツは、無条件GOTOや条件付きIF- THEN GOTOを「無秩序に」使用すると「スパゲッティコード」になり得る一方で、プログラマーはこれらの命令のみを用いて構造化されたプログラムを書くことが できると指摘している。その一方で、「構造化言語で構造の悪いプログラムを書くことも可能であり、それほど難しくはない」とも述べている。[48] タウスワースは、ベーム＝ジャコピニの3つの標準構造[49]（SEQUENCE、IF-THEN-ELSE、WHILE-DO）に、さらに2つ（DO- WHILEとCASE）を追加している。[50] 構造化プログラムのさらなる利点は、数学的帰納法を用いた正しさの証明に適している点にある。[51]
Legal status See also: Software patent By themselves, algorithms are not usually patentable. In the United States, a claim consisting solely of simple manipulations of abstract concepts, numbers, or signals does not constitute "processes" (USPTO 2006), so algorithms are not patentable (as in Gottschalk v. Benson). However practical applications of algorithms are sometimes patentable. For example, in Diamond v. Diehr, the application of a simple feedback algorithm to aid in the curing of synthetic rubber was deemed patentable. The patenting of software is controversial,[52] and there are criticized patents involving algorithms, especially data compression algorithms, such as Unisys's LZW patent. Additionally, some cryptographic algorithms have export restrictions (see export of cryptography).	法的地位 関連項目：ソフトウェア特許 アルゴリズム自体は、通常、特許の対象とはならない。米国では、抽象的な概念、数値、または信号の単純な操作のみで構成されるクレームは「プロセス」には 該当しない（USPTO 2006）ため、アルゴリズムは特許の対象とならない（Gottschalk v. Benson事件参照）。しかし、アルゴリズムの実用的な応用は特許取得可能な場合がある。例えば、Diamond v. Diehr事件では、合成ゴムの加硫を助けるための単純なフィードバックアルゴリズムの応用が特許取得可能とされた。ソフトウェアの特許化は議論の的と なっており[52]、アルゴリズム、特にユニシスのLZW特許のようなデータ圧縮アルゴリズムに関する特許には批判がある。さらに、一部の暗号アルゴリズ ムには輸出規制が課されている（暗号技術の輸出を参照）。
Classification By implementation Recursion A recursive algorithm invokes itself repeatedly until meeting a termination condition and is a common functional programming method. Iterative algorithms use repetitions such as loops or data structures like stacks to solve problems. Problems may be suited for one implementation or the other. The Tower of Hanoi is a puzzle commonly solved using recursive implementation. Every recursive version has an equivalent (but possibly more or less complex) iterative version, and vice versa. Serial, parallel or distributed Algorithms are usually discussed with the assumption that computers execute one instruction of an algorithm at a time on serial computers. Serial algorithms are designed for these environments, unlike parallel or distributed algorithms. Parallel algorithms take advantage of computer architectures where multiple processors can work on a problem at the same time. Distributed algorithms use multiple machines connected via a computer network. Parallel and distributed algorithms divide the problem into subproblems and collect the results back together. Resource consumption in these algorithms is not only processor cycles on each processor but also the communication overhead between the processors. Some sorting algorithms can be parallelized efficiently, but their communication overhead is expensive. Iterative algorithms are generally parallelizable, but some problems have no parallel algorithms and are called inherently serial problems. Deterministic or non-deterministic Deterministic algorithms solve the problem with exact decisions at every step; whereas non-deterministic algorithms solve problems via guessing. Guesses are typically made more accurate through the use of heuristics. Exact or approximate While many algorithms reach an exact solution, approximation algorithms seek an approximation that is close to the true solution. Such algorithms have practical value for many hard problems. For example, the Knapsack problem, where there is a set of items, and the goal is to pack the knapsack to get the maximum total value. Each item has some weight and some value. The total weight that can be carried is no more than some fixed number X. So, the solution must consider the weights of items as well as their value.[53] Quantum algorithm Quantum algorithms run on a realistic model of quantum computation. The term is usually used for those algorithms that seem inherently quantum or use some essential feature of Quantum computing such as quantum superposition or quantum entanglement. By design paradigm Another way of classifying algorithms is by their design methodology or paradigm. Some common paradigms are: Brute-force or exhaustive search Brute force is a problem-solving method of systematically trying every possible option until the optimal solution is found. This approach can be very time-consuming, testing every possible combination of variables. It is often used when other methods are unavailable or too complex. Brute force can solve a variety of problems, including finding the shortest path between two points and cracking passwords. Divide and conquer A divide-and-conquer algorithm repeatedly reduces a problem to one or more smaller instances of itself (usually recursively) until the instances are small enough to solve easily. Merge sorting is an example of divide and conquer, where an unordered list is repeatedly split into smaller lists, which are sorted in the same way and then merged.[54] In a simpler variant of divide and conquer called prune and search or decrease-and-conquer algorithm, which solves one smaller instance of itself, and does not require a merge step.[55] An example of a prune and search algorithm is the binary search algorithm. Search and enumeration Many problems (such as playing chess) can be modelled as problems on graphs. A graph exploration algorithm specifies rules for moving around a graph and is useful for such problems. This category also includes search algorithms, branch and bound enumeration, and backtracking. Randomized algorithm Such algorithms make some choices randomly (or pseudo-randomly). They find approximate solutions when finding exact solutions may be impractical (see heuristic method below). For some problems, the fastest approximations must involve some randomness.[56] Whether randomized algorithms with polynomial time complexity can be the fastest algorithm for some problems is an open question known as the P versus NP problem. There are two large classes of such algorithms: Monte Carlo algorithms return a correct answer with high probability. E.g. RP is the subclass of these that run in polynomial time. Las Vegas algorithms always return the correct answer, but their running time is only probabilistically bound, e.g. ZPP. Reduction of complexity This technique transforms difficult problems into better-known problems solvable with (hopefully) asymptotically optimal algorithms. The goal is to find a reducing algorithm whose complexity is not dominated by the resulting reduced algorithms. For example, one selection algorithm finds the median of an unsorted list by first sorting the list (the expensive portion), and then pulling out the middle element in the sorted list (the cheap portion). This technique is also known as transform and conquer. Back tracking In this approach, multiple solutions are built incrementally and abandoned when it is determined that they cannot lead to a valid full solution. Optimization problems For optimization problems there is a more specific classification of algorithms; an algorithm for such problems may fall into one or more of the general categories described above as well as into one of the following: Linear programming When searching for optimal solutions to a linear function bound by linear equality and inequality constraints, the constraints can be used directly to produce optimal solutions. There are algorithms that can solve any problem in this category, such as the popular simplex algorithm.[57] Problems that can be solved with linear programming include the maximum flow problem for directed graphs. If a problem also requires that any of the unknowns be integers, then it is classified in integer programming. A linear programming algorithm can solve such a problem if it can be proved that all restrictions for integer values are superficial, i.e., the solutions satisfy these restrictions anyway. In the general case, a specialized algorithm or an algorithm that finds approximate solutions is used, depending on the difficulty of the problem. Dynamic programming When a problem shows optimal substructures—meaning the optimal solution can be constructed from optimal solutions to subproblems—and overlapping subproblems, meaning the same subproblems are used to solve many different problem instances, a quicker approach called dynamic programming avoids recomputing solutions. For example, Floyd–Warshall algorithm, the shortest path between a start and goal vertex in a weighted graph can be found using the shortest path to the goal from all adjacent vertices. Dynamic programming and memoization go together. Unlike divide and conquer, dynamic programming subproblems often overlap. The difference between dynamic programming and simple recursion is the caching or memoization of recursive calls. When subproblems are independent and do not repeat, memoization does not help; hence dynamic programming is not applicable to all complex problems. Using memoization dynamic programming reduces the complexity of many problems from exponential to polynomial. The greedy method Greedy algorithms, similarly to a dynamic programming, work by examining substructures, in this case not of the problem but of a given solution. Such algorithms start with some solution and improve it by making small modifications. For some problems, they always find the optimal solution but for others they may stop at local optima. The most popular use of greedy algorithms is finding minimal spanning trees of graphs without negative cycles. Huffman Tree, Kruskal, Prim, Sollin are greedy algorithms that can solve this optimization problem. The heuristic method In optimization problems, heuristic algorithms find solutions close to the optimal solution when finding the optimal solution is impractical. These algorithms get closer and closer to the optimal solution as they progress. In principle, if run for an infinite amount of time, they will find the optimal solution. They can ideally find a solution very close to the optimal solution in a relatively short time. These algorithms include local search, tabu search, simulated annealing, and genetic algorithms. Some, like simulated annealing, are non-deterministic algorithms while others, like tabu search, are deterministic. When a bound on the error of the non-optimal solution is known, the algorithm is further categorized as an approximation algorithm.	分類 実装方法による 再帰 再帰アルゴリズムは、終了条件を満たすまで自身を繰り返し呼び出すもので、関数型プログラミングにおける一般的な手法である。反復アルゴリズムは、ループ などの反復処理やスタックのようなデータ構造を用いて問題を解決する。問題によっては、どちらの実装方法が適しているか異なる場合がある。ハノイの塔は、 再帰的な実装を用いて解かれることが多いパズルである。すべての再帰的バージョンには、それと同等の（ただし、多少複雑さが異なる可能性のある）反復的 バージョンが存在し、その逆もまた然りである。 シリアル、並列、または分散 アルゴリズムは通常、コンピュータがシリアルコンピュータ上で一度にアルゴリズムの1つの命令を実行するという前提で議論される。シリアルアルゴリズム は、並列アルゴリズムや分散アルゴリズムとは異なり、こうした環境向けに設計されている。並列アルゴリズムは、複数のプロセッサが同時に問題に取り組むこ とができるコンピュータアーキテクチャの利点を活用する。分散アルゴリズムは、コンピュータネットワークを介して接続された複数のマシンを利用する。並列 および分散アルゴリズムは、問題を部分問題に分割し、その結果を再び統合する。これらのアルゴリズムにおけるリソース消費は、各プロセッサの処理サイクル だけでなく、プロセッサ間の通信オーバーヘッドも含まれる。一部のソートアルゴリズムは効率的に並列化できるが、その通信オーバーヘッドは大きい。反復ア ルゴリズムは一般的に並列化可能だが、並列アルゴリズムが存在しない問題もあり、これらは本質的にシリアルな問題と呼ばれる。 決定的または非決定的 決定的アルゴリズムは、各ステップで正確な決定を下して問題を解く。一方、非決定的アルゴリズムは推測によって問題を解く。推測は通常、ヒューリスティッ クの使用によって精度が向上する。 正確または近似 多くのアルゴリズムが正確な解に到達する一方で、近似アルゴリズムは真の解に近い近似解を求める。このようなアルゴリズムは、多くの困難な問題に対して実 用的な価値を持つ。例えば、ナップサック問題では、一連のアイテムがあり、ナップサックに詰め込んで総価値を最大にするのが目標だ。各アイテムには重量と 価値がある。運べる総重量は、ある固定値Xを超えてはならない。したがって、解法ではアイテムの重量と価値の両方を考慮しなければならない。[53] 量子アルゴリズム 量子アルゴリズムは、量子計算の現実的なモデル上で実行される。この用語は通常、本質的に量子的な性質を持つアルゴリズム、あるいは量子重ね合わせや量子 もつれといった量子計算の本質的な特徴を利用するアルゴリズムに対して用いられる。 設計パラダイムによる分類 アルゴリズムを分類するもう一つの方法は、その設計手法やパラダイムによるものである。一般的なパラダイムには次のようなものがある： ブルートフォースまたは網羅的探索 ブルートフォースとは、最適な解が見つかるまで、考えられるすべての選択肢を体系的に試していく問題解決手法である。このアプローチは、変数のあらゆる組 み合わせを検証するため、非常に時間がかかることがある。他の方法が利用できない場合や、複雑すぎる場合にしばしば用いられる。ブルートフォースは、2点 間の最短経路の探索やパスワードの解読など、様々な問題を解決できる。 分割統治法 分割統治アルゴリズムは、問題を（通常は再帰的に）それ自体の1つまたは複数のより小さなインスタンスに繰り返し縮小し、それらのインスタンスが容易に解 けるほど小さくなるまで続ける。マージソートは分割統治法の例であり、順序のないリストを繰り返し小さなリストに分割し、それらを同様にソートしてから結 合するものである。[54] 「プルーニング・アンド・サーチ」または「ディクリース・アンド・コンクァー」アルゴリズムと呼ばれる分割統治法のより単純な変種では、自身のより小さな インスタンスを1つ解決するだけで、結合ステップを必要としない。[55] プルーニング・アンド・サーチアルゴリズムの例として、二分探索アルゴリズムが挙げられる。 探索と列挙 多くの問題（チェスのようなもの）は、グラフ上の問題としてモデル化できる。グラフ探索アルゴリズムは、グラフ上を移動するためのルールを規定するもので あり、そのような問題に有用である。このカテゴリには、探索アルゴリズム、分枝限定法、およびバックトラッキングも含まれる。 ランダム化アルゴリズム このようなアルゴリズムは、一部の選択をランダム（または擬似ランダム）に行う。これらは、正確な解を求めることが現実的でない場合に近似解を見つける （以下のヒューリスティック法を参照）。一部の問題では、最速の近似解を得るには何らかのランダム性が必要となる。[56] 多項式時間計算量を持つランダム化アルゴリズムが、特定の問題に対して最速のアルゴリズムとなり得るかどうかは、P対NP問題として知られる未解決問題で ある。このようなアルゴリズムには、主に2つの大きな分類がある： モンテカルロアルゴリズムは、高い確率で正しい答えを返す。例：RPは、多項式時間で実行されるこれらのサブクラスである。 ラスベガスアルゴリズムは常に正しい答えを返すものの、その実行時間は確率的にのみ上界が定められている。例：ZPP。 計算量の削減 この手法は、困難な問題を、（望ましくは）漸近的に最適なアルゴリズムで解ける、よりよく知られた問題へと変換するものである。目標は、結果として得られ る還元されたアルゴリズムの計算量に支配されない、還元アルゴリズムを見つけることである。例えば、ある選択アルゴリズムは、まずリストをソートし（計算 コストの高い部分）、次にソートされたリストの中央の要素を取り出す（計算コストの低い部分）ことで、ソートされていないリストの中央値を求める。この手 法は「変換と征服」としても知られている。 バックトラッキング このアプローチでは、複数の解を段階的に構築し、それらが有効な完全解に導かないと判断された時点で破棄する。 最適化問題 最適化問題については、アルゴリズムのより具体的な分類が存在する。このような問題に対するアルゴリズムは、前述の一般的なカテゴリの1つまたは複数に該 当するだけでなく、以下のいずれかに分類される場合がある。 線形計画法 線形等式および不等式制約に束縛された線形関数の最適解を探索する場合、制約を直接利用して最適解を導出できる。このカテゴリの問題を解くアルゴリズムは 存在し、一般的なシンプレックス法などが挙げられる。[57] 線形計画法で解ける問題には、有向グラフの最大流問題などがある。もし問題において未知数のいずれかが整数である必要がある場合、その問題は整数計画法に 分類される。線形計画法アルゴリズムは、整数値に関するすべての制約が表面的であること、すなわち解がいずれにせよこれらの制約を満たすことが証明できれ ば、そのような問題を解くことができる。一般の場合、問題の難易度に応じて、特化されたアルゴリズムまたは近似解を求めるアルゴリズムが用いられる。 動的計画法 問題に最適部分構造（つまり、部分問題の最適解から全体の問題の最適解を構築できること）と、重複する部分問題（つまり、多くの異なる問題インスタンスを 解くために同じ部分問題が使用されること）が見られる場合、動的計画法と呼ばれるより迅速なアプローチにより、解の再計算を回避できる。例えば、重み付き グラフにおける始点と終点の間の最短経路は、すべての隣接頂点から終点への最短経路を用いて求めることができる。動的計画法とメモ化は密接に関連してい る。「分割統治法」とは異なり、動的計画法における部分問題はしばしば重複する。動的計画法と単純な再帰との違いは、再帰呼び出しのキャッシュ化、すなわ ちメモ化にある。部分問題が独立しており、繰り返されない場合、メモ化は役に立たない。したがって、動的計画法はすべての複雑な問題に適用できるわけでは ない。メモ化を用いた動的計画法は、多くの問題の計算量を指数関数級から多項式級へと低減させる。 貪欲法 貪欲アルゴリズムは、動的計画法と同様に、部分構造を検査することで動作する。ただし、この場合は問題そのものではなく、与えられた解の部分構造を検査す る。このようなアルゴリズムは、ある解から始め、小さな修正を加えることでそれを改善していく。問題によっては常に最適解を見つけるが、他の問題では局所 最適解で止まってしまうこともある。貪欲アルゴリズムの最も一般的な用途は、負のサイクルを持たないグラフの最小全域木を見つけることである。ハフマン 木、クルスカル法、プリム法、ソリン法は、この最適化問題を解くことができる貪欲法である。 ヒューリスティック法 最適化問題において、ヒューリスティックアルゴリズムは、最適解の探索が現実的でない場合に、最適解に近い解を見つける。これらのアルゴリズムは、処理が 進むにつれて最適解にますます近づいていく。原則として、無限に実行し続ければ、最適解を見つけることになる。理想的には、比較的短時間で最適解に極めて 近い解を見出すことができる。これらのアルゴリズムには、局所探索、タブー探索、シミュレーテッド・アニーリング、遺伝的アルゴリズムなどが含まれる。シ ミュレーテッド・アニーリングのように非決定論的なアルゴリズムもあれば、タブー探索のように決定論的なアルゴリズムもある。非最適解の誤差の上限が分 かっている場合、そのアルゴリズムはさらに近似アルゴリズムとして分類される。
Examples Further information: List of algorithms One of the simplest algorithms finds the largest number in a list of numbers of random order. Finding the solution requires looking at every number in the list. From this follows a simple algorithm, which can be described in plain English as: High-level description: 1. If a set of numbers is empty, then there is no highest number. 2. Assume the first number in the set is the largest. 3. For each remaining number in the set: if this number is greater than the current largest, it becomes the new largest. 4. When there are no unchecked numbers left in the set, consider the current largest number to be the largest in the set. (Quasi-)formal description: Written in prose but much closer to the high-level language of a computer program, the following is the more formal coding of the algorithm in pseudocode or pidgin code: Algorithm LargestNumber Input: A list of numbers L. Output: The largest number in the list L. if L.size = 0 return null largest ← L[0] for each item in L, do     if item > largest, then         largest ← item return largest "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item. "return" terminates the algorithm and outputs the following value.	例 詳細情報：アルゴリズム一覧 最も単純なアルゴリズムの一つは、順不同の数字のリストの中から最大の数字を見つけるものだ。解を見つけるには、リスト内のすべての数字を調べる必要があ る。これに基づいて、次のような単純なアルゴリズムが導かれる。平易な言葉で説明すると： 概要： 1. 数字の集合が空の場合、最大の数字は存在しない。 2. 集合の最初の数が最大数であると仮定する。 3. 集合内の残りの各数について：その数が現在の最大数より大きい場合、それが新しい最大数となる。 4. 集合内に未確認の数が残っていない場合、現在の最大数を集合内の最大数とみなす。 （準）形式的な記述：散文で書かれているが、コンピュータプログラムの高レベル言語に非常に近い、以下の記述は、擬似コードまたはピジンコードによる、よ り形式的なアルゴリズムの記述である： アルゴリズム LargestNumber 入力：数値のリスト L。 出力：リスト L における最大の数値。 if L.size = 0 return null largest ← L[0] for each item in L, do     if item > largest, then         largest ← item return largest 「←」は代入を表す。例えば、「largest ← item」は、largestの値がitemの値に変わることを意味する。 「return」はアルゴリズムを終了させ、次の値を出力する。
Abstract machine ALGOL Algorithm = Logic + Control Algorithm aversion Algorithm engineering Algorithm characterizations Algorithmic bias Algorithmic composition Algorithmic entities Algorithmic synthesis Algorithmic technique Algorithmic topology Computational mathematics Garbage in, garbage out Introduction to Algorithms (textbook) Government by algorithm List of algorithms List of algorithm books List of algorithm general topics Medium is the message Regulation of algorithms Theory of computation Computability theory Computational complexity theory	抽象機械 ALGOL アルゴリズム = 論理 + 制御 アルゴリズム嫌悪 アルゴリズム工学 アルゴリズムの特性化 アルゴリズム的バイアス アルゴリズム的構成 アルゴリズム的実体 アルゴリズム的合成 アルゴリズム的手法 アルゴリズム的位相論 計算数学 ゴミを入れれば、ゴミが出る 『アルゴリズム入門』（教科書） アルゴリズムによる統治 アルゴリズム一覧 アルゴリズムに関する書籍一覧 アルゴリズムの一般的なトピック一覧 メディアはメッセージである アルゴリズムの規制 計算論 計算可能性理論 計算複雑性理論
Notes 01. "Definition of ALGORITHM". Merriam-Webster Online Dictionary. Archived from the original on February 14, 2020. Retrieved November 14, 2019.  David A. Grossman, Ophir Frieder, Information Retrieval: Algorithms and Heuristics, 2nd edition, 2004, ISBN 1402030045  "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).  Well defined concerning 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).  "an algorithm is a procedure for computing a function (concerning some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1977:1).  "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).  "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1971:5).  "An algorithm has one or more outputs, i.e., quantities which have a specified relation to the inputs" (Knuth 1973:5).  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 the use of continuous methods or analog devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers 1987:2). 10. Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia and Grafton, Anthony. Information: A Historical Companion, Princeton: Princeton University Press, 2021. p. 247  "algorism". Oxford English Dictionary. Retrieved May 18, 2025.  Chaucer, Geoffrey. "The Miller's Tale". Line 3210.  Skeat, Walter William (1914). "agrim, agrum". In Mayhew, Anthony Lawson (ed.). A Glossary of Tudor and Stuart Words: Especially from the Dramatists. Clarendon Press. pp. 5–6.  Grabiner, Judith V. (December 2013). "The role of mathematics in liberal arts education". In Matthews, Michael R. (ed.). International Handbook of Research in History, Philosophy and Science Teaching. Springer. pp. 793–836. doi:10.1007/978-94-007-7654-8_25. ISBN 9789400776548.  "algorithm". Oxford English Dictionary. Retrieved May 18, 2025.  Stone (1971), p. 8.  Simanowski, Roberto (2018). The Death Algorithm and Other Digital Dilemmas. Untimely Meditations. Vol. 14. Translated by Chase, Jefferson. Cambridge, Massachusetts: MIT Press. p. 147. ISBN 9780262536370. Archived from the original on December 22, 2019. Retrieved May 27, 2019. [...] the next level of abstraction of central bureaucracy: globally operating algorithms.  Dietrich, Eric (1999). "Algorithm". In Wilson, Robert Andrew; Keil, Frank C. (eds.). The MIT Encyclopedia of the Cognitive Sciences. MIT Cognet library. Cambridge, Massachusetts: MIT Press (published 2001). p. 11. ISBN 9780262731447. Retrieved July 22, 2020. An algorithm is a recipe, method, or technique for doing something.  Stone requires that "it must terminate in a finite number of steps" (Stone 1973:7–8). 20. Boolos and Jeffrey 1974, 1999:19  Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip. Springer Science & Business Media. pp. 7–8. ISBN 9783642181924.  Sriram, M. S. (2005). "Algorithms in Indian Mathematics". In Emch, Gerard G.; Sridharan, R.; Srinivas, M. D. (eds.). Contributions to the History of Indian Mathematics. Springer. p. 153. ISBN 978-93-86279-25-5.  Hayashi, T. (2023, January 1). Brahmagupta. Encyclopedia Britannica.  Zaslavsky, Claudia (1970). "Mathematics of the Yoruba People and of Their Neighbors in Southern Nigeria". The Two-Year College Mathematics Journal. 1 (2): 76–99. doi:10.2307/3027363. ISSN 0049-4925. JSTOR 3027363.  Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons. ISBN 978-1-118-46029-0.  Chabert, Jean-Luc, ed. (1999). A History of Algorithms. doi:10.1007/978-3-642-18192-4. ISBN 978-3-540-63369-3.  Dooley, John F. (2013). A Brief History of Cryptology and Cryptographic Algorithms. Springer Science & Business Media. pp. 12–3. ISBN 9783319016283.  Knuth, Donald E. (1972). "Ancient Babylonian Algorithms" (PDF). Commun. ACM. 15 (7): 671–677. doi:10.1145/361454.361514. ISSN 0001-0782. S2CID 7829945. Archived from the original (PDF) on December 24, 2012.  Aaboe, Asger (2001). Episodes from the Early History of Astronomy. New York: Springer. pp. 40–62. ISBN 978-0-387-95136-2. 30. Ast, Courtney. "Eratosthenes". Wichita State University: Department of Mathematics and Statistics. Archived from the original on February 27, 2015. Retrieved February 27, 2015.  Knuth, Donald E. (1996). Selected Papers on Computer Science. CSLI Publications. pp. 1–2. Al-Khwarizmi's work was the first to provide a systematic, rule-based approach to solving equations, which is why the word 'algorithm' was coined from his name to describe this methodical process.  Bolter 1984:24  Bolter 1984:26  Bolter 1984:33–34, 204–206.  Bell and Newell diagram 1971:39, cf. Davis 2000  Melina Hill, Valley News Correspondent, A Tinkerer Gets a Place in History, Valley News West Lebanon NH, Thursday, March 31, 1983, p. 13.  Davis 2000:14  Kleene 1943 in Davis 1965:274  Rosser 1939 in Davis 1965:225 40. Sipser 2006:157  Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of run-time evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2): 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.  Gillian Conahan (January 2013). "Better Math Makes Faster Data Networks". discovermagazine.com. Archived from the original on May 13, 2014. Retrieved May 13, 2014.  Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price, "ACM-SIAM Symposium On Discrete Algorithms (SODA) Archived July 4, 2013, at the Wayback Machine, Kyoto, January 2012. See also the sFFT Web Page Archived February 21, 2012, at the Wayback Machine.  "Best Case". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology (NIST). National Institute of Standards and Technology. Retrieved May 29, 2025.  "worst case". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology (NIST). National Institute of Standards and Technology (NIST). Retrieved May 29, 2025.  Goodrich, Michael T.; Tamassia, Roberto (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons, Inc. ISBN 978-0-471-38365-9. Archived from the original on April 28, 2015. Retrieved June 14, 2018.  "Big-O notation (article) | Algorithms". Khan Academy. Retrieved June 3, 2024.  John G. Kemeny and Thomas E. Kurtz 1985 Back to Basic: The History, Corruption, and Future of the Language, Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0.  Tausworthe 1977:101 50. Tausworthe 1977:142  Knuth 1973 section 1.2.1, expanded by Tausworthe 1977 at pages 100ff and Chapter 9.1  "The Experts: Does the Patent System Encourage Innovation?". The Wall Street Journal. May 16, 2013. ISSN 0099-9660. Retrieved March 29, 2017.  Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems | Hans Kellerer | Springer. Springer. doi:10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. S2CID 28836720. Archived from the original on October 18, 2017. Retrieved September 19, 2017.  Goodrich, Michael T.; Tamassia, Roberto (2001). "5.2 Divide and Conquer". Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. p. 263. ISBN 9780471383659.  Goodrich & Tamassia (2001), p. 245, 4.7.1 Prune-and-search.  For instance, the volume of a convex polytope (described using a membership oracle) can be approximated to high accuracy by a randomized polynomial time algorithm, but not by a deterministic one: see Dyer, Martin; Frieze, Alan; Kannan, Ravi (January 1991). "A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies". J. ACM. 38 (1): 1–17. CiteSeerX 10.1.1.145.4600. doi:10.1145/102782.102783. S2CID 13268711. 57. George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.	注 01. 「アルゴリズムの定義」。メリアム・ウェブスターオンライン辞書。2020年2月14日にオリジナルからアーカイブされた。2019年11月14日に閲 覧。  デビッド・A・グロスマン、オフィール・フリーダー、『情報検索：アルゴリズムとヒューリスティクス』、第2版、2004年、ISBN 1402030045   「例えば、あらゆる古典的な数学的アルゴリズムは、有限個の英語の単語で記述することができる」（Rogers 1987:2）。  アルゴリズムを実行する主体に関して明確に定義されている：「指示に反応し、計算を実行できる計算主体（通常は人間）が存在する」 （Rogers 1987:2）。 「アルゴリズムとは、（整数に関する何らかの選択された表記法に関して）関数を計算するための手順である……この（数値関数への）制限は、一般性の喪失を もたらさない」（Rogers 1977:1）。 「アルゴリズムには、0個以上の入力、すなわちアルゴリズムが開始される前に最初に与えられる量がある」（Knuth 1973:5）。 「有限性のみを欠く可能性がある点を除き、アルゴリズムのすべての特徴を備えた手順は、『計算手法』と呼ぶことができる」（Knuth 1971:5）。 「アルゴリズムは一つ以上の出力、すなわち入力と特定の関係を持つ量を有する」（Knuth 1973:5）。 （入力を含まない）内部プロセスがランダムなプロセスがアルゴリズムであるかどうかは議論の余地がある。ロジャースは次のように述べている。「計算は、連 続的な方法やアナログ装置を使用することなく、離散的な段階的な方法で実行される……サイコロなどのランダムな方法や装置に頼ることなく、決定論的に進め られる」（Rogers 1987:2）。 10. ブレア、アン、デュギッド、ポール、ゴーイング、アンヤ＝シルヴィア、グラフトン、アンソニー。『Information: A Historical Companion』、プリンストン：プリンストン大学出版局、2021年。p. 247 「algorism」。オックスフォード英語辞典。2025年5月18日閲覧。 チョーサー、ジェフリー。「粉屋の話」。3210行目。  スキート、ウォルター・ウィリアム（1914）。「agrim, agrum」。メイヒュー、アンソニー・ローソン（編）。『チューダー朝およびスチュアート朝用語集：特に劇作家からの引用』。クラレンドン・プレス。 pp. 5–6。 グラビナー、ジュディス・V.（2013年12月）。「リベラルアーツ教育における数学の役割」。マシューズ、マイケル・R.（編）。『歴史・哲学・科学 教育研究国際ハンドブック』。スプリンガー。793–836頁。doi:10.1007/978-94-007-7654-8_25。ISBN 9789400776548. 「アルゴリズム」。『オックスフォード英語辞典』。2025年5月18日閲覧。 ストーン（1971年）、p. 8。  シマノフスキー、ロベルト（2018年）。『死のアルゴリズムとその他のデジタル・ジレンマ』。Untimely Meditations。第14巻。チェイス、ジェファーソン訳。マサチューセッツ州ケンブリッジ：MITプレス。p. 147。ISBN 9780262536370。2019年12月22日にオリジナルからアーカイブされた。2019年5月27日閲覧。[...] 中央官僚機構の次の抽象化レベル：地球規模で動作するアルゴリズム。  ディートリッヒ、エリック（1999）。「アルゴリズム」。ウィルソン、ロバート・アンドリュー；カイル、フランク・C.（編）。『MIT認 知科学百科事典』。MIT Cognetライブラリー。マサチューセッツ州ケンブリッジ：MITプレス（2001年刊）。p. 11。ISBN 9780262731447。2020年7月22日に取得。アルゴリズムとは、何かを行うためのレシピ、方法、または技術である。 ストーンは、「有限回のステップで終了しなければならない」と要求している（ストーン 1973:7–8）。 20. ブーロスとジェフリー 1974, 1999:19  シャベール、ジャン＝リュック（2012）。『アルゴリズムの歴史：小石からマイクロチップまで』。スプリンガー・サイエンス＆ビジネス・メ ディア。pp. 7–8。ISBN 9783642181924.  スリラム, M. S. (2005). 「インド数学におけるアルゴリズム」. Emch, Gerard G.; Sridharan, R.; Srinivas, M. D. (編). 『インド数学史への寄稿』. Springer. p. 153. ISBN 978-93-86279-25-5.  林, T. (2023年1月1日). ブラマグプタ. ブリタニカ百科事典.  ザスラフスキー, クローディア (1970). 「ナイジェリア南部のヨルバ族とその近隣住民の数学」. 『The Two-Year College Mathematics Journal』. 1 (2): 76–99. doi:10.2307/3027363. ISSN 0049-4925. JSTOR 3027363. クック, ロジャー・L. (2005). 『数学史：概説』. ジョン・ワイリー・アンド・サンズ. ISBN 978-1-118-46029-0.   シャベール、ジャン＝リュック編（1999）。『アルゴリズムの歴史』。doi:10.1007/978-3-642-18192-4。ISBN 978-3-540-63369-3。  ドゥーリー、ジョン・F.（2013）。『暗号学と暗号アルゴリズムの簡史』. Springer Science & Business Media. pp. 12–3. ISBN 9783319016283.  クヌース, ドナルド・E. (1972). 「古代バビロニアのアルゴリズム」 (PDF). Commun. ACM. 15 (7): 671–677. doi:10.1145/361454.361514. ISSN 0001-0782. S2CID 7829945. 2012年12月24日にオリジナル (PDF) からアーカイブされた。  アボー、アスガー (2001). 『天文学の初期史におけるエピソード』. ニューヨーク：スプリンガー。pp. 40–62。ISBN 978-0-387-95136-2。 30. アスト、コートニー。「エラトステネス」。ウィチタ州立大学：数学・統計学部。2015年2月27日にオリジナルからアーカイブされた。2015年2月 27日に取得。  クヌース、ドナルド・E. (1996). 『コンピュータ科学選集』. CSLI Publications. pp. 1–2. アル＝フワリズミの業績は、方程式を解くための体系的で規則に基づいたアプローチを初めて提供したものであり、そのため、この方法論的なプロセスを表す言 葉として、彼の名前に由来する「アルゴリズム」という言葉が造語された。  ボルター 1984:24  ボルター 1984:26   Bolter 1984:33–34, 204–206.  Bell and Newell diagram 1971:39, cf. Davis 2000  Melina Hill, Valley News Correspondent, A Tinkerer Gets a Place in History, Valley News West Lebanon NH, 1983年3月31日木曜日, p. 13.   Davis 2000:14  Kleene 1943 in Davis 1965:274  Rosser 1939 in Davis 1965:225 40. Sipser 2006:157  Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). 「実行時評価の（ブラック）アート：我々はアルゴリズムを比較しているのか、それとも実装を比較しているのか？」。Knowledge and Information Systems. 52 (2): 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.  ジリアン・コナハン（2013年1月）。「数学の進歩がデータネットワークを高速化する」。discovermagazine.com。 2014年5月13日にオリジナルからアーカイブされた。2014年5月13日に閲覧。 ハイサム・ハサニエ、ピョートル・インディク、ディナ・カタビ、エリック・プライス、「ACM-SIAM離散アルゴリズムシンポジウム（SODA）」 2013年7月4日ウェイバックマシンにアーカイブ、京都、2012年1月。sFFTのWebページも参照のこと。2012年2月21日ウェイバックマシ ンにアーカイブ。 「ベストケース」。『アルゴリズムとデータ構造辞典』。米国国立標準技術研究所（NIST）。米国国立標準技術研究所（NIST）。2025年5月29日 閲覧。 「ワーストケース」。『アルゴリズムとデータ構造辞典』。米国国立標準技術研究所（NIST）。米国国立標準技術研究所（NIST）。2025年5月29 日閲覧。 Goodrich, Michael T.; Tamassia, Roberto (2002). 『アルゴリズム設計：基礎、解析、およびインターネットの例』. John Wiley & Sons, Inc. ISBN 978-0-471-38365-9. 2015年4月28日にオリジナルからアーカイブされた。2018年6月14日閲覧。 「Big-O表記（記事） | アルゴリズム」. Khan Academy. 2024年6月3日閲覧.  John G. Kemeny and Thomas E. Kurtz 1985 『Back to Basic: The History, Corruption, and Future of the Language』, Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0.   タウスワース 1977:101 50. タウスワース 1977:142  クヌース 1973 第1.2.1節、タウスワース 1977の100ページ以降および第9.1章で展開  「専門家たち：特許制度はイノベーションを促進するか？」。ウォール・ストリート・ジャーナル。2013年5月16日。ISSN 0099-9660。2017年3月29日閲覧。  ケラーラー、ハンス；ペルシー、ウルリッヒ；ピシンガー、デビッド（2004）。『ナップサック問題 | ハンス・ケラーラー | スプリンガー』。スプリンガー。doi:10.1007/978-3-540-24777-7。ISBN 978-3-540-40286-2. S2CID 28836720. 2017年10月18日にオリジナルからアーカイブされた。2017年9月19日閲覧。 Goodrich, Michael T.; Tamassia, Roberto (2001). 「5.2 分割統治法」. 『アルゴリズム設計：基礎、解析、およびインターネット上の例』. John Wiley & Sons. p. 263. ISBN 9780471383659.   Goodrich & Tamassia (2001), p. 245, 4.7.1 Prune-and-search.  例えば、凸多面体（所属オラクルを用いて記述される）の体積は、ランダム化された多項式時間アルゴリズムによって高精度に近似できるが、決定 論的なアルゴリズムではできない。Dyer, Martin; Frieze, Alan; Kannan, Ravi (1991年1月). 「A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies」. J. ACM. 38 (1): 1–17. CiteSeerX 10.1.1.145.4600. doi:10.1145/102782.102783. S2CID 13268711. 57. George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
Bibliography Axt, P (1959). "On a Subrecursive Hierarchy and Primitive Recursive Degrees". Transactions of the American Mathematical Society. 92 (1): 85–105. doi:10.2307/1993169. JSTOR 1993169. Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw–Hill Book Company, New York. ISBN 0-07-004357-4. Blass, Andreas; Gurevich, Yuri (2003). "Algorithms: A Quest for Absolute Definitions" (PDF). Bulletin of European Association for Theoretical Computer Science. 81. Archived (PDF) from the original on October 9, 2022. Includes a bibliography of 56 references. Bolter, David J. (1984). Turing's Man: Western Culture in the Computer Age (1984 ed.). Chapel Hill, NC: The University of North Carolina Press. ISBN 978-0-8078-1564-9., ISBN 0-8078-4108-0 Boolos, George; Jeffrey, Richard (1999) [1974]. Computability and Logic (4th ed.). Cambridge University Press, London. ISBN 978-0-521-20402-6.: cf. Chapter 3 Turing machines where they discuss "certain enumerable sets not effectively (mechanically) enumerable". Burgin, Mark (2004). Super-Recursive Algorithms. Springer. ISBN 978-0-387-95569-8. Campagnolo, M.L., Moore, C., and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In Proc. of the 4th Conference on Real Numbers and Computers, Odense University, pp. 91–109 Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045. Reprinted in The Undecidable, p. 89ff. The first expression of "Church's Thesis". See in particular page 100 (The Undecidable) where he defines the notion of "effective calculability" in terms of "an algorithm", and he uses the word "terminates", etc. Church, Alonzo (1936). "A Note on the Entscheidungsproblem". The Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326. S2CID 42323521. Church, Alonzo (1936). "Correction to a Note on the Entscheidungsproblem". The Journal of Symbolic Logic. 1 (3): 101–102. doi:10.2307/2269030. JSTOR 2269030. S2CID 5557237. Reprinted in The Undecidable, p. 110ff. Church shows that the Entscheidungsproblem is unsolvable in about 3 pages of text and 3 pages of footnotes. Daffa', Ali Abdullah al- (1977). The Muslim contribution to mathematics. London: Croom Helm. ISBN 978-0-85664-464-1. Davis, Martin (1965). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. ISBN 978-0-486-43228-1. Davis gives commentary before each article. Papers of Gödel, Alonzo Church, Turing, Rosser, Kleene, and Emil Post are included; those cited in the article are listed here by author's name. Davis, Martin (2000). Engines of Logic: Mathematicians and the Origin of the Computer. New York: W.W. Nortion. ISBN 978-0-393-32229-3. Davis offers concise biographies of Leibniz, Boole, Frege, Cantor, Hilbert, Gödel and Turing with von Neumann as the show-stealing villain. Very brief bios of Joseph-Marie Jacquard, Babbage, Ada Lovelace, Claude Shannon, Howard Aiken, etc. Public Domain This article incorporates public domain material from Paul E. Black. "algorithm". Dictionary of Algorithms and Data Structures. NIST. Dean, Tim (2012). "Evolution and moral diversity". Baltic International Yearbook of Cognition, Logic and Communication. 7. doi:10.4148/biyclc.v7i0.1775. Dennett, Daniel (1995). Darwin's Dangerous Idea. New York: Touchstone/Simon & Schuster. pp. 32–36. ISBN 978-0-684-80290-9. Dilson, Jesse (2007). The Abacus ((1968, 1994) ed.). St. Martin's Press, NY. ISBN 978-0-312-10409-2., ISBN 0-312-10409-X Yuri Gurevich, Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pp. 77–111. Includes bibliography of 33 sources. van Heijenoort, Jean (2001). From Frege to Gödel, A Source Book in Mathematical Logic, 1879–1931 ((1967) ed.). Harvard University Press, Cambridge. ISBN 978-0-674-32449-7., 3rd edition 1976[?], ISBN 0-674-32449-8 (pbk.) Hodges, Andrew (1983). Alan Turing: The Enigma. New York: Simon and Schuster. ISBN 978-0-671-49207-6., ISBN 0-671-49207-1. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof. Kleene, Stephen C. (1936). "General Recursive Functions of Natural Numbers". Mathematische Annalen. 112 (5): 727–742. doi:10.1007/BF01565439. S2CID 120517999. Archived from the original on September 3, 2014. Retrieved September 30, 2013. Presented to the American Mathematical Society, September 1935. Reprinted in The Undecidable, p. 237ff. Kleene's definition of "general recursion" (known now as mu-recursion) was used by Church in his 1935 paper An Unsolvable Problem of Elementary Number Theory that proved the "decision problem" to be "undecidable" (i.e., a negative result). Kleene, Stephen C. (1943). "Recursive Predicates and Quantifiers". Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.2307/1990131. JSTOR 1990131. Reprinted in The Undecidable, p. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in Kleene 1952:300) and name it "Church's Thesis"(Kleene 1952:317) (i.e., the Church thesis). Kleene, Stephen C. (1991) [1952]. Introduction to Metamathematics (Tenth ed.). North-Holland Publishing Company. ISBN 978-0-7204-2103-3. Knuth, Donald (1997). Fundamental Algorithms, Third Edition. Reading, Massachusetts: Addison–Wesley. ISBN 978-0-201-89683-1. Knuth, Donald (1969). Volume 2/Seminumerical Algorithms, The Art of Computer Programming First Edition. Reading, Massachusetts: Addison–Wesley. Kosovsky, N.K. Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms, LSU Publ., Leningrad, 1981 Kowalski, Robert (1979). "Algorithm=Logic+Control". Communications of the ACM. 22 (7): 424–436. doi:10.1145/359131.359136. S2CID 2509896. A.A. Markov (1954) Theory of algorithms. [Translated by Jacques J. Schorr-Kon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e., Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 60-51085.] Minsky, Marvin (1967). Computation: Finite and Infinite Machines (First ed.). Prentice-Hall, Englewood Cliffs, NJ. ISBN 978-0-13-165449-5. Minsky expands his "...idea of an algorithm – an effective procedure..." in chapter 5.1 Computability, Effective Procedures and Algorithms. Infinite machines. Post, Emil (1936). "Finite Combinatory Processes, Formulation I". The Journal of Symbolic Logic. 1 (3): 103–105. doi:10.2307/2269031. JSTOR 2269031. S2CID 40284503. Reprinted in The Undecidable, pp. 289ff. Post defines a simple algorithmic-like process of a man writing marks or erasing marks and going from box to box and eventually halting, as he follows a list of simple instructions. This is cited by Kleene as one source of his "Thesis I", the so-called Church–Turing thesis. Rogers, Hartley Jr. (1987). Theory of Recursive Functions and Effective Computability. The MIT Press. ISBN 978-0-262-68052-3. Rosser, J.B. (1939). "An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem". Journal of Symbolic Logic. 4 (2): 53–60. doi:10.2307/2269059. JSTOR 2269059. S2CID 39499392. Reprinted in The Undecidable, p. 223ff. Herein is Rosser's famous definition of "effective method": "...a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps... a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer" (p. 225–226, The Undecidable) Santos-Lang, Christopher (2015). "Moral Ecology Approaches to Machine Ethics" (PDF). In van Rysewyk, Simon; Pontier, Matthijs (eds.). Machine Medical Ethics. Intelligent Systems, Control and Automation: Science and Engineering. Vol. 74. Switzerland: Springer. pp. 111–127. doi:10.1007/978-3-319-08108-3_8. ISBN 978-3-319-08107-6. Archived (PDF) from the original on October 9, 2022. Scott, Michael L. (2009). Programming Language Pragmatics (3rd ed.). Morgan Kaufmann Publishers/Elsevier. ISBN 978-0-12-374514-9. Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing Company. ISBN 978-0-534-94728-6. Sober, Elliott; Wilson, David Sloan (1998). Unto Others: The Evolution and Psychology of Unselfish Behavior. Cambridge: Harvard University Press. ISBN 9780674930469. Stone, Harold S. (1971). Introduction to Computer Organization and Data Structures. McGraw-Hill, New York. ISBN 9780070617261. Cf. in particular the first chapter titled: Algorithms, Turing Machines, and Programs. His succinct informal definition: "...any sequence of instructions that can be obeyed by a robot, is called an algorithm" (p. 4). Tausworthe, Robert C (1977). Standardized Development of Computer Software Part 1 Methods. Englewood Cliffs NJ: Prentice–Hall, Inc. ISBN 978-0-13-842195-3. Turing, Alan M. (1936–37). "On Computable Numbers, With An Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2. 42: 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712.. Corrections, ibid, vol. 43(1937) pp. 544–546. Reprinted in The Undecidable, p. 116ff. Turing's famous paper completed as a Master's dissertation while at King's College Cambridge UK. Turing, Alan M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society. 45: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. Reprinted in The Undecidable, pp. 155ff. Turing's paper that defined "the oracle" was his PhD thesis while at Princeton. United States Patent and Trademark Office (2006), 2106.02 **>Mathematical Algorithms: 2100 Patentability, Manual of Patent Examining Procedure (MPEP). Latest revision August 2006 Zaslavsky, C. (1970). Mathematics of the Yoruba People and of Their Neighbors in Southern Nigeria. The Two-Year College Mathematics Journal, 1(2), 76–99. https://doi.org/10.2307/3027363 NIST Releases First 3 Finalized Post-Quantum Encryption Standards.	参考文献 Axt, P (1959). 「部分再帰的階層と原始再帰度について」. 『Transactions of the American Mathematical Society』. 92 (1): 85–105. doi:10.2307/1993169. JSTOR 1993169. Bell, C. Gordon and Newell, Allen (1971), 『コンピュータ構造：読解と例題』, McGraw–Hill Book Company, ニューヨーク. ISBN 0-07-004357-4. Blass, Andreas; Gurevich, Yuri (2003). 「アルゴリズム：絶対的定義の探求」 (PDF)。Bulletin of European Association for Theoretical Computer Science. 81. 2022年10月9日にオリジナルからアーカイブ (PDF)。56件の参考文献を含む。 ボルター、デビッド・J. (1984). 『チューリングの男：コンピュータ時代の西洋文化』（1984年版）。ノースカロライナ州チャペルヒル：ノースカロライナ大学出版局。ISBN 978-0-8078-1564-9、ISBN 0-8078-4108-0 ブーロス、ジョージ；ジェフリー、リチャード（1999年）[1974年]。『計算可能性と論理』（第4版）。ケンブリッジ大学出版局、ロンドン。 ISBN 978-0-521-20402-6.: 参照：第3章「チューリングマシン」において、「効果的に（機械的に）列挙不可能な特定の列挙可能集合」について論じられている。 バーギン、マーク（2004）。『超再帰的アルゴリズム』。スプリンガー。ISBN 978-0-387-95569-8。 カンパニョーロ、M.L.、ムーア、C.、およびコスタ、J.F. (2000) 「部分再帰関数のアナログ的特徴付け」。第4回実数とコンピュータに関する会議論文集、オーデンセ大学、pp. 91–109 チャーチ、アロンゾ (1936). 「初等数論における解けない問題」。『American Journal of Mathematics』58巻2号：345–363頁。doi:10.2307/2371045。JSTOR 2371045。『The Undecidable』に再録、89頁以降。「チャーチのテーゼ」の最初の表現。特に100ページ（『The Undecidable』）を参照のこと。そこでは、彼は「アルゴリズム」を用いて「有効な計算可能性」の概念を定義し、「終結する」という言葉などを使 用している。 チャーチ、アロンゾ（1936）。「決定問題に関する一考察」。『記号論理学ジャーナル』。1 (1): 40–41。doi:10.2307/2269326. JSTOR 2269326. S2CID 42323521. チャーチ、アロンゾ（1936）。「決定問題に関する注記への訂正」。『記号論理学ジャーナル』。1 (3): 101–102. doi:10.2307/2269030. JSTOR 2269030. S2CID 5557237. 『The Undecidable』p. 110ff に再録。チャーチは、本文約3ページと脚注約3ページで、決定問題が解けないことを示している。 ダッファ、アリ・アブドゥッラー・アル＝（1977）。『数学へのイスラームの貢献』。ロンドン：クルーム・ヘルム。ISBN 978-0-85664-464-1。 デイヴィス、マーティン（1965）。『The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions』。ニューヨーク：レイヴン・プレス。ISBN 978-0-486-43228-1。デイヴィスは各論文の前に解説を添えている。ゲーデル、アロンゾ・チャーチ、チューリング、ロッサー、クリーネ、エ ミール・ポストの論文が収録されており、本記事で引用されたものは著者の名前順にここに列挙されている。 デイヴィス、マーティン（2000）。『論理のエンジン：数学者とコンピュータの起源』。ニューヨーク：W.W. ノートン。ISBN 978-0-393-32229-3。デイヴィスは、ライプニッツ、ブーレ、フレゲ、カンター、ヒルベルト、ゲーデル、チューリングの簡潔な伝記を提示し ており、フォン・ノイマンは物語をさらう悪役として描かれている。ジョゼフ＝マリー・ジャカード、バベッジ、エイダ・ラブレス、クロード・シャノン、ハ ワード・エイケンなどの非常に短い伝記も含まれている。 パブリックドメイン 本記事には、ポール・E・ブラックによるパブリックドメインの資料が組み込まれている。「アルゴリズム」。『アルゴリズムとデータ構造辞典』。NIST。 ディーン、ティム（2012）。「進化と道徳的多様性」。『Baltic International Yearbook of Cognition, Logic and Communication』。7。doi:10.4148/biyclc.v7i0.1775。 デネット、ダニエル（1995）。『ダーウィンの危険な思想』。ニューヨーク：タッチストーン／サイモン＆シュスター。pp. 32–36。ISBN 978-0-684-80290-9。 ディルソン、ジェシー（2007）。『アバカス』（1968年、1994年版）。セント・マーティンズ・プレス、NY。ISBN 978-0-312-10409-2., ISBN 0-312-10409-X ユーリ・グレヴィッチ、「逐次抽象状態機械による逐次アルゴリズムの表現」、ACM Transactions on Computational Logic、第1巻第1号（2000年7月）、pp. 77–111。参考文献33件を含む。 ファン・ヘイノルト、ジャン（2001）。『フレゲからゲーデルへ：数学論理学の資料集、1879–1931』（（1967）年版）。ハーバード大学出版 局、ケンブリッジ。ISBN 978-0-674-32449-7。第3版 1976年[?]、ISBN 0-674-32449-8（ペーパーバック） ホッジズ、アンドルー（1983）。『アラン・チューリング：エニグマ』。ニューヨーク：サイモン・アンド・シュスター。ISBN 978-0-671-49207-6。ISBN 0-671-49207-1。彼の証明に至る経緯と考察については、「真実の精神」の章を参照のこと。 クリーネ、スティーブン・C. (1936). 「自然数の一般再帰関数」. 『マテマティシェ・アンナレン』. 112 (5): 727–742. doi:10.1007/BF01565439. S2CID 120517999. 2014年9月3日にオリジナルからアーカイブされた。2013年9月30日に取得。1935年9月、アメリカ数学会にて発表。『The Undecidable』p. 237ff に再録。クリーネによる「一般再帰」（現在は μ-再帰として知られる）の定義は、チャーチが1935年の論文『初等数論における解けない問題』において、「決定問題」が「決定不能」であることを証明 する際に用いられた（すなわち、否定的な結果である）。 クリーネ、スティーブン・C. (1943). 「再帰的述語と量詞」. 『アメリカ数学会誌』. 53 (1): 41–73. doi:10.2307/1990131. JSTOR 1990131. 『The Undecidable』に再録、p. 255以降。クリーネは「一般再帰」の定義を洗練させ、第12章「アルゴリズム理論」において「テーゼI」（p. 274）を提示した。彼は後にこのテーゼを（Kleene 1952:300）で繰り返し、「チャーチのテーゼ」（Kleene 1952:317）と名付けた（すなわち、チャーチのテーゼ）。 クリーネ、スティーブン・C. (1991) [1952]. 『メタ数学入門』（第10版）。ノース・ホランド出版。ISBN 978-0-7204-2103-3。 クヌース、ドナルド（1997）。『Fundamental Algorithms』第3版。マサチューセッツ州レディング：アディソン・ウェズリー。ISBN 978-0-201-89683-1。 クヌース、ドナルド（1969）。『The Art of Computer Programming』第1版 第2巻／半数値アルゴリズム。マサチューセッツ州レディング：アディソン・ウェズリー。 コソフスキー, N.K. 『数学的論理の要素とその部分再帰的アルゴリズム理論への応用』, LSU出版, レニングラード, 1981 コワルスキー, ロバート (1979). 「アルゴリズム＝論理＋制御」. Communications of the ACM. 22 (7): 424–436. doi:10.1145/359131.359136. S2CID 2509896. A.A. マルコフ (1954) 『アルゴリズム論』。[翻訳：ジャック・J・ショア＝コンおよびPSTスタッフ] 発行地 モスクワ、ソ連科学アカデミー、1954年 [すなわち、エルサレム、イスラエル科学翻訳プログラム、1961年；米国商務省技術サービス局（ワシントン）より入手可能] 概要 444ページ、28cm。ロシア語のタイトルページを追加。ソ連科学アカデミー数学研究所著作集、第42巻。原題：Teoriya algerifmov。[QA248.M2943 ダートマス大学図書館。米国商務省技術サービス局、番号 OTS 60-51085。] ミンスキー、マービン (1967). 『Computation: Finite and Infinite Machines』（初版）。Prentice-Hall、ニュージャージー州イングルウッド・クリフス。ISBN 978-0-13-165449-5。ミンスキーは第5.1章「計算可能性、有効な手続き、およびアルゴリズム」において、自身の「…アルゴリズムの概念 ――有効な手続き…」を展開している。無限機械。 ポスト、エミル (1936). 「有限組合せ過程、定式化I」. 『記号論理学ジャーナル』. 1 (3): 103–105. doi:10.2307/2269031. JSTOR 2269031. S2CID 40284503. 『The Undecidable』に再録、pp. 289ff。ポストは、単純な指示リストに従い、印を書き込んだり消したりしながら箱から箱へと移動し、最終的に停止する、ある人間の単純なアルゴリズム 的プロセスを定義している。これは、クリーネによって、彼の「テーゼI」、いわゆるチャーチ＝チューリングのテーゼの根拠の一つとして引用されている。 ロジャース、ハートリー・ジュニア（1987）。『再帰関数と有効計算可能性の理論』。MITプレス。ISBN 978-0-262-68052-3。 ロッサー、J.B. (1939). 「ゲーデルの定理とチャーチの定理の証明に関する非公式な解説」. 『Journal of Symbolic Logic』. 4 (2): 53–60. doi:10.2307/2269059. JSTOR 2269059. S2CID 39499392. 『The Undecidable』p. 223ff. に再録。ここにロッサーの有名な「有効な方法」の定義がある：「...各ステップが正確に予め定められており、有限回のステップで確実に答えを導き出す方 法... 「その機械は、問題を投入し、（後に）答えを読み取るという人間の介入以外を必要とせず、集合内のあらゆる問題を解くことになる」」（p. 225–226, 『The Undecidable』） サントス＝ラング, クリストファー (2015). 「機械倫理への道徳生態学的アプローチ」 (PDF). ヴァン・ライセウィック, サイモン; ポンティエ, マティス (編). 『Machine Medical Ethics』. Intelligent Systems, Control and Automation: Science and Engineering. Vol. 74. スイス: Springer. pp. 111–127. doi:10.1007/978-3-319-08108-3_8. ISBN 978-3-319-08107-6. 2022年10月9日にオリジナルからアーカイブ（PDF）された。 スコット、マイケル・L.（2009年）。『プログラミング言語のプラグマティズム』（第3版）。モーガン・カウフマン・パブリッシャーズ／エルゼビア。 ISBN 978-0-12-374514-9。 シプサー、マイケル（2006年）。『計算理論入門』. PWS Publishing Company. ISBN 978-0-534-94728-6. ソーバー, エリオット; ウィルソン, デビッド・スローン (1998). 『他者への奉仕：利他的行動の進化と心理学』. ケンブリッジ: ハーバード大学出版局. ISBN 9780674930469. ストーン, ハロルド・S. (1971). 『コンピュータ組織とデータ構造入門』. マグロウヒル、ニューヨーク. ISBN 9780070617261. 特に第1章「アルゴリズム、チューリングマシン、およびプログラム」を参照。彼の簡潔で非公式な定義：「…ロボットが従うことのできる命令の列は、アルゴ リズムと呼ばれる」（p. 4）。 タウスワース, ロバート・C (1977). 『コンピュータ・ソフトウェアの標準化された開発 第1部 方法論』. ニュージャージー州イングルウッド・クリフス: プレンティス・ホール社. ISBN 978-0-13-842195-3. チューリング, アラン・M. (1936–37). 「計算可能な数について、決定問題への応用を付して」. ロンドン数学会紀要。第2シリーズ。42: 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712.. 訂正、同上、第43巻（1937年）pp. 544–546. 『The Undecidable』p. 116ff に再録。チューリングの有名な論文で、英国ケンブリッジ大学キングス・カレッジ在学中に修士論文として完成したものである。 チューリング, アラン・M. (1939). 「序数に基づく論理体系」. 『ロンドン数学会紀要』. 45: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. 『The Undecidable』155頁以降に再録。「オラクル」を定義したチューリングの論文は、プリンストン大学在学中の博士論文である。 米国特許商標庁 (2006), 2106.02 **>数学的アルゴリズム：2100 特許性、『特許審査手続マニュアル』（MPEP）。最新改訂版 2006年8月 ザスラフスキー, C. (1970). 『ナイジェリア南部のヨルバ族とその近隣住民の数学』. 『The Two-Year College Mathematics Journal』, 1(2), 76–99. https://doi.org/10.2307/3027363 NIST、 最初の3つのポスト量子暗号化標準を最終決定として公表。
Further reading Bellah, Robert Neelly (1985). Habits of the Heart: Individualism and Commitment in American Life. Berkeley: University of California Press. ISBN 978-0-520-25419-0. Berlinski, David (2001). The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer. Harvest Books. ISBN 978-0-15-601391-8. Chabert, Jean-Luc (1999). A History of Algorithms: From the Pebble to the Microchip. Springer Verlag. ISBN 978-3-540-63369-3. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction To Algorithms (3rd ed.). MIT Press. ISBN 978-0-262-03384-8. Harel, David; Feldman, Yishai (2004). Algorithmics: The Spirit of Computing. Addison-Wesley. ISBN 978-0-321-11784-7. Hertzke, Allen D.; McRorie, Chris (1998). "The Concept of Moral Ecology". In Lawler, Peter Augustine; McConkey, Dale (eds.). Community and Political Thought Today. Westport, CT: Praeger. Jon Kleinberg, Éva Tardos(2006): Algorithm Design, Pearson/Addison-Wesley, ISBN 978-0-32129535-4 Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms Archived July 1, 2017, at the Wayback Machine. Stanford, California: Center for the Study of Language and Information. Knuth, Donald E. (2010). Selected Papers on Design of Algorithms Archived July 16, 2017, at the Wayback Machine. Stanford, California: Center for the Study of Language and Information. Wallach, Wendell; Allen, Colin (November 2008). Moral Machines: Teaching Robots Right from Wrong. US: Oxford University Press. ISBN 978-0-19-537404-9. Bleakley, Chris (2020). Poems that Solve Puzzles: The History and Science of Algorithms. Oxford University Press. ISBN 978-0-19-885373-2.	追加文献（さらに読む） ベラ、ロバート・ニーリー（1985）。『心の習慣：アメリカ生活における個人主義とコミットメント』。バークレー：カリフォルニア大学出版局。ISBN 978-0-520-25419-0。 ベルリンスキー、デビッド（2001）。『アルゴリズムの到来：アイデアからコンピュータへの300年の旅』。ハーベスト・ブックス。ISBN 978-0-15-601391-8. シャベール、ジャン＝リュック（1999）。『アルゴリズムの歴史：小石からマイクロチップまで』。シュプリンガー・ヴェルラッグ。ISBN 978-3-540-63369-3。 トーマス・H・コーメン、チャールズ・E・ライサーソン、ロナルド・L・リベスト、クリフォード・スタイン（2009）。『アルゴリズム入門』（第3 版）。MITプレス。ISBN 978-0-262-03384-8。 ハレル、デビッド；フェルドマン、イシャイ（2004）。『アルゴリズム学：計算の精神』. アディソン・ウェズリー. ISBN 978-0-321-11784-7. ハーツケ, アレン・D.; マクローリー, クリス (1998). 「道徳的エコロジーの概念」. ローラー, ピーター・オーガスティン; マッコンキー, デール (編). 『今日のコミュニティと政治思想』. コネチカット州ウェストポート: プレーガー. ジョン・クラインバーグ、エヴァ・タルドス（2006）：『アルゴリズム設計』、ピアソン／アディソン・ウェズリー、ISBN 978-0-32129535-4 ドナルド・E・クヌース（2000）。『アルゴリズム解析に関する選集』2017年7月1日、ウェイバックマシンにアーカイブ。カリフォルニア州スタン フォード：言語・情報研究センター。 ドナルド・E・クヌース（2010）。『アルゴリズム設計に関する選集』2017年7月16日、ウェイバックマシンにアーカイブ。カリフォルニア州スタン フォード：言語・情報研究センター。 ウェンデル・ウォラック、コリン・アレン（2008年11月）。『モラル・マシーンズ：ロボットに善悪を教える』。米国：オックスフォード大学出版局。 ISBN 978-0-19-537404-9. ブリークリー、クリス（2020年）。『パズルを解く詩：アルゴリズムの歴史と科学』。オックスフォード大学出版局。ISBN 978-0-19-885373-2。
https://en.wikipedia.org/wiki/Algorithm

★アルゴリズム思考術 : 問題解決の最強ツール  / ブライアン・クリスチャン, トム・グリフィス著 ; 田沢恭子訳, 早川書房 , 2017

リ ンク

• ︎アルゴリズムについて書く▶︎▶︎︎▶︎▶︎︎▶︎▶︎︎▶︎▶︎︎▶︎▶︎
  

文 献

• アルゴリズム思考術 : 問題解決の最強ツール  / ブライアン・クリスチャン, トム・グリフィス著 ; 田沢恭子訳, 早川書房 , 2019 . - (ハヤカワ文庫, 8342 . ハヤカワ文庫NF ; NF538)︎

そ の他の情報

CC

Copyleft, CC, Mitzub'ixi Quq Chi'j, 1996-2099