Quite a bit

Friday, 4 February 2011 22:16
skiminok: (Default)
Выдержка из одного эдиториала TC.

We then need to count the number of maximum matchings in this graph, and then we're done. Unfortunately, this is a #P-complete problem, and if we can solve it in polynomial time, we would have proved that P = NP. That would make this problem quite a bit trickier than the usual Division 1 Medium.

Слова, вынесенные в заголовок, отправили меня ржать под стол :D Почти буквально)
skiminok: (xkcd)
Давайте рассмотрим все алгоритмы, существующие на свете, и попытаемся узнать, можно ли автоматически, с помощью машины (т.е. опять же алгоритма) отвечать на какие-то вопросы, касающиеся тех или иных алгоритмов.

Рассмотрим два алгоритма и . Назовем их эквивалентными, если на одном и том же входе они оба либо не останавливаются, либо выдают один и тот же ответ.

Любой алгоритм имеет текст. Текст алгоритма — строка в некотором ограниченном алфавите. Так что мы можем выписать все строки, которые существуют в этом алфавите (например, в лексикографическом порядке), этих строк счетное число, и можно пронумеровать их последовательно натуральными числами. Некоторые из этих строк представляют собой корректные алгоритмы, остальные же — "не компилирующиеся" — будем считать алгоритмами, которые всегда зацикливаются. Итак, каждый алгоритм получил свой уникальный номер.

Рассмотрим некоторое числовое множество . Назовем его инвариантным, если выполняется следующее свойство: номера любых двух эквивалентных алгоритмов либо оба лежат в , либо оба не лежат в нем.
Например, множество "Алгоритмы, которые на входе 1 выдают 39" — инвариантно. Аналогично инвариантными являются множества "Алгоритмы, которые останавливаются хоть на каком-нибудь входе", "Алгоритмы, которые возвращают только четные числа", "Алгоритмы, которые никогда не зацикливаются" и так далее.

Фактически, понятие инвариантного множества можно представлять как некоторое свойство алгоритма. Причем мы берем только свойства, характеризирующие алгоритм как класс — зависящие от его входа, выхода и факта конечного времени работы. Например, множество "Алгоритмы, выполняющие ровно 42 шага" — не инвариантно.

Очевидно, если множество — инвариантно, то его дополнение также инвариантно.

Множество называется разрешимым, если для него можно построить разрешающий алгоритм , который для любого числа на входе всегда останавливается и выдает 1, если , и 0, если .
Простой пример разрешимого множества — простые числа. Сюда же относятся четные числа, любые конечные множества, все множество , и еще многие различные примеры. Существуют также неразрешимые множества, но в данном посте этот вопрос затрагивать не стоит.

Множество называется перечислимым, если для него можно построить полуразрешающий алгоритм , который принимает на вход число , и возвращает 1, если , в противном же случае () — зацикливается.
Понятно, что любое разрешимое множество является перечислимым: разрешающий алгоритм легко превратить в полуразрешающий, добавив ему в конец вечный цикл вместо возвращения значения 0. Гораздо интереснее вопрос "Существует ли перечислимое неразрешимое множество?" Правильный ответ — да, существует, и не одно, однако построение конкретных примеров тоже выходит за рамки данного поста.

Теорема Райса (в некоторых редакциях теорема Успенского-Райса) утверждает поразительный факт:
Любое нетривиальное свойство алгоритма является неразрешимым.
Иными словами:
Если некоторое инвариантное множество разрешимо, то имеет место либо , либо .

Доказательство )
Таким образом, принципиально невозможно построить такую среду/оболочку/систему/IDE, которая по коду данного ей произвольного алгоритма будет автоматически определять, справедливо ли для него какое-то специфическое свойство, каким бы простым и очевидным это свойство ни было. В частности, неразрешима так называемая проблема останова — не существует алгоритма, который по коду другого алгоритма и входному числу определил бы, остановится ли на входе .

Примечательно, что огромное количество программистов, в глаза не видевших никогда теорию алгоритмов и theoretical computer science, свято уверены, что любую задачу на свете можно решить и запрограммировать, были бы время и ресурсы.

Если бы.
skiminok: (xkcd)
Открылся Q&A сайт по theoretical computer science. Давайте сделаем этот сайт местом, где можно обсудить интересные вопросы с умными людьми. :)

via [livejournal.com profile] ilyaraz

skiminok: (xkcd)

