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

Осенний семестр

Вопросы к экзамену

Материалы к лекциям

• Лекция 2
  • Сортировка слиянием
  • Быстрая сортировка
• Лекция 3
  • Сортировка подсчетом и цифровая
  • Куча, сортировка кучей.
• Лекция 4
  • Очередь с приоритетом
• Лекция 5
  • Хеши
• Лекция 6
  • Двоичное дерево поиска
  • Самобалансирующиеся деревья поиска

Лабораторные работы

• Как сдавать задачи
• Cроки посыла задач лабораторных работ в систему ограничены 2-3 неделями в зависимости от сложности заданий.

План курса

• Лекция 1. Асимптотические обозначения. Cортировка вставкой
  Асимптотические обозначения (O, Ω,Θ). Теорема о связи O, Ω и Θ. Свойства O с доказательствами (правило сумм, правило произведений и умножения и добавления константы). Сортировка вставкой (Inserion Sort). Оценка времени работы сортировки вставкой. Доказательство корректности сортировки вставками (с помощью инварианта цикла).
• Лекция 2. Сортировки методом декомпозиции.
  Сортировка слиянием (Merge Sort). Доказательство корректности операции Merge с помощью инварианта цикла. Точная оценка времени работы сортировки слиянием. Быстрая сортировка (Quick Sort). Оценка времени работы быстрой сортировки в лучшем и худшем случае. Рандомизированный вариант алгоритма быстрой сортировки и его преимущества.
• Лекция 3. Линейные сортировки. Пирамидальная сортировка.
  Сортировка подсчетом (Counting Sort) + оценка времени работы. Устойчивость алгоритмов на примере сортировки подсчетом. Поразрядная сортировка (Radix Sort) + оценка времени работы. Двоичное дерево: терминология (определение, родитель, потомок, предок, глубина, высота и полное дерево). Определение двоичной кучи и реализация на массиве. Восстановление свойства невозрастания кучи (Heapify) + оценка времени работы. Алгоритм создания кучи (Build_Max_Heap) + грубая оценки времени работы. Точная оценка времени работы Build_Max_Heap (стр. 186-187). Сортировка кучей (Heap Sort) + оценка времени работы.
• Лекция 4. Элементарные структуры данных: стек, очередь, списки. Очередь с приоритетами. Бинарный поиск.
  Стеки, очереди, списки (односвязные, двусвязные, циклические) и операции с ними. Очередь с приоритетами на основе кучи. Операции в очереди с приоритетами. Бинарный поиск (Binary Search) + оценка времени работы.
• Лекция 5. Хеш-таблицы.
  Таблицы с прямой адресацией. Хеш-таблицы. Разрешение коллизий с помощью цепочек. Хеш-таблицы с закрытой адресацией: метод деления и метод умножения. Хеш-таблицы с открытой адресацией: вставка, поиск и удаление. Линейное исследование, квадратичное исследование, двойное хеширование. Сравнительный анализ качества хеширования в этих подходах на основе числа исследуемых последовательностей.
• Лекция 6. Бинарные деревья поиска.
  Двоичное дерево поиска. Центрированный, прямой и обратный обходы двоичного дерева поиска. Оценка времени работы центрированного обхода двоичного дерева поиска. Операции, выполняемые с бинарными деревьями поиска (с пояснением корректности и оценкой времени работы): поиск элемента по ключу, поиск минимума и максимума, поиск предшествующего и последующего элементов, вставка элемента в дерево, удаление элемента из дерева. Сбалансированные деревья поиска.

  Литература

  • Кормен, Лейзерсон и др. "Алгоритмы. Построение и анализ"
  • Ахо, Хопкрофт, Ульман "Структуры данных и алгоритмы"