이산수학

 



1. 개요
2. 수학에서의 '이산수학'
2.1. 주요 분야
2.2. 교재
2.3. 문제의 어려움
2.4. 중·고등학교 과목에서의 안습한 위치
3. 교과로서의 '이산수학'
3.1. 7차 교육과정 고등학교 과목 이산수학
3.2. 현황 및 잘못된 분류: 이산수학이 '확률과 통계'다?
4. 컴퓨터공학과에서 일컫는 '이산수학'
5. 관련 문서


1. 개요

이산수학에 대해 설명하는 문서. 수학 영역으로서, 수학 교과로서, 컴퓨터 관련으로서의 이산수학이 가리키는 방향이 다소 다르므로 유의 바람.
대수학을 비롯한 근대 수학이 꽃피기 전까지 가히 수학의 여왕으로 군림했다고 할 수 있는 분야다. 정수론에서 다루는 정수(整數)가 Integer이 아니라 Number로 번역되는 것만 봐도 알 수 있다. 실제로 대수적 수까지 포함하여 수론으로 통칭하기도 한다. 현대 수학의 발전 이후에는 주로 대수학의 범주에 들어가게 되었으나, 문제 해결을 위한 방법론은 실로 다양하다. 대수학적 방법론 외에도 디오판토스 방정식과 타원곡선 등을 다루는 데에는 해석적 방법론이, 격자점 문제 등을 다루는 데에는 기하학적 방법론이 사용되기도 한다. 또 20세기 이전에는 정치적으론 그다지 각광을 받지 못하는 수학자들만의 분야였으나, 양차 세계대전 당시 소수를 기반으로 한 암호 체계가 발달하면서 사회적으로도 주목받게 되었다. 이와 동시에 우리 현실과 밀접하게 연관되어 있는 계산적 정수론이 발전하게 되었다. 수많은 정수론자들이 리만가설을 증명하려 노력하고 있지만 아직 증명을 못하고 있다. 넷상에서 리만가설이 증명되면 RSA 암호체계에 결함이 생긴다는 이야기가 떠도는데, 근거없는 이야기이다. 이 이야기는 다큐멘터리 등에서 수학의 유용성을 어떻게 해서든 보이려 일부러 표현을 모호하게 하였기 때문으로 보이는데, 리만가설과 RSA와의 관계는 소수를 다룬다는 사실 이외에는 없다.


2. 수학에서의 '이산수학'

'''離散數學 / Discrete Mathematics'''
실수처럼 연속성이 있는 것들이 아니라 주로 정수, 논리 연산 같이 서로의 값들이 연속적이지 않고 뚝뚝 떨어져 있거나 구분되는 것들을 주로 연구하므로 '유한 수학'이라고도 불린다.
예를 들면 1, 2, 3... 하고 자연수만으로 이루어진 수열을 적어놓았다면 실수 범위에서 연속적이지 않고 뚝뚝 떨어져 있으니 이산적이라 할 수 있다. 1과 2 사이에는 보통 1<n<2인 소수 등을 예로 들면서 무수히 많은 수가 있다고 하지만 이산수학에는 그게 없다. 1보다 크면서 가장 작은 수는 무조건 2다. 전문적으로는 열린 집합인 위상 공간에 대한 수학이라고도 한다.
'이산(離散)'은 이산가족 할 때의 그 이산이다. 전산학에서 많이 쓰인다는 측면을 강조할 때에는 전산수학이라고도 칭한다.

2.1. 주요 분야

이산구조(discrete structure)에 관한 수학이다. 수학을 커다란 두 줄기로 양분하면 이산구조와 연속체 구조가 나온다. 이산구조와 연속체 구조는 일반적으로 '셀 수 있는 것'과 '셀 수 없는 것' 정도로 구분하며[1] 개중에 연구 대상이 '셀 수 있는 오브젝트'일 경우 보통 이산수학이라 칭한다. 이 '셀 수 있는 오브젝트'는 다시 두 가지로 나뉘는데 '알고리즘적인 것'과 '비알고리즘적인 것'이 그것이다. 덕분에 컴공에서도 꽤 배운다.
수리논리학에 속하는 분야이기도 하고, 이산수학에 속하는 분야이기도 하다. 아마도 모든 수학의 기본이 되는 집합의 개념을 배우는 학문이기 때문일 듯. 필요로 하는 수학적 사전지식이 매우 적고 타 수학 분야와 관련성도 비교적 적은 편임과 동시에 집합론 자체도 매우 큰 분야이기 때문에 해외의 경우 집합론을 전공분야로 정할 시 선형대수와 실해석의 쌩기초만 배운 후 이후부터는 석사 졸업 때까지 거의 수리논리와 집합론 과목만 들을 수 있는 대학도 있긴 하다. 물론 그만큼의 교수진이 받쳐 줘야 가능한 커리큘럼이다. 보통의 경우는 집합론을 전공으로 정하더라도 학부 말이나 석사쯤 간 다음에 논리학과 같이 묶어서 본격적으로 배우기 시작하는데 사실 이런 '기본 루트'를 쫓아갈 경우 석사 졸업 때까지도 기초 수준을 벗어나기가 힘들기 때문에 상당한 수준의 독학이 요구된다. 보통 수학을 잘 모르는 이들은 '집합'을 중학교부터 배운다고 무시하는 경우가 많은데 수학 분야 중 가장 추상적인 분야 중의 하나이며 도저히 상상 불가능한 '이상하고 복잡한' 집합들을 순수 논리에 의지해서 헤쳐나가야 하며 집합론 공리계 자체를 다루는 학문이기 때문에 사실 보통의 인간 직관이 가장 안 통하는 분야 중 하나라 '쉽다'와는 당연히 거리가 매우 멀다.


2.2. 교재

  • 이산수학 (Kenneth H. Rosen 저, 맥그로힐) [원제: Discrete mathematics and its applications.]
이 책의 장점은 서술이 많다는 점이다. 다른 책들처럼 예제 딸랑 던져주고 문제해설하는 식이 아니라 개념을 충실하게 서술했다는 점이 매우 큰 장점이다. 한국의 책들이나 다른 책들은 수학문제집이라는 느낌을 주지만, 이 책은 개념에 대한 설명이 충실하여 급할 때는 예제 없이 개념만 읽어도 좋다. 충실한 설명 덕분에 수학과 뿐만 아니라 컴퓨터공학과에서도 많이 사용하는 교재이다. 현재 8판까지 나와 있고 번역서도 있다. 하지만 번역서는 번역을 하다가 포기한 듯한 수준으로, 도저히 이해되지 않는 어색한 문장이 있으며, 영어 어순을 그대로 두어 영어 원문이 무엇인지 능히 짐작할 수 있을 정도로 번역을 대충 했다. 또한 결정적으로, 문제 해설이 전혀 번역되어 있지 않다. [2]
  • Schaum's Outline of Discrete Mathematics (Seymour Lipschutz 저, 맥그로힐)
위 책과 마찬가지로 맥그로힐 출판사에서 출판한 책 인데 저자가 다르고 책 구성도 다르다. 참고로 위 책은 아예 학부 과정을 넘어서 대학원 과정까지 욱여넣었는데 이 책은 딱 학부과정에 쓸 만한 내용까지만 넣어서 읽기 편하다. 대략 4분의 1 밖에 되지 않는다! 사실 Outline 책은 전공서적이라고 하긴 어렵고 전공서적을 축약한 문제집 같은 것이라고 보면 좋다. 말 그대로 틀 잡아주는 부류의 책들이다. 요약본이라고 생각하면 간단하다.

2.3. 문제의 어려움

수학에서 매우 큰 비중을 차지하고 있음에도 불구하고[3] 중학교, 고등학교에서는 용어조차 언급되지 않는 영역[4]으로 사실 이산수학적 감각은 '''모든 문제 풀이의 근원'''이라고 감히 말할 수 있으며 거의 모든 학술 분야에서 응용된다. 특히 수능이나 PSAT 자료해석은 이 소양이 기본적으로 깔려있어야 한다. 같은 카테고리인 대수, 해석, 기하뿐만 아니라 아예 화학[5], 생명과학[6], 경제 등 고난도 문항에서 이 이산수학 센스가 필요하다.
크게 다음과 같은 센스가 이산수학식 센스로 엮인다.
  • 되는 것, 안 되는 것: 어떤 것에 대하여 여러 경우를 갈라서 조건에 부합하지 않는(모순되는) 것 찾기 (예: 절댓값이 취해진 변수에 대한 방정식)
  • 개수 세기 (예: 격자점] 일일이 세기, 정수의 개수 세기 등)
  • 개수를 일일이 세지 못할 때 곱의 법칙 아이디어로 신속하게 해결하기
  • 시행착오법: 예를 들면 $$ 2^{x}=12+x~(x>0) $$같이 대수적으로 풀 수 없는 방정식에서 직관적으로 $$x=4$$를 뽑아낼 수 있는 역량. 이러한 식으로 x=2, 3, 4, ... 처럼 하나씩 대입해보아야 풀리는 문제들을 시행착오법이라 하는데, 2017학년도 이후 수학 영역(30번 문항), 과학탐구 영역(화학I, 화학II, 생명과학I 고난도 문항)에서 굉장히 많이 요구된다. 특히 과탐은 시간이 촉박하기 때문에 얻어걸린 정수 값(속된 말로 운빨좆망겜)에 큰 희비가 갈린다.
  • 규칙성을 갖는 수의 나열에서 천문학적인 순서에 있는 값 추론하기. 수열에서 배우지만, 그 이전 과정에서는 언급이 아예 없다.
즉, 이산수학은 수학을 다루는 데 있어서 기본기와 같다. 이산수학 자체가 워낙 단순한 내용들로 구성되어있어서 얕보기 일쑤지만, 이산수학 문제는 풀이의 핵심이 아예 그 자체이기 때문에 더럽게 꼬기 시작하면 밑도 끝도 없이 난이도가 천정부지로 치솟는다. 이 부분에 있어서는 가히 미적분이나 대수학 따위는 명함도 못 내민다. 고난도 미적분 추론 문항에서도 경우를 나누는 센스가 바로 이 이산수학에서 비롯된 것이기도 하다. 미적분 추론 문항에 이산수학 센스가 빠지면 문제 수준을 중급 이상으로 때려놓기 힘들다. 수학 외적으로도 이산수학적 테크닉은 대단히 중요하다. 수능의 화학1과 생명 과학1은 죄다 이런 문항이다. 또한 문제적 남자 같은 데서 나오는 수학 문제에서도 주로 사용하는 센스가 바로 이산수학이다. 보통 그런 문제를 풀면 그 사람이 똑똑하다는(IQ가 높다는) 인식이 생기지만, 사실 그걸 떠나 이 이산수학 영역에 능한 것일 확률이 높다.
다시 말해, 이상하게 본인이 미적분은 잘하지만, 머리를 써야 하는 데서 취약하다 싶으면 십중팔구 이 이산수학을 못하는 것이다. 2009 개정 교육과정 시기 대수능 30번 미적분 킬러 문제 풀이 역시 실제로 경우의 수를 나눠가면서 따져야 하는데, 미적분 자체가 지나치게 어려운 것이라기보단 그냥 이 이산수학식 센스가 과하게 요구되는 경향을 따라가지 못해서 어려워 보이는 것이다. 대표적으로 2018 수능 수학 나형 30번 문항은 얼핏 보면 '이차함수+수열의 극한+적분법' 같으나, 결국 자연수 k('''이산수학'''적인 조건)을 이용하는 것이 관건이었다.
국제수학올림피아드에서 대한민국 사람들이 가장 못하는 영역도 바로 이 순수 이산수학이다. 이산수학을 간단히 토막 개념으로 이용하는 분야가 통계학으로 이어지는데, 문과라도 사회과학 계열 친구들은 대학 진학 순간부터 아무리 해도 통계학의 마수에서 벗어날 수 없을 것이다. 수학이 싫어서 문과 쪽으로 대학 왔는데 왜 나는 통계학이라는 이름의 이산수학을 공부하고 있냐며 내가 이러려고 문과에 왔나 자괴감이 들어를 외치게 된다. 이산수학은 수능 끝난 고3 시기라도 한번 공부를 해두자. 물론 어문계열 진학자라면 한숨 좀 돌릴 수 있겠지만 이들도 대학원을 선택하게 된다면 '''문학 전공이 아닌 이상''' 최소한의 이학 소양이 필수다. 대학원에서는 어학 전공자들도 양적연구방법론 때문에 기본 통계학 감은 갖고 있어야 한다.

