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

Бакалавриат 2022/2023

Статус: Курс по выбору (Программная инженерия)

Направление: 09.03.04. Программная инженерия

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

Где читается: Факультет компьютерных наук

Когда читается: 2-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Бессмертный Александр Игоревич, Горденко Мария Константиновна, Нестеров Роман Александрович, Терлыч Никита Андреевич, Топтунов Александр Алексеевич

Язык: русский

Кредиты: 4

Контактные часы: 72

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

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

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

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

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

2022/2023 учебный год 4 модуль
Оитоговая = 0.3 * Оэкзамен + 0.7 * Онакопленная Онакопленная складывается из: 1. Осам. - решение контестов (Я.Контест) 2. Окдз - КДЗ (3 штуки) 3. Осем - тесты (и другая активность) на семинарах Онакопленная = 0.6 * Осам + 0.3 * Окдз + 0.1 * Осем

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

Авторы

Горденко Мария Константиновна
Петрухина Анастасия Сергеевна

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