랄뚜기의 코딩일기

일반적으로 Time-complexity가 polynomial이면 efficient하다고 하고, Exponential이면 inefficient하다고 정의한다. 하지만 실제로는 cubic만 되도 Time-complexity가 엄청 늘어나므로 실질적으로는 거리가 멀다. Worst-Case versus Average-Case Time Complexity Worst-case complexity란 말 그대로 모든 경우가 다 일어나고 끝나는 경우이다. Average-case complexity는 평균적으로 걸리는 시간 복잡도이다. Quick sort를 예로 들자면, Worst-case complexity는 O(n^2)이고 Average-case complexity는 O(nlogn)이다 g(n)은 이해하였으니 넘어가도..

combinational systems combintaional circuit을 만들 때, behavioral forms, structural components, physical objects로 나눌 수 있다. Logical operations 논리 연산에는 AND( * ), OR( + ), NOT( ~ )이 있다. NOT은 문자 위에 ( - )를 하거나 옆에( ' )를 하여 표현 할 수도 있고 AND 연산자는 생략이 가능하다. 위 Truth Table을 Logic Diagram으로 표현하면 위와 같다. 여기서 조심해야 할 것은 Truth Table은 한 개 밖에 나올 수 없지만, Logic Diagrams은 여러가지가 나올 수 있다는 것이다.(한 Truth Table에 여러가지 Logic Diagra..

Chomsky hierarchy 1번 유형을 CSL(context-sensitive language), 2번 유형을 CFL(context-free language) 마지막으로 3번 유형을 RL(regular language) Regualr expression Regular expression은 union,star,concatenation 모두 가능하다. regular expression을 할 때 주의 할 점은 concatenation은 교환법칙이 성립하지 않는다는 것이다. Syntax chart BNF(Backus-Naur Form) EBNF(Extended BNF)

Running programs에 limits를 두지 않는다면 OS는 그저 library에 불과하다. Recap : Process Creation 1. 프로그램 코드를 memory와 process의 address space에 저장해준다. 2. 프로그램의 run-time stack이 할당된다. - 스택을 local variables, function parameters, return address를 저장하는 데 사용한다. - main함수의 argc,argv로 stack을 초기화한다. 3. 프로그램의 heap을 만든다. - 명시적으로 선언된 동적할당된 데이터를 위해 사용된다. - malloc과 free가 필요하다. 4. OS가 다른 일을 한다. - (I/O) setup 5. 프로그램을 실행한다.(main())..

Order of Algorithms

Tree search algorithm tree search는 방문한 곳을 또 방문하기 때문에 무한루프를 돌 가능성이 높다. Graph search algorithm graph search는 방문한 곳을 closed list나 explored set을 이용하여 저장한다. 때문에 무한루프를 돌 일이 없다. Best-first (graph) Search 위의 내용을 간략하게 설명하자면 bfs를 할 때 pop을 하고 reached를 확인하는 것이 아니라 push를 하기 전에 reached를 확인 하는 것이 더 효율적인 graph search라고 할 수 있다. Uninformed search strategies blind search라고도 불리우는데 problem definition에서 제공된 정보들만 사용가능..

DIGITAL-TO-DIGITAL CONVERSION analog 뿐만 아니라 digital신호도 digital신호로 바뀐다. line coding, block coding, scrambling 이렇게 3가지로 나뉜다. line coding은 필수적이며 block coding과 scrambling은 있어도 되고 없어도 된다. Line coding line coding은 위에서 말한 것 처럼 Digital신호를 Digital신호로 바꿔주는 것을 말한다. text,numbers,graphical images 등등으로 저장된 code를 전송하기 위해 convert해주는 것이다. Block coding Block coding은 line coding의 performance를 향상시키기 위해 사용된다. Decodi..

Alphabet Alphabet : 공집합이 아닌 기호들의 유한 집합, 시그마로 나타낸다. C언어의 알파벳은 영문 소문자, 대문자,0~9,특수문자 +,* ... String String 문자열 : 알파벳에 있는 기호들을 나열한 finite sequence이다. String Length, Concatenation of string String length는 문자열의 길이: string을 이루는 기호의 개수를 의미한다. Concatenation은 두 개의 문자열을 연결하여 새로운 문자열을 만드는 연산이다. Empty string Empty string : 공문자열이란 뜻으로 length가 0인 문자열을 의미한다. Prefix, Suffix 시그마대거 = 시그마스타 - 엡실론 Language Union of ..

fork() fork()를 해주면 child process는 부모와는 다른 프로세스에 메모리를 할당받게 된다. 하지만 부모와 contents는 같다. 새롭게 생성된 process는 이것만의 registers와 PC(program counter register)를 갖게 된다. parent 에서 fork()는 child process의 PID를 retun 해주고 child에서는 0을 return 한다. #include #include #include int main(int argc,char* argv[]){ //getpid()는 실행 중인 process id를 구해준다 printf("hello world (pid:%d)\n",(int) getpid()); //child는 여기서 부터 실행 int rc = f..

BCD 코드는 종류에 따라 각각의 특성이 있다. 대표적인 특성으로 Excess 3 Code와 2421 Code는 합이 9가 되는 순서쌍끼리 서로 complement하다는 것이다. 이런 특성에 맞지 않으면 invalid하다고 판단한다. 아직 잘은 모르겠지만 통신 간에 delay등으로 코드가 변형된 것을 잡기 위해서 만들어 진 것 같다. 일반적으로 이진수에서 1000+0101=1101이지만 BCD addition에서는 1101에 6을 더해서 10인 부분(0001)과 3(0011)인 부분으로 나눈다. Gray code의 특징은 앞 뒤로 bit의 차이가 1밖에 나지 않는다는 것이다. Hamming 코드는 3 check bits를 이용하여 error를 찾는다. 마지막에 2^n-n-1이 의미하는 것은 check b..