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

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

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

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

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент информатики

Где читается: Санкт-Петербургская школа физико-математических и компьютерных наук

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

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

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

Преподаватели: Гаевой Никита Сергеевич, Копелиович Сергей Владимирович, Мухин Михаил Сергеевич, Олемская Александра Витальевна, Подкопаев Антон Викторович

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

Кредиты: 3

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

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

Аннотация

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

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

Формирование у студентов теоретических знаний и практических навыков в области теории алгоритмов, современных структур данных и их реализации на языке программирования C++ для построения математических моделей дискретных структур и разработки программного обеспечения.

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

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

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

Основые понятия теории алгоритмов и структур данных
Динамическое программирования.
Комбинаторные и графовые алгоритмы
Элементы теории сложности алгоритмов.
Кратчайшие пути. Жадные алгоритмы
Деревья поиска, деревья отрезков и другие аналогичные структуры
Алгоритмы на графах.
Потоки в орграфах. Строки
Игры на графах. Быстрое преобразование Фурье. Линейная алгебра

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

Домашнее задание №1
Домашнее задание №2
Домашнее задание №3
Домашнее задание №4
Письменный экзамен №1
Письменный экзамен №2
Письменный экзамен №3
Письменный экзамен №4
Домашнее задание №1
Домашнее задание №2
Домашнее задание №3
Домашнее задание №4
Письменный экзамен №3
Письменный экзамен №4
Экзамен проводится в устной форме. Экзамен проводится на платформе Zoom. К экзамену необходимо подключиться согласно расписанию, высланному преподавателем накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры, микрофона, возможность записи экрана, поддержка Zoom. Для участия в экзамене студент обязан: явиться к согласно расписанию, включить камеру, микрофон, запись экрана. Во время экзамена студентам запрещено: выключать камеру, общаться или переписываться с кем-либо, кроме принимающих экзамен. Во время экзамена студентам разрешено: пользоваться бумажными и электронными конспектами или другими материалами. Кратковременным нарушением связи во время экзамена считается нарушение связи меньше одной минуты. Долговременным нарушением связи во время экзамена считается нарушение минута и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.

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

2020/2021 учебный год 2 модуль
0.41 * Домашнее задание №2 + 0.59 * Домашнее задание №1
2020/2021 учебный год 4 модуль
0.41 * Письменный экзамен №4 + 0.59 * Домашнее задание №4
2021/2022 учебный год 2 модуль
0.25 * Домашнее задание №4 + 0.5 * Письменный экзамен №4 + 0.25 * Домашнее задание №3

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

Авторы

Кузнецов Антон Михайлович

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