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

Цели и задачи дисциплины

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

Краткое содержание дисциплины

Временная и пространственная сложность алгоритмов. Примеры анализа сложности алгоритмов. Фундаментальные структуры данных. Типы данных. Стандартные типы данных. Структурированные типы данных (массивы, записи, множества). Многомерные массивы. Файлы и последовательности. Алгоритмы обработки массива: поиск в массиве, максимальный элемент в массиве, реверс массива, циклический сдвиг. Отбор нужных элементов в массиве. Алгоритмы сортировки и поиска. Задача сортировки. Внутренняя и внешняя сортировка. Метод пузырька, выбора, вставки. Быстрая сортировка, сортировка кучей, сортировка слиянием, пирамидальная сортировка. Бинарный поиск для подбора порогов в моделях. Понятие динамического программирования. Динамическое программирование вместо рекурсии. Динамическое программирование вместо перебора. Жадные алгоритмы. Применение динамического программирования в алгоритме выравнивания последовательностей в выборках. Методы динамического программирования: метод частичных сумм, составные цепочки в символьной строке. Массив, замкнутый в кольцо. Метод скользящего окна. Метод двух указателей. Понятие графа. Примеры графов. Способы представления графов. Алгоритмы на графах: жадные алгоритмы, поиск путей на графах. Алгоритмы для рекомендательных систем. Алгоритмы на строках. Поиск подстрок. Прямой поиск подстроки в строке. Алгоритм Кнутта-Морриса-Пратта. Алгоритм Бойера-Мура. Списки. Связный список. Добавление в конец списка. Удаление элемента из списка. Двусвязные списки. Циклические списки. Кольцевые двусвязные списки. Понятие стека. Стеки на базе массивов. Стек на основе списка. Добавление и удаление элемента. Понятие очереди. Реализация очереди. Деки (двусторонние очереди). Приоритетные очереди. Применение очередей в графовых моделях. Понятие дерева. Вес дерева. Описание дерева. Дерево поиска. Бинарное дерево поиска. Поиск по дереву с включением. Алгоритмы обхода дерева. Удаление элемента. Оптимальное и сбалансированное по высоте дерево. Алгоритмы добавления и удаления вершины в дереве. Красно-черные деревья. KD деревья для хранения и поиска в многомерных пространствах. Хэш-таблицы. Выбор хэш-функции. Разрешение коллизий. Поиск и добавление элементов в хэш-таблицу. Техника хэширования признаков для машинного обучения.

Компетенции обучающегося, формируемые в результате освоения дисциплины

Выпускник должен обладать: