본문 바로가기

컴퓨터 과학/이산수학

[이산수학]정렬 알고리즘의 한계 정렬 알고리즘은 데이터를 특정 순서로 나열하는 알고리즘이다. 여러 가지 정렬 알고리즘이 존재하며, 각 알고리즘은 서로 다른 특징과 성능을 가지고 있다. 하지만 모든 (비교 기반) 정렬 알고리즘은 절대로 $\mathcal{O}(n\log n)$보다 좋은 성능을 낼 수 없다. 증명 우선 데이터들이 총 $n$개가 주어진다고 하자. 그렇다면 만들 수 있는 $n$-튜플의 경우의 수는 총 $n!$개이다. 이 가운데 단 하나만이 올바른 순서쌍이 될 것이다. ($(a_1,\cdots,a_n)$에 대해, $1\le i\le j\le n\implies a_i\le a_j$인 튜플) 결정 트리의 최소 높이가 $\log n!=\sum_{k=1}^n\log k$이므로 다음 관계식을 만족한다. $$\int_1^{n-1}\log .. 더보기
[이산수학]귀납법과 재귀 수학적 귀납법 수학적 귀납법은 다음과 같은 명제를 의미한다. $$(P(1)\wedge \forall k(P(k)\rightarrow P(k+1)))\rightarrow\forall nP(n)$$ 추론 규칙으로는 다음과 같다. $$\frac{ \begin{matrix} P(1) \\ P(k)\to P(k+1) \end{matrix}}{\forall nP(n)}$$ 예제1 수학적 귀납법을 이용하여 다음을 증명하라. $$1+2+\cdots +n=\frac{n(n+1)}{2}$$ 우선 $P(1)$이 참임을 보이자. $P(1)\equiv (1=\frac{1\times(1+1)}{2})$이므로 참이다. 그리고 $P(k)\to P(k+1)$가 참. 즉, $P(k)$가 참이라면 $P(k+1)$이 참임을 보이자. $1+.. 더보기
[이산수학]그래프 이론 그래프의 기본 용어들 그래프 이론은 다양한 현상을 모델링하고 분석하기 위해 그래프를 사용하는 수학적인 분야이다.. 그래프는 노드(node)와 간선(edge)으로 구성된 추상적인 자료 구조로, 이들을 사용하여 다양한 관계를 표현할 수 있다. 그래프의 기본 용어는 다음과 같다. 노드(Node): 노드는 그래프의 기본 단위로, 보통 어떤 개체나 개념을 나타낸다. 간선(Edge): 간선은 노드 간의 관계를 나타낸다. 두 노드를 연결하는 선으로, 이 선은 방향이 있을 수도 있고 없을 수도 있다. 방향성(유/무방향 그래프): 간선에 방향이 있는 경우 유방향 그래프라고 부른다. 방향성이 없는 그래프는 무방향 그래프이다. 가중치(Weight): 간선에 가중치를 부여할 수 있다. 이는 간선이 나타내는 관계의 강도나 비용.. 더보기
[이산수학]정수론 정수론은 정수에 대한 성질을 연구하는 학문이다. 순수 수학이지만 컴퓨터와 인터넷 보안에 핵심적인 역할을 하고있다. 약수 정수론에서 약수는 $a\mid b$로 표기한다. "a가 b를 나눈다." 또는 "a는 b의 약수이다."를 의미한다. 이는 다음과 같이 정의된다. $$a\mid b \iff \exists c\in \mathbb{Z}(ac=b)$$ 즉, a에 c를 곱해서 b가 되는 정수 c가 존재한다면 a는 b의 약수이다. 예를 들어 6은 3으로 나눌 수 있기 때문에 6의 약수이다. (3 * 2 = 6) 약수가 아니라면 $a \nmid b$로 표기한다. 몫과 나머지 몫과 나머지는 나눗셈 알고리즘을 통해서 정의된다. 정의는 다음과 같다. 정수 $a$와 $b$에 대해서 $a=qb+r$ 그리고 $0\le r 더보기
[이산수학]시간 복잡도와 공간 복잡도 시간 복잡도란 컴퓨터 프로그램의 입력값과 계산 수행 시간의 관계를 나타내는 척도이다. 이와 비슷하게 공간 복잡도란 프로그램의 입력값과 메모리 공간의 관계를 나타내는 척도이다. 두 개념 모두 점근 표기법이란 것을 통해서 나타낸다. 점근 표기법은 함수의 증감 양상을 나타내는 것이다. (이번 글은 기초적인 극한 개념이 필요합니다.) 점근 표기법은 여러가지가 있으며 다음과 같이 정의된다. 함수 $f:X\rightarrow Y$에 대해서 ($X$와 $Y$는 보통 실수 또는 자연수이다.) $$f= \mathcal{o}(g)\iff \lim_{x\to \infty} \frac{f(x)}{g(x)}=0$$ $$f= \mathcal{O}(g)\iff \limsup \frac{f}{g}0$$ $$f= \omega(g)\i.. 더보기
[이산수학]알고리즘 많은 문제들은 일반적인 문제들의 특별한 경우로 생각하여 풀 수 있다. 예를 들면 다음과 같다. 1. n개의 정수를 담은 튜플이 주어졌을 때, 최소 원소를 찾으시오. 2. n개의 정수를 담은 튜플이 주어졌을 때, 최대 원소를 찾으시오. 3. n개의 정수를 담은 튜플이 주어졌을 때, 짝수 정수를 모두 찾으시오. 이러한 문제들은 정수들 중에서 특정 성질을 만족하는 정수를 찾는 문제의 특별한 형태이다. 일련의 절차를 통해 일반화된 문제를 푸는 방법이 필요하다. 이러한 일련의 절차를 알고리즘이라 한다. 알고리즘은 여러 경우로 일반화할 수 있다. 1. 정수의 서열이 주어졌을 때, 가장 큰 수를 찾으시오. 2. 집합이 주어졌을 때, 모든 부분집합을 나열하시오. 3. 정수의 집합이 주어졌을 때, 점점 커지는 순서대로 .. 더보기
[이산수학]선형대수학 기초 선형대수학은 해석학과 함께 응용 범위가 굉장히 넓은 수학 분야이다. 프로그래밍에서는 배열과 같은 개념들의 기반이 되어준다. 프로그래머 이외에도 공대생이라면 필수적으로 배우며, 주로 행렬을 다룬다. 1. 행렬과 기초 용어 행렬은 수를 직사각형 형태로 나열한 것을 의미한다. 예를 들면 다음과 같은 행렬이 있다. $$ \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix}$$ 행렬은 다음과 같이 표기하기도 한다. $$\begin{pmatrix} a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \\ \end{pmatrix}$$ ($a_{1,1}$과 같이 성분의 위치가 일의 자리 숫자만으로 구성된 경우, $a_{11}$로 줄여서 쓰기도 한다.) 이 때, $a_{.. 더보기
[이산수학]공리계 1. 공리 논리학이나 수학 등의 형식적인 이론체계에서 가장 기초가 되는 명제이다. 그리고 이는 증명없이 참으로 받아들여진다. 즉, 일종의 약속이다. 이러한 공리는 왜 필요한 걸까? 그 이유는 수학의 모든 명제는 근거가 있어야 하기 때문이다. 어떠한 명제가 참임을 보이기 위해 근거가 되는 명제가 필요하다. 근거가 되는 명제와 추론규칙을 이용하여 연역적으로 또 다른 명제를 도출한다. 이를 증명이라 한다. 다른 명제로부터 또 다른 명제가 참임을 연역적으로 보이는 것이 핵심이다. 공리없이 논리체계를 구성하려면 2가지 형태를 띄게 된다. 첫 번째는 다음과 같다. $$A\leftarrow B\leftarrow C\leftarrow \cdots$$ A라는 명제가 참임을 보이기 위해 B라는 명제가 필요하고, B라는 명.. 더보기

티스토리툴바