Discrete Mathematics(4190.101)

Fall 2014

Instructor

Jehee Lee

E-mail: jehee (at) mrl (dot) snu (dot) ac (dot) kr

Office: 302-325

Phone: 880-1845

Teaching Assistant

Dongchul Jo

Email: dcjo (at) mrl (dot) snu (dot) ac (dot) kr

Office 302-312-1

Phone: 880-1864

TA hour: Mon, Fri (14:00 ~ 15:00)

Class hours

Tuesday and Thursday, 11:00 to 12:15

Class Room

Building 302, Room 106

Textbook

Discrete Mathematics and its Applications , Kenneth Rosen (7th edition, global edition), McGraw Hill

Pre-requisites

This course has no pre-requisites.

과목 개요

이 과목은 학생들이 논리적이고 계산적으로 생각하고, 이산 수학의 여러 기법들을 실질적으로 문제를 푸는데 적용하는 것을 목표로 합니다. 미적분학에서 주로 연속적인 함수 혹은 개체를 대상으로하는데 반해서, 이산 수학은 불연속적인 개체를 대상으로한 다양한 수학 분야들을 아우르는 입문적 성격의 과목입니다. 이산수학에 처음 발을 내딛는 초심자들에게 논리, 증명, 집합, 함수, 알고리즘, 관계, 그래프, 트리에 관련된 기본적인 개념을 이해할 수 있는 기회를 제공합니다. 이 과목은 향후 컴퓨터를 전공, 복수전공, 부전공할 학생들을 염두에 두고 있으나, 이산 수학의 근본 개념은 컴퓨터 뿐만 아니라 과학과 공학 전 분야에 대해 공통적으로 적용되기에 컴퓨터와 관련 없는 타 전공 학생들이 수강해도 됩니다.

컴퓨터와 이산 수학의 연계는 그 첫단계에서 논리적이고 엄정한 수학적 (logical and mathematically rigorous) 사고의 방법을 배우는 것에서 부터 시작하여, 이를 그 다음 단계인 계산적이고 알고리즘적인 사고 방식 (computational and algorithmic thinking)으로 연결하는 고리의 역할을 합니다. 강의는 이산수학에 포함되는 다양한 분야를 폭 넓게 개론적으로 다루며, 향후 상위 단계의 과목으로 연결될 접점에 해당하는 부분에서 응용 예를 들여다 보는 방식으로 진행됩니다.

평가 방식

Homework: 20%

  • 매주 숙제가 나갈 계획이고 매 목요일마다 수업 시작하기 전에 숙제를 제출하도록 합니다. 숙제는 모두 손으로 써서 제출하도록 하고, 시간이 지난 숙제는 받지 않습니다. 숙제는 완료도와 정답률을 부분적으로 고려하여 평가합니다. 한 학기 전체에서 한 번까지는 숙제를 제출하지 않는 것을 허용합니다.

Quiz: 20%

  • 비정기적으로 수업 시간 중에 20분 정도 시간을 할애해서 퀴즈를 실시합니다. 퀴즈는 그 전시간에 공지합니다.

Midterm Exam: 30%

  • 중간 시험은 8주차 목요일 (10월 23일) 정규 수업 시간에 진행합니다.

Final Exam: 30%

  • 기말 시험은 마지막주 목요일 (12월 11일) 정규 수업 시간에 진행합니다.

수업 진행에 대한 조언

스터디 그룹을 만들어서 같이 숙제와 공부를 해도 됩니까?

  • 스터디 그룹을 만들고 같이 공부하는 것을 적극 권장합니다. 다만, 문제를 푸는 방법을 같이 연구하더라도 숙제는 자기 자신의 풀이 방법을 자기 자신의 글로 적어서 제출해야 합니다. 동료가 풀어놓은 것으로 보고 옮겨적어야 한다면 문제에 대해 충분히 이해하고 있다고 볼 수 없으므로 자신의 숙제로 제출해서는 안 됩니다. 같이 공부하는 것은 숙제에 대해서만 적용되고 시험과 퀴즈에는 적용되지 않습니다.

계산기가 필요합니까?

  • 계산기를 쓰는 것은 무방하나 실제 수업과 시험, 퀴즈, 숙제에서 계산기가 필요할 경우는 없을 것 입니다.

수업에 꼭 출석해야 합니까?

  • 숙제는 수업 시간에만 받습니다. 이 외 시간에는 숙제를 받지 않으니 수업에 참석해야 합니다. 퀴즈도 수업시간 중에 비정기적으로 봅니다. 이런 이유 외에도 수업 시간에 배우는 내용을 혼자서 공부하려면 몇배의 시간과 노력이 필요합니다. 지금까지 십 수년 간의 강의 경험에서 보면 수업을 잘 들어오지 않는 학생이 좋은 성적을 받는 경우는 거의 본 적이 없습니다. 수업에 반드시 출석하기 바랍니다.

