アルゴリズム

数学およびコンピュータサイエンスにおけるアルゴリズム( / ˈ æ l ɡ ə r ɪ ð əm / ^ⓘ ）は、数学的に厳密な命令の有限シーケンスであり問題を、計算を。^[1]計算とデータ処理を実行するための仕様として使用されます。より高度なアルゴリズムでは、条件をコード実行をさまざまなルートに転送し（自動意思決定）、有効な推論自動推論と呼ばれます）。

対照的に、ヒューリスティックは、明確に定義された正しい結果や最適な結果がない問題を解決するためのアプローチです。^[2]たとえば、ソーシャルメディアの推奨システムは一般に「アルゴリズム」と呼ばれますが、実際には本当に「正しい」推奨は存在しないため、ヒューリスティックに依存しています。

効果的な方法として、アルゴリズムは有限の空間と時間^[3]^内で、関数[5]を計算するための明確に定義された形式言語^[6]で表現できます。初期状態と初期入力 (おそらく空) から開始し、^[6]命令は計算を記述します。計算が実行されると、有限の数の明確に定義された連続状態^[7]を経て、最終的に「出力」 ^[8]が生成され、最終終了状態で終了します。ある状態から次の状態への遷移は必ずしも決定論的ではありません。ランダム化アルゴリズムと呼ばれる一部のアルゴリズムでは、ランダム入力が組み込まれています。^[9]

語源

825年頃、ペルシャの科学者で博学者のムハンマド・イブン・ムーサ・アル・フワーリズミーは、『インドの計算書』と『インドの算術における加減算』を著した。 ^{[1] 12世紀初頭には、}ヒンドゥー教とアラビア数字のシステムと算術に関するアル・フワーリズミーのテキストのラテン語訳が登場し、例えばセビリアのヨハネの著作とされる『算術実践の書』や、バースのアデラードの著作とされる『インド算術の書』がある。^[10]ここで、alghoarismiまたはalgorismi はアル＝フワーリズミの名前のラテン語化であり、テキストはDixit Algorismi、つまり「アル＝フワーリズミはこう語った」というフレーズで始まります。^[2] 1230年頃、英語の単語algorismが証明され、その後1391年にチョーサーによって英語はフランス語の用語を採用しました。^[3]^[4]^[^{説明が必要}^] 15世紀に、ギリシャ語の ἀριθμός ( arithmos、「数」、cf.「算術」) の影響を受けて、ラテン語はalgorithmusに変更されました。^[^{引用が必要}^]

意味

非公式な定義の 1 つは、「一連の操作を正確に定義する一連の規則」である^[11]^{[引用による確認が必要]。これには、すべての}コンピュータプログラム(数値計算を行わないプログラムを含む)、および規定された官僚的手順^[12] または料理本のレシピ^[13]が含まれる。一般に、プログラムは最終的に停止する場合にのみアルゴリズムである^[14] —無限ループが望ましい場合もあります。Boolos、Jeffrey、1974、1999 は、アルゴリズムを、出力を決定するための明示的な命令セットと定義し、計算機または記号に対して特定の基本操作のみを実行できる人間がそれに従うことができる。^[15]

ほとんどのアルゴリズムは、コンピュータプログラムとして実装されることを目的としています。ただし、アルゴリズムは、生物学的ニューラルネットワーク(たとえば、計算を実行する人間の脳や餌を探す昆虫)、電気回路、機械装置など、他の手段によって実装されることもあります。

歴史

古代のアルゴリズム

数学の問題を解くための段階的な手順は、古代から記録されている。これには、バビロニア数学（紀元前2500年頃）^{[16] 、} エジプト数学（紀元前1550年頃）^{[16] 、} インド数学（紀元前800年頃以降）^[17]^[18]、イファの神託（紀元前500年頃）^[19]、ギリシャ数学（紀元前240年頃）^[20]、アラビア数学（紀元後800年頃）^{[21]などが含まれる。}

アルゴリズムの最古の証拠は、古代メソポタミアの数学に見いだされる。バグダッド近郊のシュルッパクで発見され、紀元前 2500 年頃のシュメールの粘土板には、最古の除算アルゴリズムが記されている。^[16]紀元前1800年頃～紀元前 1600年頃のハンムラビ王朝時代には、バビロニアの粘土板に数式を計算するアルゴリズムが記されていた。^{[22]アルゴリズムは}バビロニアの天文学でも使われていた。バビロニアの粘土板には、重要な天文イベントの時間と場所を計算するアルゴリズムの手順が記され、使用されている。^[23]

算術アルゴリズムは古代エジプトの数学にも見られ、紀元前 1550年頃のリンド数学パピルスにまで遡る。^{[16]アルゴリズムは後に古代}ヘレニズム数学でも使用された。その例としては、ニコマコスの『算術入門』 [ ^24]で説明されているエラトステネスのふるい^[20]^{: Ch 9.2}とユークリッドの互除法^[20]^{: Ch 9.1 があり、これは}ユークリッドの『原論』（紀元前 300年頃）で初めて説明されている。古代インドの数学の例には、シュルバ・スートラ、ケーララ学派、ブラフマスピュタシッダーンタなどがある。^[17]

暗号化されたコードを解読するための最初の暗号アルゴリズムは、9世紀のアラブの数学者アル・キンディーが『暗号文解読に関する手稿』で開発した。彼は、最も初期の暗号解読アルゴリズムである頻度分析による暗号解読法を初めて説明した。^[21]

コンピューター

重力駆動時計

ボルターは、重り駆動時計の発明を「中世ヨーロッパの重要な発明」と呼び、特に機械式時計のチクタク音を生み出すバージ脱進機機構^{[25]を挙げている。「正確な自動機械」}^[26]は、13 世紀の「機械式オートマトン」や、 19 世紀半ばのチャールズ・バベッジとエイダ・ラヴレースの差分エンジンと解析エンジンなどの「計算機械」に直接つながった。 ^[27]ラヴレースは、コンピュータでの処理を目的とした最初のアルゴリズム、バベッジの解析エンジンを設計した。これは、単なる計算機ではなく、真のチューリング完全なコンピュータと見なされた最初の装置である。バベッジの 2 番目の装置の完全な実装は、彼女の死後数十年にわたって実現されなかったが、ラヴレースは「歴史上最初のプログラマー」と呼ばれている。

電気機械式リレー

ベルとニューウェル (1971) は、ホレリスカード(パンチカード) の前身であるジャカード織機と「電話交換技術」が、最初のコンピュータの開発につながったと書いています。^[28] 19 世紀半ばまでには、電話の前身である電信が世界中で使用されていました。19 世紀後半までには、ティッカーテープ( 1870 年代頃) が使用され、ホレリスカード (1890 年頃) も使用されました。その後、テープ上のボードットコードをパンチペーパーで使用したテレプリンター( 1910 年頃)が登場しました。

電気機械式リレーの電話交換ネットワークは1835 年に発明されました。これが1937 年にジョージ・スティビッツによるデジタル加算装置の発明につながりました。ベル研究所で働いていたとき、彼はギア付きの機械式計算機の「面倒な」使用法に気づきました。「1937 年のある晩、彼は自分のアイデアをテストするつもりで家に帰りました... 試行錯誤が終わると、スティビッツは 2 進加算装置を組み立てていました。」^[29]^[30]

形式化

1928年、アルゴリズムの現代概念の部分的な形式化は、デイヴィッド・ヒルベルトが提起した決定問題を解く試みから始まった。その後の形式化は、「効果的な計算可能性」^[31]または「効果的な方法」^[32 ]を定義する試みとして組み立てられた。これらの形式化には、1930年、1934年、1935年のゲーデル・ヘルブラン・クリーネの再帰関数、 1936年のアロンゾ・チャーチのラムダ計算、1936年のエミール・ポストの定式化1、1936年～ 1937年および1939年のアラン・チューリングのチューリングマシンが含まれていた。

表現

アルゴリズムは、自然言語、疑似コード、フローチャート、ドラコンチャート、プログラミング言語、制御テーブル（インタープリタによって処理される）など、さまざまな表記法で表現できます。アルゴリズムの自然言語表現は冗長で曖昧になる傾向があり、複雑なアルゴリズムや技術的なアルゴリズムにはほとんど使用されません。疑似コード、フローチャート、ドラコンチャート、制御テーブルは、自然言語の一般的な曖昧さを回避するアルゴリズムの構造化された表現です。プログラミング言語は主に、アルゴリズムをコンピューターで実行可能な形式で表現するためのものですが、アルゴリズムの定義や文書化にも使用されます。

チューリングマシン

表現方法は多数あり、チューリングマシンプログラムは、マシンテーブルのシーケンス（詳細については、有限状態マシン、状態遷移テーブル、および制御テーブルを参照）、フローチャートやドラコンチャート（詳細については、状態図を参照）、基本的なマシンコードまたは「4つのセット」と呼ばれるアセンブリコードなどの形式で表現できます。アルゴリズムの表現は、チューリングマシンの記述の3つのレベルに分類することもできます。高レベル記述、実装記述、および形式記述です。^[33]高レベル記述は、アルゴリズム自体の品質を記述しますが、チューリングマシン上での実装方法は考慮しません。^[33]実装記述は、アルゴリズムを実行するためにマシンがヘッドを動かしてデータを格納する一般的な方法を記述しますが、正確な状態は示しません。^[33]最も詳細には、形式記述は、チューリングマシンの正確な状態テーブルと遷移のリストを示します。^[33]

フローチャート表現

フローチャートと呼ばれるグラフィカルな補助手段は、アルゴリズム (およびそれに対応するコンピュータプログラム) を記述および文書化する方法を提供します。フローチャートには、プログラムフローを示す矢印、四角形 (SEQUENCE、GOTO)、ひし形 (IF-THEN-ELSE)、およびドット (OR-tie) の 4 つの主要な記号があります。サブ構造は四角形内に「ネスト」できますが、スーパー構造から単一の出口が発生する場合に限られます。

アルゴリズム分析

多くの場合、アルゴリズムにどれだけの時間、ストレージ、その他のコストが必要かを知ることが重要です。このような定量的な答え (推定値) を得るために、アルゴリズムを分析する方法が開発されてきました。たとえば、n個の数値のリストの要素を加算するアルゴリズムでは、ビッグ O 表記法を使用すると、時間要件は⁠ ⁠ $O(n)$ になります。アルゴリズムは、これまでのすべての要素の合計と、入力リスト内の現在の位置という 2 つの値のみを記憶する必要があります。入力数値を格納するために必要なスペースがカウントされない場合、スペース要件は⁠ ⁠ですが、そうでない場合は⁠ ⁠が必要です。 $O(1)$ $O(n)$

異なるアルゴリズムでは、異なる命令セットを使用して、他のアルゴリズムよりも少ない時間、スペース、または「労力」で同じタスクを完了する場合があります。たとえば、バイナリ検索アルゴリズム (コスト⁠ ⁠ ) は、ソートされたリストまたは配列の $O(\log n)$ テーブル検索に使用すると、シーケンシャル検索 (コスト⁠ ⁠ $O(n)$ ) よりも優れたパフォーマンスを発揮します。

形式的対経験的

アルゴリズムの分析と研究は、コンピュータサイエンスの分野です。アルゴリズムは、特定のプログラミング言語や実装を参照せずに、抽象的に研究されることがよくあります。アルゴリズム分析は、実装ではなくアルゴリズムの特性に焦点を当てる点で、他の数学分野に似ています。擬似コードは、単純で一般的な表現であるため、分析によく使用されます。ほとんどのアルゴリズムは、特定のハードウェア/ソフトウェアプラットフォームに実装され、そのアルゴリズムの効率は実際のコードを使用してテストされます。特定のアルゴリズムの効率は、多くの「1 回限りの」問題では重要ではないかもしれませんが、高速でインタラクティブな商用または長期にわたる科学的使用のために設計されたアルゴリズムでは、非常に重要になる場合があります。小さな n から大きな n にスケーリングすると、通常は問題のない非効率的なアルゴリズムが頻繁に明らかになります。

経験的テストは、パフォーマンスに影響を与える予期しない相互作用を発見するのに役立ちます。ベンチマークは、プログラムの最適化後のアルゴリズムの潜在的な改善の前後を比較するために使用できます。ただし、経験的テストは正式な分析に取って代わることはできず、公平に実行するのは簡単ではありません。^[34]

実行効率

十分に確立されたアルゴリズムでも改善の余地があることを示す例として、FFTアルゴリズム（画像処理の分野で多用されている）に関する最近の重要な技術革新により、医療用画像処理などのアプリケーションで処理時間を最大1,000倍短縮できる可能性がある。^[35]一般に、速度の向上は問題の特殊な特性に依存し、実際のアプリケーションでは非常に一般的である。^[36]この規模の高速化により、画像処理を多用するコンピューティングデバイス（デジタルカメラや医療機器など）の消費電力を削減できる。

デザイン

アルゴリズム設計は、問題解決やアルゴリズムのエンジニアリングのための方法または数学的プロセスです。アルゴリズムの設計は、オペレーションリサーチにおける分割統治法や動的計画法など、多くの解決理論の一部です。アルゴリズム設計を設計および実装するための手法は、アルゴリズム設計パターンとも呼ばれ、^[37]テンプレートメソッドパターンやデコレータパターンなどの例があります。アルゴリズム設計の最も重要な側面の1つは、リソース（実行時間、メモリ使用量）の効率です。ビッグオー表記法は、たとえば、入力のサイズが増加するにつれてアルゴリズムの実行時間がどのように増加するかを表すために使用されます。^[38]

構造化プログラミング

チャーチ＝チューリングのテーゼによれば、どんなアルゴリズムもどんなチューリング完全モデルでも計算できる。チューリング完全性には、条件付き GOTO、無条件 GOTO、代入、HALT の 4 つの命令タイプだけが必要である。しかし、ケメニーとカーツは、無条件 GOTO と条件付き IF-THEN GOTO を「無秩序に」使用すると「スパゲッティコード」になる可能性があるが、プログラマーはこれらの命令だけを使用して構造化プログラムを書くことができると指摘している。一方、「構造化言語で構造化の悪いプログラムを書くことも可能であり、それほど難しくはない」。^[39]タウスワースは、3 つのベーム＝ヤコピニ標準構造[ ^40] SEQUENCE、IF-THEN-ELSE、WHILE-DO に、さらに DO-WHILE と CASE の 2 つを追加した。^[41]構造化プログラムのもう 1 つの利点は、数学的帰納法を使用して正しさを証明できることである。^[42]

法的地位

アルゴリズム自体は、通常は特許の対象になりません。米国では、抽象概念、数値、または信号の単純な操作のみからなるクレームは「プロセス」を構成しないため (USPTO 2006)、アルゴリズムは特許の対象になりません ( Gottschalk v. Bensonの場合など)。ただし、アルゴリズムの実際のアプリケーションは特許の対象になる場合があります。たとえば、Diamond v. Diehrでは、合成ゴムの硬化を助けるための単純なフィードバックアルゴリズムの適用は特許の対象とみなされました。ソフトウェアの特許は議論の的となっており、^{[43]アルゴリズム、特に}UnisysのLZW 特許などのデータ圧縮アルゴリズムに関連する特許は批判されています。さらに、一部の暗号化アルゴリズムには輸出制限があります (暗号化の輸出を参照)。

分類

実装によって

再帰: 再帰アルゴリズムは、終了条件を満たすまで繰り返し呼び出される、一般的な関数型プログラミング手法です。反復アルゴリズムは、ループなどの繰り返しやスタックなどのデータ構造を使用して問題を解決します。問題は、いずれかの実装に適している場合があります。ハノイの塔は、一般的に再帰実装を使用して解決されるパズルです。すべての再帰バージョンには、同等の (ただし、複雑さは多少異なる) 反復バージョンがあり、その逆も同様です。
シリアル、パラレル、分散: アルゴリズムは通常、シリアルコンピュータではコンピュータがアルゴリズムの命令を 1 つずつ実行するという前提で説明されます。シリアルアルゴリズムは、並列アルゴリズムや分散アルゴリズムとは異なり、これらの環境向けに設計されています。並列アルゴリズムは、複数のプロセッサが同時に問題に取り組めるコンピュータアーキテクチャを活用します。分散アルゴリズムは、コンピュータネットワークを介して接続された複数のマシンを使用します。並列アルゴリズムと分散アルゴリズムは、問題をサブ問題に分割し、結果をまとめて収集します。これらのアルゴリズムでのリソース消費は、各プロセッサのプロセッササイクルだけでなく、プロセッサ間の通信オーバーヘッドも含まれます。一部のソートアルゴリズムは効率的に並列化できますが、通信オーバーヘッドは高価です。反復アルゴリズムは一般に並列化可能ですが、一部の問題には並列アルゴリズムがなく、本質的にシリアルな問題と呼ばれます。
決定論的か非決定論的か: 決定論的アルゴリズムは、各ステップで正確な決定を下して問題を解決します。一方、非決定論的アルゴリズムは推測によって問題を解決します。推測は通常、ヒューリスティックの使用によってより正確になります。
正確か近似か: 多くのアルゴリズムが正確な解に到達するのに対し、近似アルゴリズムは真の解に近い近似値を求める。このようなアルゴリズムは多くの難しい問題に対して実用的な価値がある。例えば、ナップザック問題では、アイテムのセットがあり、ナップザックに詰めて合計値が最大になるようにすることが目的である。各アイテムには重さと価値がある。持ち運べる合計重量は、ある固定数X以下である。したがって、解決策ではアイテムの価値だけでなく重さも考慮する必要がある。^[44]
量子アルゴリズム: 量子アルゴリズムは、量子計算の現実的なモデルに基づいて実行されます。この用語は通常、本質的に量子的であると思われるアルゴリズムや、量子重ね合わせや量子もつれなどの量子計算の重要な機能を使用するアルゴリズムに対して使用されます。

デザインパラダイムによって

アルゴリズムを分類する別の方法は、設計方法論またはパラダイムによって分類することです。一般的なパラダイムには次のようなものがあります。

ブルートフォースまたは徹底的な検索: ブルートフォースは、最適な解決策が見つかるまで、あらゆる可能なオプションを体系的に試す問題解決方法です。このアプローチは、あらゆる変数の組み合わせをテストするため、非常に時間がかかります。他の方法が利用できない、または複雑すぎる場合によく使用されます。ブルートフォースは、2 点間の最短経路の検索やパスワードの解読など、さまざまな問題を解決できます。
分割して征服する: 分割統治アルゴリズムは、問題を 1 つ以上のより小さなインスタンスに繰り返し縮小し (通常は再帰的に)、インスタンスが簡単に解決できるほど小さくなるまで続けます。マージソートは分割統治の一例で、順序なしリストを 1 つの項目を含むセグメントに分割し、セグメントをマージすることでリスト全体のソートを取得できます。分割統治のより単純な変形は減少統治アルゴリズムと呼ばれ、それ自体の 1 つの小さなインスタンスを解決し、その解決法を使用してより大きな問題を解決します。分割統治は問題を複数の部分問題に分割するため、統治段階は減少統治アルゴリズムよりも複雑です。^{[出典が必要]}減少統治アルゴリズムの例としては、二分探索アルゴリズムがあります。
検索と列挙: 多くの問題 (チェスのプレイなど) は、グラフ上の問題としてモデル化できます。グラフ探索アルゴリズムは、グラフ内を移動するためのルールを指定するもので、このような問題に役立ちます。このカテゴリには、検索アルゴリズム、分岐限定列挙、バックトラッキングも含まれます。
ランダム化アルゴリズム: このようなアルゴリズムは、いくつかの選択をランダム（または擬似ランダム）に行う。正確な解を見つけることが現実的でない場合に、近似解を見つける（以下のヒューリスティックな方法を参照）。問題によっては、最速の近似には何らかのランダム性が伴わなければならない。^[45]多項式時間計算量を持つランダム化アルゴリズムが、いくつかの問題に対して最速のアルゴリズムになり得るかどうかは、 P対NP問題として知られる未解決の問題である。このようなアルゴリズムには、大きく2つのクラスがある。

モンテカルロアルゴリズムは、高い確率で正しい答えを返します。たとえば、RP は多項式時間で実行されるこれらのサブクラスです。
ラスベガスアルゴリズムは常に正しい答えを返しますが、その実行時間は確率的に制限されます（例：ZPP）。

複雑さの軽減: この手法は、難しい問題を、（うまくいけば）漸近的に最適なアルゴリズムで解決できる、よりよく知られた問題に変換します。目標は、結果として得られる縮小アルゴリズムによって複雑さが左右されない縮小アルゴリズムを見つけることです。たとえば、ある選択アルゴリズムは、最初にリストをソートし（コストの高い部分）、次にソートされたリストの中央の要素（コストのかからない部分）を取り出すことで、ソートされていないリストの中央値を見つけます。この手法は、変換と征服とも呼ばれます。
バックトラッキング: このアプローチでは、複数のソリューションが段階的に構築され、有効な完全なソリューションに到達できないと判断された時点で放棄されます。

最適化問題

最適化問題の場合、アルゴリズムはより具体的に分類されます。このような問題のアルゴリズムは、上記の一般的なカテゴリの 1 つ以上と、次のいずれかに分類されます。

線形計画法: 線形等式制約と不等式制約で制限された線形関数の最適解を探す場合、制約を直接使用して最適解を生成することができます。このカテゴリのどの問題でも解くことができるアルゴリズムがあり、たとえば人気のシンプレックスアルゴリズムがあります。^[46]線形計画法で解くことができる問題には、有向グラフの最大フロー問題があります。問題が未知数のいずれかが整数であることも要求する場合、それは整数計画法に分類されます。線形計画法アルゴリズムは、整数値に対するすべての制約が表面的である、つまり、解がいずれにせよこれらの制約を満たすことが証明できれば、そのような問題を解決できます。一般的なケースでは、問題の難易度に応じて、特殊なアルゴリズムまたは近似解を見つけるアルゴリズムが使用されます。
動的プログラミング: 問題が最適なサブ構造 (つまり、最適解はサブ問題に対する最適解から構築できる) と重複するサブ問題(つまり、同じサブ問題が多くの異なる問題インスタンスの解決に使用されている) を示している場合、動的計画法と呼ばれるより迅速なアプローチによって、解の再計算を回避できます。たとえば、フロイド-ワーシャルアルゴリズムでは、重み付きグラフの開始頂点と目標頂点間の最短経路は、すべての隣接する頂点から目標への最短経路を使用して見つけることができます。動的計画法とメモ化は一緒に使用されます。分割統治法とは異なり、動的計画法のサブ問題は重複していることがよくあります。動的計画法と単純な再帰の違いは、再帰呼び出しのキャッシュまたはメモ化です。サブ問題が独立していて繰り返されない場合、メモ化は役に立ちません。したがって、動的計画法はすべての複雑な問題に適用できるわけではありません。メモ化動的計画法を使用すると、多くの問題の複雑性が指数関数的から多項式的へと軽減されます。
貪欲な方法: 貪欲アルゴリズムは、動的計画法と同様に、問題ではなく与えられたソリューションのサブ構造を調べることによって機能します。このようなアルゴリズムは、何らかのソリューションから始めて、小さな変更を加えることでそれを改善します。問題によっては、常に最適なソリューションが見つかりますが、他の問題では、局所最適値で止まる場合があります。貪欲アルゴリズムの最も一般的な用途は、負のサイクルのないグラフの最小全域木を見つけることです。ハフマン木、クラスカル、プリム、ソリンは、この最適化問題を解決できる貪欲アルゴリズムです。
ヒューリスティックな方法: 最適化問題では、最適解を見つけることが現実的でない場合に、ヒューリスティックアルゴリズムによって最適解に近い解が見つかります。これらのアルゴリズムは、処理が進むにつれて最適解にどんどん近づいていきます。原則として、無限の時間実行すると最適解が見つかります。理想的には、比較的短時間で最適解に非常に近い解を見つけることができます。これらのアルゴリズムには、局所探索、タブー探索、シミュレーテッドアニーリング、遺伝的アルゴリズムなどがあります。シミュレーテッドアニーリングのように非決定論的なアルゴリズムもあれば、タブー探索のように決定論的なアルゴリズムもあります。最適でない解の誤差の境界がわかっている場合、アルゴリズムはさらに近似アルゴリズムに分類されます。

例

最も単純なアルゴリズムの 1 つは、ランダムな順序の数字のリストで最大の数字を見つけることです。この解を見つけるには、リスト内のすべての数字を調べる必要があります。このことから、簡単な英語で次のように説明できる単純なアルゴリズムが生まれます。

高レベルの説明:

数字のセットが空の場合、最高数字は存在しません。
セット内の最初の数字が最大であると仮定します。
セット内の残りの各数字について、この数字が現在の最大値より大きい場合は、それが新しい最大値になります。
セット内に未チェックの数字が残っていない場合は、現在の最大数字をセット内の最大数字とみなします。

(準)正式な説明: 散文で書かれていますが、コンピュータプログラムの高級言語に非常に近い、疑似コードまたはピジンコードでのアルゴリズムのより正式なコーディングは次のとおりです。

アルゴリズムLargestNumber
入力: 数値のリストL。出力: リストL
内の最大値。

 L.size = 0の場合、 null
を返すlargest ← L [0]
 Lの各 項目 について、item > largestの場合、largest ← itemを返すlargest

「←」は代入を表します。たとえば、「largest ← item 」はlargestの値がitemの値に変更されることを意味します。
「return」はアルゴリズムを終了し、次の値を出力します。

参照

注記

^ ab 「ALGORITHMの定義」。Merriam -Websterオンライン辞書。2020年2月14日時点のオリジナルよりアーカイブ。2019年11月14日閲覧。
^ ab David A. Grossman、Ophir Frieder、『情報検索：アルゴリズムとヒューリスティックス』第 2 版、2004 年、ISBN 1402030045
^ ab 「たとえば、古典的な数学アルゴリズムはすべて、有限個の英語の単語で記述できます」(Rogers 1987:2)。
^ ab アルゴリズムを実行するエージェントに関して明確に定義されています。「通常は人間である計算エージェントが存在し、命令に反応して計算を実行できます」(Rogers 1987:2)。
^ 「アルゴリズムとは、（整数の選択された表記法に関する） 関数を計算する手順です...この（数値関数への）制限によって一般性が失われることはありません」（Rogers 1987:1）。
^ 「アルゴリズムには0 個以上の入力、つまりアルゴリズムが開始する前に最初に与えられる量があります」(Knuth 1973:5)。
^ 「有限性に欠ける可能性を除いてアルゴリズムのすべての特性を備えた手順は、「計算方法」と呼ばれることがあります」（Knuth 1973:5）。
^ 「アルゴリズムには 1 つ以上の出力、つまり入力と特定の関係を持つ量があります」(Knuth 1973:5)。
^ ランダムな内部プロセス (入力を含まない) を持つプロセスがアルゴリズムであるかどうかは議論の余地があります。ロジャーズは次のように意見を述べています。「計算は、連続的な方法やアナログデバイスを使用せずに、離散的なステップ方式で実行されます...サイコロなどのランダムな方法やデバイスに頼らずに、決定論的に進められます」(Rogers 1987:2)。
^ ブレア、アン、デュギッド、ポール、ゴーイング、アンジャ・シルビア、グラフトン、アンソニー。情報：歴史ガイド、プリンストン：プリンストン大学出版局、2021年、p.247
^ ストーン 1973:4
^ シマノウスキー、ロベルト（2018）。死のアルゴリズムとその他のデジタルジレンマ。Untimely Meditations。第14巻。チェイス、ジェファーソン訳。マサチューセッツ州ケンブリッジ：MITプレス。p.147。ISBN 9780262536370. 2019年12月22日時点のオリジナルよりアーカイブ。2019年5月27日閲覧。[...] 中央官僚機構の抽象化の次のレベル：グローバルに動作するアルゴリズム。
^ ディートリッヒ、エリック (1999)。「アルゴリズム」。ロバート・アンドリュー・ウィルソン、フランク・C・ケイル (編)。MIT 認知科学百科事典。MIT Cognet ライブラリ。マサチューセッツ州ケンブリッジ: MIT プレス (2001 年出版)。11 ページ。ISBN 9780262731447. 2020 年7 月 22 日閲覧。アルゴリズムとは、何かを行うためのレシピ、方法、またはテクニックのことです。
^ ストーンは「有限数のステップで終了する必要がある」と要求している（ストーン1973：7–8）。
^ ブーロスとジェフリー 1974,1999:19
^ abcd Chabert, Jean-Luc (2012).アルゴリズムの歴史: 小石からマイクロチップまで. Springer Science & Business Media. pp. 7–8. ISBN 9783642181924。
^ ab Sriram, MS (2005). 「インド数学におけるアルゴリズム」。Emch, Gerard G.、Sridharan, R.、Srinivas, MD (編)。インド数学の歴史への貢献。Springer。p. 153。ISBN 978-93-86279-25-5。
^ 林徹 (2023年1月1日). ブラフマグプタ. ブリタニカ百科事典.
^ザスラフスキー、クラウディア (1970)。 「ナイジェリア南部のヨルバ族とその近隣住民の数学」。2年制大学数学ジャーナル。1 (2): 76–99。doi : 10.2307 /3027363。ISSN 0049-4925。JSTOR 3027363 。
^ abc クック、ロジャー L. (2005)。数学の歴史：簡単なコース。ジョンワイリーアンドサンズ。ISBN 978-1-118-46029-0。
^ ab Dooley, John F. (2013).暗号学と暗号アルゴリズムの簡潔な歴史. Springer Science & Business Media. pp. 12–3. ISBN 9783319016283。
^ Knuth, Donald E. (1972). 「古代バビロニアのアルゴリズム」(PDF) . Commun. ACM . 15 (7): 671–677. doi :10.1145/361454.361514. ISSN 0001-0782. S2CID 7829945. 2012年12月24日時点のオリジナル(PDF)からアーカイブ。
^ Aaboe, Asger (2001).天文学初期史のエピソード. ニューヨーク: Springer. pp. 40–62. ISBN 978-0-387-95136-2。
^ Ast, Courtney. 「エラトステネス」. ウィチタ州立大学: 数学・統計学部. 2015年2月27日時点のオリジナルよりアーカイブ。 2015年2月27日閲覧。
^ ボルター 1984:24
^ ボルター 1984:26
^ ボルター 1984:33–34、204–206。
^ ベルとニューウェルの図 1971:39、デイビス 2000 を参照
^ メリナ・ヒル、バレー・ニュース特派員、「ティンカーラーが歴史に名を残す」、バレー・ニュース・ウェスト・レバノン、NH、1983年3月31日木曜日、13ページ。
^ デイビス 2000:14
^ クリーネ 1943、デイビス 1965:274
^ Rosser 1939、Davis 1965:225 より
^ abcd シプサー 2006:157
^ Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). 「実行時評価の (ブラック) アート: 比較しているのはアルゴリズムか実装か?」.知識と情報システム. 52 (2): 341–378. doi :10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.
^ Gillian Conahan (2013 年 1 月). 「Better Math Makes Faster Data Networks」. discovermagazine.com. 2014 年 5 月 13 日時点のオリジナルよりアーカイブ。2014年5 月 13 日閲覧。
^ Haitham Hassanieh、Piotr Indyk、Dina Katabi、Eric Price、「ACM-SIAM Symposium On Discrete Algorithms (SODA)」、2013 年 7 月 4 日アーカイブ、Wayback Machine 、京都、2012 年 1 月。また、2012 年 2 月 21 日アーカイブ、 Wayback Machineにある sFFT Web ページも参照してください。
^ Goodrich, Michael T. ; Tamassia, Roberto (2002). アルゴリズム設計: 基礎、分析、インターネットの例。John Wiley & Sons, Inc. ISBN 978-0-471-38365-9. 2015年4月28日時点のオリジナルよりアーカイブ。2018年6月14日閲覧。
^ 「Big-O記法（記事）| アルゴリズム」。カーンアカデミー。 2024年6月3日閲覧。
^ John G. Kemenyと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
^ タウスワース 1977:142
^ Knuth 1973 セクション 1.2.1、Tausworthe 1977 により 100 ページ以降と第 9.1 章で拡張
^ 「専門家：特許制度はイノベーションを促進するか？」ウォール・ストリート・ジャーナル。2013年5月16日。ISSN 0099-9660 。2017年3月29日閲覧。
^ ケラー、ハンス;フェルシー、ウルリッヒ。デイビッド・パイジンジャー (2004)。ナップザックの問題 |ハンス・ケラー |スプリンガー。スプリンガー。土井：10.1007/978-3-540-24777-7。ISBN 978-3-540-40286-2. S2CID 28836720. 2017年10月18日時点のオリジナルよりアーカイブ。2017年9月19日閲覧。
^ たとえば、凸多面体の体積(メンバーシップオラクルを使用して記述) は、ランダム多項式時間アルゴリズムによって高精度に近似できますが、決定論的アルゴリズムでは近似できません。Dyer, Martin、Frieze, Alan、Kannan, Ravi (1991 年 1 月) を参照してください。「凸体の体積を近似するためのランダム多項式時間アルゴリズム」。J . ACM。38 ( 1): 1–17。CiteSeerX 10.1.1.145.4600。doi : 10.1145 /102782.102783。S2CID 13268711 。
^ George B. Dantzigと Mukund N. Thapa。2003 年。線形計画法 2: 理論と拡張。Springer-Verlag。

