Алгоритмы и структуры данных. Подгруппа 105-1
Содержание
- 1 О курсе
- 2 Итоговая оценка за курс
- 3 Оценивание домашних работ
- 4 Мотивация к изучению алгоритмов. Подсчёт числа операций (12.01)
- 5 O-символика и стратегия "разделяй и властвуй" (15.01)
- 6 Сложение и умножение (19.01)
- 7 Решение рекуррентных уравнений (22.01)
- 8 Большое домашнее задание №1
- 9 Бинарное дерево поиска (26.01)
- 10 Алгоритм Карацубы, Штрассена. Быстрая сортировка (29.01)
- 11 Динамическое программирование (ДП). Первые примеры (02.01)
- 12 ДП. Задача о разрезании стержня (05.01)
- 13 ДП. Перемножение цепочки матриц. Оптимальное бинарное дерево поиска (начало) (09.02)
- 14 ДП. Расстановка пробелов. Оптимальное бинарное дерево поиска (середина) (12.02)
- 15 Способы представления графов в памяти (16.02)
- 16 Реализация поиска в глубину (19.02)
- 17 Большое домашнее задание №2
О курсе
План лекций и список рекомендуемой литературы.
Итоговая оценка за курс
Итоговая оценка (ИО) зависит от
- оценок за пять больших домашних заданий (БДЗ1, БДЗ2, ..., БДЗ5),
- оценок за домашние задания (ДЗ1, ДЗ2, ...),
- оценки за контрольную работу (КР),
- оценки за экзамен (ЭКЗ),
и может быть вычислена по формуле:
ИО = 0.7 * (0.3 * КР + 0.7 *(ИДЗ1 + ИДЗ2 + ИДЗ3 + ИДЗ4 + ИДЗ5)/5) + 0.3 * ЭКЗ = = 0.21*КР + 0.98*ИДЗ1 + 0.98*ИДЗ2 + 0.98*ИДЗ3 + 0.98*ИДЗ4 + 0.98*ИДЗ5 + 0.3*ЭКЗ,
где
ИДЗi = min (10, 0.7 * БДЗi + 0.4 * <cредняя оценка за ДЗj, прошедшие с предыдущего БДЗ по i-ое>)
Оценивание домашних работ
- Все задания предполагаются индивидуальными. Запрещены любые заимствования без ссылки на автора.
- Решения после установленного дедлайна не принимаются. Дедлайн указан в заголовке каждого задания.
- Везде, где требуется написать алгоритм, можно использовать любой язык программирования или псевдокод.
- Там, где требуется построить алгоритм с заданной асимптотикой, приведите обоснование, что полученный алгоритм удовлетворяет этому условию.
- Эти правила не действуют, если в задании явно оговорено иное.
Мотивация к изучению алгоритмов. Подсчёт числа операций (12.01)
План занятия
- Числа Фибоначчи. Определение. Примитивный рекурсивный алгоритм вычисления i-ого числа. Оценка числа операций. Анализ причин неэффективности. Алгоритм с запоминанием вычисленных ранее значений. Оценка числа операций. Сравнение с предыдущим. (подробнее: глава 0, страницы 8-10 из книги <<Алгоритмы>>, см. список рекомендованной литературы)
- Задача о ханойской башне. Постановка задачи. Рекурсивный алгоритм. Рекуррентная формула для числа перемещений. Замкнутая формула для числа перемещений (+ доказательство). Доказательство того, что эту задачу нельзя решить используя меньшее число перемещений дисков. (Разбор задачи о ханойской башне, автор Сергей Объедков)
- Сортировка пузырьком. Алгоритм. Подсчёт количество операций сравнения и обмена (swap). Анализ наилучшего и наихудшего случаев (Википедия)
Домашнее задание 1 (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.
O-символика и стратегия "разделяй и властвуй" (15.01)
План занятия
- Сортировка слиянием. Алгоритм, рекуррентное соотношение для времени сортировки, сложность. Подробнее: §2.3 Сортировка слиянием (стр. 54).
- О-символика. §0.3 О-символика (стр. 10).
- Задача о слиянии m упорядоченных массивов по n элементов. Три алгоритма решения: последовательное слияние, слияние "деревом" (обе функции используют Merge из MergeSort), аналог Merge для m массивов. Анализ сложности каждого из них.
Домашнее задание 2 (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 Алгоритм Евклида (стр. 23).
- * Докажите, что определение НОД-а, приведённое ниже, корректно.
- Постройте алгоритм, основанный на этом определении.
- Какой алгоритм будет быстрее для 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 Умножение чисел*)
* Читать.
Домашнее задание 3 (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)
План занятия
- Примеры решений рекуррентных уравнений (см. конспект).
Домашнее задание 4 (до 14.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.
Большое домашнее задание №1
Необходимо реализовать все 6 задач из контеста. Каждую задачу можно писать на С++ или Python. На выполнение работы отводится две недели. Каждая задача оценивается в 10/6 балла. Оценка может быть снижена за плохой код, но не более чем на 25%.
Бинарное дерево поиска (26.01)
План занятия
- Определение. Пример.
- Не модифицирующие алгоритмы: поиск (рекурсивный и итеративный алгоритмы), поиск минимума, inordered обход (вывод значений узлов в отсортированном порядке), поиск следующего по возрастанию.
- Модифицирующие алгоритмы: вставка (рекурсивная реализация), удаление (только идея).
Читать Кормена и др., глава 13, стр. 248
Домашнее задание 5 (до 16.02)
- Для получения максимальной оценки можно выполнить или все задачи без звёздочки, или задачу со звёздочкой. Преподаватель понимает, что реализацию БДП сложно не найти в интернете, но от копипасты не будет никакой пользы. Напротив, самостоятельная реализация очень полезна и приветствуется, даже если не получится выполнить всех пунктов задания.
- Задачи с двумя звёздочками необязательны.
Задачи
- Нарисуйте бинарные деревья поиска высотой 2, 3, 4, 5 и 6 для множества ключей {1, 4, 5, 10, 16, 17, 21}. Корень дерева имеет высоту 0.
- Сортировка с использованием БДП.
- Какова асимптотическая сложность алгоритма вставки элемента в дерево высоты d? Почему? Назовите наилучший и наиухдший случаи.
- Дана последовательность из n чисел. Напишите алгоритм, который строит БДП в узлах которого стоят элементы данной последовательности. Можно использовать функцию Insert. Назовите наилучший и наихудший случаи. Есть теорема о том, что полученный алгоритм будет работать в среднем случае за время O(n * log n).
- Дана последовательность из n чисел. Напишите алгоритм, который выводит их в порядке возрастания. Используйте бинарное дерево поиска. Какова в среднем случае сложность этого алгоритма? Назовите наилучший и наихудший случаи. Какова сложность в наихудшем случае?
- Напишите функцию GetRoot, которой на вход подаётся указатель на произвольный узел дерева, а она возвращает указатель на корень.
- Напишите процедуру PrintLeafs, которой на вход подаётся указатель на корень дерева, и она печатает листья дерева
- по возрастанию,
- по убыванию.
- ** Альтернативный обход в порядке возрастания бинарного дерева поиска с n узлами (или центрированный (inordered) обход) можно осуществить путём поиска минимального элемента дерева с помощью функции Minimum с последующий n-1 вызовом функции Next. Каково время работы такого алгоритма?
- * Реализуйте на С++ структуру данных бинарное дерево поиска, используя заготовку.
- Нарисуйте бинарное дерево поиска, которое строится в функции getTreeExample.
- Реализуйте следующие алгоритмы:
- поиск минимума,
- inordered обход (вывод значений узлов в отсортированном порядке),
- поиск следующего по возрастанию,
- вставка элемента в дерево,
- сортировка последовательности с использованием БДП (дан вектор чисел, необходимо вывести их по возрастанию),
- ** удаление.
Алгоритм Карацубы, Штрассена. Быстрая сортировка (29.01)
План занятия
- Алгоритм Карацубы.
- Алгоритм Штрассена. Читать Дасгупту и др., §2.5 Умножение матриц
- Быстрая сортировка и доказательство того, что в среднем случае она работает за О(n * log n). Читать Кормена и др., глава 8 Быстрая сортировка, стр. 148
Домашнее задание 6 (до 18.02)
Задачи
- Пусть мы хотим найти двоичное представление десятичного числа 10n. Будем считать, что n --- степень двойки (n = 2k).
Pwr2Bin(n): если n == 1: вернуть 1010 z = ... вернуть Multiply(z, z)
Multiply --- функция, перемножающая два n-битовых двоичных числа x и y по алгоритму Карацубы за O(nlog23).
- Впишите недостающую строку псевдокода.
- Запишите рекуррентное соотношение на время работы и решите его.
-
Пусть мы хотим перевести произвольное десятичное число x в записи которого n=2k чисел в двоичную систему счисления.
Dec2Bin(n): если n == 1: вернуть binary[x] разделить x на два десятичных числа xl и xr из n/2 цифр. вернуть ...
Здесь binary --- это массив, содержащий двоичное представление десятичных цифр.
- Впишите недостающую строку псевдокода.
- Запишите рекуррентное соотношение на время работы и решите его.
- Докажите, что математическое ожидание времени работы алгоритма быстрой сортировки (усреднение по всем вариантам выбора опорного элемента) на любом входе размера n удовлетворяет соотношению: T(n) ≤ O(n) + 1/n * Σni=1 (T(i-1) + T(n-i)).
- Найдите решение соотношения из предыдущего пункта.
Динамическое программирование (ДП). Первые примеры (02.01)
План занятия
- Нахождение самой длинной возрастающей подпоследовательности.
- Нахождение редакционного расстояния (или редакционной стоимости, расстояния Левенштейна).
- Нахождение представителя большинства.
Домашнее задание 7 (до 20.02)
- В этом задании везде, где требуется реализовать алгоритм, необходимо привести код на любом языке программирования.
- Для получения максимальной оценки нужно решить все задачи без звёздочек. Одна решённая задача со звёздочкой заменяет одну задачу без звёздочки.
Задачи
- Реализуйте алгоритм нахождения редакционного расстояния (алгоритм Вагнера — Фишера). Например, редакционное расстояние между словами "anthropology" и "anthologies" равно 6.
- Реализуйте алгоритм нахождения длины наибольшей общей подстроки. Например, длина наибольшей общей подстроки "anthropology" и "anthologies" равна 8 ("antholog"). Чем больше это значение, тем схожей строки.
- Предположим теперь, что сравниваемые строки состоят из символов 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.
Напишите алгоритм, который находит максимальную стоимость всех возможных выравниваний. Верно ли, что чем больше это значение, тем непохожей строки?
- Как давно один народ отделился от другого? Кто похожей — итальянец и китаец или якут и эфиоп? На эти вопросы можно отвечать с разных точек зрения — культурной, исторической, лингвистической, ... В последние же годы человечество научилось секвенировать геном, что позволило исследовать этот вопрос с точки зрения генетики. Секвенирование генома — это процесс записи ДНК в виде нуклеотидной последовательности, которая представляет собой последовательность из четырёх символов — A, С, G и T. Существуют базы, которые хранят генетическую информацию о людях из разных стран и континентов, например, http://www.mtdb.igp.uu.se/ → Download mtDNA sequences. Чем больше сходство между геномами, тем сильнее родственные связи между их обладателями. Используя решение предыдущего пункта, выполните задания:
- Определите, кто похожей — итальянец и китаец или якут и эфиоп?
- Найдите нескольких похожих и нескольких непохожих народностей.
- * Выберите одну народность. Найдите самых похожих и самых непохожих на неё.
- * Найдите самые похожие и самые непохожие народности.
ДП. Задача о разрезании стержня (05.01)
План занятия
- Постановка задачи.
- Решение с нахождением максимума по ri + rn-i. Алгоритм. Дерево рекурсивных вызовов. Оценка сложности.
- Решение с нахождением максимума по pi + rn-i. Алгоритм. Дерево рекурсивных вызовов. Оценка сложности.
- Восходящий алгоритм с запоминанием. Вывод длин кусочков стержня. Оценка сложности.
- Нисходящий алгоритм с запоминанием. Оценка сложности.
Читать Кормена и др., 3-е изд., §15.1 Разрезание стержня, стр. 393
Домашнее задание 8 (до 22.02)
- Решая задачу о разрезании стержня мы вначале построили рекурсивное решение с нахождением максимума по ri + rn-i для всех 1 ≤ i < n. Его сложность описывалась рекуррентной формулой T(n) = n + Σn-1i=1(T(i) + T(n-i)), T(1) = 1.
- Объясните эту формулу.
- Покажите с помощью метода подстановок, что T(n) ≤ 2n.
- Покажите с помощью контрпримера, что описанная далее жадная стратегия не всегда определяет оптимальный способ разрезания стержня. Определим плотность стержня длиной i как pi/i, то есть как стоимость единицы его длины. Жадная стратегия для стержня длиной n отрезает от стержня первую часть длиной i, где 1 ≤ i ≤ n, имеющую максимальную плотность. Затем та же жадная стратегия применяется к оставшейся части длиной n-i.
- Рассмотрим модификацию задачи разрезания стержня, в которой в дополнение к цене pi каждого стержня добавляется фиксированная цена разреза c. Теперь прибыль, связанная с решением, представляет собой сумму цен частей стержня минус стоимость разрезов. Разработайте алгоритм динамического программирования для этой модифицированной задачи.
- Непрерывным участком называется группа подряд идущих элементов. Например, для последовательности
5, 15, −30, 10, −5, 40, 10
элементы 15, −30, 10 образуют непрерывный участок, а 5, 15, 40 -- нет. Постройте линейный алгоритм для следующей задачи:
Вход: список чисел a1, a2, ... , an. Выход: непрерывный участок с максимальной суммой (сумма участка нулевой длины равна нулю).
Для приведённого примера ответом будет 10, −5, 40, 10 с суммой 55. Какова сложность алгоритма? Почему?
- Надо заплатить v рублей, имея купюры в x1, x2, ..., xn рублей (купюр каждого типа сколько угодно). Это не всегда возможно (скажем, купюрами в 10 и 25 рублей можно заплатить 45 рублей, но не 47 и не 15). Постройте основанный на методе динамического программирования алгоритм со временем работы O(nv), выясняющий, возможна ли уплата.
- Как решить предыдущую задачу, если каждая купюра имеется в единственном экземпляре? (Например, купюрами в 1, 5, 10, 20 рублей можно заплатить 16 = 1 + 5 + 10 и 31 = 1 + 10 + 20 рублей, но не 40 (не хватит денег). Время работы алгоритма по-прежнему O(nv).
- Ещё один вариант той же задачи: купюр каждого типа сколько угодно, но всего разрешается использовать не более k купюр. (Например, если есть купюры в 5 и 10 рублей, а k = 6, то 55 разменять можно, а 65 –– нет).
ДП. Перемножение цепочки матриц. Оптимальное бинарное дерево поиска (начало) (09.02)
План занятия
- Задача о перемножении цепочки матриц. Постановка задачи.Пример. Нисходящий алгоритм. Читать Кормена и др., 3-е изд., §15.2 Перемножение цепочки матриц, стр. 403
- Построение оптимального дерева поиска. Постановка задачи. Читать Кормена и др., 3-е изд., §15.5 Оптимальные бинарные деревья поиска, стр. 431
Домашнее задание 9 (до 24.02)
- Найдите оптимальную расстановку скобок в произведении последовательности матриц, размерности которых равны 5×10, 10×3, 3×12, 12×5, 5×50, 50×6.
- Напишите восходящий алгоритм для поиска оптимальной расстановки скобок.
ДП. Расстановка пробелов. Оптимальное бинарное дерево поиска (середина) (12.02)
План занятия
- Задача о расстановке пробелов. Постановка задачи. Решения для трёх случаев: 1. нужно вернуть можно ли разбить текст на слова; 2. вернуть разбивку на слова; 3. слова встречаются не равновероятно, вернуть наиболее вероятную разбивку на слова.
- Построение оптимального дерева поиска. Постановка задачи. Вывод математического ожидания времени поиска. Читать Кормена и др., 3-е изд., §15.5 Оптимальные бинарные деревья поиска, стр. 431
Праздничное домашнее задание 10 (до 02.03)
- ["♥♥♥♡", "♡♡♡", "♡♥♡", "❥♥♡", "♥♡♡", "♡♥♡♡", "♥♡♥", "♥♥♥", "♡♡♡♡", "❥♥♥", "♥♥♡♥", "❥❥♡", "♥♡♥♥", "❥♡♥", "♡♥♥", "♥♡♡♥", "♡♥♥♡", "❥❥♥", "♡♡♡♥", "♥♥♡", "♡♡♥♥", "♥♥♡♥♥", "♥♡♡♡", "♥♥♥♥", ",", "."]
"♡♡♡♥♡♡♥❥♥♥♡♡♡♡❥♥♥❥❥♡❥❥♥♡♥♡❥♥♡♡♥♡♥♡♡♡♥♡♡♡♥♥❥❥♥♡♡♡♡❥♥♥♥♥♡♥♥♡♥♡♡♡♥♡♡❥♥♡♥♡♥♥❥♥♥♡♥♥❥♥♡❥♡♥❥♡♥♡♥♡♡♥♡♡♡❥❥♡❥❥♥♡♥♡♥♥♥❥❥♡.
♥♡♡♥♥♡♥❥♥♥♥♡♥♥♡♡♡♥♥♥♡❥♥♥❥❥♡❥❥♥♡♥♡♡♡♡♡♥♥,❥❥♥♥♥♥♥♡♥♥❥♥♥❥❥♥♥♥♥❥❥♡♡♥♥♡."
Подсказка: разбейте текст на слова из списка и посмотрите на азбуку Морзе.
Способы представления графов в памяти (16.02)
План занятия
- Разбор ошибок в домашнем задании.
- Графы. Способы представления графов в памяти (матрица смежности, список рёбер, список соседей (список смежностей), матрица инцидентности). Зависимость сложности алгоритмов от способа представления. Читать Кормена и др., 3-е изд., §22.1 Представление графов, стр. 626
Домашнее задание 11 (до 02.03)
- Задача A.
- Задача B.
- Нарисуйте неориентированный граф с 5 вершинами и 8 рёбрами. Напишите его матрицу смежности, список рёбер, список соседей (список смежностей), матрицу инцидентности.
- Нарисуйте ориентированный граф с 4 вершинами и 3 рёбрами. Напишите его матрицу смежности, список рёбер, список соседей (список смежностей), матрицу инцидентности.
- Дан ориентированных граф. Исходящая степень вершины v --- это количество исходящих из неё рёбер, входящая степень v --- это количество рёбер входящих в v. Имеется представление ориентированного графа с использование списка соседей. Как долго будут вычисляться исходящие степени всех вершин графа? А входящие степени?
- Дан граф G = (V, E). Какие из рассмотренных способов хранения графов используют меньше всего памяти для хранения G? Указание: рассмотрите случаи |V|2 < |E| и |V|2 > |E|.
- Пусть C --- это матрица смежности графа G.
- Как связаны элементы матрицы С2 и граф G?
- Как связаны элементы матрицы Сn и граф G?
- Пусть B --- это матрица инцидентности ориентированного графа G. Как связаны элементы матрицы BBT и граф G?
Реализация поиска в глубину (19.02)
План занятия
- Реализация поиска в глубину и смежных задач.
Домашнее задание 12 (до 5.03)
- (С++) Выберите любой способ хранения графа. Реализуйте поиск в глубину.
- (С++) Напишите алгоритм, который возвращает данные о том, какие вершины лежат в одной компоненте связности.
- (любой ЯП или псевдокод) Напишите алгоритм проверки сильной связности ориентированного графа. Какова его сложность?
Большое домашнее задание №2
Задание индивидуальное. В случае нарушения академических норм, ставится 0 за весь контест.
Необходимо реализовать 3 задачи из контеста, см. распределение задач. Каждую задачу можно написать на С++ или Python. На выполнение работы отводится две недели (см. время окончания контеста).
Алгоритм сдачи задач:
- Получить OK за задачу в контесте.
- Залить исходный код на Review Board. (Инструкция по использованию Review Board. В поле Reviewers - People указать логин семинариста (avalanche)). Работы, которые не были туда отправлены, не оцениваются вовсе.
- В течении суток вам приходят замечания к коду.
- Вы их исправляете, проверяете в контесте, что программа по-прежнему проходит все тесты, заливаете новую версию в Review Board. Штрафов за посылки НЕ будет.
- Процесс повторяется до тех пор, пока у меня остаются замечания или пока не истёк дедлайн. После закрытия контеста будут ещё одни сутки на доработку замечаний в Review Board.
- Оценивается последняя версия работы в Review Board.