Настоящая работа посвящена решению следующей задачи. Имеется граф. Требуется узнать, содержит или нет этот граф подграфы определенного вида, и если содержит, то указать в каких местах. При этом техника решения должна быть такова, чтобы вид графов, вхождения которых ищутся, мог задаваться в качестве параметра. Более точно, класс решаемых задач можно описать следующим образом: имеется набор графов и набор правил, с помощью которых более крупные графы можно конструировать из более мелких. Требуется узнать, можно ли сконструировать заданный граф. Рассматриваемая постановка исходно возникла как попытка развить сложившуюся к настоящему времени технику верификации и контроля типов данных в языках программирования. С теоретической точки зрения предлагаемые в работе результаты можно рассматривать как обобщение конечно-автоматной теории на случай анализа ориентированных графов (на вход автомата поступает не цепочка символов, а граф). С практической точки зрения предлагается технология анализа структур данных (размеченных ориентированных графов), подобная технологии лексических анализаторов. Основные компоненты подобной технологии представлены на рис.1. Как видно из рисунка, технология создания лексических анализаторов включает в себя компилятор с языка спецификаций (с языка регулярных выражений) в исполняемый код (в готовую программу распознавания – конечный автомат). При этом исполняемый код, как правило, несоизмеримо сложнее для восприятия человеком, чем исходная спецификация. Современные средства контроля типов данных также работают по схеме, представленной на рис.1. Например, в C++ (или в Java) в качестве языка спецификаций используется усеченный вариант регулярных выражений над деревьями (с помощью аппарата наследования классов реализуется объединение множеств, а конкатенация и итерация, хотя и не в полной мере, имитируется ссылками на типы членов описываемых классов), а в качестве программы анализа используется конечный автомат над деревьями (этот автомат строится по исходной спецификации). О том, что современные средства спецификации данных слабо развиты, свидетельствует хотя бы тот факт, что существующие средства описания типов данных не дают возможности задать даже такое ключевое для программирования понятие, как "двунаправленный список". Последнее связано с тем, что наличие средств описания структур данных в языке программирования подразумевает наличие следующих процедур: Под непротиворечивостью описания подразумевается факт существования хотя бы одной структуры данных, которая удовлетворяет требованиям, заданным в описании. Необходимость проверки исходной спецификации на непротиворечивость приводит к тому, что существующие средства описания обладают очень слабыми выразительными возможностями. Так, современнные языки спецификаций данных (включая все варианты графовых грамматик) либо недостаточно выразительны, чтобы точно описать двунаправленный список, либо не допускают возможность проверки непротиворечивости описания. В настоящей работе предлагается следующий подход к разрешению сложившийся тупиковой ситуации. Описывается формальный язык и две возможные интерпретации этого языка (две формальные теории, основанные на одном и том же языке): жесткая интерпретация и мягкая интерпретация одного и того же формального языка. При мягкой интерпретации можно осуществить проверку непротиворечивости, но язык обладает слабыми выразительными способностями (тем не менее, он при этом более выразителен, чем современные средства спецификации). А жесткая интерпретация хотя и порождает неразрешимую теорию (теорию с неразрешимой проблемой выполнимости), но обладает следующими ценными свойствами: 1. по любому описанию можно автоматически построить программу, которая допускает ровно те графы, которые соответствуют описанию; 2. выразительные возможности языка спецификаций при жесткой интерпретации довольно высоки (например, на нем можно совершенно точно описать, что такое двунаправленный список). В качестве распознающих графы программ (программ, которые строятся по спецификации) используются программы специального вида (итерационные и объектно-ориентированные итерационные автоматы), которые по своим алгебраическим свойствам очень похожи на обычные конечные автоматы. Для этих программ (автоматов) выполняется следующее свойство: для любого распознающего графы автомата существует соответствующее ему описание множества структур данных (описание типа данных). На рисунке 2 представлена схема информационных зависимостей между разделами. Кратчайшая последовательность для освоения основного теоретического результата (раздел 4.3) помечена на рисунке жирными стрелками. В главе 1 рассматривается три способа формального представления понятия "структура данных": Три способа формального представления структур данных потребовались по следующим причинам. При распознавании структур данных (при использовании формализма итерационных и объектно-ориентированных автоматов в главах 3 и 4) используется формализм функциональных схем. В то же время для спецификации типов даных используется более приближенный к реальным структурам данных конечно-автоматный формализм (исключением является описываемый в разделе 2.1 язык спецификации итерационных типов, который использует формализм функциональных схем). Именно из-за того, что распознавание происходит на уровне схем, а спецификация – на уровне автоматов, в разделе 1.2 так много внимания уделено вопросу перевода с автоматного уровня на схемный. То, что потребовалось два разных конечно-автоматных представления, связано с тем, что конечные автоматы используются в дальнейшем не только в формальном языке спецификации (глава 2), но и как элементы области интерпретации этого языка. При этом использование раскрашенных автоматов в качестве элементов области интерпретации приводит к созданию жесткой теории (жесткой интерпретации языка спецификаций). В то же время использование раскрашенных автоматов Мура в качестве элементов области интерпретации приводит к созданию языка, в котором проблема непротиворечивости спецификации разрешима... Андрей Владимирович БАБИЧЕВ Кандидат технических наук, старший научный сотрудник. В 1976 г. закончил МИИТ по специальности "прикладная математика". С тех пор работает в Институте проблем управления РАН. Кандидатская диссертация (1982) посвящена вопросам организации беспереборного синтаксического анализа контекстно-свободных языков. После защиты диссертации некоторое время занимался задачами автоматического распараллеливания (использование линейного преобразования для распараллеливания циклических конструкций), затем задачами, связанными с построением систем тестирования и верификации. В настоящее время занимается вопросами создания логического языка спецификации технических конструкций. В качестве разработчика участвовал в крупных проектах по созданию компиляторов (Fortran77, Pascal, С/С++ , Prolog), систем тестирования/верификации, систем моделирования и систем резервного копирования данных. |
2023. 720 с. Твердый переплет. 21.9 EUR
Книга «Зияющие высоты» – первый, главный, социологический роман, созданный интеллектуальной легендой нашего времени – Александром Александровичем Зиновьевым (1922-2006), единственным российским лауреатом Премии Алексиса де Токвиля, членом многочисленных международных академий, автором десятков логических... (Подробнее) URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR
Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее) URSS. 2024. 704 с. Твердый переплет. 26.9 EUR
В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее) 2023. 696 с. Твердый переплет в суперобложке. 119.9 EUR
Опираясь на новейшие исследования, историк Кристофер Кларк предлагает свежий взгляд на Первую мировую войну, сосредотачивая внимание не на полях сражений и кровопролитии, а на сложных событиях и отношениях, которые привели группу благонамеренных лидеров к жестокому конфликту. Кларк прослеживает... (Подробнее) URSS. 2024. 800 с. Мягкая обложка. 37.9 EUR
ВЕРСАЛЬ: ЖЕЛАННЫЙ МИР ИЛИ ПЛАН БУДУЩЕЙ ВОЙНЫ?. 224 стр. (ТВЁРДЫЙ ПЕРЕПЛЁТ) 11 ноября 1918 года в старом вагоне неподалеку от Компьеня было подписано перемирие, которое означало окончание Первой мировой войны. Через полгода, 28 июня 1919 года, был подписан Версальский договор — вердикт, возлагавший... (Подробнее) URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR
Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее) URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR
Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире. Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее) URSS. 2024. 248 с. Мягкая обложка. 14.9 EUR
В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные... (Подробнее) URSS. 2024. 240 с. Твердый переплет. 23.9 EUR
Предлагаемая вниманию читателей книга, написанная крупным биологом и государственным деятелем Н.Н.Воронцовым, посвящена жизни и творчеству выдающегося ученого-математика, обогатившего советскую науку в области теории множеств, кибернетики и программирования — Алексея Андреевича Ляпунова. Книга написана... (Подробнее) 2023. 416 с. Твердый переплет. 19.9 EUR
Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые... (Подробнее) |