a. 정의
i. 데이터 타입을 추상적*(수학적)으로 정의한 것
1) 추상 = 어떤 물체나 현상의 중요한 특징만을 추출하여 표현하는 것
2) 가장 중요한 추상의 타입
i) 부분으로 나누기(Has-A abstraction) → 요소(component)로 나누어 별개로 생각
ex) A car has-a engine, has-a transmission. A window has-a menu bar.
ii) 전문성으로 나누기(Is-A abstraction) → 일반화(generalization)된 객체로 본다
ex) A car is-a means of transportation. A bicycle is-a wheeled vehicle.
3) Model
i) 예상되는 공식 또는 해법을 만드는 데 사용되는 추상 또는 개념적 객체(오브젝트)
ii) 문제에 대한 추상적인 관점을 정의 & 문제와 관련된 것과 정의하려는 속성(property)에만 집중
iii) ADT는 Model의 일종. 모델에 대한 부분적인 해법(partial solution).
ii. 데이터 연산이 무엇(what)인지는 정의O, 하지만 어떻게(how) 컴퓨터 상에 구현할 것인지는 정의X
→ 구현의 독립: 단지 수행 기능만 함축적으로 나타내므로 표현이나 구현에 대한 자세한 설명 불필요(인터페이스)
1) 연산에 필요한 추상: 무엇(what)이 수행되는지 알지만 어떻게(how) 수행되는지 몰라도 좋다는 것
iii. 제공자: 사용자에게 데이터 객체 이름과 연산자 이름 제공
사용자: 이를 이용하여 실제로 필요한 데이터 객체와 연산자 구현
iv. <객체의 명세 & 객체에 대한 연산의 명세>가 <객체의 표현 & 연산의 구현>으로부터 분리된 데이터 타입
ex) Ada의 package, C++의 class 등
v. 프로그램의 제어보다는 자료에 관심을 두고 자료구조 및 그와 관련된 연산들로 구성된 모듈을 작성
→ 정수나 실수형 같은 하나의 자료형으로 취급
vi. 데이터의 표현이나 연산의 구현은 제외하고 데이터와 연산의 본질에 대한 명세만 정의
b. 속성
i. 추상으로 잘 정의된 개체(entity) 생성
ii. 개체들은 항목들(items)의 자료 구조(data structure)를 정의
ex) 관리자는 이름, 생일, 주민등록번호 등을 가진다.
iii. 자료 구조는 정의된 연산(defined operations)에 의해서만 접근 가능. 즉, 해당 타입의 자료 구조에 접근하는 유일한 방법.
→ 이 연산들의 집합(a set of operations)을 인터페이스라 하고 개체에 의해 밖으로 전달(export)된다.
iv. 위와 같은 속들을 가진 개체를 ADT라 한다.
1) 예제: List
i) List 타입의 객체(instance)에 대한 인터페이스는 인터페이스 정의 파일에 의해 정의된다.
ii) 정의된 연산: insert, get, append, delete, search ... etc
iii) 어플리케이션 영역(domain)은 제공되는 연산들의 어의적 의미(semantic meaning)에 의해 정의된다.
iv) 공리(axioms)와 전제조건(preconditions)들은 다음과 같은 진술을 포함한다
a) 빈 list는 list이다
b) l = (d1, d2, d3, ... dn)을 list라 하자.
그렇다면 l.append(dm)의 결과 l = (d1, d2, d3, ... dn, dm)이 된다.
c) list트의 첫번째 요소(element)는 오직 리스트가 비어있지 않을 때만 삭제될 수 있다.
c. 캡슐화(encapsulation)
i. 데이터와 연산을 결합. 변수들과 함수들을 에워싼다.
ii. ADT의 사용자들로부터 자료와 연산의 세부사항을 지킨다
iii. 복소수(complex number)에 대한 ADT인 Complex를 만들었다면, 잘 알려진 자료형인 정수(integers)처럼 사용 가능
iv. 모듈 방법을 가능하게 한다
v. 자료에 대한 접근 통제
vi. 인터페이스로부터 구현을 분리
vii. 기본형(build-in types)을 확장
d. ADT의 특징
i. 프로그램의 추상화 → 알고리즘 → 구체화 → 프로그램
데이터 타입의 추상화 → 추상 데이터 타입 → 구체화 → 데이터 타입
ii. 객체(instance)의 생성을 가능하게 한다. OOP에서 ADT는 class에 해당.
iii. C언어는 ADT를 명시적으로 구현하는 기법 없지만, ADT의 개념을 갖도록 설계 가능
iv. ADT로 작성된 모듈은 일반 자료형과 같은 방법으로 사용
v. 저급 언어보다 객체지향언어에서 구현하기 더 쉽다
vi. 프로그램 속에 표현될 복잡한 관계를 가진 대량의 데이터 → 추상화 및 단순화 → 문제 해결 방법을 찾기
e. ADT의 조건
i. 자료형과 연산에 대한 정의가 한 곳에서 가능
ii. 자료형과 연산이 하나로 묶인 자료형에 대한 프로그램의 접근 제한할 수 있어야 함
f. ADT의 구현 방법
i. 자료와 그에 관련된 연산들의 기본적인 특성 기술
ii. 이미 존재하는 자료형 이용하여 기술된 내용 구현
iii. 기술 내용과 구현 결과가 일치함을 보여야 함
g. 자료의 추상
i. 문자열, 숫자, 이진트리 등과 같이 연산의 대상이 되는 자료를 추상화
ii. 종류
1) 기본적 추상: 컴퓨터 안에 저장된 자료 값을 추상화
ex) 변수: 자료 값이 저장된 메모리에는 이름을 부여하여 추상화
2) 구조적 추상: 연관된 자료 값의 집합을 추상화
ex) 배열, 레코드 등
3) 단위 추상: 단위 프로그램 전체에 대한 추상화
ex) C++의 class, Ada의 package, Java의 class
h. 공식
i. 객체 지향(Object-Orientation) =
객체(Abstraction)
+ 클래스(ADT & 클래스화(Classification))
+ 상속(재사용
+ 동적 바인딩(Dynamic Binding. 즉, 다형성(Polymorphism), 유연성(Flexibility))
ii. 객체 지향의 발전:
모듈 → 정보 은닉(Information hiding) → 자료 캡슐화 → ADT → 클래스와 객체
i. ADT의 구성 요소
i. 구조 이름
ii. 객체(data, 자료)의 정리
iii. 함수(연산)의 정리
1) 데이터 쿠조는 크게 세 부분으로 나눌 수 있다
표현하려는 데이터 구조 = ( 데이터 구조의 정의영역 집합, 함수의 집합, 공리의 집합 )
Structure = ( Domain, Function, Axiom )
2) S와 D의 관계: S ∈ D
iv. NaturalNumber 추상 데이터 타입 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
ADT NaturalNumber
objects : 0에서 시작해서 컴퓨터상의 최대 정수 값(INT_MAX)까지
순서화된 정수의 부분 범위이다.
functions :
Nat_Number의 모든 원소 x, y와 Boolean의 원소 TURE, FALSE에 대하여,
+, -, <, ==는 일반적인 정수 연산자이다.
NaturalNumber Zero() ::= 0
Boolean IsZero() ::= if(x) return FALSE
else return TRUE
Boolean Equal(x, y) ::= if(x == y) return TRUE
else return FALSE
NaturalNumber Successor(x) ::= if(x == INT_MAX) return x
else return x + 1
NaturalNumber Add(x, y) ::= if((x + y) <= INT_MAX) return x + y
else return INT_MAX
NaturalNumber Subtract(x, y) ::= if(x < y) return 0
else return x - y
end NaturalNumber
|
