Прикладная математика I: алгоритмы и автоматы

2016/2017

Статус: Дисциплина общефакультетского пула

Кто читает: Факультет математики

Где читается: Факультет математики

Когда читается: 1, 2 модуль

Преподаватели: Саватеев Юрий Вячеславович

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

Кредиты: 5

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

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

Аннотация

Изучение данной дисциплины базируется на обязательной дисциплине «Логика и алгоритмы». Для освоения учебной дисциплины студенты должны свободно владеть основными базовыми понятиями теории множеств и математической логики.

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

Формирование у слушателей ясного представления об основных понятиях и методах, лежащих в основе современных теории автоматов, теории вычислимости и сложности вычислений
Получение сведений о важнейших теоремах и конструкциях в этих теориях
Ознакомление с некоторыми приложениями этих теорий в математике и теоретической информатике

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

Освоил методы построения алгоритмов для различных математических задач

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

Конечные автоматы
Регулярные выражения
Контекстно –свободные грамматики
Автоматы с магазинной памятью
Машины Тьюринга
Разрешимость и перечислимость
Неразрешимые задачи
Сводимость
Временная сложность, класс P
Класс NP
Пространственная сложность, класс PSPACE
Классы L и NL

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

Участие студента в решении и разборе задач на семинарах
Письменный экзамен
Включает в себя теоретический вопрос и три задачи, по одной из каждого раздела курса. Время написания — 2 часа.

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

Промежуточная аттестация (2 модуль)
0.7 * Письменный экзамен + 0.3 * Участие студента в решении и разборе задач на семинарах

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