Владстон Феррейра Фило Теоретический минимум по Computer Science Все что нужно программисту и разработчику

2018

Переводчик А. Логунов

Технический редактор Н. Суслова

Литературный редактор А. Петров

Художники Л. Егорова, С. Маликова, Р. Яцко

Корректоры Н. Сидорова, Г. Шкатова

Верстка Л. Егорова

© Перевод на русский язык ООО Издательство «Питер», 2018

© Издание на русском языке, оформление ООО Издательство «Питер», 2018

© Серия «Библиотека программиста», 2018

* * *

Друзья — это семья, которую мы сами себе выбираем. Я посвящаю книгу моим друзьям Ромуло, Лео, Мото и Крису, которые постоянно меня торопили, чтобы я ее, наконец, закончил.

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

Лорд Байрон, из письма будущей жене Аннабелле (1813 год).

Их дочь Ада Лавлейс стала первым программистом

Предисловие

Каждый в нашей стране должен научиться программировать, потому что это учит думать.

Стив Джобс

Когда компьютеры начали менять мир, открывая перед людьми беспрецедентные возможности, расцвела новая наука — computer science. Она показала, как использовать компьютеры для решения задач. Это позволило нам использовать весь потенциал вычислительных машин. И мы достигли удивительных, просто сумасшедших результатов.

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

Рис. 1. Компьютерные задачи^[1]

Эта книга — моя скромная попытка помочь миру, а также подтолкнуть вас к эффективному использованию компьютеров. В ней понятия computer science представлены в простой форме. Я свел научные подробности к минимуму. Хочется надеяться, что computer science произведет на вас впечатление, и ваш программный код станет лучше.

Эта книга для меня?

Если вы хотите щелкать задачи как орешки, находя эффективные решения, то эта книга для вас. От вас потребуется только чуть-чуть опыта в написании программного кода. Если вам приходилось этим заниматься и вы различаете элементарные операторы вроде for и while, то все в порядке. В противном случае вы найдете все необходимое (и даже больше) на каких-нибудь онлайновых курсах программирования^[2]. Вы можете пройти такой курс всего за неделю, и притом бесплатно. Для тех же, кто уже знаком с информатикой, эта книга станет превосходным повторением пройденного и поможет укрепить знания.

Но разве computer science не только для ученых?

Эта книга — для всех. Она о вычислительном мышлении. Вы научитесь превращать задачи в вычислимые системы. Вы также будете использовать вычислительное мышление в повседневных задачах. Упреждающая выборка и кэширование помогут вам упростить процесс упаковки вещей. Освоив параллелизм, вы станете эффективнее управляться на кухне. Ну и, разумеется, ваш программный код будет просто потрясающим.

Да пребудет с вами сила! 

Влад

Глава 1. Основы

Информатика не более наука о компьютерах, чем астрономия — наука о телескопах. Информатика неразрывно связана с математикой.

Эдсгер Дейкстра

Компьютерам нужно, чтобы мы разбивали задачи на посильные для них части. Тут нам понадобится немного математики. Не паникуйте, это не высшая математика — написание хорошего программного кода редко требует знания сложных уравнений. В главе 1 вы найдете набор инструментов для решения разных задач. Вы научитесь:

моделировать идеи в блок-схемах и псевдокоде;

отличать правильное от неправильного при помощи логики;

выполнять расчеты;

уверенно вычислять вероятности.

Этого достаточно, чтобы переводить мысли в вычислимые решения.

1.1. Идеи

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

Блок-схемы

Когда разработчики «Википедии» обсуждали организацию коллективной работы, они создали блок-схему дискуссии. Договариваться проще, если все инициативы перед глазами и объединены в общую картину (рис. 1.1).

Компьютерный код, как и изображенный выше процесс редактирования вики-страницы, по существу является процессом. Программисты часто пользуются блок-схемами для изображения вычислительных процессов на бумаге. Чтобы другие могли понимать ваши блок-схемы, вы должны соблюдать следующие рекомендации^[3]:

