Cтраница 3
Вместе с тем в этих алгоритмах многое должно быть общим в связи с тем, что конечный результат работы алгоритма - двумерное изображение - в принципе одинаково для различных ИПС. При реализации любого алгоритма приходится сталкиваться с примерно аналогичными трудностями. Немало общего должно быть у алгоритмов вывода структурной химической информации и алгоритмов вывода других видов графической информации. [31]
Вместе с тем в этих алгоритмах многое должно быть общим в связи с тем, что конечный результат работы алгоритма - двумерное изображение - в принципе одинаково для различных ИПС. При реализации любого алгоритма приходится сталкиваться с примерно аналогичными трудностями. Немало общего должно быть у алгоритмов вывода структурной химической информации и алгоритмов вывода других видов графической информации. [32]
В данной ситуации особое значение приобретает способность алгоритма проводить направленный вывод, не генерировать излишних дизъюнктов, а также быстро определять кандидатов на резольвиро-вание и получать соответствующую резольвенту. Подобным требованиям удовлетворяют алгоритмы дедуктивного вывода на графах связей, так как пространство поиска на каждом шаге является легко обозримым ( в графе одновременно хранится информация обо всех кандидатах на резольвирование), дизъюнкты, которые не могут результативно участвовать в процессе вывода ( дизъюнкты с чистыми литерами - литерами без связей), удаляются из графа связей вместе со всеми связями, значительно упрощая его структуру. Быстрота вывода обеспечивается однократным вычислением и постоянным хранением унификатора для каждой связи. Также достоинством процедуры вывода на графе связей является возможность адаптации существующих алгоритмов для вывода на графе связей, что позволяет комбинировать достоинства существующих алгоритмов вывода и алгоритмов вывода на графах связей. Недостатками процедуры вывода на графе связей являются необходимость пересчета графа связей на каждом шаге резольвирования с вычислением новых связей и унификаторов и необходимость хранения всего графа связей в оперативной памяти. Параллельный вывод на графах связей позволяет частично решить проблему необходимости пересчета графа на каждом шаге резольвирования, так как одновременно резольвируются несколько связей. Недостатком процедур параллельного вывода является генерация некоторого количества бесполезных, лишних дизъюнктов, что вытекает из самого принципа организации параллельного вывода, когда резольвируются все связи одновременно. [33]
Для управления очередью используются два управляющих слова: одно содержит адрес первого элемента очереди, другое - адрес последнего элемента. Добавление элемента в очередь происходит сравнительно просто. Если начальную ячейку элемента, который должен быть введен в очередь, обозначить через Z, а ее содержимое - через С ( Z), то суть алгоритма заключается в том, чтобы обратить С ( Z) в 0000, показав тем самым, что это теперь последний элемент очереди, и изменить предпоследний элемент очереди, связав его с ячейкой Z. Управляющее слово очереди, указывающее ее последний элемент, также нужно изменить, чтобы оно содержало адрес Z. Если исключить проверку очереди на пустоту, алгоритм вывода элемента из очереди сходен с алгоритмом ввода, но применяется управляющее слово, содержащее адрес первого элемента в очереди. [34]
Большинство алгоритмов синтеза больших систем так или иначе связаны с перебором вариантов, что, в свою очередь, сводится к вычислению эффективности системы при заданных значениях ее параметров. Поэтому важной задачей является построение общих формул для эффективности системы, учитывающих возможность варьирования ее структуры. Заметим, что если имеются удобные аналитические формулы для эффективности систем из некоторого класса L, то выбор оптимального варианта системы из этого класса может быть осуществлен эффективно. Если же для каждой системы нужно выводить свою формулу для эффективности, то задача синтеза затрудняется. К настоящему времени выявлены некоторые классы систем подобного рода, причем вместе с теоремой о существовании решения в заданном классе аналитических выражений приводится также явный алгоритм вывода этих выражений, допускающий реализацию на цифровой вычислительной машине. Это делает возможным осуществить синтез ( правда, в ограниченном классе систем) вполне автоматически. [35]