События

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

Вероятность суммы двух совместных событий равна сумме вероятностей этих событий минус вероятность их совместного появления:
p(A + B) = p(A) + p(B) - p(AB).

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

Вероятность суммы двух несовместных событий равна сумме вероятностей этих событий:
p(A + B) = p(A) + p(B).

Зависимые события – такие события, появление одного из которых влияет на появление другого события.

Вероятность произведения двух зависимых событий равна произведению одного из них на условную вероятность другого:
p(A * B) = p(A) * p(В/А) = p(B) * p(А/В).

Независимые события – такие события, появление одного из которых не влияет на появление другого события.

Вероятность произведения двух независимых событий равна произведению вероятностей этих событий:
p(A*B) = p(A)*p(B).

Противоположное событие - событие, являющееся обратным по отношению к какому либо событию.

Например успешному шансу появления четверки на игральной кости будет являться 1/6. А противоположностью этого события будет являться шанс, что кость не выпадет, то есть 5/6.

Вероятность противоположного события равна единице, минус вероятность этого события

Формула полной вероятности:
Вероятность события А, которое может произойти одновременно с одним из n попарно несовместимых событий Н1, Н2, ... Нn , называемых гипотезами, образующих полную группу событий, равна:

p(A)=p(H1)*p(A/H1)+p(H2)*p(A/H2)+...+p(Hn)*p(A/Hn)

Пример1:

Вероятность попадания в цель при стрельбе первого и второго орудий соответственно равны:
р(А) = 0,7 и р(В) = 0,8.
Найти вероятность событий:
а) попадания при одном залпе (из обоих орудий) хотя бы одним из них;
б) попадание при одном залпе из обоих орудий.

Здесь события совместимы и независимы. Поэтому используем соответствующую формулу:

В случае (а):
p(A + B) = p(A) + p(B) - p(AB) = 0,7+0,8-0,7*0,8 = 0,94
или 1-(1-0,7)*(1-0,8) = 0,94

Вслучае (б):

p(A*B) = p(A)*p(B) = 0,7*0,8 = (или) 7/10 + 8/10 = 0,56

Пример2:

В первой коробке содержится 20 радиоламп, из них 18 стандартных, во второй коробке - 10 ламп, из них 9 стандартных. Из второй коробки наудачу взята лампа и переложена в первую. Найти вероятность того, что лампа, наудачу извлеченная из первой коробки, будет стандартной.

В таком, с одной стороны сложном примере, всего-то нужно использовать формулу полной вероятности:

А - событие "лампа, наудачу извлеченная из первой коробки, будет стандартной";
Н1 - событие "из второй коробки переложена стандартная лампа";
Н2 - событие "из второй коробки переложена нестандартная лампа".

p(H1)=9/10;
p(H2)=1/10;
p(A/H1)=19/21; (Так как в коробке +1 стандартная лампа)
p(A/H2)=18/21; (Так как в коробке +1 не стандартная лампа)
p(A) =p(H1)*p(A/H1)+p(H2)*p(A/H2) = 9/10*19/21+1/10*18/21 = 189/210 = 0,9

Использовались материалы отседова:
http://www.spcpa.ru/learning/zao/v7.html

Класическое опртеделение теории вероятностей

Вероятностью события является сумма вероятностей исходов, благоприятствующих этому событию.

Ну а если же вероятное пространство построено из равно возможных исходов - то класическая теорема примет вид:

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

Другими словами если мы кидаем одну игральную кость, то шанс выпада четверки будет 1/6.
Где 1 - число благоприятствующих событий (четверка ведь в кости одна), а 6 - общее число исходов (всего 6 сторон у игральной кости)

Так же вероятность представляется в виде:

1. Простой дроби: 1/6
2. Десятичной дроби: 0.1666666(6)
3. Процентах 16.66%
   

Основные правила комбинаторики

Правило сложения и правило умножения

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

Например один злостный взломщик кода подбирает пароль, состоящий из 6 символов. И он точно знает, что первые два символа - это цифры (0-9) а последующие четыре - буквы (a-g(всего 7)). Но вот только одного он не помнит, либо первые два символа - это все-таки буквы, а последующие четыре не иначе как цифры (вот так вот пароль криво подслушал).

Что бы рассчитать все возможные варианты такого перебора можно воспользоваться правилами сложения и умножения:

1. В случае если первые 2 - цифры, остальные буквы: 7^2*10^4 = 490000
2. В случае если первые 2 - буквы, остальные цифры: 10^2*7^4 = 240100
3. Эти два варианта были несовместимыми множествами, т.к. друг к другу перебором никак не относятся. Поэтому остается их только сложить и получить количество комбинаций.

Полностью расчет будет выглядеть так:

Теорема о включениях и исключениях

(потом еще допишу)

Сочетания с повторениями

Хех ну здесь штука хоть и замысловатее, но все равно полезная.

Допустим у нас есть склад котлет, всего на складе 9 сортов этих самых котлет =)
А нам-то надо всего ничего, эдак штук 45, не больше не меньше. При чем пока спит сторож мы эти 45 котлет тягаем в полной темноте и вообще не ясно какой сорт оказался в сумке, лишь бы оказался.
И тут можно высчитать количество комбинаций из 45 котлет со всевозможными сортами. Тут могут быть и все котлеты одного сорта и все полностью разного и т.п.
Все это легко и просто считается по формуле:А полностью формула выглядит вот так:

Сочетания без повторений

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

А вот допустим нужно просто сунуть руку в карман с 20 разными монетами достать оттуда эдак штук 6 и переложить в другой карман. Ясное дело в кармане они будут лежать как небольшая кучка, ни разу не упорядоченная. Вот тут-то и применяется сочетание.
И будет решаться вот так вот:

Перестановки с повторениями

А вот здесь хоть на вид и сложнее, чем в перестановках без повторений, но на самом деле все предельно просто. Главное сразу понять зачем они нужны, эти перестановки с повторениями. И вроде про это нормально нигде не написано.

Итак допустим такая ситуация, передо мной стоит (уже) четыре чашки одинаковой раскраски, но две кружки с чаем и две кружки с кофе.
С одной стороны возможные варианты комбинаций можно высчитать просто 4!
Но с другой то стороны, мы имеем 2 абсолютно одинаковые кружки с кофе и 2 абсолютно одинаковые кружки с чаем. Из этого следует, что если в комбинации:

(кофе)D (чай)D (кофе)D (чай)D

Поменять местами кружки с кофе, то от этого комбинация абсолютно не изменится.
Поэтому идем другим путем и рассчитываем по новой формуле:
Где n - количество всех элементов, n1 - количество элементов первого типа, n2 - количествово элементов второго типа и т.п.

И теперь правильно считаем по правильной формуле:

Вот всего-то получается комбинаций.

Перестановки без повторений

Это пожалуй одно из самых примитивов комбинаторики.
Перестановки - это когда надо тупо что-то с чем-то поменять местами и посмотреть сколько из этого может выйти комбинаций

Например стоит у меня на столе 5 разных кружек, с не скажу каким содержимым. И вот с чего-то взбрендило меня их переставлять местами и при этом считать сколько может быть вариантов. Тут уже можно догадаться, что за содержимое кружек даже не прибегая к теории вероятностей :D

Ну так вот. Что бы высчитать все возможные комбинации - совсем не надо вот так их тупо двигать, а всего навсего высчитать факториал из их количества. То есть в этом случае 5!

Ну а что бы не возникало никаких вопросов, почему же все-таки факториал, можно провести небольшое расследование:

1. Итак допустим у нас только одна кружка. Сколькими же способами ее можно расставить :) Конечно же одним! Но по математически, это будет 1*1 ибо дальше будет понятно.
2. А вот в случае двух кружек? Тут уже посчитать сложнее и придется умножить возможные варианты перестановки одной кружки, уже на 2.
3. А вот теперь 3 кружки. Тут уже сложнее, но деваться некуда. Если две кружки можно было переставить только двумя способами - то тут уже эти два способа множим на три!
4. Ну и четыре кружки так же предыдущую расстановку умножаем на 4.
5. Ну и с пятой круженцией то же самое.
   

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

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

P.s. В кружки надо что-то другое наливать, интересней было бы...

Размещения без повторений

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

А что если ячейками является несколько стульев, а элементами люди? Очевидно, что на трех разных стульев не может сидеть один и тот же человек (Конечно если он не наберется наглости и не ляжет вдоль стульев, чем эффектно испортит весь эксперимент). Вот как раз в такие моменты и используется формула размещения без повторения которая выглядит вот так:
Где m - количество элементов, а k - количество ячеек.

m! - рассчитывает все возможные варианты комбинаций данных элементов.
(m-k)! - все возможные варианты элементов оставшихся без ячеек.
Разделив одно на другое - каким-то боком узнаем, все варианты размещения без повторений О_о

Это была удобная продвинутая формула. Но так же есть и более простая. То есть если так же выбрать кто будет сидеть на трех стульях из 14 человек, можно не вспоминать то нечто ужасное с восклицательными знаками, а просто перемножить таким образом:

14 (садим одного на стул)*13(посадили еще одного)*12(и еще одного, 3 стула заняты)=2184 комбинации. Если подставить в формулу выше - получим тот же ответ.

И накой же нам тогда верхняя формула с факториалами? А на тот случай, если стульев окажется эдак 80, а человек эдак 120. Не перемножать же все долгой длинной цепочкой =)

Где все это применяется, уже очевидно. Осталось только привести несколько хитрых примеров:

Известно, что бы нейтрализовать студента П. (гыгы) требуется 4 человека, всего кандидатов на эту должность 230 человек. Сколькими комбинациями можно нейтрализовать студента П.
Ответ таков: Или 230*229*228*227 = (нейтрализовали)
Или 230!/(230-4)! = (нейтрализовали)

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

Или так: На балл пришло 74 гусара и 55 дам. Гусары кинулись расхватывать дам, пока была возможность. И кто успел - нашел себе пару. Сколько могло получиться комбинаций с гусаров и дам.
Здесь даже и не хочется использовать простой метод, потому как аж 55 раз перемножать число (хотя фига тут с одной стороны). Но с хорошим калькулятором (или таблицей факториалов от 1 до 100) легко и просто высчитываем:
74!/(74-55)!= и смотрим как долго гусары могли бегать за дамами =)

Размещения с повторениями

Итак размещения с повторениями - это случай, когда из некоторого количества (n) элементов выбирают (m) элементов, при чем каждый из элементов n может повторяться сколько угодно раз или вообще отсутствовать.

Сама формула выглядит так:

Применение:

Например, что бы высчитать комбинацию кодового замка из шести цифр достаточно возвести число 10 (цифры ячейки замка от 0 до 10) в степень 6 (всего ячеек у замка).

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

Если подытожить то эта формула применяется к чему угодно, где есть модель такого рода:

(От такого рода, не дописал еще какого!)

Это все примеры были с постоянным числом возможных переменных. А что если попадется задача такого типа:
Всего сидит 5 картежников. У троих на руках по две карты, а у двоих по четыре. Если они походят какой-либо картой одновременно, то воспользуемся методом умножения и возможных комбинаций будет столько:

То есть просто разделяем объекты по одинаковым переменным, возводим каждый в степень и перемножаем.

Сессия

Думал начать писать в блоге начиная с арифметики и дальше

Разложение числа на множители

Будем раскладывать скажем число 360 на множители простым способом:

Итак, смотрим на что делится 360, а делится оно на: 2, 3, 5, 9, 10. Из этих чисел выбираем, которое больше нравится (мну нравится 3, она же неофициальная "зю") и делим на него:

360 / 3 = 120

Повторяем ситуацию с числом 120, оно делится на 2, 3, 5. Возьмем теперь эдак 5:

120 / 5 = 24

Смотрим, делится на 2, 3 возьмем 3

24 / 3 = 8

Ну и остается три раза на 2 поделить восемь:

8 / 2 = 4
4 / 2 = 2
2 / 2 = 1

Теперь выписываем все, на что мы делили и получаем: 2, 2, 2, 3, 5, 3 и ежели это перемножить - то получим исходное число 360.

Спрашивается: вот к чему вообще оно надо это разложение?

Конечно же для того, что бы взломать Криптосистему RSA! Вон оно оказывается чему в школе учат. :) Правда тут для разложения используют "Функцию Эйлера", которую я вспомню позднее.

Ну и еще это все надо для того, что бы найти "Наибольший общий делитель"(НОД) и "Наименьшее общее кратное"(НОК)

НОД

Возьмем два числа 360 и 420, разложим их и будем высматривать нечто одинаковое:

360 = 2*2*2*3*3*5
420 = 2*2*3*5*7

Теперь это одинаковое просто перемножим:

2 * 2 * 3 * 5 = 60

Выходит наибольший общий делитель это число 60.

НОК

Чтобы найти НОК - так же разложим число 360 и 420, только на этот раз добавим одному из них недостающие члены:

360 = 2*2*2*3*3*5
420 = 2*2*3*5*7

НОК = 2*2*3*5*7*2*3 = 2520

Проверка:

360 * 420 = НОД(60) * НОК(2520)
151200 = 151200

Вот все и сошлось.

Признаки делимости целых чисел

Основная теорема арифметики:

Каждое натуральное число, кроме 1, может быть разложено на простые множители единственным образом.

Признаки делимости целых чисел:

• Число делится на 2, если его последняя цифра 0, 2, 4, 6, 8.
• Число делится на 3, если сумма его цифр делится на 3. (Ха, помню надо было написать часть кода, где нужно было найти массив чисел, делящихся на 3 без остатка. И естественно это простое правило не вспомнил)
• Число делится на 4, если число из двух последних цифр делится на 4. (аналогично)
  
• Число делится на 5, если его последняя цифра 0 или 5.
• Число делится на 6, если оно делится на 2 и на 3.
• Число делится на 7, если
  
• Число делится на 9, если сумма его цифр делится на 9.
• Число делится на 10, если последняя цифра числа 0.
  

Приступимс...

В общем-то этот блог надо было начать еще лет эдак 6-7 назад, но увы, не начал. Теперь придется все наверстывать и вспоминать. И это, на самом деле, очень хорошо :)

Итак самые примитивные примитивы:

N - Множество натуральных чисел: 1, 2, 3, 4, 5, ... ∞.
Бывают простыми - с делителем, равным единице (1, 2, 3, 5, 7, 11, 13, 17, ... ∞)
И составными - с делителем, отличным от единицы (4, 6, 8, 9, 10, ... ∞)

Z - Множество Целых чисел: (-∞ ... , -3, -2, -1, 0, 1, 2, 3 ... ∞)

Z0 - Множество положительных целых чисел: 1, 2, 3, 4, ... ∞
Делятся на четные (2, 4, ... ∞) и нечетные (1, 3, ... ∞)

Q - Множество рациональных чисел - это:

• Целые числа (Z)
  
• Обыкновенная положительная или отрицательная дробь n/m, где n принадлежит множеству Z, а m множеству N
• Конечная или бесконечная периодическая, положительная или отрицательная десятичная дробь
  

I - Множество иррациональных чисел: бесконечная, десятичная непериодическая дробь (√2, π, ... )

R - Множество действительных чисел, рациональные, иррациональные, положительные
или отрицательные.

Так же имеет смысл представить вот такую схему:

Где видно, что каждый старший тип числа содержит в себе более младший.