이산수학 - 정수론, 나눗셈, 베주의 항등식, 유클리드 호제법, 나머지 연산, 소수와 소인수 분해, RSA 암호
1. 나눗셈 a는 정수이고 b는 양의 정수라 할 때, 다음을 만족하는 유일한 정수 q, r이 존재한다. \[ a = bq + r \quad \text{단,} \quad 0 \leq r 이 정리는 어떤 정수 \( a \)를 양의 정수 \( b \)로 나누면, 몫 \( q \)와 나머지 \( r \)가 존재하며, 나머지 \( r \)는 0 이상 \( b \) 미만의 범위에 속한다는 것을 의미한다. 예를 들어, \( a = 17 \)이고 \( b = 5 \)인 경우를 생각해보자. \( a \)를 \( b \)로 나누면 다음과 같이 나타낼 수 있다.\[17 = 5 \cdot 3 + 2\]여기서 몫 \( q = 3 \)이고 나머지 \( r = 2 \)이다. 또한, 나머지 \( r \)는 0 이상 5 미만의 ..
2024. 5. 15.
이산수학 - 그래프, 트레일, 경로, 이분 그래프, 완전 이분 그래프, 정규 그래프, 오일러 투어, 해밀턴 경로
1. 기본사항 다음 그림처럼 점과 두 점을 서로 연결하는 선으로 이루어진 도형을 그래프라 한다. 2. 주요 용어 그래프 \( G \)는 꼭지점(vertex)들과 변(edge)들로 구성된다. 이를 수식으로 나타내면 \( G = (V, E) \)이다. 여기서 \( V = \{ v | v \text{는 꼭지점} \} \)이고, \( E = \{ e | e \text{는 변} \} \)이다.변은 두 꼭지점을 연결한다. 즉, 변에 의해 발생(incident)된다고 한다.연결된 두 꼭지점은 서로 인접(adjacent)한다고 한다.병렬 변(parallel edge)은 두 꼭지점을 연결하는 변이 복수개 있을 때를 의미한다.루프(loop)는 동일한 꼭지점을 연결하는 변을 뜻한다.고립된 꼭지점(isolated ..
2024. 5. 15.
이산수학 - 함수, 함수의 상등, 전사함수, 단사함수, 합성함수, 계승함수, 바닥함수, 천장함수, 나머지 함수
1. 기본사항 집합 \(X\)와 \(Y\)가 주어졌을 때, \(X\)에서 \(Y\)로의 함수 \(f\)는 다음 조건을 만족하는 관계이다.모든 \(x \in X\)에 대해, 오직 하나의 \(y \in Y\)가 존재하여 \((x, y) \in f\)를 만족한다. 이를 수식으로 표현하면 다음과 같다.\[ \forall x \in X, \exists ! y \in Y \quad \text{such that} \quad (x, y) \in f \]즉, \(X\)의 임의의 원소 \(x\)에 대해, \((x, y) \in f\)를 만족하는 \(y\)가 \(Y\)에 오직 하나만 존재한다.이를 함수 \(f\)로 표현하면 다음과 같이 쓸 수 있다.\[ f : X \to Y \]그리고, \(f(x) = y\)라는 관계를 만..
2024. 5. 15.
이산수학 - 관계, 관계의 표현, 관계의 성질, 관계의 종류, 반사적, 대칭적, 추이적, 동치관계
1. 기본사항관계란 객체들 간의 연관성을 포현하는 구조이다. 이산수학에서 관계는 주로 두 집합에 속하는 서로 다른 두 원소 사이의 연관성을 표현하는 데 사용된다. 두 집합 X와 Y에 대하여 곱집합 X x Y의 부분집합 R을 X에서 Y로의 관계라고 말한다. 집합 \(A\)와 \(B\)의 곱집합(Cartesian Product) \(A \times B\)는 \(A\)의 원소와 \(B\)의 원소의 모든 순서쌍(ordered pair)들의 집합을 의미합니다. 즉,\[ A \times B = \{ (a, b) \mid a \in A, b \in B \} \] 집합 \( X \)에서 집합 \( Y \)로의 (이항)관계 \( R \)은 \( X \times Y \)의 부분집합이다.- 이항관계 \( R \)에 대..
2024. 5. 15.
이산수학 - 행렬: 행렬의 연산, 종류, 정방행렬, 단위행렬, 역대칭행렬, 삼각행렬, 역행렬, 부울행렬
1. 기본 사항 행렬은 행과 열로 구성되는 사각형 형태로 수를 배열한 것 \begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8 \\9 & 0 & 2 & 5 \\\end{bmatrix} - 컴퓨터 분야의 활용프로그래밍 언어 자료구조 컴퓨터 그래픽스패턴인식 로봇동작 인공지능행렬 m과 n이 양의 정수일 때, m개의 행과 n개의 열로 구성된 직사각형의 수 배열 A를 \( m \times n \) 행렬이라 한다.행렬 \( A \)에서 i번째 행의 j번째 열의 수를 행렬 \( A \)의 \((i,j)\) 원소라 하며, \( a_{ij} \)로 표시한다. 행렬 \( A \)를 간단히 \( A = [a_{ij}] \)로 표기하기도 한다.- 행 벡터(row vector): \( 1 \ti..
2024. 5. 15.
