Задача о четырех красках

Новости математики. Задачи и головоломки.

Задача о четырех красках

Сообщение Oleg » Вс апр 01, 2012 12:21 am

Задача о четырех красках

Можно ли области любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?
Аватара пользователя
Oleg
Администратор
Администратор
 
Сообщения: 49960
Зарегистрирован: Вс окт 09, 2005 9:08 pm
Откуда: Москва
Медали: 10
Пол: Мужской
Соционический тип: Бальзак
Тип по психе-йоге: Сократ (ВЛЭФ)
Темперамент: Флегматик
Профессия: Программист, оптимизатор

Задача о 4 красках

Сообщение Oleg » Вс апр 01, 2012 12:27 am

ТЕОРЕМЫ ЧЕТЫРЕХ КРАСОК

Доказательство Аппеля и Хакена, в целом хотя и принятое математическим сообществом, вызывает до сих пор определенный скептицизм. Для читателя, поверхностно знакомого с математикой, предыдущая фраза должна вызвать изумление: а как же обязательный для математики принцип исключенного третьего, в соответствии с которым утверждение либо справедливо, либо нет? Дело обстоит не так просто. Вот что пишут сами авторы доказательства: "Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно".

Говоря прямо, компьютерную часть доказательства невозможно проверить вручную, а традиционная часть доказательства длинна и сложна настолько, что ее никто целиком и не проверял. Между тем доказательство, не поддающееся проверке, есть нонсенс. Согласиться с подобным доказательством означает примерно то же, что просто поверить авторам. Но и здесь все сложнее.

Вернемся сначала к доказательствам формулы Эйлера и теоремы о 5-раскраске. Ее-то вроде бы нетрудно проверить, взяв лист бумаги и карандаш. Но рассуждения в ней основаны на очевидных соображениях типа: "Плоский граф разрезает плоскость на совокупность D(G ) неперекрывающихся многоугольных областей". Между тем это утверждение не принадлежит к числу аксиом или школьных теорем плоской геометрии, и его нужно доказывать. Соответствующая теорема, сформулированная К. Жорданом, доказывается очень непросто, однако основные трудности связаны с тем, как следует понимать слова типа "разрезает", интуитивно вполне ясные, но с трудом поддающимся формализации. В свете этого замечания становится уже не совсем понятным, доказана ли теорема о пяти красках или мы поверили правдоподобным рассуждениям, основанным на интуитивных представлениях о свойствах геометрических фигур.

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

Трудно даже вообразить длину полного вывода теоремы о пяти красках в соответствии с современными стандартами математической логики и системы аксиом геометрии. Но совершенно точно, что такое рассуждение никто никогда не проделывал из-за бесполезности этого занятия: формальные выводы практически не поддаются проверке в силу свойств человеческой психики: помимо их гораздо большей (по сравнению с привычными рассуждениями) длины их сознательное усвоение идет гораздо медленнее. Поэтому обычно удовлетворяются уверенностью в том, что формальный вывод возможен в принципе.

В формуле Эйлера, например, математики не сомневаются. Вообще принятие доказательства есть некий социальный акт. Выдающийся алгебраист Ю.И. Манин в своей книге "Доказуемое и недоказуемое" [6] пишет по этому поводу: "_отсутствие ошибок в математической работе (если они не обнаружены), как и в других естественных науках, часто устанавливается по косвенным данным: имеют значение соответствие с общими ожиданиями, использование аналогичных аргументов в других работах, разглядывание "под микроскопом" отдельных участков доказательства, даже репутация автора, словом, воспроизводимость в широком смысле. "Непонятные" доказательства могут сыграть очень полезную роль, стимулируя поиски более доступных рассуждений."

Именно такая история происходит и с доказательством теоремы о четырех красках. Не так давно появилось новое доказательство (см. [5], где изложены основные идеи), причем та часть, которая выполнена не на компьютере, уже поддается проверке. Однако компьютерная часть все еще остается скорее предметом веры. Ведь даже проверка распечаток всех программ и всех входных данных не может гарантировать от случайных сбоев или даже от скрытых пороков электроники (вспомним, что ошибки при выполнении деления у первой версии процессора Pentium были случайно обнаружены спустя полгода после начала его коммерческих продаж - кстати, математиком, специалистом в теории чисел). По-видимому, единственный способ проверки компьютерных результатов - написать другую программу и для другого типа компьютера. Это, конечно, совсем непохоже на стандартный идеал дедуктивных рассуждений, но именно так осуществляется проверка утверждений во всех экспериментальных науках.

Из которых математика, стало быть, исключена напрасно.

http://www.pereplet.ru/obrazovanie/stsoros/1062.html
Аватара пользователя
Oleg
Администратор
Администратор
 
Сообщения: 49960
Зарегистрирован: Вс окт 09, 2005 9:08 pm
Откуда: Москва
Медали: 10
Пол: Мужской
Соционический тип: Бальзак
Тип по психе-йоге: Сократ (ВЛЭФ)
Темперамент: Флегматик
Профессия: Программист, оптимизатор

Задача о 4 красках

Сообщение Oleg » Вс апр 01, 2012 12:31 am

О доказательстве

К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница), впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок[1]. Проблема четырёх красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

Новое доказательство, основанное на алгебраических и топологических методах, дал индийский математик Ашей Дарвадкер[2] в 2000 году.

Наиболее известные попытки доказательства:

Альфред Кэмпе предложил доказательство в 1879[3], его опровергли в 1880, на основе его идей удалось доказать, что любую карту можно раскрасить в 5 цветов.
Питер Тэт предложил другое доказательство в 1880[4], его опровергли в 1891.
В своей книге[5] В. А. Горбатов утверждает, что предложил классическое доказательство ещё в 1964 (объёмом около 30 стр.). Однако опровержений, как и подтверждений, это доказательство пока не получило, см. также[6].

Подробнее http://ru.wikipedia.org/wiki/%D0%9F%D1% ... 0%BE%D0%BA
Аватара пользователя
Oleg
Администратор
Администратор
 
Сообщения: 49960
Зарегистрирован: Вс окт 09, 2005 9:08 pm
Откуда: Москва
Медали: 10
Пол: Мужской
Соционический тип: Бальзак
Тип по психе-йоге: Сократ (ВЛЭФ)
Темперамент: Флегматик
Профессия: Программист, оптимизатор


Вернуться в Математика

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

Зарегистрированные пользователи: Алексище, den4ik228, Exabot [Bot], Google [Bot], Google Adsense [Bot], Oliwer, TailWind, Yandex 3.0 [Bot], Yandex [Bot], Кошка Почемучка