Теоретический минимум по Computer Science

И еще одно формирование команды 23 человека хотят в вашу команду. В отношении каждого вы подбрасываете монету и принимаете его, только если выпадает «орел». Каковы шансы, что вы возьмете семь человек или меньше?

Да, это трудно посчитать. Если вы будете долго искать в Интернете, то в конечном счете придете к биномиальному распределению. Вы можете визуализировать его в Wolfram Alpha[21], набрав: B(23,l/2) <= 7.

Подведем итоги

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

Раздел 1.1 объяснил, почему и как мы должны излагать мысли в письменной форме. Для наших задач мы создаем модели и применяем к ним концептуальные инструменты.

Раздел 1.2 познакомил с инструментами из булевой алгебры для работы с формальной логикой и таблицами истинности.

Раздел 1.3 показал важность теории вероятности и комбинаторики для решения задач разного рода. Быстрый приблизительный подсчет может показать вам, стоит ли браться за дальнейшие вычисления. Программисты-новички часто теряют время, анализируя слишком много сценариев.

Наконец, раздел 1.4 объяснил основные правила, позволяющие подсчитать вероятность чего-либо. Это бывает очень полезно при разработке решений, которые должны взаимодействовать с нашим дивным, но неопределенным миром.

Таким образом, мы в общих чертах обрисовали множество важных аспектов того, что ученые называют дискретной математикой. Еще больше интересного можно почерпнуть из приведенных ниже материалов или просто найти в «Википедии». Например, вы можете воспользоваться принципом Дирихле, чтобы доказать, что в Нью-Йорке по крайней мере у двух человек одинаковое число волос в шевелюре!

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

Полезные материалы

• Дискретная математика и ее применения, 7-е издание (Discrete Mathematics and Its Applications, см. https://code.energy/rosen).

• Слайды профессора Жаннет Уинг, иллюстрирующие вычислительное мышление, см. https://code.energy/wing.

Глава 2. Вычислительная сложность

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

Ада Лавлейс

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

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

На меньшее количество операций нужно меньше вычислительной мощности. Нам нравятся быстрые решения, поэтому мы следим за числом операций в наших алгоритмах. В случае со многими алгоритмами необходимое число операций быстро растет с увеличением объема входных данных. В нашем случае может потребоваться всего несколько операций для сортировки 26 карт, но в четыре раза больше операций для сортировки 52 карт!

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

рассчитывать и интерпретировать временные сложности;

выражать их рост при помощи необычной нотации «О большое»;

избегать экспоненциальных алгоритмов;

убедиться, что у вашего компьютера достаточно памяти.

Но прежде нам предстоит узнать, как определяется временная сложность алгоритма.

Временная сложность записывается как: T(n). Она показывает количество операций, которые алгоритм выполняет при обработке входящих данных объема n. Также T(n) называют стоимостью выполнения алгоритма. Если наш алгоритм сортировки игральных карт подчиняется T(n) = n², то мы можем предсказать, насколько больше потребуется времени, чтобы отсортировать колоду двойного размера: .

Надейтесь на лучшее, но готовьтесь к худшему