С радостью отмечаю, что моих читателей на мякине не проведёшь. Задача про взвешивание девяти шаров не стала для подавляющего большинства чем-то серьёзным. Подавляющее большинство читателей дало изумительный по своей тривиальности ответ (конечно, правильный): «Взвешиваем 4 и 4 шара. Если весы в равновесии, то дефектный — оставшийся. Если нет — поступаем по алгоритму, описанному для восьми шаров (третий вариант взвешивания)». Несколько иных ответов также сводили задачу к взвешиванию восьми шаров.

Изначально я планировал после девяти шаров предложить тем же путём взвесить двенадцать, но теперь смысла не вижу — ответ ясен. Могу предложить дать ответ на вопрос о том, из какого максимального количества шаров можно выявить дефектный за три взвешивания на плечевых весах? Если кому интересно, может дать свой вариант ответа здесь (комментарии скрываться не будут, поскольку ответ достаточно простой).

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

Дано n одинаковых на вкус, цвет, объём и другие физические характеристики, кроме массы, шаров. Из них ровно один дефектный, отличающийся от остальных по массе. Найти минимальное количество взвешиваний на обычных плечевых весах, которое со стопроцентной достоверностью выявит дефектный шар.

Tags: Наука

(2 комментария | Оставить комментарий)

Ещё раз, что ли, взвесим шары?	17 Апр, 2008 @ 10:13

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

( Варианты решения )

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

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

Tags: Наука

(31 комментарий | Оставить комментарий)

Взвесим шары?	10 Апр, 2008 @ 11:28

Пусть никто из читателей не ищет в наименовании темы скрытый смысл. На рассмотрение предлагаю интересную задачу про взвешивание. Предыдущий опыт показал, что интересные задачи востребованы читателями, поэтому и предлагаю на рассмотрение ещё одну. Естественно, с дальним прицелом (конкретнее — прицел направлен на проект ТС/ТУ), так что прошу читателей активно участвовать в решении. Тем более, что в этот раз (и последующие) я буду скрывать комментарии, так что подсмотреть не удастся.

Итак, задача. Дано 8 (восемь) одинаковых на вид шаров, из которых один отличается по весу, причём неизвестно, в какую сторону. К этим шарам прилагаются обычные плечевые весы, на которых можно сопоставлять веса шаров и их групп (можно попарно взвешивать сами шары и группы шаров друг с другом — один с одним, два с двумя и т. д.). Необходимо выявить дефектный шар за три взвешивания.

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

Tags: Наука

(92 комментария | Оставить комментарий)

Гипергеометрическое распределение против суверенной демократии	14 Мар, 2008 @ 11:38

Я уже упоминал, что математики давно разобрались с демократией (а особенно с так называемыми «демократическими выборами»). Пришло время кое-что добавить в эту корзину. Ежели кто помнит, то пару недель назад я опубликовал несложную вероятностную задачу для читателей, которая заключалась в поиске вероятности для определённой выборки. Тогда несколько человек дали абсолютно верный ответ, но никто не стал задумываться о том, какие прикладные следствия имеет эта задача.

Итак, нижеследующая формула является формулой для расчёта значений гипергеометрического распределения, которое используется для моделирования количества удачных выборок без возвращения из совокупного множества элементов, в которых имеются элементы с дефектами:

Что она может дать? Всё очень просто. Абсолютно также недавно я рассматривал миф о том, что Россия должна принадлежать нерусским на тех же самых условиях, что и Русским. В этом рассмотрении изучался национальный состав «республики» Адыгея, где при 65 % Русского населения в выборном органе власти Русские занимают всего 40 % мест. Вышеприведённая формула как раз и позволит рассчитать вероятность такого события. Впрочем, рассчитывать вероятность в данном случае достаточно сложно, поскольку числа слишком большие, а вот оценить весьма несложно. На языке Haskell был быстро написан набор функций для оценки вероятностей:

combination :: Double -> Double -> Double
combination k n = product [(k + 1)..n] / product [1..(n - k)]

probability k' k n' n = (combination k' n' * combination (k - k') (n - n')) / combination k n

probabilities k n' n = [probability k' k n' n | k' <- [0..k]]

maxProbability k n' n = getMax $ zip (probabilities k n' n) [0..k]
  where
    getMax l = getMax' l (0, 0)

    getMax' []          v      = v
    getMax' ((x, n):ps) (y, m) = if (x > y)
                                   then getMax' ps (x, n)
                                   else getMax' ps (y, m)

При помощи этих функций, к примеру, можно оценить вероятность существующего положения в выборном органе власти «республики» Адыгея. Она находится где-то около 6.3 %. Другими словами, подобное положение, какое мы наблюдаем наяву, могло получиться лишь в шестидесяти трёх случаях из тысячи при равномерном распределении представителей всех национальностей при выборах (а именно такое и ожидается в случае демократических выборов). Максимальная же вероятность имеет распределение мест в выборном органе, при котором Русские занимают около 70 % мест — вероятность этого события чуть выше 26 %.

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

Tags: Выборы, Наука, ФП

(34 комментария | Оставить комментарий)

Рассчитаем вероятности?	2 Мар, 2008 @ 11:20

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

Дано n шаров, из которых n' белых и, соответственно, (n - n') чёрных. Из этих n шаров случайным образом отбирают k шаров. Соответственно, среди этих отобранных шаров оказалось k' белых и (k - k') чёрных.

Какова вероятность p выпадения именно полученного соотношения из k' белых и (k - k') чёрных шаров (расположение шаров в выборке не имеет значения) при условии полностью случайного выбора?

Tags: Наука

(53 комментария | Оставить комментарий)

Other entries

» Железнодорожное моделирование и конечные автоматы

Поскольку я долгое время работал на железной дороге, то в том году упросил сына попросить у Деда Мороза на новый год в качестве подарка железнодорожную модель в немецком исполнении. Дед Мороз не заставил себя долго упрашивать и принёс под ёлку стартовый набор «Пожарный поезд» от немецкой компании PIKO. Сын, конечно, был весьма рад, ну и я немного радовался. Дополнительно Снегурочка подарила нам дополнительные рельсы для более мощных путевых развитий.

Сегодня мы можем выкладывать вполне себе изящные путевые развития. Вот давеча выложили такое:

Запустили по нему два локомотива, причём один ехал по часовой стрелке, а другой против. Но они никогда не сталкивались, потому как скорости у них были одинаковые, а стрелки переключались сами (механически) таким образом, что локомотивы всегда разъезжались в местах разъезда. Стрелку переключает сам локомотив, когда наезжает на неё с плюса или минуса (в соответствующую сторону и переключает).

Вот смотрели мы на это дело, смотрели, а потом я понял, что всё это дело вполне себе можно моделировать при помощи конечных автоматов. Быстро набросал на бумаге диаграмму, из которой путём несложных оптимизаций сделал автомат, состоящий всего из четырёх состояний и четырёх же переходов из состояния в состояние. После этого я вспомнил, что у меня на книжной полке имеется замечательная книга, которую и хочу представить читателям:

Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. — М.: Вильямс, 2007. — 528 стр. — ISBN 978-5-8459-1347-0. Рекомендую всем, интересующимся программированием и информационными технологиями, к покупке. Книга хороша тем, что позволяет программисту понять многие глубинные смыслы того, что называется «искусством программирования» (а то сегодня некоторые программисты даже не обладают базовым математическим образованием). Вместе с тем, книга не занудна, читается легко. Так что весьма рекомендую.

26 Фев, 2008 @ 10:31

(10 комментариев | Оставить комментарий)

» Катаморфизм и прочие интересные вещи

Те мои читатели, что заинтересованы в изучении функционального программирования, наверняка будут обрадованы такой информацией. На русском общеобразовательном ресурсе «Традиция» я открыл тему ФП, λ-исчисления, комбинаторной логики и теории категорий (а также всего остального, что с этими областями научной деятельности связано). Ведь «Традиция» — это именно общеобразовательный ресурс, который основан на технологии «Вики», что позволяет каждому участвовать в создании и проработке материалов. К тому же он лишён многих недостатков википедии, где имеется обширное педерастическое лобби.

Сейчас я время от времени занимаюсь переносом материалов, переводом интересных статей и написанием новых. Из числа последнего: статья «Катаморфизм», которая выставляется в категорию «хорошие статьи» (правда, критерии «хорошести» ещё неопределенны). Кроме того, ресурс можно использовать для перевода материалов из иностранных источников (например, статья «Изоморфизм Карри-Говарда» постепенно переводится в настоящий момент).

Так что всех интересующихся и небезразличных объявленным темам прошу присоединяться.
24 Май, 2007 @ 20:08

(3 комментария | Оставить комментарий)

» История как формальная система

Время от времени ко мне приходят мысли о том, что представители гуманитарного научного сообщества как-то не так, не совсем правильно понимают предмет науки. Ведь как учат технических специалистов в технических же учебных заведениях? Наука, прежде всего, строит некоторую модель той области объектного мира, которая является объектом её пристального внимания. Человек и человеческое общество не может выйти за рамки своей чувственной сферы, а потому создаваемые модели всегда будут приблизительными, описательными. И сказано, что таковые модели принимаются тогда, когда они приносят определённую пользу: являются непротиворечивыми, более или менее полными и позволяют решать определённые задачи. Пока модель отвечает таким признакам, она используется. Как только в рамках модели находятся какие-то противоречия, модель либо пересматривается и дополняется, либо отвергается.

В математике давно уже́ формализовали (и не единственным способом) такой подход к освоению и описанию действительности. Одним из подходов к описанию того, о чём веду речь, является понятие формальной системы. Вот определение из БСЭ:

Формальная система — неинтерпретированное исчисление, класс выражений (формул) которого задаётся обычно индуктивно — посредством задания исходных («элементарных», или «атомарных») формул и пра́вил образования (построения) формул, а подкласс доказуемых формул (теорем) — посредством задания системы аксиом и пра́вил вывода (преобразования) теорем из аксиом и уже́ доказанных теорем.

