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

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

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


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

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


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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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


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

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


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

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

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

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


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

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

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

Откуда: Прямо сейчас меня здесь нет
Сообщений: 58146
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

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


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

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

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

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

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

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

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

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

Откуда: Москва
Сообщений: 488
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

Откуда: Прямо сейчас меня здесь нет
Сообщений: 58146
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

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

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

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


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

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

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

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

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

Откуда: Москва
Сообщений: 488
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

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


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


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

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

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


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


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

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



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

Откуда: Екатеринбург
Сообщений: 1300
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]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3] 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить