Программирование - это просто
Advertisement
Главная arrow Математика и информатика arrow Теория алгоритмов для чайников. arrow Теория алгоритмов для чайников. Урок 2. Математическое определение алгоритма.
29.05.2024 г.
Главное меню
Главная
Интернет магазин
Программные продукты
Биржевые роботы
Искусственный интеллект
Математика и информатика
1С:Предприятие
Уроки C#
Уроки Delphi
Уроки программирования
Web-программирование
Дизайн и графика
Компьютер для блондинок
Исходники
Статьи
Платный раздел
Рассказы про компьютеры
Хитрости и секреты
Системный подход
Размышления
Наука для чайников
Друзья сайта
Excel-это не сложно
Все о финансах
.
Теория алгоритмов для чайников. Урок 2. Математическое определение алгоритма. Печать E-mail
Автор megabax   
08.01.2020 г.
New Page 1

Теория алгоритмов для чайников. Урок 2. Математическое определение алгоритма.

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

Итак, с математической точки зрения алгоритм можно определить как четверку множеств (Q, I, Ω, f). Q - это множество, содержащее подмножества I и Ω, а f - это функция, переводящее множество Q само в себя. Функция f оставляет неподвижными все точки множества Ω, то есть f(q)=q для всех элементов q из множества Ω. Эти четыре элемента Q, I, Ω, f представляют стояния вычисления, ввод, вывод и правило вычислений. Каждое входное значение x из множества I определяет вычисляемую последовательность x0, x1, x2, ... следующим образом:

x=x0 и xk+1=f(xk) для k≥0.

Если k - это наименьшее целое число, для которого xk принадлежит Ω, значит вычисляемая последовательность заканчивается через k-шагов. Эта вычислительная последовательность дает xk для заданного x. Некоторые вычислительные последовательности никогда не заканчиваются, но алгоритм - это метод вычислений, который должен закончится за конечное число шагов для всех x из I.

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

Что значит "множество содержит подмножество"? Если представить, что множество I - это мешок с некими предметами, а Ω - мешок с другими предметами, то множество Q - это третий мешок, в который высыпали содержимое первых двух мешком и до этого там могло что-то быть. Если говорить более строго, то объект, принадлежащий какому то подмножеству, принадлежит также множеству, которое содержит это подмножество. Но это множество может содержать и другие объекты, а может и не содержать.

Идем дальше. Что значит "f - это функция, переводящее множество Q само в себя"? Это означает, что область определения функции (множество Q) содержит в себе область значений функции, т. е. f(q) для всех элементов q множества Q также является элементом множества Q. Иными словами, аргументами функции является тот же набор значений, что и результаты вычислений этой функции. То есть, мы берем любое значение аргумента функции из области допустимых значений (множество Q), в результате получаем что-то, что также мы можем подставить в аргумент функции.

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

Идем дальше.  Чтобы было более понятно, опишу пример прошлого урока (алгоритм Евклида) через данное определение. Пусть элементами множества Q будут является все величины (n), все упорядоченные пары (m, n) и все упорядоченные четверки (m, n, r, p), где p - целое положительное число, r - неотрицательное целое число. Пусть I - это множество всех пар (m, n), Ω - множество всех величин (n). Определим функцию f - следующим образом:

f((m,n))=(m,n,0,1);

f((n))=(n);

f((m,n,r,1))=(m,n, остаток от деления m на n,2);

f((m,n,r,2))=(n) если r=0, иначе (m,n,r,3);

f((m,n,p,3))=(n,p,p,1)

Теперь разберем эту запись более подробно. Итак, мы подставляем в функцию f пару (m,n) и получаем набор (m,n,0,1). Вы, наверное, догадались, что он соответствует первому шагу алгоритма.  Подставив в функцию первый шаг, мы получим данные для второго шага: f((m,n,r,1))=(m,n, остаток от деления m на n,2). А вот подставив в функцию второй шаг, мы получаем либо результат, либо данные для третьего шага: f((m,n,r,2))=(n) если r=0, иначе (m,n,r,3). На а третий шаг переводит множество Q в вид, необходимый для первого шага: f((m,n,p,3))=(n,p,p,1). Обратите внимание, что здесь на месте m стоит n, а на месте n - остаток от деления m на n.

Возникает еще вопрос: "в чем смысл записи f((n))=(n)?". По идее, она должна создать бесконечную рекурсию. Но, это кажется только на первый взгляд. Дело в том, что данная запись - это не алгоритм, а лишь набор формул. А выражение f((n))=(n) означает, что (n) необходимо интерпретировать как выходной параметр очередного, и, в данном случае, конечного шага алгоритма.

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

Итак, пусть A - это ограниченное множество букв, а A* - множество всех строк, определенных на множестве A, т. е . множество всех упорядоченных последовательностей x1x2 ... xn, где n≥0, и xiÎA для 1 ≤ i ≤ n. Идея заключается в том, чтобы закодировать состояния вычислений таким образом, чтобы они были представлены строками из множества A*. Тогда пусть N - целое неотрицательное число, а Q - множество всех пар (σ, i), σÎA*, а i целое число. 1 ≤ i ≤ N.
Пусть I - подмножество пар из Q, для которых i=0, а Ω - подмножество пар из Q, для которых i=N. Если θ и σ строки из A*, то мы будем говорить, что θ входит в σ, если σ имеет вид αθω, где  α и ω - некоторые строки.

Теперь построим функцию f при помощи строк  θi, φi и целых чисел ai, bi, 0 ≤ i < N:

f(σ, i) = (σ, ai), если θi не входит в σ.

f(σ, i) = (αφiω, bi), если α является самой короткой строкой, для которой σ=αθiω.

f(σ, N)=(σ, N).

Теперь объясняю, как эта функция будет работать. На входе у нас есть пары  (σ, i). Мы подставляем  их в функцию f. Если строка σ не содержит в себе  некоторую строку θi , то мы получаем (σ, ai) - то есть пару строка и некое число. Иными словами, номер превращается в число ai. Заметим, что строка при этом не меняется. Но у нас номер i может превращаться и в bi в том случае, когда σ уже  содержит в себе  некоторую строку θi.

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

 

Последнее обновление ( 08.01.2020 г. )
 
« След.   Пред. »
 
© 2024 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги