Важно уметь считать вещи правильно, ведь в случае с вычислительными задачами вам придется делать это много раз[16]. Математика далее будет еще более сложной, чем раньше, но не пугайтесь. Кое-кто полагает, что ему не стать хорошим программистом только потому, что, как ему кажется, математик он так себе. Если хотите знать, лично я завалил школьный экзамен по математике , и все же я стал тем, кем хотел . В школе дают совсем не ту математику, которая делает людей хорошими программистами.
Никто не захочет зубрить формулы и пошаговые процедуры, если он уже сдал выпускные экзамены. Если такая информация вдруг понадобится — ее легко отыскать в Интернете. Расчеты не обязательно делать от руки на бумаге. От программиста в первую очередь требуется интуиция. Познания в комбинаторике и умение решать комбинаторные задачи развивает эту интуицию. Так что давайте поработаем с несколькими инструментами по порядку: с умножением, перестановками, сочетаниями и суммами.
Правило умножения
Если некоторое событие происходит n разными способами, а другое событие — m разными способами, то число разных способов, которыми могут произойти оба события, равно n × m. Вот пара примеров.
Взлом кода Предположим, что PIN-код состоит из двух цифр и латинской буквы. На то, чтобы ввести код один раз, уходит в среднем одна секунда. Какое максимальное время потребуется, чтобы подобрать правильный PIN-код?
Две цифры можно набрать 100 способами (00–99), букву — 26 способами (A — Z). Следовательно, всего существует 100 × 26 = 2600 PIN-кодов. В худшем случае, чтобы подобрать правильный, нам придется перепробовать их все. Через 2600 секунд (то есть через 43 минуты) мы его точно взломаем.
Формирование команды Допустим, 23 человека хотят вступить в вашу команду. В отношении каждого кандидата вы подбрасываете монету и принимаете его, только если выпадет «орел». Сколько всего может быть вариантов состава команды?
До начала набора есть всего один вариант состава — вы сами. Далее каждый бросок монеты удваивает число возможных вариантов. Это должно быть сделано 23 раза, таким образом, вам нужно посчитать, чему равно 2 в степени:
вариантов команды.
Обратите внимание, что один из этого множества вариантов — когда в команде состоите только вы.
Перестановки
Если у нас n элементов, то мы можем упорядочить их n! разными способами. Факториал числа имеет взрывной характер, даже с малыми значениями n он дает огромные числа. На случай, если вы с ним не знакомы:
n! = n × (n — 1) × (n — 2) … × 2 × 1.
Легко заметить, что n! — это общее количество способов упорядочивания n элементов. Сколькими способами можно выбрать первый элемент из n? После того как он будет выбран, сколькими способами можно выбрать второй? Сколько вариантов останется для третьего? Подумайте об этом некоторое время, а потом переходите к примерам[17].
Коммивояжер Ваша транспортная компания осуществляет поставки в 15 городов. Вы хотите знать, в каком порядке лучше объезжать эти города, чтобы уменьшить расход топлива. Если на вычисление длины одного маршрута требуется микросекунда, то сколько времени займет вычисление длины всех возможных маршрутов?
Любая перестановка 15 городов дает новый маршрут. Факториал — это количество различных комбинаций, так что всего существует 15! = 15 × 14 × … × 1 ≈ 1,3 трлн маршрутов. Число микросекунд, которые уйдут на их вычисление, примерно эквивалентно 15 дням. Будь у вас не 15, а 20 городов, вам бы понадобилось 77 тысяч лет.
Совершенная мелодия Девушка разучивает гамму из 13 нот. Она хочет, чтобы вы показали все возможные мелодии, в которых используется 6 нот. Каждая нота должна встречаться один раз на мелодию, а каждая такая мелодия должна звучать в течение одной секунды. О какой продолжительности звучания идет речь?
Мы должны подсчитать количество комбинаций по 6 нот из 13. Чтобы исключить неиспользуемые ноты, нужно остановить вычисление факториала после шестого множителя. Формально — это количество возможных комбинаций m из n возможных элементов. В нашем случае получится:
= 1 235 520 мелодий.
Чтобы их все прослушать, потребуется 343 часа, так что вам лучше убедить девушку найти идеальную мелодию каким-нибудь другим путем.
Перестановки без повторений
Факториал n! дает завышенное число способов упорядочивания n элементов, если некоторые из них одинаковые. Лишние комбинации, где такие элементы просто оказываются на других позициях, не должны учитываться.
Если в последовательности из n элементов r идентичны, существуют r! способов переупорядочить их. То есть n! включает r! таких комбинаций. Чтобы получить число уникальных комбинаций, нужно разделить n! на этот излишек. Например, число различных сочетаний букв E в CODE ENERGY равняется .
Игры с ДНК Биолог изучает сегмент ДНК, связанный с генетическим заболеванием. Тот состоит из 23 пар нуклеотидов, где 9 должны быть A — T, а 14 — G — C.
Ученый хочет выполнить моделирование на всех возможных сегментах ДНК, где есть такое количество пар нуклеотидов. Сколько задач ему предстоит выполнить?
Сначала вычислим все возможные комбинации этих 23 пар нуклеотидов. Затем, чтобы учесть повторяющиеся пары нуклеотидов A-T и G-C, разделим результат на 9! и на 14! и получим:
вариантов.
Но задача еще не решена. Нужно учесть ориентацию пар нуклеотидов.
Следующие два примера не тождественны:
Для каждой последовательности из 23 пар нуклеотидов существует 223 различных сочетаний ориентации. Потому общее количество комбинаций равно:
817 190 × 223 ≈ 7 трлн.
И это только для крошечной последовательности всего из 23 пар нуклеотидов, где мы знаем распределение! Наименьшая воспроизводимая ДНК, которая известна на сегодняшний день, — это ДНК крохотного цирковируса свиней, и в ней 1800 пар нуклеотидов. Код ДНК и жизнь в целом с технологической точки зрения по-настоящему удивительны. Просто с ума можно сойти: ДНК человека имеет около 3 млрд пар нуклеотидов, продублированных в каждой из 3 трлн клеток тела.
Комбинации
Представьте колоду из 13 игральных карт только пиковой масти . Сколькими способами вы сможете раздать шесть карт своему сопернику? Мы уже видели, что — это количество перестановок 6 карт из 13. Поскольку порядок их следования не имеет значения, нужно разделить это число на 6! чтобы получить
комбинаций.
Бином — это количество способов, которыми можно извлечь m элементов из ряда, состоящего из n элементов, независимо от порядка их следования:
Конструкция в левой части (запись бинома) читается как «из n по m»[18].
Шахматные ферзи У вас есть пустая шахматная доска и 8 ферзей, которые допускается ставить на доске где угодно. Сколькими разными способами можно разместить фигуры?
Шахматная доска поделена на 64 клетки, 8 × 8. Число способов выбрать 8 клеток из 64 составляет млрд[19].
Правило суммирования
Подсчет сумм последовательностей часто встречается при решении комбинаторных задач. Суммы последовательных чисел обозначаются прописной буквой «сигма» (). Такая форма записи показывает, как выражение будет суммироваться для каждого значения i:
выражение с участием i.
Например, суммирование первых пяти нечетных чисел записывается так:
.
Обратите внимание: чтобы получить слагаемые 1, 3, 5, 7 и 9, вместо i последовательно используются числа от 0 до 4 включительно. Следовательно, сумма первых n натуральных чисел составляет:
Когда гениальному математику Гауссу было 10 лет, он устал от суммирования натуральных чисел одного за другим по порядку и нашел такой ловкий прием:
Догадаетесь, каким образом Гаусс это обнаружил? Объяснение приема приведено в приложении II. Давайте посмотрим, как можно его использовать для решения следующей задачи.
Недорогой перелет Вы должны слетать в Нью-Йорк в любое время в течение следующих 30 дней. Цены на авиабилеты изменяются непредсказуемо в соответствии с датами отъезда и возвращения. Сколько пар дней необходимо проверить, чтобы отыскать самые дешевые билеты для полета в Нью-Йорк и обратно на ближайшие 30 дней?
Любая пара дней между сегодняшним (день 1) и последним (день 30) допустима при условии, что возвращение будет в тот же день или позже, чем отъезд. Следовательно, 30 пар начинаются с 1-го дня, 29 пар начинаются со 2-го дня, 28 — с 3-го и т. д. И есть всего одна пара, приходящаяся на последний день. Таким образом, 30 + 29 + … + 2 + 1 — общее количество пар, которое нужно рассмотреть. Мы можем записать это как и использовать удобную формулу Гаусса:
пар.
Кроме того, мы можем решить эту задачу при помощи комбинаций, выбрав 2 дня из 30. Порядок не имеет значения: на более ранний день придется отъезд, на более поздний — возвращение. Таким образом, мы получим . Что-то не то… Дело в том, что мы должны учесть еще и случаи, когда прибытие и отъезд приходятся на одну дату. Так как дней всего 30, следовательно, .
1.4. Вероятность
Принципы случайности помогут вам разобраться в азартных играх, предсказании погоды или проектировании системы резервного хранения данных с низким риском отказа. Принципы эти просты, и все же большинство людей понимают их неправильно.
Рис. 1.8. Случайное число[20]
Сейчас мы применим наши навыки решения комбинаторных задач к вычислению вероятностей. Затем мы узнаем, каким образом различные типы событий используются для решения задач. Наконец, мы увидим, почему азартные игроки проигрываются в пух и прах.
Подсчет количества возможных вариантов
Бросок кубика имеет шесть возможных результатов: 1, 2, 3, 4, 5 и 6. Шансы получить 4, следовательно, составляют . А какова вероятность выпадения нечетного числа? Это может произойти в трех случаях (когда на кубике будет 1, 3 или 5), потому шансы составляют . Вероятность того, что некое событие произойдет, выражается такой формулой:
Она работает, потому что каждый возможный исход одинаково вероятен. Кубик имеет ровные грани, и человек, бросающий его, нас не обманывает.
Еще одно формирование команды Снова 23 человека хотят вступить в вашу команду. В отношении каждого кандидата вы подбрасываете монету и принимаете его, только если она падает «орлом». Какова вероятность, что вы никого не возьмете?
Мы уже убедились, что существует 223 = 8 388 608 возможных вариантов состава команды. Вам придется рассчитывать только на себя в одном-единственном случае: если в результате подбрасывания монеты выпадут 23 «решки» подряд. Вероятность такого события равна P(никто) = . Если посмотреть на это с высоты птичьего полета, то вероятность того, что конкретный рейс коммерческой авиакомпании потерпит крушение, составляет порядка 1 из 5 млн.
Независимые (совместные) события
Если вы одновременно бросаете монету и кубик, то шанс получить «орел» и 6 равняются , или 8 %. Когда исход одного события не влияет на исход другого, их называют независимыми. Вероятность получить сочетание конкретных результатов двух независимых событий равна произведению вероятностей каждого из них.
Резервное хранение Вам нужно организовать хранение данных в течение года. Один диск имеет вероятность сбоя 1 на 1 млрд. Другой стоит 20 % от цены первого, но в его случае вероятность сбоя — 1 на 2000. Какой диск вам следует купить?
Если вы решите использовать три дешевых диска, то потеряете данные, только если все три выйдут из строя. Вероятность того, что это произойдет, равняется . Риск потери данных оказывается гораздо ниже, чем в случае с дорогим диском, а заплатите вы всего 60 % от его стоимости.
Несовместные события
Бросок кубика не может одновременно дать 4 и нечетное число. Вероятность получить либо 4, либо нечетное число, следовательно, равняется . Когда два события не могут произойти одновременно, они несовместные, или взаимоисключающие. Если вам нужно подсчитать вероятность любого из нескольких несовместных событий, просто просуммируйте их индивидуальные вероятности.
Выбор подписки Ваш интернет-сервис предлагает три тарифа: бесплатный, основной и профессиональный. Вы знаете, что случайный посетитель выберет бесплатный тариф с вероятностью 70 %, основной — с вероятностью 20 % и профессиональный — с вероятностью 10 %. Каковы шансы, что человек подпишется на платный тариф?
Перечисленные события несовместны: нельзя выбрать и основной, и профессиональный тарифы одновременно. Вероятность, что пользователь подпишется на платный тариф, равняется 0,2 + 0,1 = 0,3.
Взаимодополняющие события
Выпавшее на кубике количество очков не может одновременно оказаться кратным трем (3, 6) и не делящимся на три, но оно определенно будет относиться к одной из этих категорий чисел. Вероятность получить результат, кратный трем, равняется , следовательно, вероятность получить число, которое не делится на три, равняется . Когда два несовместных события охватывают все возможные варианты, их называют взаимодополняющими, или соподчиненными. Сумма вероятностей взаимодополняющих событий равна 100 %.
Игра «Защита башни» Ваш замок защищен пятью башнями. Каждая имеет 20 %-ную вероятность поразить захватчика, прежде чем он достигнет ворот. Каковы шансы остановить его?
Вероятность поразить врага равна 0,2 + 0,2 + 0,2 + 0,2 + 0,2 = 1, или 100 %, верно? Неверно! Никогда не суммируйте вероятности независимых событий, не совершайте распространенной ошибки. Вместо этого используйте взаимодополняющие события дважды следующим образом.
• 20 %-ный шанс поразить врага — взаимодополняющий для 80 %-го шанса промахнуться. Вероятность того, что не попадут все башни, составляет 0,85 ≈ 0,33.
• Событие «все башни промахнулись» — взаимодополняющее для события «по крайней мере одна башня попала». Значит, вероятность остановить врага равна 1–0,33 = 0,67.
«Заблуждение игрока»
Если вы подбросили монету 10 раз и получили 10 «орлов», увеличилась ли от этого вероятность, что на 11-м броске выпадет «решка»? Или будет ли вероятность выигрыша в лотерею комбинации из шести последовательных чисел от 1 до 6 ниже, чем любой другой комбинации?
Не становитесь жертвой «заблуждения игрока»! Уже случившееся никак не влияет на результат независимого события. Никак. Никогда. В по-настоящему случайно разыгрываемой лотерее вероятность выпадения любого конкретного числа точно такая же, как любого другого. Нет никакой закономерности, согласно которой числа, редко выпадавшие в прошлом, должны чаще выпадать в будущем.
Более сложные вероятности
Можно было бы и дальше рассказывать о вероятности, но рамки раздела не позволяют этого. Всегда, занимаясь решением сложных задач, подыскивайте дополнительные инструменты. Вот пример.
И еще одно формирование команды 23 человека хотят в вашу команду. В отношении каждого вы подбрасываете монету и принимаете его, только если выпадает «орел». Каковы шансы, что вы возьмете семь человек или меньше?
Да, это трудно посчитать. Если вы будете долго искать в Интернете, то в конечном счете придете к биномиальному распределению. Вы можете визуализировать его в Wolfram Alpha[21], набрав: B(23,l/2) <= 7.