Целые и последовательности (последовательное распределение)

Введение

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

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

Целые

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

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

Позиционные системы для представления целых чисел очень широко известны, поскольку они встречаются во многих разделах математики, начиная с "новой математики" и кончая углубленным курсом теории чисел. В системе счисления с основанием $$r$$ каждое положительное целое число имеет единственное представление в виде конечной последовательности$$(d_{0},d_{1},d_{2},d_{3},\ldots,d_{k}),$$ в которой каждое $$d_{i}$$ - целое, удовлетворяющее условию $$0 \leqslant d_{i} < r$$ и $$d_{k} \ne 0.$$ Нуль представляется последовательностью $$(0).$$ $$r$$ называется основанием системы $$(r > 1).$$ Целое, соответствующее последовательности (2.1), имеет вид$$N = d_{0} + d_{1}r + d_{2} r^2 + d_{3} r^3 + \ldots + d_{k} r^k,$$ что принято выражать следующим образом:$$N = (d_{k} d_{k - 1} \ldots d_{1d} d_{0} )_{r}.$$ На протяжении истории использовались различные значения $$r.$$ Например, древние вавилоняне использовали $$r = 60,$$ а индейцы племени Майя — $$r = 20.$$ Сегодня наиболее широко используется $$r = 10$$ - десятичная система, которую мы унаследовали от арабов, и $$r = 2$$ - двоичная система, которая лежит в основе современных вычислительных устройств. В действительности она применяется лишь на самом низком уровне аппаратного оборудования; в сложных вычислительных устройствах и базисных языках удобнее использовать $$r = 8$$ или $$r = 16.$$

Единственность этого представления можно доказать методом от противного. Числа $$N = 0$$ и $$N = 1,$$ очевидно, имеют единственное представление. Предположим, что представление не единственно, и пусть $$N > 1$$ будет наименьшим целым числом, имеющим два различных представления:$$N = (d_{k} d_{k - 1} \ldots d_{0})_{r} = (e_{l} e_{l - 1} \ldots e_{0} )_{r}.$$ Если $$k \ne l,$$ то без потери общности предположим, что $$k > l.$$ Тогда, поскольку$$\sum\limits_{i = 0}^l {(r - 1)r^i = r^{l + 1} - 1} < r^{l + 1} < r^k$$ и поскольку $$d_{k} \ne 0,$$ мы заключаем, что$$(d_k d_{k - 1} \ldots d_0 )_r > (e_l e_{l - 1} \ldots e_0 )_r,$$ что невозможно. Таким образом, мы должны иметь $$k = l.$$ Аналогично, если $$d_k > e_k,$$ мы имели бы снова неравенство (2.2) и отсюда с необходимостью $$d_k = e_k.$$ Следовательно, число$$N - d_k r^k = (d_{k - 1} d_{k - 2},\ldots,d_0 = (e_{k - 1} e_{k - 2} \ldots e_0 )_r$$ имеет два различных представления, что противоречит предположению, что $$N$$ - наименьшее из таких чисел.

Для доказательства того, что каждое положительное целое имеет представление по основанию $$r,$$ достаточно задать алгоритм, конструирующий (с необходимостью единственное) представление данного числа $$N.$$

Алгоритм 1. Преобразование числа $$N$$ в его представление $$(d_k d_{k {-1} \ldots d_1 d_0 )_r $$ в системе счисления с основанием $$r$$ .

Он строит последовательность $$d_0,d_1,d_2,\ldots d_k $$ путем повторения деления на $$r$$ и записи остатков. Пусть на первом шаге при делении $$N$$ на $$r$$ остаток будет $$d_0 .$$ Частное, полученное в результате первого шага, делим на $$r,$$ вновь полученное частное делим на $$r$$ и так далее. Полученная в результате такого процесса последовательность остатков и будет требуемым представлением $$N$$ по основанию $$r.$$

Важным обобщением систем счисления с основанием $$r$$ являются смешанные системы счисления, в которых задается не единственное основание $$r,$$ а последовательность оснований $$r_0,r_1,r_2,\ldots$$, и последовательность (2.2) соответствует целому$$N = d_0 + d_1 r_0 + d_2 r_0 r_1 + d_3 r_0 r_1 r_2 + \ldots + d_k \prod\limits_{i = 0}^{k - 1} {r_i },$$ где теперь каждое $$d_i$$ удовлетворяет неравенству $$0 \leqslant d_i < r_i $$ и $$d_k \ne 0 ,$$ если $$N \ne 0$$ - тот факт, что каждая такая последовательность соответствует единственному числу и каждое положительное целое число имеет единственное представление, следует из простого обобщения результатов для обычных систем счисления, которые являются частным случаем смешанных систем при $$r_i = r,i \geqslant 0.$$

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

Пример. Рассмотрим нашу систему измерения времени: секунды, минуты, часы, дни недели и годы. Это - в точности смешанная система с $$r_0 = 60,r_1 = 60,r_2 = 24,r_3 = 7,r_4 = 52.$$

Представление целого $$N$$ в смешанной системе счисления $$(r_0,r_1,\ldots ) $$ осуществляется с помощью алгоритма 2, который является простым обобщением алгоритма 1. Вместо того, чтобы для получения $$d_k $$ в качестве делителя всегда использовалась $$r,$$ в алгоритме 2 используется $$r_k .$$

Алгоритм 2. Преобразование числа $$N$$ в его представление $$(d_0,d_1,\ldots,d_k ) $$ в смешанной системе счисления $$(r_0,r_1,r_2,\ldots )$$.

Последовательности

Бесконечная последовательность$$s_1,s_2,s_3,\ldots$$ формально определяется как функция $$f,$$ областью определения которой является множество положительных целых чисел: $$f(i) = s_i,i \geqslant 1.$$ Во многих случаях индексирование последовательности более удобно начинать с нуля; тогда областью определения $$f$$ будет множество целых неотрицательных чисел. Аналогично определим конечную последовательность или список$$s_1,s_2,\ldots,s_n$$ как функцию, областью определения которой является множество $$\{ 1,2,\ldots,n\}.$$ Примером бесконечной последовательности являются простые числа$$i:1\;2\; 3\; 4\; 5\; 6\; 7\; 8\; 9\; 10…$$ $$p_i : 2\; 3\; 5\; 7\; 11\; 13\; 17\; 19\; 23\; 29…,$$ а перестановка$$\Pi(1,2,3,4,5,6)=(6,2,5,1,3,4)$$ представляет собой пример конечной последовательности.

В комбинаторных алгоритмах часто приходится встречаться с представлениями конечных последовательностей (или начальных сегментов бесконечных последовательностей ) и операциями над ними.

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

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

Так, $$s_1 $$ хранится, начиная с ячейки $$l_1 ,$$ $$s_2 $$ хранится, начиная с ячейки $$l_2 = l_1 + d,$$ $$s_3 $$ хранится, начиная с ячейки $$l_3 = l_1 + 2d$$ и так далее, где $$d $$ - число ячеек, требуемых для хранения одного элемента последовательности.

Описанное выше представление последовательности имеет ряд преимуществ. Во-первых, оно легко осуществимо и требует небольших расходов в смысле памяти. Кроме того, оно полезно и потому, что существует простое соотношение между $$i$$ и адресом ячейки, в которой хранится $$s_i :$$$$l_i = l_1 + (i - 1)d.$$ Это соотношение позволяет организовать прямой доступ к любому элементу последовательности. Наконец, последовательное представление имеет достаточно широкий диапазон и включает в себя в качестве специального случая представление многомерных массивов.

Например, чтобы представить массив размером $$n \times m$$$$\left( {\begin{array}{*{20}c} {a_{11} } {a_{12} } {\ldots } {a_{1m} } \\ {a_{21} } {a_{22} } {\ldots } {a_{2m} } \\ . . . . \\ {a_{n1} } {a_{n2} } {\ldots } {a_{nm} } \\ \end{array} } \right)$$ будем рассматривать его как последовательность $$s_1,s_2,\ldots,s_n ,$$ в которой каждое $$s_i $$ в свою очередь является последовательностью из $$m$$ элементов $$i$$ -й строки нашей матрицы. Таким образом, число ячеек, требуемых для записи элемента $$s_i $$ (будем обозначать это число символом $$d$$ ), равно $$m\bar d,$$ где $$\bar d$$ - число ячеек, требуемых для записи элемента $$a_{ij} .$$ Поскольку последовательность $$s_i $$ начинается в ячейке$$l_i = l_1 + (i - 1)d = l_1 + (i - 1)m\bar d,$$ ячейка для $$a_{ij} $$ будет иметь следующий адрес:$$l_i + (j - 1)\bar d = l_1 + [(i - 1)m + (j - 1)]\bar d.$$ Это представление известно как построчная запись матрицы ; постолбцовая запись получается, если (2.4) рассматривать как последовательность $$t_1,t_2,\ldots t_m $$ в которой каждое $$t_i $$ в свою очередь является последовательностью из элементов $$i$$ -го столбца матрицы.

Последовательное распределение, наряду с преимуществами, имеет значительные недостатки. Например, такое представление становится неудобным, если требуется изменить последовательность путем включения новых и исключения имеющихся там элементов. Включение между $$s_i $$ и $$s_{i + 1} $$ нового элемента требует сдвига $$s_{i + 1},s_{i + 2},\ldots,s_n $$ вправо на одну позицию; аналогично, исключение $$s_i $$ требует сдвига тех же элементов на одну позицию влево. С точки зрения времени обработки, такое передвижение элементов может оказаться дорогостоящим, и в случае динамических последовательностей лучше использовать технику связного распределения, рассматриваемую в следующей лекции.

Характеристические векторы. Важной разновидностью последовательного распределения является случай, когда такому представлению подвергается последовательность некоторой основной последовательности $$s_1,s_2,s_3 \ldots $$ В этом случае можно представить последовательность более удобно, используя характеристический вектор - последовательность из нулей и единиц, где $$i$$ -й разряд равен единице, если $$s_i $$ принадлежит рассматриваемой последовательности, и нулю в противном случае.

Например, характеристический вектор начального сегмента последовательности (2.3)$$s_i:\quad 1 \;2 \;3 \;4 \; 5\; 6\; 7\; 8\; 9\; 10$$ характеристический вектор для простых чисел:$$\quad 0 \;1 \; 1\; 0\; 1\; 0\; 1\; 0\; 0\;0$$ Здесь основной последовательностью является последовательность целых положительных чисел. В ЭВМ с 32-разрядными словами для запоминания простых чисел, меньших $$10^6$$, потребуется $$10^6.32 = 31250$$ слов. Замечая далее, что для $$i > 1$$ число $$2i$$ не простое, можно сэкономить половину этого поля, выписывая разряды только для чисел видов $$2i + 1,i \geqslant 1,$$ и запоминая, что простое число 2 отсутствует. Таким образом, простые числа, меньшие чем $$10^6 ,$$ можно записать только 15625 словами. Поскольку число простых чисел, меньших $$10^6 ,$$ равно 78498, последовательное представление, описанное ранее, потребовало бы поля в пять раз меньшего размера.

Характеристические векторы полезны в ряде случаев. Их полезность вытекает из их компактности, существования простого фиксированного соотношения между $$i$$ и адресом $$i$$ -го разряда и возможности при таком представлении очень легко исключать элементы.

Главное неудобство характеристических векторов состоит в том, что они не экономичны. Исключение составляют "плотные" последовательности последовательностей $$s_1,s_2,s_3 \ldots .$$ Кроме того, их трудно использовать, если не существует простого соотношения между $$i$$ и $$s_i .$$ Если такое соотношение сложное, то использование характеристических векторов может быть очень не экономичным в смысле времени обработки. Если последовательности недостаточно плотные, то значительным может оказаться объем памяти. В случае простых чисел между $$i$$ и $$s_i $$ имеется простое соотношение: $$s_i = i$$ (или $$s_i = 2i + 1,$$ если использовать только нечетные числа). Теорема о простых числах утверждает, что число простых чисел, меньших $$n,$$ приблизительно равно $$n/ \ln n$$ ; таким образом, простые числа относительно плотно распределены в множестве целых чисел.