skyjump's blog

Spooling
 

O-notation
Upper bound. 이보다 커질 수 없다.

Ω-notation
lower bound. 이보다 작아질 수 없다.

Θ-notation
tight bound. upper bound도 될 수 있고 lower bound도 될 수 있다.




ο-notation (small O notation)
tight 하지 않은 upper bound

ω-notation (small Ω notation)
tight 하지 않은 lower bound

함수의 비교
 

Duality
Boolean Algebra의 중요한 속성.
하나를 보여주면 다른 하나도 보여줄 수 있다.
예를 들면 헌팅턴의 공준, 공리에서  x+y = y+x 임을 보이면 x*y = y*x도 성립한다.
즉 binary operators( +, * )나 identity elements(+일 때는 0, *일 때 1)을 바꿈으로써 하나가 성립하면 다른 하나도 성립한다.

Boolean function
Ex) F1 = x + y'z
Truth tables로 값을 찾을 수 있다.
Logic gate로 구현할 수 있다.

Complement of Function.
F'은 F의 값이 0인 경우가 1이다.
드모르간 (DeMorgan) 법칙을 이용해 구할 수 있다.
또는 dual을 구하고 각 문자에 complement를 하면 된다.

Minterms and Maxterms

그림에서 보면 minterms 와 maxterms는 complement 관계에 있다.

Truth table로 부터 함수의 min terms를 구할 수 있다.
그리고 함수 F의 함수값이 0이 되는 부분을 이용하여 F'의 min terms도 구할 수 있고
이 함수를 다시 complement하면 본래의 F로 돌아가지만 max terms으로 표현된다.
따라서 min term을 알면 max terms도 안다. (complement 관계!)

Boolean expressions
52쪽 참고

Digital logic gate
54쪽 참고
 

소프트웨어는 고객이 원하는 기능을 하도록 해야 한다.
 

Elimination이 성공할 경우
pivot이 0이 아니다.
pivot : (i,i) 위치의 값

Elimination이 실패할 경우
pivot 위치에 0이 나올 경우

Back-substitution
Elimination이 끝난 후, 끝부분 부터 답을 찾아나가는 것.
예) 1w = 2 부터 위로 올라가면서 w, v, u를 구한다.
2u + v + w = 5
    -8v - 2w = -12
            1w = 2

Elimination Matrix
Eij (i 번째 row, j번째 column)의 값(- l)은 i번째 row * l  에서 j번째 row를 빼라는 의미

Matrix multiplication