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

Одним из подходов к обработке данных нечеткой логики может быть разработка компьютера с использованием троичной логики (base-3), чтобы данные могли храниться в виде «true», «false» и «unknown»

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

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

График транзакций является сериализуемым, если его действие эквивалентно действию некоторого последовательного графика

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

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

 Lock A;        Lock B;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock B;
 B = B + 10;    C = C + 20;

 A = A - 10;    Lock B;
 Lock B;        B = B - 20;
 B = B + 10;    Unlock B;
 Unlock B;      C = C + 20;

 Lock A;        Lock A;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock A;
 B = B + 10;    C = C + 20;

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

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

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

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

Input

Ориентированный граф , где

Стоимость для любых , где и если только

Definition

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

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

Если для любого

Problem

Определить для любого

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

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

Тогда

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

для и

для любого

Каково время работы алгоритма Флойда-Уоршалла ?

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

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

Компания X отгрузила 5 компьютерных чипов, 1 из которых был бракованным, а компания Y отгрузила 4 компьютерных чипа, 2 из которых были бракованными

Один компьютерный чип должен быть выбран случайным образом из 9 чипов, отгруженных компаниями

Если обнаружится, что выбранный чип неисправен, какова вероятность того, что чип был изготовлен компанией Y ?