mojo's Blog

※ Control Flow Processors 은 오직 한가지 일을 한다. 시작부터 종료까지 CPU는 일련의 명령을 한 번에 하나씩 읽고 실행(해석)한다. 이러한 sequence 는 CPU의 control flow 라고 한다. 다음과 같이 startup 부터 shutdown 까지 n 개의 instruction 이 존재한다고 할 때, 시간이 지날때 마다 instruction_1 부터 시작하여 instruction_n 까지 실행되는 것을 알 수 있다. ※ Altering the Control Flow control flow 를 변경하는 두가지 메커니즘이 존재한다. Jumps and branches Call and return 위 메커니즘으로 program state 의 변화에 대응한다. 유용한 시스템 부족으..

Approximate Salesman traveling salesman (tsp) Input: \(A_{n}\) n × n matrix \(d_{ij}\) ≥ 0 Output: A cyclic permutation π that minimizes \(\ c(\pi ) = \sum_{i=1}^{n}d_{i, \pi (i)}\) π : {1, · · · , n} → {1, · · · , n} is a permutation where π(i) denotes i’s successor. traveling salesman (threshold) Input: \(A_{n}\) n × n matrix \(d_{ij}\) ≥ 0 and a number l Question: Is there a cyclic permutatio..

Claim: S is not much larger than the optimal vertex cover Sopt . S가 최적의 vertex cover Sopt 보다 더 크지 않다고 한다. 왜 그런지 알아보도록 한다. Note first that |S| = 2k where k is the number of edges that our algorithm pebbled. Since k edges have no vertices in common, and since each one has at least one endpoint in Sopt , we have |Sopt | ≥ k. Thus, S is at most twice as large as Sopt , 여기서 k는 앞에서 사용했던 알고리즘으로 조약돌을 놓은 ..

Various Costs for a Graph G = (V, E) 임의의 정점 u, v 가 존재할 때 u에서 v로 가는 경로를 찾을때, Adjacency list : O(|V| + |E|), 정점을 전부 탐색하면서 연결된 간선들을 탐색한다. Adjacency matrix : O(|V|^2), 서로 연결된 경우가 1이므로 1인 경우를 모두 탐색한다. Prim's Minimum Spanning Trre Algorithm Idea – In each step, find and add an edge of the least possible weight that connects the (current) tree to a non-tree vertex. Algorithm 꼭짓점들의 집합을 partition 하는 방식이다..

Code Generation 연산 레지스터가 여러 개인 경우: ● 구문 트리를 만들 때 각 노드의 부분 트리를 계산하는 데 필요한 레지스터의 수 를 먼저 계산한 다음 표시. 레지스터의 수를 label로 가진 구문 트리에서 목적 코드를 생성해낸다. ● 이 방법을 통해 STORE연산이 필요하지 않기 위한 레지스터의 수를 구할 수 있다. ● 레지스터의 수를 때때로 A. Ershov 수(Ershov number)라 부른다. 식 E를 계산하는 데 필요한 레지스터의 수를 CR(E)로 표시하면 [알고리즘]에 의해 구문 트리로부터 CE(E) 값을 구할 수 있다. Label을 붙이는 순서는 터미널 노드에서 루트 노드로 진행하며, 필요한 레지스터의 수가 큰 쪽의 부분 트리부터 목적 코드로 변환해가면 된다. [알고리즘] 레..

인접 행렬을 이용한 다익스트라 알고리즘을 구현한 코드이다. Solution Code /* Dijkstra's algorithm for a digraph in adjacency matrix */ #include #include void create_graph(void); void display(void); int find_path(int, int, int*, int*); #define MAX 4096 #define TEMP 0 #define PERM 1 struct node { int predecessor; int dist; /*minimum distance of node from source*/ int status; }; int n, adj[MAX][MAX]; void main() { int i, sou..