1

私はCSのコースを取っていますが、率直に言って抽象データ型代数に関して講師が何を話しているのか分かりません。これは私が Web 上ですぐに解決策を見つけることができたものではなく、コミュニティの誰かが問題についてより深い洞察や理解を持っているのではないかと思いました。

スタック：

isempty(createstack()) = true
isempty(push(n, s)) = false 
top(push(n, s)) = n 
pop(push(n, s)) = s

列：

isempty(createqueue()) = true
isempty(add(n, q)) = false
front(add(n, q)) = n, if q is empty
front(add(n, q)) = front(q), if q is not empty removefront(add(n, q)) = q,
if q is empty      removefront(add(n, q)) = add(n, removefront(q)),
if q is not empty

表記は確かに少し奇妙です...上記は実際にはどういう意味ですか〜キューとスタックの一般的な動作を先入れ先出しと先入れ後出しとして理解しています。

4

1 に答える 1

2

抽象データ型を使用して、実装を指定せずに型の動作を記述することができます。タイプは、どのような条件が常に維持されなければならないかを説明する一連の公理またはルールとして定義します。Djikstraはかつて、ADT はキューの動作を記述するための非常に便利なツールであると言っていました... しかし、まあ、Djikstra の知られている超批判的なユーモアはさておき、ADT の少なくとも 1 つの実際のアプリケーションを考えることができます:アサーション.

アサーションを使用すると、(自然言語のドキュメントではなく) 形式的でコンパイル可能で実行可能な言語で型がどのように機能するかを指定できます。コントラクト手法による設計では、ソース言語または何らかの形式のメタ言語でメソッド (一般に型に対する操作) の実行前または実行後に保持する必要がある述語として記述されることがよくあります。アサーションをサポートするフレームワーク ( CodeContractsなど).NET の場合) すべての述語が必要なときに保持されていることを自動チェックします。このようにして、自分のコードがアサーションの 1 つに違反している場合、バグがあることがわかります。したがって、ある意味では、テストケースを指定することによって (これは経験的なテスト方法論になります)、型が適合しなければならない事前条件、事後条件、および不変条件を指定することによって (これは、理論的なテスト方法）。

主流のソフトウェア開発では使用されていませんが、私の知る限り、(アサーションのチェックはパフォーマンス ヒットになる可能性があります) テスト中に使用できます。

純粋に理論的な観点から言えば、ADT はまさにそれであり、特定の実装に関係なく、型の動作について推論できるようにする抽象化です。形式主義が好きなら (私のように)、開発者に定理のリストを提供してもらうことは、開発者のコ​​ードが何をすべきかを説明するあいまいなせせらぎよりも優れていることはありません。

一方、論理プログラミングや関数型プログラミングなどの一部の代替プログラミング パラダイム (オブジェクト指向の代替としての代替であり、二次的なものではなく、重要でないものなど) は、型構造の ADT に基づいています。非常に興味深い例は、Haskell言語です。型、継承、ポリモーフィズムの穴の新しい画像を提供します。

于 2013-02-14T16:24:13.253 に答える