이산수학

이산수학

이재학․황선욱

목 차

I. 서 론··· 1

Ⅱ. 중등학교 이산수학의 내용··· 3

1. 우리 나라 제7차 교육과정의 이산수학 ··· 3

2. 미국의 이산수학 규준 ··· 4

III. 이산수학의 내용··· 7

IV. 교육과정 개발 방향··· 9

V. 교육과정··· 10

1. 성격과 목표 ··· 10

2. 내용 체계 ··· 12

3. 영역별 내용 ··· 13

4. 보충 자료 ··· 16

이산수학 학습 내용 1. 헤아림의 원리 ··· 19

2. 귀납적 정의 ··· 30

3. 알고리즘 ··· 36

4. 그래프 이론 ··· 41

5. 모델링 ··· 83

I. 서 론

이산수학을 학교 교육에 접목시키려는 많은 노력은 수학에 관심이나 재능이 뛰어난 우수한 학생을 대상으로 기술 산업의 시대, 특히 컴퓨터에 의한 정보화 시대를 준비하게 하려는 측면을 강조하면서 최근에 이루어졌다.

미국에서는 1989년 NCTM의 ‘학교 수학 교육과정과 평가의 규준’에서 추천 하여 1991년에 나온 ‘Discrete Mathematics across the Curriculum, K-12’의 일련의 연구가 있으며, Rutgus 대학에서는 수학에 재능이 있거나 관심이 많은 학생들을 대상으로 한 과외 프로그램 ‘Young Scholar Program in Discrete Mathematics’을 실시하고 있다. 네델란드의 10, 11학년의 교수요목에는 이산수 학의 내용이 상당한 수준까지 제시되어 있으며, 덴마크의 Gymnasium A수준 에서는 프랙탈, 카오스, 선형계획법 등의 주제를 다루고 있다.

우리 나라의 경우에는 이산수학을 중등학교에서 소위 영재를 위한 선택 과 목으로 성격을 지으려는 의견이 있었으나 많은 지지를 얻지 못하였고, 현재는 이산수학이 지나치게 이론적이고 실생활과는 유리된 기존의 입시 위주의 수학 내용에 식상한 많은 학생이나 수학에서 부진한 학생을 위하여 좋은 대안으로 고등학교 심화 선택 과목으로 정해져 있는 실정이다.

지금의 교육 현장에서는 이산수학에 대하여 생소한 수학 교사가 대부분이며 이산수학에 관심을 가지고 공부를 한 교사라 하더라도 이산수학의 여러 분야 전체에 익숙한 사람은 거의 없다고 할 수 있다. 이는 2003년부터 고등학교 현 장에서 학생들이 이산수학을 선택할 때 이를 적절히 지도할 수 있는 수학 교 사가 매우 부족하다는 뜻이다. 그 동안 교사 양성 기관이나 연수 기관에서 이 산수학 또는 그래프 이론 등의 이름으로 교과목 개설이나 강의가 있어 왔으나 통일된 교육과정이 제시되지 않은 상태였으며 따라서 구체적으로 어떤 내용을 다루어야 하며 그 수준 또한 정하기가 어려웠다. 이는 이산수학이라는 과목 자 체가 아직 완전히 정립되지 않았다는 데에도 원인이 있으며 또한 이산수학에 서 다룰 수 있는 영역이 방대하고 각 영역마다 특성이 있어 이를 획일화하여 하나의 교육과정으로 정하는 것에는 많은 논란과 이견이 있을 수밖에 없다는 데에도 있다. 교육인적자원부의 제7차 교육과정에서 고등학교에서의 이산수학

기도 어려우며 실제로 많은 개선의 여지가 있을 것이다. NCTM(1990)의 연구 보고서에서 제안한 고등학교 수준의 이산수학 내용이나 이산수학을 실제로 가 르치고 있는 외국의 고등학교 교육과정과 비교하고, 수학의 타 영역과의 연계 성, 실제 교육 현장의 상황 등을 고려하여 이산수학 교육과정은 더 연구되어 이산수학, 더 나아가서 수학 본래의 교육 목표에 더 접근할 수 있도록 개편되 어야 할 것이다. 따라서, 교사양성기관에서는 이러한 미래를 전망하고 그에 대 처할 수 있도록 이산수학 교육과정을 미래 지향적으로 적절히 정하는 것은 매 우 의미있는 일이다. 또한, 이산수학 교육과정을 개발함에 있어서 NCTM (2000)의 ‘학교 수학의 원칙과 규준’에서 언급한 교육과정의 원칙-교육과정은 단순히 여러 가지 활동이나 내용을 모아 둔 것만이 아니라 일관성있고, 중요한 수학을 강조하며, 종합적인 교육과정을 통해 각 학년에 걸쳐 명료하게 표현되 어야 한다. 수학은 상호 연관성이 매우 높고 누적적인 과목이다. 따라서 위계 별로 개념을 잘 조직하여 제시해야 한다. 수학을 관련성이 무시된 주제별 모음 으로 보지 않고, 중요한 수학적 개념 사이의 관련성을 인식할 수 있도록 해야 한다. 학생들은 이러한 관련성과 기능을 습득하므로 그들의 이해가 더 깊어지 고 확장된다. 교육과정은 또한 중요한 수학 즉, 앞으로 상급학교에서의 학습이 나 가정, 직업 등에서의 문제 해결을 준비하는 수학에 초점을 맞추어야 한다.

-에 충실하도록 한다.

Ⅱ. 중등학교 이산수학의 내용

1. 우리 나라 제7차 교육과정의 이산수학

우리 나라의 제7차 교육과정에서 ‘이산수학’은 10단계 수학의 도달 여부 에 상관없이 이산수학에 관심이 있고 실생활에 필요한 이산수학을 학습하기 를 희망하는 학생들을 대상으로 하는 선택 과목으로서, ‘이론적이고 학문 중 심적인 수학의 성격을 탈피하여 이산수학의 기본적인 개념, 원리, 법칙을 바 탕으로 우리 주위에서 흔히 경험하는 사회 현상 및 자연 현상의 우연성을 이해하고, 여러 가지 자료를 처리하고 분석할 수 있는 능력을 신장하는 데 적합한 과목’으로 규정하고 있다. 교육과정에서 제시한 이산수학의 학습 목 표는 다음과 같다.

‘수학의 기본적인 지식과 기능을 활용하여 실생활의 이산적인 상황의 문 제를 수학적으로 사고하는 능력을 기르고, 합리적으로 의사를 결정하며, 창 의적으로 문제를 해결할 수 있다.

가. 일상적인 정보에서 수량적인 관계나 법칙을 계산기나 컴퓨터를 이용하 여 이해하고, 활용할 수 있다.

나. 세기의 기본이 되는 방법과 집합이나 자연수를 나누는 방법을 이해하고, 이를 이용하여 실생활에서 여러 가지 경우의 수를 구할 수 있다.

다. 사물의 현상을 그래프와 행렬 등을 이용하여 조직, 해석하고, 이를 활용 할 수 있다.

라. 여러 가지 문제를 알고리즘적으로 사고하고 처리하는 능력을 기른다.

마. 다양한 의사 결정 과정과 상충적인 상황에서 합리적이고 논리적인 사고 를 하여 문제를 해결할 수 있다.’

이상의 학습 목표를 달성하기 위하여 제시된 이산수학의 내용체계는 다 음과 같다.

가. 선택과 배열

세기의 방법 : 배열의 존재성, 포함 배제의 원리, 집합의 분할, 수의 분 할, 여러 가지 분배의 수