В технических науках такой подход используется повсеместно. Ближайший пример — физика, где имеются различные модели действительности для разных областей применения, которые, к тому же сосуществуют вместе, хотя иной раз некоторыми своими положениями противоречат друг другу; например, механика Ньютона и квантовая механика. Странно то, что я не наблюдаю такого подхода в гуманитарной сфере.

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

Хронологическая соотнесённость событий, историческая трактовка их — обо всём этом мы никогда и ни при каких условиях не сможем сказать с достаточной степенью достоверности. Всё, что мы получаем от наших предков, является лишь «уликами», которые могут помочь (да, именно так) нам построить некоторое описание того, что было в прошлом. Модель прошлого. Именно модель, но не объективное описание прошлой действительности. И, само собой, таких моделей может быть несколько, даже и противоречащих друг другу. Но пока модель является работающей, пока её можно использовать для тех или иных целей, она живёт.

Кстати, это отлично понимают наши недруги, которые пользуются тем, что многие не понимают этого, а потому будут «хавать» те модели, которые им будут навязываться кукловодами. Поэтому-то в области истории наблюдается столько явных и неявных образчиков манипуляции. Так что, как говорится, sapienti sat.
12 Апр, 2007 @ 18:05

(22 комментария | Оставить комментарий)

» Про «олимпиады» и конкурсы

А вот, что мне подумалось, и, сдаётся мне, что мысль сия может быть интересна адептам функционального программирования. Я как-то не нашёл у нас каких-либо конкурсов или «олимпиад» по программированию, связанных с функциональным программированием. За кордоном таковые конкурсы проводятся регулярно, некоторые из адептов в них участвуют и даже занимают серьёзные позиции. Но у нас этого явно нет.

А посему в целях пропаганды ФП и популяризации оного интересно было бы подумать насчёт организации подобных мероприятий. Можно начать, скажем, с организации небольшого конкурса для школьников и студентов, на котором предложить какие-нибудь непростые задачи математического плана для решения в функциональном стиле на каком-нибудь интересном языке. Если получится, то можно идти далее — завязаться с каким-нибудь ВУЗом, типа МГУ, МИФИ или МФТИ, где сильны позиции ФП, а там и проводить подобные мероприятия на регулярной основе.

Много ли для сего надо с организационной и финансовой точек зрения?
2 Апр, 2007 @ 18:17

(2 комментария | Оставить комментарий)

» Кое-что о комбинаторе I

Напишу нынче кое-какие мысли, которые пришли мне на ум некоторое время назад, когда я экспериментировал с комбинаторной логикой, комбинаторами и их представлением на языке Haskell. Интерес возник в связи с комбинатором I, который обычно выражается в базисе S, K как SKK. Однако можно легко заметить, что в этом выражении на третьем месте может стоять произвольный объект, поскольку он уничтожается канцеллятором K:

SKKx =_S Kx(Kx) =_K x
Т. е. выражение комбинатора тождества I в базисе S, K может быть и таким: SKS, и таким: SK(KK), и таким: SK(SK) и многим каким ещё. Почему же в теории выбрано именно представление SKK?

Ответ на этот вопрос даёт типизация. Дело в том, что в изначальной комбинаторной логике типов у комбинаторов нет. Но, поскольку комбинаторы являются функциями, им можно приписать типы. Это сделать достаточно просто, глядя на комбинаторные характеристики. Поэтому можно выписать типы базовых комбинаторов S и K:

S :: (a -> b -> g) -> (a -> b) -> a -> g

K :: a -> b -> a

Здесь-то и кроется ответ на поставленный вопрос. Конечно, в нетипизированной комбинаторной логике можно принять любое представление комбинатора I, но если перейти к типам, то нужно будет заботиться об их согласовании, а поэтому так просто выразить какой-либо комбинатор в базисе не удастся — необходимо следить за типами. Поэтому, принимая в расчёт типы, можно посмотреть, что будет при аппликации комбинаторов SKK. Первая аппликация SK даст новый объект, имеющий тип (a -> b) -> a -> a. Как видно из сигнатуры, этот объект ожидает на вход два параметра — функцию из a в b и некий объект типа a. Вторая аппликация (SK)K произведёт унификацию типов (и здесь весьма тонкий момент), при которой исходная переменная типа b примет значение (b -> a) из типа комбинатора K. Впрочем, это не важно, поскольку эта часть в выводе всё равно не участвует (на то K и канцеллятор), а потому тип объекта (SK)K будет (a -> a). Т. е. тип комбинатора тождества I.

Если же подобным образом рассматривать выражение SKS, то будет видно, что после первой аппликации произвести унификацию типов не удастся, как бы этого не хотелось. И вот возникает вопрос — почему «отцы» комбинаторной логики изначально приняли выражение комбинатора I за SKK — они видели проблему типизации, или это получилось случайно?

Также задаю вопрос адептам функционального программирования для самостоятельной проработки и закрепления материала. Какие возможные представления комбинатора тождества I в базисе S, K не дадут проблем с унификацией типов (предложенное решение — не единственно)?
26 Мар, 2007 @ 17:54

(17 комментариев | Оставить комментарий)

Top of Page Разработано LiveJournal.com