Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2 3 4 5      [все]
 Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Предположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения.
Как программно проверить, верно ли предположение о сложности?
17 июн 19, 12:31    [21909660]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
плавно увеличивать N и замерять время работы алгоритма в различных попугаях ?

100-120-144-172-207...-1000000000000
17 июн 19, 12:40    [21909670]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
плавно увеличивать N и замерять время работы алгоритма в различных попугаях ?

100-120-144-172-207...-1000000000000


И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?
17 июн 19, 13:36    [21909732]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?
Постройте два графика: получившийся и предполагаемый. Сделайте сравнение в пределах погрешности.
17 июн 19, 13:38    [21909733]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48659
График, построенные по результатам эксперимента, должен совпасть с графиком, построенным на теоретических данных, с заданной точностью.
17 июн 19, 13:38    [21909734]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Interloper
И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?
Постройте два графика: получившийся и предполагаемый. Сделайте сравнение в пределах погрешности.


Насколько большое N нужно брать для графика?
17 июн 19, 13:43    [21909736]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Насколько большое N нужно брать для графика?
Зависит от того, под какие данные рассчитан алгоритм.

Если речь идет про простую сферическую в вакууме сортировку уровня студенческих лабораторных, то я бы сказал, что достаточно взять до миллиона элементов.

Просто бывают алгоритмы, к примеру тех же сортировок, рассчитанных на сортировку малых массивов, скажем, до 20 элементов. И гонять такой алгоритм даже на 100 элементах уже кощунство.
17 июн 19, 13:50    [21909743]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Interloper
Насколько большое N нужно брать для графика?
Зависит от того, под какие данные рассчитан алгоритм.

Если речь идет про простую сферическую в вакууме сортировку уровня студенческих лабораторных, то я бы сказал, что достаточно взять до миллиона элементов.

Просто бывают алгоритмы, к примеру тех же сортировок, рассчитанных на сортировку малых массивов, скажем, до 20 элементов. И гонять такой алгоритм даже на 100 элементах уже кощунство.


В том то и дело, что мы не знаем как устроен алгоритм внутри.
Для N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный.
Так что такой принцип решения не годится.
17 июн 19, 13:54    [21909748]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
x1ca4064
Member

Откуда:
Сообщений: 1011
Interloper
И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?


Делить время на сложность - должно асимптотически приближать к некоторой константе, т.е. Время/(n*log(n)), для Вашего примера.
17 июн 19, 13:57    [21909753]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
В том то и дело, что мы не знаем как устроен алгоритм внутри.

Если у алгоритма нет генератора случайных чисел в виде одного из параметров "работы", то пройдитесь от 1 до 2^K, каждый раз увеличивая размер чисел вдвое. Делая несколько замеров на каждом N, с разными входными данными. Верхний предел - простое любопытство, время, при котором компьютер будет гонять алгоритм достаточно продолжительное для вашего ожидания время. В некоторых случаях это могут и быть и сутки, но для простых замеров достаточно, чтобы алгоритм работал одну-две минуты.

Если есть генератор случайных чисел и он определяет сложность, и погрешность при этом велика, то никак вы не определите, что там внутри. Для одних и тех же данных время может различаться, либо различаться не на одних и тех же, а скажем на соседних данных (с точки зрения алгоритма). Например, 2+2 будет складываться одну минуту, а 2+3 уже пятнадцать минут.
17 июн 19, 13:58    [21909754]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin,

Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.
17 июн 19, 14:20    [21909778]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
x1ca4064
Interloper
И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?


Делить время на сложность - должно асимптотически приближать к некоторой константе, т.е. Время/(n*log(n)), для Вашего примера.


Каков алгоритм проверки на асимптотическое приближение?
17 июн 19, 14:20    [21909780]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Interloper
Aklin,

Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.
Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час.
17 июн 19, 14:56    [21909822]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
x1ca4064
Member

Откуда:
Сообщений: 1011
Interloper

Каков алгоритм проверки на асимптотическое приближение?


Я бы попробовал метод наименьших квадратов для линейного приближения: если угол наклона стремится к 0, значит приближаемся к асимптоте.
17 июн 19, 14:56    [21909824]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Barlone
Interloper
Aklin,

Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.
Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час.


Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.
17 июн 19, 14:58    [21909832]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
x1ca4064
Interloper
Каков алгоритм проверки на асимптотическое приближение?


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


Наклона чего по отношению к чему? Как будем оценивать стремление к нулю?
17 июн 19, 15:00    [21909833]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
x1ca4064
Member

Откуда:
Сообщений: 1011
Interloper

Наклона чего по отношению к чему? Как будем оценивать стремление к нулю?


У Вас есть набор точек Y=(Время)/(Сложность) от X=(Сложность), после МНК получим:
Y=a*X+b, если a мало (внешний задаваемый параметр, означет точность нашего диагноза), значит (Время)=O(Сложность)
17 июн 19, 15:06    [21909844]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Interloper
Barlone
пропущено...
Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час.


Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.
А вам с какой целью? Успешная проверка на некотором наборе вариантов не будет являться доказательством вашего предположения. Если конечно это не полный перебор всех возможных вариантов входных данных.
17 июн 19, 15:07    [21909848]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Barlone
Interloper
пропущено...


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


Мне чисто из интереса.
17 июн 19, 15:09    [21909851]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
x1ca4064
Interloper
Наклона чего по отношению к чему? Как будем оценивать стремление к нулю?


У Вас есть набор точек Y=(Время)/(Сложность) от X=(Сложность), после МНК получим:
Y=a*X+b, если a мало (внешний задаваемый параметр, означет точность нашего диагноза), значит (Время)=O(Сложность)


МНК даст нам оценку отклонения нашей функции от некоторой эталонной. Какую считать эталонной для O(N*N)? Нам то неизвестны коэффициенты, "спрятанные" внутри О большое.
17 июн 19, 15:12    [21909858]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Если чисто из интереса, то непонятна претензия:
Interloper
Для N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный.
Так что такой принцип решения не годится.

В любом случае, у программной реализации есть ограничения на входные данные: какое количество данных помещается в память, помещаются ли сами значения в используемый тип...
17 июн 19, 15:15    [21909861]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Если алгоритм работает с каким-то массивом, то константа про О большом будет меняться в момент, когда массив перестанет помещаться в кеш.
17 июн 19, 15:22    [21909871]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Barlone
Если чисто из интереса, то непонятна претензия:
Interloper
Для N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный.
Так что такой принцип решения не годится.

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

Чисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал.
Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.
17 июн 19, 15:24    [21909872]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Interloper
Чисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал.
Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.
Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности.
17 июн 19, 15:34    [21909878]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Barlone
Interloper
Чисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал.
Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.
Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности.


То есть такой проверяющий алгоритм не существует?
17 июн 19, 15:47    [21909894]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Interloper
Barlone
пропущено...
Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности.


То есть такой проверяющий алгоритм не существует?

Твои уточняющие вопросы напоминают легкий троллинг отвечающих.
Тебе уже в первом ответе дали методику.

Ты ее применил? Ты нарисовал график в Excel?

Давай дружище сделай как советуют опытные. А потом подойдешь к теории снова.
17 июн 19, 19:25    [21910149]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
mayton
Interloper
пропущено...


То есть такой проверяющий алгоритм не существует?

Твои уточняющие вопросы напоминают легкий троллинг отвечающих.
Тебе уже в первом ответе дали методику.

Ты ее применил? Ты нарисовал график в Excel?

Давай дружище сделай как советуют опытные. А потом подойдешь к теории снова.


График меня не интересует. Я уже понял, что проблема алгоритмически неразрешима.
Вопрос я задал фундаментальный, решение тупо взять нарисовать график, очевидно, не решает поставленную задачу.
17 июн 19, 23:11    [21910210]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
А чего ты ожидал?
17 июн 19, 23:27    [21910214]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
mayton,

доказательство несуществования такого проверяющего алгоритма
18 июн 19, 08:12    [21910271]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Действительно, пусть существует проверяющий алгоритм 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 июн 19, 11:33    [21910432]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Aklin,

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

Это несложно проверить, сделав, скажем, сто тестов на одной длине массива.


Interloper
или показать, что его не существует.
Скорее нужно придумать наличие факторов, которые не дадут честно замерить время. Например тот же рандом при задержках. Если задержка будет каждый раз разная и на одном и том же массиве время будет различаться, скажем, в зависимости от предыдущих данных, тогда можно смело закрывать лавочку по данному алгоритму.


Дерзайте, экспериментируйте. За вас писать весь процесс никто не станет здесь.

Interloper
Каков алгоритм проверки на асимптотическое приближение?

Определение асимптоты можно в википедии прочитать, это несложно.

Interloper
Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.
Ну так определяйте величину конечности этого времени при длине массива (или числе тестов) стремящихся к бесконечности.


Interloper
То есть такой проверяющий алгоритм не существует?
Существует.
Называется программист.
В зависимости от конкретного поведения конкретного алгоритма придумываются конкретные действия по его тестированию.

Но, повторюсь, если в алгоритме рандом в качестве одного из ведущих факторов, то такой алгоритм вы за конечное время выявить не сможете, а его результаты будут битые (неверные).
Поэтому встает вопрос о алгоритмической неразрешимости.
А в этом случае нужно думать уже не методами программирования, а математическими теориями.
18 июн 19, 11:59    [21910457]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Действительно, пусть существует проверяющий алгоритм S, который может определить имеет ли произвольный алгоритм сложность O(nlogn). Покажем, как с его помощью можно решить проблему останова.
Не подходит. По условиям, алгоритм завершится за конечное время для любых входных данных.



Поэтому по сути решение задачи следующее: определить насколько сильной является поведение рандомной части (включая часть про зависимость от предыдущих данных) (пусть будет в процентах от общего времени исполнения это будет P). Это несложно сделать.

После этого сказать что для данного алгоритма определена следующая сложность (это тоже несложно сделать) с погрешностью 2*P.

Задача решена.
18 июн 19, 12:01    [21910461]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Заметим, что если A останавливается за конечное число шагов m, то начиная с некоторого n=n0 алгоритм P(n, A) так же выполняется за конечное число шагов (ему не приходится проверять алгоритм A на n^2 шагов, достаточно проверить m шагов), таким образом его сложность будет O(1) <= O(nlogn).
Неверно.

Неверный вывод из несвязанных предпосылок.
Если алгоритм имеет конечное время исполнения, это еще не значит, что у него сложность известная.
И уж тем более не значит, что она <= O(n*log(n))
18 июн 19, 12:03    [21910464]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Не подходит. По условиям, алгоритм завершится за конечное время для любых входных данных.

Это не мешает подать на вход любой алгоритм.
18 июн 19, 12:32    [21910504]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Неверно.

Неверный вывод из несвязанных предпосылок.
Если алгоритм имеет конечное время исполнения, это еще не значит, что у него сложность известная.
И уж тем более не значит, что она <= O(n*log(n))


Верно. Если алгоритм при увеличении n, начиная с определенного n выполняется за конечное константное время, то его сложность O(1) <= O(nlogn).
18 июн 19, 12:33    [21910506]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Поэтому по сути решение задачи следующее: определить насколько сильной является поведение рандомной части (включая часть про зависимость от предыдущих данных) (пусть будет в процентах от общего времени исполнения это будет P). Это несложно сделать.

После этого сказать что для данного алгоритма определена следующая сложность (это тоже несложно сделать) с погрешностью 2*P.

Задача решена.


Алгоритмы детерминированы, в них нет "рандомной части". Рассматриваются алгоритмы, выполняемые на детерминированной машине Тьюринга.
18 июн 19, 12:35    [21910511]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
exp98
Member

Откуда:
Сообщений: 1848
Interloper
Действительно, пусть существует проверяющий алгоритм S, который может определить имеет ли произвольный алгоритм ...
Дружище, вы безусловно в чём-то разбираетесь ... и немного путаетесь ...
Если вы знаете, что ваша задача из разряда неразрешимой массовой проблемы, то это не значит, что частный вариант проблемы обязательно неразрешим.
Выше уже ответили для случаев конкретных задач. Теоретизировать ступайте в теорию алгоритмов. Более того, если ваш сферический алгоритм похож на алгоритм с оракулом, то возможны всякие чудеса. Например он может в случайное время (закладка такая была) нажимать на тормоз/акселератор ... Или вообще, по команде извне ...
Кроме тестов, для чёрных ящиков не придумали лучшего.
Выбираете гипотезу, набираете статистику, проверяете гипотезу и т.д... Повезло - вы в коричневом в шоколаде ...
18 июн 19, 12:44    [21910522]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
exp98,

В чем путаюсь? Я знаю, что есть решение для частных случаев. Но меня интересует общий случай. И для общего случая проблема неразрешима.
18 июн 19, 12:47    [21910525]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Верно. Если алгоритм при увеличении n, начиная с определенного n выполняется за конечное константное время, то его сложность O(1) <= O(nlogn).

ММм... может и так, но к нашей задачи это отношения все равно не имеет.


Interloper
Не подходит. По условиям, алгоритм завершится за конечное время для любых входных данных.

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

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




Interloper
Алгоритмы детерминированы, в них нет "рандомной части". Рассматриваются алгоритмы, выполняемые на детерминированной машине Тьюринга.
Нет гарантий конечности времени исполнения на машине Тьюринга (см. выше).


Interloper
Но меня интересует общий случай. И для общего случая проблема неразрешима.
Общий случай на практике не встречается, только частные и конечные.
18 июн 19, 13:01    [21910553]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Алгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

1) требуем конечность алгоритма на всех допустимых входных данных.
если в требовании отказано, объявляем задачу о конечности алгоритмически неразрешимой
2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность.
3) задача решена.
18 июн 19, 13:03    [21910558]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Aklin
Алгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

1) требуем конечность алгоритма на всех допустимых входных данных.
если в требовании отказано, объявляем задачу об определении сложности алгоритмически неразрешимой
2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность.
3) задача решена.


поправка*
18 июн 19, 13:03    [21910559]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Aklin
Алгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

1) требуем конечность алгоритма на всех допустимых входных данных.
если в требовании отказано, объявляем задачу об определении сложности алгоритмически неразрешимой
2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность.
2.1) Если итоговая погрешность соизмерима с величиной асимптоты, то считаем алгоритм неконечным.
3) задача решена.
18 июн 19, 13:05    [21910561]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
В реальности имплементация алгоритма - будет наполнена побочными эффектами. Такими как
например
- попадание в кеши L2/L3
- наличие побочных эффектов многозадачности (Амдал и когеррентность)
- страничный кеш оперативной памяти
- резкое изменение отклика жёсткого диска в зависимости от нагрузки (близко к когеррентности)
- побочные эффекты рантайма (warmup) и управления памятью (фаза уборки мусора).

Они имеют более сложную (гистерезисную) природу и асимтотическая формула сложности
алгоритма как такового будет иметь бОльшую поправку. Грубо говоря вы просто увеличиваете
количество (n) и ожидаете к примеру логариму. Но на графике будет логарифма а потом - внезапный
скачок вверх (безо всякой видимой причины). И сколько ни смотрите на вашу формулу и алгоритм - там НИГДЕ
не будет видимого пояснения такого поведения.

Классическая машинка тьюринга не имела кешей L2/L3. Как вы будете их эффект учитывать - ума не приложу.
18 июн 19, 13:22    [21910584]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Алгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

1) требуем конечность алгоритма на всех допустимых входных данных.
если в требовании отказано, объявляем задачу о конечности алгоритмически неразрешимой
2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность.
3) задача решена.


Я могу придумать алгоритм, на котором ваши тесты покажут неверный результат, о том и речь. Так как тесты проверят только конечное число входных данных. А сложность алгоритма связана с его поведением на бесконечности.
18 июн 19, 13:22    [21910589]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
mayton,

Все же, для больших входных данных, эффектом кэшей можно пренебречь. Возьмите имплементацию любого алгоритма сортировки, нарисуйте график зависимости времени от размера массива - начиная с некоторого n он будет соответствовать установленной теоретической сложности алгоритма.
18 июн 19, 13:25    [21910591]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
mayton
Как вы будете их эффект учитывать - ума не приложу.
Практика показывает, что кэш ограничен, причем жутко ограничен и его легко перегрузить, тем самым нивелировать его эффект.

Но даже если речь пойдет про объемы входных данных соизмеримых с кэш, все равно погрешность не может превышать какие-то разумные пределы. Если оценка по времени будет в T, а погрешность даже в T/3, это перебор.

Поэтому с моей колокольни вопрос об оценке сложности стоит только в разделении алгоритма на конечный (=предсказуемый) и бесконечный (=непредсказуемый). Вторые рассматривать не следует хотя бы из невозможности их оценки.

Interloper
Так как тесты проверят только конечное число входных данных. А сложность алгоритма связана с его поведением на бесконечности.

Не стоит рассматривать недопустимые входные данные.
Если написано, что алгоритм принимает только конечные входные данные то смотрите сложность только в пределах допустимых входных данных. За пределами допустимых входных данных алгоритм следует считать неработающим (что есть равенство неконечности, а определение его сложности алгоритмически неразрешаемым). Тогда встает вопрос, зачем вообще оценивать алгоритм там, где он не работает?
18 июн 19, 13:29    [21910602]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin,

Можно написать алгоритм сортировки, который будет сортировать массив любого объема, помещающийся в памяти. Вы будете запускать тесты на всех возможных длинах массива? В таком случае, пока тесты завершатся, анализ будет уже никому не нужен.
18 июн 19, 13:32    [21910607]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
mayton,

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

В этом случае сложность понятна, но время исполнения будет зависеть исключительно от входных данных.

Для нашей задачи время для конкретного N нужно определять для разных входных данных (включая многочисленные повторы одинаковых входных цепочек), тем самым уйдя от удачных входных данных и от зависимости от предыдущих данных.


В конце концов речь будет идти только о вероятностном поведении. А значит нужно найти такой алгоритм оценки, который бы оценивал лучше, чем погрешность оценки, этого будет достаточно с математической точки зрения. Если речь идет про неконечные (=непредсказуемые) алгоритмы, то достаточно будет доказать, что погрешность оценки соизмерима (или выше), чем время работы алгоритма, а значит с вероятностной точки зрения оценивать алгоритм будет нельзя (=невозможно). Опять же, это тоже результат.
18 июн 19, 13:33    [21910608]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Aklin,

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


Мы говорим про оценку конечного алгоритма. Оценка конечная. Время на оценку конечное.
Время оценки у нас на одном конце линейки, а точность оценки (=погрешность) на другом. Уменьшая время на оценку увеличиваем погрешность.

Другими словами, нельзя сделать и быстро и дешево и качественно и одновременно.
А значит выбираем наиболее значимый параметр, и идем в его направлении.
18 июн 19, 13:36    [21910613]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Если речь идет про неконечные (=непредсказуемые) алгоритмы, то достаточно будет доказать, что погрешность оценки соизмерима (или выше), чем время работы алгоритма, а значит с вероятностной точки зрения оценивать алгоритм будет нельзя (=невозможно).


Мы не можем вычислить заранее, что алгоритм неконечный. Это фундаментальное ограничение.
18 июн 19, 13:40    [21910618]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Interloper
Aklin,

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


Мы говорим про оценку конечного алгоритма. Оценка конечная. Время на оценку конечное.
Время оценки у нас на одном конце линейки, а точность оценки (=погрешность) на другом. Уменьшая время на оценку увеличиваем погрешность.

Другими словами, нельзя сделать и быстро и дешево и качественно и одновременно.
А значит выбираем наиболее значимый параметр, и идем в его направлении.


На скольких наборах входных данных вы будете тестировать алгоритм?
18 июн 19, 13:41    [21910619]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48659
Interloper
В чем путаюсь?

В постановке задачи. В первом посте вы написали про алгоритм, имеющий фиксированную сложность. А потом внезапно перешли к чёрному ящику, внутри которого Х алгоритмов, причём каждый со своей сложностью.

Interloper
меня интересует общий случай.

Общий случай работает точно так же, только для каждого из Х вышеназванных алгоритмов выделяется диапазон и совпадение графиков проверяется отдельно на каждом из диапазонов.
18 июн 19, 13:42    [21910621]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Interloper
mayton,

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

Вы только что похоронили любую оптимизацию имплементации.
18 июн 19, 13:44    [21910625]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Мы не можем вычислить заранее, что алгоритм неконечный. Это фундаментальное ограничение.
Но можем вычислить погрешность времени исполнения.
Если, как я выше писал, погрешность измерения выше соизмерима с временем исполнения, тогда алгоритм следует перевести в разряд неконечных.



Interloper
На скольких наборах входных данных вы будете тестировать алгоритм?
А сколько у меня попыток для запуска?

Если у меня десять попыток, а входных данных может быть до миллиона, то сделаю по две попытки на 10, 100, 1000, 10000, 100000 и 1000000 элементов.
А потом посчитаю дельту между двумя запусками, о объявлю ее погрешностью

Если миллион попыток, а входных данных не больше 100, то можно по много раз перебрать все входные данные.
18 июн 19, 13:47    [21910631]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Dimitry Sibiryakov
Interloper
В чем путаюсь?

В постановке задачи. В первом посте вы написали про алгоритм, имеющий фиксированную сложность. А потом внезапно перешли к чёрному ящику, внутри которого Х алгоритмов, причём каждый со своей сложностью.

Interloper
меня интересует общий случай.

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


Возможно, действительно изложил сумбурно. Задача: анализировать алгоритмы, имеющие фиксированную сложность, но неизвестную нам, о которой мы можем лишь формулировать гипотезу.
В первом посте я писал, что мы можем просто замерять время выполнения на каждом тесте. Но пусть даже мы можем намного больше - анализировать исходный код алгоритма или его определение на машине Тьюринга. Оказывается, даже с таким расширенным инструментарием, точно проверить гипотезу о сложности невозможно.
18 июн 19, 14:13    [21910663]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Dimitry Sibiryakov
Общий случай работает точно так же, только для каждого из Х вышеназванных алгоритмов выделяется диапазон и совпадение графиков проверяется отдельно на каждом из диапазонов.


В том-то и дело, что нет способа выбрать диапазон, достаточный для проверки. А проверять на всем диапазоне тупо перебором нецелесообразно - это займет намного больше времени, чем практическая эксплуатация алгоритма. Более того, даже если вы проверите алгоритм на всех возможных вариантах для конкретного объема памяти на вашей машине, алгоритм на машине с большим объемом памяти может вести себя по иному. Вот прямо специально его возьмут и запрограммируют так, что для входных данных объемом меньше N (причем N не влезет в вашу доступную память) сложность алгоритма будет такой, а для входных данных больше N - сложность будет другой, и далее меняться не будет. То есть как бы вы не замеряли алгоритм на своей машине, вы не получите правильный результат.
18 июн 19, 14:17    [21910674]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Interloper
На скольких наборах входных данных вы будете тестировать алгоритм?
А сколько у меня попыток для запуска?

Если у меня десять попыток, а входных данных может быть до миллиона, то сделаю по две попытки на 10, 100, 1000, 10000, 100000 и 1000000 элементов.
А потом посчитаю дельту между двумя запусками, о объявлю ее погрешностью

Если миллион попыток, а входных данных не больше 100, то можно по много раз перебрать все входные данные.


Ни на каком конечном наборе данных нельзя сделать вывод о сложности алгоритма. Что именно вам непонятно в этом утверждении?

Смотрите объяснение выше, в котором я объясняю что даже полным перебором вариантов на конкретном компьютере нельзя оценить сложность алгоритма.
18 июн 19, 14:20    [21910682]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9508
Interloper
Вот прямо специально его возьмут и запрограммируют так, что для входных данных объемом меньше N (причем N не влезет в вашу доступную память) сложность алгоритма будет такой, а для входных данных больше N - сложность будет другой
Вообще никак не бьётся с (выделено мною):
Interloper
Задача: анализировать алгоритмы, имеющие фиксированную сложность, но неизвестную нам, о которой мы можем лишь формулировать гипотезу.
18 июн 19, 14:34    [21910701]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
точно проверить гипотезу о сложности невозможно
Если есть алгоритм, исходник, в котором нет рандома, то возможно.

