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

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

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

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

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

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

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

5.1. Доказать, что следующие функции есть примитивно рекурсивные:

a) f(х)= х+n;

б) f(x)= n;

в) f(x)= x!

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

а) g(х)= J_1,1; h(х, у, f(х, у))= f₊(J_3,1, J_3,3);

б) g(х)= J_1,1; h(х, у, f(х, у))= f₊(J_3,1, J_3,2);

в) g(х)= J_1,1; h(х, у, f(х, у))= f₊(J_3,2, J_3,3);

5.3. Применить оператор минимизации к функции f по переменной у. Найти области определения и значения функции .

a) f(a, y) = [y/2];

б) f(x, y) = (x - 2y);

в) f(x, y) = (x² - 2y).

5.4. Построить машину Тьюринга для вычисления функций:

a) f(x)= x/2;

б) f(x)= Sg x;

в) f(x)= [x/2].

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

Т : q_о #  q₁ # П ;

q_о|  q₁ # П ;

q₁ #  q₂ # с ;

q₁ |  q₁ | П .

5.6. Построить машины Тьюринга, выполняющие служебные функции:

a) T₁: #|^{x - 1}q_o|#  q_k|^x# ;

б) T₂: #|^{x - 1}q_o|#  |^x# q_k |^x# ;

в) T₃: q_o|^x# q_k|^x/2 #.

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

T: #|^x # |^{y - 1}q_o|# #|^x#|^y#|^{(x + y) - 1}q_k|#.

5.8. Какие слова могут быть получены при использовании в нормальном алгоритма Маркова правил подстановки: 1) авва; 2) ас  са из слов: а) Р_о = ававав ; б) Р_о = авсавс; в) Р_о = васвас .

Глава 6. Конечные автоматы

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

Единый подход в описании технических и программных средств определил понятие "автомат", как математическую модель системы, обеспечивающей прием, хранение и обработку информации. Ограничение числа параметров математической модели определило другое понятие – “конечный автомат”.

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

При синтезе автоматов формируют систему из элементарных автоматов, эквивалентную заданному абстрактному автомату. Такой автомат называют структурным.