• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

2017/2018
Учебный год
RUS
Обучение ведется на русском языке
8
Кредиты

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

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

Аннотация

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

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

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

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

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

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

  • 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
  • неблокирующий Экзамен
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.15 * Контрольная работа 1 + 0.15 * Контрольная работа 2 + 0.05 * Самостоятельная работа 1 + 0.05 * Самостоятельная работа 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