Список заданий по ДМ-сем2 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 90: Строка 90:
 
# Для каких $a$ определен $\log^*_a x$?
 
# Для каких $a$ определен $\log^*_a x$?
 
# Докажите, что если для $a$ и $b$ определен $\log^*_a x$ и $\log^*_b x$, то $\log^*_a x = O(\log^*_b x)$.
 
# Докажите, что если для $a$ и $b$ определен $\log^*_a x$ и $\log^*_b x$, то $\log^*_a x = O(\log^*_b x)$.
 +
# Предложите решение задачи с помощью дерева отрезков (ДО). Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить $i$-й элемент. Указание: не используйте групповые операции с модификаторами поддеревьев.
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить сумму отрезке.
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить произведение на отрезке.
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти элемент с минимальным индексом, больший или равный заданного значения.
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти на заданном отрезке элемент с минимальным индексом, больший или равный заданного значения.
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить значение к элементам на отрезке, найти элемент с минимальным индексом, больший или равный заданного значения.
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log^3 n)$. Заявляйте эту задачу только, если не умеете решать быстрее.
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log^2 n)$. Заявляйте эту задачу только, если не умеете решать быстрее.
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log n)$.
 +
# Предложите решение задачи с помощью ДО и деревьев поиска. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й, изменить элемент
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить сумму на отрезке
 +
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить минимум на отрезке
 +
# В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ (возможно пересекающихся) отрезков из выбранного множества
 +
# На базе предыдущего задания решите задачу о минимуме на отрезке без изменения элементов за $O(1)$ на запрос и $O(n \log n)$ предподготовки.
 
</wikitex>
 
</wikitex>

Версия 14:09, 3 мая 2015

<wikitex>

