Discrete Mathematics

SKKU Math Lectures and Labs

Name 이름 : 오 동 찬

Major and Student No 전공 및 학번 : 컴퓨터공학과

DM Ch 9, Trees

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

DM-Ch-9-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-9-Lab.html

(DM Ch 9, Part 1) https://youtu.be/v6wQeWmMBq8 (DM Ch 9, Part 2) https://youtu.be/gl1cD6-0prs

[Team 5] Ch 9. Solutions http://matrix.skku.ac.kr/2018-DM-Sol/Ch9/

Ch 9, (talk, 문제풀이 발표) https://youtu.be/nvwYSFwCoFo

(1) State more than 10 DM Definitions and concepts and Theorems what you learned from the first 9 Chapters. and State more than 9 things that you know/can/find after you studied the first 9 Chapters.

I. Euclidean Algorithm:

유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.

Example

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. => 42

1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. => 21

42는 21로 나누어떨어진다.

따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

78696 ＝ 19332×4 ＋ 1368

19332 ＝ 1368×14 ＋ 180

1368 ＝ 180×7 ＋ 108

180 ＝ 108×1 + 72

108 ＝ 72×1 ＋ 36

72 ＝ 36×2

따라서, 최대공약수는 36이다.

II. Big-O, Big-Omega, Big-Theta Notations:

1. 빅-오(Big-Oh) 표기법

2. 빅-오메가(Big-Omega) 표기법

3. 세타(Theta) 표기법

III. Bezout’s Theorem:

IV. Modulo Arithmetic:

• a ≡b (mod n )a ≡b (mod n )

• a와 b는 n으로 나눈 나머지가 같다는 뜻

V. RSA Algorithm:

RSA는 공개키 암호시스템의 하나로, 암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘으로 알려져 있다. RSA가 갖는 전자서명 기능은 인증을 요구하는 전자 상거래 등에 RSA의 광범위한 활용을 가능하게 하였다.

RSA는 두 개의 키를 사용한다. 여기서 키란 메시지를 열고 잠그는 상수(constant)를 의미한다. 일반적으로 많은 공개키 알고리즘의 공개키(public key)는 모두에게 알려져 있으며 메시지를 암호화(encrypt)하는데 쓰이며, 암호화된 메시지는 개인키(private key)를 가진 자만이 복호화(decrypt)하여 열어볼 수 있다. 하지만 RSA 공개키 알고리즘은 이러한 제약조건이 없다. 즉 개인키로 암호화하여 공개키로 복호화할 수도 있다.

공개키 알고리즘은 누구나 어떤 메시지를 암호화할 수 있지만, 그것을 해독하여 열람할 수 있는 사람은 개인키를 지닌 단 한 사람만이 존재한다는 점에서 대칭키 알고리즘과 차이를 가진다.

RSA는 소인수 분해의 난해함에 기반하여, 공개키만을 가지고는 개인키를 쉽게 짐작할 수 없도록 디자인되어 있다.

보다 이해하기 쉬운 예를 들자면, A라는 사람에게 B라는 사람이 메시지를 전하고자 할 때 B는 A의 열린 자물쇠를 들고 와 그의 메시지를 봉인(공개키 암호화 과정에 해당)하고, 그런 다음 A에게 전해 주면, 자물쇠의 열쇠(개인키에 해당)를 가지고 있는 A가 그 메시지를 열어보는(개인키 복호화 과정에 해당) 식이 된다. 중간에 그 메시지를 가로채는 사람은 그 열쇠를 가지고 있지 않으므로 메시지를 열람할 수 없다.

VI. Time Complexity:

계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다.

VII. Bubble Sort:

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

Pseudo CODE:

procedure bubbleSort( A : list of sortable items ) defined as:

for each i in 1 to length(A) do:

for each j in length(A) downto i + 1 do:

if A[ j ] < A[ j - 1 ] then

swap( A[ j ], A[ j - 1 ] )

end if

end for

end procedure

VIII. Insertion Sort:

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다. 선택 정렬이나 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

Pseudo CODE:

insertion_sort ()

{

int i ,j ,remember ;

for (i =1 ;i <n ;i ++)

{

remember =data [(j =i )];

while (--j >=0 &&remember <data [j ]){

data [j +1 ]=data [j ];

data [j ]=remember ;

}

IX. Cartesian Product:

집합론에서, 곱집합 (영어: Cartesian product)는 각 집합의 원소를 각 성분으로 하는 튜플들의 집합이다. 곱집합은 집합의 다양체에서의 직접곱이며, 집합의 범주에서의 곱이다.

X. De morgan’s Law:

드 모르간의 법칙 (De Morgan's laws)은 수리 논리학이나 집합론에서 논리곱(집합의 공통 부분), 논리합(집합의 모든 부분), 부정(여집합) 연산간의 관계(드 모르간의 상대성이라고 부름)를 기술하여 정리한 것으로, 수학자 오거스터스 드 모르간의 이름을 따서 드 모르간의 법칙이라고 한다.

XI. Equivalence classes:

An equivalence class is defined as a subset of the form , where is an element of and the notation "" is used to mean that there is an equivalence relation between and . It can be shown that any two equivalence classes are either equal or disjoint, hence the collection of equivalence classes forms a partition of . For all , we have iff and belong to the same equivalence class.

A set of class representatives is a subset of which contains exactly one element from each equivalence class.

For a positive integer, and integers, consider the congruence , then the equivalence classes are the sets , etc. The standard class representatives are taken to be 0, 1, 2, ..., .

XII. Permutation & Combination:

Definition 2.1

A Permutation of distinct elements , , is an ordering of the elements , , .

Definition 2.8

-permutation of (distinct) elements

Theorem 2.10

The numbers of -permutation of a set of distinct objects is

, .

Definition 2.15

Given a set   containing   (distinct) elements,

(a) An -combination of   is an unordered selection of -elements of

      (i.e. an    -element subset of ).

(b) The number of -combination of a set of   distinct elements is   or .

XIII. Pigeon-Hole Principle:

The Pigeonhole Principle (the Dirichlet Drawer Principle or the Shoe Box Principle ) is sometimes useful in answering the question: Is there an item having a given property? When the Pigeonhole Principle is successfully applied, the principle tells us only that the object exists; the principle will not tells us how to find the object or how many three are.

Figure 6.8.1 pigeons in pigeonholes.

Pigeonhole Principle (1st Form)

If pigeons fly into pigeonholes and , some pigeonhole contains at least two pigeons.

XIV. Catalan Number:

XV. Recurrence Relation:

XVI. Tower of Hanoi:

(QnA에 제가 올린 내용을 가져왔습니다.)

하노이 탑이란

위 사진과 같이

퍼즐의 일종으로서 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있습니다.

두 가지 조건을 만족시키며 한 기둥에 꽂힌 원판들을 순서 그대로 다른 기둥으로 옮겨서 다시 쌓게 됩니다.

두 가지 조건이란

1. 한 번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

원판의 갯수를 n개라 하면 보통 2ⁿ-1의 이동으로 원판을 모두 옮길 수 있습니다.

(*이 때 2ⁿ-1 는 메르센 수라고 불립니다 - 추후 메르센 수에 대해 간단히 정리하여 올리겠습니다.)

하노이의 탑 문제는 Recursive, 즉 재귀 호출을 이용하여 풀 수 있는 예제로 Recursive 함수를 만드는 알고리즘의 예제로 피보나치 수와 같이 자주 사용합니다.

간단히 C코드를 올려보도록 하겠습니다.

감사합니다!

출처:

1.https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%9

XVII. Euler’s Cycle:

흔히 우리가 알고 있는 한붓그리기가 가능한 그래프를 오일러 싸이클이라고 합니다.

유명한 예로 쾨니히스베르크의 다리 문제가 있습니다.

XVIII. Dijkstra’s Shortest-Path Algorithm:

특히 알고리즘 문제에서 심화 과정으로 많이 나오는 다익스트라 알고리즘은 컴퓨터공학적으로 굉장히 중요한 부분입니다. 네트워크 등 많은 분야에서 사용되기 때문에 중요하게 익혀야 하는 개념입니다.

XIX. N-Cube(Hypercube):

The hypercube is a generalization of a 3-cube to dimensions, also called an -cube or measure polytope. It is a regular polytope with mutually perpendicular sides, and is therefore an orthotope. It is denoted and has Schläfli symbol .

The following table summarizes the names of -dimensional hypercubes.

XX. Spanning Trees:

Graph에서 모든 Vertices를 포함하고 있는 부분 그래프를 Spanning Tree라고 합니다. 모든 Edge를 포함할 필요 없이 모든 Vertices만 포함하면 됩니다. 이를 확장하여 MST(Minimum Spanning Tree) 알고리즘을 배우기도 합니다.

XXI. Binary Trees:

Binary Tree는 각각의 노드가 최대 두 개의 Child 노드를 가지고 있는 트리 형태의 Data Structure입니다. 맨 위의 노드를 Root라고도 하며 Height라는 높이를 가지고 있는 것이 이 자료구조의 특징입니다.

XXII. Tree Traversal & Prefix, Postfix Notation:

Tree의 순차 방문 과정에서 Pre, Post, In- Order 방식은 각각 Left Child먼저, Right Child 먼저, Parent Node 먼저를 뜻합니다.

또 Prefix, Postfix Notation은 수식 표기법으로써 연산자와 피연산자의 표시 순서에 따라 달라지게 됩니다.

XXIII. Isomorphisms of Trees:

XXIV. (In Addition) Binary Search Tree:

Binary Search Tree는 다음의 속성을 가지는 Binary Tree형태의 자료구조 입니다.

1. 각 노드에 값이 있다.

2. 노드의 왼쪽 Child Tree에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

3. 노드의 오른쪽 Child Tree에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있다.

4. Subtree는 각각이 Binary Search Tree여야 한다.

RB Tree와 다른 점은 트리의 구조에 따라 시간복잡도가 O(log n)에서 O(log n)으로 변화할 수 있다는 것입니다. 트리의 구조가 최악일 경우, 즉 한 쪽으로만 쏠려있을 경우 시간복잡도가 최대가 됩니다.

XXV. (In Addition) Red-Black Trees:

레드 블랙 트리는 Self-Balancing Binary Search Tree로써 효율적이고 우수한 실행 시간을 보이는 자료구조입니다. 항상 O(log n)의 시간복잡도로 Insert, Delete, Search를 하는 것이 특징입니다.

다만 복잡하고 고려해야 할 조건이 있어 어렵게 다가올 수 있는 자료구조 입니다.

RB TREE의 몇가지 조건을 올리겠습니다.

1. 노드는 레드 혹은 블랙 중의 하나이다.

2. 루트 노드는 블랙이다.

3. 모든 리프 노드는 블랙이다.

4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)

5. 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

REFERENCES

[1] http://ko.wikipedia.org/wiki

[2] http://mathworld.wolfram.com/EquivalenceClass.html

[3] http://matrix.skku.ac.kr/2018-DM/

(2) 본인이 본 강좌를 수강하면서 특히 기억나는 내용 :

1. RSA 관련하여 전공 수업(최형기 교수님의 Security)에서 배웠던 내용을 참고하여 QnA에 정보글로 올렸는데 교수님께서 그와 관련하여 Comment 올려 주신게 기억에 남습니다. 또한 저와 같은 과 친구들도 있고 그 중 1학년 학생들도 있는데 그 친구들이 이산수학이 여러 분야에서 다양하게 활용 될 수 있지만 특히 컴퓨터공학도에게 꼭 필요한 부분인 것을 알아서 수업 때 조금 더 동기부여가 될 수 있다고 생각합니다. 또 학기 초반에 북한 수학자들도 Global Mathematical Notation을 쓰는지 궁금하여 올린 질문이 있었습니다. 사실 터무니 없는 질문이지만 교수님께서 정성스레 답변 주신 것에 큰 감동을 받았고 그 이후 QnA에 질문 올리는 것의 내용에 상관없이, 두려움 없이 질문을 할 수 있었습니다. 또 김희성 군이 푼 문제를 제가 잘못 보고 혼란을 준 경우도 있었는데 이 경우 교수님과 김영철 학생을 비롯한 네 명이서 QnA를 통한 의사소통으로 서로의 오류를 찾고 고치는 과정이 굉장히 뿌듯하기도 하고 마음에 와 닿았습니다. 얼굴 한 번 본 적 없는 동료이지만 같이 대화하며 해결점을 찾아나가는 과정에서 이 수업의 가치를 다시 한 번 느낄 수 있었던 것 같습니다.

2. 교수님과의 면담 후 QnA로 학우들과 공유한 것이 기억에 남습니다. 그 내용을 간략히 올립니다.

>> 교수님께서 정말 좋은 말들을 많이 해주셨는데, 제가 깨달은 것은 PBL Report의 필요성입니다.

사실 대부분의 학우분들은 한 학기가 지나면 혹은 1년이 지나면 그간 배웠던 과목들의 세부 내용을 잊어버리는 경우가 많습니다. 예를들어 저번학기에 공학수학1을 배우고 요번 학기에 공학수학2를 수강할 때 공수1 내용이 기억안나 다시 찾아보는 경우가 있을 것 입니다. 이는 저희가 여태까지 Pass를 위한, 학점만을 위한 수업을 해왔기 때문입니다. 저장된 강의노트라든지 교과서가 있으면 쉽게 찾아볼 수 있고 혹은 구글링으로도 찾아볼 수 있겠지만, 만약 저희가 PBL Report를 통해 정리해놨다면 어떨까요? 본인이 한 학기동안 배운 내용 전체가 하나의 문서 File을 통해 드라이브에 저장되어 있다면, 우선 언제 어디서든 열어보고 확인할 수 있을 것 입니다. 또한 본인이 직접 해 보고 적은 내용이기 때문에 그 학기에 학습한 내용이 더욱 세세하고 정확하게 기억 날 것 입니다. 이는 단순히 구글링을 통해 간단히 정보를 찾아내는 것과는 다르게 한 학기의 기억 전체를 떠올리게 할 수 있을 것입니다. 아마 취업을 준비하게 되면 저희는 면접을 대비하여 전공 공부를 다시금 하게 될 것 입니다. 만약 모든 전공과목에 대해 PBL Report로써 정리되어 있다면, 우리는 아주 짧은 시간안에 그 과목의 전체 내용을 쉽게 다시 상기할 수 있을 것입니다. 결국 한 학기가 끝난 후, 졸업 후, 10년 후에도 Computer라는 좋은 저장매체에 PBL Report가 깔끔하게 정리된 채 저장되어 있다면, 우리는 언제든 잊지않고 우리가 해본 모든 내용을 찾아볼 수 있는 것입니다. 아마 대부분 130학점을 졸업 때 까지 들으실텐데, 이 130학점을 좀 줄이고 대부분의 전공과목에 PBL Report형식이 도입이 된다면 우리는 대학교라는 곳에서 진정한 지식을 배우고, 미래에도 언제든 다시 공부할 수 있는 좋은 본인만의 자료를 생산하여 보유 하게 될 것입니다. 또 이 전까지는 여러 문제를 '푸는데' 만 집중했다면 지금은 문제 자체의 개념을 숙지한 후 푸는 것은 여러 '도구'를 이용해 더욱 실제적인 예시를 풀면서 새로운 지식을 창출하는 것에 초점을 맞추고 있습니다. 이중,삼중 적분 문제 등 매우 복잡한 문제에서 우리가 코드 사용법과 문제의 원리만 알고 있다면 어떠한 복잡한 수가 나와도 매우 빠르게 답도 내고 직접적으로 확인하도록 그래프까지 매우 빠르게 그릴 수 있습니다. 아마 중고등학교 교육과정을 쭉 따라온 저희들에겐 익숙하지 않은 방법일 수 있습니다. 하지만 학교가 아닌 사회에서 이러한 문제들을 접한다면 Textbook의 예제처럼 답이 딱 떨어지는 문제는 없을 것 입니다. 오히려 손으로 계산하기 불가능 할 것 입니다. 그렇지만 여러 '도구'를 이용해 손쉽게 계산하고 눈에 보이도록 그래프 등의 결과까지 만들어낸다면, 어떠한 문제라도 좋은 결과를 도출 할 수 있을 것입니다. 만약 우리가 위의 방법을 익히고 나간다면 하버드 대학 졸업생 에게도 꿀릴 것 없는 경쟁력을 가지게 될 것입니다. 저 같은 경우 ABEEK 요건 충족을 하기 위해 이산수학을 듣게 되었지만, 이산수학 수업을 통해, 또 교수님과 학우분들의 지식을 통해 정말 많은 것을 배우는 것 같습니다. 단순히 과목을 배우는게 아니라 어떻게 공부할지, 어떻게 생각할지를 배우고 있는 것 같아서 항상 감사할 따름입니다.

또 추가로 교수님의 수업 후 기억에 남는 부분이 있어 그 부분도 공유하고자 합니다

(3) 동료와 같이 DM 강좌를 (action learning) 학습 하면서 배우거나 느낀 점은?

‘동료와 같이’ 한다는 것이 요즘 대학생들에게는 어색할 것이라 생각합니다. 왜냐하면, 모두들 좋은 성적을 얻기 위해 서로를 견제하고 경쟁 상대로 생각하기 때문입니다. 하지만 이상구 교수님의 이산수학 강의는 그렇지 않았습니다. 특히 저는 서로를 성적으로 경쟁하는 상대라는 것을 완전히 잊고 같이 성장해가는 동료로서 인식하게 되었습니다. 물론 성적은 상대적으로 평가가 되겠지만 궁극적인 목표는 좋은 성적이라기 보단 내가 새로운 지식을 얻고 발전해나가는 것임을 깨닫게 되었습니다. 사실 저 또한 여태까지 동료와 의사소통하는 것을 꺼리고 ‘내 성적만 좋으면 되지’라는 개인주의적 생각이 강했습니다. 하지만 여러 동료들과 QnA 등 여러 방식을 통해 의사소통하고 서로의 지식을 공유하고 또 교수님께서 여러 방면으로 도움을 주면서 이 수업이 진정한 ‘지식 함양의 장’이라는 것을 알게 되었습니다. 처음에는 다른 수업들보다 할게 많고 또 부담도 있었지만 매일 꾸준히 QnA를 확인하고 모르는 것을 물어보고 다른 동료의 문제를 Finalize 및 Revise 하면서 ‘이런게 진짜 배움이구나’라는 생각을 가지게 되었습니다. 또 모르는 사람과 한 조가 되어 서로를 천천히 알아가고 수업시간에 열의를 가지고 참여하는 다른 친구들을 보면서 저 또한 스스로를 가다듬어 가면서 지식은 물론 인성 또한 길러가고 있는 제 자신을 발견했습니다. 성균관대학교도 우리나라를 넘어 이제 전 세계가 주목하는 일류 대학으로서, 이러한 학생들의 실제적인 발전을 위해, 더욱 Action Learning을 추구하고, 수업 방식을 점차 바꿔가면서 진정한 Global Leader를 기르기 위해 노력해야 한다고 생각합니다. 성적으로 모든 것을 평가받고 성적 하나만을 위해 더욱 더 개인주의로 빠져들게 하는 현대 한국 사회 및 고등 교육 과정에서 이러한 Action Learning 및 Flipped Learning은 한줄기 빛이며 이러한 학습을 통해 학업의 진정한 목적을 깨닫고 점차 발전해나가는 모습이 생겼으면 좋겠습니다.

또한 서로의 경험을 공유할 수 있다는 것은 매우 좋은 기회인 것 같습니다. 각자가 20년이 넘게 다른 환경에서 살아왔다는 것은 저와는 다른 경험과 기회가 있었다는 것입니다. 그런 사람의 경험을 듣고 제 새로운 경험으로써 받아들인다면, 그 사람의 인생의 길을 간접 경험하고 그만큼의 경험치가 쌓이게 된다고 생각합니다. 그래서 QnA나 수업에서 조별 토론을 통해 다른 학우들의 경험을 듣는 것은 정말 행복한 시간이었습니다. 이제 곧 학기가 끝나가는데, 이산수학에서의 3개월은 정말 잊지 못할 것 같습니다. 또 이 수업을 통해, 교수님을 통해, 학우들을 통해 배웠던 내용과 경험을 이용하여 추후 성균관대학교의 자랑스러운 일원으로서 학교를 빛내고 싶습니다.

1. Chapter 9 문제 풀이

● Solution과 문제를 같이 올려 문제를 참여하지 못 하는 학생들이 Solution을 보고 Chapter 9을 공부할 수 있게 진행 합니다.

● 각 문제를 Finalize시 학우들의 Comment를 달게 하여 학우분들의 느낀점과 생각을 다 같이 공유하고자 합니다.

2. Chapter 9 내용 정리

● 교수님께서 올리신 Lecture Note와 Google 검색을 통해 Chapter 9에 사용된 이론과 개념을 한 번에 정리하고자 합니다.

3. Chapter 9과 연관된 내용 찾기

● Chapter 9이 Tree인 만큼 컴퓨터공학과 연결되는 부분이 많을 것입니다. 그렇기에 Tree와 관련된 여러 코드들을 찾아보고 정리한 후 그 내용들이 컴퓨터공학적으로 어떻게 활용되고 사용되는지 추합하고자 합니다.

3장. Your PBL 참여 부분

Part 1: 수업 내용 관련하여 답변을 얻은 일반 유의미한 질문들 [Part 1: Your meaningful questions in QnA which you had you got the Final answer.]

◆ Number of your QnA participation upto the Due date.(157개)

Comment: 저의 실수로 김희성 학우가 푼 문제 말고 다른 문제를 Revise하여 혼선이 있었습니다. 충분히 김희성 학우는 기분이 안 좋을 수 있음에도 정중히 교수님께 확인을 부탁드렸고 저도 저의 실수를 발견할 수 있었습니다. 그 후 제가 올린 사과문을 교수님께서 인용하여 Post 해주시기도 했습니다.저의 실수로 인해 만들어진 혼란이었지만 김희성 학우는 물론 교수님까지 활발한 의사소통을 통해 오류를 잡아나가는 것을 보며 진정한 동료로서의 수업동료와 교수님의 진심어린 관심까지 느낄 수 있었던 부분이었습니다. Action Learning이 이런 점에 있어 큰 도움이 된다 생각합니다. 다른 수업에서는 서로의 잘못을 일부러 찾아내고 그것을 이용해 헐뜯기 까지 하는 수업이 있는 반면에 이산수학 수업은 서로의 발전을 위해 서로 협력하고 도와주는 것 같아 큰 감동을 느낄 수 있었습니다.

Comment: 고차원의 영역을 인간이 상상할 수 없기에 그 부분에 항상 궁금증이 있었습니다. 교수님의 설명을 통해 확 와닿게 된 점은, 수학자들이 생각하는 방식과 수학의 필요성입니다. 고차원 공간을 우리가 아직은 직접 볼 수 없어도 수학적 지식을 통해 예측하고 생각하는 것 자체가 고차원 공간을 볼 수 있는 미래로 향해 가는 것이라고 생각합니다. 이렇게 느끼고 나니 수학의 필요성을 더욱 느끼게 되었습니다. 또 인류의 발전이 결국 인간의 호기심으로 인해 발전해가고 있다는 것을 느끼게 되었습니다.

Comment: 순열과 조합을 고등학교 때 배우는데, 그 배우는 순서에 관한 질문이었습니다. 제가 개인적으로 학생들 과외를 꾸준히 진행해오고 있는데 항상 순열을 먼저 배우고 조합을 먼저 배우는 것에 궁금증이 있었습니다. 조합에 순서를 주는게 순열이라 생각했기 때문입니다. 하지만 전종문 학우와 특히 학원을 운영하신다는 전수호 학우님의 친절한 설명 덕분에 그 당위성을 알고 깨닫게 되었습니다.

Comment: Pigen-Hole Principle에 관한 질문이었습니다. 컴퓨터공학에서 배우는 경우가 있는데 실생활에 적용되는 부분이 궁금했습니다. Mohammad학우가 친절하고 정확하고 자세하게 예시를 올려주어 크게 도움이 됐습니다.

Part 2 : Finalize 된 문제들

p.197, Problem 4 (Chapter Self-Test)

Solved by 오동찬 Date: 2018.09.27

Finalized by 서명원 Date: 2018.09.27

Re-Finalized by 오동찬 Date: 2018.09.29

Final OK by TA Date : 2018. 10. 02

Problem

4. For the Hash function (https://en.wikipedia.org/wiki/Hash_function)

h(x) = x mod 13,

show how the data

784, 281, 1141, 18, 1, 329, 620, 43, 31, 684

would be inserted in the order given in initially empty cells indexed 0 to 12.

+) In hash function, my using modulo operation, we can get output h(x) by input x. This means that we can index inputs to different outputs. Additionally, by choosing modulo number, in this case 13, we can put data to certain range of indexed(in this case 13-1 = 12 cases).

So, in this problem we get hash outputs(empty cells) from given data and stored them to 13 different empty cells.

Solution

By mod operation, we insert data as an x and get h(x) (or y) result.

(x,y means "store item x in cell y.")

(784, 4), (281, 8), (1141,10) (18,5), (1,1), (329, 6), (620, 9), (43, 7), (31, 11), (684,12) □

Hashing variable-length data[https://en.wikipedia.org/wiki/Hash_function)

When the data values are long (or variable-length) character strings—such as personal names, web page addresses, or mail messages—their distribution is usually very uneven, with complicated dependencies. For example, text in any natural language has highly non-uniform distributions of characters, and character pairs, very characteristic of the language. For such data, it is prudent to use a hash function that depends on all characters of the string—and depends on each character in a different way.

In cryptographic hash functions, a Merkle–Damgård construction is usually used. In general, the scheme for hashing such data is to break the input into a sequence of small units (bits, bytes, words, etc.) and combine all the units b[1], b[2], …, b[m] sequentially, as follows

S ← S0; // Initialize the state.for k in 1, 2, ..., m do // Scan the input data units: S ← F(S, b[k]); // Combine data unit k into the state.return G(S, n) // Extract the hash value from the state.

This schema is also used in many text checksum and fingerprint algorithms. The state variable S may be a 32- or 64-bit unsigned integer; in that case, S0 can be 0, and G(S,n) can be just S mod n. The best choice of F is a complex issue and depends on the nature of the data.

Comment: Hash Table의 뜻과 그를 이용한 간단한 문제 풀이 였습니다. 또한 교수님과 다른 동료들의 추가적 정보로 Hash Table이 어떻게 쓰이는지 또 기본 Algorithm은 무엇인지 학습할 수 있었고 Hash Table의 사용 이유도 추가적 학습을 통해 알 수 있었습니다.

Page 64 problem 10

solved by 금상인 Date 2018.09.20

finalized by 오동찬 Date 2018.09.20

Final OK by TA Date 2018.10.04

p64 problem 10

Problem

Write the converse and contrapositive of the proposition of problem 9.

Solution

Converse : If Leah studies hard, she will get an A in discrete mathematics. (q -> p)

Contrapositive : If Leah doesn't study hard, she will not get an A in discrete mathematics.

(~q -> ~p) ■

Comment: 명제가 무엇인지 또 명제의 역, 가정, 대우 등이 무엇인지에 대해 중,고등학교 때 배웠던 내용을 상기하여 풀 수 있었던 문제였습니다.

p64 Problem 19

Finalized by 오동찬 Date : 2018.09.30

Final OK by TA Date : 2018.10.04

Let P(n) be the statement

n and n+2 are prime.

In Exercises 19 and 20, write the statement in words and tell whether it is true or false

Problem 19

∀n P(n)

Solution

The given statement means that "For all positive integers n,n and n+2 are prime.".

In this statement there is an counterexample such as n = 13.

Thus, the proposition is false. ■

Comment: Mathematical Notation을 이해하고 그에 맞는 내용을 Sentence로 옮겨 적을 수 있는 능력을 키우는 문제였습니다.

124 Problem 16 Solved by 오동찬 Date 2018.9.27

Revised and Finalized by 정호진 Date 2018.9.27

Final OK by SGLee

Use mathematical induction to prove that the statements in Exercises 13-16 are true for every positive integer n.

Ch 2, p124 , Problem 16.

Use mathematical induction to prove that the statements in Exercises 13-16 are true for every positive integer n.

16. 2^(n+1) < 1+(n+1)2^n

Solution

(1) Basic step:

If n =1

2^2 < 1+2*2^1

=> 4<5

So the statement is true for n=1 .

(2) Inductive step: Assume that it is true for k=n

[Show it is true for k=n+1 ] that is 2^(n+1) < 1+(n+1)2^n

LHS= 2^(n+2) = 2 · 2^(n+1) < 2 [1+(n+1)2^n]

=> 2^(n+2) < 2+(n+1)2^(n+1) = 1 + [1+(n+1)2^(n+1)]

=> 2^(n+2) < 1 + [2^(n+1)+(n+1)2^(n+1)]

=> 2^(n+2) < 1+ (n+2)2^(n+1) .

Therefore we have shown that 2^(n+2) < 1+(n+2)2^(n+1) .

By mathematical induction, 2^(n+1)<1+(n+1)2^n is true for every positive integer n. ■

Comment: 귀납적 방법으로 특정 명제를 증명하는 법을 익히고 증명하는데 있어 정확한 설명과 수식을 통해 그 완성도를 높이는 법을 배운 문제입니다.

Final OK by SGLee , p124 Problem 17 엄자균 오동찬 finalized by 강병훈 오동찬

p124 Problem 17 solved by 오동찬

finalized by 오동찬

Page : 124 Problem 17 Solved By : 엄자균 Date:27/ Sep/2018 17.

finalized by :강병훈 Date:27/ Sep/2018 17.

Final OK by SGLee

Problem

Find the quotient q and remainder r as in Theorem 5.6 when n = 101 is divided by d = 11

Solution

By dividing n = 101 by d = 11, 101 = 9*11 + 2 we can get the quotient 9, and its remainder 2.

Thus q = 9, r = 2. ■

Page : 124 Problem 17 Solved By : 엄자균 Date:27/ Sep/2018 17.

finalized by :강병훈 Date:27/ Sep/2018 17.

Final OK by SGLee

Find the quotient q and remainder r as in theorem 5.6 when n=101 is divided by d=11.

Solution

DM Ch. 3, Functions, Sequences, and Relations

DM-Ch-3-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-3-Lab.html

Theorem 5.6

Quotient-Remainder Theorem

If and , , there exist integers (quotient) and (remainder) satisfying

.

and are unique; that is, if

and

then and .

Let

Show that is nonempty.

n = 101, n ≧ 0 , then

so .

Suppose that .

Since is a positive integer, .

Thus

In this case, .

Therefore is nonempty.

Since is nonempty set of nonnegative integers,

by Well-Ordering Property,

has a smallest element, which we denote .

We let denote the specific of for which . Then

Since , . [Show that .] (BWOC) Suppose that . Then

Thus . Also .

But is the smallest integer in .

This contradiction shows that .

Shown that if and , , there exist integers and satisfying

We turn now to the uniqueness of and . Suppose that

and .

We must show that and .

Subtracting the previous equations, we obtain

which can be rewritten

The preceding equation shows that divides .

However, because and ,

But the only integer strictly between and divisible by is .

Therefore,

Thus,

hence

The proof is complete. □

So, when d=11, 101= n = dq + r has only one solution and

101= = 9×11＋2 where q = 9 and r = 2 ■

Comment: 간단한 계산을 통해 나눗셈의 몫과 Remainder를 구하는 문제였습니다. 또한 다른 동료들과 교수님의 추가적 Solution을 통해 Quotient-Remainder Theorem을 익히고 세밀한 풀이법을 익힐 수 있었습니다.

p.197, Problem 4 (Chapter Self-Test)

Solved by 오동찬 Date: 2018.09.27

Finalized by 서명원 Date: 2018.09.27

Re-Finalized by 오동찬 Date: 2018.09.29

Final OK by TA Date : 2018. 10. 02

Problem

4. For the Hash function (https://en.wikipedia.org/wiki/Hash_function)

h(x) = x mod 13,

show how the data

784, 281, 1141, 18, 1, 329, 620, 43, 31, 684

would be inserted in the order given in initially empty cells indexed 0 to 12.

So, in this problem we get hash outputs(empty cells) from given data and stored them to 13 different empty cells.

Solution

By mod operation, we insert data as an x and get h(x) (or y) result.

(x,y means "store item x in cell y.")

(784, 4), (281, 8), (1141,10) (18,5), (1,1), (329, 6), (620, 9), (43, 7), (31, 11), (684,12) □

Hashing variable-length data[https://en.wikipedia.org/wiki/Hash_function)

Final OK by SGLee Page 198 problem 14 solved by 서명원 finalized by 오동찬

Page.198 problem 14 (chapter self-test)

solved by 서명원

finalized by 오동찬

Final OK by SGLee

Problem

14. Given that the relation

{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)}

is an equivalence relation on {1,2,3,4},

find [3], the equivalence class contaning 3.

How many (distinct) equivalence classes are there?

Solution

Draw graph with above problem set.

In the graph above, we can see that we have two possible set can go to {3}.

So, [3] = {3,4} =[4] and [1] = {1, 2} =[2] .

There are two equivalence classes. ■

Comment: Graph를 통해 집합들 간의 관계를 파악하는 문제였습니다. 또한 서명원 학생의 정확한 그림을 통해 그 이해가 쉽고 제가 Finalize 하는데 큰 도움이 되었습니다.

Fianl OK by SGLee, Page 198 Problem 19 Re-Finalized by 오동찬 9/10 pts

P198 Problem 19

Solved by 오동찬

Finalized by 만우흠

Re-Finalized by 오동찬

Exercises 17-20 refer to the relations

R₁= {(1,x), (2,x), (2,y), (3,y)},

R₂= {(x,a), (x,b), (y,a), (y,c)}.

Problem 19

Find the matrix product A₁A₂.

Solution

Comment: Matrix Relation을 통해 Matrix 자체를 구하고 두 Matrix의 Product를 구하는 문제였습니다. 푸는 과정 중에 교수님께서 여러 번 수정해주셔서 좀 더 완벽한 Finalize를 할 수 있었던 문제입니다.

Final OK by SGLee (다시 고쳐봅니다)Page 198 Problem 20 모하메드 Re-Finalized by 오동찬

Page 198 Problem 20

Solved by 오동찬 : 2018.09.27

Finalized by Muhammad/모하메드 2018.09.28

Re-Finalized by 오동찬 2018.09.29

Final OK by SGLee

Exercises 17-20 refer to the relations

R₁= {(1,x), (2,x), (2,y), (3,y)},

R₂= {(x,a), (x,b), (y,a), (y,c)}.

Problem 20
Use the result of Exercise 19 to find the matrix of the relation R₂° R₁.

+) Result of Exercise 19

Solution

Comment: 위의 Problem 19와 같이Matrix Relation을 통해 Matrix 자체를 구하고 두 Matrix의 Product를 구하는 문제였습니다. 푸는 과정 중에 교수님께서 여러 번 수정해주셔서 좀 더 완벽한 Finalize를 할 수 있었던 문제입니다.

Final OK by SGLee, Page 196 Problem 7 Re-Finalized, Dear 엄자균 and 오동찬, 엄자균, 오동찬

Dear 엄자균 and 오동찬, Page 196 Problem 7 엄자균 Finalized by 오동찬

(Attached DOC file in case there is an error.)

Problem 6

Solution

Comment: Sigma 안의 index를 바꿔 다시 고쳐쓰는 문제였습니다. 풀이 과정 중에 실수가 많고 불분명한 부분이 많아 교수님께서 수정을 요구하셨고 여러 차례 수정 끝에 Final OK를 받아낸 문제입니다. 간단한 문제라도 세심한 관심과 풀이가 필요한 것을 느끼게 해 준 문제입니다.

p.370 Problem 3

Solved by 오동찬 Date 2018.10.27

Revised by 신혜수 Date 2018.10.28

Finalized by 김영철 Date 2018.10.28

Refinalized by 정호진 Date 2018.11.05

revised by 강병훈 Date 2018.11.05

Final OK by TA Date 2018.11.05

Problem

How many functions are there from an n -element set onto {0, 1}?

Solution

1. each element have 1 or 0

=2ⁿ

2. every element is 0 , every element is 1

3. deduct them

=2ⁿ - 2

Answer: 2ⁿ -2

■

Comment :전사함수의 정의를 모르면 틀리기 쉬운 문제다. 모든 함숫값이 0인 경우, 1인 경우를 빼야한다는 것을 인지하고 문제를 풀어야 틀리지 않을 수 있다.

Comment: 전사함수의 정의를 Revise와 Finalize를 해준 학우를 통해 배우게 되었습니다.

p.370 Problem 4

Solved by 오동찬 Date 2018.10.28

Finalized by 김영철 Date 2018.10.28

Final OK by TA Date 2018.11.03

Refinalized by 엄자균 Date 2018.11.07

Revised by 강병훈 Date 2018.11.09

Problem

A seven-person committee composed of Greg, Hwang, Isaac, 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?

Solution

There is Seven person and five position to select.

1.Greg is secretary: 6 × 5 × 4 × 3 = 360

2.Greg is not an officer: 6 × 5 × 4 × 3 × 2 = 720

Answer

Total: 360 + 720 = 1080.

Comment: 경우의 수를 구하는 기본적인 문제입니다. 고등학교 때 배운 부분이지만 다시금 공부하여 기억에 남은 부분입니다.

p.371 Problem 5 Chapter 6 Self-Test

Solved by 오동찬 Date 2018.10.28

Finalized by 김영철 Date 2018.10.28

Refinalized by Muhammad Date 2018.10.29

Final OK by TA Date 2018.11.05

Refinalized by 엄자균 Date 2018.11.07

Revised by 강병훈 Date 2018.11.09

Problem

How many 3-combinations are there of six objects?

Solution

C(6 ,3) = 6 ! ÷ (3 ! × 3!) = 20

Answer: 20 ■

Note

Definition 2.15

Given a set   containing   (distinct) elements,

(a) An -combination of   is an unordered selection of -elements of (i.e. an           -element subset of ).

(b) The number of -combination of a set of   distinct elements is   or .

Comment: 조합의 정의를 이용해 풀 수 있었습니다. 교수님 Lecture Note를 참고하여 조합의 Definition을 한 번 더 이해하게 되었습니다.

p.371 Problem 7 Chapter 6 Self-Test

Solved by 오동찬 Date 2018.10.28

Finalized by 김영철 Date 2018.10.28

Refinalized by Muhammad Date 2018.10.28

Final OK by TA Date 2018.11.03

Refinalized by 엄자균 Date 2018.11.07

Revised by 강병훈 Date 2018.11.09

Problem

How many six-card hands chosen from an ordinary 52-card deck
contain three cards of one suit and three cards of another suit?

Solution

1. C(13, 3) = 286 (one suit)

2. C(13, 3) = 286 (another suit)

3. C(4 , 2) = 6 (2 suits)

4. 286 x 286 x 6 = 490,776 .

Answer: 490,776 ■

Comment: 조합의 정의를 이용해 풀 수 있었습니다. 카드 덱으로부터 고르는 경우의 수를 구하는 문제였습니다.

p.371 Problem 8 Chapter 6 Self-Test

Solved by 오동찬 Date 2018.10.28

Finalized by 김영철 Date 2018.10.28

Refinalized by Muhammad Date 2018.10.28

Final OK by TA Date 2018.11.03

Refinalized by 엄자균 Date 2018.11.07

Revised by 강병훈 Date 2018.11.09

Problem

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 non defective discs?

Solution

1. defective : 3, not defective : 1 C(5,3) × C(95,1).

2 , defective : 4 C(5,4)

C(5,3) × C(95,1).+ C(5,4)

Answer: 955 ■

Comment: 조합의 정의를 이용해 풀 수 있었습니다. 예전 확률 및 랜덤 프로세스에서 비슷한 문제를 풀어본 경험이 떠올랐습니다.

p.371 Problem 9 Chapter 6 Self-Test

solved by 오동찬 2018.10.28

finalized by 김영철 2018.10.28

refinalized by 신혜수 2018.10.29

final OK by TA 2018.11.05

Refinalized by 김주형 Date 2018.11.07

Revised by 강병훈 Date 2018.11.09

Problem

How many strings can be formed by ordering the letters ILLINOIS ?

Solution

ordering the 8 letters,

n!= 8!

I : 3 repetition

L: 2 repetition

∴8!/(3!×2!)

Answer : 8!/(3!×2!) = 3360. ■

Comment: 반복되는 것이 있는 순열을 구하는 문제였습니다. 흔히 고등학교에서 ‘같은 것이 있는 순열’이라는 이름을 통해 배웠던 내용입니다.

p.371 Problem 10

Solved by 오동찬 Date 2018.10.28

Finalized by 김영철 Date 2018.10.28

RE-Finalized by 전종문 Date 2018.10.28

Re-Finalized by 정호진 Date 2018.11.05

revised by 강병훈 Date 2018.11.05

Problem

H ow many strings can be formed by ordering the letters ILLINOIS

if some I appears before some L ?

Solution

1. 8!/3!×2! = 3360

2. put LLIII order 8!/5! = 336

3. 3360-336=

Answer : 3024 ■

Note

I가 L보다 앞에 있는 strings 수를 직접 구하기 힘들기 때문에 전체 strings수에서 모든 L이 I보다 앞에 있는 strings 수를 빼서 구하는 방법을 생각하는게 중요하다고 생각한다.

0. To solve A ="Some X are Y" problem, we first have to think about A^c = "No X is Y" and then subtract it from the whole event.(A=U-A^c )

1. So we have to find out the number of cases of "No I appears before L", and

subtract it from the whole event, which is, according to Problem-9, 3360.

2. Now let's calculate the number of cases of "No I appears before L". Excluding I and L,

there are N, O and S remaining. We only have to find their spots among 8 spots,

because then the remaining 5 spots will be automatically decided, in L-L-I-I-I order.

3. The number of possible cases of ordering N, O and S is P(3,3)=

8 x 7 x 6 = 336 . To get the answer, we need to subtract this from the whole event.

4. So the answer is 3360 - 336 = 3024.

Answer: 3024 ■

Comment :Also we can solved this problem for another way.

At 3,number of possible cases of no I appears before some L is equal to number of case that put L,L,I,I,I in letters which is ordering N,O,S.

So, number of possible cases of no I appears before some L

= p(3,3)×H(4,5)=p(3,3)×C(8,3)=8 ×7 ×6 =336

Comment: 조합과 순열을 이용해 푸는 문제입니다. 문제 접근 방식을 어떻게 하느냐에 따라서 쉽게 풀릴 수도 있고 여러 가지 경우를 고려해야 할 수도 있는 복합적인 문제였습니다.

p.371 Problem 26 Chapter 6 Self Test

Solved by 오동찬 Date 2018.10.29

Finalized by 김영철 Date 2018.10.29

Re-Finalized by 전종문 Date 2018.10.30

Final OK by TA Date 2018.11.02

Re-Finalized by 만우흠 , Date: 2018.11.07

revised by 강병훈 , Date: 2018.11.09

Problem

Find the coefficient of x³ yz⁴ in the expansion of (2 x + y + z )⁸

Solution

expansion of (2x + y + z)⁸ =(2x + y + z)(2x + y + z)(2x + y + z)(2x + y + z)(2x + y + z)(2x + y + z)(2x + y + z)(2x + y + z)

Then choose three terms for the x in C(8,3)ways.

choose on term for y in C(5,1)ways.

Thus the coefficient of x³ yz⁴ in the expansion (2x + y + z)⁸ is

2³ C(8,3).C(5,1)

=2³ (8!/3!5!)5

=2³ 8!/3!4!

=322560/144

=2240

Answer : 2240 ■

Comment: 조합을 이용해 다항식의 전개항을 구하는 문제입니다. 추후 교수님의 강의에서 Sage코드를 이용해 빠르게 구하는 법을 익혔습니다.

[Final OK by SGLee and TA] ch 6, p.371, prob.27 김승연, 오동찬, 칭기즈, TA

Problem 27 section 7 p. 371

Solved By 오동찬, Date: 2018.10.29

Finilized By 칭기즈 , Date: 2018.10.29

Final OK by TA , Date: 2018.10.31

[Final OK by SGLee and TA]

Problem 27 section 7 p. 371

Use the Binomial Theorem to prove that

Binomial Theorem

Theorem 7.1

Binomial Theorem

If and , then

.

Solution:

Notice that:

in the given problem a = 2 and b = -1 .

Also:

Thus,

which can be written as

hence,

Because the LHS and RHS is equal due to the Binomial expansion when a = 2 and b = -1 . So the answer is 1 .

Comment: 이항정리를 이용한 간단한 문제였습니다. 이항정리 개념을 확실히 익힐 수 있었습니다.

[Final OK by SGLee]Ch 6, P.371 Problem 28 김승연, 오동찬,전종문,김은율

Problem 28 section 7 p. 371

Solved by 오동찬 Date: 2018.10.29

Finalized by 전종문 Date: 2018.10.30

Re-Finalized by 김은율 Date: 2018. 10.31

Problem

Rotate Pascal’s triangle counterclockwise so that the top row consists of 1’s .

Explain why the second row lists the positive integers in order 1, 2, ....

Solution

Here is the Pascal's triangle which is symmetric.

The picture above is the Pascal's triangle. Like in problem, if we rotate the triangle counterclockwise, so that the top row consists of 1’s .

And the numbers in the second row (from the right to left) will be 1, 2, 3, 4, 5,….

That is because, the second row consist of C(n,1)=n as we see in the following picture.

Patterns Within the Triangle

https://www.mathsisfun.com/pascals-triangle.html

∴ The second row lists C(n,1)=n ■

Comment: 이항정리와 함께 배운 파스칼의 삼각형입니다. 파스칼의 삼각형의 특징과 구조를 정확히 익힐 수 있었습니다.

[Final OK by SGLee and TA] p. 371 Problem 29 김승연, 오동찬, 칭기즈, TA

[Final OK by TA] p. 371 Problem 29 Solved By 오동찬 Finilized by 칭기즈

Problem 29 section 8 p. 371

Solved By 오동찬, Date: 2018.10.29

Finilized by 칭기즈 Date: 2018.10.29

Final OK by TA date : 2018.10.31

Problem

Show that every set of 15 socks chosen among 14 pairs of socks contains at least one matched pair

Solution

We can use the Pigeon Hole principle in this problem.

Pigeonhole Principle (1st Form)

If pigeons fly into pigeonholes and , some pigeonhole contains at least two pigeons.

Let's assume:

n = 15 socks (as each pigeons )

k = 14 pairs( as pigeonhole.)

k => (다른 색깔의 14가지 pigeonholes) 14 < 15 (15개의 pigeons )

Thus,

If Than we can assign 15 each socks to 14 different (colored) pairs, by the Pigeon Hole principle, there is some a (color, pigeon hole) pair of sock that contain at least two socks (pigeons).

Conclusion:

Therefore, every set of 15 socks chosen among 14 pairs of socks contains at least one matched pair. ■

Comment: 비둘기집 원리를 익힐 수 있는 문제였습니다. 정확한 설명이 부족해 여러 학우들이 애먹었으나 결국 모두 합심하여 Final Ok를 받아낸 문제입니다.

[Final OK by SGLee] Ch 7, P424, P.5 칭기즈 finalized by 오동찬

Ch 7, p. 424 problem 5

solved by 칭기즈 Date 2018.11.09

finalized by 오동찬 Date 2018.11.10

Final OK by SGLee

Ch 7, p. 424 Problem 5

Is the recurrence relation

a_n = a_n-1 + a_n-3

a linear homogeneous recurrence relation with constant coefficients?

Solution:

Definition:

Definition 2.6

Thus,

The recurrence relation in the definition is linear because the right-hand side is a sum of previous terms of the sequence which are

a_n-1 and a_n-3

Notice that:

a_n = 1 *a_n-1 + 1*a_n-3

Hence, 1 is a constant coefficient .

Conclusion:

The recurrence relation,

a_n =a_n-1 +a_n-3

is a linear homogeneous recurrence relation with constant coefficients ■

Comment:

We could find that the given recurrence relation is a linear homogeneous recurrence relation with constant coefficients , due to the definition.

Comment: Linear homogeneous recurrence relation에 관한 문제입니다. recurrence relation이 고등학교 때 배운 점화식과 비슷하다는 것에 흥미를 느꼈던 부분입니다.

[TA] Ch 9, P. , Exercise 17

Solved by 오동찬 Date : 2018.11.24

Revised by 전종문 Date : 2018.11.24

Finalized by 김희성 Date : 2018.11.27

Final OK by TA Date : 2018.11.28

Problem

Decode the bit string using the Huffman code given below

Solution

By Tree,

huffman code

S: 11

A: 10

E: 00

N: 010

P: 0110

L: 01110

D: 01111

The given string is 1110011101001111 ⇒11 10 01110 10 01111 ⇒ SALAD

∴SALAD ■

Comment:

Huffman code를 이용하여 Tree에 있는 문자열로 Decode 해보는 문제였다.

**********************

comment

허프만 코드 설명을 추가 하였습니다.

Comment: 허프만 코드에 관한 기본적인 문제입니다. Revise 와 Finalize해준 학우들의 의견을 들을 수 있어 좋았습니다.

Ch 9,Exercise 31

Solved by 오동찬 Date : 2018.11.24

Revised by 김승연 Date : 2018.11.27

Finalized by 김희성 Date : 2018.11.27

Final OK by TA Date : 2018.11.28

Problem

If the forest F is consisted of m tress and have n vertices, how many edges does forest F has?

Solution

A tree with n vertices has n −1 edges.

Say your forest has k trees. Denote by n₁ , n₂ , …, n_k the number of vertices of each tree.

Thus the i_th tree has n_i₋₁ edges.

Summing up, the total number of edges is

∴ n −k ■

comment : 아주 잘 정리되어있어서 이론만 추가 하였습니다.

Comment: Forest에 관한 간단하고 기본적인 문제입니다. 정리된 이론을 통해 다시 한 번 복습하였습니다.

[Revised] Ch 9, P. , Exercise 2 by 오동찬 and 김주형

[TA] Ch 9, P. , Exercise 2 Solved by 오동찬 Revised by 김주형

[Finalized] by 김희성 Date 2018.11.26

[Final OK] by TA Date 2018.11.28

Problem

With below figure of a tree, find order of vertices with Pre-order traversal, In-order, Post-order traversal , respectively.

Solution

- preorder traversal : A-B-C-D-E-F

- inorder traversal : C-B-E-F-D-A

- postorder traversal : C-F-E-D-B-A

전위 순회는 [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회합니다.
중위 순회는 [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회합니다.
후위 순회는 [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회합니다.

Comment

Preorder traversal Inorder traversal

Root-Left-Right Left-Root-Right

Postorder traversal

Left-Right-Root

reference : lecture note

http://matrix.skku.ac.kr/2018-DM/DM-Ch-9-Lab.html

최대한 단순화해서 문제를 풀어보았습니다.

Comment: Pre-Order, In-Order 등 여러 순회 법을 익힐 수 있는 기본적인 문제입니다.

Ch 9, P. , Exercise 8

Solved by 오동찬 Date : 2018.11.24

Revised by 김정주 Date : 2018.11.26

Finalized by 김희성 Date : 2018.11.27

Final OK by TA Date : 2018.11.28

Problem

Write each expression with binary tree, Prefix notation and postfix notation

8. (A*B+C*D)-(A/B-(D+E))

Binary tree

Solution

Prefix notation : - + * A B * C D - / A B + D E

Postfix notation : A B * C D * + A B / D E + - - ■

Comment: Prefix Notation, Postfix notation 등 여러 표기법을 익힐 수 있는 문제였습니다. 사실 인간에게는 익숙치 않기에 컴퓨터가 이해하는 방식을 배울 필요가 있었습니다.

◆ Final comment

Nov. PBL보고서를 마치고 (5점)

9월 : 학기 초에는 PBL 리포트가 무엇인지 QnA가 무엇인지 또 매주 강의 정리는 어떻게 해야하는지 정말 너무 해야할 것이 많다고 느껴졌고 어떤식으로 하는지 잘 감도 안잡혔습니다. 하지만 교수님께서 매주 친절히 수업시간을 할애하시며 거의 한 달간을 계속 설명을 해주셨고 또 주변 친구들의 도움을 통해 점차 익히고 익숙해지게 되었습니다. 그 후 QnA에 여러 Exercise 문제를 풀기도 하고 다른 친구들의 문제를 Revise/Finalize 하며 고쳐가면서 점차 교수님의 이산수학 수업에 익숙해지게 되었습니다. 또 여러 수정과정을 거쳐 Final OK가 늘어나는 저의 풀이들을 보면서 뿌듯함을 느끼기도 하고 성취감을 느끼기도 하였습니다. 그렇게 9월 한 달은 매우 빠르게 지나갔습니다.

10월 : 실제로 1st PBL 리포트 제출을 위해 문서를 작성하면서 매 주 조금씩 꾸준히 올렸던 QnA 글들과 문제들의 양을 보며 ‘내가 이렇게 많이 했었나’라는 생각이 들었습니다. 결국 조금씩이라도 꾸준히 해온 것이 큰 성과를 보이기 시작한 것입니다. 또 보고서를 통해 나의 한 일을 정리하고 자신을 되돌아보면서 앞으로 남은 학기를 어떻게 보낼 것인지 어떤 점을 개선해야 될 것인지 파악하게 되었습니다. 문제 풀이는 물론 다른 학우들과 의사소통을 더 늘리고 여러 가지 정보들을 공유하고 질문을 더 많이 올리는 것에 집중하며 조원들을 비롯 다른 학우들과 더 가까워 지는 것이 그 방향 중 하나라고 할 수 있겠습니다. 또 유종의 미를 거두기 위해 1st PBL 리포트를 제출했다는 것에 만족하지 않고 더욱 꾸준히 조금씩 정보를 얻고 글을 공유하며 문제를 푸는 것이 중요하다고 생각합니다.

중간고사를 준비하며: 어떻게 보면 우리는 시험기간을 위해 시험을 위해 또 학점만을 위해 대학 생활을 하고 있는 것은 아닌지 생각이 듭니다. 조금 더 건설적이고 발전적인 대학생활을 위해 당연히 시험 준비도 중요하겠지만 평소에 배우는 사람으로서 배우는 자로서의 태도를 익히고 배움의 태도를 가꿔나가는 것이 필요하다고 생각합니다.

11월 : 중간고사가 끝난 후 조가 정해지게 되었습니다. 처음에는 조장 선정 방식이 의아했었는데 교수님의 면담 후 정확히 알게 되었습니다. 만약 학기 초부터 Random하게 조장이 정해진다면 몇몇은 책임감을 가지고 끝까지 가겠지만 그렇지 못한 학우들도 있을 것입니다. 하지만 중간고사 까지의 과정과 성적 그리고 결과들을 보고 책임감 있게 학우들을 끌고나갈 조장을 정한다면 조금 더 팀플이 매끄럽고 진취적으로 흘러갈 것이라고 하셨습니다. 그렇게 저는 Team 5의 조장이 되었습니다. 다행하게도 4명의 학우들이 지원을 해주셔서 5명의 팀을 꾸릴 수 있게 되었습니다. 그 이후 수업은 조금 더 Flipped Class에 맞게 흘러갔다고 생각합니다. 개인적으로도 예습해오는 양이 늘었으며 QnA가 훨씬 활발해져 교수님의 Offline 강의 이전에 더 많은 정보를 공유하고 학습할 수 있었습니다. 또 교수님의 관심과 조장들의 노력 덕분에 중간고사까지는 참여가 저조했던 학우들을 활동할 수 있도록 더욱 격려하였고, 개인적인 사정(사업, 개인 일)등으로 시간이 부족했던 학우들도 교수님의 배려와 관심으로 각자에게 맞는 방향으로 공부를 하기 시작했습니다. 특히 이 부분에서 저는 ‘이산수학’ 수업의 대단함을 느낄 수 있었습니다. 특히 교수님께서는 한 명의 낙오자 없이 본인에게 ‘맞는’ 방식으로 수업을 듣고 공부하기를 원하셨고, 바쁜 학우들도 본인의 시간을 내어 본인의 방향으로 수업을 진행하였습니다. 11월의 거의 마지막을 보내고 있는 지금, 그 학우들의 작업물을 보면 충분한 시간을 투자했고 또 결과물도 괜찮게 나오고 있다고 생각합니다. 또 좋았던 점은 수업 때 조별 Discussion 시간이 많아진 점입니다. 저희 조원들도 개인 사업과 여러 일로 주기적인 QnA 활동을 참여하지 못하는 인원이 있습니다. 그런 인원과 Discussion 시간을 이용하여 각자의 어려움을 나누고 할 수 있는 방향을 함께 모색하여 수업을 진행할 수 있어 조별 Discussion 시간은 정말 소중한 시간이었습니다. QnA Board에서는 중간고사 이후 문제 풀이 보다는 각자의 경험, 지식 등을 공유하는 글이 많아졌습니다. 개인적으로도 굉장히 좋았습니다. 문제 풀이도 많이 하면 좋겠지만, 어느 정도 예제를 익히고 I-campus로 온라인 강의를 듣고 교수님의 Offline 강의를 들으면 어느정도는 개념도 이해하고 사용할 수 있다고 생각합니다. 하지만 각자가 가지고 있는 수학적 지식과 경험 등을 공유하는 것은 지금 이 시간, 지금 이 수업 아니면 할 수 없다고 생각합니다. 그렇기에 여러 학우들, 또 교수님의 경험과 정보를 공유하는 것은 제게 정말 뜻 깊고 소중한 시간이 된 것 같습니다. 또한 QnA 참여율도 높아져서 중간고사 이전보다 참여하는 학우들이 많아져 더욱 풍성하고 다양한 지식 정보의 창이 된 것 같았습니다.

소감: 이제 ‘이산수학’은 한 학기 동안을 거쳐 마지막으로 다가가고 있습니다. Final Project와 발표 등을 남겨놓고 있는 상황에서 저희 Team 5는 각자의 시간과 여건에 맞춰 적절하게 역할은 분배하여 진행하고 있습니다. 다른 사람이 보기에 많이 부족한 결과물 일 수 있습니다. 하지만 저희가 교수님의 ‘이산수학’ 강의에서 배운 것을 충분히 보여주기에 적합하다고 생각합니다. 단순히 한 과목을 배운 것으로 끝나지 않고 같이 협동하며 서로의 발전을 도모하고, 수학을 단순히 문제 풀이의 과목으로 생각하지 않고 수학적 사고와 컴퓨터를 이용한 그 사고의 확장을 지향하는 것이 저희가 이 과목에서 배운 것입니다. 또 Flipped Class, Action Learning을 통해 스스로를 발전시키기위해 공부해나가고 여러 정보들을 접하는 것을 배웠습니다. 또 지속적인 QnA 참여는 다양한 학우들과 교수님의 생각을 배우고 느낄 수 있어 좋았습니다. 개인적으로는 QnA에 올린 모든 글을 PDF 형식이나 어떠한 방식으로든 저장하고 싶습니다. 이제는 문제를 푸는게 주된 것이 아닌, 사고하는 방식과 활용하는 방식을 배우는 시대이기에, ‘이산수학’ 강의 및 Flipped, Action Learning Class는 더욱 확대되고 많은 학생이 배워야 할 때라고 생각합니다.

앞으로 남은 1달여간 유종의 미를 거두기 위해 더욱 정진하고 성실히 임하겠습니다.

감사합니다. ■

Part VI. Solutions of Ch. 9

1. Ch.9 문제를 Solution과 함께 올려 학우들이 공부하고 Revise, Finalize하게 함

- 현재 진행 중입니다.

2. Finalize 된 문제들에 학우들의 Comment를 달게 해서 각자의 생각들을 공유하게 함

- 현재 진행 중입니다.

3. Finalize 된 문제들을 Team 5가 취합하여 필요한 부분은 보충하고 Ch.9의 중요한 Theorem 등을 같이 정리함

4. Ch.9가 Tree 부분인 만큼 코드나 컴퓨터공학적으로 공유할 부분이 있을 것 같아 여러 종류의 Tree와 Graph에 관련한 부분을 직접 코딩하였습니다.

현재 완료된 3, 4번 먼저 올리겠습니다.

Ch. 9 Trees 9.1 Introduction

Definition 1.1

tree

A tree is a connected undirected graph with no simple cycles.

Rooted tree

rooted tree

A rooted tree is a tree in which one vertex has been designated as the root.

level of a Vertex
The level of a vertex is the length of the simple path from the root to

Height

The height of a rooted tree is the maximum of all level number of its vertices.

9.2 Terminology and Characterizations of trees

Definition 2.1

Parents, Child, ...

Theorem 2.3

TFAE

Let be a graph with vertices. The following are equivalent.

(a) is a tree

(a) is connected and acyclic. (“acyclic”= having no circles)

(a) is connected and has edges.

(a) is acyclic and has edges.

9.3 Spanning Trees

Definition 3.1

Tree is a spanning tree of a graph if is a subgraph of that contains

all of the vertices of

Theorem 3.4

G 가 spanning Tree T 를 갖는다. ⇔ G가 connected 그래프이다.

9.4 Minimal Spanning Trees

Definition 4.1

is a weighted graph.

Minimal spanning tree of is a spanning tree of with minimum weight.

Theorem 4.5

Prim’s Algorithm (Algorithm 4.3) is correct; that is, at the termination of Algorithm

4.3, is a minimal spanning tree.

9.5 Binary Trees

Definition 5.1

A binary tree is a rooted tree in which each vertex has either no children, one

child, or two children.

A vertex has one child, that child is designated as either a left child or a right

child(but not both).

A vertex has two children,

one child is designated a left child and

the other child is designated a right child.

Theorem 5.4

Theorem 5.6

Definition 5.8

A binary search tree is a binary tree in which data are associated with the

vertices. The data are arranged so that, for each vertex in , each data item in the

left subtree of is less than the data item in , and each data item in the right

subtree of is greater than the data item in .

9.6 Tree traversals

9.7 Decision Trees and the Minimum Time for Sorting

Definition

Decision Tree

A binary tree containing an   algorithm to decide which course of action to take.

Use

to   specify algorithms

to   obtain lower bounds on the worst-case time for sorting

Theorem 7.3

If  n is the number of comparisons needed to sort n items in the worst case by a

sorting algorithm, then f(n)   (n * log n).

9.8 Isomorphisms of Trees

Theorem 8.3

There are three non-isomorphic trees with five vertices.

Definition 8.4

Theorem 8.7

There are four nonisomorphic rooted trees with four vertices. These four rooted trees

are shown in Figure 8.9.

Definition 8.8

Theorem 8.11

There are four nonisomorphic rooted trees with four vertices. These four rooted trees

are shown in Figure 8.9.

Theorem 8.12

There are n nonisomorphic binary trees with nvertices

where C_n = C ( 2n , n ) / (n+1) is the n th Catalan number.

Theorem 8.14

The worst-case time of Algorithm 8.13 is  (n) , where n is the total number of

vertices in the two trees.

I) Binary Search Tree

II) Red Black Tree

< RB Tree의 Fix시 Left Rotate를 위한 함수>

<각각 Insert와 Tree Insert 함수>

III) Find the Graph is Tree or Not

IV) Find the Graph is Connected or Not

■

◆ Comment after PBL/Project/발표

Nov. PBL보고서를 마치고

소감: 이제 ‘이산수학’은 한 학기 동안을 거쳐 마지막으로 다가가고 있습니다. Final Project와 발표 등을 남겨놓고 있는 상황에서 저희 Team 5는 각자의 시간과 여건에 맞춰 적절하게 역할은 분배하여 진행하고 있습니다. 다른 사람이 보기에 많이 부족한 결과물 일 수 있습니다. 하지만 저희가 교수님의 ‘이산수학’ 강의에서 배운 것을 충분히 보여주기에 적합하다고 생각합니다. 단순히 한 과목을 배운 것으로 끝나지 않고 같이 협동하며 서로의 발전을 도모하고, 수학을 단순히 문제 풀이의 과목으로 생각하지 않고 수학적 사고와 컴퓨터를 이용한 그 사고의 확장을 지향하는 것이 저희가 이 과목에서 배운 것입니다. 또 Flipped Class, Action Learning을 통해 스스로를 발전시키기 위해 공부해나가고 여러 정보들을 접하는 것을 배웠습니다. 또 지속적인 QnA 참여는 다양한 학우들과 교수님의 생각을 배우고 느낄 수 있어 좋았습니다. 개인적으로는 QnA에 올린 모든 글을 PDF 형식이나 어떠한 방식으로든 저장하고 싶습니다. 이제는 문제를 푸는게 주된 것이 아닌, 사고하는 방식과 활용하는 방식을 배우는 시대이기에, ‘이산수학’ 강의 및 Flipped, Action Learning Class는 더욱 확대되고 많은 학생이 배워야 할 때라고 생각합니다.

앞으로 남은 1달여간 유종의 미를 거두기 위해 더욱 정진하고 성실히 임하겠습니다.

감사합니다. ■

Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).

Definition 2.1
A Permutation of distinct elements , , is an ordering of the elements , , .

Pigeonhole Principle (1st Form)
If pigeons fly into pigeonholes and , some pigeonhole contains at least two pigeons.

Definition 1.1	tree
A tree is a connected undirected graph with no simple cycles.

Rooted tree	rooted tree
A rooted tree is a tree in which one vertex has been designated as the root.

Height
The height of a rooted tree is the maximum of all level number of its vertices.

Theorem 3.4	G 가 spanning Tree T 를 갖는다. ⇔ G가 connected 그래프이다.

Theorem 8.3
There are three non-isomorphic trees with five vertices.