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

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

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

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

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

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

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

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

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

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

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

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

Преподаватели: Близнец Иван Анатольевич, Копелиович Сергей Владимирович, Мокеев Александр Сергеевич, Мухин Михаил Сергеевич, Олемская Александра Витальевна, Подкопаев Антон Викторович, Смирнов Петр Юрьевич, Тигина Мария Михайловна

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

Кредиты: 8

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

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

Аннотация

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

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

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

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

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

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

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

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

Коллоквиум №2
Коллоквиум №2 проводится в форме ответов на вопросы билета. Билет содержит два вопроса. На подготовку ответа выделяется 2,5 часа.
Домашнее задание №2
Домашнее задание №2 выдается студентам в одном варианте и состоит из 6 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
Домашнее задание №1
Домашнее задание N№1 выдается студентам в одном варианте и состоит из 6 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
Домашнее задание №3
Домашнее задание №3 выдается студентам в одном варианте и состоит из 6 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
Домашнее задание №4
Домашнее задание №4 выдается студентам в одном варианте и состоит из 5 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
Домашнее задание №5
Домашнее задание №5 выдается студентам в одном варианте и состоит из 6 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
Экзамен №2
Письменный экзамен №2 проводится в форме ответов на вопросы экзаменационного билета. Экзаменационный билет содержит два вопроса из перечня вопросов к экзамену. На подготовку ответа выделяется 2,5 часа.
Домашнее задание №6
Домашнее задание №6 выдается студентам в одном варианте и состоит из 5 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
Коллоквиум №3
Коллоквиум №3 проводится в форме ответов на вопросы билета. Билет содержит два вопроса. На подготовку ответа выделяется 2,5 часа.
Коллоквиум №1
Коллоквиум №1 проводится в форме ответов на вопросы билета. Билет содержит два вопроса. На подготовку ответа выделяется 2,5 часа.
Экзамен №1
Письменный экзамен №1 проводится в форме ответов на вопросы экзаменационного билета. Экзаменационный билет содержит два вопроса из перечня вопросов к экзамену. На подготовку ответа выделяется 2,5 часа.
Экзамен №3
Письменный экзамен №3 проводится в форме ответов на вопросы экзаменационного билета. Экзаменационный билет содержит два вопроса из перечня вопросов к экзамену. На подготовку ответа выделяется 2,5 часа.

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

2021/2022 учебный год 2 модуль
0.3 * Коллоквиум №1 + 0.2 * Домашнее задание №2 + 0.3 * Экзамен №1 + 0.2 * Домашнее задание №1
2021/2022 учебный год 4 модуль
0.3 * Коллоквиум №2 + 0.3 * Экзамен №2 + 0.2 * Домашнее задание №3 + 0.2 * Домашнее задание №4
2022/2023 учебный год 2 модуль
0.3 * Коллоквиум №3 + 0.2 * Домашнее задание №6 + 0.2 * Домашнее задание №5 + 0.3 * Экзамен №3

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

Авторы

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

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