Алгоритмы и структуры данных. Подгруппа 105-1
Материал из Wiki - Факультет компьютерных наук
Версия от 17:08, 23 января 2015; Kassalanche (обсуждение | вклад)
Содержание
О курсе
План лекций и список рекомендуемой литературы.
Оценивание домашних работ
- Все задания предполагаются индивидуальными. Запрещены любые заимствования без ссылки на автора.
- Решения после установленного дедлайна не принимаются. Дедлайн указан в заголовке каждого задания.
- Везде, где требуется написать алгоритм, можно использовать любой язык программирования или псевдокод.
- Там, где требуется построить алгоритм с заданной асимптотикой, приведите обоснование, что полученный алгоритм удовлетворяет этому условию.
- Эти правила не действуют, если в задании явно оговорено иное.
(12.01) Мотивация к изучению алгоритмов. Подсчёт числа операций
План занятия
- Числа Фибоначчи. Определение. Примитивный рекурсивный алгоритм вычисления i-ого числа. Оценка числа операций. Анализ причин неэффективности. Алгоритм с запоминанием вычисленных ранее значений. Оценка числа операций. Сравнение с предыдущим. (подробнее: глава 0, страницы 8-10 из книги <<Алгоритмы>>, см. список рекомендованной литературы)
- Задача о ханойской башне. Постановка задачи. Рекурсивный алгоритм. Рекуррентная формула для числа перемещений. Замкнутая формула для числа перемещений (+ доказательство). Доказательство того, что эту задачу нельзя решить используя меньшее число перемещений дисков. (Разбор задачи о ханойской башне, автор Сергей Объедков)
- Сортировка пузырьком. Алгоритм. Подсчёт количество операций сравнения и обмена (swap). Анализ наилучшего и наихудшего случаев (Википедия)
Домашнее задание (12.01 - 26.01)
- Для получения максимального балла требуется решить или все задачи без звёздочек, или все задачи со звёздочками.
Во всех задачах, если не оговорено иного, предполагаем, что работаем с целыми неотрицательными числами. Для первых 7 задач необходимо
- описать что можно считать наилучшим и наихудшим случаями,
- для каждого из двух случаев подсчитать отдельно количество операций сравнения и swap (если есть).
Задачи
- Даны три числа, требуется вернуть наименьшее.
- Даны три числа, требуется отсортировать их.
- Дана последовательность A из n элементов и число x, требуется найти элемент равный x. Примечание: если таких значений i несколько, вернуть любое; если такого элемента нет, функция должна сообщить об этом.
- * Дана упорядоченная последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Алгоритм должен быть эффективней, чем в предыдущем пункте и использовать то, что последовательность упорядочена.
- Дана последовательность из 100 000 чисел от 0 до 100. Напишите эффективный алгоритм сортировки, который бы учитывал специфику входных данных.
- * Дано 32 битное неотрицательное число. Требуется номер первого ненулевого бит. Разрешается использовать операцию обращения к i-тому биту. В дополнение к заданиям в преамбуле укажите математическое ожидание количества операций сравнения, считая, что числа распределены равномерно.
- * Даны 32 битные неотрицательные числа m и n. Требуется вывести True, если m < n, иначе False. Разрешается использовать операцию обращения к i-тому биту. В дополнение к заданиям в преамбуле укажите математическое ожидание количества операций сравнения битов, считая, что числа распределены равномерно.
- Напишите рекурсивную функцию, вычисляющую n-ое число Фибоначчи (как на занятии). Подсчитайте количество рекурсивных вызовов.
- * Напишите функцию, вычисляющую n-ое число Фибоначчи, у которой число операций — полином от n, и которая использует количество памяти, независящее от n.
(15.01) O-символика и стратегия "разделяй и властвуй"
План занятия
- Сортировка слиянием. Алгоритм, рекуррентное соотношение для времени сортировки, сложность. Подробнее: §2.3 Сортировка слиянием.
- О-символика. §0.3 О-символика.
- Задача о слиянии m упорядоченных массивов по n элементов. Три алгоритма решения: последовательное слияние, слияние "деревом" (обе функции используют Merge из MergeSort), аналог Merge для m массивов. Анализ сложности каждого из них.
Домашнее задание (15.01-29.01)
- Для получения максимального балла требуется решить или все задачи без звёздочек, или все задачи со звёздочками.
- Во всех задачах, если не оговорено иного, для простоты можно считать, что n является степенью какого-либо числа, например, степенью двойки.
Задачи
- Дана функция F, определённая ниже. Сколько строк она напечатает? Указание: для обоих подпунктов рассмотрите два случая: 1. n является степенью двойки, 2. n не является степенью двойки.
- Запишите рекуррентное соотношение для числа строк.
- Решите уравнение, полученное в предыдущем пункте, то есть, выведите замкнутую (нерекуррентную формулу). Для простоты можно считать, что n является степенью двойки.
- В массиве A размера n записана возрастающая последовательность целых чисел. Постройте алгоритм типа "разделяй и властвуй", который проверяет, существует ли такой индекс i, что A[i] = i
- за время O(n),
- * за время O(log n).
- Какие случаи для вашего алгоритма являются наихудшими и наилучшими? Какого время работы в лучшем и худшем случаях?
- Дан бесконечный массив A, первые n элементов которого содержат возрастающую последовательность положительных чисел, а дальше стоят -1. Значение n не дано. Постройте алгоритм, который получает на вход целое число x и находит это x в массиве --- или говорит, что там его нет,
- за время O(n),
- за время O(log n).
- Рассмотрим алгоритм вычисления наибольшего общего делителя (НОД) двух положительных чисел, основанный на методе "разделяй и властвуй".
- (задание не оценивается) Прочитайте параграф 1.2.3 Алгоритм Евклида.
- * Докажите, что определение НОД-а, приведённое ниже, корректно.
- Постройте алгоритм, основанный на этом определении.
- Какой алгоритм будет быстрее для n-битовых чисел a и b при больших значениях n --- ваш или алгоритм Евклида?
- * Покажите как за время O(n log n) удалить из массива размера n все дубликаты, то есть оставить каждый элемент в одном экземпляре.
- * Даны два упорядоченных массива размера 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.1.2 Умножение*)
- Рекурсивный алгоритм умножения и его сложность (§1.1.2 Умножение*)
- Алгоритм умножения, реализующий стратегию "разделяй и властвуй", анализ сложности (§2.1 Умножение чисел*)
* Читать.
Домашнее задание (19.01 - 2.02)
- Во всех задачах для простоты можно считать, что n является степенью какого-либо числа.
Задачи
- Найдите произведение чисел 10011011 и 10111010 (в двоичной системе счисления), используя алгоритм умножения чисел, основанный на методе «разделяй и властвуй». Необходимо не только дать ответ, но и привести ход решения.
- Алгоритм, решая задачу размера n, производит 3 рекурсивных вызова для подзадач размера n-1 и комбинирует из них решение исходной задачи за О(n).
- Напишите рекуррентную формулу, описывающую количество операций.
- Нарисуйте три верхних уровня дерева вызовов.
- Сколько всего будет уровней?
- Сколько подзадач на i-ом уровне?
- Какой размер каждой подзадачи на i-ом уровне?
- Какова сложность работы алгоритма?
- Алгоритм, решая задачу размера n, производит 10 рекурсивных вызовов для подзадач размера n/2 и комбинирует из них решение исходной задачи за О(5n).
- Напишите рекуррентную формулу, описывающую количество операций.
- Нарисуйте два верхних уровня дерева вызовов.
- Сколько всего будет уровней?
- Сколько подзадач на i-ом уровне?
- Какой размер каждой подзадачи на i-ом уровне?
- Какова сложность работы алгоритма?
- Докажите, что 3m² + m = O(m²).
- Докажите, что lg m = O(m/1000), где lg m — это логарифм с двоичным основанием.
- Докажите, что из равенства f(n) = O(g(n)) не следует, что g(n) = O(f(n)).
- Докажите, что O(m) содержится в O(m²).
(22.01) Решение рекуррентных уравнений
План занятия
- Примеры решений рекуррентных уравнений (см. конспект в плане лекций).
Домашнее задание (23.01 - 6.02)
- Нельзя использовать утверждение основной теоремы о решении рекуррентных соотношений.
- Можно использовать метод построения дерева рекурсии или подстановку (метод с угадыванием ответа).
Задачи
- Какой из трёх приведённых ниже алгоритмов вы бы предпочли? Обоснуйте свой ответ.
- Алгоритм A, решая задачу, производит пять рекурсивных вызовов для подзадач вдвое меньшего размера, после чего строит ответ для исходной задачи за линейное время.
- Алгоритм B, решая задачу размера n, делает два рекурсивных вызова для задач размера n − 1, после чего находит ответ за время O(1).
- Алгоритм C, решая задачу размера n, рекурсивно решает девять задач размера n/3 и строит ответ за время O(n2).
- Найдите T(n) в замкнутой форме для любых 7 из 10 приведённых ниже рекуррентных соотношений:
- T(n) ≤ 2T(n/3) + 1;
- T(n) ≤ 7T(n/7) + n;
- T(n) ≤ 9T(n/3) + n2;
- T(n) ≤ 8T(n/2) + n3;
- T(n) ≤ 49T(n/25) + n3/2log n;
- T(n) ≤ T(n − 1) + 2;
- T(n) ≤ T(n − 1) + nc, где c ≥ 1 –– константа;
- T(n) ≤ T(n − 1) + cn, где c > 1 –– константа;
- T(n) ≤ 2T(n − 1) + 1;
- T(n) ≤ T(sqrt(n)) + 1