#noindex ## fork할때 새 페이지에 noindex 넣을 것 <> = 대각선논법 간단한 설명 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 등을 세로축에 쓰면 대각선의 점들에 해당하기 때문이다. = 선택: 멀티플렉서 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 = 응답: 디코더 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 = 기억: 플립플롭 flip-flop, 래치 latch = // 컴여세 pp. 74-76 그리고 기억장치도 '그리고', '또는', '아닌'으로 조립할 수 있다. 이건 언뜻 이해하기 어려울 수 있다. 기억은 시간이 관련되어야 하는데, 생각을 조립하는 그 세 개의 접속사에는 시간 개념이 없기 때문이다. (각주: 스위치를 쓰지 않는 자연스런 기억 장치도 있다. [[VG:축전기,capacitor]]라는 장치다. 축전기는 비유하자면 물컵이다. 그런데 물 대신 전기를 보관(기억)할 수 있는 장치다. 축전기에 전기를 담고 빼는 것이 메모리에 쓰고 읽는 일이 된다.) 상위레벨의 개념에 머물면 그렇지만, 흥미롭게도 현실로 내려가보면 시간을 견디는 기억이 그 세 개의 회로로 구현될 수 있다. 병렬, 직렬, 뒤집기 스위치를 잘 연결하면, 하는 일이 기억인 회로가 스위치로 만들어지는 것이다. 컴퓨터가 발명되기도 전인 1918년에 컴퓨터와 상관없이 이미 스위치만 가지고 가능하다고 발견된 스위치 회로였다. 플립플롭 혹은 래치라고 부른다. ([[VG:플립플롭,flip-flop]] [[VG:래치,latch]]) ---- 두 회로가 동시에 서로를 물면서 엮여 있는 회로다. (아래 그림에서 (NOR표기)는 '또는' 한 결과를 '아닌'하는 회로를 간단히 표현한 것이다. 선이 겹쳐도 연결된 게 아니다. 점이 있는 곳이 연결된 경우다.) https://i.imgur.com/VoqYhlJ.gif [[https://commons.wikimedia.org/w/index.php?curid=4845402 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 (기억)|| = 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$ (한 번 곱하는 횟수)보다는 적게 곱하게 된다.) = 복잡도 and big-O / 점근표기법 = // 컴여세 p101 [[VG:복잡도,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^^n^^배 커진다 ||기하급수배 exponential || ||$O(n!)$ ||n^^n^^배 정도 커진다 (각주) ||계승배 factorial || (각주): $n! \approx \sqrt{2\pi n}(n/e)^n.$ ([[VG:스털링_공식,Stirling_formula]]) 예를 들어 입력 크기 $n$ 이 1이었다가 10이 되면, 비용이 $O(n)$ 인 경우는 10배가 커지지만, $O(n^2)$ 인 경우는 100배가 커지고, $O(2^n)$ 인 경우는 약 1000배가 커지고, $O(n!)$ 인 경우는 3,000,000배보다 더 커진다! = addhere =