TPKアルゴリズム

TPKアルゴリズムは、ドナルド・クヌースとルイス・トラブ・パルドがコンピュータプログラミング言語の進化を説明するために考案したシンプルなプログラムです。1977年に出版された彼らの著書『プログラミング言語の初期開発』の中で、トラブ・パルドとクヌースは、配列、インデックス、数学関数、サブルーチン、入出力、条件分岐、反復処理を含む小さなプログラムを紹介しました。そして、これらの概念がどのように表現されるかを示すために、初期のプログラミング言語でこのアルゴリズムの実装を作成しました。

「TPK」という名前を説明するために、著者らはグリムの法則（子音「t」、「p」、「k」に関するもの）、「typical」という単語の音、そして自分たちのイニシャル（Trabb PardoとKnuth）に言及した。^{[ 1 ]}この論文に基づいた講演で、Knuthは次のように述べた。^{[ 2 ]}

このテーマの奥深さを理解するには、優秀な人々がいかに苦労して取り組んできたか、そしてアイデアが一つずつどのように生まれてきたかを知る必要があります。この研究のために――このアイデアの主な発案者はルイスだったと思いますが――私たちは一つのプログラム、つまり一つのアルゴリズムを取り上げ、それをあらゆる言語で記述します。そうすることで、一つの例からその言語特有の特性を素早く把握できるのです。私たちはこれをTPKプログラムと呼んでいますが、それがトラブ・パルドとクヌースの頭文字をとったものであることは、単なる面白い偶然です。

クヌースはそれを次のように説明しています。^{[ 3 ]}

私たちは「TPKアルゴリズム」と呼ばれるシンプルな手順を導入し、それぞれの言語特有のスタイルでTPKを表現することで、各言語の個性を表現しました。[…] TPKアルゴリズムは11個の数値を入力として受け取ります。${\displaystyle a_{0},a_{1},\ldots ,a_{10}}$すると、11組のペアのシーケンスが出力されます。${\displaystyle (10,b_{10}),(9,b_{9}),\ldots ,(0,b_{0}),}$どこ

${\displaystyle b_{i}={\begin{cases}f(a_{i}),&{\text{if }}f(a_{i})\leq 400;\\999,&{\text{if }}f(a_{i})>400;\end{cases}}\quad f(x)={\sqrt {|x|}}+5x^{3}.}$

この単純な作業は、まともなプログラミング言語であれば、明らかにそれほど難しいものではない。

擬似コードでは：

11個の数値をシーケンスS に読み込むように要求する。シーケンスSを逆順にする。シーケンスSの各項目に対して関数を呼び出して操作を実行する。 結果がオーバーフローした 場合はユーザー に警告する。そうでない場合は結果を表示する。

このアルゴリズムは、入力デバイスから11個の数値を読み込み、配列に格納した後、逆順に処理します。各値にユーザー定義関数を適用し、関数の値、または値が一定の閾値を超えたことを示すメッセージを報告します。

• Rosetta Codeでは、多くの言語で実装されています。
• 複数の言語での実装