WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

КАЛИНИНГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

В.Ф. ПОНОМАРЁВ

ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ

Утверждено Ученым советом университета в качестве учебного пособия по

дисциплине «Математическая логика и теория алгоритмов» для студентов

специальностей

230101.65- Вычислительные машины, комплексы, системы и сети,

230102.65-Автоматизированные системы обработки информации и управления Калининград Издательство КГТУ 2005

КАЛИНИНГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

В.Ф. ПОНОМАРЁВ

ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ

Утверждено Ученым советом университета в качестве учебного пособия по дисциплине «Математическая логика и теория алгоритмов» для студентов специальностей 230101.65- Вычислительные машины, комплексы, системы и сети, 230102.65-Автоматизированные системы обработки информации и управления Калининград Издательство КГТУ ББК 32. УДК 681. Пономарев В.Ф. Основы теории алгоритмов: учебное пособие. - Калининград: Изд-во КГТУ, 2005.- 53с.

Учебное пособие предназначено студентам, изучающим «Математическую логику и теорию алгоритмов». В нем рассмотрены три алгоритмических модели: рекурсивные функции, машина Тьюринга и нормальные алгоритмы Маркова. Эти модели составляют фундамент теории алгоритмов и служат основой для разработки и анализа вычислительных алгоритмов практических задач. На многочисленных примерах показаны процедуры вычисления простейших числовых функций. В заключении приведены оценки временнй и ёмкостной сложности вычислительных алгоритмов.

Рис.-26, табл.-16, список лит.-10 название Рецензент - Жебелев С.И., к.ф.-м. н., доцент кафедры систем управления и вычислительной техники Калининградского государственного технического университета © Калининградский государственный технический университет, 2005г.

© Пономарев В.Ф., 2005г.

Вениамин Федорович Пономарев

ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ

Предисловие Понятие "алгоритм" принадлежит к числу основных понятий математики и занимает одно из центральных мест в организации вычислительных процессов и проектировании разнообразных дискретных устройств.

Еще в IX веке великий узбекский ученый Мухаммед бен-муса аль-Хорезми разработал систему правил четырех арифметических действий над числами в десятичной позиционной системе счисления (он жил приблизительно с 783 по 850г.). Эти правила предписывали строгую последовательность действий для получения искомого результата. Так возникло понятие "алгоритм" в честь арабского имени аль-Хорезми.

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

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

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

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

Выделяют три основных типа алгоритмических моделей:

первый — рекурсивные функции — связывает понятие алгоритма с элементарными вычислительными операциями на множестве целых положительных чисел;

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

третий — нормальный алгоритм Маркова — связывает понятие алгоритма с элементарными преобразованиями слов произвольного алфавита, замещая части или всего слова другим словом.

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

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

Для закрепления полученных знаний рекомендуется самостоятельно решить задачи, представленных в «Вопросы и задачи» и сверить их с решениями, представленными в «Ответы и решения». Кроме того, рекомендуется выполнить индивидуальное задание по разработке программы вычисления простейших функций на машине Тьюринга.

1. Рекурсивная функция - модель алгоритма Рекурсия * есть способ вычисления значения числовой функции по известным значениям независимых переменных аргумента и известному значению функции в некоторой исходной точке.

Известно, что любое число может быть синтаксически представлено цепочкой ("."), где существует только одна синтаксическая переменная —. Поэтому любую вычислимую функцию, заданную на множестве натуральных чисел и принимающую значения на том же множестве принято называть рекурсивной функцией *.

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

Для формирования механизма вычисления рекурсивных функций даны наборы простейших базовых функций: константы, тождества и следования и наборы элементарных операций: суперпозиции, рекурсии, минимизации и итерации.

Функция константа. Если f={(x1, x2,..., xn, у)| xiN, yN}=Cn или y = f(x1, x2,…xn)=Cn, то любым значениям независимых переменных аргумента функции ставится в соответствие значение функции, равное постоянной величине (константе) - Сn, где n –число независимых переменных аргумента. Чаще всего Cn=0. Поэтому её называют также нуль-функцией. Например, если f={(x1, x2, x3, у)}=C3, то для x1 = 5, x2 = 4, x3 = 7 и C3 = 0 имеем у=f(5, 4, 7)=0 или, если Сn= при тех же значениях независимых переменных, то y=f(5, 4, 7)=1.

Функция тождества. Если f={(x1, x2,...,, xn, у)| xiN, yN}= I m, то любым значениям независимых переменных аргумента функции ставится в соответствие ее значение, равное значению m-го независимого переменного аргумента, где 1mn – место независимого переменного аргумента в их упорядоченном списке. Поэтому её называют также функцией выбора аргумента. Например, если f={(x1, x2, x3, у)}= I3, то для x1 = 5, x2 = 4, x3 = 7 имеем у = 4, если f={(x1, x2,, x3, у)}= I3, то для x1 = 5, x2 = 4, x3 = 7 имеем у = 7.

Функция следования. Если f={(x, у)| xiN, yN}=(x), то любому значению независимой переменной аргумента ставится в соответствие значение функции, равное числу, непосредственно следующему за числом, являющимся значением независимой переменной. Например, если для f={(x, у)}=(x) дано x = 5, то у = (5+1) = 6, если для f={(x, у)}=(x) дано x = 7, то у = (7+1) = 8.

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

Операция суперпозиции. Если даны функция h от m независимых переменных, т.е. h(m) = (z1, z2,…, zm,, у| ziN, yN), и m функций gi от n независимых переменных, т.е. gi(n) = {(x1i, x2i,..., xni, zij)| xijN, zjiN }, то в результате подстановки функций g1(n), g2(n),…, gm(n) вместо независимых переменных функции h(m) может быть получена новая функция f(n) = (x1, x2,..,, xn, у) от n независимых переменных, т.е.

h(m) = (zi, z2,..., zm, y), g1(n) = (x1, x2,..., xn, z1), g2(n) = (x1, x2,..., xn, z2),

gm(n) = (x1, x2,..., xn, zm)...

h(m) = (g1(n), g2(n),..., gm(n), y) или f(n) = (x1, x2,..., xn, y).

Значения функций g1(n), g2(n),..., gm(n), найденные для данных независимых переменных x1 = a1, x2 = a2,..., xn = an, принять за независимые переменные аргумента функции h(m) и вычислить ее значение, которое принять за значение функции f(n) = (x1. x2,..., xn, y).

Пример 1. Пусть h(1)==(z, y) или y=h(1)(z)=(z) и g(1)==(х, z) или z=g(1)(x)=(х).

Тогда h(1) = (g(1)(x), у) = ((x)) или y = h(1)(g(1)(x))= ((x))=2(х).

При x = 5 имеем z = 5+1 = 6 и у = 6+1 = 7.

Пример 2. Пусть h(2) = (z1, z2, y) или y = h(2)(z1, z2) = (z1z2), Тогда h(2) = (g1exp(1)(x), g2*(1)(x), y) = x23x или y = 3x3.

При x = 2 имеем z1 = 4, z2 = 6 и y = 46 =38 = 24.

Оператор суперпозиции записывают так:

где h(m) = ( z1, z2,..., zm, y) и gi(n) = (x1i (n), x2i (n),..., xni (n), zi).

Основные свойства функций, вычисляемых с помощью оператора суперпозиции:

• если вычислимы функции h f = (x1, x 2,..., x n, y) = Sn (h (m),g1 ),g (n ),...,g (n ) );

ными являются любые операторы подстановки, перестановки и переименования любых независимых переменных аргумента;

• если среди функций gi имеется хотя бы одна частично рекурсивная, то и функция f также будет частичной.

Пример 3. Перестановка и/или переименование независимых переменных аргумента функции h при n=m:h(m) = (zi, z2,..., zm, y), g1(m) = (x1, x2,..., xm, z1) = I3, g2(m) = (x1, x2,..., xm, z2) = I5,

gm(m) = (x1, x2,..., xm, zm) = I m, h(m) = (g1(m), g2(m),..., gm(m), y) или f(m) = (x3, x5,..., xm, y).

Пример 4. Циклическая перестановка независимых переменных аргумента функции h при n = m:

h(m) = (z1, z2,..., zm, y), g1(m) = (x1, x2,..., xm, z1) = I 2, g2 = (x1, x2,..., xm, z2) = I m,

gm-1(m) = (x1, x2,..., xm, zm-1) = I m, gm = (x1, x2,..., xm, zm) = I m, h(m) = (g1(m), g2(m),..., gm(m), y) или f(m) = (x2, x3,..., xm, x1, y).

Пример 5. Введение дополнительной независимой переменной аргумента:

h(m) = (zi, z2,..., zm, y), g1(m+1) = (x1, x2,..., xm+1, z1) = I1 +1,

gm(m+1) = (x1, x2,..., xm+1, zm) = I m+1, h(m) = (g1(m+1), g2(m+1),..., gm(m+1), y) или f(m+1) = (x2, x3,..., xm+1, y).

Операция рекурсии. Если даны n-местная рекурсивная функция g(n) и (n+2)-местная рекурсивная функция h(n+2), то можно найти (n+1)-местную рекурсивную функцию f(n+1), используя схему примитивной рекурсии:

