대학수업/이산수학

[10] 이산수학(정수의 표현과 알고리즘, 소수와 최대공약수)

정수의 표현 : 우리는 일상생활에서 10진법을 이용하여 정수를 표현한다. 하지만 컴퓨터는 연산할 때 2진법을 사용하고, 문자나 숫자 등을 표현할 때 8진법 또는 16진법을 사용한다. 정수 n을 위의 그림처럼 표현한 것을 n의 밑 b 전개(base b expansion of n)라 한다. 2진수 곱셈 : 10진수가 10의 자리마다 들여쓰기를 하는 것처럼, 2진수는 2의 자리마다 들여쓰기한다. 소수 : 1보다 큰 모든 정수는 최소한 두 정수(1과 자기 자신)로 나누어 떨어진다. 정확히 두 개의 서로 다른 양의 정수가 약수인 양의 정수를 소수(prime)라고 한다. 대수학의 기본 정리 : 1보다 큰 모든 정수는 소수이거나, 둘 이상의 소수의 곱으로 표현할 수 있다. 소수 판별법 : 만약 n이 합성수라면, n의..

[09] 이산수학(행렬을 이용한 연산)

주대각선 : 파란색으로 표시된 부분의 성분은 행렬 A의 주대각선 상에 있다. 대각합 : 주대각선 위 모든 성분들을 대각항이라 하고, 대각항들의 합을 대각합이라고 한다. 정방행렬 A의 대각합은 tr(A) 또는 trace(A)로 표기한다. 행렬의 대각합은 행과 열 번호가 같은 성분들의 합과 같다. 영행렬(Zero matrix) : 성분이 모두 0인 행렬 모든 i,j에 대하여 a(ij) = 0인 행렬을 말하며, 간단히 볼드체의 O이라고 표기한다. 교대 행렬(Skewed-symmetric matrix) : 전치행렬에 (-)를 붙인 n x n 행렬을 교대행렬이라고 한다. 삼각 행렬(Triangular matrix) : 상부삼각행렬(upper triangular matrix) : 주대각선 아래에 있는 모든 항들이 ..

[08] 이산수학(수열과 행렬)

주제 : 수열과 행렬 수열이란 정수 집합의 부분집합으로부터 집합 s로의 함수이다. (ex. 등차수열, 등비수열) 점화 관계란 앞서 나온 항들 간의 재귀적 규칙성을 이용하여 다음에 올 항들을 나타내는 것이다. 특히, 점화 관계가 효력을 나타내기 시작하는 항에 앞서서 나타나는 항을 초기 조건(initial conditions)라고 한다. 피보나치수열 점화 관계의 해 : 초기 조건이 수반된 점화 관계를 푸는 것, 또는 "해를 구하시오."라는 의미 점화 관계로부터 수열의 닫힌 공식(closed formula)라고 부르는 수열의 일반항을 구하는 것 점화 관계의 방법들: 반복법 : 점화 관계를 반복적으로 사용하여 해를 찾는 방법 특수한 정수 수열 : 패턴 찾기 같은 값이 계속 나타나는가? 즉, 같은 값이 연속해서 ..

[07] 이산수학(함수)

주제 : 함수 함수 : 한 집합의 각 원소를 다른(또는 같은) 집합의 특정 원소와 관련 짓는 것 함수는 때때로 사상 또는 변환이라고도 한다. 단사 함수 : 일대일 함수 단사 함수 보장 조건 : 전사 함수 : 정의역 A, 공역 B가 있을 때, B에 속한 모든 원소 b에 대하여 f(a) = b인 A에 속한 a가 존재할 경우 f를 전사 함수라고 한다. 전단사 함수 : 단사 함수이고 동시에 전사 함수인 함수(일대일 대응 관계) 역함수 : f가 A로부터 B로의 전단사 함수라고 하자. f의 역함수는 B의 원소 b에 A의 원소 a를 다른 것과 중복되지 않게 대응시키는 함수이다. 역함수를 만들 수 있는 전단사 함수는 가역함수, 전단사 함수가 아닌 경우 비가역 함수이다. 함수의 합성 : g가 집합 A로부터 집합 B로의 ..

[06] 이산수학(집합)

주제 : 집합 집합의 표현법 : 원소나열법 : 집합의 원소를 모두 나열하는 것 조건 제시법 : 집합의 원소들의 공통적인 특성을 기술하는 것 집합의 구간 : 닫힌구간, 열린 구간 두 집합이 같은 원소를 갖고 있다면 그 두 집합은 같다고 표현한다. 특수한 집합 : 공집합 : 원소를 갖지 않는 특수한 집합 단일 원소 집합 : 단 하나의 원소만 갖는 집합{공집합} 벤 다이어그램 : 집합 간의 관계를 나타내는 데 종종 사용한다 부분집합 : 임의의 집합 S에 대해 포함되는 원소들의 집합 진부분집합 : 공집합과 자기 자신을 제외한 부분집합 멱집합 : 임의의 집합 S가 주어졌을 때, 집합 S의 멱집합은 집합 S의 모든 부분집합의 집합이다. 데카르트곱 : 집합은 원소의 순서를 무시하지만, 여기서는 순서를 고려한다고 가정..

[05] 이산수학(증명)

주제 : 증명 가설(conjecture) : 어떤 부분적 증거나 휴리스틱한 논증, 또는 전문가의 직관에 근거하여 참이라고 주장되는 문장 증명(proof) : 어떤 정리가 참이라는 것을 입증하는 유효한 논증 정리(theorem, facts, results) : 그것이 참임을 보일 수 있는 하나의 진술 주장(propositions) : 상대적으로 덜 중요한 정리 보조정리(lemma) : 증명하는데 도움이 되는 약간 덜 중요한 정리. 개별적 증명 필요 따름정리(corollary) : 증명된 정리로부터 직접적으로 귀결될 수 있는 정리 가설이 증명되면 그 가설을 정리라고 한다. 정리 증명 방법 : 대상 영역의 일반적 원소를 선택 이 원소가 문제의 성지을 갖는지 확인 전칭 일반화를 적용하여 모든 원소에 대해 성립함..