Thursday, April 23, 2009

Анекдот из эпохи DOS -2 (ЮМОР)

Диггер спросил как-то т. Комманда Кома: "За что же, Вы, т. Комманд Ком, отца Вындоуза так не любите?".
"Мышами от него воняет", - быстро ответил тот.

Индийские проблемы усугубляют тревожную ситуацию с продовольствием во всем мире.


...недобор урожая [в провинции Пенджаб в Индии] в этом году может быть самым большим за последние 20 лет...

...в Пенджабе выращивается 44% всей индийской пшеницы. В этом году, только согласно официальным прогнозам, сбор зерна на в штате должен уменьшиться с 16 млн тонн до 9 млн тонн. Причина — неблагоприятные погодные условия: так, если в январе-феврале в Пенджабе была небывалая засуха, то весь апрель шли сильнейшие дожди, которые буквально смыли остатки урожая...

Индийские проблемы усугубляют тревожную ситуацию с продовольствием во всем мире. Засухи и неурожаи в Северной и Южной Америке, Китае и ряде других стран и регионов значительно сократили сбор зерновых по всему миру, что неизбежно погонит цены на продукты питания вверх в самом ближайшем будущем. И ударит это, в свою очередь, прежде всего по странам с сильной зависимостью от мировых рынков...

http://bfm.ru/news/2009/04/22/indii-grozit-golod.html

Банк и головная боль (ЮМОР)

Если вы должны банку сто тысяч, то это ваша головная боль, если вы должны банку сто миллионов, то это уже головная боль банков.

Тест на выживаемость

Мое мнение о «Чёрном Лебеде» Нассима Николаса Талеб. Часть II

UPDATE: Продолжение, начало тут Часть I

Давыдов в который раз прорекламировал книгу Талеба, от него просто тащится. По его наводке я начал читать перевод на русский его книги. Я читаю главы по мере их появления и пока прочитал чуть больше половины книги. Однако, оставшаяся часть посвящена психологическим моментам, которые, конечно, сами по себе интересны, но они не являются основой (core) мировоззрения Талеба.

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

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

Ниже есть продолжение.

Утверждение. Пустое множество является подмножеством любого множества. Иначе говоря, $\forall A ~ (\emptyset \subseteq A)$.
Доказательство. Возьмём произвольное множество $A~$. Нам нужно доказать, что если мы переберём все варианты элементов с $\emptyset$, то мы их обязательно обнаружим в $A$. Перебор всех вариантов, являясь один из способов доказательства, в данном случае не подходим и вот по чему. Говоря более формально, нам нужно доказать, что для любого $x$, если $x \in \emptyset$, то $x \in A$. Проблема в том, что, согласно определению пустого множества, нет таких $x$, так как $~ \forall x ~ (x \notin \emptyset)$. Если мы не можем перебирать варианты, то что мы можем сделать? Мы можем воспользоваться асимметрией, которую заметил Талеб "перевернув" утверждение. Каким образом? Используя доказательство от противного.
Допустим (от противного), что утверждение, которое нам нужно доказать, что ($\forall x ~ x \in \emptyset\Rightarrow x \in A$) ложно. В таком случае, существует $x$, такой что $x \in \emptyset$, но $x \notin A$. В частности, существует $x$, такой что $x \in \emptyset$. Но это противоречит определению пустого множества (см. выше). Мы пришли к противоречию. Значит наше допущение (от противного) было неверно, а значит было верно утверждение. Что и требовалось доказать.

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

Задача $1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{n(n + \frac12)(n + 1)}{3}$ для всех натуральных значений $n$.
Доказательство. Опять-таки, согласно Талебу, чтобы доказать такое утверждение, нужно обязательно перебрать все возможны значения $n$. Недостаточно убедиться, что утверждение верно, скажем для первой сотни. Также недостаточно сделать случайную выборку из $n$. Одним из способов доказательства, служит использование метода математической индукции. Я не буду здесь приводить ни сам метод не доказательство это равенства (его можно найти здесь, пример 2.2). Важно лишь понимать, что натуральные числа имеют "врождённое свойство", принцип, который помогает сделает "обобщение". При этом сам этот "принцип математической индукции" эквивалентен "принципу существования минимума", т.е. он может быть доказан как теорема. Это является частным случаем, когда проблема индукции успешно решена. Замечу, что этот принцип используется также при построении натурального ряда (он вводится либо в качестве аксиомы, либо выводиться в качестве теоремы).

Утверждение. Все простые числа нечётные.
Замечание. Для простоты будем рассматривать только натуральные числа.
Доказательство. Для начала попробуйте доказать это утверждение сами. Не получается? Тогда я помогу. Натуральное простое число - это такое число, которое не имеет делителей, кроме самого себя и единицы. Нечетное число, это такое число, которое не имеет 2 в качестве делителя.

Для удобства ведён обозначение. $a \dag b~$ обозначает, что "а не делиться на b", т.е. $\neg (\exists x ~ a*x=c)$

На этот раз сначала приведём доказательства, а "доказательство Талеба" оставим на закуску. Итак, возьмём любое простое число, назовём его $p~$, т.е. число, у которого нет делителей, кроме самого себя и единицы. Нужно доказать, что $2 \dag p~$, т.е. для этого числа двойка также не является делителем. Итак, имеем, что $\forall a \quad (1 \lt a \lt p) \quad a \dag p \Rightarrow \forall a \quad (1 \lt a\lt p) \quad a \dag p$, из этого следует, что $\forall a \quad (2\le a \lt p) \quad a \dag p)~$. В частности, вместо $a~$ можно взять $2~$ и тогда получим, что $2 ~ \dag p~$. Что и требовалось доказать.

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

Доказательство другим способом.
Допустим (от противного), что утверждение, неверно. Т.е., что существует чётное простое число... Вы всё ещё продолжаете читать? Перечитайте последнюю фразу. Чётное простое число. Вы такого случайно не знаете. Как насчёт двойки? Это число простое ($2=2*1~$) и чётное. Вместо того чтобы прийти к противоречию, мы нашли контр-пример. Другими словами, нам удалось фальсифицировать утверждение.

Но как так может быть. Одним способом, нам удалось доказать, а другим опровергнуть одно и то же утверждение. Правильно, так не бывает. Это значит, что мы допустили ошибку либо в первом либо во втором доказательстве. Я её допустил намеренно, чтобы вас проверить.

Как же знать, где ошибка? Отвлечёмся от доказательства. Мы имеем утверждение, что все простые числа нечётные. Мы имеем контр-пример, или «чёрного лебедя». 2 безусловно является простым числом и безусловно чётным. Неважно, какое бы доказательством бы не было, этот пример, демонстрирует, что оно неверно. Мы "случайно", в процессе другого способа "передоказать" утверждение, обнаружили, что оно неверно. Имея контр-пример, т.е. сертификат о фальсификации данного утверждения, мы можем быть уверены, что оно неверно.

Очевидно, что доказывать от противного неверное утверждение это нонсенс. Мы никогда не придём к противоречию.

Попробуем перечитать первое доказательство и найти в нём ошибку. Попробуйте перечитать его сначала сами, подставляя $p=2~$. Нашли ошибку?

Давайте повторим процесс доказательстве чуть медленнее. Итак, возьмём любое простое число $p$. Нужно доказать, что $2 \dag p~$ Итак, имеем, что $\forall a ~ (1 \lt a \lt p) \quad a \dag p~$. Это, так сказать, дано. Если $a \gt 1~$ и $а~$ натуральное число, то из этого следует, что $a>=2~$. Здесь подвоха нет. Из этого следует, что $\forall a ~ (2 \le a \lt p) \quad a \dag p~$. Далее, мы легкомысленно подставили $a=2$. В таком случаем, получим $(2\le 2\lt p) \quad 2 \dag p~$. $2\le 2~$ очевидно верно. Но выполняться ли $2\lt p~$? Если $p \gt 2~$, то, очевидно, выполняется. И можем продолжить доказательство. Собственно, это значит, что $2 \dag p~$. Что и требовалось доказать. Но что если $p=2~$? В этом случае выражение будет иметь такой вид $(2\le 2\lt 2) \quad 2 \dag 2~$. Очевидно, что это выражение ложно, т.к. $2 \lt 2~$ ложно, а значит и $(2\le 2\lt 2)~$ ложно; $2 \dag 2~$ тоже ложно. Напомню, это вывод из того, что нам "дано" после того как мы попытались подставить значения в кванторы. В итоге, мы получили ложное утверждение, а значит подстановка наша (последняя $p=2~$) была неправомерна. Значит этот особый случай, который нужно проверить отдельно от основного доказательства. До этого места мы доказали утверждения для всех случаев, кроме случае $p=2~$. В случае $p=2~$, как мы видели выше утверждение не работает и доказательство тоже. Однако, мы можем "исправить" утверждение, которое будет верно.

Исправленное утверждение. Все простые числа, кроме двух, нечётные.

Это утверждение мы доказали выше.

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

Вернёмся на секунду к изначальному утверждению. Оно гласило, что "Все простые числа нечётные." Обозначим множеством $V~$ (от verification, верификация) все те значения, при которых утверждено верно. Обозначим множеством $F~$ (от falsification, фальсифицируемость) множество значений, при которых утверждение ложно. Что мы можем сказать о них? Ну, во первых, очевидно, что $V \subseteq \mathbb{N}~$ и $F \subseteq \mathbb{N}~$, так как мы условились, что нашей предметной областью являются натуральные числа. Так же очевидно, что $V \cap F = \mathbb{N}~$, так как это утверждение либо истинно либо ложно. Более того $V \cap F = \emptyset~$, так как утверждение не может быть и истинным и ложным одновременно. Из последних двух равенств следует, что $\bar V = \mathbb{N} \setminus \{V\} = F ~$ и $\bar F = \mathbb{N} \setminus \{F\}= V ~$.

Выше мы доказали, что $F = \{2\}~$ и $V = \mathbb{N} \setminus \{2\}~$. Давайте задумаемся на секундочку.

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

Однако, способ перебора является не единственно возможным. Можно попытаться доказать это утверждение и иным способом. В случае, если $F = \emptyset~$ эффективным приёмом может оказаться доказательство от противного, можно также попытаться его использовать когда $F~$ чётко выраженную структуру, в самом простом случае конечно, чтобы можно было "исправить" утверждение.

UPDATE: Продолжение, начало тут Часть I
Продолжение следует.

Oracle покупает Sun Microsystems за 7 миллиардов долларов

http://txt.newsru.co.il/arch/finance/21apr2009/oracle_sun_601.html
http://www.cnbc.com/id/30305213/
http://it.themarker.com/tmit/article/6440"