검색어 입력폼

계산이론개요

저작시기 2006.01 |등록일 2006.12.30 파워포인트파일MS 파워포인트 (ppt) | 44페이지 | 가격 1,800원

소개글

나머지는 본문 내용을 참조 해주세요

목차

1.목적
2.수학적 개요
3.집합
4.오토마타
5.함수
6.관계
7.반사성Reflexivity
8.대칭성Symmetry
9.전이성Transitivity
10.그래프
11.트리
12.증명기법
13.Example 1.5
14.언어, 문법, 오토마타

본문내용

트리(1/2)
그래프의 한 종류이다.
사이클을 갖지 않고, 루트라 불리는 특별한 하나의 정점을 가지는 유향 그래프
루트root : one distinct vertex
리프들leaves
부모parent
자식child
레벨level
높이height

증명기법(1/2)
Proof by induction(귀납법)
Example 1.5
Example 1.6
Example 1.7
Proof by contradiction(귀류법)

Proof by induction
몇 개의 특정 사례가 참이라는 사실들로부터 여러 문장들이 참임을 추론해 내는 기법
예) 참임을 증명하고자 하는 문장들의 순서열 P1,P2,… 이 있다고 하고 다음이 성립함을 가정
임의의 k(k>=1)에 대해 P1,P2,…,Pk는 참이다.
n>=k인 모든 n에 대해서 P1,P2,…,Pn이 참인 사실이 Pn+1이 참임을 의미하도록 하는 문제
다운로드 맨위로