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

Современные методы принятия решений: алгоритмы и структуры данных

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

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

Аннотация

Данный курс покрывает базовые алгоритмы и структуры данных и полезен студентам любого IT-направления. В рамках курса студенты познакомятся с понятиями асимптотической сложности, научатся оценивать сложность алгоритмов, а также изучат базовые алгоритмы, которые зачастую спрашивают при прохождении собеседований на различные IT- позиции.
Цель освоения дисциплины

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

  • Знать основные структуры данных
  • Знать способы реализации основных структур данных на языке C++, включая средства стандартной библиотеки (STL)
  • Знать основные методы поиска (линейный и бинарный)
  • Знать различные методы сортировок (линейные, итерационные, рекурсивные)
  • Уметь проводить оценку сложности простых алгоритмов
  • Уметь реализовывать различные методы поиска на языке C++
  • Уметь реализовывать различные методы сортировок на языке C++
  • Уметь решать задачи, связанные с сортировками и методами поиска
Планируемые результаты обучения

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

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

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

  • Простые алгоритмы и асимптотическая оценка их сложности
  • Простые структуры данных.
  • Методы поиска. Линейный поиск. Бинарный поиск.
  • Итерационные сортировки. Сортировка пузырьком. Сортировка выбором. Сортировка простыми вставками. Сортировка бинарными вставками.
  • Линейные сортировки. Сортировка подсчетом. Цифровая сортировка (LSD, MSD).
  • Рекурсия. Понятие прямой и косвенной рекурсии. Задача о Ханойских башнях.
  • Рекурсивные сортировки. Сортировка слиянием. Быстрая сортировка.
  • Двоичная куча. Пирамидальная сортировка.
Элементы контроля

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

  • неблокирующий Домашнее задание
    Есть бонусное задание (Бонус)
  • неблокирующий Экзамен
    Итог = Округление(0.7 * Накоп + 0.3 * Э). Округление арифметическое. Если Накоп >=8, то студент может получить Накоп в качестве итоговой оценки, не приходя на экзамен. В рамках курса по каждой теме предусмотрено бонусное задание. Выдается на каждой неделе после проведения лекции и семинара на соответствующую тему. Форма проведения – решение задач в системе Яндекс.Контест. За каждый решенный блок задач можно получить до 2 баллов к оценке за основное домашнее задание по соответствующей теме. Дедлайн по всем задачам – 1 неделя после последнего занятия.
Промежуточная аттестация

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

  • 2021/2022 учебный год 3 модуль
    0.3 * Экзамен + 0.7 * Домашнее задание
Список литературы

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

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

  • Алгоритмы: построение и анализ, Кормен, Т., 2007
  • Структуры данных и алгоритмы, Ахо, А. В., 2010

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

  • Дискретная математика для программистов, Новиков, Ф. А., 2001
  • Дискретная математика для программистов, Хаггард, Г., 2010
  • Структуры данных и алгоритмы Java, Лафоре, Р., 2014