본문 바로가기

전체 글

(99)
Logic Boolean Algebra Propositions and Well Formed Formulas propositoin : declarative sentence that "must be true or false but not both" logical connectives : - ¬(not) - $\vee$(or) - $\Rightarrow$(implies) - $\wedge$(and) - $\Leftrightarrow$(if and only if) Well Formed Formula (wff) : all propositional constants and T/F are wffs tautology : 항등 contradiction : 모순 satisfiable wff : wff that is not a con..
Recurrence Relations and Recursive Algorithms Recurrence Relations and Recursive Algorithms Recurrence Relations recurrence relations (difference equation) - for a n.f. $(a_0,a_1,\cdots ,a_r,\cdots )$, an equation relating $a_r$ for any $r$ to one or more of $a_i$ ($i
Discrete Numeric Functions and Generating Functions Discrete Numeric Functions and Generating Functions function : binary relation that assigns to each element in domain a unique value which is element in range discrete numeric function / numeric function - functions whose domain is natural numbers and range is set of real numbers - denote n.f. Manipulation of numeric functions sum of two n.f.'s : n.f. whose value at r is equal to sum of values o..
Analysis of Algorithms 수많은 내용이 생략됨;; Analysis of Algorithms Time Complexity of Algorithms time complexity of an algorithm : the time it takes to execute an algorithm upper bound : a best possible algorithm for solving the problem - determining upper bound : just solve the problem lower bound : No algorithm for solving the problem will have complexity lower than the bound - show that time complexity of any algorithm th..
Graphs Graphs Basic Terminology directed graph $G=(V,E)$ - V : set of vertices - E : binary relation on V, called edges - edge(a,b) is incident with vertices a and b, incident from a, incident into b - a is initial vertex and b is terminal vertex of edge(a,b) loop : edge that is incident from and into same vertex adjacent : two vertices joined by an edge. a is adjacent to b and b is adjecent from a for..
Relations and Functions 중간고사 이전 부분은 Set/Propositions, Permutation/Combination/Discrete probability이나 pass함 Relations and Funcitons Intruduction Cartesian product of A and set B, A x B : set of all ordered pairs (a,b) where $a \in A$ and $b \in B$ ex) {a, b} x {a, c, d} = {(a,a), (a,c), (a,d), (b,a), (b,c), (b,d)} Binary relation from set A to set B : - subset of A x B - R is binary relation from A to B and if (a,b) $\i..
Chapter#25 Log-structured File Systems 대망의 마지막 챕터 Chapter#25 Log-structured File Systems Log-structured File System Journaling은 TxB, TxE도 쓰고 double write하여 오버헤드 있음 > Log-structured File System(LFS) 사용 e.g. F2FS, NetApp's WAFL, Btrfs, ZFS, ... 장점 : no consistent update problem no double writes write performance가 좋다 - disk는 sequential I/O operation에 optimized되어있음 Data block을 쓰고 순차적으로 metadata block도 쓴다. Single data block을 하나씩 쓰면 latenc..
Chapter#24 FSCK and Journaling Chapter#24 FSCK and Journaling - Crash Consistency Problem - File System Checker(fsck) - Journaling Crash Consistency Problem Crash Consistency file system data structure은 파워가 꺼져도 persist해야함 crash-consistency problem 발생 및 해결책 - fsck (file system checker) - Journaling (wrire-ahead logging) Crash Consistency Problem open() > lseek() > write() > close() 작업을 한 경우 기존 file 크기는 1 첫 direct pointer가 4(Da..