이산수학

(전산수학에서 넘어옴)

離散數學
Discrete Mathematics

이 항목은 전산수학로도 들어올 수 있다.

1 개요

이산적인 수학 구조를 다루는 수학의 한 분야이며 논리적인 지식이 많이 요구되는 학문이다. 여기서 '이산(離散)'은 이산가족 할 때의 그 이산으로, 값들이 연속적이지 않고 뚝뚝 떨어져 있는 것을 뜻한다. 예를 들면 1, 2, 3... 하고 자연수만으로 이루어진 수열을 적어놓았다면 실수 범위에서 연속적이지 않고 뚝뚝 떨어져 있으니 이산적이라 할 수 있다.

전산학에서 많이 쓰인다는 측면을 강조할 때에는 전산수학이라고도 칭한다.

2 컴퓨터공학과에서의 이산수학

수학적인 로직을 다루기 때문에 Circuit이나 논리구조 관련 풀이나 증명을 주로 배우고 디지털 논리, 자료 구조, 알고리즘 등 컴퓨터 학과에서 듣는 수업의 내용이 총망라되어 있다. 그러므로 자신이 속한 과가 4년제 컴퓨터 관련 과라면 반드시 배워야 할 과목이다. 실제로, 대부분의 대학교의 컴퓨터공학과에서 이산수학 과목이 전공필수인 경우가 많다. 다만, 수학과의 이산수학과 컴퓨터공학의 이산수학은 해당 과목에 대한 관점이 다르기에 내용에서 차이가 많이 난다.

3 7차 교육과정의 이산수학

7차 교육과정 초기 시절 수리영역 가형 선택과목으로도 있었는데, 공부를 전혀 안 하고서 눈치껏 풀어도 한두 문제쯤 맞출 수 있는 기이함을 보인다. 이유는 고등학교 수준의 경우 논리적으로 접근만 해도 다 풀리는 문제들이기 때문. 하지만 수포자들에게는 수1보다 더 괴랄한 과목이기도 했다 이런 면에서는 PSAT 상황판단 영역의 퀴즈문제와 비슷한듯. 그러나 선택률은 최저.[1]

이는 대학에서의 유용성을 고려해서 과목을 선택했기 때문이다. 7차 교육과정 초기 당시 미분과 적분 과목은 대학 미적분을 이해하기 위한 알파와 오메가와도 같은 과목이기 때문에 선택률이 99%에 달했다.

워낙 마이너해서 서점 검색대에 '이산수학'을 검색하면 몇만원짜리 컴퓨터공학 관련 책들만 잔뜩 나온다. 심지어 수학의 정석으로 유명한 홍성대조차 버린 과목. 고교 과정에서 7차 교육과정이 처음 적용되었던 해는 2003년이므로, 당시 고등학교 개정 교육과정 문제집은 학생들이 예비 고1이었던 2002년부터 나오기 시작했다. 2002년~2004년 정도까지 출시되었던 7차 교육과정 초기 판본에는 정석 시리즈 소개에서 '이산수학(발매예정)'이라는 문구가 들어가 있었다. 이산수학 교과서도 국정교과서였고, 이산수학 교재를 발간한 회사는 천재교육과 신사고 정도 뿐이었다.

당시 수리 가형(현행 수학 가형 또는 수학 B형)의 마지막 선택과목이었던 확률과 통계[2]는 실제로 책이 발매되기도 했고[3] 하지만 결국 이산수학은 떡밥만 남긴 채 7차 교육과정이 끝날 때까지 발매가 되지 않았다.

이는 사실 정석 자체가 일본 참고서를 기반으로 번역하고 짜깁기한 책이라 그러한 것인데, 비교적 최근에 추가된 이산수학에 대한 내용이 당시 일본 참고서 원본에 제대로 나오지 않았기 때문이다. 그래서인지 개정 교육과정에서는 빠졌다.(하지만 몇몇 개념들은 앞으로 뺐다. 행렬의 그래프라든가)[4]

단원은 행렬과 그래프, 알고리즘과 순서도, 분할 정도 된다.

4 기타

학부 컴퓨터과학의 이산수학 과목에서 배우는 이산수학 자체는 그다지 어렵지도 않고, 양도 많지가 않기때문에 보통 논리학을 포함시켜 배우는 경우가 많다. 또한, 아무래도 해석학이나 다른 전통적인 수학분야들에 비해 최신분야에 속하기때문에 배우는 내용 자체도 아직 그다지 표준화가 되어있지 않아 교수마다 가르치는 내용에 대한 차이가 크게 벌어지기도 한다. 일단, 한학기동안 배우는 것들을 살펴보면...

먼저 자연수와 정수의 구성방법이다. 그냥 수학적 귀납법과 Modular arithmetics 정도라 그다지 어렵지 않다. 교수에 따라 type theory 혹은 recursion theory(computability) 를 첨가시켜 가르치는 경우도 있다.

그리고, 조합론. 중고교때로 보면 경우의 수. 원래 조합론은 lattice, counting function, incidence function, generating function, matroids 등을 기본으로 배우지만, 보통 컴공과 학생들에게는 불가능에 가깝기 때문에[5] 고교과정에 가깝게 재미있게 배운다. 대표적인 문제로는 n명이 모자를 한곳에 벗어 뒀다가 다시 썼을 때, 한명도 자신의 모자를 안 쓸 확률 같은거. 쉬워 보이지만, 고등과정이 아니다[6]. 이것들을 쉽게 표현하기 위한것이 생성함수(Generating function, G.F.)인데, 테일러전개처럼 등호의 왼쪽은 닫힌형태(sin), 오른쪽은 차수가 무한이 올라가는 다항식으로 되어 있다. 각 차수의 계수가 어떤 수열의 항이 된다. 해석학에서는 수렴반경[7]이 중요한 반면, 이산수학에서는 다항식의 계수가 중요하기 때문에 수렴반경은 아웃오브안중. 성격이 다른 분야이므로.

다음으로는 그래프 이론. 색칠하기. 꼭지점(vertex)에 색을 칠하고 선분(edge)으로 이어져 있으면 다른 색을 칠하도록 할 때, 주어진 그래프는 몇개의 색으로 칠할 수 있을까, 하는 문제다. 단, 최소한의 색만 칠해야 한다..[8] 최단거리찾기 등. 이부분은 실제 프로그래밍에 응용가능한 알고리즘이 종종 등장하니 알아두면 좋다. 원래 대학에서 배우는 그래프 이론은 확률론이 더해지는데, 확률론은 이산수학과는 관련이 별로 없고(당연하겠지만, 연속체 구조다.), 더이상 구성적(알고리즘적)인 내용이 별로 안나오기 때문에 컴공생 입장에서는 고교레벨의 그래프이론까지만 배운다. 물론, 배우고싶어도 사전에 배워야 하는 확률론이 해석학과 측도론등을 베이스로 하고 있어 컴공생에게는 좀 난해하기때문에 못배운다.
여기까지는 일반적으로 알고있는 이산수학으로, 고교수학과 크게 다른것도 없고 그다지 난해한 부분도 찾아보기 힘들어 교수나 학생이나 죽죽 훑고들 넘어간다. 하지만...

중반부를 넘어갈즈음 끝판왕인 논리와 증명이론이 등장한다. 쉽게 말하면 컴퓨터 과학의 언어에 대해 배우는 부분으로, 명제논리와 일차언어의 문법과 모델이론에서 시작하여 Herbrand-Interpretation, Skolemization, 데이비스-퍼트남 증명방법등을 배우며 운이 좋다면 본격적으로 수학의 논리학과 컴퓨터과학이 연결되는 부분인 proof as a program 으로 유명한 Curry-howard correspondence도 구경할 수 있는 안드로메다로 향하게 된다. 물론, 컴공생으로서, 그것도 반학기만에 이것들을 제대로 이해하고 응용문제를 푼다는것은 거의 불가능에 가깝기 때문에 이런것도 있다식으로 관광을 하는 정도지만, 그럼에도 관광을 당하는것에는 변함없다. 여기서 배우는 것들은 컴퓨터 과학의 언어임과 동시에 수학의 언어이기도 하기때문에(말하자면 컴퓨터 과학과 수학은 같은 뿌리를 갖고있다.), 이부분부터는 실제 수학과 수학만큼 난이도가 급상승하게 된다. 물론, 위에서 말한것과 반대의 의미로 운이 좋다면 이 부분을 제끼는 교수를 만나게 될 것이나, 그렇지 않으면 이 부분을 극복하는 것이 이 과목의 핵심이다.

5 관련 항목

  1. ↑ 1000명도 되지 않았다. 상당수의 일반 고등학교에선 수업조차 개설하지 않는 과목이었다.
  2. ↑ 지금의 적분과 통계에서 확률, 통계 부분만 떼어 오고 중학교 통계 내용을 합하면 바로 이 과목이 된다. 다만 수학1의 확률-통계 부분과 별 차이 없는 잉여과목이었다.(...)
  3. ↑ 통계 문제 풀 때 시뮬레이션을 실제로 해 보라고 프로그램을 넣은 CD까지 같이 묶어서 팔았다!
  4. ↑ 이마저도 2009 개정 교육과정에선 빠진다. 즉, 이산수학의 모든 과정이 아예 삭제되었다.가 아니다. 2009 개정 교육과정의 확률과 통계에 2007 개정 교육과정일때 빠져있었던 분할이 들어갔다. 그러나 2015 개정 교육과정에서 빠지면서 모든 이산수학의 내용이 고교 과정에서 삭제되었지만 경우의 수와 중복조합 때문에 완전히 삭제되었다고 볼 수 없다.
  5. ↑ 물론 교수진과 해당 학교가 수학에서 중점을 두는 분야에 따라 다르지만, 저것들은 수학과에서도 일반적으로 학부때는 구경도 못하는 경우가 많다.
  6. ↑ 고등과정에서도 단순히 수형도를 그려 경우의 수를 세는 문제로 출제될 때도 있지만, 일반적인 풀이법은 배우지 않는다. 교란수열이라고도 한다.
  7. ↑ 차수가 무한하니까 절댓값이 어떤 수보다 크면 발산한다. |r|>1이면 1+r+r^2+...가 발산하는 것처럼.
  8. ↑ 참고로, 4색정리는 그냥 유명한 문제일뿐 매우 난해하기때문에 실제 이산수학에서는 보통 그냥 6가지 색으로 가능하다는 것까지만 배운다. 처음 문제제기 된 이후 100년이 넘도록 매년 한개 이상의 오류가 섞인 증명이 발표되었었고, 십여년전에 드디어 오류가 없는 증명이 등장했다고 여겨지고 있는데 이 증명은 무려 1500 가지 이상의 경우의 수를 포함하고, 이 1500 가지의 경우의 수를 나누기 위한 룰만 600개가 넘는다. 그리하여, 결국 컴퓨터의 도움을 받아 증명을 한 케이스이다.