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

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

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

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

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

Аннотация

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

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

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

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

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

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

  • Понятие и свойство алгоритма. Способы записи алгоритма. Различные формализации понятия алгоритма.
    Определение понятия «алгоритм». Основные свойства алгоритма. Способы записи алгоритмов, их «плюсы» и «минусы». Тезис Тьюринга-Чёрча. Нормальные алгоритма Маркова. Частично рекурсивные функции.
  • Сложность алгоритмов. Классы алгоритмов.
    Понятие сложности алгоритма. Базовые инструменты оценки сложности. Нотация большого «О». Классификация алгоритмов по сложности.
  • Поиск в ширину. Поиск в глубину. Рекурсия.
    Алгоритм Ли. Игра в пятнашки. Оценка вычислительной сложности рекурсивных алгоритмов.
  • Двоичные деревья.
    Двоичные деревья. Случайные деревья. Терминология и классификация деревьев. Сбалансированные деревья. Примеры использования деревьев. Поиск в заданном интервале в дереве.
  • Хеширование
    Хеширования с цепочками. Хеширования с открытой адресаций. Линейное хеширования, квадратичное, двойное. Консистеное хеширование.
  • Построение различных комбинаторных объектов
    Генерация множества всех подмножеств. Генерация сочетаний. Генерация перестановок. Генерация размещений. Задача о рюкзаке. Задача о сумме подмножества.
  • Жадные алгоритмы
    Принцип жадности. Оптимальность подзадач. Матройды – теоретическое основание жадных алгоритмов. Сжатие без потерь. Алгоритм Хафмана
  • Динамическое программирование
    Принцип Белмана. Задача о поиске кратчайшего пути в графе. Алгоритм Дейкстры. Псевдополиномиальное решение задачи о рюкзаке.
  • Динамическое программирование – разные задачи.
    Расстояние редактирования. Задача о расстановке скобок. Задача «Взлом сети». Оптимальный порядок перемножения матриц.
  • Алгоритмы на графах
    Представление графов в памяти компьютера. Матрица смежности, инцидентности, список рёбер. Поиск всех путей длинной k. Поиск кратчайшего пути. Поиск максимального пути.
  • Алгоритмы на графах – 2
    Поиск максимального независимого множества. Вычисление характеристик графа. Задача поиска минимального остова. Проверка графов на изоморфность
  • Геометрические задачи
    Построение выпуклой оболочки. Вращение геометрических фигур. Элементы компьютерной графики.
Элементы контроля

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

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

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

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

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

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

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

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

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