文献

Axt, P (1959). 「部分再帰階層と原始再帰次数について」.アメリカ数学会誌. 92 (1): 85–105. doi : 10.2307/1993169 . JSTOR 1993169.
Bell, C. Gordon および Newell, Allen (1971)、「Computer Structures: Readings and Examples」、McGraw–Hill Book Company、ニューヨーク。ISBN 0-07-004357-4。
Blass, Andreas ; Gurevich, Yuri (2003). 「アルゴリズム: 絶対的な定義の探求」(PDF) .欧州理論計算機科学協会紀要. 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。
Campagnolo, ML, Moore, C.、および Costa, JF (2000) 部分再帰関数のアナログ特性評価。第 4 回実数とコンピュータに関する会議の議事録、オーデンセ大学、pp. 91–109
チャーチ、アロンゾ(1936)。「初等数論の解決不可能な問題」。アメリカ数学ジャーナル。58 (2): 345–363。doi :10.2307/2371045。JSTOR 2371045。『The Undecidable 』の89 ページ以降に再録。「チャーチのテーゼ」の最初の表現。特に 100 ページ (『 The Undecidable』) を参照。ここでチャーチは「有効な計算可能性」という概念を「アルゴリズム」という観点から定義し、「終了する」という単語などを使用しています。
チャーチ、アロンゾ ( 1936)。「 Entscheidungsproblemに関するノート」。The Journal of Symbolic Logic。1 ( 1 ): 40–41。doi :10.2307/2269326。JSTOR 2269326。S2CID 42323521 。チャーチ、アロンゾ(1936)。「Entscheidungsproblem に関するノートの訂正」。The Journal of Symbolic Logic。1 ( 3) : 101–102。doi :10.2307/2269030。JSTOR 2269030。S2CID 5557237 。『The Undecidable 』110ページ以降に再録。チャーチは、約3ページの本文と3ページの脚注で、Entscheidungsproblemが解決不可能であることを示しています。
ダッファ、アリ・アブドゥラ・アル（1977）。イスラム教の数学への貢献。ロンドン：クルーム・ヘルム。ISBN 978-0-85664-464-1。
デイビス、マーティン(1965)。『決定不能なもの：決定不能な命題、解決不能な問題、計算可能な関数に関する基本論文』ニューヨーク：レイヴン・プレス。ISBN 978-0-486-43228-1。デイビスは各記事の前に解説をしています。ゲーデル、アロンゾ・チャーチ、チューリング、ロッサー、クリーネ、エミール・ポストの論文が含まれています。記事で引用されている論文は、著者名順にリストされています。
デイビス、マーティン（2000年）。『論理エンジン：数学者とコンピュータの起源』ニューヨーク：WW Nortion。ISBN 978-0-393-32229-3。デイビスは、ライプニッツ、ブール、フレーゲ、カントール、ヒルベルト、ゲーデル、チューリングの簡潔な伝記を載せており、フォン・ノイマンは注目を集める悪役となっている。ジョセフ・マリー・ジャカード、バベッジ、エイダ・ラブレス、クロード・シャノン、ハワード・エイケンなどの非常に簡潔な伝記も掲載されている。
この記事には、Paul E. Black のパブリックドメインマテリアルが組み込まれています。「アルゴリズム」。アルゴリズムとデータ構造の辞書。NIST 。
ディーン、ティム（2012）。「進化と道徳的多様性」バルト国際認知・論理・コミュニケーション年鑑。7。doi ：10.4148 /biyclc.v7i0.1775。
デネット、ダニエル(1995)。『ダーウィンの危険な思想』ニューヨーク：タッチストーン/サイモン＆シュスター。pp. 32–36。ISBN 978-0-684-80290-9。
ディルソン、ジェシー (2007)。そろばん ((1968, 1994) 編)。セント・マーチンズ・プレス、ニューヨーク州。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 (2000 年 7 月)、pp. 77–111。33 件の資料の参考文献が含まれています。
ヴァン・ヘイエノールト、ジャン（2001）。『フレーゲからゲーデルまで、1879年から1931年までの数学論理学の原典』（（1967）版）。ハーバード大学出版局、ケンブリッジ。ISBN 978-0-674-32449-7。、第 3 版 1976[?]、ISBN 0-674-32449-8 (pbk.)
ホッジス、アンドリュー（1983年）。アラン・チューリング：エニグマ。ニューヨーク：サイモン＆シュスター。ISBN 978-0-671-49207-6。、ISBN 0-671-49207-1。彼の証明に至る歴史と議論については、「真理の精神」の章を参照。
Kleene, Stephen C. (1936). 「自然数の一般再帰関数」. Mathematische Annalen . 112 (5): 727–742. doi :10.1007/BF01565439. S2CID 120517999. 2014年9月3日時点のオリジナルよりアーカイブ。 2013年9月30日閲覧。1935 年 9 月、アメリカ数学会で発表。The Undecidableの 237 ページ以降に再掲載。Kleene の「一般再帰」(現在は mu-再帰として知られている) の定義は、Church の 1935 年の論文An Unsolvable Problem of Elementary Number Theoryで使用され、この論文では「決定問題」が「決定不能」(つまり、否定的な結果) であることを証明しました。
クリーネ、スティーブン C. ( 1943)。「再帰述語と量指定子」。アメリカ数学会誌。53 (1): 41–73。doi : 10.2307/ 1990131。JSTOR 1990131 。『 The Undecidable』255ページ以降に再録。クリーネは「一般再帰」の定義を洗練し、「12. アルゴリズム理論」の章で「テーゼ I」 (274ページ) を提唱した。彼は後にこのテーゼを繰り返し (クリーネ 1952:300)、「チャーチのテーゼ」 (クリーネ 1952:317) (つまりチャーチのテーゼ) と名付けた。
クリーネ、スティーブン C. (1991) [1952]。メタ数学入門（第 10 版）。ノースホランド出版。ISBN 978-0-7204-2103-3。
クヌース、ドナルド(1997)。『基礎アルゴリズム、第 3 版』。マサチューセッツ州レディング: アディソン・ウェスレー。ISBN 978-0-201-89683-1。
Knuth, Donald (1969)。第 2 巻/半数値アルゴリズム、コンピュータプログラミングの芸術、初版。マサチューセッツ州レディング: Addison–Wesley。
コソフスキー、NK数理論理学の要素と部分再帰アルゴリズムの理論への応用、LSU 出版、レニングラード、1981 年
Kowalski, Robert (1979). 「アルゴリズム=ロジック+制御」. Communications of the ACM . 22 (7): 424–436. doi : 10.1145/359131.359136 . S2CID 2509896.
AA Markov (1954)アルゴリズムの理論。[Jacques J. Schorr-Kon および PST スタッフによる翻訳] 印刷モスクワ、ソ連科学アカデミー、1954 年 [すなわち、エルサレム、イスラエル科学翻訳プログラム、1961 年。ワシントンの米国商務省技術サービス局から入手可能] 説明 444 ページ。28 cm。ソ連科学アカデミー数学研究所の著作のロシア語翻訳、v. 42 に追加。原題: Teoriya algerifmov。[QA248.M2943 ダートマス大学図書館。米国商務省技術サービス局、番号 OTS 60-51085。]
ミンスキー、マービン(1967)。『計算：有限マシンと無限マシン』（初版）。プレンティス・ホール、ニュージャージー州エングルウッド・クリフス。ISBN 978-0-13-165449-5。ミンスキーは、第 5.1 章「計算可能性、効果的な手順、アルゴリズム。無限のマシン」で、「アルゴリズムの概念 - 効果的な手順...」を拡張しています。
ポスト、エミール(1936)。「有限組み合わせプロセス、定式化 I」。記号論理学ジャーナル。1 (3): 103–105。doi :10.2307/2269031。JSTOR 2269031。S2CID 40284503。『The Undecidable』 289ページ以降に再録。ポストは、人間が簡単な指示リストに従って、マークを書いたり消したりしながら箱から箱へと移動し、最終的に停止するという、アルゴリズムのような単純なプロセスを定義しています。これは、クリーネが「テーゼI」、いわゆるチャーチ・チューリングのテーゼの出典の1つとして引用しています。
ロジャース、ハートリー・ジュニア（1987）。再帰関数と実効計算可能性の理論。MIT 出版。ISBN 978-0-262-68052-3。
Rosser, JB ( 1939)。「ゲーデルの定理とチャーチの定理の証明の非公式な解説」。Journal of Symbolic Logic。4 ( 2): 53–60。doi :10.2307/2269059。JSTOR 2269059。S2CID 39499392 。『The Undecidable 』の 223 ページ以降に再録。ここには、ロッサーの「効果的な方法」の有名な定義があります。「...各ステップが正確に事前に決定され、有限数のステップで確実に答えを出す方法...質問を挿入して (後で) 答えを読む以外は人間の介入なしに、セット内のあらゆる問題を解く機械」(225 ～ 226 ページ、『The Undecidable』)
サントス・ラング、クリストファー (2015)。「機械倫理への道徳生態学アプローチ」(PDF)。ヴァン・リセウィク、サイモン、ポンティエ、マタイス (編)。機械医療倫理。インテリジェントシステム、制御、自動化: 科学と工学。第 74 巻。スイス: シュプリンガー。pp. 111–127。doi :10.1007 / 978-3-319-08108-3_8。ISBN 978-3-319-08107-62022年10月9日時点のオリジナルよりアーカイブ（PDF）。
スコット、マイケル L. (2009)。プログラミング言語語用論(第 3 版)。Morgan Kaufmann Publishers/ Elsevier。ISBN 978-0-12-374514-9。
シプサー、マイケル (2006)。計算理論入門。PWS 出版。ISBN 978-0-534-94728-6。
ソバー、エリオット、ウィルソン、デイビッド・スローン（1998年）。『他者へ：利他的な行動の進化と心理学』ケンブリッジ：ハーバード大学出版局。ISBN 9780674930469。
ストーン、ハロルド S. (1972)。コンピュータ組織とデータ構造入門(1972 版)。McGraw-Hill、ニューヨーク。ISBN 978-0-07-061726-1。特に、「アルゴリズム、チューリングマシン、プログラム」というタイトルの最初の章を参照してください。彼の簡潔な非公式の定義は、「ロボットが従うことができる一連の命令はすべて、アルゴリズムと呼ばれます」（p. 4）。
Tausworthe, Robert C (1977)。コンピュータソフトウェアの標準化された開発パート 1 方法。Englewood Cliffs NJ: Prentice–Hall, Inc. ISBN 978-0-13-842195-3。
チューリング、アラン M. ( 1936–37)。「計算可能数について、その計算問題への応用」。ロンドン数学会紀要。シリーズ 2。42 : 230–265。doi :10.1112/plms/s2-42.1.230。S2CID 73712 。. Corrections、同書、第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)。ヨルバ族と南ナイジェリアの近隣住民の数学。2年制大学数学ジャーナル、1(2)、76-99。https://doi.org/10.2307/3027363

さらに読む

ベラ、ロバート・ニーリー（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。
Harel, David; Feldman, Yishai (2004)。『アルゴリズム：コンピューティングの精神』Addison-Wesley。ISBN 978-0-321-11784-7。
Hertzke, Allen D.; McRorie, Chris (1998)。「道徳生態学の概念」。Lawler, Peter Augustine、McConkey, Dale (編)。今日のコミュニティと政治思想。ウェストポート、コネチカット州: 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 . カリフォルニア州スタンフォード: 言語情報研究センター。
Knuth, Donald E. (2010). Selected Papers on Design of Algorithms Archived July 16, 2017, at the Wayback Machine . カリフォルニア州スタンフォード: 言語情報研究センター。
ウォラック、ウェンデル、アレン、コリン（2008年11月）。『道徳マシン：ロボットに善悪を教える』米国：オックスフォード大学出版局。ISBN 978-0-19-537404-9。
ブレイクリー、クリス（2020）。『パズルを解く詩：アルゴリズムの歴史と科学』オックスフォード大学出版局。ISBN 978-0-19-885373-2。

外部リンク

「アルゴリズム」。数学百科事典。EMS Press。2001 [1994]。
Weisstein、Eric W.「アルゴリズム」。MathWorld。
アルゴリズムとデータ構造の辞書 –米国国立標準技術研究所

