이산수학 (Discrete Mathematics) 개요 (Overview) 2006년 봄학기 문양세 강원대학교 컴퓨터과학과

이산수학 개요 및 응용 분야 과목 개요 이산수학의 응용 분야 전산학(Computer Science)의 필수 기초 과목 Overview of Discrete Mathematics 과목 개요 전산학(Computer Science)의 필수 기초 과목 논리 및 명제, 집합 이론, 관계, 순열 및 조합, 순환 관계, 그래프 및 트리, …  알고리즘 설계 및 분석, 데이타베이스 설계, 프로그래밍 원리 등 컴퓨터 전반에 걸쳐 필요한 수학 기반의 추상적 개념을 다룸 이산수학의 응용 분야 Programming Languages Algorithms & Data Structures Compiler Design & Automata Theory Database Design & Implementation Computer Architecture and Networks Operating Systems Cryptography & Security Just about Everything in Computer Science!

강의 계획(1/3) 선수 과목 (Prerequisites) 강의 시간 및 담당 교수 강의 교재 Overview of Discrete Mathematics 선수 과목 (Prerequisites) 없음 (고등학교 교육을 충실히 받은 학생은 모두 수강 가능함) 강의 시간 및 담당 교수 강의 시간: 월, 목 3교시 (12:00-13:30) 담당 교수: 문양세 (자연과학대 5호관 201호실, x8449, ysmoon@kangwon.ac.kr) 강의 교재 공은배 외, 이산수학(제5판), 인터비젼 원서: Rosen, K. H., Discrete Mathematics and Its Applications, 5/E, McGraw-Hill. Web Site: http://www.mhhe.com/math/advmath/rosen/ 참고도서: Liu, C. L., Elements of Discrete Mathematics, 2/E, McGraw-Hill.

강의 계획(2/3) 평가 기준 강의 계획 중간시험 30% 기말시험 40% 숙제 20% 출석 10% 1 Overview of Discrete Mathematics 평가 기준 중간시험 30% 기말시험 40% 숙제 20% 출석 10% 강의 계획 Week 강의 내용 비고 1 Overview, Logic, Propositional Equivalences, Predicates and Quantifiers $1.1, $1.2, $1.3 2 Nested Quantifiers, Proof Methods, Sets $1.4, $1.5 3 Sets, Set Operations $1.6, $1.7 4 Functions, Algorithms, Growth of Functions $1.8, $2.1 5 Growth of Functions, Algorithm Complexity $2.2, $2.3 6 The Integers and Division, Integers and Algorithms $2.4, $2.5 7 Matrices, Proof Strategy $2.7, $3.1 8 중간시험

강의 계획(3/3) Overview of Discrete Mathematics 강의 계획 (계속) Week 강의 내용 비고 9 Sequences and Summations, Mathematical Induction $3.2, $3.3 10 Recursion, Recursive Algorithms $3.4, $3.5 11 Basics of Counting, The Pigeonhole Principle $4.1, $4.2 12 Permutations and Combinations, Discrete Probability $4.3, $5.1 13 Recurrence Relations, Divide-and-Conquer $6.1, $6.3 14 Relations and Its Properties, n-ary Relations, Representing Relations $7.1, $7.2, $7.3 15 기말시험 기타 사항 강의 사이트: http://cs.kangwon.ac.kr/~ysmoon/courses/2006_1/dm/dm.html ( 강의 노트는 강의 전까지 Upload 예정임) 숙제 제출 관련: 제출 기한 이후에 제출하면 20% 감점

Traveling Salesman Problem Overview of Discrete Mathematics 문제 정의 N개의 도시(C1, C2, … CN)와 두 도시 i와 j 사이의 거리 dij가 주어졌을 때, 모든 도시를 한번씩 방문해야 하는 외판원이 다리 품을 가장 적게 파는 경로(shortest tour)는? 경로의 가짓수 계산 첫 번째 도시를 선택할 수 있는 가짓수: N가지 두 번째 도시를 선택할 수 있는 가짓수: (N-1)가지 …  경로의 가짓수 = N(N-1)(N-2)…(2)(1) = N! TSP를 풀기 위해 얼마나 걸리는가? 하나의 경로 계산을 위해 1 ns가 걸린다고 가정 (1 GHz  1 flop/1 ns) N=10: 3,628,800 ns = 0.0036288 sec. N=50: 3.02 x 1064 ns = 3.02 x 1055 seconds = 3.50 x 1050 days = 9.59 x 1047 years  해결할 수 있는 방법은? (Refer to http://www.tsp.gatech.edu//index.html) 56 32 51 62 115 73 108 49 89 94

Summary of Notations Overview of Discrete Mathematics