スタック(抽象データ型)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
プレートのスタックと同様に、追加または削除は上部でのみ可能です。
プッシュおよびポップ操作によるスタックランタイムの単純な表現。

コンピュータサイエンスではスタックは要素のコレクションとして機能する抽象データ型であり、2つの主要な操作があります。

  • コレクションに要素を追加するPush、および
  • Pop。これは、まだ削除されていない最後に追加された要素を削除します。

要素がスタックから外れる順序により、代替名であるLIFO後入れ先出し)が生成されます。さらに、ピーク操作により、スタックを変更せずにトップにアクセスできる場合があります。[1]このタイプの構造の「スタック」という名前は、互いに積み重ねられた一連の物理的なアイテムに類似していることに由来しています。この構造により、スタックの一番上からアイテムを簡単に取り除くことができますが、スタックのより深いアイテムに到達するには、最初に他の複数のアイテムを取り除く必要がある場合があります。[2]

線形データ構造、またはより抽象的には順次コレクションと見なされるプッシュおよびポップ操作は、スタックの最上位と呼ばれる構造の一方の端でのみ発生します。このデータ構造により、スタックを単一リンクリストおよび最上位要素へのポインターとして実装できます。スタックは、容量を制限するように実装できます。スタックがいっぱいで、プッシュされるエンティティを受け入れるのに十分なスペースが含まれていない場合、スタックはオーバーフロー状態にあると見なされます。ポップ操作は、スタックの一番上からアイテムを削除します。

深さ優先探索を実装するには、スタックが必要です

歴史

Stacksは、1946年にAlan M. Turingがサブルーチンを呼び出したり、サブルーチンから戻ったりする手段として「埋める」および「埋めない」という用語を使用したときに、コンピュータサイエンスの文献に登場しました。[3] [4] サブルーチンは、1945年 にコンラートツーゼZ4にすでに実装されていました。

ミュンヘン工科大学のクラウス・サメルソンフリードリッヒ・L・バウアー、1955年にスタックのアイデアを提案し[5] [6]、1957年に特許を申請しました。[7] [8] [9] [10] 1988年3月にサメルソンが亡くなったとき、バウアーはスタック原理の発明でIEEE Computer PioneerAwardを受賞しました。[11] [6]同様の概念は、1954年前半にチャールズレオナルドハンブリン[12]によって、1958年にヴィルヘルムカメラー [ de ]によって独立して開発されました。[13] [14]

スタックは、多くの場合、カフェテリアのプレートのバネ仕掛けのスタックのアナロジーを使用して説明されます。[15] [2] [16]きれいなプレートがスタックの一番上に置かれ、すでにそこにあるものを押し下げます。プレートがスタックから削除されると、その下のプレートがポップアップして新しいトッププレートになります。

必須ではない操作

多くの実装では、スタックには、基本的な「プッシュ」および「ポップ」操作よりも多くの操作があります。必須ではない操作の例は、「スタックの最上位」または「ピーク」です。これは、スタックから削除せずに最上位の要素を監視します。[17]これは、「ポップ」の後に「プッシュ」を続けて同じデータをスタックに返すことで実行できるため、必須の操作とは見なされません。スタックが空の場合、「スタックトップ」または「ポップ」操作の実行時にアンダーフロー状態が発生します。さらに、多くの実装では、スタックが空であるかどうか、およびスタックがそのサイズを返すかどうかのチェックが提供されます。

ソフトウェアスタック

実装

スタックは、配列またはリンクリストのいずれかを介して簡単に実装できますいずれの場合も、データ構造をスタックとして識別するのは、実装ではなくインターフェイスです。ユーザーは、他のヘルパー操作をほとんど行わずに、アイテムを配列またはリンクリストにポップまたはプッシュすることのみが許可されます。以下は、擬似コードを使用した両方の実装を示しています

配列

次のように、配列を使用して(制限付き)スタックを実装できます。通常はゼロオフセットにある最初の要素が下部になりarray[0]、最初の要素がスタックにプッシュされ、最後の要素がポップオフされます。プログラムは、これまでにプッシュされたアイテムの数を記録する変数topを使用して、スタックのサイズ(長さ)を追跡する必要があります。したがって、次の要素が挿入される配列内の場所を指します(ゼロ-ベースのインデックス規則)。したがって、スタック自体は3要素構造として効果的に実装できます。

構造スタック:
    maxsize:整数
    上:整数
    items:アイテムの配列
プロシージャinitialize(stk:スタック、サイズ:整数):
    stk.items←サイズアイテムの新しい配列、最初は空
    stk.maxsize←サイズ
    stk.top←0

プッシュ操作は、オーバーフローをチェックした後 、要素を追加し、最上位のインデックスをインクリメントします。

プロシージャpush(stk:stack、x:item):
     if stk.top = stk.maxsize:
        オーバーフローエラーを報告する
    その他
        stk.items [stk.top]←x
        stk.top←stk.top + 1

同様に、popはアンダーフローをチェックした後、トップインデックスをデクリメントし、以前はトップだったアイテムを返します。

プロシージャpop(stk:スタック):
     stk.top = 0の場合:
        アンダーフローエラーを報告する
    その他
        stk.top←stk.top− 1
        r←stk.items [stk.top]
        rを
返す

動的配列を使用すると、必要に応じて拡大または縮小できるスタックを実装できます。スタックのサイズは単純に動的配列のサイズです。動的配列の最後にアイテムを追加したり、アイテムを削除したりするには、償却されたO(1)時間が必要なため、スタックの非常に効率的な実装です。

リンクリスト

スタックを実装するための別のオプションは、単一リンクリストを使用することです。スタックは、リストの「先頭」へのポインターであり、リストのサイズを追跡するためのカウンターが付いている可能性があります。

構造フレーム:
    データ:アイテム
    次へ:フレームまたはnil
構造スタック:
    ヘッド:フレームまたはnil
    サイズ:整数
プロシージャinitialize(stk:スタック):
    stk.head←nil
    stk.size←0

アイテムのプッシュとポップはリストの先頭で行われます。この実装ではオーバーフローは不可能です(メモリが使い果たされていない限り):

プロシージャpush(stk:スタック、x:アイテム):
    newhead←新しいフレーム
    newhead.data←x
    newhead.next←stk.head
    stk.head←newhead
    stk.size←stk.size + 1
プロシージャpop(stk:スタック):
     if stk.head = nil:
        アンダーフローエラーを報告する
    r←stk.head.data
    stk.head←stk.head.next
    stk.size←stk.size-1
    rを
返す

スタックとプログラミング言語

PerlLISPJavaScriptPythonなどの一部の言語では、スタック操作を標準のリスト/配列型でプッシュおよびポップできます。一部の言語、特にForthファミリーの言語(PostScriptを含む)は、プログラマーが直接表示および操作できる言語定義のスタックを中心に設計されています。

以下は、 Common Lispでスタックを操作する例です(「>」はLispインタープリターのプロンプトです。「>」で始まらない行は式に対するインタープリターの応答です)。

>  setf  stack  list'a  '  b'c    ;; 変数 "stack" 
A  B  C 
>  pop  stack   ;;を設定します。一番上の(左端の)要素を取得し、スタック
A 
> スタックを変更する必要があります        ;; スタックの値を確認します
B  C 
>  push  '新しい スタック  ;; 新しいトップをスタックにプッシュします
NEW  B  C 

C ++標準ライブラリのコンテナタイプのいくつかには、LIFOセマンティクスを使用したpush_backおよびpop_back操作があります。さらに、スタックテンプレートクラスは既存のコンテナを適応させて、プッシュ/ポップ操作のみで制限されたAPIを提供します。PHPにはSplStackクラスがあります。Javaのライブラリには、の特殊化であるクラスが含まれています。以下は、そのクラスを使用し たJava言語のサンプルプログラムです。StackVector

import  java.util.Stack ;

class  StackDemo  { 
    public  static  void  main String [] args  { 
        Stack < String >  stack  =  new  Stack < String > (); 
        スタックプッシュ"A" );     //スタックスタックに「A」を挿入します
        プッシュ"B" ); //スタックスタックに「B」を挿入しますプッシュ"C" ); //スタックスタックに「C」を挿入します    
            
        プッシュ"D" );     //スタックシステムに「D」を挿入します
        アウトprintln スタックピーク()); //スタックの最上位( "D")スタックを出力しますポップ(); //最上位( "D")スタックを削除しますポップ(); //次のトップを削除します( "C")} }    
            
            
    