용어와 기호 : 합의 법칙, 곱의 법칙, 순열, 조합, 비둘기집의 원리, 포함 배제의 원리, 수의 분할, 집합의 분할,

_nP_r, n!, _nC_r 나. 그래프

그래프 : 그래프의 뜻, 여러 가지 그래프 수형도 : 여러 가지 수형도, 생성 수형도 여러 가지 회로 : 오일러 회로, 해밀턴 회로

그래프의 활용 : 행렬의 뜻, 그래프와 행렬, 색칠 문제

용어와 기호 : 그래프, 꼭지점, 변, 꼭지점의 차수, 경로, 회로, 수형도, 생성 수형도, 오일러 회로, 해밀턴 회로, 인접행렬

다. 알고리즘

수와 알고리즘 : 수와 규칙성, 수와 알고리즘

점화 관계 : 두 항 사이의 관계식, 세 항 사이의 관계식

용어와 기호 : 알고리즘, 순서도, 점화 관계, 일반항, 부분합, a_n, S_n 라. 의사 결정과 최적화

의사 결정 과정 : 2 × 2 게임, 선거와 정당성

최적화와 알고리즘 : 계획 세우기, 그래프와 최적화 용어와 기호 : 최적의 경로

2. 미국의 이산수학 규준

가. NCTM의 규준

1989년 미국의 NCTM에서 제안한 수학교육과정에서 9-12 학년을 위한 이산수학의 성격은 다음과 같다.

“21세기로 가는 시점에서 정보와 정보의 교환은 최소한 물건의 생산만 큼 중요한 것이 되었다. 물리적 또는 물질 세계는 미적분과 대수, 기하, 삼각함수의 필수 아이디어인 연속 수학에 의해 흔히 모델화 되는 반면,

정보 처리라는 비물질 세계는 이산적인 수학의 사용을 요구한다. 컴퓨터 공학 역시 수학이 사용되고 창조되는 방법에 점차 강하게 영향을 미치 고 있다. 컴퓨터는 본질적으로 유한이고 이산적인 기계이다. 따라서 이 산수학으로부터의 내용은 컴퓨터를 사용하는 문제해결에 필수적이다. 이 런 점에서 모든 학생들로 하여금 이산수학의 개념과 방법을 경험하게 하는 것은 중요하다. 비록 이산수학이 상대적으로 새로운 분야이지만, 여기에서는 그것을 유한개의 원소를 갖는 집합과 체계로 단순화하여 제 한하여 생각한다.”

위와 관련하여 학생들이 도달하여야 할 목표로서 다음을 제시하고 있다.

1) 유한그래프, 행렬, 점화식 관계와 같은 이산 구조를 사용하여 문제 상황을 표현할 수 있어야 한다.

2) 행렬을 사용하여 유한 그래프를 표현하고 분석할 수 있어야 한다.

3) 알고리즘을 개발하고 분석할 수 있어야 한다.

4) 세기와 이산 확률 문제를 풀 수 있어야 한다.

대학 진학 학생들은 이에 더하여 다음을 더 요구하고 있다.

5) 선형계획법과 차분방정식을 이용하여 문제를 표현하고 해결할 수 있 어야 한다.

6) 알고리즘의 응용 및 컴퓨터 타당화와 관련된 문제 상황을 탐구할 수 있어야 한다.

나. COMAP의 제안

최근 미국에서 연구, 발표된 COMAP(Consortium for Mathematics and its Applications)에서 제안하는 이산수학의 내용은 다음과 같다.

1) 그래프이론(4-5주)

최소생성수형도(Prim의 알고리즘, Kruskal의 알고리즘)

그래프의 구조(기본 개념, 다이어그램이나 인접행렬 등으로 표현하기) 회로와 경로(오일러 회로 알고리즘, 해밀턴 회로, 경로, 순회판매원 문

제, 최단경로문제에 대한 Dijkstra의 알고리즘)

Network 색칠 문제 수형도의 구조

2) 헤아림의 기술(4-5주)

논리, 집합, 벤 다이어그램(disjuction and union, conjuction and intersection, negation and complement, 포함배제의 원리) 합의 법칙, 곱의 법칙

순열과 조합

파스칼 삼각형과 이항계수

이산확률과 그 응용(mutually exclusive events and addition rule, 독립 사건과 곱의 법칙, 조건부 확률, 이산 상황에서의 기대값) 3) 수학적 귀납법과 반복(차분방정식)(4-5주)

일계 반복 관계(Iterating first-order recursion relations)

반복의 응용(등차수열, 등비수열, 지수적 성장, 재정수학, population dynamics)

일계 선형 점화식에서 일반항 구하기 이계 반복 차분방정식(피보나찌 수열) 4) 행렬의 모델(1-2주)

마코프 연쇄

인구 분포에 대한 Leslie 모델 Leontief input-output 모델

Ⅲ. 이산수학의 내용

이산수학은 수학의 다른 분야와 비교하여 상대적으로 새로운 분야이며 그 내용이 타 영역과 중복되기도 하고, 많은 사람이 인정하는 표준화된 내용도 정 해졌다고 볼 수 없는 실정이다. 컴퓨터와 관련된 이산수학의 내용-알고리즘의 복잡도, 유한상태 기계, 부울 대수-이나 부호이론, 암호학, 선형계획법 등의 응 용수학도 이산수학의 범주에 포함될 수 있으며, 집합론의 명제, 관계, 함수 등 의 내용도 대부분의 이산수학 책에서 다루어지고 있다. 현재, 이산수학이란 이 름으로 출판된 국내외의 책에서 많이 다루는 이산수학의 주제를 살펴보면 다 음과 같다.

가. a 출판사(국내)

집합 및 함수 : 집합, 관계, 함수, 함수의 성장

기초 : 알고리즘, 알고리즘의 복잡성, 수치함수의 연산, 수학적 귀납법, 순열과 조합, 비둘기집의 원리, 램지의 성질

점화관계 그래프 이론

언어와 유한상태 기계 나. b 출판사(국내)

수학적 모델, 알고리즘 언어

명제와 논리, 집합의 정의, 연산, 성질, 종류 수학적 귀납법, 관계와 함수

그래프 이론 형식언어와 기계 부울 대수 대수체계

수치함수와 생성함수, 계차방정식, 알고리즘의 분석 다. c 출판사(국외)

알고리즘 언어

조합

그래프 이론

부울 대수, 대수 구조

기계와 계산-오토마타, 유한상태 기계, 튜링 머신 확률

라. d 출판사(국외) 선거이론 분배이론 게임이론 그래프이론 Markov Chain 마. e 출판사(국외)

수와 세기 : 정수, 함수와 세기, 세기의 원칙(오일러 함수, 치환), 디자인, 분할, 모듈러 계산

그래프와 알고리즘 : 알고리즘과 복잡도, 그래프, network, 점화식

대수적 방법 : 군, 환, 체, 다항식환, 유한체와 그 응용, 오류정정 부호, 생성함수,

자연수의 분할, 대칭성과 세기(Polya's theorem)

Ⅳ. 교육과정 개발 방향

학생들이 장래에 다양한 전공이나 직업을 택할 수 있도록 중등학교의 수학 프로그램은 그 영역을 보다 넓히고 깊게 하는 것이 바람직하다. 또한, 학생들 의 능력, 적성, 포부를 고려하여 많은 나라에서는 다양한 교육 과정을 제시하 고 있으며 우리 나라 제7차 수학교육과정도 이를 수용하여 여러 가지의 선택 과목을 제시하고 있다. 고등학교의 이산수학도 이와 관련하여 교육 과정의 내 용이 앞으로는 더욱 다양해지고 깊어질 것이 예상된다. 이에 대비하여 교사 양 성 기관에서의 교육과정은 미래를 대비하여 준비하는 것이 되어야 한다. 따라 서, 이산수학도 현재의 고등학교 이산수학의 영역에서 더 확장하고 보다 전문 화된 내용으로 교육과정을 구성하여야 한다. 또한, 이산수학을 통하여 수학의 본질을 이해하고 수학을 즐길 수 있으며 이 과정에서 실생활에서의 수학의 활 용성과 유용성을 느끼게 하는 교육과정이 되어야 할 것이다. 한편, 이산수학의 기초 개념인 집합이나 논리를 비롯하여 대수학에서 다루어질 수 있는 부울 대 수, 부호이론, 암호학과 수치해석학에서 다루어지는 계차방정식이나 방정식의 수치적 해법 등은 각각의 영역에서 다루어지는 것이 더욱 타당할 것이다. 이와 같은 맥락에서 교사 양성 기관에서의 이산수학 교육과정의 주제를 선별하는 데 다음과 같은 원칙을 설정하는 것은 적절할 것이다.

가. 수학의 기본적인 지식과 기능을 활용하여 실생활의 이산적인 상황의 문제 를 수학적으로 사고하는 능력을 기르고 합리적으로 의사를 결정하며, 창의 적으로 해결할 수 있는 주제를 선별한다.

나. 초, 중등학교 교육과정, 특히 고등학교 이산수학의 교육과정과 연계된 주제 를 선별한다.

다. 수학의 타 영역과의 연계성을 고려하여 일반적으로 수학교육과의 필수 과 목의 한 주제로 다루어질 수 있는 것은 제외한다.

라. 미래의 중등학교 교육과정에 대비하여 미래 지향적인 폭넓은 주제와 깊이 를 고려한다.

Ⅴ. 교육과정

1. 성격과 목표

수학에서 나온 여러 가지 개념과 계산 방법은 일상생활이나 타 학문의 연구에 매우 유용하게 쓰인다. 특히, 수학의 기본 개념에서 출발한 이산수학 은 실생활의 문제를 모델링하고 그 문제를 해결하는 데 일반적인 방법론으 로서의 역할을 하고 있다. 실제로 ‘이산수학’이 무엇인가라고 정확히 정의하 기는 쉽지 않다. ‘이산(discrete)'의 뜻은 따로 따로 떨어진 것을 의미하며 이산수학은 연속수학이라는 수학과 대비되는 말이다. 여기서 연속이란 말은 틈이 없으며 갑작스런 변화가 없다는 뜻이다. 우리에게 익숙한 미분, 적분은 연속수학의 대표적 예이다. 이산수학이나 연속수학에서 사용하는 주제나 기 술은 대부분 같다. 예컨대, 집합이나 그 원소와 거기에 정의된 구조에 관한 성질을 연구하는 것은 동일하다. 또, 문제 해결을 위한 일반적인 방법론(아 래 그림)도 마찬가지이다.

문제 문제의 해

⇓ ⇑ 추상적 모델 ⇒ 변환된 모델

그러나 연속수학은 실수의 집합이나 그와 비슷한 집합(구간이나 평면에 서의 한 영역)이 주된 기본공간이며 따라서 이들 공간은 기하학적으로 볼 때 연속적인 표현을 갖는다. 반면에, 이산수학은 기하학적으로 볼 때 그 원 소가 서로 떨어져 있는 집합을 기본공간으로 한다. 즉, 이산수학에서는 유한 집합이나 가산집합에 관한 성질을, 연속수학에서는 불가산집합에 관한 성질 을 연구한다.

본 교육과정의 목표는, 이산수학의 기본적인 개념, 원리, 법칙을 활용하여 실생활에서 일어나는 유한이나 불연속 상황의 문제를 수학적으로 분류하고

논리적으로 사고하여 합리적으로 문제를 해결하는 능력과 태도를 기르는 것 이며, 이 목표를 달성하기 위하여 이산수학의 학습 내용을 세기의 원리와 점화식, 알고리즘, 그래프, 의사결정 과정의 5개 영역으로 하며, 각 영역에서 의 내용 전개에는 이산적인 상황의 문제를 모델링한 다양한 소재를 사용하 도록 한다. 한편, 이산수학은 고등학교 수학 I의 내용 중에서 순열, 조합, 확 률 및 통계 영역을 충분히 이해하고, 대학에서 집합론을 이수한 모든 학생 을 대상으로 개설할 수 있는 필수 과목으로 본 강좌에 필요한 선수학습 내 용은 다음과 같다.

선수학습 내용 :

집합론 :

집합의 기본 성질 집합의 정의 집합의 연산 멱집합 곱집합 집합의 분할 관계 :

이항관계 관계의 성질 동치관계와 분할 함수 :

단사함수, 전사함수 함수와 기수

역함수 이항연산 순열과 조합, 확률 :

경우의 수 : 합의 법칙, 곱의 법칙 순열

조합 이항계수 확률 기대값

2. 내용 체계

1. 헤아림의 원리

1-1. 포함배제의 원리 1-2. 교란

1-3. 비둘기집의 원리 1-4. 집합의 분할 1-5. 수의 분할

2. 귀납적 정의 2-1. 점화식 2-2. 특성다항식 2-3. 생성함수

3. 알고리즘

3-1. 기본적 알고리즘 3-2. 알고리즘의 분석 3-3. 탐색알고리즘 3-4. 분류알고리즘

4. 그래프 이론

4-1. 그래프의 정의 4-2. 여러 가지 그래프 4-3. 유향그래프 4-4. 오일러 그래프 4-5. 해밀턴 그래프

4-6. 경로 알고리즘 4-7. 수형도

4-8. 평면그래프 4-9. 그래프의 색칠

5. 모델링

5-1. 게임이론 5-2. 마코프 연쇄 5-3. Leslie 모델

5-4. Leontief input-output 모델

3. 영역별 내용

1. 헤아림의 원리

이 영역에서 포함배제의 원리, 비둘기집의 원리 및 집합과 수의 분할 에 대하여 알아본다. 포함배제의 원리는 기본 원리의 이해와 구체적인 상 황에서 이들 원리를 적절히 적용할 수 있도록 하는 것이 중요하다. 집합 과 수의 분할에서는 조직적으로 나열할 수 있는 능력과 이로부터 유추할 수 있는 규칙성을 찾아내도록 한다.

가. 포함배제의 원리를 이해하고 구체적인 사례에서 이 원리를 적용하여 개수를 계산할 수 있게 한다.

나. 교란(Derangement) 의 뜻을 알고 그 값을 구하는 방법을 이해한다.

다. 비둘기집의 원리를 이해하고, 이 성질을 이용하여 해결할 수 있는 구체적 상황 을 알아본다. 또, 여러 가지 경우에 이 원리를 적용할 수 있게 한다.

라. 집합의 분할을 이해하고 스터링의 수를 알고 이를 이용할 수 있게 한다.

마. 수의 분할에서는 주어진 자연수를 몇 개의 합으로 나타낼 수 있는 방법의 수를 구할 수 있게 하고 이를 응용할 수 있도록 한다.

용어와 기호 : 포함배제의 원리, 교란, 비둘기집의 원리, 램지의 성질, 집 합의 분할, 스터링의 수, 수의 분할, _Dn, _{S( n,k)}, _{P( n,k)}

2. 귀납적 정의

반복적 상황을 점화식으로 나타내고, 점화식으로부터 수열의 일반항 을 구할 수 있게 한다. 또, 이를 응용하여 수와 관련된 여러 가지 규칙 성의 문제를 해결할 수 있도록 한다.

가. 점화식의 뜻을 이해하게 한다.

나. 두 항, 세 항 사이의 관계식으로부터 특성다항식이나 생성함수를 이 용하여 일반항을 구할 수 있게 한다.

용어와 기호 : 점화식, 특성다항식, 특성해, 일반해, 생성함수

3. 알고리즘

문제 해결의 일반적인 과정에서 한 단계에서 다음 단계로 변화하는 과정을 알고리즘의 사고로 살펴보고 특정한 문제의 해결 과정에서 일반 화의 가능성을 추정하고 그 추정을 확인하는 절차는 문제 해결 전략에 서 중요하다. 실세계에 기반을 둔 수열의 문제나 점화 관계도 알고리즘 으로 접근함으로써 수학적 탐구활동이 풍부해 질 수 있다. 알고리즘의 개발과 분석은 컴퓨터를 이용하여 문제 해결하는 방법의 핵심이 된다.

알고리즘의 관점에서 수학을 탐구하는 기회를 경험하고 컴퓨터 등 기술 공학적 도구를 수학 활동에 이용하고 나아가 수학적 소프트웨어를 개발 할 수 있는 능력은 현대인이 갖추어야할 기본 소양이다.

가. 알고리즘의 뜻을 이해하고, 간단한 문제 해결을 위한 알고리즘을 간 단 명료하게 작성할 수 있다.

나. 알고리즘의 분석을 위해 알고리즘의 복잡도를 이해하고 복잡도에 관 한 기본 성질을 이해한다.

다. 탐색 알고리즘과 분류알고리즘을 이해한다.

용어와 기호 : 알고리즘, 복잡도, 탐색알고리즘, 분류알고리즘, f = O( g), f⋏g, f ≍g

4. 그래프

그래프는 그 응용 범위가 매우 넓어 수학뿐만이 아니라 자연과학, 사 회과학 등 거의 전 학문 분야에서 쓰이고 있다. 특히, 컴퓨터 과학과 관 련된 분야나 도시 계획, 교통 문제 등 현대에 이르러 그 쓰임새가 더욱 광범위해지고 있다. 이 영역에서는 실생활의 문제를 주요 소재로 하여 그래프 이론을 전개하고 이들 이론을 바탕으로 문제 해결 능력을 기른 다.

가. 그래프의 뜻을 알고 여러 가지 용어의 뜻을 안다.

나. 그래프로 모델링될 수 있는 여러 가지 실제 문제 상황의 예를 안다.

다. 여러 가지 종류의 그래프를 알고, 유향그래프의 뜻을 안다.

라. 그래프를 행렬을 이용하여 나타낼 수 있고, 그래프의 여러 가지 성 질을 이해한다.

마. 오일러 그래프와 해밀턴 그래프를 이해하고 이를 응용할 수 있다.

바. 최단경로 문제와 스케쥴링의 문제를 그래프를 이용하여 해결할 수 있다.

사. 수형도와 생성수형도를 이해하고 이를 이용하여 배낭꾸리기 문제를 해결할 수 있다.

아. 평면그래프를 이해하고 오일러 공식, 그래프의 평면성 판단, 평면그 래프의 쌍대그래프를 이해한다.

자. 그래프의 색칠 문제를 이해하고 이를 이용하여 여러 가지 문제를 해 결할 수 있다. 또, 지도의 색칠 문제도 이해한다.

용어와 기호 : 그래프, 꼭지점, 변, 면, 유향그래프, 단순그래프, 완전그래 프, 이분그래프, 오일러 회로, 해밀턴 회로, 꼭지점(변, 면) 의 차수, 경로, 수형도, 생성 수형도, 평면그래프, 오일러 공식, 쌍대그래프, 꼭지점(변)의 색칠, 채색다항식, 지도, 사색정리, deg (v)

5. 모델링

주어진 상황을 수학적으로 모델링하고, 그 모델에서 우리가 알고자하 는 여러 가지 사실을 파악하여 문제 해결을 할 때 수학이 어떻게 적용

되는지 이해함으로써 수학의 가치를 인식하고 수학의 흥미를 유발하도 록 한다. 게임이론에서는 기하학적인 풀이가 가능한 _{2 × 2} 게임만을 다 루도록 한다.

가. 여러 가지 게임의 뜻을 이해한다.

나. 혼합전략의 게임에서 최적전략을 구할 수 있다.

다. 마코프 체인(Markov Chain)을 이해한다.

다. 경제 시스템에서 Leontief input-output 모델을 이해한다.

용어와 기호 : 게임, 영합게임, 비영합게임, 결정적 게임, 순수 전략, 혼 합 전략, 게임의 값, Markov Chain, transition matrix, Leontief input-output 모델

4. 보충 자료

1. 교육부, 수학과 교육과정, 교육부 고시 1997-15호, 제7차 수학과 교육과 정, 대한교과서, 1997.

2. 교육부, 고등학교 교육과정 해설 5, 수학, 대한교과서, 2001.

3. 교육인적자원부, 고등학교 확률과 통계, 한국교원대학교 1종도서 확률과 통계 편찬위원회, 천재교육, 2003.

4. 교육인적자원부, 고등학교 이산수학, 강원대학교 1종도서 편찬위원회, 천 재교육, 2003.

5. NCTM, Curriculum and Evaluation Standards for School Mathematics, 1989.

6. NCTM, Principles and Standards for School Mathematics, 2000.

7. Goodaire, E. G., Parmenter, M. M, Discrete Mathematics with Graph Theory, Prentice-Hall, 1998.

8. Dossey, Giordano, McCrone, Weir, COMAP, Mathematics Methods and Modeling for Today's Mathematics Classroom, A Contemporary Approach to Teaching Grades 7-12, Brooks/Cole, 2002.

9. Wilson, R. J., Watkins, J. J., Graphs An Introductory Approach, John

Wiley & Sons, 1990.

10. West, D. B, Introduction to Graph Theory, Prentice-Hall, 1996.

11. Hu, T. C., Combinatorial Algorithms, Addison-Wesley, 1982.

12. 김세헌, 현대 경영과학-계량의사결정론, 무역경영사, 1999.

13. 이효구, 박승안, 신정판 경제⋅경영수학, 박영사, 1997.

14. 이재학, 교사양성대학에서의 이산수학 교육과정, 한국수학교육학회지 시리즈 E, 수학교육, 2002.

15. 이준열, 이산수학 제7차 교육과정의 구현 방안 연구, 한국수학교육학회 지 시리즈 A, 수학교육, 2002.

16. 박진홍, 새로운 이산수학, 교우사, 1996.

17. 유원희, 이산수학, 경문사, 1992.

이산수학 학습 내용

1. 헤아림의 원리

물건의 개수를 헤아리는 것에서부터 어떤 사건이 일어날 수 있는 경우의 수 를 세는 것은 초등학교 혹은 그 이전의 유치원 교육에서 시작하여 지금까지의 교육에서 뿐만이 아니라 일상 생활에서 항상 일어나는 일일 것이다. 여기에서 는 우리가 그동안 알게 모르게 그 원리를 이용하였던 헤아림(counting)의 기본 원리를 다시 한번 조명해 보고, 이를 수학적으로 표현하고 더 나아가 일반화의 과정을 거쳐 보다 고급의 셈의 기술로 발전시켜 보도록 한다. 단, 여기에는 순 열과 조합이 기본적인 도구로 쓰이나 이와 관련된 내용은 선수학습으로 이미 이루어져 있다고 생각한다.

1-1. 포함 배제의 원리

이산수학을 수강하는 100명의 학생 중에 3/4은 여학생이며 80%는 자기 컴퓨터를 가지고 있다고 한다.

질문 1. 자기 컴퓨터를 가지지 않은 남학생은 몇 명인가? 공식을 구해 보 자. 이 수는 최대 몇 명이며 최소 몇 명인가?

질문 2. 자기 컴퓨터를 가지고 있는 여학생은 몇 명이라고 생각할 수 있는 가?

성질 1. 유한집합 U의 부분집합 A,B 에 대하여 다음이 성립한다.

1) |A∪B | = |A | + |B | - |A∩B | 2) |A∩B| ≤ min {|A |,|B |}

3) |A⋱B | = |A | - |A∩B | ≥ |A | - |B | 4) |A^c| = |U | - |A |

5) |A△B | = |A∪B | - |A∩B | = |A | + |B | - 2|A∩B | = |A⋱B | + |B⋱A | 6) |A×B | = |A |×|B |

문제 1. 세 유한집합 A, B, C의 합집합의 원소의 개수에 대한 공식을 만 들고 증명하여라.

성질 2 (포함 배제의 원리). 유한개의 유한 집합 A₁, A_2, …, A_n 에 대하 여 합집합 A₁∪A₂…∪A_n의 원소의 수는 다음과 같다.

|A₁∪ A₂… ∪ A_n| = ∑

i |A_i| -∑

i ＜ j|A_i∩ A_j| + ∑

i ＜ j ＜ k| A_i∩ A_j∩ A_k| - … + ( - 1)^{n + 1}|A₁∩ A₂∩ … ∩ A_n|

문제 2. 어느 대학 수학과에 30대의 PC가 있으며 이 중 20대는 Window 98 을 운영하고 있으며, 8대는 액정 모니터, 25대는 외장 CD-ROM 드라이버가 장착되었다. 또, 20대는 이들 사양 중 적어도 2개 이상을 가지고 있으며, 6 대는 이들 사양 모두가 장착되었다고 한다.

