U E D R , A S I H C RSS
ZeroWiki

TAOCP/Basic Concepts

1. 1.1 Algorithms


1.1. ์•Œ๊ณ ๋ฆฌ์ฆ˜ E(์œ ํด๋ฆฌ๋“œ์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜(Euclid's algorithm)) 

~cpp 
์–‘์˜ ์ •์ˆ˜ 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๋‹จ๊ณ„๋กœ ๋Œ์•„๊ฐ„๋‹ค.โ– 


~cpp 
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์ด ๊ตํ™˜๋œ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค
์šฐ๋ฆฌ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ƒˆ๋กœ์šด ๋‹จ๊ณ„๋ฅผ ์ถ”๊ฐ€ํ•  ์ˆ˜ ์žˆ๋‹ค(๊ผญ ํ•„์š”ํ•˜์ง„ ์•Š๋‹ค)

~cpp 
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์ด๋‹ค


1.2. ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ 5๊ฐ€์ง€ ์ค‘์š”ํ•œ ํŠน์ง•

1) ์œ ํ•œ์„ฑ(Finiteness)
์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์œ ํ•œํ•œ ๋‹จ๊ณ„ ํ›„์— ํ•ญ์ƒ ์ข…๋ฃŒ๋˜์–ด์•ผ ํ•œ๋‹ค

2) ๋ช…ํ™•์„ฑ(Definiteness)
์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ฐ ๋‹จ๊ณ„๋Š” ์ •ํ™•ํžˆ ์ •์˜๋˜์–ด์•ผ ํ•œ๋‹ค

3) ์ž…๋ ฅ(Input)
์•Œ๊ณ ๋ฆฌ์ฆ˜์€ 0๊ฐœ ์ด์ƒ์˜ ์ž…๋ ฅ์„ ๊ฐ€์ง„๋‹ค

4) ์ถœ๋ ฅ(Output)
์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•˜๋‚˜ ์ด์ƒ์˜ ์ถœ๋ ฅ์„ ๊ฐ€์ง„๋‹ค

5) ํšจ์œจ์„ฑ(Effectiveness)
์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ณดํ†ต ํšจ์œจ์ ์œผ๋กœ ์ˆ˜ํ–‰๋˜๋„๋ก ๊ธฐ๋Œ€๋œ๋‹ค


1.3. ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ฐœ๋…์„ ์ˆ˜ํ•™์  ์ง‘ํ•ฉ๋ก ์˜ ๊ด€๊ณ„๋กœ ๋‚˜ํƒ€๋‚ด๊ธฐ

๊ณ„์‚ฐ์ ์ธ ๋ฐฉ๋ฒ•(computational method)์„ 4์Œ์˜ (Q,I,ฮฉ,f)๋กœ ํ˜•์‹์„ ๊ฐ–์ถฐ ์ •์˜ํ•˜์ž
Q๋Š” ๋ถ€๋ถ„์ง‘ํ•ฉ I์™€ ฮฉ๋ฅผ ํฌํ•จํ•˜๋Š” ์ง‘ํ•ฉ์ด๋‹ค
f๋Š” Q์—์„œ Q ์ž๊ธฐ์ž์‹ ์œผ๋กœ ๊ฐ€๋Š” ํ•จ์ˆ˜์ด๋‹ค
ฮฉ์˜ ๋ชจ๋“  ์›์†Œ q์— ๋Œ€ํ•˜์—ฌ f(q)๋Š” q์™€ ๊ฐ™์•„์•ผ ํ•œ๋‹ค.
Q : ๊ณ„์‚ฐ
I : ์ž…๋ ฅ
ฮฉ : ์ถœ๋ ฅ
f : ๊ณ„์‚ฐ ๊ทœ์น™
์ง‘ํ•ฉ I์˜ ์›์†Œ x์˜ ์ž…๋ ฅ์€ ๊ณ„์‚ฐ์ˆ˜์—ด, x0, x1, x2,..., ๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ํ•œ๋‹ค
~cpp 
	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๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜๋œ๋‹ค.
~cpp 
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).

2. 1.3. MIX

์ด ์ฑ…์˜ ์ˆ˜๋งŽ์€ ๋ถ€๋ถ„์—์„œ MIX์–ธ์–ด๊ฐ€ ๋“ฑ์žฅํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ๋…์ž๋Š” ์ด ์ ˆ์„ ์ฃผ์˜ ๊นŠ๊ฒŒ ๊ณต๋ถ€ํ•ด์•ผ ํ•œ๋‹ค.

2.1. 1.3.1. Description of MIX

