7-2강 - Greedy Algorithm 2 (Scheduling)

4. Minimizing Total Time in the system

 

0) 문제 소개

j1~jn : job

t1~tn : job 소요 시간

w1~wn : 각 job을 하기 전에 기다리는 시간

1) Algorithm

정렬하고 실행 시간이 짧은 것 먼저 시작한다.

 

2) Multiprocessor Scheduling

processor가 여러개 있어도 마찬가지로

실행 시간이 짧은 것부터 각 processor에 job을 할당합니다.

 

5. Scheduling with Deadlines

0) 문제 소개

d1~dn : deadline

p1~pn : 각 job 별로 d1~dn 안에 job을 완료하면 p1~pn이라는 이득을 얻는다.

S : job들의 부분집합

feasible set : S의 모든 job들을 deadline 안에 끝낼 수 있을 때, S를 feasible set이라고 한다.

feasible sequence : feasible이 가능하게 S의 job들을 나열한 sequence

profit이 큰 것부터 실행

1) 알고리즘

(정렬되어 있는 상태)

profit이 가장 큰 것부터 작은 순으로 K에 추가했을 때 feasible한지 check

K가 feasible하면 S에 추가 (아니면 K는 다시 J에 i+1를 추가한 것으로 돌아간다.)

 

cf> 일반적인 greedy를 증명하는 법

...

 

6. Huffman

0) prefix code

앞부분부터 비교해서 각 code가 다른 것

b는 (a, c)와 다르다. (0 vs 1)

a는 c와 다르다. (10 vs 11)

 

1) Huffman Algorithm

0> Huffman Tree 관련 정의할 것

v1~vn : 각 character를 의미

T : binary tree

bits(T) : T의 bit 기댓값

frequency(vi) : vi의 사용 빈도

depth(vi) : T에서의 depth (각 code의 length이기도 합니다.)

 

1> 자료구조 : min heap PQ

(frequency 기준으로 min heap)

 

2> Algorithm

[1] min heap : PQ에서 frequency 작은 것 2개(p, q) 뽑고

[2] Tree : frequency 합친 것(r)을 root로 하고 p와 q를 left, right로 한다.

[3] min heap : 합친 것을 다시 PQ에 insert

 

3> example