2017년 가을학기 교과목 수강신청기간을 맞이하여 지난 학기에 하였던 것처럼 이번 2017년 가을학기에 열릴 이산수학/그래프이론 관련 교과목 및 기타 흥미로운 교과목을 정리해봅니다.
MAS477 Introduction to Graph Theory (그래프이론개론). 월수 13:00~14:15, 엄상일
- (네, 아시다시피 제가 하는 과목입니다.) 보통 매년 가을학기에 열렸으며 제가 연구년을 갔던 2013년에는 Andreas Holmsen 교수님이 강의를 하셨었고 작년에는 대수적 그래프이론 전공한 Brendan Rooney 교수님이 강의를 하였습니다. 2년만에 다시 하게 되었습니다.
- 그래프이론의 다양한 부분을 다룹니다. 보통 많이 생각하는 기초적인(?) 해밀턴 회로 오일러 회로 같은건 다루지 않습니다. 주요 내용을 언급하면 아래와 같습니다.
- 그래프 connectedness: 그래프가 얼마나 잘 연결되었는지, 그리고 한 점에서 다른 점으로 몇 개의 서로 겹치지 않가 있는지와 같은 Menger 정리 등.
- 그래프의 매칭: 남녀 학생을 짝지울때 써먹는(?) 홀의 결혼정리와 König의 정리, 그리고 남녀가 아닌 일반적인 그래프의 perfect matching에 관한 Tutte의 정리, 그리고 그래프의 maximum matching이 어떤 구조인지 설명하는 Gallai-Edmonds Structure 정리와 함께 Edmonds의 유명한 다항식 시간에 maximum matching 찾는 알고리듬을 다룹니다.
- 평면그래프: 이산수학 시간에는 정리만 배웠던 Kuratowski 정리를 엄밀하게 증명합니다. 오일러 공식 및 dual에 대해 다룹니다.
- 채색 문제:
4색정리5색정리를 증명합니다. List Coloring도 배우며 이를 통해 Thomassen의 다른 방식의 5색 정리 증명도 배웁니다. 그리고 perfect graph에 관한 성질도 배웁니다. - Flow 문제: 채색문제의 dual이라고 할 수 있는 nowhere-zero flow에 관해 배우고 관련된 Tutte의 유명한 추측들을 다룹니다.
- 그외 시간에 따라 다룰 가능성이 있는 주제: Turan 정리, Hadwiger 추측, Szemeredi의 Regularity lemma, Higman의 lemma, Kruskal의 well-quasi-ordering 정리, Robertson과 Seymour의 그래프 마이너 정리
- 교재: 매년 R. Diestel 교수의 그래프 이론 GTM 책(http://diestel-graph-theory.com)을 교재로 지정하였으나, 올해는 참고도서로만 지정하였습니다.
책 값이 비싸다는 불평들이 있었고, 사실 수업 내용은 평행우주를 달린다는 평도 있었기에… - Syllabus
MAS583C Topics in Analytic Combinatorics (해석조합론), 화목 10:30-11:45, 김동수 교수님
- 예전에 1학점 특강으로 잠깐 개설된 적이 있던 주제인데 이번에 처음 3학점 특강 과목으로 개설되었습니다. 학부 고년차나 대학원생의 경우 학부때 배우는 복소 과목이 어떻게 조합론에서 쓰일 수 있나 알아보는 기회가 되겠습니다. 특히 어떤 조합적 대상의 수를 asymptotic하게 새는 도구들을 배우게 된다고 보시면 됩니다. 과목을 마치게 되면 생성함수를 잘 다루게 될 것이고, 생성함수를 복소평면 위에서의 함수로 이해한 다음 singular point들을 찾아서 분석하는 기술을 습득하게 될 겁니다. 그 외에 다른 재미있는 주제가 있을 것 같습니다.
- 교재: 참고도서만 지정되어 있습니다.
- Analytic Combinatorics, Philippe Flajolet and Robert Sedgewick, Cambridge University Press, 2009
- 810페이지짜리 두꺼운 책입니다. 저는 16만원 넘게 주고 산 책인데, 이 책의 홈페이지에서 PDF로 다운받을 수 있습니다.
- Analytic Combinatorics in Several Variables, Robin Pemantle and Mark C. Wilson, 2013
- 역시 책의 홈페이지에서 draft 버젼의 PDF를 살펴볼 수 있습니다.
- Analytic Combinatorics, Philippe Flajolet and Robert Sedgewick, Cambridge University Press, 2009
아래는 그 외에 눈 여겨 본 과목들입니다. 일부 내용은 실라버스에서 발췌한 것입니다.
- CS422 계산이론 (Martin Ziegler 교수님)
- The Theory of Computation provides a sound logical foundation to computer science. By comparing various formal models of computation with respect to their capabilities, it identifies both fundamental features and ultimate limitations of contemporary digital computing machinery. Rigorous notions of efficiency are captured by famous complexity classes such as P and PSPACE; and concepts like oracles or polynomial-time reduction permit to compare computational problems with respect to their algorithmic cost: NP-hardness results thus serve as ‘beacons’ of intractability.
- EE412 빅데이터 분석 개론 (신진우 교수님)
- EE488A 머신러닝 소개 (유창동 교수님), EE488B 딥러닝과 알파고 (정세영 교수님), CS492E 기계학습입문 (양은호 교수님): 전기전자 및 전산학부 과목인데, 비슷한 주제로 세 과목이 열리네요.
- EE817 Network Science (박홍식 교수님):
- In the first half we deal with fundamental network and graph theory and then study generation, characteristics and analysis of various types of networks such as regular, random, small-world, and scale-free network. In the second half, we study dynamic processes on networks including phase transition, resilience, synchronization, epidemic spreading and information spreading in social networks.
- MAS711 암호 및 부호이론 (한상근 교수님)
- EE623 정보이론 (정혜원 교수님):
- This course is a graduate-level introduction to information theory. Information theory is one of the most elegant mathematical theories, with a direct and significant impact to our lives in the information age. In this class, we will learn how to model the information transmission/processing system, with applications of data science as well as communications, and analyze the model from information-theoretical perspectives to derive fundamental limits on what is possible on the system.
- 전산학부의 기본 과목 중 관련 과목: CS204 이산구조, CS300 알고리듬 개론
- 최적화 관련 산업및 시스템 공학과 교과목들: IE539 컨벡스 최적화 (김우창 교수님), IE631 정수계획법 (박성수 교수님)