2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение27.10.2012, 22:32 
Думаю, что нет. Как именно доказывать?

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение27.10.2012, 22:45 
Аватара пользователя
Aleksand в сообщении #636682 писал(а):
Как именно доказывать?

Для начала попробуйте доказать, что достаточно конечное число красок. (Число не зависит от карты).

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение27.10.2012, 22:55 
Ну пять-то красок хватит. Причём сам доказал, без чьей-либо помощи.

-- 28.10.2012, 00:19 --

Это с чего это Вы взяли, что "число цветов не зависит от карты". Есть 4-х цветные карты. Возможно, что при большом числе стран буду 5-цветные карты. Далее 6-и, 7-и, 8-и цветные.

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 00:03 
Aleksand в сообщении #636691 писал(а):
Ну пять-то красок хватит.
Aleksand в сообщении #636691 писал(а):
Далее 6-и, 7-и, 8-и цветные.
Противоречие.

 
 
 
 Posted automatically
Сообщение28.10.2012, 00:22 
Аватара пользователя
 i  Тема перемещена из форума «Дискуссионные темы (Ф)» в форум «Computer Science»

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 00:26 
Это и есть доказательство "от противного". Правильно. Это противоречие. Шестицветных карт не бывает. А из пятицветных сразу семицветные не получатся.

-- 28.10.2012, 01:50 --

Ещё уточню свой вопрос. Я его уже задавал на другом форуме, и мне ответили, что было доказано, что если все карты с числом стран, скажем, менее 10 000 окрашиваются в 4 цвета, то при большем числе стран пятицветных карт уже не будет. Вот на компьютере перебрали карты до 10 000 стран, пятицветных там не оказалось, а значит их нет вообще.

От такого доказательства у меня волосы дыбом встали.

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 01:07 
Aleksand в сообщении #636711 писал(а):
От такого доказательства у меня волосы дыбом встали.
Странно. Доказательства с проверкой двух-пяти альтернативных вариантов ничем качественно не отличаются от доказательств с проверкой миллиарда вариантов.

(Внимание!)

Aleksand в сообщении #636711 писал(а):
доказательство "от противного"
Кавычки лишние.

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 01:21 
Я не знаю что такое "доказательства с проверкой двух-пяти альтернативных вариантов".

(Оффтоп)

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

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 02:20 
Aleksand в сообщении #636715 писал(а):
Я не знаю что такое "доказательства с проверкой двух-пяти альтернативных вариантов".

Ваше невежество ничего не меняет: доказательство путем полного перебора ничем не хуже любого другого в плане строгости.

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 02:40 

(Оффтоп)

Nemiroff в сообщении #636718 писал(а):
доказательство путем полного перебора ничем не хуже любого другого в плане строгости.

Да. Но, вообще-то, если количество вариантов необозримо и перебирает компьютер (как в случае проблемы 4-х красок), то хуже. Так как мы никогда не можем быть уверены в компьютере (даже если реализовать несколько различных алгоритмов на нескольких компьютерах различной архитектуры).

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 05:33 
longstreet в сообщении #636720 писал(а):
Nemiroff в сообщении #636718 писал(а):
доказательство путем полного перебора ничем не хуже любого другого в плане строгости.

Да. Но, вообще-то, если количество вариантов необозримо и перебирает компьютер (как в случае проблемы 4-х красок), то хуже. Так как мы никогда не можем быть уверены в компьютере (даже если реализовать несколько различных алгоритмов на нескольких компьютерах различной архитектуры).

Ах, вон Вы про что. Я не сомневаюсь что компьютер правильно расчитал варианты. Просто теорема будет доказана только для карт с числом стран менее 10 000.

-- 28.10.2012, 07:32 --

Меня бы устроило, если бы доказывающий сказал примерно так:
Вероятность появления 5-цветной карты с увеличением числа стран не увеличивается, а уменьшается. Причём не стремится к нулю, а в точке 10 000 точно равен нулю. А дальше график пересекает ось абсцисс и уходит вниз. То есть нет смысла рассматривать все карты. Достаточно рассмотреть карты с числом стран менее 10000. А это можно перебрать на компьютере. И если ничего не найдём, то дальше там ничего не будет.
Но как расчитать вероятность появления 5-и цветной карты, если их никто не видел? Да так ли это? С увеличением числа стран трудность раскраски карты увеличивается. Поэтому и возникла эта задача.
Вот я и хочу спросить, куда же можно приспособить этот компьютер? Что им перебирать?

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 11:45 
Так вы почитайте доказательство. (Или хотя бы о нём в нормальном источнике.) Естественно, прежде чем предлагать алгоритм перебора, доказывается, что достаточно перебрать лишь некоторые типы карт (которых конечное число) $-$ и это существенная часть всего доказательства.

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 13:43 
Да нет у меня "нормальных" источников. Я не предлагаю алгоритма перебора. Это просто мои предположения. А вот то, что достаточно перебрать только часть вариантов... А вот с этим я не очень согласен...

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 13:44 
Aleksand в сообщении #636842 писал(а):
А вот то, что достаточно перебрать только часть вариантов... А вот с этим я не очень согласен...

Вы что, не слышите?
longstreet в сообщении #636778 писал(а):
доказывается, что достаточно перебрать лишь некоторые типы карт (которых конечное число) и это существенная часть всего доказательства.

Как вы можете быть не согласны с доказательством, если вы с ним не разобрались? :shock:

-- 28.10.2012, 13:49 --

Материала полно (кликните; если не ошибаюсь, то что вас интересует - изложено в главе Reducibility). Может, и на русском полное изложение идеи доказательства есть $-$ не знаю.

 
 
 
 Re: Возможно ли доказать теорему о 4-х красках при помощи компью
Сообщение28.10.2012, 17:27 

(Ещё одно уточнение.)

Aleksand в сообщении #636715 писал(а):
Теорема либо доказана, либо недоказана, либо её невозможно доказать. И всякие альтернативы неуместны. Во всяком случае мне такое неизвестно.
Когда теорему невозможно доказать, она одновременно не доказана (на все времена). Т. е. из ваших «альтернатив» в конкретное время реализуется либо первая, либо вторая, либо третья и вторая вместе — надо было их немного переформулировать.

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group