랄뚜기의 코딩일기

Basic logic library이다. 암기하도록 하자. Exclusive-OR연산이다. 비교 연산이 같으면 0 다르면 1을 나타내는 연산이다. Exclusive-OR 연산의 특징이다. X⨁1=X'이 되는 것과 (X⨁Y)'=X⨁Y'=X'⨁Y=XY+X'Y' 인 것을 기억하면 될 것 같다. (a⨁b)=a'b+ab' , (a⨁b)'=a'b'+ab 로 표현할 수 있다. 따라서 위와 같은 논리회로로 표현할 수 있다. Binary Adder and Subtracters 두 개의 Binary 수를 더할 때, 같은 자리에 위치한 X,Y가 더해진다고 하자. 더해질 수 있는 요소는 X,Y 그리고 한 자릿수 밑에서 발생 할 수 있는 Cin까지 총 3가지이고 발생하는 결과는 Sum과 2를 초과할 경우 발생하는 Cout이 있..

Types of Errors bit들이 다른 포인트로 이동할 때, interference에 의한 예측할 수 없는 변화에 노출된다. interference는 신호의 모양을 바꾼다. single-bit error는 주어진 bits에서 한 개의 bit만 바뀐 것을 의미한다. burst error는 2개 이상의 bits들이 변화한 것을 의미한다. Redundancy Error를 detecting 하거나 correcting 하는 것의 central concept은 redundancy(중복)이다. 에러들을 감지하거나 바로 고치기 위해서는 추가적인 bits나 data를 보내야 한다. 이런 redundants들은 sender에게서 만들어지고 remover에게서 제거된다. redundants들은 잘못된 bit들을 rec..

Memory Virtualiziation OS는 physical memory를 가상화한다. OS는 각각의 프로세스에 가상 메모리 공간을 제공한다. 각각의 프로세서에게는 자기가 모든 메모리를 사용하는 것처럼 보인다. Process structure: struct thread switch from user stack to kernel stack을 할 때 raise privilege level도 같이 해줘야 한다. Motivation for Virtualization Uniprogramming : 한 프로세스만 그 시간에 돈다. p1과 p2가 가상 메모리를 위와 같이 할당받았다고 했을 때, 실제 physical memory에서 kernel영역을 공유하고 있고 user영역은 따로 사용하고 있다. Abstract..

Merge Sort Divide - merge sort에서 배열을 divide하는데 필요한 시간은 O(1)이다. (이미 배열의 index를 알고 있기 때문에) Conquer - 각각의 subarray를 recursive하게 sorting한다. T(n) = 2T(n/2)+cn Combine - 각각의 subarray를 merge하면서 sorted array로 바꿔준다. O(n) void merge_sort(int *n, int left, int right){ int middle; if(left

Context-free Grammar Context-free Grammar는 Chomsky hierarchy에서 생성 규칙의 왼쪽은 논터미널 기호 하나로 이루어져있고 오른쪽 부분은 문자열인 것을 말한다. Parse Tree Leftmost derivation : 유도 과정의 각 단계에서 sentential form의 가장 왼쪽에 있는 nonterminal symbol를 replacement하는 경우 Rightmost derivation : 유도 과정의 각 단계에서 sentential form의 가장 오른쪽에 있는 nonterminal symbol를 계속해서 replacement하는 경우 Left parse : leftmost derivation에 의해서 사용된 생성 규칙 순서 Right parse : r..

Nodes and Links data-link layer에서의 communication은 node-to-node이다. 데이터는 목적지까지 가기 위해 많은 네트워크(LANs and WANs)를 거쳐야 한다. LANs와 WANs는 router로 연결되어있다. 우리는 보통 두 host와 router들을 node라 하고 그 사이의 network를 link라고 한다. Services Data-link layer는 physical 그리고 network layer사이에 위치한다. Data-link layer는 network-layer에 서비스를 제공하고 physical layer에게서 서비스를 받는다. Two Categories of Links 두 개의 node가 cable이나 air로 physically conne..

Lexical Analysis 소스 프로그램을 token 단위로 분리하여 토큰 스트림을 출력한다. Token Token은 터미널 기호들로 구성된 문법적으로 의미 있는 최소 단위이다. Special form - language designer - 예약어(Reserved word) : for, if, int 등의 언어에 이미 정의된 단어 - 연산자(operator) : +,-,*,/, a|b|c|....|Y|Z digit (d) -> 0|1|2|...|9 Recognition of Reserved Words C에서 예약어를 만드는 방법은 identifier를 만드는 방법과 동일하다. identifier인지 먼저 검사하고 별도 표에 기록되어 있는 reserved word와 비교한다. 매칭되는 것이 있으면 해당..

Max(Min) Heap Definition 정의 1 : max(min) heap은 internal node(child node가 존재하는 node)가 그들의 children보다 작지(크지) 않은 완전이진트리를 말한다. 정의 2 : root node가 각각의 child 보다 작고(크고) 각각의 child를 root node로 갖는 subtree들은 max(min) heap 의 특징을 가지고 있다. max(min) heap은 max(min)heap 특징을 지닌 완전이진트리이다. Priority Queue는 insert와 delete가 모두 O(log n)으로 insert와 delete가 모두 빈번하게 나오는 경우 훨씬 효율적이다. Heap Sort 방법 1. 배열 n의 정렬되지 않은 요소들을 max hea..

Canonical Forms - Minterm Minterm은 위 처럼 3개의 변수로 이루어져 있을 때, 그들의 곱(and) 연산으로 이루워지게 되고, 2^3으로 8개가 나오게 된다. 그리고 각각의 minterm에 notation을 붙이게 된다. F1(Sum of minterms)인 경우에는 1이 나오는 경우이므로 1-minterms라고 하고 F1'은 0이 나오는 경우이므로 0-minterms라고 한다. 당연히 둘은 complement하다. 그리고 F1은 합(or)연산으로 이루어져 있기 때문에 1-minterms로 모든 Boolean function을 표현할 수 있다. Canonical Forms - Maxterm Maxterms은 Minterms와 다르게 변수들의 합(or)연산으로 이루어져있다. Max..

Multiprocessor Scheduling Multicore processor의 등장으로 multiprocessor-scheduling이 필요하게 되었다. 우리는 threads를 활용하여 여러 개의 CPU들에 jobs을 schedule 해주어야 한다. Single CPU with cache Cache에는 main memory에 있는 popular data들을 복제하여 저장해놓는다. Cache는 Main Memory에 비해 접근이 빠르다. Cache coherence CPU 0과 CPU 1이 data D를 다룬다고 할 때, 각각의 cache들은 private한 성질을 가지고 있으므로, CPU 1은 update 된 D'가 아닌 D를 가져오게 된다. 따라서 CPU에서 update data를 cache에서 ..