• 검색 결과가 없습니다.

Computer Algorithm 프

N/A
N/A
Protected

Academic year: 2022

Share "Computer Algorithm 프"

Copied!
43
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

Computer Algorithm

프로그래밍을 중심으로

남수 진

다음커뮤니케이션

(2)

Part I

Bitmap Sorting

(3)

Programming Pearls Bitmap Sorting

The Problem

Input

A file containing at most n positive integers, each less than n, where n = 107. It is a fatal error if any integer occurs twice in the input. No other data is associated with the inter.

Output

A sorted list in increasing order of the input integers.

Constraints

At most (roughly) a megabye of storage is available in main memory; ample disk storage is available. The run time can be at most several minutes; a run time of ten seconds need not be decreased.

(4)

Programming Pearls Bitmap Sorting

Implementation Sketch

Viewd in this light, the bitmap or bit vector representation of a set screams out to be used. We can represent a toy set of nonnegative integers less than 20 by a string of 20 bits. For instance, we can store the set {1, 2, 3, 5, 8, 13} in this string:

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

The bits representing numbers in the set are 1, and all other bits are 0.

/* phase 1: initialize set to empty */

for i = [0, n) bit[i] = 0

/* phase 2: insert present elements into the set */

for each i in the input file bit[i] = 1

(5)

Part II

Vector Rotation

(6)

Programming Pearls Vector rotation

The Problem

Rotate a one-dimensional vector of n elements left by d positions.

For instance, with n = 8 and d = 3,

the vector abcdefgh is rotated to defghabc.

Can you rotate the vector in time proportional to n using only a few dozen extra bytes of storage?

(7)

Programming Pearls Vector rotation

Pricey Solutions

One might try to solve the problem by copying the first d elements of x to a temporary array, moving the remaining n − d elements left d places, and then copying the first d from the temporary array back to the last positions in x.

One could define a function to rotate x left one position (in time proportional to n) and call it d times, but that would be too time-expensive.

(8)

Programming Pearls Vector rotation

The Juggling Algorithm

The Idea (n = 12, d = 3):

(9)

Programming Pearls Vector rotation

The Block-Swap Algorithm

The Idea:

Change ab to ba

If a is shorter, divide b into bl and br . Swap a and br to change ablbrinto brbla.

Recur on pieces of b.

(10)

Programming Pearls Vector rotation

The Reversal Algorithm

The Idea:

Reverse a to get arb.

Reverse b to get arbr.

Reverse all to get (arbr)r= ba.

(11)

Part III

Josephus Problem

(12)

Concrete Mathematics Josephus problem

An ancient problem named for Flavius Josephus

Legend has it that Josephus wouldn’t have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 the rebels trapped in a cave by the Romans.

Preferring sucide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining persion until no one was left.

(13)

Concrete Mathematics Josephus problem

Josephus problem

In our variation, we start with n people numbered 1 to n around a circle, and we eliminate every second remaining persion until only one survives.

2, 4, 6, 8, 10, 3, 7, 1, 9, so 5 survives.

The Problem: Determine the survivor’s number, J(n).

For example, J(10) = 5.

(14)

Concrete Mathematics Josephus problem

J(n) = n/2

We just saw that J(10) = 5. We might conjecture that J(n) = n/2 when n is even;

J(10) = 5 J(2) = 1 The conjecture fails for n = 4 and n = 6

n 1 2 3 4 5 6

J(n) 1 1 3 1 3 5

(15)

Concrete Mathematics Josephus problem

J(2n), When the number is even

If n itself is an even number, we arrive at a situation similar to what we begin with, except that there are only half as many people, and their numbers have changed.

So let’s suppose that we have 2n people originally.

J(2n) = 2J(n) − 1, for n ≥ 1.

J(20) = 2J(10) − 1 = 2· 5 − 1 = 9

(16)

Concrete Mathematics Josephus problem

J(2n + 1), What about the odd case?

With 2n + 1 people, it turns out that person number 1 is wiped out just after person number 2n, and we’re left with

J(2n + 1) = 2J(n) + 1, for n ≥ 1.

(17)

Concrete Mathematics Josephus problem

Recurrence of the problem

Combining these equations with J(1) = 1 give us a recurrence that define J in all cases:

J(1) = 1;

J(2n) = 2J(n) − 1, for n ≥ 1;

J(2n + 1) = 2J(n) + 1, for n ≥ 1.

This recurrence is much more “efficient,” because it reduces n by a factor of 2 or more each time it’s applied. We could compute J(100000), say, with only 19 application above equation. But still, we seek a

closed

form,

because that will be even quicker and more informative. After all, this is a matter of life or death.

(18)

Concrete Mathematics Josephus problem

Seek the closed form of our recurrence.

Our recurrence make it possible to build a table of small values very quickly.

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