ハードウェアスタック

アーキテクチャレベルでのスタックの一般的な使用法は、メモリの割り当てとアクセスの手段です。

スタックの基本アーキテクチャ

複数レベルのプロシージャ呼び出しのローカルデータと呼び出し情報を格納する典型的なスタック。このスタックは、その原点から下向きに成長します。スタックポインタは、スタックの現在の最上位のデータを指します。プッシュ操作はポインタをデクリメントし、データをスタックにコピーします。ポップ操作は、スタックからデータをコピーしてから、ポインターをインクリメントします。プログラムで呼び出される各プロシージャは、プロシージャの戻り情報(黄色)とローカルデータ(他の色)をスタックにプッシュすることで格納します。このタイプのスタック実装は非常に一般的ですが、バッファオーバーフロー攻撃に対して脆弱です(テキストを参照)。

一般的なスタックは、原点が固定され、サイズが可変のコンピュータメモリの領域です。最初、スタックのサイズはゼロです。スタックポインタは、通常はハードウェアレジスタの形式で、スタック上の最後に参照された場所を指します。スタックのサイズがゼロの場合、スタックポインタはスタックの原点を指します。

すべてのスタックに適用できる2つの操作は次のとおりです。

  • スタックポインタが指す位置にデータ項目を配置し、スタックポインタ内のアドレスをデータ項目のサイズで調整するプッシュ操作。
  • ポップまたはプル操作:スタックポインターが指す現在の場所のデータ項目が削除され、スタックポインターがデータ項目のサイズによって調整されます。

スタック操作の基本原理には多くのバリエーションがあります。すべてのスタックには、メモリ内の固定された場所があり、そこから始まります。データ項目がスタックに追加されると、スタックポインターが移動して、スタックの現在の範囲を示します。これは、原点から離れて拡張されます。

スタックポインタは、スタックの原点、または原点の上または下の限られた範囲のアドレスを指す場合があります(スタックが成長する方向によって異なります)。ただし、スタックポインタはスタックの原点を越えることはできません。つまり、スタックの起点がアドレス1000にあり、スタックが下向きに(アドレス999、998などに向かって)大きくなる場合、スタックポインタを1000を超えて(1001、1002などに)インクリメントしてはなりません。スタックでのポップ操作により、スタックポインタがスタックの原点を超えて移動すると、スタックアンダーフローが発生します。プッシュ操作によってスタックポインタがスタックの最大範囲を超えてインクリメントまたはデクリメントされると、スタックオーバーフローが発生します。

スタックに大きく依存する一部の環境では、次のような追加の操作が提供される場合があります。

  • 複製:一番上のアイテムがポップされ、次にもう一度押されます(2回)。これにより、前の一番上のアイテムの追加のコピーが一番上になり、元のアイテムがその下になります。
  • ピーク:最上位のアイテムが検査(または返送)されますが、スタックポインターとスタックサイズは変更されません(つまり、アイテムはスタックに残ります)。これは、多くの記事でトップオペレーションとも呼ばれます。
  • 交換または交換:スタック交換場所の一番上の2つのアイテム。
  • 回転(またはロール):最上位のn個のアイテムが回転してスタック上を移動します。たとえば、n = 3の場合、スタック上のアイテム1、2、および3は、それぞれスタック上の位置2、3、および1に移動されます。この操作には多くのバリエーションがあり、最も一般的なのは左回転右回転と呼ばれます。

多くの場合、スタックは下から上に向かって成長して視覚化されます(実際のスタックのように)。また、左から右に成長して「最上部」が「右端」になるように、または上から下に成長するように視覚化することもできます。重要な機能は、スタックの一番下が固定位置にあることです。このセクションの図は、上から下への成長の視覚化の例です。スタック「上」(9)はアイテムがプッシュまたはポップされる場所であるため、上(28)はスタック「下」です。

右に回転すると、最初の要素が3番目の位置に移動し、2番目の要素が最初の位置に移動し、3番目の要素が2番目の位置に移動します。このプロセスの2つの同等の視覚化を次に示します。

