• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Научный семинар

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
5
Кредиты

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

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

Аннотация

Основой содержание дисциплины «Научный семинар» являются обучение слушателей основам публичного научного доклада. Паре слушателей даётся новая для них тема из дискретной математики и смежных областей и по ней они должны сделать доклад, рассчитанный на 1 час. После доклада они должны ответить на вопросы (10 мин.). Остаток занятия посвящён разбору преподавателем доклада и уточнению им упущенных моментов.
Цель освоения дисциплины

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

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

Результаты освоения дисциплины

  • Изучение базовых алгоритмов на графах
  • Изучение понятия NP-полноты
  • Изучение скорости работы операций и особенностей различных структур данных
  • Изучение базавых LZW алгоритмов
  • Нетривиальные сортировки и сортировки за линейное время
  • Прочие одиночные темы и темы по выбору докладчиков
Содержание учебной дисциплины

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

  • Графы и их задачи на графах
    Эйлеровость, задача о хроматическом числе, изоморфизм графов, задачи о паросочетании и клике.
  • NP-полные задачи
    Задачи о рюкзаке и максимальном потоке
  • Структуры данных,
    Кучи, КЧ-деревья
  • Сжатие информации
    Сжатие без потерь, словарные сжатия
  • Сортировки
    Сортировки за линейное время, сортировки с использованием продвинутых структур данных
  • Прочие темы
    Простые числа, числа Мерсена, задача поиска подстроки, реккурентные соотношения и прочие темы, в том числе и выбранные слушателем.
Элементы контроля

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

  • неблокирующий Зачёт за 1 модуль
  • неблокирующий Экзамен за курс
  • неблокирующий Доклад в паре - 1-2 модуль
  • неблокирующий Доклад в тройке - 3 модуль
Промежуточная аттестация

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

  • Промежуточная аттестация (1 модуль)
    0.7 * Доклад в паре - 1-2 модуль + 0.3 * Зачёт за 1 модуль
  • Промежуточная аттестация (3 модуль)
    0.3 * Доклад в тройке - 3 модуль + 0.5 * Промежуточная аттестация (1 модуль) + 0.2 * Экзамен за курс
Список литературы

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

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

  • Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018

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

  • Бинарные отношения, графы и коллективные решения, учебное пособие, 2-е изд., перераб. и доп., 341 с., Алескеров, Ф. Т., Хабина, Э. Л., Шварц, Д. А., 2017
  • Бинарные отношения, графы и коллективные решения, учебное пособие, 298 с., Алескеров, Ф. Т., Хабина, Э. Л., Шварц, Д. А., 2006
  • Графы и алгоритмы. Структуры данных. Модели вычислений, учебник, 319 с., Алексеев, В. Е., Таланов, В. А., 2012