본문 바로가기

𝓡𝓸𝓸𝓶5: 𝒦𝑜𝓇𝑒𝒶 𝒰𝓃𝒾𝓋/Discrete mathematics

(5)

[이산수학] Chapter 1. Logic and proofs 1. Propositions : 명제 - 만약 p, q가 명제라면, connective를 이용해 새로운 compound proposition을 만들 수 있다. (conjunction AND, inclusive disjunction OR, exclusive disjunction OR(XOR), negation, implication, double implication) 2. Conditional propositions(조건명제) and logical equivalence(동치) - conditional proposition : p->q "if p then q", "p only if q" p : 가정, 충분조건 / q : 결론, 필요조건 - logically equivalent (converse(역), co..

[이산수학] Chapter 6. Counting methods and the pigeonhole principle 1. Basic Principles - Menu for Quick Lunch : 점심 메뉴를 고르는 경우의 수 1) Multiplication Principle(곱셈법칙) : k개의 연속적인 행동이 있을 때, 이 행동을 수행하는 경우의 수는 n1n2...nk ex) 8 bit string 에서 101이나 111로 시작하는 것의 개수 : 2^5 * 2 2) Addition Principle (덧셈법칙) nj개의 elements를 가지고 있는 k개의 pairwise disjoint sets가 있을 때, 이 sets의 결합 X = ∪Xj 는 n1 + n2+...+ nk의 elements를 가진다. 2. Permutations and Combinations (순열과 조합) 1) Permutation : 순열 (..

[이산수학] Chapter 5. Introduction to Number Theory 1. Divisors 1) - d가 n을 나누어 떨어지게 할 때, 즉 n=dq를 만족하는 integer q가 존재할 때, d divides n이라고 말한다. - 이 때 q를 quotient, d를 divisor 또는 n의 factor라고 부른다. - d divides n일 때 d|n으로 쓴다. Theorem 5.1.3 m, n, d를 정수라고 하자. 만약 d|m이고 d|n이면 d|(m±n)이다. 또한 d|m이면 d|mn이다. proof : d|m이고 d|n이면 m=dq, n=dq' 라고 쓸 수 있다. m+n = dq + dq' = d(q+q')이다. 따라서 d|(m+n) 이다. 2) Prime and Composite - Prime : 소수 - Composite : 합성수 composition은 2와 루..

[이산수학] Chapter 4. Algorithms 1. Introduction - 알고리즘은 다음과 같은 특징들을 가지고 있다. 1) input 2) output 3) precision : 정확하게 서술되어야 한다 4) determinism : 수행의결과는 unique하다. 또한 input과 선행된 step에 따라 결정된다. 5) finiteness : 알고리즘은 끝나야 한다. (유한개의 instruction이 수행된 이후엔 멈춰야 함) 6) correctness : 알고리즘에 의해 도출된 output은 맞아야 한다. 7) generality : 모든 input에 대해 적용되어야 한다. 2. Examples of Algorithms - 큰 수 찾기 알고리즘, 문자열 찾기 알고리즘, 삽입 정렬 알고리즘 - Randomized Algorithms (무작위 ..

[이산수학] Chapter 3. Relations 1. Relations - 주어진 집합 X, Y에서 Cartesian product X x Y 를 하면 그 결과는 x∈X, y∈Y인 (x, y)의 모든 ordered paris 이다. X x Y = {(x,y) | x∈X and y∈Y} -Binary relation (이진 관계) : 두 집합의 원소 사이의 관계 집합 X 에서 집합 Y 로의 binary relation R은, Cartesian product X x Y 의 subset(부분집합)이다. Ex) X = { 1, 2, 3 } and Y = { a, b } R = {(1, a), (1, b), (2, b), (3, a)} 는 X와 Y 사이의 relation이다. - Domain : y∈Y인 y에 대하여 (x, y)가 relation R에 속할 때..

이전 1 다음

티스토리툴바