Дискретная математика, алгоритмы и структуры данных, 2 семестр

  1. Постройте массив, в котором сортировка выбором делает максимальное число обменов
  2. Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.
  3. Найдите минимальное число сравнений для сортировки 4 элементов
  4. Найдите минимальное число сравнений для сортировки 5 элементов
  5. Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
  6. Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов
  7. Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти
  8. Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(1)$ дополнительной памяти
  9. Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов
  10. Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
  11. Докажите, что с использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $\Omega(n \log n)$
  12. Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n^2)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве.
  13. Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n \log n)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве. Указание: зная порядок на подстроках длины $L$ порядок на подстроках длины $2L$ можно восстановить за $O(n)$.
  14. Пусть известно, что массив длины $n$ из чисел от 1 до $n$ получен с помощью генератора случайных чисел, каждое число независимо получено с помощью равномерного распределения. Предложите модификацию алгоритма сортировки подсчетом, который сортирует данный массив за $O(n)$ используя лишь $O(\sqrt{n})$ дополнительной памяти (обе оценки должны выполняться в среднем).
  15. Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
  16. Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
  17. Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
  18. Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
  19. Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $2^k$. Преложите алгоритм определения за $O(1)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
  20. Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $n$. Преложите алгоритм определения за $O(\log n)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
  21. Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 одного знака.
  22. Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.
  23. Предложите алгоритм определения глубины сортирующей сети за $O(k)$, где $k$ - число компараторов.
  24. Докажите или опровергните, что для любого заданного неотсортированного набора из 0 и 1 существует сеть компараторов, которая сортирует все наборы кроме заданного
  25. Докажите или опровергните, что для любой перестановки чисел от 1 до $n$ существует сеть компараторов, которая сортирует все перестановки, кроме заданной
  26. Постройте сортирующую сеть для 5 проводов с минимальным числом компараторов
  27. Предложите сортирующую сеть с $O(n \log^2 n)$ компараторов.
  28. Разберитесь в том, как устроена сортирующая сеть с $O(n \log n)$ компараторов и изложите это за 15 минут, чтобы общие идеи были ясны
  29. Докажите, что сортирующая сеть имеет глубину $\Omega(\log n)$
  30. Как найти $s$-й по величине элемент в куче при малых $s$?
  31. Предложите массив, который при превращении в кучу с помощью алгоритма за $O(n)$ требует выполнить максимальное число обменов.
  32. Предложите массив, из кучи в отсортированный массив требует выполнить максимальное число обменов.
  33. В массиве есть $k$ элементов, для которых нарушено условие кучи. Преваритите массив в кучу за $k \log n$ действий
  34. Докажите, что нельзя проверить, есть ли в куче два одинаковых элемента быстрее, чем за $\Omega(n \log n)$.
  35. Проанализировать саморасширяющийся массив, если расширение происходит в $A$ раз ($1 < A$)
  36. Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в 2 раза, а при заполнении менее чем на 1/4 - сужение в 2 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.
  37. Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в A раз, а при заполнении менее чем на B - сужение в C раза
  38. Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(\log n)$.
  39. Задан односвязный список, каждый элемент знает следующий после себя. При этом возможно, что на самом деле список зацикливается (один из элементов ссылается как на следующий на элемент, который уже встречался в списке перед ним). Требуется проверить, зацикливается ли заданный односвязный список за $O(n)$ с $O(1)$ дополнительной памяти
  40. В массиве есть элемент, который встречается хотя бы $n/2$ раз. Требуется найти его за $O(n)$ с $O(1)$ дополнительной памяти
  41. Использования памяти без инициализации. Задан массив $a[1..n]$. Требуется поддержать две операции: $set(i, x)$ и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.
  42. Счетчик Кнута. Рассмотрим массив $a[0..n-1]$. Будем считать, что в каждом элементе может быть число 0, 1 или 2 и массив представляет собой число $a[0]+a[1]\cdot 2+a[2]\cdot 4 + \ldots + a[n-1]\cdot2^{n-1}$. Требуется реализовать операцию добавления $2^k$ к числу, представленному в массиве за истинное $O(1)$ и $O(n)$ дополнительной памяти.
  43. Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакого размера за $O(1)$ времени и $O(1)$ дополнительной памяти
  44. Предложите реализацию стека, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в стеке"
  45. Стек с множественным извлечением. Добавим в стек операцию multipop(k), которая снимает вершины стека k элементов. Докажите, что амортизированная стоимость операции multipop равна $O(1)$. Сформулируйте окончательное доказательство с использованием метода потенциалов.
  46. Продемонстрируйте, как просимулировать очередь на двух стеках. Амортизированная стоимость операций push и pop должна быть $O(1)$.
  47. Предложите реализацию очереди, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в очереди". Амортизированная стоимость всех операций должна быть $O(1)$.
  48. Можно ли реализовать два стека на очереди (ограничений на время выполнения операций нет)?
  49. В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Какое оптимальное асимптотически $d$ следует выбрать?
  50. В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Время выполнения decreaseKey - $C_1 \log n$, а extractMin - $C_2 d \log n$. Какое $d$ следует выбрать?
  51. Пусть подряд выполняется $n$ операций insert в пустую биномиальную кучу. Какое среднее время операции?
  52. Как можно модифицировать биномиальную кучу, чтобы insert выполнялось за истиное $O(1)$, а амортизированная стоимость остальных операций не поменялась?
  53. Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Ограничений на число деревьев одного ранга нет. Разработайте операции merge и extractMin для тонких куч. Амортизированная стоимость операции extractMin должна быть $O(\log n)$. Амортизированная стоимость операции merge должна быть $O(1)$.
  54. Разработайте операцию decreaseKey для тонкой кучи. Докажите, что амортизированное время выполнения есть $O(1)$ (используйте потенциал $2M + T$, где $M$ - число вершин, у которых удалили ребенка)
  55. Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$
  56. Ускорение extractMin. Докажите, что в тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
  57. Предложите алгоритм удаления из АВЛ-дерева.
  58. Предложите алгоритм добавления в красно-черное дерево
  59. Предложите алгоритм удаления из красно-черного дерева
  60. Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
  61. Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
  62. Предложите алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$
  63. В АВЛ-дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
  64. В красно-черном дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
  65. Предложите реализацию АВЛ-дерева, в которой в каждом узле хранится $O(1)$ бит
  66. Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
  67. Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
  68. Пусть заданы наборы ключей $(x_1, x_2, ..., x_n)$ и $(y_1, y_2, ..., y_n)$, где все $x$-ы и все $y$-и различны. Докажите, что существует единственное декартово дерево с набором ключей в вершинах $(x_i, y_i)$
  69. В условиях предыдущей задачи пусть $x_1 < x_2 < .. < x_n$, покажите как построить декартово дерево за $O(n)$
  70. Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?
  71. Проведите анализ случай zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции
  72. Проведите анализ случай zig-zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции
  73. Статическая оптимальность сплей-дерева. Докажите, что если к ключам $1, ..., n$, сложенным в сплей-дерево выполняется m запросов, к $i$-му ключу осуществляется $k_i$ запросов, где $k_i > 0$, то суммарное время работы не превышает $O(m H(p_1, p_2, .., p_n))$, где $p_i = k_i / m$, $H$ - шенноновская энтропия
  74. Постройте пример сплей-дерева, содержащего не менее 6 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком
  75. Постройте пример сплей-дерева, содержащего не менее 7 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком
  76. Теорема о близких запросах в сплей-дереве. Пусть в сплей-дерево сложены ключи $1, ..., n$, зафиксируем один из ключей $f$, пусть выполняется $m$ запросов к ключам. Докажите, что суммарное время на запросы есть $O(n \log n + m + \sum(\log(|q_i - f| + 1)))$, где $q_i$ - $i$-й запрос
  77. Предложите реализацию insert в декартовом дереве.
  78. Предложите реализацию insert в декартовом дереве, использующую не более одного вызова split/merge.
  79. Предложите реализацию remove в декартовом дереве.
  80. Предложите реализацию remove в декартовом дереве, использующую не более одного вызова split/merge.
  81. Докажите оценку $O(\log n)$ для реализации СНМ со сжатием путей, но когда второе дерево всегда подвешивается на первое (а не обязательно меньшее на большее)
  82. Докажите оценку $O(\log^* n)$ для СНМ, если вместо рангов используется число вершин в поддереве (меньшее дерево подвешивается на большее)
  83. Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ ребер
  84. Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Приведите пример, где высота дерева в результате серии объединений будет $\Omega(n)$.
  85. Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.
  86. Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое произвольным образом, но не проводить сжатие путей, то среднее время работы get будет $O(\log n)$.
  87. Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое случайным образом и проводить сжатие путей, то среднее время работы get будет $O(\log^* n)$.
  88. Для каких $a$ определен $\log^*_a x$?
  89. Докажите, что если для $a$ и $b$ определен $\log^*_a x$ и $\log^*_b x$, то $\log^*_a x = O(\log^*_b x)$.
  90. Предложите решение задачи с помощью дерева отрезков (ДО). Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить $i$-й элемент. Указание: не используйте групповые операции с модификаторами поддеревьев.
  91. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить сумму отрезке.
  92. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить произведение на отрезке.
  93. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти элемент с минимальным индексом, больший или равный заданного значения.
  94. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти на заданном отрезке элемент с минимальным индексом, больший или равный заданного значения.
  95. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить значение к элементам на отрезке, найти элемент с минимальным индексом, больший или равный заданного значения.
  96. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log^3 n)$. Заявляйте эту задачу только, если не умеете решать быстрее.
  97. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log^2 n)$. Заявляйте эту задачу только, если не умеете решать быстрее.
  98. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log n)$.
  99. Предложите решение задачи с помощью ДО и деревьев поиска. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й, изменить элемент
  100. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить сумму на отрезке
  101. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить минимум на отрезке
  102. В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ (возможно пересекающихся) отрезков из выбранного множества
  103. На базе предыдущего задания решите задачу о минимуме на отрезке без изменения элементов за $O(1)$ на запрос и $O(n \log n)$ предподготовки.

</wikitex>