Группы логических переменных могут представлять числа в двоичной форме[14]. Логические операции в случае с двоичными числами могут объединяться для расчетов.
Логический вентиль получает значения через входные контакты, выполняет работу и передает результат через выходной контакт. Существуют логические вентили AND, OR, XOR и т. д. Значения True и False представлены электрическими сигналами с высоким и низким напряжением соответственно. Сложные логические выражения можно вычислять таким образом практически мгновенно. Например, электрическая схема на рис. 1.6 суммирует два числа.
Давайте посмотрим, как работает эта схема. Не поленитесь, проследите за ходом выполнения операций, чтобы понять, как устроена магия (рис. 1.7).
Рис. 1.6. Схема суммирования двухразрядных чисел, передаваемых парами логических переменных (
Рис. 1.7. Вычисление 2 + 3 = 5 (в двоичном формате это 10 + 11 = 101)
Чтобы воспользоваться преимуществом этого быстрого способа вычислений, мы преобразуем числовые задачи в двоичную (логическую) форму. Таблицы истинности помогают моделировать и проверять схемы. А булева алгебра — упрощать выражения и, следовательно, схемы.
Когда-то логические вентили изготавливали с использованием больших, неэффективных и дорогих электрических реле. Когда на смену реле пришли транзисторы, стало возможным массовое производство логических вентилей. Люди находили все новые и новые способы делать транзисторы меньше[15]. Принципы работы современного центрального процессора (ЦП) по-прежнему построены на булевой алгебре. Современный ЦП — это просто схема, которая состоит из миллионов микроскопических контактов и логических вентилей, управляющих электрическими потоками информации.
1.3. Комбинаторика
Важно уметь считать вещи правильно, ведь в случае с вычислительными задачами вам придется делать это много раз[16]. Математика далее будет еще более сложной, чем раньше, но не пугайтесь. Кое-кто полагает, что ему не стать хорошим программистом только потому, что, как ему кажется, математик он так себе. Если хотите знать, лично я завалил школьный экзамен по математике
Никто не захочет зубрить формулы и пошаговые процедуры, если он уже сдал выпускные экзамены. Если такая информация вдруг понадобится — ее легко отыскать в Интернете. Расчеты не обязательно делать от руки на бумаге. От программиста в первую очередь требуется интуиция. Познания в комбинаторике и умение решать комбинаторные задачи развивает эту интуицию. Так что давайте поработаем с несколькими инструментами по порядку: с умножением, перестановками, сочетаниями и суммами.
Правило умножения
Если некоторое событие происходит
Взлом кода
Две цифры можно набрать 100 способами (00–99), букву — 26 способами (A — Z). Следовательно, всего существует 100 × 26 = 2600 PIN-кодов. В худшем случае, чтобы подобрать правильный, нам придется перепробовать их все. Через 2600 секунд (то есть через 43 минуты) мы его точно взломаем.
Формирование команды
До начала набора есть всего один вариант состава — вы сами. Далее каждый бросок монеты удваивает число возможных вариантов. Это должно быть сделано 23 раза, таким образом, вам нужно посчитать, чему равно 2 в степени:
Обратите внимание, что один из этого множества вариантов — когда в команде состоите только вы.
Перестановки
Если у нас