• записывайте состояния и инструкции внутри прямоугольников;

• записывайте принятие решений, когда процесс может пойти различными путями, внутри ромбов;

• никогда не объединяйте инструкции с принятием решений;

• соединяйте стрелкой каждый последующий шаг с предыдущим;

• отмечайте начало и конец процесса.

Рис. 1.1. Редакционный процесс в «Википедии»^[4]

Рассмотрим составление блок-схемы на примере задачи поиска наибольшего из трех чисел (рис. 1.2).

Рис. 1.2. Поиск наибольшего из трех чисел

Псевдокод

Так же, как блок-схемы, псевдокод выражает вычислительные процессы. Псевдокод — это код, удобный для нашего восприятия, но непонятный для машины. Следующий пример передает тот же процесс, что был изображен на рис. 1.2. Задержитесь на минуту и проверьте, как он работает с разными значениями A, B и C^[5].

function maximum(A, B, C)

····if A > B

·········if A > C

··············max ← A

·········else

··············max ← C

····else

·········if B > C

··············max ← B

·········else

··············max ← C

····print max

Заметили, что этот пример полностью игнорирует синтаксические правила языков программирования? В псевдокод можно вставлять даже разговорные фразы! Когда вы пишете псевдокод, дайте своей творческой мысли течь свободно — как при составлении блок-схем (рис. 1.3 ).

Рис. 1.3. Псевдокод в реальной жизни^[6]

Математические модели

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

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

Загон для скота На ферме содержат два вида домашних животных. У вас есть 100 мотков проволоки для сооружения прямоугольного загона и перегородки внутри него, отделяющей одних животных от других. Как поставить забор, чтобы площадь пастбища была максимальной?

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

l

w

A = w × l

100 = 2w + 3l

Подберем w и l, при которых площадь A будет максимальной.

Подставив l из второго уравнения в первое, получаем:

Да это же квадратное уравнение! Его максимум легко найти при помощи формулы корней квадратного уравнения, которую проходят в средней школе. Квадратные уравнения так же важны для программиста, как мультиварка — для повара. Они экономят время. Квадратные уравнения помогают быстрее решать множество задач, а это для вас самое главное. Повар знает свои инструменты, вы должны знать свои. Математическое моделирование вам просто необходимо. А еще вам потребуется логика.

1.2. Логика

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

Рис. 1.4. Логика программиста^[7]

Для начала мы поэкспериментируем с логическими высказываниями и операторами. Затем научимся решать задачи с таблицами истинности и увидим, как компьютеры опираются на логику.

Операторы

В математике переменные и операторы (+, ×, −, …) используются для моделирования числовых задач. В математической логике переменные и операторы указывают на достоверность. Они выражают не числа, а истинность (true) или ложность (false). Например, достоверность выражения «Если вода в бассейне теплая, то я буду плавать» основывается на достоверности двух вещей, которые можно преобразовать в логические переменные A и B:

A: Вода в бассейне теплая.

B: Я плаваю.

Они либо истинны (true), либо ложны (false)^[8]. A = True обозначает теплую воду в бассейне, B = False обозначает «Я не плаваю». Переменная B не может быть наполовину истинной, потому что я не способен плавать лишь отчасти. Зависимость между переменными обозначается символом , условным оператором. A B выражает идею, что A = True влечет за собой B = True:

A B: если вода в бассейне теплая, то я буду плавать.

При помощи других операторов можно выражать другие идеи. Для отрицания идеи используется знак! оператор отрицания.!A противоположно A:

!A: Вода в бассейне холодная.

!B: Я не плаваю.

Противопоставление. Если дано A B, и я при этом не плаваю, что можно сказать о воде в бассейне? Теплая вода влечет за собой плавание, потому, если его нет, вода в бассейне не может быть теплой. Каждое условное выражение имеет противопоставленный ему эквивалент:

Для любых двух переменных A и B

A B тождественно! B !A.

Еще пример: если вы не умеете писать хороший код, значит, вы не прочли эту книгу. Противопоставлением данному суждению является такое: если вы прочли эту книгу, значит, вы умеете писать хороший код. Оба предложения сообщают одно и то же, но по-разному^[9].

Двусторонняя условная зависимость. Обратите внимание, что высказывание «Если вода в бассейне теплая, то я буду плавать» не означает: «Я буду плавать только в теплой воде». Данное высказывание ничего не говорит насчет холодных бассейнов. Другими словами, A B не означает B A. Чтобы выразить оба условных суждения, используйте двустороннюю условную зависимость:

A <—> B: Я буду плавать, если и только если вода в бассейне теплая.

Здесь теплая вода в бассейне равнозначна тому, что я буду плавать: знание о воде в бассейне означает знание о том, что я буду плавать, и наоборот. Опять же, остерегайтесь обратной ошибки: никогда не предполагайте, что B A следует из A B.

AND, OR и XOR. Эти логические операторы — самые известные, поскольку они часто записываются в исходном коде в явном виде — AND (И), OR (ИЛИ) и XOR (исключающее ИЛИ). AND возвращает True, если все идеи истинны; OR возвращает True, если любая идея истинна; XOR возвращает True, если идеи взаимоисключающие. Представим вечеринку, где подают водку и вино:

A: Вы пили вино.

B: Вы пили водку.

A OR B: Вы пили.

A AND B: Вы пили и то и другое.

A XOR B: Вы пили, не смешивая.

Проверьте, правильно ли вы понимаете, как работают эти операторы. В табл. 1.1 перечислены все возможные комбинации двух переменных. Обратите внимание, что A B тождественно! A OR B, а A XOR B тождественно!(A <—> B).

Таблица 1.1. Логические операции для четырех возможных комбинаций A и B

Булева алгебра

Булева алгебра^[10] позволяет упрощать логические выражения точно так же, как элементарная алгебра упрощает числовые.

Ассоциативность. Для последовательностей, состоящих только из операций AND или OR, круглые скобки не имеют значения. Так же, как последовательности только из операций сложения или умножения в элементарной алгебре, эти операции могут вычисляться в любом порядке.

A AND (B AND C) = (A AND B) AND C;

A OR (B OR C) = (A OR B) OR C.

Дистрибутивность. В элементарной алгебре мы раскрываем скобки: a × (b + c) = (a × b) + (a × c). Точно так же и в логике выполнение операции AND после OR эквивалентно выполнению операции OR над результатами операций AND и наоборот:

A AND (B OR C) = (A AND B) OR (A AND C);

A OR (B AND C) = (A OR B) AND (A OR C).

Правило де Моргана^[11]. Одновременно лета и зимы не бывает, поэтому у нас либо не лето, либо не зима. С другой стороны, оба выражения «не лето» и «не зима» истинны, если (и только) у нас не тот случай, когда либо лето, либо зима. Согласно этой логике, выполнение операций AND может быть сведено к операциям OR и наоборот:

!(A AND B) =!A OR! B;

!A AND!B =!(A OR B).

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

Перегрев сервера Сервер выходит из строя из-за перегрева, когда кондиционирование воздуха выключено. Он также выходит из строя из-за перегрева, если барахлит кулер. При каких условиях сервер работает?

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

A: Сервер перегревается.

B: Кондиционирование отключено.

C: Не работает кулер.

D: Сервер вышел из строя.

(A AND B) OR (A AND C) D.

Используя правило дистрибутивности, выведем за скобки A:

A AND (B OR C) D.

Сервер работает, когда! D. Противопоставление записывается так:

!D !(A AND (B OR C)).

Применим правило де Моргана и раскроем скобки:

!D !A OR!(B OR C).

Воспользуемся правилом де Моргана еще раз:

!D !A OR (!B AND!C).

Данное выражение нам говорит, что когда сервер работает, мы имеем либо! A (он не перегревается), либо! B AND!C (все в порядке и с кондиционированием воздуха, и с кулером).

