Форум движения за возрождение отечественной науки
21 Августа 2019, 02:46:49 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.

Войти
Новости: Форум движения за возрождение отечественной науки
 
   Начало   Помощь Поиск Войти Регистрация  
Страниц: [1]   Вниз
  Печать  
Автор Тема: Теория алгоритмов  (Прочитано 5970 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Андрей Александрович Козлов
Модераторы
Ветеран
*

Репутация: +33/-13
Offline Offline

Пол: Мужской
Сообщений: 769


« : 11 Ноября 2011, 15:40:50 »

Во всех книгах по теории алгоритмов алгоритм определяется по разному но всякий раз как  "... конечный набор правил."
Ключевым является слово "конечный".
С одной стороны - ну какая разница - просто математики не хотят иметь дело с бесконечными наборами правил, а с другой, это определение используется во множестве теорем, как некая аксиома.
Так, любая функция, реализующая какое-то действие, по умолчанию считается как имеющая алгоритм, записанный конечным набором символов и следовательно имеющая свой уникальный номер в каком ни будь списке всех конечных алгоритмов.
Однако, то что некая функция имеет простой и понятный смысл , еще не означает , что у неё должен быть конечный алгоритм (т.е. состоящий из конечного набора символов).

Рассмотрим пример.

Пусть у нас имеется следующий алгоритм:
Цитировать
вход: целое положительное N
i=5
while N<>0
  if i=0 return 0
  if N=0 return 1
  N=N-1
  i=i-1
loop
return 0
Алгоритм сравнивает N с числом 5 и возвращает 1 если оно меньше 5 и 0 в противном случае.
Немного странный и нерациональный, но тут надо сказать несколько слов:
В нашем языке (на котором реализован алгоритм) отсутствуют операции сложения и вычитания (кроме вычитания единицы) сравнения с числами (кроме сравнения с нулем) ну и прочие ,не участвующие здесь, операции.
Этот алгоритм ,очевидно, конечный.
Но давайте еще немного обедним наш язык и исключим из него операцию цикла (while ... loop).
Как измениться алгоритм, когда его придется переписать в соответствии с новыми правилами?
А вот как:
Цитировать
i=5
  if i=0 return 0
  if N=0 return 1
  N=N-1
  i=i-1
  if i=0 return 0
  if N=0 return 1
  N=N-1
  i=i-1
  if i=0 return 0
  if N=0 return 1
  N=N-1
  i=i-1
  ...
Из конечного алгоритма он вынужденно превратится в бесконечный.

Итак, данный пример показал, что понятие конечный/бесконечный алгоритм - это только вопрос реализации и возможностей языка.
В одной реализации этот алгоритм будет конечным, в другой - бесконечным.

Еще один пример:
Запись чисел в некоторой системе счисления можно назвать алгоритмом.
Алгоритмом по которому можно из набора цифр получить число.
Например из цифр в двоичной записи: '101' - следуя инструкции получаем число 5 .
Тогда, запись числа 1/3 в двоичной системе счисления будет бесконечным набором цифр: 0.1010101 ... (это если в нашем языке не участвуют круглые скобки, означающие период).
И в то же время то же число (тот же алгоритм) в троичной системе счисления будет записано конечным набором цифр.
Или в той же двоичной системе счисления, но с круглыми скобками: 0.(101) - уже конечный алгоритм (хотя подразумевающий бесконечное количество действий!).

Итак, добавлением или удалением из языка элементарных операций можно один и тот же алгоритм сделать как конечным, так и бесконечным.
« Последнее редактирование: 11 Ноября 2011, 15:44:31 от Андрей Александрович Козлов » Записан

Если вы все знаете и все понимаете - значит вам не все говорят.
Андрей Александрович Козлов
Модераторы
Ветеран
*

Репутация: +33/-13
Offline Offline

Пол: Мужской
Сообщений: 769


« Ответ #1 : 16 Декабря 2011, 01:17:30 »

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

Сходящиеся ряды обладают свойствами чисел, но ряды не числа.

Во первых, потому, что ряды - это алгоритмы, а алгоритмы нельзя упорядочить.

Их можно пересчитать (если их конечное число) но упорядочить нельзя, поскольку упорядочение подразумевает кольцо по сложению и умножению, а из алгоритмов такое кольцо составить нельзя.

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

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

Пример - знаменитая диагональ Кантора.

Цитировать
Чтоб показать, что "диагональ" не всегда дает результат, построю свою собственную диагональ на действительных числах, на отрезке от нуля до единицы [0,1) , но только предварительно упорядочу их по своему:

0 0 0 0 0 0 ...
1 0 0 0 0 0 ...
0 1 0 0 0 0 ...
1 1 0 0 0 0 ...
0 0 1 0 0 0 ...
...            ...

В лексикографическом порядке.

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

Применим алгоритм и получим ...

1 1 1 1 1 1 ...

Да, но ведь цепочка из одних единиц это 0.(1) = 1 - число не входящее в отрезок [0,1).
Диагональ Кантора дала сбой - не смогла выдать число, не входящее в упорядоченный список.
Получается все действительные числа (на отрезке от нуля до единицы) можно пересчитать?

Но ,на самом деле, некорректен сам метод.

Его некорректность сразу станет очевидна, если переиначить его в следующий:
Цитировать
Пусть у нас имеется алгоритм, пересчитывающий некое бесконечное множество объектов.
Тогда, я строю следующий "контр алгоритм": на каждом шаге работы пересчитывающего алгоритма, я выбираю такое число, которое пересчитывающий алгоритм еще не посчитал.
И объявляю это число - "не прошедшем пересчета".
Если, в какой-то момент времени это число все же будет посчитано, у меня наготове будет уже другое число "не прошедшее пересчета".
Таким образом, сколько бы ни работал ,какой угодно, пересчитывающий алгоритм - всегда можно будет предъявить число "не прошедшее пересчета".
И тогда я могу утверждать, что доказал, что данное множество - несчетно - поскольку не существует алгоритма, который бы пересчитал бы все члены этого множества.

Как видно - это была некоторая модификация парадокса Зенона про Ахила и Черепаху.
Или его другой ,более алгоритмический, вариант: "Парадокс Литвуда"
(Если в мешок класть шары со скоростью в 10 раз большей, чем вынимать, то сколько шаров в нем останется за бесконечное время?)

Вывод очевиден: нельзя отождествлять числа с алгоритмами и доказывать при этом "числовые теоремы".
У алгоритмов могут быть свои собственные свойства и особенности, не применимые к числам.
« Последнее редактирование: 16 Декабря 2011, 01:19:44 от Андрей Александрович Козлов » Записан

Если вы все знаете и все понимаете - значит вам не все говорят.
Андрей Александрович Козлов
Модераторы
Ветеран
*

Репутация: +33/-13
Offline Offline

Пол: Мужской
Сообщений: 769


« Ответ #2 : 19 Декабря 2011, 20:17:10 »

Итак, с чего надо начать, чтобы построить правильную теорию алгоритмов?

Конечно с классификации.

За элементарный алгоритм примем такой, где нет никаких циклов и развилок.

просто линейное следствие, типа:
Цитировать
x=5
или
Цитировать
y=f(x)
здесь есть входные параметры (x) и выходные параметры (y).

Сама функция f - может быть каким угодно сложным алгоритмом, но в нашем языке она участвует как элементарный символ.

Уже сейчас можно начать изучать некоторые свойства и доказывать теоремы.

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

Дальше, "правильные" алгоритмы должны подчиняться свойству подстановки (проектирования).

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

Например:
Цитировать
в алгоритм:
y=x+1
потставим вместо x - число 0
Получим:
y = 0+1 = 1
Алгоритм превратился в
y=1
Сформулируем следующее свойство "подстановки":
Цитировать
Обозначим
<a,x| F> - подстановка вместо входного параметра x числа (или элемента) a в алгоритм F.
Тогда, для любого алгоритма F должно выполняться:
<a,x|F(x)> = F(<a,x|x>)
Т.е. простыми словами про это свойство можно сказать так:
Не важно, на каком этапе производить подстановку - сначала вычислить алгоритм в общем виде (с абстрактной переменной x) и потом вместо переменной x подставить число или сначала подставить вместо переменной число и произвести с ним все те же действия, что указаны в алгоритме.
Результат не изменится.

Если это свойство выполняется для каждого элементарного символа языка, то оно будет выполняться и для любого алгоритма, составленного из символов этого языка.
Это просто доказывается, примерно так:
Цитировать
Пусть для F и G свойство подстановки выполняется, тогда оно выполняется и для их комбинации:
 <a,x|F(G(x))> = F(<a,x|G(x)>) = F(G(<a,x|(x)>)) =  F(G(a))

Ах, да...
Тут мне могут существенно возразить:
"А какой смысл в 'вычислении в общем виде' если мы пока не подставим в алгоритм число, не узнаем результата?
Т.е. y=x+1 - так и будет непонятным набором символов, пока мы туда не подставим число.
Т.е. подстановка числа - это и есть алгоритм!"

Нет, подстановка - это вовсе не алгоритм.

Ведь с алгоритмами мы можем производить всевозможные действия без подстановки.
Например, решать уравнения, оптимизировать и т.д.

Цитировать
Оптимизация, это ,например, когда мы алгоритм:
y=x+1
z=y+1
заменяем алгоритмом
z=x+2 (к стати пользуясь подстановкой - вместо y подставляем x+1 - подставлять можно не только числа, но и другие алгоритмы)

Цитировать
Решения уравнений, это когда мы для алгоритма:
y=x+1
производим подстановку не x , a y - выходного параметра:
<0,y| y=x+1 > = 0=x+1
После этого, нам надо обратить алгоритм и найти, чему равно x
(Это как раз сложная задача, которая пока не имеет решения в общем виде, кроме перебора)
« Последнее редактирование: 19 Декабря 2011, 20:20:23 от Андрей Александрович Козлов » Записан

Если вы все знаете и все понимаете - значит вам не все говорят.
Андрей Александрович Козлов
Модераторы
Ветеран
*

Репутация: +33/-13
Offline Offline

Пол: Мужской
Сообщений: 769


« Ответ #3 : 23 Декабря 2011, 15:06:57 »

Зачем нужно выполнения этого свойства - подстановки?
А вот практическое применение.
Только немного расширим это свойство - пусть у нас имеется алгоритм для чисел на множестве M (x,y принадлежат M) и пусть у нас есть расширение множества M до множества N.
Пусть <M,N,x| x > - это расширение чисел x на множество N  , а <N,M,x| x )> - это обратная проекция множества N на M.
Тогда, если результат не меняется при такой операции: <N,M,x| F(<M,N,x| x >) > = F(x) - то это может облегчить работу с алгоритмом.
Пример - комплексные числа.
В стандартном алгоритме F(x) - если в нем встречается функция извлечения корня и х - из множества действительных чисел, то в некоторых случаях наш алгоритм не сможет вычислить результат.
Но мы можем временно расширить множество х из R (действительные числа) до С (комплексные) - вычислить алгоритм на этом множестве, а затем снова спроектировать C на R:

F(x) = <C,R,x|F(<R,C,x|x>)>
(при обратной проекции может оказаться, что проекция невозможна - это будет означать что решения в действительных числах не существует)

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

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

Если вы все знаете и все понимаете - значит вам не все говорят.
Андрей Александрович Козлов
Модераторы
Ветеран
*

Репутация: +33/-13
Offline Offline

Пол: Мужской
Сообщений: 769


« Ответ #4 : 29 Декабря 2011, 00:57:10 »

Итак, современная математика чисел и функций - это самая простая разновидность алгоритмов.
Линейная.
Вычисления следуют одно за другим, результаты одного действия подставляются в следующее.
Схема таких алгоритмов выглядит как дерево (граф) с несколькими корнями и вершинами.
Все ли алгоритмы можно свести к линейной форме?

Например, оператор if - можно ли его привести к линейной форме?

Можно:
Цитировать
if a then
  y=F(x)
else
  y=G(x)
endif

можно заменить функцией:

y = a*F(x) + (1-a)*G(x)
(а принимает значение 0 и 1)
Это известный прием в математике, когда надо параметрически объединить две разные функции , оказывается это простой алгоритмический "IF".

При такой замене даже не увеличивается сложность алгоритма.
("Сложность" определим как количество символов в записи алгоритма)
И значит без IF можно вполне обойтись.

Дальше идут циклы.
Но циклы мы уже заменяли IF-ами.
А IF-ы можно заменить параметром.
Следовательно, цикл тоже можно заменить параметром, только параметр вместо двух выражений (0 и 1) будет принимать набор значений ,например, от 1 до N
И сам цикл заменится ,например, суммой по этому параметру.

Т.е. то, что у математиков выглядит как сумма чего-то там от 1 до N - это ,на самом деле, цикл.
Записан

Если вы все знаете и все понимаете - значит вам не все говорят.
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.11 | SMF © 2006-2009, Simple Machines LLC Valid XHTML 1.0! Valid CSS!