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

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

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

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

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

Аннотация

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

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

  • знать основные структуры данных (список, дерево, хеш-таблицы, графы), базовые алгоритмы (поиск в глубину, поиск в ширину, принцип разделяй и властвуй, динамическое программирование, поиск с отсечением, генерирование комбинаторных объектов).
  • развить алгоритмическое мышление
  • овладеть навыками программирования на языке C++ в процессе реализации основных вычислительных алгоритмов и структур данных
Планируемые результаты обучения

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

  • Владеет методом "поиск в глубину"
  • Владеет методом "поиск в ширину"
  • Знает различные формализации понятия алгоритма.
  • Понимает и умеет реализовывать "двоичное дерево"
  • Понимает и умеет реализовывать различные методы хэширования
  • Понимает когда можно использовать "жадные" алгоритмы.
  • Решает задачи методом динамического программирования
  • Умеет использовать метод динамического программирования
  • Умеет использовать нотацию большого О
  • Умеет оценивать вычислительную сложность алгоритмов
  • Умеет реализовывать алгоритмы поиска минимального остова, определения изоморфноти графов
  • Умеет реализовывать алгоритмы построения выпуклой оболочки и вращения геометрических фигур
  • Умеет реализовывать базовые алгоритмы на графах
  • Умеет реализовывать различные комбинаторные объекты
  • Умеет реализовывать рекурсивные алгоритмы
Содержание учебной дисциплины

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

  • Понятие и свойство алгоритма. Способы записи алгоритма. Различные формализации понятия алгоритма.
  • Сложность алгоритмов. Классы алгоритмов.
  • Поиск в ширину. Поиск в глубину. Рекурсия.
  • Двоичные деревья.
  • Хеширование
  • Построение различных комбинаторных объектов
  • Жадные алгоритмы
  • Динамическое программирование
  • Динамическое программирование – разные задачи.
  • Алгоритмы на графах
  • Алгоритмы на графах – 2
  • Геометрические задачи
Элементы контроля

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

  • неблокирующий Лабораторная работа "Ход-конём"
  • неблокирующий Лабораторная работа "Хамелеон"
    Поиск в ширину
  • неблокирующий Лабораторная работа "Задача о сумме"
  • неблокирующий Лабораторная работа "Сортировка подсчётом"
  • неблокирующий Лабораторная работа "Хэширование цепочками"
  • неблокирующий Лабораторная работа "Хэширование с открытой адресацией (двойное хэширование!)"
  • неблокирующий Лабораторная работа "Поиск по интервалу в двоичном дереве"
  • неблокирующий Лабораторная работа "Лабиринт с бомбами"
    Поиск в ширину/Динамическое программирование
  • неблокирующий Лабораторная работа "Оптимальный порядок перемножения матриц"
    Динамическое программирование
  • неблокирующий Лабораторная работа "Жук-инвалид"
  • неблокирующий Лабораторная работа "Острова"
  • неблокирующий Лабораторная работа "Количество правильных скобочных последовательностей"
  • неблокирующий Лабораторная работа "Найти минимальный остов"
  • неблокирующий Лабораторная работа "Взлом сети"
    Динамическое программирование
  • неблокирующий Лабораторная работа "Быстрая сортировка"
    Разделяй и властвуй
  • неблокирующий Лабораторная работа "Жадны до денег"
    Динамическое программирование
  • неблокирующий Лабораторная работа "Ход-конём"
  • неблокирующий Лабораторная работа "Хамелеон"
    Поиск в ширину
  • неблокирующий Лабораторная работа "Задача о сумме"
  • неблокирующий Лабораторная работа "Сортировка подсчётом"
  • неблокирующий Лабораторная работа "Хэширование цепочками"
  • неблокирующий Лабораторная работа "Хэширование с открытой адресацией (двойное хэширование!)"
  • неблокирующий Лабораторная работа "Поиск по интервалу в двоичном дереве"
  • неблокирующий Лабораторная работа "Лабиринт с бомбами"
    Поиск в ширину/Динамическое программирование
  • неблокирующий Лабораторная работа "Оптимальный порядок перемножения матриц"
    Динамическое программирование
  • неблокирующий Лабораторная работа "Жук-инвалид"
  • неблокирующий Лабораторная работа "Острова"
  • неблокирующий Лабораторная работа "Количество правильных скобочных последовательностей"
  • неблокирующий Лабораторная работа "Найти минимальный остов"
  • неблокирующий Лабораторная работа "Взлом сети"
    Динамическое программирование
  • неблокирующий Лабораторная работа "Быстрая сортировка"
    Разделяй и властвуй
  • неблокирующий Лабораторная работа "Жадны до денег"
    Динамическое программирование
Промежуточная аттестация

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

  • 2021/2022 учебный год 2 модуль
    0.06 * Лабораторная работа "Взлом сети" + 0.06 * Лабораторная работа "Жадны до денег" + 0.06 * Лабораторная работа "Найти минимальный остов" + 0.06 * Лабораторная работа "Поиск по интервалу в двоичном дереве" + 0.08 * Лабораторная работа "Ход-конём" + 0.06 * Лабораторная работа "Острова" + 0.06 * Лабораторная работа "Сортировка подсчётом" + 0.06 * Лабораторная работа "Задача о сумме" + 0.06 * Лабораторная работа "Оптимальный порядок перемножения матриц" + 0.06 * Лабораторная работа "Хэширование цепочками" + 0.06 * Лабораторная работа "Быстрая сортировка" + 0.06 * Лабораторная работа "Количество правильных скобочных последовательностей" + 0.08 * Лабораторная работа "Хамелеон" + 0.06 * Лабораторная работа "Хэширование с открытой адресацией (двойное хэширование!)" + 0.06 * Лабораторная работа "Лабиринт с бомбами" + 0.06 * Лабораторная работа "Жук-инвалид"
Список литературы

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

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

  • Алгоритмы : построение и анализ, 2-е изд., 1290 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2012
  • Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018

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

  • Апанасевич С.А. - Структуры и алгоритмы обработки данных. Линейные структуры: учебное пособие - Издательство "Лань" - 2019 - ISBN: 978-5-8114-3366-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/113934

Авторы

  • Пономаренко Александр Александрович
  • Калягин Валерий Александрович