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



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







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


ASP






XML



CSS

SSI





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











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








   Базы Данных









   Графика






Данные




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

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

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

Абстрактным алфавитом называется любая конечная совокупность объектов, называемых буквами или символами данного алфавита. Иными словами алфавит - это конечное множество различимых символов (слово "абстрактный" для краткости здесь и далее опускается). Алфавит, как и любое другое множество, может быть задан перечислением его элементов. Например, алфавит A есть A={a, b, c}, алфавит B есть B={x, y}.

Под словом или строкой в алфавите понимают любую конечную последовательность символов. В последовательности (цепочке) между символами стоит операция сцепки или конкатенации, т.е. менять местами символы в последовательности нельзя. Например, в алфавите А словами являются любые последовательности: a, ac, cb, acb, bb, а в алфавите B: x, y, yx, xx и т. п.

Число символов в слове называется длиной этого слова. Так слова в алфавите А, приведенные в примере, имеют длину соответственно 1, 2, 2, 3, 2. Различают также пустые слова, не содержащие ни одного символа. Слово р называется подсловом слова q, если слово q можно представить в виде q=pr, где r - любое слово, в том числе и пустое. Очевидно, что такое понятие слова будет отличаться от аналогичного в разговорных языках. Здесь под словом можно понимать любую последовательность символов, даже бессмысленную.

При расширении алфавита понятие слова может существенно меняться. Так, например, в алфавите A={0,1,2,3,4,5,6,7,8,9} цепочка символов 69+73 представляет собой два слова, соединенные знаком суммы, а в алфавите В={+,0,1,2,3,4,5,6,7,8,9} это будет одно слово.

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

Пусть заданы слова в алфавитах X и Y и заданы соответствия между этими словами. Если xi – слово в алфавите X, а yj – слово в алфавите Y, то алфавитный оператор Гxi=yj преобразует входное слово xi в выходное слово yj. Символ Г в алфавитном операторе означает отображение.

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

Совокупность всех слов, на которых алфавитный оператор определен, называется областью его определения. Алфавитный оператор, не сопоставляющий данному входному слову ai никакого выходного слова bj (в том числе и пустого), на этом слове не определен.



Комментарии

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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