0
голосов
0
ответов
40 показов
В структуре данных хранится k-элементное подмножество A n-элементного множества
В структуре данных находится k-элементное подмножество A n-элементного множества. Необходимо проверить, принадлежит ли A элемент x. Для этого можно сд ...
1
голос
0
ответов
79 показов
Дан массив из n чисел. Нужно разбить
Дан массив из n чисел. Нужно разбить этот массив на максимальное количество непрерывных подмассивов так, чтобы после сортировки элементов внутри каждо ...
0
голосов
0
ответов
46 показов
Докажите, что если T1(n) = aT1(n/b) + f(n)
Докажите, что если T1(n) = aT1(n/b) + f(n), T2(n) = aT2(n/b) + g(n) и f(n) = Θ(g(n)), тоT1(n) = Θ(T2(n)).
0
голосов
0
ответов
59 показов
На вход подаётся числовой массив A из n элементов.
На вход подаётся числовой массив A из n элементов. Требуется найти число инверсий вмассиве, т. е. пар индексов (i, j), таких что i<j и a[i] > a[ ...
0
голосов
0
ответов
56 показов
Предположим, удалось установить, что любое число
Предположим, удалось установить, что любое число можно возвести в квадрат за O(n), гдеn – длина числа в двоичной записи. Докажите, что тогда любые два ...
0
голосов
1
ответ
56 показов
Язык множества подслов неполиномиального языка полиномиален?
Существует ли язык 𝐿 ̸∈ 𝒫, такой, что язык множества его подслов 𝐴(𝐿) ∈ 𝒫? По определению, считаем𝐴(𝐿)={𝑏|∃𝑎,𝑐∈Σ* : |𝑎𝑐|>0, 𝑎𝑏𝑐∈𝐿}.
0
голосов
0
ответов
46 показов
Доказать корректность рекурсивного алгоритма деления с остатком
Доказать корректность рекурсивного алгоритма деления с остатком (x:y = yq+r) и получить верхнюю оценку на время его работы.
0
голосов
0
ответов
53 показа
Функции T1(n) и T2(n) заданы рекуррентными формулами
Функции T1(n) и T2(n) заданы рекуррентными формулами, известно что Ti(1) = Ti(2) = Ti(3) = 1, i = 1,2. 1) Докажите, что для функции T2(n) = T2(n-1) + ...
0
голосов
0
ответов
56 показов
Верно ли, что ∃ε > 0 : n log n = Ω(n^(1+ε))?
Верно ли, что ∃ε > 0 : n log n = Ω(n^(1+ε))?
0
голосов
0
ответов
58 показов
Известно, что f(n) = O(n^2), g(n) = Ω(1), g(n) = O(n).
Известно, что f(n) = O(n^2), g(n) = Ω(1), g(n) = O(n). Положимh(n) = f(n)/g(n).1. Возможно ли, что а) h(n) = Θ(nlogn); б) h(n) = Θ(n^3)?2. Приведите н ...
0
голосов
0
ответов
53 показа
Пусть для положительной функции f(n) известно
Пусть для положительной функции f(n) известно, что f(n) = (3 + o(1))^n + Θ(n^100).Верно ли в общем случае, что log f(n) = Θ(n)?
0
голосов
0
ответов
94 показа
Сравнить размеры двух ящиков
Даны два ящика с размерами (L,B,H). Нужно определить равны ли они без учёта положения в пространстве... т.е. ящики с размерами (1,2,3), (1,3,2), (2,1, ...
0
голосов
0
ответов
70 показов
Для право-линейной грамматики создать автомат-анализатор.
Для право-линейной грамматики создать автомат-анализатор. Продукции грамматики приведеныниже в таблице. Затем, инвертировав правые части продукций гра ...
0
голосов
0
ответов
69 показов
Осуществить лексический анализ языка программы для вычисления суммы
Осуществитьлексическийанализязыкапрограммыдлявычислениясуммыкомпонентарифметической прогрессии.
0
голосов
1
ответ
139 показов
Найти число моделей формулы F
δ = < f > τ = < 1 > Sn(δ) = n^nF = ∀x[f(f(x)) = x]Найти число моделей для F.
142 вопроса
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.