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

이산수학 개요 및 응용 분야 과목 개요 이산수학의 응용 분야 전산학(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) 없음 (고등학교 교육을 충실히 받은 학생은 모두 수강 가능함) 강의 시간 및 담당 교수 강의 시간: 월, 목 2교시 (10:30-12:00) 담당 교수: 문양세 (자대 5호관 215호실, x8449, ysmoon@kangwon.ac.kr) 교재 공은배 외, 이산수학(제5판/제6판), 인터비젼/한국맥그로힐 원서: Rosen, K. H., Discrete Mathematics and Its Applications, McGraw-Hill. Web Site: http://www.mhhe.com/math/advmath/rosen/

강의 계획(2/3) 평가 기준 강의 계획 중간시험 30% 기말시험 40% 숙제 20% Overview of Discrete Mathematics 평가 기준 중간시험 30% 기말시험 40% 숙제 20% 출석 10% (1/3 결석 시, 학교 원칙에 의해 F임에 유의) 강의 계획 Week 강의 내용 비고 1 Overview, Logic, Propositional Equivalences, Predicates and Quantifiers 2 Nested Quantifiers, Proof Methods, Sets 3 Sets, Set Operations 4 Functions, Algorithms, Growth of Functions 5 Growth of Functions, Algorithm Complexity 6 The Integers and Division, Integers and Algorithms 7 Matrices, Proof Strategy 8 중간시험

강의 계획(3/3) Overview of Discrete Mathematics 강의 계획 (계속) Week 강의 내용 비고 9 Sequences and Summations, Mathematical Induction 10 Recursion, Recursive Algorithms 11 Basics of Counting, The Pigeonhole Principle 12 Permutations and Combinations, Discrete Probability 13 Recurrence Relations, Divide-and-Conquer 14 Relations and Its Properties, n-ary Relations, Representing Relations 15 기말시험 기타 사항 강의 사이트: http://cs.kangwon.ac.kr/~ysmoon/courses/2012_1/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

이산수학? 뭐에다 써? 재귀 함수 집합? 리스트? floor function 명제 함수 Overview of Discrete Mathematics 재귀 함수 집합? 리스트? 명제 함수 floor function

Summary of Notations Overview of Discrete Mathematics

중독… 미친 사람… (나쁜 버전) Overview of Discrete Mathematics

중독… 미친 사람… (좋은 버전) Overview of Discrete Mathematics

중독된 미래의 당신 모습은? Overview of Discrete Mathematics VS