2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Теория алгоритмов
Сообщение21.03.2020, 11:43 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Mihaylo в сообщении #1446002 писал(а):
Существует ли универсальное доказательство, что первый алгоритм эффективнее?

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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение21.03.2020, 16:34 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение21.03.2020, 22:07 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение22.03.2020, 05:59 


12/07/15
2907
г. Чехов
Xaositect в сообщении #1446123 писал(а):
Мое мнение - если были бы сколько-то общие соображения такого вида, то многие задачи теории сложности были бы проще.

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

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

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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение22.03.2020, 13:25 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Mihaylo в сообщении #1446176 писал(а):
Но тем не менее грубый метод есть: если на шаге выполняются операции, явно не связанные с последующими результатами вычислений и конечным выводом, то такие шаги неэффективны
А еще если брать достаточно низкий уровень алгоритмов (МТ), то становится вообще непонятно, что такое "операция связана с чем-то дальше".
Проблема в том, что декомпозиция задачи на подзадачи, разбиение алгоритма на осмысленные блоки и т.д. - штуки существенно неформальные и не всегда возможные. Большая часть алгоритмов, решающих данную задачу, на взгляд человека делают что-то очень странное, и выделить в их работе какие-то осмысленные элементы без вспомогательных веществ нельзя.

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение22.03.2020, 16:10 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение22.03.2020, 17:45 


12/07/15
2907
г. Чехов
mihaild в сообщении #1446267 писал(а):
А еще если брать достаточно низкий уровень алгоритмов (МТ), то становится вообще непонятно, что такое "операция связана с чем-то дальше".

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

arseniiv в сообщении #1446305 писал(а):
Mihaylo
Вы вот говорите, что теория алгоритмов вам не нужна. Но если вы познакомитесь со штуками например пятью разных вычислительных формализмов

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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение22.03.2020, 20:46 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение23.03.2020, 08:36 


14/01/11
2916

(Оффтоп)

arseniiv в сообщении #1446378 писал(а):
любого из комбинаторных исчислений, типа KS или BCKW

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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение29.03.2020, 10:04 


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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение29.03.2020, 12:39 


14/01/11
2916
Mihaylo в сообщении #1449182 писал(а):
Вычисляется изменение энтропии пошагово по мере выполнения программы, реализующей тот или иной алгоритм.

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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение30.03.2020, 06:50 


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

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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение30.03.2020, 13:20 
Заслуженный участник


27/04/09
28128
Mihaylo в сообщении #1449430 писал(а):
Математическое определение пока не готов дать.
Как же вы считаете её тогда?

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение30.03.2020, 14:01 


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

 Профиль  
                  
 
 Re: Теория алгоритмов
Сообщение30.03.2020, 14:03 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Mihaylo в сообщении #1449513 писал(а):
количество возможных комбинаций конечного результата $N(S, R, T)$.
Оно же всегда равно $1$ - МТ детерменирована.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 56 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group