Всем привет!

Думаю, многие из вас слышали о проблеме четырех красок. Это известная теорема, которую не могли доказать более ста лет.

Историю ее доказательства я много раз слышал в научно-популярном изложении, но глубоко не вникал в математические детали.

Мне стало интересно разобраться, как именно доказывал эту теорему Кемпе, какой контрпример нашел Хивуд и как в итоге устроено компьютерное доказательство Аппеля и Хакена.

Я не нашел достаточно подробного изложения на русском языке, поэтому взял книгу Робина Уилсона «Four Color Suffice», узнал из нее все, что мне было интересно, и кратко пересказал это для вас. Большинство иллюстраций в статье взято из этой книги.

Приятного чтения!

Если вы не знаете, что такое префикс-функция строки, не знаете, как она вычисляется, или, что самое главное, не до конца понимаете, почему алгоритм вычисления префикс-функции работает за линейное время, то эта статья для вас.

Я прошел через череду осознаний и озарений, прежде чем достичь просветления, и теперь предлагаю вам пройти этот путь вместе со мной.

12 сентября 2024 года OpenAI представила новую модель OpenAI o1-preview - первую модель, которая по утверждению создателей умеет "рассуждать".

Я решил посмотреть, насколько хорошо она умеет отвечать на вопросы из игры "Что? Где? Когда?"