< Discrete Math (Spring, 2018) >

[강의 동영상 &실습실]

http://matrix.skku.ac.kr/sglee/2003-f-DM-Lecture/CH-3-Lec/index.html

​DM Ch. 1, Sets and Logic

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-1/
DM-Ch-1-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-1-Lab.html
DM Ch. 1, 동영상강의
Ch 0 Introduction                   https://youtu.be/9ahFnOFTWNQ
1.1, 1.2 Propositions                https://youtu.be/QgdKqmCFW2Y
1.3, 1.4 Rules of Inference         https://youtu.be/92siPfThf0M
1.5, 1.6 Nested Quantifiers         https://youtu.be/7M7w9eX5D0Q

DM Ch. 2, Proofs

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-2/
DM-Ch-2-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-2-Lab.html
DM Ch. 2, 동영상강의
2.1, 2.2 More Methods of Proof Problem  https://youtu.be/xEMkHb2AkYk
2.4, 2.5 Math Ind &Well-Ordering Prop   https://youtu.be/areatkjOjcg

DM Ch. 3, Functions, Sequences, and Relations

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-3/
DM-Ch-3-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-3-Lab.html
DM Ch. 3, 동영상강의
Functions, Sequences, and Relations 1
https://youtu.be/MhM_9ZuGAis
Functions, Sequences, and Relations 2  https://youtu.be/ZjAtN9HkZwM
Functions, Sequences, and Relations 3  https://youtu.be/Uuwsx2aiEPI

DM Ch. 4, Algorithms

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-4/

DM-Ch-4-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html
DM Ch. 4, 동영상강의   https://youtu.be/Dtv-9ykjFFA

DM Ch. 5, Introduction to Number Theory

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-5/

DM-Ch-5-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-5-Lab.html
DM Ch. 5, 동영상강의

5-1  Divisors    https://youtu.be/NN46r0qlIW0
5-2  Repr of Integers and Integer Alg https://youtu.be/aF5MPAjkMcI
5-3  The Euclidean Algorithm   https://youtu.be/sSuzv8J3MSA

Review (Ch 1-5)  https://youtu.be/aeKA-MNkhCw

PBL 학생 발표 (Ch 1-5 Solutions)  https://youtu.be/HuzLCXDD2AA

DM Ch 6, Counting Methods and the Pigeonhole Principle

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-6/

DM-Ch-6-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-6-Lab.html
DM Ch. 6, 동영상강의
6.1 Basic Principles
https://youtu.be/AU_AbwTSI_Y
6.2 Permutations and Combinations  https://youtu.be/yBwkCoX460o
6.3 Generalized Permutations and Combinations

DM Ch 7, Recurrence Relations

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-7/

DM Ch. 7, 동영상강의 https://youtu.be/1n0dC_ICo4U

DM Ch 8, Graph Theory

Lecture Note      http://matrix.skku.ac.kr/2018-DM/Ch-8/

DM Ch. 8, 동영상강의

DM Ch 9, Trees

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-9/

DM Ch. 9, 동영상강의

CH 10, Network Models (if time permits)

Ch 11 Boolean Algebras and Combinatorial Circuits (if time permits)

Ch 12 Automata, Grammars, and Languages (if time permits)

CH 13 Computational Geometry (if time permits)

Appendix

< Discrete Math (Spring, 2018) >

2018 1StSemester  PBL Report

Flipped/PBL Action Learning

Discrete Mathematics

Prof : Sang-Gu LEE

과제함 Due day : 2018 / 6 / 1(Fri.)

학생들이 QnA에 업로드한 Comment or Answer 일부

(1) State more than 10 DM Definitions and concepts what you learned in Ch. 1-8

Definition: Sets, Propositions, Quantifiers, Proof and methods of proof (direct Proof, contrapositive, counter-examples, etc), Mathmetical Induction, Functions, Sequence and String, Relations, Equivalence Relations, Matrices of Relation, Algorithms(Binary Search, sorting, insertion, etc), Recursive Algorithms(Factorial), Divisors, The Euclidean Algorithm, 경우의 수, 비둘기집 원리, 순열, 조합, 이산 확률, 이항 계수, 점화식, 카탈랑 수, 특성 방정식, 그래프, 해밀턴 사이클, 오일러 회로, 동형, 그래프의 표현, 평면 그래프의 조건, 순간 착란

(2) State more than 5 things that you know/can/find ...  after you studied the 1-8 Chapters.

수학적 귀납법과 Strong Form of Induction의 방식

한정사(Quantifier)와 같은 수학적 기호로 서술된 문장을 해석하기

relation의 종류(reflexive, symmetric, transitive, antisymmetric) 파악

coding of algorithms

matrics의 연산 방법

Definition of Bing O, Omega, Theta

Difference between ‘ not symmetric ’and ‘ antisymmetric ’

카탈랑 수를 이용하여 점화식 풀기

특성 방정식을 치환의 방법을 이용하여 쉽게 풀기

해밀턴 사이클과 오일러 회로 구분하기

모양이 다른 그래프의 동형 확인

평면 그래프의 조건을 이용하여 그래프 확인하기

(3)  교수님과 다른 학생들이 업로드한 Q 에 10개 이상의 자신의 Comment or Answer  (Discussions) 를 주시오.

(4) (첨부한) PBL 보고서에 <자기평가>, <동료평가> + <자신이 QnA 에 업로드한 Q and Answer (Reply) 를 모아서> 주어진 첨부 형식에 맞추어 내용을 채어서 Due Day 전에 제출하시오. 양과 질을 평가하여 성적을 부여합니다.

그리고 중간고사와 기말고사에 여러분이 학습하고 PBL 보고서에 보고한 내용을 반영합니다.

(1) 개인/동료와 같이 DM 강좌를 (PBl/Filpped/Action learning) 학습 하면서 배우거나 느낀 점은?

기존까지 저는 BSM 과목에 대해서는 책을 혼자 읽어보면서 독자적으로 학습하는 과목이라고 생각했었습니다. 하지만 이번 이산수학에 들어서 는 새로운 Flipped class 방식으로 학습을 진행하게 되었습니다. 처음에는 매번 지속적으로 Q&A 게시판에 방문하면서 다른 학생들과 소통하고 토론하고 교수님께 질문을 남기는 작업들이 매우 귀찮았고 복잡했었습니다. 하지만 이렇게 학습을 진행하고 나니 오히려 머리에 더 잘 기억되었고 학습도 능동적으로 참여하면서 하다 보니 이전까지 해왔던 BSM과목 학습효과에 비해 이번 이산수학이 더 뛰어났다는 것을 알 수 있었습니다. 앞으로도 Q&A 게시판에 적극적으로 참여하며 학습에 임해야겠다고 생각했습니다. 그리고 이번 강의말고도 다른  Flipped class가 열린 곳에서도 적극적으로 참여해야겠다고 생각했습니다.

(2) State more than 3 things that you know/can/find ...  after you studied the first 8 Chapters.

집합을 나타내는 기호들과 용어들을 활용하는 법

명제를 나타내는 기호들과 명제들을 증명하는 법

양수사(quantifiers)의 기호 및 활용법, 여러 가지 다양한 증명법들, 다양한 관계들의 종류와 표기법

여러 가지 알고리즘들과 이들의 time complexity를 분석하는 방법들, 정수이론 이진, 팔진, 16진수의 체계 및 나머지 정리, Permutation과 Combination을 활용한 경우의 수 계산, 그래프 이론과 알고리즘을 이용하여 최단 거리를 구하기

 ch1 Sets and logics Sets Symbol, Disjoint, Venn diagram, Partition, Cartasian Product. Propositions conjunction, disjunction, truth table, Operator, conditional proposistion, logical equivalence, biconditional proposition, De Morgan’s law, contrapositive. Inference hypothesis, the modus ponens, modus tollens, conjunction, hypothetical syllogism, Qunatifiers universal quantifiers, existentially quantified statement, nested          quantifiers, ch2 Proofs Mathematical system, direct proofs, counter examples, proof by contradiction, proof by contrapositive, proof by cases, exhaustive proof, proof of equivalence, existence proof, mathematical induction, strong form of induction, well-ordering property ch3 Functions, Sequences, Relations Function round or floor of x, one to one function, onto function, inverse function, bijective function, binary operator, unary operator, sequences, strings. Relation reflexive, symmetric, antisymmetric, transitive, partial order, compositition, equivalence relation, partition, equivalence class. matrix of relation. ch4 Algorithms characteristics of algorithms, linear search, binary search, bubble sort, insertion sort, randomized algorithm, analysis of algorithms, big oh of g(n), omega of g(n), theta of g(n), recursive algorithm ch5 Number Theory divisors, composite, prime number, gcd(m,n), lcm(m,n), decimal num, binary number, octal number, hexadecimal number and operations of these number systems, euclidian algorithm, BEZOUT‘s theorem ch6 Counting Method Basic Principles of Counting, Permutations and Combinations and their Generalization, Bionomial Coefficients and Combinational Identities, The Pigeonhole Principle ch7 Recurrence Relations Fibonacci Sequence, Tower of Hanoi’s minimum moving, Ackerman’s Function, Solving recurrence relation(iteration, linear homogeneous recurrence relation), General method of linear homogeneous recurrence relation, ch8 Graph Theory Vertex, Edge, Path, Complete Graph, Complete bipartite Graph, Cycle, Simple Path, Simple Cycle, Euler Cycle, Hamiltonian Cycle, TSP, Shortest Path Algorithm(Dijkstra’s Algorithm), Adjacency Matrix, Isomorphisms of graph, Planar Graph ch9 Tree Terminology and characterization of Trees, Spanning Tree, Minimal Spanning Tree, Binary Trees, Tree Traversals, Isomorphism of trees.

1.  QnA 통하여 논의에 참여했던 내용에 자신도 참여했던 것 모두와 기타 자신이 제공한 유의미한 정보 또는 그것에 자신이 참여한 부분을 모두 아래에 정리하세요.

(1) 질문by이대희 2018.3.13   답변by prof.  2018.3.14 추가질문 by주경용 2018.3.16 추가답변by prof. 2018.3.17 . Final by 양승찬 2018.3.18

(질문)  Lecture2를 예습하면서

http://matrix.skku.ac.kr/2018-DM/Ch-2/

Example 1.11에서 X∩(Y-Z)=(X∩Y)-(X∩Z)

 Example  1.11 Given a direct proof of the following statement. For all sets ,  and , .

Another way:

(final)

(2)

질문 by장호 2018.3.18

답변 by함형빈2018.3.18

답변 by이대희2018.3.20

final by이대희2018.3.26

(질문)

(답변)

(추가답변)

(추가답변)

(추가답변)

(final by 이대희)

처음에는 질문자와 같게 생각했고 이에 대해 질문을 올리고나서 교수님의 답글을 보았습니다.

2번문제

2. Quiz 3 ) 3.1 번 문제 " 임의의 주어진 자연수 n 에 대하여  그 주어진 자연수 n 보다 큰 x  즉    x >n 되는  (즉 주어진  n 보다 큰 자연수 x는 언제나 존재합니다.)    <---  이도 분명합니다.

이런 의미입니다.

따라서 다른 의미입니다. 와 같은 것을 의미하지 않나요?

간단하게 축약한 군 더더기 없는 국제어인 수학식을 (구어식 약간은 풀어쓰면 말이 길어 지거나, 의미 전달이 불분명해 질 수 있는) 우리 말로 표현하는 과정에서  < "( for arbituraly chosen n,)  즉 임의의 주어진 자연수 n 에 대하여,  그 주어진 자연수 n 보다 큰 x  즉    x >n 되는  (즉 주어진  n 보다 큰 자연수 x는 언제나 존재합니다.) ​>  생긴 불분명한 우리말 표현의 미묘한 차이  때문에 이군이 잘못 이해한 것입니다.

그나저나 임의의 주어진  실수 k 에 대해 그보다 작은 정수 t 는 존재 합니다.

그러나 임의의 주어진  실수 k 에 대해 그보다 작은 양의 정수 t 는 존재하지 않을 수도 있습니다.

어순으로 인해 생긴 오해였으며 임의의 주어진 실수k에 대해 그보다 작은 양의 정수 t는 존재하지 않을수도 있기때문에 False가 맞습니다.

(3)

질문 by 이대희 2018.3.19, 2018.3.20

final by 이대희 2018.3.26

final ok by prof 2018.3.20

(답변)

(추가 질문)

(답변)

(final)

4<=k<n인 경우 성립한다고 가정할 때, K=n임을 보이면 strong math induction에 의해

증명이 가능한 예제였고 풀이 중 n-2<k가 아니라 n-2<n이어야 맞지 않는가라고 생각했지만

교수님의 explanation을 보고나서, K=n인 경우이므로 n-2<k인것을 이해하였습니다.

(summary)

1. Algorithms' charateristics

1)input 2)output

3) Definiteness 4)Effectiveness

5)Finiteness 6)Correctness

7)Generality

2.Examples of Algorithms

1)Linear Algorithm

 Algorithm  2.1 Linear Search Algorithm

2)Binary Search

 Algorithm 2.2 The Binary Search Algorithm procedure binary search ( : integer, , ,  : increasing integers)   { is left endpoint of search interval}   { is right endpoint of search interval}  while               if  then        else   if  then location   else location  return

3)Sorting+Insertion Sorting

 Algorithm  2.3 Insertion Sort procedure insertion sort(, , ,  : real numbers with ) for  to           while                      for  to                {, , ,  is in increasing order}

4)Time&Space for algorithms

-Best case time

-Worst case time

5)Randomized algorithms

 Algorithm  2.4 Shuffle  - skip procedure change(, ,  : values of denominations of coins, where   ;  : a positive integer) for   to        { counts the coins of denomination  used}     while        {add a coin of denomination }       { is the number of coins of denomination  in the change for }

3. Analysis for Algorithms

-Big oh function - upper bound

-Omega - lower bound

-Theta function -satisfy both(bound)

if, except for a constant factor and a finite number of exceptions,

is bounded above by .

is an asymptotic upper bound for .

if, except for a constant factor and a finite number of exceptions,

is bounded below by .

is an asymptotic lower bound for .

if, except for constant factors and a finite number of exceptions,

is bounded above and below by .

is an asymptotic tight bound for .

4. Recursive Algorithms

1)computing n Factorial

2)Robot walking& Fibonacci Sequence

(질문)

2018.03.30질문by 이대희

2018.03.30답변by 채영도

(답변)

(질문)

2018.04.06질문by 오정호

2018.04.06답변by 이대희(revised by prof.Lee)

(답변)

20180509 question by 김동준

20180511 answer by 이대희

20180511 question by 이대희

20180511 answer by prof.Lee

수업시간에 더욱 자세히 가르쳐 주셨는데, 결국 가격이 정해지고 그 가격으로 인하여 물건의 개수(수요)가 영향을 받게되는 것을 p_n=kq_(n+1)로 나타낸 것이었습니다.

20180511 question by 주경용

20180511 answer by 이대희(Final OK)

20180511 summary by 이대희

20180516 information about Ackermann's function by 이대희

20180515 question by 양승환

pdf ch7 에 있던 문제를 한번 바꿔보아서 풀어보았습니다. 쉬운 수로 풀어서인지 정말 간단하게 풀렸는데 질문이 있습니다. 그 때 잘 기억이 안나는데 an의 관계가 a(n-3)보다 더 가게 되어서 3차 이상인 식도 근을 구해서 똑같이 연립을 하면 되는건가요?

20180516 answer by 이대희

20180516 이대희

20180517 revised by 이대희

20180518 summary for Ch8(week 12)by 이대희

# Problem solving part

12. 1. Question of Ch1 Example 5.23

2018.03.21. Question by 정유민

2018.03.22. Solved by 이세영

Comment :

이 문제는 제가 이산수학 과목을 수강하게 되면서 한 첫 질문이었습니다. 혼자 공부하던 중 풀이를 봐도 잘 모르겠던 점이 있어 이를 질문했습니다. 구체적인 예를 가져왔다는 동료의 답변을 보면서 이를 해결 할 수 있었습니다.

2. Question of Chapter 1 Example 6.14

2018.03.21. Question by 정유민

2018.03.21. Solved by 이상구 교수님

2018.03.21. Finalized by 김민규

Question :

Finalize :

Comment :

진리표에 대한 사소한 내용이었지만, 이 단원에서 주된 내용이었던 진리표를 짚고 넘어감으로써 단원의 전반적인 내용을 이해하는 데에 수월했습니다.

3. Question of Quiz 4 – problem 1

2018.03.21. Question by 정유민

Comment :

제가 아는 내용을 적고, 물어볼 내용을 적는 방법으로 QnA를 활용했습니다.

4. Finalize of Chapter 3

– Remainder theorem and Composition

2018.03.27. Question by 왕짜오샹

2018.03.27. Solved by 이상구 교수님

2018.04.08. Finalized by 정유민

Comment :

question만 했던 지금까지와는 달리, 내용을 취합하고 나의 풀이를 덧붙임으로써 finalize를 하며 내용을 더 정확히 이해할 수 있었습니다.

5. problems about quiz 6-2

2018.04.04. Question by 김동준

2018.04.05. Solved by 정유민

Question :

Comment :

헷갈리는 개념인 reflexive, symmetric, transitive의 개념을 한꺼번에 정리해 개념을 확실히 했고, 이를 문제풀이를 통해 동료와 공유하며 공부했습니다.

6. chapter 4

- ex 3.3, 3.6, quiz 6-2(1)

2018.04.04. Question by 왕짜오샹

018.04.06. Solved by 정유민

Comment :

이 문제를 풀기 전에는 단원의 중요 내용인 Big oh notation을 정확히 어떤 식으로 써야할지 잘 이해하지 못했었습니다. 하지만 문제를 직접 접하고 풀어봄으로써 부등식에서 이 개념을 쓰는 방법을 알게 되었습니다.

7. Review of Chapter4

2018.04.05. Review by 정유민

Comment :

하나하나 배웠던 개념들은 어떻게보면 나무라고 할 수 있는데, 4장의 내용을 전체적으로 보면서 정리하다보니 숲을 볼 수 있었습니다.

8. Preview of Chapter 5

2018.04.06. Preview by 정유민

9. Proof of Chapter 5 theorem 1.7

2018.04.07. Proof by 정유민

Comment :

많은 친구들이 증명 내용을 올려주었지만, 어떻게 하면 쉽게 이해할 수 있을지 풀어내기 위해 고민했었던 시간이었습니다.

10. Chapter 4 Example 3.6

2018.04.07. Question by 김동준

2018.04.08. Solved by 이상구 교수님

2018.04.08. Finalized by 정유민

Comment :

앞의 big oh 문제에서도 언급했듯이, 동료의 질문을 통해 나 또한 정확하게 개념을 정립할 수 있었습니다.

11. Chapter 5.2 Number System

2018.04.07. Question by 김동준

2018.04.07. Solved by 정유민

2018.04.08. Finalized by 주경용

2018.04.09. Re-Finalized by 조경목

Re-Finalized :

13.

Comment :

김동준 학우의 질문을 통해서 공부를 함에 있어서 왜 배우는 지, 실생활에서는 어떻게 사용되는지를 생각하는 것은 중요함을 깨닫게 되었습니다. 또한 question, solve, finalize, re-finalize 와 같이 소통하며 의견을 나누는 활동이 특히나 보였던 문제로, QnA 게시판의 역할이 돋보였습니다.

1. preview of ch 6 (여기서부터 중간고사 이후부분)

2018.05.04. preview by 정유민

Comment :

본 수업에 들어가기 전에 경우의 수와 비둘기 집 원리에 대한 내용인 6장을 미리 예습 하여, 본 수업에서의 이해를 더욱 수월하게 할 수 있었습니다.

2. preview of ch 7

2018.05.11. preview by 정유민

Comment :

수업에 들어가기에 앞서 7장에는 특히 경제학 내용이 나와 있어서 더욱 흥미로웠습니다. 저는 수업에서 배운 내용이 실제로 적용되는 부분에 더욱 관심이 가는 편이라, 7단원에 더욱 빠져들 수 있었습니다.

3. summary of ch 7

2018.05.11. summary by 정유민

Comment :

어릴 적 가지고 놀았던 하노이 탑을 이제는 점화식으로 나타낼 수 있다는 점이 흥미로웠습니다. 그리고 경제학 거미집에 대해 관심이 생겨 더욱 찾아보는 공부를 했다(QnA에 답변했습니다). 게다가 처음 배우게 된 특성방정식은 새로운 형태의 점화식을 풀어내는 신기하고 유용한 방법이었습니다.

4. preview of ch 8

2018.05.25. preview by 정유민

Comment :

전에 배웠던 <수리적 사고>라는 과목에서도 나왔던 내용에 새로운 내용까지 추가해서 배우면서, 역시 수학은 따로따로가 아니라 결국은 하나라는 생각이 많이 들었습니다. 그리고 서로 다른 모양이지만 같은 그래프인 동형에 대해서도 흥미로웠습니다.

5. ch 7 – ex 2.10

Question :

2018.05.11. Question by 양승찬

2018.05.28. Solved by 정유민

Comment :

alternative way로 치환을 하는 방법을 설명해준 답변입니다. 저도 처음 배우는 내용이라 이해가 잘 되지 않았었는데, 이렇게 생각하니 이해가 수월했습니다. 그래서 이를 같은 부분을 어려워하는 동료와 나누었습니다. 게다가 교수님의 답변을 덧붙여서 더욱 정확도를 높였습니다.

6. ch 7 경제학 거미집

2018.05.11. Question by 이세영

2018,05.28. Solved by 정유민

문제에 답하기에 앞서, 경제학 거미집에 대해 조사를 해보았습니다.

이처럼, 책에서 제시된 수렴하는 형태의 경제학 거미집 뿐만 아니라 여러 형태의 그래프가 존재할 수 있습니다.

[출처] [경제학원론SE]022_5.2 거미집 이론|작성자 문과스텐

Question 1. 가격의 변동폭이 커지는 거미집일 경우에는, 실제 시장에서도 동일하게 적용되어 제품의 가격의 변동이 점점 커지는지 궁금합니다. (이로 인해 시장에 미치는 영향이 클 것이라고 생각됩니다.)

Answer 1. 가격의 변동폭에는 수요와 공급의 가격탄력성, 수요와 공급 곡선의 기울기가 영향을 미친다. 가격의 변동이 점점 커지는 지는 곡선의 개형에 따라 다를거라 생각합니다.

Question 2. 거미집 그림에서, 각 지점에서 지점으로 이동할 때, x축과 평행하게 또는 y축과 평행하게 거미집의 화살표가 이동하고 있습니다. 실제 가격도 그래프와 같이 일직선 상으로 변동되나요?

Answer 2. 이론적으로는 일직선 상으로 이동하는 것 같습니다. 하지만, 실제 시장에서는 매우 많은 변수가 작용하기 때문에, 단정짓기는 힘들지 않을까요?!

★★ 책에서 배우는 수학 지식이 실제 경제 시장에서 이용되고 접목되는 점이 매우 흥미로운 것 같아요!!

Comment :

평소 경제학에 관심이 많던 제겐 7단원 중에 특히 흥미로웠던 부분입니다. 그래서 더욱 관련 내용을 찾아보고, 조사한 자료를 바탕으로 이세영 학우의 수업 전 질문에 답을 하였습니다.

7. ch 7 – ex 2.8

Question : 2018.05.11. Question by 이상철

Answer : 2018,05.28. Solved by 정유민

Comment :

‘상계수 선형 동차/비동차 점화식’내용은 처음 접하는 내용이었습니다. 점화식의 형태를 통해 점화관계를 구분하는 개념을 배웠고, 이를 나누었습니다.

8. Finalize about recurrence relation

2018.05.11. Question by 양승환

2018.05.11. Solved by 이상구 교수님

2018,05.28. Finalize by 정유민

Question :

General method of solving linear homogeneous recurrence relation에서

왜  an을 t^2 로 a(n-1)를 t 로 바꾸는지 궁금합니다.

Finalize :

an=5a(n-1)-6a(n-2) 식을  an=tⁿ으로 치환하고  t^(n-2)로 나누면,

t²=5t-6  이 됩니다.

[교수님의 답변]을 덧붙이자면,

(t^n - 5 t^{n-1} + 6 t^{n-2})

= (t^{n-2}) (t^2 - 5 t^{1} + 6 t^{0})  = 0 을 푸는 것이 해가 같기 때문입니다.

그 뒤로는, 다음의 해법을 따라가면 된다.

출처: 이상구 교수님의 lecture note - Discrete Math chapter 7

Comment :

내가 쉽게 이해한 부분을 공유하고, 여기서 멈추는 것이 아니라 문제를 푸는 과정까지 첨부하여 질문한 학우가 이를 확실히 이해할 수 있도록 도왔습니다.

+)) 이 예시를 통해 쉽게 이해할 수 있었습니다.

9. Finalize about catalan number

2018.05.15. Solved by 이상철

2018.05.16. RE by 이혜정

2018,05.28. Finalize by 정유민

Question :

Given that C0 = C1 = 1 and C2 = 2. compute C3,C4, and C5 by using the recurrence relation  Example7.1.7.

Idea : Catalan Number

1. Catalan number C​n is the number of ways to reach from point (0,0) to point (n,n). However, even though the path can touch the diagonal line that connects (0,0) and (n,n), it must not go over the line.

2. Catalan number C​n ​can also be defined as the number of ways to divide a convex polygon with n + 2 sides into triangles, without the sides crossing each other. The picture below shows when n = 4

카탈랑 수는 다음 점화식을 만족한다.

C0 = C1 = 1, C2 = 2

Cn = sum _{k=1} ^{n}Ck-1Cn-k = C0Cn-1 + C1Cn-2 + C2Cn-3 + .....+Cn-1C0

∴C3 = C0C2 + C1C1 + C2C0

= 1*2 + 1+ 2*1 = 5

∴C4 = C0C3 + C1C2 + C2C1 + C3C0

= 1*5 + 1*2 + 2*1 + 5*1 = 14

∴C5 = C0C4 + C1C3 + C2C2 + C3C1 + C4C0

= 1*14 + 1*5 + 2*2 + 5*1 + 14*1 = 28 + 10 + 4 = 42

Comment :

다른 학우가 답변해준 내용을 모으고, 이에 덧붙여 문제를 풀이하여서 더욱 풍성한 finalize를 만들었습니다.

10. Finalize about ch 7.1.26

2018.05.15. Solved by 이상철

2018.05.16. RE by 이혜정

2018,05.28. Finalize by 정유민

Comment :

카탈랑 수에 대한 내용은 처음 배우는 거라 개념을 먼저 짚고 문제를 풀이하여 더욱 이해와 정리를 높였습니다.

# Coding part - chapter 7

1.

출처:DM-Ch-7-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-7-Lab.html

이렇게 긴 풀이를 coding을 이용하면,

<code>                            → <실행 결과>

from sympy import Function, rsolve

from sympy.abc import n

a = Function('a')

f = a(n) - 5*a(n-1) + 6*a(n-2)

rsolve(f, a(n), {a(0): 7, a(1):16})

2.

출처:DM-Ch-7-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-7-Lab.html

이렇게 긴 풀이를 coding을 이용하면,

<code>                            →  <실행 결과>

from sympy import Function, rsolve

from sympy.abc import n

d = Function('d')

f = d(n) - 3*d(n-1) + 2*d(n-2)

rsolve(f, d(n), {d(0): 200, d(1): 220})

3.

출처:DM-Ch-7-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-7-Lab.html

이렇게 긴 풀이를 coding을 이용하면,

<code>                            → <실행 결과>

from sympy import Function, rsolve

from sympy.abc import n

g = Function('g')

f = g(n) - g(n-1) - g(n-2)

rsolve(f, g(n), {g(1): 1, g(2): 1})

Part 1. Ch 7 Summarize

7.1 Introduction

점화식의 정의

점화식은 수열의 일반항을 한 개 이상의 앞선 항들을 이용하여 나타낸 식이다. 점화식과 함께 처음 몇 개의 항의 값이 주어지면 수열의 모든 항의 값을 구할 수 있다. 여기서 처음 몇 개의 항을 초기조건이라고 한다.

점화식의 여러 예시들

1. 피보나치 수열                          2. 멱집합의 원소의 개수

3. 하노이 탑 문제                       4. 수요와 공급 곡선

5. 아커만 함수

7.2 Solving recurrence relations

점화식의 풀이

1. Iteration (반복)

2. Linear homogeneous recurrence relation with constant coefficient (동차 선형 점화식)

1. Iteration (반복)

말 그대로 반복이다. 주어진 초기값 부터 시작해서 n의 값을 계속 증가시켜 보며 수의 규칙성을 확인, 이전 항과 다음항의 관계를 수식으로 만든다. 흔히 등차, 등비, 계차 등 이러한 규칙성을 볼 수 있다.

Iteration 예시들

(a)                                          (b) 하노이의 탑

2. Linear homogeneous recurrence relation with constant coefficient (동차 선형 점화식)

동차 선형 점화식은 위의 정의 와 같이 오른쪽 항이 an 의 이전항에 상수 c 가 곱해진 것들의 합으로만 이루어진 점화식이다.

