Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835160 Fri, 24 Jul 2020 22:20:40 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835160 Цитата scrum0fscrums @ 24.07.20, 21:10

Линейное программирование решается линейно.

Квадратичное программирование решается квадратично.
Выпуклое программирование - выпукло.
Динамическое - динамично.
Математическое программирование - математично.
Но вот нелинейное программирование, как ты его ни крути, нелинейно.
Вот такая вот загогулина :D]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835143 Fri, 24 Jul 2020 21:10:10 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835143 scrum0fscrums Алгоритмы https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835120 Fri, 24 Jul 2020 17:02:32 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835120 Цитата scrum0fscrums @ 24.07.20, 13:27

AVA12
Линейное программирование решается за линейное время. Так что порядок. Чёрт его знает, может и утка. Архив не больно авторитетный ресурс.

Методы ЛП, например, симплекс-метод в худшем случае экспоненциальны. Что неудивительно - чем универсальнее метод, тем он более трудоёмкий.
Задача ЛП принадлежит классу P.

Добавлено 24.07.20, 17:10

Цитата

However this LP will only have polynomial size if the algorithm terminates
in polynomial time.

Вот, собственно, и всё :)
Если я правильно поняла, то каким-то образом автоматизировали написание программ, использующих методы ЛП.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835118 Fri, 24 Jul 2020 15:55:48 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835118 Цитата

Это у них лемма. Далее доказывается линейность.

Это не лемма, это часть аннотации. В которой нет ни слова о линейном размере итогового алгоритма. Если эта самая линейность где-то хотя бы упоминается - приведите цитату.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835115 Fri, 24 Jul 2020 15:38:57 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835115 Цитата AVA12 @ 24.07.20, 14:06

Где утка?

Утка в том, что может и ошибка закралась. Что-то уж больно неправдоподобно. Тысячу раз уже и теорему Ферма доказывали и то, что P=NP и то, что P≠NP. И всё с ошибками как позже выяснялось.

Добавлено 24.07.20, 15:40

Цитата AVA12 @ 24.07.20, 13:06

If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size"

Это у них лемма. Далее доказывается линейность. Надо от начала до конца статью читать. Две статьи.]]> scrum0fscrums Алгоритмы https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835113 Fri, 24 Jul 2020 14:06:00 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835113 Цитата

Линейное программирование решается за линейное время. Так что порядок.

Переведите, пожалуйста, на русский язык ту английскую цитату, что я привел.

Цитата

Чёрт его знает, может и утка.

Где утка? Откуда взялось утверждение "если для задачи есть полиномиальный алгоритм, то есть и линейный алгоритм"? Где и когда оно было опубликовано? Если у вас лично какие-то особенные нетрадиционные способы чтения и понимания написанного - это ваши личные проблемы, не надо обвинять других.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835112 Fri, 24 Jul 2020 13:27:25 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835112 AVA12
Линейное программирование решается за линейное время. Так что порядок. Чёрт его знает, может и утка. Архив не больно авторитетный ресурс.]]> scrum0fscrums Алгоритмы https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835109 Fri, 24 Jul 2020 13:06:43 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835109 линейное программирование" и "линейное время/память" (а также "полином" и "полиноминальное время/память"). Плюс, как водится, кто-то не читает документы, на которые ссылается, в частности, в упор не видит фразу "If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size". В общем, революция отменяется.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835102 Fri, 24 Jul 2020 11:35:04 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835102 scrum0fscrums, это какой-то вопрос, или что?
]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835076 Fri, 24 Jul 2020 08:21:07 +0000 Линейный алгоритм есть почти для любой задачи https://forum.sources.ru/index.php?showtopic=419230&view=findpost&p=3835076 https://arxiv.org/pdf/2005.05764.pdf
А тут программная реализация преобразователя программы из полиномиальной формы в линейную
https://arxiv.org/pdf/2005.02853.pdf]]> scrum0fscrums Алгоритмы