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

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


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

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

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

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

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


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

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

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

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


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

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

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

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

Откуда: Москва
Сообщений: 488
Действительно, пусть существует проверяющий алгоритм 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

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

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

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


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


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

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

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

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


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

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

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



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

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

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

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

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

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

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

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


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

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

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

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


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

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

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

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

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

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


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

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

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




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


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

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

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

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

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


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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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


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

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

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


Мы не можем вычислить заранее, что алгоритм неконечный. Это фундаментальное ограничение.
18 июн 19, 13:40    [21910618]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить