Теория алгоритмов

[mihaild]

Mihaylo в сообщении #1446002 писал(а):

Существует ли универсальное доказательство, что первый алгоритм эффективнее?

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

[arseniiv]

Притом модель даже была предложена:

Xaositect в сообщении #1445388 писал(а):

Ну $\frac{a}{b}(b^2c)$ вполне вычисляет то, что надо.
Больше того, я могу придумать (нереалистичную) модель, когда этот алгоритм будет самым эффективным - если начиная с некоторого числа цифр в числе умножение внезапно становится очень медленным, а сложность деления такого скачка не имеет, и при этом таши типичные данные имеют $a$ чуть выше этого предела, а $b$ и $c$ значительно меньше.

[Xaositect]

Мое мнение - если были бы сколько-то общие соображения такого вида, то многие задачи теории сложности были бы проще. Вся суть P vs NP - необходимо доказательство того, что нет "хитрого" промежуточного вычисления, которое упростит задачу и позволит не делать перебор.

[Mihaylo]

Xaositect в сообщении #1446123 писал(а):

Мое мнение - если были бы сколько-то общие соображения такого вида, то многие задачи теории сложности были бы проще.

Я пытаюсь выискать соображения не обязательно сильные, но хотя бы слабые.

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

Нужно тогда рассматривать не множество начальных шагов, а множество алгоритмов (по сигнатуре задачи) - в этом множестве можно отметать алгоритмы с неэффективными шагами (такие алгоритмы неэффективны в целом). Но сам этот перебор выглядит как NP-полная задача. Хотя, кто сказал, что экспоненциальные алгоритмы невыполнимы?..

[mihaild]

Mihaylo в сообщении #1446176 писал(а):

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

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

[arseniiv]

Mihaylo
Вы вот говорите, что теория алгоритмов вам не нужна. Но если вы познакомитесь со штуками например пятью разных вычислительных формализмов, вы лучше увидите то, о чём говорят mihaild и Xaositect. Кстати некоторые из формализмов вообще плохо допускают какую-то декомпозицию в том смысле, что если мы хотим собрать из двух выраженных в них вычислений одно, которое проделывает сначала первое, а потом второе над его результатами, то такая сборка может быть очень хитрым процессом, а не просто как в каком-нибудь питоне *res = f(*g(*args)). Для алгорифмов Маркова это не очень тривиально например. И если например захотеть ограничиваться только «хорошими» в этом плане формализмами, надо будет сначала определить, какими такими именно хорошими. И после всего этого останется аргумент из предыдущего поста: даже человек может придумать алгоритм, который очень долго будет распутывать другой, а уж множество всех возможных решающих задачу алгоритмов будет содержать и вещи трудновообразимые. Даже если взять такую казалось бы натуральную для вычислений с натуральными числами вещь как машину Минского, и поинтересоваться алгоритмами сложения двух чисел, можно будет найти что-то не совсем уж тривиальное, если не ограничивать число промежуточных регистров.

[Mihaylo]

mihaild в сообщении #1446267 писал(а):

А еще если брать достаточно низкий уровень алгоритмов (МТ), то становится вообще непонятно, что такое "операция связана с чем-то дальше".

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

arseniiv в сообщении #1446305 писал(а):

Mihaylo
Вы вот говорите, что теория алгоритмов вам не нужна. Но если вы познакомитесь со штуками например пятью разных вычислительных формализмов

Нет, я не отвергаю теорию, наоборот! Просто пока не могу найти нужное мне. Наверное искомое слишком сложное и никому ненужное
Что за пять формализмов?

[arseniiv]

Mihaylo в сообщении #1446338 писал(а):

Что за пять формализмов?

Оценочное число достаточно отличающихся друг от друга моделей вычислений, которые полезно иметь в виду, чтобы представлять такие вещи в общем. Например:
• типа машины Тьюринга — конечный автомат, управляющий и управляемый лентой/лентами/подобной «пространственно связанной» памятью — включая машины со стеком/очередью;
• типа машины Минского или FRACTRAN — конечный автомат, управляющий памятью из конечного числа именованных регистров, которые могут хранить каждый неограниченное число значений, например натуральные числа;
• типа алгорифма Маркова или tag system — система переписывания подструктур в какой-то структуры, типа строк, но могут быть например графы;
• типа μ-рекурсивных функций — алгебра термов, которые можно собирать из более простых термов по определённым правилам, каждый представляющий алгоритм целиком;
• типа λ-исчисления (или любого из комбинаторных исчислений, типа KS или BCKW) или π-исчисления — близко к предыдущему, потому зачтём их вместе за полтора пункта; не каждый терм представляет алгоритм: некоторые термы представляют значения, а некоторые ничего, но зато правила составления термов проще;
• по-моему что-то ещё довольно отличающиеся от всего перечисленного есть.

[Sender]

(Оффтоп)

arseniiv в сообщении #1446378 писал(а):

любого из комбинаторных исчислений, типа KS или BCKW

Хотел было спросить, почему не IKS, а оказалось, что I выражается через K и S. Мило.

[Mihaylo]

Сейчас смотрю лекцию по лямбда-исчислению, и KS там было, но пока до практического применения не дошло. Пока лишь высокий уровень абстрагирования.

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

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

А я замахнулся на незавершенные (неполные) алгоритмы и их анализ. Это неопределенность структурная (в противопоставление параметрической неопределенности) - довольно сложная тема. И похоже нераскрытая.

Сейчас результат такой: проанализировал задачи и несколько готовых алгоритмов. Вычисляется изменение энтропии пошагово по мере выполнения программы, реализующей тот или иной алгоритм. В "классических" задачах энтропия уменьшается от H до 0. В каких-то алгоритмах график изменения не зависит от входных данных задачи и энтропия на каждом шаге вычисляется аналитически. Но в общем она зависит от входных данных и аналитически невычислима.
Также обнаруживаются задачи и алгоритмы, в которых энтропия явно не доходит до 0 при остановке программы. Это, в первую очередь, оптимизационные задачи, вероятностные алгоритмы.

Пока затрудняюсь обобщить алгоритм вычисления энтропии на i-ом шаге алгоритма, решающего конкретную задачу. И сейчас встали несколько основных вопросов:
1. Для любого ли алгоритма возможно вычисление энтропии на i-ом шаге выполнения?
2. Возможно ли вычисление энтропии для неполных алгоритмов?
3. Может в некоторых случаях энтропия как мера неопределенности иметь вероятностное распределение?

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

[Sender]

Mihaylo в сообщении #1449182 писал(а):

Вычисляется изменение энтропии пошагово по мере выполнения программы, реализующей тот или иной алгоритм.

Что вы понимаете под энтропией в данном случае?

[Mihaylo]

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

Хотя математически все довольно просто:
$I(S,R,T) = \log N(S,R,T)$, где $S$ и $R$ - состояние и результат работы алгоритма, $T$ - задача.
Совершенно бесполезное определение

[arseniiv]

Mihaylo в сообщении #1449430 писал(а):

Математическое определение пока не готов дать.

Как же вы считаете её тогда?

[Mihaylo]

Интуитивно можно сказать
Определяю количество возможных комбинаций конечного результата $N(S, R, T)$. На каждом шаге эта величина уменьшается вплоть до единицы в конце выполнения, когда программа выдает единственный правильный результат. Однако существуют алгоритмы, для которых эта величина трудновычислима или невычислима(?) на промежуточных шагах.

[mihaild]

Mihaylo в сообщении #1449513 писал(а):

количество возможных комбинаций конечного результата $N(S, R, T)$.

Оно же всегда равно $1$ - МТ детерменирована.