[Action Learning]

Discrete Mathematics  (PBL report)

                   by Professor: Sang-Gu LEE

 

 

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

Definition: sets, cardinality, subset, super set, Venn diagram, proof, counterexample, mathematical induction, contrapositive, contradiction, function, sequence, algorithm, pseudocode, appendix, binary search, bubble sort, insertion sort, divisor, Euclidean algorithm, prime, composite, GCD, LCM, decimal number system, binary number system, hexadecimal number system.

 

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.

 

   * Applications of TSP in indusrty.

 

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를 활용하여 배열의 존재성 문제를 증명하기

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

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

 

수식을 역, 대우 등 여러 기호로 변환해 표현하기

여러 가지 증명의 방법들 중 적합한 증명의 방법을 고르는 기준들

수학적 귀납법을 이용하여 증명하기

유클리디안 알고리즘 활용하여 최대공약수 구하기

진법 변환하기

 

◆ Personal Reflection Note

1. Do you understand the most of contents of this learning process?

I am able to understand most of the contents through this learning process. Discrete Mathematics is quite a challenging subject, but thanks to professor’s passion and also the QnA discussion on icampus really helped me a lot for my understanding,

2. What kind of learning materials have you used to study?

-      Class lesson

-      Discrete Mathematics Richard Johnsonbaugh Seventh Edition (Textbook)

-      Lecture notes and QnA discussions.

-      Materials that were shared by professor on icampus

-      internet search,

-       

3. What did you learn through the learning activities of this course?

I learned that through active discussion through the QnA session, we could find a lot more questions that we might be unable to usually think of through normal learning process. Through sharing ideas, I am able to further improve my knowledge, and it is able to push me to study and prepare early for my learning.

4. What have you learned from other colleagues?

 

As a foreigner myself, I am able to discuss freely about the subjects through the QnA discussion. The QnA section has become a medium for the students to exchange what they learn and on the same time all of us learn to be competitive in learning.

 

5. How do you apply newly learned information to real world problems?

 

As a student who is currently taking major in computer engineering, I realize how discrete mathematics is going to help me a lot in the basic of computer. Logic, Proof, Functions, Relations, these are just some of the basic stuffs that I will learn further in my study of computer engineering. 

 

6. Self-Evaluation for Q/A Activities.

My Score: 80

At first, I was actually unable to understand the method of score and learning of the class. Therefore, for the first two weeks, I was unable to contribute in the QnA learning. However, thanks to the kind professor that gave me and other students time for the make-up chance, I am able to fully grasp the method of this class and in the end, to catch up and participate fully in the QnA discussions.

 

7. Evaluation for other students

 Some other students were also unable to understand the procedure of this class for the first few weeks. But in the end, most of them are able to understand and participate in the QnA. The students use the QnA to ask any questions that they do not know, to fix the errors in typing, and also to ask the professor anything about the learning and also the notice. Some of the students works really hard to participate.

8. Do you understand the most of contents of this learning process?

The content of the previous chapters is basic knowledge, so it is not difficult to understand. Because English is not very good, the learning process is not very smooth.

9. What kind of learning materials have you used to study?

 

-      I have a Chinese discrete mathematics textbook.

-      I can also find a lot of knowledge through the Internet.

-      Can also communicate with other students on the forum.

 

10. What did you learn through the learning activities of this course?

 

In the course I actually learnt some new things which I never knew before and those things were from almost by the sharing of knowledge with students and discussing with professor in Q&A. So these activities helped me a lot for learning new ideas and new things which going to help me in future.

11. What have you learned from other colleagues?

 

Learning a lot of new knowledge, and at the same time using Q&A for the first time, it feels very fresh, and it’s also a big boost to yourself..

 

12. How do you apply newly learned information to real world problems?

Although I learned a lot of new things, in fact,  I not know how to apply it to life. It may be that there is not enough knowledge to learn now and there are not many opportunities to use it. I will try to do this because it will make me feel satisfied to be able to use what I learned.

13. Self-Evaluation for Q/A Activities.

My Score :  70

   I can only try to raise my questions and get involved. Maybe it's not good enough now and it didn't fit well into this way, but then I hope to continue to improve.

14. Evaluation for other students

I have to say that many students are very hard working and very powerful. They can not only raise various problems that I can not think of, but also solve other people’s problems. They have a lot of places that I can study.

 

◆ Self-Evaluation   [Your Opinions]

 

