21. Пусть V — множество вершин и E — множество ребер графа, причем ребро e ∈ E соединяет вершины x,y ∈V. Что означают предикаты P(x,y), Q(e, x, y), R(x,e)?
22. Каким десятичным числам соответствуют следующие двоичные числа: а) 1011; б) 1000110; в) 110100111?
23. Переведите в двоичную систему счисления десятичные числа: а) 51; б) 64; в) 125; г) 1000.
24. Выполните в двоичной системе следующие операции над десятичными числами: 21 + 37; 31 + 105; в) 25 · 8; г) (8 + 19) · 11; д) 24 · 8 — 17. Проверьте полученные результаты в десятичной системе.
25. Переведите в двоичную систему счисления с точностью до пяти двоичных знаков после запятой числа: а) 0,131; б) 0,25; в) 175,26.
26. Дайте обоснование правил перевода десятичных числе в двоичные.
27. Сложите двоичные числа 11001110 и 11010111 по обычному правилу и по модулю два. Найдите разность полученных результатов и объясните ее смысл.
6. Вероятности
1. Случайные события. Познание закономерностей объективного мира позволяет выявлять связи между событиями (или явлениями) и условиями, которые определяют их появление. Если можно указать комплекс условий, при каждой реализации которого событие неизбежно происходит, то это событие называется достоверным. Событие, которое заведомо не может произойти при реализации данного комплекса условий, называется невозможным. Очевидно,
- 73 -
невозможность события равносильна достоверности противоположного события.
Однако предсказать с полной определенностью наступление того или иного события удается далеко не всегда. Это связано с тем, что часто указываемый комплекс условий не отражает всей совокупности причинно-следственных связей между явлениями. Либо вызывающие данное событие причины еще недостаточно изучены, либо учет всей совокупности причин настолько сложен, что практически целесообразно ограничить комплекс условий наиболее существенными и поддающимися контролю. Возникающая при этом неопределенностью является признаком случайных событий.
Случайное событие относительно некоторого комплекса вполне определенных условий может произойти, а может и не произойти. Примеры случайных событий: перегорание лампочки через 1000 ч работы, попадание в цель при обстреле тремя снарядами, выпадание пяти очков при бросании игральной кости, победа киевского «Динамо» в предстоящем футбольном чемпионате и т.п.
2. Вероятность. Возможность появления случайного события А при реализации комплекса условий S оценивается количественной мерой, которая называется вероятностью и обозначается как P(A/S) или короче P(A). Обычно вероятность достоверного события принимается равной единице, а невозможного события нулю. Тогда для любого события 0 ≤ P(A) ≤ 1, а вероятность случайного события выражается положительным числом, меньшим единицы.
Интуитивно ясно, что событие тем более вероятно, чем чаще оно происходит в рассматриваемых условиях. Таким образом, вероятность P(A/S) непосредственно связана с частотой появления события А при многократном повторении комплекса условий S. С увеличением числа таких повторений, называемых испытаниями, частота все более точно характеризует значение вероятности.
Закономерности, присущие случайным событиям, имеют массовый характер и называются вероятностными или стохастическими. Они играют большую роль в науке и технике при исследовании сложных явлений, проектировании и планировании.
Существует много различных подходов к определению вероятности, которые обычно сводятся к описанию практических приемов ее вычисления. Основные из них рассматриваются ниже.
3. Классическое (комбинаторное) определение. Если из общего числа n равно возможных и несовместных исходов (случаев) событию А благоприятствуют m исходов, то вероятность события А
Например, при подбрасывании монеты возможны два исхода — выпадение герба (Г) и цифры (Ц). Эти исходы можно считать равно
- 74 -
возможными (никакой из них не имеет преимущества перед другим) и несовместными (они не могут появиться вместе). Поэтому вероятность герба равна 1/2. Такая же вероятность и выпадания цифры. Полученный результат говорит о том, что при многократных подбрасываниях монеты примерно в половите случаев выпадает греб, причем этот результат тем ближе к действительности, чем больше число испытаний. При подбрасывании двух монет число всех исходов равно четырем {ГГ, ГЦ, ЦГ, ЦЦ}. Вероятность выпадения двух гербов (как и двух цифр) равна 1/4, но герб и цифра будут появляться с вероятностью 2/4 = 1/2, поскольку этому событию благоприятствую два исхода {ГЦ, ЦГ}.