이산수학(Discrete Mathematics)

Presentation on theme: "이산수학(Discrete Mathematics)"— Presentation transcript:

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

2 이산수학 개요 및 응용 분야 과목 개요 이산수학의 응용 분야 전산학(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!

3 강의 계획(1/3) 선수 과목 (Prerequisites) 강의 시간 및 담당 교수 교재
Overview of Discrete Mathematics 선수 과목 (Prerequisites) 없음 (고등학교 교육을 충실히 받은 학생은 모두 수강 가능함) 강의 시간 및 담당 교수 강의 시간: 월, 목 2교시 (10:30-12:00) 담당 교수: 문양세 (자대 5호관 215호실, x8449, 교재 공은배 외, 이산수학(제5판/제6판), 인터비젼/한국맥그로힐 원서: Rosen, K. H., Discrete Mathematics and Its Applications, McGraw-Hill. Web Site:

4 강의 계획(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 중간시험

5 강의 계획(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 기말시험 기타 사항 강의 사이트: ( 강의 노트는 강의 일주일 전까지 Upload 예정임) 숙제 제출 관련: 제출 기한 이후에 제출하면 20% 감점

6 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 = 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 56 32 51 62 115 73 108 49 89 94

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

8 Summary of Notations Overview of Discrete Mathematics

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

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

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