суббота, 25 апреля 2009 г.

Быстрее, выше, сильнее...

Тренируются ли профессиональные саперы в игру "Сапер"?
Купил очередную мышь (у предыдущей сдохло колесо). Привыкал в сапере, результаты сразу на +20%. Прошла неделя, привык, результаты восстановились. 
Мат. ожидание = 90+n (на среднем и малом поле все скучно и неинтересно, поэтому результатов не помню). Личный абсолютный рекорд = 71(лет пять, наверно, назад. Всего в жизни 70+n делал раз десять. Тогда мышь еще с шариком была). Со 80+n прохожу примерно в 5%. Как можно сделать 46(абсолютный зарегистрированный рекорд)? Тут, правда, ограничения в интерфейсе мозг-мышка, а не в монитор-глаз-мозг. От двух до семи все считать умеют, а вот точно 300..500 кликов в минуту делать уже сложнее. 
Есть одна прикольная модификация сапера - Crazy Minesweeper. Там мины разной "разрывной силы": от 1 до 3. Поэтому считать надо уже уметь не до 8, а до 24 :) Ну, по- крайне до 12 иногда приходится. Когда ее впервые увидел, то мозг вынесло. Стандартные шаблоны из простого сапера не работают, иногда приходится думать. Жаль, что она немного платная, на максимальном размере не дает. 
Личный рекорд на среднем поле (16х16) = 48.91 сек (91 - это сотые доли секунды, там время до сотых измеряется). Хотя там рекорд на сайте вообще в 25 сек. Там же есть модификации на нестандартном замещении (не совсем уж многогранники Вороного, но отличается от квадратного). Честно, не играл.
Когда остается совсем немного, то есть немного пародоксальная вешь. Иногда лучше вскрывать ту ячейку, где вероятность нарваться больше, чем в других. Но в случае успеха это даст какую-то информацию. Например, если осталось три невскрытых (в один ряд) и одна мина. Вскрывать центральную бессмысленно. Только этот пример для равных вероятностей(придумайте пример самостоятельно. Я знаю такой, только тут рисовать придется).
В общем, моторика рук и никакого мошеничества. Интересно, есть вот геймерские мыши... 
ЗЫ. 0 < n < 10

вторник, 21 апреля 2009 г.

Сломали индукцию

Сегодня был финал по спорту. Конечно же, поздравляем ИТМО! Вот именно они и сломали (позитивно) индукцию. В 1999, 2001, 03, 05, 07 команда ИТМО занимала третье место, в этом году взяли абсолют. 
Как это обычно происходит у физиков (и программистов тоже бывает), пытаются чуть модифицировать правило. Так как третье место заняли Бурундучки, то легко предложить следующую индукцию: в нечетные года команда из Питера занимает третье место :) . Ждем 2011...
За последние 10 лет абсолют был у России (6 раз), Китай && Польша (по 2 раза). В школьном IOI страны примерно тоже, пропорции немного другие. Хоть в этом году и было 100 команд (в прошлом 80+n), но почему-то на NEERC досталось только 11 мест (это еще при условии, что в прошлом у нас тоже был абсолют, там 12 мест было). Приехали украинцы и украли место. (причем, фактически, у ИжГТУ. Надо сейчас им мстить: отправить Питер + Петрозаводск в NWERC, Москва + Саратов + еще кого-нибудь в SERC. Мест на 5-6 больше станет :) ). 
Причем опять на замороженной таблице есть порядка 10 команд, которые не могут сдать даже самой халявы. Причем половина из штатов. А у них 22 места. Сейчас всей южной америке тоже мест 20 дают. Когда я участвовал, мы стабильно (или погранично) могли бы пройти в финал с любого полуфинала из США, южной америки, Австралии и Океании. Хотя наш уровень = 30 + n на NEERC. Со всей южной америки тогда было 3 места. Как-то глупо по численности делить места.

вторник, 14 апреля 2009 г.

Кстати...

Опять про Рамануджана.
13*133 :), причем дважды :) . 
Сам он тогда не видел, что :1729: = 19. 19 развернуть в 91.  19*91 = 1729. 
:a: = сумма цифр числа
За исключением тривиальной 1, есть всего 3 таких хитрых(кроме Рамануджана, еще 2). 

пятница, 10 апреля 2009 г.

\lambda и мэйнстрим

\lambda и мэйнстрим
Хочется высказаться на счет текущего состояние ФП и то, что понимается мейнстримом (скорее всего все выпады пойдут в сторону ms).
Для кого предазначено это сообщение? Если вы лично знакомы с Д. Скоттом, Per Martin-Lof (не знаю как правильно по-русски), ну, или хотя бы Ф. Вадлером; вас не пугает импредикативный полиморфизм(хотя я уже забыл что это :), но созвучно с синхрофазатроном); между словами морфизм и монада вы найдете что-то более общее чем общая первая буква "м", и что все тот же морфизм не имеет ничего общего со всякими *-измами (капитализм, марксизм, ...) ... - дальше вы можете не читать, все равно ничего нового вы здесь не узнаете.
Начнем с определений и операций. 
Определение можно прочитать в любой книжке по \lambda-исчислению. :) Что понимается под \lambda-ой в ms я лично не знаю, хотя в msResearch есть несколько вменяемых людей, кто смог бы им объяснить.
Имееется понятие нормальной формы, редукции. \lambda-выражение можно редуцировать, до тех пор, пока не придем к нормальной форме (выражение, которые уже нельзя редуцировать). Например, 4 - это нормальная форма. f - "обычно" тоже (просто функция), а f 4  - можно вычислять.
Есть две "вспомогательные" редукции: \alpha, \mu (если не ошибаюсь). Первая - переименование свободных переменных, вторая - если функции равны, то и равны их значения, вычисленные на одних аргументах.
Основная - \beta-редукция. Просто подстановка (ну, или чуть сложнее, из-за коллизии переменных).
Есть еще оператор неподвижной точки, для целей рекурсии. Иначе бы все было бы плоско. Так же имеются несколько примитивов (типа, if, равенства, арифметики).
В с#(3) с "\lambda-ой" можно сделать только одну вещь - откомпилировать в delegate. :) А у него тоже не слишком много свободы, его можно только вычислить (invoke). По смыслу, делегат - замыкание (closure). Изменив свободную переменную в определении делегата, мы тем самым изменим следующий invoke.
В ФП, как всем известно, функции являются объектами первого уровня. То есть их можно *нормально* использовать: создавать, передавать как аргумент и прочее.  Там это очень удобно и красиво. При наличия таких простых вещей как карринг, вывод типов все становится (опять же) очень лаконично. Примеры тут.
А ms хочет ввести понятие "\lambda" уже в С/++(2010). :) . Осенизаторскую машину ложкой меда не исправить. F# - получился как породия на ocaml, но все-равно императивный. Какие-то попытки добавить в некоторые фенечки к C# все равно ни к чему позитивному не приведут. Был бы смысл разделить императивный код и *точно ФП код* (хотя бы просто атрибутами), но side-effect всегда можно получить, ибо рефлексия. C-шный const отказались делать в шарпе, так как, типа, всегда можно низкоуровнево (*void) хоть куда в памяти записать. Msil && .net по определению процедурно-объектны (настоящее ООП, имхо в акторной модели, тот же Smalltalk, но это отдельный флейм). Даже тот делегат выбивается из общей картины. Жабовские анонимные классы, взамен делегатам, и то как-то в теме (полагаю, преследовали одну цель). 
В современном ФП (да какое оно там современное? та же Miranda, *ML,  пред- и пост- haskell-ные - конец 80, начало 90-хх) никакие дженерики, препроцессоры, никакие проблемы с типами (понятие cast-exception просто отсутствует, ибо негде), никакой мутабельности, все строго по теории. Просто думать надо по-другому.
Что я тут хотел сказать... Теперь уже и не знаю: слишком много хочется хочется сказать, только что-то не связно (без цели) получается. Переубеждать кого-то в споре ФП vs. императивщина - это банальщина. Что в мейнстриме ФП не будет пока еще лет 10 - это точно. Что уже лет 10 есть довольно вкусные экземляры ФП. Что современные реализации ФП довольно далеки от теории (в реализациях еще копать и копать), но там *такие* абстракции, что программистам оно и не надо (и не снилось) (те же \lambda-кубы, и высших размерностей :) ).  Что когда ms говорит, что это ФП и все будет рулез, то продолжайте жевать свой гамбургер и запевайте кака-колой.

понедельник, 6 апреля 2009 г.

Бег иноходца

Я на десять тыщ рванул, как на пятьсот, -
и спекся.
Володя.
Сегодня (неожидано) проснулся и пошел бегать. Попытки осуществить это были и раньше, но они заканчивались на фазе выключения будильника.
Первоначально хотел пробежать трешку без остановки, после первого круга - решил что два вполне сойдет. Как Вы, наверное, уже догадались, непрерывно пробежал только километр. Если не учитывать плохие погодные условия (утренний снег и скользский поворот. Центробежной вынесло 2 раза), то график примерно в 2 раза хуше школьного :).
В итоге пробежал $2 - \epsilon$, прошел пешком 0.5. Не сдох.
Если я у вас (зачем-то ?) займу кучу денег, то знайте (опять же зачем-то, держите за спиной камень или огнестрельное).
Не то, что бы к чемпионату мира готовлюсь. Но хотелось бы, что когда придет кто-нибудь с капюшоном или с косой, быть здоровым и желательно не молодым.
Я впервые не был иноходцем,
Я стремился выиграть, как все!
Опять Володя.

четверг, 2 апреля 2009 г.

Смысл?

-Есть ли жизнь после смерти?
-Если ее и там нет, то это уже наглость!
Сейчас меня торкнет на небольшую философию. 
Есть первичные понятия, и есть сущности выражаемые посредством определений. Первичные понятия, такие как точка, прямая, множества, как известно, определений не имеют и иметь не могут (не будем смотреть на всяких Цермело с Френкелем. Так же не будем упоминать понятие алгоритм, хотя в школе нам поддиктовку что-то определяли :) С возрастом наивность ушла). 
А вот есть ли у понятия "жизнь" определение? Или это первичное понятие? Конечно в медицине или у юриков что-то есть. В какой-нибудь астрофизике, наверное, тоже. Среди лысо-бородатых классиков(то ли Ленин, то ли Маркс) есть такое, как "способ существования белковых тел". Вроде бы ничего так определение, а вот Вы можете напротив своей жизни поставить "способ существования"? или медицинское "биологические процессы"? Вот и я о том же... Так что отнесем к первичным понятиям.
Продолжая пьянку. У всех есть мечта, фантазии, желания(если этого нет, то тут понятие жизнь не применимо). Далее идет понятие цели. Цель - это не мечта, к цели идут. Ее ставять, достигают(или не достигают), ставят новую. А к мечте не идут, она летает. И ждут когда же она упадет. Цель уже есть не у всех. 
А еще дальше идет понятие смысла. Определения точно не дам. Но это не первое и не второе. Это не просто не достижимая(слабо) цель, это нечто нематериальное. И это не виртуальные мечты. Если мечты могут менять чуть ли не каждый день, цели более долговечны (от месяца до десятилетий), то смысл, если он все-таки появляется, статичен. 
Иногда, он приходит. Иногда и мудрость со старотью приходит. Чаще всего старость приходит одна. Смысл не летает, его не ставят и не достигают. 
Если с примером целей (хорошо, если это не мечты) для среднестатистического человека все просто: квартира, машина, жена/муж/любовник/дети, работа. То с примером смысла придется пасануть. Он точно есть не у всех. Даже не могу сказать, есть ли он у меня. Или у кого-то другого. Последние года два иногда думал над этом. Кажется, что есть (доказать не могу :) ), даже два. Как я уже сказал, что это философия. Поэтому четких определений и строгих доказательств не будет. В слух оглашать не буду, ибо личное. А может и нет его? Как узнать?
Абстракции четвертого уровня очень редки. Более четвертого порядка в жизни вообще не встречаются. Есть ли что-то более крутое, чем смысл? Три сущности вроде обозначил. Можно конечно что-то низкоуровневое выдвинуть, тогда смысл станет четвертого порядка. Но, видимо, не стоит. 
Кстати, можно попытаться определить философскую статью. В ней число вопросительных знаков довольно много, и это не интервью. А ответов и знаков факториала вообще нет. И это не задачник по физике(там обычно ответы есть).
Короче, если у Вас есть конструктивные мысли(отличные от моих) по всему этому, то всегда готов выслушать при личной встрече. Хотя и не употребляю (и зло- тоже).

Числа, множества и отношение

Настоящий математик при обращении к своей ... (нет, не половинке, она должна быть целой. В крайнем случае, иррациональной, но никак не 1/2) будет использовать слово "единственная". Следовательно, множество настоящих математиков, обладающих гаремом, пусто. update[26.04.09] Все-таки рациональные люди лучше иррациональных (про числа отношение лучше не определено). Так что допускается и множество рациональных чисел, за исключение 1/2. Комплексные числа и квантерионы, как и люди, тоже бывают, но нас не интересуют. Действительные интереснее, что какие-то мнимые части рассматривать.