Нормальные алгоритмы маркова реферат

Обновлено: 04.07.2024

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

В этом уточнении выделенные нами 7 параметров были определены следующим образом:

Совокупность исходных данных - слова в алфавите S;

Совокупность возможных результатов - слова в алфавите W;

Совокупность возможных промежуточных результатов - слова в алфавите

Р=S W V, где V - алфавит служебных вспомогательных символов.

Действия имеют вид либо a®g, либо aag, где a, gÎP * , где

P* - множество слов над алфавитом Р, и называется правилом подстановки. Смысл этого правила состоит в том, что обрабатываемое слово w просматривается слева направо и ищется вхождение в него слова a.

Определение.3.1. Слово a называется вхождением в слово w, если существуют такие слова b и n над тем же алфавитом, что и a и w, для которых верно: w=ban.

Если вхождение a в w найдено, то слово a заменяется на слово g.

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

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

Правило начала - просмотр правил всегда начинается с первого.

Правило окончания - выполнение алгоритма заканчивается, если:

было применено правило подстановки вида aag,

не применимо ни одно правило подстановки из схемы алгоритма.

7. Правило размещения результата - слово, полученное после окончания выполнения алгоритма.

Рассмотрим пример 1 из лекции 2:

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

Cхема этого НАМ показана на рисунке 3.1.

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

Увеличиваем на единицу, начиная с цифр младших разрядов.

Рис.3.1. Схема НАМ для вычисления U₁ (n)=n+1

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

где k - количество цифр в n, l - количество 9, которые были увеличены на 1.

Но в любом случае сложность НАМ для U₁ (n) больше сложности Машины Тьюринга для этой же функции, которая равнялась k+1.

Обратите внимание, что у НАМ порядок следования правил подстановки в схеме алгоритма существенно влияет на результат, в то время как для МТ он не существеннен.

Построим НАМ для примера 2 из лекции 2:

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

Итак, S=<|>; W=S; V=Æ, т.е. пусто.

Cложность этого алгоритма равна 1, в то время как сложность алгоритма для Машины Тьюринга равнялась n.

Теперь построим НАМ для примера 3 из лекции 2:

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

Схема этого алгоритма приведена на рисунке 3.2.

Сложность этого НАМ будет n+[log₁₀ n], что существенно меньше сложности для Машины Тьюринга, вычисляющей эту функцию, которая равнялась n 2 +[log₁₀ n(log₁₀ n+1)].

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

Замечание: исходное слово надо задать в форме *

Для нормальных алгоритмов Маркова справедлив тезис, аналогичный тезису Тьюринга.

Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий.

Построение алгоритмов из алгоритмов.

До сих пор, строя ту или иную МТ, или НАМ мы каждый раз все делали заново. Естественно задать вопрос, а нельзя ли при построении, например, новой МТ пользоваться уже построенной ранее МТ.

Например, МТ₃ из примера 3

по существу есть надлежащим образом объединенные МТ для U₁ (n)=n+1 и U₂ ((n)₁ )=(n-1)₁ .

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

Мы рассмотрим эту проблему применительно к МТ. Однако все сформулированные нами утверждения будут справедливы и для НАМ и для других эквивалентных уточнений понятия алгоритма. Эквивалентость уточнений понятия алгоритма мы рассмотрим позже.

Определение.3.2. Будем говорить, что МТ₁ можно эффективно построить из МТ₂ и МТ₃ если существует алгоритм, который позволяет, имея программу для МТ₂ и МТ₃ , построить программу для МТ₃ .

Определение.3.3.Последовательной композицией МТ А и В называется такая МТ С, что

область применимости МТ А и С совпадают;

Другими словами, применение С к слову a дает такой же результат, как последовательное применение к этому же слову сначала А, а потом к результату применения А - В.

Последовательную композицию МТ_А и МТ_В будем обозначать АoВ.

Теорема 3.1. Пусть даны МТ А и В, такие, что В применима к результатам работы А и Q_A Q_B =Æ.

Тогда можно эффективно построить МТ С такую, что С= АoВ.

В качестве алфавита данных и множества состояний для МТ_С возьмем объединение алфавитов данных и множеств состояний для А и В, т.е.

D_C =D_A D_В , Q_C = Q_A Q_B

