Processing math: 100%

본문 바로가기

Study/이산수학

(6)

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

$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..

티스토리툴바