Алгоритмы и структуры данных. Подгруппа 105-1 — различия между версиями

Версия 02:20, 4 февраля 2015

О курсе

План лекций и список рекомендуемой литературы.

Оценивание домашних работ

• Все задания предполагаются индивидуальными. Запрещены любые заимствования без ссылки на автора.
• Решения после установленного дедлайна не принимаются. Дедлайн указан в заголовке каждого задания.
• Везде, где требуется написать алгоритм, можно использовать любой язык программирования или псевдокод.
• Там, где требуется построить алгоритм с заданной асимптотикой, приведите обоснование, что полученный алгоритм удовлетворяет этому условию.
• Эти правила не действуют, если в задании явно оговорено иное.

Мотивация к изучению алгоритмов. Подсчёт числа операций (12.01)

План занятия

1. Числа Фибоначчи. Определение. Примитивный рекурсивный алгоритм вычисления i-ого числа. Оценка числа операций. Анализ причин неэффективности. Алгоритм с запоминанием вычисленных ранее значений. Оценка числа операций. Сравнение с предыдущим. (подробнее: глава 0, страницы 8-10 из книги <<Алгоритмы>>, см. список рекомендованной литературы)
2. Задача о ханойской башне. Постановка задачи. Рекурсивный алгоритм. Рекуррентная формула для числа перемещений. Замкнутая формула для числа перемещений (+ доказательство). Доказательство того, что эту задачу нельзя решить используя меньшее число перемещений дисков. (Разбор задачи о ханойской башне, автор Сергей Объедков)
3. Сортировка пузырьком. Алгоритм. Подсчёт количество операций сравнения и обмена (swap). Анализ наилучшего и наихудшего случаев (Википедия)

Домашнее задание 1 (12.01 - 26.01)

• Для получения максимального балла требуется решить или все задачи без звёздочек, или все задачи со звёздочками.

Во всех задачах, если не оговорено иного, предполагаем, что работаем с целыми неотрицательными числами. Для первых 7 задач необходимо

• описать что можно считать наилучшим и наихудшим случаями,
• для каждого из двух случаев подсчитать отдельно количество операций сравнения и swap (если есть).

Задачи

1. Даны три числа, требуется вернуть наименьшее.
2. Даны три числа, требуется отсортировать их.
3. Дана последовательность A из n элементов и число x, требуется найти элемент равный x. Примечание: если таких значений i несколько, вернуть любое; если такого элемента нет, функция должна сообщить об этом.
4. * Дана упорядоченная последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Алгоритм должен быть эффективней, чем в предыдущем пункте и использовать то, что последовательность упорядочена.
5. Дана последовательность из 100 000 чисел от 0 до 100. Напишите эффективный алгоритм сортировки, который бы учитывал специфику входных данных.
6. * Дано 32 битное неотрицательное число. Требуется номер первого ненулевого бит. Разрешается использовать операцию обращения к i-тому биту. В дополнение к заданиям в преамбуле укажите математическое ожидание количества операций сравнения, считая, что числа распределены равномерно.
7. * Даны 32 битные неотрицательные числа m и n. Требуется вывести True, если m < n, иначе False. Разрешается использовать операцию обращения к i-тому биту. В дополнение к заданиям в преамбуле укажите математическое ожидание количества операций сравнения битов, считая, что числа распределены равномерно.
8. Напишите рекурсивную функцию, вычисляющую n-ое число Фибоначчи (как на занятии). Подсчитайте количество рекурсивных вызовов.
9. * Напишите функцию, вычисляющую n-ое число Фибоначчи, у которой число операций — полином от n, и которая использует количество памяти, независящее от n.

O-символика и стратегия "разделяй и властвуй" (15.01)

План занятия

1. Сортировка слиянием. Алгоритм, рекуррентное соотношение для времени сортировки, сложность. Подробнее: §2.3 Сортировка слиянием (стр. 54).
2. О-символика. §0.3 О-символика (стр. 10).
3. Задача о слиянии m упорядоченных массивов по n элементов. Три алгоритма решения: последовательное слияние, слияние "деревом" (обе функции используют Merge из MergeSort), аналог Merge для m массивов. Анализ сложности каждого из них.

Домашнее задание 2 (15.01-29.01)

• Для получения максимального балла требуется решить или все задачи без звёздочек, или все задачи со звёздочками.
• Во всех задачах, если не оговорено иного, для простоты можно считать, что n является степенью какого-либо числа, например, степенью двойки.

Задачи

1. Дана функция F, определённая ниже. Сколько строк она напечатает? Указание: для обоих подпунктов рассмотрите два случая: 1. n является степенью двойки, 2. n не является степенью двойки.
   1. Запишите рекуррентное соотношение для числа строк.
   2. Решите уравнение, полученное в предыдущем пункте, то есть, выведите замкнутую (нерекуррентную формулу). Для простоты можно считать, что n является степенью двойки.