그렇다면 Linear vs Non-linear / Homogeneous vs Non-homogeneous 의 차이를 알아보자

다음은 nonlinear recurrence relation 이다.

위의 보기와 같이 항들이 합으로 되어 있는 것이 아니라 곱으로 이루어져 있다.

다음은 nonhomogeneous recurrence relation 이다.

위의 보기와 같이 오른쪽 항이 0 이 아니다. homogeneous 일때는 항상 0 이어야 한다.

다음은 not a linear homogeneous recurrence relation with constant coefficients 이다.

위의 보기와 같이 an-1에 곱해져 있는 값이 상수가 아니다.

General method of solving

Linear homogeneous recurrence relation with constant coefficient

동차 선형 점화식 풀이 예시

이렇게 일반적인 풀이 방식이 있지만 다음과 같이 더 빠르고 간결하게 풀 수 있는 방법도 있다.

이러면 시간과 풀이를 줄이고 동차 선형 점화식을 빠르게 풀 수 있습니다.

그냥 보이면 잘 모르므로 예시를 첨부하겠습니다.

피보나치 수열을 간단한 동차 선형 점화식 풀이로 푸는 예시

이상으로 Ch 7 단원 summary 를 마치겠습니다.

Part 2. Ch 7 Problem Solving

Prolem solution 1

문제>>

Given that C0 = C1 = 1 and C2 = 2. compute C3,C4, and C5 by using the recurrence relation

Example7.1.7.

개념>> Catalan Number:

1. Catalan number Cn is the number of ways to reach from point (0,0) to point (n,n). However, even though the path can touch the diagonal line that connects (0,0) and (n,n), it must not go over the line.

2. Catalan number Cn can also be defined as the number of ways to divide a convex polygon with n + 2 sides into triangles, without the sides crossing each other. The picture below shows when n = 4

풀이>>

카탈랑 수는 다음 점화식을 만족한다.

C0=C1=1,C2=2

Cn = sum _{k=1} ^{n}Ck-1Cn-k = C0Cn-1 + C1Cn-2 + C2Cn-3 + .....+Cn-1C0

∴C3 = C0C2 + C1C1 + C2C0

= 1*2 + 1+ 2*1 = 5

∴C4 = C0C3 + C1C2 + C2C1 + C3C0

= 1*5 + 1*2 + 2*1 + 5*1 = 14

∴C5 = C0C4 + C1C3 + C2C2 + C3C1 + C4C0

= 1*14 + 1*5 + 2*2 + 5*1 + 14*1 = 28 + 10 + 4 = 42

Problem solution 2

Ch 7.1 ex 26

문제>>

Show that the Catalan numbers are given by the recurrence relation.

(n+2)Cn+1 + (4n+2)Cn, n≥0, and initial condition C0 = 1.

개념>>

풀이에 들어가기에 앞서, the Catalan number에 대한 개념을 짚고 가자.

음이 아닌 정수 n에 대해서, n 번째 카탈란 수 는 다음과 같다.

풀이>>

(n+2)Cn+1 = (4n+2)Cn (n≥0) 위 식을 정리하면,

(n+1)Cn = (4n-2)Cn-1 식이 된다.

위에서 설명한 카탈란 수의 꼴로 만들기 위해

Cn/Cn-1 = 4n-2/n+1 = 2(2n-1)/n+1 꼴을 만든다.

Cn/Cn-1 * Cn-1/Cn-2 * Cn-2/Cn-3 *.....*C1/C0

= 2(2n-1)/n+1 * 2(2(2n-1)-1)/n * 2(2(n-2)-1)/n-1 *....* 2(1)/1

= 2^n/(n+1)! * (2n-1)(2n-3)......(2n-(2k-1)).....(3)(1)

[밑줄 친 부분이 2n-(홀수)들의 곱]

= {2n(2n-1)(2n-2).....(2)(1)}/{2n(2n-2)(2n-4).....(2)}

= (2n)!/(2^n * n!)

최종적으로 남은 식을 정리해보면,

Cn/C0 = 2^n/(n+1)! * (2n)!/(2^n * n!)

= (2n)!/{n!*(n+1)!}

C0=1인 초기조건에 따라, Cn = (2n)!/{n!*(n+1)!}

Problem solution 3

Ch 7.2 ex 37 다음 점화 관계를 풀어라

임이 주어졌다.

에서

부분이 임을 알수 있으므로,

n>2일 때 C_n=2*C_(n-1) 임을 알수 있다.

이는 선형 점화식이므고, 특성 방정식의 해가 2이므로 t*2^n 승의 일반항을 가짐을 알 수 있다.

를 대입해보면

임을 알 수 있다.

Problem solution 4

문제. 다음 점화 관계를 풀어라

an = -2n an-1 + 3n(n-1) an-2  , a0 = 1, a1 = 2

Solution

bn=an / n! 이라고 하자

문제의 식 an = -2n an-1 + 3n(n-1) an-2 에서 양변을 n!로 나누면

an / n! = -2n an-1 / n! + 3n(n-1) an-2 / n!

= -2 an-1 / (n-1)! + 3 an-2 / (n-2)!

따라서 bn = -2 bn-1 + 3 bn-1

=> bn - bn-1 + 3bn-1 - 3bn-2 = 0

=> bn - bn-1 = -3 (bn-1 - bn-2) =>수열 {bn-bn-1}은 공비가 -3이고 첫째항이 b1-b0 인 등비수

∴ bn-bn-1 = (-3)n-1(b1-b0)

b1-b0 = a1-a0 = 2 -1 = 1

bn-bn-1 = (-3)n-1 , bn = bn-1 + (-3)n-1

bn = bn-1 + (-3)n-1

bn-1 = bn-2 + (-3)n-2

…

…

b2 = b1 + (-3)1

+ b1 = b0 + (-3)0

=> bn = b0 + (-3)0 + (-3)1 + (-3)2 + … + (-3)n-2 + (-3)n-1

= 1 + {5-(-3)n}/4 = an / n!

∴ an = {n! / 4}*{5-(-3)n

Problem solution 5

문제. 다음 점화 관계를 풀어라. (초기값 없음.)

Solution

## a​n ​= p * 4​n ​+ k * 2​n​ + 1 이 된다.

Problem solution 6

문제. 다음 점화 관계를 풀어라. (초기값 없음.)

## a​n​ = k * 2​n​ + p * 5​n​ + 13 + 4n 이 된다.

Problem solution 7

문제. 다음 점화 관계를 풀어라. (초기값 없음.)

## 은 위의 치환 관계를 따라가면 된다.

1.  김동준

(1) 질문

1.

답변)

note: 혼동하고 있는 개념에 대해 질문을 하고, 제가 문제를 잘못 이해해서 벌어진 일이라는 것을 알았습니다

2.

3.

5.

답변

6.

7.

답변

8.

답변

9.

10.

11.

답변

12.

답변

13.

답변

14.

15.

답변

15.

16.

코멘트

17.

유용한 사이트

18.

19. summary

20.

21.

PBL 참여 부분

14.
 유형 Q & A 제목 Ch1. ex 2.5, 예습 중 질문 참여자 questioned by 김민규, finalized by SGLee 질문 복습은 큰 문제 없이 진행하였습니다만, 예습과정에서 확신이 없는 부분이 있어 질문드립니다.   증명 과정 중 2번째 줄에 확신이 없습니다. 단지 positive integer n을 0 이라고 가정만 해서 저런 증명이 나온 것인지 궁금합니다. 답변 Dear 김민규군, Example2-2-5, answer,  답   증명 과정 중 2번째 줄 ? 단지 positive integer n, m 에 대한 얘기이므로     2 m^2  <=  40   이므로    m^2  <=  20   임은 당연하고,  positive integer m  에 대하여   m <= 4  임은 당연한 것인데 ...   그럼  모두 이해가 될 것 같습니다.
 유형 Q & A 제목 Q & Comments on ch1 and ch2 (1 of 3) 참여자 questioned by 김민규, finalized by SGLee 질문 ex1.6.9의 설명은 이해했습니다만, 제가 의문이 있는 예제는 다음 예제 입니다. 저는 이 문제를 모든 y에 대하여 x >=y를 만족하는 어떠한 x가 있느냐 라고 이해했습니다. 그리고 Domain of discourse가 set of positive integer이기에 x와 y가 가질 수 있는 값은 양의 무한이라고 생각했습니다. 그렇기에 y가 굉장히 큰 수라고 해도 y보다 큰 어떤 x가 존재 할거 라는 제 논리로 저는 True라고 생각하는데 제 논리에서 어떠한 오류가 있는지 궁금합니다. 답변 저는 이 문제를 모든 y에 대하여  x >=y 를 만족하는 어떠한 x가 (언제나) 있느냐 라고 이해했습니다.   <---  OK   그리고 Domain of discourse가 set of positive integer이기에 x와 y가 가질 수 있는 값은 양의 무한이라고 생각했습니다. 그렇기에 y가 굉장히 큰 수라고 해도 y보다 큰 어떤 x가 존재 할거   라는 제 논리로 저는 True라고 생각하는데 제 논리에서 어떠한 오류가 있는지 궁금합니다.     <---  Your logic is OK so far^^  Good!

 유형 Q & A 제목 Q & Comments on ch1 and ch2 (2 of 3) 참여자 questioned by 김민규, finalized by SGLee 질문 다음 질문입니다. ch1 교안 제일 마지막 페이지(53p)에 있는 예제입니다. 2번에 대한 질문입니다. 바로 직전 질문과도 연관이 되어있는 것 같은데요.  solution의 풀이말고 ex1.6.10에 의해 x
 유형 정보 제공 제목 Q & Comments on ch1 and ch2 (3 of 3) 참여자 questioned by 김민규, finalized by SGLee 내용 ch2는 다양한 증명 방법과 수학적귀납법에 대해서 배우는 파트입니다.   귀납법에 대한 내용 중 저에게 생소한 개념이었던 Well-Ordering Property에 대한 적절한 한국어 설명과 좋은 적용 예시가 있기에 첨부합니다.   Well-Ordering Property : S는 자연수(N)의 부분집합이고, 공집합이 아니라고 하면, S의 어떤 원소인 m이 항상 존재하는데, 어떤 m이냐면, S의 모든 원소 s에 대하여 m<=s을 만족하는 그런 m이 존재한다.   즉 최소항이 존재한다는 뜻입니다.     예시:가 무리수임을 증명하여라   가 무리수임을 증명하여라 가 무리수임을 증명하여라   제 글은 여기까지입니다. 감사합니다.
 유형 Q & A 제목 ch1, ex1.6.10 : second question. 참여자 questioned by 김민규, answered by SGLee, finalized by 김민규 질문 정확한 이해가 안되어 두번째 질문 드립니다.   예제의 답은 False인데 저는 위와 같은 이유로 True라고 생각했습니다.   그런데 교수님께서 제 논리가 OK라고 하셔서 정답이 T인지 F인지 혼란이 옵니다.   아시는 분 있으면 답변 부탁드립니다.   감사합니다. 답변 Dear Mr. 김,  Do finalize this  ch1, ex1.6.10 : second question.​   김민규  군이 물어 본 문제를 스마트 폰에서 답을 주다보니 수식이 제대로 안보여 내가 준 답을 김 군이 다르게 이해 했나보는 군요^^   A. 이 문제가 True 이려면 말 그대로 임의의 (즉 모든) 양의 정수  y 보다 큰 ( x >=y  인) 를 ' 어떤' (특정한) x값이 존재해야 한다.    그러나   y  는 그런 x 는 존재하지 않는다    즉, ex1, ex2 처럼 임의의 y값에 따라 x값이 변하면 안된다. 그러므로 만약 특정한 x=1100이면 1100보다 큰 y값은 존재하므로 false. 또, 만약 특정한 x=20000이면 20000보다 큰 y값은 존재하므로 false. 즉 양의 정수 y의 범위가 양의 무한대 이므로, 항상 특정한 x 보다 큰 y가 존재. 그러므로 답은 false. ******* Q.  모든  양의 정수 y 에 대하여 x >=y  를 만족하는 양의 정수  x 가 존재하느냐?    A. (False)  Proof 증명 : 이를 보이기 위하여 모순을  이용한 증명을 하면   만일 그런 x  가 존재한다면  y = x+1  이란 y 를 잡으면 그 y 보다는 x 가 클 수 가없으므로  모순이다.  즉, 임의의 (즉 모든) 양의 정수  y 보다 큰 ( x >=y  인) ' 어떤' (특정한) x 값 은  존재하지 않는다.  따라서 False 이다.  QED.

유형

정보 제공

제목

ch2 proof by contradiction : a typing error

참여자

김민규

내용

위의 표는 ch2 교안에 수록되어있는 진리표입니다.

The propositions

and      Using proof by contradiction

are equivalent.

Using a truth table: The equivalence relation is

4행 6열의 T가 오타이며 F로 정정해야 한다고 생각합니다.

r이면서 not r인 경우는 없기 때문입니다.

 유형 정보 제공 제목 Prof's Addition : difference answering/finalizing 참여자 김민규 내용 Prof's Addition : difference answering/finalizing​ professor's Answer : difference answering/finalizing​ professor's Answer : difference between answering a question and finalizing​   Q&A에 해당 내용을 게시하라는 교수님의 요청에 글 남깁니다. 1. The First  질문  하는 학생 이름 2. The First ​ 그 질문에 첫 코멘트나 답을 주는 학생 이름  3.   ...  그 질문과  best 정답을 구해 하는 토론 과정 ... ***********************                                                                        2016.3.8 Revised by 오충헌 2016.3.10. Finalized by 권의회 2016.3.10. ReFinalized by 박종우 2016.3.10. Final OK by SGLee   [Sample] Ch-1-Prob-8-ReFinal-권의회 (New) (page 48) LA Chapter 1 Exercises Find a vector equation of the line between the two points  ...?? and  ... . Sol. Let  ...  be the vector through the points   ...  be the parallel to vector   ...  that is particular point in   ...   (also   ...  could be changed any point in   ...  . Checked by Sage. var('x,y,z,h') var('t') P = vector([5,0,1,0]) Q = vector([0,2,6,5]) R= Q-P print "vector equation= ", P+R*t vector equation= (-5*t + 5, 2*t, 5*t + 1, 5*t) =>  OK ■ http://math3.skku.ac.kr/home/pub/163   Note : 두 점이 주어질 때 그 두점을 지나는 vector equation을 구하는 문제이다. 각 점을   ...  와  ...   라 할 때,   ...  임을 이용하여 문제를 해결하였다. 다른   ...  에서도 위와 같이 문제를 해결할 수 있을 것이다. 4. The Best  토론을 거쳐 질문과 답을 이해 한 학생이 질문과 답을 읽기 좋게 정리하여 (​ 질문과 답을 일목요연하게 정리하여 게시.​)  final  선언 하는 것,   그 학생의 이름  5.  ​ The Best​  : 위의 학생이 Final  한 답을 다른 학생이 보고, 자신이 이해하기 더 좋게 더 이쁘게 6.  교수님 혹은 조교님이 검토 후 문제없다면 제목에 Final OK 선언. 7. (이 과정이 끝나면 질문한 학생, 답을한 학생, final선언 학생은 보고서에 해당 글을 실을 수 있음.
 유형 Q & A 제목 2-5 strong induction EX5.1 참여자 questioned by 김태현, Answered by 윤소정, finalized by 김민규 질문 n-2=2a+5b가 성립함을 보임으로써 n에 대해서도 성립함을 보였는데 n-5으로부터 n으로 유도하는것은 안보여도 되는것인지 질문드립니다. 또 만약에 안보여도 되는것이라면 n-2에서 n으로 유도하지말고 n-5에서 n으로는 어떻게 유도하는지 질문드립니다. 답변 이대희 군, 맞게 이해하였습니다.  (Your logic is right)  n-2<  n= k ? More Explanatio Ind, 가설에 의하여  ( Assume true for any    ( 4 <=  )   k   < n  인 경우 즉,     n 보다 작은  모든 k 에 대하여  k=2a' + 5b'  인 a' 과 b' 가 존재한다.      [Show true  for  n=k  ]     (즉   n보다 작은 n-2가 ind hyp에 의해 n-2=2a+5b  인 a 과 b 가 존재하므로 k=n 일때  만 보이면 된다.  )    n=k   인 경우  =>   4 <= n-2   < n=k          =>  n보다 작은 n-2가 ind hyp에 의해 n-2=2a+5b  인 a 과 b 가 존재하므로          =>  n=2a+2+5b = 2(a+1) + 5b 인 a 과 b 가 존재하므로            즉, 주어진 statement 는   n일때도     성립한     따라서   It has been proved , by Strong Math Induction.         이렇게 쓰시면 될 듯합니다.
 유형 Q & A 제목 2-5 strong induction EX5.1 (cont) 참여자 questioned by 김태현, Answered by 윤소정, finalized by 김민규 답변 Q1. 풀이는 n-2로 가정하여 문제를 풀었는데, n-5일 경우는 생각하지 않아도 되는가? Q2. n-2로 풀지말고 n-5로 풀 수도 있는가? A1. 풀이에서 n-2 = 2a + 5b 일 경우 n역시 이를 성립함을 보였고 Basic step에서 n=4, 5 일 때 성립함을 보였으므로 (모든 경우의 수에 대한 것을 해결했으으로) 이미 문제에서 주어진 조건을 만족하기 때문에 가정이 완료되어 n-5를 이용한 별도의 증명은 필요없다고 생각. 즉 모든 범위에서 만족함을 보였기 때문에 추가로 n-5로 다시 풀어야 할 필요가 없다. A2.
 유형 Q & A 제목 예제 1.6.14 참여자 questioned by 정유민, Answered by SGLee, finalized by 김민규 질문 The question is :   Write the negative of ∃x∀y(xy<1), where the domain of discourse is R×R . In the solution of this question, Determine the truth value of the given statement and its negation.   Using the generalized De Morgan’s laws for logic, we find that the negative is ￢(∃x∀y(xy<1))≡∀x￢(∀y(xy<1))≡∀x∃y￢(xy<1)≡∀x∃y(xy≥1)   The given statement ∃x∀y(xy<1) is true.   ∵ There is at least one x (namely x =0 ) such that xy<1 for every y .   Since the given statement is true, its negation is false.​   I can't understand the final sentence. Why 'Since the given statement is true, its negation is false.'? 답변 by the definition 2.9 in ch1.2(Propositions),  ​ The negation of truth statement is False and the the negation of false statement is True. ​ Therefore, you can understand​. ​
 유형 Q & A 제목 Quiz4 problem1 참여자 questioned by 정유민, Answered by SGLee, finalized by 김민규 질문 Q. quiz 4의 솔루션을 참고해보면, 명제의 the first implication 뿐만 아니라 the converse implication 과정까지도 따진다. 왜 ​the converse implication 를 따져야하는가? 답변 ch1 중 biconditional proposition (등치명제) 부분 Truth table입니다.   오른쪽 테이블 3열과 6열이 동일하므로, 등치명제를 증명하는 것은,  the first implication​ & the converse implication​를 통해 증명하는 것과 같음을 알 수 있습니다.
 유형 Q & A 제목 ch4, ex3.8 omega, theta, big O 표기법 정의 참여자 questioned by 김동준, Answered by SGLee, finalized by 김민규 질문 Q. omega, theta, big O 표기법의 정의를 몰라 문제 및 증명의 이해가 어렵다. 답변 A.  먼저 세 가지 notation에 대한 정의를 알아야 합니다.   그리고 이 문제를 증명하려면 정의 3.2 의 마지막 줄   을 만족함을 보여주면 됩니다.   이에 대한 적당한 양의 상수(C_1=1, C_2=1/4)가 있음을 보였으므로 증명이 완료됩니다.     ch4, ex3.8  in  http://matrix.skku.ac.kr/2018-DM/Ch-4/
 유형 Q & A 제목 ch4, ex3.8 omega, theta, big O 표기법 정의 (cont) 참여자 questioned by 김동준, Answered by SGLee, finalized by 김민규 답변 ch4, ex3.8  in  http://matrix.skku.ac.kr/2018-DM/Ch-4/
 유형 Q & A 제목 Direct proof of 'If n^2 is even n is even' 참여자 questioned by 김동준, Answered by SGLee, finalized by 김민규 질문 Q. Direct proof of 'If n^2 is even n is even' 답변 A. ​ n^2 is even n is even​을 증명하는 방법은 다양하다.  그 중에서 짧고 명확한 것이 귀류법이기에 귀류법이 많이 쓰이며, 다른 것은 선호하지 않는다. *그렇지만 같은 고민을 가지고 있는 질문에 대한 답변이 있기에 첨부합니다. Direct proof :   Q.
 유형 Q & A 제목 Direct proof of 'If n^2 is even n is even' (Cont) 참여자 questioned by 김동준, Answered by SGLee, finalized by 김민규 답변
 유형 Q & A 제목 Quiz4, problem3 참여자 questioned by 이금택, Answered by 주경용, finalized by 김민규 질문 Q. 답변 A. *proof by contradiction :   In this case, (유리수의 경우) the conclusion is 'There exists no smallest positive rational number.' ( =q)   1. so,  (유리수의 경우) Suppoose that  which    means    is ​'There exists a smallest positive rational number.' ​   2. if we assume that 'k' is the smallest positive rational number,   3. there is another positive rational number('k/2') that is smaller than 'k'                                  (k / 2   <    k ) 4.  It   occurs is a counterexample and contradiction  to (our assumtion 'k' is the smallest positive rational number, ). ​   So the proposition(q) proves to be true from the proof by contradiction​.
 유형 Comment 제목 4장 pseudocode 참여자 Commented by 김민규, Answered by 함형빈 질문 for, if, return 같은 용어가 생소해서 4장 전반적으로 이해가 어렵습니다. 답변 일단 for, if, return을 이해하기 위해서 조건문과 반복문에 대해서 알아보겠습니다.  조건문은 말 그대로 특정 조건에 만족될 때 수행되는 문법이다. 이는 우리가 일반적으로 알고 있는 C언어의 if-else 문, switch문과 동일하다. ​ ​ ​물론 python과 같은 언어는 들여쓰기를 하지 않아도 됨니다. 두번째로 반복문이라면 보통 while loop과 for loop이 있는데, for loop에 관한 것이 더욱 궁금한 것 같아 for만 알려드리겠습니다. ​  이처럼 코드 용어는 예시를 보면서 그것이 어떻게 돌아가는지를 확인한다면 이해를 하기 쉬울 것입니다. 조금이라도 도움이 되었으면 좋겠습니다.
 유형 Comment 제목 Ch4. Comment 참여자 김민규 내용 Big oh, omega, theta를 이용해 어떤 한 연산의 reiteration 상한과 하한을 가늠해 볼 수 있다.   ​     그러므로 연산이 완료 되는데 까지 걸리는 시간을 예측해 볼 수 있다.
 유형 정보 제공 제목 typing error Ch4 ex3.3 참여자 김민규 내용 C_1이 22가 되면 n=1일 때 식이 성립하지 않습니다.   3n^5+n^5+17n^5+n^5 이 부분을   3n^5+n^5+17n^5+2n^5으로 바꾸고 C_1 = 23이 되어야 한다고 생각합니다
 유형 Comment 제목 Ch5. Preview 참여자 김민규 내용 5장은 중 고등학교 때 배운 몫과 나머지, 최대공약수, 최소공배수, 소인수분해에 대해 먼저 배우고 진수 변환과 같은 알고리즘, 그리고 유클리드 알고리즘에 대해서 배운다. 그리고 정수론은 이용한 암호시스템에 대하여 학습한다.
 유형 Q & A 제목 ch2. well-ordering property 참여자 questioned by 염승재, Answered by 주경용, 김지만, finalized by 김민규 질문 Q.집합 X가 공집합이 아니라는 것을 보이는 과정의 이해가 어렵다. 답변 우선 몫-나머지 정리에서 d, n은 정수이고 d>0   이 문제에서 정수 n이 1) n>=0, 2) n<0   이 두 범위에서 각각 nonempty라는 것을 보여주면 모든 n의 경우에 대해 증명이 완료.   1) n>=0의 경우에서 k가 0일 경우, n-dx0>=0이므로 n이 X의 원소. ( nonempty라는 것을 보이려면 단 하나의 원소만 보여주면 되므로) 2) n<0일 경우도 위의 증명처럼 따라가면 n-nd>=0( 해설 상에서는 n을 나눈 1-d <=0 ) 이 얻어지는데(문제의 해설, 위의 집합에서 n=k일 때의 원소.) 그러므로 X는 nonempty임.     결국 모든 정수 n의 경우에 X가 nonempty임을 보임.
 유형 Q & A 제목 ch3 sequence, ex2.7, ex2.8 참여자 questioned by 염승재, Answered by 윤소정, finalized by 김민규 질문 Q.2.7 답은 increasing이고 2.8 답은 decreasing 아닌가? 답변 A. increasing은 >, nondecreasing 은 >= decreasing은 <, nonincreasing 은 <= 의 기호로 나타낼 수 있음     그러므로 위의 정의에 따라 2.7의 경우에선 increasing &nondecreasing 둘 다 답이 될 수 있고, 2.8의 경우에선 decreasing& nonincreasing​ 둘 다 답이 될 수 있음.
 유형 Comment 제목 간단 시험후기 & ch6 comment. 순열, 조합, 확률과 통계 참여자 김민규 내용 시험후기:    교수님께서 강조하신 부분, 그리고 QnA에서 활발하게 논의가 되어졌던 내용이 시험문제의 주를 이루었습니다. 전형적인 암기 문제나, 지엽적인 개념을 묻는 형식의 시험이 아니라, 수강생들이 이산수학의 기초 중 핵심적인 개념의 맥을 잘 짚고 있는가?, 그리고 주도적으로 공부를 했는가?를 물어보는 시험이었다고 생각합니다.    전형적인 시험형식에서 벗어나 흥미로운 형식의 시험이었고, 개인적으로 이번 학기 중 이산수학 만큼은 꽤나 주도적으로 공부했다고 생각하기에 만족스러운 시험이었습니다.     Ch6 comment:    고등학교 순열, 조합, 확률과 통계 과정과 내용적으로 큰 교집합을 이루고 있습니다.     많은 예제를 통해 쉽게 이해를 유도하고, 올려주신 Lab을 통해 직접 예제를 다룰 수 있기에 다행히도 전반적인 이해에 있어서 큰 어려움은 없을 것 같습니다.
 유형 Comment 제목 Online 참석 참여자 김민규 내용 챕터6 코멘트는 어제 작성했기에 생략합니다.
 유형 Q & A 제목 example 6.6.21 참여자 questioned by 이세영, Answered by SGLee, finalized by 김민규 질문 1번 수식   ------ 2번 수식 두 수식 간의 연관성. 답변 A.
 유형 Q & A 제목 example 6.6.21 (cont) 참여자 questioned by 이세영, Answered by SGLee, finalized by 김민규 답변
 유형 Pro.Solving 제목 exercises 6.6 #22~#26 Answer (1 of 5) 참여자 김민규 질문 답변
 유형 Pro.Solving 제목 exercises 6.6 #22~#26 Answer (2 of 5) 참여자 김민규 질문 답변
 유형 Pro.Solving 제목 exercises 6.6 #22~#26 Answer (3 of 5) 참여자 김민규 질문 답변
 유형 Pro.Solving 제목 exercises 6.6 #22~#26 Answer (4 of 5) 참여자 김민규 질문 답변
 유형 Pro.Solving 제목 exercises 6.6 #22~#26 Answer (5 of 5) 참여자 김민규 질문 답변
 유형 Q & A 제목 6-1, example 1.13 참여자 questioned by 염승재, Answered by SGLee, finalized by 김민규 질문 Q.   I can't understand passages written in green. 답변 A.   There are six members, and three offices.   First, Alice can choose one of the three.   Then, there are five members remain, and two offices remain.   Now, It doesn't matter who takes the office.   So, another office can be chosen by five people.   and then, the other office can be chosen by four people.   Therefor, the number of selection in which Alice is an officer is 3*5*4 = 60.
 유형 정보 제공 제목 Catalan Numbers and Grouping with Parenthesis. 참여자 김민규 내용 This example and SGLee's example are almost the same. I understand everything except the last part.​ For ease to use, I upload pdf file as well.
 유형 Preview 제목 Ch6, t개 주머니 k개 공 example 참여자 김민규 질문 t개 주머니 k개 공 example 식의 유도 과정이 궁금합니다. 답변
 유형 pro.solving 제목 6.7 ex Problem 3 and 6 and 22 (1 of 3) 참여자 solved by 주경용, revised by 김민규 질문 Q. 다음에 주어진 각 식이 전개되었을 때 앞에 주어진 항의 계수를 구하라.    #3  (x^4 y^7  ,〖(x+y)〗^11) 답변 #3  이항정리 C(n,k)a​n-k​b​k​ ​를 이용하면 됩니다. 따라서 C(11,7)x​11-7​y​7 ​이므로 C(11,7)은 11!/4!7! = 330
 유형 pro.solving 제목 6.7 ex Problem 3 and 6 and 22 (2 of 3) 참여자 solved by 주경용, revised by 김민규 질문 Q. 다음에 주어진 각 식이 전개되었을 때 앞에 주어진 항의 계수를 구하라.   #6 (w^2 x^3 y^2 z^5  ,〖(2w+x+3y+z)〗^12) 답변 #6 역시 이항정리를 이용하면 됩니다. 따라서 12개 항에서 (2w)​2​(x)​3​(3y)​2​(z)​5​ 이므로 C(12,2)C(10,3)C(7,2)C(5,5) 를 계산하면 됩니다. 12!/10!2! X 10!/7!3! X 7!/5!2! X 1 = 166,320인데 w​2​ 계수 4, ​y​2​ 계수 9를 곱하면 최종 답은 5,987,520
 유형 pro.solving 제목 6.7 ex Problem 3 and 6 and 22 (3 of 3) 참여자 solved by 주경용, revised by 김민규 질문 #22 이항정리를 이용하여 다음을 보이라. (∑_(k=0)^n▒〖2^k C(n,k)〗=3^n)   (* 워드를 이용해 문제 수식을 직접 만들었으나 이미지로만 붙여넣기가 가능해 이미지로 첨부합니다.) 답변 #22 3​n​을 (1+2)​n​으로 두면 쉽게 풀립니다. (1+2)​n​ =  ∑ C(n,k) 1​n-k​2​k​ =    ∑2​k​C(n,k) 가 됩니다.​​
 유형 pro.solving 제목 Sec 6.8, ex problem 4 and 7 (1 of 2) 참여자 solved by 주경용, revised by 김민규 질문 #4     한 반의 35명의 학생 중에서 적어도 두 사람은 이름이 같은 영어 철자로 시작한다는 것을 증명하라.      Prove that among 35 students in a class, at least two have first names that start with the same letter. 답변 #4    ABCDEFGHIJKLMNOPQRSTUVWXYZ = 알파벳 총 개수 = 26개   한 반의 35명을 pigeon 이라고 하자. 그러면 알파벳(영어)철자 26개는 pigeonhole 이 된다.   따라서 첫 번째 원리에 입각해보면 비둘기(사람)의 수가 더 많기 때문에   당연히 적어도 두 사람은 이름이 같은 영어 철자로 시작할 것이다.     [ ABCDEFGHIJKLMNOPQRSTUVWXYZ = Total number of alphabets = 26 Let's say 35 people in a class are pigeons. Then the 26 alphabetic (English) spellings become pigeonhole.   So, based on the first principle, at least two people will have the same english spelling, because there are more pigeons (people) than the pigeonhole. ]
 유형 pro.solving 제목 Sec 6.8, ex problem 4 and 7 (2 of 2) 참여자 solved by 주경용, revised by 김민규 질문 #7    13명의 이름이 데니스, 에비타, 페르디난드이고, 성은 오, 피에트로, 김, 로스텐코프스키이다. 최소한 두 사람은 서로 같은 성과 이름을 가지고 있다는 것을 보이라.    Thirteen persons have first names Dennis, Evita and Ferdinand and last names Oh, Pietro, Kim and Rostenkowski. Show that at least two persons have the first and last names. 답변 #7   이름 = 데니스, 에비타, 페르디난드 = 3가지   ​   성  =  오, 피에트로, 김, 로스텐코프스키 = 4가지     성함 = 총 3x4 = 12가지      사람을 pigeon으로 본다면 총 13명인데 성함인 pigeonhole이 12가지 이므로    첫 번째 원리에 입각해보면 사람이 더 많기 때문에 최소한 두 사람은 서로 같은    성과 이름을 가질 것이다.​     [ First name = Denise, Evita, Ferdinand = 3 things Last name = Oh, Pietro, Kim, Rostenkovsky = 4 things Full Name = Total 3x4 = 12   If you look at a person as a pigeon, there are a total of 13 people. Since there are 12 pigeonholes, at least two people will have the same first and last names because there are more people based on the first principle. ]﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿
 유형 Pro.solving 제목 Ch 6 self-Test solution (1 of 7) 참여자 solved by 양승찬, revised by 김민규 질문 #1. How many eight-bit strings begin with 0 and end with 101? 답변 Dear 양승찬, I revised some problems (#6, #8, #12)   And I think It is now complete.   sol) What we can choose among 8 bit strings is the rest 4bits.   And Each 4 bits can be 0 or 1. So the count is 2*2*2*2 = 16
 유형 Pro.solving 제목 Ch 6 self-Test solution (2 of 7) 참여자 solved by 양승찬, revised by 김민규 질문 #4. A seven-Person committee composed of Greg, Hwang, Issac, Jasmine, Kirk, Lynn, and Manuel is to select a chairperson, vice-chairperson, social events chairperson, secretary, and treasurer. How many ways can the officers be chosen if either Greg is secretary or he is not an officer? 답변 sol) the committee is composed of 7 persons. and the officers are 5. because of the condition of this problem, there can be 2 cases.     1) Greg is secretary   Then 6 persons should choose 4 officers. So it equals to Permutation(6, 4)   = P(6,4)   2) Greg is not officer   Then 6 persons should choose 5 officers. So it equals to Permutation(6, 5)   = P(6,5)     So the Sum of these are answer = 1080
 유형 Pro.solving 제목 Ch 6 self-Test solution (3 of 7) 참여자 solved by 양승찬, revised by 김민규 질문 #6 How many strings can be formed by ordering the letters ABCDEF, if A appears before C and E appears before C? 답변 sol) ​We construct the strings by a three-step process.   First, we choose positions for A, C, and E [C(6, 3) ways]. Next, we place A, C, and E in these positions. We can place C one way (last), and we can place A and E two ways (AE or EA). Finally, we place the remaining three letters (3! ways). Therefore, the total number of strings is C(6, 3) · 2 · 3!.
 유형 Pro.solving 제목 Ch 6 self-Test solution (4 of 7) 참여자 solved by 양승찬, revised by 김민규 질문 #8 A shipment of 100 compact discs contains five defective discs. In how many ways can we select a set of four compact discs that contains more defective than nondefective discs? 답변 sol)  case 1 : 3 defective discs, 1 normal disc.   case 2 : 4 defective discs, 0 normal disc.   We must select either three or four defective discs. Thus the  total number of selections is C(5, 3)C(95, 1) + C(5, 4).
 유형 Pro.solving 제목 Ch 6 self-Test solution (5 of 7) 참여자 solved by 양승찬, revised by 김민규 질문 #11 In how many ways can 12 distinct books be divided among four students if each student gets three books? 답변 sol) C(12,3)*C(9,3)*C(6,3)*C(3,3)    = 369600
 유형 Pro.solving 제목 Ch 6 self-Test solution (6 of 7) 참여자 solved by 양승찬, revised by 김민규 질문 #12 How many integer solutions of  x1+x2+x3+x4=17   satisfy x1 >=0, x2>=1, x3>=2, x4>=3 답변 sol) let x2'=x2-1. x3'=x3-2, x4'=x4-3   then the equation equals to x1 + x2' + x3' + x4' =11   and each values are equal or bigger than 0. So the number of integer solutions are   4H11 = C(14,4) -> Incorrect   4H11 = C(14,11) = C(11,3) -> Correct
 유형 Pro.solving 제목 Ch 6 self-Test solution (7 of 7) 참여자 solved by 양승찬, revised by 김민규 질문 #26 Find the coefficient of x^3 y z^4 in the equation of (2x + y + z)^8 답변 sol)  2^3*C(8,3)*C(5,1)*C(4,4)
 유형 preview 제목 Ch7 comment 참여자 김민규 내용 고교 때 배운 점화식의 개념을 좀 더 체계적이고 수학적으로 접근하는 것 같습니다. 실생활의 사례를 예제로 들어 이해가 쉽고 흥미롭게 배울 수 있을 것 같습니다.
 유형 comment 제목 Ch7 after class comment 참여자 김민규 내용 점화식에 대한 간단한 예제와 사례를 살펴보고 점화식을 간단하게 풀 수 있는 다양한 방법에 대해서 배움. 그 중에서 특성방정식을 이용한 풀이법이 가장 효율적이고 유용하다고 생각.
 유형 정보 제공 제목 ch8.3 예습, Hamiltonian cycle. 참여자 김민규 내용 A cycle in a graph  contains each vertex in  exactly once, except for the starting and ending vertex that appears twice, a Hamiltonian cycle. A connected graph  has a Hamiltonian cycle       is a Hamiltonian graph. ex)   ● Traveling Salesperson Problem Given a weighted graph , find a minimum-length Hamiltonian cycle in .   Traveling salesperson problem  1. To visit every vertex of a graph G only once by a simple cycle.   2. Such a cycle is called a Hamiltonian cycle.  3. If a connected graph G has a Hamiltonian cycle, G is called a Hamiltonian graph.
 유형 정보 제공 제목 ch8.3 예습, Hamiltonian cycle. (cont) 참여자 김민규 내용 ex)   And this problem can solve by integer linear programming formulation. (선형 정수 제약식)
 유형 정보 제공 제목 ch8.3 예습, Hamiltonian cycle. (cont) 참여자 김민규 내용 *https://ko.wikipedia.org/wiki/%ED%95%B4%EB%B0%80%ED%84%B4_%EA%B2%BD%EB%A1%9C​​   *https://en.wikipedia.org/wiki/Travelling_salesman_problem​
 유형 preview 제목 Ch8.3 comment on professor lecture note 참여자 김민규 내용 며칠 전 예습한 내용을 올린 것과 같이 챕터 8.3에서 배우는 해밀턴싸이클과 외판원 문제 등을 배우는데, 외판원 문제는 선형정수제약식을 세워서 풀 수 있습니다. 제약 조건을 만족하면서 목적함수 Z를 최소화 시키는 경로를 찾는 것 입니다.
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 ch8. Sec 1~4 summary (Combined) (cont) 참여자 김민규 내용
 유형 Q & A 제목 육상과 수학, 트랙의 길이 참여자 questioned by 김민재, Answered by 홍석호, finalized by 김민규 질문 Q. 육상 경기장의 원형 코스의 너비가 1.2m라고 가정하면 인접한 두 코스의 반지름의 차가 1.2m이므로 바깥쪽 코스의 길이는 인접한 안쪽 코스의 길이보다 7.54m가 더 길다. 따라서 원형 코스에서는 반지름의 길이와는 관계없이 인접한 두 코스의 반지름의 차가 1.2m이기만 하면 그 두 코스의 차는 항상 7.54m가 된다.​   왜 항상 7.54m가 될까? 답변 코스의 너비는 아래의 그림을 보면 이해가 쉽다. (아래의 그림은 너비를 1.22로 보았음)   아래 그림을 보면 바깥 코스일 수록 트랙의 길이는 늘어남을 알 수 있다.
 유형 Q & A 제목 육상과 수학, 트랙의 길이 (cont) 참여자 questioned by 김민재, Answered by 홍석호, finalized by 김민규 답변 위 그림의 반원 부분 2개를 합치면 원이 된다. 이제 계산을 해보자.   1. 일단 반지름이 r 일 때 원의 둘레는 2πr 로 나타낼 수 있습니다.  따라서 π를 3.14라고 생각하면 원의 둘레는 글의 내용과 같은 6.28 r 이 됩니다.  말 그대로 반지름의 6.28배가 되는 것입니다.   2. 따라서 글의 예시에 나와 있듯이 코스의 너비가 1.2 m 라는 말은    두 코스의 반지름 r 이 1.2 m 차이 난다는 것이고 (한 라인의 반지름이 'r'm이라면,   그 바깥 라인의 반지름은 (r+1.2)m)     3. 원의 둘레는 반지름의 6.28 배 이므로 바깥의 코스가 7.54 m 더 길다는 이야기 입니다.    (r+1.2)m * 6.28 = 약 (r + 7.54) m   출처 및 더 자세한 설명은 :
 유형 pro.solving 제목 Sec 6.2 problem 7 solve by 주경용 참여자 solved by 주경용, revise by 김민규 질문 Q. In how many ways can we select a chairman, vice-chairman, and recorder from a group of 11 persons? 답변 A. This problem has order(permutations). The number of 3 permutations of a set of 11 distinct object is P(11,3) = 11 x 10 x 9 = 990
 유형 pro.solving 제목 Sec 6.2 problem 13 solve by 주경용 참여자 solved by 주경용, revise by 김민규 질문 Q. Determine how many strings can be formed by ordering the letters ABCDE subject to the conditions given?    Condition: Contains either the substring AE or the substring EA or both. 답변 A.    AE를 하나로 두고 보면 AE,B,C,D 로써 배열한 가능한 수는 4! 를 X ->OK   EA를 하나로 두고 보면 EA,B,C,D 로써 배열한 가능한 수는 4! 를 Y -> OK   그렇지만 두 집합의 교집합을 생각하게 되면 중복되기 때문에 빼줘야합니다. -> NO    There is no intersection.   So, 4! contain the substring AE and 4! contain the substring EA.   The answer is 4! + 4! = 2*4!
 유형 pro.solving 제목 Sec 6.2 problem 19 solve by 주경용 참여자 solved by 주경용, revise by 김민규 질문 Q. In how many ways can five distinct Martians and eight distinct Jovians wait in line if no two martians stand together? 답변 A. Jovians can wait in line M position. = 8!    O-M-O-M-O-M-O-M-O-M-O-M-​O-M-O-M-O   and martians can wait in line in O position. -> There are 9 O positions.   So, P(9,5)     => 8!*P(9,5)
 유형 pro.solving 제목 Sec 6.2 problem 24 solve by 주경용 참여자 solved by 주경용, revise by 김민규 질문 Q. In how many ways can five distinct Martians and eight distinct Jovians be seated at a circular table if no two Martians sit together? 답변 A. 목 = seats for Jovians Fix a seat for a Jovian. There are 7! arrangements for the remaining Jovians. For each of these arrangements, we can place the Martians in five of the eight in-between positions (Red checked point), which can be done in P(8,5) ways. So, There are 7!*P(8,5)
 유형 pro.solving 제목 sec 6.7 problems solution (1 of 3) 참여자 solved by 양승찬, revise by 김민규 질문 Q1.(#3)   Coefficients of  x^4 y^7 :(x+y)^11​ 답변 I think there is no problem in your solution.   I just modify a little.   A1. (#3)   = 1^4 * C(11,4) * 1^7 * C(7,7) = 330
 유형 pro.solving 제목 sec 6.7 problems solution (2 of 3) 참여자 solved by 양승찬, revise by 김민규 질문 Q2.(#6)   Coefficients of w^2 x^3 y^2 z^5 : (2w+x+3y+z)^12 답변 A2. (#6)   = 2^2 * C(12,2) * 1^3 * C(10,3) * 3^2 * C(7,2) * 1^5 * C(5,5) = 5987520
 유형 pro.solving 제목 sec 6.7 problems solution (3 of 3) 참여자 solved by 양승찬, revise by 김민규 질문 Q3 (#22) ​ Use the Binomial Theorem to show that​ 답변 A3.(#22)
 유형 Q & A 제목 축구의 무승부 확률 계산 참여자 questioned by 김민재, Answered by SGLee, finalized by 김민규 질문 대등하게 매칭된 두 팀 간에 평균 총 2.5골이 예상되는 한 Premier League 경기를 가정해 보겠습니다. 이 시나리오에서 각 팀은 상대팀에 대해 매 경기마다 평균 1.25골을 기록합니다. 푸아송 분포의 예측에 따르면 두 팀이 득점하지 못할 확률은 29%입니다. 따라서 경기가 0-0 무승부로 끝날 조정 전 확률은 이 두 확률을 서로 곱해서 구할 수 있습니다. 0.29 * 0.29 = 0.08   Premier League의 실제 데이터와 마찬가지로 1-1 무승부는 발생할 확률이 약 13%로 더 높습니다. 모든 무승부 점수에 대해 이 수치를 계산하면 0-0, 1-1, 2-2 등에 대한 확률을 서로 더하여, 비슷하게 매칭된 두 팀 간의 일반적인 Premier League 경기에 대한 전반적인 무승부 확률을 구할 수 있습니다.   실제 푸아송 분포의 작은 편차에 대해 보정하지 않은 이 예에서 무승부가 발생할 확률은 약 27%로 예측됩니다.   Q1. 조정전 확률이란?   Q2. 무승부가 발생할 확률 27% 구하는 과정 답변
 유형 Q & A 제목 축구의 무승부 확률 계산 (cont) 참여자 questioned by 김민재, Answered by SGLee, finalized by 김민규 답변 A1. 아마도 푸아송분포가 현실의 모든 조건을 고려하여 확률을 구하지 않기 때문에 조정이 필요하다는 말이라고 생각한다. 푸아송분포는 구단 상태, 경기장 상태, 선수들의 컨디션 같은 현실적인 제약조건을 고려하지 않고 확률을 계산하기 때문이다.   A2. 각 팀은 평균이 1.25인 푸아송분포를 따른다고 했으므로, 분포는 아래와 같다.   오른쪽 상단의 표를 통해 각 확률을 구할 수 있다. ​ 1. 0:0 무승부 일 확률 = 0.2865 * 0.2865 2. 1:1 무승부 일 확률 = 0.3581 * 0.3581 3. 2:2 무승부 일 확률 = 0.2238 * 0.2238 4. 3:3 무승부 일 확률 = 0.0933 * 0.0933 ​ 1,2,3,4의 확률을 모두 더하면 약 26.9%의 값이 나온다.   3:3 이상의 무승부가 나올 확률 ( ex: 4:4 일 확률은 0.0008468)은 매우 작으므로   이 경기에서 무승부가 될  총 확률은 문제가 제시한 답처럼 27%라고 계산 할 수 있다.   분포 출처 : https:www.geogebra.org/m/nMvYybd9

유형

정보 제공

제목

supplement : Ch 6.2.23, Catalan number, C(2n,n+1)

참여자

김민규

내용

 Example 2.23 How many routes are there from the lower-left corner of an  square grid to the   upper-right corner if we are restricted to traveling only to the right or upward and if we are allowed to touch but not go above a diagonal line from the lower-left corner to the upper-right corner?

ch6.2, ex 23의 이해를 돕기 위한 국문, 영문 자료를 찾아보았습니다.

대각선 윗 부분을 대칭시킬 것인지, 아랫부분을 대칭시킬 것인지의 차이만 있을 뿐 전체적인 풀이 과정은

동일합니다.

(수식이 깨져 출처를 캡쳐해 올립니다. 출처 사이트로 가시면 copy가 가능합니다.)

 유형 정보 제공 제목 supplement : Ch 6.2.23, Catalan number, C(2n,n+1) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 supplement : Ch 6.2.23, Catalan number, C(2n,n+1) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 supplement : Ch 6.2.23, Catalan number, C(2n,n+1) (cont) 참여자 김민규 내용
 유형 정보 제공 제목 supplement : Ch 6.2.23, Catalan number, C(2n,n+1) (cont) 참여자 김민규 내용
 유형 preview 제목 Ch8 preview / Ch9 Preview / Ch 9 summary 참여자 김민규 내용 최단경로. 즉 한 출발점에서 도착점까지 가는 다양한 경로 중 가장 가깝게 갈 수 있는 경로에 대해서 배우는 파트입니다. 그리고 이것을 행렬로 표현하는 방법, 그리고 행렬로 푸는 법에 대해서 배웁니다. //   트리는 특히 컴퓨터 연상에서 많이 쓰이며 데이터를 구조화하고 분류하는데 유용합니다. 이번 장에서는 트리의 특성, 기본적인 용어에 대하여 배우고 다양한 트리 기법에 대해 배웁니다. //   트리의 용어, 신장트리에 대해 배웠고 가장 중요한 이진트리에 대해 배웠다. 이진트리는 다양만 문제를 컴퓨터가 연산가능 하게끔 해준다는 점에서 가장 핵심이라고 볼 수 있습니다
 유형 정보 제공 제목 ch6. supplement : Bayes's theorem 참여자 김민규 내용 수업교안에는 포함되어 있는 않는 6.6절의 베이즈정리이지만 고교과정에서 유사한 개념을 배우기에, 또 현재까지도 다양한 분야에 쓰이기에 소개해보고자 합니다.   이 간단한 개념이 요즘 이슈인 빅데이터를 통한 예측에도 쓰입니다. 개념을 먼저 설명하고, 빅데이터 (데이터마이닝)에서 어떻게 쓰이는지 알아보겠습니다.   먼저 개념에 대한 설명입니다.
 유형 정보 제공 제목 ch6. supplement : Bayes's theorem (cont) 참여자 김민규 내용 다음은 데이터마이닝에서 예측을 위해 베이즈정리가 쓰이는 원리를 설명하고 있습니다.   ​위의 예시처럼, 구조화된 데이터를 이용해 각 확률을 구하고, 베이즈 정리를 통한 식 변형을 이용해 수학적으로 예측이 가능합니다.    first reference : https://blog.naver.com/jvioonpe/220228306144 second reference : http://bab2min.tistory.com/559

Discrete Mathematics              Prof : Sang-Gu LEE

과제함 Due day :  2018/6/15(Fri.)

Name (이름) : 주경용

Major and Sudent No (전공 및 학번) : 생명과학과

(1) State more than 10 DM Definitions and concepts what you learned in Ch. 1, 2, 3, 4, 5, 6, 7, 8, 9.

set, partition, cartesian product, tautology, Demorgan’s law, Nested quantifiers, proof by contradiction, strong form of induction, The Quotient-Reminder Theorem, bijection, sorting

composition function, lengh of string, partial order, equivalence relation, equivalence class, prime factorization, big oh, omega, theta, recursive algorithm, fibonacci sequence, gcd, lcm, union, intersection, repeating squaring, euclidean algorithm, multiplication principle, addition principle, inclusion-exclusion principle, permutation, combination, catalan number, binomial theorem, pigeonhole principle, recurrence relation, Mersenne number, ackerman’s function, linear homogeneous recurrence relation, Dijkstra algorithm, Euler cycle, Hamiltonian cycle, binary tree

(2) State more than 5 things that you know/can/find ...  after you studied the first 8 Chapters.

injective function과 subjective function을 활용하여 bijection function 확인하기

Induction을 이용하여 statement을 verify하기

direct or indirect proof을 이용하여 proposition(or theorem)을 입증하기

함수의 reflexcivity, symmetyric, transitivity 특성을 통해 동치관계 확인하기

증가수열, 감소수열, 비감소수열, 비증가수열 차이점 확인 및 수열에서 구분하기

Nested quantifires의 order of quantifiers을 고려해 proposition의 참, 거짓여부 판단하기

Analysis of algorithms using big O, omega and theta

euclidean algorithm을 이용하여 효율적으로 gcd 구하기

카탈랑 수를 활용하여 기울기 y=x를 넘지 않는 good routes 찾아보기

순서와 반복 고려 여부에 따라 permutation 혹은 combination을 이용해 경우의 수 구하기

pigeonhole principle를 활용하여 배열의 존재성 문제를 증명하기

반복법을 이용하여 점화관계 풀기

오일러 사이클과 해밀턴 사이클 차이점 비교 및 그래프에서 활용하기

(3) QnA 담당교수님 다른 학생들이 업로드한 Q 에 10개 이상의 자신의 Comment or Answer  (Discussions) 를 주시오.

(4) 그리고 (첨부한) PBL 보고서에

<자기평가>, <동료평가> + <자신이 QnA 에 업로드한 Q and Answer (Reply) 를 모아서>

주어진 첨부 형식에 맞추어 내용을 채어서 Due Day 전에 제출하시오. 양과 질을 평가하여 성적을 부여합니다.  [The First or The Best!]

그리고 중간고사와 기말고사에 여러분이 학습하고 PBL 보고서에 보고한 내용을 반영합니다.

[성찰노트]

※ 다음 항목들을 고려하여 자신의 학습과정과 내용을 기록하시오.

1. 나는 지금 수행되고 있는 학습의 진행내용을 이해하고 있는가?

화교학교를 나온 제가 수학적 지식은 다른 학우보다 뒤쳐지기 때문에 우선적으로 복습에 중점을 두고 교안과 교재를 함께 보면서 그 주에 배운 내용을 이해하려고 노력하고 있습니다. 또한 모르거나 이해가 안 되는 내용들은 Q&A를 활용해 질문과 답을 거치며 그 주에 배운 내용을 이해하려고 했습니다. 그래도 만약에 이해가 안 되는 내용이 있다면 인터넷으로 검색해보고 알아감으로써 점점 더 학습의 진행내용을 이해해 나가고 있습니다.

2. 어떤 방법을 통해서 학습하였는가?(학습방법 및 자료)

우선적으로 교수님께서 올려주신 교안을 가지고 공부를 하면서 이해가 안 되는 부분에 대해서는 본 교재를 가지고 함께 공부하고 있습니다. 그리고 수업 날 배운 내용들은 다음 수업 날 전까지는 반드시 복습하였습니다. 이는 Q&A에 활동을 하는 원천이 되었습니다. 또한 이해가 안 된다고 생각되는 것들은 질문을 하여 다른 학우나 교수님의 답을 얻음으로써 잘못된 개념이나 모르는 것들을 정확하게 학습할 수 있었습니다.

3. 본 강좌의 학습활동을 통하여 무엇을 배웠나?

진도를 거듭하면 할수록 수학이 활용되는 곳이 정말 다양하다는 것을 알 수 있었습니다. 우리가 쉽게 접하는 일상생활 속의 문제부터 시작해서 기계와 관련된 알고리즘 등에 쓰이는 수학적 개념들에 대해 많이 배울 수 있었습니다. 그리고 sage code를 활용해 문제를 풀어봄으로써 이전에는 배워보지 못한 새로운 code text들이나 알고리즘 방식도 알게 되었습니다. 또한 어떤 theorem에 대해 많은 proof를 통해 입증하면서 단순히 수만 넣고 계산하던 방식에서 벗어나 폭넓게 수학을 바라볼 수 있는 시선도 배웠습니다. 마지막으로 Q&A에 질문과 답을 하고 학우들의 것도 살펴보면서 배운 개념을 견고히 하고 새로운 사실도 알게 되면서 모른다고 가만히 있기보다는 적극적으로 학우 및 교수님과 소통을 해서 많은 개념들을 이해 및 공유해야겠다는 자세도 배웠습니다.

4. 다른 동료들로부터 무엇을 배웠는가?

Quiz에 대한 답안을 가지고 학우들이 많이 했을 텐데 누군가는 그와는 다른 방법으로 문제를 풀어보려고 Q&A에 자신의 지식을 공유한 모습을 보면서 나도 문제를 보는 폭넓은 시야를 배워야겠다고 생각했습니다. 또한 학우들이 Finalize를 할 때 질문과 답에 더 도움이 될 수 있는 자료를 보태는 것을 보면서 나도 학우나 질문자에게 더 도움을 줄 수 있는 내용들을 적극적으로 찾아봐야겠다는 자세도 배웠습니다. 마지막으로 퀴즈에 오류가 있었는데 동료가 이미 질문을 하고 제가 그 의견에 동참을 하던 과정에서 그 동료의 선 질문이 없었더라면 고쳐지지 않았을지 모를 문제였기 때문에 이해가 안 되는 것들은 적극적으로 물어보고 소통해나가야겠다는 자세도 배울 수 있었습니다.

5. 새롭게 배운 내용을 실제 생활에 어떻게 적용할 것인가?

생명과학에는 생명현상 관찰과정에서 인식한 문제를 해결하기 위해 연역적 탐구가 있는데 잠정적 결론이라고 일컫는 가설은 실제로 수업에서 배우는 가설과 유사합니다. 그 가설을 확인하기 위해 실험을 하며 변수가 되는 독립변인과 결과 값인 종속변인이 있는데 이는 마치 domain과 range와 유사합니다. 저는 이 부분에서 이산수학의 내용을 접목시킨다면 효과적으로 전공공부를 할 수 있을 뿐만 아니라 연구 분야에서도 좀 더 간략하고 효율적으로 실험과정을 이끌 수 있을 것 같습니다.

6. QnA 활동에서 자신의 역할과 기여도에 대한 평가(자신의 활동에 점수를 주고 그 이유를 적으세요.) :

-   90    점.

- 우선 저는 Question을 제일 많이 했습니다. 그것이 다른 학우에게 도움이 될지는 모르겠지만 질문을 통해서 제가 헷갈렸던 점들은 모두 해결할 수 있었습니다. 그리고 저의 질문을 통해 또 많은 학우들이 Finalize를 할 수 있었기에 서로에게 도움이 되었다고 생각합니다. Answer에서는 사실 적극적으로 임하지는 못했지만 제가 아는 한에서 답을 줌으로써 질문자나 저나 지식을 되새겨보는 계기가 되었습니다. 그리고 다른 학우의 내용에 comment를 달아줌으로써 단지 수학적 지식뿐만이 아닌 인문학적 태도도 배웠던 것 같습니다.

7. 다른 학생에 대한 평가

어쩌면 예습과 복습을 하고 Q&A에서 이를 다시 다룬다는 것이 쉽지 않을 수 있습니다. 하지만 많은 학생들이 이에 임하였고 하루하루 글이 쌓여가는 것을 보면서 저 자신도 나태해지지 말아야겠다는 생각이 들었습니다.

▶ 자체평가에 따른 잘한 점

사실 어려울 것이라고 생각한 이산수학을 교수님의 수업내용과 교안과 교재 그리고 무엇보다 Q&A에 적극적으로 임함으로써 잘 이해할 수 있었습니다. 특히 저는 Q&A에서 교수님이나 동료들에게 모르거나 이해가 안가는 내용을 적극적으로 물어보는 편이었습니다. 그래서인지 잘못된 개념이나 모르는 것들을 빨리 확인하고 넘어갈 수 있었습니다. 또한 다른 학우들이 푼 문제들을 Final을 위해 정리해보면서 개념을 다시 복습할 수 있었고 새로운 방식으로 문제들을 푼 학우들을 보며 comment로 ‘대단하다, 이해가 잘된다.’ 등의 의견도 달았던 기억이 남습니다. 마지막으로 교수님께서 만들어주신 실습실을 통해 sage code를 이용해보면서 문제적용도 해보고 이렇게도 접근할 수 있다는 것을 알게 된 기회가 되었습니다.

▶ 자체평가에 따른 아쉬운 점

가장 아쉬운 점은 아마 학우들의 질문을 봐도 이해가 안 되어 답변을 제대로 못 준 경우입니다. 교안에 있는 내용이나 퀴즈에서 습득했던 내용들은 어느 정도 답변을 해줬으나 그것을 변형하여 물어볼 경우 제대로 이해하지 못한 게 아쉽습니다. 또한 초반에 질문에 대한 답변만 받고 final을 하지 않아 답을 해주신 교수님에 대한 감사함이나 이해를 했다는 표시를 제대로 하지 못한 것도 아쉬운 점으로 남습니다. 마지막으로 중간고사 이후로 문제를 풀어야하는 HW가 많았었는데 적극적으로 임하지 못한 것 같아 아쉬움으로 남습니다. 따라서 다른 학우들이 푼 HW 문제들을 적극적으로 공부하고 이해하면서 남은 기간을 잘 마무리 해나가겠습니다.

자신의 학습에 도움이 된 우수한/성실한 동 료 평 가

황병재, 이동욱 :  자체평가 중 잘한 점

황병재 학우님은 중간고사 이후부터 퀴즈 문제나 hw문제를 정말 많이 푸시고 공유해주셨습니다. 덕분에 저도 그 지식에 sage code를 활용해볼 수 있었고 모르는 문제들도 이해할 수 있었습니다. 또한 이동욱 학우님은 제가 CH6에서 푼 수식적으로 푼 문제들을 이해하기 쉽고 보기 편안하게 그림을 덧붙여주시고 설명을 더 보태어주셨습니다. 또한 카탈랑 수에 대해서도 의견을 나눴던 기억이 납니다. 따라서 두 분의 학우 분을 추천합니다.

5-1. 본 수업을 통해 자신이 습득한 자기 주도적 학습 기술을 구체적으로 설명하시오.

수업 후에 바로 복습을 하는 편입니다. 복습을 하면서 생긴 의문점을 질문하고 배운 이론을 제대로 이해했는지 예제문제로 확인해봅니다. 그 후에 퀴즈를 풀면서 이론을 되짚어보고 해결능력을 향상시켰습니다. 다른 학우가 푼 quiz에 sage code를 사용해서 답을 덧보태거나 final을 할 때 외부자료를 첨언해 구체적으로 답을 적음으로써 질문자나 저나 모두가 이해가 잘 되도록 하였습니다.

12-1. 본 수업과정에서 자신이 참여한 활발한 의사소통을 구체적으로 설명하시오.

Q&A 게시판에서 박성빈 학우가 선 질문으로 quiz 2-1문제에 의아함을 제기하였을 때 저도 이 생각에 동참한다고 답을 달면서 그 반례를 들었던 점이 생각납니다. 교수님께서도 퀴즈 문제에 오류가 있다고 하셔서 바꿔야 된다는 결론이 나왔습니다. 또한 김건우 학우님이 예제 풀이과정에서 이해가 안 된다고 하셨던 부분에 대해 답으로 부연설명을 했던 것들도 생각납니다. 그리고 수학이 적용된 운동 분야를 적은 김민재 학우분의 내용에 견해를 달면서 운동에 담겨진 수학도 알 수 있었고 그 학우의 내면도 조금이나마 공감할 수 있었습니다.

14-1. Flipped/PBL 방식의 수업에서 효과적이었다고 생각되는 부분을 구체적으로 설명하시오.

Q&A에 질문과 답을 하려면 우선적으로 그 주에 배운 내용을 당연히 알고 있어야 합니다. 그런 점에서 복습을 이끌어낸다는 점이 제게는 큰 효과이었습니다. 시험기간에 닥쳐서 몰아치는 공부보다 꾸준히 하는 공부가 머리에 더 잘 기억되었고 누가 Q&A 게시판에 무엇을 올렸을지 궁금함까지 생기면서 수업에 대한 집중도도 함께 상승되었던 것 같습니다.

15. 2-3 장. 참여 부분 (New Form),  Name:  주경용

16.       -  중간고사의 10~15점 부분입니다.

자기 평가와 본인의 Project (Term paper) Proposal 에 대해 아래를 채우시오.

1.  (20점) 본인이 그간 Q&A,  동료학생, “DM"강좌 등에 기여한 내용을 간단히 서술하세요!

(1)  QnA 참여 회수 <QnA에서 직접 확인하세요> : 각 주별(토요일에서 금요일)

(1) 1주차 : 총 0 회,  2주차: 총 2 회,  3주차 : 총 7회, 4주차 : 총 17 회, 5주차(4월포함) : 12회, 6주차: 총 5회, 7주차 : 중간고사, 8주차 : 총 13회, 9주차 : 총 12회, 10주차 : 총 4회, 11주차 : 총 10회, 12주차: 총 12회, 13주차 : 총 4회, 14주차 : 총 4회

총  112  회  (질문:   61회,  답변/수정:  51 회)

(2) 온라인 출석 회수 :     32회  / 32회

(3) 오프라인 출석 및 결석 회수 : 14 회 /  0회   (수강정정기간에 신청)

(2) 본인이 본 강좌를 통하여 기여한 내용

1. Q&A에 올린 좋은 수학시 및 관련 또는 기타 유의미한 정보 개수 (  21 개)

2. 본인이 토론을 정리하여 마무리한 (누군가 제목에 Final 표시한) QnA 내용에 자신의 이름이 포함 된 것 (제가 final 선언으로 final ok 받은 것 : 19개, 저의 질문과 답변으로 final ok 받은 것 18~20개)

(3) 1, 2 중에서 특히 기억나는 내용 : 교수님이 만들어주신 실습실에 제가 sage code를 활용해서 황병재 학우님이 푸신 퀴즈 ch7 43번 문제나 이상철 학우님이 푸신 퀴즈 ch7 40, 42번 문제를 적용시켜 답을 도출하고 final 해봄으로써 한 번 더 이해해볼 수 있었던 시간들이 기억에 많이 남습니다. 그리고 황병재 학우님이 푸신 ch8.1 15번 문제나 나빌 학우가 푸신 ch8.1 14번 문제를 제가 아는 지식을 동원해 revise해서 final ok받은 것도 기억에 많이 남습니다. 마지막으로 김민재 학우분이 올려주신 운동에 숨겨진 수학내용도 참 재미있게 읽었었고 제 견해를 곁들이면서 정말 소통하는 느낌을 받았습니다.

(4) 개인/동료와 같이 LA 강좌를 (PBl/Filpped/Action learning) 학습 하면서 배우거나 느낀 점은?

이제는 이렇게 수업해가는 것이 적응이 되고 다른 수업보다도 더 재미있는 것 같습니다. 사실 공부는 흥미가 떨어지면 하고 싶지 않지만 이 수업은 제게 흥미를 이끌어 주었습니다. 우선 화교학교에서 배운 수학과는 다른 이산수학이 어렵게 다가왔지만 수업 후 매일 복습을 하면서 모르는 점은 질문을 하고 답을 받고 이해를 하면서 제가 수학에 점점 지식이 쌓인다는 것이 느껴졌습니다. 물론 부족한 점이 많지만 배운 내용들을 하나하나 까먹지 않게 Q&A나 퀴즈, 예제 등으로 복습함으로써 제 것으로 만들려고 노력하고 있습니다. 개인적으로 공부를 할 때는 마땅히 물어볼 곳도 없고 소극적인 성격으로 나서서 교수님께 물어보지 못했는데 이렇게 열린 공간에서 많은 학우 및 교수님과 학습하는 것이 단순한 수학적 지식을 쌓는 것만을 넘어 자신감을 주었기 때문에 만족하고 있습니다. 마지막으로 교수님 및 학우들과 많은 소통을 하면서 느낀 점은 상대방에게 어떻게 하면 더 효과적으로 답변을 줄 수 있을지 그리고 어떻게 질문을 하면 상대방에게 나의 착오가 잘 전달될지에 대해서도 다방면의 생각을 하면서 글을 써보는 능력을 배울 수 있었습니다.

나) DM March PBL보고서를 마치고

사실 이과수학에 대해 제대로 공부해 본적이 없어서 이산수학에 막연한 두려움을 갖고 있었습니다. 하지만 학우 및 교수님과 소통하며 모르는 점들을 질문하고 풀이방법에 대해 논의하는 과정이 제가 지식을 쌓는데 큰 도움이 되었습니다. 사실 부족한 점이 아직 많이 있습니다. 지식뿐만이 아니라 어떤 의미 있는 질문을 하고 답을 줘야 할지도 많이 고민하게 된 시간이었습니다. 그래도 단순히 시험기간에 닥쳐서 벼락치기 공부만 하던 제가 수업을 마친 후 복습을 한다는 것은 큰 변화였고 그 노력이 그래도 Q&A게시판에서 활동하게 된 원천이었다고 생각합니다. 지치지 않고 꾸준히 공부해서 앞으로도 많은 활동을 보여줄 것이며 저처럼 수학을 어려워하시는 분들도 포기하기보다는 꼭 복습을 하셔서 모르는 것에 대해 많이 질문하시고 답을 보며 또 공부하시다보면 많은 도움이 될 것이라고 생각합니다. 감사합니다.

다) DM April PBL보고서를 마치고

사실 이과수학에 대해 제대로 공부해 본적이 없어서 이산수학에 막연한 두려움을 갖고 있었습니다. 하지만 학우 및 교수님과 소통하며 모르는 점들을 질문하고 풀이방법에 대해 논의하는 과정이 제가 지식을 쌓는데 큰 도움이 되었습니다. 특히 교수님께서 답을 주실 때 다양한 추가 자료를 함께 올려주시거나 잘못된 개념에 대해 명확히 잡아주신 덕택에 이해가 더 빨라질 수 있었습니다. 사실 부족한 점이 아직 많이 있습니다. 그게 꼭 수학적 지식뿐만이 아니라 영어실력도 부족하고 의미 있는 질문과 답을 하는 것도 아직 미숙합니다. 하지만 단순히 시험기간에 닥쳐서 벼락치기 공부만 하던 제가 수업을 마친 후 복습을 한다는 것은 큰 변화였고 그 노력이 그래도 Q&A게시판에서 활동하게 된 원천이었다고 생각합니다. 앞으로 남은 기간 동안 더 많은 학우 및 교수님과 지식을 공유하면서 많은 것들을 배워나가겠습니다. 비단 교안이나 교재에 있는 내용이나 증명이 아니더라도 자신이 알고 있는 지식을 활용해 다양한 증명이나 답을 보이는 학우들을 보면서 저도 그들을 본받고 따라가려고 노력해 나가겠습니다. 감사합니다.

DM Final PBL/Project 보고서를 마치고

처음에는 두려움 반으로 시작했던 ‘이산수학’이였는데 이제는 공부에 재미도 느끼고 이런 교육 방식에 적응이 다 된 것 같습니다. 사실 아직 부족한 점은 많이 있습니다. 다른 학우보다 이해가 늦고 복습도 몇 번을 더해야 이해가 될 때도 있습니다. 하지만 그럴 때마다 교수님께 질문하고 학우 분들이 답을 수정해줌으로써 제가 부족한 점이 무엇인지 알아가고 고쳐나가는 과정이 될 수 있었습니다. 특히 교수님께서 답을 주실 때 다양한 추가 자료를 함께 올려주시거나 잘못된 개념에 대해 명확히 잡아주신 덕택에 이해가 더 빨라질 수 있었습니다. 제가 이번 수업을 하면서 느낀 점은 외국인(화교)라고 해서 수학에 자신없어하고 겁먹을 필요가 없다는 것이었습니다. 시작이 조금 늦을 뿐 충분히 따라갈 수 있다는 뜻입니다. 저는 특히 시험기간에 닥쳐서 벼락치기 공부만 하던 버릇에서 벗어나 수업 이후에 복습을 한다는 것은 큰 변화였고 그 노력이 Q&A게시판에서 고스란히 녹아들을 수 있었습니다.

비단 수학적 지식뿐만이 아니라 더 나아가서 본다면 어떻게 설명하면 더 나은 답을 줄지 아니면 어떻게 질문하면 상대방이 나의 문제점이 무엇인지를 정확히 알 수 있을지에 대한 글쓰기 능력도 기를 수 있었던 것 같습니다. 뿐만 아니라 각양각색의 학우들을 이해하는데도 좋았던 시간이 될 수 있었습니다. 마지막으로 저는 이 수업을 통해서 제 자신이 그래도 많이 바뀌었던 것에 만족합니다.

처음에는 두려움 반으로 시작했던 ‘이산수학’이였는데 이제는 공부에 재미도 느끼고 이런 교육 방식에 적응이 다 된 것 같습니다. 사실 아직 부족한 점은 많이 있습니다. 다른 학우보다 이해가 늦고 복습도 몇 번을 더해야 이해가 될 때도 있습니다. 하지만 그럴 때마다 교수님께 질문하고 학우 분들이 답을 수정해줌으로써 제가 부족한 점이 무엇인지 알아가고 고쳐나가는 과정이 될 수 있었습니다. 특히 교수님께서 답을 주실 때 다양한 추가 자료를 함께 올려주시거나 잘못된 개념에 대해 명확히 잡아주신 덕택에 이해가 더 빨라질 수 있었습니다. 제가 이번 수업을 하면서 느낀 점은 지식을 함께 공유하면서 서로 소통하는 것이 문제를 보는 안목을 넓히고 나아가 더 많은 생각과 개념을 배울 수 있었던 소중한 시간이었다는 것입니다. 또한 저와 같이 수학을 두려워하고 어려워하는 학생들에게도 자신감과 용기를 돋아주는 계기가 되었다는 점에서 이제는 수학을 더 배워보고 싶다는 생각이 들게 만들어주었습니다.

특히 시험기간에 닥쳐서 벼락치기 공부만 하던 버릇에서 벗어나 수업 이후에 복습을 한다는 것은 큰 변화였고 그 노력이 Q&A게시판에서 고스란히 녹아들을 수 있었습니다. 그리고 비단 수학적 지식뿐만이 아니라 더 나아가서 본다면 Q&A 활동에 있어서 어떻게 설명하면 질문자가 답을 잘 이해할지 아니면 어떻게 질문하면 답변자가 문제점이 무엇인지를 정확히 알 수 있을지에 대해 생각해보면서 글을 쓰는 능력도 한층 향상할 수 있었습니다. 뿐만 아니라 각양각색의 학우들을 이해하는데도 좋았던 시간이 될 수 있었습니다. 마지막으로 저는 이 수업을 통해서 제 자신이 그래도 많이 바뀌었던 것에 만족합니다.

DM Final Individual PBL Presentation을 마치고

여러 학우들의 발표들을 보면서 느낀 점은 제가 아직 고쳐야 할 점이 많다는 것이었습니다. 제가 아무리 Q&A에서 활동을 많이 했더라도 그 부분을 잘 살려서 학우 및 교수님에게 많은 정보를 제공했어야 했는데 그렇게 하지 못했던 것 같습니다. 이것은 제가 준비가 많이 부족했기 때문이라고 생각합니다. 다른 학우의 발표는 자신이 말하고자 하는 것을 확실히 목표로 잡고 중점을 두고 발표하는 것 같았습니다. 저 역시도 많은 Q&A의 활동 내용 중에서 제가 정말 중요하다고 생각되는 부분만 선택해서 발표를 하였는데 우선 효과적으로 전달이 되지 않았던 것 같아 아쉬움이 남습니다. 우선 실수를 하는 것에 대한 두려움 때문에 대본을 손에 계속 들고 있었고 학우들 및 교수님의 이해하고 있는지에 대한 표정 등에 대해 살펴보면서 진행을 했어야 했지만 모니터에만 집중해서 발표를 이어갔습니다. 이번 발표가 아쉬운 점도 많았지만 그래도 제 나름대로 만족했던 점도 있었습니다.

우선 제가 선택한 발표 자료는 실질적으로 제가 어떤 역할을 함으로써 그 과정이 어떻게 바뀌었는지를 알 수 있도록 설명하였습니다. 단순히 이렇게 답변했다가 아니라 반례를 들었다든지 혹은 계차수열의 공식을 알맞게 고쳤다는 것 등을 구체적으로 언급해서 제가 무슨 역할을 했는지를 알려드렸습니다. 그리고 실질적으로 sage code 활용에 있어서도 황병재 학우님이 푸신 문제와 맞는 코드 법을 교안에 있는 것을 이용해서 풀었다는 점을 강조하면서 다방면으로 문제를 접근할 수 있었음을 알려드릴 수 있었습니다.

그러나 아직 아쉬운 점이 많이 남습니다. 발표영상을 보면 저는 계속 모니터만 주시하고 있고 학우들이 어떻게 바라보고 있는지에 대해서 생각하지 못했던 점이나 최소한 교수님과 눈으로 소통을 계속해서 잘하고 있는 것인지 등을 파악했어야 했는데 그 기회를 놓쳤습니다. 또한 약간의 말더듬으로 인해서 듣는 학우분과 교수님이 불편하거나 잘 안 들릴 수 있었을 가능성도 배제할 수 없었기에 준비를 꼼꼼하게 하지 못한 것들은 아쉬움으로 많이 남습니다.

지금도 계속 느끼고 있지만 이런 점들은 계속 고쳐나가야 할 숙제인 것 같습니다. 비단 학교 발표가 아닌 사회생활에서도 의사소통은 필수이고 전달력 또한 매우 중요한 부분을 차지하기 때문입니다. 이제 이번 주 금요일 날 발표하실 학우 분들을 보고 제가 무엇을 더 배워가야 할지를 알아보고 이 발표 pbl을 마무리 짓도록 하겠습니다.

INDEX

1. 박종호 : 팀원 소개 및 CH1~3 요약 정리 및 Q&A 문제 풀이

2. 주경용 : CH4~9 요약 정리 및 Q&A 선정 문제 풀이

3. 남영욱 : 팀 프로젝트에 대해 느낀 점 및 앞으로 개선방향

Chapter 1 PBL Report

Team6

1. 1]Q&A

 Question & Answer Chapter Ch1, Sets and Logics Date 2018.03.09 Type Writer Title Contents Question 조규상 Problems in solving Quiz 1,2 In Quiz1.Problem 3   (6)T/F The proposition "If all cats are white, then all dog is brown" is true   Solution says it is True.   I wonder if it is true because hypothesis is false.   Or are there any other reason exists?   2. In Quiz2. Problem 1   Solution writes a truth table to determine the validity.   Is it okay to solve in this way?   p: “Socrates is a cat.” q : “Socrates is a mortal.” r: “Socrates is a man.”   p → q r ∨ (¬q)   r ∨ (¬q) ≡ (¬q) ∨ r ≡ q → r   p → q q → r ∴p → r Answer 1 이상구 교수님 Final: Dear Mr. 조규상​, Use truth table to determine^^ Final: Dear Mr. 조규상​,  Use truth table to determine^^ Dear Mr. 조규상​,  Here is my Comment^^ 1. In Quiz1. Problem 3   (6) T/F The proposition "If all cats are white, then all dog is brown" is true Because if it is true because the hypothesis (all cats are white) is false. [Yes you are right] ​ 2. In Quiz2. Problem 1   Solution writes a truth table to determine the validity.   p: “Socrates is a cat.” q : “Socrates is a mortal.” r: “Socrates is a man.”   p → q r ∨ (¬q)   r ∨ (¬q) ≡ (¬q) ∨ r ≡ q → r   p → q q → r ________ ∴p → r   Is it okay to solve in this way?​  틀리지는 않았지만, truth table 을 이용하여 validity 를 determine 하라고 요구하였으니.  이 답을 부분 점수를 받을 수 있습니다.   Use truth table to determine the validity.​ 로 다시 한번 해 보시는 것이 맞습니다. 2 박종호 final 박종호 : quiz2 problem1 In Quiz2.Problem 1 Solution writes a truth table to determine the validity.   p: “Socrates is a cat.” q : “Socrates is a mortal.” r: “Socrates is a man.”   p → q r ∨ (¬q) r ∨ (¬q) ≡ (¬q) ∨ r ≡ q → r p → q q → r ________ ∴p → r   ->위 문제에 대한 진리표는 솔루션에 있으니 생략하고 r ∨ (¬q) ≡ (¬q) ∨ r ≡ q → r라고 작성하신 부분에서 동치가 나와 참고하시라고 작성합니다.​   예제 1.2.13을 참고하시면 p->q의 부정과 p 또는 ㄱq와의 논리적 동치(logically equivalent)를 다뤘습니다. 같은 방식으로 동치 관계를 구한 것들을 올립니다.   1. ㄱ(p v q) ≡​ ㄱp and ㄱq 2. ㄱ(p and q) ≡​ ㄱp​ v ㄱq​ 3. p->q ≡​ ㄱp​ and q 4. p​<->q ≡​ (p->q) and (q->p)   p → q q → r ________ ∴p → r   작성자는 동치를 이용해 q->r을 이끌어내고 가설적 삼단논법(hypothetical syllogism)의 규칙으로 p->r이 타당함을 증명해냈습니다. 근데 문제에는 진리표를 작성하라는 말이 없음에도 불구하고 부분 점수를 받는군요~ 삼단논법은 그림 1.4.1과 예제 1.4.4를 참고하시면 이해가 편할 것 같습니다.

