• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Книга
Integral Robot Technologies and Speech Behavior

Kharlamov A. A., Pantiukhin D., Borisov V. et al.

Newcastle upon Tyne: Cambridge Scholars Publishing, 2024.

Статья
On Trees with a Given Diameter and the Extremal Number of Distance-k Independent Sets

D. S. Taletskii.

Journal of Applied and Industrial Mathematics. 2023. Vol. 17. No. 3. P. 664-677.

Глава в книге
Graph density and uncertainty of graphical model selection algorithms
В печати

Kalyagin Valeriy, Kostylev Ilya.

In bk.: Advances in Optimization and Applications. 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers Communications in Computer and Information Science. Vol. 1913. Springer, 2024.

Препринт
Independent sets versus 4-dominating sets in outerplanar graphs

Taletskii D.

math. arXiv. Cornell University, 2023

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

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