ChessPro online

Математика

вернуться в форум

30.09.2007 | 20:54:28

Главная  -  Поговорим?  -  Наука

1

chich

раввин

20.02.2014 | 23:21:54
Сайт

все его сообщения:
за день, за месяц,
за все время
Компьютер вывел математическое доказательство, слишком сложное для человека

Двое математиков русского происхождения из Ливерпуля, Алексей Лисица и Борис Конев, придумали интересную дилемму: что будет, если заставить компьютерную программу решить математическую задачу, но решение будет слишком сложным и длинным, чтобы его проверил человек?

Для примера учёные взяли так называемую Проблему несоответствия Эрдеша, сформулированную знаменитым венгерским математиком Полом Эрдешем (Paul Erdős). Задача построена вокруг поиска закономерности в бесконечном списке всего двух чисел "1" и "-1". Проблема возникает в тот момент, когда отсекается бесконечная последовательность, а затем создаётся конечная последовательность с использованием определённой константы. Сумма чисел и называется фигурой несоответствия.

Лисица и Конев ввели условия задачи с константой несоответствия "2" в компьютер со специальным программным обеспечение SAT-solvers ("Решатели задач выполнимости булевых формул"), которые предназначены для создания математических доказательств.

Компьютер выдал файл с решением математической проблемы, объём которого превышал на пару гигабайтов объём всей "Википедии". Очевидно, что человеку проверить это решение будет не под силу. И потому учёные задают вопрос всем своим коллегам: готовы ли мы настолько доверять компьютерам, чтобы они самостоятельно решали математические и другие логические задачи?

2

iourique

21.02.2014 | 00:28:56

все его сообщения:
за день, за месяц,
за все время
На случай, если кого-то интересует вменяемое изложение тех же фактов.
номер сообщения: 49-47-10302

3

Sad_Donkey

КМС

21.02.2014 | 14:15:35

все его сообщения:
за день, за месяц,
за все время
Википедия:
"Проблема Гольдбаха (гипотеза Гольдбаха, проблема Эйлера, бинарная проблема Гольдбаха) — утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел. Одна из самых известных открытых математических проблем; в совокупности с гипотезой Римана включена под номером 8 в список проблем Гильберта (1900) и является одной из немногих проблем Гильберта, до сих пор остающихся нерешёнными по состоянию на 2010-е годы."

Насколько мне известно, проблема Гольдбаха недавно решена. Ответ - положительный.

Сделал это какой-то китаец, вернувшись на родину после того, как ему отказали в трудоустройстве в США. Кроме этой сплетни, никаких подробностей не знаю.

__________________________
Я вам работать не мешал Не мешайте мне отдыхать
номер сообщения: 49-47-10303

4

iourique

21.02.2014 | 18:59:47

все его сообщения:
за день, за месяц,
за все время
Что-то я сомневаюсь. Результат громкий, подробности бы были. Слабая (тернарная) гипотеза Гольдбаха была доказана в прошлом году - не знаю, проверено ли доказательство, но вроде особо никто не сомневался.

А китаец (правда, вполне себе работающий в Америке) недавно доказал, что существует бесконечно много пар простых чисел, отличающихся не более чем на 70,000,000 (результат был впоследствии улучшен до 264).
номер сообщения: 49-47-10304

5

Sad_Donkey

КМС

21.02.2014 | 19:50:20

все его сообщения:
за день, за месяц,
за все время
Интересно. Наверное, вы "правее". Узнаете еще что-нибудь на эту тему, расскажите, пожалуйста.

__________________________
Я вам работать не мешал Не мешайте мне отдыхать
номер сообщения: 49-47-10305

6

Хайдук

чайник

13.04.2014 | 18:31:59

