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

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

Пусть N — множество всех натуральных чисел.

Какие из следующих множеств счетные?

• Совокупность всех функций от N до {0, 1}
• Набор всех функций от {0, 1} до N
• Наибольшее подмножество из N

Что из приведенного ниже представляет собой обратный (post-order) обход T?

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

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

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

Некоторый рандомизированный алгоритм 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 является составным?

Пусть A и B — два набора слов (строк) из ∑* для некоторого алфавита символов ∑

Предположим, что B является подмножеством A

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

• Если A конечно, то и B конечно
• Если A регулярно, то и B регулярно
• Если A не зависит от контекста, то и B не зависит от контекста

На конвейерном RISC-компьютере, где все арифметические команды имеют одинаковый CPI (cycles per instruction), какие из следующих действий улучшат время выполнения типичной программы?

• Увеличение частоты тактового цикла
• Запрещение любой переадресации в конвейере
• Удвоение размеров кэша интсрукций и кэша данных без изменения времени такта

Для каждого неотрицательного целого числа n пусть  — максимально возможное число областей, на которые плоскость может быть разделена n прямыми линиями

Например, и

Тогда имеет порядок

Что из перечисленного НЕ является разумным обоснованием выбора режима активного ожидания для асинхронного события?

Какое из следующих утверждений об Ethernet-сетях является ЛОЖНЫМ?