[edit]

1. 대각선논법 간단한 설명 SNU이광근 ¶

// 대각선논법,diagonal_argument 작성중
From: 컴여세 p41

무한이 다 같은 무한이 아니고

자연수,natural_number의 개수보다

실수,real_number의 개수가 훨씬 크다.
또, 자연수의 개수보다 자연수의

부분집합,subset의 개수가 훨씬 더 크다. Georg_Cantor가 처음으로 확인해 준 사실이다.

에 대한 각주:

다음과 같이 확인할 수 있다. 대각선 논법diagonalization 이라고 불린다.

자연수의 부분집합들의 개수가 자연수 개수만큼만 있다면 모순이 된다.
자연수의 부분집합을 자연수로 번호 붙이기에는 늘 부족하게 된다. 다음과 같은 이유 때문이다.

자연수의 부분집합들이 자연수만큼만 있다면 그 집합들을 자연수로 모두 번호 매길 수 있을 것이다.
N1, N2, N3 등등. 이제 N1부터 차례로 살피면서 자연수 집합 X를 만들 수 있는데, 이 집합이 모든 자연수의 부분집합들과는 다르게 된다!
X는 빈집합(

공집합,empty_set)에서 시작해서,
N1에 1이 없으면 X에 1을 넣고, 있으면 X에 넣지 않는다. 다음으로
N2에 2가 없으면 X에 2를 넣고, 있으면 X에 넣지 않는다.
이 과정을 N3, N4 등 모두에 대해서 한다.
그러면, X는 자연수의 부분집합이 분명하지만 N1, N2 등등 모두와 다르다.
자연수로 번호 매긴 것이 다인 줄 알았는데(N1, N2 등등) 그 외에 또 있는 것이다(X).

이런 논법을 대각선 논법이라고 부르는 이유는 X를 만들 때 따지는 (N1, 1), (N2, 2), … 들이
N1, N2 등을 가로축에 쓰고
1, 2 등을 세로축에 쓰면
대각선의 점들에 해당하기 때문이다.

[edit]

2. 선택: 멀티플렉서 multiplexer mux ¶

