논리회로 (logic circuit) 조합회로(combinational circuit) - Boole 함수의 집합을 논리적으로 구현하는 동작을 수행 - 출력이 입력값에 따라 결정됨 순차회로(sequential circuit) - 출력이 저장된 값과 입력 값에 따라 달라짐. - 출력 값이 현재 입력 값 뿐만 아니라 이전 입력값에 따라 달라짐. - 회로의 동작을 입력 값과 저장된 값의 시간순서로 정의할 수 있음. 조합회로 조합회로 • 출력값이 현재의 입력값에 의해 결정됨 • 입력변수와 논리 게이트, 출력 변수들로 구성됨 n개의 입력변수에 대해 2^n개의 2진 입력조합이 가능 각 입력조합에 대하여 하나의 출력 출력 변수 하나를 Boole 함수로 표현할 수 있음. 디지털 시스템을 설계하는데 자주 사용되는 조합회..

선택 정렬 수행시간 최악: (n-1)+(n-2)+···+2+1 = Θ(n2) 평균: (n-1)+(n-2)+···+2+1 = Θ(n2) • 각 루프마다 – 최대 원소를 찾는다 – 최대 원소와 맨 오른쪽 원소를 교환한다 – 맨 오른쪽 원소를 제외한다 • 하나의 원소만 남을 때까지 위의 루프를 반복 # 일반 selectionSort(A[], n) { # A[1 ... n]을 정렬한다 for last

NAND 게이트, NOR 게이트 구현, Exclusive-OR 함수 디지털 회로는 AND나 OR 게이트보다는 대개 NAND와 NOR 게이트를 이용하여 구현됨. NAND와 NOR 게이트는 회로적으로 구성되기 쉽기 때문에 모든 IC 디지털 논리 회로군의 기본 게이트로 사용됨. AND, OR, NOT으로 주어지는 Boole 함수를 등가의 NAND와 NOR로 구성된 논리 도표로 변환할 수 있는 법칙과 과정 개발됨 NAND 회로 NAND 게이트로 된 Boole 함수의 구현을 위해서는 곱의 합 형태로 만들어야 함. 다중 레벨 AND-OR 논리 도표를 NAND 논리 도표로 변환 - 모든 AND 게이트를 AND-invert로 바꾼다. - 모든 OR 게이트를 invert-OR로 바꾼다. - 논리 도표의 모든 버블을 검사..

디지털 논리 게이트와 게이트 레벨 최소화(카르노맵) 디지털 논리 게이트 다중 입력으로의 확장 2진 연산에서 교환법칙과 결합법칙이 성립하면 게이트는 다중 입력으로 확장 가능. OR 연산, and 연산, exclusive-OR 연산 x + y = y + x (x+y)+z=x+(y+z)= x+y+z NAND와 NOR연산자는 결합법칙이 성립하지 않음. (x↓y)↓z≠x↓(y↓z) (x↓y)↓z= [(x+y)'+z]' = (x+y)z'= xz' + yz' x↓(y↓z)= [x+(y+z)'] ' = x'(y+z)= x'y + x'z x↓y↓z= (x+y+z)' x↑y↑z= (xyz)' 양논리와 음논리 2진 신호는 전이하는 동안을 제외하고는 2개의 값 중 하나를 가지며, 한 신호의 값은 1을 다른 것은 0을 나타냄...

점화식 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것이다. 예시 an = an-1 + 2 f(n) = n f(n−1) f(n) = f(n−1) + f(n−2) f(n) = f(n/2) + n 점화식의 점근적 분석 방법 (반복 대치, 추정 후 증명, 마스터 정리) 반복 대치 더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법이다. 기본 개념 T(n) = T(n−1) + c T(1) ≤ c T(n) = T(n−1) + c = (T(n−2) + c) + c = T(n−2) + c + c = (T(n−3) + c) + c + c = T(n−3) + c + c + c … = T(1) + (n −1)c ≤ c + (n −1)c = cn 예시1 T(n) = T(n−1) + n T(1) =..

알고리즘의 점근적 분석이란? 크기가 작은 문제에서는 알고리즘의 효율성이 중요하지 않다. 그래서 비효율적인 알고리즘을 사용해도 무방하다. (오히려 더 빠른 경우도 존재한다) 크기가 충분히 큰 문제에서는 알고리즘의 효율성이 매우 중요하다. 그래서 비효율적인 알고리즘은 치명적으로 작용한다. 이렇게 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라 한다. 표기법에는 Ο, Ω, Θ, ω, ο 가 존재한다. 점근적 상한 ( asymptotic upper bound ) 정의 (lim n->INF) f(n) / g(n) 0, n0 ≥ 0 s.t.∀n ≥ n0, cg(n) ≥ f(n) } f(n) ∈ O(g(n))을 관행적으로 f(n) = O(g(n))이라고 쓴다. 직관적 의미 f(n) = O(g(n)) ⇒ ..