인문대 혹은 사회대 소속의 비전공자가 이 과목을 수강해도 됩니까?

  • 이산 수학은 특별한 선수 과목이 없습니다. 이 과목은 처음 입문 과목이기 때문에 누구나 수강할 수 있습니다. 컴퓨터나 프로그래밍에 대한 기본적인 지식이 있다면 도움이 될 여지는 있습니다. 하지만, 강의에서 학생들이 컴퓨터에 대해서 잘 알거나 프로그래밍에 익숙할 것이라고 가정하지 않습니다.

답안과 숙제의 작성

  • 수학 문제를 푼다는 것은 단순히 수식을 나열하는 것이 아니라, 그 밑바닥에 깔린 정교하고 엄정한 수학적 논리의 전개입니다. 몇몇 수식을 나열하고 읽는 사람이 그 내부의 논리를 유추하도록 하는 것은 수학의 엄정한 논리와는 거리가 있습니다. 숙제와 시험/퀴즈의 답안을 작성할 때는 완결된 문장과 정확한 용어로 단계마다 논리가 명확히 드러나도록 작성해야 합니다. 채점자가 논리를 알아서 유추하길 기대하지 마십시오. 완결되지 않은 불완전한 문장에는 부분 점수만을 부여합니다.

교재 버전에 대하여

교재는 Discrete Mathematics and its Applications 7th edition global edition을 사용하고 있습니다. global edition과 기존 7th edition은 전체적으로 거의 비슷하지만 일부 문제가 다릅니다. 그래서 일단은 숙제로 나가는 문제 부분만 스캔해서 업로드하고 있습니다.

Schedule homework
Week 1 9 / 2 Course Introduction

Propositional logic (sec 1.1) pdf
9 / 4 Propositional equivalence (sec 1.2, 1.3, and 1.4)
Week 2 9 / 9 No Class
9 / 11 Predicate logic and nested quantifiers (sec 1.4 and 1.5) pdf
Week 3 9 / 16 Rules of inference (sec 1.6) pdf
9 / 18 Mathematical proofs (sec 1.8 and 1.9) Sec 1.1: 6, 10, 14, 18, 24, 26

Sec 1.2: 2, 6, 10, 18

Sec 1.3: 4, 10

pdf
Week 4 9 / 23 Proof Methods and Strategies
9 / 25 Sets and Functions pdf Sec 1.4: 18, 22, 26, 28, 30, 36

Sec 1.5: 4, 16, 24, 26

Sec 1.6: 4, 10, 14, 20

Sec 1.8: 3, 6, 8, 16

pdf
Week 5 9 / 30 Sets and Functions
10 / 2 Sequences Sums and Matrices Sec 1.9: 3, 14

Sec 2.1: 6, 8, 14, 18, 29

Sec 2.2: 10, 16, 22, 28

pdf
Week 6 10 / 7 Algorithms pdf
10 / 9 No Class
Week 7 10 / 14 The Growth of Functions (sec 3.2)
10 / 16 Complexity of Algorithms (sec 3.3)
Week 8 10 / 21 Mathematical induction and strong induction pdf Sec 3.1: 7, 10, 14, 15, 30, 35, 38, 39

Sec 3.2: 2, 4, 6, 18, 31, 32, 47, 48

Sec 3.3: 2, 9, 10, 14, 17, 18

pdf
10 / 23 Midterm Exam
Week 9 10 / 28 Recursive definitions
10 / 30 Recursive algorithms
Week 10 11 / 4 Counting: basic counting rules pdf
11 / 6 Counting: permutations and combinations Sec 5.1: 4, 6, 8, 12, 18

Sec 5.2: 3, 6, 8, 9

Sec 5.3: 3, 8, 10, 14, 24-36

pdf
Week 11 11 / 11 Discrete Probability pdf
11 / 13 Bayes' Theorem Sec 6.1: 12, 18, 25, 32, 33, 34

Sec 6.2: 6, 8, 12, 19

Sec 6.3: 7, 8, 12, 14

Sec 6.4: 2, 6, 20

Sec 6.5: 4, 6, 8, 14, 16, 24, 32

pdf
Week 12 11 / 18 Advanced Counting Techniques pdf
11 / 20 Advanced Counting Techniques Sec 7.2: 8, 16, 18, 24

Sec 7.3: 6, 10

Sec 7.4: 8, 12, 19, 23

pdf
Week 13 11 / 25 Relations pdf
11 / 27 Relations
Week 14 12 / 2 No Class
12 / 4 No Class
Week 15 12 / 9 No Class
12 / 11 Final Exam (범위는 처음부터 끝까지) [grade]

클레임은 12/19 오후 12시부터 6시까지 302동 312-1호에서