랄뚜기의 코딩일기

Uncertainty Uncertainty를 고려해야 하는 이유가 무엇일까? 우리는 여태까지 fully observable한 상황에서의 circumstance에서의 data만 다루었지만 위의 내용처럼 실제의 환경은 partially observable하기 때문에 확률적으로 접근해야 한다. Making decisions under uncertainty 실제로 Decision theory = utility theory + probability theory로 정한다. 하지만 지금 배우는 내용에서는 probability theory만을 다루도록 한다. Probability Basics 다 아는 내용이다. 확률은 0과 1사이에 있고 모든 확률의 합은 1이다. Random Variables Propositions ..

A greedy approach Pi/Wi를 내림차순으로 정렬한다.(Greedy) knapsack이 찰 때까지 item을 고른다. Implementation 1 Sort the item -> O(nlogn) Repeat the choice -> O(n) O(n+nlogn) = O(n logn) Implementation 2 Put the items in a heap -> O(n) Repeat the choice -> O(k logn) O(n+k logn) = ? Implementation2 방식으로 하면 k값에 따라 시간복잡도가 달라진다. 확실한 것은 가장 최악이 O(n logn)으로 Implementation1 방식보다 훨씬 효율적이다. Knapsack Example 2: n=6, W=10 Huffma..

Condition Variables There are many cases where a thread wishes to check whether a condition is true before continuing its execution. Example: A parent thread might wish to check whether a child thread has completed. This is often called a join(). How to wait for a condition Condition variable Queue of threads Waiting on the condition An explicit queue that threads can put themselves on when some..

Design procedure Specification Formulation - Obtain a state digram or state table State Assignment - Assign binary codes to the states Filp-Flop Input Equation Determination - Select flip-flop types and derive flip-flop equations from next state entries in the table Output Equation Determination - Derive output equations from output entries in the table Optimization - Optimize the equations Tech..

Multicast Routing은 Unicast Routing을 활용한 것인데 특별한 규칙이 있는 것이 아니라 주먹구구식으로 구현을 했기 때문에 학부과정에서 깊게 배우기는 매우 힘들다. 따라서 개념 정도만 간단히 외우도록 하자. Unicasting In unicasting, there is one source and one destination network. The relationship between the source and the destination network is one to one. Each router in the path of the datagram tries to forward the packet to one and only one of its interfaces. Unicast에서..

D flip flop Moore model circuit Equation D1 = q1q2'+xq1' D2 = xq1 z = q2' 회로를 보면 x값이 직접적으로 z와 연결되어 있지 않다. 따라서 현재의 input에 영향을 받지 않으므로 Moore circuit이다. For next state q*=D q1* = D1 q2* = D2 JK flip flop Moore model circuit Equation JA = x, KA = xB' JB = KB = x + A' z = A + B A B x Ja Ka Jb Kb A* B* 0 0 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 1 1 ..

CLR parsing SLR 방법보다 강력하다는 장점 lookahead를 구하는 과정이 복잡하고 시간이 오래 걸리며 parse table이 크다는 단점 LALR(Look ahead LR) parsing LR(1)과 같이 reduce action에서는 lookahead를 이용 Parsing table의 크기를 되도록 작게 구성 Strengths SLR 방법보다 강력 parse table의 크기가 CLR 방법보다 작음 프로그래밍 언어의 구문 구조를 대부분 편리하게 표현할 수 있음 모호하지 않은 문맥자유 문법으로 표현된 거의 모든 언어를 인식 에러를 초기에 탐지 가능 Weaknesses parse table을 만들기 위해 lookahead 기호를 구하는 것이 어려움 LALR Parser Implementati..

Lock-based Concurrent Data structure Adding locks to a data structure makes the structure thread safe. How locks are added determine both the correctness and performance of the data structure. 여기서 알아두면 좋은 것은 correctness와 performance가 trade off 관계에 있다는 것이다. Example : Concurrent Counters without Locks typedef struct __counter_t{ int value; pthread_lock_t lock; } counter_t; void init(counter_t *c){..

Locks : The Basic Idea Ensure that any critical section executes as if it were a single atomic instruction. Add some code around the critical section lock_t mutex; // some globally-allocated lock 'mutex' ... lock(&mutex); balance=balance+1; unlock(&mutex); Lock variable holds the state of the lock available (or unlocked or free) No therad holds the lock acquired (or locked or held) Exactly one t..

Intractable은 아주 다루기 힘든이란 뜻으로 Intractable Problem이란 말 그대로 풀기 힘든 문제라는 뜻이다. 문제 P에 대한 효율적인 알고리즘은 발견 되지 않았지만, 그 문제가 많은 시간을 필요로 한다는 것을 증명한 사람도 없었다. 문제 P에 대한 exponential time algorithm 이 있지만 아무도 polynomial time algorithm을 찾을 수 없었고, P에 대한 exponential time algorithm이 존재하지 않음을 증명 할 수 있다. exponential time alogrithm 이 발견된 문제 중 가장 어려운 문제 그룹인 NP-Complete이 있는데 이 그룹의 문제에 대한 Polynomial time algorithm을 발견하면 expon..