Курс изучает основы теории сложности и вычислений. Дается определение вычислительной сложности алгоритма. В курсе рассматриваются вопросы вычислительной и емкостной сложности алгоритмов, их соотношении между собой, эффективности алгоритмов, решающих задачи за полиномиальное время и иных с экспоненциальной зависимостью времени решения от данных. А также изучаются детерминированные и недетерминированные алгоритмы, полиномиально разрешимые задачи, полиномиальные алгоритмы. Приводятся доказательства NP полноты.
- Мұғалім: Жибек Алибиева