Алгоритмы и структуры данных. Подгруппа 105-1 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(→Домашнее задание (15.01-29.01)) |
|||
Строка 32: | Строка 32: | ||
===Домашнее задание (15.01-29.01)=== | ===Домашнее задание (15.01-29.01)=== | ||
− | # | + | Везде, где требуется написать алгоритм, можно использовать любой язык программирования или псевдокод. |
− | # | + | |
− | # | + | ====Задачи==== |
+ | # Сколько строк напечатает программа? Запишите рекуррентное соотношение и решите его, то есть, выведите замкнутую (нерекуррентную формулу). Можно считать, что n является степенью двойки. | ||
+ | Функция F(n) | ||
+ | если n > 1: | ||
+ | напечатать "всё ещё работаю" | ||
+ | F(n/2) | ||
+ | F(n/2) | ||
+ | # В массиве A размера n записана возрастающая последовательность целых чисел. Постройте алгоритм типа "разделяй и властвуй", который проверяет, существует ли такой индекс i, что A[i] = i | ||
+ | #* за время O(n), | ||
+ | #* * за время O(log n), | ||
+ | #* какие случаи для вашего алгоритма являются наихудшими и наилучшими? Какого время работы в лучшем и худшем случаях? | ||
+ | # Дан бесконечный массив A, первые n элементов которого содержат возрастающую последовательность положительных чисел, а дальше стоит -1. Значение n не дано. Постройте алгоритм, который получает на вход целое число x и находит это x в массиве --- или говорит, что там его нет, за время O(log n). | ||
+ | # Рассмотрим алгоритм вычисления наибольшего общего делителя (НОД) двух положительных чисел, основанный на методе "разделяй и властвуй". (Перед выполнением рекомендуется прочитать "Алгоритмы", параграф 1.2.3 Алгоритм Евклида) | ||
+ | #* * Докажите, что<source lang="cpp">2НОД(a/2, b/2), если а и b чётны,\nНОД(a,b) = 2НОД(a, b/2), если а нечётно, b чётно, | ||
+ | НОД((a-b)/2, b), если а и b нечётны,</source> | ||
+ | #* Посторойте алгоритм, основанный на этом соотношении. | ||
+ | # Какой алгоритм будет быстрее для n-битовых чисел a и b при больших значениях n --- ваш или алгоритм Евклида? | ||
+ | |||
+ | Задачи взяты из книги "Алгоритмы", глава 2 | ||
==(19.01) Анализ рекуррентных соотношений== | ==(19.01) Анализ рекуррентных соотношений== | ||
===План занятия=== | ===План занятия=== |
Версия 23:48, 15 января 2015
Содержание
Оценивание
В каждом домашнем задании для получения максимального балла требуется решить или все задачи без звёздочек, или все задачи со звёздочками. Решения после установленного дедлайна не принимаются.
(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) Сложность алгоритмов и стратегия "разделяй и властвуй"
План занятия
- Сортировка слиянием. Алгоритм, рекуррентное соотношение для времени сортировки, сложность. (подробнее: <<Алгоритмы>>, параграф 2.3, стр. 54, см. список рекомендованной литературы)
- Понятие сложности алгоритма.
- Задача о слиянии m упорядоченных массивов по n элементов. Три алгоритма решения: последовательное слияние, слияние "деревом" (обе функции используют Merge из MergeSort), аналог Merge для m массивов. Анализ сложности каждого из них.
Домашнее задание (15.01-29.01)
Везде, где требуется написать алгоритм, можно использовать любой язык программирования или псевдокод.
Задачи
- Сколько строк напечатает программа? Запишите рекуррентное соотношение и решите его, то есть, выведите замкнутую (нерекуррентную формулу). Можно считать, что n является степенью двойки.
Функция F(n) если n > 1: напечатать "всё ещё работаю" F(n/2) F(n/2)
- В массиве A размера n записана возрастающая последовательность целых чисел. Постройте алгоритм типа "разделяй и властвуй", который проверяет, существует ли такой индекс i, что A[i] = i
- за время O(n),
- * за время O(log n),
- какие случаи для вашего алгоритма являются наихудшими и наилучшими? Какого время работы в лучшем и худшем случаях?
- Дан бесконечный массив A, первые n элементов которого содержат возрастающую последовательность положительных чисел, а дальше стоит -1. Значение n не дано. Постройте алгоритм, который получает на вход целое число x и находит это x в массиве --- или говорит, что там его нет, за время O(log n).
- Рассмотрим алгоритм вычисления наибольшего общего делителя (НОД) двух положительных чисел, основанный на методе "разделяй и властвуй". (Перед выполнением рекомендуется прочитать "Алгоритмы", параграф 1.2.3 Алгоритм Евклида)
- * Докажите, что
2НОД(a/2, b/2), если а и b чётны,\nНОД(a,b) = 2НОД(a, b/2), если а нечётно, b чётно, НОД((a-b)/2, b), если а и b нечётны,
- Посторойте алгоритм, основанный на этом соотношении.
- Какой алгоритм будет быстрее для n-битовых чисел a и b при больших значениях n --- ваш или алгоритм Евклида?
Задачи взяты из книги "Алгоритмы", глава 2
(19.01) Анализ рекуррентных соотношений
План занятия
- * Докажите, что