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

Нормальный Алгоритм Маркова Реферат.rar
Закачек 1786
Средняя скорость 6465 Kb/s

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В программе для А все правила ap®b!w, где a,bÎDA*, wÎ <Л,П, Н>заменим на ap®bqoBw, где qoBÎ QB — начальное состояние для В. Этообеспечит включение В в тот момент, когда А свою работу закончила и не раньше,т.к. QA/>QB=Æ.

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

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

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

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

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

Обоснование. Мы не будем давать здесьстрого доказательства в виду его технической сложности. Покажем лишьобоснование правильности утверждения теоремы. Обозначим DC=DA/>DB; QC=QA/>QB.

Основная проблема: какгарантировать чтобы А не затронула слово b, а В — слово a. Для этого введем в алфавит DС символ||. Добавим для всех состояний qiÎQC таких,что qiÎQA правила вида ||qi®||qiЛ, т.е. каретка машины Абудет, натыкаясь на символ ||, уходить влево.Соответственно для всех qjÎQC таких,что qjÎQB добавим правила вида ||qj®||qjП, т.е. каретка машины В будет уходитьвправо. Тем самым мы как бы ограничиваем ленту для Асправа, а для В слева.

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

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

Теорема 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.3. машину В машиной Е, а заключительное состояние в машине В заменимна начальное состояние в машине />. В итоге получим нужный результат.

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

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

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

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

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

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

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

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

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

Что такое правило подстановки?

Зависит ли результат от порядкаследования правил в НАМ?

Что происходит когда не применимо ни одно правило подстановки?

Норма́льный алгори́тм Ма́ркова (НАМ) — один из стандартных способов формального определения понятия алгоритма, так же как и машина Тьюринга. Понятие нормального алгоритма введено А.А. Марковым в конце 1940-х годов. Традиционно, когда говорят об алгоритмах Маркова, используют слово «алгорифм».

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

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам в котором алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Примером схемы нормального алгоритма в пятибуквенном алфавите | * abc может служить схема

Процесс применения нормального алгоритма к произвольному слову V в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V‘ — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V , если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V‘ , то работа алгоритма считается завершённой, и результатом этой работы считается слово V‘ . Иначе среди формул подстановки, левая часть которых входит в V‘ , выбирается самая верхняя. Если эта формула подстановки имеет вид , то из всех возможных представлений слова V‘ в виде RLS выбирается такое, при котором R — самое короткое, после чего работа алгоритма считается завершённой с результатом RDS . Если же эта формула подстановки имеет вид , то из всех возможных представлений слова V‘ в виде RLS выбирается такое, при котором R — самое короткое, после чего слово RDS считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

Например, в ходе процесса применения алгорифма с указанной выше схемой к слову | * | | последовательно возникают слова | b * | , ba | * | , a | * | , a | b * , aba | * , baa | * , aa | * , aa | c , aac , ac | и c | | , после чего алгорифм завершает работу с результатом | | . Другие примеры смотрите ниже.

Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».

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

Использование алгоритма Маркова для преобразований над строками:

  1. «А» → «апельсин»
  2. «кг» → «килограмм»
  3. «М» → «магазинчике»
  4. «Т» → «том»
  5. «магазинчике» →• «ларьке» (заключительная формула)
  6. «в том ларьке» → «на том рынке»

«Я купил кг Аов в Т М.»

При выполнении алгоритма строка претерпевает следующие изменения:

  1. «Я купил кг апельсинов в Т М.»
  2. «Я купил килограмм апельсинов в Т М.»
  3. «Я купил килограмм апельсинов в Т магазинчике.»
  4. «Я купил килограмм апельсинов в том магазинчике.»
  5. «Я купил килограмм апельсинов в том ларьке.»

На этом выполнение алгоритма завершится (так как будет достигнута формула № 5, которую мы сделали заключительной).

Данный алгоритм преобразует двоичные числа в «единичные», то есть на выходе получается строка из N единичек, если на входе у нас было N в двоичной системе. Например, 101 преобразуется в 5 единиц:

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

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

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

Нормамльный алгоримтм (алгоримфм) Мамркова (НАМ, также марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-хгодов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.

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

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

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

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

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

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

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

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

Например, в алфавите А = <а, b, с>имеются слова 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.

4. Игошин В.И. Математическая логика и теория алгоритмов: Учебное пособие для студентов учреждений высшего профессионального образования.- М.: Издательский центр «Академия», 2008.

5. Крупский В.Н., Плиско В.Е. Теория алгоритмов: Учебное пособие.- М.: Издательский центр «Академия», 2005.

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

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

Размещено на Allbest.ru

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

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

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

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

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

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

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

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

Потоки в сетях, структура и принципы формирования алгоритма Форда-Фалкерсона, особенности его реализации программным методом. Минимальные остовные деревья. Алгоритм Борувки: понятие и назначение, сферы и специфика практического использования, реализация.

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

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

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.


Статьи по теме