Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 15»

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 15 Сборник переводов Под редакцией О. Б. ЛУПАНОВА ИЗДАТЕЛЬСТВО «МИР» МОСКВА 1978 УДК 519. 95 Научный совет по кибернетике Академии наук СССР Продолжение новой серии кибернетических сборников, публикация кото- которых была начата издательством «Мир» в 1965 г. В данном выпуске представ- представлены обзорные статьи и оригинальные работы известных зарубежных ученых по наиболее актуальным проблемам теоретической кибернетики. Большой ин- интерес представляют статьи о распознавании образов, оценках сложности управ- управляющих систем, теоретических и прикладных задачах программирования. Осо- Особенно следует отметить работу Ульфа Гренандера, в которой строится теория распознающих алгоритмов над формальными грамматиками, и работу Дональ- Дональда Кнута по теоретическим и практическим аспектам автоматического постро- построения трансляторов с языков программирования. Книга предназначена научным работникам, инженерам-исследователям, аспирантам и студентам математических специальностей, занимающимся и ин- интересующимся теоретической кибернетикой и ее приложениями. Редакция литературы по математическим наукам ипииг Математические вопросы Сложность вычисления элементарных симметрических функций и коэффициентов интерполяционного полинома1) Ф. Штрассен Резюме. Для вычисления множества всех элементарных симметрических функций от п переменных необходимо выполнить по крайней мере п A6&2 п—2) умножений и делений2). Эта нижняя оценка и аналогичные нижние оценки для сложности еще некоторых вычислений и задач интерполяции получены с использованием идей и результатов алгебраической геометрии. 1. ВВЕДЕНИЕ Мы исследуем минимальное число Ь (Р) умножений и де- делений, достаточное для вычисления (т. е. определения числен- численного значения) конечного множества Р рациональных функций над бесконечным полем к. Для удобства предположим, что наряду со сложением и вычитанием умножения на скаляр также времени не требуют. Основная часть работы посвящена дока- доказательству нижней оценки для Ь(Р). Эта оценка, очевидно, является нижней оценкой для минимального числа всех опера- операций при вычислении Р. При получении нижних оценок для Ь{Р) до сих пор исполь- использовались два нетривиальных метода: 1. Метод Пана [7], при котором конкретные значения при- придаются по очереди содержащимся в Р переменным (см. также [13] и указанную там литературу). Этот метод можно успешно применять во многих случаях, однако, естественно, он дает только такие нижние оценки, которые не превосходят числа переменных в Р. 2. Предложенный Моцкином [б] метод, позволяющий оценить снизу сложность вычислений „почти всех" полиномов данной степени и использующий соображения размерности. Здесь речь ) 51газ5еп V. , О1е Вегесппип&зкотркхИа! уоп е1етегйаг-5утте1п- 8сЬеп РипкНопеп ипб. уоп 1п{егро1аиопзкоеШ21еп1:еп, Nитепвске МаЛкетапк, Ваш! 20, Не!* 3, 1973, 238-251. 2) Элементарное доказательство этого факта находится в статье А. Шён- хаге, перевод которой дается в настоящем сборнике (стр. 22). — Прим.