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

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

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

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

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

• Клейнберг Дж., Традос Е. Алгоритмы: разработка и применение. СПб.: Питер, 2017.

• Выбор стратегии проектирования алгоритмов (Choosing Algorithm Design Strategy, Shailendra Nigam, см. https://code.energy/nigam).

• Динамическое программирование (Dynamic programming, by Umesh V. Vazirani, см. https://code.energy/vazirani).

Глава 4. Данные

Хорошие программисты беспокоятся о структурах данных и их отношениях.

Линус Торвальдс

Контроль над данными в computer science имеет принципиальное значение: вычислительные процессы состоят из операций над данными, которые преобразуют вход в выход. Но алгоритмы обычно не конкретизируют, как они выполняются. К примеру, алгоритм merge (см. раздел «Итерация» главы 3) опирается на неустановленный внешний исходный код, который создает списки чисел, проверяет наличие в них элементов и добавляет эти элементы в списки. Алгоритм queens (раздел «Поиск (перебор) с возвратом») делает то же самое: он не заботится о том, как выполняются операции на шахматной доске или как позиции хранятся в памяти. Эти детали скрыты позади так называемых абстракций. В главе 4 мы узнаем:

как абстрактные типы данных делают код чистым;

какие общие абстракции желательно знать и уметь ими пользоваться;

какие существуют способы структурирования данных в памяти.

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

Абстракции

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

В программном обеспечении процедурные абстракции скрывают за вызовом процедур сложности реализации процесса. В алгоритме trade (см. раздел «Разделяй и властвуй» главы 3) процедуры min и max скрывают механику поиска минимальных и максимальных чисел и тем самым упрощают алгоритм. При помощи абстракций можно создавать модули[44], которые позволяют выполнять сложные операции вызовом одной единственной процедуры, вроде этой:

html ← fetch_source("https://code.energy")

Всего одной строкой кода мы получили страницу сайта, несмотря на то что внутренние операции для этой задачи чрезвычайно сложны[45].

Абстракции данных будут центральной темой главы. Они скрывают детали процессов обработки данных. Но прежде чем мы сможем понять, как работает абстракция, нам необходимо освежить наше понимание типов данных.

Тип данных

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

Например, переменная, содержащая последовательность символов, которые можно преобразовать в верхний или нижний регистр, и допускающая добавление новых символов, имеет тип String (строка). Строки представляют текстовые данные. Переменная, которую можно инвертировать и которая допускает операции XOR, OR и AND, имеет тип Boolean (логический). Такие булевы переменные принимают одно из двух значений: True или False. Переменные, которые можно складывать, делить и вычитать, имеют тип Number (численный).