이산수학

3. 이산수학의 주요 분야

이산수학은 여러 분야를 포함하며, 각 분야는 컴퓨터 과학 및 정보 통신 기술 발전에 중요한 역할을 한다. 주요 분야는 다음과 같다:

• 수리 논리학: 논리적 사고 과정을 수학적으로 연구한다. 수학적 증명은 수리논리학에서 중요하며, 자동 정리 증명과 소프트웨어 형식적 검증으로 발전했다.
• 집합론: 집합의 성질과 연산을 연구한다. 데이터베이스 등에 활용된다.
• 정수론: 정수의 성질과 관계를 연구하며, 암호학 등에 활용된다.
• 조합론: 주어진 조건을 만족하는 경우의 수를 세거나 최적의 조합을 찾는 방법을 연구한다. 알고리즘 설계 등에 활용된다.
• 그래프 이론: 그래프와 네트워크를 연구한다.
• 알고리즘: 문제를 해결하기 위한 절차나 방법을 연구한다.
• 정보 이론: 정보의 정량화를 연구하며, 부호 이론과 밀접하게 관련되어 있다.
• 오토마타 이론
• 계산 가능성 이론
• 계산 복잡도 이론
• 확률론
• 선형대수학
• 함수
• 순서 집합
• 증명 이론
• 계수와 관계

3. 1. 수리 논리학

3. 2. 집합론

3. 3. 정수론

정수의 성질과 관계를 연구하는 분야이다. 암호학, 정보 보안 등에 활용된다. 특히 모듈러 산술, 디오판토스 방정식, 선형 및 2차 합동, 소수 및 소수판정에 응용된다. 수론의 다른 이산적인 측면에는 수의 기하학이 포함된다.

3. 4. 조합론

조합론은 주어진 조건을 만족하는 경우의 수를 세거나, 최적의 조합을 찾는 방법을 연구하는 분야이다. 이는 알고리즘 설계, 네트워크 최적화 등에 활용된다.

조합론은 이산 구조를 결합하거나 배열하는 방법을 연구한다. 세부 분야는 다음과 같다.

• 조합적 열거: 특정 조합 객체의 수를 세는 데 집중한다. 예를 들어 열두 가지 방법은 순열, 조합, 분할을 세는 통합 프레임워크를 제공한다.
• 해석적 조합론: 복소 해석 및 확률론의 도구를 사용하여 조합 구조의 열거(즉, 수를 결정하는 것)에 관한 것이다. 명시적 조합 공식과 생성 함수를 사용하여 결과를 설명하는 조합적 열거와 대조적으로, 해석적 조합론은 점근적 공식을 얻는 것을 목표로 한다.
• 위상적 조합론: 조합론에서 위상 수학 및 대수적 위상 수학/조합적 위상 수학의 기술을 사용하는 것에 관한 것이다.
• 설계 이론: 특정 교집합 속성을 가진 부분 집합 모음인 조합 설계에 대한 연구이다.
• 분할론: 정수 분할과 관련된 다양한 열거 및 점근적 문제를 연구하며, q-급수, 특수 함수, 직교 다항식과 밀접하게 관련 있다. 원래는 수론과 해석학의 일부였지만, 현재는 조합론의 일부 또는 독립적인 분야로 간주된다.
• 순서론: 유한 및 무한 부분 순서 집합에 대한 연구이다.^[1]

조합론은 "끊임없이 세는" 수학이라고 할 수 있다. 유한한 수에 대해 생각하며, 그 사고방식의 기본은 다음과 같다.^[2]

• 해결책은 존재하는가?
• 얼마나 많은 수의 해결책이 있는가?
• 최적의 해결책이 있는가?

그래프 이론의 많은 문제는 조합론과 관련이 있다. 예를 들어, 그래프에서 두 정점 사이의 경로에 관한 문제는 다음과 같다.^[2]

• 경로는 존재하는가?
• 얼마나 많은 수의 경로가 있는가?
• 최적의 경로를 찾을 수 있는가?

그 외에도 그래프 채색에 관한 문제 등 조합론과의 관련이 깊다.^[2]

학교 교육 영역에서 가르치는 조합론 관련 내용으로는 순열·조합이 있다.^[2]

3. 5. 그래프 이론

그래프 이론은 그래프와 네트워크를 연구하는 분야로, 점과 선으로 연결된 그래프의 구조와 성질을 연구한다. 종종 조합론의 일부로 간주되지만, 자체적인 문제들을 가지고 독립적인 분야로 여겨질 만큼 충분히 크고 뚜렷하게 성장했다.^[14]

그래프는 자연적 및 인공적 구조에 대한 모델 중 하나이며, 물리적, 생물학적 및 사회적 시스템에서 다양한 유형의 관계와 프로세스 역학을 모델링할 수 있다. 컴퓨터 과학에서 그래프는 통신 네트워크, 데이터 구성, 계산 장치, 계산 흐름 등을 나타낼 수 있다.

그래프 이론은 조합론과 관련이 깊다. 예를 들어, 그래프에서 두 정점 사이의 경로에 관한 문제는 다음과 같다.

• 경로는 존재하는가?
• 얼마나 많은 수의 경로가 있는가?
• 최적의 경로를 찾을 수 있는가?

그래프 채색에 관한 문제 등도 조합론과 관련이 깊다.

3. 6. 알고리즘

문제를 해결하기 위한 절차나 방법을 연구하는 분야이다. 컴퓨터 과학의 모든 분야에 활용된다.

이론 전산학에는 알고리즘과 자료 구조 연구가 포함된다. 계산 기하학은 알고리즘을 기하학적 문제와 기하학적 객체의 표현에 적용하는 반면, 컴퓨터 이미지 분석은 알고리즘을 이미지의 표현에 적용한다.

이산수학에서 자주 사용되는 공통적인 문제 해결 방법은 알고리즘에 의한 해결 방법이다. 문제의 구조를 알고리즘으로 대체하여 분석함으로써 문제를 해결한다. 알고리즘의 이론은 귀납적인 생각을 포함한다. 즉, 알고리즘의 이론 자체도 이산수학의 한 부분을 이루고 있다고 할 수 있다.

3. 7. 정보 이론

정보 이론은 정보의 정량화를 연구하는 분야이다. 이는 효율적이고 신뢰할 수 있는 데이터 전송 및 저장 방법을 설계하는 데 사용되는 부호 이론과 밀접하게 관련되어 있다. 정보 이론은 아날로그 신호, 아날로그 부호화, 아날로그 암호화와 같은 연속적인 주제도 다룬다.

4. 이산수학의 응용 분야

이산수학은 컴퓨터 과학, 정보 통신, 암호학 등 다양한 분야에서 널리 응용된다.

이산수학은 정수처럼 딱딱 떨어지는 값들을 다루기 때문에, 연속적인 값을 다루는 미적분학과는 다르다. 이산 미적분, 이산 푸리에 변환, 이산 기하학 등 다양한 분야가 있다.

이산 미적분학에서는 수열을 주로 다룬다. 수열은 데이터에서 얻거나, 이산 동적 시스템에서 만들 수 있다. 차분 방정식은 미분 방정식과 비슷하지만, 미분 대신 항들 간의 차이를 이용한다. 시간 척도 미적분학은 차분 방정식과 미분 방정식을 통합하여, 연속적인 데이터와 이산적인 데이터를 함께 다룰 수 있게 해준다.

응용 수학에서 이산 모델링은 연속적인 모델을 이산적으로 만든 것이다. 점화 관계를 사용하며, 이산화는 연속적인 모델을 이산적인 모델로 바꾸는 과정이다. 수치 해석이 그 예시이다.

학교 교육에서는 행렬, 집합, 순열, 조합, 논리, 증명, 수학적 귀납법, 점화식, 수열 등을 가르친다. 그 외에도 게임 이론, 마르코프 연쇄, 사회 선택 이론 등이 활용된다.

4. 1. 컴퓨터 과학

4. 2. 정보 통신

4. 3. 암호학

4. 4. 기타 응용 분야

5. 이산수학과 관련된 주요 문제들

이산수학은 많은 중요한 미해결 문제들을 포함하고 있으며, 이러한 문제들에 대한 연구는 학문 발전의 중요한 동력이 된다.^[18]

• 4색 정리: 그래프 이론에서, 1852년에 처음 언급되었지만 1976년에야 케네스 아펠과 볼프강 하켄이 컴퓨터를 이용하여 증명하였다.^[15] 이 문제는 평면 그래프의 각 영역을 인접한 영역과 다른 색으로 칠할 때 네 가지 색으로 충분하다는 것을 증명하는 문제이다.
• 힐베르트의 두 번째 문제: 다비트 힐베르트가 1900년에 제시한 문제로, 산술의 공리가 무모순임을 증명하는 것이었다. 그러나 1931년 괴델의 불완전성 정리에 의해 이것이 산술 자체 내에서는 불가능하다는 것이 증명되었다.
• 힐베르트의 열 번째 문제: 정수 계수를 갖는 다항식 디오판토스 방정식이 정수 해를 갖는지 여부를 결정하는 문제였다. 1970년에 유리 마티야세비치는 이것이 불가능하다는 것을 증명했다.
• P-NP 문제: 이론 전산학에서 가장 유명한 미해결 문제 중 하나로, 복잡도 종류 P (복잡도)와 NP (복잡도)가 같은지 여부를 묻는 문제이다. 클레이 수학 연구소는 이 문제의 최초 증명에 대해 100만달러의 상금을 제공한다.^[18]

6. 이산수학 교육

현재 많은 대학교 컴퓨터과학 관련 학과에서 이산수학을 전공 과목으로 채택하고 있다.^[10] Kenneth H. Rosen이 유명한 저자 중 한 명이다.

다음은 일본의 이산수학 교재 목록이다.

참조

_[1] 서적 Discrete Mathematics Prentice Hall 2008
_[2] 논문 Discrete and continuous: a fundamental dichotomy in mathematics https://scholarship.[...] 2021-06-30
_[3] 웹사이트 Discrete Structures: What is Discrete Math? https://cse.buffalo.[...] 2018-11-16
_[4] 서적 Discrete mathematics https://books.google[...] The Clarendon Press Oxford University Press
_[5] 서적 Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules, and Articles https://books.google[...] Mathematical Association of America 2009
_[6] 서적 Applied Discrete Structures https://discretemath[...]
_[7] 서적 Mathematics as a Service Subject Cambridge University Press
_[8] 서적 Discrete Mathematics in the Schools American Mathematical Society
_[9] 웹사이트 UCSMP http://ucsmp.uchicag[...]
_[10] 서적 Basic Proof Theory https://books.google[...] Cambridge University Press 2000-07-27
_[11] 서적 Handbook of Proof Theory https://books.google[...] Elsevier
_[12] 서적 KI 2001: Advances in Artificial Intelligence: Joint German/Austrian Conference on AI, Vienna, Austria, September 19-21, 2001. Proceedings https://books.google[...] Springer 2001-10-16
_[13] 논문 Cyclic proofs of program termination in separation logic 2008-01
_[14] 서적 Graphs on Surfaces https://www.press.jh[...] Johns Hopkins University Press 2001
_[15] 서적 Four Colors Suffice https://archive.org/[...] Penguin Books
_[16] 서적 Alan Turing: The Enigma Random House
_[17] 서적 Reconstruction the Tree of Life: Taxonomy And Systematics of Large And Species Rich Taxa https://books.google[...] CRC Press
_[18] 웹사이트 Millennium Prize Problems http://www.claymath.[...] 2008-01-12
_[19] 서적 入門有限・離散の数学；1　離散数学入門 朝倉書店