![]() Форум мехмата МГУ по высшей математике
| Пользователям: | Аксиома — это истина, на которую не хватило доказательств. |
Форумы > Математика > Высшая математика > Тема > Страница 2 |
Объявления | Последний пост | |
---|---|---|
![]() | Правила и принципы форума «Высшая математика» | 28.10.2009 15:17 |
![]() | Открыта свободная публикация вакансий для математиков | 26.09.2019 16:34 |
![]() | Книги по математике и экономике в добрые руки! | 10.08.2023 09:45 |
06.07.2005 02:41 Дата регистрации: 20 лет назад Посты: 14 | Swine-Heart algorithm's code Спасибо большое Saha !!! За вашу отзывчивость и желание помочь. Поверьте ваши усилия не пройдут даром - ваш Swine-Heart algorithm's code будет детально рассмотрен и изучен, надеюсь наше сотрудничество на ниве знаний и во имя знаний - будет продолжаться. С уважнием Bagira. |
06.07.2005 03:00 Дата регистрации: 20 лет назад Посты: 14 | Приглашение к участию обсуждения Swine-Heart algorithm's code Надеюсь количество участников этой темы увеличится, отдельное спасибо также вам egor и maxal. |
06.07.2005 03:20 Дата регистрации: 20 лет назад Посты: 417 | это же бабл-гам! экспоненциальный к тому же Во-первых, скушались все индексы [ i ], обычно код оборачивают во что-то типа [ code ] ... [ /code ], но на этом форуме оно не работает. ;-( А во-вторых, это обычное динамическое программирование, ничего революционного. Проблема в том, что оно требует O(m) вычислений и столько же памяти. Т.е. приведенный алгоритм является экспоненциальным. |
06.07.2005 03:22 Дата регистрации: 20 лет назад Посты: 417 | нечего тут обсуждать Динамическое программирование. Примерно тоже самое, что предлагал egor. Сложность экспоненциальная. |
06.07.2005 20:21 Дата регистрации: 20 лет назад Посты: 16 | Уверены ? Если не ошибаюсь, алгоритм является экспоненциальным, если входные его данные сидят в показателе степени какого-нибудь числа, - двойки, например. Причём здесь O(m) ? Это более чем удовлетворительная сложность ( разве что log может спустить на землю ) и она является полиномиальной. Причём здесь экспоненциальность ? А то что это динамическое программирование, - так я не спорю. Методы динамического программирвоания всегда отличались красотой. Во всем известной задаче на покрытие метод динамического программирования имеет действительно экспоненциальную сложность, однако оргинальность его идеи неоспорима. P.S. Если точнее, в нашей задаче не O(m), а O(k*m), где k- длина массива. Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means ! |
06.07.2005 21:57 Дата регистрации: 20 лет назад Посты: 417 | конечно Помните, что дано число m? Какая его длина? Очевидно, длина пропорциональна log(m). Далее, m = 2^log(m) - вот вам и экспонента. Другими словами, можете вы решить задачу для m=10^6, а для m=10^10 или для m=10^100 ? Боюсь, что последнее предложенному алгоритму не под силу. А вот, например, алгоритму описанному на http://www.mathforum.ru/forum/read/1/4870/4940/#4940 m=10^100 вполне по зубам. А все потому, что тот алгоритм полиномиальный. Чуствуете разницу? |
07.07.2005 23:32 Дата регистрации: 20 лет назад Посты: 14 | Решение исходной задачи В дополнение к предыдущим версиям решения исходной задачи предложенные egor- хочу предложить к обсуждению ещё 2 версии: а) precondition: рекурсивный алгоритм получает параметры: массив A, r=n ,Sum=m postcondition: алгоритм выдаёт True или False SUBSET-SUM (A, r, Sum) 1 if Sum = 0 2 then return True 3 if r < 1 4 then return False 5 return SUBSET-SUM (A, r - 1, Sum) or SUBSET-SUM (A, r - 1, Sum- A[r]) P.S. SUBSET-SUM (A, r - 1, Sum) <=>обработай массив величины=r - 1 в котором есть член A[r] SUBSET-SUM (A, r - 1, Sum - A[r]) <=>обработай массив величины=r - 1 в котором отсутвует член A[r] Это экспоненциальный алгоритм T(n) = O(2^n). б) итеративный алгоритм использует вспомогательный stack - M, precondition: алгоритм получает параметры: массив A, r=n ,Sum=m postcondition: алгоритм выдаёт True или False SUBSET-SUM (A, r, Sum) 1 found = False 2 PUSH (M, (r, Sum)) 3 while not found and not EMPTY-STACK (M) 4 do (r, Sum) = POP (M) 5 if Sum = 0 6 then found = True 7 else if r >= 1 8 then PUSH (M, (r - 1, Sum)) 9 PUSH (M, (r - 1, Sum - A[r])) 10 return found P.S. PUSH (M, (r - 1, Sum)) <=>обработай стэк M, величины=r - 1 в котором есть член A[r] PUSH (M, (r - 1, Sum - A[r])) <=>обработай стэк M, величины=r - 1 в котором отсутвует член A[r] Интересно ваше мнение форумчане-какие плюсы и минусы у каждого из этих 2 алгоритмов? |
08.07.2005 00:28 Дата регистрации: 20 лет назад Посты: 16 | Weird... Что такое длина числа m ? Первый раз втречаюсь с таким понятием. И зачем нам какой-то log (m) совать в степень ? Возможно. По крайней мере, я не проверял опытным путём, так что промолчу. Здесь я не решусь с вами спорить, но подозрения у меня есть. Во-первых, у вас числа два. Во-вторых, они оба взаимно простые. В-третьих, вы где-то там "не ограничили общность". Все эти три пункта, конечно, может и не ограничивают так называемой общности, и алгоритм действительно делает своё "полиномиальное" дело. Но уж больно халявно всё это выглядит... Может, предложите строго формализовыанный алгоритм, для произвольного набора чиел, а не для пары и т.п.? Тогда действительно можно будет посмотреть и положить конец дискуссиям. Знаете ли, сколько учусь, постоянно с недоверием отношусь к фразам "не ограничивая общности" ( как жизнь показывает, недаром ) Под этим, кажись, скрывается обыкновенная природная халявность. А если начать капать глкбже, там такое может вылезть... Много всяких людей отучивается от глубинной рутинной работы, останавливаясь на уровне сырой идеи. Жаль, но это, как правило, гроша не стоит. Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means ! |
08.07.2005 00:52 Дата регистрации: 20 лет назад Посты: 417 | это по незнанию
Ну, батенька, Вам надо почитать хотя бы основы теории сложности вычислений. Без знания их рассуждения о сложности становятся профанацией. Можно начать с http://www.mccme.ru/free-books/matpros5.html или . Вкратце: сложность алгоритма - есть функция от длины входа и выхода. Длина - число битов (0 и 1) требуемое для записи числа. Длина целого неотрицательного числа примерно равна двоичному логарифму из этого числа. Далее, что является входом рассматриваемой задачи? Это числа m, n, и n чисел массива a[], скажем, максимальное из которых A. Таким образом, длина входа будет примерно log(m) + n*log(A). Откуда, грубо говоря, сложность полиномиального алгоритма для этой задачи может полиномиально зависеть от n и log(m), но не от m. Дело в том, что если сложность зависит полиномиально от m, то она зависит экспоненциально от длины m, так как m=2^log(m) - экспоненциальная функция от log(m).
А тут и проверять не надо. Невооруженным глазом видно, что в Вашем алгоритме используется массив размера m и цикл до m. При m=10^100 такие операции практически неосуществимы.
Вашей задачи для частного случая n=2. Я привел этот алгоритм в качестве иллюстрации того, что такое полиномиальный алгоритм (в отличие от приведенного Вами алгоритма, который является экспоненциальным). |
08.07.2005 20:17 Дата регистрации: 20 лет назад Посты: 16 | Согласен Ух ты-ы-ы ! Честное слово, введённое вами определние я слышу впервые ! И всё никак не могу взять в толк, причём здесь двоичное представление числа m, а не оно само. Но разъяснять не надо, я только убедился, что МЫ ДЕЙСТВИТЕЛЬНО РАЗГОВАРИВАЛИ НА РАЗНЫХ ЯЗЫКАХ : вы, видимо, всё это время посвящали меня в какие-то специальные моменты профессиональной теории алгоритмов ( я имел, конечно, дело с машинами Тьюринга, где встречалась длина входа как число единичек или тому подобной дряни - это хоть отдалённо с вашими словами соприкасается ? ), я же использовал самые обыкновенные понятия алгоритма как набора интуитивных операций, где основной вклад в сложность дают всевозможные циклы. Например, сортировка пузырька даёт O(n^2), быстрая сортировка даёт O(n*log n) и т.п. Теперь вы поняли, какими терминами я оперировал всё это время ? Именно с моей точки зрения алгоритм Харта имеет прекрасную полиномиальную сложность. Вопрос из любопытства : а зачем используются такие понятия, как длина числа ? Это принципиальный момент ? Это актуально в прикладной области или это бессмысленный пережиток чистой дискретной математики ? Спасибо за ваш ответ. В общем, я бы попросил вас, если вам не сложно, предъявить здесь строго формализованный алгоритм, на который вы ссылаетесь. Фразы типа "рассмотрим два чиcла" или "не ограничивая общности" не производят должного эффекта. Остановиться на сырой идее и пропустить мимо себя якобы рутинную, черновую работу ( которую многие высокомерно считают ниже себя ) - это даже не пол дела. Увы, так всегда показывал мой опыт. Прикрываясь этими фразами, многие авторы учебников и лекторы просто дают волю своей халявности - обыкновенной человеческой халявности. Думаю, если здесь будет представлен точный алгоритм для произвольного набора чисел, тогда дискуссиям будет положен конец, и один из двух алгоритмов достойно займёт первое место по скорости выполнения. Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means ! |
08.07.2005 21:05 Дата регистрации: 20 лет назад Посты: 417 | не упорствуйте
В том-то и дело, что язык один. Просто Вы пытаете "интуитивно" использовать понятия, о которых имеется слабое представление, в то время как у них существует чёткое определение.
НЕТ, НЕТ и еще раз НЕТ! Алгоритмы O(n^2) и O(n*log n) для сортировки действительно являются полиномиальными, потому что n здесь - размер сортируемого массива (т.о. длина входа есть ~ n*log(A)). В рассматриваемой задаче также есть массив длины n, но плюс к этому число m не является размером чего-либо, просто числом длины ~ log(m). Поэтому алгоритм, например, сложности O(n^2 * log(m)) для ее решения был бы полиномиальным, но алгоритм сложности O(n*m) является экспоненциальным, увы.
Конечно приципиальный! Люди хотят что-бы объём вычислений был соразмерен с объёмом данных. Если это так, то задача будет "решабельной" при любом объёме входных данным; нет - нет. В этой связи стоит также упомянуть знаменитую проблему P != NP, за решение которой дают миллинон долларов. Наверное, не просто так.
Тогда увы. Если Вам так трудно найти и разобрать указанные понятия, то разжевывать я не собираюсь. И так уже наша дискуссия становится чрезчур утомительной.
Полиномиального алгоритма не будет. Это NP-полная задача. Когда я говорил "легко решается", я подразумевал случай фиксированного n. Для каждого фиксированного малого n можно указать полиномиальный алгоритм, но их сложность растет экспоненциально с ростом n. |
11.07.2005 00:43 Дата регистрации: 20 лет назад Посты: 16 | Поищу статью Ну вот мы и пришли к благополучному завершению глупого спора. Свине-хартовский алг. удобен своей краткостью, простотой ( всего лишь два цикла ), не требует специальных вызовов функций, рекурсий и тому подобной дряни. И вообще код на уровне школьного понимания. Даст бог, двойной цикл сразу провалится в кэш и решит все проблемы быстродействия. Правда, в предельных случаях могут возникнуть проблемы с выделением памяти, но что поделать ? Да и сама природа задачи требует большого объёма памяти ( если числа астрономические ). А понятия NP, не NP - экономистов, химиков и остальных не интересует. O(k*m) - и точка ( с этим даже вы, maxal, не поспорили. А получается это действительно "интуитивным" подсчётом шагов в циклах ). Видимо, именно в связи с вышесказанным алг. порадовал многих современников. Найду ссылку или статью - обязательно сошлюсь, там всё будет написано. Но это точно не моя фантазия, я сам держал текст статьи на англ. яз.. Удачи ! Bye ! :-) Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means ! |
16.07.2005 14:22 Дата регистрации: 20 лет назад Посты: 398 | Псевдополиномиальность и историческое замечание Листаю книгу Гэри и Джонсона "Вычислительные машины и труднорешаемые задачи" (написана в 1978). В параграфе 4.2 (Задачи с числовыми параметрами и сильная NP-полнота) как раз подробно обсуждается задача о разбиении и алгоритм динамического программирования. К тому, что уже было сказано на форуме, можно добавить совсем чуть-чуть. Описанный здесь алгоритм с двумя циклами - классический пример "псевдополиномиального по времени алгоритма" (временная функция ограничена сверху полиномом от двух переменных: длины входа и максимального числового параметра). Историческое замечание.
|
31.03.2007 14:10 Дата регистрации: 18 лет назад Посты: 1 | Рекурсивный алгоритм, определяющий группу чисел из массива, чтобы сумма=m Option Base 1 Sub МассивСумма() Dim isxArray() Dim i As Integer Dim j As Integer Dim k As Integer Dim a As Integer Dim SodJach As Double Dim pSum As Double Dim XSum As Double Dim str_msg As String i = 0 Do i = i + 1 SodJach = ActiveCell.Value If ActiveCell.Value = 0 Then Exit Do ReDim Preserve isxArray(i) isxArray(i) = SodJach ActiveCell.Offset(1, 0).Range("A1").Select Loop 'Создан массив размером (i-1) XSum = Sheets("Лист2").Range("B1") iz = 0 For k = 1 To i - 2 For j = k + 1 To i - 1 pSum = isxArray(k) + isxArray(j) If pSum = XSum Then iz = iz + 1 ActiveSheet.Cells(1, iz + 5) = isxArray(k) ActiveSheet.Cells(2, iz + 5) = isxArray(j) str_msg = str_msg & isxArray(k) & ":" & isxArray(j) & ";" End If Next Next MsgBox "Слогаемые: " & str_msg, , _ str_msg = "" 'Выполнен перебор 2 слогаемых If i - 1 = 3 Then Exit Sub iz = 0 For k = 1 To i - 3 For j = k + 1 To i - 2 For a = j + 1 To i - 1 pSum = isxArray(k) + isxArray(j) + isxArray(a) If pSum = XSum Then iz = iz + 1 ActiveSheet.Cells(4, iz + 5) = isxArray(k) ActiveSheet.Cells(5, iz + 5) = isxArray(j) ActiveSheet.Cells(6, iz + 5) = isxArray(a) str_msg = str_msg & isxArray(k) & ":" & isxArray(j) & ":" & isxArray(a) & ";" End If Next Next Next MsgBox "Слогаемые: " & str_msg, , _ str_msg = "" 'Выполнен перебор для 3 слогаемых End Sub Для дальнейшего перебора на большее число слогаемых нужно добавлять циклы For Next. Программа написана в VBA для Exel (в столбце А начиная с ячейки A1 расположен одномерный массив, в ячейке B1 сумма m. Программа протестировна на практике без проблем. Кто предложит упростить на других языках или в сочетании языков упростить написание кода для увеличения числа слогаемых? |
Copyright © 2000−2023 MathForum.Ru & MMOnline.Ru Разработка, поддержка и дизайн — MMForce.Net | ![]() | ![]() |