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

Пусть M — одноленточная детерминированная машина Тьюринга с ленточным алфавитом {blank, 0, 1}, и C обозначает (возможно, бесконечное) вычисление M, начинающееся с пустой ленты

Входными данными для каждой задачи, приведенной ниже, являются M и целое положительное число n

Какая из следующих проблем является разрешимой?

• Вычисление C длится не менее n шагов
• Вычисление C длится не менее n шагов, и M выводит 1 в какой-то момент после n-го шага
• M сканирует не менее n различных квадратов ленты во время вычисления C

Выходные данные процедуры mystery зависят от используемого метода передачи параметров

  procedure mystery
    a : integer;
    b : integer;
    procedure enigma(x,y)
    begin
      y = y + b;
      x = b + x;
      b = x + b;
      a = y;
    end enigma;
  begin
    a = 2; b = 7;
    enigma(a,b);
    write(a); write(b);
  end mystery;

Предположим, что все параметры передаются по значению

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

Логическая схема имеет три входных бита: где  — младший бит, а  — старший бит

Выход схемы равен 1, если на ее входе указано любое из трехбитовых чисел 1, 4, 5 или 6; в противном случае выход схемы равен 0

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

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

Какое из следующих утверждений о дейтаграммах, отправляемых узлом в сети с использованием протокола IPv4, является верными?

• Датаграммы в источнике должны иметь размер наименьшего максимального блока передачи (MTU) всех соединений на пути к месту назначения
• Дейтаграммы могут быть фрагментированы во время маршрутизации
• Дейтаграммы собираются заново только в пункте назначения

Некоторая конвейерная RISC-машина имеет 8 регистров общего назначения R0, R1, …, R7 и поддерживает следующие операции

 ADD Rs1, Rs2, Rd    Add Rs1 to Rs2 and put the sum in Rd
 MUL Rs1, Rs2, Rd    Multiply Rs1 by Rs2 and put the product in Rd

Операция обычно занимает один цикл; однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций.

Рассмотрим выражение AB ABC BC + +, где переменные A, B, C находятся в регистрах R0, R1, R2

Если содержимое этих трех регистров не должно изменяться, то каково минимальное количество тактов требуется для последовательности операций, которая вычисляет значение AB ABC BC + +?

Рассмотрим следующий псевдокод, где n — неотрицательное целое число

  x = 0;
  i = 0;
  while i < n do
    x = x + 2^i;
    i = i + 1;
  end

Что из приведенного ниже является инвариантом цикла для оператора while?

(Примечание: инвариант цикла для оператора while — это утверждение, которое верно каждый раз, когда сторожевое условие оценивается во время выполнения оператора while)

Центральный процессор имеет арифметический модуль, который складывает байты, а затем устанавливает свои флаговые биты V, C и Z следующим образом

Бит V устанавливается, если происходит арифметическое переполнение (в арифметике с двумя дополнениями)

Бит C устанавливается, если во время операции генерируется перенос из самого старшего бита

Бит Z устанавливается, если результат равен нулю

Каковы значения флагов битов V, C и Z после добавления 8-битных байтов 1100 1100 и 1000 1111 ?

Рассмотрите следующую функцию

  f(k)
  {
    x = 2;
    for i = 1 to k
      x = x * x;
    return x;
  }

Если n и k — целые положительные числа, то наименьшее значение k, при котором приблизительно равно?

Предположим, что Q и R — языки.

Предполагая, что , что из следующего следует, что R отсутствует в P?