Введение Основные понятия и проблемы теории алгоритмов icon

Введение Основные понятия и проблемы теории алгоритмов




НазваниеВведение Основные понятия и проблемы теории алгоритмов
страница1/5
Дата конвертации02.06.2013
Размер0.7 Mb.
ТипДокументы
источник
  1   2   3   4   5

Введение

Основные понятия и проблемы теории алгоритмов



На самых ранних этапах развития математики, в ней стали возникать различные вычислительные процессы чисто механического характера; с их помощью искомые величины ряда задач вычислялись последовательно из данных исходных величин по определенным правилам и инструкциям. Со временем все такие процессы получили название алгоритма (алгоритма).

Например, правила выполнения арифметических операций над многозначными числами, алгоритмы нахождения наибольшего общего делителя двух положительных натуральных чисел, наибольшей общей меры двух отрезков, наибольшего общего делителя двух много членов; разложение натурального числа на простые множители, извлечение квадратного корня из натурального числа, решения системы уравнений методом последовательного исключения неизвестных и т.п.

До 30-х годов XX века, понятия алгоритма в интуитивном смысле было достаточно и в своей основе оно не менялось, так как для определения является ли объект алгоритмом или нет, достаточно знать свойства алгоритма.

А) алгоритм– это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задается исходная система величин, а в каждый следующий момент система величин получается по определенному закону (программе из системы величин, имевшихся в предыдущий момент времени (дискретность алгоритма));

Б) система величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется системой величин, полученных в предшествующие моменты времени (детерминированность);

В) закон получения последующей величины из предшествующей должен быть простым и локальным (элементарность шагов алгоритма);

Г) если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма (направленность алгоритма);

Д) начальная система величин может выбираться из некоторого потенциально бесконечного множества (массовость алгоритма)

В начале XX века стали усложняться объекты, которыми оперировали алгоритмы (векторами, матрицами, множествами, функциями), как следствие –возникли вопросы об элементарности шагов алгоритма (например, можно ли считать элементарным шагом взятие интеграла или транспонирование матрицы?), о том, что понимать конечностью и однозначностью алгоритма. Возникла мысль, что не все задачи имеют алгоритмическое решение. Доказательство факта отсутствия алгоритма потребовало его точного определения, попытки решить эту проблему привели к появлению теории алгоритмов, которая вместе с математической логикой, объединенной в метаматематику, обосновывают методы математики математическими методами. С развитием вычислительной техники выяснилось, что в ее основе должна лежать теория алгоритмов, так как современные ЭВМ могут решать только алгоритмически решаемые задачи.

Оказалось, что теория алгоритмов тесно связана с рядом разделов лингвистики, физиологии мозга и психологии, философии, естествознания. Например, достаточно старые вопросы о том, является ли мозг сложной машиной, как он работает, в чем состоит разница между трудом творческим и механическим, в первом приближении теперь часто формулируют следующим образом: можно ли принципиально построить машину (Тьюринга), перерабатывающую поступающую информацию также как головной мозг какого-нибудь животного. Ясно, что теория алгоритмов не может дать ответы на эти вопросы, но она помогает отчетливее понять суть вопросов такого рода.

В середине 30-х годов XX века усилиями математиков: Давида Гильберта, а Чёрча, Алана Тьюринга, Эмиля Поста, С. Клини, Андрея Андреевича Маркова и других, задача точного определения алгоритмов была решена. Основной идеей всех решений было построение алгоритмической модели, которая содержала бы конечный набор конкретных шагов, способ определения следующего шага, способ записи шагов и т.д.

Поиск велся в 3-х направлениях, которые и определили три типа алгоритмических моделей:

  1. направление основано на арифметизации алгоритма, так как любые данные можно закодировать целыми числами, то шаги здесь – известные арифметические операции, а их последовательность задается формулой. Сама формула строиться при помощи двух приемов:

  • суперпозиции;

  • рекурсии.

Суперпозиция – подстановка одной формулы в другую, то есть вводиться набор элементарных операций и с помощью подстановок строятся более сложные выражения. Например, (ab)+(c/d) – есть суперпозиция операций: x+y, xy, x/y.

Рекурсия задает функции через самих себя. Например,

n!=F(n)=.

