1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 102
Текст из файла (страница 102)
Покажите, что каждую булеву функцию от и переменных можно реализовать с помощью не более п2" логических элементов с двумя входами. е12.27. Покажите, что для каждого и существует булева функция от и переменных, наименьшая реализация которой требует примерно 2"/п логических элементов с двумя входами. **12.28.
О сложности реализации конкретных булевых функций известно мало. Однако, если ограничиться реализациями на схемах, являющихся деревьями, то можно показать, что для некоторых функций требуется пе/1ой и логических элементов. Докажите, что следующее условие достаточно для того, чтобы булева функция от и переменных требовала для своей реализации не менее пв/1оя п логических элементов. Условие. Пусть |(х„ ..., ха) — булева функция от и переменных. Разобьем множество переменных х~ на Ь=п/1оя и блоков по 1ой и переменных в каждом.
Присвоим значения (О или 1) всем переменным в Ь вЂ” 1 блоках. Это можно сделать 2"/и способами. Результатом будет функция от 1ой и переменных, совпадающая с одной нз 2" функций от 1оя п переменных. Функция, получаемая в действительности, зависит от значений, присвоенных переменным в Ь вЂ” 1 блоках. Пусть В~ — блок переменных, которым значения не присвоены. Если присваивание подходящих значений переменным не из В, дает порядка 2"/п различных функций от переменных из В„ причем это выполняется для каждого 1, 1<1<1од и, то любая древовидная схема для / должна содержать пв/1оя и логических элементов.
"а12.29. Пусть па=2+1оап и Щ1<1<п/т, 1</н-.т) — такое множество т-мерных векторов из О и 1, что каждый вектор 1м имеет среди своих компонент не менее двух единиц. Пусть О Модуль анена а+Ы равен У ае+Ье, 49а упвлжиения (Хта Хаа Хлглк ) ® Хгх ' ) (Э Ц ХЕ т<г<лгла ~ г<Е<л!а а<а< л туг< л Ь Еалг такие. итл гг где (гч — это 1-я компонента вектора 1ол Докажите, что в любой реализации функции / с помощью древовидной схемы не менее ит1!оя и логических элементов. *12.30.
Постройте другие булевы функции, для реализации которых с помощью древовидных схем требуется (а) им* и (б) пекод и логических элементов. 12.31. Пусть Яг(х„..., х„) — симметрическая булева функция, принимающая значение ! тогда и только тогда. когда в точности г' переменных х; имеют значение 1. (а) Найдите реализацию функции Яа(хь..., х„) с мишгмально возможным числом логических элементов.
(б) Найдите древовидную реализацию для 5,(х„..., хл) с минимально возможным числом логических элементов. лл12.32. В примере 12.9 мы доказали, что любая схема, пригодная для вычисления значений произвольного полинома и-й степени, требует и умножений. Постройте конкретный полином и-й степени с вещественными коэффициентами, для вычисления значений которого требуется и умножений. к*12.33. Докажите, что умножение матриц в полукольце положительных целых чисел с операциями М1Ь! и + требует си' операций, где с — постоянная, 0(с(1. "*12.34.
Докажите, что умножение булевых матриц с операциями И и ИЛИ требует и' операций. Упр. 12.35 и 12.36 касаются такого представления полинома, при котором значение полинома в точке можно вычислить примерно за и!2 умножений. "*12.33. Пусть р(х) — полипом и-й степени, где и — нечетное целое число, большее 1. Запишем его в виде р (х) = (х' — а) г( (х) + Ьх + с. (а) Покажите, что при подходящем сг можно взять Ь=О, (б) Покажите, что существуют такие а, и ))„что р(х) можно представить в виде ( х ) ( х а ) г ( т а ) и, значит, полипом р(х), представленный этими аг и !)п можно вычислить за ) ггг2 ~+2 умножений. 499 ГЛ.
1О НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ (в) Параметры а1 в (б) могут оказаться комплексными числами, Как преодолеть эту трудность? Указание: Подставьте у+с вместо х в р (х) прн подходящем с и вместо вычисления значения р (х) в точке х=х, вычислите некоторый полипом р'(у) в точке у=х,— с. Упр. !2.35 не дает метода для вычисления а1. Более того, параметры а, не обязательно рациональные числа. В следующем упражнении делается попытка преодолеть эти трудности. **12.3б.
Пусть т — целое число. Для 1(1(т положим (ио — !)о+ (! — !)о -)- Зм+ ! Гоо— т и г,! —— т — 1+!+1, 1<1<1. Определим цепь с параметрами а» и ))А1 как вычисление вида С! (Х) ~ — (Х'!о+а )(Х~и+~ ) с„(х) (он+а„)(х'! .1-()м), си(х) (с! !,+аи)(х"и+()1!). Пусть р(х)='~ сн(х).
!=1 (а) Докажите, что показатель наибольшей степени переменной х, коэффициент при которой зависит от а», равен ~ г!, а показатель е ! наибольшей степени переменной х, коэффициент при которой зависит от ()», равен Р' г,о — г». (б) Докажите, что всякий полипом степени, не превосходящей т(т+1)+1, со старшим коэффициентом, равным 1, можно представить т(т+1)+1 параметрами, так что (1) этот полинам можно вычислить по параметрам за т(т+1)!2+0(т) умножений и (й) параметры являются рациональными функциями от коэффициентов. Проблемы для исследования Каждой неветвящейся программе можно следующим образом поставить в соответствие ориентированный ациклический граф.
Узлы графа представляют входы и переменные. Если ( -у й— шаг, то из д в ( н из(! в ( идуториентированные ребра. Заметим, что число шагов программы ровно вдвое меньше числа ребер. Поэтому нижняя оценка числа ребер в любом ориентированном ациклическом графе, соответствующем вычислению для конкретной задачи, дает нижнюю оценку числа шагов в любой неветвящейся программе для этой задачи.
злмнчлния по лмтнэлттвв 12.37. докажите или опровергните, что для больших л всякий ориентированный ациклический граф с л истоками и л выходами, удовлетворяющий условию иа пропускные способности из упр. 12.22, содержит не менее л ]од л ребер. 12.38. Удовлетворяет ли каждый граф, соответствующий неветвящейся программе для умножения двух л-разрядных двоичных целых чисел (предполагается, что используются битовые операции), условию на пропускные способности из упр. 12.22? Замечания пе литературе Теорема 12.2 и общая формулировка задачи, изучаемой в этом разделе, принадлежат Винограду [1970а]. Теоремы !2.! и !2.3 взяты из работы Фидуччив [1971]. Тот факт, что без использования делений для вычисления значения поли- нома л.й степени требуется л умножений, приписывается (Кнутом [1969!) Гарсиа ').
Пан 11966] распространил этот результат на мультипликативные операции. Мацкин 11955] показал, что для вычисления значения полинома с предварительной обработкой коэффициентов необходима [ п/2 ]+1 умножений. Одной из первых в этом направлении была работа Островского 11954). Белага [196!) усилил результат Мацкина, а также получил оценку длн числа сложений †вычитан. Виноград [197061 показал, что для умножения комплексных чисел необходимы три умножения. Упр. 12.7 обсуждается Виноградом [!973], Материал о нижних оценках для умножения матриц (упр. 12,9 — 12.16) основан на работе Хопкрофта, Керра 1197!). Результаты упр. 12.17 независимо получены несколькими авторами.
Часть (в) Виноград (частное сообщение) приписывает Унгару. Упр. !2.18 и 12.19 заимствованы у Хопкрофта, Мусинского [!973]. Упр. 12.20 — 12,22, 12.37 и 12.38 основаны на беседах с Флойдом. Упр. 12.24 и 12.25 взяты у Моргенштерна [1973), пр. 12.28 и !2.29 — у Нечипорука 1!966), 12.30(а) — у Харпера, Сэвнджа 1972), упр. !2.32 — у Штрассена [1974], упр. !2.33 — у Керра 11970), упр.
12.34 — у Пратта [19741, упр.!2.35 — у Ива [19641 и упр. 12.36 — у Рабина, Винограда [19711. Еще некоторые попытки получения нижних оценок для числа арифметических операций были сделаны Бородиным, Куком [!974], Кедемом 119741 и Киркпатриком [1972, 19741. х) Э!от результат был впервые доказан В. Я. Паном в 1960 г.
в более сильной форме и изложен в его статье [!962). Читатель, интересующийся алгебраической трактовкой вопросов сложности вычисления наборов поливанов, может обратиться к многочисленным работам Ф. Штрассена, например [1973, 19761.— Прим, перса. СПИСОК ЛИТЕРАТУРЫ ') Адельсон-Вельский Г. М., Ландис Е. М. 1!9621 Одни алгоритм организации информации, Доклады АН СССР, 146, № 2, 263 — 266. Арлазаров В.
Л., Днниц Е. А., Кранрод М. А., Фараджев И. А. ]!970] Об экономном построении транэнтивного замыкания графа, Доклады АП СССР, !94, № 3, 04с8™7 — 488. Аха (ред.) (АЬо А. У.) [1973] Сиггеп1з (п Гйе (Ьеогу о! сотри!]пй, Ргеп(!се-На!1, Епй!емоод С!!!(з, К.Л. Ахо, Гэри, Ульман (АЬо А. Ч., Оагеу М. ](а 1Л1тап Л. Р.) [1972) ТЬе (гапМНче гедис(1оп а( а б!гес(ед йгарЬ, 3)АМ Л. Сотри!., 1, № 2, !31-137.
Аха, Стейглиц, Ульман (АЬо А. У., 3(е1811!х К., ГЛ!!пап Л. Р.) [Г974] Еча!иаНпй ро!упоппа!з а( Пхеб зе1з о1 ро!п(з, Ве11 1.аЬога1ог!ез, Миггау Н!11, Ь].Л. См. также 3)АМ Л. Сагрри., 4, № 4 (!975), 533 — 539. Ахо, Ульман (АЬо А. Ч., 1)1!»пап Л. Р.) ]!972) ТЬе Гйеогу о] рагз!пй, 1гапз1аВап апб сотрЯ!пй. Уо!. 1: Рагз!пй, РгепНсе-На11, Епй!еиооб С!1!!з, Н. Л.
(Русский перевод: Ахо А., Ульман Дж., Теория синтаксического анализа, перевода и компиляции. Том 1: Синтаксический анализ, М., Мир, 1978.) ]1973[ ТЬе 1Ьеогу о! рагз!пй, 1гапз!аНоп апб сотр!Впй. Чо!. 2: Сотр]1]пй, РгепНсе-На11, Епй!е»чааб СЯНз, Н.Л. (Русский перевод: Ахо А., Ульман Дж., Теория синтаксического анализа, перевода и компиляции. Том 2: Камни.
лчция, М., Мир, 1978.) Ахо. Хиршберг, Ульман (АЬо А. Ч., Н)гзсЬЬегй Р. 5., 1Л1тап Л. Р.) ]1974] Ваипдз ап Гйе сотр1ехйу о! 1Ье »пах1та) саттон зиЬзейиепсе ргоЫет, 1ЕЕЕ 151Ь Апина) Бутрозгпт оп бюКсЬ|пй апд АЫота(а ТЬеогу, Ыетч Ог1езпз, 104 — 109. Ахо. Хапкрофт, Ульман (АЬо А. У., Норсгой Л. Е., ()11тап Л. Р.) [!968] Типе апд 1аре сотр!ехйу о1 ризйбоюп аи1ота1оп 1апйиайез. /л)агт. анд Солт«о!., !3, № 3, 186 — 206. (Русский перевод в сб. «Языки и автоматы», М, Д!ир, 1975, стр. 185 — 197.) [!974] Оп !(пд]пй 1ожез( саттон апсеыогз !и (геев, 3)АМ Л.
Сотри!., 5, № 1. 115 — 132. Банч, Хопкрофт (Виней Л.. Норсгой Л. Е.) (!974] ТНапйи!аг !ас!ог)ха!]оп апб !пчегзьоп Ьу 1аз( та1г!х ти)1)р1!сабоп, Моди Сотри!., 28, № 125, 23! — 236. Белага Э. Г. [196!] О вычислении значений мнагочленов ат одного переменного с предва- ') Работы, отмеченные знаком ', добавлены при переводе. †Пр.
перев. 502 список литвихтчаы рительной обработкой коэффициентов. Проблемы кибернетики, аып. 5, М., Физматгиэ, 7 — 15. Беллман (ВеИвап И. Е.) [!957) Оупаппс ргойгавпппй, Рг!псе(оп 1»п!чегзИу Ргет, Рг!псе1оп, Х.у. [Русский перевод: Беллман Р., Линамическое программирование, М., ИЛ, 1960.) Берж (Вегйе С.) [!958] ТЬе !Ьеогу о( йгарйз апб Из аррИса1юпз, %Иеу, Хечг Уог!с (Русский перевод: Берж С., Теория графов и ее применение, М., ИЛ, 1962.) Беркхард (Виг1йагб %. Е.) [!973] Хопгесигз!че 1гее 1гачегзв! а1йог!Иипз, Ргос.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
