랄뚜기의 코딩일기

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

Search vs Planning milk, bananas 그리고 cordless drill을 가져오는 임무가 있다고 하자. Standard search algorithms은 아마 fail 할 것이다. Planning systems do the following: open up action and goal representation to allow selection divide-and-conquer by subgoaling relax requirement for sequential construction of solutions Planning as state space search Planning as a search problem : search from the initial state through ..

Internet에서의 Unicast routing은 hierarchical routing을 사용해야만 한다. General Idea In unicast routing, a packet is routed, hop by hop, from its source to its destination by the help of forwarding tables. The source host needs no forwarding table because it delivers its packet to the default router in its local network. The destination host needs no forwarding table either because it receives the packet f..

위는 각각의 layer마다 적용되는 protocol의 종류이다.(모두 외우기) Network-Layer Protocols Network layer는 하나의 main protocol 그리고 3개의 부수적인 protocol로 생각되어질 수 있다. Main protocol은 IPv4로 packetizing, forwarding 그리고 packet의 delivery에 책임이 있다. ICMPv4는 IPv4가 delivery과정에서 발생하는 error를 다룰 수 있게 해준다. IGMP는 IPv4가 multicasting하는 것을 돕는다. ARP는 address mapping을 하는데 쓰인다. 여기서 강의자료에서는 ARP가 Network layer에서 이뤄진다고 했지만, 교수님께서는 Data-link에서 이뤄진다고 ..

FOL to PL FOL(First order logic)을 inference하기 위해서는 PL(Propositional logic)으로 바꿔줘야 한다. Propositional inference를 할 때 Ground sentence를 이용한다. 위 처럼 variable이 없는 sentence를 Ground setence라고 하고, ground atomic setence를 propositional symbol로 보면 된다. Universal Instantiation (UI) Rule 만약 ∀v ɑ 라는 FOL을 PL로 바꾼다고하자. 그렇다면 식은 아래와 같다. 위의 식이 의미하는 것은 ɑ에다가 v(variable) 대신에 g(ground term)을 넣으라는 뜻이다. SUBST(𝝷,ɑ) = ɑ𝝷 : th..

Packetizing Network layer의 첫번째 임무는 packetizing이다. payload를 encapsulate해주고 목적지에서는 payload를 decapsulate해준다. Network layer는 payload를 변형되지 않게 옮기는 것이 목적이다. Routing and Forwarding network layer의 또 다른 목적은 routing과 forwarding이다. Packet Switching From the discussion of routing and forwarding, we infer that a kind of switching occurs at the network layer A router is a switch that creates a connection betw..

Sequential systems ( finite state machine ) systems with memory Output depends on present input and past history Synchoronous systems Clock signal regulates input, internal, and output signal Clock Alternating sequence of 0 and 1 at a regular rate Two kinds : 0 and 1 in same length, 0 longer than 1 Clock period T = 1/clock_rate Moore machine Moore machine은 현재의 Input이 아니라 과거의 input에만 영향을 받는다. 첫번째..

thread : Used to interact with this thread. attr : Used to specify any attributes this thread might have. Stack size, Scheduling priority,... start_routine : the function this thread start running in arg : the argument to be passed to the function (start routine) a void pointer allows us to pass in any type of argument 만약 start_routine 대신에 다른 type argument가 필요하다면 declaration은 위와 같을 것이다. thread :..

Thread란 single running process를 위한 새로운 abstraction이다. Multi-threaded program Multi-threaded program은 한 개 이상의 execution을 가진다. Multiple PCs (Program Counter) Thread들끼리 같은 address space를 공유한다. 각각의 thread들은 고유의 PC(Program Counter)와 register들을 가지고 있다. 여러개의 TCB(thread control block)이 각각의 thread의 상태를 저장하기 위해 필요하다. 만약 T1에서 T2로 switching된다면 T1의 register state는 저장이되고 T2의 register state가 restore될 것이다. addr..

Implementing LRU Algorithm Counter implementation 모든 page table에는 counter가 있다 page는 entry를 통해서 참조 되고, counter에 clock을 복사한다. clock은 memory에 참조가 일어날 때마다 증가한다. page가 replace 되야할 때, counter를 확인하여 어떤 page가 replace 될 지 결정한다. Stack implementation doubly linked list 형식으로 page number를 stack으로 만든다. page가 참조 될 때마다 해당 page number를 stack의 top에 올려놓는다. 즉, top이 most recently used가 되고 bottom이 LRU가 된다. update하는데 ..