2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Сложность компьютерных алгоритмов
Сообщение29.05.2015, 19:24 
Как известно, любая компьютерная программа или остановится, или зациклится за время $T<2^N$, где $N$ - количество бит программы и использованной памяти. У меня вопрос - существуют ли задачи, алгоритмы которых не могут решить за время $T>N^2$, где $N$ - количество бит программы и использованной памяти? Хочу подчеркнуть, что речь идёт именно о наличии строгого математического доказательства для компьютерной программы, то есть числа имеют ограниченную длину, применяются операции компьютерного округления. Нигде на глаза не попадалось подобное доказательство, а вопрос интересный.
Заранее благодарю всех участников.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 20:51 
Возможно я не понял вопрос, он мне кажется каким-то тривиальным. Мне кажется, что Вы спрашиваете, существуют ли задачи, которые "не влазят" в конечный комп ($N^2$ тут даже не при чем). Так конечно существуют - любой достаточно длинный экземпляр любой массовой задачи. Например, вычислить $2^{N^2+1}+1$.

Я не угадал?

vlapay в сообщении #1021195 писал(а):
то есть числа имеют ограниченную длину
Это нечто непонятное совсем. Вот дана Вам строка. Как понять, "означает" ли она число или нет?

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 21:12 
Sonic86 в сообщении #1021233 писал(а):

Я не угадал?

Нет.

Цитата:
Вот дана Вам строка. Как понять, "означает" ли она число или нет?

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

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 21:18 
vlapay в сообщении #1021195 писал(а):
задачи, алгоритмы которых не могут решить
Не понял. Можно переформулировать?

vlapay в сообщении #1021195 писал(а):
Как известно, любая компьютерная программа или остановится, или зациклится за время $T<2^N$, где $N$ - количество бит программы и использованной памяти.
Что значит «зациклится за время»?

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 21:32 
arseniiv в сообщении #1021254 писал(а):
vlapay в сообщении #1021195 писал(а):
задачи, алгоритмы которых не могут решить
Не понял. Можно переформулировать?

Алгоритм, применяемый в программе (сама программа) не может найти решение задачи за время ...


Цитата:
Что значит «зациклится за время»?

Движение программы по замкнутому циклу, если такое случается, может произойти не сразу, а за определённое время.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 21:49 
arseniiv в сообщении #1021254 писал(а):
Что значит «зациклится за время»?
Он имеет ввиду ту тривиальную вещь, что комп зациклится максимум спустя $2^N$ тактов. Т.е. число состояний у компа конечно и переход из одного состояния в другое детерминирован. Значит, если прога детерминирована и при ее исполнении комп выполнил $2^N$ тактов, то он зациклился.

vlapay в сообщении #1021249 писал(а):
Вот у нас есть набор гирь с разными весами, натуральными числами. Как найти количество вариантов наборов гирь, дающих один и тот же вес? Существует ли строгое математическое доказательство, что не существует "быстрого алгоритма", могущего выдать число этих наборов гирь?
"быстрого алгоритма" - это алгоритма со скоростью работы $\Omega(f(n))$, т.е. не быстрее, чем $Cf(n)$?
Для каких-то задач есть такое доказательство (помнится, у Верещагина и Шеня написано, что нижние оценки алгоритмов - это трудно). Например, очевидно, что если скорость работы алгоритма не меньше функции длины входных данных. (сумма целых чисел с $n$ разрядами делается не быстрее, чем за $O(n)$, сложение матриц - не быстрее, чем за $O(n^2)$)
Но это все исключительно свойства массовых задач безотносительно к компу. При чем здесь комп?


В общем, Ваша проблема в формулировке. Выразитесь максимально точно.
vlapay в сообщении #1021249 писал(а):
Ну, или любая другая задача, которую можно сформулировать в виде программы с ограниченным количеством бит памяти, используемой в вычислениях.
Вот здесь нечто странное.
Что такое массовая задача? Массовая задача - это бесконечное семейство задач, параметризованное конечным множеством переменных. Поскольку массовая задача бесконечна, найдется конкретный экземпляр массовой задачи, длина которого не влезет в комп/программу с с ограниченным количеством бит памяти, используемой в вычислениях. И что делать будем?

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 21:51 
vlapay в сообщении #1021195 писал(а):
Как известно, любая компьютерная программа или остановится, или зациклится за время $T<2^N$, где $N$ - количество бит программы и использованной памяти. У меня вопрос - существуют ли задачи, алгоритмы которых не могут решить за время $T>N^2$, где $N$ - количество бит программы и использованной памяти?
Существуют. Для доказательства достаточно привести пример.
Вот он: поставим задачу нахождения периода последовательности чисел разрядности $N-C$ (C - длина программы), каждое следующее число формируется из предыдущего по заданному правилу (реализованному в программе). Программа выполняет $2^{N-C}+1$ шагов вычисления следующего числа, потом запоминает одно вычисленное число, потом снова выполняет шаги преобразования числа до получения равного запомненному. Количество шагов будет равно периоду. Для некоторых правил преобразования числа и некоторых начальных значений период будет не меньше $2^{N-C}-1$, что можно сделать много больше величины и $(N-C)^2$ и $N^2$ выбором достаточно большого $N$. Пример правила преобразования чисел - простой двоичный счётчик.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 21:54 

(Оффтоп)

Dmitriy40 в сообщении #1021276 писал(а):
Существуют. Для доказательства достаточно привести пример.
Угу, я ему тоже сначала так сказал.
Тут проблема в том, чтобы понять, что хочет клиент.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 21:56 
Добавление.
Если расширить задачу до поиска периода заранее неизвестной формулы преобразования числа, то не уверен что её можно решить за количество шагов менее $2^{N-C}$ - тот же самый простейший двоичный счётчик (а для особо наивных - в коде Грея с инвертированными отдельными разрядами - угадывайте! :-) ). Т.е. границу $(N-C)^2$ и $N^2$ превышаем с большим запасом (для достаточно больших N).

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 22:03 
Sonic86 в сообщении #1021272 писал(а):
Он имеет ввиду ту тривиальную вещь, что комп зациклится максимум спустя $2^N$ тактов. Т.е. число состояний у компа конечно и переход из одного состояния в другое детерминирован. Значит, если прога детерминирована и при ее исполнении комп выполнил $2^N$ тактов, то он зациклился.
А-а-а, т. е. тут прога — это КА, а не машина Тьюринга. Спасибо, да, действительно тривиально. :-)

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 22:26 
Dmitriy40 в сообщении #1021276 писал(а):
Существуют. Для доказательства достаточно привести пример.
Вот он: поставим задачу нахождения периода последовательности чисел разрядности $N-C$ (C - длина программы), каждое следующее число формируется из предыдущего по заданному правилу (реализованному в программе). Программа выполняет $2^{N-C}+1$ шагов вычисления следующего числа, потом запоминает одно вычисленное число, потом снова выполняет шаги преобразования числа до получения равного запомненному. Количество шагов будет равно периоду. Для некоторых правил преобразования числа и некоторых начальных значений период будет не меньше $2^{N-C}-1$, что можно сделать много больше величины и $(N-C)^2$ и $N^2$ выбором достаточно большого $N$. Пример правила преобразования чисел - простой двоичный счётчик.

По моему, этот пример не может считаться доказательством. Доказательство будет тогда, когда будет доказано, что нельзя упростить программу, то есть, что не существует какой-то другой программы, могущей получить тот же результат вычислений за гораздо более короткое время. В этом суть вопроса.
Sonic86 в сообщении #1021272 писал(а):
"быстрого алгоритма" - это алгоритма со скоростью работы $\Omega(f(n))$, т.е. не быстрее, чем $Cf(n)$?
Для каких-то задач есть такое доказательство (помнится, у Верещагина и Шеня написано, что нижние оценки алгоритмов - это трудно). Например, очевидно, что если скорость работы алгоритма не меньше функции длины входных данных. (сумма целых чисел с $n$ разрядами делается не быстрее, чем за $O(n)$, сложение матриц - не быстрее, чем за $O(n^2)$)
Но это все исключительно свойства массовых задач безотносительно к компу. При чем здесь комп?

Вот именно, это направление меня интересует. Может кто-то знает, существует ли хоть один алгоритм, для которого доказано, что "не быстрее, чем за $O(n^2)$"?
Комп универсален и ограничен в ресурсах, и в этом его сила, так как и наш мир ограничен в ресурсах. В его основе лежать минимально необходимые логические операции, а это фундаментальный уровень.
Цитата:
В общем, Ваша проблема в формулировке. Выразитесь максимально точно.

Пытаюсь.

Цитата:
Что такое массовая задача? Массовая задача - это бесконечное семейство задач, параметризованное конечным множеством переменных. Поскольку массовая задача бесконечна, найдется конкретный экземпляр массовой задачи, длина которого не влезет в комп/программу с с ограниченным количеством бит памяти, используемой в вычислениях. И что делать будем?

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

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 22:54 
vlapay в сообщении #1021291 писал(а):
а в идеале - существует ли универсальный алгоритм-ускоритель, который любые программы с вложенными циклами может "распрямить", получить тот же результат без циклов?
Этот вопрос тоже не очень-то поставлен, но если его как-то понимать, то, например, бывают циклы, тело которых при любом раскладе выполняется конечное число раз, а бывают остальные, но и первые «распрямлять» не обязательно выйдет — какой-нибудь for i in 1..n, если n — аргумент программы.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение29.05.2015, 23:37 
vlapay в сообщении #1021291 писал(а):
Dmitriy40 в сообщении #1021276 писал(а):
Существуют. Для доказательства достаточно привести пример.
По моему, этот пример не может считаться доказательством. Доказательство будет тогда, когда будет доказано, что нельзя упростить программу,
С моим уточнением ниже о произвольной заранее неизвестной функции преобразования мне думается достаточно легко доказать невозможность такого упрощения программы (не в размере самой программы C, а в количестве необходимых шагов вычислений). Правда сам я этого сделать не могу. :-(

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 08:44 
arseniiv в сообщении #1021307 писал(а):
vlapay в сообщении #1021291 писал(а):
а в идеале - существует ли универсальный алгоритм-ускоритель, который любые программы с вложенными циклами может "распрямить", получить тот же результат без циклов?
Этот вопрос тоже не очень-то поставлен, но если его как-то понимать, то, например, бывают циклы, тело которых при любом раскладе выполняется конечное число раз, а бывают остальные, но и первые «распрямлять» не обязательно выйдет — какой-нибудь for i in 1..n, если n — аргумент программы.

Уточню - можно ли получить ограниченный объём вычислений, не более $N^2$, с помощью универсального алгоритма-ускорителя?
Dmitriy40 в сообщении #1021327 писал(а):
С моим уточнением ниже о произвольной заранее неизвестной функции преобразования мне думается достаточно легко доказать невозможность такого упрощения программы (не в размере самой программы C, а в количестве необходимых шагов вычислений). Правда сам я этого сделать не могу. :-(

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

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 11:22 
vlapay в сообщении #1021291 писал(а):
Вот именно, это направление меня интересует. Может кто-то знает, существует ли хоть один алгоритм, для которого доказано, что "не быстрее, чем за $O(n^2)$"?
Так я же Вам объясняю: пусть есть задача, у которой длина входа $=d(n)$, тогда время работы алгоритма $=\Omega(d(n))$ (за исключением каких-нибудь дурацких задач типа "вернуть 1-й элемент из массива длины $n$").
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

vlapay в сообщении #1021291 писал(а):
а в идеале - существует ли универсальный алгоритм-ускоритель
Смотря, что под этим понимается. Для вычисления конечной функции есть единственный универсальный вариант - полное упорядочивание входных данных (лексикографическое )и табулирование функции, оно работает за $O(D\ln n)$, где $D$ - максимальная длина значения функции. (тоже, давно известно, что поиск в массиве с произвольным свойствами невозможно выполнить быстрее чем за $O(\ln n)$, где $n$ - длина массива, т.е. скорость поиска всегда $\Omega(\ln n)$).

vlapay в сообщении #1021291 писал(а):
который любые программы с вложенными циклами может "распрямить", получить тот же результат без циклов?
Очевидно, что цикл "распрямить" нельзя. Просто потому, что длина входной задачи не ограничена. Например, дано $n$ элементов, надо найти их сумму.

vlapay в сообщении #1021429 писал(а):
Уточню - можно ли получить ограниченный объём вычислений, не более $N^2$, с помощью универсального алгоритма-ускорителя?
Похоже, что уже бред пошел :-(
Еще раз говорю: Вы не сформулировали вопрос нормально. Что такое "универсальный алгоритм-ускоритель"? $N$ - это у Вас что? Откуда берется $N^2$?
Пока Вы будете изливать мутный поток сознания, ни разу не обработанный, помочь Вам никто не сможет.

vlapay в сообщении #1021429 писал(а):
Вопрос об универсальном алгоритме-ускорителе интересен и фундаментален.
Вопрос пока отсутствует.

vlapay в сообщении #1021429 писал(а):
Если есть универсальный алгоритм, то мы можем быстро получить доказательство любой теоремы (решение любой задачи), если такое вообще существует в природе.
Бред, доказательство теоремы - $NP$-полная задача.

 
 
 [ Сообщений: 26 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group