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

UptoLike

ВУЗ: 

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

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

Рубрика: 

14 Приведите пример вычислимой универсальной функции, не являю-
щейся главной.
15 Пусть X, Y – два различных множества. Рассмотрим программы, име-
ющие доступ к двум оракулам для X и для Y и функции, которые можно вычи-
слить с помощью таких программ. Укажите такое множество Z, что X – Y – вы-
числимость совпадает с Z – вычислимостью.
16 Описать конструкцию функции Аккермана.
17 Составить программу для решения на машине Тьюринга задачу удвое-
ния числа.
18 Составить схему примитивной рекурсии для двуместных функций
[x/y] – неполное частное, rest(x,y) – остаток от деления x на y.
19 Составить нормальный алгоритм для функции
λ(x)=x+1.
20 Доказать, что алгоритм распознавания несамоприменимости нормаль-
ных алгоритмов невозможен.
21Как работает сортировка вставками на входе A=(31,41, 59, 26, 41, 58)?
22 Измените процедуру сортировки вставками так, чтобы она сортирова-
ла числа в невозрастающем порядке.
23 Рассматривается задача поиска.
Вход: Последовательность n чисел A=(a
1
,…,a
n
) и число v.
Выход: Индекс i, для которого v=A[i] или NIIL.
Напишите алгоритм (линейного поиска), который последовательно про-
сматривает A в поисках v.
24 Сколько сравнений потребуется в среднем алгоритму линейного по-
иска, если искомым элементом может быть любой элемент массива с одинако-
вой вероятностью? Каково время работы в худшем случае и в среднем? Как за-
писать эти времена с помощью
θ - обозначений?
25Дана последовательность чисел x
1
,…,x
n
. Покажите, что за время
θ(nlog(n)) можно определить, есть ли в этой последовательности два одинако-
вых числа.
26 Как записать выражение n
3
/1000-100n
2
-100n+3 с помощью θ - обозна-
чений?
27 Даны коэффициенты a
0
,…,a
n-1
многочлена; требуется найти его значе-
ние в заданной точке x. Естественный алгоритм требует времени
θ(n
2
). Как вы-
полнить вычисления за время
θ(n), не используя дополнительного массива?
Используйте «схему Горнера»:
∑
−
=
1
0
n
i
a
i
x
i
=(…(a
n-1
x+a
n-2
)x+…+a
1
)x+a
0
28 Покажите работу сортировки слиянием для массива A=(3, 41, 52, 26,
38, 57, 9, 49).
29 Покажите по индукции, что если T(n)=
{
,2),2/(2
,2,2
n
nеслиnT
nесли
=
=
то T(n)=nlog(n) (при всех n, являющихся степенями двойки).
30 Сортировку вставками можно оформить как рекурсивную процедуру:
желая отсортировать A[1..n], мы (рекурсивно) сортируем A[1..(n-1)], а затем 
       14 Приведите пример вычислимой универсальной функции, не являю-
щейся главной.
       15 Пусть X, Y – два различных множества. Рассмотрим программы, име-
ющие доступ к двум оракулам для X и для Y и функции, которые можно вычи-
слить с помощью таких программ. Укажите такое множество Z, что X – Y – вы-
числимость совпадает с Z – вычислимостью.
       16 Описать конструкцию функции Аккермана.
       17 Составить программу для решения на машине Тьюринга задачу удвое-
ния числа.
       18 Составить схему примитивной рекурсии для двуместных функций
[x/y] – неполное частное, rest(x,y) – остаток от деления x на y.
       19 Составить нормальный алгоритм для функции λ(x)=x+1.
       20 Доказать, что алгоритм распознавания несамоприменимости нормаль-
ных алгоритмов невозможен.
       21Как работает сортировка вставками на входе A=(31,41, 59, 26, 41, 58)?
       22 Измените процедуру сортировки вставками так, чтобы она сортирова-
ла числа в невозрастающем порядке.
       23 Рассматривается задача поиска.
       Вход: Последовательность n чисел A=(a1,…,an) и число v.
       Выход: Индекс i, для которого v=A[i] или NIIL.
       Напишите алгоритм (линейного поиска), который последовательно про-
сматривает A в поисках v.
       24 Сколько сравнений потребуется в среднем алгоритму линейного по-
иска, если искомым элементом может быть любой элемент массива с одинако-
вой вероятностью? Каково время работы в худшем случае и в среднем? Как за-
писать эти времена с помощью θ - обозначений?
       25Дана последовательность чисел x1,…,xn. Покажите, что за время
θ(nlog(n)) можно определить, есть ли в этой последовательности два одинако-
вых числа.
       26 Как записать выражение n3/1000-100n2-100n+3 с помощью θ - обозна-
чений?
       27 Даны коэффициенты a0,…,a n-1 многочлена; требуется найти его значе-
ние в заданной точке x. Естественный алгоритм требует времени θ(n2). Как вы-
полнить вычисления за время θ(n), не используя дополнительного массива?
                                 n −1
Используйте «схему Горнера»:    ∑i =0
                                        a i x i=(…(an-1x+an-2)x+…+a1)x+a0
      28 Покажите работу сортировки слиянием для массива A=(3, 41, 52, 26,
38, 57, 9, 49).
                                                         2, если n = 2,
      29 Покажите по индукции, что если           T(n)=       {
                                                         2T (n / 2), если n = 2 n ,
то T(n)=nlog(n) (при всех n, являющихся степенями двойки).

     30 Сортировку вставками можно оформить как рекурсивную процедуру:
желая отсортировать A[1..n], мы (рекурсивно) сортируем A[1..(n-1)], а затем

Страницы