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

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

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

Студент TODO №1 №2 №3 №4 №5 №6 №7 №8
466 Количество подстрок (2 балла) Поиск с ошибками (3 балла) Период строки (2 балла) Регулярные выражения (5-8 баллов) Замкнутость регулярных (1 балл) Сопоставление строк Антимат по Ахо-Корасику Кратчайшая строка по словарю (3 балла) Сравнение версий файлов (3-7 баллов) Конденсация графа (1 балл) Топологическая сортировка (2 балла) Чётность (3 балла) Паутина (1 балл) Сложность DSU (Устная, 3 балла) 2-SAT (5 баллов) Мосты онлайн (4 балла) Wormholes (1 балл) Наличные (2 балла) Сравнение Дейкстры и A* (4 балла) Паралелльный поиск в графе (8 баллов) КС-достижимость: алгоритм (4 балла) КС-достижимость: сложность (5 баллов) Нормальная форма Хомского (2 балла) Минимизация КС-автомата (4 балла) k-й наибольший элемент (4 балла) deleteMin в расширяющихся кучах (2 балла) Краскал (1 балл) Компания MST (2 ,балла) Пополнение несвязного графа (3 балла) Усложнение лабиринта (4 балла) Параллельный алгоритм Борувки (10 баллов) Площадь объединения прямоугольников (1 балл) Воздушный змей (1 балл) Собака на привязи (1 балл) Выпуклая оболочка (2 балла) Град (3 балла) Пахом и овраг (3 балла) Эффективный планировщик движения
Александр Симонов 36
Алтынова Анна 36
Бабушкин Алексей 37
Борисов Максим 34
Жоховец Илья 38
Ионин Василий 36
Кононов Николай 36
Матросов Максим 35
Мироненко Фома 34
Миронов Валерий 36
Сатановский Артем 34
Чен Александр 37
Шляпников Тимофей 37

Задачи

Домашняя работа 8. 31.10.19
  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.

  7. Эффективный планировщик движения

    Пусть есть бот, которому нужно попасть из точки A в точку B. Но на карте расставлены враги (точки). Нужно придумать наиболее близкий к оптимальному маршрут, который проходит как можно дальше от врагов. На паре мы обсуждали, что это можно сделать по диаграмме Вороного. Напишите симулятор этого процесса. Баллы следующие:
    + Визуализатор врагов и движения бота --- 3 балла
    + Построение диаграммы Вороного
    ++ Воспользоваться готовой библиотекой -- 1 балл
    ++ Написать алгоритм пересечения полуплоскостей -- 3 балла
    ++ Написать инкрементальный алгоритм -- 5 баллов
    ++ Написать алгоритм Форчуна -- 15 баллов
    + Интеллект бота по диаграмме Вороного
    ++ При статичном множестве врагов -- 2 балла
    ++ Симуляция движения + случайно появляющиеся враги -- 4 балла

Домашняя работа 7. 30.10.19
  1. Краскал (1 балл)

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

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

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

  3. Пополнение несвязного графа (3 балла)

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

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

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

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

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

Домашняя работа 6. 30.10.19
  1. k-й наибольший элемент (4 балла)

    Дан список запросов, каждый из которых представляет собой либо число "A", либо пару чисел "n,k". Если дано число A, то нужно присоединить его к концу массива (в начальный момент времени он пуст). Если дана пара n,k, то нужно вывести k-й в порядке убывания элемент среди n первых элементов массива.

    Пример:
    1
    2
    3
    2,2
    2
    3
    5
    4,1
    6,4

    Должно вывестись
    1 3 2

    Указание: используйте персистентные структуры

  2. deleteMin в расширяющихся кучах (2 балла)

    Докажите, что deleteMin в расширяющейся куче работает за O(n*log n)

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

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

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

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

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

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

  4. Минимизация КС-автомата (4 балла)

    Реализуйте алгоритм минимизации автомата, построенного по контекстно-свободной грамматике. Чем он отличается от алгоритма минимизации обычного конечного автомата?

Домашняя работа 4. 16.10.19
  1. Wormholes (1 балл)

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

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

    См. PDF-ку

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

    См. PDF-ку

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

    См. PDF-ку

Домашняя работа 3. 16.10.19
  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 (5 баллов)

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

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

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

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

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

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

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

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

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

Домашняя работа 1. 12.09.19
  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-2019 HwProj