Бакалавриат
2020/2021
Алгоритмы и структуры данных
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Департамент информатики
Когда читается:
2-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Язык:
русский
Кредиты:
3
Контактные часы:
66
Программа дисциплины
Аннотация
Данная дисциплина опирается на дисциплины из школьного курса и направлена на овладение навыками использования основных применяемых в программировании структур данных, алгоритмов обработки данных и анализа этих алгоритмов, взаимосвязи алгоритмов и структур данных. В результате изучения этой дисциплины студенты будут иметь практические навыки конструирования конкретных алгоритмов и структур данных для решения разнообразных математических и программистских задач. В результате изучения дисциплины обучающийся должен: знать: - методы оценки сложности алгоритмов в среднем и в худшем случаях; - элементарные структуры данных; - постановки основных задач; - основные классы алгоритмов: «разделяй и властвуй», «жадные алгоритмы», алгоритмы на динамическое программирование; - специализированные структуры данных, используемые в различных алгоритмах. уметь: - оценивать сложность алгоритмов в среднем и в худшем случаях; - выделять из практических задач их алгоритмическую составляющую; - реализовывать изученные алгоритмы и структуры данных на процедурных языках программирования; - выбирать оптимальные алгоритмы и структуры данных, в зависимости от конкретных ограничений на решение задачи; - применять приближённые алгоритмы в тех случаях, когда эффективное точное решение невозможно. владеть: - методами оценки сложности алгоритмов сложность алгоритмов в среднем и в худшем случаях; - навыками реализации алгоритмов и структур данных на процедурных языках программирования.
Цель освоения дисциплины
- Целью освоения дисциплины «Алгоритмы и структуры данных» является формирование у студентов теоретических знаний и практических навыков в области теории алгоритмов, современных структур данных и их реализации на языке программирования C++ для построения математических моделей дискретных структур и разработки программного обеспечения.
Планируемые результаты обучения
- Знает основые понятия теории алгоритмов и структур данных
- Владеет основными понятиями динамисечкого программирования. Владеет понятиями кобинаторики и подмножеств. Знает основные алгоритмы и структуры данных, применяемые для различных задач.
- Знает основные способы модификации базовых алгоритмов, применяемые для различных задач.
- Использует базовые алгоритмы и подходы и модифицирует их, исходя из специфики решаемой задачи.
- Подбирает оптимальный алгоритм для конкретной практической задачи, анализирует его эффективность.
- Формализует и описывает алгоритм решения поставленных практических задач. Математически корректно и адекватно записывает алгоритмы, наиболее корректно описывающие дискретные объекты прикладной задачи.
Содержание учебной дисциплины
- Основые понятия теории алгоритмов и структур данных
- Динамическое программирования.
- Комбинаторные и графовые алгоритмы
- Элементы теории сложности алгоритмов.
- Кратчайшие пути. Жадные алгоритмы
- Деревья поиска, деревья отрезков и другие аналогичные структуры
- Алгоритмы на графах.
- Потоки в орграфах. Строки
- Игры на графах. Быстрое преобразование Фурье. Линейная алгебра
Элементы контроля
- Домашнее задание №1
- Домашнее задание №2
- Домашнее задание №3
- Домашнее задание №4
- Письменный экзамен №1
- Письменный экзамен №2
- Письменный экзамен №3
- Письменный экзамен №4Экзамен проводится в устной форме. Экзамен проводится на платформе Zoom. К экзамену необходимо подключиться согласно расписанию, высланному преподавателем накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры, микрофона, возможность записи экрана, поддержка Zoom. Для участия в экзамене студент обязан: явиться к согласно расписанию, включить камеру, микрофон, запись экрана. Во время экзамена студентам запрещено: выключать камеру, общаться или переписываться с кем-либо, кроме принимающих экзамен. Во время экзамена студентам разрешено: пользоваться бумажными и электронными конспектами или другими материалами. Кратковременным нарушением связи во время экзамена считается нарушение связи меньше одной минуты. Долговременным нарушением связи во время экзамена считается нарушение минута и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
Промежуточная аттестация
- Промежуточная аттестация (2 модуль)0.59 * Домашнее задание №2 + 0.41 * Письменный экзамен №2
Список литературы
Рекомендуемая основная литература
- Алгоритмы и структуры данных: Учебник / Белов В.В., Чистякова В.И. - М.:КУРС, НИЦ ИНФРА-М, 2016. - 240 с.: 60x90 1/16. - (Бакалавриат) (Переплёт 7БЦ) ISBN 978-5-906818-25-6 - Режим доступа: http://znanium.com/catalog/product/551224
Рекомендуемая дополнительная литература
- Skiena, S. S. (2008). The Algorithm Design Manual (Vol. 2nd ed). London: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=277139