Исследовательский потенациал молодых ученых: взгляд в будущее - 2017

ХIII Региональная научно-практическая конференция аспирантов, соискателей, молодых ученых и магистрантов 196 жит использование логики предикатов первого порядка, а также идея, согласно которой программист указывает программе не последова‐ тельность шагов решения задачи, а описывает предметную область задачи на логическом языке. Заметим, что хотя первые компьютерные реализации систем ав‐ томатического доказательства теорем появились еще в конце пятиде‐ сятых годов прошлого века, основной принцип построение таких сис‐ тем был сформулирован лишь в 1965 году Дж. Робинсоном [1]. Робин‐ сон разработал правило резолюций – правило вывода, которое позво‐ ляет ответить на вопрос, существует ли в исходном множестве логи‐ ческих выражений противоречие [2]. Данное правило является более сильным правилом вывода, чем modus ponens [1], и оно эффективно реализуется с помощью компьютера. Кроме того, именно правило ре‐ золюций явилось тем фундаментом, на котором был построен один из наиболее известных языков логического программирования – Пролог. Название языка является сокращением, обозначающим программиро‐ вание в логике [3]. Рассмотрим на примере данного языка основные плюсы и мину‐ сы логического программирования: До тоинства: 1. Операции, совершаемые в логическом программировании всегда понятны; 2. Результат практически всегда не зависит от выбранного пути реализации; 3. Применяется в качестве не вычислительного языка, исполь‐ зуя только выражения и факты. Недостатки: 1. Невозможность реализации комплексных проектов, т. е. в ре‐ альности логический язык может идти дополнением к процедурному, но самостоятельно используется крайне редко; 2. Из‐за недостатка в инвестициях и простом внимании, слабо развивается; 3. Не лучший выбор в задачах с вычислительными операциями. Вернемся к задаче о построении минимального остовного дере‐ ва. В качестве языка реализации описанного алгоритма будем исполь‐ зовать Пролог, что накладывает определенные ограничения: по‐ скольку в данном языке отсутствуют массивы, то граф будем пред‐ ставлять списком, который будет хранить пары вершин, соединенных ребром, и вес самого ребра. Изначально данный список будет пустым. Затем из всех ребер, добавление которых к текущему подграфу не вы‐ зовет появления цикла, выбирается ребро наименьшего веса и добав‐