Maintenance script: Repair batch-0003 pages from live compare

2026-03-27T00:29:11Z

Repair batch-0003 pages from live compare

← Older revision		Revision as of 00:29, 27 March 2026
Line 5:		Line 5:
	양의 정수 m과 n이 주어졌을때, 그것들의 최대공약수(greatest common divisor)		양의 정수 m과 n이 주어졌을때, 그것들의 최대공약수(greatest common divisor)
	(m과 n을 모두 나누는 가장 큰 양의 정수)를 구한다.		(m과 n을 모두 나누는 가장 큰 양의 정수)를 구한다.
	E1. [나머지 구하기] m을 n으로 나누고 나머지를 r이라 하자.(0 <= r < n)		E1. [나머지 구하기] m을 n으로 나누고 나머지를 r이라 하자.(0 <= r < n)
	E2. [그것이 0인가?] r = 0 이면, 알고리즘은 끝난다; n이 답이다.		E2. [그것이 0인가?] r = 0 이면, 알고리즘은 끝난다; n이 답이다.
	E3. [줄이기] m <- n, n <- r 으로 설정한다, 그리고 E1단계로 돌아간다.■		E3. [줄이기] m <- n, n <- r 으로 설정한다, 그리고 E1단계로 돌아간다.■

	Fig 1. 알고리즘 E의 순서도		Fig 1. 알고리즘 E의 순서도
Line 26:		Line 26:
	우리는 다음과 같은 새로운 단계를 추가할 수 있다(꼭 필요하진 않다)		우리는 다음과 같은 새로운 단계를 추가할 수 있다(꼭 필요하진 않다)

	E0. [m >= n 인지 확인하기] m < n 이라면, m <-> n 을 교환한다		E0. [m >= n 인지 확인하기] m < n 이라면, m <-> n 을 교환한다

	E1으로 돌아가서 544/119 = 4+68/119, 그러므로 r <- 68		E1으로 돌아가서 544/119 = 4+68/119, 그러므로 r <- 68
Line 83:		Line 83:
	* Words( Partitial fieslds of words포함)		* Words( Partitial fieslds of words포함)
	여섯 바이트로 이루어진다. 한 바이트에는 0~63까지 숫자가 들어갈 수 있다. 그림으로 나타내면 다음과 같다.		여섯 바이트로 이루어진다. 한 바이트에는 0~63까지 숫자가 들어갈 수 있다. 그림으로 나타내면 다음과 같다.
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\| 0		\| 0
Line 104:		Line 104:
	레지스터는 앞에 소문자 r을 붙여 표기		레지스터는 앞에 소문자 r을 붙여 표기
	A, X register		A, X register
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\| ±		\| ±
Line 132:		Line 132:
	Input, Output Devices		Input, Output Devices
	* Instruction format		* Instruction format
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\| 0		\| 0
Line 154:		Line 154:
	여기서 더해진 주소를 M, M에 들어있는 값을 CONTETNS(M)이라고 한다.		여기서 더해진 주소를 M, M에 들어있는 값을 CONTETNS(M)이라고 한다.
	* Notation		* Notation
	~~~cpp~~ OP ADDRESS, I(F)		<code>OP ADDRESS, I(F)</code>
	같은 형식으로 쓴다.		같은 형식으로 쓴다.
	<!> ''예) LDA는 명령어 코드가 8이다.		<!> ''예) LDA는 명령어 코드가 8이다.
Line 246:		Line 246:
	----		----
	[[TAOCP]]		[[TAOCP]]

imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:09Z

New page

__TOC__
= 1.1 Algorithms =

== 알고리즘 E(유클리드의 알고리즘(Euclid's algorithm)) ==
양의 정수 m과 n이 주어졌을때, 그것들의 최대공약수(greatest common divisor)
(m과 n을 모두 나누는 가장 큰 양의 정수)를 구한다.
E1. [나머지 구하기] m을 n으로 나누고 나머지를 r이라 하자.(0 <= r < n)
E2. [그것이 0인가?] r = 0 이면, 알고리즘은 끝난다; n이 답이다.
E3. [줄이기] m <- n, n <- r 으로 설정한다, 그리고 E1단계로 돌아간다.■

Fig 1. 알고리즘 E의 순서도

|<------------------------------------------------------|
↓ |
-------------------- ------------------ 아니오 -------------
| E1.나머지 구하기 |-------->( E2.그것이 0인가? )-------->| E3.줄이기 |
-------------------- ------------------ -------------
|예
↓

m = 119 와 n = 544 가 주어졌다고 하자
E1 단계에서 시작. m을 n으로 나누면 몫은 0이고 나머지는 119이다. 그러므로 r <- 119
E2 단계에서 r ≠ 0 이므로 적용되지 않는다
E3 단계에서 m <- 544, n <- 119
이것으로 처음에 m < n 이면 항상 m과 n이 교환된다는 것을 알 수 있다
우리는 다음과 같은 새로운 단계를 추가할 수 있다(꼭 필요하진 않다)

E0. [m >= n 인지 확인하기] m < n 이라면, m <-> n 을 교환한다

E1으로 돌아가서 544/119 = 4+68/119, 그러므로 r <- 68
다시 E2는 적용되지않고
E3에서 m <- 119, n <- 68
다음순환에서 r <- 51, m <- 68, n <- 51
다음에 r <- 17, m <- 51, n <- 17
마지막으로 51을 17로 나누었을때, r <- 0, 그러므로 E2에서 알고리즘은 종료된다
119와 544의 최대공약수는 17이다

== 알고리즘의 5가지 중요한 특징 ==
1) 유한성(Finiteness)
알고리즘은 유한한 단계 후에 항상 종료되어야 한다

2) 명확성(Definiteness)
알고리즘의 각 단계는 정확히 정의되어야 한다

3) 입력(Input)
알고리즘은 0개 이상의 입력을 가진다

4) 출력(Output)
알고리즘은 하나 이상의 출력을 가진다

5) 효율성(Effectiveness)
알고리즘은 보통 효율적으로 수행되도록 기대된다

== 알고리즘의 개념을 수학적 집합론의 관계로 나타내기 ==
계산적인 방법(computational method)을 4쌍의 (Q,I,Ω,f)로 형식을 갖춰 정의하자
Q는 부분집합 I와 Ω를 포함하는 집합이다
f는 Q에서 Q 자기자신으로 가는 함수이다
Ω의 모든 원소 q에 대하여 f(q)는 q와 같아야 한다.
Q : 계산
I : 입력
Ω : 출력
f : 계산 규칙
집합 I의 원소 x의 입력은 계산수열, x0, x1, x2,..., 를 다음과 같이 정의한다
x0 = x 이고 xk + 1 = f(xk) (k >= 0)
Ω에 속하는 xk 에 대하여 k가 가장 작은 정수라면 계산수열은 k단계에서 종료된다고 한다. 그리고 이 경우에 x로부터 결과 xk가 생성된다고 한다.

알고리즘 E는 다음과 같이 이런 관계로 형식화된다.
Q를 모든 단일 (n), 모든 순서있는 쌍 (m,n), 모든 순서있는 4쌍 (m,n,r,1), (m,n,r,2), (m,n,p,3) (m,n,p는 양의 정수, r은 음이 아닌 정수)의 집합이라 하자.
I를 모든 쌍 (m,n)의 부분집합이라 하자.
Ω를 모든 단일 (n)의 부분집합이라 하자.
f는 다음과 같이 정의된다.
f((m,n)) = (m,n,0,1}; f((n)) = (n);
f((m,n,r,1)) = (m, n, m을 n으로 나눈 나머지, 2);
r = 0 이면 f((m,n,r,2)) = (n), 그렇지 않으면 (m,n,r,3);
f((m,n,p,3)) = (n,p,p,1).

