Алгоритмы и структуры данных

19.Б13-мм группа

Дмитрий Мордвинов

Студент TODO №1 №2 №3 №4 №5 №6 №7
627 Количество подстрок (2 балла) Поиск с ошибками (3 балла) Период строки (2 балла) Регулярные выражения (5-8 баллов) Замкнутость регулярных (1 балл) Сопоставление строк Антимат по Ахо-Корасику Кратчайшая строка по словарю (3 балла) Бойер-Мур (3 балла) Сравнение версий файлов (3-7 баллов) Конденсация графа (1 балл) Топологическая сортировка (2 балла) Чётность (3 балла) Паутина (1 балл) Сложность DSU (Устная, 3 балла) 2-SAT (3 балла) Мосты онлайн (4 балла) Краскал (1 балл) Компания MST (2 балла) Параллельный алгоритм Борувки (10 баллов) Сравнение производительностей MST-алгоритмов (3 балла) Пополнение несвязного графа (3 балла) Усложнение лабиринта (4 балла) Wormholes (1 балл) Наличные (2 балла) Сравнение Дейкстры и A* (4 балла) Паралелльный поиск в графе (8 баллов) Задача 1. КС-достижимость: алгоритм (4 балла) Задача 2. КС-достижимость: сложность (5 баллов) Задача 3. Нормальная форма Хомского (2 балла) Задача 4. Пересечение КА через тензорное произведение (4 балла) Раскраска клик (4 балла) Раскраска клик 2 (5 баллов) Сапёр (4 балла) Преобразование Цейтина (3 балла) Площадь объединения прямоугольников (1 балл) Воздушный змей (1 балл) Собака на привязи (1 балл) Выпуклая оболочка (2 балла) Град (3 балла) Пахом и овраг (3 балла)
Буканов Валерий 24
Головин Максим 40
Гущин Илья 39
Ермоленко Ксения 41
Лапина Екатерина 34
Ледовских Михаил 37
Максимова Анна 38
Наказной Илья 37
Пантелеймонов Андрей 38
Платонова Анна 37
Радионов Никита 41
Рюттель Игорь 40
Сергеев Матвей 41
Сурков Никита 40
Суслов Алексей 24
Танченко Яна 36
Хельмянов Артем 40

Задачи

Домашняя работа 7. 22.11.20
  1. Площадь объединения прямоугольников (1 балл)

    Даны прямоугольники на плоскости с вершинами в точках с целыми координатами и сторонами, параллельными осям координат. Необходимо найти площадь их объединения.

  2. Воздушный змей (1 балл)

    Решите задачу http://acm.timus.ru/problem.aspx?space=1&num=1963. К коду приложите ссылку на AC.

  3. Собака на привязи (1 балл)

    Решите задачу http://acm.timus.ru/problem.aspx?space=1&num=1246. К коду приложите ссылку на AC.

  4. Выпуклая оболочка (2 балла)

    Решите задачу http://acm.timus.ru/problem.aspx?space=1&num=1305. К коду приложите ссылку на AC.

  5. Град (3 балла)

    Решите задачу http://acm.timus.ru/problem.aspx?space=1&num=1317. К коду приложите ссылку на AC.

  6. Пахом и овраг (3 балла)

    Решите задачу http://acm.timus.ru/problem.aspx?space=1&num=1750. К коду приложите ссылку на AC.

Домашняя работа 6. 30.10.20
  1. Раскраска клик (4 балла)

    Напишите программу, которая по данному k определяет максимальный размер клики n, рёбра которой можно покрасить в k цветов таким образом, что ни один треугольник из рёбер не покрашен в один цвет. Например, для k = 1 ответ 2, для k = 2 ответ 5. Используйте какой-нибудь современный SAT-решатель для проверки наличия покраски для фиксированных k, n.

  2. Раскраска клик 2 (5 баллов)

    Попробуйте написать решение предыдущей задачи самостоятельно, без использования SAT-решателя, превзойдя его по эффективности. Предъявите время работы Вашего алгоритма и SAT-решателя для разных k и n.

  3. Сапёр (4 балла)

    Напишите программу, которая по заданной конфигурации поля игры «Сапёр», т.е. таблице, в каждая ячейка которой помечена миной, числом (сколько мин в соседних квадратах) или пуста, и пустой ячейке говорит, безопасна или небезопасна эта ячейка. Другими словами, проверьте, есть ли расположение мин на поле, удовлетворяющее входным ограничениям. Используйте SAT-решатель для проверки этого факта.

  4. Преобразование Цейтина (3 балла)

    Реализуйте преобразование Цейтина, переводящее входную формулу логики высказываний в КНФ.

Домашняя работа 5. 30.10.20
  1. Задача 1. КС-достижимость: алгоритм (4 балла)

    Реализуйте алгоритм для решения задачи достижимости с КС ограничениями через произведение булевых матриц

  2. Задача 2. КС-достижимость: сложность (5 баллов)

    Какова временная сложность алгоритма для решения задачи достижимости с КС ограничениями через произведение булевых матриц относительно размера входного графа и размера грамматики?

  3. Задача 3. Нормальная форма Хомского (2 балла)

    Предложите алгоритм преобразования произвольной контекстно-свободной грамматики в нормальную форму Хомского. Оцените увеличение размера грамматики при таком преобразовании.

  4. Задача 4. Пересечение КА через тензорное произведение (4 балла)

    Реализуйте алгоритм пересечения двух КА через тензорное произведение матриц смежности в двух вариантах: булева декомпозиция матриц смежности и "честные" матрицы смежности над множествами символов. Сравните производительность вариантов, проанализируйте и обоснуйте полученные результаты сравнения.

