Бакалавриат 2024/2025

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

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

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

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

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

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

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

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

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

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

Кредиты: 5

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

Аннотация

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

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

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

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

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

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

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

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

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

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

• 2024/2025 3rd module
  0.3 * Домашнее задание + 0.7 * Устный экзамен

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

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

• 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

Авторы

• Подольский Владимир Владимирович
• Вялый Михаил Николаевич