2.1.1. ์šฉ์–ด๊ณผ ํ‘œ๊ธฐ๋ฒ•

  • Words( Partitial fieslds of wordsํฌํ•จ)
    ์—ฌ์„ฏ ๋ฐ”์ดํŠธ๋กœ ์ด๋ฃจ์–ด์ง„๋‹ค. ํ•œ ๋ฐ”์ดํŠธ์—๋Š” 0~63๊นŒ์ง€ ์ˆซ์ž๊ฐ€ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋ฆผ์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.
    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
    ยฑ Byte Byte Byte Byte Byte
    • I register - rI1~rI6๊นŒ์ง€ ์žˆ์Œ.
    ยฑ Byte Byte
    J register
    + Byte Byte
    ๊ทธ ์™ธ์—
    Overfolw toggle - on, off
    Comparison indicator, - EQUAL, LESS, GREATER
    Input, Output Devices
  • Instruction format
    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 || ๊ณผ ๊ฐ™๋‹ค.''

2.1.2. ์—ฐ์‚ฐ

  • 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)์ด ์žˆ๋‹ค.

2.2. 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๊ฐ™์ด ๋ณ€ํ•˜์ง€ ์•Š๋Š” ๊ฒƒ์€ ์ƒ๋žตํ•œ๋‹ค.

2.2.1. 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์ด๋Ÿฐ ์‹์œผ๋กœ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค. ์ด ๊ณผ์ •์„ ์ปดํ“จํ„ฐ๋กœ ์‹œ๋„ํ•ด๋ณด์ž.

2.2.2. 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
์ž˜ ๋ชจ๋ฅด๊ฒ ๋‹ค.

2.2.3. Another Approach(Algorithm B)

What is this computer-oriented method for permutation multipulication?
์˜ค๋ฅธ์ชฝ์—์„œ ์™ผ์ชฝ์œผ๋กœ ์˜ค๋ฉด์„œ ๋‹ต์„ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.
(์—ฌ๊ธฐ์„œ๋Š” ์ฑ…์— ์žˆ๋Š” Table2(p.173)๋ฅผ ๋ด์•ผ ํ•œ๋‹ค. ์„ธ๋กœ ํ•œ ์ค„์ด Ti๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๊ทธ ๋ฐ–์— i, j, Z ๊ฐ’์„ ์ ์–ด ๋†“์œผ๋ฉด ์ดํ•ดํ•  ์ˆ˜ ์žˆ๋‹ค. n์€ ๋ฌธ์ž์˜ ๊ฐœ์ˆ˜์ด๋‹ค.)
B1. ๋ชจ๋“  1โ‰คkโ‰คn์— ๋Œ€ํ•ด์„œ Tk โ† k. ์˜ค๋ฅธ์ชฝ๋ถ€ํ„ฐ ์ฝ์„ ์ค€๋น„๋ฅผ ํ•œ๋‹ค.
B2. ์‹์„ ์˜ค๋ฅธ์ชฝ๋ถ€ํ„ฐ ํ•˜๋‚˜์”ฉ ์ฝ์œผ๋ฉด์„œ
) ์ด๋ฉด Zโ†0ํ•˜๊ณ  B2๋ฐ˜๋ณต
( ์ด๋ฉด B4๋กœ.
๊ทธ ์™ธ์—๋Š” i์ธ xi๋ฅผ ๊ฐ€์ง€๊ณ  B3๋กœ
B3. Zโ†”Ti๋ฅผ ํ•˜๊ณ  ๋‚˜์„œ Ti = 0์ด๋ฉด jโ†i๋ฅผ ํ•œ ๋’ค B2๋กœ.
B4. Tj โ† Z ํ›„์— B2๋กœ.
  • Timing
    ์—ฐ์Šต๋ฌธ์ œ10์— ์žˆ๋‹ค.

2.2.4. Inverse

์ˆœ์—ด ์—ฐ์‚ฐ์„ ์›๋ž˜๋Œ€๋กœ ๋Œ๋ฆฌ๋Š” ์ˆœ์—ด(์—ญํ–‰๋ ฌ๊ณผ ๋น„์Šทํ•˜๋‹ค.)
๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๋งŽ์ด ์“ฐ๋ฉด ์‰ฝ๊ฒŒ ํ•ด๊ฒฐ( Y[Xk โ† k )
ํ•˜์ง€๋งŒ ์žฌ๋ฏธ์‚ผ์•„ nใ…ฃ ๋งค์šฐ ํฌ๊ณ  ๋‚จ๋Š” ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ์—†๋‹ค๊ณ  ํ•ด๋ณด์ž.

2.2.5. Algorithm I

(์ด๋ฒˆ์—๋„ Table 3(p.177)๋ฅผ ๋ณด๋ฉด์„œ ํ•˜๋ฉด ๋œ๋‹ค.)
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:09
Processing time 0.0102 sec