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

Откуда: Екатеринбург
Сообщений: 1300
Если нужно оценивать сложность произвольного алгоритма и полностью формальное доказательство не нужно, то я бы сделал анализатор выражений. Для начала тупо искал бы в 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

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

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

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

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

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

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


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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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


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

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

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


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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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