Предисловие к русскому изданию.
Наука о вычислениях прошла большой путь развития с тех пор, как в августе 1978 г. мной было написно предисловие к этой книге. На наших глазах на много порядков возросли скорости компьютеров, размеры программ и сложность компьютерных систем. Вместе с ними быстро росла и потребность в понимании этих сложных объектов.
Эта книга показала важное значение теории сложности схем для выявления фундаментальных границ возможностей вычислений и помогла вновь сосредоточить усилия исследователй на конкретных проблемах. Она также привлекла внимание ученых за границами бывшего Советского Союза к большому массиву блестящих исследований по теории логических схем, выполненных советскими математиками и инженерами, - разделу науки, получившему известность под названием теории сложности схем.
Для меня является большой честью и доставляет радость, что эта книга, первая из написанных мной, переводится на русский язык. Надеюсь, что она, став более доступной читателю, сможет побудить во многих молодых умах стремление сравняться с предшественниками или превзойти их, и внести свой вклад в создание основ теоретической кибернетики.
Я выражаю искреннюю благодарность проф. О.М. Касим-Заде, затратившему много усилий, чтобы довести эту книгу до издания на русском языке. Я также хочу поблагодарить проф. О.Б. Лупанова за его поддержку этого предприятия.
Я выражаю глубокую признательность двум переводчикам моей книги: покойному Е.П. Липатову, задумавшему этот проект и значительно продвинувщему его, прежде чем вмешалась тяжелая болезнь, а так же М.И. Гринчуку, завершившему работу над переводом и подготовившему книгу к печати.
Джон Э. Сэвидж
Предисловие
Сложность вычислений составляет одну из важнейших проблем современной науки о вычислениях (в оригинале - computer science. Это словосочетание также переводится на русский язык иногда как "кибернетика", а иногда - как "информатика". - Прим. пер.). Эта сложность представляет собой громадное препятствие, стоящие на нашем пути, которое мы должны преодолеть, коль скоро требуется понимать те сложные программы и машины, которые мы создаем. Таков главный стимул, побуждающий к развитию науки о вычислениях.
Было выработано много различных подходов к проблеме сложности вычислений, особенно в области теории и практики программирования. Нами будет развит другой подход к проблеме сложности. Мы измеряем сложность задач с помощью точных методов, а затем изучаем потребность в ресурсах (таких, как пространство и время), необходимых при наиболее благоприятных условиях для вычисления функции данной сложности на универсальных вычислительных машинах. Результаты, относящиеся к этой теме, мы выводим в виде неравенств, определяющих нижние границы для возможных соотношений между пространством и временем. Изучение таких соотношений полезно для развития интуитивных представлений об эффективном (с точки зрения стоимости) использовании вычислительных машин.
В этой книге преследуются две главные цели. В ней выводятся результаты, касающиеся упоминавшихся выше пространственно-временных соотношений, и дается продвинутая изложение наиболее важных разделов теории логических схем и автоматов. В частности, книга содержит две главы (2 и 3), посвященных вопросов сложности и глубины логических схем и длины формул для булевых функций. В этих главах изложены многочисленные и весьма интересные результаты, большинство которых получено совсем недавно или разбросано по научной литературе на русском языке.
В главах 4 и 5 изложен ряд классических разделов теории последовательностных машин и машин Тьюринга, а также представлены некоторые новые результаты, которые используются при выводе пространственно-временных соотношений. Классические разделы включают в себя такие темы, как привидение машин, регулярные выражения, универсальные машины Тьюринга, неразрешимость проблемы остановки и частично-рекурсивные функции. Новым является соотношение, связывающие величину произведения сложности схемы последовательностной машины на время ее работы с величиной сложности схемы для функции, которая вычисляется этой машиной; сюда относятся также вопросы оценки количества вычислительной работы и сложности программ.
В главе 6 подробно рассмотрены основные составные части универсальных вычислительных машин, начиная от триггеров, включая микропрограммирование и заканчивая описанием запоминающих устройств. Эти вопросы изучаются с позиции проблематики сложности. Приводится ряд интересных схемных алгоритмов для выполнения арифметических операций, причем эти алгоритмы одновременно имеют небольшую сложность и небольшую глубину. Данная глава может служить хорошим введением в организацию универсальных вычислительных машин.
Глава 7 посвящена выводу вычислительных неравенств, которые устанавливают нижние границы для пространственно-временных соотношений. В ней также содержаться новые результаты, показывающие, что для многих задач такие нижние границы близки к допустимым. В предположении, что границы достижимы, исследуются оптимальные (при различных функциях стоимости) рабочие точки на этих пространственно-временных границах. Приводится несколько интересных выводов, согласующихся с современной практикой.
Глава 8 является основным введением в три теоремы, относящиеся к области построения и анализа алгоритмов: сортировку, умножение матриц и NP-полные задачи. Мы рассматриваем ряд (безусловных) сетей сортировки, а также условные алгоритмы, включая пирамидальную сортировку. В параграфе 8.2 содержаться Штрассена и краткое описание быстрого преобразования Фурье. В параграфе 8.3 рассматривается ряд NP-полных задач, а также приблеженные полиномиальные алгоритмы для некоторых из них. Эти три раздела содержат существенные результаты и примеры важных проблем, которые используются в этой книге.
При написании книги я имел счастье пользоваться помощью многих друзей. Среди тех, кто еритически прочел большую или существенную часть книги, были Ховард Эллиот, Иешошуа Имбер, Рой Джонсон, Эдмунд Ламанье, Джоэл Силверберг, Соумитри Свами и Чарльз Уэйд. Все они - недавние выпускники Браунского университета. Иные из моих друзей прочли наиболее важные разделы книги и предложили полезные советы и дополнения. Среди них - Дидрих ван Дален, Энди ван Дам, Лэрри Харпер, Дэниел Леман, Клем Мак-Говэн, Рон Райвест, Боб Сэджуик и Фрэнсис Яо. Свой вклад внесли и многие другие, включая моих учеников последних лет.
Работа над этой книгой началась во время моего годового творческого отпуска в 1973/74 гг. На математическом факультете Высшей технической школы Эйндховена (THE), Нидерланды. За предоставленную мне возможность провести отпуск в этом самом гостеприимном институте, находящемся в этой самой гостеприимной стране, я благодарю Эдсгара Дэйкстру и Джека ван Линта. Я выражаю также свою признательность проф. д-ру Люмбеку за весьма благоприятную рабочую обстановку.
Решение задачи превращения моих набросков в печатную форму выпало на долю Е.Е.Ф.М. Басельманс-Вейерс, Ханни ван Донген-ван Ниссельрой, Марес ван ден Хурк и Х.К. ван дер Путтен-Босхер из THE, а также Линды и Шарон Тревет, Джойс Оливер и Клэр Крокетт из Браунского университета. Я выражаю им мою искреннюю благодарность за доброжелательное сотрудничество, скорое обслуживание и замечательно отпечатанные материалы. Моя благодарность относится также к С. Лоуэс за ее значительную помощь в поиске ссылок.
Я выражаю мою искреннюю признательность Браунскому университету, частично финансировавшему этот мой творческий отпуск равно как и дальнейшую работу, а также мемориальному фонду Джона Саймона Гуггенхейма и нидерландско-американской комиссии по обмену в образовании (NACEE) частично поддерживавшим мой творческий отпуск. В особенности мне хотелось бы упомянуть Уоббина Куоста, исполнительного директора NACEE, который оказал наибольшее содействие в создании гостеприимной атмосферы для стипендиатов Фулбрайта-Хейса в Нидерландах. Я благодарю также национальный научный фонд за поддержку моих исследований, нашедших отражение в этой книге.
И, наконец, я выражаю искреннюю благодарность моей жене Патриции, которая была мне подлинным источником поддержки и вдохновения и самоотверженно способствовала скорейшему завершению работы над этой книгой. Я также обязан упоминуть наших детей, Элизабет и Кевина, за их терпение.
1976, Джон Э. Сэвидж
Мое мнение
Замечательная книжка, просто бальзам на раны, старый добрый математический способ изложения. Сначала вводятся понятия, делаются определения, затем формалируются и доказываются теоремы, все формализовано, никаких плясок с бубнами и объяснений на пальцах, как это стало принято в последнее время в книгах по программированию. Примеры есть, но они только подчеркивают теорию, а не подменяют ее. Так что те, кто хочет разобраться, в теории сложности, и понять, как сравнить два алгоритма и выбрать оптимальный, почитайте эту книгу. Вполне допускаю, что некоторые материалы, немного устарели, но во-первых в книге по возможности даются ссылки на "свежие" результаты, а во-вторых фундаментальные понятия не претерпели изменений, а начинать строить стоит с фундамента, коим эта книга вполне может стать.
Содержание.
|