Алгоритмы и структуры данных

Бакалавриат 2024/2025

Статус: Курс обязательный (Бизнес-информатика)

Направление: 38.03.05. Бизнес-информатика

Кто читает: Департамент бизнес-информатики и операционного менеджмента

Где читается: Санкт-Петербургская школа экономики и менеджмента

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

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

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

Преподаватели: Окусков Иван Сергеевич, Романцов Семен Денисович

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

Кредиты: 6

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

Аннотация

Курс «Алгоритмы и структуры данных» направлен на изучение подходов к решению задач из различных областей. Лекционный материал состоит из теоретического описания алгоритмов и структур данных для решения алгоритмических задач. Семинары представляют собой применение и реализацию описанного на лекции материала.

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

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

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

Понимает основные модели вычислений и методы анализа алгоритмов, включая оценку их временной и пространственной сложности
Умеет реализовывать эффективные алгоритмы сортировки и поиска средствами языка программирования Python
Способен объяснять принцип работы алгоритма и применить его.
Знает основные структуры данных, умеет строить их и использовать для решения практических задач
Умеет решать задачи, связанные с отрезками, включая применение персистентных структур данных для хранения и обработки информации
Разбирается в основах теории графов, включая основные определения и свойства графов
Умеет находить кратчайшие пути и минимальные остовы с использованием известных алгоритмов.
Способен реализовывать алгоритмы поиска минимальных путей средствами языка программирования Python
Понимает алгоритмы для решения задач на нахождение максимального потока и задачи о паросочетаниях в графах

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

Паросочетания и задачи о максимальном потоке
Кратчайшие пути и минимальные остовы
Вводная лекция. Модель вычислений и методы анализа алгоритмов
Эффективные алгоритмы сортировки и поиска
Структуры данных. Бинарные деревья поиска и сбалансированные деревья
Задачи на отрезках. Персистентные структуры данных
Теория графов

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

Текущий контроль работы на семинарах
Проводится офлайн с показом студентом экрана с выполненным заданием/работающим кодом и объяснением логики решения задачи, если оно необходимо. Объем выполненных заданий должен соответствовать объему заданий в соответствии с планом работы группы.
Практические задания
Описание задания Разработайте программу на языке Python для реализации и сравнения эффективности различных алгоритмов сортировки массивов. Цели задания: 1. Освоить практическое применение алгоритмов сортировки 2. Научиться анализировать и сравнивать эффективность алгоритмов 3. Развить навыки программирования на Python 4. Улучшить понимание структур данных и их использования Шаги выполнения задания: Реализуйте следующие алгоритмы сортировки: Пузырьковая сортировка (Bubble Sort) Сортировка вставками (Insertion Sort) Быстрая сортировка (Quick Sort) Сортировка слиянием (Merge Sort) Создайте функцию для генерации случайных массивов различных размеров (100, 1000, 10000 элементов) Напишите код для измерения времени выполнения каждого алгоритма сортировки на сгенерированных массивах Проведите эксперименты, запустив каждый алгоритм на массивах разных размеров не менее 10 раз Соберите и проанализируйте данные о времени выполнения каждого алгоритма Создайте графики, отображающие зависимость времени выполнения от размера массива для каждого алгоритма Напишите краткий отчет, сравнивающий эффективность реализованных алгоритмов сортировки Подготовка отчета: 1. Опишите реализованные алгоритмы сортировки и их основные характеристики 2. Представьте результаты экспериментов в виде таблиц и графиков 3. Проанализируйте полученные результаты, сравнив эффективность алгоритмов 4. Сделайте выводы о преимуществах и недостатках каждого алгоритма 5. Укажите, в каких ситуациях каждый алгоритм может быть наиболее эффективен 6. Приложите исходный код программы Подача задания: 1. Предоставьте отчет в формате PDF 2. Загрузите исходный код программы в виде архива ZIP 3. Укажите свое имя, группу и номер задания в названии файлов
Контрольная работа №1
Контрольная работа 1 включает в себя 3 задания. Каждое задание оценивается максимум в 2 балла
Контрольная работа №2
Контрольная работа 2 включает в себя 3 задания. Каждое задание оценивается максимум в 2 балла
Экзамен
Проводится офлайн с использованием IDE Visual Studio Code и Python 3.12. Экзамен предусматривает тестовую часть, задания открытой формы и практическую часть. Тест и задания открытой формы выполняются на экзаменационном бланке, практические задания выполняются на компьютере университета. Число тестовых заданий, заданий открытой формы и практических заданий 4, 2 и 2 соответственно.

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

2024/2025 4th module
0.15 * Контрольная работа №1 + 0.15 * Контрольная работа №2 + 0.2 * Практические задания + 0.1 * Текущий контроль работы на семинарах + 0.4 * Экзамен

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

Авторы

Романцов Семен Денисович
Окусков Иван Сергеевич
Орлова Екатерина Дмитриевна

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