(컴퓨터 과학을 위한) 이산수학

목차 (Table of Contents)

• 목차
• 제1장 집합, 증명유형, 귀납 = 1
• 1.1 기본정의 = 2
• 1.1.1 수학적으로 집합 기술하기 = 3
• 1.1.2 집합 소속자격 = 5
• 1.1.3 집합들의 동등 = 5
• 1.1.4 유한 집합과 무한 집합 = 6
• 1.1.5 집합들 간의 관계 = 7
• 1.1.6 벤 다이어그램 = 8
• 1.1.7 증명유형들 = 10
• 1.2 연습문제 = 14
• 1.3 집합연산 = 17
• 1.3.1 합집합과 교집합 = 17
• 1.3.2 차집합, 여집합, 드모르간의 법칙 = 23
• 1.3.3 새로운 증명유형 30
• 1.3.4 멱집합과 곱 = 31
• 1.3.5 격자와 부울 대수 = 32
• 1.4 연습문제 = 35
• 1.5 포함-배제의 원리 = 39
• 1.5.1 유한 원소수 = 39
• 1.5.2 두 집합에 대한 포함-배제의 원리 = 41
• 1.5.3 세 집합에 대한 포함-배제의 원리 = 43
• 1.6 연습문제 = 47
• 1.7 수학적 귀납법 = 51
• 1.7.1 귀납법의 첫 형태 = 51
• 1.7.2 귀납법에 의해 증명하는 증명유형 = 56
• 1.7.3 응용: 피보나치 숫자들 = 58
• 1.7.4 응용: 멱집합의 크기 = 60
• 1.7.5 응용: 등비수열 = 61
• 1.8 프로그램의 정확성 = 63
• 1.8.1 의사코드 규약 = 64
• 1.8.2 완전 제곱을 생성하는 알고리즘 = 65
• 1.8.3 제곱근을 계산하는 두 개의 알고리즘 = 66
• 1.9 연습문제 = 70
• 1.10 수학적 귀납법의 강력한 형대 = 75
• 1.10.1 수학적 귀납법의 강력한 형태 이용 = 77
• 1.10.2 응용: 승의 계산 알고리즘 = 82
• 1.10.3 응용: 인수분해 찾기 = 84
• 1.10.4 응용: 이진탐색 = 87
• 1.11 연습문제 = 89
• 1.12 이 장의 정리 = 92
• 1.12.1 용어, 정리, 알고리즘, 증명유형 = 93
• 1.12.2 복습문제 = 97
• 1.12.3 복습심화문제 = 98
• 1.12.4 컴퓨터 과학에서의 이산수학 활용 = 100
• 제2장 형식 논리 = 103
• 2.1 명제논리의 소개 = 104
• 2.1.1 식 = 106
• 2.1.2 식에 대한 표현 트리 = 109
• 2.1.3 식에 대한 단축 표기법 = 112
• 2.1.4 게이트를 사용한 식의 표현 = 112
• 2.2 연습문제 = 114
• 2.3 참과 논리적 참 = 118
• 2.3.1 항진명제 = 122
• 2.3.2 항진명제로의 치환 = 125
• 2.3.3 논리적으로 타당한 추론 = 126
• 2.3.4 조합망 = 129
• 2.3.5 동등한 부분식들의 대체 = 131
• 2.3.6 부정을 간략화하기 = 131
• 2.4 연습문제 = 133
• 2.5 정규형 = 139
• 2.5.1 논리합 정규형 = 139
• 2.5.2 응용: DNF와 조합망 = 143
• 2.5.3 응용: 논리곱 정규형 = 143
• 2.5.4 응용: CNF와 조합망 = 145
• 2.5.5 충족가능성과 타당성 검증 = 146
• 2.5.6 유명한 P≠NP 추측 = 147
• 2.5.7 도출 증명: 자동화된 논리 = 148
• 2.6 연습문제 = 150
• 2.7 술어와 한정화 = 154
• 2.7.1 술어 = 154
• 2.7.2 정량화 155
• 2.7.3 제한된 정량화 = 156
• 2.7.4 중첩된 정량자 = 157
• 2.7.5 부정과 정량화 = 158
• 2.7.6 논리곱과 논리합에 대한 정량화 = 159
• 2.7.7 응용: 루프 불변 단언 = 161
• 2.8 연습문제 = 164
• 2.9 이 장의 정리 = 169
• 2.9.1 용어와 정리 = 170
• 2.9.2 복습문제 = 172
• 2.9.3 복습심화문제 = 173
• 2.9.4 컴퓨터 과학에서의 이산수학 활용 = 174
• 제3장 관계 = 179
• 3.1 이항 관계 = 180
• 3.1.1 n항 관계 = 185
• 3.2 이항 관계의 연산 = 186
• 3.2.1 역 = 186
• 3.2.2 합성 = 188
• 3.3 연습문제 = 189
• 3.4 관계의 특별한 형태 = 191
• 3.4.1 반사적 및 비반사적 관계 = 191
• 3.4.2 대칭적 및 반대칭적 관계 = 193
• 3.4.3 추이적 관계 = 196
• 3.4.4 반사적, 대칭적, 추이적 폐쇄 = 197
• 3.4.5 응용: 의학 및 공학에서의 추이적 폐쇄 = 201
• 3.5 연습문제 = 203
• 3.6 동치 관계 = 206
• 3.6.1 분할 = 209
• 3.6.2 동치 관계의 비교 = 213
• 3.7 연습문제 = 215
• 3.8 순서 관계 = 218
• 3.8.1 부분 순서 = 218
• 3.8.2 선형 순서 = 221
• 3.8.3 비교가능한 원소들 = 223
• 3.8.4 순서에서의 최적 원소 = 224
• 3.8.5 응용: 극소원소 찾기 = 227
• 3.8.6 응용: 부분 순서를 확장하기 = 228
• 3.9 연습문제 = 230
• 3.10 관계형 데이터베이스: 소개 = 231
• 3.10.1 관계의 형태로 정보를 저장하기 = 232
• 3.10.2 관계형 대수 = 234
• 3.11 연습문제 = 241
• 3.12 이 장의 정리 = 243
• 3.12.1 요약 = 243
• 3.12.2 복습문제 = 245
• 3.12.3 복습심화문제 = 247
• 3.12.4 컴퓨터 과학에서의 이산수학 활용 = 248
• 제4장 함수 = 251
• 4.1 기본 정의 = 252
• 4.1.1 규칙으로서의 함수 = 254
• 4.1.2 집합으로서의 함수 = 254
• 4.1.3 재귀적으로 정의된 함수들 = 256
• 4.1.4 함수의 그래프 = 258
• 4.1.5 함수의 동등성 = 259
• 4.1.6 함수의 제한 = 262
• 4.1.7 부분 함수 = 262
• 4.1.8 1-1과 전사 함수 = 265
• 4.1.9 증가 함수와 감소 함수 = 272
• 4.2 연습문제 = 273
• 4.3 함수의 연산 = 278
• 4.3.1 함수의 합성 = 278
• 4.3.2 함수의 역 = 281
• 4.3.3 함수의 다른 연산 = 283
• 4.4 수열과 부분 수열 = 284
• 4.5 연습문제 = 287
• 4.6 비둘기 집의 원리 = 290
• 4.6.1 k대 1 함수 = 291
• 4.6.2 비둘기 집의 원리의 증명 = 294
• 4.6.3 응용: 유리수의 소수 표현 = 294
• 4.6.4 응용: 약수와 스케줄의 문제 = 297
• 4.6.5 응용: 두 가지 조합적 결과들 = 298
• 4.7 연습문제 = 301
• 4.8 셀 수 있는 집합과 셀 수 없는 집합 = 303
• 4.8.1 셀 수 있는 무한 집합 = 305
• 4.8.2 칸토어의 첫 번째 대각선 추론 = 308
• 4.8.3 셀 수 없는 집합과 칸토어의 두 번째 대각선 추론 = 309
• 4.8.4 멱집합의 기수 = 313
• 4.9 연습문제 = 313
• 4.10 이 장의 정리 = 315
• 4.10.1 용어와 정리, 알고리즘 = 316
• 4.10.2 복습문제 = 318
• 4.10.3 복습심화문제 = 320
• 4.10.4 컴퓨터 과학에서의 이산수학 활용 = 322
• 제5장 알고리즘 분석 = 325
• 5.1 함수 증가율의 비교 = 326
• 5.1.1 증가율을 비교하기 위한 척도 = 327
• 5.1.2 점근적 지배의 속성 = 331
• 5.1.3 다항 함수 = 334
• 5.1.4 지수 및 로그 함수 = 336
• 5.2 연습문제 = 339
• 5.3 프로그램 복잡도 = 342
• 5.3.1 명령어 수를 세기 = 344
• 5.3.2 선택을 보여주는 두 알고리즘 = 347
• 5.3.3 반복을 설명하는 알고리즘 = 349
• 5.3.4 중첩된 반복을 설명하는 알고리즘 = 352
• 5.3.5 알고리즘의 시간 복잡도 = 353
• 5.3.6 복잡도 정의의 변형 = 356
• 5.4 연습문제 = 358
• 5.5 계산불능성 = 362
• 5.5.1 정지 문제 = 364
• 5.6 이 장의 정리 = 367
• 5.6.1 용어와 정리, 알고리즘 = 368
• 5.6.2 복습문제 = 369
• 5.6.3 복습심화문제 = 370
• 5.6.4 컴퓨터 과학에서의 이산수학 활용 = 371
• 제6장 그래프 이론 = 379
• 6.1 그래프 이론의 소개 = 380
• 6.1.1 정의 = 382
• 6.1.2 부분 그래프 = 384
• 6.2 악수 문제 = 387
• 6.3 경로와 사이클 = 389
• 6.3.1 해밀턴 사이클 = 391
• 6.4 그래프 동형 = 394
• 6.5 그래프의 표현 = 396
• 6.5.1 인접 행렬 = 396
• 6.5.2 인접 리스트 = 397
• 6.6 연습문제 = 397
• 6.7 연결된 그래프 = 402
• 6.7.1 CONN 관계 = 403
• 6.7.2 깊이 우선 탐색 = 404
• 6.7.3 Dfs의 복잡도 = 407
• 6.7.4 넓이 우선 탐색 = 408
• 6.7.5 결합 요소를 찾는 과정 = 410
• 6.8 쾨니히스베르크 다리 문제 = 411
• 6.8.1 그래프 그리기 = 415
• 6.9 연습문제 = 417
• 6.10 트리 = 421
• 6.10.1 트리의 정의 = 422
• 6.10.2 트리의 특성 = 423
• 6.11 신장 트리 = 425
• 6.11.1 크루스컬의 알고리즘 = 426
• 6.11.2 크루스컬의 알고리즘의 정확성 = 426
• 6.11.3 가중 그래프에 크루스컬의 알고리즘을 적용 = 427
• 6.11.4 크루스컬의 가중 그래프 알고리즘의 정확성 = 429
• 6.12 루트가 있는 트리 = 430
• 6.12.1 이진 트리 = 432
• 6.12.2 이진탐색 트리 = 434
• 6.12.3 트리 순회 = 437
• 6.12.4 응용: 결정 트리 = 439
• 6.13 연습문제 = 441
• 6.14 유향 그래프 = 445
• 6.14.1 기본 정의 = 445
• 6.14.2 유향 추적, 경로, 회로, 사이클 = 446
• 6.14.3 유향 그래프의 동형 = 447
• 6.15 응용: 회의 시설의 일정 설계 = 447
• 6.15.1 WAITFOR 그래프 = 448
• 6.16 유향 그래프에서 사이클 찾기 = 450
• 6.16.1 유향 사이클 검출 알고리즘 = 451
• 6.16.2 유향 사이클 검출의 정확성 = 452
• 6.17 일정에서의 우선순위 = 452
• 6.17.1 위상 정렬 알고리즘 = 453
• 6.17.2 위상 정렬 알고리즘의 정확성 = 454
• 6.18 유향 그래프에서의 연결성 = 455
• 6.18.1 강하게 결합된 유향 그래프 = 455
• 6.18.2 응용: 일방통행인 도로의 도로망 설계 = 457
• 6.19 유향 그래프에서 오일러 회로 = 458
• 6.20 연습문제 = 459
• 6.21 이 장의 정리 = 463
• 6.21.1 용어와 정리, 알고리즘 = 464
• 6.21.2 복습문제 = 467
• 6.21.3 복습심화문제 = 469
• 6.21.4 컴퓨터 과학에서의 이산수학 활용 = 472
• 제7장 경우의 수 세기와 순열 조합론 = 477
• 7.1 외판원의 문제 = 478
• 7.2 수를 세는 법칙 = 480
• 7.2.1 곱의 법칙 = 481
• 7.2.2 합의 법칙 = 483
• 7.3 집합 분해 법칙 = 485
• 7.3.1 여집합을 이용한 수 세기 = 486
• 7.3.2 비둘기 집의 원리의 이용 = 487
• 7.3.3 응용: 유닉스 로그온 암호 = 489
• 7.4 연습문제 = 490
• 7.5 순열과 조합 = 493
• 7.5.1 순열 = 494
• 7.5.2 일렬 정렬 = 495
• 7.5.3 원 순열 = 497
• 7.5.4 조합 = 498
• 7.5.5 포커게임 = 500
• 7.5.6 여집합을 이용한 수 세기 = 502
• 7.5.7 소문제로 분해하기 = 503
• 7.6 k번째 순열의 생성 = 506
• 7.7 연습문제 = 508
• 7.8 반복을 갖는 경우의 순열 = 513
• 7.8.1 반복을 갖는 경우의 순열 = 513
• 7.8.2 반복을 갖는 경우의 조합 = 516
• 7.9 조합 등식 = 519
• 7.9.1 이항계수 = 521
• 7.9.2 다항식 = 524
• 7.10 파스칼 삼각형 = 525
• 7.11 연습문제 = 527
• 7.12 이 장의 정리 = 533
• 7.12.1 용어와 정리 = 534
• 7.12.2 복습문제 = 535
• 7.12.3 복습심화문제 = 536
• 7.12.4 컴퓨터 과학에서의 이산수학 활용 = 537
• 제8장 이산 확률 = 541
• 8.1 컴퓨터 과학에서 확률의 개념 = 542
• 8.1.1 도입 예제 = 543
• 8.1.2 기본적 정의 = 544
• 8.1.3 확률의 빈도적 해석 = 547
• 8.1.4 도입 예제의 재고 = 547
• 8.1.5 균등확률밀도와 조합이론 = 549
• 8.1.6 집합이론과 사건의 확률 = 552
• 8.2 연습문제 = 557
• 8.3 교차곱 표본공간 = 561
• 8.3.1 곱의 법칙 = 561
• 8.3.2 표본공간의 교차곱 = 564
• 8.3.3 베르누이 시행 과정 = 567
• 8.3.4 교차곱 형태의 사건 = 570
• 8.3.5 사건을 나타내는 두 가지 방법 = 572
• 8.4 연습문제 = 575
• 8.5 독립사건과 조건부 확률 = 578
• 8.5.1 독립사건 = 578
• 8.5.2 조건부 확률 = 581
• 8.5.3 조건부 확률의 탐험 = 584
• 8.5.4 전 확률 공식과 베이즈 공식의 사용 = 587
• 8.6 연습문제 = 589
• 8.7 이산형 확률변수 = 593
• 8.7.1 확률변수의 분포 = 593
• 8.7.2 이항분포 = 595
• 8.7.3 초기하분포 = 596
• 8.7.4 확률변수의 기대값 = 598
• 8.7.5 확률변수들의 합 = 601
• 8.8 연습문제 = 604
• 8.9 분산, 표준편차 및 대수의 법칙 = 605
• 8.9.1 분산과 표준편차 = 606
• 8.9.2 독립인 확률변수들 = 608
• 8.10 연습문제 = 615
• 8.11 이 장의 정리 = 616
• 8.11.1 용어와 정리, 알고리즘 = 617
• 8.11.2 복습문제 = 619
• 8.11.3 복습심화문제 = 620
• 8.11.4 컴퓨터 과학에서의 이산수학 활용 = 623
• 제9장 재귀 관계 = 627
• 9.1 하노이의 탑 문제 = 627
• 9.1.1 하노이 탑 문제에 대한 재귀 관계 = 630
• 9.1.2 하노이 탑 재귀 관계의 해 = 630
• 9.2 1차 재귀 관계의 해 구하기 = 632
• 9.2.1 역치환을 이용한 1차 재귀 관계의 해 구하기 = 633
• 9.3 연습문제 = 636
• 9.4 피보나치 재귀 관계 = 641
• 9.4.1 2차 재귀 관계 = 641
• 9.4.2 피보나치 재귀 관계의 해 구하기 = 644
• 9.4.3 2차 재귀 관계의 해를 구하는 규칙 = 646
• 9.5 연습문제 = 647
• 9.6 분할정복 패러다임 = 648
• 9.7 이진탐색 = 649
• 9.7.1 정확성 = 650
• 9.7.2 복잡도 = 650
• 9.8 병합정렬 = 651
• 9.8.1 정확성 = 652
• 9.8.2 예제 = 652
• 9.8.3 복잡도 = 652
• 9.9 n-비트 정수의 곱셈 = 653
• 9.10 분할정복 재귀 관계 = 656
• 9.10.1 분할정복 재귀 관계의 복잡도 = 660
• 9.11 연습문제 = 661
• 9.12 이 장의 정리 = 662
• 9.12.1 용어, 정리, 알고리즘 = 662
• 9.12.2 복습문제 = 664
• 9.12.3 복습심화문제 = 664
• 9.12.4 컴퓨터 과학에서의 이산 수학 활용 = 665
• 부록 A 언어와 정규 집합 = 669
• 부록 B 유한 오토마타 = 675
• 찾아보기 = 681