OberonCore
https://forum.oberoncore.ru/

Решение уравнений Диофанта
https://forum.oberoncore.ru/viewtopic.php?f=28&t=4036
Страница 1 из 1

Автор:  vvp [ Воскресенье, 29 Июль, 2012 05:37 ]
Заголовок сообщения:  Решение уравнений Диофанта

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

Вложения:
Example.rar [2.55 КБ]
Скачиваний: 194

Автор:  Александр Ильин [ Воскресенье, 29 Июль, 2012 12:48 ]
Заголовок сообщения:  Re: Решение уравнений Диофанта

vvp писал(а):
НЕ бог весть какая идея, но копаясь на досуге с разными задачками нашел метод решения любого уравнения Диофанта.
Не понял. Математической открытие свершилось?
http://ru.wikipedia.org/wiki/Диофантово_уравнение:
Цитата:
Десятая проблема Гильберта, сформулированная в 1900 году, состоит в нахождении алгоритма решения произвольных алгебраических диофантовых уравнений. В 1970 году Юрий Матиясевич доказал алгоритмическую неразрешимость этой проблемы.

Автор:  vvp [ Воскресенье, 29 Июль, 2012 16:47 ]
Заголовок сообщения:  Re: Решение уравнений Диофанта

Александр Ильин писал(а):
vvp писал(а):
НЕ бог весть какая идея, но копаясь на досуге с разными задачками нашел метод решения любого уравнения Диофанта.
Не понял. Математической открытие свершилось?
http://ru.wikipedia.org/wiki/Диофантово_уравнение:
Цитата:
Десятая проблема Гильберта, сформулированная в 1900 году, состоит в нахождении алгоритма решения произвольных алгебраических диофантовых уравнений. В 1970 году Юрий Матиясевич доказал алгоритмическую неразрешимость этой проблемы.


Конечно нет. Алгоритмическая разрешимость требует конечности процесса. А мое преобразование для произвольного уравнения конечность процесса не гарантирует. Кроме того я более менее уверен в действенности преобразования для уравнений первой степени. Для второй и выше не все понятно.

Автор:  vvp [ Среда, 03 Октябрь, 2012 11:06 ]
Заголовок сообщения:  Re: Решение уравнений Диофанта

Однако с алгоритмической неразрешимостью у меня возникли проблемы. Дело в том, что по весне, мне удалось получить алгоритм решающий любые диофантовы уравнения в целых числах. Получил и забыл. Мои ребята его реализовали, мы порешали огромное количество разных уравнений.
А сегодня я сообразил, что это радикально противоречит утверждению о алгоритической неразрешимости. Может быть я что не вижу и не понимаю, поэтому ниже излагаю метод и привожу пример. Излагаю на уравнении с двумя переменными, для упрощения дела. Количество переменных и степеня роли не играют.

Итак имеем некоторое уравнение. Допустим, что оно имеет корни x и y. Очевидно, что эта пара представима одним из четырех способов:
1) x=2x y=2y
2) x=2x+1 y=2y+1
3) x=2x+1 y=2y
4) x=2x y=2y+1
Мы получили четыре подстановки преобразующие исходное уравнение в четыре новых, одно из которых содержит решение исходного и что приятно в этих уравнениях корни изменились вдвое.
Этот ветвящийся процесс можно продолжать до тех пор пока корни не станут нулями или единицами. Ясно, что это произойдет за конечное число шагов. Вопрос в том, как эту точку определить и что с ней делать. Так как это не детальная математическая статья, я покажу на примере
Решим уравнение 3x+5xy-4y=53
1) x=2x y=2y тупиковая ветвь, так как слева от равенства четное число а справа нечетное.
2) x=2x+1 y=2y+1
После преобразований 16x+20xy+2y = 49 тупиковая ветвь
3) x=2x y=2y+1
После преобразований 16x+20xy-8y=57 тупиковая ветвь
4) x=2x+1 y=2y
После преобразований 3x+10xy+y=25
Это возможно. Проверим есть ли здесь тривиальное решение
1) x=0 y=0 получаем 0=25 не решение
2) x=0 y=1 получаем 1=25 не решение
3) x=1 y=0 получаем 3=25 не решение
4) x=1 y=1 получаем 14=25 не решение
Тривиального решения нет, поэтом второй шаг, так же из четырех подстановок, но сокращу до одной
x=2x+1 y=2y
После преобразований получаем 3x+20xy+11y=11
Очевидно есть тривиальное решение x=0 y=1
Крутим подстановки обратно
x=2*0+1= 1 y=2*1 = 2
x=2*1+1 = 3 y=2*2 = 4
Проверяем 3*3+5*3*4-4*4 = 53
Независимость от количества переменных и степеней очевидно, так как используется только четность или нечетность корней.
В чем я не прав?

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

Автор:  vvp [ Четверг, 04 Октябрь, 2012 04:20 ]
Заголовок сообщения:  Re: Решение уравнений Диофанта

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

Автор:  vvp [ Четверг, 11 Октябрь, 2012 01:50 ]
Заголовок сообщения:  Re: Решение уравнений Диофанта

Обдумал, сможет ли алгоритм остановиться если решения нет. Пришел к положительному выводу. Дело в том, что критерий остановки не требует обнаружения корня. Он останавливается если ни одной итерации нет и уже не может быть тривиального решения. А что такое тривиальное решение я показал на примере. Есть корень или нет для остановки роли не играет. Обнаружение корня это как бы между делом.

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/