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

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

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

Например, и

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

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

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

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

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

Рассмотрите следующие два языка

Что из нижеследующего верно в отношении и  ?

Схема Эйлера неориентированного графа — это схема, в которой каждое ребро графа встречается ровно один раз

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

• Полный граф с 12 вершинами
• Полный граф с 13 вершинами
• Дерево с 13 вершинами

Рассмотрим следующий псевдокод

  x := 1;
  i := 1;
  while (x <= 1000)
  begin
    x := 2^x;
    i := i + 1;
  end;

Каково значение i в конце псевдокода?

Рассмотрите языки и , каждый по алфавиту {a, b}, где

Что из нижеследующего должно быть верно в отношении и  ?

• Если регулярный, то регулярный
• Если не зависит от контекста, то не зависит от контекста
• Если рекурсивный, то рекурсивный

Чтобы найти решение уравнения для полинома степени с производной , метод Ньютона делает итерации вида

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

Предположим, что у некоторого программного продукта средняя наработка на отказ составляет 10 000 часов, а среднее время на ремонт — 20 часов.

Если продуктом пользуются 100 клиентов, какова его доступность?