이산수학(Discrete mathematics, 離散數學)은
이산적인 수학 구조에 대해 연구하는 학문으로, 연속되지 않는 공간을 다룬다.
유한수학이라고도 하며, 전산학적인 측면을 강조할 때는 전산수학이라고도 한다.
주로 정수, 유한 그래프, 형식 언어 같이 가산집합에 속하는 개념을 다룬다.
이산수학은 전산학의 기초가 되는데, 이것은 컴퓨터에서 다루는 자료형이 이산적이라는 것에서 기인한다.
이산수학에서 나온 개념과 기호는 컴퓨터 알고리즘과 프로그래밍 언어의 문제나 대상들을 연구하는 데 유용하다.
이산수학의 주제
논리학(論理學, 문화어: 론리학)은 올바른 추론과 증명의 법칙을 연구하는 학문을 말한다.
일반적으로는 논증의 학문이라고 정의되며, 판단·추리·개념 등의 올바른 조리에 관한 과학이라고도 한다.
논리학이 구체적으로, 정확하게 무엇인지에 대해 답하기는 쉽지 않다고도 한다.
집합론(集合論, set theory)은 추상적 대상들의 모임인 집합을 연구하는 수학 이론이다.
집합론은 술어논리학과 함께 대부분의 수학기초론 체계의 근본으로, 현대 수학을 논리적으로 지탱하는 밑바탕이 된다.
소박한 집합론(naive set theory)에서는 집합을 단순히 대상들을 모아서 만들어지는 자명한 개념으로 이해한다.
초등학교 및 중학교 등의 교육과정에서 다루는 집합의 개념은 이에 해당한다.
소박한 집합론의 모순을 해결하기 위해 등장한 공리적 집합론은
집합들과 그 포함관계가 만족하는 공리들을 규정하는 방법으로 집합을 간접적으로 정의한다.
여기에서 집합과 그 포함관계는 유클리드 기하에서의 점이나 선과 같은 무정의 용어로 볼 수 있다.
공리적 집합론은 대부분의 경우 대학에서 수학을 전공하지 않는 이상 배우지 않는다.
정수론(整數論) 혹은 수론(數論)은 수학의 한 분야로 각종 수의 성질을 대상으로 한다.
조합론(組合論)은 순수 수학의 한 갈래로서 연속적이지 않은 대상을 다룬다.
보통 유한한 대상에 관심을 갖는다.
조합론은 대수학, 확률론, 에르고드 이론, 기하학 등 수학의 여러 분야와 관련되어 있다.
또한, 전산학, 통계 물리학 같은 분야와도 관계가 있다.
조합론에는 특정 조건을 만족하는 대상의 수를 세는 열거 조합론, 조건들이 언제 만족되는지 알아내고
그 조건을 만족하는 대상들을 만들고 해석하는 조합 설계 이론과 매트로이드 이론,
"가장 큰", "가장 작은", "최적"인 대상을 찾는 extremal 조합론과 조합최적화, 대상들이 갖는 대수적 구조를 찾는 대수 조합론이 있다.
그래프 이론(문화어: 그라프 리론)은 그래프의 특성을 연구하는 수학과 컴퓨터 과학의 한 분야로,
특정 집단내 대상들 간의 관계를 그래프로 나타낸 수학적 구조이다.
여기서의 그래프는 노드(nodes)와 두 노드를 연결하는 선(edge)으로 구성되어 있다.
이러한 그래프 가운데 방향이 없는(undirected) 그래프는 노드들 간에 차이가 없음을 의미하며,
방향이 있는(directed) 그래프 역시 존재한다.
그래프 이론에서의 그래프와 다른 일반 수학적인 그래프와 혼동하지 말아야 한다.
알고리즘(영어: algorithm 알고리듬[*], IPA: [ǽlɡərìðm])이란 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임이다.
정보 이론(情報理論)은 최대한 많은 데이터를 매체에
저장하거나 채널을 통해 통신하기 위해 데이터를 정량화하는 응용 수학의 한 분야이다.
데이터의 단위인 정보 엔트로피는 보통 저장 또는 통신에 사용되는 평균적인 비트 수로 표현된다.
예를 들어 매일의 날씨 정보가 3비트의 엔트로피를 가진다면,
하루의 날씨를 평균 약 3비트로 기술할 수 있다.
정보 엔트로피는 열역학에서의 엔트로피와 크게 다르지 않은 개념으로,
정보엔트로피(정보량)가 높을수록 불확실성은 커진다.
반대로 계에서의 정보량은 불확실성의 정도이므로 불확실성이 적은 계의 정보 엔트로피(정보량)는 줄어들 수 있다.
영어알파벳의 경우 모든 알파벳이 동일한 확률도 발생한다면
정보엔트로피(정보량)은 4.754887비트이지만 알파벳의 출현 빈도값을 계산하면 4.08비트까지 줄어든다.
이것 외에도 어떤 철자가 오면 그 뒤에 특정철자가 올 확률이
아주 높은 등 여러가지 이유가 있기 때문에 정보 엔트로피(정보량)는 더욱 줄어들 수 있게 된다.
한 가지 예를 들면 q가 오면 그뒤에 a,u가 올 확률이 거의100%이다.
정보 이론의 기본적인 주제가 적용되는 기술로 ZIP 파일(무손실 데이터 압축),
MP3 파일(손실 데이터 압축), DSL(채널 부호화), MIMO(채널 모델) 등이 있다.
정보 이론 분야는 수학, 통계학, 전산학, 물리학, 전자공학과 연관되어 있으며,
보이저 계획의 성공, 콤팩트 디스크의 발명, 휴대전화의 실용화, 인터넷의 개발, 언어학과 인간 지각의 연구, 블랙홀의 이해 등 많은 곳에 큰 영향을 끼쳤다.
전산학에서, 계산 가능성 이론(計算可能性理論, 영어: computability theory)은
계산 이론의 한 갈래로서 계산 모형을 이용하여 어떠한 문제를 계산할 수 있는지를 연구하는 이론이다.
계산 가능성 이론은 어떤 문제가 풀릴 수 있는가를 따지기 때문에,
어떻게 문제가 효율적으로 풀릴 수 있겠는가를 다루는 계산 복잡도 이론과는 구별한다.
계산 복잡도 이론(Computational complexity theory)은
컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리듬을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다.
이 때 알고리듬의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다.
복잡도의 기준은 알고리듬이 소모하는 소요 시간과 메모리 사용량 등의 자원이다.
일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다.
확률론(確率論)은 확률에 대해 연구하는 수학의 한 분야이다.
확률론은 비결정론적 현상을 수학적으로 기술하는 것을 목적으로 하며,
주요 연구 대상으로는 확률 변수, 확률 과정, 사건 등이 있다.
확률론은 통계학의 수학적 기초이다. 또한 인간은 살아가기 위해 매 순간
직접적으로 예측할 수 없는 방법으로 변화하는 환경에 대처하여 결정을 내릴 필요가 있으며,
이는 의식적으로나 무의식적으로나 확률론에 기반하게 된다.
통계역학 등에서, 완전한 정보가 알려지지 않은 복잡계를 기술하는 데에도
확률론적 방법론은 큰 역할을 한다.
이에 더해 20세기 초에 등장한 물리학 이론인 양자역학은, 미시계의 물리적 현상이 근본적으로 확률적인 본질을 갖고 있음을 알려주었다.
선형대수학(線型代數學, 영어: linear algebra)은 벡터 공간, 벡터, 선형 변환, 행렬, 연립 선형 방정식 등을 연구하는 대수학의 한 분야이다.
현대 선형대수학은 그 중에서도 벡터 공간이 주 연구 대상이다. 추상대수학, 함수해석학에 널리 쓰이고 있다.
선형대수학은 자연과학과 공학에도 널리 활용된다. 선형 연립방정식을 푸는 좋은 방법으로는 소거법과 행렬식이 있다.
함수(函數)는 공집합이 아닌 두 집합 
, 
에 대하여 의 각 원소를 의 오직
하나의 원소에 대응시키는 대응 관계이다.
수학의 순서론 등에서 부분순서(部分順序, partial order)는
"a는 b보다 같거나 크다"라는 관계를 일반화한 것이다.
부분순서가 주어진 집합을 부분순서집합(partially ordered set, 줄여서 poset)이라고 한다.
완전순서집합의 원소들은 언제나 크기를 비교할 수 있지만,
부분순서집합의 원소들은 꼭 언제나 비교가 가능해야 할 필요는 없다.
(즉, 부분순서의 경우 두 원소 a와 b에 대해, a≥b도 아니고 b≥a도 아닐 수도 있다.)
부분순서는 부분순서 위상을 정의한다.
수학에서, 계수(係數)는 어느 변수에 일정하게 곱해진 상수 인자이다.
예를 들어, 
에서 계수는 
이고. 
에서 계수는, 
이다. (보통, 1은 계수에서 생략한다.)
그 대상은 변수, 벡터, 함수 등과 같은 것들이 될 수 있다. 이 경우에 그 대상들은 같은 방법으로 지수화되는 데, 다음과 같이 표현된다:
여기서 an은 각각의 n = 1, 2, 3, …에서 변수 xn의 계수이다.
변수 x에 대한 다항식 P(x)에서, xk의 계수는 k를 지수로 하여 다음과 같은 약속과 함께 주어질 수 있는데
ak ≠ 0이고 가장 큰 k에서, 다항식은 통상적으로 x의 가장 큰 지수부터 내림차순 (가령, x5 + x4 + x2 ...)으로 쓰기 때문에
ak는 P의 최고차 계수라고 불린다.
이항계수를 포함하여 수학에서 중요한 계수들은 이항정리의 식에서 보이며, 이것들 중 특수한 경우로 파스칼의 삼각형이라 부르는 형태가 있다.
수학에서 관계(關係)는 "자연수 a가 b보다 작다"와 같은 이항관계를 일반화한 것이다.
앞의 경우와 같이 두 대상 사이에 주어지는 관계는 이항관계라 하고,
"점 a,b,c가 한 직선상에 놓여있다"와 같이 세 대상 사이에 주어지는 관계는 삼항관계라 한다.
이산수학
- 저자
- Richard Johnsonbaugh 지음
- 출판사
- 피어슨에듀케이션코리아(컴퓨터) | 2005-03-21 출간
- 카테고리
- 컴퓨터/IT
- 책소개
- 이산수학 제6개정판. 이번 판에서는 논리 및 증명 부분을 강화한...
글쓴이 평점 
