mojo's Blog

We explore the relationship between decision problems and their optimization versions. For most, the optimal solution can be found in polynomial time if and only if the decision version can be also. 이번에 배울 내용은 decision problem과 optimization version 사이의 관계를 알아가는 부분이다. optimal solution은 decision version이 polynomial time에 속하게 될 경우 발견된다고 한다. For computationally intractable problems, we will study ap..

Kruskal’s Minimum Spanning Tree Algorithm • Idea – Finds an edge of the least possible weight that connects any two trees in the forest. forest 내에서 두 개의 tree로 연결되어진 가중치가 최소가 되는 간선것을 찾는 아이디어를 활용한다. 즉, Disjoint-Set 을 이용하여 해결해야 한다. • Implementation using disjoint-set data structure 0. A 는 초기에 empty set으로 간선(u, v) 을 담기 위한 용도로 사용된다. 1. 먼저 MAKE-SET 함수를 통해 각 정점별로 자기 자신을 가르키도록 하도록(parent[v] = v) 설정한다. 2..

Machine-dependent Optimization 기계 종속적 최적화 기법Machine-dependent Optimization ● 기계의 특성에 따라 달라질 수 있음 ● 중복 명령어 제거, 효율적인 명령어 선택, 레지스터 할당과 배정, 명령어 스케줄링 등이 있음 중복 명령어 제거 ● 핍홀 최적화 기법에서 사용하는 것과 동일 ● 중복되는 로드 명령문이나 저장 명령문을 제거함으로써 최적화하는 방법 효율적인 명령어 선택 ● 동일한 기능을 가진 더 효율적인 명령어로 대치함으로써 최적화하는 방법 ● ex) 소스코드 x = x + 1에 대한 명령어는 다음과 같다: LOAD R1, x ADD R1, 1 STORE x, R1 컴퓨터가 레지스터나 메모리에서 1을 증가시키는 INC(increase) 명령어를 가질 ..

When Maximizing is Harder than Minimizing We showed previously that min cut is in P. How about max cut? max cut Input: A weighted graph G and an integer k. Question: Does there exist a cut in G of weight k or greater? 몇주전에 min cut이 P에 속한 것을 확인하였다. (Duality, Reduction :: M - J - C (tistory.com)) max cut 은 P 에 속하는지 NP 에 속하는지에 대해서 알아보도록 한다. We will reduce nae-3-sat to unweighted max cut where every..

Directed Acyclic Graph (DAG) 자료 흐름 분석이 완료된 후 기본 블록에 대한 코드를 생성할 때, 각 블록에 대해 DAG(directed acyclic graph) 생성하여 활용한다. ● DAG는 값이 어떻게 계산되는지를 그림으로 나타내준다. ● DAG는 주로 블록 내부에서 사용되지만, 블록 외부에서 어떤 문장이 그 문장에서 계산한 값을 사용하는지 알아볼 수 있으므로 매우 중요하다. DAG는 모든 산술식에 대한 노드를 가진다. ● 내부 노드(interior node)는 연산자를 나타내고 그 자식 노드는 피연산자를 나타낸다. ● 터미널 노드는 id나 constant이고 중간 노드는 연산자이다. ● 노드 옆에 여러 개의 id를 놓을 수 있으며, 이는 노드의 계산 결과를 이 id들이 공유함..

What on-disk structures to represent files and directories?  - Contiguous, Extents, Linked, FAT, Indexed, Multi-level indexed  - Which are good for different metrics?  What disk operations are needed for:  - make directory, open file, write/read file, close file on-disk structures : disk 상에 있는 구조체로 file, directory를 나타내기 위한 용도다. contiguous, extents, linked, fat, indexed, multi-level indexed 등..