• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2020/2021

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

Статус: Курс обязательный (Программная инженерия)
Направление: 09.03.04. Программная инженерия
Когда читается: 2-й курс, 1-3 модуль
Формат изучения: без онлайн-курса
Язык: русский
Кредиты: 8

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

Аннотация

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

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

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

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

  • Применяет методы комбинаторики при подсчете комбинаторных объектов
  • Использует эффективные алгоритмы для построения оптимальных расписаний
  • Использует эффективные алгоритмы для нахождения оптимальных потоков
  • Использует приближенные и эвристические алгоритмы для труднорешаемых задач комбинаторной оптимизации
  • Использует основные структуры данных при разработке алгоритмов
Содержание учебной дисциплины

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

  • Раздел 1. Дополнительные главы комбинаторики
    Тема 1. Однородные рекуррентные соотношения и системы Решение однородных систем линейных рекуррентных соотношений с постоянными коэффициентами методом исключения неизвестных и матричным методом (через нахождение собственных значений и собственных векторов матрицы, составленной из коэффициентов). Тема 2. Неоднородные рекуррентные соотношения и системы Решение неоднородных систем линейных рекуррентных соотношений с постоянными коэффициентами методом исключения неизвестных и матричным методом (через нахождение собственных значений и собственных векторов матрицы, составленной из коэффициентов). Примеры задач, приводящих к рекуррентным соотношениям. Тема 3. Производящие функции Полиномиальные и экспоненциальные производящие функции. Нахождение производящих функций для конкретных последовательностей с использованием рядов Тейлора и известных разложений элементарных функций в ряд Маклорена. Решение линейных рекуррентных соотношений с постоянными коэффициентами через производящие функции. Тема 4. Методы доказательства оценок сложности рекурсивных алгоритмов Примеры рекурсивных алгоритмов. Получение рекуррентных соотношений при анализе сложности рекурсивных алгоритмов. Взаимная рекурсия. Решение линейных неоднородных рекуррентных соотношений с постоянными коэффициентами (методом неопределенных коэффициентов) и с переменными коэффициентами (через производящие функции). Тема 5. Симметрическая группа подстановок. Теорема Бернсайда. Свойства симметрической группы подстановок. Теорема Бернсайда. Подсчет числа неэквивалентных комбинаторных объектов с помощью теоремы Бернсайда. Тема 6. Цикловой индекс группы подстановок. Теория перечисления Пойя. Цикловой индекс подстановки и группы подстановок. Теория перечисления Пойа. Первая и вторая теоремы Пойа. Подсчет числа неэквивалентных комбинаторных объектов с помощью теорем Пойа.
  • Раздел 2. Эффективные алгоритмы теории расписаний
    Тема 7. Алгоритмы теории расписаний для независимых заданий Построение расписания минимальной стоимости для независимых заданий и одного исполнителя. Построение расписания минимальной длительности с прерываниями для независимых заданий. Ленточная стратегия. Диаграммы Ганта. Тема 8. Алгоритмы теории расписаний для зависимых единичных заданий. Построение расписания минимальной длительности без прерываний для заданий с графом зависимости в виде ориентированного корневого дерева. Построение расписания минимальной длительности без прерываний с двумя исполнителями для единичных заданий с произвольным орграфом зависимости. Уровневая стратегия. Тема 9. Алгоритмы теории расписаний для зависимых заданий произвольной длительности Построение расписания минимальной длительности с прерываниями для заданий произвольной длительности с произвольным орграфом зависимости. Уровневая стратегия с лексикографическим упорядочением. Тема 10. Алгоритмы теории расписаний для исполнителей с разной производительностью Построение расписания минимальной длительности с прерываниями для независимых заданий произвольной длительности и для исполнителей с разной производительностью. Тема 11. Конвейерная задача Построение расписания минимальной длительности для независимых двухэтапных заданий произвольной длительности и двух исполнителей (конвейерная задача). Алгоритм Джонсона.
  • Раздел 3. Эффективные алгортмы для решения потоковых задач
    Тема 12. Алгоритм поиска максимального паросочетания в двудольном графе Чередующиеся цепи. Метод «волны» для поиска чередующихся цепей. Теорема Бержа. Алгоритм поиска максимального паросочетания с помощью чередующихся цепей. Тема 13. Алгоритм поиска совершенного паросочетания в двудольном графе Чередующееся дерево. Метод «волны» для поиска чередующихся деревьев. Теорема Холла. Алгоритм поиска совершенного паросочетания с помощью чередующихся деревьев. Тема 14. Венгерский алгоритм для решения задачи о назначении Матрица затрат и её свойства. Диагональная редукция матрицы затрат. Венгерский алгоритм для решения задачи о назначении. Тема 15. Алгоритм поиска максимального потока в сети Поток в двухполюсной сети. Величина потока. Разрез сети. Пропускная способность разреза. Теорема Форда-Фалкерсона. Остаточная сеть. Алгоритм поиска максимального потока в двухполюсной сети с помощью остаточной сети. Тема 16. Алгоритм поиска максимального потока минимальной стоимости Стоимость потока в двухполюсной сети. Остаточная сеть. Алгоритм поиска максимального потока минимальной стоимости путем устранения циклов отрицательной стоимости в остаточной сети. Тема 17. Транспортная задача Транспортная задача, венгерский алгоритм. Сведение задач комбинаторной оптимизации к потоковым задачам. Решение задач о кратчайших путях в графе, о максимальном паросочетании и задачи о назначении с помощью потоковых алгоритмов.
  • Раздел 4. Труднорешаемые задачи, приближенные алгоритмы, эвристики
    Тема 18. Динамическое программирование Принцип Бэллмана и метод динамического программирования. Примеры и оценка сложности алгоритмов комбинаторной оптимизации, основанных на методе динамического программирования. Тема 19. Дискретная задача оптимального распределения инвестиций Полиномиальный алгоритм оптимального дискретного распределения инвестиций на основе метода динамического программирования. Комбинаторная оценка его сложности. Тема 20. Метод ветвей и границ Метод ветвей и границ. Алгоритмы для решения задачи о рюкзаке и задачи коммивояжера на основе метода ветвей и границ. Алгоритм Литтла. Тема 21. Приближенные алгоритмы и эвристики для решения задачи о рюкзаке Эвристики и приближенный алгоритм для задачи о рюкзаке с гарантированной погрешностью. Точный полиномиальный алгоритм для задачи о сверхвозрастающем рюкзаке. Тема 22. Точные и приближенные алгоритмы для решения задачи коммивояжера Эвристики для решения задачи коммивояжера. Приближенный алгоритм Кристофидиса для евклидовой задачи коммивояжера с гарантированной точностью. Тема 23. Генетические алгоритмы Общая схема и параметры генетического алгоритма. Операторы скрещивания, мутации и отбора. Решение задачи коммивояжера, задачи о рюкзаке и непрерывной задачи об оптимальном распределении инвестиций с помощью генетического алгоритма. Криптоанализ шифра с помощью генетического алгоритма.
  • Раздел 5. Элементарные структуры данных, деревья поиска
    Тема 24. Стек, очередь, связанные списки Элементарные структуры данных: стек, очередь, связанные списки. Алгоритмы, основанные на двоичной куче (сортировка кучей, очередь с приоритетами). Тема 25. Сбалансированные деревья поиска Обзор сбалансированных деревьев, АВЛ-дерево, Splay-дерево. Двоичный поиск в отсортированном массиве, двоичное дерево поиска.