Повторяя прочитанный у Евгения [livejournal.com profile] antilamer Кирпичева материал про свертки, залез попутно в область, которую я пока не покрывал: префиксные суммы, сегментированные пробеги, и их связь со сверткой. И обнаружил там весьма занимательный для функциональщика алгоритм для построения выпуклой оболочки под названием Quick Hull. Короткую его реализацию с помощью сегментированных пробегов я пока оставил до лучших времен, а вот простой наивный перевод на F# определения алгоритма у Кирпичева почему бы и не сделать.

Тем более что получается это очень просто. Весь код помещается в пределах одного экрана. Вроде бы без багов :)

UPD: Поубирал все явные декларации типов в функциях алгоритма. Компилятор F# умный, сам все выводит.


type Point =

    { x: float; y: float; }

    static member (<) (a: Point, b: Point) =

        (a.x < b.x) || (a.x = b.x && a.y < b.y)

    static member (-) (a: Point, b: Point) =

        { x = a.x - b.x; y = a.y - b.y }

    static member (^^) (a: Point, b: Point) =

        a.x * b.y - b.x * a.y

    override this.ToString() =

        sprintf "(%f, %f)" this.x this.y

 

type Segment = { start: Point; finish: Point }

 

let quickHull points =

    let rec hullStep line = function

        | [] -> [line.start; line.finish]

        | points ->

            let p, q, PQ = line.start, line.finish, line.finish - line.start

 

            let distKey a = (p - a) ^^ (q - a)

            let a = List.maxBy distKey points

            let AP, AQ = (p - a), (q - a)

 

            let besidesP x = (AP ^^ PQ) * (AP ^^ (x - p)) < 0.0

            let besidesQ x = (AQ ^^ (x - q)) * (AQ ^^ PQ) > 0.0

            let pointsOfP = List.filter besidesP points

            let pointsOfQ = List.filter besidesQ points

 

            let ansP = hullStep {start = a; finish = p} pointsOfP

            let ansQ = hullStep {start = a; finish = q} pointsOfQ

            ansP @ ansQ

 

    let p, q = List.min points, List.max points

    let PQ = q - p

 

    let upper (x: Point) = PQ ^^ (x - q) > 0.0

    let lower (x: Point) = PQ ^^ (x - q) < 0.0

    let upPoints, downPoints = List.filter upper points, List.filter lower points

 

    let ansUp = hullStep {start = p; finish = q} upPoints

    let ansDown = hullStep {start = q; finish = p} downPoints

    ansUp @ ansDown |> Set.ofList |> Set.toList

 

let example = [ { x = 0.0; y = 0.0 };

                { x = 0.0; y = 1.0 };

                { x = 1.0; y = 1.0 };

                { x = 1.0; y = 0.0 };

                { x = 0.5; y = 0.8 } ]

let hull = quickHull example

skiminok: (xkcd)
Всем читателям, кто еще не знаком, рекомендую замечательный блог Эрика Липперта — одного из главных разработчиков компилятора Microsoft Visual C# и собственно стандарта языка C#. (У кого напряги с инглишем — есть русский перевод, правда, он тормозит на три месяца =).

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

UPDATE: My close personal friend (and fellow computer geek) Jen notes that in the Twilight series of novels, the so-called "werewolves" (who are not transformed by the full moon and therefore not actually werewolves) maintain their rigid social ordering in both wolf and human form; the projection from human to wolf is covariant in the social-ordering relation. She also notes that in high school, programming language geeks are at the bottom of the social order, but the projection to adulthood catapults them to the top of the social order, and therefore, growing up is contravariant. I am somewhat skeptical of the latter claim; the former, I'll take your word for it. I suppose the question of how social order works amongst teenage werewolves who are computer geeks is a subject for additional research. Thanks Jen!

Вот так концепции ФП незаметно втираются в нашу повседневную жизнь. Да, девочкам-фанаточкам Сумерок — привет ;)
skiminok: (Default)
Я теперь счастливый обладатель двух культовых трудов:

   


Сезон мозголомства можно считать торжественно открытым.

А ещё в субботу я эпически зафейлил второй раунд CodeJam`a. Собственно, я ничего другого и не ожидал, но всё-таки немного обидно.
skiminok: (Default)
Немного про L-грамматики. Это потрясающе.
(мотороллер не мой)

Profile

skiminok: (Default)
skiminok

Most Popular Tags

July 2011

S M T W T F S
     12
3456789
10111213141516
17181920212223
242526272829 30
31      

Syndicate

RSS Atom