М.М. ГОРБУНОВ-ПОСАДОВ - Системное обеспечение пакетов прикладных программ (1184225), страница 36
Текст из файла (страница 36)
Планировщик работает исходя из следующих предпосылок.В данной ситуации заданы начальное и целевое состояние, т.е. множествоэлементов ситуации, значения которых предполагаются известными, имножество элементов, значения которых нужно вычислить. Требуется найтиминимальную по цене цепочку модулей из функционального наполненияпакета, последовательное применение которых к начальномусостоянию позволяет определить значения элементов целевого состояния.Модуль М считается применимым к состоянию S, если вх (М) ⊆ S.Применение модуля M дает новое состояние S’ = S ⊇ вых (М).Специфика планирования вычислений по сравнению с планированиемпроизвольных направленных действий заключается в том, что S' = S ∪ вых(М).
Поэтому при планировании исключается (при существовании решения)возможность построения тупикового пути.В планировщике исполнителя ЗАДАЧА применен простой методпланирования, заключающийся в построении нескольких случайноподобранных, но очищенных от лишних вычислений цепочек и в выборе изних в качестве решения цепочки с минимальной ценой.
Тот факт, что припостроении случайной цепочки невозможны тупики, а также то, что изцепочек исключаются лишние модули, чем обеспечивается приемлемоекачество любой получаемой цепочки, делает предложенный способпланирования достаточно практичным и эффективным. Число цепочекопределяется ресурсом, представляющим собой ограничение на суммарнуюдлину сгенерированных цепочек. Время практически линейно зависит отвыбранного ресурса, и если он достаточно велик, то результатомпланирования будет цепочка, близкая к минимальной.Генерация случайной цепочки происходит следующим образом.Планировщик в ответ на запрос о модуле получает от конкретизатораописание во внутреннем представлении входов и выходов некоего случайновыбранного модуля - вх (М) и вых (М). Если для текущего состояния (вкачестве первого текущего состояния берется начальное) выполняютсяусловия S ⊇ вых (M) и ¬(S ⊇ вых (М)), т.е.
если модуль М применим к S и егоприменение позволяет вычислить значения новых элементов ситуации, томодуль М включается в планируемую цепочку, а в качестве текущегоберется состояние S’ = S ∪ вых (М). Если эти условия не выполняются, тоследует запрос к конкретизатору с требованием предоставить описаниедругого модуля. Построение цепочки успешно завершается, если длянекоторого текущего состояния окажется, что целевое состояние являетсяего подмножеством. Далее обратным просмотром из полученной цепочкиисключаются лишние модули, т.е. модули, не участвующие в вычислениизначений элементов целевого состояния. После этого планировщикгенерирует запросы к конкретизатору о цене модулей, входящих в«чистую» цепочку, и, суммируя полученные значения, определяет ее цену.Как видно из описания функций планировщика, основными задачамиконкретизатора являются извлечение необходимой для планировщикаинформации о конкретных конфигурациях, обсчитываемых модулями, и означениях тех характеристик модулей, которые являются параметрамиоптимизации, а также перевод этой информации во внутреннее представление.
Работа конкретизатора представляет собой диалог с системойВОПРОС-ОТВЕТ-2, в котором конкретизатор генерирует вопрос,обрабатывает множество полученных ответов, по результатам обработкиснова генерирует вопрос к системе и т.д. Конкретизатор работаетследующим образом. Первоначально он формирует внутреннеепредставление начального и целевого состояний и передает этуинформацию планировщику. В ответ на запрос планировщика о модулеконкретизатор случайным образом выбирает модуль из имеющегося у негосписка модулей и формирует запрос к базе данных об обсчитываемых этиммодулем конфигурациях. Возможно, что этот модуль в заданном состояниине применим или его применение не вырабатывает новых известныхвеличин.
Тогда, в ответ на повторные запросы планировщика,конкретизатор осуществляет полный перебор (по кольцу) всего спискамодулей, начиная с данного. Если ни один модуль не подходит, значитзадача не имеет решения. Если же в некотором состоянии какой-либомодуль применим несколькими способами (например, когда имеетсянесколько треугольников, в которых известно по две стороны и одномууглу), то конкретизатор выбирает случайное возможное применение ивыдает его планировщику. Помимо этого, конкретизатор в ответ насоответствующий запрос планировщика вычисляет цену модуля, извлекаязначения его характеристик из базы данных.Последним этапом интерпретации оператора ЗАДАЧА являетсягенерация текста программы, реализующей спланированный расчет.Выполнение этого этапа не представляет принципиальной трудности,поскольку конкретизатором были получены все необходимые данные:соответствия между элементами ситуации и входными и выходнымиячейками модулей результирующей цепочки, номера начальных операторов модулей, являющиеся их идентификаторами в системе ВОПРОСОТВЕТ-2, а также значения элементов ситуации, определенные при еезадании.
Вместе со спланированной цепочкой эти данные однозначноопределяют последовательность вызовов модулей и интерфейс междуними. Сгенериро-ванная программа помещается на хранение в базу данных.Идентификатором программы служит номер ее первого оператора,задаваемый при постановке задачи. Вместе с программой запоминаютсяданные, необходимые для ее запуска, а также (для проверки корректностизапуска) подмножество элементов начального состояния, котороеиспользовалось в найденном решении.Работа исполнителя ЗАПУСК начинается с проверки полнотымножества значений тех элементов начального состояния, которыеиспользуются при найденном решении.
В том случае, если значениянекоторых из этих элементов не определены, на терминал выдаетсясоответствующий отказ. Если же при проверке полнота подтвердилась,исполнитель ЗАПУСК формирует и передает на обработку системеВОПРОС-ОТВЕТ-2 вычислительный оператор вида ВЫПОЛНИ <номероператора>, который обеспечивает передачу управления на первыйоператор сгенерированной программы расчета.
После выполнения этойпрограммы значения элементов целевого состояния выдаются на терминал.В следующем разделе приводится протокол работы с пакетом МП,снабженный соответствующими комментариями.6.3.5. Протокол работы с пакетом МП. Далее следует протокол сеансаработы с пакетом МП. Основной комментарий к протоколу будет дан вконце раздела. Здесь отметим только, что сообщения, выдаваемые пакетом,печатаются в протоколе с отступом в четыре позиции.НАЧИНАЙТЕ РАБОТУПРЕДПИСАНИЕ 'ЧТЕ СЕМАНТИКА'ПОНЯТНОПРОЧТИ ГЕОМЕТРИЮСИТУАЦИЯ: ПРЯМАЯ - А В, ПРЯМАЯ - В С, ПРЯМАЯ - C D,ПРЯМАЯ - A G D, ПРЯМАЯ - A F Е C, ПРЯМАЯ - B E D,ПРЯМАЯ - В F G, РАВНЫ AT FC, РАВНЫ BE EDЗАДАЧА: ДАНО АВ И AF И FE И У-ВАF, НАЙТИ S-CDE,ОПТИМИЗИРУЯ ВРЕМЯ, НАЧАЛО ПРОГРАММЫ 10ЗАДАЧА РЕШЕНА, ПРОГРАММА С 10 ДО 94ВЫДАЙ ПРОГРАММУ С 10 ДО 9410 ПУСТЬ Р(1) = Э(1001)12 ПУСТЬ Р(2) = Э(1002)14 ПУСТЬ Р(3) = Э(1004)16 ВЫПОЛНИ 100018 ПУСТЬ Э(1016) = Р(4)20 ПУСТЬ Э(1021) = Р(6)22 ПУСТЬ Э(1047) = Р(5)24 ПУСТЬ Р(1) = Э(1021)26 ВЫПОЛНИ 150028 ПУСТЬ 3(1022) = Р(2)30 ПУСТЬ Р(1) = Э(1002)32 ВЫПОЛНИ 123334 ПУСТЬ 3(1006) = Р(2)36 ПУСТЬ Р(2) = Э(1003)38 ПУСТЬ Р(1) = Э(1006)40 ВЫПОЛНИ 140042 ПУСТЬ Э(1007) = Р(3)44 ПУСТЬ Р(1) = Э(1003)46 ПУСТЬ Р(2) = Э(1016)48 ПУСТЬ Р(3) = Э(1022)50 ВЫПОЛНИ 100052 ПУСТЬ Э(1013) = Р(4)54 ПУСТЬ Э(1055) = Р(6)56 ПУСТЬ Э(1025) = Р(5)58 ПУСТЬ Р(1) = Э(1013)60 ВЫПОЛНИ 123362 ПУСТЬ Э(1015) = Р(2)64 ПУСТЬ Р(1) = Э(1025)66 ВЫПОЛНИ 123368 ПУСТЬ Э(1028) = Р(2)70 ПУСТЬ Р(1) = Э(1007)72 ПУСТЬ Р(2) = Э(1015)74 ПУСТЬ Р(3) = Э(1028)76 ВЫПОЛНИ 100078 ПУСТЬ Э(1029) = Р(4)80 ПУСТЬ Э(1053) = Р(6)82 ПУСТЬ Э(1046) = Р(5)84 ПУСТЬ Р(1) = Э(1007)86 ПУСТЬ Р(2) = Э(1015)88 ПУСТЬ Р(3) = Э(1029)90 ВЫПОЛНИ 160092 ПУСТЬ Э(1005) = Р(4)94 ВОЗВРАТВЫЧИСЛИ А = ARCSIN 0.6ВЫДАЙ А.643501108ЗАПУСК: ПРИ АВ = 5 И AF = 4.5 И FE = 2.3 ИУ-FAB = 0.78, НАЧАЛО ПРОГРАММЫ 10S-CED = .298597720Е1ЗАПУСК: ПРИ ВА = 8.7 И AF = 4.5 И FE = 2.3 И У-FAB =0.78,НАЧАЛО ПРОГРАММЫ 10S-CED = .673038404Е1ВОПРОС 'НАЧАЛО К1 1000'НАЧАЛО А0 1000ВОПРОС 'МОДУЛЬ А0 К1'МОДУЛЬ А0 ПО-ДВУМ-СТОРОНАМ-ТРЕУГОЛЬНИКА-ИУГЛУ-МЕЖДУ-НИМИ-ВЫЧИСПЯЕТ-ОСТАЛЬНЫЕ-УГЛЫ-ИТРЕТЫО-СТОРОНУ, ДЛИНА-ПРОГРАММЫ-16ВЫДАЙ ПРОГРАММУ С 1000 161000 ВЫЧИСЛИ Р(4) = Р(1) Р(1)1001 ВЫЧИСЛИ Т = Р(2) Р(2)1002 ВЫЧИСЛИ Р(4) = Р(4) + Т1003 ВЫЧИСЛИ Т = COS Р(3)1004 ВЫЧИСЛИ Т = Т 21005 ВЫЧИСЛИ Т = Т Р(1)1006 ВЫЧИСЛИ Т = Т Р(2)1007 ВЫЧИСЛИ Р(4) = Р(4) - Т1008 ВЫЧИСЛИ Р(4) = SQRT Р(4)1009 ВЫЧИСЛИ Р(5) = SIN Р(3)1010 ВЫЧИСЛИ Р(5) = Р(5) Р(2)1011 ВЫЧИСЛИ Р(5) = Р(5) : Р(4)1012 ВЫЧИСЛИ Р(5) = ARCSIN Р(5)1013 ВЫЧИСЛИ Р(6) = 3.142 - Р(5)1014 ВЫЧИСЛИ Р(6) = Р(6) - Р(3)1015 ВОЗВРАТВОПРОС 'ВРЕМЯ А0 К1'ВРЕМЯ А0 5ВОПРОС 'НАЧАЛО Kl 1600 И ВХОД Kl К2 ИЯЧЕЙКА K2 КЗ'НАЧАЛО Л0 1600 И ВХОД Л0 П7 И ЯЧЕЙКА П7 Р(1)НАЧАЛО Л0 1600 И ВХОД Л0 Л8 И ЯЧЕЙКА П8 Р(2)НАЧАЛО Л0 1600 И ВХОД Л0 Л9 И ЯЧЕЙКА П9 Р(3)ВОПРОС 'ВЫХОД ПО К1 И ЯЧЕЙКА Kl K2'ВЫХОД ПО П10 И ЯЧЕЙКА Л10 Р(4)ВОПРОС 'РОД Kl УГОЛ'РОД У-АВС УГОЛРОД У-АВЕ УГОЛРОД У-СВЕ УГОЛРОД У-BAF УГОЛРОД У-BAG УГОЛРОД У-CBF УГОЛРОД У-ECD УГОЛРОД У-BFE УГОЛРОД У-DEF УГОЛРОД У-EDG УГОЛРОД У-EFG УГОЛРОД У-ABF УГОЛРОД У-BCD УГОЛРОД У-ВСЕ УГОЛРОД У-CDG УГОЛРОД У-CDE УГОЛРОД У-FAG УГОЛРОД У-AGF УГОЛРОД У-DGF УГОЛРОД У-AFB УГОЛРОД У-AFG УГОЛРОД У-BEF УГОЛРОД У-ВЕС УГОЛРОД У-CED УГОЛРОД У-EBF УГОЛВОПРОС 'Kl ABD K2'ЭЛМ ABD СТЦВЕРШ ABD AВЕРШ ABD DУГОЛЗ ABD У-АВЕУГОЛ2 ABD У-BAGУГОЛ1 ABD У-EDGРОД ABD ТРЕУГОЛЬНИКСТОРОНА ABD АВВЕРШ ABD ВСТОРОНА ABD ADСТОРОНА ABD BDПЛОЩ ABD S-ABDВОПРОС 'РАВНО Kl K2 И ЭЛМ Kl СТЦ'РАВНО У-BFE У-AFG И ЭПМ У-BFE СТЦРАВНО У-DEF У-ВЕС И ЭПМ У-DEF СТЦРАВНО У-EFG У-AFB И ЭПМ У-EFG СТЦРАВНО AF CF И ЭПМ AF СТЦРАВНО CF AF И ЗПМ GF СТЦРАВНО BE ED И ЗПМ BE СТЦРАВНО ED BE И ЭПМ ED СТЦРАВНО У-AFB У-EFG И ЭПМ У-AFB СТЦРАВНО У-AFG У-BFE И ЭПМ У-AFG СТЦРАВНО У-BEF У-CED И ЭПМ У-BEF СТЦРАВНО У-ВЕС У-DEF И ЭПМ У-ВЕС СТЦРАВНО У-CED У-BEF И ЭПМ У-CED СТЦЗАДАЧА: ДАНО BF И FE И BE И ЕС, НАЙТИ AD,ОПТИМИЗИРУЯ РАЗМЕР, НАЧАЛО ПРОГРАММЫ 500ЗАДАЧА РЕШЕНА, ПРОГРАММА С 500 ДО 562ЗАПУСК: ПРИ BF = 5.9 И EF = 1.8 И BE = 5.5 И СЕ =2.4, НАЧАЛО ПРОГРАММЫ 500AD = .786618239E19000 ПУСТЬ К = 4989001 ВЫЧИСЛИ К = К + 29002 ЗАШЛИ КОМАНДУ К В А(К) КАК СТРОКУ9003 ЕСЛИ НЕВОЗМОЖНО НА 90119004 ОБРАЗУЙ В М ИЗ А(К) ОТ 5 ДО 119005 ЕСЛИ M HE-РАВНО 'ВЫПОЛНИ' НА 90019006 ОБРАЗУЙ В М ИЗ А(К) ОТ 13 ДО 169007 СОЕДИНИ 'НАЧАЛО К1 И М В М9008 СОЕДИНИ М И 'И МОДУЛЬ Kl K2' В M9009 ВОПРОС М9010 НА 90019011 ВОЗВРАТВЫПОЛНИ 9000НАЧАЛО Д0 1300 ИМОДУЛЬ Д0 ПО-ТРЕМ-СТОРОНАМ-ТРЕУГОЛЬНИКА-ВЫЧИСЛЯЕТЕГО-УГЛЫ,ДЛИНА-ПРОГРАММЫ-16НАЧАЛО Г0 1500 ИМОДУЛЬ Г0 ВЫЧИСЛЯЕТ-УГОЛ, ДОПОЛНЯНЩИЙ-ДАННЫЙ-ДО180-ГРАДУСОВ,ДЛИНА-ПРОГРАММЫ-2НАЧАЛО Е0 1100 ИМОДУЛЬ Е0 ВЫЧИСЛЯЕТ-СУММУ-ДЛИН-ДВУХ-ОТРЕЗКОВ,ДПИНА-ПРОГРАММЫ-2НАЧАЛО Н0 1233 ИМОДУЛЬ Н0 ПРИСВАИВАЕТ-ЗНАЧЕНИЕ-ОДНОЙ-ВЕЛИЧИНЫДРУГОЙ-ПРИ-РАВЕНСТВЕ-ЭТИХ-ВЕЛИЧИН, ДЛИНАПРОГРАММЫ-2НАЧАЛО Е0 1100 ИМОДУЛЬ Е0 ВЫЧИСЛЯЕТ-СУММУ-ДЛИН-ДВУХ-ОТРЕЗКОВ,ДЛИНА-ПРОГРАММЫ-2НАЧАЛО Н0 1233 ИМОДУЛЬ Н0 ПРИСВАИВАЕТ-ЗНАЧЕНИЕ-ОДНОЙ-ВЕЛИЧИНЫДРУГОЙ-ПРИ-РАВЕНСТВЕ-ЭТИХ-ВЕЛИЧИН, ДЛИНАПРОГРАММЫ-2НАЧАЛО А0 1000 ИМОДУЛЬ А0 ПО-ДВУМ-СТОРОНАМ-ТРЕУГОЛЬНИКА-И-УГЛУМЕЖДУ-НИМИ-ВЫЧИСЛЯЕТ-ОСТАЛЬНЫЕ-УГЛЫ-И-ТРЕТЬЮСТОРОНУ, ДЛИНА-ПРОГРАММЫ-16ПРЕДПИСАНИЕ 'ЧТЕ СЕМАНТИКА'ПОНЯТНОСИТУАЦИЯ:ПРЯМАЯ - А В,ПРЯМАЯ - А С,ПРЯМАЯ - В D С,ПРЯМАЯ - F D А, РАВНЫ BD АС, ЗНАЧЕНИЕ AD 3.5, ЗНАЧЕНИЕDC 2.1ЗАДАЧА: ДАНО У-BDF, НАЙТИ ВА И S-BDA,НАЧАЛО ПРОГРАММЫ 700ЗАДАЧА РЕШЕНА, ПРОГРАММА С 700 ДО 776ЗАПУСК: ПРИ У-BDF = 1.57, НАЧАЛО ПРОГРАММЫ 700АВ = .537891000Е1S-ABD = .714040100Е1ЗАДАЧА: ДАНО У-BDF, НАЙТИ FD, НАЧАЛО ПРОГРАММЫ 900РЕШЕНИЕ ЗАДАЧИ НЕ НАЙДЕНОЗАДАЧА: ДАНО У-BDF, НАЙТИ DA И DC, НАЧАЛО ПРОГРАММЫ900ИСКОМЫЕ ВЕЛИЧИНЫ ИЗВЕСТНЫКомментарий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
