Вариант 737271221.
Какая из следующих формул исчисления предикатов должна быть верной при любых интерпретациях?
Какие из следующих задач будут решаться с помощью алгоритмов за полиномиальное время, если предполагается, что ?
Какая из следующих задач может быть решена с помощью стандартного жадного алгоритма?
Массив A содержит 256 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 4096
Массив B содержит 512 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 8192
Предположим, что только массивы A и B могут быть кэшированы в изначально пустой, физически адресуемой, физически маркированной, кэш-памяти с прямым отображением, объемом 2 Кбайт и размером блока 8 байт
Затем выполняется следующий цикл
for (i = 0; i < 256; i++) A[i] = A[i] + B[2*i];
Сколько байт будет записано в память во время выполнения цикла, если в кэше предусмотрена политика обратной записи?
Предположим, что целевой объект t — это целочисленное значение, хранящееся в некотором элементе целочисленного массива x, который отсортирован в неубывающем порядке, и рассмотрим следующую схему цикла для поиска t
<initialization of h and k> while (x[h] != t) { P; }
Если initialization устанавливает инвариант , какое из следующих определений для P, взятое по отдельности, гарантирует, что цикл завершится с , предпологая, что t появляется в массиве?
Некоторый рандомизированный алгоритм A предназначен для определения, является ли данное положительное целое число n простым, путем генерации случайной битовой строки r и, основываясь на значениях n и r, путем вывода либо Yes (n является простым), либо No (n является составным)
Выполнение алгоритма А гарантирует следующее
На входе m алгоритм A выполняется k раз (k > 0) и генерирует случайную строку при i-м выполнении , где являются взаимно независимыми
Если m является составным, какова вероятность того, что в каждом из k различных вариантов выполнения результат A будет YES?
Рассмотрите следующую функцию
f(k) { x = 2; for i = 1 to k x = x * x; return x; }
Если n и k — целые положительные числа, то наименьшее значение k, при котором приблизительно равно?
Предположим, что в каждом из k различных вариантов выполнения результат A равен No. Какова вероятность того, что m является составным?
Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами
Пусть M и m, соответственно, являются максимальным и минимальным количеством связанных компонентов в любом графе в коллекции
Если граф не имеет замкнутых циклов и между любой парой узлов имеется не более одного ребра, что из следующего верно?
Хэш-таблицы могут способствовать эффективному решению всех проблем, описанных ниже КРОМЕ