Тест по Computer Science — вопросы

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

Какие из следующих задач будут решаться с помощью алгоритмов за полиномиальное время, если предполагается, что ?

• Дана комбинационная схема с n входами и m выходами и вентилями, где каждый вентиль является либо AND, OR, или NOT, и заданы m значений в качестве выходных данных или определяют, что не является возможным выходным сигналом схемы
• Учитывая n на n матриц A с рациональными числовыми элементами, либо найдите точное значение, обратное для A, либо определите, что не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел a/b (), где a и b выражены в двоичной системе счисления)
• Задан ориентированный граф с узлами, пронумерованными , и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла n, либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)

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

• Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер
• Нахождение максимальной клики в неориентированном графе
• Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер

Массив 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 появляется в массиве?

• if x[h] < t then h := h + 1
• h := h + 1
• k := k — 1

Некоторый рандомизированный алгоритм A предназначен для определения, является ли данное положительное целое число n простым, путем генерации случайной битовой строки r и, основываясь на значениях n и r, путем вывода либо Yes (n является простым), либо No (n является составным)

Выполнение алгоритма А гарантирует следующее

• Если n — простое число, то результатом A всегда будет Yes
• Если n является составным, то существует вероятность p > 0, такое что результатом A будет No с вероятностью p и Yes с вероятностью 1 — p

На входе 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, при котором приблизительно равно?

Некоторый рандомизированный алгоритм A предназначен для определения, является ли данное положительное целое число n простым, путем генерации случайной битовой строки r и, основываясь на значениях n и r, путем вывода либо Yes (n является простым), либо No (n является составным)

Выполнение алгоритма А гарантирует следующее

• Если n — простое число, то результатом A всегда будет Yes
• Если n является составным, то существует вероятность p > 0, такое что результатом A будет No с вероятностью p и Yes с вероятностью 1 — p

На входе m алгоритм A выполняется k раз (k > 0) и генерирует случайную строку при i-м выполнении , где являются взаимно независимыми

Предположим, что в каждом из k различных вариантов выполнения результат A равен No. Какова вероятность того, что m является составным?

Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами

Пусть M и m, соответственно, являются максимальным и минимальным количеством связанных компонентов в любом графе в коллекции

Если граф не имеет замкнутых циклов и между любой парой узлов имеется не более одного ребра, что из следующего верно?

Хэш-таблицы могут способствовать эффективному решению всех проблем, описанных ниже КРОМЕ