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

Бакалавриат 2020/2021

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Курс обязательный (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Кафедра прикладной математики и информатики (Нижний Новгород)

Где читается: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

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

Формат изучения: без онлайн-курса

Преподаватели: Пономаренко Александр Александрович

Язык: русский

Кредиты: 5

Контактные часы: 56

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

Аннотация

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

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

знать основные структуры данных (список, дерево, хеш-таблицы, графы), базовые алгоритмы (поиск в глубину, поиск в ширину, принцип разделяй и властвуй, динамическое программирование, поиск с отсечением, генерирование комбинаторных объектов).
развить алгоритмическое мышление
овладеть навыками программирования на языке 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 * Лабораторная работа "Хэширование цепочками"

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