Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс (1083731), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Определение 7. Будем говорить, что схема реализует систему функций, реализуемых в ее выходах.

Определение 8. Сложностью схемы из функциональных элементов называется число функциональных элементов в схеме.

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

Пример. Полусумматор. Пусть v и v₁ — выходы на рисунке, ; . Сложность (число элементов) полусумматора равна 4.

В дальнейшем при построении схем ячейку полусумматора будем обозначать просто

Пусть есть 2 n-разрядных числа, и требуется найти их сумму (в дальнейших обозначениях x_i, y_i — разряды чисел, а q_i — единицы переноса).

При i = 1, 2, …, n – 1 задача решается системой функций

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

где f_v= (x  y)  q, f_v = xy  (x  y) · q = xy  (x  y) · q = m (x, y, q). Ячейку сумматора будем обозначать ₁ и в дальнейшем в схемах подставлять вместо ячейки сумматора символ ₁ с тремя входами (x, y, z) и двумя выходами (z, q).

Заметим, что сложность схемы, реализующей ячейку сумматора равна L (₁) = 9. Очевидно, z_n = x_n  y_n, q_{n – 1} = x_ny_n, z₀ = q₀.

§23. Сумматор. Верхняя оценка сложности сумматора.
Вычитатель

Для набора будем обозначать .

Определение 1. Сумматором S_n порядка n называется схема с 2n входами x₁, x₂, …, x_n, y₁, y₂, …, y_n и n + 1 выходом z₀, z₁, z₂, …, z_n такая, что .

Теорема 1. Существует схемный сумматор порядка n в базисе {, &, } с числом элементов 9n – 5.

Доказательство. Построим искомый схемный сумматор. Для этого возьмём одну ячейку полусумматора, содержащую четыре элемента, и n – 1 ячейку сумматора, каждая из которых содержит девять элементов. Построим из этих частей сумматор.

Вычислим сложность построенной схемы: L (S_n) = 9L (₁) + L () =
= 9(n – 1) + 4 = 9n – 5. Теорема доказана.

Определение 2. Вычитателем W_n порядка n называется схема с 2n входами x₁, x₂, …, x_n, y₁, y₂, …, y_n и n выходами z₁, z₂, …, z_n такая, что при

.

Теорема 2. Существует схемный вычитатель порядка n в базисе {, &, } с числом элементов 11n – 5.

Доказательство. Заметим предварительно, что

.

Действительно,

.

Тогда вычитатель реализуется схемой

и его можно построить, используя 2n отрицаний и 1 сумматор порядка n. При этом L (W_n) = 2n + L (S_n) = 2n + (9n – 5) = 11n – 5. Так как , то , и выход вычитателя определен. Теорема доказана.

§24. Метод Карацубы построения схемы для умножения, верхняя оценка её сложности

Определение 1. Умножителем M_n порядка n называется схема с 2n входами x₁, x₂, …, x_n, y₁, y₂, …, y_n и 2n выходами z₁, …, z_2n такая, что . При этом

.

Определение 2. Через M (n) обозначим наименьшую сложность умножителя порядка n в базисе {, &, }.

Утверждение. Существует схема из функциональных элементов для умножения n-разрядного числа X на 1-разрядное число y с числом элементов n.

Доказательство. Действительно, если X = |(x₁, x₂, …, x_n)| и Xy =
= Z = |(z₁, z₂, …, z_n)|, то z_i = x_iy для всех i = 1, 2, …, n. Следовательно, для реализации такой схемы понадобится ровно n элементов, реализующих конъюнкцию. Утверждение доказано.

При умножении двух n-разрядных чисел X и Y «в столбик» можно n раз умножить X на 1-разрядное число (всего n² конъюнкций) и затем n – 1 раз сложить числа длиной не более 2n. Для реализации такой схемы необходим также n – 1 сумматор порядка 2n. Согласно теореме 1, сложность сумматора порядка 2n равна L (S_2n) = 9 · 2n – 5 = 18n – 5, и сложность подобного умножителя составит n² + (n – 1) · (18n – 5) =
= 19n² – 23n + 5. Такой алгоритм (схема) имеет сложность по порядку n². Следующая теорема показывает, что такой алгоритм умножения «в столбик» не оптимален по порядку.

Лемма 1. Существует такая константа C₁ > 0, что

M (n + 1)  M (n) + C₁ n

для всех n.

Доказательство. Пусть требуется перемножить два (n + 1)-раз-рядных числа и . Тогда

Поэтому для вычисления достаточно использовать умножитель M_n со сложностью M (n) для вычисления XY, 2n элементов конъюнкции для вычисления x₀Y и y₀X, 1 элемент конъюнкции для вычисления x₀y₀ и 3 сумматора порядка не более 2n + 2, так как . Отметим, что числа x₀y₀, x₀Y и y₀X надо подавать на сумматоры со сдвигом, одновременно подавая на младшие разряды 0. При этом 0 можно предварительно получить подсхемой с 2 элементами, реализующей . Так как сложность каждого сумматора можно сделать не более 9(2n + 2), а сложность M_n равна M (n), то сложность полученной схемы будет не больше, чем M (n) + C₁n для некоторой константы C₁. Лемма доказана.

Лемма 2 (основная) [Карацуба А. А.]. Существует константа C₂ такая, что

M (2n)  3M (n) + C₂n

