Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Конструктивные объекты
(продолжение)
►Следующие объекты не являются
конструктивными объектами. Мы не
можем представить их в виде слов в
некотором конечном алфавите.
► 1) Действительное число, являющееся
бесконечной десятичной дробью.
► 2) Произвольная функция
f(x)
из
N
в
N
.
Счетные множества
Напомним некоторые сведения о счетных множествах.
► Множество
A
называется равномощным множеству
B,
если существует биективное (взаимно однозначное)
отображение множества
A
во множество
B.
Если
A
равномощно
B,
то
B
равномощно
A.
► Множество
A
называется счетным множеством, если
оно равномощно множеству натуральных чисел
N.
В
этом случае существует биекция f:
N
A
и элемент a с
условием f(n)=a можно обозначить через a
n
.
Таким
образом, справедливо утверждение:
►
Множество A счетно, тогда и только тогда, когда его
элементы можно представить в виде бесконечной
последовательности без повторений:
A={a
0
, a
1
, a
2
,...}.
Счетные множества
(продолжение)
Отметим следующие известные свойства счетных множеств.
1. Подмножество счетного множества конечно или счетно.
2. Объединение конечного или счетного числа конечных или
счетных множеств конечно или счетно.
3. Множество действительных чисел не является счетным
множеством.
4. Множество
M
, состоящее из всех строк (x
1
,x
2
,..., x
n
) произвольной
длины
n≥0,
где
x
i
N,
является счетным множеством.
5. Пусть
A
– конечный алфавит и
X
– множество всех слов в
алфавите
A
. Тогда множество
X
является счетным множеством.
► Пусть
M
– бесконечное множество конструктивных объектов,
являющихся множеством входных объектов некоторого
алгоритма. Множество
M
можно рассматривать как множество
слов в некотором алфавите. По пункту 5) множество
M
является
счетным множеством.
Алгоритмы и функции
► Пусть имеется некоторый алгоритм
A
. На его
вход поступает объект
P
– набор данных
u
1
,u
2
,...u
n
.
Каждый конструктивный объект
u
i
есть слово в некотором алфавите
W
. Слова в
алфавите
W
образуют счетное множество и
занумерованы натуральными числами. Поэтому
каждый конструктивный объект
u
имеет номер
x
N.
Такая операция присвоения номеров
называется кодированием объектов. Число
x,
присвоенное объекту, называется его кодовым
номером.
Алгоритмы и функции
(продолжение)
► Вместо конструктивных объектов
u
1
,u
2
,...,u
n
во
всевозможных вычислениях можно
рассматривать их кодовые номера
x
1
,x
2
,..., x
n
.
Предположим на вход алгоритма
A
поступила
строка конструктивных объектов
u
1
,u
2
,...,u
n
, а
на выходе алгоритма получен объект
v
с
номером
y.
Переходя к кодовым номерам,
можно считать, что на входе была строка из
n
натуральных чисел (
x
1
,x
2
,..., x
n
), а на выходе
число
y
N.
Алгоритмы и функции
(продолжение)
► Если учесть обычное определение функции
f(x
1
,x
2
,..., x
n
)
на множестве
N
как правило, которое каждому набору аргументов
(
x
1
,x
2
,..., x
n
) ставит в соответствие значение функции, то получаем
следующую возможную точку зрения на понятие алгоритма:
► Алгоритм
A
вычисляет некоторую
n
-арную функцию
f(x
1
,x
2
,..., x
n
)
,
определенную на множестве
N.
► Слова «определенную на множестве N» означают, что
вместо переменных подставляются натуральные числа.
Из вышесказанного понятно, почему в теории алгоритмов
функции, определенные на множестве натуральных чисел,
являются одним из основных предметов обсуждения.
Частичные функции
► Частичной
n
-арной функцией
f,
заданной на множестве
натуральных чисел, называется правило, которое
некоторым наборам натуральных чисел (
x
1
,x
2
,..., x
n
)
ставит в соответствие однозначно определенное число
f(x
1
,x
2
,..., x
n
)
N.
► Множество
X
, состоящее из всех наборов
(x
1
,x
2
,..., x
n
),
для которых существует значение функции, называется
областью определения функции
f
и обозначается
через
Dom(f).
Множество всех значений функции
f
называется областью значений функции
f
и
обозначается через
Ran(f).
Частичные функции
(продолжение)
► Назовем функцию
f
всюду определенной, если
ее значение определено при любом наборе
аргументов. Поэтому частичная функция
f(x
1
,x
2
,..., x
n
)
всюду определена тогда и только
тогда, когда
Dom(f)=N
n
.
► При
n=0
мы будем рассматривать всюду
определенную нуль-арную функцию
f,
не
имеющую аргументов. Тогда значения функции
f
не могут изменяться и равны некоторому
числу a. В этом случае функция
f
(функция
выделения числа a) отождествляется с числом
a.
Вычислимые функции
► Функция
f(x
1
,x
2
,..., x
n
)
называется вычислимой, если существует
алгоритм
A,
вычисляющий функцию
f.
► Слова «алгоритм A вычисляет функцию f» означают следующее:
1) если на вход алгоритма
A
поступает набор аргументов
(x
1
,x
2
,..., x
n
)
из области определения функции
f,
то алгоритм
останавливается и выдает результат
f (x
1
,x
2
,..., x
n
);
2) если на вход алгоритма
A
поступает набор аргументов вне
области определения функции
f,
то алгоритм работает бесконечно
или останавливается без выдачи результата.
► Определение вычислимой функции основывается на понятии
алгоритма, которое является интуитивным понятием и не имеет
пока строгого определения. Поэтому верно следующее утверждение.
► Понятие вычислимой функции является интуитивным понятием, не
имеющим строгого определения.
Лекция 3. Примитивно
рекурсивные функции
►Исходные функции. Рассмотрим некоторый набор
простейших функций, вычислимость которых
очевидна.
Функция следования. Рассмотрим функцию
s(x),
заданную правилом
s(x)=x+1
для всех натуральных
x.
Эта функция очевидно
вычислима, т.к. алгоритм ее вычисления состоит из
простейшего действия«добавления к
x
палочкам
еще одной палочки». Функция
s(x)
называется
функцией следования.