mojo's Blog

Problem – Let J = {1, 2, …, n} be a set of jobs to be served. – Each job takes one unit of time to finish. – Each job has a deadline and a profit. • If the job starts before or at its deadline, the profit is obtained. ➢ Schedule the jobs so as to maximize the total profit (not all jobs have to be scheduled). 예를 들어서 다음과 같은 Job(Deadline, Profit)이 4개 존재한다고 하자 이때, 최대 이익을 낼 수 있는 경우는 job = [4, 1] 인 경우..

Intermediate code는 ● semantic analysis 단계에서 만들어진 syntax tree를 이용하여 생성되거나, ● 문법 규칙이 reduce 될 때마다 syntax-directed translation으로 생성된다. ● intermediate code를 생성하는 데는 intermediate language를 사용한다. 컴파일러의 frontend와 backend를 연결해주는 기능을 한다. Intermediate Code 생성 방법 ● intermediate code generator (ICG)를 이용 ○ 파스 트리 또는 구문 트리를 순회하면서 효과적인 intermediate code를 생성 ● syntax-directed translation (SDT) 방법 ○ CFG의 각 생성 규칙에..

Hard Disk Drives Hard drive 의 특성을 이해해야 내부적으로 어떻게 돌아가는지에 대해 알 수 있다! Base Geometry hard drive를 옆에서 본 측면이다. platter가 3개 있고 platter 위아래 부분은 surface 이다. (density를 높이기 위해 아래에도 있음) arm이 왔다 갔다하고 위아래에 존재함 예를 들어 foo파일이 첫번째 platter에 있다면 6개의 Disk head가 병렬적으로 센싱하지 않는다. => 하나만 active 상태가 되서 파일을 찾아감 (controller가 다 잡을 수 없기 때문 + 충분히 빠른 이유) 이번엔 위에서 본 hard drive 이다. Arm이 왔다 갔다 하고 Sector가 512 byte로 존재한다. 읽거나 쓸 때 51..

Maximum Non-overlapping Intervals 이전에 Earliest finish first 방법이 가장 그럴듯 해 보인 방법임을 확인하였다. 따라서 이에 대한 알고리즘을 알아보도록 한다. Greedy algorithm Input : A = {a1, a2, ..., an} with ai = [si, fi] for 0 ≤ si S = S ∪ {aj}, k = j, aj를 담아주고 담아준 인덱스 j를 k에 넣어준다. (j..

Semantic Analysis: ● Syntax tree와 symbol table을 이용하여 소스 프로그램이 언어 정의에 의미적으로 (semantically) 일치하는지 검사 ● identifier가 프로그램 내의 수식과 문장에서 해당 언어의 type 규칙에 따라 올바르게 사용되고 있는지를 검사하는 data type checking 수행, 그 결과를 syntax tree 혹은 symbol table에 저장 의미 분석기(semantic analyzer)가 수행 ● 입력: ○ parsing으로 얻은 parse tree 또는 syntax tree ● 출력: ○ Semantic analysis가 이뤄진 parse tree 또는 syntax tree ○ Syntax directed translation을 이용하..

Integer partitioning 어떻게 해결해야 할지에 대한 접근법을 들어보자. 1. Greedy strategy 예를 들어 S = {4, 5, 6, 7, 8} 가 있을 때, Greedy strategy 로는 solution을 찾을 수 없다. 2. Dynamic programming To solve an instance of subset sum, need to calculate f(1, t). Note that f(j, t) = f(j + 1, t) or f(j + 1, t - xj). The boundary condition is f(l, t) = true if t = 0 or t = xl and false otherwise. The running time is propotional to the ..