[ главная ]   [ рейтинг статей ]   [ справочник радиолюбителя ]   [ новости мира ИТ ]



Ответов: 0
25-02-12 07:01







   Web - программирование
PHP


ASP






XML



CSS

SSI





   Программирование под ОС











   Web - технологии








   Базы Данных









   Графика






Данные




Программирование под ОС / Алгоритмы /

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

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

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

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

Формальное определение алгоритма

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

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

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

Свойства алгоритма

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

К числу других свойств алгоритма относятся массовость и результативность.

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

Свойство результативности определяет понятие области применимости алгоритма. Областью применимости называется множество слов, для которых алгоритм результативен. Тогда массовость алгоритма – это применимость ко всей области его определения.

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




Комментарии

 Ваш комментарий к данному материалу будет интересен нам и нашим читателям!



Последние статьи: Программирование под ОС / Алгоритмы /

Основные понятия теории алгоритмов - часть первая
09-04-2009   

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

Кол. просмотров: общее - 2979 сегодня - 1

Основные понятия теории алгоритмов - часть вторая
09-04-2009   

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

Кол. просмотров: общее - 3016 сегодня - 1

Основные понятия теории алгоритмов - часть третья
09-04-2009   

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

Кол. просмотров: общее - 3077 сегодня - 1

Основные понятия теории алгоритмов - часть четвертая
09-04-2009   

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

Кол. просмотров: общее - 2768 сегодня - 0

Оценка сложности алгоритмов
09-04-2009   

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

Кол. просмотров: общее - 2961 сегодня - 1



  WWW.COMPROG.RU - 2009-2012 | Designed and Powered by Zaipov Renat | Projects