Для начала ищем места, которые могут зависнуть алгоритм. Если такие есть, то задача решена (ибо доказательство неконечности тоже результат).

Если алгоритм не зависает, то делаем простое аппроксимирование, ну или ассиптоту ищем в заданной погрешности.

Interloper
Ни на каком конечном наборе данных нельзя сделать вывод о сложности алгоритма. Что именно вам непонятно в этом утверждении?
Алгоритм, тем более конкретная программа не может быть определена на бесконечном объеме данных. А раз она определена только на конечном объеме данных, то достаточно искать примеры в этом объеме. Их может быть немало, но этот список все равно конечен.
Вопрос тот же: если алгоритм работает на N элементах T времени, то нужно будет не менее чем T*log(N)*log(N) запусков для грубой оценки, это в сферических условиях в вакууме. Наличие любого стремного фактора можно сразу умножать на десять. T можно определить, как можно и определить конечность алгоритма, имея его исходник на понятном языке (в данном случае математически идеальная машина Тьюринга является малопонятной). Еще встает вопрос о конечности самого исходника. Время, требуемое для анализа алгоритма будет также зависеть от размера исходника.

В общем, если все размеры определены, то потребуется что-то вроде A*B*C*D*E... = X времени для оценки.

Interloper
Смотрите объяснение выше, в котором я объясняю что даже полным перебором вариантов на конкретном компьютере нельзя оценить сложность алгоритма.

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

Нужно делить мух и котлет. Найдите условия конечности, а неконечные алгоритмы сразу в мусорку с пометкой "нерешаемо".
18 июн 19, 18:44    [21910941]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Basil A. Sidorov
Interloper
Вот прямо специально его возьмут и запрограммируют так, что для входных данных объемом меньше N (причем N не влезет в вашу доступную память) сложность алгоритма будет такой, а для входных данных больше N - сложность будет другой
Вообще никак не бьётся с (выделено мною):
Interloper
Задача: анализировать алгоритмы, имеющие фиксированную сложность, но неизвестную нам, о которой мы можем лишь формулировать гипотезу.


Вообще нет противоречия. Сложность не может быть фиксированной или нефиксированной, она одна. Это теоретический концепт, говорить о котором можно только с точки зрения асимптотики. Еще раз: сложность нельзя проверить на конечном числе входных данных, сколько бы данных вы не взяли.
18 июн 19, 19:07    [21910954]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Interloper
точно проверить гипотезу о сложности невозможно
Если есть алгоритм, исходник, в котором нет рандома, то возможно.

Для начала ищем места, которые могут зависнуть алгоритм. Если такие есть, то задача решена (ибо доказательство неконечности тоже результат).

Невозможно даже для агоритмов без рандома.
Места, в которых может зависнуть алгоритм, нельзя найти программно.
18 июн 19, 19:09    [21910959]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Алгоритм, тем более конкретная программа не может быть определена на бесконечном объеме данных. А раз она определена только на конечном объеме данных, то достаточно искать примеры в этом объеме. Их может быть немало, но этот список все равно конечен.

И сразу ошибка. Алгоритм может быть определен на неограниченном объеме данных. Алгоритм сортировки может сортировать массивы любой размерности, лишь бы они умещались в памяти.
18 июн 19, 19:11    [21910960]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Там идет жонглирование понятиями. Сначала утверждается что алгоритм конечен, а потом идет попытка выдать конечный алгоритм за бесконечно долгий. Не стоит этого делать.

Если вы что-то не поняли, не стоит сразу называть это жонглированием. Там не было речи о бесконечно долгом алгоритме.
18 июн 19, 19:12    [21910962]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Вопрос тот же: если алгоритм работает на N элементах T времени, то нужно будет не менее чем T*log(N)*log(N) запусков для грубой оценки, это в сферических условиях в вакууме. Наличие любого стремного фактора можно сразу умножать на десять. T можно определить, как можно и определить конечность алгоритма, имея его исходник на понятном языке (в данном случае математически идеальная машина Тьюринга является малопонятной). Еще встает вопрос о конечности самого исходника. Время, требуемое для анализа алгоритма будет также зависеть от размера исходника.

В общем, если все размеры определены, то потребуется что-то вроде A*B*C*D*E... = X времени для оценки.

1. Конечность алгоритма определить невозможно (см. неразрешимость проблемы останова)
2. Какое бы N не взять, можно проанализировать только сложность алгоритма на промежутке от 1 до N, но не сложность всего алгоритма, который определен для любого N.
18 июн 19, 19:15    [21910964]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Места, в которых может зависнуть алгоритм, нельзя найти программно.
Вы явно не знакомы с методиками тестирования и верификации =)


Interloper
И сразу ошибка. Алгоритм может быть определен на неограниченном объеме данных. Алгоритм сортировки может сортировать массивы любой размерности, лишь бы они умещались в памяти.
Объем памяти на реальном компьютере ограничен.


Interloper
1. Конечность алгоритма определить невозможно (см. неразрешимость проблемы останова)
С определенной вероятностью возможно.

Вопрос лишь в объеме ресурсов. Нельзя определить конечность алгоритма если объем ресурсов на определение меньше. чем объем ресурсов на использование этого алгоритма.
В некоторых других случаях можно (особенно имея исходник).


Interloper
2. Какое бы N не взять, можно проанализировать только сложность алгоритма на промежутке от 1 до N, но не сложность всего алгоритма, который определен для любого N.
Я правильно понимаю, что вы говорите, например при N=3 мы можем определить конечность алгоритма при N=1, N=2 и N=3, а для других целых 0 < N <= 3 определить не можете ?

Начните с утверждения, что алгоритм протестирован. и дальше либо подтвердите его, определив конечную сложность, либо опровергните.

Если же речь про сферические в вакууме алгоритмы, не используемые на практике, то задача должна звучать иначе.
18 июн 19, 19:37    [21910969]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
exp98
Member

Откуда:
Сообщений: 1848
Топик закончится только после того, как мы все дружно восхитимся ТээСовым "открытием".
18 июн 19, 20:01    [21910977]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
love_bach
Member

Откуда:
Сообщений: 560
зачем вообще это все. есть алгоритм, есть его оценка. что тут происходит? алгоритм раскраски? коммивояжера? нет? ну тогда зачем?
18 июн 19, 21:11    [21911021]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
love_bach
Member

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


фигня какая. это в самом алгоритме. чо там проверять
18 июн 19, 21:14    [21911022]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Объем памяти на реальном компьютере ограничен.

На конкретном - да. Но можно найти компьютер с большим объемом памяти, чем на том, на котором запускаем тесты.
18 июн 19, 21:18    [21911024]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Вопрос лишь в объеме ресурсов. Нельзя определить конечность алгоритма если объем ресурсов на определение меньше. чем объем ресурсов на использование этого алгоритма.
В некоторых других случаях можно (особенно имея исходник).

Если найдете способ как, сразу получите Нобелевку, не меньше.
В каких некоторых случаях? Для алгоритма суммы чисел? Тогда да.
Может имеет смысл сначала разобраться в вопросе вместо того, чтобы упрямо гнуть свою линию, ничем не подкрепляя?
18 июн 19, 21:21    [21911026]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
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 июн 19, 21:30    [21911029]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

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


фигня какая. это в самом алгоритме. чо там проверять


Если в алгоритме тысячи строк, "глазами" оценить сложность не получится.
18 июн 19, 21:32    [21911030]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
Interloper
Предположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения.
Как программно проверить, верно ли предположение о сложности?
зачем это проверять? особенно с учётом возможной переменной асимптотики.
Обычная практическая задача в CS: проверяют\доказывают конечность реализации алгоритма, т.е. лимит времени на конкретном железе на крайних условиях. А задача по доказательству асимптотики алгоритма лежит обычно на алгоритмистах\математиках.
19 июн 19, 00:14    [21911108]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
На конкретном - да. Но можно найти компьютер с большим объемом памяти, чем на том, на котором запускаем тесты.
Любое конечное большое число памяти всегда много меньше, чем бесконечное.
"много меньше" это значит, что даже если ты помножишь этот объем памяти сам на себя хоть тысячу раз подряд, все равно будет меньше.
Это школьный уровень алгебры и начал анализа.


Interloper
Может имеет смысл сначала разобраться в вопросе вместо того, чтобы упрямо гнуть свою линию, ничем не подкрепляя?
Вам тот же совет =)


Interloper
Но если запустить алгоритм на следующих N
В рамках задачи, где алгоритм определен для любого целого N <= 3 нельзя запускать этот алгоритм для любого N > 3.
Это другая задача, которую на практике не решают (точнее решают программисты-теоретики или программисты-верификаторы, а не то, чем мы здесь занимаемся).

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



Interloper
Если в алгоритме тысячи строк, "глазами" оценить сложность не получится.
Это значит алгоритм нечитаемый, а значит он неконечный может быть.
Исходим из условий читаемости алгоритма, его исходника.
19 июн 19, 00:43    [21911114]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1349
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 июн 19, 04:49    [21911133]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1349
Если нужно оценивать сложность произвольного алгоритма и полностью формальное доказательство не нужно, то я бы сделал анализатор выражений. Для начала тупо искал бы в AST циклы, потом добавил анализ использования переменных циклов, чтобы отслеживать такие ситуации:

for (int i = 0; i < 100; i+=2) { i--; }

Потом добавил анализ рекурсивных вызовов. И дальше по мере поступления новых алгоритмов усложнял анализ.

На выходе анализатора можно выдавать две вещи:
1) примерную оценку
2) какие-нибудь граничные значения переменных, которые использовал бы при запуске алгоритма, чтобы посчитать реальное время выполнения

Затем сравнивал бы оценку и то, что получается по результатам запуска. Если есть расхождения, то выдаём предупреждение. И такие алгоритмы оцениваем уже китайским методом: арендуем подвальчик с сотней китайцев. Они анализируют алгоритм и дорабатывают оцениватель. Хотя не обязательно подвальчик, можно запилить какой-нибудь сайт или мобильную игру "Оцени сложность алгоритма".


Кстати, есть безумная идея. Можно сделать алго-валюту (a la крипто-валюта). Только если в криптовалютах деньги даются тупо за вычисление хеша. То в алго-валюте деньги будут выдаваться за более эффективную реализацию алгоритмических задачек. Скажем один участник отправляет в p2p-сеть алгоритмическую задачку, минимальные требуемые критерии (например, максимальная сложность, объем памяти и т.п.) и какую-то сумму реальных денег. Другие участники отправляют свои реализации алгоритма. 1-ый чел, который отправил алгоритм, который удовлетворяет минимальным условиям, получает допустим 1/e или 1/pi от исходной суммы. 2-ой чел, который отправит алгоритм лучше 1-го получит 1/e от оставшейся суммы и т.д.
19 июн 19, 06:27    [21911142]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1349
Кстати, одним из обязательных требований к реализации алгоритма может быть наличие формального доказательства сложности. Если оно нужно, то чел донатит штуку баксов и люди потом сидят полгода доказывают. Или быстрее, если они гении математики.

Interloper, короче, всё, другого общего решения у этой задачки нет. Нужно делать алго-валюту, инфа 100%.
19 июн 19, 06:50    [21911144]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Любое конечное большое число памяти всегда много меньше, чем бесконечное.
"много меньше" это значит, что даже если ты помножишь этот объем памяти сам на себя хоть тысячу раз подряд, все равно будет меньше.

Конечное число памяти позволяет проверить алгоритм только на конечном наборе данных.
19 июн 19, 07:52    [21911166]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Но если запустить алгоритм на следующих N
В рамках задачи, где алгоритм определен для любого целого N <= 3 нельзя запускать этот алгоритм для любого N > 3.
[/quot]
В рамках задачи алгоритм определен для любого целого N. Это у вас есть памяти столько, что вы можете проверить алгоритм только для значений N<=3, что не даст правильно оценить сложность алгоритма.
19 июн 19, 07:54    [21911168]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Опять вернулись к тому, что вы ставите в условие конечность алгоритма, а потом требуете определить его работоспособность за пределами условий.


Вы путаете конечность алгоритма в смысле того, что он заканчивается за конечное число шагов, и конечность множества допустимых входных данных. Алгоритм "сумма двух чисел" конечен, но на вход ему могут быть поданы сколь угодно большие числа и их бесконечно много.

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

Если вы не понимаете теорию, это не делает ее неверной и несвязной. Что касается общих случаев: я указал в постановке задачи, что интерес представляет общий случай, универсальный алгоритм.
19 июн 19, 08:01    [21911173]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Конечное число памяти позволяет проверить алгоритм только на конечном наборе данных.

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


Interloper
В рамках задачи алгоритм определен для любого целого N. Это у вас есть памяти столько, что вы можете проверить алгоритм только для значений N<=3, что не даст правильно оценить сложность алгоритма.
Тот же ответ: если памяти не хватает, то _НЕЛЬЗЯ_ определять. Можно переформулировать условия задачи для N <= 3, тогда можно. А иначе нельзя. Это уже другая задача.

Тут вопрос простой, я выше писал. МОжно ли запустить алгоритм с массивом N > 3 на компьютере с памятью N <= 3 и при этом алгоритм не упадет? Ответ: не выйдет, алгоритм упадет (будет читать ошибочные данные и т.п.), то есть алгоритм неработоспособный. А значит мы простыми методами доказали на практике неработоспособность алгоритма, задача решена. Алгоритм отправляется разработчикам для правок (чтобы на компьютере с памятью N <= 3 можно было загружать данные N > 3). А пока этого не сделано, у нас готовый ответ: алгоритм не работает.

Зачем определять сложность неработающего алгоритма я не понимаю.


Interloper
Вы путаете конечность алгоритма в смысле того, что он заканчивается за конечное число шагов, и конечность множества допустимых входных данных. Алгоритм "сумма двух чисел" конечен, но на вход ему могут быть поданы сколь угодно большие числа и их бесконечно много.

В линуксе есть генератор случайных чисел, чтение из которого никогда не заканчивается. Сделаем проще. Запустим алгоритм читать из этого генератора число размером больше, чем оперативная память. А когда алгоритм упадет по причине нехватки памяти объявим, что алгоритм неработоспособный и оценка его сложности невозможна. Задача решена.



Мысль по-прежнему кристально чиста:
1) определить, что алгоритм конечен на данном компьютере для всех допустимых входных комбинаций (это вопрос к верификации). если это по каким-либо причинам, вне зависимости от причин, не может быть реализовано, то принимаем сложность равную "минус один", что идентично "алгоритм завис или упал".
2) определить асимптоту и погрешность. если погрешность относительно мала, то ответ найден. Если велика, то принимаем сложность алгоритма как "минус два", что идентично "сложность алгоритма случайна".
19 июн 19, 12:22    [21911404]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
А если задача стоит определить сложность не запуская алгоритм на компьютере, то это совсем иные методы.

Но начинать все равно придется с определения конечности.
19 июн 19, 12:23    [21911407]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Зачем определять сложность неработающего алгоритма я не понимаю.


Алгоритм работает. Но на вашем конкретном компьютере он имеет предельно допустимый набор возможных входных данных. На другом компьютере будет другой. Оценивая алгоритм только на своем компьютере, вы не сможете сделать вывод о его асимптотическом поведении, так как для этого нужно знать, как алгоритм ведет себя при неограниченном увеличении N.
19 июн 19, 13:32    [21911502]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Но начинать все равно придется с определения конечности.

Что вы понимаете под конечностью?
19 июн 19, 13:32    [21911503]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48659
Interloper
Оценивая алгоритм только на своем компьютере, вы не сможете сделать вывод о его асимптотическом поведении

Сможем. Это называется "экстраполяция" и является результатом решения задачи аппроксимации набора значений некоторой функцией.

Поэтому возвращаемся к первому ответу: получаем столько пар (N,t) сколько не надоест, строим по ним график из точек, аппроксимируем их разными функциями, смотрим в какую функцию он укладывается лучше всего. Эту функцию и объявляем сложностью данного алгоритма.
19 июн 19, 14:02    [21911541]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Dimitry Sibiryakov,

Существуют алгоритмы, для которых такой способ будет давать неверное решение. Пример приводил выше. Так можно и рандомно выбирать сложность и объявлять ее ответом. Точное решение либо есть, либо его нет. Для данной задачи - нет и в принципе быть не может.
19 июн 19, 15:39    [21911634]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48659
Interloper
Для данной задачи - нет и в принципе быть не может.

Как скажете, сэр.
19 июн 19, 16:26    [21911685]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Алгоритм работает.
Это не доказано.


Interloper
Оценивая алгоритм только на своем компьютере, вы не сможете сделать вывод о его асимптотическом поведении

А вы не сможете оценить его на всех компьютерах планеты, а значит, даже имея линейны алгоритм, состоящий из одного цикла, вы не можете говорить с вероятностью даже близкой к 50%, что у него сложность линейная, ведь это не так.

Другими словами, в вашем "общем случае, мы действительно не можем определить сложность нерабоющего алгоритма хотя бы потому, что он не работает".


Interloper
Aklin
Но начинать все равно придется с определения конечности.

Что вы понимаете под конечностью?

Конечный объем входных данных на конечном ограниченном числе машин с конечным ограниченным числом параметров, и при этом на этих условиях алгоритм работает конечное время, не превышающее заданное.

Если это не так, то алгоритм нуждается в доработке.


Dimitry Sibiryakov
Поэтому возвращаемся к первому ответу: получаем столько пар (N,t) сколько не надоест, строим по ним график из точек, аппроксимируем их разными функциями, смотрим в какую функцию он укладывается лучше всего. Эту функцию и объявляем сложностью данного алгоритма.
Если верить ТС, не выйдет, потому что нужно построить график для таких N, которые ни один компьютер в мире запустить не сможет.
Interloper
Точное решение либо есть, либо его нет. Для данной задачи - нет и в принципе быть не может.
Для неточной задачи не может быть точного решения.
19 июн 19, 19:01    [21911815]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48659
Aklin
Если верить ТС, не выйдет, потому что нужно построить график для таких N, которые ни один компьютер в мире запустить не сможет.

Да, да, я уже понял, что слова "аппроксимация" и "экстраполяция" для него пустое сотрясение воздуха, недостойное открытия гугля.
19 июн 19, 19:25    [21911822]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Dimitry Sibiryakov,

Постановка задачи требует точного ответа, аппроксимация здесь неуместна. Аппроксимировать можно, что угодно, но задача не звучит как "аппроксимируйте сложность алгоритма".
20 июн 19, 07:56    [21911976]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Конечный объем входных данных на конечном ограниченном числе машин с конечным ограниченным числом параметров, и при этом на этих условиях алгоритм работает конечное время, не превышающее заданное.

Конечность алгоритма никак не связана с выходными данными и машинами.
Алгоритм сортировки - конечен. Работает с массивами сколь угодно большой длины.
20 июн 19, 07:59    [21911977]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Другими словами, в вашем "общем случае, мы действительно не можем определить сложность нерабоющего алгоритма хотя бы потому, что он не работает".

В общем случае мы не можем определить сложность рабочего алгоритма, потому что эта задача эквивалентна алгоритмически неразрешимой задаче определении того, закончит ли произвольный алгоритм работу за конечное число шагов. Если вы не верите, что такая задача неразрешима, теория алгоритмов в помощь.
20 июн 19, 08:02    [21911978]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1349
Завершаемость определить проще. Для функциональных языков, где единственный источник незавершаемости - это рекурсия, это делается так.

1) Для всех аргументов определена мера. Для числовых аргументов - это обычно просто значение числа. Для строковых - это может быть длина строки или ещё что-то. Для алгебраических типов данных - это обычно количество конструкторов в выражении. Например для "Cons 4 (Cons 2 Nil)" размер может быть равен 3. Аналогично вычисляется размер деревьев (количество узлов) и т.п.

Для таких простых типов мера обычно определяется автоматически. Для более сложных её приходится определять вручную. Например, мне здесь пришлось определить такую меру:

primrec size_type :: "'a type => nat" where
  "size_type OclSuper = 0"
| "size_type (Required t) = 0"
| "size_type (Optional t) = 0"
| "size_type (Collection t) = Suc (size_type t)"
| "size_type (Set t) = Suc (size_type t)"
| "size_type (OrderedSet t) = Suc (size_type t)"
| "size_type (Bag t) = Suc (size_type t)"
| "size_type (Sequence t) = Suc (size_type t)"
| "size_type (Tuple t) = Suc (ffold tcf 0 (fset_of_fmap (fmmap size_type t)))"


2) По умолчанию тот же Isabelle HOL пытается найти аргумент или комбинацию аргументов функции, которые с каждым шагом рекурсии уменьшаются. Обычно этого достаточно.

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

termination
  by (relation "measure (&#955;(xs, ys). size ys)";
      auto simp add: elem_le_ffold' fmran'I)


А здесь (раздел 4.1) есть хороший пример почему автоматическое доказательство завершаемости может не работать:

function sum :: "nat => nat => nat" where
"sum i N = (if i > N then 0 else i + sum (Suc i) N)"


Эта функция вычисляет сумму 1+2+...+N

Аргумент i с каждым шагом увеличивается на 1, а аргумент N остается неизменным. Поэтому они определяют меру N - i, которая с каждым шагом уменьшается. И ещё добавляют 1, видимо потому, что на последнем вызове рекурсии i > N. При этом N - i будет всё-равно 0, потому что это натуральные числа, а не целые. И если не добавить 1, то на двух последних шагах мера будет 0 - оставаться неизменной, а должна уменьшаться.

termination sum
apply (relation "measure (&#955;(i,N). N + 1 - i)")
apply auto
done




Для императивных языков доказательство завершаемости должно быть сложнее, потому что там есть переменные, значения которых могут изменяться не только при рекурсивных вызовах, но просто по ходу выполнения алгоритма. Но общая идея там должна быть такая же:

1) Определяем источники незавершаемости. Тут кроме рекурсивных вызовов это могут быть циклы и функции из стандартной библиотеки! Кстати функции из стандартной библиотеки могут ещё и влиять на сложность алгоритма: поиск в массиве, в хеше и т.п.

2) Определяем простые правила для определения завершаемости (например, один из аргументов или их комбинация всегда уменьшаются или, например, переменная цикла только уменьшается/увеличивается пока не доходит до конечного значения).

3) Для сложных ситуаций всё-равно пользователю придется определять кастомную меру. Кстати, эта мера может быть обязательной частью алгоритма. Чел, который написал алгоритм, пусть прикладывает и меру.

4) Самая жесть - это интегрировать всё это с какой-нибудь системой автоматического доказательства теорем. Обычно это сводится к тому, что нужно реализовать этот язык программирования (на котором пишутся алгоритмы) в Isabelle HOL или ещё какой-то системе. Для Isabelle HOL есть какая-то реализация Java, какие-то примеры простых абстрактных императивных языков. Я, например, реализовывал язык OCL. Причём, там только абстрактный синтаксис, система типов, правила типизации выражений, без семантики. Для того же C# или другого языка нужно либо искать готовую реализацию, либо это тема для докторской диссертации на несколько лет.



Короче, сделать всё полностью формально очень сложно. Если это требуется, то проще всего, чтобы люди, которые пишут алгоритмы, писали их сразу на нормальном языке типа Isabelle HOL, который поддерживает автоматизированные доказательства теорем. При этом сами и доказывали бы завершаемость, сложность и т.п. Либо можно использовать языки, которые легко интегрируются с такими системами. Для Scala вроде было что-то такое.

Если формальное доказательство не нужно. А просто запускать алгоритм много раз - это слишком тупо. То нужны какие-то эвристики. Например, парсим функцию, получаем её абстрактное синтаксическое дерево (во многих языках это поддерживается). И анализируем циклы, рекурсивные вызовы и т.п. Затем подтверждаем полученную оценку запуском алгоритма на разных входных данных. С практической точки зрения это самое простое и реальное, что можно сделать. На мой взгляд такая штука была бы очень прикольной и востребованной. Например, есть PVS Studio, которая не может формально доказать корректность программы, но в ней заложено много эвристик, которые находят типовые ошибки. С практической точки зрения это уже не плохо. Аналогично и ваша штука могла бы примерно оценивать сложность алгоритмов.
20 июн 19, 10:04    [21912029]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
Ares_ekb,

попробуй ради интереса доказать так O(N) для алгоритма составления бинарной кучи
20 июн 19, 10:30    [21912045]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Постановка задачи требует точного ответа
Нельзя сделать точный ответ в неточных условиях.


Interloper
Конечность алгоритма никак не связана с выходными данными и машинами.
Алгоритм сортировки - конечен. Работает с массивами сколь угодно большой длины.

Пока нет гарантий что алгоритм вообще работает и выдает верный ответ - оценивать его бесполезно.


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

Ты снова пытаешься получить ТОЧНЫЙ Ответ на задачу без условия.
Так не выйдет.
Сделай условие. Сделай границы работы. И тестируй.
Если же вопрос про ТЕОРЕТИЧЕСКУЮ сложность - это вопрос анализа структуры кода, не более чем. Объем данных тут роли не играет. Это сугубо теоретическая оценка, не привязанная ни к чему. Для этой оценки не нужно запускать этот алгоритм даже один раз.
20 июн 19, 12:10    [21912122]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
exp98
Member

Откуда:
Сообщений: 1848
Aklin
Зачем определять сложность неработающего алгоритма я не понимаю
Затем, что это сферический алгоритм, да ещё и в ваккууме. Такова идэ фикс ТСа. Причём, в задаче нет ни теоретического, ни практического значения. Таких вы ни в чём не убедите, поздравьте с открытием, и прения прекратятся. Лично я поздравляю!

З.Ы. Может кто недопонимает неразрешимость массовой алг-й пр-мы. Это не возможность решить задачу в принципе, а невозможность составить один такой алгоритм для всех частных случаев.
Я не уверен, что ТС сам это до конца понимает.
20 июн 19, 13:08    [21912176]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48659
Interloper
Постановка задачи требует точного ответа

Не может быть у этой задачи точного ответа, поскольку так называемая "сложность алгоритма" - не точная величина, а всего лишь грубая оценка. Она не может быть применена для вычисления времени работы алгоритма на заданном объёме данных.
20 июн 19, 13:52    [21912221]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
exp98
Затем, что это сферический алгоритм, да ещё и в ваккууме. Такова идэ фикс ТСа. Причём, в задаче нет ни теоретического, ни практического значения.
Я так понял, что ТС хочет определить некую сложность для сферического в вакууме и нигде не описанного алгоритма в общем виде. Алгоритм-то в общем виде, а вот сложность должна быть точной величиной.

Забавно в общем.

А чем дальше тем веселее: раз для ряда алгоритмов сложность нельзя определить потому что алгоритмы не могут завершиться, то значит это правило ТС растягивает на все алгоритмы без исключения, делая заранее придуманный им вывод, со ссылками на несвязанные статьи.
20 июн 19, 14:19    [21912245]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Dimitry Sibiryakov
Interloper
Постановка задачи требует точного ответа

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

Да эта теоретическая оценка может очень сильно отличаться.
И мы даже не сможем придумать никакой поправочный коэффициент. Поскольку тут дело будет даже не в коэффициенте.
Вобщем простая многослойная нейронная сеть автору в помощь и наверное удастся экспериментально подобрать кривую
похожую на фактический отклик алгоритма.
20 июн 19, 14:35    [21912264]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
exp98
Затем, что это сферический алгоритм, да ещё и в ваккууме. Такова идэ фикс ТСа. Причём, в задаче нет ни теоретического, ни практического значения.
Я так понял, что ТС хочет определить некую сложность для сферического в вакууме и нигде не описанного алгоритма в общем виде. Алгоритм-то в общем виде, а вот сложность должна быть точной величиной.

Забавно в общем.

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


Сложность должна быть не точной величиной, а указанием на один из классов сложности. Но в целом вы почти меня поняли: так как не существует универсального алгоритма для определения факта остановки любого алгоритма, то и не существует универсального алгоритма для проверки сложности, иначе этот алгоритм может быть преобразован в алгоритм определения факта остановки.
20 июн 19, 18:30    [21912442]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Ares_ekb,

Интересно, изучу ваши выкладки на досуге, спасибо.
20 июн 19, 18:33    [21912443]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Сложность должна быть не точной величиной, а указанием на один из классов сложности.


Interloper
так как не существует универсального алгоритма для определения факта остановки любого алгоритма

Не существует алгоритма для оценки неработающего алгоритма в виде черного ящика.

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


Interloper
Сложность должна быть не точной величиной, а указанием на один из классов сложности.
Это сугубо теоретический вопрос тогда, а не вопрос программирования.
20 июн 19, 18:39    [21912446]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
exp98
Member

Откуда:
Сообщений: 1848
А ещё я тугодум и так и не понял
автор
...алгоритма для проверки сложности, иначе этот алгоритм может быть преобразован в алгоритм определения факта остановки
Для нас доказали теорему о неразрешимости массовой проблемы останова.
Проверка сложности является частным случаем алгоритма проверки останова. Для этого ч-го случая мне лично не приходилось видеть признанных доказательств неразр-ти.
Кроме того,не приходилось видеть и док-в того, что если неразрешима массовая проблема, то неразр-ма и частная проблема.

Тем не менее нам здесь пытались втюхать, что она верна по причине того, что является ч-м случ-м алгоритма проверки останова и потому верна. Т.о., налицо неправомерное применение "доказательства от противного", т.е. весьма противное доказательство. И прежде всего я протестовал против этого, поскольку все другие рассуждения были достаточно очевидны.
20 июн 19, 20:09    [21912483]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Не существует алгоритма для оценки неработающего алгоритма в виде черного ящика.

Слова "неработающего" и "в виде черного ящика" уберите, а так все верно. С чего вы выдумали, что речь идет о неработающих алгоритмах - ума не приложу.
Что касается вида, то он может быть любой, хоть исходный код. Не исходный код какого-то одного конкретного алгоритма: алгоритм оценки должен принимать на вход исходный код любого алгоритма. Для частного случая в виде подмножества алгоритмов, решение, безусловно существует.
20 июн 19, 21:04    [21912495]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
Aklin
Это сугубо теоретический вопрос тогда, а не вопрос программирования.

Это вопрос теории алгоритмов, естественно, а не того программирования, которым вы занимаетесь в офисе.
20 июн 19, 21:05    [21912496]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 523
exp98
Для этого ч-го случая мне лично не приходилось видеть признанных доказательств неразр-ти.
.

Доказательство приведено в этой теме на 2й странице. Оно достаточно простое, чтобы в нем мог разобраться любой, кто знает основные понятия математической логики.
20 июн 19, 21:06    [21912497]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1349
kealon(Ruslan)
попробуй ради интереса доказать так O(N) для алгоритма составления бинарной кучи

Чтобы доказать формально нужно время. Интересная идея, я попробую, если будет возможность. Но на это уйдет наверное неделя-две, потому что я никогда таким не занимался.

А с помощью эвристик это можно сделать так:

Алгоритм выглядит следующим образом (по ссылке ещё есть ссылка на прикольную книгу, где всё описано более подробно "Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ"):
Build_Heap(A)
  A.heap_size = A.length
  for i = floor(A.length/2) downto 1
    do Heapify(A, i)
где A - это входной массив, который нужно превратить в кучу
A.length - его длина (которая равна длине кучи A.heap_size и для простоты мы эту длину будем иногда обозначать просто N)
Heapify - это функция, которая упорядочивает элементы в поддереве кучи:
Heapify(A, i)
  left = 2i
  right = 2i+1
  largest = i
  if left <= A.heap_size и A[left] > A[largest]
    then largest = left
  if right <= A.heap_size и A[right] > A[largest]
    then largest = right
  if largest != i
    then Обменять A[i] и A[largest]
         Heapify(A, largest)


Допустим этот алгоритм написан на каком-то реальном ЯП, а не псевдоязыке. Мы распарсили его и получили абстрактное синтаксическое дерево (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. Попробую пояснить почему так.

Например есть цикл:
for (int x = i; x < N; x += step) { ... }
Для него сложность будет O((N-i)/step). Если i=0 и step = 1, то это вырождается просто в O(N).

Для такого цикла:
for (int x = i; x < N; x *= step) { ... }
Сложность будет 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 июн 19, 22:57    [21912528]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1349
Идея всего этого такая... В книге приводится какое-то очень не тривиальное доказательство сложности O(N). Там делается утверждение
Поскольку число вершин высоты h в куче из n элементов не превышает ceil(n / 2^(h+1)), а высота всей кучи не превышает floor(lg n), то время работы не превышает
и дальше приводится какая-то безумная формула.

Автоматизировать такие рассуждения невозможно. А ту последовательность действий, которую я привёл выше, вполне можно автоматизировать.
20 июн 19, 23:10    [21912534]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1349
Насчет формальных доказательств. Нашёл очень клёвую реализацию некоторого абстрактного императивного языка IMP2 для Isabelle HOL. В нём есть переменные, циклы, условия и т.п. Ещё можно задавать разные инварианты для императивных программ, которые можно доказывать. И ещё для этого языка буквально неделю назад запилили реализацию двоичной кучи как-раз по книге Кормена Т. и др. "Алгоритмы: построение и анализ". Там доказывается корректность этой реализации.

Причём реализация двоичной кучи занимает по идее 1 страницу, а доказательств там больше чем на 20 страниц. И это даже без доказательства сложности алгоритма. Это показывает на сколько всё сложно с формальными методами. На практике для произвольных алгоритмов реально использовать только какие-то эвристики, которые описывал выше.
21 июн 19, 08:38    [21912604]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
Ares_ekb,

да, в математическом доказательстве используется сходящаяся геометрическая прогрессия - тынц
И это очень простой пример, без подкавык.
По многим алгоритмам используется оптимистичная оценка, например: хэш-таблица, декартово дерево

Судя по всему, даже со специализированным языком "с подсказками" и частично работающее, в общем виде реально тянет на RocketScience
21 июн 19, 09:38    [21912658]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
Ares_ekb
Насчет формальных доказательств. Нашёл очень клёвую реализацию некоторого абстрактного императивного языка IMP2 для Isabelle HOL. В нём есть переменные, циклы, условия и т.п. Ещё можно задавать разные инварианты для императивных программ, которые можно доказывать. И ещё для этого языка буквально неделю назад запилили реализацию двоичной кучи как-раз по книге Кормена Т. и др. "Алгоритмы: построение и анализ". Там доказывается корректность этой реализации.

Причём реализация двоичной кучи занимает по идее 1 страницу, а доказательств там больше чем на 20 страниц. И это даже без доказательства сложности алгоритма. Это показывает на сколько всё сложно с формальными методами. На практике для произвольных алгоритмов реально использовать только какие-то эвристики, которые описывал выше.
я так подозреваю, что если ты не НАСА, то платить программистам за такую разработку явно перебор :-)
21 июн 19, 09:42    [21912660]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Aklin

Слова "неработающего" и "в виде черного ящика" уберите, а так все верно. С чего вы выдумали, что речь идет о неработающих алгоритмах - ума не приложу.
Что касается вида, то он может быть любой, хоть исходный код. Не исходный код какого-то одного конкретного алгоритма: алгоритм оценки должен принимать на вход исходный код любого алгоритма. Для частного случая в виде подмножества алгоритмов, решение, безусловно существует.
С того, что его разработчик не может гарантировать конечность времени исполнения этого алгоритма на допустимых входных данных.
21 июн 19, 12:02    [21912822]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Interloper
Aklin
Это сугубо теоретический вопрос тогда, а не вопрос программирования.

Это вопрос теории алгоритмов, естественно, а не того программирования, которым вы занимаетесь в офисе.
Тогда речь не может идти о том, что на компьютере не хватит памяти, или вообще о количестве запусков.
21 июн 19, 12:03    [21912823]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48659
Interloper
Сложность должна быть не точной величиной, а указанием на один из классов сложности.

Тогда вспоминай матан (если, конечно, для тебя это слово не матерное). Степенная функция отличается от линейной и логарифмической. Причём для их различения достаточно трёх точек.
21 июн 19, 13:36    [21912926]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59177
Dimitry Sibiryakov
Причём для их различения достаточно трёх точек.
В указанных ТС пределах делать замеры нельзя, ибо функция может потенциально зависнуть.

А если она "может" то зависнет.
А если зависнет, то встает вопрос об алгоритмически невозможном определении конечности этого алгоритма, а это известная доказанная проблема, поэтому даже пытаться не стоит =)

А доказывать математически он не хочет.
21 июн 19, 13:46    [21912932]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1349
kealon(Ruslan)
да, в математическом доказательстве используется сходящаяся геометрическая прогрессия - тынц

И это очень простой пример, без подкавык.
Проблема таких доказательств как по ссылке в том, что их невозможно автоматизировать. Там очень много рассуждений, каких-то посылок, которые берутся просто из головы автора и никак не следуют из структуры алгоритма. Например, откуда взялась эта лемма "Пусть для какого-то элемента массива при вызове siftdown было сделано i вызовов оператора swap. Тогда его индекс не превосходил floor(n/2^i)"? Ни один инструмент точно не сможет сформулировать и доказать такую лемму из ниоткуда.

Чтобы можно было оценивать сложность автоматически, нужно свести эту процедуру к каким-то очень простым шагам. Пусть этих шагов будет очень много, пусть там будет много тупого перебора, но зато это можно автоматизировать.

Насчет подкавык. Вполне возможно, что для человека какое-то доказательство будет сложным, а для тупого машинного перебора - простым. Или наоборот.

kealon(Ruslan)
Судя по всему, даже со специализированным языком "с подсказками" и частично работающее, в общем виде реально тянет на RocketScience
Если полностью формальное доказательство, то да. А если какие-то полуформализованные эвристики по анализу кода, как я описывал, то вполне реально сделать. Хотя даже это вполне потянуло бы на диссертацию :)
21 июн 19, 15:16    [21913055]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
vas0
Member

Откуда: Таможенный союз (Россия, Казахстан)
Сообщений: 1289
Если взять просто быструю сортировку Хоара (QuickSort). Сложность в худшем n^2. Сложность в среднем n*log, да и то сложность в среднем оценивается лишь вероятностно.

Доказательство сложности в среднем даже зная алгоритм непростая задача. А для черного ящика видимо и вообще мрак. Если "опорный элемент" для хоара будет случайно выбираться, уже с оценкой будешь иметь проблему: иногда n*log, а иногда n^2.

Оценка по сложности это скорее подсказка, чтобы не попасть с проклятием размерности, а не точная величина.
23 июн 19, 04:19    [21913491]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2653
Interloper
mayton
пропущено...

Твои уточняющие вопросы напоминают легкий троллинг отвечающих.
Тебе уже в первом ответе дали методику.

Ты ее применил? Ты нарисовал график в Excel?

Давай дружище сделай как советуют опытные. А потом подойдешь к теории снова.


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

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


Программно проверить? Напишите программу, если хотите программно проверить. Одним из параметров будет функция подозрительная на асимптотику, проведите ряд экспериментов по n, постройте отношение затраченного времени черного ящика и ф. подозрительной на асимптотику, если функция та самая, то в пределе получите константу. Что там как вы говорите алгоритмически неразрешимого? Вам по-моему о чем-то подобном говорили
11 июл 19, 21:27    [21925259]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5      [все]
Все форумы / Программирование Ответить