이산수학(Discrete Mathematics)

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

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

2 이산수학? 무엇을 배울 것이라 생각하고 왔나요? 수학… 어렵다… 전필도 아닌데… 피해갈 수 없을까?
Overview of Discrete Mathematics 무엇을 배울 것이라 생각하고 왔나요? 수학… 어렵다… 전필도 아닌데… 피해갈 수 없을까? 미적, 선대, 머 그런거랑 별반 다르지 않겠지? 여러분은 이산수학을 어떻게 생각하고 수강신청 했나요?

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

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

5 강의 계획(2/3) 평가 기준 (비율은 변경될 수 있음) 강의 계획 중간시험 30% 기말시험 40%
Overview of Discrete Mathematics 평가 기준 (비율은 변경될 수 있음) 중간시험 30% 기말시험 40% 숙제 20% (일반숙제 6-7회, 프로그래밍 숙제 2-3회 예정) 출석 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 중간시험

6 강의 계획(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% 감점

7 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

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

9 Summary of Notations Overview of Discrete Mathematics

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

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

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

13 전산학, 컴퓨터 프로그래밍에서 수학적 토대를 제공함
이산수학? Overview of Discrete Mathematics 전산학, 컴퓨터 프로그래밍에서 수학적 토대를 제공함 수학이간 하지만 비교적 어렵지 않습니다. 컴퓨터 전공에서 꼬옥 필요한 수학 엑기스를 배웁니다. 추후 알고리즘, 데이터베이스 등의 기초실력으로 작용합니다. 자~ 한 학기 이산수학 열심히 공부해 봅시다!