1. 2]Q&A                                                              Final OK

1.   3]Q&A                                                               Final Ok

 Question & Answer Chapter Ch1, Sets and Logics Date 2018.03.10 Type Writer Title Contents Question 함형빈 Quiz #1 Problem 1 number 3 Cardinality of P(T)를 물어봤는데 이중 P가 정확히 무엇을 의미하는지는 모르겠지만 solution에 답이 8로 나와있는데...... 그건 아닌 것 같다고 생각됩니다.   P가 전체를 의미한다면 10이 나올 것이고, 중복되지 않는 것이나 T set에 있는 것과 같은 것의 총합이라 한다면 6이 답일텐데...... 왜 8이 나왔는지 모르겠습니다. Final 이상구 교수님 Final OK by SGLee: Answer : Quiz #1 Problem 1 number 3, Cardinality of P(T) = 8 Answer : Quiz #1 Problem 1 number 3,  Cardinality of P(T) = 8 Answer Given set T=(2,4,8) , Cardinality of P(T), the power sot of T. ​ empty set,(2), (4), (8), (2,4), (2,8), (4,8), (2,4,8)    Total   8  Cardinality of P(T) = 8   그러므로 #Promblem1-(3)의 답이 8 입니다.

1. 4]Q&A                                                              Final Ok

 Question & Answer Chapter Ch1, Sets and Logics Date 2018.03.10 Type Writer Title Contents Question 장호 Power set P( ) 질문 Quiz1의 problem1이나 problem2에서 P(T)와 P(S)가 나왔는데, 그 의미를 모르갰습니다. Answer 1 조규상 Final: Final OK by SGLee Quiz 1 Problem 1-3, Power set, 8 Final: Final OK by SGLee Quiz 1 Problem 1-3, Power set, 8​ Power set으로 생각하시면 8으로 나옵니다   Q set T=  {2, 4, 8} 의 Power set 안의 부분집합의 개수는?   Answer  Final: Answer Re: Quiz #1 Problem 1 number 3, Power set, 8   공집합, {2},  {4}, {8}, {2, 4},  {2, 8}, {4, 8}, {2, 4, 8} 총 8 개입니다. ******************* 그러므로 #Promblem1-(3)의 답이 8입니다. Final: Answer Re: Quiz #1 Problem 1 number 3, Power set, 8   위에도 답을 주셨습니다.