アルゴリズムリポジトリ

ストーニーブルックアルゴリズムリポジトリ –ニューヨーク州立大学ストーニーブルック校
ACM アルゴリズム集 –計算機協会
スタンフォード GraphBase は 2015 年 12 月 6 日にWayback Machineにアーカイブされました–スタンフォード大学

[:0-1] 「ALGORITHMの定義」。Merriam -Websterオンライン辞書。2020年2月14日時点のオリジナルよりアーカイブ。2019年11月14日閲覧。

[:2-2] David A. Grossman、Ophir Frieder、『情報検索：アルゴリズムとヒューリスティックス』第 2 版、2004 年、ISBN 1402030045

[:3-3] 「たとえば、古典的な数学アルゴリズムはすべて、有限個の英語の単語で記述できます」(Rogers 1987:2)。

[:4-4] アルゴリズムを実行するエージェントに関して明確に定義されています。「通常は人間である計算エージェントが存在し、命令に反応して計算を実行できます」(Rogers 1987:2)。

[5] ^ 「アルゴリズムとは、（整数の選択された表記法に関する） 関数を計算する手順です...この（数値関数への）制限によって一般性が失われることはありません」（Rogers 1987:1）。

[6] 「アルゴリズムには0 個以上の入力、つまりアルゴリズムが開始する前に最初に与えられる量があります」(Knuth 1973:5)。

