ttt (Контрольная работа 1)
Описание файла
Файл "ttt" внутри архива находится в следующих папках: Контрольная работа 1, кр1. Документ из архива "Контрольная работа 1", который расположен в категории "". Всё это находится в предмете "вычислительная сложность алгоритмов" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "ttt"
Текст из документа "ttt"
Вычислительная сложность алгоритмов, экзамен 2006-2007.
1 Вариант.
-
Как известно, одним из алгоритмов вычисления an с помощью умножений является бинарный алгоритм. Верно ли, что сложность по числу умножений этого алгоритма является монотонной функцией при рассмотрении в качестве входа
а) самого числа n
б) битовой длины m числа n?
-
Пусть TA(n) и T’A(n) – сложности в худшем случае алгоритма А по двум видам используемых операций, TA’’(n) – сложность по суммарному числу операций обоих видов. Какие из следующих соотношений обязательно выполняются (указать номера):
-
TA(n) + T’A(n) = TA’’(n) 2) TA(n) + T’A(n) ≤ T’’A(n).
-
Предыдущая задача при рассмотрении сложности в среднем вместо сложности в худшем случае.
-
Пусть для сложности TA(n) некоторого алгоритма А выполняются следующие оценки:
а) Можно ли из этих оценок выделить такую, что любая из оставшихся оценок является ее следствием?
б) Можно ли из этих оценок выделить такую, которая является следствием любой из оставшихся оценок?
-
Какие из оценок справедливы для сложности в худшем случае TBS(n) бинарного поиска места элемента в упорядоченном массиве длины n (указать номера):
// Далее 5 заданий по второй контрольной
Ответы (правильные):
1: Б
2: - -
3: + +
4: а) 2 б) 3
5: 1
