中庸 中庸

앞선 Dijkstra 알고리즘이나, Bellman-Ford 알고리즘은 하나의 Source 에서 다른 모든 vertex 들 간에 shortext path를 구하는 알고리즘입니다. 이와 같은 문제를 single-source shortest path problem 이라고 합니다. 단일 source 가 아닌 임의의 모든 두 vertex u, v 에 대해 u에서 v로의 shortest path를 구하는 문제를 all-pairs shortest path problem 이라고 합니다. Directed Graph G = (V, E) 가 (undirected graph의 경우 bellman-ford 알고리즘과 같은 방법으로 directed graph로 변환하여) negative cycle이 없는 경우 G에서 all-pa..

Shortest Path 를 구하는 대표적인 Alogorithm 으로는 Dijkstra Algorithm 이 있었습니다. Dijkstra 알고리즘의 key lemma 는 다음과 같았습니다. Dijkstra Algorithm 에서 (아직 방문 안 한 vertex 들 중) vertex s 에서부터의 shrotest path 길이가 가장 짧은 vertex 를 v라 하면 그 길이는 실제 s에서 v로의 shortest path 길이와 같다. 위 key lemma 는 weight 가 negative 인 edge 가 존재할 경우 성립하지 않습니다. 그 이유는 다음과 같습니다. 그렇다면 negative edge 가 있는 경우에도 동작하는 Shortest path 를 구하는 Algorithm은 무엇이 있을까요? The ..

저번에 다룬 Problem 개념을 재정의하겠습니다. Problem Instance 는 일종의 binary string 이라고 생각할 수 있습니다. (Instance 가 Binary Code로 전환되었다고 생각합시다.) Problem 을 다음과 같이 재정의하도록 하겠습니다. Problem : 어떤 조건을 만족시키는 ( = YES 라 답하는 ) Problem Instance 들의 set. 그러므로, Problem 에 속한 Instance 는 모두 YES Instance가 됩니다. 어떤 Problem X 에 대해 어떤 mapping A 가 임의의 s ∈ X 에 대해 A(s) = YES이고, 역도 성립할 경우 A를 Problem X를 해결하는 Alogrithm 이라고 합니다. 이제 NP - Completenes..

3-SAT Problem 을 Independent Set Problem 으로 Reduction 하는 과정에 대해 살펴보도록 하겠습니다. 본론에 들어가기 앞서 문제를 이해하기 위한 개념들을 살펴보도록 하겠습니다. Definition Literal : Literal 은 Boolean variable xi 나 그 부정 (negation) ¬xi 을 의미합니다. Clause : Clause 는 literal 들의 disjunction (논리합 ∨) 을 의미합니다. Conjunctive Normal Form : Conjuctive Normal Form은 clause 들의 conjunction (논리 곱 Λ) 으로 표현된 proportional formula (명제 식) 을 뜻합니다. (x1 ∨ x2 ∨ ¬ x4 ..

프로그래머에게는 메모리에 대한 이해가 중요합니다. 메모리에 대한 이해가 중요한 이유는 다음과 같습니다. 메모리는 무한한 자원이 아닙니다. 메모리 참조 버그는 매우 치명적입니다. 버그의 영향이 시공간적으로 동떨어져서 발견되고, Run-time 에 버그가 발생하는 경우 실제 세계에서 큰 손실을 초래할 수 있습니다. 메모리의 성능은 일정하지 않습니다. CPU 와 가까운 메모리공간인 Cache는 속도가 빠르지만, Memory 나 Auxillary Memory는 Cache보다 속도가 느립니다. 따라서 메모리 시스템의 특성을 잘 반영하는 프로그램을 디자인해야 만족스러운 성능을 얻을 수 있습니다. 그냥 코드를 짜면, 컴파일러가 알아서 메모리를 고려하여 컴파일 해주는데 왜 동적 메모리를 사용하고 관리하는 법을 알아야할..

Independent Set Problem과 Vertex Cover Problem 에 Polynomial-Time Reduction 을 적용해보겠습니다. 먼저 Vertex Cover 의 정의부터 알아보겠습니다. Definition of Vertex Cover Graph G = (V, E) 에 대해 G의 모든 edge 들의 endpoint 를 적어도 하나 이상 포함하는 vetex set S ⊂ V 을 G 의 Vertex Cover 라고합니다. 즉 어떤 Vertex Set 이 Vertex Cover 라면 ∀ (i, j) ∈ E 에 대하여 i ∈ S or j ∈ S 가 성립합니다. 위의 그래프에서 {1,2,3,4,5,6} 은 Trivial 하게 G의 Vertex Cover입니다. {2,5,4} 도 G의 Ver..

어떤 Algorithm 이 polynomial - time 에 동작하는 경우 즉, O(n^d) 에 동작하는 경우에 해당 알고리즘을 보통 Effecient Algorithm 이라고 합니다. 보통의 경우, 어떤 문제를 해결하는 Efficient Algorithm 을 찾기 위해서는 그 문제를 polynomial time 에 동작하는 reduction 이 가능한지를 생각하며, 이를 polynomial-time reduction 이라고 합니다. Polynomial Time Reduction 의 정의를 살펴보겠습니다. Definition of Polynomial Time Reduction Decision Problem X 에서 Decision Problem Y 로의 Polynomial Time Reduction 은..

그래프 G(V,E) 의 Independent Set 을 구하는 문제는 Cliques 를 구하는 문제로 reduction 할 수 있습니다. 먼저 Indepedent Set 과 Clique 의 정의에 대해 알아보도록 하겠습니다. Definition of Indepedent Set Graph G(V, E) 에 대해 Vertex set V’ ⊂ V 에 속한 모든 vertex 들이 서로 adjacent 하지 않으면 V’ 은 G 의 independent set 입니다. ( ∀ i, j ∈ V', (i, j) ∉ E 이면 V' 은 그래프 G의 Indepedent Set ) Definition of Clique Graph G(V, E)에 대해 Vertex set V’ ⊂ V 에 속한 모든 vertex 들이 서로 adj..