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

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

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

Согласно стандарту IEEE, 32-разрядное число с плавающей запятой одинарной точности N определяется как

где S — знаковый бит, F — дробная мантисса, а E — смещенный показатель степени

Число с плавающей запятой хранится в формате S : E : F, где S, E и F хранятся в 1 бите, 8 битах и 23 битах соответственно

Каково десятичное значение числа с плавающей запятой C1E00000 (шестнадцатеричная система счисления)?

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

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

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

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

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

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

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

Что из перечисленного не является свойством растровой графики (Bitmap graphics)?

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

Пусть k — целое число, большее 1. Какое из следующих значений соответствует порядку возрастания выражения в зависимости от n?

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

Input

Направленный граф , где

Стоимость для всех , где тогда и только тогда, когда

Definition

длина кратчайшего пути от до для всех

Если нет пути от до , то

Если для всех

Problem

Определить для всех

Алгоритм Флойда-Уоршалла дает решение динамического программирования для определения массива для и по следующим условиям

длина кратчайшего пути от до , для которого все промежуточные узлы на этом пути находятся в (где никакие промежуточные узлы не допускаются, если

Тогда

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

для и

для всех

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

Выходные данные процедуры 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?

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

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

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

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