Сегодня три человека, не сговариваясь, прислали мне ссылку на очередную статью, автор которой утверждает, что нашел алгоритм решения NP-трудных задач. Свое мнение по поводу P=NP статей я высказывал 13 лет назад, сейчас я, может быть, высказывал бы его не в таких жестких терминах, но по сути ничего не поменялось ( Read more... )

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

Каждому программисту известно, что такое регулярные выражения. Каждому человеку, прошедшему базовый курс CS, известно, что базовые регулярные выражения (без backtracking-а) хорошо моделируются недетерминированными конечными автоматамиВ интересах этой записи ( Read more... )

Факт, который я для себя открыл совсем недавно (непонятно, почему в университете об этом как-то умалчивали ( Read more... )

Подскажите, если кто знает, буду благодарен ( Read more... )

Я закончил мехмат примерно 11 лет назад. Не знаю, как сейчас, но в 2002 году весь наш выпуск заботил совершенно практический вопрос: зачем стране 400 математиков в год, и чем мы все будем заниматься через несколько месяцев? Понятно, что какие-то варианты были тогда, как есть они и сейчас, но ощущение глобальной недосказанности присутствовало ( Read more... )

Перечитываю сейчас очень хорошую книжку К.Ю. afranius Еськова "История Земли и жизни на ней" (ещё существует её альтернативное издание с устрашающим названием "Удивительная палеонтология" и с выдернутой из контекста как-бы-креационистской цитатой на обложке). Хотя она и маскируется под школьный учебник для продвинутых школьников, уровень изложения совсем ( Read more... )

Была такая замечательная страна - Венецианская республика. Очень богатое и влиятельное государство, существовавшее тысячу лет и построившее ту самую Венецию, которой восхищаются поэты ( Read more... )

dfyz пишет:

Придумал прикольную алгоритмическую задачку для собеседования. В pairs лежит массив пар строк, надо написать функцию FindGluingSequence(), возвращающую массив gluingSequence, на котором CheckAnswer(pairs, gluingSequence) вернёт True. Если такого массива не существует, то вернуть None. Чтобы было понятнее, в исходнике есть пара примеров ( Read more... )

802_11 попросила такие же тексты, как про бозон, только про матстатистику и теорвер. К сожалению, о них я знаю больше, чем об элементарных частицах, поэтому писать гораздо сложнее ( Read more... )

(извините все, кому будет непонятно)

There is a deterministic algorithm for B2-formula-SAT which runs in time 2(1-μc)n on formulas of size at most cn. Here μc > 0 is a constant only depending on cЧто-то я полностью пропустил эту ветвь исследований (в статье ещё довольно много ссылок на аналогичные результаты), а ведь это же не шутка: грубо говоря ( Read more... )