|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[133] Упражнение 4.60. Подав запрос (живет-около ?person (Хакер Лиза П)) Лиза П. Хакер может найти людей, которые живут с ней рядом, и с которыми она вместе может ездить на работу. С другой стороны, когда она пытается найти все пары людей, живущих друг около друга, при помощи запроса (живет-около ?person-1 ?person-2) она видит, что каждая подходящая пара людей попадается в выводе дважды, например (живет-около (Хакер Лиза П) (Фект Пабло Э)) (живет-около (Фект Пабло Э) (Хакер Лиза П)) Почему так происходит? Можно ли получить список людей, живущих рядом друг с другом, в котором каждая пара появлялась бы по одному разу? Ответ объясните. Логика как программы Можно рассматривать правило как своего рода логическую импликацию: если присваивание значений переменным образца удовлетворяет телу, то оно удовлетворяет заключению. Следовательно, можно считать, что язык запросов способен производить логический вывод (logical deduction) на основании правил. В качестве примера рассмотрим операцию append, описанную в начале раздела 4.4. Как мы уже сказали, append характеризуется следующими двумя правилами: •Для любого списка y, append пустого списка и y дает y •Для любых u, v, y и z, append от (cons u v) и y дает (cons u z), если append от v и y дает z. Чтобы выразить это в нашем языке запросов, мы определяем два правила для отношения (append-to-form x y z) которое можно интерпретировать как «append от x и y дает z»: (rule (append-to-form () ?y ?y)) (rule (append-to-form (?u . ?v) ?y (?u . ?z)) (append-to-form ?v ?y ?z)) В первом правиле нет тела, и это означает, что следствие выполняется для любого значения ?y. Обратите также внимание, как во втором правиле car и cdr списка изображаются с использованием точечной записи. При помощи этих двух правил мы можем формулировать запросы, которые вычисляют append от двух списков: ;;; Ввод запроса: (append-to-form (a b) (c d) ?z) ;;; Результаты запроса: (append-to-form (a b) (c d) (a b c d)) Удивительнее то, что мы с помощью тех же правил можем задать вопрос «Какой список, будучи добавлен к (a b), дает (a b c d)?» Это делается так: ;;; Ввод запроса: (append-to-form (a b) ?y (a b c d)) ;;; Результаты запроса: (append-to-form (a b) (c d) (a b c d)) Можно также запросить все пары списков, append от которых дает (a b c d) : ;;; Ввод запроса: (append-to-form ?x ?y (a b c d)) ;;; Результаты запроса: (append-to-form () (a b c d) (a b c d)) (append-to-form (a) (b c d) (a b c d)) (append-to-form (a b) (c d) (a b c d)) (append-to-form (a b c) (d) (a b c d)) (append-to-form (a b c d) () (a b c d)) Может показаться, что, используя правила для вывода ответов на перечисленные запросы, система демонстрирует немалый интеллект. На самом же деле, как мы увидим в следующем разделе, при разборе правил она следует хорошо определенному алгоритму. К сожалению, хотя в случае с append результаты впечатляют, в более сложных ситуациях общие методы могут не сработать, как мы увидим в разделе 4.4.3. Упражнение 4.61. Следующие правила определяют отношение next-to, которое находит в списке соседние элементы: (rule (?x next-to ?y in (?x ?y . ?u))) (rule (?x next-to ?y in (?v . ?z)) (?x next-to ?y in ?z)) Каков будет ответ на следующие запросы? (?x next-to ?y in (1 (2 3) 4)) (?x next-to 1 in (2 1 3 1)) Упражнение 4.62. Определите правила, которые реализуют операцию last-pair из упражнения 2.17, которая возвращает последнюю пару непустого списка. Проверьте Ваши правила на таких запросах, как (last-pair (3) ?x) , (last-pair (1 2 3) ?x) и (last-pair (2 ?x) (3)) . Правильно ли Ваши правила работают с запросами вида (last-pair ?x (3)) ? Упражнение 4.63. Следующая база данных (см. книгу Бытия, 4) содержит генеалогию сыновей Ады вплоть до Адама, через Каина: (сын Адам Каин) (сын Каин Енох) (сын Енох Ирад) (сын Ирад Мехиаель) (сын Мехиаель Мафусал) (сын Мафусал Ламех) (жена Ламех Ада) (сын Ада Иавал) (сын Ада Иувал) Сформулируйте правила, такие как «Если S сын F, а F сын G, то S внук G» и «Если W жена M, а S сын W, то S также сын M» (предполагается, что в библейские времена это в большей степени соответствовало истине, чем теперь). Эти правила должны позволить системе найти внука Каина; сыновей Ламеха; внуков Мафусала. (В упражнении 4.69 можно найти правила, с помощью которых выводятся более сложные родственные связи.) 4.4.2 Как действует система обработки запросов В разделе 4.4.4 мы представим реализацию интерпретатора запросов в виде набора процедур. В этом разделе дается обзор системы и объясняется ее общая структура, без низкоуровневых деталей реализации. После того, как мы опишем интерпретатор, нам легче будет понять его ограничения и некоторые тонкости, в которых логические операции языка запросов отличаются от операций математической логики. Должно быть очевидно, что вычислителю запросов требуется какая-то разновидность поиска, чтобы сопоставлять запросы с фактами и правилами в базе данных. Одним из способов сделать это была бы реализация системы запросов в виде недетерминистской программы с использованием amb-интерпретатора из раздела 4.3 (см. упражнение 4.78). Другая возможность состоит в том, чтобы управлять поиском при помощи потоков. Наша реализация использует этот второй подход. Запросная система организована вокруг двух основных операций, которые называются сопоставление с образцом (pattern matching) и унификация (unification). Сначала мы опишем сопоставление с образцом и объясним, как эта операция, вместе с организацией информации в виде потоков кадров, позволяет нам реализовывать как простые, так и составные запросы. Затем мы обсудим унификацию - обобщение сопоставления с образцом, которое требуется для реализации правил. Наконец, мы покажем, как части интерпретатора связываются воедино процедурой, классифицирующей выражения, подобно тому, как eval разбирает выражения в интерпретаторе, описанном в разделе 4.1. Сопоставление с образцом Сопоставитель (pattern matcher) - это программа, которая проверяет, соответствует ли некоторая структура данных указанному образцу. Например, список ((a b) c (a b)) соответствует образцу (?x c ?x) при значении переменной ?x, равном (a b) . Этот же список соответствует образцу (?x ?y ?z) при значениях переменных ?x и ?z, равных (a b) и значении ?y, равном b. Однако он не соответствует образцу (?x a ?y) , поскольку этот образец требует, чтобы вторым элементом списка был символ a. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||