В программе для А все правила ap®b!w, где a,bÎD_A *, wÎ заменим на ap®bq_o B w, где q_o B ÎQ_B - начальное состояние для В. Это обеспечит включение В в тот момент, когда А свою работу закончила и не раньше, т.к. Q_A Q_B =Æ.

Табличная запись программы для С показана на рисунке 3.3.

Рис 3.3 Структура табличной записи программ для Машины С.

Определение3.4.Параллельной композицией Машин Тьюринга А и В назовем такую Машину С, для которой:

D_C =D_A D_B

Q_C =Q_A Q_B

Из этого определения видно, что порядок применения МТ_А и МТ_В не влияет на результат. Он будет такой же как если бы мы независимо применили А к слову a, а В к слову b.

Теорема 3.2 Для любых МТ А и МТ В можно эффективно построить МТ С такую, что С=А||В

Обоснование. Мы не будем давать здесь строго доказательства в виду его технической сложности. Покажем лишь обоснование правильности утверждения теоремы. Обозначим D_C =D_A D_B ; Q_C =Q_A Q_B _.

Основная проблема: как гарантировать чтобы А не затронула слово b , а В - словоa . Для этого введем в алфавит D_С символ ||. Добавим для всех состояний q_i ÎQ_C таких, что q_i ÎQ_A правила вида ||q_i ®||q_i Л, т.е. каретка машины А будет, натыкаясь на символ ||, уходить влево. Соответственно для всех q_j ÎQ_C таких, что q_j ÎQ_B добавим правила вида ||q_j ®||q_j П, т.е. каретка машины В будет уходить вправо. Тем самым мы как бы ограничиваем ленту для А справа, а для В слева.

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

Оказывается справедливо следующее утверждение: множество алгоритмов, реализуемых МТ с полулентой, эквивалентно множеству алгоритмов, реализуемых МТ с полной лентой. Обозначим Ф(Р) Машину Тьюринга, реализующую распознающий алгоритм:

Теорема 3.3. Для любых Машин Тьюринга А, В и Ф, имеющих один и тот же алфавит S, может быть эффективно построена машина С над тем же алфавитом S, такая что

Обозначим: E(Р) тождественную машину, т.е. Е(Р)=Р

СOPY(Р) копирующую машину, т.е. СOPY(Р)=Р||Р,

BRANCH(P) - эта машина переходит либо в состояние р₁ , либо в состоянии р_о . Ее программа состоит из 4-х команд:

Эта машина строится по следующей формуле:

Согласно теоремам 3.1 и 3.2., мы можем построить машину , зная Е, Ф и COPY. Теперь, имея , BRNCH, A и В, можно построить машину С следующим образом:

Машина oBRANCH заканчивает свою работу либо в состоянии р₁ , если слово P обладает нужным свойством, либо в состоянии р_о , находясь в начале слова P. Поэтому, если принять у машины А состояние р₁ , как начальное, а у машины В состояние р_о , как начальное, то машина А будет включена при условии, что Ф(Р)=1, а машина В будет включена, если Ф(Р)=0.

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

Теорема 3.4. Для любых машин А и Ф можно эффективно построить машину L такую, что

Доказательство: Заменим в доказательстве теоремы 3.3. машину В машиной Е, а заключительное состояние в машине В заменим на начальное состояние в машине . В итоге получим нужный результат.

Теорема 3.5. (Бомм, Джакопини, 1962)

Любая Машина Тьюринга может быть построена с помощью операции композиций o, || , если Ф, то А иначе В, пока Ф применяй А.

Эту теорему мы даем здесь без доказательства.

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

Следствие 3.2 Мы получили что-то вроде языка, на котором можно описывать новую Машину Тьюринга, используя описания уже существующих, а затем, используя теоремы 3.1 - 3.4, построить её функциональную схему.

Следствие 3.3 Алгоритм - это конструктивный объект. В случае Машины Тьюринга атомарными объектами являются команды, а теорема 3.5 определяет правила композиции.

Алгоритм - конструктивный объект;

Алгоритм можно строить из других алгоритмов;

o, ||, if_then_else, while_do - универсальный набор действий по управлению вычислительным процессом.

Понятие нормального алгоритма Маркова как одного из стандартных способов формального определения понятия алгоритма. Особенности понятия ассоциативного исчисления. Характеристика суперпозиции, объединения, разветвления и итерации алгоритмов и их специфика.

Рубрика	Математика
Вид	реферат
Язык	русский
Дата добавления	03.10.2014
Размер файла	16,8 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

1. Нормальный алгоритм Маркова

Список использованных источников

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

Нормальный алгоритм Маркова обычно понимают как некий упорядоченный набор продукций(замен подстрок). Продукции могут быть как и обыкновенными(выполняться столько раз, сколько это возможно) так и финальными(выполняются только 1 раз и после них работа алгоритма заканчивается). Продукции выполняются начиная с первой. Если первую выполнить нельзя -- делаем вторую итд. Если же после какой-либо продукции можно опять выполнить какую-то из предудущих -- выполняем. Работа алгоритма закнчивается тогда, когда нет следующей для выполнения продукции и все предыдущие нельзя выполнить или после выполнения какой-нибудь финальной продукции.

1. Нормальный алгоритм Маркова

Для формализации понятия алгоритма российский математик А.А. Марков предложил использовать ассоциативные исчисления.

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

Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М.

Зададим в некотором алфавите конечную систему подстановок

где N, М, S, Т. - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N.

Например, в алфавите А = имеются слова N = ab, М = bcb, К = abcbcbab, Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab или аbсаbаb.

Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

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

Последовательность слов Р, P1, Р2. М называется дедуктивной цепочкой, ведущей от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки - смежное.

Слова Р и М называют эквивалентными, если существует цепочка от Р к М и обратно.

Слова abcde и acbde - смежные (подстановка bc - cb). Слова abcde - cadbe эквивалентны.

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

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

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

Алфавит: Система подстановок В:

Предписание о применении подстановок: в произвольном слове Р надо сделать возможные подстановки, заменив левую часть подстановок на правую; повторить процесс с вновь полученным словом.

Так, применяя систему подстановок В из рассмотренного примера к словам babaac и bсaсаbс получаем:

babaac > bbcaaac > остановка

bcacabc > bcacbcac > bcacccac > bсасаbс > бесконечные процесс (остановки нет), так как мы получили исходное слово.

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

Такой набор предписаний вместе с алфавитом А и набором подстановок В определяют нормальный алгоритм. Процесс останавливается только в двух случаях: 1) когда подходящая подстановка не найдена; 2) когда применена последняя подстановка из их набора. Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами подстановок.

Приведем пример нормального алгоритма, описывающего сложение -натуральных чисел (представленных наборами единиц).

Алфавит: Система подстановок В:

Слово Р: 11+11+111

Последовательная переработка слова Р с помощью нормального алгоритма Маркова проходит через следующие этапы:

Р = 11 + 11 + 111 Р5 = + 1 + 111111

Р1 = 1 + 111 + 111 Р6 = ++ 1111111

Р2 = + 1111 + 111 Р7 = + 1111111

Р3 = + 111 + 1111 Р8 = 1111111

Р4 = + 11 + 11111 Р9 = 1111111

Нормальный алгоритм Маркова можно рассматривать как универсальную форму задания любого алгоритма. Универсальность нормальных алгоритмов декларируется принципом нормализации: для любого алгоритма в произвольном конечном алфавите А можно построить эквивалентный ему нормальный алгоритм над алфавитом А,

Разъясним последнее утверждение. В некоторых случаях не удается построить нормальный алгоритм, эквивалентный данному в алфавите А, если использовать в подстановках алгоритма только буквы этого алфавита. Однако, можно построить требуемый нормальный алгоритм, производя расширение алфавита А (добавляя к нему некоторое число новых букв). В этом случае говорят, что построенный алгоритм является алгоритмом над алфавитом А, хотя он будет применяться лишь к словам в исходном алфавите A. алгоритм марков ассоциативный исчисление

Если алгоритм N задан в некотором расширении алфавита А, то говорят, что N есть нормальный алгоритм над алфавитом А.

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

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

I. Суперпозиция алгоритмов. При суперпозиции двух алгоритмов А и В выходное слово первого алгоритма рассматривается как входное слово второго алгоритма В. Результат суперпозиции С может быть представлен в виде С(р) = В(А(р)),

II. Объединение алгоритмов. Объединением алгоритмов А и В в одном и том же алфавите называется алгоритм С в том же алфавите, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В, в записанные рядом слова А(р) и В(р).

III. Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов А, В и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = B(p), если С(р) = е, где е - пустая строка.

IV. Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

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

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

Список использованной литературы

1. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ вычислительных алгоритмов. / М., Мир, 1979г., 536С.

