1626435657-d8b5859c603358f86e10eaa21136178f (844271)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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. Что означает, что один класс схем программ транслируем в другой?

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)