• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2024/2025

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

Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 3-й курс, 1-4 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Язык: русский
Кредиты: 4

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

Аннотация

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

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

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

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

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

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

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

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

  • неблокирующий Посещение научных мероприятий
    В части посещения научных мероприятий студенты по своему выбору в течение года посещают научные мероприятия, интересные с точки зрения теоретической информатики. Это могут быть конференции, школы, семинары, мини-курсы и курсы, которые не засчитываются в оценку по другим курсам. Курс произвольной длины засчитывается как 2 семинара. В случае сомнений в том, будет ли мероприятие засчитано в НИС, стоит согласовать мероприятие с руководителями специализации. О некоторых мероприятиях, которые можно засчитывать в НИС появляется информация в телеграмм канале специализации, который называется специализация ТИ.
  • неблокирующий Реферат
    В каждом модуле необходимо написать реферат по одной из предложенных статей. Список статей объявляется в начале модуля. Каждая статья реферируется одним студентом. Выбрать статью для реферата необходимо в указанные сроки, иначе реферат в данном модуле не засчитывается. Информация о статьях и другие организационные объявления (сроки сдачи рефератов и т. п.) публикуются в телеграмм канале Курсы по выбору и НИС ТИ, на который нужно обязательно подписаться, и на вики-странице курса. Объем реферата должен не превосходить 1.5 стандартных страниц TeX’а. В реферате нужно рассказать о статье по следующему плану: 1. Содержание статьи. 2. Оценка вклада статьи в развитие науки (чем интересна, какие возможны приложения и т. п.) с точки зрения автора реферата. Желательны аргументы в пользу приводимой оценки статьи. 3. Краткое описание техники основных доказательств. Пункт 3 обязателен для получения оценок 9, 10; хорошо исполненных первых двух пунктов достаточно для получения оценки 8.
  • неблокирующий Экзамен
    Экзамен проводится в конце курса в формате собеседования. На экзамене обсуждается содержание посещенных студентом семинаров в целом, а также какая-то одна из прослушанных тем по выбору студента. Рассказ должен быть построен по тому же плану, что и реферат, но в устной форме. Максимальная длительность рассказа — 20 минут.
Промежуточная аттестация

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

  • 2024/2025 4th module
    Итог = Округление(0.3 * СМ + 0.3 * РФ + 0.4 * Э), где СМ — оценка за посещение мероприятий, РФ — средняя оценка за написание рефератов, Э — оценка за экзамен.
Список литературы

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

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

  • 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

Авторы

  • Вялый Михаил Николаевич
  • Сысоева Алевтина Александровна