Мы используем файлы cookies для улучшения работы сайта НИУ ВШЭ и большего удобства его использования. Более подробную информацию об использовании файлов cookies можно найти здесь, наши правила обработки персональных данных – здесь. Продолжая пользоваться сайтом, вы подтверждаете, что были проинформированы об использовании файлов cookies сайтом НИУ ВШЭ и согласны с нашими правилами обработки персональных данных. Вы можете отключить файлы cookies в настройках Вашего браузера.

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

Теоретическая инфоpматика

2021/2022
Учебный год
RUS
Обучение ведется на русском языке
4
Кредиты
Статус:
Курс по выбору
Когда читается:
2-й курс, 1 семестр

Преподаватель

Омельченко Александр Владимирович

Омельченко Александр Владимирович

Программа дисциплины

Аннотация

Дисциплина «Теоретическая информатика» относится к блоку дисциплин по выбору вариативной части программы. Дисциплина знакомит аспирантов с теоретическими основами информатики. Для освоения дисциплины необходимы компетенции, полученные в ходе изучения дисциплины «Иностранный (английский) язык для исследователей», а также базовых математических курсов в рамках 1-2 курса бакалавриата.
Цель освоения дисциплины

Цель освоения дисциплины

  • Целью освоения дисциплины «Теоретическая информатика» является знакомство с теоретическими основами информатики и основами теории сложности вычислений.
Планируемые результаты обучения

Планируемые результаты обучения

  • Знать ссновные классы вычислительной сложности, а также установленные связи включения между ними на данный момент
  • Иметь навыки определять принадлежность вычислительной задачи тому или иному классу
  • Иметь навыки построения сведений одних вычислительных задач к другим
  • Уметь доказывать полноту задач в том или ином классе вычислительной сложности
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Вычислительные модели. Класс NP.
  • Метод диагонализации. Различные теоремы и иерархии.
  • Вычислительная сложность по памяти
  • Полиномиальная иерархия
  • Булевы схемы и вероятностные вычисления
Элементы контроля

Элементы контроля

  • неблокирующий Домашнее задание
    Домашнее задание – небольшая письменная работа. В домашнем задании аспирант должен продемонстрировать знание основных концепций дисциплины, умение решать задачи, находить и анализировать необходимые примеры.
  • неблокирующий Аудиторная работа
    Аудиторная работа – участие в обсуждениях по теме семинарского занятия, ответы на вопросы преподавателя. В ходе аудиторной работы аспирант должен продемонстрировать умение ведения обсуждения по теме семинарского занятия и оперативного вовлечения в сформированную дискуссию по поставленным вопросам.
  • блокирующий Устный экзамен
    Итоговый контроль осуществляется в форме устного экзамена. На экзамене аспирант должен продемонстрировать владение основными положениями материала в форме устного ответа на экзаменационные вопросы по предложенной теме. Экзаменационный билет содержит два вопроса. Ответ и время на подготовку – 60 мин.
Промежуточная аттестация

Промежуточная аттестация

  • 2021/2022 учебный год I семестр
    0.3 * Аудиторная работа + 0.3 * Домашнее задание + 0.4 * Устный экзамен
Список литературы

Список литературы

Рекомендуемая основная литература

  • Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
  • Dexter C. Kozen. Theory of Computation (2006), Springer
  • Edward K. Blum, Alfred V. Aho. Computer Science (2011), Springer

Рекомендуемая дополнительная литература

  • Tourlakis, G. J. (2012). Theory of Computation. Hoboken, N.J.: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=451360

Авторы

  • Кузнецов Антон Михайлович
  • Близнец Иван Анатольевич

 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!