2.4. 중·고등학교 과목에서의 안습한 위치

크게 수학에서는 대수, 기하, 해석, 이산수학(정수론, 조합론, 집합론)으로 구분하려는 성격이 있는데, 중등교육에서도 '이산수학'은 실질적인 비중이 매우 큼에도 불구하고 용어 언급이 전혀 안 되는 안습한 수준이다. 그러나 고등학교 1학년 과정은 거의 절반이 이산수학으로 구성되어있으며, 실질적으로 매우 중요한 기반이 된다.
흔히 중·고등학교 과정에서 접할 수 있는 이산수학엔 경우의 수(또는 조합론), 순열, 조합, 수열, 집합론 등이 대표적이다.
  • 2015 개정 교육과정 기준 '이산수학'의 내용
    • 수학 1(중학): '소인수분해', '정수와 유리수'(정수 부분), '통계'
    • 수학 2(중학): '확률'
    • 수학 3(중학): '대푯값과 산포도'
    • 수학: '집합과 명제', '함수'(함수의 정의, 역함수, 합성함수 부분), '경우의 수'
    • 수학Ⅰ: '수열'
    • 확률과 통계: '순열과 조합', '확률', '통계'(이산확률변수, 이항분포 부분)
  • 과거에 '일반선택과정'에 있었으나 빠진 내용
    • 소수, 이진법, 십진법, 비둘기집의 원리, 포함배제의 원리, 알고리즘과 순서도, 세 개 이상의 점화 관계, 다항식의 최소공배수 및 최대공약수, 자연수의 분할, 집합의 분할 등
    • '그래프와 행렬' 단원은 고급 수학Ⅰ으로 올라갔으나 제대로 편성해서 가르치는 학교가 극소수이므로 여기서 다룬다.

3. 교과로서의 '이산수학'


3.1. 7차 교육과정 고등학교 과목 이산수학



3.2. 현황 및 잘못된 분류: 이산수학이 '확률과 통계'다?

현 교육과정은 불가피하게 이산수학 관련 내용'''(특히 순열, 조합, 분할, 이항정리 등)'''을 '확률과 통계' 과목으로 몰아놓고 있으나 실제로 그 내용들은 '확률과 통계'와 '''공유'''할 뿐이지 확통만을 위해서만 존재하는 것들이 아니다. 특히 엄연히 순열, 조합, 자연수의 분할, 집합의 분할 관련 내용은 이산수학 영역이다. 차라리 애매성을 피한다면 고1 수학 혹은 수학Ⅰ 같이 영역 명칭이 특칭화되지 않은 과목으로 모조리 몰빵했어야 더욱 적합한 조치였을 것이다.

4. 컴퓨터공학과에서 일컫는 '이산수학'

수학적인 로직을 다루기 때문에 논리회로 설계를 위한 기초 논리학 및 불 대수 관련 풀이나 증명을 먼저 배우고 이외에도 컴퓨터 대수, 자료구조, 알고리즘 등 컴퓨터 학과의 다른 수업에서 나오는 수학적 개념들을 총망라한다. 그러므로 자신이 속한 과가 4년제 컴퓨터 관련 학과라면 반드시 배워야 할 과목이다. 실제로, 대부분의 대학교의 컴퓨터공학과에서 이산수학 과목이 전공필수인 경우가 많지만 전공선택 강의가 있는 다른 대학교도 몇 군데 있다. 다만, 수학과의 이산수학과 컴퓨터공학의 이산수학은 해당 과목에 대한 관점이 다르기에 내용에서 차이가 많이 난다.
학부 컴퓨터과학의 이산수학 과목에서 배우는 이산수학 자체는 그다지 어렵지도 않고, 양도 많지가 않기 때문에 보통 논리학을 포함시켜 배우는 경우가 많다. 또한, 아무래도 해석학이나 다른 전통적인 수학분야들에 비해 최신분야에 속하기때문에 배우는 내용 자체도 아직 그다지 표준화가 되어있지 않아 교수마다 가르치는 내용에 대한 차이가 크게 벌어지기도 한다. 일단, 한학기동안 배우는 것들을 살펴보면
먼저 자연수와 정수의 구성방법이다. 그냥 수학적 귀납법과 Modular arithmetics 정도라 그다지 어렵지 않다. 교수에 따라 type theory 혹은 recursion theory(computability) 를 첨가시켜 가르치는 경우도 있다.
그리고, 조합론. 중고교때로 보면 경우의 수. 원래 조합론은 lattice, counting function, incidence function, generating function, matroids 등을 기본으로 배우지만, 보통 컴공과 학생들에게는 불가능에 가깝기 때문에[7] 고교과정에 가깝게 재미있게 배운다. 대표적인 문제로는 n명이 모자를 한곳에 벗어 뒀다가 다시 썼을 때, 한명도 자신의 모자를 안 쓸 확률 같은거. 쉬워 보이지만, '''고등과정'''이 아니다[8]. 이것들을 쉽게 표현하기 위한것이 생성함수(Generating function, G.F.)인데, 테일러전개처럼 등호의 왼쪽은 닫힌형태(sin), 오른쪽은 차수가 무한이 올라가는 다항식으로 되어 있다. 각 차수의 계수가 어떤 수열의 항이 된다. 해석학에서는 수렴반경[9]이 중요한 반면, 이산수학에서는 다항식의 계수가 중요하기 때문에 수렴반경은 아웃오브안중. 성격이 다른 분야이므로.
다음으로는 그래프 이론. 색칠하기. 꼭지점(vertex)에 색을 칠하고 선분(edge)으로 이어져 있으면 다른 색을 칠하도록 할 때, 주어진 그래프는 몇개의 색으로 칠할 수 있을까, 하는 문제다. 단, 최소한의 색만 칠해야 한다..[10] 최단거리찾기 등. 이부분은 실제 프로그래밍에 응용가능한 알고리즘이 종종 등장하니 알아두면 좋다. 원래 대학에서 배우는 그래프 이론은 확률론이 더해지는데, 확률론은 이산수학과는 관련이 별로 없고(당연하겠지만, 연속체 구조다.), 더이상 구성적(알고리즘적)인 내용이 별로 안나오기 때문에 컴공생 입장에서는 고교레벨의 그래프이론까지만 배운다. 물론, 배우고싶어도 사전에 배워야 하는 확률론이 해석학과 측도론등을 베이스로 하고 있어 컴공생에게는 좀 난해하기때문에 못배운다.
여기까지는 일반적으로 알고있는 이산수학으로, 고교수학과 크게 다른것도 없고 그다지 난해한 부분도 찾아보기 힘들어 교수나 학생이나 죽죽 훑고들 넘어간다. 하지만...
중반부를 넘어갈즈음 끝판왕인 논리와 증명이론이 등장한다. 쉽게 말하면 컴퓨터 과학의 언어에 대해 배우는 부분으로, 명제논리와 일차언어의 문법과 모델이론에서 시작하여 Herbrand-Interpretation, Skolemization, 데이비스-퍼트남 증명방법등을 배우며 운이 좋다면 본격적으로 수학의 논리학과 컴퓨터과학이 연결되는 부분인 proof as a program 으로 유명한 Curry-howard correspondence도 구경할 수 있는 안드로메다로 향하게 된다. 물론, 반학기만에 이것들을 제대로 이해하고 응용문제를 푼다는것은 거의 불가능에 가깝기 때문에 이런것도 있다식으로 관광을 하는 정도지만, 그럼에도 관광을 당하는것에는 변함없다. 여기서 배우는 것들은 컴퓨터 과학의 언어임과 동시에 수학의 언어이기도 하기때문에(말하자면 컴퓨터 과학과 수학은 같은 뿌리를 갖고있다.), 이부분부터는 실제 수학과 수학만큼 난이도가 급상승하게 된다. 물론, 위에서 말한것과 반대의 의미로 운이 좋다면 이 부분을 제끼는 교수를 만나게 될 것이나, 그렇지 않으면 이 부분을 극복하는 것이 이 과목의 핵심이다. 다만 2020년 현재 대한민국의 4년제 대학의 컴퓨터과학과중 이산수학 과목에서 위 내용을 가르치는 학교와 교수는 없다고 단언해도 좋을정도일만큼 이 문서를 읽는 예비 컴공과 위키러들은 너무 걱정하진 말자. 만약 배운다고 해도 나만 못하는게 아니라는 것을 알고있자.

