Кто читает:: Кафедра информационных технологий в бизнесе (Пермь) (Факультет социально-экономических и компьютерных наук)

Статус:: Курс обязательный

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

Преподаватели

Городилов Алексей Юрьевич

Морозенко Владимир Викторович

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

Аннотация

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

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

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

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

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

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

Раздел 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
Экзамен
Экзамен проводится с использованием асинхронного прокторинга. Требования к ПК пользователя: 1. Стационарный компьютер или ноутбук (мобильные устройства не поддерживаются); 2. Операционная система Windows (версии 7, 8, 8.1, 10) или Mac OS X Yosemite 10.10 и выше; 3. Интернет-браузер Google Chrome последней на момент сдачи экзамена версии: (для установки браузера используйте ссылку https://www.google.com/chrome/, для проверки и обновления версии браузера используйте ссылку chrome://help/, при переходе можно увидеть номер версии своего браузера и кнопку для обновления, если они доступны); 4. Наличие постоянного интернет-соединения со скоростью передачи данных от пользователя не ниже 5 Мбит/сек.; 5. Разрешена передача данных по сетевым портам: 80 TCP, 443 TCP, 3478 TCP/UDP (уточнить этот вопрос у провайдера/открыть панель управления - система и безопасность - брандмауэр защитника Windows- дополнительные параметры. Убедитесь, что нет ограничений на входящее и исходящее соединение); 6. Наличие исправной и включенной веб-камеры (включая встроенные в ноутбуки); 7. Наличие исправного и включенного микрофона (включая встроенные в ноутбуки). https://elearning.hse.ru/data/2020/04/23/1559799268/Инструкция%20по%20работе%20в%20системе%20прокторинга%20Экзамус%202020.%20Асинхрон.pdf

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

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

Бакалаврская программа «Программная инженерия»

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

Преподаватели

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

Аннотация

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

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

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

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

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

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

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

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