Введение в алгоритмы

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

В результате изучения дисциплины слушатели должны познакомиться с базовыми структурами данных и алгоритмами в объектно-ориентированном подходе к программированию.

В результате изучения дисциплины слушатели должны

• иметь понятие об абстрактных типах данных и способах структуризации данных;
• изучить некоторые классические алгоритмы обработки данных и уметь проводить их оценки;
• научиться выбирать алгоритмы и структуру данных в зависимости от задачи и условий для ее решения;
• овладеть приемами обработки структур данных при объектно-ориентированном подходе к проектированию и программированию.

Содержание разделов дисциплины

1. Простые и сложные структуры данных. Способы структуризации данных. Массивы, записи и списки. Динамические структуры данных. Представление динамических массивов, дескриптор массива. Объектно-ориентированный подход к организации структур данных. Итерация элементов в сложных структурах данных. Виды итераторов.
2. Алгоритмы сжатия и шифрования текстов. Алфавитное кодирование. Префиксные коды. Алгоритм Хаффмена. Шифрование с открытым ключом: алгоритм RSA.
3. Поиск по строке.Поиск подстроки. Наивный подход. Алгоритм Рабина-Карпа. Алгоритм Кнута-Морриса-Пратта.
4. Поиск и сортировки. Индексация данных и поиск по ключу. Двоичный поиск. Методы оценки алгоритмов сортировки. Сортировки вставками. Сортировка Шелла. Сортировка слиянием. Пирамидальная сортировка. Быстрая сортировка. Цифровая сортировка. Поиск медианы.
5. Абстрактные типы данных. Понятие абстрактного типа данных и его реализации, примеры. Типы и структуры данных – общее и различия в этих понятиях.
6. Стеки и очереди. Абстрактный стек и способы его реализации. Простейшие алгоритмы анализа текста с использованием стека. Простая очередь и способы ее реализации. Очередь с приоритетами и ее реализация в виде пирамиды (кучи).
7. Деревья поиска. Способы представления деревьев. Алгоритмы вставки и удаления элементов. АВЛ-деревья, 2-3-деревья, В-деревья.
8. Словари и хеширование. Понятие словарей и отображений. Принципы хеширования. Хеш-функции и хеш-таблицы, способы разрешения конфликтов.
9. Алгоритмы на графах. Понятие графа. Виды графов. Представление графов. Пути в графах и обходы графов. Посещение вершин и дуг. Топологическая сортировка графа. Поиски минимальных путей. Алгоритм Дейкстры. Транзитивное замыкание графа. Алгоритм умножения матриц и алгоритм Флойда. Нахождение всех минимальных путей. Поиск минимального остова: алгоритм Крускала и алгоритм Прима.
10. Процедурное представление знания. Способы представления знаний в процедурах. Задача о расстановке ферзей на шахматной доске

Дополнительные главы

1. Алгоритм Штрассена быстрого умножения матриц.
2. Дискретное преобразование Фурье – быстрый алгоритм.
3. Алгоритм Брезенхема построения прямых и окружностей.
4. Задача коммивояжера.

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

• Основная литература
• Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — М.: Издательский дом «Вильямс», 2000.
• Вирт Н. Алгоритмы и структуры данных — СПб.: Невский Диалект, 2001.
• Кормен. Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2000.
• Новиков Ф.А. Дискретная математика для программистов. — СПб.: Питер, 2004; 2-е изд.: Питер, 2005.
• Дополнительная литература
• Кубенский А.А. Создание и обработка структур данных в примерах на Java. — СПб.: БХВ-Петербург, 2001.