1. Introduction

▶ purpose & motivation

   - Theory of computation(계산이론)

: computation, algorithm

: definitions

: limitations of computers...

- 컴퓨터에 대한 한계는 어디까지일까? 계산이란?알고리즘?정의?한계?

 ~ 컴퓨터의 능력이 어디까지인지 파악하고자...

- 계산이론은 3가지로 구분

1. 복잡도 이론 - 복잡도 ~ "난이도"

2. 계산능력 이론 - 컴퓨터의 계산 가능한 한계는 어디 ~ " 풀수 있는 것과 없는 것을 구분"

3. 오토마타 이론 - 컴퓨터를 추상화  - ( finite automata / CFG / Turing machines)

    ~ "어떤 방식으로 추상화?" "오토마타 간의 표현능력의 차이?"

▶ mathematical preliminaries - 수학적 사전지식

▷ set (collection... well-defined)

cf. countable VS uncountable

▷ natural number / natural number / rational number / real number

▷ subset

▷ power set 

▷ union / intersection / difference / cartesian product / complement

cf. Sequence

cf. Multiset

▷ binary relation

▷ K-ary function (also binary relation) / domain / range 

▷ functions ; one-to-one(injective) / onto(surjective) / bijection(=injection&surjective)
  # 참고하기 :  

http://ko.wikipedia.org/wiki/%EB%8B%A8%EC%82%AC%ED%95%A8%EC%88%98

▷ equivalence relation ... reflexive / symmetric / transitive 모두 만족
▷ graph G = (V,E)

▷ graph 종류 : directed/undirected , labeled , tree 

// path, cycle, simple path/cycle,  connected...

▷ degree of V

▷ alphabet (finite set) -> symbol -> strings...
▷ alphabet ... Sigma ~ finite sequence of symbol... 

  * length of string / empty string / Reverse / substring / concatenation ...

▷ Language --- a set of strings

    symbol ~ alphabet ~ string ~ language

▷ basic boolean expression 

* implication 은 1->0만 0!

▶ Definitions, Theorems, and Proofs

▷ definition - describe the objects and notions that we use

* Precision ~ essential to any mathematical def

▷ proof - convincing logical argument that a statement is true

▷ theorem - mathematical statement proved trye

▷ Lemmas - 증명과정에 필요한 참인 명제

▷ corollaries - related statements are true

▶ Proof techniques

- Axiom : 증명 과정에서 사용

▷ direct proof

▷ constructive proof

▷ non-constructive proof

▷ proof by contradiction

▷ proof by induction [귀납]

- basic

- induction step

- induction hypothesis

▶ the pigeon hole principle

http://en.wikipedia.org/wiki/Pigeonhole_principle

▷ 

n+1 이상의 개체가 n 개의 상자에 있을때, 최소 하나의 박스는 두개 이상의 개체를 담고있다.