2. Аляев Ю., Козлов О. Алгоритмизация и языки программирования Pascal, C++, VisualBasic. - М.: Финансы и статистика, 2003.

3. Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие.- М.: Форум: Инфра-М, 2004.

6. Семакин И.Г., Шестаков А.П. Основы программирования: Учебник. - М.: Мастерство, 2001

7. Успенский, В. А.; Семенов, А. Л. Теория алгоритмов: математические основы, 3 -е изд. - М.: Наука, 2005.

Подобные документы

Основные понятия теории марковских цепей. Теория о предельных вероятностях. Области применения цепей Маркова. Управляемые цепи Маркова. Выбор стратегии. Оптимальная стратегия является марковской - может зависеть еще и от момента времени принятия решения.

реферат [75,6 K], добавлен 08.03.2004

Цепь Маркова как простой случай последовательности случайных событий, области ее применения. Теорема о предельных вероятностях в цепи Маркова, формула равенства Маркова. Примеры для типичной и однородной цепи Маркова, для нахождения матрицы перехода.

курсовая работа [126,8 K], добавлен 20.04.2011

Нове уточнення поняття алгоритму вітчизняним математиком Марковим: 7 уточнених ним параметрів. Побудова алгоритмів з алгоритмів. Універсальний набір дій по управлінню обчислювальним процесом. Нормальні алгоритми Маркова. Правило розміщення результату.

реферат [48,7 K], добавлен 30.03.2009

Доказательство существования или отсутствия алгоритма для решения поставленной задачи. Определение алгоритмической неразрешимости задачи. Понятия суперпозиции функций и рекурсивных функций. Анализ схемы примитивной рекурсии и операции минимизации.

курсовая работа [79,5 K], добавлен 12.07.2015

Цепи Маркова как обобщение схемы Бернулли, описание последовательности случайных событий с конечным или счётным бесконечным числом исходов; свойство цепей, их актуальность в информатике; применение: определение авторства текста, использование PageRank.

Курсовая написана студенткой АГПИ, состоит из 43стр. В курсовую работу входят такие главы как: неформальное понятие алгоритма, основные требования к алгоритмам, необходимость в математическом уточнение понятия алгоритма, нормальны алгоритмы Маркова, присоединяющее алгоритмы, сокращающие алгоритмы,сокращающий алгоритм, удваивающий алгоритм, вприменение теории нормальных алгоритмов,

Воробьев В.П., Грибунин В.Г. Теория и практика вейвлет-преобразования

формат djvu
размер 554.67 КБ
добавлен 23 января 2012 г.

Санкт-Петербург, 1999 г. Излагаются основные вопросы теории вейвлет-преобразования; рассмотрены принципы построения вейвлет-фильтров, практические аспекты осуществления преобразования, современные направления исследований в этой области; обсуждаются алгоритмы сжатия изображений с использованием вейвлет-преобразования; приведены технические данные о микросхемах АDV6хх,осуществляющих сжатие видео на основе этой технологии; в приложениях представлен.

Воронцов К.В. Лекции по алгоритмам кластеризации и многомерного шкалирования

формат pdf
размер 253.95 КБ
добавлен 06 апреля 2011 г.

Кластеризация и многомерное шкалирование. Алгоритмы кластеризации. Эвристические графовые алгоритмы. Функционалы качества кластеризации. Статистические алгоритмы. Иерархическая кластеризация. Многомерное шкалирование.

Кузнецов Г.В., Фомичев В.В., Сушко С.О., Фомичева Л.Я. Математические основы криптографии (УКР)

формат djvu
размер 14.26 МБ
добавлен 26 мая 2011 г.

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

Курсовая работа - Логико-математический анализ темы Квадратные неравенства

формат docx
размер 597.05 КБ
добавлен 06 октября 2011 г.

Курсовая работа - Логико-математический анализ темы Линейная функция, ее свойства и график в курсе математики 7-11 классах

формат doc
размер 97.79 КБ
добавлен 24 мая 2011 г.

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

Курсовая работа - Логико-математический анализ темы Параллельность прямых и плоскостей в курсе геометрии 10-11 классов

формат doc
размер 444 КБ
добавлен 24 мая 2011 г.

Курсовая работа по прикладной математике

формат doc
размер 781 КБ
добавлен 20 сентября 2011 г.

Пинскер И.Ш. (ред.) Поиск зависимости и оценка погрешности