1) 이들 사양 중 적어도 한 가지 이상이 장착된 PC는 몇 대인가?

2) 이들 사양이 하나도 없는 것은 몇 대인가?

3) 오직 한 가지 사양만 가지고 있는 PC는 몇 대인가?

문제 3. 1에서 300까지의 정수 중에서 다음 조건을 만족하는 정수의 개수를 구하여라.

1) 3, 5, 7 중 적어도 하나로 나누어지는 수

2) 3과 5로는 나누어지지만 7로는 나누어지지 않는 수 3) 5로는 나누어지나 3과 7로는 나누어지지 않는 수

1-2. 교란(Derangements)

4집에 각각 한 통의 편지를, 글자를 모르는 배달부가 한 집에 한 통씩 아 무렇게나 배달한다고 할 때, 4집 모두 자신에게 오는 편지를 받지 못하는 경우의 수는 몇 가지나 될까? 하인이 파티에 참석한 각 사람의 코트를 보관 했다가 임의로 돌려줄 때, 모든 사람이 다 자신의 코트를 돌려 받지 못할 확률은 어떻게 될까?

순서가 정해진 n개의 서로 다른 기호(symbol)를 각 기호가 모두 원래의 위치에 있지 않도록 배열하는 것을 n개의 교란(derangement)라고 부르고

n개 기호의 교란의 총 수를 D_n으로 나타낸다.

예. 두 기호 1, 2의 교란은 21 하나 뿐이다. 따라서, D₂= 1이다.

1, 2, 3의 교란은 312, 231 두 개다. 즉, D₃= 2이다.

1, 2, 3, 4의 교란은 다음의 9개가 있다.

2341 2413 2143 3142 3412 3421 4123 4312 4321 따라서, D₄= 9.

D_n을 구하는 일반적 방법을 생각해 보기 위해 먼저, D₄를 구해 보자.

1, 2, 3, 4의 치환 중 첫째 자리에 1이 위치하는 치환의 집합을 A₁, 둘째 자리에 2가 위치하는 치환의 집합을 A₂라 하고 A₃, A₄를 같은 방법으로 정하자. 이때, 적어도 한 숫자가 자신의 순서에 위치하는 치환의 집합은

A₁∪ A₂∪ A₃∪ A₄

이다. 1, 2, 3, 4의 치환 전체의 개수는 4≠24이고 교란은 위 집합의 여집합 이므로

D₄= 4! - | A₁∪ A₂∪ A₃∪ A₄| 그런데,

| A₁∪ A₂∪ A₃∪ A₄| = ∑

i |A_i| -∑

i ＜ j|A_i∩ A_j| + ∑

i ＜ j ＜ k|A_i∩ A_j∩A_k| - | A₁∩ A₂∩ A₃∩ A₄|

여기서, |A₁| = 3!, |A₁∩ A₂| = 2!, |A₁∩ A₂∩A₃| = 1!이므로

| A₁∪ A₂∪ A₃∪ A₄| = 4( 3!) - 4C 2( 2!) + 4C 3( 1!) - 1 따라서,

= 4!- 4! + 4!

2! - 4!

3! + 4!

4!

= 4!

(

3! + 1 4!

)

= 9

이상을 일반화하면 다음 공식을 얻을 수 있다.

모든 자연수 n에 대하여,

D_n = n!

(

)

≈ n!

e

1-3. 비둘기집의 원리

비둘기집의 원리는 우리가 이미 알게 모르게 많이 사용한 논리로서 그 원리는 매우 간단하다. 즉, 비둘기 집은 n개 밖에 없는데 비둘기는 n마리 보다 더 많이 있다면, 비둘기 집 가운데 어느 하나는 반드시 2마리 이상의 비둘기가 사용해야 한다는 것이다. 이것은, 정의역과 공역이 각각 유한집합 인 함수에 관한 간단한 성질 즉, A, B가 모두 유한집합이고 |A | ＞ |B |이면, A에서 B로의 어떤 함수도 1-1이 될 수는 없다는 것으로 표현되어지기도 한다.

이제, B를 비둘기 집의 집합이라 하고 A를 비둘기의 집합이라 하고, f 를 각각의 비둘기에 비둘기집을 배정하는 함수로 생각해 보자. 함수 f 가 1-1이 아니라는 것은 적어도 두 마리의 비둘기가 같은 집에 배정된다는 것 을 뜻하는 것이다.

일반적으로 비둘기집의 원리는 다음과 같이 서술된다.

비둘기 집의 원리 1.

n ＞ m일 때, _n개의 물건을 _m개의 상자에 넣으려면 어떤 방법으로 넣더라 도 적어도 어느 한 상자에는 두 개 이상의 물건을 넣어야 한다.

이 원리를 쓰면, 다음을 쉽게 설명할 수 있다.

1) 367명 중에는 생일이 같은 사람이 반드시 있다.

2) _{n + 1}개의 정수 중에는 두 수의 차가 _n으로 나누어지는 수가 적어도 한 쌍 있다.

문제 4. 한 변의 길이가 2인 정사각형의 내부에서 5개의 점을 어떻게 선택 하더라도 두 점 사이의 거리가 기껏해야 2인 한 쌍의 점이 반드시 존재함 을 설명하여라.

문제 5. 임의의 자연수 10개를 택하여 제1항부터 10항까지의 수열을 만들면 어떤 방법으로 만들더라도 몇 개의 연속된 항의 합이 10의 배수가 되는 것 이 반드시 존재함을 증명하여라. 단, 한 개의 항도 연속된 것이라고 본다.

비둘기 집의 원리는 다음과 같이 확장될 수 있다. 즉, 2n + 1마리의 비둘 기가 n개의 집에 들어가면 적어도 어느 한 집에는 3마리 이상의 비둘기가 들어가야 한다. 이를 일반화하면 다음과 같이 말할 수 있다.

비둘기 집의 원리 2.

n ＞ m일 때, n개의 물건을 m 개의 상자에 넣으려면 어떤 방법으로 넣더라 도 적어도 어느 한 상자에는

⌈

⌉

예 1. 44개의 의자를 5개의 테이블에 배치하려면 적어도 한 테이블에는

⌈

⌉

비둘기 집의 원리의 응용으로 다음 램지의 성질이 있다.

정의. 어떤 자연수 _r이 _{( p,q)}-Ramsey 성질을 갖는다는 것은, _r명의 임의 의 모임 중에서 서로 친구인 _p명의 모임이 있든가, 아니면 서로 알지 못하 는 _q명의 모임이 있는 경우를 뜻한다.

예. 6명의 모임에서는 서로가 친구인 3명이 있든지 서로가 모르는 3명이 있 든지 둘 중 하나가 반드시 성립한다. 따라서 6은 (3, 3)-Ramsey 성질을 갖 는다.

이유) 6명 중 한 명을 갑이라 하고, _A를 갑과 친구인 사람의 집합, _B를 갑과는 모르는 사람의 집합이라 하면, #( A) + #( B) = 5이다. 비둘기 집의 원 리에 의해 두 집합 중에는 3명 이상이 들어가는 것이 있다. #( A)가 3 이상 즉, A = {b,c,d,… }라 하자. 이들 중 한 쌍 예컨대 b, c가 서로 친구이면, 갑, b, c는 서로 친구이고 서로 친구인 쌍이 하나도 없으면 서로 모르는 사람이 3명 이상 반드시 있게 된다. #( B)가 3이상일 경우도 같은 방법으 로 설명할 수 있다.

문제 6. 10은 (4, 3)-Ramsey 성질을 가짐을 증명하여라.

1-4. 집합의 분할 (Partition)

집합론에서 집합의 분할에 관하여 이미 알아보았다. 여기에서는 집합을 분할하는 방법의 수에 대하여 알아보기로 한다.

집합 _A의 분할이란 공집합이 아닌 _A의 부분집합들의 모임 _{{Ai|i ∈I }} 으로 다음 두 성질을 만족해야 한다.

(1) 부분집합 A_i 전체의 합집합은 A이다.

(2) 각각의 부분집합은 서로 소(disjoint)이다.

이때, 부분집합 A_i 를 분할의 부분(part)라고 한다.

예. 집합 A = {1,2,3,4 }의 분할 방법 1개의 부분으로 분할 : {1,2,3,4 }

2개의 부분으로 분할 : { {1,2,3 },4 }, { {1,2,4 },3 }, { {1,3,4 },2 }, { {2,3,4 },1 } { {1,2 }, {3,4 } }, { {1,3 }, {2,4 } }, { {1,4 }, {2,3 } }

3개의 부분으로 분할 : { {1,2 }, {3 }, {4 } }, { {1,3 }, {2 }, {4 } }, { {1,4 }, {2 }, {3 } }, { {2,3 }, {1 }, {4 } }, { {2,4 }, {1 }, {3 } }, { {3,4 }, {1 }, {2 } }

4개의 부분으로 분할 : { {1 }, {2 }, {3 }, {4 } }

n개의 원소를 갖는 집합을 k개의 부분으로 분할하는 방법의 수를 S( n,k)로 표시한다. 이를 이계 스털링 수(Stirling numbers of the second kind)라 한다. 위의 예에서 S( 4,1)＝1, S( 4,2)＝7, S( 4,3)＝6, S( 4,4)＝1임을 알 수 있다.

정리. S( n,k) = S( n - 1,k - 1) + k S( n - 1,k).

증명) n명의 사람 1, 2, 3, …, n을 k개의 그룹으로 나누는 방법

ⅰ) n이 혼자서 1개의 그룹을 이루는 경우

이 경우는 1, 2, 3, …, n - 1을 k - 1개의 그룹 X₁, X₂,…, X_{k - 1}로 분할함으로써 k개의 그룹 X₁, X₂,…, X_{k - 1},{ n}을 얻을 수 있다. 이 경우의 분할의 수는 S( n - 1,k - 1)이다.

ⅱ) _n이 다른 사람과 함께 1개의 그룹을 이루는 경우

이 경우는 1, 2, 3, …, _{n - 1}을 _k개의 그룹 _{X1, X2,…, Xk}로 분할하 고, 그 분할 방법의 수는 S( n - 1,k), n을 X₁, X₂,…, X_k 중 어느 하 나의 그룹에 포함시키면 된다.(포함시키는 방법의 수는 k) 따라서 이 경우의 분할 수는 kS( n - 1,k)이다.

그러므로 ⅰ), ⅱ)에 의해 S( n,k)〓S( n - 1,k - 1)＋kS( n - 1, k).

예. S( 4,3)의 값을 구하는 과정을 위의 공식과 관련하여 알아보자.

(1) S( 3,2) = 3으로 { {1,2 }, {3 } }, { {1,3 }, {2 } }, { {2,3 }, {1 } }이 있다. 이로부터 {4 }를 추가하여 다음 3개를 구성할 수 있다.

{ {1,2 }, {3 }, {4 } }, { {1,3 }, {2 }, {4 } }, { {2,3 }, {1 }, {4 } }

(2) S( 3,3) = 1으로 { {1 }, {2 }, {3 } }이 있다. 이로부터 다음 3개를 찾을 수 있 다.

{ {1,4 }, {2 }, {3 } }, { {1 }, {2,4 }, {3 } }, { {1 }, {2 }, {3,4 } } 그러므로, S( 4,3) = S( 3,2)＋3S( 3,3)임을 알 수 있다.

참고. 스털링 수의 삼각형 n = 1

n = 2 n = 3 n = 4 n = 5 n = 6

1 1 1 1 3 1 1 7 6 1 1 15 25 10 1 1 31 90 65 15 1

토의. 스터링 계수에 대한 다음 성질을 포함한 여러 가지 성질을 찾아보고 증명해 보자.

① _{S( n,n)＝1}, _{S( n,1)＝1} ② S( n,n - 1)＝C ( n, 2)

③ S( n,2)＝ 2ⁿ-2 2

1-5. 수의 분할

자연수 _n, _k에 대하여 _n개의 똑같은 바둑돌을 _k개의 그룹으로 나누는 방법의 수를 _n의 _k-분할 수라하고, _{P( n,k)}로 나타낸다.

예. 1) 7을 3개의 자연수의 합으로 나타내는 방법은 다음의 4가지이다.

7 ＝ 1＋1＋5

＝ 1＋2＋4

＝ 1＋3＋3

＝ 2＋2＋3 따라서, P( 7,3)＝4.

2) n개의 바둑돌을 1개의 그룹 또는 n개의 그룹으로 나누는 방법은 각각 한 가지씩 뿐이므로 P( n,1)＝1, P( n,n)＝1 ( n＝1, 2,3,…).

분할 수에 대하여 다음 정리가 성립한다.

정리. 1 ＜ k ＜ n인 정수 n, k에 대하여

P( n,k)＝P( n - k,1)＋P( n - k,2)＋…＋P( n - k,k).

증명) P( n,k)는 n개의 바둑돌을 똑같은 모양의 k개의 통에 빈 통이 없도 록 넣는 방법의 수이다. 우선, 각 통에 1개씩 넣고 남은 n - k개의 바둑돌을 각 i = 1, 2, …, k에 대하여 i개의 통에 빈 통이 없도록 넣으면 ( P( n - k, i ) 가지)된다. 따라서 등식이 성립한다.

예. 1) P( 4,2) = P( 2,1) + P( 2,2) = 1 + 1 = 2

P( 4,3) = P( 1,1) = 1

2) 자연수 4를 몇 개의 자연수의 합으로 나타내는 방법의 수는 P( 4,1) + P( 4,2) + P( 4,3) + P( 4,4) = 1 + 2 + 1 + 1 = 5(가지)

토의. 고등학교에서 공부한 중복조합과 자연수의 분할을 비교하여보면 다음 과 같다. 이들 사실을 이해하고 그 뜻에 대하여 알아보자.

① n개의 바둑돌을 k개의 서로 다른 통에 빈 통이 없이 넣음

kH_{n - k}= ( x₁+ x₂+…+ x_k= n의 양의 정수해의 개수)

② _n개의 바둑돌을 _k개의 서로 다른 통에 넣음(빈 통 허용)

kH_n= ( x₁+ x ₂+…+ x_k= n의 음이 아닌 정수해의 개수)

③ n개의 바둑돌을 k개의 그룹으로 나눔 P( n,k)(분할수)

④ n개의 바둑돌을 k개 이하의 그룹으로 나눔

P_k(n)= P ( n, 1) + P ( n,2) + … + P ( n,k)

공 구별 서로 같은 공

빈상자

상자구별 불허 허용

다른 모양 ① _kH_{n - k} ② _kH _n 같은 모양 ③ P( n,k) ④ _Pk(n)

예. 서로 다른 5개의 물건을 서로 다른 3개의 상자에 넣되 빈 상자가 없도 록 배분하는 방법의 수를 구하여라.

풀이) S는 5개를 3상자에 넣는 모든 배분의 집합이라 하고, A_i는 상자 i 가 비어 있도록 하는 배분의 집합이라 하자. 그러면

| S | =₃ ∏5= 3⁵

| A_i| = ₂∏5= 2⁵ (각 물건을 나머지 2상자에 넣는 배분의 수),

| A_i∩ A_j| = ₁∏5= 1 ⁵

| A₁∩ A₂∩ A₃| = 0 따라서,

| ^{A1∩ A 2∩ A 3}|^{= 35-}

(

)

(

)

참고. A_i는 상자 i가 비어있도록 하는 배분이므로 다른 상자 j가 비어 있 든 말든 상관없다. 따라서 | A_i| = 2⁵이다. 그리고

(

)

예. _a가 3개, b가 4개, c가 5개 있다. 여기서 10개를 취하는 조합의 수를 구하여라.

풀이) a, b, c가 각각 무한히 많은 집합을 M이라 하자. M 10개를 취하 는 모든 조합의 집합을 S라 하고, S에서

a를 4개 이상 포함하는 것들의 집합을 A, b를 5개 이상 포함하는 것들의 집합을 B, c를 6개 이상 포함하는 것들의 집합을 _C 라 하자. 그러면

| S | =₃ H ₁₀= 66

| A | =₃ H₆= 28 (∵ M에서 6개를 취한 조합에 a를 4개 넣 으면 A의 원소가 된다)

| B | =₃ H₅= 21

| C | =₃ H₄= 15

A ∩ B는 a가 적어도 4개, b가 적어도 5개가 들어있으므로

| A ∩ B | =₃ H₁= 3 이다. 마찬가지로

| A ∩ C | =₃H ₀= 1, | B ∩ C | = 0, | A ∩ B ∩ C | = 0 따라서,

| A ∩ B ∩ C |= 66 - ( 28 + 2 1 + 15) + ( 3 +1 + 0) - 0 = 6

예. 방정식x + y + z = 14 (x, y, z는 0에서 8까지의 정수)의 해의 수를 구하 여라.

풀이) _{x, y, z}에 제한을 하지 않고 음이 아닌 정수해의 집합을 _S라 하고, x, y, z가 9이상인 해의 집합을 각각 A, B, C라 하자. 그러면

| S | =₃ H₁₄= 120, | A | = | B | = | C | = ₃H ₅= 21

| A ∩ B | = | A ∩ C | = | B ∩ C | = | A ∩ B ∩ C | = 0 따라서,

| A ∩ B ∩ C |= 120 - 3 ×21 = 57

2. 귀납적 정의

자연수 n에 대하여 2ⁿ을 정의해 보자. 이를테면, 2ⁿ= 2⋅2⋅2⋅…⋅2 와 같이 정의할 수 있을 것이다. 또 다는 방법으로,

2¹=2, 2^{k + 1}= 2⋅ 2^k (k≥1) 과 같이 정의해도 된다.

여기서, 후자와 같이 정의하는 방법을 귀납적 정의(recursive definition)라고 한다. 즉, _{n = 1}일 때, ₂ⁿ은 분명히 정의되어 있고, _{n = k}일 때 ₂ⁿ이 정의되었 다고 가정하면 _{n = k + 1}일 때도 정의된다. 그러므로 수학적귀납법의 원리에 의 해 모든 자연수 n 에 대하여 2ⁿ이 정의됨을 알 수 있다. 이와 같은 정의를 사용하여 정의되는 대표적인 것으로 n!이 있으며 다음과 같이 정의 한다.

0≠1,

( k + 1)≠ ( k + 1)k! ( k ≥0)

2-1. 점화식

수열(자연수를 정의역으로 하는 함수)도 귀납적으로 쉽게 정의할 수 있 다. 예컨데, 피보나찌 수열은

a ₁=1, a₂= 1, a_{k + 1}= a_k+ a_{k -1} (k≥2) 처럼 정의할 수 있다.

질문. 등차수열과 등비수열을 귀납적으로 정의해 보자.

이제, 귀납적으로 정의된 수열의 일반항(explicit form)을 구하는 문제에 대 하여 알아보자.

정의. 귀납적 관계식(이를 흔히 점화식이라 부른다)

a_n= ra_{n - 1}+sa_{n - 2}+f(n) (r, s는 상수이고, f( n)은 n에 관한 함수이다)

을 상수계수의 2차 선형점화식이라 부른다. 특히 f( n)=0일 때, 이 식을 동 형(homogeneous)이라 한다. 2차란 이 점화식에서 a_n이 앞의 두 항에 의해 결정됨을 뜻한다.

예. 점화식

a_n= a_{n - 1}+ a_{n - 2} a_n=5 a_{n - 1}-6 a _{n - 2}+n

은 각각 상수계수의 2차 선형점화식이다. 그러나, 점화식 a_n=5 a_{n - 1}+3 a_{n - 3}

은 2차가 아니며,

a _n= a_{n - 1} a_{n - 2}+3n-1 은 선형이 아니므로 각각 2차 선형점화식이 아니다.

2-2. 특성다항식

상수계수의 동형 2차 선형점화식

a _n-r a _{n - 1}-s a_{n - 2}=0 ………… (1)

에 대하여 _x²_-rx-s를 점화식 (1)의 특성다항식(characteristic poly- nomial)이라고 한다. 또 이 특성다항식의 근을 특성해라 한다. 예컨대,

a_n= 5a_{n - 1}-6a_{n - 2}의 특성다항식은 x²-5x+6이며 특성근은 2, 3이다.

정리 1. 다항식 x²-rx-s의 두 근을 _{x1, x2}라 하면, 점화식 a _n-r a _{n - 1}-s a_{n - 2}=0, n≥2

의 해는 다음과 같다.

x₁≠x₂이면, a_n= c₁xⁿ₁+c₂xⁿ₂ x₁= x₂= x이면, a_n= c₁xⁿ+c₂nxⁿ 여기서, _c1,c2는 초기 조건으로 결정된다.

점화식을 만족한다. 같은 방법으로 특성다항식이 서로 다른 두 근을 가질 때에도 정리의 결과가 성립한다.

토의. 위의 정리를 미분방정식에서 2계 선형 미분방정식의 해를 구하는 방 법과 비교, 토의해 보자.

예. 피보나찌 수열

a _n= a_{n - 1}+ a_{n - 2}, n≥2 a₀=1, a₁=1

의 일반항을 구해 보자.

풀이) 주어진 점화식의 특성다항식은 x²-x-1 이고, 이 식의 두 근은

1 + 5

2 , 1 - 5 2 이다. 따라서 일반항은 위의 정리에 의해

a_n= c₁

(

)

(

)

이다. 초기조건 _{a 0= 1, a 1= 1}에서 c₁+ c₂= 1

c₁

(

)

(

)

따라서,

a_n= 1

5

(

)

(

)

이다. 실제로, 피보나찌 수열의 n번째 항은 a_{n - 1}= 1

5

(

)

(

)

이다.

문제 7. 다음 점화식으로 주어진 수열의 일반항을 구하여라.

(1) a_n= 5 a_{n - 1}-6 a_{n - 2}, n≥2 a₀=1, a₁=4 (2) a_n= 4 a_{n - 1}-4 a_{n - 2}, n≥2 a₀=1, a₁=4

동형이 아닌 2차 선형점화식에서 일반항을 구하는 데는 다음 정리가 사 용된다.

정리 2. _pn이 점화식 _{an= ran - 1+san - 2+f(n)}의 특수해, _qn이 점화식 a_n= ra_{n - 1}+sa_{n - 2}의 해이면 _pn+qn은 점화식 _{an= ran - 1+san - 2+f(n)}의 해 이다.

토의. 동형이 아닌 2계 선형미분방정식의 일반해를 구하는 방법을 알아보 고, 위 정리의 증명을 해 보자.

예. 점화식 _{an= 2an - 1+3an - 2+5}ⁿ_{, n≥2, a0=-2, a1= 1}의 해를 구해 보 자.

풀이) p_n= a 5ⁿ의 꼴임을 짐작할 수 있으므로 이를 주어진 점화식에 대입 하면

a 5ⁿ=2a 5^{n - 1}+3a 5^{n - 2}+ 5ⁿ 25a = 10a + 3a + 25

a = 25 12

따라서, 특수해로서 p_n= 25

12 5ⁿ을 얻는다.

한편, 점화식 a_n=2a_{n - 1}+3a_{n - 2}의 일반해는 특성다항식 x²-2x-3

의 두 근이 -1, 3이므로 정리 1에 의해

q_n= c₁(-1)ⁿ+c₂3ⁿ 이다. 그러므로, 구하는 해는 정리 2로부터

p_n+q_n= ²⁵

12 5ⁿ+c₁(-1)ⁿ+c₂3ⁿ 이다. 초기 조건을 이용하면, _c1=- ¹⁷

24 , c₂=- 27

8 임을 알 수 있다.

문제 8. 다음 점화식으로 주어진 수열의 일반항을 구하여라.

(1) a_n=-3 a_{n - 1}+n, n≥1 a ₀= 1

(2) a_n= 4 a_{n - 1}-4 a_{n - 2}+n, n≥2 a₀= 5, a₁= 9

2-3. 생성함수

정의. 수열 {a_n}에 대하여 함수

f( x) =a₀+a ₁x+a₂x²+a ₃x³+…

을 {a_n}의 생성함수라 한다.

생성함수의 합, 곱은 일반적인 방법으로 정하며 생성함수를 이용하여 점 화식의 해를 구할 수 있다.

예. _{an=2an - 1-an - 2, n≥2}, _{a0= 3, a 1=-2}를 풀어 보자.

풀이) f( x)를 이 수열의 생성함수라고 하면, f( x) =a₀+a₁x+a₂x²+a ₃x³+…

2x f( x) = 2a₀x+2a₁x²+ … x²f(x) = a₀x²+a₁x³+…

따라서,

f( x) - 2x f( x) + x²f(x) = 3-8x 즉,

f( x) = 1

( 1 - x)²(3-8x)

= ( 1 + 2x + 3x²+ … + ( n + 1)xⁿ+ …)( 3 - 8x)

= 3 - 2x - 7x^2…+(-5n+3)xⁿ+ … 그러므로, a _n= 3 - 5n이다.

문제 9. 생성함수를 이용하여 다음 점화식의 일반항을 구하여라.

(1) a _n=-3a_{n - 1}+10a_{n - 2}, n≥2, a₀=1, a₁=4

(2) _{a n=-an - 1}+2n-3, n≥1, a₀= 1

토의. 생성함수의 계수를 구하는 방법을 해석학에서 특수한 함수의 테일러 급수 전개식의 계수를 구하는 방법을 이용할 수 있을지에 대하여 토의해 보 자.

3. 알고리즘

체계적인 문제해결은 인간의 주 활동이다. 문제해결은 두 단계로 나눌 수 있다. 첫째, 문제해결을 위하여 정확히 정의된 일련의 절차를 구안해야한다. 이 것은 흥미로운 일이며 좋은 착상이 요구된다. 다음은 이들 절차에 따라 수행하 는 일로 보통은 시간이 많이 소요되는 지루한 작업이며, 이는 컴퓨터에게 맡기 는 것이 최선일 것이다. 문제해결을 위한 일련의 절차를 우리는 알고리즘이라 고 부른다. 알고리즘의 개념은 처방전, 절차와 과정, 방법 및 컴퓨터 프로그램 과 밀접한 관계가 있다. 알고리즘은 일상의 언어로 나타낼 수 있으나 보통은 순차적인 지시 사항을 잘 표현할 수 있는 정교한 형식적 언어를 선택해서 사 용한다. 이와 같은 형식적 언어로 알고리즘을 나타낸 것을 프로그램이라 한다.

여기에서는 일상의 언어와 컴퓨터가 인식할 수 있는 형식적 프로그래밍 언어 의 중간 단계의 언어를 사용하여 알고리즘을 나타내기로 한다.

3-1. 기본적 알고리즘

모든 컴퓨터는 저장하는 장소(location)를 가지고 있다. 각 장소는 한 개 의 숫자를 쓸 수 있는 조그마한 칠판으로 비유될 수 있다. 컴퓨터는 수를

a⋅10b는 정수이고 _0.1≤a≤1.

의 형태로 저장한다. 각각의 장소는 문자나 숫자가 딸린 문자로 이름을 붙 인다. 예컨대, A, C, A0, X7, X(0), X(1), ..., B(3,4) 등과 같은 이름을 붙일 수 있다. 컴퓨터는 몇 가지의 한정된 간단한 명령어나 지시 사항 예컨대, 변 수의 지정, 두 수의 대소 비교, 사칙연산 정도만을 수행할 수 있다. 먼저, 간 단한 예를 통하여 알고리즘의 표현 방법을 익혀 보기로 하자.

예 1. 주어진 n개의 수 a_1, a_2, …, a_n의 합을 구하는 알고리즘은 다음과 같다.

Step 1 : S ← 0;

Step 2 : for i = 1 to n, S ← S + a_i ; Step 3 : print S