// 컴여세 pp. 72-73
둘 중 하나를 조건에 따라 결정하는 회로를 만들 수 있다. 즉,
들어오는 입력 x, y 중에서
선택자 z가 0이면 x를, 1이면 y를 선택하는 회로다. '''멀티플렉서multiplexer''라고 한다.
이러한 회로 역시 마찬가지로 입력과 출력을 표로 그리고 원하는 출력이 나오도록 회로를 만들어 주면 된다.

x	y	z	결과
0	0	0	0
0	1	0	0
1	0	0	1
1	1	0	1
0	0	1	0
0	1	1	1
1	0	1	0
1	1	1	1

결과가 1이 되는 xyz의 4가지 경우는 100 110 011 111 이다. 따라서 위의 작동을 하는 디지털 논리회로는 다음과 같다.

x(-y)(-z)+xy(-z)+(-x)yz+xyz

같은 일을 하는 더 간단한 회로로 다시 쓰면 아래와 같이 된다.

x(-z)+yz

[edit]

3. 응답: 디코더 decoder ¶

// 컴여세 pp. 73-74
번호를 부르면 응답하는 디코더decoder도 회로로 만들 수 있다.

출력이 두 개의 선 x, y이다. 선택자(입력) c의 값에 따라 x나 y 중 하나만 1이 되는 회로다.

c	x	y
0	1	0
1	0	1

따라서 논리회로는 x=-c이고 y=c이다.

출력이 네 개의 선 x, y, z, w라고 하자. 이 경우 선택자(입력)는 두 개가 필요하다. 선 c와 d에 따라, 네 개의 출력 선 중에서 하나만 1이 된다.

c	d	x	y	z	w
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

따라서 논리회로는 다음과 같다.

x=(-c)(-d)
y=(-c)d
z=c(-d)
w=cd

[edit]

4. 기억: 플립플롭 flip-flop, 래치 latch ¶

// 컴여세 pp. 74-76

그리고 기억장치도 '그리고', '또는', '아닌'으로 조립할 수 있다.
이건 언뜻 이해하기 어려울 수 있다. 기억은 시간이 관련되어야 하는데, 생각을 조립하는 그 세 개의 접속사에는 시간 개념이 없기 때문이다. (각주: 스위치를 쓰지 않는 자연스런 기억 장치도 있다.

축전기,capacitor라는 장치다. 축전기는 비유하자면 물컵이다. 그런데 물 대신 전기를 보관(기억)할 수 있는 장치다. 축전기에 전기를 담고 빼는 것이 메모리에 쓰고 읽는 일이 된다.)
상위레벨의 개념에 머물면 그렇지만, 흥미롭게도 현실로 내려가보면 시간을 견디는 기억이 그 세 개의 회로로 구현될 수 있다. 병렬, 직렬, 뒤집기 스위치를 잘 연결하면, 하는 일이 기억인 회로가 스위치로 만들어지는 것이다. 컴퓨터가 발명되기도 전인 1918년에 컴퓨터와 상관없이 이미 스위치만 가지고 가능하다고 발견된 스위치 회로였다. 플립플롭 혹은 래치라고 부른다. (

플립플롭,flip-flop

래치,latch)

두 회로가 동시에 서로를 물면서 엮여 있는 회로다. (아래 그림에서 (NOR표기)는 '또는' 한 결과를 '아닌'하는 회로를 간단히 표현한 것이다. 선이 겹쳐도 연결된 게 아니다. 점이 있는 곳이 연결된 경우다.)

By Napalm Llama - Modification of Wikimedia Commons file R-S.gif (shown below), CC BY 2.0

즉, 위의 상황을 연립방정식으로 표현하면 다음과 같다.

Q=−(R+Q̅)
Q̅=−(S+Q)

이렇게 연결하면 R(reset)과 S(set)의 조합으로 0 혹은 1을 메모리(Q)에 쓰게 되고, 이후에 R과 S가 모두 0이 되면 그 이전의 Q 값을 유지하게 된다.
기억하는 것이다.
살펴보자. R = 0, S = 1인 경우를 보자. S = 1이므로 Q̅는 무조건 0이다. 그러면 Q는 1이 된다. 서로의 결과를 입력으로 물고 있어서 이 결과는 변함없다. 그런 후, R과 S가 모두 0으로 떨어져도, Q는 1을 유지한다. 이제부터 R = 0, S = 0인 동안은 Q가 기억되는 것이다. 그러다가 0을 쓰고 싶으면 R = 1, S = 0을 넣는다. 그러면 Q는 0이 된다. 그런 후, R과 S가 모두 0으로 떨어져도, Q는 0을 유지한다. 이제부터 R = 0, S = 0인 동안은 Q가 기억되는 것이다.

시간	S	R	Q
$t$	1	0	1
$t+1$	0	0	1 (기억)
$t+2$	0	1	0
$t+3$	0	0	0 (기억)

[edit]

5. power 계산 algorithm ¶

// 컴여세 p99
$a^n=\underbrace{a\times\cdots\times a}_{n}$ 계산하기.

$a$ 를 $n-1$ 번 곱하면 된다.
더 빨리 하는 방법은 반만큼만 곱하고 그 결과를 제곱하는 것을 반복해서 적용하는 것이다. 반만큼만 곱한 후 제곱하기. 반만큼을 곱할 때도 다시 그 반만큼만 곱해서 제곱하기 등 반복해서 내리 파고든다. 예를 들어 $a^8$ 라면 $a^4$ 를 계산한 다음 제곱하는 것이다. $a^4$ 도 $a^2$ 를 계산한 후 제곱하면 된다. $a^2$ 은 제곱만하면 된다. 즉 제곱을 세 번 $((a^2)^2)^2$ 하면 $a^8$ 을 얻을 수 있다. $a^n$ 을 이런 식으로 하면 곱하는 횟수는, $a^n=(\cdots(\overbrace{a^2)^2 \cdots )^2}^{k}$ 인 $k,$ 즉 $2^k=n$ 인 $k$ 이므로 $\log_2 n$ 만큼만 곱하는 것으로 줄어든다. ('만큼'이란 표현을 쓴 이유가 있다. $a^7$ 같이 홀수 승이 나타나면 제곱하고 한 번 곱해야 $(\times a)$ 한다. $a^7 = (a^2 \times a)^2 \times a.$ 그렇지만 많아야 $\log_2 n$ (제곱 횟수) $+\log_2 n$ (한 번 곱하는 횟수)보다는 적게 곱하게 된다.)

[edit]

6. 복잡도 and big-O / 점근표기법 ¶

// 컴여세 p101

복잡도,complexity

알고리즘 복잡도의 종류를 구분하는 표기법이 있다. 'big-O' 표기법이라고 하는데, 입력의 크기를 $n$ 이라고 하고, 계산 비용이 입력이 커지면서 결국 어떤 함수 $f(n)$ 의 상수곱을 넘지 않으면 $O(f(n))$ 이라고 쓴다.
예를 들어 어떤 알고리즘의 비용이 $5n+3$ 이면 $O(n)$ 이다. $2n^3 + n^2$ 이었으면 $O(n^3)$ 이다. 즉 제일 차수가 높은 항만 남기고 계수는 무시하면 된다.
실제 계산 복잡도가 $10000 \times n^2$ 이었건 $3n^2 + 10n$ 이었건 모두 $O(n^2)$ 이다.

복잡도의 종류마다 그 성격을 살펴보면 다음과 같다.

실행비용	$n$ 이 2배가 되면	일컫기를
$O(1)$	변함없다	상수 constant
$O(\log n)$	약간의 상수만큼 커진다	로그 logarithmic
$O(n)$	2배 커진다	선형 linear
$O(n\log n)$	2배보다 약간 더 커진다	엔로그엔 n log n
$O(n^2)$	4배 커진다	제곱배 quadratic
$O(n^k)$ (상수 k)	2^k배 커진다	k승배, 다항 polynomial
$O(k^n)$ (상수 k>1)	kⁿ배 커진다	기하급수배 exponential
$O(n!)$	nⁿ배 정도 커진다 (각주)	계승배 factorial