CSE1312 이산구조를 수강하고

인하대학교 CSE1312 이산구조는 원래 이산수학이라는 이름으로 진행되던 강의였다. 사실 대부분의 대학에서는 이산수학이라고 하고 있을 것인데, 굳이 바꾼 이유는 모르겠다.

 

이산구조 과목은 21년도 커리큘럼 변경전에는 2학년 과목으로 짜여있던 과목이었다. 아마 자료구조와 같이 수강하는 것을 노린 것인진 몰라도, 내용 자체도 전반적인 컴퓨터공학의 기초 부분을 다루고 있고, 난이도도 정말 기본 베이스의 수준이기에 1학년으로 개편된 것이 아주 좋다고 생각이 든다.

 

교재는 Kenneth Rosen의 Discrete Mathematics and Its Applications를 사용했다.

https://books.google.co.kr/books/about/Discrete_Mathematics_and_Its_Application.html?id=T_K9tgEACAAJ&source=kp_cover&redir_esc=y

Discrete Mathematics and Its Applications

 

8주차까지는 명제 논리, 집합론, 알고리즘, 시간복잡도, 수학적 귀납법, Counting(비둘기집 문제등)을 다룬다.

 

강의의 초반 1단원은 명제 로직으로, Connectives(부정, 논리곱, 논리합, implication)등을 다루는데, 이때 커리큘럼상 같은 시간대에 있는 논리회로를 같이 수강한다면 논리회로의 AND, OR gate등과 함께 같은 것을 두 번 배우는 느낌을 받게 된다.

아무튼 명제와 predicate, quantifier, nested 된 quantifier 등과 함께 마지막 응용으로 영어 statement를 predicate logic으로 나타내본다.

전체적으로 뭔가 한 번씩 해본 느낌의 파트로, 이미 알고 있는 것을 제대로 공식화하는 느낌이 있다.

 

2단원은 집합론으로, 기초 set, function, sequence, cardinality, matrix 등을 다룬다. 이것 역시 고등수학을 다시 배우는 느낌이다.

 

3단원은 알고리즘으로, Pseudocode로 시작해 여러 탐색 방법, 정렬 방법을 배운다. 이때 Big-O, Theta, Omega 등의 시간 복잡도도 배우는데, 이후 자료구조나 알고리즘 과목들을 배우는데 기초적으로 도움이 될 것 같은 파트이다.

 

5단원은 수학적 귀납법으로, basic step과 inductive step으로 문제를 해결하는 법을 배운다. 추가적으로 집합과 structure도 귀납적으로 정의하거나 다루어보고, 알고리즘 또한 귀납적으로 풀기 좋은 여러 방법을 배운다. 역시나 예시로는 factorial, gcd, binary search 등이 나온다.

아마 중간 전에서는 가장 어렵게 들어갈 수 있는 파트라고 생각하는데, midterm exam도 해당 파트에서 가장 어려운 문제가 나왔던 것으로 기억한다.

 

Couting 파트는 직관적인걸 이론적으로 정의하는 느낌이 드는 파트인데, 비둘기집 문제등 처음 듣는다면 아마 흥미로운 부분도 있을 것 같다.

 

그리고 기말까지 Couting 단원에서 순열과 조합, 이항계수 generalized 순열, 조합등 통계학 수업과 고등학교 확률과 통계에서 배웠던 것 같은 무언가를 다시 되풀이한다.

 

8단원은 Advanced Counting Techniques로 귀납 응용으로 피보나치 토끼, 하노이탑, Bit string counting 등의 응용적인 문제가 나온다. 이 또한 문제를 어렵게 낸다면 얼마든지 어렵게 낼 수 있을 것 같은 파트다.

그리고 divide-conquer 알고리즘으로 이항 탐색, 머지 소트, 빠른 정수곱 등등과 master theorem을 통한 시간 복잡도 분석등을 배웠다. 아마 해당 파트부터 정말 처음 보는 것들이 나와서 재밌었던 것 같다. 빠른 정수곱은 이전에 알고리즘을 공부할 때 n^1.6 수준으로 분할하여 곱을 하는 방식으로 들었을 때 굉장히 신기했었는데, 해당 교과에서도 다루는 것을 보고 기초적인 교과로써 다른 강의를 듣기 전에 수강한다면 정말 좋을 것 같다는 생각이 들었다.

그리고 추가적으로 set의 inclusion-exclusion을 다뤘다.

 

9장은 Relation으로 reflexive, symmetric, antisymmetric, transitive 등의 관계와, relation의 composition 그리고 matrix, digraph 등으로 표현하는 방법을 배웠다. 추가적으로 closure와 equivalence relation, partition of set 등도 다루었다.

해당 단원은 원래 알고 있던 게 하나도 없던 파트여서 재밌게 공부할 수 있었다.

 

10장과 11장은 Graph와 Tree로 그래프는 그래프의 타입과 특성, isomorphism(동형), connectivity, Euler and Hamiltonian graph 등을 다루고, Tree는 간단한 트리 기초와 traversal을 배운다.

자료구조를 이미 수강해서 그런지 크게 새로운 부분은 없었다.

 

전체적인 총평으로는 컴퓨터공학 첫 입문으로 듣는다면 유용하고 가볍게 들을 수 있을 과목이다. 다만 21년도 커리큘럼 개편으로 과정이 꼬이면서 이미 모든 걸 다 배운상태에서 들은 느낌이라 아쉬웠다.

그리고 4단원의 암호학도 재미있는 파트 일 것 같은데, 들어가지 않아 아쉬웠다. 커리큘럼 개편으로 정수론이 사라졌는데 해당 파트도 스킵하니 아쉬움이 컸다.