все его сообщения:
за день, за месяц,
за все время
в принципе, почтенный чич, компы выводят доказательства НЕ для того, чтобы мы их проверяли, а то иначе какого хр*на ради доверять компам работу вообще? Даже наоборот: именно компу возлагают проверить некоторые очень длинные и сложные выкладки. Вот курьезный пример: целая группа экспертов не смогли на протяжении нескольких лет (!) придти к согласию верна ли некая теорема об упаковании пространства шарами, все устали и ... за*бали работу . Тяперича сам автор теоремы, почувствовав себя обиженным непризнанием своего результата, вкалывает в программу для компа, которая смогла бы выдать непререкаемый вердикт о том верна ли его теорема (в чем он сам не сомневается) или да
номер сообщения: 49-47-10378

7

avi47

15.04.2014 | 00:42:52

все его сообщения:
за день, за месяц,
за все время
Нет ли теории, разработавшей задачу определения количества символов, используемых для решения той или иной проблемы?
номер сообщения: 49-47-10382

8

shcherb

19.01.2015 | 15:40:59

все его сообщения:
за день, за месяц,
за все время
Мемория. Леонид Канторович

На вагоностроительном заводе имени Егорова в Ленинграде с помощью линейного программирования сделали раскрой металла. Это была пионерная работа и в мире, и у нас в стране. Делалось все в эпоху арифмометров, а не ЭВМ, вообще, вероятно, это было первое в мировой практике реальное применение методов линейного программирования. После того как были применены оптимальные методы и несколько сократился расход металла, оказалось, что резко уменьшилась возможность сдачи металлолома. В итоге был сорван план сдачи отходов металла, а раз один из показателей плана не выполнен, то предприятие не может быть премировано в полном размере. Тогда райком помог преодолеть эту трудность, и в виде исключения премия заводу была сохранена, несмотря на срыв одного из показателей. Второй казус этой ситуации: отраслевое начальство, получив рапорт о том, что завод на 4 процента увеличил использование металла при раскрое, предложило им не терять темпа и в следующем году опять подняло план использования металла на те же 4 процента. Выходило, что металл должен использоваться на 101 процент, и пришлось даже писать бумагу от академии, что больше 100 процентов не бывает.



__________________________
не надо шутить с войной
номер сообщения: 49-47-10648

9

Sad_Donkey

КМС

19.01.2015 | 23:59:59

все его сообщения:
за день, за месяц,
за все время
В студенческие годы слышал такую задачу. Может быть, она кого-нибудь развлечет.
Доказать, что у каждого тетраэдра есть ребро, такое, что все углы, для которых оно является стороной - острые.

__________________________
Я вам работать не мешал Не мешайте мне отдыхать
номер сообщения: 49-47-10649

10

jenya

не то, чтобы очень
но и не так, чтобы совсем не

06.02.2015 | 22:28:53

все его сообщения:
за день, за месяц,
за все время
Урок алгебры в 7-м классе по теме "Система линейных уравнений с двумя переменными"

В классе 36 учеников. Девочек на 3 меньше, чем мальчиков.
номер сообщения: 49-47-10658

11

dimarko

06.02.2015 | 22:34:42

все его сообщения:
за день, за месяц,
за все время
jenya: Урок алгебры в 7-м классе по теме "Система линейных уравнений с двумя переменными"

В классе 36 учеников. Девочек на 3 меньше, чем мальчиков.
позор Виктору Перестукину!
номер сообщения: 49-47-10659

12

dimarko

07.02.2015 | 20:14:51

все его сообщения:
за день, за месяц,
за все время
dimarko:
jenya: Урок алгебры в 7-м классе по теме "Система линейных уравнений с двумя переменными"

В классе 36 учеников. Девочек на 3 меньше, чем мальчиков.
позор Виктору Перестукину!

сегодня жена справедливо указала, что задача не так однозначна, как мне поначалу казалось
возможно, что некоторое нечетное количество учеников попросту не определилось со своим полом
правда, тогда она и нерешаема))
номер сообщения: 49-47-10660

13

jenya

не то, чтобы очень
но и не так, чтобы совсем не

07.02.2015 | 20:18:30

все его сообщения:
за день, за месяц,
за все время
Красивая мысль. Задача не так однозначна во всех смыслах. На ту же тему: три туалета.
номер сообщения: 49-47-10661

14

Vova17

кмс

07.02.2015 | 21:46:59

все его сообщения:
за день, за месяц,
за все время
Вы куда-то не туда математику заводите.


__________________________
Спасение там, где опасность.
номер сообщения: 49-47-10662

15

dimarko

07.02.2015 | 23:24:11

все его сообщения:
за день, за месяц,
за все время
Vova17: Вы куда-то не туда математику заводите.

прошу прощения за оффтоп
однако не могу не отметить, что идея с тремя туалетами нагло уворована проклятыми капиталистами из советской действительности
устные семейные предания донесли до наших дней цитату из заводской газеты "Красный Котельщик"
В заметке, в частности, сообщалось, что заводским строительным управлением закончено строительство бань для мужчин и для женщин, а уже в ближайшее время планируется ввод в эксплуатацию бани для инженерно-технических работников.
номер сообщения: 49-47-10663

16

jenya

не то, чтобы очень
но и не так, чтобы совсем не

07.02.2015 | 23:32:00

все его сообщения:
за день, за месяц,
за все время
номер сообщения: 49-47-10664

17

Grigoriy

28.02.2015 | 20:09:11

все его сообщения:
за день, за месяц,
за все время
Sad_Donkey: В студенческие годы слышал такую задачу. Может быть, она кого-нибудь развлечет.
Доказать, что у каждого тетраэдра есть ребро, такое, что все углы, для которых оно является стороной - острые.

Слишком просто
номер сообщения: 49-47-10668

18

Grigoriy

21.03.2015 | 23:18:05

все его сообщения:
за день, за месяц,
за все время
Две лодки отчаливают одновременно от противоположных берегов озера. Лодки плывут по прямой и с постоянной скоростью. Первый раз они встречаются в 500 метрах от одного берега, а на обратном пути - в 300-х метрах от другого берега. Какова ширина озера?

Pешить в уме :-)
номер сообщения: 49-47-10681

19

dimarko

22.03.2015 | 00:44:33

все его сообщения:
за день, за месяц,
за все время
Подбором то решил
но это неверный подход
номер сообщения: 49-47-10682

20

FIBM

22.03.2015 | 01:21:08

все его сообщения:
за день, за месяц,
за все время
Grigoriy: Две лодки отчаливают одновременно от противоположных берегов озера. Лодки плывут по прямой и с постоянной скоростью. Первый раз они встречаются в 500 метрах от одного берега, а на обратном пути - в 300-х метрах от другого берега. Какова ширина озера?

Pешить в уме :-)

Какую часть задачи (физическую или вычислительную) разрешается сделать "на бумаге"?
номер сообщения: 49-47-10683

21

Grigoriy

22.03.2015 | 01:54:54

все его сообщения:
за день, за месяц,
за все время
Up to you
номер сообщения: 49-47-10684

22

Grigoriy

22.03.2015 | 01:59:01

все его сообщения:
за день, за месяц,
за все время
Там есть решение в лоб - получается квадратное уравнение - т е где-то уровень 7-ого класса. Но если вглядеться, можно увидеть решение понятное думаю и сообразительному 3-класснику. 5-класснику точно. Думаю, что я в 5-м классе бы решил. :-)
Думаю, впрочем, что и в 4-м бы увидел.
номер сообщения: 49-47-10685

23

Michael_S

22.03.2015 | 02:44:33

все его сообщения:
за день, за месяц,
за все время
Я решил в уме, но при этом пользовался тем же грубым методом иксов, игреков и пропорций, которым решал бы на бумаге. Закрыл глаза, напряг остатки памяти и готово. Всяко проще, чем думать.

P.S.
только иксов, без игреков
номер сообщения: 49-47-10686

24

Grigoriy

22.03.2015 | 03:29:46

все его сообщения:
за день, за месяц,
за все время
Вы, Михаэль, гигант :-) Я так не могу :-) Я , как и Вы с FIBM, в уме составил пропорцию, прикинул квадратное уравнение, озлился на автора - "Он предлагает это решать в уме?!") - понял, что вряд ли, вгляделся - и за пару минут решил просто :-)
номер сообщения: 49-47-10687

25

Michael_S

22.03.2015 | 03:39:27

все его сообщения:
за день, за месяц,
за все время
Так уравнение хотя и квадратное, но без свободного члена (Ржевский, молчать!). Что сильно облегчает вычисление корней в уме.
номер сообщения: 49-47-10688

26

Grigoriy

22.03.2015 | 04:11:44

все его сообщения:
за день, за месяц,
за все время
А вот "правильное" уравнение, выводимое и решаемое в уме без проблем:

3*500 = s+300
номер сообщения: 49-47-10689

27

Michael_S

22.03.2015 | 04:59:55

все его сообщения:
за день, за месяц,
за все время
Ну да, если начать думать, то можно заметить, что расстояние, пройденное двумя лодками вместе при первой встрече равно одной ширине озера, а при второй встрече трём ширинам, т.е. ровно втрое больше (по причине этого "ровно" и не было в квадратном уравнении свободного члена), и что в виду постоянства скоростей то же соотношение 1:3 сохраняется для расстояний, пройденных каждой из лодок в отдельности.
Но ведь для этого надо думать
Вы - математик, для вас думать над чем то математическим нормально, а может даже в удовольствие.
Я - не математик, получавший пятерке на уроках математики в школе и на экзаменах в институте и даже выигрывавший кой-какие мат.олимпиады для нематематиков. Для меня математика - поваренная книга, позволяющая найти решение по возможности не думая.
Поэтому у нас кардинальная разница в подходах.
номер сообщения: 49-47-10690

28

Grigoriy

22.03.2015 | 05:08:35

все его сообщения:
за день, за месяц,
за все время
Да никакой разницы :-) Я ведь сказал, что тоже решал сначала в лоб, и только потом, зная, что простое решение существует, стал его искать.
номер сообщения: 49-47-10691

29

jenya

не то, чтобы очень
но и не так, чтобы совсем не

22.03.2015 | 05:52:24

все его сообщения:
за день, за месяц,
за все время
Grigoriy: А вот "правильное" уравнение, выводимое и решаемое в уме без проблем:

3*500 = s+300

У меня пошло тяжелее: получив инструкцию решать в уме, я отправился в душ и после мучительных раздумий решал уравнение

3*[(ширина - 500) - 500] = [(2*ширина - 300) - (ширина + 300)]
номер сообщения: 49-47-10692

30

FIBM

22.03.2015 | 11:34:11

все его сообщения:
за день, за месяц,
за все время
Grigoriy: Да никакой разницы :-) Я ведь сказал, что тоже решал сначала в лоб, и только потом, зная, что простое решение существует, стал его искать.

Мне кажется, что разница есть. Для "некоторых" самое важное в этой задаче увидеть, что путь пропорционален скоростям лодок, после этого получить равенство для отношения путей пройденных до встреч. А вот как решить это равенство-некрасиво, "в лоб" или с помощью "трюка" (прибавив единицу к обеим частям равенства)-дело десятое. Для других "этот трюк"-самое главное в этой задаче. Но, в любом случае задача симпатичная, спасибо.

Что по поводу "детской задачи Синая" из фильма представленного jenya?
номер сообщения: 49-47-10693

31

Roger

22.03.2015 | 17:21:10

все его сообщения:
за день, за месяц,
за все время
У меня правильное уравнение выглядит, как 1000 = s - 200

Для этого надо отмотать на одну встречу назад. За время от "нулевой" до первой встречи одна из лодок прошла 1000 м, а от первой до второй - (s - 500 + 300).

Правду сказать, решал я во сне, а во сне линейные уравнения идут тяжелее, чем наяву квадратные.
номер сообщения: 49-47-10694