OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Понедельник, 22 Октябрь, 2018 17:56

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Решение уравнений Диофанта
СообщениеДобавлено: Воскресенье, 29 Июль, 2012 05:37 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
НЕ бог весть какая идея, но копаясь на досуге с разными задачками нашел метод решения любого уравнения Диофанта.
Правда метод не слишком интересный. Не понятно когда он гарантированно работает лучше простого перебора. Просто я такого приема не встречал для общих подходов. Поясняю на примере. Пример в файле.


Вложения:
Example.rar [2.55 КБ]
Скачиваний: 148
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решение уравнений Диофанта
СообщениеДобавлено: Воскресенье, 29 Июль, 2012 12:48 
Аватара пользователя

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


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

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


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


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

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

Итак имеем некоторое уравнение. Допустим, что оно имеет корни 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
Независимость от количества переменных и степеней очевидно, так как используется только четность или нечетность корней.
В чем я не прав?

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решение уравнений Диофанта
СообщениеДобавлено: Четверг, 04 Октябрь, 2012 04:20 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Слабое место которое я сам вижу у алгоритма в уравнениях в которых нет корней. В общем случае не до конца понятно, как он будет себя вести.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решение уравнений Диофанта
СообщениеДобавлено: Четверг, 11 Октябрь, 2012 01:50 
Аватара пользователя

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Обдумал, сможет ли алгоритм остановиться если решения нет. Пришел к положительному выводу. Дело в том, что критерий остановки не требует обнаружения корня. Он останавливается если ни одной итерации нет и уже не может быть тривиального решения. А что такое тривиальное решение я показал на примере. Есть корень или нет для остановки роли не играет. Обнаружение корня это как бы между делом.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2018, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB