이산수학

김상목 지음

드림미디어 2024년 03월 11일 출간

작품소개

책소개

이 책은 미적분학 정도의 선행지식을 전재로 하여 개념의 이해에 목적을 두고 집필되었다.
수학전공자에게 이 책은 조합수학의 입문서로 역할을 하는 한편 효과적인 컴퓨터 알고리즘과
계산에 대한 개념을 갖고 타 분야의 주제를 모델링할 수 있는 이산수학의 응용성을 체감할
수 있기 바란다. 한편, 비 수학전공자에게 이 책이 알고리즘 교과목을 위한 기본 수학책으로
활용되기를 바라며, 자신의 전공에 있어서 이산수학적으로 모델링할 수 있는 역량이 배양될
수 있기를 기대한다. 이산수학지식과 논리적 사고역량이 향상되어 알고리즘과 모델링의 근본
원리를 이해함으로서, 자신의 전공에서 보다 창의적이고 개선된 결과를 낼 수 있기를 바란다.
이 책은 5개의 장으로 나뉘어 집필되었으며, 구체적인 장 별 내용과 저자의 의도는 다음과
같다.

1. 이산수학적 추론과 증명의 기본이 되는 논리에 대해 요약하고, 셈법(counting)의 주요 소
이산수학 Discrete Mathematics
재와 방법론을 제공하는 집합론을 개관한다. 이는 포함배제의 원리, 함수의 개수, 수학적
귀납법, 수열의 점화식. 비둘기집의 원리, 그래프 이론의 논리적 기반이 된다.

2. 정보 이론의 근간이 되는 정수의 기본성질과 잉여류 계산법, 오일러 정리에 대하여 다루
고, 이를 바탕으로 대표적 공개키 암호 체계인 RSA의 이론적 배경과 원리를 제시하며 이
산수학적 원리, 구체적 알고리즘에 대하여 다룬다.

3. 이산함수인 수열에 대한 표현법과 잘 알려진 해법들을 소개한다. 다음으로, 수열의 생성
함수에 대한 대수적 의미와 계산법을 다루며 이를 이용한 선형동차수열의 해법을 다룬
다. 비선형 수열의 예로 카탈란수열의 점화식을 소개하고 생성함수를 이용하여 이 수열
의 일반항을 유도한다.

4. 이산수학과 조합수학의 주요 주제인 셈법(Counting)을 다룬다. 셈의 기본 법칙이 되는
덧셈법칙과 곱셈법칙 위에서 순열, 조합, 중복순열, 중복조합 등의 기초 방법론을 소개한
다. 이들로부터 특수한 집합의 셈법과 여러 종류의 함수의 개수의 셈 및 스털링수(Stirling
number), 정수의 분할수, 카탈란수의 동치수 등을 정의하고 각각의 주요 법칙을 다룬다.
특히 각각의 삼각형법칙(세 항 간의 점화식)을 비교 검토한다. 이들에 관한 이론적 전개
는 풍부한 예시를 통하여 이해가 쉽도록 유도하였고, 반면 자세한 증명은 몇 몇 정리로
국한해 제시하고, 나머지는 조합수학으로 미루기로 한다.

5. 대표적인 이산구조인 그래프(Graph)에 관해 기본적인 용어설명으로부터 이론 전반에
걸친 주요 주제를 다룬다. 타 분야 독자의 이해도를 고려하여 증명보다는 다종의 다
이어그램과 표를 동반한 예제들을 다양하게 제공하였고, 전공자를 위하여 제시한 주
요 정리에는 엄밀한 집합론에 입각하여 엄밀하게 기술하였다. 최소거리수형도(Kruskal
Algorithm), 드브르인 그래프(de Bruijn graph) 등의 응용적 주제에 대하여 실생활의 수
요를 모델링하여 지도 위에서 계산하는 과정을 알고리즘에 따라 제시하였다. 앞 장의 셈
법을 그래프 이론에 적용하여 주어진 위수에 대한 해당 그래프(번호있는 그래프, 번호없
는 그래프, 트리그래프, 드브르인그래프)의 개수에 대해 집중적으로 다룬다. 낮은 위수
의 각종 그래프의 개수는 실제로 그래프의 다이어그램을 구현하여 제시하여 이해도를
높였다. 또한 그래프이론의 각 종 난제에 관해서 예시하여 연구의 방향과 기초 방법론을
제시하였다

작가정보

저자(글) 김상목