Discrete Mathematics 이산수학
이산수학은 연속적(continuous)이 아닌 불연속(discrete) 객체를 다루는 수학의 한 분야
예를 들어, 미적분학은 주로 연속적인 대상을 다루며 이산수학에서는 다루지 않는다.
이산수학에서는 컴퓨터 과학에서 필요로 하는 수학적 토대를 제공함
discrete objects의 예:
- 정수
- 컴퓨터 프로그램에서 각 단계
- 도로망에서 A지점에서 B지점으로 이동하는 서로 다른 경로
- 로또복권에서 당첨이 될 경우의 수
이산수학으로 해결하려는 다양한 문제들
- 논리적인 사고를 통한 상황의 논리적 분석
- 다양한 증명 방법을 통한 엄밀한 증명
- 그래프를 통한 통신 네트워크의 분석
- 행렬과 행렬식을 통한 일차 방정식의 수립과 해법
- 부울 대수와 스위치 이론을 통한 하드웨어의 이해
- 문법과 언어에 대한 이해
- 트리 개념을 적용한 실세계 문제 풀이
- 이산적인 확률을 통한 통계적 분석
- 교통망에서 두 도시를 연결하는 최단 거리
- 알고리즘의 이해와 분석
- 오토마타를 통한 이론적 기계 작동의 기본 원리를 이해
이산 수학의 이해
Mathematical Reasoning (수리적 추론): 수학적 주장 및 논증(mathematical arguments and proofs)에 대하여 읽고, 이해하고, 구성하는 능력
Combinatorial Analysis (조합분석): 서로 다른 종류의 객체들의 경우의 수를 계산하는 방법
Discrete Structures (이산구조):
- 이산구조는 객체와 그들 사이의 관계를 나타내는 추상적인 수학적 구조
- 이산구조의 예: 집합, 순열, 관계, 그래프, 트리 및 유한 상태 기계 등
Algorithmic Thinking (알고리즘적 사고): 알고리즘은 특정 문제를 해결하기 위한 일련의 과정.
- 알고리즘적 사고
1. 특정 문제에 대한 알고리즘을 지정하고,
2. 실행에 필요한 메모리 및 시간을 분석하며,
3. 알고리즘이 문제에 대한 해답을 제대로 생성하는지 확인
Applications and Modeling (응용 및 모델링):
- 이산수학은 컴퓨터 분야 뿐만 아니라 화학, 생물학, 언어학, 지리학, 비즈니스 등 많은 영역에서의 문제를 해결하는 데 적용할 수 있음.
- 이산수학의 주제를 이해하고 다양한 영역에서 새로운 모델을 개발할 수 있는 능력을 기르는 것이 중요함
인공지능과 이산수학
- 논리적 분석과 적절한 정보의 검색 - 명제와 논리
- 정보의 판단 - 그래프, 트리, 집합론
- 정보의 연관성 - 관계, 함수, 형식언어, 문법
- 복잡한 연산 - 행렬과 행렬식
- 복잡한 문제의 시스템화 - 오토마타
- 문제 해결 - 알고리즘을 이용한 문제 해결
출처 : http://bigdata.dongguk.ac.kr/lectures.html
이산집합
1) 이산집합
자연수와 일대일 가능한 집합이거나 유한집합을 이산집합이라고 한다. 즉, 원소의 개수를 셀 수 있는 집합이다.
2) 이산수학(discrete mathematics)
이산수학은 이산집합 위에 정의된 수와 그들의 성질에 대하여 연구하는 수학의 한 분야이다. 고등학교 교육과정에서 이산수학을 찾아보면 수학Ⅰ의 '경우의 수'와 관련한 단원이며, 심화과정으로 이산수학과목이 있다.
3) 이산수학의 특성
이산수학이 다른 수학분야와 가장 다른 점은 사전지식이 필요 없다는 것이다.
예를 들어보자. 적분을 공부하기 위해서는 실수를 알아야 한다. 수열을 알아야 하고 수열의 극한과 무한급수를 알아야 한다. 이를 확장시킨 함수의 극한을 알아야 한다. 당연히 방정식은 기본적으로 알아야 한다. 미분을 알아야 하고, 삼각함수, 지수, 로그함수 등의 성질을 알아야 비로소 적분을 공부할 수 있다. 하지만, 서로 다른 5명이 한줄로 앉는 방법의 수를 구하는 경우에는 사전지식이 거의 필요 없다. 어떻게 하면 보다 편리하게 셀 수 있을지에 대해서만 고민하면 된다. 이산수학은 학생들의 두뇌개발에 적절한 과목이며 디지털 시대와 더불어 중요성이 더욱 부각되고 있다.
4) 유리수는 이산집합이다.
유리수는 이산적인 수이다. 얼핏 생각하기에 정수는 띄엄띄엄 값이 존재하지만 유리수는 빽빽하게 존재할 것 처럼 여겨진다. 하지만 유리수는 정수와 마찬가지로 띄엄띄엄 존재한다.
유리수는
로 구성된다. 따라서 유리수는 두 개의 정수로서 구성됨을 알 수 있고,
로 생각한다면 모든 유리수는 좌표평면에 한점 한점 찍힐 것이다.(이때 각각의 좌표는 정수이고 x축 위에는 점이 없다.) 결국 유리수를 센다는 것은 좌표평면의 정수 점들을 세는 것과 대동소이한 일이 된다. 이처럼 유리수는 셀 수 있는 수들의 집합 즉, 이산집합이다.
출처 : 네이버 지식백과 / 통합논술 개념어 사전, 2007. 12. 15., 한림학사
離散數學 / Discrete mathematics
실수처럼 연속성이 있는 것들이 아니라 주로 정수, 논리 연산같이 서로의 값들이 연속적이지 않고 뚝뚝 떨어져 있거나 구분되어 '셀 수 있는' 것들을 주로 연구하므로 '유한 수학'이라고도 불린다.
이산수학에서는 실수 같이 연속적인 성질이 있는 대상이 아니라 주로 정수, 그래프, 논리 연산 같이 서로 구분되는 값을 가지는 대상을 연구한다. 따라서 이산수학에서는 미분적분학이나 수치 해석같이 '연속적'인 분야에서 다루는 주제는 다루지 않는다. 이산적인 대상은 정수로 개수가 열거되는 경우가 많다. 공식적으로, 이산수학은 가산집합을 다루는 수학의 한 부류로 특징지을 수 있다. 하지만 이산수학이라는 용어에 대해 정확한 정의는 내려져 있지 않다. 사실, 이산수학은 포함된 주제에 의해서 정의되기 보다는, 이산수학이 다루는 주제가 아닌 것들에 의해서 정의된다.
이산수학에서 연구하는 집합의 종류는 무한 혹은 유한집합이다. 이산 수학중에서도 유한 집합을 다루는 한 분야에 대해서 가끔씩 유한 수학이라는 용어가 쓰이기도 한다.
이산적인 과정을 통해서 데이터를 저장하고, 동작하는 디지털 컴퓨터의 개발으로 인해 20세기 후반에 이산수학에 대한 연구가 점점 활기를 띄기 시작했다. 이산수학에 포함된 개념과 기호들은 컴퓨터과학자들이 알고리즘, 프로그래밍 언어, 암호학, 계산이론 등의 문제를 연구하는 데 유용하였다.
원래 전통적으로 기하학을 제외한 대수학은 연속체 수학이 아니라 이산수학의 영역이었으나 [1], 실수가 정의되고 뉴턴 역학과 미적분학이 태동한 이후로 해석 기하학과 접목되며 연속체 수학이 일반적인 수학을 일컫게 된다. 그러나 통계역학과 양자역학이 등장하고 나서 다시 서로 이산되어 있는 양자들을 확률의 형태로 재정의할 필요성이 생기게 되었으며 이산수학의 방법론이 크게 발전하게 된다.
'이산(離散)'은 이산가족 할 때의 그 이산이다. 전산학에서 많이 쓰인다는 측면을 강조할 때에는 전산 수학이라고도 칭한다.
이산 구조(discrete structure)에 관한 수학이다. 수학을 커다란 두 줄기로 양분하면 이산 구조와 연속체 구조가 나온다. 이산 구조와 연속체 구조는 일반적으로 '셀 수 있는 것'과 '셀 수 없는 것' 정도로 구분하며 [2] 개중에 연구 대상이 '셀 수 있는 오브젝트'일 경우 보통 이산수학이라 칭한다. 이 '셀 수 있는 오브젝트'는 다시 두 가지로 나뉘는데 '알고리즘적인 것'과 '비알고리즘적인 것'이 그것이다. 덕분에 컴퓨터과학을 전공하면 공부하게 된다.
집합론(유한)
수리 논리학에 속하는 분야이며. 배우는 이유는 아무래도 모든 수학의 기본이 되는 집합의 개념을 배우는 학문이기 때문이다. 필요로 하는 수학적 사전 지식이 매우 적고 타 수학 분야와 관련성도 비교적 적은 편임과 동시에 집합론 자체도 매우 큰 분야이기 때문에 해외의 경우 집합론을 전공 분야로 정할 시 선형 대수와 실 해석의 쌩기초만 배운 후 이후부터는 석사 졸업 때까지 거의 수리 논리와 집합론 과목만 들을 수 있는 대학도 있긴 하다. 물론 그 만큼의 교수진이 받쳐 줘야 가능한 커리큘럼이다. 보통의 경우는 집합론을 전공으로 정하더라도 학부 말이나 석사쯤 간 다음에 논리학과 같이 묶어서 본격적으로 배우기 시작하는데 사실 이런 '기본 루트'를 쫓아갈 경우 석사 졸업 때까지도 기초 수준을 벗어나기가 힘들기 때문에 상당한 수준의 독학이 요구된다. 보통 수학을 잘 모르는 이들은 '집합'을 중학교부터 배운다고 무시하는 경우가 많은데 수학 분야 중 가장 추상적인 분야 중의 하나이며 도저히 상상 불가능한 '이상하고 복잡한' 집합들을 순수 논리에 의지해서 헤쳐나가야 하며 집합론 공리계 자체를 다루는 학문이기 때문에 사실 보통의 인간 직관이 가장 안 통하는 분야 중 하나라 '쉽다'와는 당연히 거리가 매우 멀다.
원문에는 각 항목에 링크가 걸려 있음 ^^
집합 : 원소 / 함수 / 수열 (유한 수열만 다룸) / 급수 (유한 수열의 급수만 다룸) / 대각선 논법 / 조합론 / 경우의 수 (합의 법칙, 곱의 법칙) / 순열 / 조합 / 파스칼의 삼각형 / 분할수 / 제1종 스털링 수 / 제2종 스털링 수 / 비둘기 집의 원리 / 도박사의 오류 / 4색 정리
크게 다음과 같은 사고가 이산수학적 아이디어로 엮인다.
되는 것, 안 되는 것 : 어떤 것에 대하여 여러 경우를 갈라서 조건에 부합하지 않는(모순되는) 것 찾기 (예: 절댓값이 취해진 변수에 대한 방정식)
개수 세기 (예: 격자점 일일이 세기, 정수의 개수 세기 등)
개수를 일일이 세지 못할 때 곱의 법칙 아이디어로 신속하게 해결하기
시행착오법 : 예를 들면
같이 대수적으로 풀 수 없는 방정식에서 직관적으로 x=4를 뽑아낼 수 있는 역량. 이러한 식으로 x=2, 3, 4, ... 처럼 하나씩 대입해보아야 풀리는 문제들을 시행착오법이라 하는데, 물론 해당 예제도 그렇지만 완전 운빨좆망겜은 아니다. 그래프의 개형 및 지수 함수의 성질에서 그리 크지 않은 수에서 한번의 교점이 생기리라는 것을 쉽게 추측할 수 있고 5를 넣어보면 전자가 커지기 때문에 5 이하의 정수들을 하나씩 넣어보고 유리수 영역으로 범위를 좁혀가면 된다. 물론 범위를 좁힐 수 있다는 이야기지 정확한 해를 찾기란 딱 떨어지는 문제가 아니면 어렵다.
규칙성을 갖는 수의 나열에서 천문학적인 순서에 있는 값 추론하기. 수열에서 배우지만, 그 이전 과정에서는 언급이 아예 없다.
즉, 이산수학은 수학을 다루는 데 있어서 기본기와 같다. 이산수학 자체가 워낙 단순한 내용들로 구성되어있어서 얕보기 일쑤지만, 이산수학 문제는 풀이의 핵심이 아예 그 자체이기 때문에 더럽게 꼬기 시작하면 밑도 끝도 없이 난이도가 천정부지로 치솟는다. [7] [8]이 부분에 있어서는 가히 미적분이나 대수학 따위는 명함도 못 내민다.
국제수학올림피아드에서 대한민국 사람들이 가장 못하는 영역도 조합 영역, 다시 말해 이산수학의 한 분야이다. 고난도 문제도 조합 영역에서 자주 출제된다.
문과 쪽에서도 대학원 진학 시에는 (순수 문학이 아닌 한[9]) 통계적 방법을 활용해 연구하는 경우가 많아지고 있으며, 이 과정에서 이산수학에 대해 간단하게나마 접해 볼 가능성이 있다. 그러나 통계 쓴다는 사회과학 분야에서도 이산수학보다는 오히려 정규분포로 대표되는 미적분의 논리를 따라서 방법론이 세워진 분야들이 굉장히 많아서, 이산 확률 분포 같은 것을 커리큘럼에서 아예 빼 버리는 경우도 실제로 있다. 이는 무책임한 것도 아니고 학문적으로 엄밀하지 못한 것도 아니다.[10] 그건 그저, 이산수학을 배울 시간에 차라리 연속적 데이터를 주물럭거리며 모수를 추론하는 게 훨씬 더 연구 생산성을 높인다고 판단했기 때문이다.
수리적인 것들을 다루기 때문에 논리 회로 설계를 위한 기초 논리학 및 불 대수 관련 풀이나 증명을 먼저 배우고 이외에도 컴퓨터 대수, 자료구조, 알고리즘 등 컴퓨터 학과의 다른 수업에서 나오는 수학적 개념들을 총망라한다. 그러므로 자신이 속한 과가 4년제 컴퓨터과학 관련 학과라면 반드시 배워야 할 과목이다. [11] 실제로, 대부분의 대학교의 컴퓨터 학과에서 이산수학 과목이 전공 필수인 경우가 많지만 전공 선택 강의가 있는 다른 대학교도 몇 군데 있다.
전체적인 내용에 대해 개괄적으로 설명하면, 먼저 자연수와 정수의 구성 방법이다. 그냥 수학적 귀납법과 Modular arithmetics 정도라 그다지 어렵지 않다. 교수에 따라 type theory 혹은 recursion theory(computability) 를 첨가시켜 가르치는 경우도 있다.
그리고, 조합론. 중고교때로 보면 경우의 수. 원래 조합론은 lattice, counting function, incidence function, generating function, matroids 등을 기본으로 배우지만 대학에 따라 다르다. 교수진과 해당 학교가 수학에서 중점을 두는 분야에 따라 다르지만, 저것들은 수학과에서도 일반적으로 학부때는 구경도 못하는 경우가 많다. 대표적인 문제로는 n명이 모자를 한 곳에 벗어 뒀다가 다시 썼을 때, 한 명도 자신의 모자를 안 쓸 확률 같은 거. 쉬워 보이지만, 중등 과정이 아니다. [12] 이것들을 쉽게 표현하기 위한 것이 생성 함수(Generating function, G.F.)인데, 테일러 전개처럼 등호의 왼쪽은 닫힌 형태(sin), 오른쪽은 차수가 무한이 올라가는 다항식으로 되어 있다. 각 차수의 계수가 어떤 수열의 항이 된다. 해석학에서는 수렴 반경 [13]이 중요한 반면, 이산수학에서는 다항식의 계수가 중요하기 때문에 수렴 반경은 아웃 오브 안중. 성격이 다른 분야다.
다음으로는 그래프 이론. 색칠하기. 꼭지점(vertex)에 색을 칠하고 선분(edge)으로 이어져 있으면 다른 색을 칠하도록 할 때, 주어진 그래프는 몇 개의 색으로 칠할 수 있을까, 하는 문제다. 단, 최소한의 색만 칠해야 한다. [14] 최단 거리 찾기 등. 이 부분은 실제 프로그래밍에 응용 가능한 알고리즘이 종종 등장하니 알아두면 좋다. 원래 대학에서 배우는 그래프 이론은 확률론이 더해지는데, 확률론은 이산수학과는 관련이 별로 없다.(당연하겠지만, 연속체 구조다.) 여기까지는 일반적으로 알고 있는 이산수학으로, 그다지 난해한 부분도 찾아보기 힘들어 교수나 학생이나 죽죽 훑고들 넘어간다. ...
출처 : 나무위키. 원문으로 더 상세한 내용들을 볼 수 있다.
이산수학 - 나무위키
이산수학에 대해 설명하는 문서.
namu.wiki