アップルバナナ
バナナ===右回転==>きゅうり
きゅうりりんご
きゅうりりんご
バナナ===左回転==>きゅうり
アップルバナナ

スタックは通常、コンピュータではメモリセルのブロックで表され、「下部」は固定位置にあり、スタックポインタはスタック内の現在の「上部」セルのアドレスを保持します。スタックが実際に低いメモリアドレスに向かって成長するか、より高いメモリアドレスに向かって成長するかに関係なく、上部と下部の用語が使用されます。

アイテムをスタックにプッシュすると、スタックポインターがアイテムのサイズによって調整され(スタックがメモリ内で成長する方向に応じて、デクリメントまたはインクリメントのいずれか)、次のセルをポイントし、新しい最上位のアイテムをにコピーします。スタック領域。正確な実装に応じて、プッシュ操作の最後に、スタックポインターがスタック内の次の未使用の場所を指している場合もあれば、スタックの最上位のアイテムを指している場合もあります。スタックが現在の最上位のアイテムを指している場合、新しいアイテムがスタックにプッシュされる前に、スタックポインターが更新されます。スタック内で次に使用可能な場所を指している場合は、新しいアイテムがスタックにプッシュさ れた後に更新されます。

スタックをポップすることは、単にプッシュの逆です。スタックの最上位の項目が削除され、プッシュ操作で使用された順序とは逆の順序でスタックポインタが更新されます。

メインメモリにスタック

x86Z80、6502を含む多くのCISCタイプのCPU設計には、専用レジスタを暗黙的に更新する専用の呼び出し、リターン、プッシュ、およびポップ命令を備えたコールスタックスタックポインタとして使用する専用レジスタがあり、コード密度が向上します。PDP-1168000などの一部のCISCプロセッサには、スタックを実装するための特別なアドレッシングモードもあり、通常は半専用のスタックポインタもあります(68000のA7など)。対照的に、ほとんどのRISCCPU設計には専用のスタック命令がないため、必要に応じて、すべてではないにしてもほとんどのレジスタをスタックポインタとして使用できます。

レジスタまたは専用メモリにスタックする

x87 浮動小数点アーキテクチャは、スタックとして編成されたレジスタのセットの 例であり、個々のレジスタ(現在のトップに対して)への直接アクセスも可能です。一般的なスタックベースのマシンと同様に、暗黙の引数としてスタックの最上位を使用すると、バス帯域幅コードキャッシュを適切に使用して、マシンコードのフットプリントを小さくすることができますが、プロセッサで可能な最適化の種類を防ぐこともできます。すべて(2つまたは3つ)のオペランドのレジスタファイルへのランダムアクセス。スタック構造は、レジスタの名前変更を伴うスーパースカラー実装も作成します 投機的実行)は、実装がやや複雑ですが、最新のx87実装で例示されているように、まだ実行可能です。

Sun SPARCAMD Am29000、およびIntel i960はすべて、関数の引数と戻り値に低速のメインメモリを使用しないようにするための別の戦略として、レジスタスタック内で レジスタウィンドウを使用するアーキテクチャの例です。

ハードウェアに直接スタックを実装する小さなマイクロプロセッサもいくつかあり、一部のマイクロコントローラには、直接アクセスできない固定深度のスタックがあります。例としては、PICマイクロコントローラーComputer Cowboys MuP21Harris RTXライン、NovixNC4016などがあり ます多くのスタックベースのマイクロプロセッサがマイクロコードレベルでプログラミング言語Forthを実装するために使用されました。スタックは、多くのメインフレームミニコンピューターの基盤としても使用されましたそのようなマシンはスタックマシンと呼ばれ、最も有名なのはバロウズB5000

スタックのアプリケーション

式の評価と構文解析

逆ポーランド記法を採用している電卓は、スタック構造を使用して値を保持します。式は、接頭辞、接尾辞、または中置記法で表すことができ、ある形式から別の形式への変換は、スタックを使用して実行できます。多くのコンパイラは、低レベルのコードに変換する前に、式やプログラムブロックなどの構文を解析するためにスタックを使用します。ほとんどのプログラミング言語は文脈自由言語であり、スタックベースのマシンで解析できます。

バックトラック

スタックのもう1つの重要なアプリケーションは、バックトラックです。迷路の中で正しい道を見つける簡単な例を考えてみましょう。出発地から目的地まで、一連のポイントがあります。ある点から始めます。最終目的地に到達するには、いくつかのパスがあります。ランダムなパスを選択するとします。ある道をたどった後、私たちが選んだ道が間違っていることに気づきました。したがって、そのパスの最初に戻ることができる方法を見つける必要があります。これは、スタックを使用して実行できます。スタックの助けを借りて、私たちは到達したポイントを覚えています。これは、そのポイントをスタックにプッシュすることによって行われます。間違ったパスにたどり着いた場合は、スタックから最後のポイントをポップして、最後のポイントに戻り、正しいパスを見つけるための探索を続けることができます。これはバックトラッキングと呼ばれます。

バックトラッキングアルゴリズムの典型的な例は、深さ優先探索です。これは、指定された開始頂点から到達できるグラフのすべての頂点を検索します。バックトラッキングの他のアプリケーションには、最適化問題の潜在的な解決策を表すスペースを検索することが含まれます。分枝限定法は、そのような空間で考えられるすべての解決策を徹底的に検索することなく、そのようなバックトラック検索を実行するための手法です。

コンパイル時のメモリ管理

多くのプログラミング言語スタック指向です。つまり、スタックから引数を取得し、戻り値をスタックに戻すこととして、最も基本的な操作(2つの数値の加算、文字の出力)を定義します。たとえば、PostScriptにはリターンスタックとオペランドスタックがあり、グラフィックス状態スタックとディクショナリスタックもあります。pコードマシンJava仮想マシンなど、多くの仮想マシンもスタック指向です。

ほとんどすべての呼び出し規約‍—‌サブルーチンがパラメータを受け取り、結果を返す方法‍—‌特別なスタック(「呼び出しスタック」)を使用して、呼び出された関数のコンテキストに切り替えるために、プロシージャ/関数の呼び出しとネストに関する情報を保持します呼び出しが終了したら、呼び出し元の関数に復元します。関数は、呼び出し元と呼び出し先の間のランタイムプロトコルに従って、引数と戻り値をスタックに保存します。スタックは、ネストされた関数呼び出しまたは再帰的な関数呼び出しをサポートするための重要な方法ですこのタイプのスタックは、CALLおよびRETURNステートメント(またはそれらに相当するもの)をサポートするためにコンパイラーによって暗黙的に使用され、プログラマーによって直接操作されることはありません。

一部のプログラミング言語は、スタックを使用して、プロシージャに対してローカルなデータを格納します。ローカルデータ項目用のスペースは、プロシージャが開始されるとスタックから割り当てられ、プロシージャが終了すると割り当てが解除されます。Cプログラミング言語は通常、この方法で実装されますデータ呼び出しとプロシージャ呼び出しの両方に同じスタックを使用すると、セキュリティに重大な影響があり(以下を参照)、プログラムに重大なセキュリティバグが発生するのを防ぐためにプログラマが注意する必要があります。

効率的なアルゴリズム

いくつかのアルゴリズムは、情報を整理するための主要なデータ構造としてスタック(ほとんどのプログラミング言語の通常の関数呼び出しスタックとは別)を使用します。これらには以下が含まれます:

  • グラハムスキャン、点の2次元システムの凸包のアルゴリズム。入力のサブセットの凸包はスタックに保持されます。これは、新しい点が船体に追加されたときに境界の凹を見つけて削除するために使用されます。[18]
  • 単調行列の行の最小値を見つけるためのSMAWKアルゴリズムの一部は、グラハムスキャンと同様の方法でスタックを使用します。[19]
  • すべての最も近い小さい値、配列内の各数値について、それよりも小さい最も近い先行する数値を見つける問題。この問題の1つのアルゴリズムは、スタックを使用して、最も近い小さい値の候補のコレクションを維持します。配列内の位置ごとに、スタックの上部に小さい値が見つかるまでスタックがポップされ、新しい位置の値がスタックにプッシュされます。[20]
  • 最近傍連鎖アルゴリズムクラスターのスタックを維持することに基づく凝集型階層的クラスタリングの方法であり、各クラスターは、スタック上の前任者の最近傍です。このメソッドが相互に最も近いクラスターのペアを見つけると、それらはポップされてマージされます。[21]

