Кафедра К3
Прикладная математика, информатика
и вычислительная техника
Алгоритмы и структуры данных
Направление подготовки: 654600 «Информатика и вычислительная техника»
Специальность: 230101 (220100) «Вычислительные машины, комплексы, системы и сети»
Семестр: 2
Вид итогового контроля: зачет
Содержание курса:
- Концепция структур данных
- Концепция типа данных
- Простейшие структуры данных
- Простые переменные
- Индексные переменные
- Последовательные структуры
- Алгоритмы внутреннего поиска
- Задача поиска
- Внутренний и внешний поиск
- Алгоритмы линейного, или последовательного поиска
- Эффективность линейного поиска
- Методы транспозиции и перемещения в начало.
- Бинарный поиск
- Поиск в таблице
- Индексно-последовательный поиск.
- Методы поиска строки
- Прямой поиск
- Алгоритм Боуера и Мура
- Методы сортировки
- Задача сортировки
- Методы внутренней сортировки
- Обменные сортировки: пузырьковая и «шейкерная»
- Сортировка вставками
- Сортировка бинарными вставками
- Сортировка с помощью прямого выбора
- Улучшенные методы сортировки
- Сортировка Шелла.
- Авторский алгоритм
- Алгоритм с заданным числом шагов.
- Обменная сортировка с разделением (сортировка Хоара).
- Алгоритм сортировки.
- Рекурсивные алгоритмы
- Понятие рекурсии
- Рекурсивные структуры
- Функция вычисления факториала
- Числа Фибоначчи
- Рекурсивный алгоритм быстрой сортировки.
- Динамические структуры данных
- Линейные связанные списки
- Однонаправленные и двунаправленные списки
- Реализация линейных списков
- Операции для работы с линейными списками
- Примеры
- Циклические списки
- Реализация циклических списков
- Операции для работы с циклическими списками. Примеры.
- Очереди. Методы реализации очередей
- Реализация очередей массивом
- Реализация очередей списком
- Операции для работы с очередями. Примеры
- Стек
- Методы реализации стека
- Операции записи в стек и извлечения из стека. Примеры
- Бинарные деревья
- Корень дерева
- Уровни бинарного дерева
- Понятие листа дерева
- Глубина бинарного дерева
- Реализация бинарных деревьев
- Идеально сбалансированные деревья
- Построение идеально сбалансированного бинарного дерева
- Использование бинарных деревьев в задаче поиска
- Построение дерева поиска
- Методы прохождения бинарных деревьев
- Прохождение дерева сверху вниз
- Прохождение дерева слева направо
- Прохождение дерева снизу вверх
- Операции включения и исключения из бинарного дерева
Рекомендуемая литература:
- Вирт Н. Алгоритмы и структуры данных. С примерами на Паскале; Пер. с англ. СПб Невский диалект, 2005 г. 351 с.
- Павловская Т. А., «Паскаль. Программирование на языке высокого уровня»: Учеб. Для вузов. — СПб: Питер, 2007 — 393 с.
- Павловская Т. А., «Паскаль. Программирование на языке высокого уровня». Практикум — СПб.: Питер, 2006 — 317 с.
Дополнительная литература:
- Лэнгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ: Пер. с англ. — М.: Мир, 1989. — 568 с.
Учебные материалы:
