Algorithms and Data Structures

2020/2021

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Department of Informatics

Course type:

Compulsory course

When:

2 year, 1, 2 module

Instructors

Bliznets, Ivan

Копелиович Сергей Владимирович

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

Аннотация

Данная дисциплина опирается на дисциплины из школьного курса и направлена на овладение навыками использования основных применяемых в программировании структур данных, алгоритмов обработки данных и анализа этих алгоритмов, взаимосвязи алгоритмов и структур данных. В результате изучения этой дисциплины студенты будут иметь практические навыки конструирования конкретных алгоритмов и структур данных для решения разнообразных математических и программистских задач. В результате изучения дисциплины обучающийся должен: знать: - методы оценки сложности алгоритмов в среднем и в худшем случаях; - элементарные структуры данных; - постановки основных задач; - основные классы алгоритмов: «разделяй и властвуй», «жадные алгоритмы», алгоритмы на динамическое программирование; - специализированные структуры данных, используемые в различных алгоритмах. уметь: - оценивать сложность алгоритмов в среднем и в худшем случаях; - выделять из практических задач их алгоритмическую составляющую; - реализовывать изученные алгоритмы и структуры данных на процедурных языках программирования; - выбирать оптимальные алгоритмы и структуры данных, в зависимости от конкретных ограничений на решение задачи; - применять приближённые алгоритмы в тех случаях, когда эффективное точное решение невозможно. владеть: - методами оценки сложности алгоритмов сложность алгоритмов в среднем и в худшем случаях; - навыками реализации алгоритмов и структур данных на процедурных языках программирования.

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

• Целью освоения дисциплины «Алгоритмы и структуры данных» является формирование у студентов теоретических знаний и практических навыков в области теории алгоритмов, современных структур данных и их реализации на языке программирования 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