Функции, которые можно построить их целых чисел, арифметических операций с помощью рекурсии и суперпозиции называются рекурсивными. Исторически они являются первыми уточнениями понятия алгоритма, то есть универсальными алгоритмическими моделями.

  1. Направление основано на мысли, что алгоритм – это то, что может быть выполнено машиной. Э. Пост и А. Тьюринг, практически одновременно (1936-37 г.г.) предложили конструкции двух абстрактных машин, предложив считать их алгоритмическими моделями. Машина состоит из памяти (ленты разбиты на ячейки), и считывающей головки, которая осматривает ячейки памяти и в зависимости от их содержимого и состояния машин, стирает увиденное или записывает новый элемент, или оставляет старое значение.

  2. Направление близкое ко II-му, но отвлекается от конкретных машинных механизмов. Преобразование данных преобразование данных представляется как система подстановок, заменяющих одну группу символов другой. Наиболее известные – Нормальные алгоритмы Маркова.

Все задачи принято делить на два класса:

  • Связанные с вычислением функции;

  • Связанные с распознаванием принадлежности объекта множеству.

Хотя второй случай можно свести к первому, деление на два класса позволяет ввести два важных понятия:

^ Вычислимая функция;

Разрешимое множество.

Функция называется вычислимой, если существует алгоритм ее вычисляющий. Поскольку понятие алгоритма является интуитивным, то и понятие вычислимой функции также интуитивно.

Множество, называется разрешимым, если существует алгоритм по определению принадлежности элемента данному множеству.

В 1936 году Чёрчем был сформулирован тезис о том, что любую вычислимую функцию можно представить как рекурсивную. Так как в отличии от понятия вычислимой функции понятие рекурсивной функции является строгим, обычная математическая техника позволяет иногда непосредственно доказать, что решающая задачу функция не может быть рекурсивной, а значит задача алгоритмически неразрешима. Точное описание класса частично рекурсивных функций вместе с тезисом Чёрча дает одно из возможных решений задачи об уточнении понятия алгоритма.

В 1937 году Тьюринг сформулировал тезис о том, что для всякой вычислимой функции существует машина Тьюринга, его вычисляющая. Доказать эти тезисы нельзя, так как понятие вычислимой функции не формализовано, но косвенным свидетельством их истинности являются строго математические теоремы вида: «Любую рекурсивную функцию можно вычислить на некоторой машине Тьюринга»;

«Для любой задачи, решаемой на машине Тьюринга, существует нормальный алгоритм Маркова» и т.п.

В теории алгоритмов установлен факт, что в универсальной алгоритмической модели всегда существует универсальный алгоритм, способный моделировать работу любого другого алгоритма. Практически этот шаг означает, что возможно построение универсальных вычислительных систем, способных выполнять любой другой алгоритм.

Появление точного понятия «алгоритма», позволило доказать алгоритмическую неразрешимость некоторых задач. Алгоритмически неразрешимые проблемы существуют и в самой теории алгоритмов:

Например, а) «проблема останова»: существует ли алгоритм, который по алгоритму а и аргументу х определяет, остановиться ли алгоритм а;

Б) «проблема эквивалентности алгоритмов»: можно ли построить алгоритм, который по двум алгоритмам определяет, вычисляют ли они одну и ту же функцию.

Более общей является теорема Райса

Теорема Райса:

Никакое свойство вычислимой функции не является разрешимым.

То есть, какое бы свойство функции мы не взяли (периодичность, ограниченность, монотонность), нельзя алгоритмически (по алгоритму вычисления функции) определить обладает ли она заданным свойством. Общая неразрешимость задана неоднозначно (означает, что неразрешимы частные случаи)

Литература:

  1. Мальцев А.И. Алгоритмы и рекурсивные функции. – 2-е изд. – М: Наука, 1986.– 368 с.

  2. Игошин В.И. Математическая логика и теория алгоритмов. –Саратов, Академия Наук, 1991.

  3. Игошин В.И. Задачник-практикум по Математической логике и теории алгоритмов. – Саратов, Академия Наук,1991

  4. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М: Физматлит, 2001.


Глава 1. Примитивно рекурсивные функции и рекурсивно-перечислимые множества.

§ 1 Функции и операции.

Здесь с целью установления терминологии и употребляемой далее символики установим ряд исходных понятий.

  1. Алфавит. Слова.

Упорядоченная конечная последовательность символов называется алфавитом. Последовательность букв называется словом. Длина слова – количество входящих в него символов. Над словами выполнима операция конкатенации (объединение, склейка). Для удобства вводят понятие пустого слова. Слово α называется подсловом слова β если найдутся два возможно пустых слова γ и δ, таких, что β=γαδ (1). Если γ – наименьшее из возможных, говорят о первом вхождении α в β. Пусть разложение (1) соответствует первому (k-му) вхождению α в β. Тогда γμδ может быть получено заменой в β первого (k-того) вхождения α на слово μ. Операция называется подстановка.

  1. Кодирование.

Теория алгоритмов имеет дело со словами в конечном алфавите.

Существуют математические объекты, которые не удовлетворяют рассмотренному определению слова в некотором алфавите. Это, например, такие важные объекты, как например, рациональные числа, функциональные операторы, действительные числа. Тем на менее ряд таких объектов может быть охарактеризован конечным числом целочисленных параметров, то есть словами в конечном алфавите. Например, алфавит из одного знака: |. Сопоставим с любым словом длины n+1 натуральное число n –

Говорят, что указанное слово изображает число n, или является кодом числа n. Аналогично можно рассмотреть двухбуквенный алфавит 0,1,а в качестве кода натурально числа n взять его двоичное представление. Но уже не любое слово будет являться кодом. Например, 01- не является кодом никакого натурального числа.

Введем двухсимвольный алфавит из символов |, /. Словом вида / условимся называть код рационального числа n/m. Здесь уже не только не любое слово является кодом, но и одному слову соответствует бесконечно много рациональных чисел: ½=||/|||; |||/|||||=½

Во всех рассмотренных случаях выполнилось общее требование при кодировании. По заданному коду объект восстанавливается однозначно.

ОПР: Пусть τ – совокупность некоторых объектов, А – какой-нибудь конечный алфавит. Закодировать совокупность τ в алфавите А – это значит задать однозначное отображение χ некоторого множества υχ слов в алфавите А на совокупность τ . Слово α из множества υχ называется кодом объекта χ(α) при кодировании χ.

В этом определении не требуется, чтобы отображение χ было однозначным, поэтому может случиться, что один и тот же объект будет иметь несколько различных кодов.

Рассмотрим примеры:

  1. Кодирование слов в многобуквенном алфавите. Пусть дан алфавит . Будем считать словом в алфавите A последовательность символов, начинающуюся с «1», заканчивающуюся «0» и не имеет последовательность вида , n>1. Тогда обозначим последовательность из k единиц . Тогда любое слово в алфавите A будет иметь вид . Тогда в алфавите B его закодировать можно словом –

Полученное кодирование однозначно.

Например, В={а, б, в, г, д, …}

Возьмем слово 120110150 – бад

2. Кодирование последовательности слов. Пусть A – некоторый алфавит; B – получен из него добавлением нового символа . Тогда совокупность из n символов в алфавите A – α1α2…αn можно закодировать одним словом вида – α1α2αn


  1. Функции. Термы.