セキュリティ

一部のコンピューティング環境では、セキュリティ違反や攻撃に対して脆弱になる可能性のある方法でスタックを使用します。このような環境で作業するプログラマーは、これらの実装の落とし穴を避けるために特別な注意を払う必要があります。

たとえば、一部のプログラミング言語は、共通スタックを使用して、呼び出されたプロシージャにローカルなデータと、プロシージャが呼び出し元に戻ることを可能にするリンク情報の両方を格納します。これは、プログラムが、プロシージャ呼び出しの重要なリターンアドレスを含む同じスタックにデータを出し入れすることを意味します。データがスタック上の間違った場所に移動された場合、または特大のデータ項目がそれを含むのに十分な大きさではないスタックの場所に移動された場合、プロシージャ呼び出しの戻り情報が破損し、プログラムが失敗する可能性があります。

悪意のある当事者は、入力の長さをチェックしないプログラムに特大のデータ入力を提供することにより、このタイプの実装を利用するスタックスマッシング攻撃を試みる可能性があります。このようなプログラムは、データ全体をスタック上の場所にコピーする場合があり、そうすることで、それを呼び出したプロシージャのリターンアドレスを変更する場合があります。攻撃者は、現在のプロシージャのリターンアドレスがリセットされて、スタック自体内(および攻撃者によって提供されたデータ内)の領域を指すように、そのようなプログラムに提供できる特定のタイプのデータを見つけるために実験することができます。これには、不正な操作を実行する命令が含まれています。

このタイプの攻撃は、バッファオーバーフロー攻撃のバリエーションであり、ソフトウェアのセキュリティ違反の非常に頻繁な原因です。これは主に、最も一般的なコンパイラの一部がデータ呼び出しとプロシージャ呼び出しの両方に共有スタックを使用し、データ項目。多くの場合、プログラマーはデータアイテムのサイズを確認するコードを記述せず、サイズが大きすぎるまたは小さすぎるデータアイテムがスタックにコピーされると、セキュリティ違反が発生する可能性があります。

も参照してください