формат djvu
размер 2.54 МБ
добавлен 10 марта 2011 г.

М.: Наука, 1985. - 148 с. (600 dpi) Сборник посвящен одному из наиболее актуальных направлений прикладной математики — анализу данных. Рассматриваются различные алгоритмы выявления зависимостей, содержащихся в эмпирических данных. Большое внимание уделяется оценке качества найденного решения. Анализируются известные методы и предлагаются новые. Сборник предназначен для широкого круга специалистов в области математического моделирования, кибернет.

Сахаров В.Л., Андреенко А.С. Методы математической обработки электроэнцефалограмм

формат pdf
размер 571.05 КБ
добавлен 17 ноября 2011 г.

Учебное пособие. - Таганрог: "Антон",2000. - 44 с. В пособии рассмотрены различные математические методы обработки и анализа электроэнцефалограмм. Приведены основные параметры электроэнцефалографического сигнала и методы регистрации сигнала и его физиологические особенности. Предложены основные алгоритмы компьютерной обработки электроэнцефалограммы.

Шпаргалка для экзамена по Математике и Информатике

формат doc
размер 263 КБ
добавлен 30 июня 2011 г.

Данная работа содержит 23 листа с ответами на следующие вопросы по курсу "Математика и информатика": Аксиомы и теоремы. Математические доказательства. Алгоритмы. Виды алгоритмов. Базы данных. СУБД. Вероятность. Виды вероятностей. Виды моделей. Геометрия Эвклида. Основные понятия эвклидовой геометрии. бальные сети ЭВМ. Информационные модели. Локальные сети ЭВМ. Методы вычисления неопределенных интегралов. Моделирование процессов. Операционная сис.

ГОСТ

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

Теоретические основы нормальных алгоритмов были сформулированы видным математиком Советского Союза А.А. Марковым в конце сороковых годов двадцатого века. Они явились некоторыми базовыми правилами по обработке словесных символов в каких-либо алфавитах, то есть начальными информационными данными и итоговыми результатами таких алгоритмов выступали буквы некоторого алфавита.

Подстановки Маркова

Под алфавитом понимается любые непустые множества. Компоненты алфавита именуются буквами, а все последовательные буквенные наборы считаются словами данного алфавита. При этом могут существовать и пустые слова, то есть не имеющие букв в своём составе. Пустые слова обозначаются символом Ʌ. Если A и B являются двумя алфавитами, и при этом алфавит A принадлежит алфавиту B, то алфавит B выступает как расширение алфавита A. Выполнять обозначение слов принято при помощи латинских букв: P, Q, R. Все слова могут являться составными частями других слов. В этом варианте первое слово считается подсловом второго слова или его вхождением. К примеру, если А является русскоязычным алфавитом, то рассмотрим следующие слова $P_1$= paragraph, $P_2$ = graf, $P_3$ = ra. Слово $P_2$ считается подсловом $P_1$, а $P_3$ это подслово $P_1$ и $P_2$, при этом в $P_1$ присутствует двойное вхождение.

Подстановкой Маркова является процедура над словами, которая выполняется при помощи двух упорядоченных слов (P, Q), и состоит в таких действиях. В выбранном слове R определяется первое вхождение слова P (при наличии такого) и, без коррекции других фрагментов слова R, подменяют в нём данное вхождение словом Q. Сформированное в итоге слово является результатом использования подстановки Маркова (P, Q) к слову R. В случае отсутствия первого вхождения P в слово R, то есть вхождения полностью отсутствуют, то это означает неприменимость подстановки Маркова (P, Q) к слову R.

Частным случаем подстановок Маркова считаются подстановки с использованием пустых слов:

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

Рисунок 1. Примеры подстановок Маркова. Автор24 — интернет-биржа студенческих работ

Готовые работы на аналогичную тему

Чтобы обозначить Марковскую подстановку (P, Q), применяется запись P → Q. Она носит название формулы подстановки (P, Q). Отдельные подстановки (P, Q) называются заключительными. Чтобы обозначить такие подстановки применяется запись P → Q, которая называется формулой заключительной подстановки. Слово P является левой частью, а слово Q считается правой частью в формуле подстановки.

Нормальные алгоритмы Маркова

Финальный перечень формул подстановок после упорядочения представлен ниже:

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