[7] 「有限性に欠ける可能性を除いてアルゴリズムのすべての特性を備えた手順は、「計算方法」と呼ばれることがあります」（Knuth 1973:5）。

[8] 「アルゴリズムには 1 つ以上の出力、つまり入力と特定の関係を持つ量があります」(Knuth 1973:5)。

[9] ランダムな内部プロセス (入力を含まない) を持つプロセスがアルゴリズムであるかどうかは議論の余地があります。ロジャーズは次のように意見を述べています。「計算は、連続的な方法やアナログデバイスを使用せずに、離散的なステップ方式で実行されます...サイコロなどのランダムな方法やデバイスに頼らずに、決定論的に進められます」(Rogers 1987:2)。

[:1-10] ブレア、アン、デュギッド、ポール、ゴーイング、アンジャ・シルビア、グラフトン、アンソニー。情報：歴史ガイド、プリンストン：プリンストン大学出版局、2021年、p.247

[11] ストーン 1973:4

[12] シマノウスキー、ロベルト（2018）。死のアルゴリズムとその他のデジタルジレンマ。Untimely Meditations。第14巻。チェイス、ジェファーソン訳。マサチューセッツ州ケンブリッジ：MITプレス。p.147。ISBN 9780262536370. 2019年12月22日時点のオリジナルよりアーカイブ。2019年5月27日閲覧。[...] 中央官僚機構の抽象化の次のレベル：グローバルに動作するアルゴリズム。

[13] ディートリッヒ、エリック (1999)。「アルゴリズム」。ロバート・アンドリュー・ウィルソン、フランク・C・ケイル (編)。MIT 認知科学百科事典。MIT Cognet ライブラリ。マサチューセッツ州ケンブリッジ: MIT プレス (2001 年出版)。11 ページ。ISBN 9780262731447. 2020 年7 月 22 日閲覧。アルゴリズムとは、何かを行うためのレシピ、方法、またはテクニックのことです。

[14] ストーンは「有限数のステップで終了する必要がある」と要求している（ストーン1973：7–8）。

[15] ブーロスとジェフリー 1974,1999:19

[Springer_Science_&_Business_Media-16] Chabert, Jean-Luc (2012).アルゴリズムの歴史: 小石からマイクロチップまで. Springer Science & Business Media. pp. 7–8. ISBN 9783642181924。

[:6-17] Sriram, MS (2005). 「インド数学におけるアルゴリズム」。Emch, Gerard G.、Sridharan, R.、Srinivas, MD (編)。インド数学の歴史への貢献。Springer。p. 153。ISBN 978-93-86279-25-5。

[18] 林徹 (2023年1月1日). ブラフマグプタ. ブリタニカ百科事典.

[19] ^ザスラフスキー、クラウディア (1970)。 「ナイジェリア南部のヨルバ族とその近隣住民の数学」。2年制大学数学ジャーナル。1 (2): 76–99。doi : 10.2307 /3027363。ISSN 0049-4925。JSTOR 3027363 。

[Cooke2005-20] クック、ロジャー L. (2005)。数学の歴史：簡単なコース。ジョンワイリーアンドサンズ。ISBN 978-1-118-46029-0。

[Dooley-21] Dooley, John F. (2013).暗号学と暗号アルゴリズムの簡潔な歴史. Springer Science & Business Media. pp. 12–3. ISBN 9783319016283。

[22] Knuth, Donald E. (1972). 「古代バビロニアのアルゴリズム」(PDF) . Commun. ACM . 15 (7): 671–677. doi :10.1145/361454.361514. ISSN 0001-0782. S2CID 7829945. 2012年12月24日時点のオリジナル(PDF)からアーカイブ。

[23] Aaboe, Asger (2001).天文学初期史のエピソード. ニューヨーク: Springer. pp. 40–62. ISBN 978-0-387-95136-2。

[24] Ast, Courtney. 「エラトステネス」. ウィチタ州立大学: 数学・統計学部. 2015年2月27日時点のオリジナルよりアーカイブ。 2015年2月27日閲覧。

[25] ボルター 1984:24

[26] ボルター 1984:26

[27] ボルター 1984:33–34、204–206。

[28] ベルとニューウェルの図 1971:39、デイビス 2000 を参照

[29] メリナ・ヒル、バレー・ニュース特派員、「ティンカーラーが歴史に名を残す」、バレー・ニュース・ウェスト・レバノン、NH、1983年3月31日木曜日、13ページ。

