Desperate Undergraduate!Desperate Undergraduate!

HW#14 : Dijkstra's Algorithm for Single Source Shortest Path Problem은 Greedy Method이면서 최적인 이유는 무엇인가?(Optimality Proof)

이번 네트워크응용설계의 주제는 "SNMP(Simple Network Management Protocol)"이였다. 침해사고대응팀에 있을 때 우리의 관제 대상 중 하나가 바로 전체 시스템의 장애 유무 였다. 모든 장비는 Manager에게 시스템의 현재 상태를 보고 하는 패킷을 보내주었고 EMS(Enterprise Management System)으로도 패킷을 보내었다.

그 당시에 SNMP는 신기한 프로토콜이였다. 이렇게 많은 네트워크 장비를 손쉽게 관리할 수 있다는 사실이 무척 흥미로웠다. 또한 장비의 장애 유무를 세심하게 볼 수 있었다. 각 장비의 Port에 대한 정보부터 시작하여 기본적인 CPU 사용률, Memory 사용률, Disk 사용률을 손쉽게 파악할 수 있었다. 또한 어떤 장비의 경우 원격으로 명령을 내릴 수 있기도 하였다.

한 가지 기억에 또 남는 것이 있다면 발전기를 점검할 때 이다. 주기적으로 발전기 점검을 하게 된다. 이 때 UPS가 잘 동작하는지도 확인한다. 하지만 UPS가 버틸 수 있는 시간에는 한계가 있기 때문에 핵심적인 장비 외에는 전원을 내린다. 그렇게 되면 SNMP 솔루션 프로그램에 망에 전부 파란색에서 빨간색으로 표시된다. 평상시같으면 큰일이지만 이 때는 괜찮다. 이런 기회가 없겠다 싶어서 화면을 갈무리 해놓던 것이 기억난다. 하지만 이것 역시 보안상 취약점이 있다. 수업 시간에도 언급하였듯이 망 정보는 밖으로 나가면 안되는 정보이다. 라우팅 테이블 역시 마찬가지이다. 예전에 유투브와 관련된 해킹 사건 역시 라우팅 테이블과 관련이 있었다.

수업을 듣던 중 옛날 생각이 나서 이렇게 글을 남긴다. 또한 현재 생각해 두고 있는 IPS 시스템을 만든다면 꼭 SNMP 기능을 구현해 보고 싶다.

알고리즘 앞반 퀴즈
A에서 J도시까지 최소비용경로 구하기.

알고리즘 뒷반 퀴즈
배낭채우기 문제.

Algorithm, Spring 2011

Course Description and Goals
본 과목은 컴퓨터공학에서 다루는 문제들을 해결하기 위한 가장 기본적이며 중요한 원칙들과 해결기법 및 전략에 대해서 강의한다. 컴퓨터공학부 3학년이 수강대상이며, 이에 준하는 수준에서 강의를 진행한다.

컴퓨터공학의 다양한 문제해결을 위한 전략을 설계하고 분석하는 것을 주요 강의 내용으로 다루며, 수강생들이 이를 효과적으로 습득하기 위해서 선수과목으로 프로그래밍 관련 과목과 데이터구조 분석/설계를 필히 이수하고 수강하여야 한다. 선수과목에서 다루어진 내용에 대해서는 강의를 생략할 예정이며, 선수과목을 미이수한 학생들은 수강신청 시 유의하여야 한다.

본 과목의 목표는 학생들이 한 학기 알고리즘을 수강한 후, 이후 직면할 수 있는 다양한 컴퓨터공학의 문제들을 효과적으로 해결할 수 있는 컴퓨터공학적 사고를 할수 있도록 하는 것이며, 주어진 문제에 대해서 가장 효과적인 접근방식 및 전략 (Approach and Strategy)를 설계하고, 제안한 알고리즘에 대한 수학적 분석을 통해 그 우월성을 입증할 수 있는 능력을 배양하게 된다.

본 과목에 대한 컴퓨터공학심화 프로그램 교과목 학습성과 구성은 다음과 같음: 학습성과-1(20%), 학습성과-2(30%), 학습성과-3(30%), 학습성과-4(20%)

Course Procedures and Evaluation
강의는 지도교수에 의한 이론강의를 중심으로 하며, 학생들의 수업참여도를 높이기 위한 질의응답, 토론을 적극 활용한다. 학생들은 제시된 교재의 심화된 내용을 반드시 스스로 학습하여 자신만의 알고리즘 설계 및 분석 능력을 습득할 수 있어야 한다.

또한, 학습한 내용에 대한 적극적인 습득을 위해 정기적인 숙제 및 퀴즈를 실시한다. 숙제는 워드프로세서를 사용하지 않고, 자신만의 유일한 예제를 만들고 연필을 이용하여 손으로 직접 풀어서 제출한다.

평가는 중간고사, 기말고사, PreTest, 퀴즈 및 숙제 점수를 반영하여 최종 성적을 산출함.
1. 중간고사는 30점 만점으로 실시함.
2. 기말고사는 30점 만점으로 실시함.
3. PreTest는 10점 만점으로 실시함 (2회:5점/회).
4. 퀴즈 및 숙제는 30점 만점으로 실시함 (퀴즈 2회:4점/회, 숙제 22회:1점/회)

Reference Textbooks
1. Foundations of Algorithms Using C++ Pseudocode by R. Neapolitan et al., Addison Wesley.
3. Introduction to Algorithms by T.H. Cormen et al., MIT Press.

Lecture Schedule and Homeworks
WEEK 1: Introduction and Design & Analysis of Algorithm
WEEK 2: Divide and Conquer (Binary Search and Merge Sort)
WEEK 3: Divide and Conquer (Quick Sort), Dynamic Programming (Binomial Coefficient)
WEEK 4: Dynamic Programming (Bionomial Coefficient, All-Pairs SP)
WEEK 5: Dynamic Programmin (All-Pairs SP, Chained Matrix Multiplication)
WEEK 6: Dynamic Programming (CMM) and Greedy (Minimum Spanning Trees)
WEEK 7: Greedy (Minimum Spanning Trees) and Pre-Test
WEEK 8: Mid-Term Exam
WEEK 9: Dynamic Programming vs Greedy (The Knapsack Problem)
WEEK 10: Backtracking (N-Queens/ Sum-of-Subsets/ Graph Coloring Problem)
WEEK 11: Backtracking (TSP Problem, 0/1 Knapsack Problem)
WEEK 12: Branch and Bound (0/1 Knapsack Problem), Best-First Search
WEEK 13: Theory of NP (Decision Problem, Optimization Problem)
WEEK 14: Theory of NP (NP-Complete Problem)
WEEK 15: Theory of NP (NP-Hard Problem, Approximation Algorithm) and Pre-Test
WEEK 16: Final Exam