Terminology Summary 용어 정리 Set (집합) Set (집합) - Element(원소)들의 모임으로, Membership(소속성)을 제외한 어떤 구조도 갖지 않는다. Set Operation (집합 연산) - Intersection(∩, 교집합) - Union(∪, 합집합) - Difference(-, 차집합) Complementation (여집합) \(\bar{S}\) (혹은 \(S^{c}\)) : 집합 \(S\)의 여집합 \(\bar{S} = \{x : x ∈ U, x \notin S\}\) (단, \(U\)는 전체 집합) Empty Set (공집합, \(\varnothing\)) - 아무 원소도 가지지 않은 집합이다. Subset (부분집합) S_{1} ⊆ S_{2} : 집합 S_{..
Logically Equivalent 논리적 동치 - \(P \leftrightarrow Q\) 가 Tautology(항진명제)이면, \(P\), \(Q\)는 "논리적으로 동치"라 표현한다. - "\(P \iff Q\)" 또는 "\(P \equiv Q\)"라 표기한다. ex) \(\neg (P \lor Q) \iff \neg P \land \neg Q \qquad (De Morgan`s Laws)\) ex) \(P \to Q \iff \neg P \lor Q\) * 논리적 동치 관계의 증명 1. 진리표를 이용하는 방법 : 변수의 개수가 증가함에 따라 결과가 기하급수적으로 증가하는 문제가 있다. 2. 기증명된 논리적 동치관계를 이용해서 증명하는 방법 Sample QUIZ Q.1 Prove the propo..
Logical Operator 논리 연산자 - 하나의 명제를 논리 연산자를 이용하여 여러 단순 명제로 도출시켜(분할시켜), 여러 단순 명제의 Truth value(진리값)들로 부터 알고자하는 명제의 진리값을 알 수 있다. * Truth Table (진리표) - 명제들의 진리값 간의 관계를 나타내는 표 1. Negation (부정) : \(\neg, ~\) - 현재 진리값의 반대값을 취하게 하는 연산자이다. (NOT연산) \(P\) \(\neg P\) \(T\) \(F\) \(F\) \(T\) 2. Conjunction (논리곱) : \(\land\) - 두 진리값이 동시에 True값인 경우를 제외한 모든 경우에는 False를 도출시키는 연산자이다. (AND 연산) \(P\) \(Q\) \(P \land ..
Proposition 명제 - True나 False중 어느 한 값으로 표현이 가능한 문장 * Propositional Logic (명제 논리) - 내부 구조가 없는 논리 명제에 논리합, 부정 등과 같은 논리 연산을 가하여 구성한 논리 명제들을 다루는 논리체계이다. - H/W설계 시, Gates나 Circuit의 정확한 동작을 정의 및 관리하는 데 이용된다.
Asymptotic Analysis Method (점근적 분석법) - 점화식* 의 점근적 복잡도를 구하는 방법 - 대표적으로 세 가지 방법이 존재 (반복 대치, 추정 후 증명, 마스터 정리) * 점화식 (Recurrence) : 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식 ex) 피보나치 수열 : \(F(n) = F(n-1) + F(n-2)\) ex) 팩토리얼의 함수적 표현 : \(f(n) = n * f(n-1)\) 마스터 정리 Master Theorem - 특정 형태의 재귀식에서 바로 결과를 도출하는 방법 - 입력의 크기가 \(n\)인 문제를 풀기 위해 입력의 크기가 \({b \over n}\) 인 문제를 풀고, 나머지 \(f(n)\) 의 오버헤드가 필요한 알고리즘의 점화식을 풀 수 있음 \(T..
Asymptotic Analysis Method (점근적 분석법) - 점화식* 의 점근적 복잡도를 구하는 방법 - 대표적으로 세 가지 방법이 존재 (반복 대치, 추정 후 증명, 마스터 정리) * 점화식 (Recurrence) : 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식 ex) 피보나치 수열 : \(F(n) = F(n-1) + F(n-2)\) ex) 팩토리얼의 함수적 표현 : \(f(n) = n * f(n-1)\) 추정 후 증명 Substitution Method - 점화식의 모양을 보고 점근적 복잡도를 추정한 후, 귀납적으로 증명하여 점근적 시간복잡도(Time Complexity)를 구하는 방법 ex) 점화식 \(T(n) ≤ 2T({n \over 2}) + n\) 의 추정 후 증명법을 통한 풀..
Asymptotic Analysis Method (점근적 분석법) - 점화식* 의 점근적 복잡도를 구하는 방법 - 대표적으로 세 가지 방법이 존재 (반복 대치, 추정 후 증명, 마스터 정리) * 점화식 (Recurrence) : 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식 ex) 피보나치 수열 : \(F(n) = F(n-1) + F(n-2)\) ex) 팩토리얼의 함수적 표현 : \(F(n) = n * F(n-1)\) 반복 대치 - 점화식을 반복하여 대치해가면서 점화식을 전체적으로 나열시킨 후에 점근적 시간복잡도(Time Complexity)를 구하는 방법 ex) 팩토리얼값(n!)을 구하는 알고리즘의 시간복잡도 분석과정 Factorial(n){ if (n = 1) return 1; // 1 else..
