September 14th, 2010

moose, transparent

одним махом пятерых побивахом (комп.)

A critical vulnerability exists in Adobe Flash Player 10.1.82.76 and earlier versions for Windows, Macintosh, Linux, Solaris, and Adobe Flash Player 10.1.92.10 for Android.

Никогда еще не видел эксплойт для столько разных ОС одновременно. Спасибо, Адоби.

Хочется, чтобы поскорее уж наступило то светлое будущее, в котором мы забудем, как кошмарный сон, это под завязку набитое багами, падениями и эксплойтами порождение криворуких садистов под названием "Флэш".
moose, transparent

раскраска дороги (математическое)

(эта запись может быть интересна читателям с познаниями в математике и сочувствующим)

На днях я прочитал о интересной задаче из теории графов - гипотеза о раскраске дороги. Эта гипотеза была открытой в течение 37 лет, но три года назад ее доказал израильский математик Авраам Трахтман. Доказательство оказалось довольно элементарным, и с некоторыми сложностями (поскольку мозги атрофировались) я смог его прочитать и понять, и даже попробую в этой записи объяснить.

Задачу можно объяснить на таком примере. Представьте себе карту города, на которой на каждом перекрестке можно поехать в одну из четырех сторон - на север, юг, восток и запад. Если машина начинает с какого-то перекрестка и следует по какому-то списку указаний - "север, север, восток" итд. - то она приедет в итоге на какой-то другой перекресток. Можно ли найти такой список указаний, возможно длинный, который приведет машину в одно и то же место, независимо от того, где она начала? Если карта выглядит как Манхэттен - регулярная решетка - то нет, но может, в ней есть много тупиков и неожиданных поворотов?

Или другой пример. Ваш друг застрял в лабиринте, в котором нужно найти центр, и позвонил вам с просьбой помочь. Вы знаете, как устроен лабиринт, но не знаете, где ваш друг. Может ли быть такая последовательность команд, которая точно приведет вашего друга в центр, где бы он ни был?

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

В общем случае, пусть есть направленный граф G - с ребрами-"стрелками" между вершинами. Пусть у этого графа есть равномерная исходящая степень d - это значит, что из каждой вершины выходит ровно d ребер. Входить при этом в каждую отдельную вершину может разное количество, необязательно d. Пусть у нас есть набор из d букв какого-то алфавита, которые мы будем называть "цветами". Тогда "раскраска" графа задается назначением для каждой вершины всех d букв для d ее исходящих ребер. Так что если мы "находимся" в какой-то вершине, и хотим "пойти" куда-то согласно цвету α, то раскраска всегда скажет нам, по какому ребру нам надо идти к какой новой вершине. "Словом" назовем любую последовательность букв-цветов. Тогда, если в графе задана раскраска, и x - какая-то вершина, а w - какое-то слово, то xw обозначает вершину, к которой мы придем, начиная с x и следуя слову w.

Раскраска называется синхронизирующей, если существует такое слово w, которое любую вершину x приводит к одной фиксированной вершине x0. В этом случае w называется синхронизирующим словом. Вопрос, который задает проблема раскраски дороги: всегда ли существует синхронизирующая раскраска? Всегда ли можно так раскрасить ребра графа, чтобы можно было свести все вершины к одной? Collapse )