Криминальная хроника

На юго-западе Москвы совершено дерзкое ограбление. В результате перестрелки убит инкассатор Банка Данных. Нападавшие использовали недетерминированные конечные автоматы и скрылись на машине Тьюринга. Похищено 140 ТБайт информации. Суммарный ущерб оценивается в 10-12 человеко-лет работы. Ведется следствие.

Журналисты уже окрестили это происшествие как Millenium Problem и относят его к NP-сложным. Разрешившему это дело оперативнику достанется ACM Award.

ГУВД г. Москвы и Московский уголовный розыск направили лучшие команды оперативников на разрешение данного происшествия. Этими командами не более чем полгода назад были разрешены BPP-трудные происшествия "ограбление коммивояжера с рюкзаком на складе" и "труп китайского почтальона в кососимметричном графе".

По оперативной информации, найдены гильзы от автомата с магазинной памятью и от недетерминированного конечного автомата калибра $6/\pi^2$. Стрелявшие скрывались за B-деревом и за бором из деревьев Штейнера.

Судя по следу матрицы протектора, оставленного на непрерывно дифференцируемой поверхности, машина нападавших принадлежит классу универсальной машины Тьюринга, работающей на бесконечной ленте. Следы машины уходят в поле комплексных чисел в направлении мнимой части.

Свидетелям данного происшествия просьба обратиться по адресу 0xCF65E или 0x38F. Реверсивность гарантируется.

ЗЫ. Ну не умею я писать про драконов...

Ограниченность

Что-то боянистое про Кронекера, Бога и натуральные числа (С)

Если вы экономист/юрист, то скорее всего вы ограничены знанием одной страны. В другой стране действуют другие законы, и бухгалтерия там тоже (скорее всего) отличается.

Если вы врач, то ограничены знанием в лечении людей. То есть не сможете просто так лечить инопланетян.

Если вы химик/физик, то ваши знания могут быть использованы даже на другой планете. Правда, некоторые фантасты способны придумать миры, где и физика и химия будет другой (например, Азимов,  "Сами Боги"). Да и гарантировать, что физика/химия одинакова во время жизни вселенной я не могу. Некоторые утвержают, что скорость света в первые секунды жизни вселенной была другой, химия там еще не действовала.

А вот если вы математик, то я что-то не могу придумать мир, где бы не было натуральных чисел (и всего остального по Кронекеру). Может быть другой мат. анализ, тер. вер - тут все зависит от физического мира, будет ли он дискретным/непрерывным, потенциально_бесконечным и прочее. Будет ли там число \pi, \e, будет ли окружность, точка и линия?

Может быть нетрадиционная алгебра, неклассическая логика, и даже неевклидова геометрия. Хотя вопрос, может там вообще не будет геометрии и алгебры. Хотя, что такое алгебра? Что-то из базовой логики/формальных систем обязательно должно быть. Ну и натуральное число. Наше все (или таки от Бога?).

Возможно, мирок даже будет без вычислителей. Так что программисты тоже зависят от вселенной.

Хотя минимальный мир - синглетонизм. Есть один объект, и более ничего. Выделим слово *один*. Можно завернуть в пустое множество, но тут опять всякие непонятные вещи (неформального) уровня, что множество как совокупность объектов. А зачем нам новая сущность, если объект только один?.. Под объектом тоже можно скрыть *ничего*. Есть ничего. Это гораздо сильнее чем, ничего нет (а в английском это одна фраза). Оно все таки есть, конструктив, однако.

Меня заносит. Если ничего нет (или даже есть ничего), то все очень скучно. Ладно, я требую оставить натуральные числа. А потом что-нибудь придумаем...

В начале было Слово, и Слово было у Бога, и само оно было Богом. (С) Библия, префикс.
Сложно получается. Пусть у нас еще есть натуральные числа. Их же называть надо... То есть еще сущность - Слово. Называть кем и для кого, это есть субъект/интерпретатор.

Трудно быть Богом, это даже не по Стругацким... Реально сложно.

Вызга монос

Есть несколько классических задачек на рекурсивную логику.

Загадано число N (N >= 2). Одному человеку сообщается N + 1, другому N - 1. Между ними происходит следующий диалог:

- Я не знаю, что это за число.
- Я не знаю, что это за число.
...
- Я не знаю, что это за число.
- Я знаю, что это за число.

В зависимости от вариации задачи, люди (не)?знают, что им сообщили (N + 1 или N - 1).
Длина диалога внезапно равна N (+-1). Надо моделировать на малых числах и курить. А то, если N велико, трудно понять, что же нам дает не знание собеседника.

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

Эта задача была на полуфинале где-то в 2003/2004. На тренировке мы до нее не дошли, другой халявы было предостаточно.

А есть еще класс задач с шапочками, где какой-либо злодей надел на (пусть) гномов шапочки двух цветов, причем известно что есть оба цвета. Все гномы видят цвет всех, кроме себя. Им нужно к 22:37 определить, какой же у них цвет шапочки. Иначе смерть, ипотека, жена_трое_детей.

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

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

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

ЗЫ. Бывают какие-то моменты времени, что мне кажется, что я эти задачки понимаю. Как любят говорить математики, множество меры 0 (про время). В остальные моменты времени я думаю так: "блин, тут же все просто должно быть, я ж это понимал." Сидишь и гошешь челову, при условии что весь вызг монесен.

math

С импортного:

polymath - эрудит

aftermath - последствия

Других префиксов пока не знаю.

Говорят (сошлемся на Арнольда), что слово "математика" переводится только с голландского. В остальных языках оно откуда-то взаимствовано и в итоге отсыл к гречке.

Конкурс "рекурсивный твит"

Не можешь чего-то достичь - организуй конкурс.
(С) Не я

Не можешь организовать конкурс - организуй конкурс по организации конкурса.
(С) ам дошел.

Задача - создать рекурсивный твит. То есть твит, который ссылается сам на себя. Желательно с содержанием "@%user_name% ты не прав" (с точностью до языка, перестановки слов и пола).

Технические особенности: понятно что твиты немутабельны. В этом и фишка, идет поток в 2000 твитов в секунду и надо как-то угадать его идентификатор. 18-ти значный. Это при условии что вы изучите api какого-нибудь клиента и разберетесь в протоколе reply-ответа. xss и injection хаки допустимы :) если сможете пройти фильтр твиттера.

Два очевидных неудавшихся примера:
http://twitter.com/#!/ajtkulov/status/148478238165958656

http://twitter.com/#!/ajtkulov/status/148479219964448768

ЗЫ. Конкурс посвящается Гёделю, а так же первому греку, кому в голову пришла фраза "я - лжец", изобретателю Уробороса и всем остальным из данной сферы. Без вас мир был бы скучнее.

Если же вам каким-либо неведомым образом это удастся - свяжитесь со мной (Приз - шоколадка).

К участию в конкурса не допускаются работники Twitter ltd, а так же лица, родившиеся 31 сентября 1979 года.

Любопытнее

Curiouser and curiouser
Alice in W.

Живешь себе, никого не трогаешь. А тебе говорят, что Эратосфена можно делать за линию. А ты не веришь, жил себе, никого не трогал. Не веришь, но любопытно. Как же так, ведь ты никого не трогал?! А тебе дают ссылку на статью 1978 года, блин 33 года назад. Как же ты вообще жил..?

И в самом деле, все оказывается тривиально. Так же тривиально, как Эратосфен с непонятным логарифмом. Даже до некоторого момента времени, Эратосфен казался медленнее чем тривиальное деление. И жили же тогда люди. А потом оказывается, что что-то непонятное быстрее и почему-то является log log n. Непонятно, но верим.

А тут линия, и на второй день становится все понятно, честная линия. Становится только не понятно, как же ты сам до этого не дошел? Видимо, никого не трогал.

Все любопытнее...

ЗЫ. David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]

Статистика в Вконтакте

Среднестатистический пользователь той самой соц.сети (какой-то брат великого Николая Дурова) в среднем обновляет аватарку, добавляет фотки с отпуска и ставит сердечки на чужих аватарках и фотографиях с отпуска.

Но только у асм-щиков в заметках можно найти обсуждение порядковой статистики, где для балансировки дерева используется информация о количестве в поддереве. Статья какого-то китайца от 2006 года. Внезапно, но китаец лет за 20 смог просечь эту фишку, а все говорят что возьмем сбалансированное дерево и расширим узел информацией о количестве узлов в поддереве.

На премию Тьюринга не хватит, но за идею я "сердечко" бы плюсанул :) .

update: плюсанул сердечко :)

Деревья

Буратино был тупой... (С)

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

Интересно, много ли существует людей, таких как я, которые подходят к окну и говорят: "Бля, и тут дерево". Они не бинарные - они зеленые.

Мне говорили, что существует болезнь излишнего использования паттерна сиглетон - называется "Синглетонизм". Видимо, мой случай назовут "массивный дендризм".

По смыслу я везде должен видеть массивы, но смотря на все через логарифмические очки ( * log(n) диоптрий) везде вижу деревья.

Интересно, пойдет ли в зачет кубка Дерево/Дом/Сын такие деревья? Хотя на огороде есть несколько моих инстансов деревьев, да и домик я требую засчитать, с сыном надо осторожнее. Это вам не 2-3-дерево.

Краткость

Тут недавно взяли на слабо. Задача почти стандартная, известная как K Problem + большая грамматика.

Далее "моя" реализация. "Моя" - потому что я заиспользовал комбинаторы.

Парсер комбинаторы - круто. Смотрим и писаем кипятком кончаем наслаждаемся.

Эта часть легко находится по подстроке "-- Carsten Schuermann: From: Monadic Parser Combinators [Hutton, Meijer]"


Тут пока некоторая магия, в которую за 5 минут не въехать. Далее должно быть понятнее.

AST - это или ссылка на ячейку, или число, или бинарный оператор из AST.
Вводим парсер для AST. Опишем стандартные арифметические операторы.

А теперь *барабанная дробь*



Собственно все, парсер (лексер + синтАнализатор) готов.
Запускаем и оно работает.



Где вы еще сможете в 3-4Кб уложится? Это вам не парсер-генератор, здесь все сделано вручную... Правда, исходя из этого - это LL. Бывает кое-что затруднительно выразить в LL, да еще и следить за левой рекурсией. LR вручную непросто реализовать, но мне местами такая грамматика больше нравится. Есть еще всякие PEG/Packrat, с не очень понятной теорией (трудно понять, выразима ли конкретная грамматика в них), и куча непрактичных но теоретических парсеров.

Далее опишем типы для "excel". Ячейка - есть строка, лист как коллекция пар из (ячейка, строковая формула) и так далее. В идеале надо бы абстрактный маппинг (словарь/функцию) из ячейки в формулу.



Простая вычислялка AST и вычислялка для строки.



Пара тривиальных вещей:



Несколько типов для вычислителя excel-я.
EvaluatedCellBuffer - это результат вычислений. Далее его как аккумулятор и будем вычислять.



Вся логика вычислений в следующем:



Далее очевидная вода:



Вычисление одной ячейки:


Тривиальный вычислитель



Пара утилитных функций



И вычисление всего листа



Примеры листов:



И примеры:


Еще можно добавить шапочку :)


В 8Кб имеет парсер, AST, вычислитель, и обход и расчет листа excel.
Несложно расширяемо на
- функции и несложную типизацию в встроенном языке
- отказаться от дву(3 ли 3.5 как в excel) мерности задачи и перейти к произвольной размерности.

У меня в текущем проекте есть нечто похожее, но это явно не 8Кб.

ЗЫ. Научиться бы здесь нормальное форматирование делать... В процессе.

Квадратная абстракция

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

Или что-то похожее. Не хватило абстракции, и пока набираюсь сил на следующую попытку.

Алфавит конечен, но каждый следующий бор строится на основе предыдущего, где в качестве узла выступает некоторый путь в боре. И так на 3-4-5-6 и более уровней. Даже не квадрат.

Какой же чай курил Рамануджан? И мне 100 гр.

Не кинокритик

Просидел неделю на больничном. Ввиду наличия свободного времени дочитал бумажные (!) из очереди. Внезапно их оказалось целых три. Это у нас на текущей работе внезапно есть бюджет на литературу.

Заказывать можно только из местных *озонов* - поэтому ничего путного там нет. Армстронг (erlang) полгода в очереди на покупку, из классики только нашелся Майерс, но как-то он не впечатляет. Коллега (уже полгода ушел в другую компанию) по приколу заказал "The Haskell road to logic, maths and programming" (от доступных русскоязычных вариантов/переводов от Р. Душкина я отговорил, ибо видел. Хотя там главка про полиморфизм мне понравилась). Пришлось мне прочитать.

На второй странице есть подряд два предложения:

As a functional programming language, Haskell is a member of the Lisp family. Others family members are Scheme, ML, Occam, Clean.

Нельзя убивать сразу же на второй странице. Ладно, хрен с ним, что haskell отнесен к лиспанутому семейству. Даже хрен с ним, что во втором предложении они настолько круты, что отличают scheme от lisp-а (я тоже смогу отличить). Но какого, б*, они пишут Ocaml с двумя ошибками? После этого пропадает вера в адекватность.

Все таки я пересилил и дочитал до конца. Далее перлов не оказалось.

В итоге оказалось, что книжка никаким боком не про haskell. А про базовые определения из мат. логики и дискретной математики для первого курса. Ну, может и про сам язык, если вы его никогда ранее не видели.

Единственное, что вспомнил/узнал нового, так это что целые числа как классы эквивалентности на паре натуральных.

Единственное, что не понял - это в конце главка про производящие функции. Я их понимаю, максимум на два хода. Только люди с мехмата МГУ их понимаю полноценно. По крайне мере, всех кого я видел, кто понимает в производящих функциях - это с ММ МГУ.

! 2\pi

Ребус.
Отгадка: не тупи

Группа

С неделю назад понял, что мне действительно не хватает. Что объединяет суффиксный массив (как работает классическое BWT я, примерно, в курсе. Как работает динамическое BWT - пока не осилил), какой-нибудь изоморфизм графов, и мои интересы в теории чисел.

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

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

Задача, образование, математика

Лучше гор могут быть только горы,
на которых еще не бывал.
Володя.

Бессмыслица — искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет.
Аркадий и Борис С.

Что такое "решить задачу"? Является ли одной из целей образования "научить решать задачи"?

Раньше, я не знал что значит "решить задачу". Потом я услышал такое определение, как "свести задачу к уже решенным", которое мне очень понравилось. Будем считать, что первый вопрос оказался тривиальным.

Под задачей будем понимать нечто большее, чем то, что указывается в сборниках задач по физике, математике или химии.

Перейдем ко второму вопросу.
Напомним один анекдот:
- Кем Вы работаете?
- Врач-педофил.
- Вы хотели сказать врач-педиатр?
- Ну... и это тоже.

Так вот, я не являюсь ни педагогом, ни педофилом, ни (не дай Бог) педиатром.
Весь мой педиатрический педофильский опыт сводится к 30 часам со школьниками и порядка 150 часов со студентами.

Учитывая это, мое мнение о системе образование таково: школьное образование нацелено на подведение к формальным системам. Химия и алгебра очень хорошо вписывается. Есть такие-то редукционные правила, несколько аксиом. И в путь. Вам рассказывают какой-то маленький класс задач, и потом доводят до чисто-механического рефлекторного автоматизма решения этого класса. Затем следующий класс задач. Физика - все то же самое. Я там научился ставить стрелочки над векторами. И так итерируют лет десять (или уже одиннадцать). Задачи все одно-двух-трех ходовые.

Принципиально, такой предмет как геометрия мог бы быть довольно интересен в школьной программе. Но, когда я учился (и еще +- десятилетие) геометрия - та же алгебра + тригонометрия. Хоть и не "решать задачи", но можно было бы побольше усилие сделать на доказательной части. Евклидовая аксиоматика и доказательства рассматриваются как то ущербно. Я видел просто задачники и олимпиадные задачники по геометрии 30-х гг. прошлого века, там не все так тривиально как сейчас (увы, я плохо знаю историю и историю математики, но что-то у нас во время войны поломали/поломалось с геометрией. Курс школьной алгебры не так сильно изменился).

В Вузе ситуация кардинально не меняется. Идет специализация по областям, вводится абстракция. А решать задачи так и не учат.

Главный вопрос - а надо ли?

Тупперово множество

До меня сегодня наконец-то дошел смысл, как же работает http://en.wikipedia.org/wiki/Tupper's_self-referential_formula.

Там в вики написано, что k и есть бинарное представление картинки, помноженное на 17. Неравенство как раз берет и выбирает нужный бит из координаты.

То же самое, что и любой одноуровневый квайн (куйан) на любом языке программирования.

Что меня сейчас поражает - так это природа. Для программных квайнов нужна машина/интерпретатор. Без машины не получится. Для графика (Туппер) нужен вычислитель (тот, кто считать умеет, знает что такое "mod", "<"). При копировании же клетки происходит великолепная вещь - копирование всего, в том числе и интерпретатора. По аналогии, при запуске квайна мы бы получили вторую копию машины, с запущенной программой. Или при проверке Тупперова графика получили копию википедии, машины, браузера. Возможно и меньшего размера, но полную копию всего.

До сих пор пока не совсем понимаю, как же клетка делится...

update [24.02.2011] Я ранее все шутил, что инопланетяне это могут легко делать в 3Д, давая в качестве упражнения в школе.

Сейчас понял, что и я могу в 3Д, и в любой другой размерности тоже. Я не инопланетянен.

До Гёделя

Как минимум был А. Дюма (вроде старший): "Все обобщения опасны, и данное тоже".
Был кто-то до Дюмы, но тут частичный склероз. Там что-то изоморфное.

Вообще в древности были древние греки: "Я - лжец".

А скорее всего где +- 3..4*(10^3) лет были древние скандинавы/китайцы, с мифическим Уроборосом.

Везде самоприменение и отрицание. Гедёль крут (от конечно Курт, но и крут) в том, что смог выразить в терминах разрешимости/перечислимости. Но явно не был первым. Не смотри выше :) .

Штанга

Haskell

Единственно, что рассмешило - ожидаемая(!, не понятно почему рассмешила, раз ожидаемая?) фотка Зефирова со штангой.

Честно говоря, не знаю откуда идет этот мем у функциональщиков про штангу (в этом году видел штангу + erlang, что уже относится к классике и еще 2-3 упоминания)...

голосовой поиск

На телефоне появился голосовой поиск. Потестировал.

тест - тесты
*кашель, случайно* - crack
*после того как покашлял, и телефон полез что-то искать, случайно вырвалось "бля"* - *запись не работала, поиск не пошел :) *
haskell - хаски
изоморфизм графов - изоморфизм графов
импредикативный полиморфизм - импликативный полиморфизм *наверно, почти угадал*
неведомая херня - неведомая херня
почему путин краб - почему путин краб
быть или не быть вот в чем вопрос достойно ли терпеть позор судьбы иль нужно оказать сопротивление - быть или не быть вот в чем вопрос eggdrop на toshiba игнор на кпк определение
e равно mc2 - евровагонка квадрат
42 - 42
1729 - 1729
67108864 - the chameleon автосим 1864

Преобразование голоса в текст явно серверное. Опять же не более месяца назад на russir-е показали, как это примерно работает (multimedia IR). Там пример был про джедайские мечи, что достаточно передавать только некоторые значимые точки звуковой волны, что бы определить/сравнить. Shazam так и работает (ему уже явно более года).

Не понятно, как искать на импортном языке..

cs club

Появились все лекции с cs club (spb). Большая часть всего этого обитала на яндексе, но в худшем качестве. Сейчас абсолютно все без пробелов, и в хорошем качестве.

Около 1/3 я уже просмотрел ранее, 1/3 меня не очень сильно интересует. Как не трудно посчитать, осталось 1/3. Лекции про DIR я слышал менее месяца назад на RuSSIR в Воронеже :) .

Еще два года назад у меня был черно-белый мобильный телефон, потом специально купил КПК HP110 (320x240), потом телефон сдох и купил что-то как телефон (стандартная нокия), потом появился HTC Hero (480x320). Снова хочется продвинутый (с точки зрения расширения экрана) телефон.

Дожили

http://stackoverflow.com/questions/3770774/what-language-to-learn-after-haskell

Заголовок: What language to learn after Haskell?
Первое предложение из поста: As my first programming language, I decided to learn Haskell.

Лично мне хочется узнать еще очень чего много интересного, а так же забыть много чего безынтересного. Respawn не сохраняет состояние.