5. 관련 문서


[1] 참고로 '셀 수 없는 것'을 다루는 학문은 후술할 해석학이다.[2] 앞부분 명제 연습문제도 문장 번역이 안되어 있다. 그리고 해설집도 딸려오는 CD로 봐야 한다. 8판 번역본에서는 본문에서 빠진 12장 '부울 대수', 13장 '계산 모델'의 내용이 출판사 홈페이지에서 제공된다. 만약 영어 실력이 되면 그냥 영어 원서를 보는 것이 좋다. 8판 번역본도 마찬가지이다.[3] 다루는 주제만 보더라도 '''논리학''', '''증명 이론''', '''함수''', '''집합론'''은 수학의 핵심 기둥들이다![4] 보통 대수, 확통, 해석(함수), 기하만 언급한다. 그에 비해 이산수학은 언급 자체도 되지 않을 뿐더러 확통으로 편입시키기도 한다. 따로 심화과목화가 된 적이 있는데 이는 구 7차 교육과정 고등학교에서 '''딱 한 번''' 존재했었다. 인기가 턱없이 부족하자 이후 교육과정에서 바로 공중분해 되었으며 그 잔재가 지금은 고급 수학I, 확률과 통계, 심화수학II 등으로 갈기갈기 찢어지거나 대학 과정으로 탈락했다.[5] 양적 관계, 금속의 반응성, 중화 반응에서 케이스 분류가 징그럽게 나온다.[6] 얘도 유전에서 케이스 분류가 징그럽게 나온다.[7] 물론 교수진과 해당 학교가 수학에서 중점을 두는 분야에 따라 다르지만, 저것들은 수학과에서도 일반적으로 학부때는 구경도 못하는 경우가 많다. 수학적인 이산수학을 정식적으로 배우는 수학과나 수학교육과에서나 배운다.[8] 고등과정에서도 단순히 수형도를 그려 경우의 수를 세는 문제로 출제될 때도 있지만, 일반적인 풀이법은 배우지 않는다. 교란수열이라고도 한다.[9] 차수가 무한하니까 절댓값이 어떤 수보다 크면 발산한다. |r|>1이면 1+r+r^2+...가 발산하는 것처럼. [10] 참고로, 4색정리는 그냥 유명한 문제일뿐 매우 난해하기때문에 실제 이산수학에서는 보통 그냥 6가지 색으로 가능하다는 것까지만 배운다. 처음 문제제기 된 이후 100년이 넘도록 매년 한개 이상의 오류가 섞인 증명이 발표되었었고, 십여년전에 드디어 오류가 없는 증명이 등장했다고 여겨지고 있는데 이 증명은 무려 1500 가지 이상의 경우의 수를 포함하고, 이 1500 가지의 경우의 수를 나누기 위한 룰만 600개가 넘는다. 그리하여, 결국 컴퓨터의 도움을 받아 증명을 한 케이스이다.

분류