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

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

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

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

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

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

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

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

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

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

Охват аудитории: для своего кампуса

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

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

Кредиты: 5

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

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

Аннотация

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

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

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

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

Авторы

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

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