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

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

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

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

Аннотация

Изучение данной дисциплины базируется на дисциплинах: • Программирование. • Дискретная математика. Основные положения дисциплины будут использованы в дальнейшем при изучении дисциплин: • Распределенные вычисления. • Современные языки и технологии программирования. • Функциональное и логическое программирование. • Web-программирование. • Семантические информационные системы. • Командный проект по программной инженерии. Настоящая дисциплина относится к базовой части Б.Пр Профессионального цикла (Major). Формат изучения дисциплины: без использования онлайн курса.
Цель освоения дисциплины

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

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

Результаты освоения дисциплины

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

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

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

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

  • Самостоятельная работа 1 (неблокирующий)
  • Самостоятельная работа 2 (неблокирующий)
  • Контрольная работа 1 (неблокирующий)
  • Контрольная работа 2 (неблокирующий)
  • Экзамен (неблокирующий)
Промежуточная аттестация

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

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

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

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

  • Структуры и алгоритмы обработки данных: Учебное пособие / Колдаев В.Д. - М.:ИЦ РИОР, НИЦ ИНФРА-М, 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
  • Математическая логика : учеб. пособие для вузов, Игошин В. И., ISBN: 978-5-16-011691-4, 2016