TmpExcerpts

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

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

무한이 다 같은 무한이 아니고 VG:자연수,natural_number의 개수보다 VG:실수,real_number의 개수가 훨씬 크다.
또, 자연수의 개수보다 자연수의 VG:부분집합,subset의 개수가 훨씬 더 크다. Georg_Cantor가 처음으로 확인해 준 사실이다.

에 대한 각주:

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

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

자연수의 부분집합들이 자연수만큼만 있다면 그 집합들을 자연수로 모두 번호 매길 수 있을 것이다.
N1, N2, N3 등등. 이제 N1부터 차례로 살피면서 자연수 집합 X를 만들 수 있는데, 이 집합이 모든 자연수의 부분집합들과는 다르게 된다!
X는 빈집합(VG:공집합,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 등을 세로축에 쓰면
대각선의 점들에 해당하기 때문이다.

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

// 컴여세 pp. 72-73
둘 중 하나를 조건에 따라 결정하는 회로를 만들 수 있다. 즉,
들어오는 입력 x, y 중에서
선택자 z가 0이면 x를, 1이면 y를 선택하는 회로다. '''멀티플렉서multiplexer''라고 한다.
이러한 회로 역시 마찬가지로 입력과 출력을 표로 그리고 원하는 출력이 나오도록 회로를 만들어 주면 된다.
xyz결과
000 0
010 0
100 1
110 1
001 0
011 1
101 0
111 1
결과가 1이 되는 xyz의 4가지 경우는 100 110 011 111 이다. 따라서 위의 작동을 하는 디지털 논리회로는 다음과 같다.
x(-y)(-z)+xy(-z)+(-x)yz+xyz
같은 일을 하는 더 간단한 회로로 다시 쓰면 아래와 같이 된다.
x(-z)+yz

3. 응답: 디코더 decoder

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

출력이 두 개의 선 x, y이다. 선택자(입력) c의 값에 따라 x나 y 중 하나만 1이 되는 회로다.
cxy
010
101
따라서 논리회로는 x=-c이고 y=c이다.

출력이 네 개의 선 x, y, z, w라고 하자. 이 경우 선택자(입력)는 두 개가 필요하다. 선 c와 d에 따라, 네 개의 출력 선 중에서 하나만 1이 된다.
cdxyzw
001000
010100
100010
110001
따라서 논리회로는 다음과 같다.
x=(-c)(-d)
y=(-c)d
z=c(-d)
w=cd

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

// 컴여세 pp. 74-76

그리고 기억장치도 '그리고', '또는', '아닌'으로 조립할 수 있다.
이건 언뜻 이해하기 어려울 수 있다. 기억은 시간이 관련되어야 하는데, 생각을 조립하는 그 세 개의 접속사에는 시간 개념이 없기 때문이다. (각주: 스위치를 쓰지 않는 자연스런 기억 장치도 있다. VG:축전기,capacitor라는 장치다. 축전기는 비유하자면 물컵이다. 그런데 물 대신 전기를 보관(기억)할 수 있는 장치다. 축전기에 전기를 담고 빼는 것이 메모리에 쓰고 읽는 일이 된다.)
상위레벨의 개념에 머물면 그렇지만, 흥미롭게도 현실로 내려가보면 시간을 견디는 기억이 그 세 개의 회로로 구현될 수 있다. 병렬, 직렬, 뒤집기 스위치를 잘 연결하면, 하는 일이 기억인 회로가 스위치로 만들어지는 것이다. 컴퓨터가 발명되기도 전인 1918년에 컴퓨터와 상관없이 이미 스위치만 가지고 가능하다고 발견된 스위치 회로였다. 플립플롭 혹은 래치라고 부른다. (VG:플립플롭,flip-flop VG:래치,latch)

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


즉, 위의 상황을 연립방정식으로 표현하면 다음과 같다.
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가 기억되는 것이다.
시간 SRQ
$\displaystyle t$ 101
$\displaystyle t+1$ 001 (기억)
$\displaystyle t+2$ 010
$\displaystyle t+3$ 000 (기억)

5. power 계산 algorithm

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

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

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

// 컴여세 p101
VG:복잡도,complexity

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

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

실행비용 $\displaystyle n$ 이 2배가 되면 일컫기를
$\displaystyle O(1)$ 변함없다 상수 constant
$\displaystyle O(\log n)$ 약간의 상수만큼 커진다 로그 logarithmic
$\displaystyle O(n)$ 2배 커진다 선형 linear
$\displaystyle O(n\log n)$ 2배보다 약간 더 커진다 엔로그엔 n log n
$\displaystyle O(n^2)$ 4배 커진다 제곱배 quadratic
$\displaystyle O(n^k)$ (상수 k) 2k배 커진다 k승배, 다항 polynomial
$\displaystyle O(k^n)$ (상수 k>1) kn배 커진다 기하급수배 exponential
$\displaystyle O(n!)$ nn배 정도 커진다 (각주) 계승배 factorial
(각주): $\displaystyle n! \approx \sqrt{2\pi n}(n/e)^n.$ (VG:스털링_공식,Stirling_formula)

예를 들어 입력 크기 $\displaystyle n$ 이 1이었다가 10이 되면, 비용이 $\displaystyle O(n)$ 인 경우는 10배가 커지지만, $\displaystyle O(n^2)$ 인 경우는 100배가 커지고, $\displaystyle O(2^n)$ 인 경우는 약 1000배가 커지고, $\displaystyle O(n!)$ 인 경우는 3,000,000배보다 더 커진다!

7. addhere