для всех n.

Доказательство. Пусть нужно перемножить два 2n-разрядных числа и . Разобьём их на части, содержащие по n разрядов:

, .

Тогда = X₁·2ⁿ + X₂, = Y₁·2ⁿ + Y₂ и

= X₁Y₁ · 2²ⁿ + (X₁Y₂ + X₂Y₁) · 2ⁿ + X₂Y₂ =
= X₁Y₁ · 2²ⁿ + [(X₁ + X₂)(Y₁ + Y₂) – X₁Y₁ – X₂Y₂] · 2ⁿ + X₂Y₂.

Так как X₁Y₂ + X₂Y₁  0, то при вычитании в квадратной скобке не возникнет отрицательных чисел. Таким образом, схему для умножения можно построить, используя два умножителя M_n с числом элементов M (n) в каждом для вычисления X₁Y₁ и X₂Y₂, умножитель M_n+1 с числом элементов M (n + 1) для вычисления (X₁ + X₂)(Y₁ + Y₂), 4 сумматора порядка не более 4n (так как ) и два вычитателя порядка 2n + 2. В некоторых сумматорах опять на младшие разряды надо подавать 0, который реализуем подсхемой с 2 элементами: , где x — любая входная переменная. Для построения схемы M_2n с учётом леммы 1 получим для некоторых констант C и C₂:

M (2n)  2 M (n) + M (n + 1) + Cn  3 M (n) + C₁n + Cn = 3 M (n) + C₂n.

Лемма доказана.

Лемма 3. Существует такая константа C₃ > 0, что для любого натурального k верно

M (2^k)  C₃3^k.

Доказательство. Положим . Тогда из леммы 2 имеем

и

для некоторой константы C₃, поскольку сумма в квадратных скобках не превосходит сумму 2 бесконечно убывающей геометрической прогрессии с первым членом и знаменателем . Таким образом, и M (2^k)  C₃ 3^k. Лемма доказана.

Теорема 3. Существует схемный умножитель в базисе {, &, } с числом элементов

.

Доказательство. Пусть n — любое натуральное число и n>1. Тогда существует натуральное k такое, что 2^k–1 < n  2^k. Для умножения n-разрядных чисел будем использовать схему с числом элементов M (2^k), подавая на старшие 2^k – n разрядов обоих сомножителей 0, предварительно реализованный подсхемой из 2 элементов. Тогда имеем, исходя из леммы 3

для некоторой константы C. Теорема доказана.

Замечание. Существует практически применимый метод Шёнхаге-Штрассена умножения с оценкой сложности O (n log n · log log n).

§25. Дешифратор. Асимптотика сложности дешифратора. Верхняя оценка сложности реализации произвольной функции алгебры логики

Определение. Дешифратором Q_n порядка n называется схема из функциональных элементов с n входами x₁, x₂, …, x_n и 2ⁿ выходами такая, что если |x₁x₂…x_n| = i, то z_i = 1 и z_j = 0 при i  j:

Заметим, что если i = (i₁, i₂, …, i_n)₂, то .

Лемма 4. Существует дешифратор Q_n с числом элементов, не превосходящим n2^{n + 1}.

Доказательство. Для реализации каждой z_i достаточно взять ровно n–1 конъюнкций и не более n отрицаний, то есть всего менее, чем 2n функциональных элементов. Всего различных конъюнкций ровно 2ⁿ, и сложность дешифратора не превосходит n2^{n + 1}. Лемма доказана.

Теорема 4. Сложность минимального схемного дешифратора порядка n не меньше, чем 2ⁿ и асимптотически не больше, чем .

Доказательство. 1) Поскольку у дешифратора Q_n ровно 2ⁿ выходов, на которых реализуются различные функции, не равные входным переменным, сложность минимального дешифратора не меньше, чем 2ⁿ.

2) Докажем существование дешифратора со сложностью . Разобьём набор входных переменных x = (x₁, …, x_n) на поднаборы x = (x₁, …, x_k) и x = (x_{k + 1}, …, x_n), где k — некоторый параметр и 1  k  n – 1. Пусть Q и Q —функциональные дешифраторы порядка k и n – k от базовых переменных x и x, а  и  — соответствующие им схемные дешифраторы, построенные по лемме. Легко видеть, что любую конъюнкцию Q_n [i], 1  i  2ⁿ, можно представить в виде Q_n [i] = Q [j]·Q [l], где i = 2^{n – k}(j – 1) + l и 1  j  2^k, 1  l  2^{n – k}. Дешифратор  порядка n от базовых переменных x содержит дешифраторы  и  в качестве подсхем и реализует каждую функцию алгебры логики Q_n [i], 1  i  2ⁿ, с помощью одного функционального элемента &, входы которого присоединены к выходам  и  в соответствии с формулой Q_n [i] = Q [j]·Q [l]. Из построения  следует, что L () = 2ⁿ + L () + L ()  2ⁿ + k·2^{k + 1} + (n – k)2^{n – k + 1}, и поэтому при получим: . Теорема доказана.

Следствие. Для любой функции алгебры логики f(x₁,…,x_n) существует реализация её схемой из функциональных элементов в базисе {,&, } со сложностью, не превосходящей .

Доказательство. Если f  0, то реализуем . Если f  0, то

, и .

Характеристики

Список файлов лекций