Проблема (не)равенства классов P и NP — одна из «задач тысячелетия», за каждую из которых объявлен приз в миллион долларов. Имеется большой список NP-полных задач, включающий такие известные задачи как задачи коммивояжера, о рюкзаке, о хроматическом числе графа, целочисленного линейного программирования и многие другие. Довольно неожиданно разные NP-полные задачи (полиномиально эквивалентные с точки зрения точных алгоритмов) оказывается ведут себя совершенно по-разному с точки зрения приближенных. В курсовой работе предлагается разобраться в теории NP-полных задач и попробовать на практике разные методы их решения (с использованием динамического и линейного программирования, приближенные и эвристические методы).