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

Аспирантура 2021/2022

Статус: Курс по выбору

Направление: 09.06.01. Информатика и вычислительная техника

Кто читает: Департамент информатики

Когда читается: 2-й курс, 1 семестр

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

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

Язык: русский

Кредиты: 4

Контактные часы: 36

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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