▶ Satisfaction according to the self-evaluation.

I am satisfied with the learning course. I am able to contribute for the QnA session and be able answer some of the questions.

 

▶ Sorrow according to the self-evaluation.

 

I feel a little regret that I was unable to understand this class procedure for the first two weeks.   Thanks to the professor I was able to make up for my tentative grade.

◆ Colleague to help your learning

 

[Your Opinion]

 

     ▶ Satisfaction according to the evaluation

She did a good job in organizing after class, summarize the lecture and also asking and answering questions in the QnA

▶ Sorrow according to the self-evaluation

        I am envious of how she managed to concentrate and complete a lot of questions and answers.

 

◆ PBL Feedback for Students

 

 16. What is the merit of this PBL class.

One-way communication When compared with other existing classes, I feel that I am more enthusiastic and active learners because I am directly involved in the lesson after the class is over.

This PBL method pushes the students to prepare early for the class and also increases the learning and promote discussions among students.

17. What do you want to improve this PBL system.

I think that the space on icampus is a bit messy and not friendly enough for the students to do a complete discussion and revision in the future.

 

◆ Solve-Revise-Finalize (and Final OK)

Participation

 

Number of your QnA participation for the first 4 week. (18)

 

 

 

Q. Tautology 와 contradiction 이 두 단어가 의미하는 것이 무엇인지 잘 모르겠습니다.

Final: Dear 이진용​ 군, contradiction​ (모순), tautology(항진(恒眞)명제​) 뜻​ (4), (5)

 

이진용​ 군, contradiction​ (모순), tautology(항진(恒眞)명제​) ​ 뜻​

https://en.wikipedia.org/wiki/Proof_by_contradiction

Proof by contradiction

 

From Wikipedia, the free encyclopedia

In logic, proof by contradiction is a form of proof, and more specifically a form of indirect proof, that establishes the truth or validity of a proposition. It starts by assuming that the opposite proposition is true, and then shows that such an assumption leads to a contradiction. Proof by contradiction is also known as indirect proof, apagogical argument, proof by assuming the opposite, and reductio ad impossibilem. It is a particular kind of the more general form of argument known as reductio ad absurdum.[1][2]

G. H. Hardy described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."[1]

From Wikipedia, the free encyclopedia

In logic, proof by contradiction is a form of proof, and more specifically a form of indirect proof, that establishes the truth or validity of a proposition. It starts by assuming that the opposite proposition is true, and then shows that such an assumption leads to a contradiction. Proof by contradiction is also known as indirect proof, apagogical argument, proof by assuming the opposite, and reductio ad impossibilem. It is a particular kind of the more general form of argument known as reductio ad absurdum.[1][2]

G. H. Hardy described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."[

Tautology- 항진(恒眞)명제(tautology) ​

논리식 혹은 합성명제에 있어 각 명제의 참·거짓의 모든 조합에 대하여 항상 참인 것을 항진(恒眞)명제(tautology) 라고 한다.

 

Tautology : 진리표 에서 알 수 있는 바와 같이......

 

i) 가능한 모든 조건 아래에서 모든 진리치가 진이 되는 명제

이것은 원자명제 진리치에 상관없이 항상 진인 이런 명제를 항진명제 (tautology)라 한다.

 

일반적으로, 어떤 진리함수적 명제의 가능한 진리치가 모두 진일 때, 오직 그 때에만, 그 명제를 tautology 라 부른다.

 

항진명제는 그 논리적 형식상 결코 위가 될 수 없고 항상 진이어야만 한다.

 

 

 

 

 

 

 

1.    Question and comment about

Chapter 1: nested quantifiers

 

Questioned by Ahmad NABIL M. Kharudin  and Final OK by SGLee.

 

Answer :

 

 

 

2.   Question and comment about Chapter 2:

Questioned by NABIL and Final OK by SGLee.

 

 

 

Answer :

 

 

 

3.   Quizi 3

Questioned by 주유흠,

Answer by 이세영 and Final OK by SGLee, 나빌

 

 

Answer :

(Quiz 3 Problem 3)

 

 

 

 

(Quiz 1 Problem 3)

 

 

 

Final OK by SGLee, 나빌

 

 

4.   Ch3

Questioned by 주유흠, Answer by 나빌 and Final OK by SGLee

 

Answer :

 

 

 

 

5.   Ch3

Questioned by 나빌, Answer by Prof and Final by 이세영

 

 

Answer :

 

 

6.    

Questioned by Prof, Answer by 나빌

 


 

Answer :


7.    

7.

Questioned by 나빌

 


Answer by Prof

 

8.    

Homework Page 444 : Questions 14,15 and 25

Solution by 나빌


 

 

Question by 정유민

Answer by: 주경용.김민준.

 

Question by 이세영

Answer by prof. 이상구

Final by 김민규

 

Question by 양승환

 Answer by정유민

Final Answer by prof. 이상구

Question by 주경용

Answer by prof. 이상구

 다른 자료들을 찾는자 양승찬


 

6. Counting methods and the Pigeonhole principle

 

6.1 Basic Principles

 

동시에 다른 조건의 것들을 고르는 경우 : 각 항목의 경우의 수를 곱해 결과를 도출

Ex> 점심으로 전식, 메인, 음료의 가짓수를 한 가지씩 골라 정하는 경우

 

순서가 있는 것들을 배열하는 경우 : 들어갈 수 있는 항목들을 1씩 제해 가며 곱함

Ex>가,나,다,라 네 가지 문자를 순서를 정해 배열하는 것

 

6.2 Permutations and Combinations (순열과 조합)

 

Permutations 순열, n개에서 r개를 뽑아 순서를 주어 배열하는 방법의 개수, P(n,r)

P(n,r)=n!/(n-r)!

Ex> 6명 중 회장과 부회장을 한 명씩 선출하는 경우

Combinations 조합, n개에서 순서 없이 r개를 뽑는 방법의 개수, C(n,r)

C(n,r)=n!/{(n-r)!r!}

Ex> 6명 중 대표위원 두 명을 선발하는 경우

 

Catalan number

 

(0,0)과 (n,n)을 잇는 직선 아래쪽을 지나지 않고, (0,0)에서 (n,n)으로 가는     최단경로의 수

 

 

6.3 Generalized Permutations and Combinations

 

6.4 Algorithms for Generating Permutations and Combinations

6.5 Introduction to Discrete Probability

6.6 Discrete Probability Theory

 

6.7 Binomial Coefficients and Combinatorial Identities

 

 

6.8 The Pigeonhole Principle

 

Limited box – ways to arrange items

1st form

2nd form

3rd form

 

 

CH 6 QnA analysis

 

Questions & problems solving

6-1-13

6-2-2,7,8,13,16,19,22,23,24,36,39

6-3-1,10

6-6-21.22,23,24,25,26

6-7-3,6,22

6-8-4,7

 

 

 

 

Summary 25

 

Question or Examples 23

 

 

 

CH 6 example solving

Questions & problems solving

6-1-13

 

 

6-1단원은 경우의 수를 구하는 것의 기본 원칙을 다루며, 13번 문제는

6명으로 이루어진 위원회에서 3개의 서로 다른 직급을 분배하는 중, a혹은 d가 직급을 가지게 되는 경우의 수를 구하는 문제로 이 문제를 풀 수 있게 되면 6-1의 모든 내용을 아는 것이라 생각해 고르게 되었다.

풀이과정은 다음과 같다. 우선 a가 직급을 가지게 되는 경우의 수와 d가 직급을 가지게 되는 경우의 수를 더한 것에 ad모두 직급을 가지게 되는 경우의 수를 빼면 (중복되었으므로) 된다.

이는 동시에 발생할 수 있는 사건에 대한 경우의 수를 고르는 문제 유형에 해당한다.

 

계산식은 다음과 같다. A가 직급을 가지게 되는 경우의 수는 3*5*4로 서로 다른 직급의 수가 3개이므로 3을 곱해주고 나머지 두 자리에 a를 제외한 5명이 나눠 자리를 차지하는 경우의 수를 구한 것으로, d가 직급을 가지게 되는 경우 역시 동일하게 3*5*4이다.

여기다가 a와 d 모두 직급을 가지게 되는 경우를 빼야 하는데, 이 경우는 우선 두 명이 세 자리중 한 자리씩 차지할 경우의 수를 구하고 남은 자리에 4명의 남은 사람 중 한 명이 들어가는 경우를 곱하면 되는데, 전자의 경우 3*2로 서로 다른 3개증 2개를 고르는 방법의 수와 동일하다.

따라서 3*5*4*2-3*2*4 = 120-24 = 96가지이다.

 

이와 같이 동시에 발생할 수 있는 사건에 대한 경우의 수를 중복해서 고르는 문제 유형의 경우, 벤다이어그램으로 이해를 도울 수 있는데, 한 사건이 일어날 가능성 + 두번째 사건이 일어날 가능성 – 두 사건이 동시에 일어날 가능성으로 구할 수 있다.

 

 

질문에서 알 수 있듯, 6-1단원 문제 풀이의 핵심은 곱해서 구할 항목들을 가려내는 것이다.

 

교수님의 답변 그대로, 어떤 자리에 들어갈 지 정하는 것 (3)에 남은 두 자리에 5명 중 두 명이 들어갈 경우의 수 (5*4)를 곱하면 된다.

 

6-1장의 문제들은 대부분 동시에 일어나는 경우의 수를 곱하는 것만 제대로 하면 손쉽게 풀 수 있다.

 

6-2-7

6-2단원은 순열에 대해 다루며 그중 7번문제는 원탁에 순서를 주어 배열하는 유형의 문제이다. 풀이법은 단순히 (n-1)! 인데, 이것은 일렬로 나열하는 방식의 경우의 수인 n!을 n으로 나눈 수로, 원탁에 배열하는 경우 일렬로 나열하는 것과는 달리 회전해도 같은 배열이기 때문이다. 그러므로 한 칸씩 한 바퀴를 회전하는 경우의 수인 n을 나눠 줌으로써 구할 수 있다.

 

 

6-2-24


 

 

 

6-3-10

6-3에서 다루는 순열의 응용 문제이다. 경로 개수 구하기 문제로,

 

 

 

 

 

              3.2 정리를 이용하여 순서 배열 공식에 대입하면   (i+j+k)! / i! j! k! 가 된다.

 

6-7-6

 

