본문 바로가기

Study

 (25)
나눗셈정리 Outline 나눗셈 정리 최대공약수 유클리드 알고리즘 디오판투스 방정식 나눗셈 정리 주어진 정수 a, b에 대해, b>0, 다음을 만족하는 유일한 정수 q, r이 존재한다. $$a=qb+r \ \ \ \ 0\leq r
수학적 귀납법과 이항정리 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..

티스토리툴바