f (n+1) (x, x,..., x, y+1)=h (n+2) (x, x,..., x, y, f (n+1) (x, x,..., x, y)), y 0.

Главным дополнительным аргументом функции h(n+2) является у, который указывает, при каком его значении следует определять значение функции f(n+1)(x1, x2,…, xn, y) для вычисления последующих значений функции f(n+1)(x1, x2,…, xn, y+1).

Оператор рекурсии описывают так:

f n+1 =(x1, x 2,..., x n, y+1)=R(g (n), h (n+2) ), где gi(n)=(x1, x2,..., xn) и h(n+2)=(x1, x2,..., xn, у, f(n+1)(x1, x2,..., xn, у)).

При исполнении операции рекурсии известными являются x1=a1, x2=a2,..., xn=an. Значением функции f(n+1) для нулевого значения главного дополнительного аргумента (y=0) есть значение функции g(n). Значением функции f(n+1) для каждого последующего значения главного аргумента (у+1) следует считать значение функции h, вычисленное по значению главного аргумента у и значению вспомогательного аргумента f(n+1)(x1, x2,..., xn, у). Функции, для вычисления значений которых использовали базовые функции и операторы суперпозиции и примитивной рекурсии, называют примитивно рекурсивными функциями.

При задании примитивно рекурсивного описания функции f(x), зависящей от одной независимой переменной, схема примитивной рекурсии имеет вид:

Пример 6. Вычислить функцию предшествования где символ « » означает оператор усеченного вычитания.

Для этого используем базовую функцию константы: g(0) = C(0) = 0 и базовую функцию тождества: h(у, f (0, у)) = I1 = y, т. е.

f (0, у+1) = h(у, f(0, у)) = у.

Так как функции g и h не содержат независимой переменной х, то:

Если i = у, то f(0, у) = (y 1) = -1(у). Пусть у = 6, тогда f(6) = -1(6) = 6 1= 5.

Так можно вычислять рекурсивную функцию предшествования -1(у)= (y 1) = R(0, у).

Пример 7. Вычислить функцию f (n) = n.

Для этого используем базовые функции g(0)=C1=0 и h(0, y, f (0, y))= (J3,2)= =(y)=y+1.

По схеме примитивной рекурсии:

f(0)=0, f(0+1)=0+1=1, f(1+1)=1+1=2, f(2+1)=2+1=3, f(i+1)=(i+1).

Следовательно, если i=n, то f(n)=(..((0+1)+1)…+1)=n есть примитивно рекурсивная функция, для вычисления которой по схеме примитивной рекурсии использованы нуль-функция, функция тождества и функция следования.

Пример 8. Вычислить функцию f(х) = х + n.

Если g(x, 0) = J2,1 = x и h(x, y, f (x, y))=(J3,2)=(y)=y+1, то по схеме примитивной рекурсии:

f(x, 0)=x, f(x, 0+1)=x+1, f(x, 1+1)=(x+1)+1=x+2, f(x, 2+1)=(x+2)+1=x+3, f(x, i+1)=(x+i)+1=x+(i+1).

Следовательно, если i=n, то f(n)=(…((x+1)+1)…+1)=(x+n) есть примитивно рекурсивная функция, для вычисления которой по схеме примитивной рекурсии использованы базовые функции тождества и следования.

Пример 9. Вычислить функцию сложения f+(x, y) = (x+y).

Для этого используем базовые функции тождества g(x) = I1 = x и следования h(x, у, f+(x, у))=(J3,3) = f+(x, у) + 1, т. е.

f+(x, 0) = g(x) = J1,1= x, f+(x, у + 1) = h(x, у, f+(x, у)) = (J3,3) = f+(x, у) + 1.

По схеме примитивной рекурсии имеем:

f+(x, 0) = g(x)=x, f+(x, 1) = h(x, 0, f+(x, 0)) = x + 1, f+(x, 2) = h(x, 1, f+x, 1)) = x + 2, f+(x, 3) = h(x, 2, f+(x, 2)) = x + 3, ………………………………… f+(x, i) = h(x, (i-1), f+(x, (i -1))) = x + i.

Если i = у, то f+(x, у) = (x+у). Пусть x=3, у=6, тогда f+(3, 6) = 3+6 = 9.

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

Функция f+(x, у) = R(x, (f+(x, у)+1)) = (x+y) является примитивно рекурсивной.

Пример 10. Вычислить функцию усеченного вычитания Для этого используем базовую функцию тождества g(x) = x и примитивнорекурсивную функцию предшествования -1(f(x, у)) = (f(x, y) 1), т. е.

По схеме примитивной рекурсии имеем:

f (x, i) = h(x, i, f (x, i)) = (x (i-1)) 1=x i.

Если i=y, то f (x, y) = x y. Пусть х = 6, y = 3, тогда f (6, 3) = 6 3 = 3.

Так, используя базовую функцию тождества и примитивно рекурсивную функцию предшествования, можно вычислять значение функции усеченного вычитания f (x, y) = R(x, 1 (f (x, y))) = (x y).

Пример 11. Вычислить функцию умножения f* (x, y) = x y.

Для этого используем базовую нуль-функцию g(x) = С1 = 0 и примитивнорекурсивную функцию сложения h(x, y, f* (x, y)) = f+(I3,1, I3,3 )= x + f* (x, y), т.е.

f* (x, y + 1) = h(x, у, f* (x, y) ) = f+(I3,1, I3,3 ) = x + f* (x, y).

По схеме примитивной рекурсии имеем:

f* (x,1) = h(x, 0, f* (x,0) ) = x+0 = x, f* (x,2) = h(x, 1, f* (x,1) ) = (x+x) = 2x, f (x,3) = h(x, 2, f* (x, 2) ) = (x+2x) = 3x, …………………………………………….

f* (x,i) = h(x, (i - 1), f* (x,i 1) ) = (x+(i - 1)x) = ix.

Пусть х=3, y=4. Тогда f* (3, 4) = 3. 4 = 12.

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

Функция f* (x, y) = R(0, f+(x, f* (x, y) )) = (xу) является рекурсивной.

Пример 12. Вычислить функцию f(n)=n!

Если g(x, 0) = 1 и h(x, y, f(x, y)) = f ( (J 3,2 ),J 3,3 ), то по схеме примитивной рекурсии:

f(x, 0)=1, f(x, 0+1)=11=1, f(x, 1+1)=21=2, f(x, 2+1)=32=6, f(x, 3+1)=46= f(i+1)=(i+1)i(i-1)(i-2)…(i-i)=(i +1)!

Если (i+1)=n, то f(n)=n! есть рекурсивная функция, так как для ее вычисления использованы базовые функции константы, тождества и следования и рекурсивная функция умножения.

Пример 13. Вычислить функцию возведения в степень f exp (x, y) = x.

Для этого используем базовую функцию константы g(x)=С1=1 и рекурсивную функцию умножения h(x, у, fexp(x, у))= f (I3,1, I3,3 )=xfexp(x, у):

fexp(x, у+1) = h(x, у, fexp(x, у)) = x fexp(x, у).

По схеме примитивной рекурсии имеем:

fexp(x, 0)=g(x)=1;

fexp(x, 1)=h(x, 0, fexp(x, 0))=x1= x;

fexp(x, 2)=h(x, 1, fexp(x, l))=xx=x2;

fexp(x, 3)=h(x, 2, fexp(x, 2))=xx2=x3, ………………………………………………..

fexp(x, i)=h(x, (i - 1), fexp(x, (i - 1)))=xx(i - 1) = xi.

Если i=у, то fexp(x, y)=xy.

Пусть x=3, у=3, тогда fexp(3, 3)=33 =27.

Так, используя базовую функцию C1 и рекурсивную функцию умножения, можно вычислять значения рекурсивной функции возведения в степень xy =R(1, f (x, fexp(x, y)))=fexp(x, y).

Пример 14. Вычислить функцию Sg(y) = где Sg *(y) – знак переменной y.

Пусть g(x) = С1 = 0 и h(x, y, Sg(x, y)) = С3 = 1, т.е.

По схеме примитивной рекурсии имеем:

Sg(x, i) = h(x, (i-1), Sg(x, (i-1))) = 1.

лат. signum – знак.

Используя две базовых функции константы, можно вычислять знаковую примитивно рекурсивную функцию Sg(y) = 1 для y>0.

Пример 15. Вычислить функцию Sg(y) = 1 Sg(y) = где Sg(y) - инверсия знака y.

Пусть g(x) = C1 = 1 и h(x, у,Sg(x, у)) = C3 = 0, т.е.

Sg(x, y+1) = h(x, y, Sg(x, y).

По схеме примитивной рекурсии имеем:

Sg(x, 1) = h(x, 0,Sg(x, 0)) = 0, Sg(x, 2) = h(x, 1,Sg(x, 1)) = 0, Sg(x, 3) = h(x, 2, Sg(x, 2)) = 0, ……………………………………….

Sg(x, i) = h(x, (i-1), Sg(x, (i-1))) = 0.

Используя две базовых функции константы, можно вычислять знаковую примитивно рекурсивную функцию Sg(y) = 0 для y>0.

Пример 16. Вычислить min{x, у}.

Эту функцию можно вычислить с помощью примитивно рекурсивной функции « » или «Sg»:

min{x, y} = x (x y) или min{x, y} = x Sg(y x) + y Sg(y x).

Тогда min{5, 3} = 5 (5 3) = 3 или min{5,3} = 5 Sg(3 5) + 3 Sg(3 5) = 3.

Тогда min{3, 5} = 3 (3 5) = 3 или min{3,5} = 3 Sg(5 3) + 5 Sg(5 3) = 3.

Функция min{x, у} является рекурсивной.

Пример 17. Вычислить max{x, у}.

Функцию также можно вычислить с помощью примитивно рекурсивной функции « » или «Sg»:

max{x, y} = y + (x y) или max{x, y} = x Sg(x y) + y Sg(x y).

Тогда max{5, 3} = 3 + (5 3) = 5 или max{5, 3} = 3 + (5 3) = 5.

Тогда max{3, 5} = 5 + (3 5)=5 или max{3, 5} = 3 Sg(3 5)+5 Sg(3 5)=5.

Функция max{x, у} является рекурсивной.

Пример 18. Вычислить |x y|.

Эту функцию можно вычислить с помощью одной примитивно рекурсивной функции « »:

Пусть x = 5, y = 3. Тогда |5 3| = (5 3) + (3 5)=2+0=2.

Пусть x = 3, y = 5. Тогда|3 5| = (3 5) + (5 3)=0+2=2.

Функция |x y| является рекурсивной.

Пример 19. Вычислить логические функции (xy), (х&у), ¬x.

С помощью примитивно рекурсивной функции усеченного вычитания возможна «арифметизация» логических функций, аргументы и значения которых принадлежат множеству {0, 1}:

a) (xy) = max(x, y) = y + (x y), b) (х&у) = min(x, y) = x (x y), Пусть x = 1, y = 0. Тогда (10) = 0 + (1 0) = 1, (1&0) = 1 (1 0) = 0, Пусть x =0, y = 1. Тогда (01) = 1 + (0 1) = 1, (0&1) = 0 (0 1) = 0, Пусть x = 1, y = 1. Тогда (10) = 1 + (1 1) = 1, (1&0) = 1 (1 1) = 1.

Множество логических операторов {¬, &, } представляют функционально полную систему. Из этого следует, что любые логические функции являются рекурсивными.

Пример 20. Вычислить предикат Р(x1, x2,…, xn).

Для «арифметизации» вычисления предикатов Р(x1, x2,…, xn), которые принимают значения на множестве {истина, ложь}, следует ввести характеристическую функцию p (x1, x 2,..., x n ), значения которой есть Очевидно, что p (x1, x 2,..., x n ) =Sg(x1, x2,…, xn). Следовательно, если характеристическая функция примитивно рекурсивная, то предикат также примитивно рекурсивный. Если предикаты Р1, Р2,…, Рn примитивно рекурсивные, то любой предикат, полученный из Р1, Р2,…, Рn с помощью логических связок, также примитивно рекурсивен.

Пример 21. Вычислить отношение между объектами r(x1, x2,…, xn).

Между математическими объектами могут быть установлены отношения : Q VT => D - функция перемещения головки.

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

где - слово (или последовательность символов), расположенное слева от считывающей – записывающей головки, - слово, расположенное под и справа от считывающей - записывающей головки; qi — текущее состояние машины Тьюринга. Символ ‘а’, находящийся в ячейке непосредственно под считывающей записывающей головкой, является первым символом слова. К не заключительной конфигурации может быть применима только одна команда, которая переводит машину в новую конфигурацию. Так реализуется дискретность и детерминизм алгоритмического процесса. Для удобства анализа вычислительных алгоритмов математик Пост предложил ограничить множество символов внешнего алфавита VT двумя символами, т.е. VT = {|, #}, где "|" (палочка) есть символ унарного кода числа, а "#" (диеза или решетка) есть символ пробела между числами, представленными в унарном коде. При этом любое целое положительное число может быть записано на информационной ленте последовательностью палочек, как это представлено в табл. 1.

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

Число в десятичной "Слово" в унарном коде на информационной Работу машины Тьюринга удобно описывать протоколом, таблицей и/или графом. При протокольной записи все команды должны быть записаны упорядоченным списком *. На заключительном шаге должно быть получено значение заданной функции y=f(x1, x2,..., xn).

Например, 1) qoai —>qiajD, 2) qiak —>qjaiD,

i) q|am—>qkanC.

см. [5], [7].

При табличном описании каждая строка имеет имя текущего и начального состояний машины, а столбец – имя символа внешней памяти. Тогда элементами таблицы являются правые части команд qjaiD (табл.3).

Cостоя Символы VT символом «/» - записываемый символ на информационную ленту и команду на перемещение головки (рис. 2).

Рис. 2. Граф поведения машины Тьюринга Рассмотрим машины Тьюринга (м. Т.), исполняющие некоторые примитивно-рекурсивные функции.

T1:= вычисление функции Сn=0 на правой полу ленте: qо|x + 1#qk|#.

Пусть Vт={|, #}.

Протокол, табл. 4 и рис. 3 отображают процесс вычисления функции Cn = 0.

Протокол T1:

2) q1|q1# П, 3) q1#q2# Л, 4) q2 #qk|C.

Пусть x = 3. Тогда для C1(3)=0 на информационной ленте машины Тьюринга будут проведены следующие преобразования:

T2:= вычисление функции Сn=1 на правой полуленте: qо|x + 1#qk||#.

Протокол Т2, табл. 5 и рис. 4 отображают процесс вычисления функции Сn =1.

3)q1#q2# |Л, q1 q1 #П q2 |Л T3:= вычисление функции (x)=х+1 на правой ленте: qo|x+1# qk |(x+1)+1#.

Протокол Т3, табл. 6 и рис. 5 отображают процесс вычисления (x)=х+1.

Пусть х=3. Тогда для (3)=3+1=4 на информационной ленте будут проведены следующие преобразования машиной Тьюринга:

q0П q1П q1П q1П q1Л q2Л q2Л T4:= вычисление функции I m на правой ленте:

где |i - слово на i-м месте информационной ленты, |xi+1 – число, равное xi.

Чтобы найти i-е слово, следует установить счетчик |m-1, указывающий наxm+1 x1+1 x2+1 xm+1 xn+ чало слова |m в q 0 |m-1 #|1 #|2 #...#|m #|n. Это позволяет при каждом проходе вправо удалять один символ в слове |m-1 и удалять одно слово |i -1, предшествующее слову |mxi+1. Поведение машины описано в табл. 7 и графом на рис. 6.

q4 q4 |Л q5 # П q1#q2)П ставится скобка, закрывающая q11 q10 #П q12 #Л символом слова |m-2. Так организован цикл.

Затем управляющее устройство стирает второе слово, третье и т. д. пока есть символы “|” в счетчике. После стирания всех символов в счетчике по команде q5)q8#П головка стирает закрывающую скобку, пробегает все пробелы “#”, по команде q8)q9#П фиксирует место слова |mxm+1, пробегает все символы слова |mxm+1 и продолжает удалять все слова справа от слова |mxm+1по командам q10|q10#П и q11|q10#П. Если при чтении ленты в соседних ячейках будут символы “#”, то конец и головка возвращается на первый символ слова |mxm+1 по командам: q11#q12#Л, q12#q12#Л, q12|q13|Л, q13|q13|Л, q13#q14#П и q14|qk|C.

T5:= вычисление примитивно рекурсивной функции предшествования (x) = x 1 на правой ленте: q | x+1 # qk | (x +1) - 1 #.

Протокол, табл.8 и рис. 7 отображают процесс вычисления -1(x) = x 1.

Пусть Vт={|, #}.

6) q3#q4#П, 7) q4|qk|C.

T6:=копирование m раз слово |x+1на правой ленте:

Для того чтобы выполнить m копий, необходимо установить на информационной ленте счетчик числа копий |m, т.е. изменить начальную конфигурацию машины так: q 0 |m #|x+1# q k |1 +1#2 +1#|3 #...#|m #.

При каждом проходе вправо в слове |m удаляется один символ, затем выполняется обычное копирование слова |x +1. Пометка переносимого символа слова |x+1 выполняется командой q2|q3(П, а закрытие слова |x+1 - командой q3#q4)П. После переноса всех символов слова |x +1 головка возвращается на самый левый символ слова |m и стирает его. Так организован цикл. Копирование следующих m копий будет продолжаться до тех пор, пока не будут удалены все символы в слове 1m. После этого следует удалить символы (, ) и поставить головку машины в начало первого слова |x+1. Множество команд, описывающих поведение машины Тьюринга, представлено табл. 9 и графом на рис. 8.

Пусть Vт.={|, #, (, )}.

q1 q1 |П q2 )П - q2 )П q2 q3 (П - q2 )П q2 )П q3 q3 |П q4 )П - q4 )П q7 q7 |Л q0#П q7 (Л q7 )Л q8 q9 |Л - q8 (П q8 )П q9 qk |C q9#П q9 |Л q9#Л T7:= сравнение длины двух слов на правой полуленте:

Символы VT q2 q2 |П q3 #Л - q4 q4 |Л q5 #П q4 )Л q6 q6 |Л q7 #П - q8 qk2 |C qk3 |C - Особенность задачи состоит в том, что слово (x+1) может быть больше, меньше или равным слову (y+1). При этом машина Тьюринга должна переходить в три различных состояния для организации ветвящегося процесса вычисления. Пусть Vт={|, #, )}. Поведение машины Тьюринга описано табл.10 и графом на рис. 9.

T8:= перестановка слов: qо|x+1# |y+1# qk|y +1# |x+1#.

Протокол, табл. 11 и рис. 10 отображают процесс перестановки слов.

Пусть Vт={|, #, (, )}.

Рис. 10. Граф алгоритма м. Т. перестановки слов.

T9:= устранение пробелов между словами qo|x1+1##...#|x2+1#qk|x1+1 # |x2+1#.

Пусть Vт={|, #, )}.

Табл. 12 и рис. 11 отображают процесс устранения пробелов между словами. После просмотра первого слова символ «#» замещается «)» для ограничения переноса влево символов второго слова. Последний символ второго слова также замещается «)» для ограничения движения считывающей головки вправо.

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

T10:= поиск последнего слова на правой ленте:

qo|x1+1#|x2+1#... # |xm+1 |x1+1#|x2+1#... # qk|xm+1.

Поиск последнего слова на правой ленте завершается после нахождения не менее двух ## (пробелов), что свидетельствует об окончании последовательности слов. Затем считывающая головка возвращается на первый символ последнего слова. На рис. 12 представлен граф, а в табл. 13 – протокол алгоритма.

T11:= вычисление функции f(x, y) = x y :

q4 q4|Л q5 #П q4 )Л Для вычисления усеченного вычитания можно использовать машины Т8 и Т1, изменив команды машины Т8: q8|qk2|C и q8#qk3|C на команды машины Т1:q8|q8#П, q8#Пq8#П (состояния q1 и q2 машины Т1 есть, соответственно, q и q9 машины T11 ). В табл. 14 и на рис. 13 показан протокол решения усеченного вычитания.

Т12:= вычисление предиката Р(x, y):

Для этого можно использовать машины Тьюринга Т8, Т1 и Т2.

В табл. 15 и на рис. 14 даны протокол и граф алгоритма.

q2 q2|П q3#Л - q3 q4#Л - q6#Л q4 q4|Л q5)#П q4)Л q5 q1#П - q8#П q6 q6|Л q7#П - q7 q7#П q10|Л - q8 q8#П q9#П - q10 - qk1|C - Для графического изображения основных операций на схеме алгоритма приняты обозначения основных блоков, показанные на рис. 15.

Последовательное и/или параллельное соединение различных блоков позволяет организовать вычисление любых частично-рекурсивных функций. Общую схему соединения нескольких блоков от “начало” до “конец” называют блок-схемой алгоритма.

Рис. 15. Основные блоки схемы алгоритма Оператор суперпозиции Sm (h (m), g (n) ). Если даны m-местная функция h=(z1, z2,..., zm, у) и m n-местных функций gi=(x1, х2,..., хn, zi), где 1im, которые вычислимы по Тьюрингу, то функция f=(x1, х2,..., хn, у) также вычислима.

Алгоритм вычисления оператора суперпозиции:

шаг 1: вычислить по заданным значениям (x1, х2,..., хn) значения функций gi (x1, х2,..., хn) для 1 i m:

Tg : q 0 |x1 +1#|x 2 +1#...#|x n +1 q k |g1 (x1 +1,x 2 +1,...,x n +1)+1#|g 2 (x1 +1,x 2 +1,...,x n +1)+1#...#|g m (x1 +1,x 2 +1,...,x n +1)+1#;

шаг 2: вычислить для полученных значений gi (x1, х2,..., хn) значение функции h(g1, g2,..., gm):

Th : q 0 |g1 (x1 +1,x 2 +1,...,x n +1)+1#|g 2 (x1 +1,x 2 +1,...,x n +1)+1#...#|g m (x1 +1,x 2 +1,...,x n +1)+1# q k |h(g1,g 2...,g m )+1#;

шаг 3: выдать результаты расчетов:

q 0 |h (g1, g2,...,g m )+1# q k |f (x +1)+1#.

На рис. 16 изображена композиция машин Тьюринга, реализующая оператор суперпозиции для n=1 и m=1.

Рис. 16. Схема алгоритма оператора суперпозиции Оператор рекурсии. Если даны n-местная функция g(x1, х2,..., хn) и (n+2)местная функция h(x1, х2,..., хn, y, f(x1, х2,..., хn, y)), которые вычислимы на машине Тьюринга, то функция f(x1, х2,..., хn, y+1)=h(x1, х2,..., хn, у, f(x1, х2,..., хn, y)) также вычислима на машине Тьюринга.

Алгоритм вычисления оператора рекурсии:

шаг 1: вычислить для заданного значения х функцию g(х);

Tg: qо|x+1 #|y+1qk|x+1 #|y+1#|g(x+1) +1, (если g является базовой функцией, то процесс ее вычисления приведен на машинах Т1, Т2, Т3);

шаг 2: ввести переменную i для счета символов слова (у+1):

Ti: qо|x+1#|y+1#|g (x+1) +1qk|i+1#|x+1#|y+1 #|g (x+1) +1; установить i = 0;

шаг 3: вычислить значение функции h(х, i, f (х, i)):

Th: qo|i+1#|x+1#|y+1 #|g(x+1) +1 qk|i+1#|x+1#|y+1 #|h((x+1), i, f (x +1, i)) +1;

шаг 4: проверить i = у;

a) если i у, то принять i = i+1 и перейти к шагу 3;

b) если i = у перейти к шагу 5; (для проверки условия использовать Т12);

шаг 5: удалить с ленты слова |y+1, |x+1, | y+1:

Tk : q|y+1#|x+1#|y+1#|h (x+1, y, f (x+1, y))+1# qk|h (x+1), y, f (x +1, y))+1#;

шаг 6: выдать результаты расчетов:

q 0 |h (x+1), y, f (x +1, y))+1# q k |f (x +1, y+1)+1#.

При реализации оператора рекурсии необходимо вычислять значения f(x, i+1) до тех пор, пока iу. При достижении i=у процесс вычисления прекращается и результат вычисления есть f(х, у+1)=h(х, у, f(х, у)). Если каждый шаг вычислительного процесса представить отдельной машиной Тьюринга, то их последовательное соединение (кроме машины, реализующей шаг 4) обеспечивает поиск значения функции f(х, у). Результат исполнения шага 4 должен поступить на входы машин Тi или Tk, т.е. машина имеет два выхода. На рис. 17 приведена схема соединения машин Тьюринга для оператора примитивной рекурсии.

Если функции g(х) и h(х, у, f(х, у)) не базовые, но вычислимые по схеме примитивной рекурсии, то функция f(х, у) также вычислима на машине Тьюринга. Вычислимые функции, значения которых определены не для всех значений независимых переменных аргумента, называют частичными. Следовательно, вычислимые функции, для которых область определения ограничена, называют частично вычислимыми функциями. Если частично вычислимая функция определена на множестве целых положительных чисел и принимает значение на том же множестве, то ее называют частично рекурсивной функцией. Вычислимую функцию, всюду определенную на множестве целых положительных чисел и принимающую значение на том же множестве, называют общерекурсивной функцией. Для иллюстрации этого алгоритма рассмотрим случай для n=1, т.е. g(x), h(x, y, f(x, y)) и f(x, y+1)= h(х, у, f(х, у)) (рис. 17).

Рис. 17. Схема алгоритма оператора рекурсии Оператор минимизации. Для поиска наименьшего корня функции (x1, х2,..., хn)=y(f(x1, х2,..., хn, y)=0) необходимо организовать последовательное приращение вспомогательного аргумента у=0, 1, 2.... и сравнивать значение функции f(x1, х2,..., хn, y) с базовой функцией Сn=0.

Алгоритм вычисления оператора минимизации (см. рис. 18):

шаг 1: ввести переменную i в функцию f(x1, x2,…, xn, y):

Ti: qо| f(x1+1# x2+1#... Xn+1, y+1)qk| f(x+11# x2+1#... Xn+1# i+1)#; установить i = 0;

шаг 2: вычислить значение функции f(х1, x2,..., xn, i):

Tf: qo| f(x+11# x2+1#.… Xn+1# i+1)# qk| f(x+11# x2+1#... Xn+1# i+1)#;

• если f(x1, x2,…, xn, i) 0, то принять i=i+1 и перейти к шагу 2;

шаг 6: выдать результаты расчетов:

Рис. 18. Схема алгоритма оператора минимизации Оператор итерации. Условием итерации является число повторений n.

Схема итерации (рис. 19): f(i) = Алгоритм вычисления оператора итерации:

шаг 1: ввести необходимое число шагов n и функцию h(f(i));

шаг 2: вычислить значение функции h(f(i)) для 1 i n:

• если in, то перейти к шагу 2;

• если i=n, то конец;

шаг 3: выдать результаты расчетов:

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

Для успешного использования левой и правой полулент машины Тьюринга была предложена система кодирования символов трех алфавитов.

Согласно этой системе (табл. 16) символы «сдвига головки» были представлены кодами 101, 102, 103, символы «внешней памяти» - кодами с числом нулей равном (2i + 4), символы «внутренней памяти» – кодами с числом нулей (2i + 5).Символ # интерпретируются как пробел между числами или словами.

Тогда любой команде (i) машины Тьюринга, имеющей вид qmasqlauD может быть сопоставлен код: код (i)= код(qm)код(as)код(ql)код(an)код(D), в котором коды всех символов приписаны друг к другу без каких-либо пробелов. Разделителем слов или чисел являются 1, так как код любого символа начинается с 1, а их различие определяется количеством нулей в коде.

На левой полуленте записывают протокол машины Тьюринга, а на правой – ее текущую конфигурацию. В процессе вычисления заданной функции на правой полуленте определяется левая часть команды qmas, где qm текущее состояние управляющего устройства, as – символ на информационной ленте под считывающей головкой. Затем на левой полуленте находится соответствующая команда qmasqlauD. После этого машина Тьюринга записывает в обозреваемую ячейку символ au, переводит управляющее устройство в состояние ql и перемещает головку не более как на одну ячейку вправо или влево.

Например, для машины Т1 протокол будет записан на левой полу ленте так:

код(Т1)=10510610910410110910610910410110910410111041021011104107106103.

Указанное кодирование является алгоритмической процедурой. Каждые пять групп единиц и нулей представляют одну команду. Следовательно, любой функции, вычисляемой на машине Тьюринга, может быть сопоставлен код (Тi) и по коду (Тi) можно выделить алгоритм вычисляемой функции. Так может быть организована нумерация алгоритмов машины Тьюринга.

В 70-е годы XX века была предложена алгоритмическая модель, представляющая собой идеализированную ЭВМ. Эта модель состоит из бесконечного числа регистров R1, R2, R3,...,, в каждом из которых может быть записано натуральное число. Часть этих регистров используют для хранения команд (аналог левой полуленты), остальные - для хранения данных, промежуточных вычислений и окончательных результатов (аналог правой полуленты). Модель позволяет организовать произвольный доступ к ячейкам памяти. Такую модель назвали «машиной произвольного доступа» - МПД.

Набор команд МПД включает:

• команду обнуления: действие команды заключается в замене содержимого регистра Rn на 0, т.е. Rn := 0, • команду прибавления единицы: действие команды заключается в увеличении содержимого регистра Rn на 1, т.е. Rn:= Rn + 1, • команду переадресации: действие команды заключается в замене содержимого регистра Rn числом rm, хранящимся в регистре Rm, т.е. Rn:=Rm, • команду условного перехода: действие команды заключается в сравнении содержимого регистров Rn и Rm:

- если Rn=Rm, то перейти к исполнению команды qi;

- если RnRm, то перейти к исполнению команды qj.

Упорядоченная последовательность команд формирует программу МПД.

3. Нормальный алгоритм Маркова - модель алгоритма Понятие "нормальный алгоритм" ввел в 1947 г. советский ученый А.А.

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

Словами Рi в алгоритме Маркова могут быть арифметические, алгебраические или логические выражения.

Нормальный алгоритм Маркова есть указание использовать упорядоченный список правил подстановки:

где i и i — некоторые слова в алфавите VT.

Множество правил и порядок их использования позволяют выполнять преобразования исходного слова Ро в заключительное слово Q, т. е.

Для организации последовательного и упорядоченного просмотра правил они должны быть индексированы i {1, 2, 3,...}.

Если слово Рi есть цепочка вида (1I2) в алфавите Vт, где 1 и 2 – слова в этом же алфавите и среди множества правил первым в упорядоченном списке есть правило II, то нужно выполнить подстановку (1i2) (1i 2).

Суть упорядоченного использования правил состоит в том, что каждое переработанное слово вновь поступает в «начало» алгоритма и вновь проверяется на подстановку правил в соответствии с протоколом.

Среди множества правил выделяют заключительное i • i, результатом подстановки которого формируется слово Q и дается указание об окончании работы алгоритма.

Процесс может оборваться на некотором слове Рi, для которого нет соответствующего правил. Тогда это слово направляется в «тупик».

Для того чтобы построить модель алгоритма, необходимо выделить упорядоченную последовательность левых частей правил подстановки, так называемых распознавателей вхождения слов i в слово Pi, и множество соответствующих операторов подстановки слова I в слово Pi+1 i.

На схеме алгоритма (см. рис. 19) эти блоки обозначены так:

• распознаватели вхождения - PBi ;

• операторы подстановки - ОПi.

Распознаватели вхождения соединяются последовательно в соответствии с заданной последовательностью правил. Второй выход распознавателя вхождения при обнаружении i в слове Рi передает информацию о слове Pi=1i2 в ОПi, где выполняется соответствующая замена слова i на слово i, т. е.

1i2 1i2=Pi+1.

Оператор подстановки направляет слово Pi+1 в «начало» алгоритма, если применена простая подстановка, и в «конец» алгоритма, если применена заключительная подстановка.

Рис. 19. Схема нормального алгоритма Маркова Ниже дано несколько примеров вычисления базовых и примитивнорекурсивных функций по схеме нормального алгоритма Маркова.

3.1 Примеры нормальных алгоритмов Маркова Пример 36. Вычислить базовую функцию Сn(х)=0 в десятичной системе счисления по схеме нормального алгоритма Маркова.

Пусть «# XXX... #» - число в десятичной системе счисления, X – цифра1, 2, 3,… Алфавит VT содержит четыре символа VT = {X, 0, #, (}, На рис. 20 приведена схема этого алгоритма.

Рис. 20. Схема алгоритма вычисления Сn = 0.

Пример 37. Вычислить базовую функцию (х) в десятичной системе счисления.

Рис. 21. Схема (х) 9)00##)000# #•1000#=#1000#=Q.

Пример 38. Преобразовать цифры десятичного числа в унарный код.

Рис.22. Схема алгоритма преобразования числа в унарный код.

Пусть x=234. Тогда Р0=# 234###(234###(1|34###(0||34####||34## #||34###||(34###||(2|4## #||(1||4###||(0|||4###||##|||4###||#|||(4## #||#|||(3|#|#||#|||(2||###||#|||(1|||###||#|||(0||||###||#|||##||||## #||#|||#||||## #||#|||#|||•|## =#||#|||#||||## Q.

Пример 39. Вычислить сумму двух чисел в унарном коде, т.е. f (х; у) = | x + y. Пусть Ро =#|x+|y#. Тогда Q =# |x + y#.

Рис.23 Схема алгоритма Пример 40. Вычислить произведения двух чисел в унарном коде: f(х; у)=|x y.

Пусть Ро= #|x |y #, тогда Q = #|x y #.

Алфавит Vт={|,, #, (, )}.

Схема алгоритма приведена на рис. 24.

Тогда P0=#|||*||##|||(*|##||(|)*|# #|(|)|)*|##(|)|)|)*|##()|)|)*|##)|)|)*|# #|))|)*|##|)|))*|##||)))*|##||)))(##||))()# #||)())##||()))##|(|))))##(|)|))))##()|))))# #)|))))##|)))))##||))))##|||)))##||||))# #|||||)##||||||##|||||•|#=Q.

Рис. 24. Схема алгоритма умножения чисел Пусть дан алфавит А = {a1, a2, …, ar}, где r – число букв или символов алфавита. Например, для латиницы это - r=26. На множестве букв алфавита согласно правилам соответствующей грамматики можно сформировать множество слов конечной длины A*={1, 2, …, 1, 2,…, }, где -пустое слово. Согласно правилам алгоритма Маркова это могут быть слова i и i. Тогда алфавитная нумерация определяется как:

Поскольку при фиксированном r каждое положительное число n однозначно представимо в виде:

n=is + is-1r + … + i1rs-1, где 1 i r – порядковый номер символа в алфавите А, нижний индекс которого указывает его место в слове i или i.

Например, для нормального алгоритма Маркова произведения двух чисел (см. прим. 40) алфавит содержит пять символов Vт={|,, #, (, )}, а протокол правила 1:= | | 1:= (|, 2:= |# 2:= (#, 3:= |( 3:= (|), 4:= )( 4:= ( ), 5:= )| 5:= |), 6:= (| 6:= (, 7:= ( ) 7:= ), 8:= ) 8:= |, 9:= |# 9:= •|#.

Номера некоторых слов: 1:= | | : n = 1+15+252 = 56, 1:= (| : n = 1+25+452 =111, 2:= |# : n = 3+15+252 = 58, 2:= (# : n = 3+45 = 23, 3:= |( : n = 4+15 = 9, 3:= (|): n = 5+15+452 = 110, 4:= )( : n = 4+55 = 29.

4:= ( ) : n = 5+45 =25 и т.д.

Следовательно, цифровой код протокола есть (56111, 5823, 9110, 2925, 2610, 214, 255, 51, 88). Далее нужно найти номер для набора двух чисел команды (см. 1.3). Так может быть сформирована упорядоченная последовательность номеров команд, моделирующая заданный алгоритм.

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

инвариантным к способу описания. Различия наблюдаются лишь в использовании алгоритмических объектов. Если для рекурсивных функций объектами являются числа и числовые функции, а процесс вычисления задан операторами суперпозиции, рекурсии, минимизации и итерации, то для машин Тьюринга такими объектами являются символы алфавитов внешней и внутренней памяти, а процесс вычисления задан протоколом, использующим функции выхода, перехода и перемещения головки. Для нормального алгоритма Маркова такими объектами являются слова или последовательности символов, а процесс вычисления задан правилами подстановки или продукциями, изменяющими состав и структуру исходной последовательности символов до искомого результата.

Функция называется вычислимой, если существует вычисляющий её алгоритм. «Вычислимость *» является одним из основных понятий теории алгоритмов, инвариантном к вычисляемой функции и алгоритму. Различие между вычислимой функцией и алгоритмом – это различие между описанием функции и способом вычисления её значений при заданных значениях независимых аргументов.

Если для решения задачи, принадлежащей единому классу задач, найден алгоритм вычисления, то о задаче говорят как об алгоритмически разрешимой проблеме. Иначе говоря, обязательным условием вычислимости или результативности вычисления является её алгоритмическая разрешимость. В этом смысле понятие «разрешимость **» является также основным понятием в теории алгоритмов.

Анализ трех типов моделей показывает, что основные свойства дискретности, детерминизма, массовости и результативности остаются неизменными для различных способов описания:

• Свойство дискретности: алгоритм состоит из отдельных элементарных действий, выполняемых по шагам; множество элементарных шагов, из которых состоит алгоритмический процесс, конечно и счетно.

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

• Свойство массовости: использование алгоритма допустимо для множества алгоритмических объектов данного типа и данного класса задач.

• Свойство результативности: остановка алгоритмического процесса обязательна после конечного числа шагов с указанием искомого результата.

см. [2], [4], [5] Выбор алгоритмической модели существенно влияет на сложность вычисления задачи. Сложность вычисления есть функция, дающая числовую оценку трудоемкости применения алгоритма к исходным данным для получения искомого результата. Чаще всего рассматривают временню сложность и ёмкостню, которые чаще всего представляются функциями от |x|, где |x| – мощность множества исходных данных.

Время вычисления описывается произведением числа шагов алгоритма от исходных данных до искомого результата н средним физическим временем реализации одного шага. Число шагов определяется его описанием в заданной алгоритмической модели. Пусть машина Тьюринга вычисляет некоторую функцию f(x) данного класса задач. Тогда t(x) есть функция, равная числу шагов при вычислении f(x), если f(x) определена. Функция t(x) называется временнй сложностью. Однако физическое время реализации одного шага алгоритма на конкретном компьютере зависит от типа компьютера, способов компиляции, скорости обработки информации, что существенно усложняет определение временнй сложности.

Объем памяти, как количественная характеристика алгоритма, определяется количеством единиц памяти, используемых в процессе вычисления алгоритма. Эта величина не может превосходить максимального числа единиц памяти, используемых на одном шаге алгоритма. Пусть машина Тьюринга вычисляет функцию f(x). Тогда s(x) есть функция, равная множеству всех ячеек информационной ленты, которые, если f(x) определена, посещаются в процессе вычисления этой функции. Функция s(x) называется ёмкостнй сложностью.

Если машина Тьюринга имеет внешнюю и внутреннюю памяти мощности n=|Vt| и m=|Q| соответственно, то для временнй и ёмкостнй функций сложности допустимы оценки:

Чаще всего временню сложность t(x) описывают полиномами от исходных данных. Если известен размер исходных данных - |x| и временная сложность задана некоторым полиномом t(|x|)=р(|x|), то оценка временнй сложности есть O(р(|x|)). Эта оценка определяется, как правило, старшим членом полиномиального ряда. При этом говорят, что машина Тьюринга решает задачу за полиномиальное время. Например, если времення сложность задана полиномом р(|x|)_=4|x|2+7|x|+12, то оценка временной сложности есть О(|x|2). Алгоритм, имеющий полиномиальное время, называют полиномиальным алгоритмом. Множество однотипных задач, разрешаемых на машине Тьюринга за полиномиальное время, принадлежит классу задач Р.

Есть задачи, для которых может быть найдено некоторое слово, являющееся «догадкой» (или удостоверением) принадлежности задачи к классу Р на см. [2], [4], [5] недетерминированной машине Тьюринга. В этом случае говорят, что задача принадлежит к классу NP, а оценка временной сложности есть O(p()).

Если t(|x|)O(p(|x|)), то говорят, что машина Тьюринга решает задачу за экспоненциальное время t(|x|) = O(c|x| ), где с – некоторая константа. Например, для булевых функций с=2. Тогда t(n) = O(2n ), где n =число булевых переменных.

Пример 41. Дано N={1, 2, 3,…, n} и RNN. Является ли R отношением эквивалентности?

Известно, что R является отношением эквивалентности тогда и только тогда, когда выполнены условия:

Дополнительным условием является r 2 (i, j) r(i, j).

Проверка этих условий ограничена независимыми оценками O(n2) и O(n), так как нужно вычислять значения r2(i, j) для каждой пары (i, j), а затем сравнивать с r(i, j). Оценка временнй сложности задачи есть O(nn2) = O(n3). Поэтому алгоритм данной задачи есть полиномиальный, а оценка его временнй сложности зависит от числа исходных данных в третьей степени.

Пример 42. Дано N={1, 2, 3,…, n} и R={(1, 2), (2, 3), (3, 4),…, (n, 1)} NN. Является ли R отношением эйлеровым?

Бинарное отношение R называют эйлеровым, если элементы R можно упорядочить (i1, i1), (i2, i2),…, (in, in), где n=|R|, и выполнить условие (i1, i2)R, (i2, i3)R,…, (in, i1)R.

Связное отношение R является эйлеровым тогда и только тогда, когда число единиц в матрице R совпадает в i-м столбе и i-й строке для каждого i {1,2..,n}.

Так как все вычисления выполняются только с одной матрицей R, сравнивая число единиц в i-й строке и i-м столбце, то времення сложность задачи будет O(n2). Поэтому алгоритм данной задачи полиномиальный, а оценка его временнй сложности зависит от числа исходных данных во второй степени.

Пример 43. Дана формула f (x1, x 2,..., x n ) = &(x1 1 x 2... x n ), где i{0,1} – значение xi булевой переменной. Проверить её выполнимость.

Алгоритм проверки выполнимости этой формулы требует перебора 2n наборов (1, 2,..., n ) и вычисления значения функции для каждого набора. Поэтому t(|x|) = O(2n ), т. е. алгоритм данной задачи - экспоненциальный.

Пример 44. Дано N={1, 2, 3,…, n} и R={(1, 2), (2, 3), (3, 4),…, (n, 1)} NN. Является ли R отношением гамильтоновым?

Бинарное отношение называют гамильтоновым, если элементы множества N можно упорядочить так (i1, i2,…, in), чтобы выполнялось условие: (i1, i2)R, (i2, i3)R,…, (in, i1)R.

Догадкой (или удостоверением) гамильтонова отношения R является заданная последовательность (R)=(i1, i2,…, in). Проверяя бинарное отношение R={(1, 2), (2, 3), (3, 4),…, (n, 1)} по заданной последовательности =(1, 2,…, n), можно убедиться, что задача проверки отношения R находится в классе NP задач.

1. Какие функции могут быть получены по схеме примитивной рекурсии:

f) g(x)=(J1,1)=x+1 h (х, у, f (х, у)) = f+(J3,1, J3,3)=x+f(x,y).

2. Применить оператор минимизации по переменной у. Найти (x).

b) f(x, y) = (x - 2y2), c) f(x, y) = (x2 - 2y), 3. Доказать тождества.

a) x+(y x) = y+(x y), 4. Какую функцию f(x) можно вычислить, используя оператор итерации b) h(f(i)= (f(i)+2[ f (i) ], 5. Какую функцию вычисляет машина Тьюринга:

q2 # q0 |C. Показать процесс на информационной ленте.

6. Написать протоколы, построить таблицу поведения, нарисовать граф поведения машины Тьюринга:

а) сдвиг слова влево на одну ячейку:

b) перенос слова с правой на левую полуленты:

#q0|x# #|x-1qk|#, c) удвоение слова:

#|x-1q0|# #|2x-1qk|#.

1а) f(x, 0) = x, f(x, 1) = x+f(x, 0) = x+x = 2x, f(x, 2) = x+f(x, 1) = x+2x = 3x, f(x, 3) = x+f(x, 2) = x+3x = 4x, ……………………………….

f(x, i) = x+f(x, i-1) = x+ix = x(i+1).

Если i = y, то f(x, y) = xy+x.

1b) f(x,0) = x, ……………………………….

f(x, i) = x+(i-1) = x+(i -1).

Если i = y, то f(x, y) = (x+y)-1.

1c) f(х, 0) = x, f(x, 1) = 0+f(x, 0) = x, f(x, 2) = 1+ f(x, 1) = 1+x, f(x, 3) = 2+ f(x, 2) = 3+x, ……………………………….

f(x, i) = (i+x).

Если i = y, то f(x, y) = (y+x).

1d) f(х, 0) = (x) = x+1, f(x, 1) = x+ f(x, 0) = x+x+1 = 2x+1, f(x, 2) = x+ f(x, 1) = x+2x+1 = 3x+1, f(x, 3) = x+ f(x, 2) = x+3x+1 = 4x+1, ……………………………….

f(x, i) = (i+1)x+1.

Если i = y, то f(x, y) = yx+x+1.

1e) f(х, 0) = 0, f(x, 1) = (f(x, 0)+1 = 1, f(x, 2) = f(x, 1)+1= 1+1 = 2, f(x, 3) = f(x, 2)+1= 2+1 = 3, ……………………………….

Если i = y, то f(x, y) = y.

Если g(x)=(J1,1)=x+1 и h (х, у, f (х, у)) = f+(J3,1, J3,3)=x+f(x,y).

По схеме примитивной рекурсии:

1f) f (x, 0)=g(x)=(x+1), f(x, (0+1))=x+(x+1)=(2x+1), f(x, (1+1))=x+(2x+1)=(3x+1), f(x, (2+1))=x+(3x+1)=(4x+1), f(x, (3+1))=x+(4x+1)=(5x+1), f(x, (4+1))=x+(5x+1)=(6x+1), f(x, (i+1))=x+((i+1)x+1)=(x((i+1)+1)+1.

Следовательно, если (i+1)=y, то f(x, y)=x(y)+1=xy+x+1 есть рекурсивная функция, так как для ее вычисления использованы базовые функции тождества и следования и примитивно рекурсивная функция сложения.

Согласно алгоритму следует вычислить (a) = y (f (a, y) Sg(y)) = 0).

Следовательно, (4) = 4 (f (4,4) Sg(4) = 0) = 4.

Пусть x=8. Тогда 0 ((8-2 02 ) 0), 1 ((8-2 12 ) 0), 2 ((8-2 22 )=0).

Следовательно, (8)= 2 ((8-2 22 )=0)=2.

Область определения функции (x) есть x= 2, 8, 18, 32,…, а область значений y=1, 2, 3, 4,…, т.е. (x) есть частично рекурсивная функция.

Следовательно, (2) = 2 (22 - 2 2 = 0)=2.

2d) для x=5 имеем f(5, 0)=50, f(5, 1)=30, f(5, 2)=10, f(5, 3)=0, т.е. (5) =3.

2e) для x=1 f(1, 0)=10, f(1, 1)=0, т.е. (1)=1, для x=2 f(2, 0)=40, f(2, 1)=10, f(2, 2)=0, т.е. (2)=2, для x=3 f(3, 0)=90, f(3, 1)=60, f(3, 2)=3 f(3, 3)=0, т.е. (3)=3, для x=4 имеем f(4, 0)=160, f(4, 1)=130, f(4, 2)=100, f(4,3)=70, f(4, 4)=40, f(4, 5)=10, f(4, 6)=0, т.е. (4)=6 и т.д.

Область определения функции (x)=y задана на множестве целых чисел x={1, 2, 3,…}, а область её значений также на множестве целых чисел y [x2/3].

3a) x+(y x) = y+(x y).

Следовательно, если x>y, то x+(y x) = y+(x y) = x, если x ( y + z ), Следовательно, если x>(y+z), то x (y+z) = (x y) z = (x-y-z), если x(y+z), x-y-z, если x>(y+z), Следовательно, если x>(y+z), то (x y) z = (x z) y = (x-y-z), если x (y+z), то (x y) z = (x z) y = 0, ч.т.д.

f(0)=0, f(1)=h(f(0))=(0+1+[ 4 0 + 1 ])=1+1=2, f(2)=h(f(1))=(2+1+[ 4 2 + 1 ])=3+3=6, f(3)=h(f(2))=(6+1+[ 4 6 + 1 ])=7+5=12, f(4)=h(f(3))=(12+1+[ 4 12 + 1 ])=13+7=20, …………………………………………… f(i)=h(f(i-1))=i2+i.

Если i=x, то f(x)=x2+x.

