논리회로 (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)) ⇒ ..

[디지털 시스템 회로 설계] 부울 대수와 논리게이트 Boole 대수 Boole 대수는 다음과 같은 공리를 만족하는 2개의 연산자 (+, *)와 원소들의 집합 B에 대해서 정의된 대수적인 구조다. Boole 대수의 특징 (1) 폐쇄: 연산자 +와 *에 대해서 닫혀있다. (2) 단위원: 연산자 +와 *에 대한 단위원은 각각 0와 1이다. x+0=0+x=x x*1=1*x=x (3) 교환법칙: 모든 x,y∈B 에 대해서 x+y=y+x x*y=y*x (4) 분배법칙: 모든 x,y∈B 에 대해서 x*(y+z)=(x*y) +(x*z) x+(y*z)=(x+y)*(x+z) (5) 보수: 모든 원소 x ∈B 에 대하여 x’ ∈B 원소가 존재하여 x+x’=1 x*x’=0 (6) x!=y를 만족하는 x,y∈B 인 원소가 적어..

다차원 배열을 쉽게 처리해주는 NumPy로 데이터 과학의 첫걸음을 떼보세요! 강의 주제 📖 NumPy(넘파이)? 대규모 다차원 배열을 다루는 파이썬 라이브러리, NumPy! 빠른 연산 속도로 대규모 데이터를 처리할 수 있습니다. NumPy는 파이썬 Pandas, SciPy, Matplotlib, Pytorch 등과 함께 데이터 과학과 머신러닝, 딥러닝 운용의 기반이 되는 대표적인 파이썬 라이브러리입니다. 파이썬에서 대규모의 다차원 배열, 그리고 행렬 데이터 처리를 위한 수치 연산을 가능하게 하며 내부적으로 C언어로 구현이 되어있기 때문에 메모리를 최소한으로 유지하고 관리하면서 동시에 연산 속도도 매우 빠른 라이브러리 중 하나입니다. 그렇다면 다차원 배열을 왜 쓰는 것일까요? 다차원 배열(ndarray)?..

[Linear Algebra] #42~45. 특성방정식② · 특수한 행렬들의 고유값 · 대각합과 고유값의 관계 · 기저(basis)

[디지털 시스템 회로 설계] 디지털 시스템과 이진 시스템 디지털 시스템 (Digital System) 이진 형태로 나타나는 정보의 이산적 요소(discrete element)를 처리하는 시스템이다. > 정보의 이산적 요소는 신호 (signal)라고 불리는 물리적 양에 의해 결정된다. > 신호: 전압, 전류 같은 전기적 신호 디지털 시스템은 디지털 모듈을 서로 연결하여 구성한다. > 여러 종류의 디지털 모듈의 동작을 이해하기 위해서는 디지털 논리 회로에 대한 지식이 필요하다. 기수 변환 2진수 -> 10진수 11010.11(2) 1×2^4 + 1×2^3 + 0×2^2 + 1×2^1 + 0×2^0 + 1×2^-1 + 1×2^-2 = 26.75(10) 10진수 -> 2진수 41 41 / 2 .. 1 20 / ..

알고리즘의 수행 시간을 좌우하는 기준은 다양하게 잡을 수 있습니다. 예를 들면 반복문의 반복 횟수, 특정한 행이 수행되는 횟수, 함수의 호출횟수 등이 있죠. 복잡도 분석 예시 Algorithm A Algorithm B Algorithm C sum

[Linear Algebra] #39~41. 수반행렬과 역행렬 · 고유값과 고유벡터 · 특성방정식