Бакалавриат 2022/2023

Научно-исследовательский семинар "Теоретическая информатика 2"

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

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

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

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

Преподаватели: Вялый Михаил Николаевич, Милованов Алексей Сергеевич

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

Кредиты: 5

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

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

Аннотация

Целями освоения научно-исследовательского семинара «Теоретическая информатика» являются освоение основ теоретической информатики, вычислительной логики и искусственного интеллекта, студентов основным понятиям и методам дискретной математики, необходимым как в дальнейшем обучении, так и в работе по специальности. Это даст участникам семинара общее представление об указанных выше областях, а также позволит в дальнейшем заниматься более продвинутыми разделами этих областей.

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

• Освоение основ теоретической информатики. Освоение основ вычислительной логики и искусственного интеллекта. Освоение методов дискретной математики, используемых в теоретической информатике.

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

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

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

• Сложность вычислений
• Сложность булевых схем
• Параметризованная сложность
• Коммуникационная сложность

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

• Домашнее задание
• Устный экзамен
  Экзамен проводится в устной форме с прокторингом в Zoom. Технические требования: web-камера, микрофон, наушники / колонки, Zoom.

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

• 2022/2023 учебный год 3 модуль
  0.7 * Устный экзамен + 0.3 * Домашнее задание

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

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

• Boolean function complexity : advances and frontiers, Jukna, S., 2012
• Communication complexity, Kushilevitz, E., 2006
• Computational complexity : a modern approach, Arora, S., 2010
• Introduction to the theory of computation, Sipser, M., 2013

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

• Parameterized Complexity of Independent Set in H-free graphs. (2018). https://doi.org/10.4230/LIPIcs.CVIT.2016.23

Авторы

• Рословцева Кристина Олеговна
• Милованов Алексей Сергеевич
• Вялый Михаил Николаевич
• Подольский Владимир Владимирович