New World

1. 오토마타 오토마타 : 자동장치, 스스로 움직이는 기계 ex) 컴퓨터 : 유한상태 오토마타 튜링머신 : 인간 사고과정을 구현하는 오토마타, 컴퓨터의 수학적 모델 형식언어 : 프로그래밍 언어들의 일반적인 특성들을 추상화 형식문법 : 프로그래밍 언어의 생성 규칙을 추상화 2. 유한 오토마타 유한 오토마타 결정적 유한 오토마타 방향 그래프 -> 상태 그래프 -> 상태도 -> 상태전이도 상태 그래프 - 상태 : 원 - 전이 : 그래프 - 입력값과 출력값 : 화살표 위에 표시 비결정적 유한 오토마타 3. 마르코프 연쇄 마르코프 연쇄 : 마르코프 성질을 지닌 이산확률과정 - 유한 오토마타의 특수한 형태 - 시간에 따른 상태의 변화를 확률로 표현 이산확률과정 - 𝑿n : 확률변수 - (𝑿𝟏,𝑿𝟐, … ,𝑿𝒏, …..

1. 나눗셈 a, b가 정수, a가 0이 아닐 때, b=ac 를 만족시키는 정수 c가 있다면 a가 b를 나머지 없이 나눈다 => a는 b의 약수(인수), 배수는 a|b로 표현 최대공약수 : d = gcd(a, b)로 표현, 0이 아닌 두 정수 a,b에 대해 d|a, d|b인 최대의 양의 정수 d를 a와 b의 최대 공약수 gcd(a,b) = 1인 경우, a,b는 서로소 베주의 항등식 : 적어도 하나는 0이 아닌 두 정수 a,b가 gcd(a, b) = d라 할 때, ax + by = d를 만족하는 정수 x, y 존재 - a,b가 서로소 => gcd(a,b) = 1 => ∃𝒙, 𝒚 ∈ 𝒁, 𝒂𝒙 + 𝒃𝒚 = 1 유클리드 호제법(알고리즘) - 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 - 두수가 서..

1. 기본 계수 법칙 두 사건 A, B가 일어날 경우의 수가 각각 N(A) = m, N(B) = n일 때, 곱의 법칙 : A, B가 동시에 일어날 경우의 수는 m x n 합의 법칙 : 𝑨 ∩ 𝑩 = ∅일때, A 또는 B가 일어날 경우의 수는 m + n 합집합의 크기 - 유한집합 |𝑨 ∪ 𝑩| = |𝑨| + |𝑩| − |𝑨 ∩ 𝑩| |𝑨 ∪ 𝑩 ∪ 𝑪| = |𝑨| + |𝑩| + |𝑪| − |𝑨 ∩ 𝑩| − |𝑨 ∩ 𝑪| − |𝑩 ∩ 𝑪| + |𝑨 ∩ 𝑩 ∩ 𝑪| - 유한집합 + 서로소 |𝑨 ∪ 𝑩| = |𝑨| + |𝑩| 2. 순열 순열, 중복순열, 원순열 순열 : 순서를 고려 중복순열 : 중복된 원소를 허용하는 순열 𝟎 ≤ 𝒓 ≤ 𝒏을 만족하는 정수 n, r에 대하여, n개의 원소를 갖는 집합에서 순서를 ..

1. 기본사항 트리 : 사이클이 없는 단순 연결 그래프 Trivial Tree : 꼭지점 하나로 구성된 트리 Empty Tree : 꼭지점이 하나도 없는 트리 Forest : 한 개 이상의 트리로 구성된 트리 루트 트리 : 루트라 부르는 노드가 존재하며 나머지 노드들이 서로 분리된 집합으로 나뉘는 트리 트리 -> 루트 트리 (서브트리, 루트 노드) 트리 노드 용어 자식 노드 : A 기준으로 B, C, D A의 차수 : 자식 노드의 수 레벨 : 루트에서 어떤 노드까지의 경로의 길이 부모 노드 : B(C or D) 기준으로 A B(C or D) 의 차수 : max { B(C or D)의 차수 | 𝑵 ∈ 𝑻 } 형제 노드 : B 기준으로 C, D 높이(깊이) : max { N의 레벨 | 𝑵 ∈ 𝑻 } 리프 노..

1. 기본사항 그래프는 꼭지점과 변으로 구성 병렬변 : 두 꼭지점을 연결하는 변이 복수개 루프 : 동일한 꼭지점을 연결하는 변 고립된 꼭지점 : 어떠한 변도 연결 X 꼭지점 동형 : 꼭지점과 변의 이름을 제외하고는 모두 동일한 그래프 방향 그래프 : 변이 방향을 가지는 그래프 무향 그래프 : 변이 방향이 없는 그래프 단순 그래프 : 루프와 병렬 변을 가지지 않는 무향 그래프 𝑮 = 𝑽, 𝑬 , 𝑯 = (𝑽 ′ , 𝑬′) (1) 𝑽 ′ ⊆ 𝑽, 𝑬 ′ ⊆ 𝑬 ⇒ 𝑯를 𝑮의 부분 그래프(subgraph) (2) 𝑽 ′ = 𝑽, 𝑬 ′ ⊆ 𝑬 ⇒ 𝑯를 𝑮의 신장 부분 그래프 (spanning subgraph) 총 차수 : 인접한 변의 개수 진입차수 : 들어오는 변의 개수 진출차수 : 나가는 변의 개수 path..

1. 기본사항 디지털 논리회로 : 디지털 신호로 입력하여 논리연산을 통해 디지털 신호로 출력 AND 게이트 : 논리곱, F = X· Y OR 게이트 : 논리합, F = X + Y NOT 게이트 : 논리부정, F = X' NAND 게이트 : F = 𝑿' + 𝒀' NOR 게이트 : F = X'· Y' XOR 게이트 : 배타적 논리합, F = 𝑿'𝒀 + 𝑿𝒀' XNOR 게이트 : F = 𝑿'𝒀' + 𝑿𝒀 2. 부울대수 부울식 -부울상수 0,1은 부울식 -부울변수 -𝑿, 𝒀가 부울식인 경우, 𝑿 + 𝒀, 𝑿 ∙ 𝒀, 𝑿', (𝑿) 도 부울식 항등법칙 : 같은 값, 𝑿 + 𝟎 = 𝑿 | 𝑿 ∙ 𝟏 = 𝑿 지배법칙 : 더해지거나 곱해지는 값과 같은 값, 𝑿 + 𝟏 = 𝟏 | 𝑿 ∙ 𝟎 = 𝟎 멱등법칙 : 같은 값을..

1. 기본사항 X, Y : 집합 X에서 Y로의 함수 : ∀𝒙 ∈ 𝑿, ∃! 𝒚 ∈ 𝒀, 𝒙, 𝒚 ∈ 𝒇 를 만족하는 𝑿에서 𝒀로의 관계 [ 𝒇 ⊂ 𝑿 × 𝒀 ] X : f의 정의역, Y : f의 공역 y : x의 상 f(x), x : y의 역상 f(x) : f의 치역 상수함수 : 𝒇 ∶ 𝑿 → 𝒀, ∀𝒙 ∈ 𝑿, 𝒇 (𝒙) = 𝒄 (𝒄는 상수) 항등함수 : 𝒇 ∶ 𝑿 → 𝑿, ∀𝒙 ∈ 𝑿, 𝒇 (𝒙) = 𝒙 2. 전사함수, 단사함수, 역함수 전사함수 ∀𝒚 ∈ 𝒀, ∃𝒙 ∈ 𝑿, 𝒇 𝒙 = 𝒚 단사함수 ∀𝒙𝟏, ∀𝒙𝟐 ∈ 𝑿 𝒇 (𝒙𝟏) = 𝒇 (𝒙𝟐) ⇒ 𝒙𝟏 = 𝒙𝟐 𝒙𝟏 ≠ 𝒙𝟐 ⇒ 𝒇 (𝒙𝟏) ≠ 𝒇 (𝒙𝟐) 전단사함수 f 가 전사함수이자 단사함수 역함수 : 전단사함수인 경우 역관계의 함수 3. 함..

1. 기본사항 곱집합 : 모든 순서쌍들의 집합 𝑨 × 𝑩 = 𝒂, 𝒃 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩} 관계 : 𝒙는 𝒚와 𝑹의 관계 (𝒙, 𝒚) ∈ 𝑹 ⇒ ⇒ 𝒙𝑹𝒚로 표기 𝑿 = 𝒀이면 𝑹을 𝑿에서의 관계 2. 관계의 표현 화살표 도표 : 화살표를 그려 나타낸 관계 방향 그래프 ( G = (V, E) ) : 점과 선으로 이루어진 도형 | 방향 , 무향 , 일반 부울 행렬 3. 관계의 성질 반사적 대칭적 추이적 ∀𝒂 ∈ 𝑨 (𝒂, 𝒂) ∈ 𝑹 ∀𝒂, 𝒃 ∈ 𝑨 𝒂, 𝒃 ∈ 𝑹 ⇒ (𝒃, 𝒂) ∈ 𝑹 ∀𝒂, 𝒃, 𝒄 ∈ 𝑨 ((𝒂, 𝒃) ∈ 𝑹 ㅅ (𝒃, 𝒄) ∈ 𝑹) ⇒ (𝒂, 𝒄) ∈ 𝑹 자신의 집합으로 다시 돌아오는 관계 서로가 서로에게 관계 A -> B, B -> C => A -> C 관계 4. 관계의 종..