Таблицы истинности

Еще один способ анализа логических моделей состоит в сверке данных со всевозможными сочетаниями ее переменных. Каждой переменной в таблице истинности соответствует свой столбец. Строки представляют комбинации состояний переменных.

Рис. 1.5. Таблицы со всеми возможными сочетаниями от одной до пяти логических переменных

Одна переменная требует двух строк: в одной она имеет значение True, в другой — False. Чтобы добавить переменную, нужно удвоить число строк. Новой переменной задается True в исходных строках и False — в добавленных (рис. 1.5). Размер таблицы истинности увеличивается вдвое с каждым добавлением переменной, поэтому такую таблицу оправданно использовать лишь в случаях, когда переменных немного^[12].

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

Хрупкая система Предположим, что мы должны создать систему управления базами данных с соблюдением следующих технических требований:

1) если база данных заблокирована, то мы можем сохранить данные;

2) база данных не должна блокироваться при заполненной очереди запросов на запись;

3) либо очередь запросов на запись полна, либо полон кэш;

4) если кэш полон, то база данных не может быть заблокирована.

Возможно ли это? При каких условиях станет работать такая система?

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

A: База данных заблокирована	1: A —> B
B: Есть возможность сохранить данные	2:!(A AND C).
C: Очередь запросов на запись полна	3: C OR D.
D: Кэш полон	4: D —>!A.

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

Таблица 1.2. Таблица истинности для проверки четырех выражений

Все технические требования удовлетворяются в состояниях с 9-го по 11-е и с 13-го по 15-е. В этих состояниях A = False, а значит, база данных не может быть заблокирована никогда. Обратите внимание, что кэш не заполнен лишь в состояниях 10 и 14.

Чтобы проверить, чему вы научились, попробуйте разгадать загадку «Кто держит зебру?»^[13]. Это известная логическая задача, ошибочно приписываемая Альберту Эйнштейну. Говорят, что только 2 % людей могут ее решить, но я сильно сомневаюсь. Используя большую таблицу истинности и правильно упрощая и объединяя логические высказывания, вы ее разгадаете, я уверен в этом.

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

А теперь давайте взглянем на самое впечатляющее применение логики: проектирование электронно-вычислительных машин.

Логика в вычислениях

Группы логических переменных могут представлять числа в двоичной форме^[14]. Логические операции в случае с двоичными числами могут объединяться для расчетов. Логические вентили выполняют логические операции с электрическим током. Они используются в электрических схемах, выполняющих вычисления на сверхвысоких скоростях.

Логический вентиль получает значения через входные контакты, выполняет работу и передает результат через выходной контакт. Существуют логические вентили AND, OR, XOR и т. д. Значения True и False представлены электрическими сигналами с высоким и низким напряжением соответственно. Сложные логические выражения можно вычислять таким образом практически мгновенно. Например, электрическая схема на рис. 1.6 суммирует два числа.

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

Рис. 1.6. Схема суммирования двухразрядных чисел, передаваемых парами логических переменных (A₁A₀ и B₁B₀) в трехразрядное число (S₂S₁S₀)

Рис. 1.7. Вычисление 2 + 3 = 5 (в двоичном формате это 10 + 11 = 101)

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

Когда-то логические вентили изготавливали с использованием больших, неэффективных и дорогих электрических реле. Когда на смену реле пришли транзисторы, стало возможным массовое производство логических вентилей. Люди находили все новые и новые способы делать транзисторы меньше^[15]. Принципы работы современного центрального процессора (ЦП) по-прежнему построены на булевой алгебре. Современный ЦП — это просто схема, которая состоит из миллионов микроскопических контактов и логических вентилей, управляющих электрическими потоками информации.

1.3. Комбинаторика

Важно уметь считать вещи правильно, ведь в случае с вычислительными задачами вам придется делать это много раз^[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! и получим:

 вариантов.

Но задача еще не решена. Нужно учесть ориентацию пар нуклеотидов.

Следующие два примера не тождественны: ...