[30] デイビス 2000:14

[31] クリーネ 1943、デイビス 1965:274

[32] Rosser 1939、Davis 1965:225 より

[:5-33] シプサー 2006:157

[KriegelSchubert2016-34] Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). 「実行時評価の (ブラック) アート: 比較しているのはアルゴリズムか実装か?」.知識と情報システム. 52 (2): 341–378. doi :10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.

[35] Gillian Conahan (2013 年 1 月). 「Better Math Makes Faster Data Networks」. discovermagazine.com. 2014 年 5 月 13 日時点のオリジナルよりアーカイブ。2014年5 月 13 日閲覧。

[Hassanieh12-36] Haitham Hassanieh、Piotr Indyk、Dina Katabi、Eric Price、「ACM-SIAM Symposium On Discrete Algorithms (SODA)」、2013 年 7 月 4 日アーカイブ、Wayback Machine 、京都、2012 年 1 月。また、2012 年 2 月 21 日アーカイブ、 Wayback Machineにある sFFT Web ページも参照してください。

[37] Goodrich, Michael T. ; Tamassia, Roberto (2002). アルゴリズム設計: 基礎、分析、インターネットの例。John Wiley & Sons, Inc. ISBN 978-0-471-38365-9. 2015年4月28日時点のオリジナルよりアーカイブ。2018年6月14日閲覧。

[38] 「Big-O記法（記事）| アルゴリズム」。カーンアカデミー。 2024年6月3日閲覧。

[39] John G. Kemenyと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。

[40] タウスワース 1977:101

[41] タウスワース 1977:142

[42] Knuth 1973 セクション 1.2.1、Tausworthe 1977 により 100 ページ以降と第 9.1 章で拡張

[43] 「専門家：特許制度はイノベーションを促進するか？」ウォール・ストリート・ジャーナル。2013年5月16日。ISSN 0099-9660 。2017年3月29日閲覧。

[44] ケラー、ハンス;フェルシー、ウルリッヒ。デイビッド・パイジンジャー (2004)。ナップザックの問題 |ハンス・ケラー |スプリンガー。スプリンガー。土井：10.1007/978-3-540-24777-7。ISBN 978-3-540-40286-2. S2CID 28836720. 2017年10月18日時点のオリジナルよりアーカイブ。2017年9月19日閲覧。

[45] たとえば、凸多面体の体積(メンバーシップオラクルを使用して記述) は、ランダム多項式時間アルゴリズムによって高精度に近似できますが、決定論的アルゴリズムでは近似できません。Dyer, Martin、Frieze, Alan、Kannan, Ravi (1991 年 1 月) を参照してください。「凸体の体積を近似するためのランダム多項式時間アルゴリズム」。J . ACM。38 ( 1): 1–17。CiteSeerX 10.1.1.145.4600。doi : 10.1145 /102782.102783。S2CID 13268711 。

[46] George B. Dantzigと Mukund N. Thapa。2003 年。線形計画法 2: 理論と拡張。Springer-Verlag。

語源

意味

歴史