1. 5]Q&A

 Question & Answer Chapter Ch1, Sets and Logics Date 2018.03.10 Type Writer Title Contents Question 홍석호 Quiz1 에 2번문제 질문드립니다. {0, {1, 2}, {3, 4, 5}} ⊆ Z.      For any set S, S ⊆ P(S). 이 둘이 False인 이유를 모르겠습니다.   그리고 더불어   p ∨ (p → q) is a tautology. 진리표를 만들어보면 항진명제라는 것은 자명합니다. 그러나 진리표 없이 문맥상으로 항진, 모순 명제를 유추할수는 없는지요? 문맥상으로 보면 P와 Q의 합집합입니다. 명제는 집합으로는 접근하면 안되는지도 궁금합니다. Answer 1 이상구 교수님 Final: Dear 홍석호​ 군, 용도에 따라 다양한 증명이 있습니다. 이것을 2장에서 배웁니다. 홍석호​ 군,   Dear 홍석호​ 군, quiz 1 problem 2 - (10) False 인 이유를 알려드립니다. For any set S, element S is in P(S)​  ​ [True,  # 9],               but  [element S⊆P(S) is False,  # 10]   멱집합(冪集合, 영어: power set) 의 정의를 자세히 보시면, ​   S 는 power set of S의 element 이기는 하지만 [True,  # 9 ] ,​,   S 는 power set of S 의 subset 은 아닙니다. [ False,  # 10] ​   ​    ​ https://ko.wikipedia.org/wiki/%EB%A9%B1%EC%A7%91%ED%95%A9     p ∨ (p → q) is a tautology. 진리표를 만들어보면 항진명제라는 것은 자명합니다......   진리표 없이 문맥상으로 항진, 모순 명제를 유추할수 있습니다. 문맥상으로 P와 Q의 합집합 임을 유추할 수 있습니다.   명제를 집합으로 접근하는 것이 벤 다이어그램을 이용하는 설명법입니다. 용도에 따라 다양한 증명이 있습니다. 이것을 2장에서 배웁니다.

1.  6]Q&A                                                               Final Ok

 Question & Answer Chapter Ch1, Sets and Logics Date 2018.03.10 Type Writer Title Contents Question 강민석 quiz1 단어뜻질문드립니다 tautology가 무슨뜻인지 몰라서 인터넷에 검색해보니 동의어반복이라는데 정확히 무슨의미인지 궁급합니다 Answer 1 이동욱 항진명제입니다. 항진명제: 언제나 참인 명제라는 뜻입니다. Final 이상구 교수님 Final OK by SGLee to 이동욱, 강민석군, 항진(恒眞)명제(tautology) ​는 ...... 강민석군, 항진(恒眞)명제(tautology) ​ quiz1 단어 뜻​     Tautology- 항진(恒眞)명제(tautology) ​   논리식 혹은 합성명제에 있어   각 명제의 참·거짓의 모든 조합에 대하여 항상 참인 것을 항진(恒眞)명제(tautology) 라고 한다.   Tautology :  진리표 에서 알 수 있는 바와 같이,...   i) 가능한 모든 조건 아래에서 모든 진리치가 진이 되는 명제   이것은 원자명제 진리치에 상관없이 항상 진인 이런 명제를 항진명제 (tautology) 라 한다. 일반적으로, 어떤 진리함수적 명제의 가능한 진리치가 모두 진일 때, 오직 그 때에만, 그 명제를 tautology 라 부른다. 항진명제는 그 논리적 형식상 결코 위가 될 수 없고 항상 진이어야만 한다.

1.  7]Q&A

 Question & Answer Chapter Ch1, Sets and Logics Date 2018.03.10 Type Writer Title Contents Question 이동욱 quiz 1 problem 2 질문 드립니다. quiz 1 problem 2 - (10) 번 문제 질문드립니다.   For any set S, S⊆P(S)   I don't have any idea why this is False... Final 이상구 Final: Dear 이동욱 군, quiz 1 problem 2 - (10) False 인 이유를 알려드립니다. Dear 이동욱 군, quiz 1 problem  2 - (10)   False 인 이유를 알려드립니다. For any set S, element S is in P(S)​  ​ [True,  # 9],               but  [element S⊆P(S) is False,  # 10]   멱집합(冪集合, 영어: power set) 의 정의를 자세히 보시면, ​   S 는 power set of S의 element 이기는 하지만 [True,  # 9 ] ,​,   S 는 power set of S 의 subset 은 아닙니다. [ False,  # 10] ​   ​    ​ https://ko.wikipedia.org/wiki/%EB%A9%B1%EC%A7%91%ED%95%A9

1.   8]Q&A

 Question & Answer Chapter Ch1, Sets and Logics Date 2018.03.11