1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 40
Текст из файла (страница 40)
В теории еще отсутствовали полюсы, информационные связи и информационный граф. В качестве инварианта допустимых распределений памяти рассматривался носитель — множество всех маршрутов (маршрут так же, как у Лаврова, определялся как маршрут величины, а не информационной связи). Допустимыми распределениями памяти были такие распределения, при цоторых носитель не сокращался. Области действия определялись как компоненты связности носителя, в котором симметричное отношение связности определялось между маршрутами. Такой подход формально требовал (правда, тривиального) докааательства конечности числа областей действия.
В работе был.сформулирован критерий несовместимости областей действия (теорема 4 з 2.3), а процедура нахождения множества транзитных операторов была описана как получение двух транэитивных замыканий (множества Е и А.), для которых были приведены рекуррентные формулы их вычисления. В указанной работе Ершовым был сделан шаг в сторону решения задачи экономии памяти для программ, содержащих массивы.
Для этого каждой величине приписывался «вес» — целое число, »» з. истогичискии овзоэ 1з7 укааывающее, сколько рядом расположенных ячеек памяти требуется для хранения величины. На всех этапах теории вплоть до раскраски вес величин никак не учитывался. В то же время, учитывая проблему, аатронутую нами з итоговом анализе (вопрос (2) в начале з 5.1), для каждого реаультата в операторной схеме считалось известным, вырабатывается ли он «в целом» илн только частично. Начинать маршрут величины могли только операторы, вырабатывавшие ее в целом. Операторы, вырабатывавшие величину не в целом, обязаны были быть транзитными операторами маршрутов. В 1968 г., в 4-м номере журнала «Кибернетика» А.
П. Ершов опубликовал статью «Об операторных схемах над общей и распределенной памятью». В этой работе он ввел понятие информационного графа, где вершинами являются полюсы (аргумевты и результаты) схемы, а дуги означают информационные связи от результата к аргументу. В частности, им было показано, что области действия по Лаврову являются компонентами связности информационного графа. На этом формирование общей теории зкономии памяти в операторных схемах, по существу, закончилось.
Модернизированное изложение теории, практически совпадающее в содержанием з 2.3, было дано А. 11. Ершовым в статье «Аксяоматика распределения памяти» опубликованной в трудах симпозиума «Теория языков и методы построения систем программирования» (Киев — Алушта, Редакционно-издательский отдел Института кибернетики АН УССР, 1972). Сведение задачи экономии памяти к раскраске вершин графа обратило взоры программистов в сторону теории графов. Одним из первых результатов такого интереса явилась совместная работа А. П. Ершова и Г. И. Кожухина «Об оценках хроматического числа связных графов» (Доклады Академии наук СССР, т. 142, № 2, 1962).
Интересно заметить, что один из ее авторов, Г. И. Кожухин, пришел к этой работе, интересуясь теорией раскраски самой по себе. Им была доказана теорема о соцзетных вершинах (теорема 8, з 3.4) и верхняя оценка хроматического числа как функция числа вершин и ребер графа. Вклад другого автора состоял в нижней оценке и в использовании восходящей к А. А.
Зыкову трактовки раскраски как последовательного склеивания вершин. В. В. Мартынюк в статье «Об экономном распределении памяти», опубликованной в 1962 г. в 3-м номере «Журнала вычислительной математики и математической физики», описал приведенное нами в главе 3 построение операторной схемы по произвольному графу несовместимости, а также предложил некоторую эвристику совмещения равновесных массивов. Л.
К. Трохан провела в 1962 г. серию экспериментов по раскраске графов 45-го порядка на ЭВМ с использованием всех трех гл. ». 3Аключитвльныи АнАлиз обсуждавшихся в $ 3.4 эвристик, доказавшую практичность даже простейшей эвристики. Опыт практического применения теории экономии памяти в конструировании транслятора был получен при проектировании так называемого альфа-транслятора, транслирующего на машинный язык программы, выраженные на альфа-языке, некотором расширении алгола.
Этот опыт был описан в работе А. П. Ершова, Л. Л. Змиевской, Р. Д. Мишкович, Л. К. Трохан «Экономия и распределение памяти в «Альфа-трансляторе», опубликованной в сборнике «Альфа — система автоматизации программирования» (Новосибирск, Сибирское отделение издательства «Наука», 1967). В качестве операторов схемы брались линейные участки машинной программы, а также гамаки простой структуры. Тело процедуры трактовалось так, что его первый оператор считался преемником каждого вызова данной процедуры, а преемниками оператора выхода из процедуры — все операторы, стоящие в программе вслед за вызовами. Кслн оператор имел в качестве аргумента формальный параметр х, то его аргументами считались все величины, 'подставляемые в вывозах на место х. Аналогично дело обстояло с результатами. Компоненты связности не строились, но учитывалась несвязность и неконкурентность маршрутов величин, описанных в параллельных блоках.
Другими словами, если описания любых величин х и у попадали в параллельные блоки, то они рассматривались в схеме как разные совместимые величины. В качестве величин рассматривались не только скаляры (занимающие одну ячейку памяти), но и массивы (векторы). Граф несовместимости задавался своей матрицей смежности и раскрашивался по первой эвристике. Массивы одинаковой длины совмещались друг с другом целиком, «один в один». При помещении массива А меньшей длины з более длинный массив В делалась попытка разместить в остатке массива В другие величины, совместимые с В, но не совместимые с А.
К моменту написания этой книги литература, относящаяся к вопросу экономии памяти, содеря«ит уже несколько десятков названий. Эти работы развивают алгоритмическую технику зкономии памяти (построение транзитивных замыканий, эврнстнка раскраски и совмещения массивов), рассматривают экономию памяти в контексте более широких преобразований программ, распространяют теорию на более содержательные классы операторных схем и программ.
Само понятие операторной схемы, различные ее свойства или извлекаемые из нее объекты продолжают изучаться в теоретических работах. О некоторых нз ннх у нас еще будет повод поговорить во второй частя книги, а в остальном знакомство с дальнейшим развитием этой темы становится предметом специального изучения, выходящего за рамки наших бесед. ЧАСТЬ 11 ПРЕОБРАЗОВАНИЯ СХЕМ ЯНОВА ГЛАВА 6 КРАТКОЕ ПОВТОРЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ $6.1. Логические формулы и булевы функции Предмет логики. Логика, подобно арифметике и геометрии, является одной из математических дисциплин, с предметом которой человек, даже того не ведая, имеет дело с первых лет своей сознательной жизни.
Более правильным было бы, пожалуй, сказать, что законы правильного рассуждения о предметах и явлениях, наряду со свойствами форм предметов и количествеаными соотношениями между предметами, являются главным содержанием математики, если говорить о ее вкладе в повседневную человеческую практику. Интересно, однако, отметить, что логика, будучи как организующий элемент человеческого общения много старше математики, стала сама объектом математического изучения совсем недавно: ко-настоящему лишь в конце девятнадцатого века. Это тем более парадокрально, что математическая логика в чем-то проще многих други~1~ разделов математики.
Зтому парадоксу есть свое объяснение, которое, однако, автор не может изложить здесь с должной глубиной. Мы ааметим только, что, с одной стороны, математики в течение долгого времени и при этом в целом успешно полагались на здравый смысл в применении законов логического рассуждения, пока конкретный математический материал (обоснование математического анализа, парадоксц теории многкеств, неевклидова геометрия) не подвели их к необходимости заняться логическими основами самой математики. С другой стороны, необходимо было достичь высокого уровня абстрактного мышления и своего рода доверия к символике, чтобы правильно найти исходные абстракции логических рассуждений и быть уверенным в универсальной применимости формально выведенных законов логики, выраженных в символической форме.
В этой повторнтельной главе мы дадим краткий обзор одного из разделов математической логики — алгебры логики и исчисления высказываний, который, по мнению автора, обладает многими замечательными качествами. Объекты этой теории н относящиеся к ней задачи сравнительно просты; в то же время доказываемые в алгебре логики и исчислении высказываний свойства н теоремы глубоки и содержательны, применимы к многим явленивм реаль- »ЗО Гл. 6. ИРАткое пОВтОРения мАтемАтическОЙ лОГики ного мира и многое в нем объясняют.
Построение теории, будучи весьма стройным и естественным, одновременно содержит в себе, как в зародыше, общую структуру многих богатых и сложных теорий современной математики. Одна из целей логического рассун<дения — это установление истины, т. е. возможности достоверно подтвердить или опровергнуть некоторое высказывание. Уже в одной этой фразе содержатся одновременно некоторое наблюдение и некоторое ограничение.
Человек рассуждает, произнося фразы на человеческом, или, как говорят, естественном языке. Ограничение состоит в том, что мы рассматриваем лишь такие фрааы естественного языка (высказывания), о которых имеет смысл говорить, что они правильны или неправильны, истинны нли лоясны. Наблюдение подсказывает нам, что свойства истинности,или ложности оказываются взаимно дополняющими; другими словами, естественный яаык устроен так, что если мы имеем некоторое ложное высказывание («Москва— столица Франции»), то всегда можно высказать его отрицание, являющееся истиным высказыванием («Неверно, что Москва— столица Франции»), и наоборот.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
