Предположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения. Необходимо программно проверить (написать алгоритм), верно ли предположение о сложности. Либо доказать, что такой проверяющий алгоритм не существует.

задан 17 Июн 16:46

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

Реально же надо сверить время работы алгоритма на разных входах с величиной f(n)=n log(n). Подать на вход числа типа n=10, 20, 50, 100, 200 или другие, и разделить на f(n). Должно быть близко к небольшой константе.

(17 Июн 17:01) falcao

@falcao: А если мы будем говорить не о проверке через эксперименты, а в принципе о проверке другим алгоритмом, который на вход принимает наш алгоритм и должен за конечное время определить, скажем, зависит ли время выполнения тестируемого алгоритма линейно от входных данных или нет, как строго доказать несуществование такого проверяющего алгоритма?

(17 Июн 17:12) DarkGenius

@DarkGenius: меня не покидает ощущение, что постановка вопроса здесь граничит с нелепостью. Есть теория сложности вычислений, и есть теория алгоритмов, в которой рассматриваются алгоритмически неразрешимые проблемы. Одно и другое вряд ли имеет смысл "смешивать". Понятно, что если машина Тьюринга останавливается, то она работает константное время, то есть укладывается в рамки O(n log n). А если не останавливается, то нет. При этом известно, что проблема остановки алгоритмически неразрешима. То есть на уровне теории алгоритмов, ничего такого быть не может. А на уровне практики -- вполне.

(17 Июн 17:37) falcao

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

(17 Июн 17:46) DarkGenius

@DarkGenius: допустим, у нас есть "волшебный" алгоритм, о котором идёт речь. С его помощью можно решить проблему остановки. Я беру машину Тьюринга, и запускаю её на n^2 шагов. Если она за это время остановилась, я выдаю число шагов её работы. Если нет, выдаю n^2. Если машина останавливается, то последовательность будет константной: O(1). Если нет, то получится n^2, что превышает O(n log n). Тем самым, становится ясно, что алгоритма тут нет.

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

(17 Июн 18:32) falcao

@falcao: неважно в контексте чего, важен вопрос. Вы пишите "Если машина останавливается, то последовательность будет константной: O(1)." С чего бы? Сложность алгоритма нельзя установить фактом, что однократный вызов алгоритма завершился за конечное время. И при чем тут проблема остановки? Искомый "волшебный" алгоритм должен возвращать 1, если проверяемый алгоритм имеет заданную сложность, либо 0, если не имеет.

(17 Июн 18:40) DarkGenius

@DarkGenius: если машина останавливается за c шагов, то по построению получится, что она для всех n, начиная с некоторого, будет выдавать число c. Если не останавливается, то она всегда выдаёт n^2. Таким образом, умея распознавать, имеет ли заданный алгоритм сложность O(n log n), я могу применить его к проблеме остановки. Это от противного доказывает, что алгоритма проверки программы на время работы O(n log n) не существует.

(17 Июн 19:40) falcao

@falcao: не понимаю. На машине запускается проверяемый или проверяющий алгоритм? Запускается один раз или сколько, для каких n? Как понимать "n^2 превышает O(n log n)"? Ведь оно будет превышать лишь начиная с некоторого N.

(17 Июн 20:05) DarkGenius

@DarkGenius: допустим, что у Вас есть проверяющий алгоритм. Я его использую как подпрограмму, при помощи которой хочу решить проблему остановки произвольной машины Тьюринга. По ней я пишу новую программу, которой на вход подаётся число n, и которая запускает машину на n^2 шагов (детали описаны выше). Эту программу я "скармливаю" подпрограмме. Та мне говорит, работает ли написанная мной программа O(n log n) шагов. Её саму я при этом не запускаю. Если анализируемая машина останавливается, то время работы равно O(1)=O(n log n), а если нет, то оно равно n^2, что не есть O(n log n).

(17 Июн 20:12) falcao

@falcao: запускать на n^2 шагов - это как? Чему равно n?

(17 Июн 22:45) DarkGenius

@DarkGenius: если у меня перед глазами есть программа, то я могу проследить, что она делает на 1-м, 2_м, ... , 100-м, ... шаге. Это делается алгоритмически. Заметьте, что в Вашей постановке задачи, программе (которую надо исследовать на предмет быстродействия), на вход подаётся число n. После чего прослеживается работа конкретной машины Тьюринга в пределах n^2 шагов. Вместо n^2 могла быть любая вычислимая функция.

Было бы желательно прояснить, в каком контексте появился Ваш вопрос. Это задача, которую Вам дали, или Вы сами поставили его как бы из любопытства?

(17 Июн 23:14) falcao

@falcao: задачу поставил сам из любопытства. В моей постановке на вход проверяемой программе подаются входные данные, ассоциированные с "объемом" данных, равным n, но это не суть, так как другая подпрограмма может генерировать нужные входные данные по числу n. И все же. Допустим, мы подаем на вход проверяющему алгоритму алгоритм, который не останавливается. Проверяющий алгоритм говорит, что проверяемый алгоритм не имеет сложность O(nlogn). Как это поможет решить проблему останова?

(17 Июн 23:29) DarkGenius

@DarkGenius: мои рассуждения достаточно стандартны для теории алгоритмов -- когда неразрешимость одной проблемы выводится из неразрешимости другой. Суть я подробно описал, и она в том, что проблема проверки программы P с входом n на предмет быстродействия слишком сложна. Если бы мы умели такое делать, то и проблема остановки бы заодно решалась. В случае, когда машина не останавливается, при каждом n будет выяснено, что программа P=P(n), построенная по заданной машине M, будет выдавать n^2 на любых данных. А если бы она останавливалась, то при n >> 1 программа P выдавала бы константу.

(17 Июн 23:42) falcao

@falcao: Как мы можем за конечное время проверить работу при каждом n? Проверка на конечном множестве n не позволяет сделать вывод о сложности.

(17 Июн 23:49) DarkGenius

@falcao: я понял ваши рассуждения, каким образом задача сводится к другой. Спасибо!

(17 Июн 23:52) DarkGenius
показано 5 из 15 показать еще 10
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×128
×55

задан
17 Июн 16:46

показан
84 раза

обновлен
17 Июн 23:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru