Алгоритмы и структуры данных. Подгруппа 105-1

О курсе

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

FAQ.

Инструкция по использованию Reviewboard.

Style guide.

Итоговая оценка за курс

Итоговая оценка (ИО) зависит от

• оценок за пять больших домашних заданий (БДЗ1, БДЗ2, ..., БДЗ5),
• оценок за домашние задания (ДЗ1, ДЗ2, ...),
• оценки за контрольную работу (КР),
• оценки за экзамен (ЭКЗ),

и может быть вычислена по формуле:

ИО = 0.7 * (0.3 * КР + 0.7 *(ИДЗ1 + ИДЗ2 + ИДЗ3 + ИДЗ4 + ИДЗ5)/5) + 0.3 * ЭКЗ =
   = 0.21*КР + 0.098*ИДЗ1 + 0.098*ИДЗ2 + 0.098*ИДЗ3 + 0.098*ИДЗ4 + 0.098*ИДЗ5 + 0.3*ЭКЗ,

где

ИДЗi = min (10, 0.7 * БДЗi + 0.4 * <cредняя оценка за ДЗj, прошедшие с предыдущего БДЗ по i-ое>)

Порядок сдачи домашних работ

Большие домашние работы

1. Получить OK за задачу в контесте.
2. Залить исходный код на Review Board. Инструкция по использованию Review Board.
   • На каждую задачу создавайте отдельный запрос на ревью.
   • В поле Reviewers - People указать логин семинариста (avalanche) и учебного ассистента (kudrandrew).
   • Не забудьте нажать Publish.
   • Работы, которые не были отправлены в RB, не оцениваются.
3. В течении суток приходят замечания к коду. Если в течении суток замечаний или Ship It не появилось, проверьте, что вы правильно отправили запрос и, если всё сделано правильно, спросите у семинариста получил ли он запрос.
4. Вы их исправляете, проверяете в контесте, что программа по-прежнему проходит все тесты, заливаете новую версию в Review Board. Штрафов за посылки НЕ будет.
5. Процесс повторяется пока остаются замечания к коду или пока не истёк дедлайн. После закрытия контеста будут ещё одни сутки на доработку замечаний в Review Board.
6. Оценивается только последняя версия работы в Review Board.

Маленькие домашние работы

1. Залить решение на Review Board. Инструкция по использованию Review Board.
   • Желаемые форматы: txt, py, cpp, h. Допускаются любые другие.
   • На каждую домашнюю работу создавайте отдельный запрос на ревью. Обязательно указывайте номер домашней работы.
   • В поле Reviewers - People указать логин семинариста (avalanche) и учебного ассистента (kudrandrew).
   • Не забудьте нажать Publish.
   • Работы, которые не были отправлены в RB, не оцениваются.
2. В течении неопределенного промежутка времени придут оценки по каждому из заданий.

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

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