2. В массиве A размера n записана возрастающая последовательность целых чисел. Постройте алгоритм типа "разделяй и властвуй", который проверяет, существует ли такой индекс i, что A[i] = i
   1. за время O(n),
   2. * за время O(log n).
   3. Какие случаи для вашего алгоритма являются наихудшими и наилучшими? Какого время работы в лучшем и худшем случаях?
3. Дан бесконечный массив A, первые n элементов которого содержат возрастающую последовательность положительных чисел, а дальше стоят -1. Значение n не дано. Постройте алгоритм, который получает на вход целое число x и находит это x в массиве --- или говорит, что там его нет,
   1. за время O(n),
   2. за время O(log n).
4. Рассмотрим алгоритм вычисления наибольшего общего делителя (НОД) двух положительных чисел, основанный на методе "разделяй и властвуй".
   1. (задание не оценивается) Прочитайте §1.2.3 Алгоритм Евклида (стр. 23).
   2. * Докажите, что определение НОД-а, приведённое ниже, корректно.
   3. Постройте алгоритм, основанный на этом определении.
   4. Какой алгоритм будет быстрее для n-битовых чисел a и b при больших значениях n --- ваш или алгоритм Евклида?
5. * Покажите как за время O(n log n) удалить из массива размера n все дубликаты, то есть оставить каждый элемент в одном экземпляре.
6. * Даны два упорядоченных массива размера m и n. Постройте алгоритм, находящий k-й по величине элемент в объединении этих массивов за время O(log(n+m)).

Функция F(n).

 если n > 1:
   напечатать "всё ещё работаю"
   F(n/2)
   F(n/2)

Определение НОД-а.

            2НОД(a/2, b/2), если а и b чётны,
 НОД(a,b) = НОД(a, b/2), если а нечётно, b чётно,
            НОД((a-b)/2, b), если а и b нечётны.

Задачи взяты из книги "Алгоритмы", глава 2 (см. список рекомендованной литературы).

Сложение и умножение (19.01)

План занятия

1. Алгоритм сложения, его сложность (§1.1.1 Сложение*)
2. "Школьный" алгоритм умножения и его сложность (§1.1.2 Умножение*)
3. Рекурсивный алгоритм умножения и его сложность (§1.1.2 Умножение*)
4. Алгоритм умножения, реализующий стратегию "разделяй и властвуй", анализ сложности (§2.1 Умножение чисел*)

* Читать.

Домашнее задание 3 (19.01 - 2.02)

• Во всех задачах для простоты можно считать, что n является степенью какого-либо числа.

Задачи

1. Найдите произведение чисел 10011011 и 10111010 (в двоичной системе счисления), используя алгоритм умножения чисел, основанный на методе «разделяй и властвуй». Необходимо не только дать ответ, но и привести ход решения.
2. Алгоритм, решая задачу размера n, производит 3 рекурсивных вызова для подзадач размера n-1 и комбинирует из них решение исходной задачи за О(n).
   1. Напишите рекуррентную формулу, описывающую количество операций.
   2. Нарисуйте три верхних уровня дерева вызовов.
   3. Сколько всего будет уровней?
   4. Сколько подзадач на i-ом уровне?
   5. Какой размер каждой подзадачи на i-ом уровне?
   6. Какова сложность работы алгоритма?
3. Алгоритм, решая задачу размера n, производит 10 рекурсивных вызовов для подзадач размера n/2 и комбинирует из них решение исходной задачи за О(5n).
   1. Напишите рекуррентную формулу, описывающую количество операций.
   2. Нарисуйте два верхних уровня дерева вызовов.
   3. Сколько всего будет уровней?
   4. Сколько подзадач на i-ом уровне?
   5. Какой размер каждой подзадачи на i-ом уровне?
   6. Какова сложность работы алгоритма?
4. Докажите, что 3m² + m = O(m²).
5. Докажите, что lg m = O(m/1000), где lg m — это логарифм с двоичным основанием.
6. Докажите, что из равенства f(n) = O(g(n)) не следует, что g(n) = O(f(n)).
7. Докажите, что O(m) содержится в O(m²).

Решение рекуррентных уравнений (22.01)

План занятия

1. Примеры решений рекуррентных уравнений (см. конспект).

Домашнее задание 4 (23.01 - 6.02)

• Нельзя использовать утверждение основной теоремы о решении рекуррентных соотношений.
• Можно использовать метод построения дерева рекурсии или подстановку (метод с угадыванием ответа).

Задачи

1. Какой из трёх приведённых ниже алгоритмов вы бы предпочли? Обоснуйте свой ответ.
   • Алгоритм A, решая задачу, производит пять рекурсивных вызовов для подзадач вдвое меньшего размера, после чего строит ответ для исходной задачи за линейное время.
   • Алгоритм B, решая задачу размера n, делает два рекурсивных вызова для задач размера n − 1, после чего находит ответ за время O(1).
   • Алгоритм C, решая задачу размера n, рекурсивно решает девять задач размера n/3 и строит ответ за время O(n²).
2. Найдите T(n) в замкнутой форме для любых 7 из 10 приведённых ниже рекуррентных соотношений:
   1. T(n) ≤ 2T(n/3) + 1;
   2. T(n) ≤ 7T(n/7) + n;
   3. T(n) ≤ 9T(n/3) + n²;
   4. T(n) ≤ 8T(n/2) + n³;
   5. T(n) ≤ 49T(n/25) + n^3/2log n;
   6. T(n) ≤ T(n − 1) + 2;
   7. T(n) ≤ T(n − 1) + n^c, где c ≥ 1 –– константа;
   8. T(n) ≤ T(n − 1) + cⁿ, где c > 1 –– константа;
   9. T(n) ≤ 2T(n − 1) + 1;
   10. T(n) ≤ T(sqrt(n)) + 1.

Большое домашнее задание №1

Необходимо реализовать все 6 задач из контеста. Каждую задачу можно писать на С++ или Python. На выполнение работы отводится две недели. Каждая задача оценивается в 10/6 балла. Оценка может быть снижена за плохой код, но не более чем на 25%.

Бинарное дерево поиска (26.01)

План занятия

1. Определение. Пример.
2. Не модифицирующие алгоритмы: поиск (рекурсивный и итеративный алгоритмы), поиск минимума, inordered обход (вывод значений узлов в отсортированном порядке), поиск следующего по возрастанию.
3. Модифицирующие алгоритмы: вставка (рекурсивная реализация), удаление (только идея).

Читать Кормена и др., глава 13, стр. 248

Домашнее задание 4 (26.01 - 9.02)

• Для получения максимальной оценки можно выполнить или все задачи без звёздочки, или задачу со звёздочкой. Преподаватель понимает, что реализацию БДП сложно не найти в интернете, но от копипасты не будет никакой пользы. Напротив, самостоятельная реализация очень полезна и приветствуется, даже если не получится выполнить всех пунктов задания.
• Задачи с двумя звёздочками необязательны.

Задачи

1. Нарисуйте бинарные деревья поиска высотой 2, 3, 4, 5 и 6 для множества ключей {1, 4, 5, 10, 16, 17, 21}.
2. Сортировка с использованием БДП.
   1. Какова асимптотическая сложность алгоритма вставки элемента в дерево высоты d? Почему? Назовите наилучший и наиухдший случаи.
   2. Дана последовательность из n чисел. Напишите алгоритм, который строит БДП в узлах которого стоят элементы данной последовательности. Можно использовать функцию Insert. Назовите наилучший и наихудший случаи. Есть теорема о том, что полученный алгоритм будет работать в среднем случае за время O(n * log n).
   3. Дана последовательность из n чисел. Напишите алгоритм, который выводит их в порядке возрастания. Используйте бинарное дерево поиска. Какова в среднем случае сложность этого алгоритма? Назовите наилучший и наихудший случаи. Какова сложность в наихудшем случае?
3. Напишите функцию GetRoot, которой на вход подаётся указатель на произвольный узел дерева, а она возвращает указатель на корень.
4. Напишите процедуру PrintLeafs, которой на вход подаётся указатель на корень дерева, и она печатает листья дерева
   1. по возрастанию,
   2. по убыванию.
5. ** Альтернативный обход в порядке возрастания бинарного дерева поиска с n узлами (или центрированный (inordered) обход) можно осуществить путём поиска минимального элемента дерева с помощью функции Minimum с последующий n-1 вызовом функции Next. Каково время работы такого алгоритма?
6. * Реализуйте на С++ структуру данных бинарное дерево поиска, используя заготовку.
   1. Нарисуйте бинарное дерево поиска, которое строится в функции getTreeExample.
   2. Реализуйте следующие алгоритмы:
      1. поиск минимума,
      2. inordered обход (вывод значений узлов в отсортированном порядке),
      3. поиск следующего по возрастанию,
      4. вставка элемента в дерево,
      5. сортировка последовательности с использованием БДП (дан вектор чисел, необходимо вывести их по возрастанию),
      6. ** удаление.

Алгоритм Карацубы, Штрассена. Быстрая сортировка (29.01)

План занятия

1. Алгоритм Карацубы.
2. Алгоритм Штрассена. Читать Дасгупту и др., §2.5 Умножение матриц
3. Быстрая сортировка и доказательство того, что в среднем случае она работает за О(n * log n). Читать Кормена и др., глава 8 Быстрая сортировка, стр. 148

Домашнее задание 5 (30.01 - 12.02)

Задачи

1. Пусть мы хотим найти двоичное представление десятичного числа 10ⁿ. Будем считать, что n --- степень двойки (n = 2^k).

   Pwr2Bin(n):
       если n == 1:
           вернуть 1010
       z = ...
       вернуть Multiply(z, z)

   Multiply --- функция, перемножающая два n-битовых двоичных числа x и y по алгоритму Карацубы за O(n^log₂3).

   1. Впишите недостающую строку псевдокода.
   2. Запишите рекуррентное соотношение на время работы и решите его.
2. Пусть мы хотим перевести произвольное десятичное число x в записи которого n=2^k чисел в двоичную систему счисления.

   Dec2Bin(n):
       если n == 1:
           вернуть binary[x]
       разделить x на два десятичных числа xl и xr из n/2 цифр.
       вернуть ...

   Здесь binary --- это массив, содержащий двоичное представление десятичных цифр.

   1. Впишите недостающую строку псевдокода.
   2. Запишите рекуррентное соотношение на время работы и решите его.
3. Докажите, что математическое ожидание времени работы алгоритма быстрой сортировки (усреднение по всем вариантам выбора опорного элемента) на любом входе размера n удовлетворяет соотношению: T(n) ≤ O(n) + 1/n * Σⁿ_i=1 (T(i-1) + T(n-i)).
4. Найдите решение соотношения из предыдущего пункта.

Динамическое программирование. Первые примеры (02.01)

План занятия

1. Нахождение самой длинной возрастающей подпоследовательности.
2. Нахождение редакционного расстояния (или редакционной стоимости, расстояния Левенштейна).
3. Нахождение представителя большинства.

Домашнее задание 6 (до 16.02)

• В этом задании везде, где требуется реализовать алгоритм, необходимо привести код на любом языке программирования.
• Для получения максимальной оценки можно решить первую задачу и либо все задачи без звёздочек, либо все с одной звёздочкой, либо одну с двумя звёздочками.

Задачи

1. Реализуйте алгоритм нахождения редакционного расстояния (алгоритм Вагнера — Фишера). Например, редакционное расстояние между словами "anthropology" и "anthologies" равно 6.
2. Реализуйте алгоритм нахождения длины наибольшей общей подстроки. Например, длина наибольшей общей подстроки "anthropology" и "anthologies" равна 8. Чем больше это значение, тем похожей строки.
3. Предположим теперь, что сравниваемые строки состоят из символов A, С, G и T. И за удаление или вставку мы платим -5. За замену буквы x на y платим w[x, y], где x, y принадлежат множеству {A, С, G, T}, a w --- это матрица весов:

   -	A	G	C	T
   A	10	-1	-3	-4
   G	-1	7	-5	-3
   C	-3	-5	9	0
   T	-4	-3	0	8

   Тогда выравнивание:

   AGACTAGTTAC
   CGA‒‒‒GACGT
   

   будет иметь следующую оценку:

   w[A,C] + w[G,G] + w[A,A] + 3*(-5) + w[G,G] + w[T,A] + w[T,C] + w[A,G] + w[C,T] = -3 + 7 + 10 - 3*5 + 7 + (-4) + 0 + (-1) + 0 = 1.
   

   Напишите алгоритм, который находит максимальную стоимость всех возможных выравниваний. Верно ли, что чем больше значение, тем непохожей строки?

4. Как давно один народ отделился от другого? Кто похожей — итальянец и китаец или якут и эфиоп? На эти вопросы можно отвечать с разных точек зрения — культурной, исторической, лингвистической, ... В последние же годы человечество научилось секвенировать геном, что позволило исследовать этот вопрос с точки зрения генетики. Секвенирование генома — это процесс записи ДНК в виде нуклеотидной последовательности, которая представляет собой последовательность из четырёх символов — A, С, G и T. Существуют базы, которые хранят генетическую информацию о людях из разных стран и континентов, например, http://www.mtdb.igp.uu.se/. Чем меньше различий между геномами, тем сильнее родственные связи между их обладателями. Используя решение предыдущего пункта, выполните задания:
   1. 1. Определите, кто похожей — итальянец и китаец или якут и эфиоп?
      2. Найдите нескольких похожих и нескольких непохожих народностей.
      3. * Выберите одну народность. Найдите самых похожих и самых непохожих на неё.
      4. * Найдите самые похожие и самые непохожие народности.