Бакалавриат
2022/2023
Научно-исследовательский семинар "Теоретическая информатика"
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
3-й курс, 1-4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
4
Контактные часы:
72
Программа дисциплины
Аннотация
Целями освоения научно-исследовательского семинара «Теоретическая информатика» являются освоение студентами основ теоретической информатики, вычислительной логики и искусственного интеллекта, основным понятиям и методам дискретной математики, необходимым как в дальнейшем обучении, так и в работе по специальности. Это даст участникам семинара общее представление об указанных выше областях, а также позволит в дальнейшем заниматься более продвинутыми разделами этих областей. Курс организован в виде семинара, на котором планируются выступления как участников семинара, так и гостей факультета - ведущих специалистов в указанных выше областях науки.
Цель освоения дисциплины
- Освоение основ теоретической информатики
- Освоение основ вычислительной логики и искусственного интеллекта
- Освоение методов дискретной математики, используемых в теоретической информатике
- Подготовка к самостоятельной научной работе
- Подготовка к более глубокому изучению указанных выше дисциплин
Планируемые результаты обучения
- Знание основных понятий и методов теоретической информатики, вычислительной логики и искусственного интеллекта
- Навыки изложения и оформления научного материала по данным областям
- Умение самостоятельно осваивать новый материал по данным областям на основании учебных статей и научных статей
Содержание учебной дисциплины
- Сложность вычислений
- Коммуникационная сложность
- Сложность булевых схем
- Сложность пропозициональных доказательств
- Параметризованная сложность
Элементы контроля
- Устный экзаменЭкзамен проводится в устной форме с прокторингом в Zoom. Технические требования: web-камера, микрофон, наушники / колонки, Zoom.
- Домашнее задание
Список литературы
Рекомендуемая основная литература
- 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
- Roughgarden, T. (2015). Communication Complexity (for Algorithm Designers). Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1509.06257