|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Предположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения. Как программно проверить, верно ли предположение о сложности? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 12:31 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
плавно увеличивать N и замерять время работы алгоритма в различных попугаях ? 100-120-144-172-207...-1000000000000 ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 12:40 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Aklinплавно увеличивать N и замерять время работы алгоритма в различных попугаях ? 100-120-144-172-207...-1000000000000 И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 13:36 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperИ как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?Постройте два графика: получившийся и предполагаемый. Сделайте сравнение в пределах погрешности. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 13:38 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
График, построенные по результатам эксперимента, должен совпасть с графиком, построенным на теоретических данных, с заданной точностью. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 13:38 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinInterloperИ как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?Постройте два графика: получившийся и предполагаемый. Сделайте сравнение в пределах погрешности. Насколько большое N нужно брать для графика? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 13:43 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperНасколько большое N нужно брать для графика?Зависит от того, под какие данные рассчитан алгоритм. Если речь идет про простую сферическую в вакууме сортировку уровня студенческих лабораторных, то я бы сказал, что достаточно взять до миллиона элементов. Просто бывают алгоритмы, к примеру тех же сортировок, рассчитанных на сортировку малых массивов, скажем, до 20 элементов. И гонять такой алгоритм даже на 100 элементах уже кощунство. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 13:50 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinInterloperНасколько большое N нужно брать для графика?Зависит от того, под какие данные рассчитан алгоритм. Если речь идет про простую сферическую в вакууме сортировку уровня студенческих лабораторных, то я бы сказал, что достаточно взять до миллиона элементов. Просто бывают алгоритмы, к примеру тех же сортировок, рассчитанных на сортировку малых массивов, скажем, до 20 элементов. И гонять такой алгоритм даже на 100 элементах уже кощунство. В том то и дело, что мы не знаем как устроен алгоритм внутри. Для N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный. Так что такой принцип решения не годится. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 13:54 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperИ как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности? Делить время на сложность - должно асимптотически приближать к некоторой константе, т.е. Время/(n*log(n)), для Вашего примера. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 13:57 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperВ том то и дело, что мы не знаем как устроен алгоритм внутри. Если у алгоритма нет генератора случайных чисел в виде одного из параметров "работы", то пройдитесь от 1 до 2^K, каждый раз увеличивая размер чисел вдвое. Делая несколько замеров на каждом N, с разными входными данными. Верхний предел - простое любопытство, время, при котором компьютер будет гонять алгоритм достаточно продолжительное для вашего ожидания время. В некоторых случаях это могут и быть и сутки, но для простых замеров достаточно, чтобы алгоритм работал одну-две минуты. Если есть генератор случайных чисел и он определяет сложность, и погрешность при этом велика, то никак вы не определите, что там внутри. Для одних и тех же данных время может различаться, либо различаться не на одних и тех же, а скажем на соседних данных (с точки зрения алгоритма). Например, 2+2 будет складываться одну минуту, а 2+3 уже пятнадцать минут. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 13:58 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Aklin, Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 14:20 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
x1ca4064InterloperИ как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности? Делить время на сложность - должно асимптотически приближать к некоторой константе, т.е. Время/(n*log(n)), для Вашего примера. Каков алгоритм проверки на асимптотическое приближение? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 14:20 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperAklin, Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 14:56 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Interloper Каков алгоритм проверки на асимптотическое приближение? Я бы попробовал метод наименьших квадратов для линейного приближения: если угол наклона стремится к 0, значит приближаемся к асимптоте. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 14:56 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
BarloneInterloperAklin, Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час. Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 14:58 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
x1ca4064InterloperКаков алгоритм проверки на асимптотическое приближение? Я бы попробовал метод наименьших квадратов для линейного приближения: если угол наклона стремится к 0, значит приближаемся к асимптоте. Наклона чего по отношению к чему? Как будем оценивать стремление к нулю? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:00 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Interloper Наклона чего по отношению к чему? Как будем оценивать стремление к нулю? У Вас есть набор точек Y=(Время)/(Сложность) от X=(Сложность), после МНК получим: Y=a*X+b, если a мало (внешний задаваемый параметр, означет точность нашего диагноза), значит (Время)=O(Сложность) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:06 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperBarloneпропущено... Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час. Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.А вам с какой целью? Успешная проверка на некотором наборе вариантов не будет являться доказательством вашего предположения. Если конечно это не полный перебор всех возможных вариантов входных данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:07 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
BarloneInterloperпропущено... Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.А вам с какой целью? Успешная проверка на некотором наборе вариантов не будет являться доказательством вашего предположения. Если конечно это не полный перебор всех возможных вариантов входных данных. Мне чисто из интереса. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:09 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
x1ca4064InterloperНаклона чего по отношению к чему? Как будем оценивать стремление к нулю? У Вас есть набор точек Y=(Время)/(Сложность) от X=(Сложность), после МНК получим: Y=a*X+b, если a мало (внешний задаваемый параметр, означет точность нашего диагноза), значит (Время)=O(Сложность) МНК даст нам оценку отклонения нашей функции от некоторой эталонной. Какую считать эталонной для O(N*N)? Нам то неизвестны коэффициенты, "спрятанные" внутри О большое. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:12 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Если чисто из интереса, то непонятна претензия: InterloperДля N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный. Так что такой принцип решения не годится. В любом случае, у программной реализации есть ограничения на входные данные: какое количество данных помещается в память, помещаются ли сами значения в используемый тип... ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:15 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Если алгоритм работает с каким-то массивом, то константа про О большом будет меняться в момент, когда массив перестанет помещаться в кеш. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:22 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
BarloneЕсли чисто из интереса, то непонятна претензия: InterloperДля N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный. Так что такой принцип решения не годится. В любом случае, у программной реализации есть ограничения на входные данные: какое количество данных помещается в память, помещаются ли сами значения в используемый тип... Чисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал. Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:24 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperЧисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал. Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:34 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
BarloneInterloperЧисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал. Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности. То есть такой проверяющий алгоритм не существует? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 15:47 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperBarloneпропущено... Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности. То есть такой проверяющий алгоритм не существует? Твои уточняющие вопросы напоминают легкий троллинг отвечающих. Тебе уже в первом ответе дали методику. Ты ее применил? Ты нарисовал график в Excel? Давай дружище сделай как советуют опытные. А потом подойдешь к теории снова. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 19:25 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
maytonInterloperпропущено... То есть такой проверяющий алгоритм не существует? Твои уточняющие вопросы напоминают легкий троллинг отвечающих. Тебе уже в первом ответе дали методику. Ты ее применил? Ты нарисовал график в Excel? Давай дружище сделай как советуют опытные. А потом подойдешь к теории снова. График меня не интересует. Я уже понял, что проблема алгоритмически неразрешима. Вопрос я задал фундаментальный, решение тупо взять нарисовать график, очевидно, не решает поставленную задачу. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 23:11 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
А чего ты ожидал? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.06.2019, 23:27 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
mayton, доказательство несуществования такого проверяющего алгоритма ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 08:12 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Действительно, пусть существует проверяющий алгоритм S, который может определить имеет ли произвольный алгоритм сложность O(nlogn). Покажем, как с его помощью можно решить проблему останова . Для этого создадим алгоритм P(n, A), который будет запускать на машине Тьюринга произвольный алгоритм A на n^2 шагов. При этом, если алгоритм A остановился менее, чем за n^2 шагов, алгоритм P возвращает число шагов, за которые он остановился; если же не остановился, возвращает n^2. Заметим, что если A останавливается за конечное число шагов m, то начиная с некоторого n=n0 алгоритм P(n, A) так же выполняется за конечное число шагов (ему не приходится проверять алгоритм A на n^2 шагов, достаточно проверить m шагов), таким образом его сложность будет O(1) <= O(nlogn). Если же алгоритм A не останавливается, алгоритм P(n, A) для каждого n будет проверять n^2 шагов алгоритма A, и его сложность будет O(n^2) > O(nlogn). Таким образом, умея с помощью алгоритма S распознавать сложность алгоритма P(n, A) мы можем решить алгоритмически неразрешимую проблему останова. Полученное противоречие доказывает невозможность существования проверяющего алгоритма S. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 11:33 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperAklin, Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует. Это несложно проверить, сделав, скажем, сто тестов на одной длине массива. Interloperили показать, что его не существует.Скорее нужно придумать наличие факторов, которые не дадут честно замерить время. Например тот же рандом при задержках. Если задержка будет каждый раз разная и на одном и том же массиве время будет различаться, скажем, в зависимости от предыдущих данных, тогда можно смело закрывать лавочку по данному алгоритму. Дерзайте, экспериментируйте. За вас писать весь процесс никто не станет здесь. InterloperКаков алгоритм проверки на асимптотическое приближение? Определение асимптоты можно в википедии прочитать, это несложно. InterloperВнесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.Ну так определяйте величину конечности этого времени при длине массива (или числе тестов) стремящихся к бесконечности. InterloperТо есть такой проверяющий алгоритм не существует?Существует. Называется программист. В зависимости от конкретного поведения конкретного алгоритма придумываются конкретные действия по его тестированию. Но, повторюсь, если в алгоритме рандом в качестве одного из ведущих факторов, то такой алгоритм вы за конечное время выявить не сможете, а его результаты будут битые (неверные). Поэтому встает вопрос о алгоритмической неразрешимости. А в этом случае нужно думать уже не методами программирования, а математическими теориями. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 11:59 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperДействительно, пусть существует проверяющий алгоритм S, который может определить имеет ли произвольный алгоритм сложность O(nlogn). Покажем, как с его помощью можно решить проблему останова .Не подходит. По условиям, алгоритм завершится за конечное время для любых входных данных. Поэтому по сути решение задачи следующее: определить насколько сильной является поведение рандомной части (включая часть про зависимость от предыдущих данных) (пусть будет в процентах от общего времени исполнения это будет P). Это несложно сделать. После этого сказать что для данного алгоритма определена следующая сложность (это тоже несложно сделать) с погрешностью 2*P. Задача решена. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 12:01 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperЗаметим, что если A останавливается за конечное число шагов m, то начиная с некоторого n=n0 алгоритм P(n, A) так же выполняется за конечное число шагов (ему не приходится проверять алгоритм A на n^2 шагов, достаточно проверить m шагов), таким образом его сложность будет O(1) <= O(nlogn).Неверно. Неверный вывод из несвязанных предпосылок. Если алгоритм имеет конечное время исполнения, это еще не значит, что у него сложность известная. И уж тем более не значит, что она <= O(n*log(n)) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 12:03 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinНе подходит. По условиям, алгоритм завершится за конечное время для любых входных данных. Это не мешает подать на вход любой алгоритм. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 12:32 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinНеверно. Неверный вывод из несвязанных предпосылок. Если алгоритм имеет конечное время исполнения, это еще не значит, что у него сложность известная. И уж тем более не значит, что она <= O(n*log(n)) Верно. Если алгоритм при увеличении n, начиная с определенного n выполняется за конечное константное время, то его сложность O(1) <= O(nlogn). ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 12:33 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinПоэтому по сути решение задачи следующее: определить насколько сильной является поведение рандомной части (включая часть про зависимость от предыдущих данных) (пусть будет в процентах от общего времени исполнения это будет P). Это несложно сделать. После этого сказать что для данного алгоритма определена следующая сложность (это тоже несложно сделать) с погрешностью 2*P. Задача решена. Алгоритмы детерминированы, в них нет "рандомной части". Рассматриваются алгоритмы, выполняемые на детерминированной машине Тьюринга. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 12:35 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperДействительно, пусть существует проверяющий алгоритм S, который может определить имеет ли произвольный алгоритм ...Дружище, вы безусловно в чём-то разбираетесь ... и немного путаетесь ... Если вы знаете, что ваша задача из разряда неразрешимой массовой проблемы , то это не значит, что частный вариант проблемы обязательно неразрешим. Выше уже ответили для случаев конкретных задач. Теоретизировать ступайте в теорию алгоритмов . Более того, если ваш сферический алгоритм похож на алгоритм с оракулом , то возможны всякие чудеса. Например он может в случайное время (закладка такая была) нажимать на тормоз/акселератор ... Или вообще, по команде извне ... Кроме тестов, для чёрных ящиков не придумали лучшего. Выбираете гипотезу, набираете статистику, проверяете гипотезу и т.д... Повезло - вы в коричневом в шоколаде ... ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 12:44 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
exp98, В чем путаюсь? Я знаю, что есть решение для частных случаев. Но меня интересует общий случай. И для общего случая проблема неразрешима. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 12:47 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperВерно. Если алгоритм при увеличении n, начиная с определенного n выполняется за конечное константное время, то его сложность O(1) <= O(nlogn). ММм... может и так, но к нашей задачи это отношения все равно не имеет. InterloperНе подходит. По условиям, алгоритм завершится за конечное время для любых входных данных. Это не мешает подать на вход любой алгоритм.Достаточно ввести правило отлаженности (работоспособности) алгоритма и сделать вид, что любое время, выбивающееся из "разумных пределов" есть неработоспособность этого алгоритма. Найти среднее время в пределах погрешности несложно. Если какие-то многочисленные запуски будут выбиваться из пределов погрешности, то следует говорить, что алгоритм неработоспособен (ошибочен). В общем виде, когда нет гарантий работоспособности алгоритма искать его сложность неперспективно и бесполезно. В таким виде, как выше вы сказали, это проблема конечности (нерешаемая). Поэтому убираем проблему конечности и идем дальше (в пределах лабораторной работы или реферата так очень даже можно). InterloperАлгоритмы детерминированы, в них нет "рандомной части". Рассматриваются алгоритмы, выполняемые на детерминированной машине Тьюринга.Нет гарантий конечности времени исполнения на машине Тьюринга (см. выше). InterloperНо меня интересует общий случай. И для общего случая проблема неразрешима.Общий случай на практике не встречается, только частные и конечные. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:01 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Алгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма: 1) требуем конечность алгоритма на всех допустимых входных данных. если в требовании отказано, объявляем задачу о конечности алгоритмически неразрешимой 2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность. 3) задача решена. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:03 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinАлгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма: 1) требуем конечность алгоритма на всех допустимых входных данных. если в требовании отказано, объявляем задачу об определении сложности алгоритмически неразрешимой 2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность. 3) задача решена. поправка* ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:03 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinАлгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма: 1) требуем конечность алгоритма на всех допустимых входных данных. если в требовании отказано, объявляем задачу об определении сложности алгоритмически неразрешимой 2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность. 2.1) Если итоговая погрешность соизмерима с величиной асимптоты, то считаем алгоритм неконечным. 3) задача решена. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:05 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
В реальности имплементация алгоритма - будет наполнена побочными эффектами. Такими как например - попадание в кеши L2/L3 - наличие побочных эффектов многозадачности (Амдал и когеррентность) - страничный кеш оперативной памяти - резкое изменение отклика жёсткого диска в зависимости от нагрузки (близко к когеррентности) - побочные эффекты рантайма (warmup) и управления памятью (фаза уборки мусора). Они имеют более сложную (гистерезисную) природу и асимтотическая формула сложности алгоритма как такового будет иметь бОльшую поправку. Грубо говоря вы просто увеличиваете количество (n) и ожидаете к примеру логариму. Но на графике будет логарифма а потом - внезапный скачок вверх (безо всякой видимой причины). И сколько ни смотрите на вашу формулу и алгоритм - там НИГДЕ не будет видимого пояснения такого поведения. Классическая машинка тьюринга не имела кешей L2/L3. Как вы будете их эффект учитывать - ума не приложу. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:22 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinАлгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма: 1) требуем конечность алгоритма на всех допустимых входных данных. если в требовании отказано, объявляем задачу о конечности алгоритмически неразрешимой 2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность. 3) задача решена. Я могу придумать алгоритм, на котором ваши тесты покажут неверный результат, о том и речь. Так как тесты проверят только конечное число входных данных. А сложность алгоритма связана с его поведением на бесконечности. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:22 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
mayton, Все же, для больших входных данных, эффектом кэшей можно пренебречь. Возьмите имплементацию любого алгоритма сортировки, нарисуйте график зависимости времени от размера массива - начиная с некоторого n он будет соответствовать установленной теоретической сложности алгоритма. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:25 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
maytonКак вы будете их эффект учитывать - ума не приложу.Практика показывает, что кэш ограничен, причем жутко ограничен и его легко перегрузить, тем самым нивелировать его эффект. Но даже если речь пойдет про объемы входных данных соизмеримых с кэш, все равно погрешность не может превышать какие-то разумные пределы. Если оценка по времени будет в T, а погрешность даже в T/3, это перебор. Поэтому с моей колокольни вопрос об оценке сложности стоит только в разделении алгоритма на конечный (=предсказуемый) и бесконечный (=непредсказуемый). Вторые рассматривать не следует хотя бы из невозможности их оценки. InterloperТак как тесты проверят только конечное число входных данных. А сложность алгоритма связана с его поведением на бесконечности. Не стоит рассматривать недопустимые входные данные. Если написано, что алгоритм принимает только конечные входные данные то смотрите сложность только в пределах допустимых входных данных. За пределами допустимых входных данных алгоритм следует считать неработающим (что есть равенство неконечности, а определение его сложности алгоритмически неразрешаемым). Тогда встает вопрос, зачем вообще оценивать алгоритм там, где он не работает? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:29 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Aklin, Можно написать алгоритм сортировки, который будет сортировать массив любого объема, помещающийся в памяти. Вы будете запускать тесты на всех возможных длинах массива? В таком случае, пока тесты завершатся, анализ будет уже никому не нужен. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:32 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Interlopermayton, Все же, для больших входных данных, эффектом кэшей можно пренебречь. Возьмите имплементацию любого алгоритма сортировки, нарисуйте график зависимости времени от размера массива - начиная с некоторого n он будет соответствовать установленной теоретической сложности алгоритма.Я уже вроде приводил пример специальных алгоритмов сортировки на малых числах. Например, нужно отсортировать пять чисел. В этом случае сложность понятна, но время исполнения будет зависеть исключительно от входных данных. Для нашей задачи время для конкретного N нужно определять для разных входных данных (включая многочисленные повторы одинаковых входных цепочек), тем самым уйдя от удачных входных данных и от зависимости от предыдущих данных. В конце концов речь будет идти только о вероятностном поведении. А значит нужно найти такой алгоритм оценки, который бы оценивал лучше, чем погрешность оценки, этого будет достаточно с математической точки зрения. Если речь идет про неконечные (=непредсказуемые) алгоритмы, то достаточно будет доказать, что погрешность оценки соизмерима (или выше), чем время работы алгоритма, а значит с вероятностной точки зрения оценивать алгоритм будет нельзя (=невозможно). Опять же, это тоже результат. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:33 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperAklin, Можно написать алгоритм сортировки, который будет сортировать массив любого объема, помещающийся в памяти. Вы будете запускать тесты на всех возможных длинах массива? В таком случае, пока тесты завершатся, анализ будет уже никому не нужен. Мы говорим про оценку конечного алгоритма. Оценка конечная. Время на оценку конечное. Время оценки у нас на одном конце линейки, а точность оценки (=погрешность) на другом. Уменьшая время на оценку увеличиваем погрешность. Другими словами, нельзя сделать и быстро и дешево и качественно и одновременно. А значит выбираем наиболее значимый параметр, и идем в его направлении. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:36 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Aklin Если речь идет про неконечные (=непредсказуемые) алгоритмы, то достаточно будет доказать, что погрешность оценки соизмерима (или выше), чем время работы алгоритма, а значит с вероятностной точки зрения оценивать алгоритм будет нельзя (=невозможно). Мы не можем вычислить заранее, что алгоритм неконечный. Это фундаментальное ограничение. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:40 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinInterloperAklin, Можно написать алгоритм сортировки, который будет сортировать массив любого объема, помещающийся в памяти. Вы будете запускать тесты на всех возможных длинах массива? В таком случае, пока тесты завершатся, анализ будет уже никому не нужен. Мы говорим про оценку конечного алгоритма. Оценка конечная. Время на оценку конечное. Время оценки у нас на одном конце линейки, а точность оценки (=погрешность) на другом. Уменьшая время на оценку увеличиваем погрешность. Другими словами, нельзя сделать и быстро и дешево и качественно и одновременно. А значит выбираем наиболее значимый параметр, и идем в его направлении. На скольких наборах входных данных вы будете тестировать алгоритм? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:41 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperВ чем путаюсь? В постановке задачи. В первом посте вы написали про алгоритм, имеющий фиксированную сложность. А потом внезапно перешли к чёрному ящику, внутри которого Х алгоритмов, причём каждый со своей сложностью. Interloperменя интересует общий случай. Общий случай работает точно так же, только для каждого из Х вышеназванных алгоритмов выделяется диапазон и совпадение графиков проверяется отдельно на каждом из диапазонов. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:42 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Interlopermayton, Все же, для больших входных данных, эффектом кэшей можно пренебречь. Возьмите имплементацию любого алгоритма сортировки, нарисуйте график зависимости времени от размера массива - начиная с некоторого n он будет соответствовать установленной теоретической сложности алгоритма. Вы только что похоронили любую оптимизацию имплементации. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:44 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperМы не можем вычислить заранее, что алгоритм неконечный. Это фундаментальное ограничение.Но можем вычислить погрешность времени исполнения. Если, как я выше писал, погрешность измерения выше соизмерима с временем исполнения, тогда алгоритм следует перевести в разряд неконечных. InterloperНа скольких наборах входных данных вы будете тестировать алгоритм?А сколько у меня попыток для запуска? Если у меня десять попыток, а входных данных может быть до миллиона, то сделаю по две попытки на 10, 100, 1000, 10000, 100000 и 1000000 элементов. А потом посчитаю дельту между двумя запусками, о объявлю ее погрешностью Если миллион попыток, а входных данных не больше 100, то можно по много раз перебрать все входные данные. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 13:47 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Dimitry SibiryakovInterloperВ чем путаюсь? В постановке задачи. В первом посте вы написали про алгоритм, имеющий фиксированную сложность. А потом внезапно перешли к чёрному ящику, внутри которого Х алгоритмов, причём каждый со своей сложностью. Interloperменя интересует общий случай. Общий случай работает точно так же, только для каждого из Х вышеназванных алгоритмов выделяется диапазон и совпадение графиков проверяется отдельно на каждом из диапазонов. Возможно, действительно изложил сумбурно. Задача: анализировать алгоритмы, имеющие фиксированную сложность, но неизвестную нам, о которой мы можем лишь формулировать гипотезу. В первом посте я писал, что мы можем просто замерять время выполнения на каждом тесте. Но пусть даже мы можем намного больше - анализировать исходный код алгоритма или его определение на машине Тьюринга. Оказывается, даже с таким расширенным инструментарием, точно проверить гипотезу о сложности невозможно. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 14:13 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Dimitry SibiryakovОбщий случай работает точно так же, только для каждого из Х вышеназванных алгоритмов выделяется диапазон и совпадение графиков проверяется отдельно на каждом из диапазонов. В том-то и дело, что нет способа выбрать диапазон, достаточный для проверки. А проверять на всем диапазоне тупо перебором нецелесообразно - это займет намного больше времени, чем практическая эксплуатация алгоритма. Более того, даже если вы проверите алгоритм на всех возможных вариантах для конкретного объема памяти на вашей машине, алгоритм на машине с большим объемом памяти может вести себя по иному. Вот прямо специально его возьмут и запрограммируют так, что для входных данных объемом меньше N (причем N не влезет в вашу доступную память) сложность алгоритма будет такой, а для входных данных больше N - сложность будет другой, и далее меняться не будет. То есть как бы вы не замеряли алгоритм на своей машине, вы не получите правильный результат. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 14:17 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinInterloperНа скольких наборах входных данных вы будете тестировать алгоритм?А сколько у меня попыток для запуска? Если у меня десять попыток, а входных данных может быть до миллиона, то сделаю по две попытки на 10, 100, 1000, 10000, 100000 и 1000000 элементов. А потом посчитаю дельту между двумя запусками, о объявлю ее погрешностью Если миллион попыток, а входных данных не больше 100, то можно по много раз перебрать все входные данные. Ни на каком конечном наборе данных нельзя сделать вывод о сложности алгоритма. Что именно вам непонятно в этом утверждении? Смотрите объяснение выше, в котором я объясняю что даже полным перебором вариантов на конкретном компьютере нельзя оценить сложность алгоритма. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 14:20 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperВот прямо специально его возьмут и запрограммируют так, что для входных данных объемом меньше N (причем N не влезет в вашу доступную память) сложность алгоритма будет такой, а для входных данных больше N - сложность будет другойВообще никак не бьётся с (выделено мною):InterloperЗадача: анализировать алгоритмы, имеющие фиксированную сложность , но неизвестную нам, о которой мы можем лишь формулировать гипотезу. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 14:34 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Interloperточно проверить гипотезу о сложности невозможноЕсли есть алгоритм, исходник, в котором нет рандома, то возможно. Для начала ищем места, которые могут зависнуть алгоритм. Если такие есть, то задача решена (ибо доказательство неконечности тоже результат). Если алгоритм не зависает, то делаем простое аппроксимирование, ну или ассиптоту ищем в заданной погрешности. InterloperНи на каком конечном наборе данных нельзя сделать вывод о сложности алгоритма. Что именно вам непонятно в этом утверждении?Алгоритм, тем более конкретная программа не может быть определена на бесконечном объеме данных. А раз она определена только на конечном объеме данных, то достаточно искать примеры в этом объеме. Их может быть немало, но этот список все равно конечен. Вопрос тот же: если алгоритм работает на N элементах T времени, то нужно будет не менее чем T*log(N)*log(N) запусков для грубой оценки, это в сферических условиях в вакууме. Наличие любого стремного фактора можно сразу умножать на десять. T можно определить, как можно и определить конечность алгоритма, имея его исходник на понятном языке (в данном случае математически идеальная машина Тьюринга является малопонятной). Еще встает вопрос о конечности самого исходника. Время, требуемое для анализа алгоритма будет также зависеть от размера исходника. В общем, если все размеры определены, то потребуется что-то вроде A*B*C*D*E... = X времени для оценки. InterloperСмотрите объяснение выше, в котором я объясняю что даже полным перебором вариантов на конкретном компьютере нельзя оценить сложность алгоритма. Там идет жонглирование понятиями. Сначала утверждается что алгоритм конечен, а потом идет попытка выдать конечный алгоритм за бесконечно долгий. Не стоит этого делать. Нужно делить мух и котлет. Найдите условия конечности, а неконечные алгоритмы сразу в мусорку с пометкой "нерешаемо". ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 18:44 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Basil A. SidorovInterloperВот прямо специально его возьмут и запрограммируют так, что для входных данных объемом меньше N (причем N не влезет в вашу доступную память) сложность алгоритма будет такой, а для входных данных больше N - сложность будет другойВообще никак не бьётся с (выделено мною):InterloperЗадача: анализировать алгоритмы, имеющие фиксированную сложность , но неизвестную нам, о которой мы можем лишь формулировать гипотезу. Вообще нет противоречия. Сложность не может быть фиксированной или нефиксированной, она одна. Это теоретический концепт, говорить о котором можно только с точки зрения асимптотики. Еще раз: сложность нельзя проверить на конечном числе входных данных, сколько бы данных вы не взяли. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 19:07 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinInterloperточно проверить гипотезу о сложности невозможноЕсли есть алгоритм, исходник, в котором нет рандома, то возможно. Для начала ищем места, которые могут зависнуть алгоритм. Если такие есть, то задача решена (ибо доказательство неконечности тоже результат). Невозможно даже для агоритмов без рандома. Места, в которых может зависнуть алгоритм, нельзя найти программно. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 19:09 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinАлгоритм, тем более конкретная программа не может быть определена на бесконечном объеме данных. А раз она определена только на конечном объеме данных, то достаточно искать примеры в этом объеме. Их может быть немало, но этот список все равно конечен. И сразу ошибка. Алгоритм может быть определен на неограниченном объеме данных. Алгоритм сортировки может сортировать массивы любой размерности, лишь бы они умещались в памяти. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 19:11 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinТам идет жонглирование понятиями. Сначала утверждается что алгоритм конечен, а потом идет попытка выдать конечный алгоритм за бесконечно долгий. Не стоит этого делать. Если вы что-то не поняли, не стоит сразу называть это жонглированием. Там не было речи о бесконечно долгом алгоритме. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 19:12 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinВопрос тот же: если алгоритм работает на N элементах T времени, то нужно будет не менее чем T*log(N)*log(N) запусков для грубой оценки, это в сферических условиях в вакууме. Наличие любого стремного фактора можно сразу умножать на десять. T можно определить, как можно и определить конечность алгоритма, имея его исходник на понятном языке (в данном случае математически идеальная машина Тьюринга является малопонятной). Еще встает вопрос о конечности самого исходника. Время, требуемое для анализа алгоритма будет также зависеть от размера исходника. В общем, если все размеры определены, то потребуется что-то вроде A*B*C*D*E... = X времени для оценки. 1. Конечность алгоритма определить невозможно (см. неразрешимость проблемы останова) 2. Какое бы N не взять, можно проанализировать только сложность алгоритма на промежутке от 1 до N, но не сложность всего алгоритма, который определен для любого N. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 19:15 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperМеста, в которых может зависнуть алгоритм, нельзя найти программно.Вы явно не знакомы с методиками тестирования и верификации =) InterloperИ сразу ошибка. Алгоритм может быть определен на неограниченном объеме данных. Алгоритм сортировки может сортировать массивы любой размерности, лишь бы они умещались в памяти.Объем памяти на реальном компьютере ограничен. Interloper1. Конечность алгоритма определить невозможно (см. неразрешимость проблемы останова)С определенной вероятностью возможно. Вопрос лишь в объеме ресурсов. Нельзя определить конечность алгоритма если объем ресурсов на определение меньше. чем объем ресурсов на использование этого алгоритма. В некоторых других случаях можно (особенно имея исходник). Interloper2. Какое бы N не взять, можно проанализировать только сложность алгоритма на промежутке от 1 до N, но не сложность всего алгоритма, который определен для любого N.Я правильно понимаю, что вы говорите, например при N=3 мы можем определить конечность алгоритма при N=1, N=2 и N=3, а для других целых 0 < N <= 3 определить не можете ? Начните с утверждения, что алгоритм протестирован. и дальше либо подтвердите его, определив конечную сложность, либо опровергните. Если же речь про сферические в вакууме алгоритмы, не используемые на практике, то задача должна звучать иначе. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 19:37 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Топик закончится только после того, как мы все дружно восхитимся ТээСовым "открытием". ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 20:01 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
зачем вообще это все. есть алгоритм, есть его оценка. что тут происходит? алгоритм раскраски? коммивояжера? нет? ну тогда зачем? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 21:11 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperПредположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения. Как программно проверить , верно ли предположение о сложности? фигня какая. это в самом алгоритме. чо там проверять ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 21:14 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinОбъем памяти на реальном компьютере ограничен. На конкретном - да. Но можно найти компьютер с большим объемом памяти, чем на том, на котором запускаем тесты. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 21:18 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinВопрос лишь в объеме ресурсов. Нельзя определить конечность алгоритма если объем ресурсов на определение меньше. чем объем ресурсов на использование этого алгоритма. В некоторых других случаях можно (особенно имея исходник). Если найдете способ как, сразу получите Нобелевку, не меньше. В каких некоторых случаях? Для алгоритма суммы чисел? Тогда да. Может имеет смысл сначала разобраться в вопросе вместо того, чтобы упрямо гнуть свою линию, ничем не подкрепляя? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 21:21 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinЯ правильно понимаю, что вы говорите, например при N=3 мы можем определить конечность алгоритма при N=1, N=2 и N=3, а для других целых 0 < N <= 3 определить не можете ? Неправильно. Вы можете протестировать алгоритм для N от 1 до 3. Допустим, он выполнился за 1, 2, 3 мс. Вы сделали вывод, что алгоритм работает за линейное время. Но если запустить алгоритм на следующих N, то можно увидеть, что алгоритм выполняется за квадратичное время, и дальше это не меняется, следовательно, сложность алгоритма - O(n^2). Пример такого алгоритма: int TestAlg(int n) { int s = 0; for (int i = 0; i < 3; ++i) s += 1; for (int i = 3; i < n; ++i) for (int j = 0; j < n; ++j) s += 1; return s; } Только пусть вместо 3 в качестве граничной точки будет какое-то очень большое число, которое вы не превысите своими тестами. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 21:30 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
love_bachInterloperПредположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения. Как программно проверить , верно ли предположение о сложности? фигня какая. это в самом алгоритме. чо там проверять Если в алгоритме тысячи строк, "глазами" оценить сложность не получится. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.06.2019, 21:32 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperПредположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения. Как программно проверить, верно ли предположение о сложности?зачем это проверять? особенно с учётом возможной переменной асимптотики. Обычная практическая задача в CS: проверяют\доказывают конечность реализации алгоритма, т.е. лимит времени на конкретном железе на крайних условиях. А задача по доказательству асимптотики алгоритма лежит обычно на алгоритмистах\математиках. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 00:14 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperНа конкретном - да. Но можно найти компьютер с большим объемом памяти, чем на том, на котором запускаем тесты.Любое конечное большое число памяти всегда много меньше, чем бесконечное. "много меньше" это значит, что даже если ты помножишь этот объем памяти сам на себя хоть тысячу раз подряд, все равно будет меньше. Это школьный уровень алгебры и начал анализа. InterloperМожет имеет смысл сначала разобраться в вопросе вместо того, чтобы упрямо гнуть свою линию, ничем не подкрепляя?Вам тот же совет =) InterloperНо если запустить алгоритм на следующих NВ рамках задачи, где алгоритм определен для любого целого N <= 3 нельзя запускать этот алгоритм для любого N > 3. Это другая задача, которую на практике не решают (точнее решают программисты-теоретики или программисты-верификаторы, а не то, чем мы здесь занимаемся). Опять вернулись к тому, что вы ставите в условие конечность алгоритма, а потом требуете определить его работоспособность за пределами условий. А когда вам отвечают, что это не удолевтворяет условиям задачи, либо же говорят, что это невозможно - вы сразу со своей несвязанной и неверной теорией лезите про "общий случай при заранее известных конечных условиях". Нет никаких общих случаев, если есть заданные условия. InterloperЕсли в алгоритме тысячи строк, "глазами" оценить сложность не получится.Это значит алгоритм нечитаемый, а значит он неконечный может быть. Исходим из условий читаемости алгоритма, его исходника. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 00:43 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperМы можем вызывать алгоритм на разных входных данных и замерять время его выполнения. Как программно проверить, верно ли предположение о сложности?Это взаимоисключающие вещи: сделать много замеров и формально доказать. Для формального доказательства есть специальные инструменты, например, Isabelle HOL . Вот, статьи: https://arxiv.org/pdf/1802.01336.pdf https://github.com/bzhan/Imperative_HOL_Time https://pdfs.semanticscholar.org/610c/ab44732605e05a2cc6359bfc47ae76260654.pdf В общем случае эта задача не решается. Это сильно зависит от алгоритма. Для начала он должен в принципе завершаться, вполне возможно, что там бесконечный цикл или рекурсия. Обычно когда на Isabelle HOL пишешь функцию, автоматически доказывается её завершаемость (function termination). Но если функция достаточно ядреная, то приходится доказывать вручную и это целая история. Сложность алгоритмов доказывать ещё сложнее. Есть отдельный класс алгоритмов: разделяй и властвуй . Он упоминается в статьях выше, для них описываются методы доказательства. Если реально хочется формально доказать, то, на это уйдет порядка полугода. Месяца через 2-3 вы только начнете понимать самые базовые вещи в формальных доказательствах. У меня, например, на эту штуку ушло 1,5 года. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 04:49 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Если нужно оценивать сложность произвольного алгоритма и полностью формальное доказательство не нужно, то я бы сделал анализатор выражений. Для начала тупо искал бы в AST циклы, потом добавил анализ использования переменных циклов, чтобы отслеживать такие ситуации: Код: c# 1.
Потом добавил анализ рекурсивных вызовов. И дальше по мере поступления новых алгоритмов усложнял анализ. На выходе анализатора можно выдавать две вещи: 1) примерную оценку 2) какие-нибудь граничные значения переменных, которые использовал бы при запуске алгоритма, чтобы посчитать реальное время выполнения Затем сравнивал бы оценку и то, что получается по результатам запуска. Если есть расхождения, то выдаём предупреждение. И такие алгоритмы оцениваем уже китайским методом: арендуем подвальчик с сотней китайцев. Они анализируют алгоритм и дорабатывают оцениватель. Хотя не обязательно подвальчик, можно запилить какой-нибудь сайт или мобильную игру "Оцени сложность алгоритма". Кстати, есть безумная идея. Можно сделать алго-валюту (a la крипто-валюта). Только если в криптовалютах деньги даются тупо за вычисление хеша. То в алго-валюте деньги будут выдаваться за более эффективную реализацию алгоритмических задачек. Скажем один участник отправляет в p2p-сеть алгоритмическую задачку, минимальные требуемые критерии (например, максимальная сложность, объем памяти и т.п.) и какую-то сумму реальных денег. Другие участники отправляют свои реализации алгоритма. 1-ый чел, который отправил алгоритм, который удовлетворяет минимальным условиям, получает допустим 1/e или 1/pi от исходной суммы. 2-ой чел, который отправит алгоритм лучше 1-го получит 1/e от оставшейся суммы и т.д. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 06:27 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Кстати, одним из обязательных требований к реализации алгоритма может быть наличие формального доказательства сложности. Если оно нужно, то чел донатит штуку баксов и люди потом сидят полгода доказывают. Или быстрее, если они гении математики. Interloper, короче, всё, другого общего решения у этой задачки нет. Нужно делать алго-валюту, инфа 100%. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 06:50 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinЛюбое конечное большое число памяти всегда много меньше, чем бесконечное. "много меньше" это значит, что даже если ты помножишь этот объем памяти сам на себя хоть тысячу раз подряд, все равно будет меньше. Конечное число памяти позволяет проверить алгоритм только на конечном наборе данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 07:52 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinНо если запустить алгоритм на следующих NВ рамках задачи, где алгоритм определен для любого целого N <= 3 нельзя запускать этот алгоритм для любого N > 3. [/quot] В рамках задачи алгоритм определен для любого целого N. Это у вас есть памяти столько, что вы можете проверить алгоритм только для значений N<=3, что не даст правильно оценить сложность алгоритма. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 07:54 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinОпять вернулись к тому, что вы ставите в условие конечность алгоритма, а потом требуете определить его работоспособность за пределами условий. Вы путаете конечность алгоритма в смысле того, что он заканчивается за конечное число шагов, и конечность множества допустимых входных данных. Алгоритм "сумма двух чисел" конечен, но на вход ему могут быть поданы сколь угодно большие числа и их бесконечно много. AklinА когда вам отвечают, что это не удолевтворяет условиям задачи, либо же говорят, что это невозможно - вы сразу со своей несвязанной и неверной теорией лезите про "общий случай при заранее известных конечных условиях". Нет никаких общих случаев, если есть заданные условия. Если вы не понимаете теорию, это не делает ее неверной и несвязной. Что касается общих случаев: я указал в постановке задачи, что интерес представляет общий случай, универсальный алгоритм. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 08:01 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperКонечное число памяти позволяет проверить алгоритм только на конечном наборе данных. Если вопрос стоит о проверке алгоритма на объеме памяти большем, чем есть на этом компьютере, значит эту задачу на этом компьютере решать нельзя. Не пытайтесь ложкой прокопать тоннель под Ла-Маншем. Для начала обзаведитесь техникой. InterloperВ рамках задачи алгоритм определен для любого целого N. Это у вас есть памяти столько, что вы можете проверить алгоритм только для значений N<=3, что не даст правильно оценить сложность алгоритма.Тот же ответ: если памяти не хватает, то _НЕЛЬЗЯ_ определять. Можно переформулировать условия задачи для N <= 3, тогда можно. А иначе нельзя. Это уже другая задача. Тут вопрос простой, я выше писал. МОжно ли запустить алгоритм с массивом N > 3 на компьютере с памятью N <= 3 и при этом алгоритм не упадет? Ответ: не выйдет, алгоритм упадет (будет читать ошибочные данные и т.п.), то есть алгоритм неработоспособный. А значит мы простыми методами доказали на практике неработоспособность алгоритма, задача решена. Алгоритм отправляется разработчикам для правок (чтобы на компьютере с памятью N <= 3 можно было загружать данные N > 3). А пока этого не сделано, у нас готовый ответ: алгоритм не работает. Зачем определять сложность неработающего алгоритма я не понимаю. InterloperВы путаете конечность алгоритма в смысле того, что он заканчивается за конечное число шагов, и конечность множества допустимых входных данных. Алгоритм "сумма двух чисел" конечен, но на вход ему могут быть поданы сколь угодно большие числа и их бесконечно много. В линуксе есть генератор случайных чисел, чтение из которого никогда не заканчивается. Сделаем проще. Запустим алгоритм читать из этого генератора число размером больше, чем оперативная память. А когда алгоритм упадет по причине нехватки памяти объявим, что алгоритм неработоспособный и оценка его сложности невозможна. Задача решена. Мысль по-прежнему кристально чиста: 1) определить, что алгоритм конечен на данном компьютере для всех допустимых входных комбинаций (это вопрос к верификации). если это по каким-либо причинам, вне зависимости от причин, не может быть реализовано, то принимаем сложность равную "минус один", что идентично "алгоритм завис или упал". 2) определить асимптоту и погрешность. если погрешность относительно мала, то ответ найден. Если велика, то принимаем сложность алгоритма как "минус два", что идентично "сложность алгоритма случайна". ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 12:22 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
А если задача стоит определить сложность не запуская алгоритм на компьютере, то это совсем иные методы. Но начинать все равно придется с определения конечности. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 12:23 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinЗачем определять сложность неработающего алгоритма я не понимаю. Алгоритм работает. Но на вашем конкретном компьютере он имеет предельно допустимый набор возможных входных данных. На другом компьютере будет другой. Оценивая алгоритм только на своем компьютере, вы не сможете сделать вывод о его асимптотическом поведении, так как для этого нужно знать, как алгоритм ведет себя при неограниченном увеличении N. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 13:32 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinНо начинать все равно придется с определения конечности. Что вы понимаете под конечностью? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 13:32 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperОценивая алгоритм только на своем компьютере, вы не сможете сделать вывод о его асимптотическом поведении Сможем. Это называется "экстраполяция" и является результатом решения задачи аппроксимации набора значений некоторой функцией. Поэтому возвращаемся к первому ответу: получаем столько пар (N,t) сколько не надоест, строим по ним график из точек, аппроксимируем их разными функциями, смотрим в какую функцию он укладывается лучше всего. Эту функцию и объявляем сложностью данного алгоритма. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 14:02 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, Существуют алгоритмы, для которых такой способ будет давать неверное решение. Пример приводил выше. Так можно и рандомно выбирать сложность и объявлять ее ответом. Точное решение либо есть, либо его нет. Для данной задачи - нет и в принципе быть не может. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 15:39 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperДля данной задачи - нет и в принципе быть не может. Как скажете, сэр. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 16:26 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperАлгоритм работает.Это не доказано. InterloperОценивая алгоритм только на своем компьютере, вы не сможете сделать вывод о его асимптотическом поведении А вы не сможете оценить его на всех компьютерах планеты, а значит, даже имея линейны алгоритм, состоящий из одного цикла, вы не можете говорить с вероятностью даже близкой к 50%, что у него сложность линейная, ведь это не так. Другими словами, в вашем "общем случае, мы действительно не можем определить сложность нерабоющего алгоритма хотя бы потому, что он не работает". InterloperAklinНо начинать все равно придется с определения конечности. Что вы понимаете под конечностью? Конечный объем входных данных на конечном ограниченном числе машин с конечным ограниченным числом параметров, и при этом на этих условиях алгоритм работает конечное время, не превышающее заданное. Если это не так, то алгоритм нуждается в доработке. Dimitry SibiryakovПоэтому возвращаемся к первому ответу: получаем столько пар (N,t) сколько не надоест, строим по ним график из точек, аппроксимируем их разными функциями, смотрим в какую функцию он укладывается лучше всего. Эту функцию и объявляем сложностью данного алгоритма.Если верить ТС, не выйдет, потому что нужно построить график для таких N, которые ни один компьютер в мире запустить не сможет. InterloperТочное решение либо есть, либо его нет. Для данной задачи - нет и в принципе быть не может.Для неточной задачи не может быть точного решения. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 19:01 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinЕсли верить ТС, не выйдет, потому что нужно построить график для таких N, которые ни один компьютер в мире запустить не сможет. Да, да, я уже понял, что слова "аппроксимация" и "экстраполяция" для него пустое сотрясение воздуха, недостойное открытия гугля. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.06.2019, 19:25 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, Постановка задачи требует точного ответа, аппроксимация здесь неуместна. Аппроксимировать можно, что угодно, но задача не звучит как "аппроксимируйте сложность алгоритма". ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 07:56 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinКонечный объем входных данных на конечном ограниченном числе машин с конечным ограниченным числом параметров, и при этом на этих условиях алгоритм работает конечное время, не превышающее заданное. Конечность алгоритма никак не связана с выходными данными и машинами. Алгоритм сортировки - конечен. Работает с массивами сколь угодно большой длины. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 07:59 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinДругими словами, в вашем "общем случае, мы действительно не можем определить сложность нерабоющего алгоритма хотя бы потому, что он не работает". В общем случае мы не можем определить сложность рабочего алгоритма, потому что эта задача эквивалентна алгоритмически неразрешимой задаче определении того, закончит ли произвольный алгоритм работу за конечное число шагов. Если вы не верите, что такая задача неразрешима, теория алгоритмов в помощь. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 08:02 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Завершаемость определить проще. Для функциональных языков, где единственный источник незавершаемости - это рекурсия, это делается так. 1) Для всех аргументов определена мера. Для числовых аргументов - это обычно просто значение числа. Для строковых - это может быть длина строки или ещё что-то. Для алгебраических типов данных - это обычно количество конструкторов в выражении. Например для "Cons 4 (Cons 2 Nil)" размер может быть равен 3. Аналогично вычисляется размер деревьев (количество узлов) и т.п. Для таких простых типов мера обычно определяется автоматически. Для более сложных её приходится определять вручную. Например, мне здесь пришлось определить такую меру: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
2) По умолчанию тот же Isabelle HOL пытается найти аргумент или комбинацию аргументов функции, которые с каждым шагом рекурсии уменьшаются. Обычно этого достаточно. 3) Если автоматически не доказывается, то приходится вручную определять меру (которая уменьшается с каждым шагом) и доказывать, что она действительно уменьшается. Например, здесь я доказывал это так (сама функция и теоремы есть по ссылке): Код: sql 1. 2. 3.
А здесь (раздел 4.1) есть хороший пример почему автоматическое доказательство завершаемости может не работать: Код: sql 1. 2.
Эта функция вычисляет сумму 1+2+...+N Аргумент i с каждым шагом увеличивается на 1, а аргумент N остается неизменным. Поэтому они определяют меру N - i, которая с каждым шагом уменьшается. И ещё добавляют 1, видимо потому, что на последнем вызове рекурсии i > N. При этом N - i будет всё-равно 0, потому что это натуральные числа, а не целые. И если не добавить 1, то на двух последних шагах мера будет 0 - оставаться неизменной, а должна уменьшаться. Код: sql 1. 2. 3. 4.
Для императивных языков доказательство завершаемости должно быть сложнее, потому что там есть переменные, значения которых могут изменяться не только при рекурсивных вызовах, но просто по ходу выполнения алгоритма. Но общая идея там должна быть такая же: 1) Определяем источники незавершаемости. Тут кроме рекурсивных вызовов это могут быть циклы и функции из стандартной библиотеки! Кстати функции из стандартной библиотеки могут ещё и влиять на сложность алгоритма: поиск в массиве, в хеше и т.п. 2) Определяем простые правила для определения завершаемости (например, один из аргументов или их комбинация всегда уменьшаются или, например, переменная цикла только уменьшается/увеличивается пока не доходит до конечного значения). 3) Для сложных ситуаций всё-равно пользователю придется определять кастомную меру. Кстати, эта мера может быть обязательной частью алгоритма. Чел, который написал алгоритм, пусть прикладывает и меру. 4) Самая жесть - это интегрировать всё это с какой-нибудь системой автоматического доказательства теорем. Обычно это сводится к тому, что нужно реализовать этот язык программирования (на котором пишутся алгоритмы) в Isabelle HOL или ещё какой-то системе. Для Isabelle HOL есть какая-то реализация Java, какие-то примеры простых абстрактных императивных языков. Я, например, реализовывал язык OCL . Причём, там только абстрактный синтаксис, система типов, правила типизации выражений, без семантики. Для того же C# или другого языка нужно либо искать готовую реализацию, либо это тема для докторской диссертации на несколько лет. Короче, сделать всё полностью формально очень сложно. Если это требуется, то проще всего, чтобы люди, которые пишут алгоритмы, писали их сразу на нормальном языке типа Isabelle HOL, который поддерживает автоматизированные доказательства теорем. При этом сами и доказывали бы завершаемость, сложность и т.п. Либо можно использовать языки, которые легко интегрируются с такими системами. Для Scala вроде было что-то такое. Если формальное доказательство не нужно. А просто запускать алгоритм много раз - это слишком тупо. То нужны какие-то эвристики. Например, парсим функцию, получаем её абстрактное синтаксическое дерево (во многих языках это поддерживается). И анализируем циклы, рекурсивные вызовы и т.п. Затем подтверждаем полученную оценку запуском алгоритма на разных входных данных. С практической точки зрения это самое простое и реальное, что можно сделать. На мой взгляд такая штука была бы очень прикольной и востребованной. Например, есть PVS Studio, которая не может формально доказать корректность программы, но в ней заложено много эвристик, которые находят типовые ошибки. С практической точки зрения это уже не плохо. Аналогично и ваша штука могла бы примерно оценивать сложность алгоритмов. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 10:04 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Ares_ekb, попробуй ради интереса доказать так O(N) для алгоритма составления бинарной кучи ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 10:30 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperПостановка задачи требует точного ответаНельзя сделать точный ответ в неточных условиях. InterloperКонечность алгоритма никак не связана с выходными данными и машинами. Алгоритм сортировки - конечен. Работает с массивами сколь угодно большой длины. Пока нет гарантий что алгоритм вообще работает и выдает верный ответ - оценивать его бесполезно. InterloperВ общем случае мы не можем определить сложность рабочего алгоритма, потому что эта задача эквивалентна алгоритмически неразрешимой задаче определении того, закончит ли произвольный алгоритм работу за конечное число шагов. Если вы не верите, что такая задача неразрешима, теория алгоритмов в помощь. Ты снова пытаешься получить ТОЧНЫЙ Ответ на задачу без условия. Так не выйдет. Сделай условие. Сделай границы работы. И тестируй. Если же вопрос про ТЕОРЕТИЧЕСКУЮ сложность - это вопрос анализа структуры кода, не более чем. Объем данных тут роли не играет. Это сугубо теоретическая оценка, не привязанная ни к чему. Для этой оценки не нужно запускать этот алгоритм даже один раз. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 12:10 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinЗачем определять сложность неработающего алгоритма я не понимаюЗатем, что это сферический алгоритм, да ещё и в ваккууме. Такова идэ фикс ТСа. Причём, в задаче нет ни теоретического, ни практического значения. Таких вы ни в чём не убедите, поздравьте с открытием, и прения прекратятся. Лично я поздравляю! З.Ы. Может кто недопонимает неразрешимость массовой алг-й пр-мы. Это не возможность решить задачу в принципе, а невозможность составить один такой алгоритм для всех частных случаев. Я не уверен, что ТС сам это до конца понимает. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 13:08 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperПостановка задачи требует точного ответа Не может быть у этой задачи точного ответа, поскольку так называемая "сложность алгоритма" - не точная величина, а всего лишь грубая оценка. Она не может быть применена для вычисления времени работы алгоритма на заданном объёме данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 13:52 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
exp98Затем, что это сферический алгоритм, да ещё и в ваккууме. Такова идэ фикс ТСа. Причём, в задаче нет ни теоретического, ни практического значения.Я так понял, что ТС хочет определить некую сложность для сферического в вакууме и нигде не описанного алгоритма в общем виде. Алгоритм-то в общем виде, а вот сложность должна быть точной величиной. Забавно в общем. А чем дальше тем веселее: раз для ряда алгоритмов сложность нельзя определить потому что алгоритмы не могут завершиться, то значит это правило ТС растягивает на все алгоритмы без исключения, делая заранее придуманный им вывод, со ссылками на несвязанные статьи. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 14:19 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Dimitry SibiryakovInterloperПостановка задачи требует точного ответа Не может быть у этой задачи точного ответа, поскольку так называемая "сложность алгоритма" - не точная величина, а всего лишь грубая оценка. Она не может быть применена для вычисления времени работы алгоритма на заданном объёме данных. Да эта теоретическая оценка может очень сильно отличаться. И мы даже не сможем придумать никакой поправочный коэффициент. Поскольку тут дело будет даже не в коэффициенте. Вобщем простая многослойная нейронная сеть автору в помощь и наверное удастся экспериментально подобрать кривую похожую на фактический отклик алгоритма. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 14:35 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Aklinexp98Затем, что это сферический алгоритм, да ещё и в ваккууме. Такова идэ фикс ТСа. Причём, в задаче нет ни теоретического, ни практического значения.Я так понял, что ТС хочет определить некую сложность для сферического в вакууме и нигде не описанного алгоритма в общем виде. Алгоритм-то в общем виде, а вот сложность должна быть точной величиной. Забавно в общем. А чем дальше тем веселее: раз для ряда алгоритмов сложность нельзя определить потому что алгоритмы не могут завершиться, то значит это правило ТС растягивает на все алгоритмы без исключения, делая заранее придуманный им вывод, со ссылками на несвязанные статьи. Сложность должна быть не точной величиной, а указанием на один из классов сложности. Но в целом вы почти меня поняли: так как не существует универсального алгоритма для определения факта остановки любого алгоритма, то и не существует универсального алгоритма для проверки сложности, иначе этот алгоритм может быть преобразован в алгоритм определения факта остановки. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 18:30 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Ares_ekb, Интересно, изучу ваши выкладки на досуге, спасибо. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 18:33 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperСложность должна быть не точной величиной, а указанием на один из классов сложности. Interloperтак как не существует универсального алгоритма для определения факта остановки любого алгоритма Не существует алгоритма для оценки неработающего алгоритма в виде черного ящика. Для работающего алгоритма с исходниками алгоритм определения сложности придумать несложно, он будет прост, тем более, что есть множество испытанных практических методов, описанных выше. InterloperСложность должна быть не точной величиной, а указанием на один из классов сложности.Это сугубо теоретический вопрос тогда, а не вопрос программирования. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 18:39 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
А ещё я тугодум и так и не понял автор...алгоритма для проверки сложности, иначе этот алгоритм может быть преобразован в алгоритм определения факта остановки Для нас доказали теорему о неразрешимости массовой проблемы останова. Проверка сложности является частным случаем алгоритма проверки останова. Для этого ч-го случая мне лично не приходилось видеть признанных доказательств неразр-ти. Кроме того,не приходилось видеть и док-в того, что если неразрешима массовая проблема, то неразр-ма и частная проблема. Тем не менее нам здесь пытались втюхать, что она верна по причине того, что является ч-м случ-м алгоритма проверки останова и потому верна. Т.о., налицо неправомерное применение "доказательства от противного", т.е. весьма противное доказательство. И прежде всего я протестовал против этого, поскольку все другие рассуждения были достаточно очевидны. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 20:09 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinНе существует алгоритма для оценки неработающего алгоритма в виде черного ящика. Слова "неработающего" и "в виде черного ящика" уберите, а так все верно. С чего вы выдумали, что речь идет о неработающих алгоритмах - ума не приложу. Что касается вида, то он может быть любой, хоть исходный код. Не исходный код какого-то одного конкретного алгоритма: алгоритм оценки должен принимать на вход исходный код любого алгоритма. Для частного случая в виде подмножества алгоритмов, решение, безусловно существует. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 21:04 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
AklinЭто сугубо теоретический вопрос тогда, а не вопрос программирования. Это вопрос теории алгоритмов, естественно, а не того программирования, которым вы занимаетесь в офисе. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 21:05 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
exp98Для этого ч-го случая мне лично не приходилось видеть признанных доказательств неразр-ти. . Доказательство приведено в этой теме на 2й странице. Оно достаточно простое, чтобы в нем мог разобраться любой, кто знает основные понятия математической логики. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 21:06 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
kealon(Ruslan)попробуй ради интереса доказать так O(N) для алгоритма составления бинарной кучи Чтобы доказать формально нужно время. Интересная идея, я попробую, если будет возможность. Но на это уйдет наверное неделя-две, потому что я никогда таким не занимался. А с помощью эвристик это можно сделать так: Алгоритм выглядит следующим образом (по ссылке ещё есть ссылка на прикольную книгу, где всё описано более подробно "Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ"): Код: sql 1. 2. 3. 4.
где A - это входной массив, который нужно превратить в кучу A.length - его длина (которая равна длине кучи A.heap_size и для простоты мы эту длину будем иногда обозначать просто N) Heapify - это функция, которая упорядочивает элементы в поддереве кучи: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
Допустим этот алгоритм написан на каком-то реальном ЯП, а не псевдоязыке. Мы распарсили его и получили абстрактное синтаксическое дерево (AST), которое будем анализировать. Сначала оценим сложность функции Heapify: Видим в AST этой функции рекурсивный вызов себя. Других рекурсивных вызовов или циклов нет, значит сложность определяется этим единственным вызовом. При рекурсивном вызове передаются 2 аргумента: A и largest. Аргумент A в теле функции никак не изменяется и передаётся как есть. Для largest возможны 3 варианта: 1) largest = i, в этом случае рекурсия прекращается 2) largest = 2i 3) largest = 2i+1 Короче анализатор AST должен сделать такие выводы: 1) С каждым рекурсивным вызовом i как минимум удваивается. 2) Рекурсия прекращается в худшем случае когда i достигает A.heap_size (для простоты будем называть её N) В wiki и в книге из этого делается неправильный вывод, что сложность этой функции равна O(log N). Наш же анализатор должен сделать вывод, что сложность равна O(log N) - O(log i) или просто O(log N/i). Где log - логарифм по основанию 2. Попробую пояснить почему так. Например есть цикл: Код: sql 1.
Для него сложность будет O((N-i)/step). Если i=0 и step = 1, то это вырождается просто в O(N). Для такого цикла: Код: sql 1.
Сложность будет O(log_step(N/i)), где log_step - логарифм по основанию step. Функция Heapify эквивалентна как-раз такому циклу со step = 2. Теперь оцениваем сложность Build_Heap. Видим в ней цикл от floor(N/2) до 1 с шагом 1. Сложность цикла равна O(sum_i (сложность тела цикла)) = O(sum_i (log N/i)) = O(sum_i (log N) - sum_i (log i)) = (раскрываем сумму по i от 1 до N/2) O(N/2 * log N - log (N/2)!) = (тут мы используем тот факт , что O(log N!) = O(N log N)) O(N/2 * log N - N/2 * log (N/2)) = O(N/2 * log (N / N/2)) = O(N/2 * log 2) = (отбрасываем константы) O(N) Готово! Чтобы все эти вычисления автоматизировать нужно: 1) Заложить все эти эвристики по анализу for, if, рекурсивных вызовов и т.п. в абстрактных синтаксических деревьях 2) Нужна какая-то система, которая упрощает O-выражения - это выглядит вполне реальным. Возможно подойдут готовые системы для символьных вычислений или можно самому что-то написать. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 22:57 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Идея всего этого такая... В книге приводится какое-то очень не тривиальное доказательство сложности O(N). Там делается утверждение Поскольку число вершин высоты h в куче из n элементов не превышает ceil(n / 2^(h+1)), а высота всей кучи не превышает floor(lg n), то время работы не превышаети дальше приводится какая-то безумная формула. Автоматизировать такие рассуждения невозможно. А ту последовательность действий, которую я привёл выше, вполне можно автоматизировать. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.06.2019, 23:10 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Насчет формальных доказательств. Нашёл очень клёвую реализацию некоторого абстрактного императивного языка IMP2 для Isabelle HOL. В нём есть переменные, циклы, условия и т.п. Ещё можно задавать разные инварианты для императивных программ, которые можно доказывать. И ещё для этого языка буквально неделю назад запилили реализацию двоичной кучи как-раз по книге Кормена Т. и др. "Алгоритмы: построение и анализ". Там доказывается корректность этой реализации. Причём реализация двоичной кучи занимает по идее 1 страницу, а доказательств там больше чем на 20 страниц. И это даже без доказательства сложности алгоритма. Это показывает на сколько всё сложно с формальными методами. На практике для произвольных алгоритмов реально использовать только какие-то эвристики, которые описывал выше. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 08:38 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Ares_ekb, да, в математическом доказательстве используется сходящаяся геометрическая прогрессия - тынц И это очень простой пример, без подкавык. По многим алгоритмам используется оптимистичная оценка, например: хэш-таблица, декартово дерево Судя по всему, даже со специализированным языком "с подсказками" и частично работающее, в общем виде реально тянет на RocketScience ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 09:38 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Ares_ekbНасчет формальных доказательств. Нашёл очень клёвую реализацию некоторого абстрактного императивного языка IMP2 для Isabelle HOL. В нём есть переменные, циклы, условия и т.п. Ещё можно задавать разные инварианты для императивных программ, которые можно доказывать. И ещё для этого языка буквально неделю назад запилили реализацию двоичной кучи как-раз по книге Кормена Т. и др. "Алгоритмы: построение и анализ". Там доказывается корректность этой реализации. Причём реализация двоичной кучи занимает по идее 1 страницу, а доказательств там больше чем на 20 страниц. И это даже без доказательства сложности алгоритма. Это показывает на сколько всё сложно с формальными методами. На практике для произвольных алгоритмов реально использовать только какие-то эвристики, которые описывал выше.я так подозреваю, что если ты не НАСА, то платить программистам за такую разработку явно перебор :-) ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 09:42 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperAklin Слова "неработающего" и "в виде черного ящика" уберите, а так все верно. С чего вы выдумали, что речь идет о неработающих алгоритмах - ума не приложу. Что касается вида, то он может быть любой, хоть исходный код. Не исходный код какого-то одного конкретного алгоритма: алгоритм оценки должен принимать на вход исходный код любого алгоритма. Для частного случая в виде подмножества алгоритмов, решение, безусловно существует.С того, что его разработчик не может гарантировать конечность времени исполнения этого алгоритма на допустимых входных данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 12:02 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperAklinЭто сугубо теоретический вопрос тогда, а не вопрос программирования. Это вопрос теории алгоритмов, естественно, а не того программирования, которым вы занимаетесь в офисе.Тогда речь не может идти о том, что на компьютере не хватит памяти, или вообще о количестве запусков. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 12:03 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
InterloperСложность должна быть не точной величиной, а указанием на один из классов сложности. Тогда вспоминай матан (если, конечно, для тебя это слово не матерное). Степенная функция отличается от линейной и логарифмической. Причём для их различения достаточно трёх точек. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 13:36 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Dimitry SibiryakovПричём для их различения достаточно трёх точек.В указанных ТС пределах делать замеры нельзя, ибо функция может потенциально зависнуть. А если она "может" то зависнет. А если зависнет, то встает вопрос об алгоритмически невозможном определении конечности этого алгоритма, а это известная доказанная проблема, поэтому даже пытаться не стоит =) А доказывать математически он не хочет. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 13:46 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
kealon(Ruslan)да, в математическом доказательстве используется сходящаяся геометрическая прогрессия - тынц И это очень простой пример, без подкавык.Проблема таких доказательств как по ссылке в том, что их невозможно автоматизировать. Там очень много рассуждений, каких-то посылок, которые берутся просто из головы автора и никак не следуют из структуры алгоритма. Например, откуда взялась эта лемма "Пусть для какого-то элемента массива при вызове siftdown было сделано i вызовов оператора swap. Тогда его индекс не превосходил floor(n/2^i)"? Ни один инструмент точно не сможет сформулировать и доказать такую лемму из ниоткуда. Чтобы можно было оценивать сложность автоматически, нужно свести эту процедуру к каким-то очень простым шагам. Пусть этих шагов будет очень много, пусть там будет много тупого перебора, но зато это можно автоматизировать. Насчет подкавык. Вполне возможно, что для человека какое-то доказательство будет сложным, а для тупого машинного перебора - простым. Или наоборот. kealon(Ruslan)Судя по всему, даже со специализированным языком "с подсказками" и частично работающее, в общем виде реально тянет на RocketScienceЕсли полностью формальное доказательство, то да. А если какие-то полуформализованные эвристики по анализу кода, как я описывал, то вполне реально сделать. Хотя даже это вполне потянуло бы на диссертацию :) ... |
|||
:
Нравится:
Не нравится:
|
|||
21.06.2019, 15:16 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Если взять просто быструю сортировку Хоара (QuickSort). Сложность в худшем n^2. Сложность в среднем n*log, да и то сложность в среднем оценивается лишь вероятностно. Доказательство сложности в среднем даже зная алгоритм непростая задача. А для черного ящика видимо и вообще мрак. Если "опорный элемент" для хоара будет случайно выбираться, уже с оценкой будешь иметь проблему: иногда n*log, а иногда n^2. Оценка по сложности это скорее подсказка, чтобы не попасть с проклятием размерности, а не точная величина. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.06.2019, 04:19 |
|
Верификация сложности алгоритма
|
|||
---|---|---|---|
#18+
Interlopermaytonпропущено... Твои уточняющие вопросы напоминают легкий троллинг отвечающих. Тебе уже в первом ответе дали методику. Ты ее применил? Ты нарисовал график в Excel? Давай дружище сделай как советуют опытные. А потом подойдешь к теории снова. График меня не интересует. Я уже понял, что проблема алгоритмически неразрешима. Вопрос я задал фундаментальный, решение тупо взять нарисовать график, очевидно, не решает поставленную задачу. InterloperПредположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения. Как программно проверить, верно ли предположение о сложности? Программно проверить? Напишите программу, если хотите программно проверить. Одним из параметров будет функция подозрительная на асимптотику, проведите ряд экспериментов по n, постройте отношение затраченного времени черного ящика и ф. подозрительной на асимптотику, если функция та самая, то в пределе получите константу. Что там как вы говорите алгоритмически неразрешимого? Вам по-моему о чем-то подобном говорили ... |
|||
:
Нравится:
Не нравится:
|
|||
11.07.2019, 21:27 |
|
|
start [/forum/topic.php?all=1&fid=16&tid=1339926]: |
0ms |
get settings: |
9ms |
get forum list: |
12ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
42ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
110ms |
get tp. blocked users: |
1ms |
others: | 12ms |
total: | 206ms |
0 / 0 |