Полезная информация
Длительность 4 месяца
Начало обучения: 31 августа 2023 года
Конец обучения: 11 января 2024 года
Theory of Complexity & Computations (Алибиева Жибек) (CSE7552) (2023) (Осень) (Магистратура) (Рус.яз)
Курс изучает основы теории сложности и вычислений. Дается определение вычислительной сложности алгоритма. В курсе рассматриваются вопросы вычислительной и емкостной сложности алгоритмов, их соотношении между собой, эффективности алгоритмов, решающих задачи за полиномиальное время и иных с экспоненциальной зависимостью времени решения от данных. А также изучаются детерминированные и недетерминированные алгоритмы, полиномиально разрешимые задачи, полиномиальные алгоритмы. Приводятся доказательства NP полноты.