1626435657-d8b5859c603358f86e10eaa21136178f (Тест)

1. Какова временная сложность МТ, которая всегда зацикливается?(не рассматриваем зацикливающиеся)

1. Что такое сложность в среднем?

1. Что значит, что сложность равна O(n)?

Временная (ёмкостная) сложность машины Тьюринга (РАМ-машины) в худшем (в среднем) имеет порядок O(n) ⇔ ∃ С1, C2 : С1*n <= T_M(n) <= C2*n для почти для всех n.

1. Возможно ли моделировать двухлетночную МТ на одноленточной?

(Да, счётные и нечётные позиции)

1. Что значит «рекурсивный график»?

(График -- Множество точек, Рекурсивный -- можно построить процедуру определения принадлежит точка графику или нет)

1. Что такое нижняя оценка сложности?

(Сложность наилучшей реализации алгоритма (эффективнее реализовать нельзя) )

1. Какие состояния автомата называются эквивалентными?

Если A -- конечный автомат. q1 ≈ q2 ⇔ A1 ≈ A2

A1 -- автомат A с q0 = q1, A2 -- автомат A с q0 = q2

1. Что такое минимальный автомат?

Автомат минимален, если

• нет недостижимых состояний

• нет эквивалентных состояний

1. Какова сложность в худшем поиска в двоичном дереве поиска?

O(2*n) (если дерево состоит только из левых/правых ветвей)

1. Какова сложность в худшем поиска в B-дереве?

O(log(n))

1. Какова сложность в худшем поиска в таблице расстановки (хэш-таблице)?

O(n) (если в таблице все элементы в одном списке одной ячейке)

1. Существуют ли методы сортировки массива сложности O(n)?

Метод сортировки, основанный на сравнениях, требует не менее O(nlog(n))

1. Какова ёмкостная сложность сортироки слиянием?

Дополнительный массив: O(n), рекурсия: O(log(n))

1. Какова сложность в худшем быстрой сортироки?

O(n^2) (как в полном переборе)

1. Существует ли пустая стандартная схема?

Нет, так как стартовая вершина v существует.

1. Что такое полурешётка?

1. Что такое стационарная разметка? (разметка -- функция на рёбрах : E -> L)

1. Что такое безопасная разметка?

Разметка безопасна, если ∀ e : (e) <= H(e)

1. Что означает, что стандартная схема тотальна?

Стандартная схема S тотальна, если∀ I : прот(S,I) конечен

Протокол схемы S при интерпретации I: прот(S,I) = (v0,W0),…, (vi,Wi), …

v -- вершины, W -- состояние памяти: X -> D

1. Что означает, что одна эквивалентность сильнее другой?

Из одной эквивалентности следует другая

1. Что такое инвариантное свойство (соотношение)?

то есть соотношение сохраняется

1. Что такое полная система преобразований для данной эквивалентности?

2. Что означает, что система преобразований корректна относительно данной эквивалентности?

1. Что такое смешанный вычислитель?

1. Что такое анализ периода связывания?

Анализ доступности переменных программы (BTA)

1. Что такое неподвижная точка оператора F? F(x0) = x0, x0 = fix F -- неподвижная точка

1. Что означает, что один класс схем программ транслируем в другой?