• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 2019/2020

Методы теоретической информатики

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

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

Аннотация

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

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

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

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

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

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

  • Анализ Фурье над конечными полями
    Базовые понятия анализа Фурье, его приложения в различных разделах теоретической информатики.
  • Вероятностные методы
    Неравенство Чернова и его применения. Обобщение на зависимые случайные величины.
  • Полиномиальный метод
    Представление булевых функций многочленами, приложения в сложности разрешающих деревьев, сложности булевых схем, коммуникационной сложности.
  • Применение методов линейного и выпуклого программирования для решения задач комбинаторной оптимизации
    Примеры ЛП и SDP релаксаций задач комбинаторного программирования. Приближенные алгоритмы их решения.
Элементы контроля

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

  • неблокирующий Домашнее задание
  • неблокирующий Коллоквиум
    Оценка за дисциплину выставляется в соответствии с формулой оценивания от всех пройденных элементов контроля. Экзамен не проводится.
  • неблокирующий Контрольная работа
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.35 * Домашнее задание + 0.5 * Коллоквиум + 0.15 * Контрольная работа
Список литературы

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

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

  • Зверев Г.Н. - Теоретическая информатика и ее основания. Т.1 - Издательство "Физматлит" - 2007 - 592с. - ISBN: 978-5-9221-0925-3 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/2386
  • Зверев Г.Н. - Теоретическая информатика и её основания. Том 2 - Издательство "Физматлит" - 2008 - 576с. - ISBN: 978-5-9221-1061-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/2378

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

  • Ульянов М.В. - Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ - Издательство "Физматлит" - 2008 - 304с. - ISBN: 978-5-9221-0950-5 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/2354