Нормальным алгоритмом Маркова в алфавите А является определённый закон формирования очерёдности слов Vi в алфавите A, на основании заданного слова V в выбранном алфавите. Начальным словом V0 очерёдности слов назначается слово V. Предположим, что некоторого значения i ≥ 0 слово Vi сформировано, и процедура реализации данной последовательности пока не завершена. В случае отсутствия в схеме нормального алгоритма формул, у которых левая часть вошла бы в Vi, то Vi+1 считается равным Vi, что даёт право считать процедуру формирования последовательности завершённой. Но когда в схеме присутствуют формулы, у которых левые части входят в Vi, то за значение Vi+1 принимается итог подстановки Маркова правой части начальной в этих формулах, замещая первое вхождение её левой части в слово. Процедура формирования последовательности может считаться завершённой, когда в текущем шаге использовалась формула финальной подстановки, в противном случае процесс продолжает выполняться. В случае обрыва процедуры формирования упомянутой последовательности, то считается, что текущий нормальный алгоритм можно применить к слову V. Оконечный элемент W последовательности является итогом использования нормального алгоритма к слову V. То есть, по сути, при помощи нормального алгоритма перерабатывается V в W.

Последовательность Vi записывается в таком порядке:

V0 ⇨ V1 ⇨ V2 ⇨ … ⇨ Vm-1 ⇨ Vm.

Здесь V0 = V, а Vm = W.

Это определение является понятием нормального алгоритма в алфавите A. В случае задания алгоритма в каком-либо алфавитном расширении A, то считается, что он является нормальным алгоритмом над A.

Приведём пример нормального алгоритма. Имеется алфавит A = . Будем рассматривать такую схему нормального алгоритма в A:

Задаваемый данной схемой алгоритм работает следующим образом. Любое слово V в алфавите A, которое содержит даже единственное вхождение буквы a, алгоритм переработает в слово, формирующееся из V путём вычёркивания в нём самого первого вхождения символа a. А если слово является пустым, то алгоритм выполняет его переработку также в пустое. Данный алгоритм не может быть использован со словами, содержащими лишь только букву b. К примеру:

aabab ⇨ abab, ab ⇨ b, aa ⇨ a, bbab ⇨ bbb, baba ⇨ bba.

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

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.

В этом уточнении выделенные нами 7 параметров были определены следующим образом:

Совокупность исходных данных - слова в алфавите S;

Совокупность возможных результатов - слова в алфавите W;

Совокупность возможных промежуточных результатов - слова в алфавите

Р=S W V, где V - алфавит служебных вспомогательных символов.

Действия имеют вид либо a®g, либо a a g, где a, g Î P * , где

P * - множество слов над алфавитом Р, и называется правилом подстановки. Смысл этого правила состоит в том, что обрабатываемое слово w просматривается слева направо и ищется вхождение в него слова a.

Если вхождение a в w найдено, то слово a заменяется на слово g.

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

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

Правило начала - просмотр правил всегда начинается с первого.

Правило окончания - выполнение алгоритма заканчивается, если:

было применено правило подстановки вида a a g,

не применимо ни одно правило подстановки из схемы алгоритма.

7. Правило размещения результата - слово, полученное после окончания выполнения алгоритма.

Рассмотрим пример 1 из лекции 2:

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

C хема этого НАМ показана на рисунке 3.1.

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

Увеличиваем на единицу, начиная с цифр младших разрядов.

Вводим служебный символ * в слово, чтобы им отметить последнюю цифру в слове.

Рис.3.1. Схема НАМ для вычисления U 1 ( n )= n +1

где k - количество цифр в n , l - количество 9, которые были увеличены на 1.

Но в любом случае сложность НАМ для U 1 ( n ) больше сложности Машины Тьюринга для этой же функции, которая равнялась k +1.

Построим НАМ для примера 2 из лекции 2:

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

Итак , S=<|>; W=S; V= Æ , т . е . пусто .

C ложность этого алгоритма равна 1, в то время как сложность алгоритма для Машины Тьюринга равнялась n .

Теперь построим НАМ для примера 3 из лекции 2:

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

Схема этого алгоритма приведена на рисунке 3.2.

Рис. 3.2. Схема НАМ для вычисления U 3 (( n ) 1 )=( n ) 10.

Сложность этого НАМ будет n +[ log 10 n ], что существенно меньше сложности для Машины Тьюринга, вычисляющей эту функцию, которая равнялась n 2 +[ log 10 n ( log 10 n +1)].

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

Замечание: исходное слово надо задать в форме *

Для нормальных алгоритмов Маркова справедлив тезис, аналогичный тезису Тьюринга.

Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий.

Построение алгоритмов из алгоритмов.

Например, МТ 3 из примера 3

по существу есть надлежащим образом объединенные МТ для U 1 ( n )= n +1 и U 2 (( n ) 1 )=( n -1) 1 .

Определение.3.2. Будем говорить, что МТ 1 можно эффективно построить из МТ 2 и МТ 3 если существует алгоритм, который позволяет, имея программу для МТ 2 и МТ 3 , построить программу для МТ 3 .

Определение.3.3.Последовательной композицией МТ А и В называется такая МТ С, что

область применимости МТ А и С совпадают;

Последовательную композицию МТ А и МТ В будем обозначать АoВ.

Теорема 3.1. Пусть даны МТ А и В, такие, что В применима к результатам работы А и Q A Q B = Æ .

Тогда можно эффективно построить МТ С такую, что С= АoВ.

В качестве алфавита данных и множества состояний для МТ С возьмем объединение алфавитов данных и множеств состояний для А и В, т.е.

D C =D A D В , Q C = Q A Q B

В программе для А все правила a p ®b ! w , где a , bÎ D A *, wÎ заменим на a p ®b q o B w , где q o B Î Q B - начальное состояние для В. Это обеспечит включение В в тот момент, когда А свою работу закончила и не раньше, т.к. Q A Q B = Æ .

Табличная запись программы для С показана на рисунке 3.3.

Рис 3.3 Структура табличной записи программ для Машины С.

Определение3.4. Параллельной композицией Машин Тьюринга А и В назовем такую Машину С, для которой:

C( a || b )=A( a || b ) ° B=B( a || b ) ° A=A( a )||B( b ) .

Из этого определения видно, что порядок применения МТ А и МТ В не влияет на результат. Он будет такой же как если бы мы независимо применили А к слову a, а В к слову b.

Теорема 3.2 Для любых МТ А и МТ В можно эффективно построить МТ С такую, что С=А||В

Обоснование. Мы не будем давать здесь строго доказательства в виду его технической сложности. Покажем лишь обоснование правильности утверждения теоремы. Обозначим D C = D A D B ; Q C = Q A Q B .

Основная проблема: как гарантировать чтобы А не затронула слово b , а В - слово a . Для этого введем в алфавит D С символ ||. Добавим для всех состояний q i Î Q C таких, что q i Î Q A правила вида || q i ® || q i Л, т.е. каретка машины А будет, натыкаясь на символ ||, уходить влево. Соответственно для всех q j Î Q C таких, что q j Î Q B добавим правила вида || q j ® || q j П, т.е. каретка машины В будет уходить вправо. Тем самым мы как бы ограничиваем ленту для А справа, а для В слева.

Теорема 3.3. Для любых Машин Тьюринга А, В и Ф, имеющих один и тот же алфавит S , может быть эффективно построена машина С над тем же алфавитом S , такая что

Обозначим: E (Р) тождественную машину, т.е. Е(Р)=Р

С OPY (Р) копирующую машину, т.е. С OPY (Р)=Р||Р,

BRANCH ( P ) - эта машина переходит либо в состояние р 1 , либо в состоянии р о . Ее программа состоит из 4-х команд:

Эта машина строится по следующей формуле:

Согласно теоремам 3.1 и 3.2., мы можем построить машину , зная Е, Ф и COPY . Теперь, имея , BRNCH , A и В, можно построить машину С следующим образом:

Машина o BRANCH заканчивает свою работу либо в состоянии р 1 , если слово P обладает нужным свойством, либо в состоянии р о , находясь в начале слова P . Поэтому, если принять у машины А состояние р 1 , как начальное, а у машины В состояние р о , как начальное, то машина А будет включена при условии, что Ф(Р)=1, а машина В будет включена, если Ф(Р)=0.

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

Теорема 3.4. Для любых машин А и Ф можно эффективно построить машину L такую, что

Теорема 3.5. (Бомм, Джакопини, 1962)

Эту теорему мы даем здесь без доказательства.

Алгоритм - конструктивный объект;

Алгоритм можно строить из других алгоритмов;

o, ||, if_then_else, while_do - универсальный набор действий по управлению вычислительным процессом.

Читайте также: