Алгебра. Языки. Программирование

Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л.

Скачать: в формате pdf (41 Мб), в формате djvu (4 Мб)

Предисловие

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

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

Понятия и результаты, изложенные в первой части, подбирались с учетом применения их во второй части книги. Так, аппарат теории множеств и отношений применяется и связи с изучением проблемы тождественных преобразований в системах алгоритмических алгебр (гл. 4, § 4.1, 4.2), классификацией формальных языков (гл. 5), разработке и методов синтаксического анализа для параметрических систем программирования (гл. 6). Свойства структуры подалгебр универсальных алгебр, рассмотренные в гл. 3, применяются при изучении проблемы полноты для модифицированных алгебр Поста (гл. 4, §4.3, 4.4) и алгебр контекстно-свободных языков (гл. 5, § 5.5). С аппаратом многоосновных алгебр (гл. 3. § 3.0) связаны концепция алгоритмических алгебр (гл. 4, § 4.1) и методы формализации синтаксиса и семантики языков программирования (гл. 6, § 6.7). В первой части использованы результаты, изложенные в работах [1,6, 8 — 10, 24, 25, 36, 49, 52, 54, 60, 61, 64, 66, 67, 70, 71, 73, 71, 77, 78, 86, 103, 108, 111-115, 118, 119, 127, 128, 133, 134, 139, 155, 156).

Вторая часть посвящена элементам теории программирования. В гл. 4 рассматривается аппарат алгоритмических алгебр, предложенный В. М. Глушковым [26] для решения проблем прикладной теории алгоритмов. Особое внимание уделено задачам, возникающим при автоматизации проектирования ЭВМ и программирования. Установлена связь аппарата алгоритмических алгебр с концепцией структурного программирования [41], которое представляет собой комплекс технологических средств, ориентированных на конструирование больших алгоритмов и программ. Показано, что алгоритмические алгебры можно рассматривать в качестве теории схем структурированных алгоритмов и программ и применять при разработке схемного и программного математического обеспечения для современных вычислительных систем, в частности при решении проблемы формализации семантики языков программирования (гл. 6, § 6.7). В гл. 4 использованы результаты, изложенные в работах [8, 18, 23—27, 31—37, 41, 43—50, 53—63, 65, 69, 72, 75—78, 80—82, 84, 91, 92, 113—117, 120—122, 128, 131, 133, 134, 136, 139, 145, 146, 148, 155, 156, 158].

Пятая глава является введением в теорию формальных языков. Рассматриваются вопросы классификации порождающих грамматик, формы их представлений, алгебраические свойства операций над языками. Изложенные результаты применяются в гл. 6 при решении проблем анализа и синтеза автоматных моделей языков (§ 6.1, 6.2), создании формализмов, ориентированных на эффективное решение задач конструирования многих важных системных процессов (§ 6.3—6.6), развитии алгебраических методов описания синтаксиса и семантики языков программирования (§ 6.7). В гл. 5 использованы результаты, изложенные в работах [3, 7, 17—25, 36, 37, 48, 70, 80, 85, 94, 95, 99, 100, 109, 110, 118, 128, 137, 138, 146].

Методологии построения современных языков и систем программирования посвящена гл. 6. В настоящем издании эта глава существенно переработана. В ней отражены некоторые новые результаты. Для этого, в связи с ограниченностью объема книги, пришлось опустить часть материала, изложенного в первом издании. Так, в § 6.1 рассмотрена концепция автоматов над внутренней памятью [37], обобщающая известные автоматные структуры (магазинные и БС-автоматы, счетчиковые машины и др.), применяемые в системном программировании (в первом издании этот параграф посвящен историческому очерку развития идей программирования и СССР и за рубежом). В связи с введением автоматов над внутренней памятью в определенной мере изменены и последующие параграфы главы, в частности рассмотрены стратегия двустороннего синтаксического анализа и её обобщение в связи с конструированием параллельных систем программирования для многопроцессорных вычислительных комплексов, методы формализации синтаксиса и семантики языков программирования с привлечением аппарата многоосновных алгебр. Методы конструирования параметрических систем программирования применялись при разработке программного обеспечения некоторых современных вычислительных систем как специализированного, так и универсального назначения. Дальнейшее развитие этих методов будет способствовать созданию высокопроизводительных комплексов ЭВМ последующих поколений. В гл. 6 использованы резуль- таты, изложенные в работах [2—5,11—16, 18—21, 28—30, 36—42, 48, 51, 52, 62, 68, 70, 71, 79, 83, 85, 87—90, 93, 95—98, 101—107, 123—126, 128— 130, 132, 135, 140—147, 149-154, 157, 159, 160].

В настоящее издании монографии внесены поправки, вызванные допущенными в первом издании неточностями, опечатками или недосмотрами.

Помещена в музей с разрешения родных автора 25 мая 2019