Математическая логика и теория алгоритмов. Стенюшкина В.А. - 111 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

ставим A[n] на правильное место в отсортированном массиве A[1..(n-1)]. На-
пишите рекуррентное соотношение для времени работы такой процедуры.
31 Пусть сортировки вставками и слиянием исполняются на одной и той
же машине и требуют 8n
2
и 64n log(n) операций соответственно. Для каких зна-
чений n сортировка вставками является более эффективной?
32 При каком наименьшем значении n алгоритм, требующий 100n
2
опе-
раций, эффективнее алгоритма, требующего 2
n
операций?
33 Пусть f(n) и g(n) – неотрицательны для достаточно больших n. Пока-
жите, что max(f(n), g(n))=Θ(f((n)+g(n)).
34 Покажите, что (n+f)
b
= Θ(n
b
) для любого вещественного a и для любого
b>0.
35 Можно ли утверждать, что
a)
2
n+1
=O(2
n
);
b)
2
2n
=O(2
n
).
36 Приведите пример функций f(n) и g(n), для которых f(n)=О(g(n)),но
f(n) ≠ о(g(n)) и f(n) ≠ Θ (g(n)).
37 Покажите, что свойства f(n)=o(g(n) и f(n)=ω g(n не могут быть выпол-
нены одновременно.
38 Докажите, что log(n!)= Θ(nlog(n)) и что n!=o(n
n
).
39 Будет ли функция
log(n) ! полиномиально ограниченной? Будет ли
функция
log(log(n)) полиномиально ограниченной?
40 Покажите, что из T(n)=T(
n/2)+1 cледует T(n)=O(log(n)), а из T(n)=2
T(
n/2+n следует T(n)=Ω(nlog(n)), и тем самым T(n)= Θ(nlog(n)).
41 Используя основную теорему, найдите асимптотически точные оценки
для соотношений:
а) T(n)=4T(n/2)+n;
б) T(n)=4T(n/2)+n
2
.
42 Используя основную теорему, покажите, что соотношение
T(n)=T(n/2)+ Θ(1) (для двоичного поиска) T(n)= Θ(log(n)).
43 Докажите, что для непрерывной задачи о рюкзаке выполнен принцип
жадного алгоритма.
44 Разработайте основанный на динамическом программировании алго-
ритм для решения дискретной задачи о рюкзаке. Алгоритм должен сработать за
время O(nW), где n – количество вещей, W – максимальный вес рюкзака.
45 Докажите, что в бинарном дереве, соответствующем оптимальному
префиксному коду, всякая вершина либо является листом, либо имеет двух де-
тей.
46 Найдите код Хаффмена для алфавита, в котором частоты символов со-
впадают с первыми восемью числами Фибоначчи: a:1 b:1 c:2 d:3 e:3 f:8 g:13
h:21Что будет, если в алфавите n символов, частоты которых совпадают с пер-
выми n числами Фибоначчи?
47 Некто утверждает, что написанная им программа сжатия информации
позволяет сжать любой файл длины 1000 (8 – битовых байтов) хотя бы на один 
ставим A[n] на правильное место в отсортированном массиве A[1..(n-1)]. На-
пишите рекуррентное соотношение для времени работы такой процедуры.
      31 Пусть сортировки вставками и слиянием исполняются на одной и той
же машине и требуют 8n2 и 64n log(n) операций соответственно. Для каких зна-
чений n сортировка вставками является более эффективной?
      32 При каком наименьшем значении n алгоритм, требующий 100n2 опе-
раций, эффективнее алгоритма, требующего 2n операций?
      33 Пусть f(n) и g(n) – неотрицательны для достаточно больших n. Пока-
жите, что max(f(n), g(n))=Θ(f((n)+g(n)).
      34 Покажите, что (n+f)b= Θ(nb) для любого вещественного a и для любого
b>0.
      35 Можно ли утверждать, что
      a) 2n+1=O(2n);
      b) 22n =O(2n).
      36 Приведите пример функций f(n) и g(n), для которых f(n)=О(g(n)),но
f(n) ≠ о(g(n)) и f(n) ≠ Θ (g(n)).
      37 Покажите, что свойства f(n)=o(g(n) и f(n)=ω g(n не могут быть выпол-
нены одновременно.
      38 Докажите, что log(n!)= Θ(nlog(n)) и что n!=o(nn).
      39 Будет ли функция log(n) ! полиномиально ограниченной? Будет ли
функция log(log(n)) полиномиально ограниченной?
      40 Покажите, что из T(n)=T(n/2)+1 cледует T(n)=O(log(n)), а из T(n)=2
T(n/2+n следует T(n)=Ω(nlog(n)), и тем самым T(n)= Θ(nlog(n)).
      41 Используя основную теорему, найдите асимптотически точные оценки
для соотношений:
      а) T(n)=4T(n/2)+n;
      б) T(n)=4T(n/2)+n2.
      42 Используя основную теорему, покажите, что соотношение
T(n)=T(n/2)+ Θ(1) (для двоичного поиска) T(n)= Θ(log(n)).
      43 Докажите, что для непрерывной задачи о рюкзаке выполнен принцип
жадного алгоритма.
      44 Разработайте основанный на динамическом программировании алго-
ритм для решения дискретной задачи о рюкзаке. Алгоритм должен сработать за
время O(nW), где n – количество вещей, W – максимальный вес рюкзака.
      45 Докажите, что в бинарном дереве, соответствующем оптимальному
префиксному коду, всякая вершина либо является листом, либо имеет двух де-
тей.
      46 Найдите код Хаффмена для алфавита, в котором частоты символов со-
впадают с первыми восемью числами Фибоначчи: a:1 b:1 c:2 d:3 e:3 f:8 g:13
h:21Что будет, если в алфавите n символов, частоты которых совпадают с пер-
выми n числами Фибоначчи?
      47 Некто утверждает, что написанная им программа сжатия информации
позволяет сжать любой файл длины 1000 (8 – битовых байтов) хотя бы на один

Страницы