문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 이산수학 (문단 편집) == [[컴퓨터과학]]에서 다루는 '이산수학' == [include(틀:컴퓨터공학)] [include(틀:이론 컴퓨터 과학)] 수리적인 것들을 다루기 때문에 논리 회로 설계를 위한 기초 논리학 및 불 대수 관련 풀이나 증명을 먼저 배우고 이외에도 컴퓨터 대수, [[자료구조]], [[알고리즘]] 등 컴퓨터 학과의 다른 수업에서 나오는 수학적 개념들을 총망라한다. 그러므로 자신이 속한 과가 4년제 [[컴퓨터과학]] 관련 학과라면 반드시 배워야 할 과목이다. [* [[#s-2.3|2.3 문단]]에서도 알 수 있듯이 대학에 와서 사실상 처음배우게 되는데, 대부분의 [[컴퓨터과학]]전공 학생들이 여기서 맨붕을 겪는다.] 실제로, 대부분의 대학교의 컴퓨터 학과에서 이산수학 과목이 전공 필수인 경우가 많지만 전공 선택 강의가 있는 다른 대학교도 몇 군데 있다. 전체적인 내용에 대해 개괄적으로 설명하면, 먼저 자연수와 정수의 구성 방법이다. 그냥 수학적 귀납법과 Modular arithmetics 정도라 그다지 어렵지 않다. 교수에 따라 type theory 혹은 recursion theory(computability) 를 첨가시켜 가르치는 경우도 있다. 그리고, [[조합론]]. 중고교때로 보면 [[경우의 수]]. 원래 조합론은 lattice, counting function, incidence function, generating function, matroids 등을 기본으로 배우지만 대학에 따라 다르다. 교수진과 해당 학교가 수학에서 중점을 두는 분야에 따라 다르지만, 저것들은 수학과에서도 일반적으로 학부때는 구경도 못하는 경우가 많다. 대표적인 문제로는 n명이 모자를 한 곳에 벗어 뒀다가 다시 썼을 때, 한 명도 자신의 모자를 안 쓸 확률 같은 거. 쉬워 보이지만, '''중등 과정'''이 아니다. [* 중등 과정에서도 단순히 수형도를 그려 경우의 수를 세는 문제로 출제될 때도 있지만, 일반적인 풀이법은 배우지 않는다. 즉, 대학교 이상에서 배우는 과정이란 소리다.] 이것들을 쉽게 표현하기 위한 것이 생성 함수(Generating function, G.F.)인데, 테일러 전개처럼 등호의 왼쪽은 닫힌 형태(sin), 오른쪽은 차수가 무한이 올라가는 다항식으로 되어 있다. 각 차수의 계수가 어떤 수열의 항이 된다. 해석학에서는 수렴 반경 [* 차수가 무한하니까 [[절댓값]]이 어떤 수보다 크면 발산한다. |r|>1이면 1+r+r^2+...가 발산하는 것으로 생각하면 된다.]이 중요한 반면, 이산수학에서는 다항식의 계수가 중요하기 때문에 수렴 반경은 아웃 오브 안중. 성격이 다른 분야다. 다음으로는 [[그래프]] 이론. 색칠하기. 꼭지점(vertex)에 색을 칠하고 선분(edge)으로 이어져 있으면 다른 색을 칠하도록 할 때, 주어진 그래프는 몇 개의 색으로 칠할 수 있을까, 하는 문제다. 단, 최소한의 색만 칠해야 한다. [* 참고로, [[4색정리]]는 그냥 유명한 문제일 뿐 매우 난해하기때문에 실제 이산수학에서는 보통 그냥 6가지 색으로 가능하다는 것까지만 배운다. 처음 문제 제기 된 이후 100년이 넘도록 매년 한 개 이상의 오류가 섞인 증명이 발표되었었고, 십 여년 전에 드디어 오류가 없는 증명이 등장했다고 여겨지고 있는데 이 증명은 무려 1,500가지 이상의 경우의 수를 포함하고, 이 1,500 가지의 경우의 수를 나누기 위한 룰만 600개가 넘는다.] 최단 거리 찾기 등. 이 부분은 실제 프로그래밍에 응용 가능한 알고리즘이 종종 등장하니 알아두면 좋다. 원래 대학에서 배우는 그래프 이론은 확률론이 더해지는데 (당연하겠지만, 연속체 구조다.) 여기까지는 일반적으로 알고 있는 이산수학으로, 그다지 난해한 부분도 찾아보기 힘들어 교수나 학생이나 죽죽 훑고들 넘어간다. 하지만 중반부를 넘어갈 즈음 끝판왕인 논리와 증명 이론이 등장한다. 쉽게 말하면 [[컴퓨터과학]]의 언어에 대해 배우는 부분으로, 명제 논리와 일차 언어의 문법과 모델 이론에서 시작하여 Herbrand-Interpretation, Skolemization, 데이비스-[[퍼트남]] 증명 방법등을 배우며 운이 좋다면 본격적으로 수학의 [[논리학]]과 [[컴퓨터과학]]이 연결되는 부분인 proof as a program으로 유명한 Curry-howard correspondence도 구경할 수 있는 안드로메다로 향하게 된다. 물론, 반 학기만에 이것들을 제대로 이해하고 응용 문제를 푼다는 것은 거의 불가능에 가깝기 때문에 이런 것도 있다식으로 관광을 하는 정도지만, 그럼에도 관광을 당하는 것에는 변함없다. 여기서 배우는 것들은 컴퓨터 과학의 언어임과 동시에 수학의 언어이기도 하기 때문에(말하자면 [[컴퓨터과학]]과 [[수학]]은 같은 뿌리를 갖고 있다.), 이 부분부터는 실제 수학과 수학만큼 난이도가 급상승하게 된다. 물론, 위에서 말한 것과 반대의 의미로 운이 좋다면 이 부분을 제끼는 교수를 만나게 될 것이나, 그렇지 않으면 이 부분을 극복하는 것이 이 과목의 핵심이다. 다만 현재 대한민국에서 컴퓨터과학을 가르치는 대학 중 학부과정의 이산수학 과목에서 위 내용을 가르치는 대학과 교수는 거의 없다고 단언해도 좋을 정도일만큼 수가 적다. 만약 배운다고 해도 나만 못하는 게 아니라는 것을 알고 있자.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기