학부 데이터구조, 알고리즘 수업에서는 Sorting, Queue, Stack, tree, graph 이런거 배웠는데, 그 이후에 대한 얘기를 하는 과목

다음 수업까지는 refresh겸 기초를 다루겠다. 별도로 기본 개념들에 대해서는 list-up해줄테니 알아서 찾아보고, 수업에서는 NP문제를 중점으로 다룬다

• NP: Nondeterministic Polynomial time (비결정론적 다항시간), Computational Complexity Theory (계산복잡도 이론)에서 중요한 개념
• 특정 입력에 대해 ‘해’를 주면 그 해가 올바른지 판단은 Polynomial time내에 가능하지만 직접 Optimal 해를 찾는 것은 어려운 문제들. 복잡한 개념이 있는 것 같지만 일단 패스
• 그 유명한거 인접 도시 다 도는 최단 경로 알고리즘 뭐 이런 문제? 같은거

중간고사는 이론으로 하고, 기말은 프로젝트 진행

• 프로젝트는 2명 묶어서 할 거고 4월 말?까지는 팀이 구성되면 좋겠다
• Idea 제안, 진척 사항, 결과 등 다수 발표가 있을 것이고 한 번씩은 꼭 발표해라. 평가해야된다.
• 교수님이 제안하는 문제가 있을거고, 그 문제를 해결하기 위한 Algorithm Design
• 결과가 최고의 알고리즘일 필요는 없지만 정상 Running(완성도)되고 랜덤 보다는 나아야함

Course overview 장표 설명

• Machine Dependent한 부분 (Compiler, Computer Architecture)는 제외하고 프로그램에서 활용하는 Algoritm을 다루고, 이 마저도 굉장히 넓은 범위지만 NP 문제 위주로 다룬다

• NP 문제라면 현 상태에서 풀기 아주 오래 걸리는 (수백만년 등..) 문제, 그래서 퀀텀 컴퓨터에 대한 기대가 크고.. 한계와 방향들에 대해 얘기하심. 퀀텀 상용화되면 필요없는 과목이라고.

• Why 배우는가? 문제를 해결하기 위해서임. Step by Step의 명시화, 효율화 등..

• 예를들어 5개의 제각각 서버에서 30개의 Application을 실행시킬 때 어떤게 최적인가?

  • 경우의 수 5^30 : single processor 기준 1nano에 하나 계산해도 3만년 걸림
  • 다른 방법이 필요함 ⇒ 통상 Heuristic(빠르고 현실적인 해결, 일종의 경험적 규칙?)라고
  • 기계 학습도 일종의 Heuristic, 최적인지는 모르겠지만 어쨌든 결과가 나오는 것

  

다음 주는 휴강

교수님이 공부하라고 한 거