参考文献

  1. ^ 対照的に、単純なQUEUEはFIFOを操作します(先入れ先出し
  2. ^ a b コルメン、トーマスH .; レイザーソン、チャールズE。; リベスト、ロナルドL。; スタイン、クリフォード(2009)[1990]。アルゴリズム入門(第3版)。MITPressとMcGraw-Hill。ISBN 0-262-03384-4
  3. ^ チューリング、アラン・マシソン(1946-03-19)[1945]、自動計算エンジン(ACE)の数学部門での開発の提案(注:1946-03-19に国立物理研究所(英国)の実行委員会の前に提示されました。)
  4. ^ カーペンター、ブライアン・エドワード; ドラン、ロバート・ウィリアム(1977-01-01)[1975年10月]。「他のチューリングマシン」コンピュータジャーナル20(3):269–279。土井10.1093 / comjnl /20.3.269(11ページ)
  5. ^ サメルソン、クラウス(1957)[1955]。ドイツ、ドレスデンのInternationalesKolloquiumüberProblemederRechentechnikで執筆。Probleme der Programmierungstechnik(ドイツ語)。ベルリン、ドイツ:VEB Deutscher Verlag derWissenschaftenpp。61–68。(注:この論文は1955年に最初に発表されました。番号スタック(Zahlenkeller)について説明していますが、線形補助メモリ(linearer Hilfsspeicher)と名付けています。)
  6. ^ a b Fothe、Michael; ウィルケ、トーマス編 (2015)。Keller、Stack undautomatischesGedächtnis– eine Struktur mit Potenzial(PDF)(Tagungsband zum Kolloquium 14. 2014年11月イエナ)。GIシリーズ:情報学(LNI)の講義ノート–テーマ(ドイツ語)。T-7。ドイツ、ボン:GesellschaftfürInformatik(GI)/KöllenDruck+ Verlag GmbH ISBN  978-3-88579-426-42020-04-12のオリジナルからアーカイブ (PDF)2020年4月12日取得(77ページ)
  7. ^ バウアー、フリードリッヒ・ルートヴィヒ; サメルソン、クラウス(1957-03-30)。"Verfahren zur automatischen Verarbeitung von kodierten DatenundRechenmaschinezurAusübungdesVerfahrens"(ドイツ語)。ドイツ、ミュンヘン:DeutschesPatentamt。DE-PS1094019 2010年10月1日取得
  8. ^ バウアー、フリードリッヒ・ルートヴィヒ; グース、ゲルハルト(1982)。Informatik –EineeinführendeÜbersicht(ドイツ語)。パート1(3版)。ベルリン:Springer-Verlagp。222. ISBN 3-540-11722-9DieBezeichnung'Keller'hierfürwurdevonBauerund Samelson in einer deutschen Patentanmeldungvom30.März1957eingeführt。
  9. ^ サメルソン、クラウス; バウアー、フリードリッヒ・ルートヴィヒ(1959)。「SequentielleFormelübersetzung」[シーケンシャルフォーミュラ翻訳]。Elektronische Rechenanlagen(ドイツ語)。1(4):176–182。
  10. ^ サメルソン、クラウス; バウアー、フリードリッヒ・ルートヴィヒ(1960)「シーケンシャルフォーミュラトランスレーション」。ACMの通信3(2):76–83。土井10.1145 /366959.366968S2CID16646147_ 
  11. ^ 「IEEE-コンピューター-パイオニア-プライス-バウアー、フリードリッヒL.」ミュンヘン工科大学、コンピュータサイエンス学部。1989-01-01。2017年11月7日にオリジナルからアーカイブされました。
  12. ^ ハンブリン、チャールズレオナルド(1957年5月)。数学表記(PDF) (タイプスクリプト)に基づくアドレスレスコーディングスキームNSW工科大学pp。121-1–121-12。2020-04-12のオリジナルからアーカイブ(PDF)2020年4月12日取得 (12ページ)
  13. ^ Kämmerer、Wilhelm(1958)。Ziffern-Rechenautomat mit Programmierung nach mathematischem Formelbild(ハビリテーション論文)(ドイツ語)。Friedrich-Schiller-Universität、イエナ、ドイツ。
  14. ^ Kämmerer、Wilhelm(1960)。ZiffernrechenautomatenElektronisches Rechnen und Regeln(ドイツ語)。1.ベルリン、ドイツ:Akademie-Verlag
  15. ^ ボール、ジョンA.(1978)。RPN計算機のアルゴリズム(1版)。米国マサチューセッツ州ケンブリッジ:Wiley-InterscienceJohn Wiley&Sons、Inc。ISBN  978-0-471-03070-6
  16. ^ ゴドセ、アトゥルP。; ゴドセ、ディーパリA.(2010-01-01)。コンピュータアーキテクチャ技術出版物。pp。1–56。ISBN 978-8-18431534-92015年1月30日取得
  17. ^ Horowitz、Ellis:「Pascalのデータ構造の基礎」、67ページ。ComputerSciencePress、1984年
  18. ^ グラハム、RL(1972)。有限平面集合の凸包を決定するための効率的なアルゴリズム情報処理レター1、132-133
  19. ^ Aggarwal、Alok; クラーヴェ、マリアM。; モラン、シュロモ; ショー、ピーター; Wilber、Robert(1987)、「行列検索アルゴリズムの幾何学的アプリケーション」、Algorithmica2(1–4):195–208、doi10.1007 / BF01840359MR 0895444S2CID 7932878  
  20. ^ バークマン、オメル; シーバー、バルーク; Vishkin、Uzi(1993)、「すべての最も近い小さい値の検出に基づく最適な二重対数並列アルゴリズム」、Journal of Algorithms14(3):344–37​​0、CiteSeerX 10.1.1.55.5669doi10.1006 / jagm.1993.1018 
  21. ^ Murtagh、Fionn(1983)、「階層的クラスタリングアルゴリズムの最近の進歩の調査」(PDF)The Computer Journal26(4):354–359、doi10.1093 / comjnl / 26.4.354

さらに読む

外部リンク