Кафедра К3 Прикладная математика, информатика
и вычислительная техника

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

Направление подготовки: 654600 «Информатика и вычислительная техника»
Специальность: 230101 (220100) «Вычислительные машины, комплексы, системы и сети»
Семестр: 2
Вид итогового контроля: зачет

Содержание курса:

  1. Концепция структур данных

    • Концепция типа данных
    • Простейшие структуры данных
    • Простые переменные
    • Индексные переменные
    • Последовательные структуры
  2. Алгоритмы внутреннего поиска

    • Задача поиска
    • Внутренний и внешний поиск
    • Алгоритмы линейного, или последовательного поиска
    • Эффективность линейного поиска
    • Методы транспозиции и перемещения в начало.
    • Бинарный поиск
    • Поиск в таблице
    • Индексно-последовательный поиск.
    • Методы поиска строки
    • Прямой поиск
    • Алгоритм Боуера и Мура
  3. Методы сортировки

    • Задача сортировки
    • Методы внутренней сортировки
    • Обменные сортировки: пузырьковая и «шейкерная»
    • Сортировка вставками
    • Сортировка бинарными вставками
    • Сортировка с помощью прямого выбора
    • Улучшенные методы сортировки
    • Сортировка Шелла.
    • Авторский алгоритм
    • Алгоритм с заданным числом шагов.
    • Обменная сортировка с разделением (сортировка Хоара).
    • Алгоритм сортировки.
  4. Рекурсивные алгоритмы

    • Понятие рекурсии
    • Рекурсивные структуры
    • Функция вычисления факториала
    • Числа Фибоначчи
    • Рекурсивный алгоритм быстрой сортировки.
  5. Динамические структуры данных

    • Линейные связанные списки
    • Однонаправленные и двунаправленные списки
    • Реализация линейных списков
    • Операции для работы с линейными списками
    • Примеры
    • Циклические списки
    • Реализация циклических списков
    • Операции для работы с циклическими списками. Примеры.
    • Очереди. Методы реализации очередей
    • Реализация очередей массивом
    • Реализация очередей списком
    • Операции для работы с очередями. Примеры
    • Стек
    • Методы реализации стека
    • Операции записи в стек и извлечения из стека. Примеры
    • Бинарные деревья
    • Корень дерева
    • Уровни бинарного дерева
    • Понятие листа дерева
    • Глубина бинарного дерева
    • Реализация бинарных деревьев
    • Идеально сбалансированные деревья
    • Построение идеально сбалансированного бинарного дерева
    • Использование бинарных деревьев в задаче поиска
    • Построение дерева поиска
    • Методы прохождения бинарных деревьев
    • Прохождение дерева сверху вниз
    • Прохождение дерева слева направо
    • Прохождение дерева снизу вверх
    • Операции включения и исключения из бинарного дерева

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

  1. Вирт Н. Алгоритмы и структуры данных. С примерами на Паскале; Пер. с англ. СПб Невский диалект, 2005 г. 351 с.
  2. Павловская Т. А., «Паскаль. Программирование на языке высокого уровня»: Учеб. Для вузов. — СПб: Питер, 2007 — 393 с.
  3. Павловская Т. А., «Паскаль. Программирование на языке высокого уровня». Практикум — СПб.: Питер, 2006 — 317 с.

Дополнительная литература:

  1. Лэнгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ: Пер. с англ. — М.: Мир, 1989. — 568 с.

Учебные материалы:

Вопросы к зачёту