= 1.3. MIX =
이 책의 수많은 부분에서 MIX언어가 등장한다. 따라서 독자는 이 절을 주의 깊게 공부해야 한다.
== 1.3.1. Description of MIX ==
=== 용어과 표기법 ===
* Words( Partitial fieslds of words포함)
여섯 바이트로 이루어진다. 한 바이트에는 0~63까지 숫자가 들어갈 수 있다. 그림으로 나타내면 다음과 같다.
{| class="wikitable"
|-
| 0
| 1
| 2
| 3
| 4
| 5
|-
| ±
| Byte
| Byte
| Byte
| Byte
| Byte
|}
필드 제한이 주어질 수 있다. 형식은 (L:R)이다. (L~R의 범위를 뜻한다.)
<!> ''예) (0:0)는 부호, (1:5)는 부호가 없는 숫자, (3:4)는 3,4번째 바이트''
* Registers
레지스터는 앞에 소문자 r을 붙여 표기
A, X register
{| class="wikitable"
|-
| ±
| Byte
| Byte
| Byte
| Byte
| Byte
|}
I register - rI1~rI6까지 있음.
{| class="wikitable"
|-
| ±
| Byte
| Byte
|}
J register
{| class="wikitable"
|-
| +
| Byte
| Byte
|}
그 외에
Overfolw toggle - on, off
Comparison indicator, - EQUAL, LESS, GREATER
Input, Output Devices
* Instruction format
{| class="wikitable"
|-
| 0
| 1
| 2
| 3
| 4
| 5
|-
| ±
|
| A A
| I
| F
| C
|}
C - 명령어 코드(the poeration code)
F - 명령어의 변경(a modification of the operation code). (L:R)이라면 8L+R = F
±AA - 메모리 주소(the address)
I - 인덱스(the index specification). 값이 1~6으로 rI1~rI6에 있는 내용과 메모리 주소를 더함
여기서 더해진 주소를 M, M에 들어있는 값을 CONTETNS(M)이라고 한다.
* Notation
~cpp OP ADDRESS, I(F)
같은 형식으로 쓴다.
<!> ''예) LDA는 명령어 코드가 8이다.
LDA 2000, 2(0:3) 은 || + || 2000 |||| 2 || 3 || 8 || 과 같다.''
=== 연산 ===
* Loading operators.
CONTENTS(M)을 레지스터에 넣는다.
LDA, LDX, LDi, LDAN, LDXN, LDiN이 있다.
* Storing operators.
레지스터의 값을 CONTENTS(M)에 넣는다.
STA, STX, STi, STJ, STZ가 있다.
* Arithmetic operators.
사칙연산을 한다. ADD, SUB, MUL, DIV가 있다.
* Address transfer operators.
이 연산에서 M은 메모리 셀을 가리키지 않고, 그냥 부호있는 숫자로 쓰인다. ENTr, ENNr, INCr, DECr가 있다. ( r은 A, X, 1~6)
<!> ''예) ENTA 2000 - > rA || + || 0 || 0 || 0 || 2000 ||''
* Comparison operator
레지스터와 CONTENTS(M)을 비교해서 LESS, GREATER, EQUAL을 설정하는 명령어이다. CMPA, CMPX, CMPi가 있다. CMPi를 할 때는 앞에 세 자리가 0이라고 가정한다.
* Jump operators.
M이 가리키는 메모리 셀로 점프한다. JSJ를 빼면 점프를 하면서 점프 명령어 다음 위치를 rJ에 저장한다. the comparison indicator를 이용하거나(JL, JE, JG, JGE, JLE, JNE) , 레지스터(JrN, JrZ, JrP, JrNN, JrNZ, JrNP)를 이용한다.
* Miscellaneous operators.
시프트 명령은 rA와 rX를 사용한다. SLA, SRA, SLAX, SRAX, SLC, SRC가 있다. M은 시프트하는 횟수를 나타낸다.
MOVE명령은 F만큼 CONTENTS(M)을 rI1이 가리키는 메모리 셀로 값을 복사한다.
<!> ''예1) rI1 = 1001일 때 MOVE 1000,(3)
CONTENTS(1000) -> CONTENTS(1001), rI1 = 1002
CONTENTS(1001) -> CONTENTS(1002), rI1 = 1003
CONTENTS(1002) -> CONTENTS(1003), rI1 = 1004''
그럼 다음엔 어떻게 되나?
<!> ''예2) rI1 = 2000일 때 MOVE 1000,(3)''
''CONTENTS(1000) -> CONTENTS(2000), rI1 = 2001
CONTENTS(1001) -> CONTENTS(2001), rI1 = 2002
CONTENTS(1002) -> CONTENTS(2002), rI1 = 2003''
(rI1값이 중간중간 바뀌는게 아니라 다 끝나고 F만큼 더해진다고 생각하면돼 --세환)
NOP 명령은 아무것도 하지 않는다.
HLT 명령은 기계를 멈춘다(The machine stops.)
* Input-output opertors.
필요할 때 보려고 생략했다.
* Conversion operators.
NUM은 rAX를 가지고 숫자로 바꾸어 rA에 저장한다. 각 바이트가 한 자리로 바뀌는데, 일의 자리만 가지고 바꾼다(10 -> 0, 23->3 )
CHAR는 rA를 가지고 문자 코드로 바꾸어 rAX에 저장한다.
* Timing
각 명령어는 실행 시간(excution time)이 있다.

== 1.3.3 Applications to Permutations ==
MIX 프로그램의 예제를 보여준다. 중요한 순열의 성질(properties of permutations)을 소개한다.

순열은 abcdef를 재배열(rearrangement)이나 이름바꾸기(renaming)를 해서 얻는다고 볼 수 있다. 이를 다음과 같이 표시할 수 있다.(p.164참조)
( a b c d e f )
( c d f b e a )
순환 표시(a cycle notation)로 쓰면 다음과 같다
( a c f ) ( b d )
''해설 : a가 c로 바뀌는 것(a goes to c)을 a->c라고 표시한다. 따라서 위의 표현은 a->c->f->a, b->d->b를 나타낸다.e->e같이 변하지 않는 것은 생략한다.''
=== Products of permutations ===
두 순열을 곱한다. (합성함수와 비슷하다.)
(a b c d e f ) × (a b c d e f )
(c d f b e a ) (b d c a f e )
= (a b c d e f )
'' ''(c a e d f b )
이를 a cycle notation으로 쓰면
(a c f ) (b d )(a b d )(e f) = (a c e f b)
과정은 왼쪽부터 시작해서 오른쪽으로 가면서 찾는 방식이다. a부터 시작하면 a->c이고, c에서 시작하면 c->f->e이런 식으로 찾을 수 있다. 이 과정을 컴퓨터로 시도해보자.
=== Algorithm A ===
A1. 모든 왼쪽 괄호에 흔적을 남긴다. 오른쪽 괄호를 왼쪽 괄호 다음 문자로 바꾸고 흔적을 남긴다.
예) '''(a c f g)''' -> ('''a c f g''' a
A2. 왼쪽에서 오른쪽으로 가면서 흔적이 없는 첫번째 문자를 START라고 한다. 왼쪽 괄호와 그 문자를 출력하고 흔적을 남긴다. 모든 문자에 흔적이 남을 경우 종료한다.
A3. 다음문자를 CURRENT로 세팅한다.
A4. 오른쪽으로 가면서 CURRENT와 같은 문자를 찾는다. 찾은 경우 흔적을 남기고 A3로 간다. (못 찾고 오른쪽 끝까지 가면 A5로 간다.)
A5. START≠ CURRENT이면 CURRENT를 출력하고 식 왼쪽부터 시작해서 A4로 간다.( 같으면 A6로 간다.)
A6. (완전한 사이클을 찾았으므로) 오른쪽 괄호를 닫고 A2로 간다.
* Timing
잘 모르겠다.
=== Another Approach(Algorithm B) ===
What is this computer-oriented method for permutation multipulication?
오른쪽에서 왼쪽으로 오면서 답을 찾는 방법이다.
(여기서는 책에 있는 Table2(p.173)를 봐야 한다. 세로 한 줄이 T[i]를 나타낸다. 그 밖에 i, j, Z 값을 적어 놓으면 이해할 수 있다. n은 문자의 개수이다.)
B1. 모든 1≤k≤n에 대해서 T[k] ← k. 오른쪽부터 읽을 준비를 한다.
B2. 식을 오른쪽부터 하나씩 읽으면서
) 이면 Z←0하고 B2반복
( 이면 B4로.
그 외에는 i인 xi를 가지고 B3로
B3. Z↔T[i]를 하고 나서 T[i] = 0이면 j←i를 한 뒤 B2로.
B4. T[j] ← Z 후에 B2로.
* Timing
연습문제10에 있다.
=== Inverse ===
순열 연산을 원래대로 돌리는 순열(역행렬과 비슷하다.)
메모리를 많이 쓰면 쉽게 해결( Y[X[k]] ← k )
하지만 재미삼아 nㅣ 매우 크고 남는 메모리가 없다고 해보자.
=== Algorithm I ===
(이번에도 Table 3(p.177)를 보면서 하면 된다.)
----
[[TAOCP]]

TAOCP/BasicConcepts - Revision history

Maintenance script: Repair batch-0003 pages from live compare

imported>Unknown at 05:28, 7 February 2021