Мотивация к изучению алгоритмов. Подсчёт числа операций (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 (до 14.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

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

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

Задачи

1. Нарисуйте бинарные деревья поиска высотой 2, 3, 4, 5 и 6 для множества ключей {1, 4, 5, 10, 16, 17, 21}. Корень дерева имеет высоту 0.
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

Домашнее задание 6 (до 18.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(x, 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. Нахождение представителя большинства.

Домашнее задание 7 (до 20.02)

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

Задачи

1. Реализуйте алгоритм нахождения редакционного расстояния (алгоритм Вагнера — Фишера). Например, редакционное расстояние между словами "anthropology" и "anthologies" равно 6.
2. Реализуйте алгоритм нахождения длины наибольшей общей подстроки. Например, длина наибольшей общей подстроки "anthropology" и "anthologies" равна 8 ("antholog"). Чем больше это значение, тем схожей строки.
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/ → Download mtDNA sequences. Чем больше сходство между геномами, тем сильнее родственные связи между их обладателями. Используя решение предыдущего пункта, выполните задания:
   1. Определите, кто похожей — итальянец и китаец или якут и эфиоп?
   2. Найдите нескольких похожих и нескольких непохожих народностей.
   3. * Выберите одну народность. Найдите самых похожих и самых непохожих на неё.
   4. * Найдите самые похожие и самые непохожие народности.

ДП. Задача о разрезании стержня (05.01)

1. Постановка задачи.
2. Решение с нахождением максимума по r_i + r_n-i. Алгоритм. Дерево рекурсивных вызовов. Оценка сложности.
3. Решение с нахождением максимума по p_i + r_n-i. Алгоритм. Дерево рекурсивных вызовов. Оценка сложности.
4. Восходящий алгоритм с запоминанием. Вывод длин кусочков стержня. Оценка сложности.
5. Нисходящий алгоритм с запоминанием. Оценка сложности.

Читать Кормена и др., 3-е изд., §15.1 Разрезание стержня, стр. 393

Домашнее задание 8 (до 22.02)

1. Решая задачу о разрезании стержня мы вначале построили рекурсивное решение с нахождением максимума по r_i + r_n-i для всех 1 ≤ i < n. Его сложность описывалась рекуррентной формулой T(n) = n + Σ^n-1_i=1(T(i) + T(n-i)), T(1) = 1.
   1. Объясните эту формулу.
   2. Покажите с помощью метода подстановок, что T(n) ≤ 2ⁿ.
2. Покажите с помощью контрпримера, что описанная далее жадная стратегия не всегда определяет оптимальный способ разрезания стержня. Определим плотность стержня длиной i как p_i/i, то есть как стоимость единицы его длины. Жадная стратегия для стержня длиной n отрезает от стержня первую часть длиной i, где 1 ≤ i ≤ n, имеющую максимальную плотность. Затем та же жадная стратегия применяется к оставшейся части длиной n-i.
3. Рассмотрим модификацию задачи разрезания стержня, в которой в дополнение к цене p_i каждого стержня добавляется фиксированная цена разреза c. Теперь прибыль, связанная с решением, представляет собой сумму цен частей стержня минус стоимость разрезов. Разработайте алгоритм динамического программирования для этой модифицированной задачи.
4. Непрерывным участком называется группа подряд идущих элементов. Например, для последовательности 5, 15, −30, 10, −5, 40, 10 элементы 15, −30, 10 образуют непрерывный участок, а 5, 15, 40 -- нет. Постройте линейный алгоритм для следующей задачи:

   Вход: список чисел a1, a2, ... ‌, an.
   Выход: непрерывный участок с максимальной суммой (сумма участка нулевой длины равна нулю).

   Для приведённого примера ответом будет 10, −5, 40, 10 с суммой 55. Какова сложность алгоритма? Почему?

5. Надо заплатить v рублей, имея купюры в x1, x2, ‌..., xn рублей (купюр каждого типа сколько угодно). Это не всегда возможно (скажем, купюрами в 10 и 25 рублей можно заплатить 45 рублей, но не 47 и не 15). Постройте основанный на методе динамического программирования алгоритм со временем работы O(nv), выясняющий, возможна ли уплата.
6. Как решить предыдущую задачу, если каждая купюра имеется в единственном экземпляре? (Например, купюрами в 1, 5, 10, 20 рублей можно заплатить 16 = 1 + 5 + 10 и 31 = 1 + 10 + 20 рублей, но не 40 (не хватит денег). Время работы алгоритма по-прежнему O(nv).
7. Ещё один вариант той же задачи: купюр каждого типа сколько угодно, но всего разрешается использовать не более k купюр. (Например, если есть купюры в 5 и 10 рублей, а k = 6, то 55 разменять можно, а 65 –– нет).

ДП. Перемножение цепочки матриц. Оптимальное бинарное дерево поиска (начало) (09.02)

1. Задача о перемножении цепочки матриц. Постановка задачи.Пример. Нисходящий алгоритм. Читать Кормена и др., 3-е изд., §15.2 Перемножение цепочки матриц, стр. 403
2. Построение оптимального дерева поиска. Постановка задачи. Читать Кормена и др., 3-е изд., §15.5 Оптимальные бинарные деревья поиска, стр. 431

Домашнее задание 9 (до 24.02)

1. Найдите оптимальную расстановку скобок в произведении последовательности матриц, размерности которых равны 5×10, 10×3, 3×12, 12×5, 5×50, 50×6.
2. Напишите восходящий алгоритм для поиска оптимальной расстановки скобок.

ДП. Расстановка пробелов. Оптимальное бинарное дерево поиска (середина) (12.02)

1. Задача о расстановке пробелов. Постановка задачи. Решения для трёх случаев: 1. нужно вернуть можно ли разбить текст на слова; 2. вернуть разбивку на слова; 3. слова встречаются не равновероятно, вернуть наиболее вероятную разбивку на слова.
2. Построение оптимального дерева поиска. Постановка задачи. Вывод математического ожидания времени поиска. Читать Кормена и др., 3-е изд., §15.5 Оптимальные бинарные деревья поиска, стр. 431

Праздничное домашнее задание 10 (до 02.03)

1. ["♥♥♥♡", "♡♡♡", "♡♥♡", "❥♥♡", "♥♡♡", "♡♥♡♡", "♥♡♥", "♥♥♥", "♡♡♡♡", "❥♥♥", "♥♥♡♥", "❥❥♡", "♥♡♥♥", "❥♡♥", "♡♥♥", "♥♡♡♥", "♡♥♥♡", "❥❥♥", "♥♥♡", "♡♡♥♥", "♥♥♡♥♥", "♥♡♡♡", "♥♥♥♥", ",", "."] "♡♡♡♥♡♡♥❥♥♥♡♡♡♡❥♥♥❥❥♡❥❥♥♡♥♡❥♥♡♡♥♡♥♡♡♡♥♡♡♡♥♥❥❥♥♡♡♡♡❥♥♥♥♥♡♥♥♡♥♡♡♡♥♡♡❥♥♡♥♡♥♥❥♥♥♡♥♥❥♥♡❥♡♥❥♡♥♡♥♡♡♥♡♡♡❥❥♡❥❥♥♡♥♡♥♥♥❥❥♡. ♥♡♡♥♥♡♥❥♥♥♥♡♥♥♡♡♡♥♥♥♡❥♥♥❥❥♡❥❥♥♡♥♡♡♡♡♡♥♥,❥❥♥♥♥♥♥♡♥♥❥♥♥❥❥♥♥♥♥❥❥♡♡♥♥♡."
   Подсказка: разбейте текст на слова из списка и посмотрите на азбуку Морзе.

Способы представления графов в памяти (16.02)

1. Разбор ошибок в домашнем задании.
2. Графы. Способы представления графов в памяти (матрица смежности, список рёбер, список соседей (список смежностей), матрица инцидентности). Зависимость сложности алгоритмов от способа представления. Читать Кормена и др., 3-е изд., §22.1 Представление графов, стр. 626

Домашнее задание 11 (до 02.03)

1. Задача A.
2. Задача B.
3. Нарисуйте неориентированный граф с 5 вершинами и 8 рёбрами. Напишите его матрицу смежности, список рёбер, список соседей (список смежностей), матрицу инцидентности.
4. Нарисуйте ориентированный граф с 4 вершинами и 3 рёбрами. Напишите его матрицу смежности, список рёбер, список соседей (список смежностей), матрицу инцидентности.
5. Дан ориентированный граф. Исходящая степень вершины v --- это количество исходящих из неё рёбер, входящая степень v --- это количество рёбер входящих в v. Имеется представление ориентированного графа с использование списка соседей. Как долго будут вычисляться исходящие степени всех вершин графа? А входящие степени?
6. Дан граф G = (V, E). Какие из рассмотренных способов хранения графов используют меньше всего памяти для хранения G и почему? Указание: рассмотрите случаи |V|² < |E| и |V|² > |E|.
7. Пусть C --- это матрица смежности графа G.
   1. Как связаны элементы матрицы С² и граф G?
   2. Как связаны элементы матрицы Сⁿ и граф G?
8. Пусть B --- это матрица инцидентности ориентированного графа G. Как связаны элементы матрицы BB^T и граф G?

Реализация поиска в глубину (19.02)

1. Реализация поиска в глубину и смежных задач.

Домашнее задание 12 (до 5.03)

1. (С++) Выберите любой способ хранения графа. Реализуйте поиск в глубину.
2. (С++) Напишите алгоритм, который возвращает данные о том, какие вершины лежат в одной компоненте связности.
3. (любой ЯП или псевдокод) Напишите алгоритм проверки сильной связности ориентированного графа. Какова его сложность?

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

Задание индивидуальное. В случае нарушения академических норм, ставится 0 за весь контест.

Необходимо реализовать 3 задачи из контеста, см. распределение задач. Каждую задачу можно написать на С++ или Python. На выполнение работы отводится две недели (см. время окончания контеста). Дорешивание.

Жадные алгоритмы (12.03)

Домашнее задание 13 (до 23.03)

1. Вася хочет купить по одной акции каждой компании. Все акции стоят одинаково, но дорожают по-разному. Каждый месяц акция i-ой компании дорожает в r_i раз. В один месяц можно купить только одну акцию.
   1. Напишите алгоритм, который выводит оптимальную последовательность покупок (такую, что на покупку всех акций потратится меньше денег).
   2. Докажите корректность алгоритма, то есть докажите, что последовательность покупок, которую выводит ваш алгоритм, оптимальна.

Структуры данных: список, очередь (16.03)

1. Реализация линейного двусвязного списка (С++).
2. Реализация очереди ограниченной длины на базе вектора (С++).
3. Реализация очереди на базе списка (С++).

Домашнее задание 14 (до 23.03)

1. Реализуйте (на С++) структуру данных Стек. У стека должно быть три операции:
   • push --- положить элемент на вершину стека;
   • pop --- удалить верхний элемент;
   • front --- вернуть значение верхнего элемента.
   Оцените время работы каждой функции.

Структуры данных: список (19.03)

Домашнее задание 13* (до 30.03)

1. Для приведённой реализации класса List (https://yadi.sk/i/c5r_79WdfMyNS).
   1. Допишите print, push_back и push_front.
   2. В функции insert_after и delete_node вставьте необходимые проверки так, чтобы они работали для крайних случаев.
   3. Напишите main в котором
      1. создаётся объект класса List,
      2. заполняется элементами с помощью функций push_back, push_front и insert_after и
      3. удаляется i-ый элемент.

Повторение (30.03)

1. Для данных пар функций выясните их связь в терминах O-, o-, Ω-, ω-, Θ-обозначений. Поставьте галочку в клетке с Ω, если f(x) = Ω(g(x)) и прочерк, если равенства нет. Википедия

   f(x)	g(x)	O	o	Ω	ω	Θ
   1	n
   1	2^100
   n * log(n)	2^100 * n * log(n)
   n	2^100 * log(n)
   n!	2^(2015n)
   n*2^n	3^n
   5^n	5^(n+1)
   n + n^2 + n^3 + ... + n^1000	7^n

2. Реализуйте алгоритм Quickselect нахождения k-ого элемента по возрастанию: http://en.wikipedia.org/wiki/Quickselect
3. На улице стоит ряд домов. В каждом из домов лежит сколько-то денег. Вор хочет обокрасть дома на переулке. Он не может обокрасть два соседних дома, потому что хозяин дома, который он обокрал, сразу предупредит соседей. Нужно найти, какую максимальную сумму вор может украсть с переулка. На вход программы подается массив неотрицательных целых чисел - количество долларов в доме с номером i. Соседние дома в массиве представлены соседними элементами. Например, пусть задан массив { 1, 4, 5 } - тогда вор максимум может украсть $6, обокрав дома 1 и 3. Пусть задан массив { 1, 7, 2 } - тогда вор максимум может украсть $7, обокрав дом 2.
   1. Придумайте алгоритм, решающий эту задачу.
   2. Реализуйте приведённый алгоритм на С++ или Python.
   3. Оцените сложность алгоритма.
4. Алфавит из всех маленьких латинских букв и пробела закодирован числами следующим способом: 'a' -> 1 'b' -> 2 'c' -> 3 ... 'z' -> 26 ' ' -> 27 На вход программы подается строка из цифр. Нужно посчитать, сколькими способами можно раскодировать эту строку.
   1. Придумайте алгоритм, решающий эту задачу.
   2. Реализуйте приведённый алгоритм на С++ или Python.
   3. Оцените сложность алгоритма.
5. Дан граф, заданный матрицей смежности. Вывести пары вершин между которыми нет пути.
   1. Придумайте алгоритм, решающий эту задачу.
   2. Реализуйте приведённый алгоритм на С++ или Python.
   3. Оцените сложность алгоритма.

Повторение (02.04)

Решали и разбирали первые 4 задачи из списка https://yadi.sk/i/2hqNdboefgrQB

Домашнее задание 14* (до 11.03)

Решите любые две задачи (подпункты НЕ считаются отдельными задачами) с предыдущей пары (Повторение (30.03)).

Повторение (06.04)

Будем решать вторую половину задач из списка https://yadi.sk/i/2hqNdboefgrQB

Домашнее задание 15 (до 16.04)

1. Приведите пример графа, который содержит отрицательные рёбра, не содержит циклов отрицательного веса и для которого алгоритм Дейкстры возвращает неверный результат.
2. Используется ли в алгоритме Дейкстры то, что веса рёбер неотрицательны? Если "да", то где именно?
3. Пусть граф содержит рёбра с весами >= -100. Если прибавить к каждому ребру 101 и при помощи алгоритма Дейкстры найти кратчайшие пути. Будут ли эти пути кратчайшими в исходном графе? Почему?

Повторение (07.04)

Решение рекуррентных соотношений

1. Решите уравнение: T(n) = 4*T(n/2) + O(n^2) с базой T(1) = O(1)
   1. Используя основную теорему.
   2. Используя дерево рекурсий.
   3. Методом подстановки.
2. Покажите, что решением T(n) = 2 T(floor(n/2)) + n является \Theta(n lg n).
3. Покажите, что решением T(n) = 2 T(floor(n/2) + 17) + n является \Theta(n lg n).
4. Решите уравнения, считая, что T(1) = O(1):
   1. T(n) = T(n-1) + n
   2. T(n) = 2*T(floor(sqrt(n))) + lg n. Указание: попробуйте использовать замену переменных.
   3. T(n) = 3*T(sqrt(n)) + lg n
5. Дайте верхнюю и нижнюю оценки функции T(n). Постарайтесь, чтобы оценки были как можно более точные
   1. T(n) = 4T(n/3) + n*lg(n)
   2. T(n) = 3T(n/3) + n/lg(n)
   3. T(n) = 4T(n/2) + n^2*sqrt(n)
   4. T(n) = T(n/2) + T(n/4) + T(n/8) + n
   5. T(n) = T(n-1) + 1/n
   6. T(n) = T(n-2) + 1/lg(n)
   7. T(n) = sqrt(n) * T(sqrt(n)) + n

Анализ и построение алгоритмов

1. Числа Фибоначчи F₁, F₂ можно выразить через F₀, F₁, используя матрицу: https://yadi.sk/i/Pm_aNzHCforFU.
   1. Покажите как вычислить F₂, F₃ через F₁, F₂.
   2. Как вычислить F_n, F_n+1 через F₀, F₁?
   3. Напишите алгоритм.
   4. Какова сложность алгоритма?
   5. Ускорьте его так, чтобы он работал за O(log n).
2. Дана последовательность символов. Какое минимальное количество символов нужно удалить из неё, чтобы получить палиндром?
   1. Напишите алгоритм (на псевдокоде или на любом языке программирования).
   2. Оцените время работы алгоритма.
3. Какую структуру данных вы бы использовали для реализации упорядоченного множества (http://neerc.ifmo.ru/wiki/index.php?title=Упорядоченное_множество)? Какая будет сложность каждой из операций над множеством?

Домашнее задание 16 (до 20.04)

1. Решите 6 задач из первой части и 6 из второй. (Укажите какие именно.) Каждый из подпунктов является отдельной задачей.

Алгоритм и теорема Форда-Фалкерсона (16.04)

1. Базовые определения (пропускные способности, сток, исток и пр.). Пример.
2. Ограничения на поток (сохранение и что меньше пропускных способностей).
3. Алгоритм Форда-Фалкерсона, пример работы
4. Разрез, определение, пример.
5. Утверждение: максимальный поток <= любого разреза.
6. Теорема Форда-Фалкерсона (с доказательством).
7. Пример на котором алгоритм Форда-Фалкерсонаработает работает очень долго при неудачном выборе путей.
8. Сложность алгоритма Форда-Фалкерсона.

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

Задание индивидуальное. В случае нарушения академических норм, ставится 0 за весь контест.

В домашнем задании пять задач. Они разделены на два варианта, помеченные римскими цифрами I и II. Свой вариант нужно узнать здесь на вкладке HW3. Третья задача — общая для двух вариантов; ее решение необходимо снабдить доказательством корректности алгоритма. На выполнение задания дается примерно 2 недели (см. точное время окончания в контесте). Каждую задачу можно написать на С++ или Python.

Алгоритм Форда-Фалкерсона и Эдмондса-Карпа (20.04)

1. Алгоритм Форда-Фалкерсона, напоминание: базовые определения, пример работы, пример на котором алгоритм работает долго, сложность.
2. Алгоритм Эдмодса-Карпа. Доказательство асимптотики времени работы.

(11.05) Красно-чёрные деревья

Красно-чёрное дерево

Домашнее задание 17 (до 18.05)

1. Зачем нужны красно-чёрные деревья?
2. Благодаря какому свойству и почему красно-чёрное дерево является сбалансированным?
3. Нарисуйте полное бинарное дерево поиска высотой 3 с ключами {1, 2, ..., 15}. Сделайте из него красно-чёрные деревья высотой 2, 3 и 4.
4. Нарисуйте красно-чёрные деревья, получающиеся последовательной вставкой элементов 12, 10, 29, 30, 31, 32 в данное дерево. Для вставки используйте алгоритм вставки из Википедии. Укажите какой именно функцией вы воспользовались.
5. Определим ослабленное красно-чёрное дерево как бинарное дерево поиска, которое удовлетворяет красно-чёрным свойствам 1, 3, 4 и 5. Другими словами, корень может быть как чёрным, так и красным. Рассмотрите ослабленное красно-чёрное дерево T, корень которого красный. Если перекрасить корень дерева T в чёрный, будет ли оно красно-чёрным деревом?
6. Покажите, что самый длинный простой нисходящий путь от вершины x к листу красно-черного дерева имеет длину, не более чем в два раза превышающую кратчайший путь от x к листу-потомку.
7. Чему равно наибольшее возможное количество внутренних узлов в красно-чёрном дереве с чёрной высоты k? А наименьшее возможное количество?
8. Нарисуйте красно-чёрные деревья, получающиеся последовательной вставкой ключей 41, 38, 31, 12, 19, 8 в изначально пустое дерево.
9. Покажите какие деревья будут получаться в результате последовательного удаления ключей в порядке 8, 12, 19, 31, 38, 41.

(14.05) Конкурентный анализ самоорганизующихся циклов

Лекция

Домашнее задание 18 (до 21.05)

Все вычисления сопроводите подробными объяснениями о том, почему верно то или иное (не)равенство.

1. Пусть имеется n-элементный список и m поисковых запросов к нему. После каждой операции поиска можно переупорядочить список. Обозначим стоимость последовательности поисков через C. Докажите, что в худшем случае C = Ω(mn).
2. Обозначим через c_i стоимость i-ого поискового запроса с применением эвристики перемещения в начало, которая включает стоимость поиска элемента в списке и стоимость его перемещения в начало списка путём ряда обменов соседних элементов списка. Покажите, что i-ая операция поиска находит элемент x в списке L с применением эвристики перемещения в начало, то c_i = 2 * rank_L(x) - 1.
3. Покажите, что c_i = 2 * rank_Li-1(x) - 1.
4. Покажите, что c*_i = rank_L*i-1(x) + t_i.
5. Докажите, что после одного обмена двух соседних элементов потенциал либо увеличивается на 2, либо уменьшается на 2.
6. Докажите, что rank_Li-1(x) = |A| + |B| + 1.
7. Докажите, что rank_L*i-1(x) = |A| + |С| + 1.
8. Покажите, что поиск i-ого элемента приводит к изменению потенциала Ф(L_i) - Ф(L_i-1) <= 2 (|A| - |B| + t*_i), где t*_i --- это количество обменов при i-ом поиске.
9. Во сколько раз стоимость С_MFT(S) превышает C_OPT(S)?

(18.05) Конечные автоматы

Задание 19 (до 25.05)

1. Постройте автомат для языка над алфавитом Σ = {0, 1} каждое слово которого содержит хотя бы два нуля. Является ли он детерминированным?
2. Постройте автомат над алфавитом Σ = {0, 1}, который допускает слова в которых число единиц делится на 5. Является ли он детерминированным?
3. Постройте автомат, который допускает пустой язык (язык в котором нет ни одного слова).
4. Постройте автомат, который допускает все слова над алфавитом Σ.
5. Постройте ДКА над алфавитом Σ = {К, Ж, З}, который допускает слова в которых после К идёт З, после З --- Ж, после Ж --- К.
6. * Постройте ДКА над алфавитом Σ = {0, 1}, который допускает слова в которых число единиц делится на 5, а число нулей на 3.
7. Постройте НКА для языка над алфавитом Σ = {0, 1, 2, 3}, состоящий из слов, в которых хотя бы одна из последних пяти букв является 1.
8. Постройте НКА над алфавитом Σ = {0, 1}, который допускает слова в которых число единиц делится на 5, а число нулей на 3.
9. Какие языки допускают автоматы https://yadi.sk/d/fNAHbjCZghERG?
10. Для каждого из автоматов https://yadi.sk/d/fNAHbjCZghERG постройте соответствующий ему ДКА.

(21.05) Регулярные выражения, КА, их эквивалентность. Лемма о накачке

Задание 20 (до 28.05)

I Написать регулярные выражения

1. Напишите регулярное выражение для языка над алфавитом Σ = {0, 1} каждое слово которого содержит хотя бы два нуля.
2. Напишите регулярное выражение над алфавитом Σ = {0, 1}, который допускает слова в которых число единиц делится на 5.
3. Напишите регулярное выражение, которое допускает пустой язык (язык в котором нет ни одного слова).
4. Напишите регулярное выражение, которое допускает все слова над алфавитом Σ.
5. Напишите регулярное выражение для языка над алфавитом Σ = {0, 1, 2, 3}, состоящий из слов, в которых хотя бы одна из последних пяти букв является 1.

II КА и регулярные выражения

1. Постройте конечный автомат для языка (111 U 01)^*1(00 U 11)^*.
2. Постройте конечный автомат для языка (ab)^*(a U b)(b U a)^*(a U bab).

III Доказать замкнутость относительно различных операций

1. Покажите, что если для языков L₁ и L₂ существует КА, который их читает, то существует КА и для их объединения L = {w | w ∈ L₁ или w ∈ L₂}.
2. Покажите, что если для языка L₁ и L₂ существует КА, который их читает, то существует КА и для языка L₁ L₂ = {xy | x ∈ L₁, y ∈ L₂}.
3. Покажите, что если для языка L существует КА, который его читает, то существует КА и для замыкания Клини L* = {w₁ w₂ ... w_k| w₁ ∈ L, w₂ ∈ L, ..., w_k ∈ L}.
4. Покажите, что если язык L регулярен, то регулярно его дополнение (т.е. язык над тем же алфавитом, которому принадлежит слово тогда и только тогда, когда оно НЕ принадлежит L) .
5. Покажите, что если язык L регулярен, то регулярно его обращение L_R = {a₁ . . . a_k | a_k . . . a₁ ∈ L}. (L_R --- это язык в котором все слова языка L записаны наоборот.)
6. * Покажите, что если языки L₁ и L₂ регулярны, то регулярно их пересечение.

IV Использование леммы о накачке (см. конспект)

1. Докажите, что не существует КА, который бы читал язык {0ⁿ1ⁿ2ⁿ}. (Пояснение: запись 0ⁿ означает строку из n нулей: 00...0.)
2. Докажите, что не существует КА, который бы читал язык {0ⁿ1ⁿ}.
3. Докажите, что не существует КА, который бы читал язык {0^n!}.

(25.05) Автоматный подход

Задание 21 (до 01.06)

Реализуйте один из следующих проектов:

1. Программа, которая считывает строку и говорит принадлежит ли она языку 0(123)*(00 U (231)*) U 111.
2. Программа, которая считывает КА и генерирует программу на языке С++, которая говорит принадлежит ли заданное слово языку, описываемому этим КА.
3. Программа, которая считывает регулярное выражение и строку и говорит принадлежит ли слово языку, описываемому этим регулярным выражением.
4. Программа, которая моделирует работу банкомата, автомата с газировкой, лифта... (что-то одно на выбор)
5. Текстовый симулятор студента. Возможные состояния: на паре, дома, есть приглашение прогулять, завтра коллоквиум, сплю и др. Есть два параметра: успеваемость и весёлось. Если хотя бы один из них упадёт ниже критической отметки, студент умрёт. Игрок принимает решение куда идти студенту. Цель: продержаться как можно дольше.

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

Контест. В домашнем задании четыре задачи. Обязательны первые три. Вместо одной из первых трёх можно сделать последнюю (только для первых 10 решивших 4-ую!). На выполнение задания даётся примерно 2 недели (см. точное время окончания в контесте). Условия ревью определяют семинаристы.

(01.06) P vs NP

План занятия

1. Напоминание: P; NP; проблема P ?= NP; NPC; сведения; пример сведений.

Задание 22 (до 8.06)

1. Задачи о гамильтоновом цикле и о гамильтоновом пути.

 Задачи о гамильтоновом цикле:
 Дан граф. Необходимо найти цикл, проходящий через каждую вершину по одному разу.

 Задачи о гамильтоновом пути:
 Дан граф и две его вершины s и t. Необходимо найти путь из s в t, проходящий через каждую вершину по одному разу.

Покажите, что задача поиске гамильтонова цикл сводится к задаче поиска гамильтонова пути. Из этого будет следовать, что искать цикл не проще, чем искать путь.

2. Задачи поиска и задачи оптимизации. Для задачи коммивояжёра варианты с поиском и оптимизацией выглядят так:

 Задача поиска:
 Вход: матрица расстояний, бюджет b
 Выход: цикл веса не более b, проходящий по всем вершинам графа, если такой есть.

 Оптимизационная задача:
 Вход: матрица расстояний
 Выход: цикл минимального веса, проходящий по всем вершинам графа, если такой есть.

Покажите, что если поисковую задачу коммивояжёра можно решить за полиномиальное время, то и оптимизационный вариант можно решить за полиномиальное время.

3. Задача поиска и задача разрешения. Пусть имеется программа, которая за полиномиальное время отвечает на вопрос , содержит л входной граф гамильтонов цикл. Как с её помощью найти за полиномиальное время сам цикл (есть он есть)?

4. Сведите задачу поиска гамильтонова цикла к задаче коммивояжёра.

5. Для задач ниже или приведите алгоритм, работающий за полиномиальное время, или сведите их к NP-полной задаче:

1. Поиск самого длинного пути
2. Поиск кратчайшего пути
3. Двудольное паросочетание
4. Трёхдольное паросочетание
5. Четырёхдольное паросочетание