4b) h(f(i)= (f(i)+1+2[ f (i) ].

f(0)=0, f(1)=(f(0)+1+2[ f (0) ]=1, f(2)=(f(1)+1+2[ f (1) ]=4, f(3)=(f(2)+1+2[ f (2) ]=9, f(4)=(f(3)+1+2[ f (3) ]=16, …………………………… f(i)=i2.

Если i=x, то f(x)=x2.

5. Пусть x=3, т.е. на информационной ленте слово # | | | #.

q0 Следовательно, машина Тьюринга вычисляет функцию (x).

q2 | q3 #Л, q3 | q3 |Л, 6b) T2: #q0|x# #|x-1qk|#, q1# q2#Л, q2| qk|C.

6c) T3: #|x-1q0|# #|2x-1qk|# 1. Выделить машины Тьюринга, реализующие служебные и вычислительные примитивно рекурсивные функции.

2. Для каждой машины Тьюринга составить таблицу поведения и нарисовать граф.

3. Выполнить композицию машин Тьюринга, составив схему соединения и обобщенную таблицу поведения.

4. Проверить “усеченное вычитание” для x>y>z>s>t и xyzst.

Вариант 1. Алферова Э.В. Теория алгоритмов. – М.: Статистика, 1973г.

2. Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. – Омск: Изд-во Наследие, Диалог-Сибирь, 2003.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – 2-е изд.,перераб. и доп. – М.:Энергоатомиздат, 1988.

4. Математическая энциклопедия /Гл. ред. И. М. Виноградов. – М.: Советская энциклопедия. т.4. 1984.

5. Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс лекций. –[email protected], 1992.

6. Першиков В.И., Савинков В.М. Толковый словарь по информатике.- М.:

Финансы и статистика, 1991г.

7. Пономарев В.Ф. Модели вычислительных алгоритмов. Учебное пособие. – Калининград: Изд-во КГТУ, 1998г.

8. Словарь по кибернетике. /Под ред. В.С. Михалевича. – 2-е изд. – К.:

Гл. ред УСЭ им. М.П. Бажана, 1989г.

9. Структура данных и алгоритмы. Альфред В. Ахо, Джон Э. Хипкрофт, Джеффрид Д. Ульман. /пер. с англ. А.А. Минько/. –М.- СПб –Киев: издательский дом «Вильямс», 2003г.

10.Успенский В.А., Семенов А.Л. Теория алгоритмов: основные понятия и приложения. – М.: Наука, 1987г.

Предисловие

1. Рекурсивная функция - модель алгоритма

1.1. Базовые функции

1.2. Элементарные операции

1.3. Нумерация наборов чисел

2. Машина Тьюринга - модель алгоритма

2.1. Описание машины Тьюринга

2.2. Примеры машин Тьюринга

2.3. Композиция машин Тьюринга

2.4. Нумерация алгоритмов

3. Нормальный алгоритм Маркова - модель алгоритма..... 3.1 Примеры нормальных алгоритмов Маркова

3.2. Нумерация слов

4. Вычислимость и разрешимость

5. Сложность вычислений

Вопросы и задачи

Ответы и решения

Индивидуальное задание

Литература



Похожие работы:

«1 Государственное образовательное учреждение высшего профессионального образования Липецкий государственный технический университет УТВЕРЖДАЮ Декан экономического факультета _В.В. Московцев 20_ г. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) МАРКЕТИНГ наименование дисциплины (модуля) Направление подготовки 080200.62 Менеджмент (код и направление подготовки) Профиль подготовки Финансовый менеджмент (наименование профиля подготовки) Квалификация (степень) бакалавр (бакалавр / магистр / дипломированный...»

«Д.А. Новиков УПРАВЛЕНИЕ ПРОЕКТАМИ: ОРГАНИЗАЦИОННЫЕ МЕХАНИЗМЫ Распределение ответственности WBS OBS Сетевой график Распределение Распределение ресурсов полномочий RBS Москва – 2007 Российская академия наук Институт проблем управления им. В.А. Трапезникова Д.А. Новиков УПРАВЛЕНИЕ ПРОЕКТАМИ: ОРГАНИЗАЦИОННЫЕ МЕХАНИЗМЫ Рекомендовано в качестве учебного пособия Методическим советом Московского физико-технического института Москва – УДК 519. Н Новиков Д.А. Управление проектами: организационные...»

«Министерство внутренних дел российской федерации Главное управление вневедомственной охраны УТВЕРЖДЕНО Заместителем начальника ГУВО МВД России полковником полиции Е.Н. Потаповым 10 декабря 2012 г. ОБ ЭФФЕКТИВНОМ ПРИМЕНЕНИИ ЗАПИРАЮЩИХ УСТРОЙСТВ, ИМЕЮЩИХСЯ НА ОТЕЧЕСТВЕННОМ РЫНКЕ, ПРИ ОРГАНИЗАЦИИ ОХРАНЫ ИМУЩЕСТВА ГРАЖДАН И ОРГАНИЗАЦИЙ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ Р 78.36.017-2012 Москва Рекомендации разработаны сотрудниками ФКУ НИЦ Охрана МВД России: И.П. Панюшовым, А.В. Гребёнкиным, Р.Н. Гурашовым...»

« ( ) Кафедра промышленной теплоэнергетики О.Ю. Усанова Методические указания к выполнению курсовой работы на тему: Расчет технологической схемы воздухоснабжения промышленного предприятия по дисциплине Технологические энергоносители предприятий для специальности 140104 Промышленная теплоэнергетика МОСКВА 2011 Курсовой проект В курсовом проекте производится расчет технологической схемы воздухоснабжения промышленного предприятия. Основными задачами курсового проекта являются: - систематизация,...»

«Муниципальное бюджетное общеобразовательное учреждение Средняя общеобразовательная школа №3 РАССМОТРЕНО СОГЛАСОВАНО УТВЕРЖДАЮ: Школьным методическим Зам. директора по УВР Директор МБОУ СОШ №3 объединением Н.Б. Приб Т.Б.Петрикант Протокол №_ от_2013г. _2013/14гг. Приказ№_от_2013 Рабочая программа по английскому языку в 10 А, Б классах 2013-2014 учебный год срок реализации Составитель: Ватченко В.А., Калашникова Н. г. Находка. Пояснительная записка Настоящая программа разработана на основе...»

«СМОЛЕНСКИЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ А.Е. Гамбург Занятость населения и ее регулирование Учебно-методическое пособие для студентов заочной формы обучения Смоленск, 2008 ПРОГРАММА (СОДЕРЖАНИЕ) УЧЕБНОЙ ДИСЦИПЛИНЫ Раздел 1. Проблемы занятости и безработицы и рынок труда в России на современном этапе 1.1. Теоретико-методологические подходы к анализу проблем занятости и безработицы Понятие и сущность занятости и безработицы. Стереотипы в понимании проблем занятости и безработицы и возможные пути их...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНЬЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА ПО ИСТОРИИ (России) 1. Организационно-методические указания по проведению экзамена. Экзамен проводится в письменной форме в виде теста и направлен на проверку знаний абитуриентов по истории России. Экзаменационный билет содержит тестовые вопросы в соответствии с...»

«Информация по обеспеченности учебно-методической литературой (бакалавры) № Наименование дисциплин по Наименование учебно-методических, методических и иных материалов( автор, место издания, п/п учебному плану год издания, тираж) 1. УМК по дисциплине История История 1. 2. Отечественная история. Методические рекомендации для самостоятельной работы студентов заочной формы обучения / под ред. Е. М. Харитонова / Сост. Салфетников Д.А., Хоружая С.В. Краснодар: КГАУ, 2009. (тираж 11 экз.) 3. История...»

«Государственное бюджетное образовательное учреждение высшего профессионального образования Оренбургская государственная медицинская академия Минздрава РФ Утверждено на заседании Учебнометодической комиссии по специальности Протокол №_ от _20г. Председатель, (степень, звание, ФИО) МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ СТУДЕНТОВ ПО ИЗУЧЕНИЮ УЧЕБНОЙ ПРАКТИКИ ОБЩИЙ УХОД ЗА БОЛЬНЫМИ ВЗРОСЛЫМИ И ДЕТЬМИ ТЕРАПЕВТИЧЕСКОГО ПРОФИЛЯ Методическое обеспечение утверждено на заседании кафедры факультетской педиатрии _...»

«Содержание 1. Характеристика основной профессиональной образовательной программы подготовки научно-педагогических кадров (ОПОП ПНК) по специальности 10.02.04 – германские языки. 4 2. Нормативная правовая база разработки ОПОП ПНК по специальности 10.02.04 – германские языки..4 3. Требования к уровню подготовки аспирантов, необходимому для освоения основной профессиональной образовательной программы подготовки научно-педагогических кадров по специальности 10.02.04 – германские языки.. 4 4....»

«СИСТЕМА ОБРАЗОВАНИЯ В ВЕНГРИИ Информационный выпуск для иностранных граждан Автор: Medjesi Anna Редактор: Erdlyi Zsuzsanna Фотографии: Hernd Gza and Rnai Gergely Графическое исполнение: Profigram Kft - fortin&Bras Studio Типография: Profilm DTP Kft. © Menedk - Migrnsokat Segt Egyeslet www.menedek.hu Будапешт, 2010 Дорогие дети и родители! В Венгрии, как и в большинстве стран мира, дети, равно как и дети иностранцев, имеют право и обязанность посещать детский сад и школу. Родителяминостранцам и...»

«Л.Н. Краснова, М.Ю. Гинзбург ОрГаНизация, НОрМирОваНие и ОпЛата труда на преДприятиях нефтянОй и газОвОй прОМышленнОсти Допущено УМО по образованию в области производственного менеджмента в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 080502 Экономика и управление на предприятии (по отраслям) УДК 331(075.8) ББК 65.24я73 К78 Рецензенты: А.Д. Галеев, начальник отдела инвестиций НГДУ Азнакаевскнефть ОАО Татнефть, канд. экон. наук,...»

«Департамент образования города Москвы Юго-Восточное окружное управление образования Научно методический центр Государственное бюджетное образовательное учреждение Центр образования №1469 РАБОЧАЯ ПРОГРАММА курса Материальные технологии для учащихся 5 класса Автор - составитель: Ким Татьяна Федоровна учитель высшей квалификационной категории Москва, 2012г. 1 Cодержание УЧЕБНАЯ ПРОГРАММА ПО ТЕХНОЛОГИИ В V КЛАССАХ (БАЗОВЫЙ УРОВЕНЬ) - ГЕНДЕРНЫЙ 3 РЕЗУЛЬТАТЫ ИЗУЧЕНИЯ ПРЕДМЕТА ТЕХНОЛОГИЯ СИСТЕМЫ...»

«1 СОДЕРЖАНИЕ Введение 1. 3 Организационно-правовое обеспечение образовательной деятельности 2. 4 Структура и система управления университетом 3. 7 Органы управления университетом 8 3.1 Структура университета 9 3.2 Структура подготовки бакалавров, специалистов и магистров 4. 14 Образовательные программы, реализуемые в университете 4.1 Сведения о контингенте обучающихся в университете 4.2 Содержание подготовки выпускников 5. Соответствие учебных планов и учебно-методической документации...»

«Министерство образования Учебное пособие и науки РФ рекомендует Бухгалтерский (финансовый) учет В. П. А стахов 9 -е издание Е юрайт В. П. Астахов Бухгалтерский (финансовый) учет УЧЕБНОЕ ПОСОБИЕ 9-е издание, переработанное и дополненное рекомендовано учебно-методическим объединением Министерства образования Российской Федерации в к тств е учебного пособия для студентов высших учебных Заведений, обучающихся по специальности 06.05.00 Бухгалтерский учет, анализ и аудит МОСКВА* ЮРКЙТ • 20П УДК...»

«Тамбовский областной институт повышения квалификации работников образования Н.К. Солопова, О.В. Вязовова ПОИСК, ТВОРЧЕСТВО, НАХОДКИ (проектная деятельность на уроке) Тамбов, 2005 г. 1 ББК 74.263.2 С 60 Авторы-составители: Н.К. Солопова, к.п.н., доцент, зав. кафедрой преподавания дисциплин естественноматематического цикла ТОИПКРО; О.В. Вязовова, зав. кабинетом информатики ТОИПКРО С 60 Предлагаемое учебно-методическое пособие посвящено рассмотрению теоретических, методических, практических...»

«Учреждение образования Белорусский государственный технологический университет УТВЕРЖДЕНА Ректором БГТУ профессором И.М. Жарским 22 марта 2010 г. Регистрационный № УД-268/баз. ТЕПЛОТЕХНИЧЕСКИЕ УСТАНОВКИ И АГРЕГАТЫ ПРЕДПРИЯТИЙ КЕРАМИКИ И ОГНЕУПОРОВ Учебная программа для специальности 1-48 01 01 Химическая технология неорганических веществ, материалов и изделий специализаций 1-48 01 01 09 Технология тонкой функциональной и строительной керамики и 1-48 01 01 11 Химическая технология огнеупорных...»

«А. С. Автономов ЮВЕНАЛЬНАЯ ЮСТИЦИЯ А.С. Автономов ЮВЕНАЛЬНАЯ ЮСТИЦИЯ Учебное пособие Москва 2009 УДК 347.157.1 ББК 67.404.532 ББК 67.711.46 А-225 Автономов А. С. Ювенальная юстиция. Учебное пособие. М.: Российский благотворительный фонд Нет алкоголизму и наркомании (НАН), 2009. — 186 с. Книга, написанная доктором юридических наук, профессором А. С. Автономовым, посвящена вопросам ювенальной юстиции: базовым понятиям, различным подходам и точкам зрения на ювенальную юстицию, проблемам ее...»

«Профилактика табакокурения среди детей и подростков (инструктивно-методические рекомендации для валеологов, педагогов, психологов) Профилактика является наиболее эффективным средством в формировании здоровой личности. Как сделать так, чтобы эффект от проведенного мероприятия был именно профилактическим, т.е. повышающим информированность, формирующим установки на здоровый единственно образ жизни и способствующим принятию верного решения - не пробовать!? В зависимости от степени риска развития...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ _ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Пензенский государственный университет архитектуры и строительства (ПГУАС) МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ ПО НАПРАВЛЕНИЮ АРХИТЕКТУРА ЧАСТЬ 2 ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ ЭКСПОЗИЦИИ Методические указания к практическим занятиям Под общей редакцией доктора технических наук, профессора Ю.П. Скачкова Пенза 2013 УДК 72:378.245.2:378.22(075.8) ББК...»




























 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.