Курсы для студентов 2018 года набора: Вычислимость и сложность
Цели курса: знакомство с основными вычислительными моделями, используемыми в теории вычислений (машины Тьюринга, равнодоступные адресные машины, схемы из функциональных элементов, вероятностные варианты этих моделей), знакомство с понятиями алгоритма, вычислимой функции, разрешимых и перечислимых множеств. В курсе будут обсуждаться примеры неразрешимых проблем и сведение одних проблем к другим. Слушатели научатся быстро оценивать время и память, требуемые данному алгоритму при его реализации на данной вычислительной модели, различать различные виды трудности задач (трудность для наихудшего входа и трудность для случайно взятого входа).
Читается: 3-4 модуль 2 курса
Пререквизиты: «Основания алгебры и геометрии»
Трудоемкость: 5 кредитов
84 аудиторных часа:
- 42 часа лекции;
- 42 часа семинары
Формы контроля:
- 1 экзамен,
- 1 контрольная работа,
- 2 домашних задания
Ведущий лектор
факультет математики: cтарший преподаватель
Видеозаписи лекций