Chapter 1. Basic Concepts

1. overview : system life cycle (시스템 생명 주기)

1. Requirements

2. Analysis

3. Design

4. Refinement and coding

5. Verification
   - Correctness proofs
   - Testing
   - Error removal
   

2. Object-oriented Design

1. 알고리즘적 분해와 객체지향적인 분해

2. Definition and Concepts of Object-Ooriented Programming

1. Object(객체) : 계산을 수행하고 상태를 갖는 개체
   ⇒ 데이터와 절차적 요소의 결합으로 볼 수 있음

2. Object-oriented programming
   (1) object --- 객체의 기본 구성 단위
   (2) object는 어떤 class 또는 type의 instance
   (3) class는 상속(inheritance) 관계에 의해 서로 연관

3. Object-oriented language
   (1) 객체를 지원
   (2) 모든 객체는 클래스에 속한다
   (3) 상속을 지원

3. Developments of Programming languages , History of C++

1. 1st Generation : FORTRAN - 수식을 계산

2. 2nd Generation : Pascal, C - 알고리즘을 효과적으로 표현

3. 3rd Generation : Modula - 추상 데이터 타입 도입

4. 4th Generation : Smalltalk, Objective-C, C++ - 상속을 이용하여 추상 데이터 타입간의 관계 표현

5. C언어가 널리 사용되고 있는 이유
   (1) 효율성 : 하드웨어를 더 활용 가능 / (2) 유연성 : 응용 분야의 문제 풀기 위해
   / (3) 가용성 : C컴파일러는 거의 모든 컴퓨터에 존재
   

3. Data Abstraction and Encapsulation

1. abstraction

1. data abstraction : 데이터 객체의 specification과 implementation 분리

2. 무엇을 하는지, 어떻게 수행하는 지를 구별 / 동작이 어떻게 구현되어있는지 알 수 없음

2. encapsulation

1. data encapsulation : 외부로부터 데이터 객체의 자세한 구현을 감춤

2. 내부 표현은 사용자로부터 감추어져 있음.

3. data type : collection of objects and set of operations that act on those objects.
   (객체와 객체에 대해 수행할 수 있는 연산 집합의 모음)

4. abstract data type(ADT) : data type that is organized in such a way that the specification of the objects and the specification of the operations on the objects is seperated from the representation of the objects and the implementation of the operations.
   (객체에 대한 정의와, 객체의 표현 및 연산의 구현이 연산의 정의와 분리되어 구성)

1. specification of operation of ADT is differ from implementation of operations
   - specification consists of the name of funcs, type of arg/result
   - 동작은 서술하나, 실제 구현의 디테일은 나타내지 않음
   - imelemtation independent

5. (참고)

6. 
   

4. Algorithm Specification

1. Introduction

1. Definition (정의)
   (1) input / (2) output / (3) definiteness / (4) finiteness / (5) effectiveness
   ( 입력 / 출력 / 명확성 / 한계성 / 효율성)

2. functions … (책참고)
   selection sort / swap func / search sorted list / compare two integer / searching ordered list

2. recursive algorithm

1. direct recursion / indirect recursion

2. examples...
   binary search / permutations
   

5. Data Abstraction

1. data type : collection of objects and set of operations that act on those objects.
   (객체와 객체에 대해 수행할 수 있는 연산 집합의 모음)

2. abstract data type(ADT) : data type that is organized in such a way that the specification of the objects and the specification of the operations on the objects is seperated from the representation of the objects and the implementation of the operations.
   (객체에 대한 정의와, 객체의 표현 및 연산의 구현이 연산의 정의와 분리되어 구성)

1. specification of operation of ADT is differ from implementation of operations
   - specification consists of the name of funcs, type of arg/result
   - 동작은 서술하나, 실제 구현의 디테일은 나타내지 않음
   - imelemtation independent

2. data type에 대한 functions을 분류 가능
   - creator/constructor :생성자
   - transformers : 값 변경
   - observers/reporters : 값 보고
   

6. Performance analysis
   (참고링크 :http://algorithm.cs.nthu.edu.tw/~ds/material/Complexity.ppt)

1. space complexity : amount of memory that it needs to run to completion.

1. Fixed space requirements
   - 요구되는 공간이 입력과 출력 크기와 무관.
   - instruction space(코드 저장 공간)
   - 단순한 변수
   - 고정크기의 구조화된 변수 (구조체)
   - 상수

2. Variable space requirements
   - 특정 변수의 크기에 따라 변경되는 구조화된 변수에 필요
   - 함수에서 instance I의 특성에 따라 주어짐
     → 특성 : I와 연계된 입출력의 수,크기, 값 등이 주로 포함
   - Sp(I): variable space requirement of program P working on an I
                      S(P) = c+ Sp(I)
       - c : fixed space requirements
   

2. time complexity : amount of computer time that it needs to run to completion

1. T(P)=caADD(n)+csSUB(n)+clLDA(n)+cstSTA(n)
   c는 상수, addtions / substractions / loads / stores (n) 은 횟수

2. program step : syntactically or semantically meaningful program segment whose execution time is independent of the instancee characteristics.
   

3. Asymptotic Notation(O,,)

1. O
   정수 (integers) 또는 복소수(real numbers)를 복소수로 변환하는 함수 f, g가 있다. 만약  |f(x)| ≤ C|g(x)|, x > k 를 만족시키는 상수 C와 k가 존재할 때, f(x)는 O(g(x)) 라고 한다.

2. 
   정수 (integers) 또는 복소수(real numbers)를 복소수로 변환하는 함수 f, g가 있다.만약  |f(x)| ≥ C|g(x)|, x > k 를 만족시키는 상수 C > 0와 k가 있을 때, f(x)는 Ω(g(x)) 라고 한다.

3. 
   f(x) 가 동시에 O(g(x)) 이고 Ω(g(x)) 일 때 f(x)는 Θ(g(x)) 라고 한다.
   

O(1) constant

O(log n) logarithmamic

O([log n]^c) polylogarithmic

O(n) linear

O(n · log n) sometimes called "linearithmic"

O(n^2) quadratic

O(n^c) polynomial, sometimes "geometric"

O(c^n) exponential

O(n!) factorial

O(n^n)   ?

7. Performance Measurement

1. Clocking

2. Generating Test Data