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

I. Системы счисления

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

Рис. I.1. Число 4321 в разных системах счисления

Архаичные системы счисления (например, римские цифры — I, II, III и т. д.) составляют числа из сумм цифр. Система счисления, которая используется сегодня, тоже опирается на суммы, но значение каждой цифры в позиции i умножается на d в степени i, где d — это некое число. Его называют основанием системы счисления. Мы обычно используем d = 10, потому что у нас десять пальцев, но система работает для любого основания d.

II. Метод Гаусса

Рассказывают, что как-то раз учитель в начальной школе в качестве наказания поставил Гауссу задачу: просуммировать все числа от 1 до 100. К изумлению учителя, Гаусс нашел ответ (5050) в течение нескольких минут. Его прием состоял в том, чтобы манипулировать порядком элементов удвоенной суммы:

= 10 100

Разделив это на 2, мы получим 5050. Мы можем записать так:

.

Следовательно:

В последней строке i отсутствует, поэтому (n + 1) суммируется снова и снова n раз. Следовательно:

III. Множества

Мы используем слово множество для описания группы объектов. Например, мы можем назвать S множеством обезьянок-эмодзи:

S = {, , ,  }.

Рис. III.1. S₁ и S₂ есть подмножества S

Подмножества. Множество объектов, содержащихся в другом множестве, называется подмножеством. Например, обезьянки, показывающие лапы и глаза, составляют подмножество S₁ = {, }. Все обезьянки в S₁ содержатся в S. Мы записываем это так: S₁ S Мы можем сгруппировать обезьянок с лапками и ртами в другом подмножестве: S₂ = {, }.

Объединение. Какие обезьянки принадлежат либо S₁, либо S₂? Ответ: обезьянки в S₃ = {, , }. Новое множество — объединение двух предыдущих. Мы записываем это так: S₃ = S₁ S₂.

Пересечение. Какие обезьянки принадлежат и S₁, и S₂? Ответ: обезьянки в S₄ = { }. Новое множество получается путем пересечения двух предыдущих. Мы записываем это так: S₄ = S₁ S₂.

Степенные множества. Обратите внимание, что S₃ и S₄ одновременно являются подмножествами S. Мы также полагаем, что S₅ = S и пустое множество S₆ = {} являются подмножествами S. Если подсчитать все подмножества S, то вы найдете 2⁴ = 16 подмножеств. Если же рассматривать их все как объекты, то мы можем собрать их в множество. Множество всех подмножеств S называется его степенным множеством:

P_S = {S₁, S₂, S₁₆}.

IV. Алгоритм Кэдейна

В разделе «Полный перебор» главы 3 мы представили задачу «Лучшая сделка».

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

В разделе «Динамическое программирование» той же главы мы показали алгоритм, который решил эту задачу с временной сложностью O(n) и пространственной сложностью O(n). Когда в 1984 году Джей Кэдейн обнаружил эту задачу, он нашел способ решить ее с O(n) по времени и O(1) по пространству:

function trade_kadane(prices):

····sell_day ← 1

····buy_day ← 1

····best_profit ← 0

····for each s from 2 to prices.length

········if prices[s] < prices[buy_day]

············b ← s

········else

············b ← buy_day

········profit ← prices[s] — prices[b]

········if profit > best_profit

············sell_day ← s

············buy_day ← b

············best_profit ← profit

····return (sell_day, buy_day)

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