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

2023/2024

Учебный год

RUS

Обучение ведется на русском языке

4

Кредиты

Кто читает:

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

Статус:

Курс обязательный

Когда читается:

3-й курс, 1-4 модуль

Преподаватель

Вялый Михаил Николаевич

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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

Авторы

• Вялый Михаил Николаевич