Volià! It seems we can group by power of 2; J(n) is always 1 at the beginning of a group and it increased by 2 within a group. So if we write n in the form n = 2m+ l, where 2m is the largest power of 2 not exceeding n and where l is what’s left, the solution to our recurrence seem to be

J(2 m + l) = 2l + 1, for m ≥ 0 and 0 ≤ l < 2 m .

(19)

Concrete Mathematics Josephus problem

Solve J(n) by computer program.

The solution to our recurrence

J(n) = J(2m+ l) = 2l + 1, for m ≥ 0 and 0 ≤ l < 2m. C program to solve J(n):

unsigned josephus(unsigned n) {

unsigned m;

for (m = 1; m <= n; m *= 2) ; return 2*(n-m/2) + 1;

}

Power of 2 played an important role in our finding solution. It’s natural to look at the radix 2 representation of n and J(n).

(20)

Concrete Mathematics Josephus problem

Seek the soft method.

Suppose n’s binary expression, n = 2m+ l (m ≥ 0, 0 ≤ l < 2m) n = bm2m+ bm−12m−1+ . . . + b12 + b0= (bm bm−1 . . . b1 b0)2, where each bi is either 0 or 1 and where the leading bit bm is 1.

n = (1 bm−1 bm−2 . . . b1 b0)2, l = (0 bm−1 bm−2 . . . b1 b0)2, 2l = (bm−1 bm−2 . . . b1 b0 0)2, 2l + 1 = (bm−1 bm−2 . . . b1 b0 1)2,

J(n) = (bm−1 bm−2 . . . b1 b0 bm)2.

(21)

Concrete Mathematics Josephus problem

Illustrate the magic.

√Let’s compute J(100). In this case we have 100 = 26+ 36, so J(100) = 2· 36 + 1 = 73.

n = 100 = (1100100)2 J(n) = J ((1100100)2)

= (1001001)2

= 26+ 23+ 1 = 64 + 8 + 1

= 73.

C program to solve J(n):

unsigned josephus(unsigned n) {

unsigned k, m;

for (m=n, k=0; m!=1; k++, m>>=1) ; return ((n & (1<<k)-1) << 1) | 1;

}

(22)

Concrete Mathematics Josephus problem

When J(n) = n/2 is true?

Let’s return briefly to our first guess, that J(n) = n/2 when n is even.

J(n) = n/2 2l + 1 = (2m+ l)/2

l = 1

3(2m− 2).

m l n = 2m+ l J(n) = 2l + 1 = n/2 n(binary)

1 0 2 1 10

3 2 10 5 1010

5 10 42 21 101010

7 42 170 85 10101010

(23)

Concrete Mathematics Josephus problem

Generalize the problem.

Does the generalized Josephus recurrence admit of such magic?

f(1) = α;

f(2n + j) = 2f(n) + βj, for j = 0, 1 and n ≥ 1.

And this recurrence unfolds, binary-wise:

f ((bm bm−1 . . . b1 b0)2)

= 2f ((bm bm−1 . . . b1)2) + βb0

= 4f ((bm bm−1 . . . b2)2) + 2βb1+ βb0 ...

= 2mf ((bm)2) + 2m−1βbm−1+· · · + 2βb1+ βb0

= 2mα + 2m−1βbm−1+· · · + 2βb1+ βb0.

f ((b m b m−1 . . . b 1 b 0 ) 2 ) = (α β b

m−1

β b

m−2

· · · β b

1

β b

0

) 2 .

(24)

Concrete Mathematics Josephus problem

Check the generalized solution.

Let’s check the following equation.

f ((b m b m−1 . . . b 1 b 0 ) 2 ) = (α β b

m−1

β b

m−2

· · · β b

1

β b

0

) 2 .

For example, when n = 100 = (1100100)2, our original Josephus values α = 1, β0= −1, and β1 = 1 yield.

n = (1 1 0 0 1 0 0)2 = 100

f(n) = (1 1 −1 −1 1 −1 −1)2

+64 +32 −16 −8 +4 −2 −1 = 73.

The cyclic-shift property follows because each block of binary digits (10· · · 00)2 in the representation of n is transformed into

(25)

Concrete Mathematics Josephus problem

Generalization of the Josephus problem

If we’re really uninhibited, we can now generalize even more. The recurrence

f(j) = αj, for 1 ≤ j < d;

f(dn + j) = cf(n) + βj, for 0 ≤ j < d and n ≥ 1.

is the same as the previous one except that we start with numbers in radix d and produce value in radix c. That is, it has the radix-changing solution

f ((b m b m−1 . . . b 1 b 0 ) d ) = (α b

m

β b

m−1

β b

m−2

· · · β b

1

β b

0

) c .

(26)

Concrete Mathematics Josephus problem

Example of the generalization

For example,

f(1) = 34, f(2) = 5,

f(3n) = 10f(n) + 76, for n ≥ 1, f(3n + 1) = 10f(n) − 2, for n ≥ 1, f(3n + 2) = 10f(n) + 8, for n ≥ 1,

and suppose we want to compute f(19). Here we have d = 3 and c = 10. Now 19 = (203)3, and the radix-changing solution tell us to perform a digit-by-digit replacement from radix 3 to radix 10. So the 2 becomes a 5, and the 0 and 1 become 76 and −1, giving

(27)

Concrete Mathematics Josephus problem

Josephus problem revisited

Let’s consider the more authentic Josephus problem in which every third person is eliminated, instead of every second. If we apply the methods that worked in previous slides to this more difficult problem, we wind up with a recurrence like

J3(n) = 3 2J3 2

3n



+ an



mod n + 1.

where we have an= −2, +1or −12 according as n mod 3 = 0, 1, or 2.

But this recurrence is too horrible to pursue.

(28)

Concrete Mathematics Josephus problem

Another approach to the problem

Whenever a person is passed over, we can assign a new number. Thus 1 and 2 become n + 1 and n + 2, then 3 is executed; 4 and 5 become n + 3 and n + 4, then 6 is executed; . . .; 3k + 1 and 3k + 2 become n + 2k + 1 and n + 2k + 2, then 3k + 3 is executed; . . . then 3n is executed (or left to survive). For example, when n = 10 the numbers are

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17

18 19 20 21 22

23 24 25

26 27

28

(29)

Concrete Mathematics Josephus problem

The survivor’s number J 3 (n)

If N > n, person number N must have had a previous number, and we can find it as fllow: We have N = n + 2k + 1 or N = n + 2k + 2, hence k =b(N − n − 1)/2c; the previous number was 3k + 1 or 3k + 2, respectively. That is, it was 3k(N − n − 2k) = k + N − n. Hence we can calculate the survivor’s number J3(n)as fllow:

N := 3n;

while N > n do N := N − n − 1 2



+ N − n;

J3(n) := N.

This is not a closed form for J3(n); it’s not even a recurrence. But at least it tell us how to calculate the answer reasonably fast, if n is large.

(30)

Concrete Mathematics Josephus problem

Simplify the algorithm

Fortunately there’s way to simplify this algorithm if we use the variable D = 3n + 1 − N in place of N. (This change in notation corresponds to assigning numbers from 3n down to 1, instead of from 1 up to 3n; it’s sort of like countdown.) Then the complicated

assignment to N becomes

D := 3n + 1 − (3n + 1 − D) − n − 1 2



+ (3n + 1 − D) − n



= n + D − 2n − D 2



= D − −D 2



= D + D 2



= 3 2D

 , and we can rewrite the algorithm as follows:

D := 1;

(31)

Concrete Mathematics Josephus problem

J q (n) when every qth person is eliminated

We can show by the same reasoning that the survivor Jq(n) when every qth person is eliminated can be calculated as follows:

D := 1;

while D ≤ (q − 1)n do D :=

 q q − 1D



; Jq(n) := qn + 1 − D.

In the case q = 2 that we know so well, this makes D grow to 2m+1 when n = 2m+ l; hence J2(n) = 2(2m+ l) + 1 − 2m+1= 2l + 1. Good.

(32)

Part IV

문학적 프로그래밍

(33)

Computer programs are fun to write Computer programs are fun to read.

컴퓨터 프로그램은 읽기 쉬워야 한다

소프트웨어 개발에 있어서,

프로그램

작성에 들어가는 노력은10%

나머지

90%는 이미 작성된 코드의유지보수, 디버깅, 문서화

작업

타인이 작성한 컴퓨터 프로그램은 읽기가 힘들다.

심지어 자신이

작성한 프로그램도 시간이 지나면 읽기 어려워진다.

우리는 다른 사람이 작성한 소스 코드를 보고 프로그래밍을 배운다.

프로그래밍 언어는 사람들 사이에사용되는 언어이기도 하다

컴퓨터 프로그램도 소설 처럼 읽고 즐길 수 있는 것이어야 한다.

(34)

Computer programs are fun to write Computer programs are fun to read.

Computer Programming as an Art

1974년 Donald Knuth의 ACM Turing Award 수상기념 강연 제목

좋은 프로그램은쉽게 읽고 이해할 수 있는 것어야 한다.

프로그램의효율성, 최적화만 강조하여 코드가 쓸데없이

복잡해진다면, 프로그램 읽기가 어렵게 되고, 디버그와

유지보수도 힘들어져서, 결국 그 소프트웨어의 효율은 전체적으로

낮아진다.

Premature optimization is the root of all evil (or at least most of

it) in programming.

(35)

Computer programs are fun to write Computer programs are fun to read.

문학적 프로그래밍(Literate Programming)

컴파일러가 쉽게 알아들을 수 있도록 프로그래밍 하기 보다는 사람이 쉽게 이해할 수 있도록 프로그래밍 하자. 이것이 결국은

프로그램의 효율을 높이는것이다!

컴퓨터 프로그래밍이란 컴퓨터가 해야 할 일들을 논리적이고 순차적으로 지시하는 것이 아니라, 컴퓨터가 해야할 일을 사람들에게 논리적이고 재미있게 설명하는 작업이다.

프로그래밍 언어의 문법과 규칙은 컴파일러에 적합한 것이어서 우리 사람들의 정서에는 맞지 않는다. 따라서 프로그램은 사람이

작성하고 읽기 편하도록 사람에게 적합한 구조로 재배열되어야

한다.

문학적 프로그래밍이란 사람들이 읽기 편하도록 프로그램을

재구성하여 자연스런 설명을 곁들인 프로그램 코드를 작성하는

것이다.

(36)

Computer programs are fun to write Computer programs are fun to read.

CWEB 시스템

C(C++, Java) 언어로 작성하는 문학적 프로그래밍언어, 시스템.

C 프로그램이란 CWEB의 섹션에서 C 코드 만을 뽑아내어서 컴파일러가 이해하기 쉬운 구조로 재배열한 프로그램이다.

CWEB 프로그램은 C 프로그램을 섹션으로 나눈 다음, 사람들이 이해하기 쉬운 구조로 설명을 곁들여 재배열한 프로그램이다.

CWEB 프로그램과 C 프로그램은 근본적으로 동일한 것이고, 단지

그 배열 순서만이 다르다.

(37)

Computer programs are fun to write Computer programs are fun to read.

CWEB 시스템 = CWEAVE + CTANGLE

문학적 프로그래밍이란 사람들이 읽기 편하도록 자연스런 설명과

프로그램 코드를 하나의 소스 파일에서 동시에작성하는 것이다.

CTANGLE: 웹파일의 각 섹션들에서 C 코드만 뽑아내어 C 파일을 만들어 낸다. 사람들의 기준에서 잘 정돈된(untangle) 코드를 뒤섞어서(tangle) 컴파일러가 이해 할 수 있는 코드를 생성한다.

CWEAVE: 웹파일로 부터 TEX 파일을 만들어 낸다. 소스 코드와 문서를 잘 조합하여 직물을 짜내듯이(weave) 보기 좋은 문서를 만든다.

(38)

Computer programs are fun to write Computer programs are fun to read.

CWEB 프로그래밍 시연

N개의 여왕 배치 문제

(39)

Part V

과제

(40)

과제 1

An n-digit number that is the sum of the nth powers of its digits is called an n-narcissistic number. It is also sometimes known as an Armstrong number, perfect digital invariant (Madachy 1979), or plus perfect number. For example,

153 = 13+ 53+ 33, 8208 = 84+ 24+ 04+ 84. Find all n-narcissistic number, for 3 ≤ n ≤ 39.

(41)

과제 2

(42)

과제 3

The number √ 1,√

2, . . . ,√

50are to be partitioned into two parts whos number is nearly equal; find the best such partition you can.

For example, it turns out to be possible to find the best partition of the smaller set of numbers √

1,√

2, . . . ,√ 30is

√ 2 +

√ 6 +

√ 9 +

√ 11 +

√ 12 +

√ 13 +

√ 14 +

√ 21 +

√ 23 +

√ 24 +

√ 25 +

√ 26 +

√ 27 +

√ 30

= 56.04142 25880 73351 85163 20826;

√ 1 +√

3 +√ 4 +√

5 +√ 7 +√

8 +√ 10 +√

15 +√ 16 +√

17 +√ 18 +√

19 +√ 20 +√

22 +√ 28 +√

29

(43)

References

참조

관련 문서

size 바이트만큼의 메모리 공간을 할당하며 그 시작주소를 void* 형으로 반환한다..

• 파이썬은 연산자와 동일한 결과를 산출하는 함수로서 특수 메소드의 정의를 허용한다.이 메소드들은 파이썬이 인식할 수 있도록 특별한

#define 에서 인자 사용 예제 compoundassign.c... 관계와

▪ 실세계의 객체에서 불필요한 부분을 제거하여 필요한 부분만을 간결하고 이해하기 쉬운 클래스 로 만드는 작업. ▪

Modern Physics for Scientists and Engineers International Edition,

The close substitutes are R&amp;D efforts, technologies, and goods that significantly constrain the exercise of market power with respect to the relevant

Function description 1) By turning ON FB_EN (Execution command), A/D conversion data of the specified channel is read. 2) The read A/D conversion data depends on the

(바) “액체 밀봉드럼 (Liquid seal drum)”이라 함은 플레어스택의 화염이 플레어시 스템으로 거꾸로 전파되는 것을 방지하거나 또는 플레어헤더에