На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Закрыто Akina 26-07-2020: Достаточно. Нет реализации - нет предмета для разговора.
  
> Линейный алгоритм есть почти для любой задачи , Настоящая революция в программировании
    Доказали, что если для задачи есть полиномиальный алгоритм, то есть и линейный алгоритм.
    https://arxiv.org/pdf/2005.05764.pdf
    А тут программная реализация преобразователя программы из полиномиальной формы в линейную
    https://arxiv.org/pdf/2005.02853.pdf
      scrum0fscrums, это какой-то вопрос, или что?
        Это тупняк. Кто-то путает понятия "линейное программирование" и "линейное время/память" (а также "полином" и "полиноминальное время/память"). Плюс, как водится, кто-то не читает документы, на которые ссылается, в частности, в упор не видит фразу "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
          Линейное программирование решается за линейное время. Так что порядок. Чёрт его знает, может и утка. Архив не больно авторитетный ресурс.
            Цитата
            Линейное программирование решается за линейное время. Так что порядок.

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

            Где утка? Откуда взялось утверждение "если для задачи есть полиномиальный алгоритм, то есть и линейный алгоритм"? Где и когда оно было опубликовано? Если у вас лично какие-то особенные нетрадиционные способы чтения и понимания написанного - это ваши личные проблемы, не надо обвинять других.
              Цитата AVA12 @
              Где утка?

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

              Добавлено
              Цитата AVA12 @
              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 -
                Цитата
                Это у них лемма. Далее доказывается линейность.

                Это не лемма, это часть аннотации. В которой нет ни слова о линейном размере итогового алгоритма. Если эта самая линейность где-то хотя бы упоминается - приведите цитату.
                  Цитата scrum0fscrums @
                  AVA12
                  Линейное программирование решается за линейное время. Так что порядок. Чёрт его знает, может и утка. Архив не больно авторитетный ресурс.

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

                  Добавлено
                  Цитата
                  However this LP will only have polynomial size if the algorithm terminates
                  in polynomial time.

                  Вот, собственно, и всё :)
                  Если я правильно поняла, то каким-то образом автоматизировали написание программ, использующих методы ЛП.
                    Любой полиномиальный алгоритм выразили через линейное программирование полиномиального размера. Линейное программирование решается линейно. Полиномиальный размер не отменяет линейность.
                      Цитата scrum0fscrums @
                      Линейное программирование решается линейно.

                      Квадратичное программирование решается квадратично.
                      Выпуклое программирование - выпукло.
                      Динамическое - динамично.
                      Математическое программирование - математично.
                      Но вот нелинейное программирование, как ты его ни крути, нелинейно.
                      Вот такая вот загогулина :D
                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                      0 пользователей:
                      Закрыто Akina 26-07-2020: Достаточно. Нет реализации - нет предмета для разговора.


                      Рейтинг@Mail.ru
                      [ Script execution time: 0,0330 ]   [ 16 queries used ]   [ Generated: 29.03.24, 06:44 GMT ]