본문 바로가기

전체 글

 (100)
수학적 귀납법과 이항정리 Outline 수학적 귀납법 이항 정리 수학적 귀납법 정렬성의 원리 : 공집합이 아니고 음이 아닌 정수들을 원소로 갖는 모든 집합 S는 최소 원소를 가진다. 즉, S는 S에 속하는 모든 $b$에 대해 $a1$이다. $a$가 $T$의 최소 원소이므로 $T$는 $a-1$을 가지지 않는다. 즉 $a-1$은 $S$에 속한다. $S$는 정의에 따라 $(a-1)+1$을 포함하며 이는 모순이다. 유한 귀납법에서 (a)는 basis for the induction (b)는 induction step (b)를 수행하며 만들어지는 가정을 induction hypothesis라 부른다. 이항 정리 $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$ $$\binom{n}{k} = \frac{n(n-1)\cd..
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..

티스토리툴바