• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Вычислимость и сложность

Читается: 3-4 модуль 2 курса 

Пререквизиты: «Основания алгебры и геометрии»

Трудоемкость:  5 кредитов

84 аудиторных часа:

  • 42 часа лекции;
  • 42 часа семинары

Формы контроля:

  • 1 экзамен,
  • 1 контрольная работа,
  • 2 домашних задания

О курсе

Цели курса: знакомство с основными вычислительными моделями, используемыми в теории вычислений (машины Тьюринга, равнодоступные адресные машины, схемы из функциональных элементов, вероятностные варианты этих моделей), знакомство с понятиями алгоритма, вычислимой функции, разрешимых и перечислимых множеств. В курсе будут обсуждаться примеры неразрешимых проблем и сведение одних проблем к другим. Слушатели научатся быстро оценивать время и память, требуемые данному алгоритму при его реализации на данной вычислительной модели, различать различные виды трудности задач (трудность для наихудшего входа и трудность для случайно взятого входа).

Программа

Ведущий лектор

Саватеев Юрий Вячеславович

Факультет математики: доцент