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

Оценивание

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

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

План занятия

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

Домашнее задание (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.

(15.01) Сложность алгоритмов и стратегия "разделяй и властвуй"

План занятия

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

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

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

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

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

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

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

Везде, где требуется построить алгоритм, работающий за O(f(n)), приведите обоснование того, что ваш алгоритм работает за указанное время.

Задачи

1. Дана функция F, определённая выше. Сколько строк она напечатает?
   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 в массиве --- или говорит, что там его нет, за время O(log n).
4. Рассмотрим алгоритм вычисления наибольшего общего делителя (НОД) двух положительных чисел, основанный на методе "разделяй и властвуй".
   1. (не оценивается) Прочитайте параграф 1.2.3 Алгоритм Евклида).
   2. * Докажите, что определение НОД-а, приведённое выше, корректно.
   3. Постройте алгоритм, основанный на этом соотношении.
   4. Какой алгоритм будет быстрее для n-битовых чисел a и b при больших значениях n --- ваш или алгоритм Евклида?
5. * Покажите как за время O(n log n) удалить из массива размера n все дубликаты, то есть оставить каждый элемент в одном экземпляре.
6. * Даны два упорядоченных массива размера m и n. Постройте алгоритм, находящий k-й по величине элемент в объединении этих массивов за время O(log(n+m)).

Задачи взяты из книги "Алгоритмы", глава 2