mojo's Blog

Semaphore: A definition #include sem_t s; sem_init(&s, 0, 1); // initialize s to the value 1 int sem_wait(sem_t *s) { decrement the value of semaphore s by one wait if value of semaphore s is negative } int sem_post(sem_t *s) { increment the vlaue of semaphore s by one if there are one or more threads waiting, wake one } sem_t 에 대한 객체 s는 integer value 를 가지고 있으며 sem_wait(), sem_post() 으로 조작이 가능하다..

Theorem 1 A 2-sat formula φ is satisfiable if and only if there is no variable x with paths from x ~> x' and x' ~> x in G(φ). Proof : If such a pair of paths exists, then φ is contradictory, and hence unsatisfiable. Suppose then that no such pair exists. Observe that a single one of these paths does not cause a contradiction. x ~> x', x' ~> x 에 대한 경로가 두 개 존재할 경우 즉, x에서 x'으로 가거나 x'에서 x으로 여러번 걸쳐 지..

0-1 Knapsack Example 2: n = 6, W = 10 알고리즘 별로 획득되는 이익이 다른것을 알 수 있다. 위 예제에서 그나마 좋은 알고리즘이 greedy 알고리즘인데 이 중에 최대 이익을 뽑아낼 수 있는 알고리즘을 활용하여 O(nlogn) 의 효율을 뽑아서 이익을 뽑도록 한다. The Greedy Methods A technique to follow the problem-solving heuristic of making the locally optimal choice at each stage. ※ Strategy - 매 순간마다 가장 최선인 것을 선택하는 방법이다. - 즉, locally optimal를 선택함으로써 globally optimal을 도달하려는 것이 궁극적인 목표이다. ※ ..

LALR Parser Implementation 1. 파싱표를 구성하기가 쉽지만 파싱표의 크기가 커지는 LR(1)을 가지고 구성 ● 같은 코어를 가진 LR(1) item을 묶어서 하나의 state로 구성 2. 효율적으로 파싱표를 구성할 수 있는 LR(0)과 lookahead를 가지고 구성 ● LR(1) item의 lookahead를 합한 것으로 구성 Example : LALR parse table을 구해보도록 하자. P: S -> CC C -> cC C -> d I3, I6는 같은 코어이므로 lookahead 를 합친다. I36 = {[S → c•C, c/d/$], [C → •cC, c/d/$], [C → •c, c/d/$]} I4, I7는 같은 코어이므로 lookahead 를 합친다. I47 = {[C..

Condition Variables There are many cases where a thread wishes to check whether a condition is true before a continuing its execution. 예를 들어서 부모 쓰레드가 자식 쓰레드가 완료되었는지 아닌지에 대한 점검하는 것으로 이를 보통 join() 이라고 부른다. 다음 코드를 보도록 하자. #include #include #include #include void *child(void *arg) { printf("child\n"); return NULL; } int main(int argc, char *argv[]){ printf("parent : begin\n"); pthread_t c; pthread_c..

Modular factorial Input: Two n-digit integers x and y Output: x! mod y 언뜻 보기에 modular exponentiation과 같다. 이 문제는 P에 속하는 문제일까? Claim : factorization ≤ modular factorial (in the sense that we can solve factorization by calling a subroutine for modular factorial a polynomial number of times.) factorization는 modular factorial로 인해 감축될 수 있다고 한다. gcd(x!, y) = 1 라는 fact를 이용하여 P에 속함을 증명해보도록 하자. (x < d, d는..