Домашняя работа 4. 18.10.20
  1. Пополнение несвязного графа (3 балла)

    Дан неориентированный граф (V,E) без петель и кратных рёбер и список вершин c_1, ... ,c_n из V. Гарантируется, что для всех i <> j, c_i не достижима из c_j. Вывести, какое максимальное количество рёбер можно добавить в граф, чтобы это свойство не нарушилось.

  2. Усложнение лабиринта (4 балла)

    Решите задачу https://www.spoj.com/problems/KPMAZE/. К коду приложите ссылку на AC.

  3. Wormholes (1 балл)

    Решите задачу https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499. К коду приложите ссылку на AC.

  4. Наличные (2 балла)

    См. PDF-ку

  5. Сравнение Дейкстры и A* (4 балла)

    См. PDF-ку

  6. Паралелльный поиск в графе (8 баллов)

    См. PDF-ку

Домашняя работа 3. 06.10.20
  1. Конденсация графа (1 балл)

    Реализуйте алгоритм конденсации ориентированного графа

  2. Топологическая сортировка (2 балла)

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

  3. Чётность (3 балла)

    Решите задачу http://acm.timus.ru/problem.aspx?space=1&num=1003. К коду приложите ссылку на AC.

  4. Паутина (1 балл)

    Решите задачу http://acm.timus.ru/problem.aspx?space=1&num=1671. К коду приложите ссылку на AC.

  5. Сложность DSU (Устная, 3 балла)

    Докажите, что сложность DSU со сжатием пути и объединением по размеру — O(log n)

  6. 2-SAT (3 балла)

    Придумайте способ эффективного поиска решений или доказательства их отсутствия для задачи 2-SAT (см. слайды). Реализуйте алгоритм.

  7. Мосты онлайн (4 балла)

    Реализуйте алгоритм поиска мостов в режиме онлайн

  8. Краскал (1 балл)

    Реализуйте Краскала с DSU

  9. Компания MST (2 балла)

    Решите задачу https://codeforces.com/contest/125/problem/E. К коду приложите ссылку на AC.

  10. Параллельный алгоритм Борувки (10 баллов)

    Придумать и реализовать параллельную версию алгоритма Борувки.

  11. Сравнение производительностей MST-алгоритмов (3 балла)

    Напишите генератор случайных взвешенных неориентированных графов. Сравните производительность собственных реализаций алгоритмов нахождения минимального остовного дерева (как минимум, Прима с кучей и Краскала с DSU).

Домашняя работа 2. 21.09.20
  1. Антимат по Ахо-Корасику

    a. (3 балла) Дан текст и список нецензурных слов. Найти все вхождения нецензурных слов в тексте.
    b. (10 баллов) Напишите расширение для Вашего любимого браузера, которое фильтрует все нецензурные слова на веб-странице.

  2. Кратчайшая строка по словарю (3 балла)

    Дан словарь. Построить кратчайшую строку, в которую входят все слова словаря.

  3. Бойер-Мур (3 балла)

    Напишите поиск подстроки в строке по Бойеру-Муру. Сравните на случайных строках производительность с реализацией КМП.

  4. Сравнение версий файлов (3-7 баллов)

    Напишите свою реализацию утилиты diff

Домашняя работа 1. 21.09.20
  1. Количество подстрок (2 балла)

    Дан текст. Посчитать количество его различных подстрок

  2. Поиск с ошибками (3 балла)

    Дан текст и строка, введённая пользователем. Найти все вхождения строки в текст с учётом, что пользователь мог ошибиться в одном символе (потерять, вставить или заменить один символ в строке).

  3. Период строки (2 балла)

    Строка называется k-периодичной, если она имеет вид α . . . α, где |α| = k. Например, строка abababab 2-периодична, 4-периодична и 8-периодична. Определите минимальный период заданной строки.

  4. Регулярные выражения (5-8 баллов)

    Напишите интерпретатор регулярных выражений

  5. Замкнутость регулярных (1 балл)

    Докажите, что класс регулярных языков замкнут относительно пересечения, дополнения и разности

  6. Сопоставление строк

    Пусть даны строки α1, . . . , αn, β1, . . . , βn ∈ Σ*.
    a. (4 балла) Найти такие i1, . . . , ik , j1, . . . , jm ∈ N, что αi1. . . αik = βj1. . . βjm, либо определить, что их не существует. Например, для α1 = a, β1 = aa подойдёт ответ i1 = 1, i2 = 1, j1 = 1.
    b. (50 баллов) Придумайте эффективный алгоритм, который находит i1, . . . , ik ∈ N, что αi1. . . αik = βi1. . . βik, либо определяет, что их не существует.

© 2014-2021 HwProj