Построение и анализ алгоритмов

2021/2022

Учебный год

RUS

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

4

Кредиты

Кто читает:

Департамент программной инженерии

Статус:

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

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

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

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

Бессмертный Александр Игоревич

Варгулёв Александр Сергоевич

Горденко Мария Константиновна

Нестеров Роман Александрович

Топтунов Александр Алексеевич

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

Аннотация

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

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

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

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

• знать основы асимптотического анализа сложности алгоритмов
• знать алгоритмы поиска кратчайших путей в графе
• знать алгоритмы поиска потока графов
• знать асимптотику основных алгоритмов обработки строк
• знать основные алгоритмы поиска
• знать основные варианты классификации сортировок
• знать основные виды итеративных сортировок
• знать основные виды сортировок
• знать основные понятия комбинаторики: сочетания, перестановки, размещения
• знать основные теоретико числовые алгоритмы
• знать представления графов в памяти компьютера
• знать разницу симметричных и ассиметричных методов шифрования
• уметь оценивать асимптотику рекурсивных алгоритмов
• уметь оценивать временную сложность итеративных алгоритмов сортировки
• уметь оценивать сложность алгоритмов
• уметь оценивать сложность рекурсивных алгоритмов сортировки
• уметь писать рекурсивные алгоритмы
• уметь применять основные алгоритмы поиска
• уметь производить асимптотическую оценку сложности линейных сортировок
• уметь реализовывать алгоритмы генерации перестановок, размещений, сочетаний с повторениями, комбинаций и разбиений
• уметь реализовывать алгоритмы генерации перестановок, сочетаний и размещений
• уметь реализовывать алгоритмы обхода графов
• уметь реализовывать алгоритмы поиска кратчайших путей в графе
• уметь реализовывать алгоритмы поиска потоков в графе
• уметь реализовывать алгоритмы Хаффмана и Шеннона-Фано
• уметь реализовывать алгоритмы, основанные на обходах
• уметь реализовывать динамические алгоритмы
• уметь реализовывать линейный сортировки
• уметь реализовывать основные алгоритмы итеративных сортировок
• уметь реализовывать основные алгоритмы обработки строк
• уметь реализовывать основные алгоритмы шифрования
• уметь реализовывать основные теоретико числовые алгоритмы
• уметь реализовывать рекурсивные сортировки

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

• Асимптотический анализ алгоритмов
• Задача поиска
• Задача сортировки
• Итеративные сортировки
• Линейные сортировки
• Понятие рекурсии. Основные задачи рекурсии. Задача о ханойских башнях.
• Рекурсивные сортировки. Двоичная куча. Пирамидальная сортировка. Сортировка слиянием. Быстрая сортировка.
• Основные понятия теории графов. Представление графов в памяти компьютера. Алгоритмы обхода графов.
• Алгоритмы, основанные на обходах графов.
• Алгоритмы поиска кратчайших путей в графе.
• Алгоритмы поиска потока в графе.
• Задачи комбинаторики. Понятие перестановок, сочетаний, размещений. Алгоритмы генерации перестановок, сочетаний и размещений без повторений.
• Комбинаторные алгоритмы. Генерация перестановок, размещений и сочетаний с повторениями. Генерация комбинаций и разбиений.
• Алгоритмы обработки строк
• Кодирование и шифрование. Алгоритм Хаффмана. Алгоритм Шеннона-Фано.
• Шифрование. Симметричное и ассиметричное шифрование. Алгоритм RSA.
• Динамическое программирование. Основные задачи, решаемые с помощью динамического программирования.
• Теоретико числовые алгоритмы.

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

• КДЗ
  Контрольное домашнее задание по оценке сортировок
• Работа на семинарах
• Экзамен
  Возможна замена на письменный тест.
• Контексты
  Контест состоит из нескольких задач по пройденной теме.

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

• 2021/2022 учебный год 4 модуль
  0.56 * Контексты + 0.3 * Экзамен + 0.07 * КДЗ + 0.07 * Работа на семинарах

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

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

• Искусство программирования. Т.1: Основные алгоритмы, Кнут, Д. Э., 2011
• Искусство программирования. Т.3: Сортировка и поиск, Кнут, Д. Э., 2012
• Теория рекурсии для программистов, Головешкин, В. А., 2006

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

• Комбинаторика и теория графов. Ч.1: ., Григорьев, Б. В., 2005