Элементы контроля

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

  • неблокирующий Самостоятельная работа 1
  • неблокирующий Самостоятельная работа 2
  • неблокирующий Контрольная работа 1
  • неблокирующий Контрольная работа 2
  • неблокирующий Экзамен
    Экзамен проводится в письменной форме очно, в виде контрольной работы из 5 заданий. Время на выполнение работы - 1 час 20 минут. Студенты, у которых накопленная оценка равна 7 баллов или выше, и оценки за контрольную точку и работу на семинарах не ниже 6 баллов, могут получить итоговую оценку по накопленной (в случае согласия с ней). Накопленная оценка вычисляется как среднее арифметическое оценок за контрольную точку и работу на семинарах.
  • неблокирующий Самостоятельная работа 1
  • неблокирующий Самостоятельная работа 2
  • неблокирующий Контрольная работа 1
  • неблокирующий Контрольная работа 2
  • неблокирующий Экзамен
    Экзамен проводится в письменной форме очно, в виде контрольной работы из 5 заданий. Время на выполнение работы - 1 час 20 минут. Студенты, у которых накопленная оценка равна 7 баллов или выше, и оценки за контрольную точку и работу на семинарах не ниже 6 баллов, могут получить итоговую оценку по накопленной (в случае согласия с ней). Накопленная оценка вычисляется как среднее арифметическое оценок за контрольную точку и работу на семинарах.
Промежуточная аттестация

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

  • Промежуточная аттестация (1 модуль)
    0.6 * Контрольная работа 1 + 0.1 * Самостоятельная работа 1 + 0.3 * Самостоятельная работа 2
  • Промежуточная аттестация (3 модуль)
    0.6 * Контрольная работа 1 + 0.1 * Самостоятельная работа 1 + 0.3 * Самостоятельная работа 2
Список литературы

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

Рекомендуемая основная литература

  • Структуры и алгоритмы обработки данных: Учебное пособие / Колдаев В.Д. - М.:ИЦ РИОР, НИЦ ИНФРА-М, 2014. - 296 с.: 60x90 1/16. - (Высшее образование: Бакалавриат) (Переплёт 7БЦ) ISBN 978-5-369-01264-2 - Режим доступа: http://znanium.com/catalog/product/418290

Рекомендуемая дополнительная литература

  • Алгоритмы и структуры данных: Учебник / Белов В.В., Чистякова В.И. - М.:КУРС, НИЦ ИНФРА-М, 2016. - 240 с.: 60x90 1/16. - (Бакалавриат) (Переплёт 7БЦ) ISBN 978-5-906818-25-6 - Режим доступа: http://znanium.com/catalog/product/551224