2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Ludmila - решение нерешенных математических задач методом по
Сообщение16.08.2021, 14:36 


16/08/21
2
Ludmila - решение нерешенных математических задач методом подбора

Описание
Скрипт Ludmila предназначен для решения нерешенных математических задач методом подбора.
Есть список элементов уравнений:

- числа (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
- операции (+, *, /, -)
- скобки (левая, правая)
- степень (квадратная, кубическая, корень квадратный, корень кубический)
- x (может быть несколько в наборе - x0, x1, x2, ...)

Есть входящие наборы данных:
- data1.txt (линейное уравнение)
- data2.txt (теорема пифагора)
- data3.txt (ряд простых чисел)

Например набор data1.txt (линейное уравнение) выглядит вот так:

3235 51 62 73

3350 52 63 74

3467 53 64 75

... и т.д. (всего 100 элеметов в наборе)

Первая цифра значение y, последующие цифры значения x (в данном случае x0, x1, x2)

Для нахождения верного уравнения перебираются комбинации уравнений. Выглядит это примерно так:

y = 1

y = 2

...

перебираются все уравнения длинной 1, затем длинной 2. Уравнения длинной 3 могут выглядеть например так:

y = 1 + x0

y = 1 + x1

... и так далее, пока не дойдет до:

y = x0 * x1 + x2

В итоге набор данных (3235 51 62 73) выдаст совпадение, далее эта форумла перебирает все наборы данных data1.txt их всего 100 штук. И если все 100 наборы данных прошли проверку, то уравнение считается решенным.

Оптимизация

Так как нет смысла уравнения в котором рядом стоят например два оператора +, поэтому есть правила конкатенации - что может стоять рядом друг с другом, а что нет. В результате чего скорость работы скрипта была увеличина в 15 раз. Правила конкатенации находятся в config.py, переменная types.

Производительность

Производительность на CPU:

- Линейное уравнение решается за 7 секунд (5 символов) v|x0;o|*;v|x1;o|+;v|x2
- Теорема пифагора решается за 8100 секунд (8 символов) bl|(;v|x0;e|**2;o|+;v|x1;e|**2;br|);e|**0.5

Задачи

Главной задачей данного скрипта является решение нерешенных математических задач
- [Открытые математические проблемы](https://ru.wikipedia.org/wiki/%D0%9E%D1 ... 0%BC%D1%8B)
- [Задачи тысячелетия](https://ru.wikipedia.org/wiki/%D0%97%D0 ... 0%B8%D1%8F)

Но не все они могут быть представлены в виде наборов данных.

To Do
- Переделать, чтобы вычисления производились не на CPU, а на GPU (CUDA).
- Добавить больше математических операций - sin, cos, tg, ctg, π, e, log (упадет производительность, но увеличится вероятность нахождения формулы).
- Добавить наборы данных для других нерешенных математических задач.

Запуск

- в файле config.py в переменной data_id указать id набора данных (1 - линейное, 2 - теорема пифагора, 3 - ряд простых чисел)
- запустить файл ludmila.py командой:
c:\Python37\python e:\python\maths\ludmila.py
- результат будет в консоле, а так же в лог файле log.txt

Вопросы
У меня есть два вопроса к сообществу:

- Есть ли подобные скрипты? Возможно кто-то уже делал такое и мой скрипт бессмысленный потому что эта работа уже проделана кем-то другим.

- Вопрос к тем кто работал с CUDA. Сейчас вычисления производятся на CPU. Возможно ли переделать на GPU тем самым повысив производительность в десятки раз?

Ссылка на исходники

https://github.com/nevstas/ludmila

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение16.08.2021, 15:02 


14/01/11
2916
Nevep в сообщении #1528818 писал(а):
Возможно кто-то уже делал такое и мой скрипт бессмысленный потому что эта работа уже проделана кем-то другим.

Например, вот:
GPT-f — Neural Network That Generates Theorem Proofs

 Профиль  
                  
 
 Posted automatically
Сообщение16.08.2021, 15:20 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Дискуссионные темы (М)» в форум «Свободный полёт»
Причина переноса: пожалуй, пока сюда.


-- 16.08.2021, 15:22 --

Nevep в сообщении #1528818 писал(а):
- Есть ли подобные скрипты? Возможно кто-то уже делал такое и мой скрипт бессмысленный потому что эта работа уже проделана кем-то другим.
Как упражнение по программированию для школьника - неплохо, хотя выбранный метод удивительно неэффективен. Ни о чем большем, увы, говорить не приходится.

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение16.08.2021, 16:50 
Заслуженный участник


08/04/08
8556
Nevep в сообщении #1528818 писал(а):
To Do
- Переделать, чтобы вычисления производились не на CPU, а на GPU (CUDA).
- Добавить больше математических операций - sin, cos, tg, ctg, π, e, log (упадет производительность, но увеличится вероятность нахождения формулы).
- Добавить наборы данных для других нерешенных математических задач.
...
- Вопрос к тем кто работал с CUDA. Сейчас вычисления производятся на CPU. Возможно ли переделать на GPU тем самым повысив производительность в десятки раз?
Вы еще предложите переписать все с питона на ассемблер для ускорения. Все это бесполезно. Вы должны знать, что доказательство теорем - $NP$ - полная задача. На практике это означает экспоненциальный рост ресурсов для решения проблемы. Любая оптимизация уменьшает время работы всего лишь в константу раз, в то время как любое увеличение любого параметра задачи увеличивает то же самое время опять в константу раз.
Т.е. простой перебор тут априори бессмысленный.
Вообще программы автоматического доказательства теорем писались с середины 20 века (была программа "логик-теоретик" и т.п.). Чтобы въехать в проблематику, можно ознакомиться с историей, использованными методами и результатами в учебниках.

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение17.08.2021, 18:33 


16/08/21
2
Sonic86 в сообщении #1528831 писал(а):
Вы еще предложите переписать все с питона на ассемблер для ускорения. Все это бесполезно. Вы должны знать, что доказательство теорем - $NP$ - полная задача. На практике это означает экспоненциальный рост ресурсов для решения проблемы. Любая оптимизация уменьшает время работы всего лишь в константу раз, в то время как любое увеличение любого параметра задачи увеличивает то же самое время опять в константу раз.
Т.е. простой перебор тут априори бессмысленный.
Вообще программы автоматического доказательства теорем писались с середины 20 века (была программа "логик-теоретик" и т.п.). Чтобы въехать в проблематику, можно ознакомиться с историей, использованными методами и результатами в учебниках.


Сейчас вычисления производятся на CPU на 1 ядре. В GPU их (ядер) сотни, а если несколько GPU - ускорение скрипта будет в несколько сот раз

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение17.08.2021, 19:01 


14/01/11
2916
Боюсь, для решения озвученных задач вашим методом вычислительных мощностей не хватит, даже если число GPU превысит число атомов во Вселенной.

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение17.08.2021, 19:02 


05/09/16
11461
Nevep
А можете показать пример, как ваш скрипт решает какую-нибудь уже решенную людьми (но которую раньше записывали в нерешенные) проблему?

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение17.08.2021, 19:37 
Аватара пользователя


07/03/16

3167
wrest в сообщении #1528945 писал(а):
как ваш скрипт решает какую-нибудь уже решенную людьми...

Зачем же зря расходовать время? Может задать сразу нерешенную?
:)

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение17.08.2021, 19:57 


05/09/16
11461
Emergency в сообщении #1528947 писал(а):
Зачем же зря расходовать время? Может задать сразу нерешенную?
:)

Как раз нет. Про решённые точно известно, что решение есть. А значит скрипт мог бы решение найти.

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение17.08.2021, 20:25 


12/07/15
2907
г. Чехов
Nevep в сообщении #1528818 писал(а):
- Линейное уравнение решается за 7 секунд (5 символов) v|x0;o|*;v|x1;o|+;v|x2
- Теорема пифагора решается за 8100 секунд (8 символов) bl|(;v|x0;e|**2;o|+;v|x1;e|**2;br|);e|**0.5

Теоремы должны доказываться, а не решаться. Вот ваша Людмила нашла некоторое уравнение, а кто скажет, что это та самая квинтэссенция знания?

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение17.08.2021, 21:16 


20/09/09
1877
Уфа
Цитата:
Вы еще предложите переписать все с питона на ассемблер для ускорения. Все это бесполезно. Вы должны знать, что доказательство теорем - $NP$ - полная задача. На практике это означает экспоненциальный рост ресурсов для решения проблемы. Любая оптимизация уменьшает время работы всего лишь в константу раз, в то время как любое увеличение любого параметра задачи увеличивает то же самое время опять в константу раз.
Т.е. простой перебор тут априори бессмысленный.
Вообще программы автоматического доказательства теорем писались с середины 20 века (была программа "логик-теоретик" и т.п.). Чтобы въехать в проблематику, можно ознакомиться с историей, использованными методами и результатами в учебниках.

Прошу прощения, можно ли в таком случае задачу доказательства теорем назвать "ИИ-полной", то есть такой, которую в будущем сможет решать "сильный ИИ" (если он будет создан)?

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение18.08.2021, 06:11 
Аватара пользователя


22/06/17
291
Nevep в сообщении #1528818 писал(а):
Есть ли подобные скрипты? Возможно кто-то уже делал такое

Vince Diesel в сообщении #1099795 писал(а):
Есть программа Eureqa, которая предлагает по набору данных варианты аналитических формул. Как рз в порядке возрастания сложности записи.

Смотрите список программ на страничке Symbolic regression.

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение20.08.2021, 07:57 


10/08/21
30
В код скрипта не всматривался и в описание не вчитывался - прошу прощения. Мой коммент чисто умозрительный.

Вообще идея на сколько я знаю не новая. Где-то кто-то когда-то и не один, предлагал решение задач методом перебора всех возможных решений. В криптографии это называется brute force... То же применяется и в комбинаторике. В софтеной среде тоже всплывала тема (и не раз) создать генератор кода, который из кусков собирает все возможные варианты (это было кажется в тематике попытке создать "сильный" AI). На одном форуме видел подобную программу для решения каких-то химических задач. Но абсолютно все такие решения упираются в одну проблему - вычислительные мощности... Но тут уже об этом писали.

Однако идея хорошая. Респектую )))

 Профиль  
                  
 
 Re: Ludmila - решение нерешенных математических задач методом по
Сообщение20.08.2021, 14:29 
Аватара пользователя


07/03/16

3167
uzlprog в сообщении #1529114 писал(а):
Где-то кто-то когда-то и не один, предлагал решение задач методом перебора всех возможных решений.

Перебор неэкономичен. Есть методы "крутого восхождения", которые широко применяются в оптимизационных задачах.

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

Модератор: Модераторы



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

Сейчас этот форум просматривают: YandexBot [bot]


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group