www.livejournal.com
avva
Зря ли я столько сил разбазарил?
1	http://avva.livejournal.com/2689750.html	числа на лбах	___	tag: задачка endoftag 	Аня, Боря и Вася сидят за круглым столом. На лбу у каждого написано целое положительное число. Как водится, каждый из них видит числа остальных, но не знает, что написано у него самого. Известно также, что сумма двух написанных чисел равна третьему. Они договорились играть так: по кругу каждый либо называет свое число, если уверен в ответе, либо говорит, что не знает. Как обычно в таких задачах, мы предполагаем, что у них идеальное логическое мышление.Аня: "я не знаю свое число".Боря: "я не знаю свое число".Вася: "я не знаю свое число".Аня: "у меня написано 25".Какие числа написаны на лбах Бори и Васи? Если можете, докажите также единственность этого решения.----Я скрываю правильные ответы первые сутки, буду раскрывать только уточняющие вопросы итп. Я бы сказал, что это задача средней сложности. Найти решение в уме можно (но непросто), доказать единственность - не уверен.
2	http://avva.livejournal.com/2689344.html	о нашей ноше	___	___	(нецензурная лексика, не читайте дальше, если вам это мешает)Мне нравится представлять, что когда кто-то несет какую-то хуйню, то он действительно ее несет на себе. Я представляю эту хуйню как что-то вроде связки хвороста, или иногда это рюкзак, набитый хуйней под завязку. Если это что-то особенно идиотское, то и ноша соответственно тяжелее, хуйни на плечах больше.Иногда вот беседую о чем-то, и понимаю вдруг, что и я, и собеседник согнулись и кряхтим под тяжестью нашей хуйни. Щадите ваши плечи и позвоночник.
3	http://avva.livejournal.com/2689046.html	традиционное	___	tag: что-читаете endoftag 	Что вы сейчас читаете или недавно прочитали?Понравилось? Рекомендуете или нет, и почему?Я тоже отмечусь в комментариях.
4	http://avva.livejournal.com/2688800.html	в сегодняшних деньгах	___	___	У лингвистов есть конвенция - звездочка перед фразой обозначает, что автор утверждает, что так на самом деле не говорят, это неграмматично. Можно и каждый раз словами это писать, но звездочка экономит место и время.По-моему, экономистам пригодилась бы подобная конвенция для обозначения "в пересчете на сегодняшние деньги" (по-английски говорят in today's dollars, inflation-adjusted итп.). Всякий раз, как я вижу обсуждение цен на что-то или зарплат или личного состояния людей 20, 30, 50, 100 лет назад, я во-первых сомневаюсь в том, указаны суммы в переводе на сегодняшние деньги или нет; а если специально указано, то это часто выглядит громоздко и требует отдельных пояснений в скобках. А если бы был такой значок, ну скажем ^, то то можно было бы писать:В 1929-м году средний годовой доход американской семьи был $2500 ($34,000^). К 1960-му году он увеличился до $6700 ($53,000^).Бюджет нового филантропического фонда, который Рокфеллер основал в 1913-м году, составил в общей сложности 250 миллионов долларов, или почти 4 миллиарда^.Если привыкнуть, то удобно станет.
5	http://avva.livejournal.com/2688572.html	пример из evo-psych	___	___	Значительный рост усыновлений - почти всегда не родственных детей, часто из других стран, нередко других рас - в современном западном обществе требует объяснений от сторонников эволюционной психологии. Усыновление детей из чужих семей не просто вредит адаптационной приспособленности в том виде, в каком ее понимают в эволюционной психологии, оно вредит ей дважды: и отнимает у родителей ресурсы для продвижения "своих" генов, и помогает чужим! Если бы был ген, который бы побуждал его носителей усыновлять посторонних детей, он давно должен был вымереть.Вот, например, как одна из книг по эволюционной психологии для широкого читателя пытается справиться с этим парадоксом:In Western society today, most examples of adoption occur between unrelated individuals. Does this suggest that kin altruism has been jesttisoned from this process in the industrialised countries? In a sense it does. In terms of giving aid to non-relatives and expecting no reward from such adoptees then we must accept that this constitutes altruism and that such behavior is currently unrelated to inclusive fitness. Such a finding, however, should not be taken as evidence that our adoption practices are completely unrelated to the evolutionary pressures that our ancestors faced. You may recall that one of the central tenets of evolutionary psychology is that, rather than expecting all current behavioral practices to increase inclusive fitness, selective processes have led to the development of a mind which in the ancient past would generally have done so. During our own ancient past (the environment of evolutionary adaptedness or EEA) it may have made adaptive sense to adopt young orphaned individuals since, as members of your small tribe, they would most probably have been relatives of some degree. This means that today we may be left with the legacy of such urges even though they may no longer be appropriate (in an evolutionary sense).В этом отрывке ясно видна тенденция, столь прискорбное и частое в эволюционной психологии, уметь объяснить все, любой поворот событий. 50, 100, 150 лет назад в западных обществах не было массового явления усыновления совершенно посторонних детей из других городов и стран, даже среди богатых людей, которые могли себе это позволить - почему? - Понятно, почему, kin altruism, даже странно, что вы задаете такой вопрос, ясно, же, что такое усыновление не может быть адаптивным. - А почему же тогда сегодня такой взрыв этого явления в западных обществах? - Конечно, в полном соответствии с принципами эволюционной психологии, это у людей с первобытных времен осталось адаптивное стремление кого-то усыновлять. Поскольку беспризорных сирот под рукой не осталось, их находят в других странах. - Ну хорошо, а вот в Индии беспризорных сирот прямо на улице под рукой сколько хочешь, и вроде нет массового усыновления их индийцами среднего класса плюс, хоть они и могли бы себе позволить - как же так? - Ну что вы такую чушь мелете, как же индийцы будут усыновлять кого попало, а kin altruism куда засунем? И так по кругу, снова и снова. На все есть ответ.
6	http://avva.livejournal.com/2688312.html	мимоходом	___	___	Я не знаю, что конкретно разозлило artem_r, но описание понравилось:«Я щитаю, что наш народ – богоносец». «Тут мой коллега сказал, что наш народ – богоносец. А я щитаю, что он не прав, и наш народ – не богоносец». «Тут у моих коллег вышел спор о том, богоносец наш народ или нет. Мои коллеги – люди умные, но они не торговали пластинами «папл» на Горбушке в 91 году и не знают, что из себя представляет наш народ на самом деле». Чушь какая-то, не пресса, а посиделки с пивасом.
7	http://avva.livejournal.com/2688160.html	шутки (англ.)	___	___	50 интеллектуальных шутокНеровного качества, но есть хорошие. Переведу и процитирую несколько, которые мне понравились:"Я лингвист, так что ценю двусмысленность выше большинства людей".Что обозначает Б. в имени Бенуа Б. Мандельброта?Бенуа Б. Мандельброт.Кто еще больший враг Полифема, чем Одиссей?Никто!В этом предложении есть ровна три ошипки.Инженер, химик и экономист оказались на необитаемом острове. Они собрались вместе и думают, как бы вернуться к цивилизации. Инженер говорит: "мы можем связать вместе ветки потолще, сделать примитивный плот и попробовать на нем доплыть до земли". Химик говорит: "если мы найдем нужные ингредиенты, то сможем разжечь костер с очень густым дымом, чтобы заметили с самолета". Экономист говорит: "значит так, предположим, что у нас есть корабль..."(непереводимо) What do you call two crows on a branch? Attempted murder. Два фермиона входят в бар. Первый говорит: "мне, пожалуйста, мартини с водкой и цедрой лимона". Второй говорит: "ах ты ж блин, это же я хотел это заказать!".На заседание философского общества спустился с неба ангел, и предложил философам ответить на любой их вопрос, но только на один. Философы начали спорить о том, какой вопрос задать. Ангел сказал: "ну вы тут решайте, я завтра вернусь и спросите".Некоторые философы предлагали связать несколько вопросов конъюнкцией, но другие возражали, что ангел не согласится считать это одним вопросом. Один философ предложил спросить ангела: "Какой вопрос самый лучший?", и потом, зная вопрос, подождать, пока не прилетит другой ангел в будущем. Но другие философы возражали, что не факт, что визит когда-либо повторится, и жалко тогда терять этот шанс.Наконец, философы договорились, и когда ангел вернулся на следующий день, задали ему следующий вопрос: "Какова упорядоченная пара, первый элемент который является лучшим вопросом, который можно задать ангелу, а второй элемент - ответом на этот вопрос?" Ангел тут же ответил: "Это упорядоченная пара, первым элементом которой является вопрос, который вы только что задали, а вторым - ответ, который я вам даю". И исчез.
8	http://avva.livejournal.com/2687753.html	красивая работа	___	___	Любопытная работа: алгоритм, моделирующий данную поверхность как самоподдерживающую структуру из блоков, которые можно распечатать на 3D-принтере:Катарсис в 1:35.
9	http://avva.livejournal.com/2687672.html	агенты щита	___	___	После первых трех серий нового сериала Джосса Уидона Agents of S.H.I.E.L.D. я ощущаю главным образом разочарование. Вряд ли буду продолжать смотреть этот сериал - видимо, он не выйдет и близко на уровень удачных сериалов Уидона (к которым я причисляю Buffy the Vampire Slayer, Firefly, и в меньшей степени Angel). Почему так получается - не знаю.В этих трех сериях в первую очередь бросается в глаза нагромождение второсортных клише из второсортных американских сериалов экшна. В начале серии героиня учится приему самозащиты - конечно, ближе к концу она его применяет. В начале серии показано, как "команда" разобщена и ее члены не доверяют друг другу - конечно, к концу совместная работа их сплотила. Стандартные типажи: ученый "нерд", почему-то в этом сериале представленный двумя персонажами (за исключением пола совершенно неотличимыми друг от друга и никак не отклоняющимися от стереотипа). Супер-крутой спецназовец, скупой на слова, никому не доверяет, пока постепенно его суровое сердце не раскрывается итд. Надуманные конфликты с надуманными разрешениями. Все избито, все второсортно. Кроме одного-единственного аспекта, который Уидон не разучился делать мастерски: "перевертышей", когда сюжет внезапно опровергает сложившиеся ожидания зрителей. Но на одних "перевертышах" не выедешь. Уидон всегда прекрасно умел их делать: в первой серии его первого сериала, "Баффи", вступление было основано на перевертыше (парень и девушка вечером в темном здании школы, постепенно зрители уверяются, что парень сейчас на нее нападет, но тут оказывается, что вампир как раз она). Но привлекательность лучших сериалов Уидона основывалась отнюдь не на перевертышах в сюжете, а на оригинальных, живых персонажах, на совмещении, нередко специально абсурдном, приземленного и притягательного (будничной жизни американских подростков и тайной борьбы со злом в "Баффи"), на отказе (не ироническом "обыгрывании", а отказе) от приевшихся нарративных клише. Всего этого нет в "агентах щита", есть только ненормальное количество перевертышей - в одной только третьей серии я насчитал пять штук - словно создатели сериала пытаются этим заместить отсутствие всего остального. Но это так не работает, постоянный обман ожиданий приедается и быстро кажется механическим и бездумным, каким, в общем, и является.И все же это не кто-нибудь, а Джосс Уидон. Наверное, какая-то искра его магии должна там быть? Чем этот его новый сериал отличается от десятков других второсортных экшн-сериалов, созданных под стандартную линейку, каждый год по несколько новых штук? Чем он отличается от какого-нибудь La Femme Nikita, или The A-Team, или Mutant X, или Walker the Texas Ranger?Увы, ничем существенным.Оценка 2/6.
10	http://avva.livejournal.com/2687420.html	иллюзия	___	___	(да, я тоже эту вспомнил)
11	http://avva.livejournal.com/2687147.html	всякая всячина (англ.)	___	___	Should we stop believing Malcolm Gladwell?Why, yes, yes we should.(see also: The pseudo-profundity of Malcolm Gladwell)I'd Do Anything For Love (But I Won't Do That) - what is the "that" that he won't do? A redditor explains.The Philosopher's Annual: a pick of 12 best articles in philosophy every year."In analytic philosophy" would be more accurate.Psychologists deem Freud's psychoanalytic theories to be outdated, so why do literary scholars still use them?Some insightful remarks in the discussion, e.g. "The lingering importance of psychoanalysis: lots of little stuff, but the big one is talk therapy. The notion that using language might help a person to overcome a mental disease was just astonishingly weird, pre-Freud."@HardSciFiMovies - a very funny Twitter account."A spider is irradiated by a particle accelerator at a science exhibit, and bites one of the students. The student is given a Band-Aid.""A scientist is trapped on an alien mothership with nothing but his Apple Powerbook. He is unable to connect to the alien computer system.""A scientist develops a revolutionary new compound capable of curing cancer, of one type, in about 50% of the early-stage patients."Virgins that are 40 years old or older, what is life like?One the more interesting recent AskReddits. Many stories, of different kinds, not only from &gt;40 year olds.
12	http://avva.livejournal.com/2686673.html	о школе	___	___	Человек спрашивает совета на форуме: его 8-летний сын жалуется, что в школе очень скучно. Что делать?Ему дают всякие советы. Один из советов - перевести ребенка на хоумскулинг. Я особенно хочу выделить часть этого комментария, которая говорит о том, чем вредна школа для умного ребенка. Я был "вундеркиндом" в школьные годы. Мне видится в этом описании много верного."Sounds like your kid is bright. Public school is child abuse for a bright kid. He will learn all the wrong lessons, things that will hamstring him for the rest of his life. He'll learn that he doesn't have to work. He'll learn that he can beat his peers while being a lazy jerk off. He'll learn that "being smart" is the standard of status, not achievement.And he'll fail to learn how to drive himself. Fail to learn how to overcome setbacks. Fail to learn how to discipline himself."Что вы думаете об этом?
13	http://avva.livejournal.com/2686215.html	дневные стихи: андрей поляков	___	___	Андрей Поляковиз сборника "Орфографический мимимум", 2001.* * *Как сделать что было в начале,что были мы дети страны,что верхние сосны качалии мы собирались нужны?Стихи говорили чуть слева...Признал у костра пионер,что, кстати, названия славане важно ему, например.Но возрасты уж поменялись!Прошедшего вряд ли вернуть.Зачем разве сосны качались,чтоб нас хорошо обмануть?В лесу на лежачей опушке,подросший всего ничего,вдруг был нам какой-нибудь пушкин,а мы пропустили его.
14	http://avva.livejournal.com/2686002.html	открытая запись	___	tag: открытая запись endoftag 	В комментах к этой Открытой Записи приветствуются любые темы, любые комменты, любые вопросы, любые ответы, любые дискуссии.Давайте поговорим о чем-нибудь.
15	http://avva.livejournal.com/2685788.html	и в заключение	___	___	Теперь у меня есть "интуитивное" решение задачи про Алису, Боба и Казино. То самое, которого так долго ждали большевики и в поисках которого я вместе, кажется, с немалым числом читателей этого дневника бились головой об стенку в последние несколько дней. То самое, по поводу которого я уже решил было, что оно не существует.Это не мое решение. Его придумал коллега из Гугла. Мне досадно, что все трюки, которые оно использует, я тоже пытался применить, но оно их все соединяет с еще большей хитроумностью и извращенностью, которые от меня ускользнули. Что я могу сказать - в Гугле работают умные люди.(додумался бы я до этого решения, если бы еще несколько дней бился головой об стенку? Не знаю, но скорее нет, чем да)Да, кстати, хоть оно, мягко скажем, не тривиальное, но действительно работает. Я проверил не только на глазок, но и программой, которую я написал для проверки решений.Ну что, хотите узнать? Дальше идут одни спойлеры![Последний шанс не узнавать и думать самому!]СПОЙЛЕРЫСПОЙЛЕРЫСПОЙЛЕРЫИтак, у нас есть 9 битов Казино, которые мы обозначим A-BCD-EFG-HI. Для простоты предположим, что в первом бите всегда есть ошибка, этого невозможно избежать в любом случае.1. Сначала опишем "базовый алгоритм", который все уже пробовали. В своем бите A Боб обозначает наиболее частый бит среди BCD, и Алиса играет его в BCD. Если у нее есть одна ошибка, Боб использует свой бит на месте ошибки, чтобы передать самый частый бит среди EFG. Если там есть одна ошибка, то Боб использует этот бит, чтобы закодировать HI вместе, предполагая, что они одинаковы.Этот алгоритм сработает, если BCD не все одинаковы, EFG не все одинаковы, и HI = 00 или 11. Кроме того, если BCD или EFG все одинаковы, он тоже сработает с легкими модификациями, и тогда даже не нужно, чтобы HI были одинаковы. Например, если BCD одинаковы, то у нас после BCD есть еще две ошибки в запасе: мы можем использовать E для большинства FGH, и тем же способом бит ошибки внутри FGH для I (а если бита ошибки нет, то и не надо, наплевать на I). А если EFG одинаковы, то у нас есть одна ошибка в запасе на HI, так что просто пользуемся H чтобы просигналить I.2. Таким образом, мы пользуемся "базовым алгоритмом", и он работает во всех случаях, кроме HI=01 или HI=10. Более того, в этом случае мы можем предположить, что BCD не одинаковы и EFG не одинаковы, иначе базовый алгоритм все равно работает.3. Теперь рассмотрим случай, когда HI=01, а EFG - любая неодинаковая комбинация, кроме 010 и 101. Таких комбинаций есть четыре, так что возможности для EFG-HI такие: 001-01, 110-01, 011-01, 100-01. Мы отклонимся от базового алгоритма следующим образом: - в случаях 001-01 и 110-01 Боб специально делает ошибку во втором бите (F). Эта ошибка говорит Алисе (которая не ошиблась в этом бите, и поэтому знает, что это не "ошибочный бит" Боба в базовом алгоритме), что следующий бит противоположен плану, по которому она шла, и вдобавок в конце идет 01. - в случаях 011-01 и 100-01 Боб похожим образом делает ошибку в первом бите (E). Эта ошибка говорит Алисе, что следующие два бита противоположны плану, и вдобавок в конце идет 01.- в обоих случаях после специальной ошибки Боба Алиса без дополнительных ошибок заканчивает игру.4. У нас остались следующие неохваченные комбинации EFG-HI. Во-первых, 010-01 и 101-01, а во-вторых любые (но не все одинаковые) значения EFG, плюс HI=10. Все остальные варианты мы рассмотрели.5. В этих оставшихся случаях мы меняем стратегию на BCD, и пользуемся трюком, который позволяет сделать две ошибки, но вытащить целых три бита. Это делается следующим образом. У нас есть два способа сделать две ошибки на BCD и закодировать там два бита:- дать в бите A неправильное большинство для BCD, чтобы Алиса сделала две ошибки, и использовать эти два бита Боба.- дать в бите А правильное большинство, Алиса делает одну ошибку (и Боб имеет в ней свой бит), но Боб делает еще одну дополнительную ошибку, причем он может выбрать одно из двух правильных мест, и этот выбор дает ему еще один бит.Наконец, выбор одной из этих двух стратегий дает нам третий бит. После того, как Алиса ответила свои BCD согласно биту A Боба, она может определить, перешли ли мы на стратегию "две ошибки", на какую из двух, и узнать все три бита.6. Эти три бита теперь дают нам возможность определить EFG-HI без единой ошибки. Первый бит определяет, верно ли, что EFG=010 или 101. Если это так, то второй бит скажет, какая из этих версий верна, а третий определит, HI=10 или HI=01. Если это не так, то обязательно HI=10, а для EFG осталось четыре возможности 001, 110, 011, 100,и второй и третий бит вместе определяют, какая из них верна.Уф. Ну как? Прекрасно, верно ведь?
16	http://avva.livejournal.com/2685504.html	ААААААААААААААААААААА	___	___	Я ее решил!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!Уже проверил и отослал решение. Сразу скажу, что мое решение найдено с помощью компьютера, и я не могу его описать в виде интуитивно понятного алгоритма для Алисы и Боба. Теперь, когда оно у меня есть, я попробую, наверное, проанализировать и "понять" его и попробовать перевести в интуитивное описание, но у меня нет уверенности, что это вообще получится.Дальше следует краткое описание того, как было найдено решение, в общих чертах, без точных подробностей и кода. Если кому-то нужен код или точные подробности, пишите мне в комментах или на почту. Если не хотите решительно никаких спойлеров, помогающих решить, не читайте дальше. Извините, если что-то непонятно, я пишу впопыхах, чтобы распрощаться наконец с этим, но готов объяснить, если надо.[Осторожно, спойлеры!]СПОЙЛЕРЫСПОЙЛЕРЫСПОЙЛЕРЫЗначит, так. Во-первых, мы предполагаем, что Алиса всегда начинает первый раунд с 0, а казино - с 1, так что в первом раунде у нас меняется только бит Боба. В случае, если казино в первом пишет 0, то Боб тоже пишет 0, они выигрывают первый раунд, и им остается угадать 5 из 8, что легко сделать "интуитивной" стратегией. Если вы уже бились над этой задачей, пытаясь сделать 6 из 9, то скорее всего 5 из 8 вы уже и так умеете, так что не буду тут описывать (если надо, спрашивайте). Поэтому по сути дела далее обсуждаются только 256 строк решения, для всех вариантов казино, в которых первый бит 1. Когда у меня это все заработало, я написал отдельно скрипт для создания остальных 256 строк вышеупомянутого интуитивного решения, и проверил их все вместе. Далее, мы решаем проблему перебором с значительными эвристическими предположениями, потому что строгий перебор - безнадежное дело. Я перепробовал три разных способа написать программу перебора, и в третьем из них - около восьми разных вариантов эвристики, пока не заработало. Сначала мы строим префиксное дерево, которое соединяет все возможные начала за Алису,Боба и Казино с их продолжениями. Например, предположим, что первые два раунда выглядят так: А:00 Б:00 К:10. Их теперь можно продолжить в третий раунд, добавляя по одному биту А,Б и К. Гипотетически есть 8 возможностей перебрать эти три бита, т.е. на каждый вариант одного раунда есть 8 продолжений. Но мы сразу будем отбрасывать невозможные продолжения, в которых между продолженными А,Б,К есть больше трех разногласий. Из-за этого только в первых нескольких раундах кол-во вариантов растет экспоненциально, а потом замедляется. В построенном до последнего 9 раунда дереве есть 140 тысяч листьев-концовок, т.е. возможных троек А,Б,К по девять бит каждая - это в тысячу раз меньше экспоненциального 512*512*512. В том виде, в каком оно построено, это дерево не задает стратегию поведения Алисы, потому что оно постоянно расщепляется, давая ей оба варианта. Скажем, от А:00 Б:00 К:10 есть все 8 возможных вариантов продолжать: и А:0 Б:0 К:0, и А:1 Б:0 К:0, и так далее. То, что в этих продолжениях есть разные Б и К - нормально, они соответствуют разным возможностям, с которыми должна справиться Алиса. Но то, что в них есть как тройки с А=0, так и тройки с A=1, означает, что Алиса в этом месте не знает, что делать. Мы хотим подрезать это дерево и отсечь в нем много ветвей так, чтобы у Алисы всегда было детерминистское поведение. Находясь в каком-то узле, например А:00 Б:00 К:10, мы хотим выбросить либо все продолжения с A=0 и все, что ниже их до самого конца, либо все продолжения с A=1. Это можно сделать огромным количеством способов. Дело не только в самом выборе, что выбрасывать в данном узле, 0 или 1, но и в том, что сами узлы с расщеплениями от этого меняются: если мы обрежем огромное подддерево ближе к началу, то все узлы с расщеплениями в нем исчезнут и по ним уже не надо ходить. С другой стороны, обрезая любое поддерево, мы теряем все листья-концовки в нем, т.е. тройки из 9 битов А-Б-К, которые теперь уже никогда не случатся. До того, как мы начали усекать дерево, любая из 512 возможных К-стратегий находится в нашем дереве в концовках огромное количество раз, в разных тройках А-Б-К. Но по мере того, как мы отрезам поддеревья, некоторые К-стратегии становятся более редкими, и в конце концов могут исчезнуть из дерева. Наша задача - этого не допустить. Если мы сможем достигнуть положения, в котором у Алисы всегда детерминированный выбор, а в листьях дерева все еще представлены все 256 К-стратегий, мы победили. Почему? Потому что возьмите тогда любую стратегию, найдите концовку А-Б-К с ней, она даст вам 9 битов Боба, и вы сможете проследить игру от корня дерева до этой концовки в точности по этому А-Б-К. У Алисы на каждом раунде нет выбора иначе как следовать по заданному пути к этой А-Б-К.Значит, мы пытаемся в каком-то порядке и по какому-то принципу обрезать поддеревья, и проверяем по дороге, что все К-стратегии все еще достижимы. Когда доходим до дерева без выборов (для Алисы), мы победили. Само дерево не очень большое, но в нем много тысяч узлов с расщеплениями, и перебрать все возможные способы их отсекать непрактично. Но напрашивается, например, идти по дереву обходом BFS или DFS, в каждом проблемном узле смотреть на какую-то эвристику, которая поможет решить, отсечь ветки-0 или ветки-1 для Алисы. В общем, это то, что я сделал. Перебрал разные варианты обхода и эвристики: например, "отсечь ту ветку, в которой больше узлов", и многие другие. Одной из лучших эвристик оказалась "посчитай минимальное количество путей достичь конкретной концовки, для всех концовок (если этот минимум упадет до 0, мы проиграли), и отсекай там, где этот минимум снижается меньше". Но одной ее тоже было недостаточно. Постепенно у меня кол-во "живых" концовок из 256 к концу работу выросло до 214, потом до 240. Наконец, я заметил, что когда я принимаю решение, у меня часто все эвристические критерии у обеих веток совпадают, и тогда я выбираю всегда отрезать ветку-0. Вместо этого я поставил случайный выбор между веткой-0 и веткой-1 в каждом случае, и запустил сто раз, так, чтобы после каждой итерации, если вдруг повезло и остались все 256 стратегий, код записал все дерево в файл. Это случилось через несколько итераций после начала.
17	http://avva.livejournal.com/2685366.html	ааааа	___	___	Второй день не сплю, не ем, думаю только об этой задаче. Хожу как зомби. Все перепробовал. Ничего не выходит. В уме, на бумаге, на компьютере. Час назад уже совсем был уверен, что получилось (в пятый раз примерно). Но нет. "..." - привычно отозвалось эхо.Завтра беру тайм-аут, видимо, потому что так жить нельзя. Но черт побери.Update: AAAAAAAAAAAAAAAAAAAAAA!
18	http://avva.livejournal.com/2685149.html	задачка	___	tag: задачка endoftag 	Отличная задачка от IBM.Перевод условия: Алиса и Боб играют против казино следующую игру: в каждом раунде Алиса выбирает бит 0/1, потом Боб, потом казино; все выборы публичные. Алиса и Боб выиграли раунд, если все три выбора одинаковые, и проиграли в обратном случае. При таких условиях казино побеждает тривиальным образом (т.к. видит выборы Алисы и Боба), поэтому на самом деле казино заранее записывает все свои выборы и они хранятся в сейфе и открываются по одному. Алиса и Боб могут договориться о стратегии заранее, но не могут обмениваться информацией во время игры (кроме своих выборов). Перед началом игры Боб подкупает работников казино и получает всю последовательность выборов казино, но он не может уже к этому моменту передать эту информацию Алисе. При этих условиях Алиса и Боб могут обеспечить себе победу в 50% раундов: на нечетных раундах Боб выбирает то, что Алиса (и Боб) должны поставить в следующем раунде, и таким образом во всех четных раундах они выигрывают.Нужно доказать, что в игр в n=9 раундов Алиса и Боб могут обеспечить минимум 6 побед.Я пока что знаю, как обеспечить 5 побед, а 6 не могу. Буду еще думать.Прошу не спойлерить - если у вас есть полное решение, дайте ссылку на свой журнал или поместите его на pastebin.com и дайте ссылку туда - это занимает ровно минуту без регистрации.Update: AAAAAAAAAAAAAAAAAAAAAA!
19	http://avva.livejournal.com/2684863.html	понравилось	___	___	
20	http://avva.livejournal.com/2684502.html	об объятиях	___	___	Рэймонд Кэрролл написала в книге о разнице между французской и американской культурами ("Cultural Misunderstandings", я писал о ней пару месяцев назад), что у американцев есть обычай, о котором они сами не всегда сознательно знают: когда друзья обнимаются, то заканчивают объятие похлопыванием ладонью по спине, и это подчеркивает, что объятие не романтическое. Она отметила, что студенты-американцы, которым она об этом рассказывала, нередко не соглашались с ней, но потом "проверяли себя" и убеждались, что не замечая того сознательно, они действительно всегда так поступают.С тех пор, как я это прочитал, я все время замечаю это похлопывание в фильмах, сериалах, где угодно - и вот сегодня, например, даже в классическом диснеевском мультфильме "Король Лев", смотрите на отметке в 2:05, когда обезьяна обнимает Муфасу:
21	http://avva.livejournal.com/2684204.html	еще о судьях	___	___	В продолжение темы о том, что лучше бы больше одного судьи. Вот прямо сегодня читаю свежую запись в блоге Фила Гринспана (неважно, кто это). Просто как пример того, что проблемы такого рода встречаются постоянно.Гринспан пишет о том, что странно, что так много людей воюют за изменение формы брака (напр. однополый брак), и почти никто не воюет за изменение последствий развода, хоть это влияет на реальную жизнь людей в сто раз больше. Но в процессе он рассказывает, как после развода устраивают деление имущества и опекунства между родителями в Массачусетсе (как обычно в Америке, в разных штатах разные законы, но Массачусетс не выходит из ряда вон в этом). Подача заявления на развод приводит обычно (если супруги не озаботились специально договориться полюбовно) к судебному рассмотрению, причем заседает один судья и от его решения зависит, будет у ребенка два родителя, или одному из них будет позволено видеть его не чаще, чем раз в две недели. "A child's future is determined by a single individual (the trial judge)". Гринспан еще много пишет о том, какие решения обычно принимает этот судья, почему это несправедливо и глупо, как можно на это повлиять итд. Но задумайтесь о самом факте: от одного этого судьи зависит, как сложится детство ребенка и жизнь родителей. Важно понять, что практически невозможно оспорить его решение - это потому что самые важные аспекты записываются как "finding of fact" и это значит, что апелляционный суд с близкой к 100% вероятностью не захочет пересматривать это. Но это же безумие. Среди тысяч и тысяч судей обязательно найдутся дураки, негодяи, взяточники, предрасположенные против женщин или мужчин. Это неизбежно, по-другому быть не может. И оспорить их решение будет невозможно. Людей, попадающих к таким судьям, мы по сути дела обрекаем на несправедливость, разрушающую жизни. Мне много написали резонного о том, почему неудобно, непрактично, дорого задействовать несколько судей при разборе дел в первой инстанции. Трудно устроить процедуральную сторону. Очень замедлится выработка вердикта. Судьи всегда будут соглашаться. И многое еще. Но мне кажется, что все эти проблемы, даже если их не удастся решить, не так прискорбны, как ситуация узаконенного произвола, когда судья может искалечить жизнь человека, и нет никакой возможности проконтролировать или оспорить его действия. Все общественные механизмы, имеющие серьезное влияние на судьбу человека, должны быть "idiot-proof". Вспомните школьные годы, и возьмите самого тупого ученика из вашего класса или всей параллели. Смешайте его с самым мерзким учеником по характеру, самым подлым, мелочным и злопамятным. Вот эта смесь - всякий раз, как вам надо иметь дело с чиновником или бюрократом любого типа, помните, что он может легко быть вот этим человеком.
22	http://avva.livejournal.com/2684088.html	фотонов нет, сказал мудрец брадатый	___	___	Вот так живешь всю жизнь, а тут выясняется, что никаких фотонов нет.1. W.E.Lamb, Anti-Photon (квантовая теория излучения)2. Jacques Moret-Bailly, Anti-Photon (астрофизика)Среди моих читателей есть физики - буду очень благодарен за краткое объяснение для нас, чайников, того, что написано в этих статьях (в первой самое важное) и насколько это мейнстримный взгляд. Действительно ли фотон - вредная абстракция, в терминах которой лучше не думать? Почему фотон - вредная абстракция, а, скажем, электрон или атом водорода - нет? (это особенно хочется понять). (И как совместить такой взгляд на излучение с, скажем, популярным объяснением эксперимента с двумя прорезями, в котором даже убрав излучение до отдельных непересекающихся фотонов мы видим интерфереционную картину?)
23	http://avva.livejournal.com/2683745.html	мастер-класс	___	tag: наука endoftag tag: языки endoftag 	Карло Гинзбург - итальянский историк. Я уже несколько раз в френд-ленте видел объявления о том, что он в Москве сейчас проводит мастер-класс. Все никак не могу понять, как это. Как историк проводит мастер-класс? Это какая-то модная глупость или нормальная практика, о которой мне не известно?
24	http://avva.livejournal.com/2683418.html	лингвистическое	___	tag: наука endoftag tag: языки endoftag 	"Что дѣлать? What is to be done?"Презентация американского лингвиста Давида Песецкого (David Pesetsky) о том, чего добилась генеративная лингвистика за время своего существования, и как это лучше объяснять другим лингвистам и широкой публике.Довольно интересная презентация (я еще не целиком ее прочитал, и не все в ней мне понятно), но у меня есть один вопрос.Песецкий использует пример того, как в русском языке слова типа врач могут употребляться и в мужском, и в женском роде: можно сказать "новая врач". При этом он справедливо замечает, что такое существительное может сочетаться с прилагательным и глаголом в разных родах, но не по-любому. Например, можно сказать "новый врач пришла", но нельзя сказать *"новая врач пришел" (лингвисты ставят звездочку перед фразами, которые они хотят отметить как неграмматичные, "так нельзя сказать").Кроме того, пишет он, то же самое наблюдается с сочетанием двух прилагательных. Можно сказать "у меня очень интересная новый врач", но нельзя сказать *"у меня очень интересный новая врач". А вот это мне кажется неверным - по-моему, оба варианта нельзя сказать. Как вы думаете, я прав или нет?
25	http://avva.livejournal.com/2683333.html	а судьи кто	___	___	Время от времени попадаются возмутительные судебные решения, которые принимают судьи в вообще говоря странах с нормально функционирующими, не клерикальными, независимыми судебными системами (т.е. я не говорю о странах типа Саудовской Аравии, где судебная система клерикальна, или России, где она управляется властью). Я в последнее время несколько раз подробно писал о таких случаях. Конечно, надо учесть, что отдельные случаи не доказывают, что у всей системы есть серьезная проблема: возможно, они очень очень очень редки, и становятся известными именно благодаря своей (очень редкой) возмутительности. Возможно, также, что в пересказе заинтересованных лиц и организаций суть этих дел искажается. Но я так не думаю. Я думаю, что случаев, когда судья принимает вопиюще несправедливое решение, много. Не знаю, сколько, но думаю, что минимум - тысячи в небольших странах каждый год, сотни тысяч в больших. Судьи тоже люди, такие как все. Людям свойственны: глупость, невнимание, капризы, идеологическая зашоренность, шкурный интерес... Нет причины считать, что учеба или работа в области юриспруденции до начала судейской карьеры магическим образом меняют людей, или отсеивают всех неподходящих кандидатов. Против судейского произвола или неверных решений есть лекарство: апелляции. Во многих странах есть также другое лекарство: суд присяжных. В обоих случаях решение принимает уже не один человек (судья), а несколько - апелляции обычно рассматривают несколько судей вместе. Вообще передать решение комитету из нескольких человек - обычный способ в человеческом обществе застраховаться от искажений, ошибок, и злоупотреблений единоличного решения. Не всегда это хорошо работает - у комитетов есть свои проблемы, как мы все хорошо знаем - но во многих важных случаях это действительно лучше, чем положиться на одного человека. И рассмотрение судебных апелляций, по всем уровням вплоть до (и особенно) Верховных Судов - явно такой случай.Но, возможно, эта система коррекции неверных решений не очень хорошо работает. Там, где есть суд присяжных, у судьи все равно остается очень много полномочий (и в плане ведения суда, и в формулировке приговора). А суды вышестоящих инстанций часто ограничены в том, что они могут (или хотят) оспорить в решении суда первой инстанции. Кроме того, в современных западных странах это очень дорого - даже суд первой инстанции обходится в огромную сумму из-за расходов на адвокатов. Многие жертвы судебной несправедливости просто не могут себе позволить апелляцию.Теперь вопрос: а почему бы в свете всего этого не назначать несколько судей - ну или минимум двоих - на каждое дело, уже в судах первой инстанции? Если в зале заседает не один судья, а хотя бы двое (а еще лучше трое), выбранные случайным образом из коллегии данного суда, то вероятность откровенно идиотских или несправедливых решений наверняка снизится. По всем процедуральным вопросам они могут принимать решения вместе; если между ними есть разногласия, их можно решать либо большинством (когда есть трое судей или больше), или по какой-то схеме главенства между судьями. У любого судьи должна быть возможность в крайнем, особенно вопиющем случае заявить, что он настолько не согласен с другими, что объявляет отвод всему набору (mistrial), и дело будут заново рассматривать другие судьи.Конечно, все это будет стоить дорого, потому что судей нужно будет в 2-3 раза больше, соответственно и расходы государства на зарплату для них возрастут. Но я не думаю, что расходы на зарплаты судей - это такая уж огромная статья расходов в бюджете, по сравнению с многими другими; ясно, что она не обанкротит государство и не изменит значительным образом баланс бюджета. Если это действительно приведет к резкому снижению вопиющих случаев судебной несправедливости - может, это стоит того?
