Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов (1082244), страница 2
Текст из файла (страница 2)
Алфавит, каклюбое множество, задается перечислением его элементов.Итак, объекты реального мира можно изображать словами в различных алфавитах. Этопозволяет считать, что объектами работы алгоритмов могут быть только слова. Тогда можносформулировать следующее определение.Алгоритм есть четкая конечная система правил для преобразования слов из некоторогоалфавита в слова из этого же алфавита.Слово, к которому применяется алгоритм, называется входным. Слово, вырабатываемоев результате применения алгоритма, называется выходным.Совокупность слов, к которым применим данный алгоритм, называется областьюприменимости этого алгоритма.Формальные определения алгоритма появились в 30-х - 40-х годах XX века.
Можновыделить три основных типа универсальных алгоритмических моделей, различающихсяисходными эвристическими соображениями относительно того, что такое алгоритм. Первыйтип связывает понятие алгоритма с наиболее традиционными понятиями математики вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа рекурсивные функции - является исторически первой формализацией понятия алгоритма.Эта модель основана на функциональном подходе и рассматривает понятие алгоритма сточки зрения того, что можно вычислить с его помощью.Второй тип основан на представлении алгоритма как некоторого детерминированногоустройства, способного выполнять в каждый отдельный момент некоторые примитивныеоперации, или инструкции. Такое представление не оставляет сомнений в однозначностиалгоритма и элементарности его шагов.
Основной теоретической моделью этого типа,созданной в 30-х годах, является машина Тьюринга, которая представляет собойавтоматную модель, в основе которой лежит анализ процесса выполнения алгоритма каксовокупности набора инструкций.Третий тип алгоритмических моделей - это преобразования слов в произвольныхалфавитах, в которых элементарными операциями являются подстановки, т.е. замены частислова (подслова) другим словом. Преимущество этого типа состоит в его максимальнойабстрактности и возможности применить понятие алгоритма к объектам произвольнойприроды. Модели второго и третьего типа довольно близки и отличаются в основномэвристическими подходами.
Примерами моделей этого типа являютсянормальныеалгоритмы Маркова и канонические системы Поста.1.4. Понятие алфавитного оператораПонятие алфавитного оператора является наиболее общим. К нему фактически сводятсялюбые процессы преобразования информации. К изучению алфавитных операторовфактически сводится теория любых преобразователей информации.
Основой теорииалфавитных операторов являются способы их задания. Если область определенияалфавитного оператора конечна, то оператор может быть задан простой таблицейсоответствия. В случае бесконечной области определения алфавитного оператора он задаетсясистемой правил, позволяющей за конечное число шагов найти выходное слово,соответствующее заданному входному слову. Алфавитные операторы, задаваемые спомощью конечной системы правил, называются алгоритмами.Алгоритмы, в соответствии с которыми решение поставленных задач сводится карифметическим действиям, называются численными алгоритмами.Алгоритмы, в соответствии с которыми решение поставленных задач сводится клогическим действиям, называются логическими алгоритмами.Различают однозначные и многозначные алфавитные операторы.Под однозначным алфавитным оператором понимается такой алфавитный оператор,который каждому входному слову ставит в соответствие не более одного выходного слова.Под многозначным алфавитным оператором понимается такой алфавитный оператор,который каждому входному слову ставит в соответствие более одного выходного слова.никакогоАлфавитный оператор, не сопоставляющий данному входному слову аiвыходного слова bj (в том числе и пустого), не определен на этом слове.Совокупность всех слов, на которых алфавитный оператор определен, называетсяобластью его определения.Два алфавитных оператора считаются равными, если равны соответствующие ималфавитные операторы и совпадает система правил, задающих действие этих алгоритмов навыходные слова.Два алгоритма считаются эквивалентными, если у них совпадают алфавитныеоператоры, но не совпадают способы их задания (система правил).
Обычно в теорииалгоритмов рассматриваются лишь такие алгоритмы, которым соответствуют однозначныеалфавитные операторы.1.5. Задания для самостоятельной работыВо всех заданиях необходимо разработать схемы алгоритмов и проанализироватьпроцесс реализации алгоритма, т.е. последовательность шагов, которая будет порождена приприменении алгоритма к конкретным исходным данным.1. Разработать словесные алгоритмы вычитания из некоторого числа Апоследовательности n чисел b1, b2, ..., bn:а) алгоритм вычисления по формуле:C=(...((A - b1) - b2) - ...
- bn)б) алгоритм вычисления по формуле:nC = A − ∑ bi .i =12. Разработать алгоритм вычисления по формуле:nC k = ∑ a i − b k (1 ≤ i ≤ n, 1 ≤ k ≤ m) .i =13. Разработать алгоритм вычисления по формуле:mC i = ∏ a k × b i (1 ≤ i ≤ m, 1 ≤ k ≤ m) .k =14. Разработать алгоритм поиска максимального (минимального) элемента изпоследовательности, заданной в виде одномерного массива А = {a1, a2, ... , ak}.5. Разработать алгоритм определения количества одинаковых чисел впоследовательности, заданной в виде одномерного массива А={a1, a2, . . . , ak}.6.
Разработать алгоритм подсчета количества одинаковых элементов в матрице Bразмерностью n × m. Размерность матрицы вводится с клавиатуры.7. Разработать алгоритм умножения матрицы на вектор.8. Разработать алгоритм умножения матрицы на матрицу.9. Разработать алгоритм транспонирования матрицы.10. Разработать алгоритм, реализующий операцию объединенияследующих двухмножеств:A = {a1, a2, . . ., ak} и B= {b1, b2, ... , bn}2. РЕКУРСИВНЫЕ ФУНКЦИИ2.1.
Общие сведенияПервой алгоритмической системой была система, основанная на использованииконструктивно определяемых арифметических (целочисленных) функций, получившихспециальное название рекурсивных функций.Рекурсией называется способ задания функции, при котором значение определяемойфункции для произвольных значений аргументов выражается известным образом череззначения определяемой функции для меньших значений аргументов.Применение рекурсивных функций в теории алгоритмов основано на идее нумерациислов в произвольном алфавите последовательными натуральными числами.
Наиболее простотакую нумерацию можно осуществить, располагая слова в порядке возрастания их длин, аслова, имеющие одинаковую длину, - в произвольном порядке.После нумерации входных и выходных слов в произвольном алфавитном операторе этотоператор превращается в функцию y = f(x), в которой аргумент х и функция y принимаютнеотрицательные целочисленные значения. Функция f(x) может быть определена не для всехзначений х, а лишь для тех, которые составляют область определения этой функции.2.2. Понятие простейших функцийЧисловые функции, значение которых можно установить посредством некоторогоалгоритма, называются вычислимыми функциями.Для того чтобы описать класс функций с помощью рекурсивных определений,рассмотрим набор простейших функций:1) Z(x1, x2, ..., xn) = 0- нуль-функция, которая определена для всех неотрицательныхзначений аргумента;2) s(x) = x+1 - функция непосредственного следования, также определенная для всехцелых неотрицательных значений своего аргумента;3) I nm (x1, x2, .
. ., xm, . . . , xn) = xm - функция выбора (тождества), повторяющая значениясвоих аргументов.Используя простейшие функции в качестве исходных функций, можно с помощьюнебольшого числа общих конструктивных приемов строить сложные арифметическиефункции. В теории рекурсивных функций особо важное значение имеют три операции:суперпозиции, примитивной рекурсии и минимизации.2.2.1.
Оператор суперпозицииОператором суперпозиции S называется подстановка в функцию от m переменных mфункций от n одних и тех же переменных. Она дает новую функцию от n переменных.Например, из функций f(x1, x2, ..., xm), f1(x1, x2, ..., xn), f2(x1, x2, ..., xn), . . ., fm(x1, x2, ..., xn)можно получить новую функцию:Sm+1(f, f1, f2, ..., fm) = g(x1, x2, ..., xn) = f(f1(x1, x2, ..., xn), f2(x1, x2, ..., xn), ..., fm(x1, ..., xn)).(1)В операции суперпозиции Sm+1 индекс сверху указывает на число функций.Таким образом, при помощи оператора суперпозиции и функции выбора можновыразить любую подстановку функции в функцию.Например, осуществляя операцию суперпозиции функций f(x) = 0 и g(x) = x+1, получимфункцию:h(x) = g(f(x)) = 0 + 1 = 1.При суперпозиции функции g(x) с этой же функцией получим функцию h(x) = g(g(x)) = x+ 2.Используя подстановку и функции тождества, можно переставлять и отождествлятьаргументы в функции:f(x2, x1, x3, .
. ., xn) = f(I22(x1, x2), I12(x1, x2), x3, . . ., xn);f(x1, x1, x3, . . ., xn) = f(I12(x1, x2), I12(x1, x2), x3, . . ., xn).Таким образом, если заданы функции тождества и операторы суперпозиции, то можносчитать заданными всевозможные операторы подстановки функций в функции, а такжепереименования, перестановки и отождествления переменных.2.2.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
