抽象データ型のソースを表示

{{参照方法|date=2022年5月}}

'''抽象データ型'''（ちゅうしょうデータがた、{{lang-en-short|abstract data type}}、ADT）とは、データ構造とその操作手続きを定義した[[データ型]]、またはデータ抽象<ref group="注釈">データ抽象（{{lang-en-short|data abstraction}}）とは、データ型の詳細定義とその操作に関する手続きを情報の局所性が高まるようにソースコード中の一カ所にまとめて記述するための記法のことを言う。情報が一カ所に局所的にまとめて記載されているため、非公開（private）部分の変更であればその定義部分の詳細を変更するだけでソースコード全体の修正が完了する。

データ型の詳細定義とその操作手続きの局所的記述を実現する方法は複数あり、抽象データ型はその一例である。</ref>の方法の1つ。通常のデータ型であれば変数宣言で変数に束縛されるものは値であるが、抽象データ型の世界において値に相当するものはデータ構造とその操作<ref group="注釈">言語に応じて名称が異なり、[[C++]]であればメンバ関数（member function）、[[Java]]であればメソッド（method）と呼ばれる</ref>のまとまり<ref group="注釈">データ型の値に相当するこのまとまりのことを抽象データ型の実体（インスタンス , instance）と呼ぶ。</ref>である。

抽象データ型を用いない場合、データ構造またはデータの操作手続きのアルゴリズムの変更を行うとソースコード中にその変更部分が散在してしまい規模によっては修正困難となるが、データとその操作がひとまとめに記載されることになる抽象データ型においては、型の定義における実装部分を変更するだけで修正が完了する。

== 概要 ==
1960年代の[[構造化プログラミング]]の時点で既に、（よく知られている）段階的詳細化といった手法や[[制御構造]]の利用の励行などの他、データ構造とコードを連携させ、データ構造の変更を行うと変更部分がソースコード中に散在してしまうというそれ以前のプログラミングにおける問題点への対処にもなる、データ抽象に関する議論は現れている（『構造化プログラミング』（日本版はサイエンス社、1975年）の、全体の約半分は[[エドガー・ダイクストラ|ダイクストラ]]による考察だが、残り約半分は[[アントニー・ホーア|ホーア]]と[[オーレ＝ヨハン・ダール|ダール]]（[[Simula]]の設計者）によるデータ論である）。抽象データ型はデータ抽象の具体的手法として1974年に[[バーバラ・リスコフ]]の提案した言語[[CLU]]において提案された<!-- 順番が変わっても把握できるように修正した上でコメントアウトしてください <ref>参考文献５</ref> -->。

==インタフェースと実装の分離==
プログラムが実装されたとき、抽象データ型は実装を隠蔽するインタフェースを表す。実装は将来において変更されうるので、抽象データ型のユーザーは実装ではなくインタフェースに関心がある。

抽象データ型の強みはユーザーから実装が隠蔽されていることである。インタフェースのみが公開されるのである。このことは、抽象データ型がいろいろな方法で実装されうることを意味するが、インタフェースに忠実な限りユーザープログラムは影響を受けないのである。

例えば、二分探索木抽象データ型はいくつかの方法で実装できる。例えば、[[二分木]]、[[AVL木]]、[[赤黒木]]、配列である。しかし実装に関わらず二分探索木は「挿入」「削除」「検索」といった同じ操作が可能である。

== 抽象データ構造 ==
'''抽象データ構造'''とは、実際の[[データ構造]]による実装に関わらず、操作の集合とその[[計算複雑性理論|計算量]]により定義されるデータのための抽象的な領域のことである。

具体的なデータ構造の選択がアルゴリズムの効率的な実装にとって重要である一方、抽象データ構造の選択は効率的なアルゴリズムの設計とその計算量の推定にとって極めて重要である。

この概念はプログラミング言語の理論で用いられる抽象データ型の概念に非常に近い。多くの抽象データ構造や抽象データ型の名前は具体的なデータ構造の名前と一致する。

==具体例==
===抽象データ型としての有理数===
[[有理数]]は計算機においてはそのまま扱うことはできない。有理数の抽象データ型は以下のように定義できる。

'''コンストラクタ''': 2つの整数 <math>a</math>、<math>b</math> を用いて有理数の抽象データ型のインスタンスを作成する。ここで <math>a</math> は分子で <math>b</math> は分母である。

'''関数''': 加算,減算,乗算,除算,指数計算,比較,約分,実数への変換

完全な記述にするためには、それぞれの関数はデータに言及して記述されるべきである。例えば、有理数<math>a/b</math>と<math>c/d</math>を乗算するときには結果は<math>ac/bd</math>と定義される。通常は入力、出力、実行前条件、実行後条件、抽象データ型に対する仮定も記述される。

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}

== 参考文献 ==
* {{Cite book |和書| title=ソフトウェア工学実践の基礎 －分析・設計・プログラミング | author=落水 浩一郎 | year=1993 | publisher=日科技連出版社 | ref=落水(1993) }}
* {{Cite book |和書| title=ずっと受けたかったソフトウェア設計の授業 | author=飯泉 純子, 大槻 繁 |url=https://books.google.co.jp/books?id=gJhtVWzM4BsC&printsec=frontcover&hl=ja&sa=X&ei=Z4ubUf_NL43mkgWD1YGoDQ&ved=0CDwQ6AEwAA*v=onepage&q&f=false | publisher=翔泳社}}
* {{citation | author=D.L.Parnas | year=1975 | title=Use of the concept of transparency in the design of hierarchically structured systems | url=http://ivizlab.sfu.ca/arya/Papers/SW/TranspDesignHierSys.pdf }}
* {{citation | author=D.L.Parnas | year=1971 | title=Information Distribution Aspects of Design Methodology | url=http://cseweb.ucsd.edu/~wgg/CSE218/Parnas-IFIP71-information-distribution.PDF }}
* {{citation | author=B.H.Liskov, S.N.Zilles | year=1974 | title=Programming with Abstract Data Type | url=http://www.znu.ac.ir/members/afsharchim/lectures/p50-liskov.pdf }}
* {{citation | title=Program Development by Stepwise Refinement | author=Niklaus Wirth | year=1971 | url=http://sunnyday.mit.edu/16.355/wirth-refinement.html | publisher=Communications of the ACM, Vol. 14, No. 4, April 1971, pp. 221-227 }}
* {{citation | title=Program Development by Stepwise Refinement and Related Topics | author=N.Gehani | year=1980 | url=http://www3.alcatel-lucent.com/bstj/vol60-1981/articles/bstj60-3-347.pdf }}
* {{Citation | author=二木 厚吉 | year=1996 | title=代数モデルの基礎 (<特集>ソフトウェア工学の基礎) | url=https://cir.nii.ac.jp/crid/1390282763062713984}}
* {{Citation | author=鳥居 宏次 , 二木 厚吉 , 真野 芳久 | year=1984 | title=プログラミング方法論の展望 | url=https://cir.nii.ac.jp/crid/1050282812855477504}}
* {{Citation | 和書 | author=二木 厚吉、中川 中 | contribution=第４章：抽象データ型とOBJ２ |year=1990 | editor=井田 哲雄、田中 二郎 | title=続 新しいプログラミング・パラダイム | }}

== 関連項目 ==
* [[OBJ]]
* [[ジョセフ・ゴーグエン]]

{{Normdaten}}
{{デフォルトソート:ちゆうしようてえたかた}}
[[Category:抽象データ型|*]]
[[Category:ソフトウェア工学]]
[[Category:ソフトウェア設計]]
[[Category:データ型]]
[[Category:アルゴリズム]]
[[Category:データ構造]]
[[Category:抽象]]
[[Category:型理論]]

[[sv:Datatyp#Abstrakta typer]]