Использованные сокращения ....................................... 3
От авторов ...................................................... 5
Введение ........................................................ 8
Часть I. ОСНОВНЫЕ ПОНЯТИЯ ДИСКРЕТНОЙ МАТЕМАТИКИ
Глава 1. Отношения и графы .................................... 17
1.1. Отношения (бинарные и n-арные) ........................... 18
1.2. Функциональные отношения. Функции и предикаты ............ 25
1.3. Граф-схемы алгоритмов и их суперпозиции .................. 32
Глава 2. Модели, алгебры и алгебраические системы ............. 40
2.1. Логико-функциональные модели. Постановка задачи .......... 41
2.2. Алгебры. Системы образующих .............................. 43
2.3. Многоосновные алгебраические системы ..................... 49
Глава 3. Автоматы ............................................. 57
3.1. Концепция автомата. Формы представления автоматов
(табличная, графовая, аналитическая) ..................... 58
3.2. Структуры памяти (эластичная лента, магазин, счетчик,
очередь) ................................................. 63
3.3. Автоматы над внутренней памятью и дискретные
преобразователи .......................................... 65
Глава 4. Формальные грамматики и языки ........................ 73
4.1. Понятие грамматики. Автоматные грамматики.
Классификация Хомского ................................... 74
4.2. Программные и матричные грамматики. Грамматики
структурного проектирования и гиперсхемы ................. 80
Глава 5. Основные понятия теории клонов ....................... 88
5.1. Понятие клона ............................................ 89
5.2. Логические клоны ......................................... 89
5.3. Полугрупповые клоны ...................................... 91
5.4. Алгоритмические клоны .................................... 94
Глава 6. Инструментарий алгебры алгоритмики ................... 97
6.1. Системы алгоритмических алгебр Глушкова и их
модификации .............................................. 98
6.2. Алгоритмический язык САА/1 .............................. 103
6.3. Инструментарий структурного программирования МУЛЬТИ-
ПРОЦЕССИСТ .............................................. 108
Заключительные замечания и библиографические сведения ......... 114
Часть II. ТЕОРИЯ КЛОНОВ И АЛГЕБРАИЧЕСКИЕ МЕТОДЫ
ПРОЕКТИРОВАНИЯ АЛГОРИТМОВ И ПРОГРАММ
Глава 7. Клон Поста и его приложения ......................... 119
7.1. Канонические формы представления булевых функций ........ 120
7.2. Теорема Поста о функциональной полноте .................. 128
7.3. Проблема минимизации в классе ДНФ ....................... 136
Глава 8. Клон Клини и его теоретико-грамматические
обобщения ........................................... 141
8.1. Алгебра Клини. Объединенные нормальные формы ............ 142
8.2. Подалгебры клона континуального типа .................... 143
8.3. Клон Клини несокращенный ................................ 145
8.4. Клон Клини с константами ................................ 148
Глава 9. Алгоритмический клон Дейкстры и его поверхность ..... 154
9.1. Алгебра и клон Дейкстры, совокупность его
максимальных подалгебр .................................. 155
9.2. Поверхность клона Дейкстры .............................. 164
9.3. Проблема функциональной полноты для клонов с
константами ............................................. 190
Глава 10. Итеративные алгоритмические клоны ................... 203
10.1. Алгебра и клон Янова, его максимальные подалгебры ....... 204
10.2. Алгебра граф-схем алгоритмов и клоны Калужнина .......... 212
10.3. Системы алгоритмических алгебр и клон Глушкова .......... 219
10.4. О построении клонов алгебр функциональных n-отношений ... 225
10.5. Алгебра алгоритмики и ее приложения ..................... 245
Заключительные замечания и библиографические заметки .......... 250
Часть III. МОДЕЛИ И ПАРАДИГМЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ
Глава 11. Параллельные вычисления и параллельные
вычислительные системы .............................. 253
11.1. Параллелизм в вычислительных системах ................... 255
11.2. Парадигмы параллельного программирования ................ 259
11.3. Концепции синхронной и асинхронной мультиобработки ...... 264
Глава 12. Современные модели параллельных вычислений .......... 280
12.1. Модели без ограничений форм параллелизма ................ 281
12.2. Модели с ограниченными формами параллелизма ............. 288
12.3. Алгеброалгоритмические модели параллельных вычислений ... 293
Глава 13. Алгебродинамические модели параллельных
вычислений с распределенной и смешанной памятью ..... 299
13.1. Алгебродинамический подход к моделированию
параллельных вычислений ................................. 300
13.2. Модели распределенной асинхронной памяти параллельных
программ ................................................ 309
13.3. Пример применения моделей асинхронных вычислений ........ 324
13.4. Методы эффективной организации смешанной
многоуровневой памяти для параллельной обработки ........ 333
13.5. Примеры и реализация алгебродинамических моделей для
эффективных параллельных вычислений ..................... 351
Глава 14. Метод интегрированной реализации процессов
обработки данных .................................... 374
14.1. Вводные понятия и определения. Постановка задачи ........ 375
14.2. Метод интегрированной реализации ВГС .................... 380
14.3. Усовершенствование метода интегрированной реализации .... 389
14.4. Характеристический граф выполнимости .................... 398
14.5. Оценка эффективности метода реализации .................. 402
14.6. Реализация произвольных ВГС ............................. 409
Глава 15. Координационные модели объектно-ориентированных
параллельных вычислений ............................. 413
15.1. Координационные модели параллельных программ ............ 414
15.2. Синхронная координационная модель объектных
параллельных программ ................................... 417
15.3. Асинхронная координационная модель параллельных
объектных вычислений .................................... 421
15.4. Экспериментальное профаммирование координационных
моделей ................................................. 427
Заключительные замечания и библиографические сведения ......... 431
Часть IV. АЛГЕБРОАЛГОРИТМИЧЕСКИЕ МОДЕЛИ МУЛЬТИОБРАБОТКИ
Глава 16. Алгеброалгоритмические средства проектирования
и синтеза в объектно-ориентированных средах ......... 436
16.1. Основные понятия парадигмы объектно-ориентированного
проектирования .......................................... 437
16.2. Многоосновные алгебры алгоритмов и объектных структур
данных .................................................. 442
16.3. Интегрированное формализованное проектирование .......... 445
Глава 17. Разработка алгеброалгоритмических моделей
символьной мультиобработки .......................... 463
17.1. Параметрически управляемая генерация регулярных схем .... 464
17.2. Регулярные схемы алгоритмов адресной сортировки
и поиска ................................................ 478
17.3. Проектирование среды конструирования алгоритмических
знаний и свойства алгоритмов ............................ 488
Глава 18. Разработка интегрированного инструментария
конструирования синтаксически правильных программ ... 516
18.1. Инструментальные средства объектно-ориентированных
параллельных программ ................................... 517
18.2. Визуализация проектирования в объектно-ориентированных
средах .................................................. 521
18.3. Трансформационная сводимость и синтез алгоритмов и
программ символьной обработки ........................... 525
18.4. Трансформационные средства проектирования схем
алгоритмов и программ и автоматизация доказательства
утверждений в алгеброалгоритмических теориях ............ 534
Глава 19. Интегрированные средства проектирования и синтеза
параллельных алгоритмов и программ .................. 541
19.1. Архитектура взаимосвязанного конструирования
аналитических, естественно-лингвистических и
граф-схемных проектов ................................... 542
19.2. Проектирование и синтез объектно-ориентированных
программ ................................................ 546
19.3. Проектирование и реализация алгоритмических знаний
символьной мультиобработки .............................. 566
19.4. Разработка лабораторного практикума по алгебре
алгоритмики и языкам программирования ................... 581
Заключительные замечания и библиографические заметки .......... 584
Приложение 1. Реализация алгоритма асинхронной конвейерной
сортировки альтернативными вставками на
языке Java ...................................... 588
Приложение 2. Фрагмент реализации алгоритма поиска
документов по ключевым словам на языке
Java ............................................ 593
Приложение 3. Проектирование и реализация параллельного
алгоритма адресной сортировки на языке С
с использованием MPI ............................ 597
Словарь ключевых понятий ...................................... 606
Список литературы ............................................. 615
|