6-8-4`

 

6-8-7

 

Pigeonhole 법칙으로 간단하게 증명 가능한 문제들이다.

SELECTIVE EXERCISES

6-1-8 (실생활 적용)

EXAMPLE _APPIED NUMBERING METHOD ON DAILY LIFE

 

6-3-4 (중복된 고르기 유형)

 

6-7-8

 

THEOREM 6.7.6

 

 

 

이항 정리 (binomial theorem) 의 증명과 이를 이용한 다른 정리

 

CH 6 summary

 

Summary

 

 

DEFINITION OF CH6-1, CH6-2

 

 

 

 

 

QUICK SUMMARY

 

CH6-1

곱셈 / 덧셈 / 포함배제원리를 활용한 문제들

-       각각의 원리를 적용해야 하는 상황들 파악하면 풀이 쉽다

-       곱셈: 동시에 일어나는 서로 다른 조건의 일들

-       덧셈: 별개로 일어나는 서로 다른 조건의 일들

-       포함배제원리: 교집합과 같이 두 상황을 더하는데 그 사이에 중복 개체가 있을 경우

 

CH6-2

순열과 조합

P(n,r)=n!/(n-r)!

C(n,r)=n!/{(n-r)!r!}

 

CH6-3

순열과 조합 (뽑아서 배열 / 순서없이 뽑음)

-       순서의 유무에 따라 순열과 조합 여부 구분

-       공식 적절히 활용

 

CH6-7

이항정리, 파스칼의 삼각형 등 정리와 증명 이해 필요

-       위 정리를 통해 새로운 정리를 유도하는 문제들

-       정리 뿐 아니라 증명 역시 숙지 필요

 

CH6-8

비둘기 집의 원리

-       주로 증명 문제가 많다

-       세 원리를 잘 숙지해서 증명에 적절히 사용하기

 

 

 

◆ Solve-Revise-Finalize (and Final OK)

Participation

1.    Number of your QnA participation ( 18 )

 

2.    I made some comments for these some new and wonderful idea for determinant properties. These can help for further studies.

 

 

 

 

1. Question about process and criteria of deciding proof way

 

Question

 

 

Answer

 

 

 

Finalization

 

 

증명법을 배우는 도중 증명법이 매우 다양함을 다시금 느꼈고, 그로 인해 어떤 상황에서 어떤 증명법이 적용되는지를 파악하면 문제를 푸는 시간이 많이 단축될 것이라는 생각이 들어 어떤 유형의 명제를 어떤 방식으로 적용해야 하는지에 대한 기준이 있을 까 궁금해서 질문하고 찾아보았다.

그 결과 파이널에 적은 것과 같이

 

1. 직접증명

2. 대우증명

- 원명제보다 대우명제가 증명하기 더 쉬운 경우

(원래 명제에서의 진리집합의 원소보다, 대우의 진리집합의 원소가 더 적을 때)

3. 귀류법

- 원명제를 있는 그대로 증명하기 어려운 경우, 기존의 전통적인 방식으로 증명을 진행하기 어려운 경우

- 원명제를 부정했을 경우의 모순을 비교적 쉽게 들 수 있을 경우

4. 수학적 귀납법

- 정수, 특히 자연수의 영역에 모두 해당되는 것을 보이라는 증명에 효과적

5. 모순 증명법

- 직접적으로 증명하기 어려운 경우, 수의 범위가 광범위한 경우

 

정도로 요약할 수 있었다.

 

2. Answer about induction proof

 

Question

 

 

 

Answer

 

 

 

Finalization

 

 

 

3. Final of chapter #1~4

 

Solution

 

 

Finalization

 

 

 

 

 

4. CH 4 preview

 

Question

 

 

Answer

예습 중 big oh / omega / theta notation에 대한 정의가 불명확해서 아이캠퍼스에 질문을 올렸는데 그 이후 수업을 듣고 교수님과의 질의응답 시간에 답을 알아서 의문점을 해결한 후 아이캠퍼스에 다시 답글을 달아 공유했습니다.

o(g(n)) -> big on

upper bound (상한 을 안다)

 

오메가(g(n)) -> omega

lower bound (하한 을 안다)

 

세타(g(n)) -> theta

 

(하한 과 상한 을 둘 다 안다 / 보다 더 정확한 범위를 안다)

 

 

5. CH 5 preview

 

Question

 

 

Answer

유클리디안 알고리즘의 내용은 이해가 갔지만 그 증명 방법이 궁금했습니다. 예습하는 중에 인터넷과 교안을 찾아 본 이후에 다시 이해가 가서 그 증명을 제 나름의 방식으로 정리한 이후 공유하였습니다.

 

6. Answer of CH 3 sequence Question

 

Question

 

 

 

Answer

 

 

Finalization

 

 

 

기호의 의미에 대한 질문에 답변을 달았는데, 단순한 내용으로 부등호에 대한 질문이었습니다.

 

 

7. Answer of Ch5 exapmle3.8

 

Question

 

 

 

Answer

 

 

유클리디안 알고리즘에 관한 질문에 답변을 단 내용으로, 유클리디안 알고리즘에 대한 설명과 한글로 풀이된 설명을 적어서 답변을 달았습니다.

 

 

8. ch6, ex 28,36,39

 

Question

 

 

 

Finalization

 

 

9. Question on Ch7 Tower of Hanoi

 

Question

 

 

 

Answer

 

 

점화식을 알아보는 방법에 대해 질문했는데, 교수님께서 답변을 달아주셨습니다. 점화식을 배움으로써 점화식인지 아닌지를 쉽게 알아차릴 수 있는 능력을 기를 수 있다는 말씀을 해주셨습니다.

 

 

10. summary on Ch7

 

Question

 

 

보충내용

 

천수현군 ch7 Summury ​

 

​Recurrence Relation (점화식)

: A sequence by giving the N-th value in terms of its predecessors

- The Fibonacci Sequence: Fn =Fn-1 + Fn-2 (n=>3), F1=1, F2=1

- Regularly compounded interest problem

- Cardinality of a power set

- N-bit strings problem (Divide solutions into 3 cases and write them as recurrence relations)

- Tower of Hanoi (Moving disks of various sizes)

- The Cobweb in Economics: Matching x-value and y-value to two Economics graphs in relation, we can find cobweb that spins around the graph

- Ackerman's Function : A(m,0) = A (m-1,1) , A(m,n) = A(m-1 , A(m,n-1)), A(0,n) = n+1

(Check them with computing websites)

 

Solving Recurrence Relations

1) iteration 2) linear homogeneous recurrence relations with constant coeffiient

 

1) iteration : Repeating recurrence relations for N, N-1, N-2 ...

2) linear homogeneous recurrence relations

An = c1An-1 + c2An-2 + ... + ckAn-k , ck != 0 

 

황병재군 ch7 Summury ​

 

​1. recurrence relation(점화식) : n번째 항이 선행항으로 결정되는 수열을 정의한다

ex) f​n​ = f​n-1​ + f​n-2

    ​f​n​이 n 번째 항,  f​n-1​, f​n-2​이  f​n​보다 앞에 있다는 뜻으로 선행항이라고 불린다.

    ​ 

 2. 점화관계풀이 

 

●​점화식에서 각 항이 ca​k 형식인 것을 선형(linear)이라고 하고 그렇지 않은 것을 비선형(nonlinear)이라고 한다 

ex) linear : c​kf​k​ + c​k+1​f​k+1​ + ...... + c​n​f​n​ = d 

                                       ( c​k​, c​k+1​, ​....​, c​n​, d = const)      nonlinear : c​n-2​f​n-2 * ​c​n-1​f​n-1 ​= f​n​   

(∴두 항이 곱하기로 되있음)

 

●​선형점화식에서 우변을 0으로 나타낼 ​수 있는 것을 

동차(homogeneous)라고 하고 그렇지 않은 것을 

비동차(nonhomogeneous)라고 한다

ex) c​kf​k​ + c​k+1​f​k+1​ + ...... + c​n​f​n​ = d​ ​​에서 d=0 이면 homogeneous

                                                                  d≠0 이면 nonhomogeneous

●선형 동차 점화관계에서 식을 n차 방정식으로 만들고 그해가 r​1​, r​2​, ..., r​k 이면 수열의 일반항은 a​n =cr​1​n​ + dr​2​n + .... + er​k​n으로 나타낼수있다.

ex)

c​1​f​n​ + c​2​f​n-1​ + c​3​f​n-2​ = 0 이라는 점화식을 

c​1​x​2​ + c​2​x + c​3​ = 0 방정식으로 만들고 그해가 r​1​, ​r​2​ 이면

 

​점화식의 일반항은 f​n ​= d​1​r​1​n​ + d​2​r​2​n​ 으로 나타낼 수 있고 

초기 값 f​1​, f​2​가 주어지면 대입하여 상수 d​1​, d​2​를 구할 수 있다.

 

 

함형빈군 ch7 Summury ​ 

 

7.1 점화식 소개

정의

A recurrence relation (점화식) defines a sequence by giving the nth value in terms of its predecessors. The nth value is given in terms of the immediately preceding value. In order for a recurrence relation to define a sequence, a “start up” value or values must be given. These start up values are initial conditions. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.

예시: Fibonacci, Hanoi Tower, Cobweb in Economics.

Fibonacci – 아래의 사이트에 가면 더 자세한 증명을 볼 수 있다.

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

 

Hanoi Tower - http://mathworld.wolfram.com/TowerofHanoi.html 해당 사이트에 가면 자세히 볼 수 있다.

Cobweb in Economics – 더 자세한 내용을 보고싶다면 아래 링크를 확인하세요.

https://terms.naver.com/entry.nhn?docId=1058339&cid=40942&categoryId=31812

 7.2 점화방식을 푸는 법.

간단한 예:

Initial이 2일 때 n번째 a는 n-1만큼 3을 곱하고 2를 더한 값이 나온다.

General method of solving linear homogeneous recurrence relation with constant coefficient는 미분방정식 때 차분방정식과 비슷한 방식으로 푼다.

 

양승찬군 

 

7.1 Introduction

 

Def) A recurrence relation for the sequence a​0​, a​1, ​.... is an equation that relates a​n ​to certain of its predecessors(a0 ~ a​n-1​). And initial conditions(a0, a1..) are given.

 

Ex) Fibonnacci Sequence f​n = ​f​n-1 + ​f​n-2, (n>=3). (f1 = 1, f2=1)

Ex) Tower of Hanoi a​n = ​2a​n-1 ​+ 1 = 2​n​ - 1

 

​

7.2 Solving Recurrence Relations

 

---------------------------------------------------------------------------

​Two Methods of solving recurrence relation 

(a) Iteration

(b) linear homogeneous recurrence relation with constant coefficient.

 

-------------------------------------------------------------------------

​Example 1) By iteration, solve the recurrence relation 

                                                a​n ​= a​n-1​ + 3.

The initial condition is

                                                 a1 = 2.

 

sol) Using given formula we can obtain a​n-1 ​= a​n-2​ + 3. Then the given formula can be written as like this. a​n​ = (a​n-2​ + 3) +3 = a​n-2​ + 3*2.

Using this process repeatably, we can get finally formula as

                                            a​n ​= a​1(n-[n-1]) ​+ 3(n-1)

And by the initial condition the recurrence relation is

                                            a​n = ​3(n-1) +2

-------------------------------------------------------------------------

​​Exmaple 2) Find an explicit formula for c​n​. The minimum number of moves in which the n-disk Tower of Hanoi puzzle can be solved. And the obtained the recurrence relation.(Using  

                                           c​n ​= 2c​n-1​ + 1


​and initial condition is c1 = 1.

 

sol) The way to solve is also by using iteration.

​c​n ​= 2​c​n-1 ​+ 1. By the given formula we can write c​n-1​ = 2c​n-2​ + 1. 

 

By using this, we can make other relation like this. 

​c​n ​= 2​c​n-1 ​+ 1 = ​2(2c​n-2​ + 1​) + 1 = 2(2c​n-2​) +2 +1

  = 2​2​(2c​n-3​ +1) + 2 + 1 = 2​2​(2c​n-3​) + 2​2 ​+ 2 + 1 = ... = 2​n-1​(c​1​) + 2​n-2​ + ... + 4 + 2 +1

  = (2​n​-1) / (2-1) = 2​n​ - 1

--------------------------------------------------------------------------

 

(b) linear homogeneous recurrence relation of order k 

 

​def) A linear homogeneous relation of order k ​​with constant coefficient is a recurrence relation of the form 

                              ​a​0 = ​c​1​a​n-1​ + ​c​2​a​n-2​ + ... + ​c​k​a​n-k, ​c​k​ ≠ 0

 

​​ex) S​n = 2S​n-1-1, f​n ​= f​n-1​ + f​n-2 

 

​Example 2.8 nonlinear recurrence relations 

                                   ​          a​n = ​3a​n-1​a​n-2​

 

​​Example 2.9 linear nonhomogeneous recurrences relation with constant coefficients 

                                             a​n - ​a​n-1​ = 2n

 

​Example 2.10 linear homogeneous recurrence relation with nonconstant coefficients 

                                             a​n​ = 3na​n-1

 

----------------------------------------------------------------------------------------

​​Example 2.13 Fibonacci sequence solved by "linear homogeneous recurrence relation of order k"

​The Fibonacci sequence is defined by the linear homogeneous second order recurrence relation

                                          f​n ​- f​n-1​ - f​n-2 ​= 0 (n>=3)

and initial condition f​1 ​= 1, f​2​ = 1.

 

​​sol) Using given formula and changing as linear homogeneous recurrence is needed.

Then we can wirte it as

                                         ​t​2 ​- t -1 = 0

​​Then by the qudratic formula t = (1±√5) / 2. 

Then we can write recurrence relation as

                                   f​n ​= b((1±√5) / 2)​n + d((1±√5) / 2)​n = 1

                                   f​1 ​= b((1±√5) / 2)​ + d((1±√5) / 2)​​ = 1

                                   f​2 ​= b((1±√5) / 2)​2​ + d((1±√5) / 2)​​​2

​​By solving this equation we can get b,d as 

                        ​               b = 1/√5​, d = -1 / √5​​

​​So the Fibonacci sequence is 

                                   f​n ​= (1/√5​)((1±√5) / 2)​n - (1 / √5)​((1±√5) / 2)​n  

 

 

 

11. Question on kuratowski’s Theorem

 

Question

 

 

 

보충자료

 

인터넷에서 찾아본 kuratowski 정리의 증명법

꽤 높은 수준의 증명법이라 완벽히 이해하지는 못했지만, 개략의 증명 과정에 대해 알 수 있었고, 다음에 한번 더 완벽히 이해해보고 싶다는 생각이 들었습니다.

 

 

12. Summary on Ch8

 

Question

 

 

 

 

13. summary on CH8 (group work)

 

8.5 representations of graphs  

​

그래프를 표현하는 방식과 동형 그래프에 대해 다룬다

 

1. adjacency matrix (인접 행렬)

​

인접 행각 정점들 간의 연결 상태를 행렬과 같은 형태로 나타내는 방법

정점의 개수가 n개일 때 인접 행렬 M은 n×n의 정사각 행렬 형태를 띤다.

 i행, j열의 값이 1이면 i와 j에 해당하는 정점이 인접해 있는 것이고, 그 값이 0이면 인접하지 않은 것이다.

i = j일 때, 한 점을 중심으로 한 고리의 개수 *2의 값을 가진다.

http://www.icampus.ac.kr/repository/attachfiles/operation/notice/dbsthwjdsj/2018_05_22_005658.PNG

 

 

왼쪽그래프를 인접 행렬로 나타내면 오른쪽의 행렬과 같이 나타내어진다.

 

인접 행렬의 특징

main diagonal 을 기준으로 대칭이다

만약 행렬A가 단순 그래프 G에 대한 인접 행렬이라면, A를 n번 거듭제곱하면 그래프 G에서 n번의 변을 거쳐 점에 다다를 수 있는 가짓수를 나타낸 행렬이다.


http://www.icampus.ac.kr/repository/attachfiles/operation/notice/dbsthwjdsj/2018_05_22_012016.PNG
증명

 

 

2. incidence matrix(접속 행렬) 

하나의 edge가 어떤 정점을 연결하고 있는 지 나타낸 행렬

가로축은 이름붙혀진 edge, 세로축은 정점으로 구성된다.

 

각 항목은 1혹은 0의 값을 가지게 된다. (연결될 경우 1, 연결되지 않을 경우 0 )

http://www.icampus.ac.kr/repository/attachfiles/operation/notice/dbsthwjdsj/2018_05_22_012722.png
그래프 G를 접속 행렬 M과 인접 행렬 A로 나타내었을 경우

 

 8.6 Isomorphisms of Graphs

 

동형 그래프란 모양이 달라도 같은 것으로 간주하는 그래프이며, 동형 관계의 두 그래프는 모양은 다르지만 같은 그래프이다.

http://www.icampus.ac.kr/repository/attachfiles/operation/notice/dbsthwjdsj/2018_05_22_013142.PNG
동형 그래프의 예

 

 

 

동형 그래프의 특징

 

만일 어떤 그래프 G1과 G2가 동형 관계에 있다면, 이를 G1 R G2라고 표기한다.

 

동형 그래프는 서로 같은 인접 행렬을 갖는다.

 http://www.icampus.ac.kr/repository/attachfiles/operation/notice/dbsthwjdsj/2018_05_22_112953.PNG 

증명

 

 

불변의 (invariant)특성 - edge, vertice의 개수 등 이 다르면 동형 그래프가 될 수 없다.

 

 

출처

DM ch8 lecture note

[네이버 지식백과] 인접 행렬 [adjacency matrix, 隣接行列] (IT용어사전, 한국정보통신기술협회)

 

 

 

March PBL comment

 

This is the first time that I have a good lecture with a PBL system. I am sure that I will write a report so that I can take a closer look at my learning attitude and have a lot of time to reflect on what I have learned so far. At first, uploading questions to the i-campus and discussing each other and creating the final project seemed awkward and difficult, but now I think I can freely share my ideas with others.

Thinking about things I've done so far I have some students who put up the things I learned in class during the school campus, so it seems natural to review them. Also, learning through communication with other students was better because I could see real-time new ideas. It seems to be very attractive to share each other's questions, answers and opinions.

In the future I would like to take a little more active participation in discussions, questions and answers.

◆ Final comment

[WANG ZHAOXIANG]

   First thing in my mind  team work is a good thing for everyone when we study a new knowledge . And also I am very thankful to our Professor and our classmate in my QA I can get my questions’s answer timely.  When I finish this PBL reports I have a Aprocess of knowledge again. When I see my QA one more time. And when I see classmate’s QA.  I am happy that I can solve problems and can do things efficiently in linear algebra course.

I want to add that thank you my all class mates who participated in QA and replies to me and asked questions and helped me in learning more and more.

This is the last assignment of this course and the first team assignment。Although in QA this class is like a big team, but in QA it is asking questions by yourself to find answer about  your questions or to solve the problems about others. But this assignment is more like a group to solve a problem the key to group work is that everyone can participate. And it becomes less difficult to work on issues that are very difficult for one person through group work. At the same time, the common learning experience of the members of our foreigner group in this class’s distinctive learning method is that we can better participate in the learning of recent courses in this lesson. Although we had some difficulties at first, we didn’t know what to do, but we gradually learned to participate in this class after I gradually learned the method of class.

This class is different than other class, in which not just the professor, but the students also play important role in the flow of learning of this class. The professor does teach in the class, but it is the students that need study in advance and find good questions to be discussed among them. This class teaches me that as a student, I need to study early for the lecture, for me to fully grasp full understanding of the learning.

 This class has taught me to start studying early and work hard to not procrastinate in my learning. Thanks to the professor guidance, I am able to change my attitude and lifestyle to become a better student.