Пусть А и В – какие-либо множества, например, совокупности всех слов в подходящих алфавитах. Совокупность пар вида , где aA, bB, называется декартовым произведением A на В и обозначается через АхВ. Аналогично, если А1, А2, …, Аm – некоторые множества, взятые в определенной последовательности, то совокупность (((…(А1 х А2) х А3х…х Аm) называется декартовым произведением множеств и обозначается А1 х А2 х А3х…х Аm. Если все множества совпадают друг с другом, то их произведение называется декартовой m-ой степенью множества А.



Декартово произведение



Пусть даны два множества X, Y. Если некоторым элементом множества X поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана частичная функция. Если область определения функции совпадает с X, то функцию называют всюду определенной. Частичные функции из Xn в Y называют частичные функции от n переменных, а функция называется n-местная частичная операция на X.

Частичные функции из Х х Х х Х х…х Х=Х(n) в Y называются частичными функциями от n переменных или n-местными функциями из X в Y. Частичная функция из Х(n) в Y называется n-местной частичной операцией на Х.

Для записи функций введем алфавит из символов трех типов:

  1. Предметные символы:

A, b, c, x, y, z, x1 , x2,..z1, …

Первые или последние буквы латинского алфавита с индексами или нет.

  1. Функциональные символы:

С верхними или нижними индексами или без них:

F, g, h, f2, ,…

Где верхний индекс определяет количество переменных функции, например, fn – n-местный функциональный символ.

3. Круглые скобки и запятая – (, ), ,

Слова, записанные в этом алфавите по определенным правилам, называются ТЕРМАМИ.


ОПР: 1. Однобуквенное слово из представленных символов – есть терм (длины - 1);

2. Слово длины «s» – есть терм, если оно имеет вид , есть термы длины меньше s, а f – n-местный функциональный символ.

Например, пусть a, b предметные символы, а f1, g2 – одноместный и двуместный функциональные символы, тогда слова:

a, b, f(a), f(b), g(a,b), g(f(a),g(a,b)) – есть термы соответственно длины: 1, 1, 4, 6, 14.

Введем понятие значения терма при заданных значениях предметных и функциональных символов. По определению задать значение предметного символа – это значит указать некоторое непустое множество, называемое основным множеством, и сопоставить с рассматриваемым символом некоторый элемент этого множества. Этот элемент и называется значением данного символа.

ОПР: 1. Задать значение предметного символа – это, значит, указать некоторое не пустое множество, называемое основным и сопоставить с просматриваемым символом некоторый элемент этого множества;

2. Задать значение n-местного функционального символа, значит сопоставить с ним n-местную операцию, определенную на основном множестве;

3. Значение терма длины 1, есть значение составляющего этот терм предметного символа;

Предположим, что основное множество Х выбрано, значения всех входящих в терм предметных и функциональных символов на этом множестве определены и терм  имеет вид где f – n-членный функциональный символ, а – термы меньшей длины. По индукции мы можем считать, что значения термов уже определены и равны некоторым элементам x1, x2,…xn множества Х. По условию символу f поставлена в соответствие n-метсная операция f0, определенная на Х. Значение этой операции в точке (x1, x2,…xn) будет каким-то элементом х из Х. Этот элемент х и будет значением терма  при заданных значениях предметных и функциональных символов.

4. Значением терма есть значение сопоставление f операции f0 в т (x1, x2,…xn), где xi значение терма

Если в качестве значений функциональных символов взяты частичные операции, определенные не всюду на множестве, то есть значение терма может быть не определено.

5. Значение терма считается не определенным, если значение хотя бы 1-го не определено или не определено значение операции f0 в т (x1, x2,…xn), где xi значение терма

В арифметике натуральных чисел, термы (2+8):2; (2х7)-7– имеют значения 5 и 7 соответственно, а значения термов 5-(3+3); 2:3; 3:(2+2); 5+(4:5) – не определены.

Значение терма (((3х)+y):y)+4 – при значениях 2 и 3 предметных символов x и y определено; и не определено, например, при значениях 2 и 5.

Имея несколько операций, заданных на некотором множестве Х можно при помощи термов записать бесконечное множество новых операций, определенных на том же множестве. В дальнейшем будем рассматривать операции, заданные на множестве натуральных чисел и принимающие натуральные значения.


§ 2 Построение примитивно-рекурсивных функций.

Назовем, простейшими следующие числовые функции, заданные над множеством N:

  1. Функция следования: S1(x)=x+1;

  2. Нуль функция: Оn(x1,x2,…,xn)=0,  xi из N;

  3. Функция проекции: (x1,x2,…,xn)= xm, где (1mn).

Операции над числовыми функциями будем называть операторами, в качестве операторов выберем операторы суперпозиции и рекурсии.

  1. ^ Суперпозиция частичных функций.

Пусть заданы n частичных функций i=1, ..n, определенные на множестве A, со значениями в множестве B и пусть на B определена частичная функция со значениями в множестве C. Пусть gm – частичная функция от m переменных, определенная на множестве A, со значениями в множестве C.

Говорят, что функция g получается операцией суперпозиции или подстановки из функций f1,f2,…,fn, если

g(x1,x2,…,xm)=f(f1 (x1,x2,…,xm),f2 (x1,x2,…,xm),…,fn (x1,x2,…,xm)).

Если через Fn обозначить множество всех частичных числовых функций от n переменных, то суперпозиция является всюду определенной функцией из множества Fn и количество функций Fm;



Операцию подстановки будем обозначать Sn+1, где верхний индекс означает число функций.

Примеры:

1.Пусть заданы обычные числовые функции f1(x,y)=x+y, f2(x,y)=xxy. Функция x1xx2+x3 (термальное представление) может быть представлена через оператор подстановки и элементарные функции в виде:

S3 (+,S3(x,, ), ) – операторный терм

2.Найти значение S2(S1,01).

Для этого значение простейшей функции 01 должно быть подставлено в S1 (x)=x+1. Но 01(x)=0, следовательно, h(x) = S2(S1, 01) = S1(01) = 0+1= 1.

3. Найти значение S3(I22,I1 1,01). В этом случае конечная функция будет двуместной (n = 3–1 =2), следовательно, h(x1,x2) = I2 2(I11,01) = I22(x1,0) = 0


  1. Оператор примитивной рекурсии.

Говорят, что n+1 местная функция f получается из n местной функции g и n+2 местной функции h. Если выполняется:

f(x1,…, xn ,0) = g(x1,…, xn), (1)

f(x1,…, xn,y+1) = h(x1,…, xn , y, f(x1,…, xn ,y)) (2)

Если n=0, то (1) и (2) примет вид:

f(0)=a; (1)

f(y+1)=h(y,f(y)). (2)

Выражения (1), (2), (1), (2) называют схемой примитивной рекурсии


Пример: f(m)=am, по определению а(0)=1 (a=1) f(m+1)=am а=h(f(m)).

Равенства (1),(2) выражают через оператор примитивной рекурсии в виде:

f=R(g,h)

R – операторный символ.

Если g и h заданы, то функция f строится по ним однозначно. Действительно, для этого достаточно вычислить последовательно числа:

b0=f(x1, x2,…xn,0)=g(x1, x2,…xn)

b1=f(x1, x2,…xn,1)=h(x1, x2,…xn,0,b0) (3)

b2=f(x1, x2,…xn,2)=h(x1, x2,…xn,1,b1)

… … …

bm+1=f(x1, x2,…xn,m)=h(x1, x2,…xn,m,bm)


Отметим :

  1. Если g и h всюду определены, то и f всюду определена;

  2. Если g и h вычислимы, то и f вычислима, причем алгоритмически по (3).


^ Определение примитивно-рекурсивных функций.

Пусть задана система G – частичных функций. Частичная функция f называется примитивно-рекурсивной относительно системы G, если она получена с помощью простейших функций (S,O,) из функций системы G конечным числом операций подстановки и примитивной рекурсии (S, R).

Если G пусто, то f называют примитивно-рекурсивной.

Операции S и R примененные ко всюду определенным функциям также дают всюду определенные функции, но тогда все примитивно-рекурсивные функции всюду определены. Из определения следует, что операции S и R, примененные к частичным функциям (примитивно-рекурсивным относительно G) вновь дают функции примитивно-рекурсивные относительно G.

Рассмотрим ряд основных функций, задаваемых на множестве натуральных чисел:

^ 1. Постоянные функции:

Для n-местной функции Оn(x1,x2,…,xn)=0 имеем представление On=S2(O1, )

Произвольная n местная постоянная функция fn=a (или f(x1,x2,…,xn)=a представима в виде: f=S(S…(O (x1,x2,…,xn ))…)=a. Так как f получена суперпозицией функций S(x), Оn(x1,x2,…,xn) она является примитивно-рекурсивной всюду определенной функцией.

Значит, все постоянные функции примитивно рекурсивны.

  1. ^ Двуместная функция f(x,y)=x+y может быть получена по схеме

f(x,0)=x=,

f(x,y)=x+(y+1)=(x+y)+1=S(x+y),

то есть f получена по схеме примитивной рекурсии из элементарных функций и S(x). Значит, всюду определена и примитивно-рекурсивна.

  1. ^ Двуместная функция f(x,y)=xy.

Рассмотрим схему: f(x,0)=x0=0=O(x)

F(x,y+1)=x(y+1)=xy+x=f(x,y)+x

Таким образом, f получена по схеме примитивной рекурсии из элементарной функции и примитивно-рекурсивной функции значит примитивно-рекурсивна и всюду определена.

  1. f(x,y)=xy

f(x,0)=x0=1 – постоянная

f(x,y+1)=xy+1=xyx=f(x,y)x;

f получена примитивной рекурсией из постоянной функции и операции умножения.

  1. Арифметическое вычитание не всегда определено на множестве натуральных чисел, поэтому введем всюду определенную на N операцию «усеченного вычитания»:




Покажем предварительно, примитивную рекурсивность функции f(x)=x–1.

f(0)=0

f(x+1)=x+1–1=x=

Функция f(x) удовлетворяет примитивно-рекурсивной схеме с примитивно рекурсивными начальными функциями O1, , а значит примитивно рекурсивна.

f(x,0)=x–0=x=;

f(x,y+1)=x– (y+1)= x–y–1 = (x–y)–1=f(x,y) –1;

Эти тождества показывают, что двуместная функция x–y возникает примитивной рекурсией их функций и f(x,y) –1 обе последние функции примитивно рекурсивные. Поэтому и функция усеченной разности (x–y) примитивно рекурсивна.

  1. Можно показать, что примитивно рекурсивны функции:

; ; |x-y|=|x–y|+|y–x|

Задача:

Найти значение функции f(3,2), если она задана следующими соотношениями:

f(0,x) = 0

f(y+1,x) = f(y,x) + x

В данном случае g(x) = 0, h(x,y,z) = y + z. Т.к. f(0,x) = g(x) = 0 при любом x, то и f(0,2) = 0, а другие значения можно вычислить последовательно:

f(1,2) = h(1,0,2)= 0+ 2 = 2

f(2,2) = h(2,2,2)= 2+ 2 = 4

f(3,2) = h(3,4,2)= 4+ 2 = 6

Несложно доказать, что в данном примере f(x,y)=x · y


§ 3 Операция минимизации. Частично рекурсивные функции.

Пусть задана некоторая функция f(x,y). Зафиксируем значение x и выясним, при каком y значение f(x,y)=0. Более сложной оказывается задача отыскания наименьшего из тех значений y, при которых f(x,y)=0. Поскольку результат решения такой задачи, очевидно, зависит от x, то и наименьшее y является функцией x. Примем обозначение:

– читается: «наименьшее y такое, что f(x,y)=0», а называют -оператором или оператором минимизации.

Подобным же образом определяется функция многих переменных:

Пусть fn – n-местная (n≥1) частичная числовая функция. Зафиксируем первые n-1 значений функции и рассмотрим

f(x1,x2,…xn-1,y)=xn (1)

для решения этого уравнения будем вычислять последовательно, полагая y=0,1,2,… . Наименьшее число a для которого выполняется

f(x1,x2,…xn-1,a)=xn (2) обозначим через μy(f(x1,x2,…xn-1,y)=xn) (3)

Описанный процесс может привести к следующим результатам:

  1. f(x1,x2,…xn-1,0) – не определено;

  2. f(x1,x2,…xn-1,y) – определено для y=0,1,2,…,a-1, но отличны от, а не определено для y=a;

  3. f – определена для всех y=0,1,2,… и отличны от xn.

Во всех этих случаях значение выражения (3) считается неопределенным, а остальных процесс обрывается и дает некоторое наименьшее y=a, которое и принимается за значение μy.

Например:

1. f(x1,x2)= x1+x2;

φ (x1,x2)= μy(x1+y=x2), тогда

φ(2,5)=3; φ(5,2) – не определено по 3-му случаю.

φ(x1,x2)= x2–x1;

  1. f(x)=;

φ (x)= μy(=x);

φ (0)=0; φ (1)=1; φ (2)=4; φ (x)=x2

Итак, значение (3) при заданной f , зависит от x1,x2,…xn и поэтому есть частичная функция от аргументов x1,x2,…xn. Эту функцию обозначим через Mf, где M – символ операции, переводящий функцию f в функцию Mf. Если заданная функция одноместна, то функцию Mf обозначают – f-1 и называют обращением функции f или обратной функцией. Таким образом,

f-1(x)= μy(f(y)=x).

Например:

для одноместной функции S1(x) обратной будет функция

для двухместной функции f(x1,x2)= x1+x2 получаем:

M(–)=S3(+,,)

Задача:

Функция f(x,y)=x - y, может быть получена с помощью оператора минимизации:

f(x,y) =μ z (y+z=x) =μ z [ I32(x,y,z) + I33(x,y,z) = I31(x,y,z)]

Вычислить, f(7,2), т.е. значение функции при y = 2 и x = 7. Положим y = 2, а x будем придавать последовательные значения:

z = 0,




2 + 0 = 2 7,

z = 1,




2 + 1 = 37,

z = 2,




2 + 2 = 47,

z = 3,




2 + 3 = 57,

z = 4,




2 + 4 = 67,

z = 5,




2 + 5 = 7=7.

Таким образом, найдено значение функции f(7,2) = 5.


^ Основное определение:

Частичная функция f, называется частично-рекурсивной относительно совокупности частичных функций G, если она получена из функций системы G и элементарных функций конечным числом операций суперпозиции S, рекурсии R, минимизации M.

Если G – пусто, то f называют просто частично-рекурсивной.

^ Из определения следует:

  1. Любая частичная функция примитивно рекурсивная на множестве G, является и частично рекурсивной относительно G. В частности, все примитивно рекурсивные функции являются частично рекурсивными;

  2. Операции S,R,M, применяемые к функциям частично рекурсивным относительно G, так же дают функции частично рекурсивные относительно G.

  3. Класс частично рекурсивных функций шире класса примитивно рекурсивных , так как последние всюду определены, а среди частично рекурсивных встречаются не всюду определенные и вообще нигде не определенные.

Если функция всюду определена и частично рекурсивна, то она называется общерекурсивной. Таким образом, все примитивно рекурсивные функции – общерекурсивны (но не наоборот).

Понятие частично-рекурсивной функции одно главных понятий теории алгоритмов: с одной стороны любая стандартно заданная частично рекурсивная функция вычислима с помощью некоторых процедур механического характера, обладающих свойствами алгоритма в интуитивном смысле; с другой стороны какие бы классы точно определенных алгоритмов до сих пор ни строились всегда оказывалось, что числовые функции, вычисляемые с помощью этих алгоритмов оказывались частично рекурсивными. Поэтому в настоящее время общепринятой является следующая естественно научная гипотеза:
  1   2   3   4   5



Похожие:

Введение Основные понятия и проблемы теории алгоритмов iconОсновные понятия Основные понятия
Система это любой объект, состоящий из взаимосвязанных частей и существующий как единое целое
Введение Основные понятия и проблемы теории алгоритмов iconВопросы к экзамену «Управленческие решения» Наука о принятии управленческих решений: характерные отличия, основные подходы к управлению
Основные понятия теории принятия решений: процесс принятия решений, понятие альтернативы и варианта, классификация и цели управленческих...
Введение Основные понятия и проблемы теории алгоритмов iconТема Основные понятия и методы теории информатики и кодирования Понятие информации
Если параметр сигнала принимает ряд последовательных значений и их конечное число, то сигнал называется
Введение Основные понятия и проблемы теории алгоритмов iconЗакон Республики Беларусь «Об обращениях граждан» глава 1 общие положения статья Основные понятия, применяемые в настоящем Законе, и их определения
Для целей настоящего Закона применяются следующие основные понятия и их определения
Введение Основные понятия и проблемы теории алгоритмов iconАдаптация в школе. Основные проблемы, возникающие
Основные проблемы, возникающие в период адаптации к условиям обучения в средней школе
Введение Основные понятия и проблемы теории алгоритмов iconПсихологические теории познания: проблемы, модели, эксперименты. Восприятие Семест Тема12. Лекция7
...
Введение Основные понятия и проблемы теории алгоритмов iconПсихологические теории познания: проблемы, модели, эксперименты. Внимание Семест Тема14. Лекция9
Психологические теории познания: проблемы, модели, эксперименты. Внимание Семест Тема14. Лекция9 Феноменология познавательных процессов....
Введение Основные понятия и проблемы теории алгоритмов iconПеречень вопросов к экзамену по дисциплине мапо на примере
Понятия социальной, экономической проблемы. Конкретизируйте переменные и параметры изученной общей динамической модели процесса решения...
Введение Основные понятия и проблемы теории алгоритмов iconМетодические рекомендации по написанию курсовых и выпускных квалификационных работ по специальности 031800 логопедия
Охватывает основные проблемы теории, методики и организации коррекционно-логопедической работы. Методические указания по написанию...
Введение Основные понятия и проблемы теории алгоритмов iconУрок математики в 6-ом классе Введение понятия координатной плоскости, координаты точки на координатной плоскости
Введение понятия координатной плоскости, координаты точки на координатной плоскости
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©sov.opredelim.com 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы