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

  Краткое содержание прочитанных лекций
16.02.2006
  • Уровни абстракции данных. Представление данных высокого уровня с использованием абстракций более низкого уровня.
  • Представление целых чисел в линейной памяти. Использование различных систем счисления для представления беззнаковых целых (двоичная; троичная с цифрами 1, 0, -1; десятичная).
  • Представление отрицательных целых чисел в прямом и дополнительном коде.
  • Представление вещественных чисел в виде порядка и мантиссы. Проблема потери точности при вычислениях.
  • Структуры (записи), выравнивание полей по заданной границе, переупорядочение полей структур. Внешняя и внутренняя фрагментация памяти, порожденная выравниванием данных.
  • Массивы со статическими и динамическими границами. Дескрипторы одномерных, двумерных и многомерных массивов.
  • Сложные значения, образованные с помощью указателей. Голова (постоянного объема памяти) и хвост (хвосты) значений.
02.03.2006
  • Кодирование текстов. Алфавитное кодирование. Разделимые коды. Префиксные коды.
  • Коды с переменной длиной. Цена кодирования. Оптимальные коды.
  • Алгоритм Фано генерации кода с переменной длиной, близкого к оптимальному.
  • Алгоритм Хаффмена генерации оптимального кода.
  • Сжатие данных. Алгоритм Лемпеля - Зива.
  • Шифрование с открытым ключом. Корректность алгоритма шифрования RSA. Цифровая подпись.
09.03.2006
  • Алгоритмы поиска подстроки в строке. Оценка скорости. "Наивный алгоритм".
  • Алгоритм Рабина - Карпа
  • Алгоритм Кнута - Морриса - Пратта
  • Алгоритм Бойера - Мура
  • Задача индексации данных. Поиск по ключу. Сортировка массива как способ построения индекса.
  • Алгоритм двоичного поиска в упорядоченном массиве.
  • Методы оценки алгоритмов сортировок: число сравнений, число перемещений, устойчивость. Сортировка "пузырьком".
  • Сортировки простыми и двоичными вставками, их применимость и оценки.
  • Сортировка Шелла
16.03.2006
  • Алгоритм слияния упорядоченных массивов. Сортировка фон Неймана (слиянием).
  • Алгоритм пирамидальной сортировки.
  • Алгоритм "быстрой" сортировки.
  • Поиск k-го наименьшего (наибольшего) элемента в массиве (поиск альфа-медианы)
  • Сортировка подсчетом.
  • Цифровая сортировка.
23.03.2006
  • Понятие об абстрактном типе данных. Примеры: абстрактная дата, список.
  • Сигнатура и семантика операций - две стороны описания абстрактного типа данных.
  • Интерфейсы Java как способ представления абстрактных типов данных. Реализации интерфейсов.
  • Две реализации абстрактных списков: связанный список и массив.
  • Итерация сложных объектов. Абстрактный итератор и его методы.
  • Внутренняя итерация. Абстрактный посетитель.
  • Реализация внешней и внутренней итерации для связанного списка.
30.03.2006
  • Абстрактные стек и очередь
  • Различные подходы к реализации стека и очередей; использование других абстракций для их реализации.
  • Реализация пары стеков в одном массиве.
  • Очередь с приоритетами и ее реализация в виде пирамиды.
  • Кольцевой список как основа для реализации очереди.
  • Применение стека для анализа скобочной структуры выражения.
  • Перевод выражения в обратную польскую запись. Алгоритм перевода, использующий стек операций.
6.04.2006
  • Двоичное дерево. Рекурсивные алгоритмы для анализа двоичного дерева.
  • Внутренняя итерация двоичного дерева с помощью рекурсивной процедуры.
  • Внешняя итерация узлов двоичного дерева, использующая стек для хранения пути от корня.
  • Внешний итератор для обхода дерева "в ширину", использующий простую очередь.
  • Поиск по ключу. Использование деревьев для поиска. Индексация данных.
  • Алгоритмы поиска и добавления данных в лист и в корень дерева.
  • Сбалансированные по высоте (АВЛ) деревья. Алгоритм "поворота".
  • Добавление нового ключа в сбалансированное по высоте дерево и балансировка получившегося дерева.
  • Красно-черные деревья. Алгоритм добавления нового ключа в красно-черное дерево.
13.04.2006
  • Хранение информации о размере в двоичных деревьях поиска. Решение задач об индексации узлов в дереве.
  • 2-3-деревья: алгоримты вставки и удаления ключей.
  • В-деревья: область применимости и алгоритмы вставки и удаления ключей.
  • Модификация В-дерева - В+-дерево.
  • Ассоциативный поиск и ассоциативные списки.
  • Хеширование данных и принципы организации хеш-таблиц.
  • Реализация простого словаря, основанного на хешировании, с хранением информации в связанных списках.
20.04.2006
  • Способы представления графов: матрица смежности, матрица инцидентности, списки смежности, список ребер.
  • Обход графа в глубину, начиная с заданной вершины: рекурсивная процедура.
  • Топологическая сортировка вершин ориентированного графа без циклов.
  • Обходы графов, начиная с заданной вершины, с помощью вспомогательного "контейнера" вершин.
  • Обход графа "в ширину" с помощью очереди.
27.04.2006
  • Поиск кратчайших путей в ненагруженном графе из заданной вершины с помощью обхода "в ширину".
  • Алгоритм релаксации ребра при поиске оптимальных характеристик вершины.
  • Алгоритм Дейкстры поиска кратчайших путей из заданной вершины в нагруженном графе с неотрицательными нагрузками на ребра.
  • Кратчайшие пути в ориентированном нагруженном графе: алгоритм Беллмана - Форда.
  • Кратчайшие пути в ориентированном графе без циклов.
  • Транзитивное замыкание графа отношения: алгоритм Флойда - Уоршалла.
  • Применение алгоритма Флойда - Уоршалла для поиска всех кратчайших путей в ориентированном нагруженном графе.
  • Алгоритмы Прима и Крускала поиска опорного дерева (скелета) графа с минимальным суммарным весом.

  Домашние задания
№ 1 (02.03.2006)
  1. Является ли код a=0, b=01, c=11
    1. префиксным?
    2. разделимым?
    (5 баллов)
  2. Произвести кодирование по Хаффмену для следующего набора символов и их вероятностей:
    a=0.4, b=0.2, c=0.15, d=0.1, e=0.06, f=0.05, g=0.04.
    Какова будет цена получившегося кодирования?
    (2 балла)
  3. Произвести сжатие текста «оба одобрили обои бобра» по алгоритму Лемпеля – Зива.
    Какова будет длина «сжатого» текста (размер словаря)?
    (2 балла)
№ 2 (09.03.2006)
  1. Привести пример строки, для которой поиск подстроки «aaabaaa» будет более эффективным, если делать его методом Кнута – Морриса – Пратта, чем если делать его методом Бойера – Мура. И наоборот.
    (3 балла)
  2. Объясните, как влияет размер таблицы кодов в методе Бойера – Мура на скорость поиска.
    (5 баллов)
  3. Что такое «холостое срабатывание» в алгоритме поиска подстроки Рабина – Карпа?
    (1 балл)
№ 3
(16.03.2006)
  1. Реализовать алгоритм "многопутевого слияния". Функция должна получать массив упорядоченных массивов и выдавать один упорядоченный массив с длиной, равной сумме длин исходных массивов, содержащий все элементы исходных массивов.
    (4 балла)
  2. Реализовать алгоритм нахождения совпадающего по значению элемента в двух упорядоченных массивах. Как распространить алгоритм на произвольное число массивов («жулик на пособии»)?
    (4 балла)
  3. Реализовать алгоритм быстрой сортировки без использования рекурсии.
    (6 баллов)
№ 4
(23.03.2006)
  1. Реализовать интерфейс Date - сделать реализацию абстрактного типа данных "дата".
    (5 баллов)
  2. Реализовать внешнюю и внутреннюю итерацию списка для случая реализации списка в виде массива.
    (3 балла)
  3. Реализовать два дополнительных метода для итератора связанного списка: insertBefore (вставка перед текущим) и insertAfter (вставка после текущего). Текущий элемент определяется аналогично методу remove – это элемент, доступ к которому был определен последним вызовом next(). Предусмотреть случай корректной работы методов insertBefore и insertAfter для случая, когда текущим элементом является первый или последний элемент списка.
    (5 баллов)
№ 5
(30.03.2006)
  1. Реализовать класс PrioQueue (очередь с приоритетами) в виде пирамиды. Пирамида должна быть реализована в виде массива подобно тому, как это сделано в алгоритме пирамидальной сортировки. Интерфейс для реализации необходимо взять из презентации Стеки и очереди.
    (5 баллов)
  2. Реализовать анализ выражения с проверкой правильности. Исходное ыражение - это строка, содержащая первичные операнды (каждый операнд - это символ c, для которого функция Character.isLetterOrDigit(c) выдает значение true), соединенные круглыми скобками и знаками операций +, -, *. Функция должна в случае нормального завершения работы выдавать строку, представляющую это выражение в обратной польской записи, а в случае обнаружения ошибки генерировать исключительную ситуацию, содержащую код ошибки, причину ошибки и позицию в строке места, где обнаружена ошибка. Основной алгоритм обработки выражения можно взять из презентации Стеки и очереди.
    (5 баллов)
№ 6
(13.04.2006)
  1. Написать метод для определения «ширины» двоичного дерева. Шириной дерева будем называть максимальное из количеств узлов на каждом из уровней дерева.
    (3 балла)
  2. Написать внешний итератор двоичного дерева для метода обхода "сверху вниз". Под обходом "сверху вниз" понимается такой порядок обхода, при котором никакой узел, лежащий на уровне i, не может быть пройден раньше, чем будут пройдены все узлы, лежащие на меньших уровнях.
    (3 балла)
  3. Ключом в двоичном дереве поиска является "временной интервал", заданный своим началом и концом – "числом секунд от 1.1.1970". Ключи упорядочены в дереве по началам интервалов. В качестве дополнительной информации в узлах хранится максимальное из значений правых концов интервалов в поддереве с корнем в этом узле. Описать (словесно, на псевдокоде или на языке Java) алгоритм изменения дополнительной информации при "поворотах" и алгоритм определения множества интервалов (узлов дерева), содержащих заданный момент времени.
    (4 балла)

  Некоторые примеры
Алгоритмы Фано и Хаффмена кодирования сообщений
Алгоритмы поиска подстроки.
Алгоритмы сортировок массивов

  Презентации
Кодирование и шифрование.
Алгоритмы поиска подстрок.
Алгоритмы сортировок.
Абстрактные типы данных. Итераторы.
Стеки и очереди.
Деревья поиска.
Ассоциативные списки и хеширование.
Алгоритмы на графах.

  Результаты выполнения домашних заданий
    1 2 3 4 5 6

Итого
  Дата: 02.03 09.03 16.03 23.03 30.03 06.04  
  Максимум: 9 9 14 13 10 10  
1 Васильев А. 9 6 8 - -   23
2 Воскобойникова Т. 4 6 8 3 (0, 1, 2) 3 (0, 3) 6 (1, 3, 2) 30
3 Душутина О. 5 4 7 - -   16
4 Железов Д. 9 6 12 7 (3, 2, 2) 6 (4, 2) 7 (-, 3, 4) 47
5 Калюкин А. 9 4 9 9 (5, 1, 3) 9 (5, 4) 9 (3, 3, 3) 49
6 Карузе Н. 8 5 9 8 (4, 3, 1) 9 (5, 4) 10 (3, 3, 4) 49
7 Козырев П. 8 6 5 7 (3, 2, 2) 10 (5, 5) 6 (3, 3, -) 42
8 Костенко Е. - - - - -   0
9 Костенко Н. - - - - -   0
10 Ксенофонтова Е. 8 6 12 9 (5, 2, 2) 10 (5, 5) 6 (3, 3, 0) 51
11 Кучук Е. 5 - - - -   5
12 Мима А. 9 6 14 10 (5, 2, 3) 9 (5, 4) 3 (1, 2, 4) 55
13 Михайленко В. 8 5 10 8 (4, 2, 2) 0 (0, -) 5 (2, 3, -) 36
14 Назаров А. 4 - - - -   4
15 Немировский С. 5 - - - -   5
16 Помелов А. 9 6 13 9 (5, 3, 1) 5 (2, 3) 6 (3, 3, -) 48
17 Радолицкий Г. - 4 - - -   4
18 Салтан А. - 5 - - -   5
19 Соколова Ю. 5 6 2 - -   13
20 Строганова Д. 9 6 9 11 (4, 3, 4) 10 (5, 5) 9 (2, 3, 4) 54
21 Федоров А. 7 3 8 5 (5, -, -) 9 (5, 4) 4 (2, 2, -) 36
22 Чернов И. - 4 6 4 (1, 1, 2) 3 (0, 3)   17
23 Яркоев К. 8 7 13 13 (5, 3, 5) 8 (4, 4) 10 (3, 3, 4) 59

Примечания:

    Ответы на некоторые домашние задания
3.1
3.2		 Многопутевое слияние и "жулик на пособии".
3.3 Быстрая сортировка без использования рекурсии
5.2 Перевод выражения в обратную польскую запись с анализом ошибок