현실에서 발생하는 최적화 문제는 많은 경우, 효율적인 알고리즘을 갖지 않는 NP-hard 문제이다. 본 강의에서는 우선 이러한 문제를 식별하는데, 기본이 되는 최적화 계산론, 다항 변환 등을 도입한다. 그리고 NP-hard 문제의 좋은 해를 효율적으로 구하는 다양한 접근법을 다룬다.