Реферат: Анализ снизу вверх и сверху вниз - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Анализ снизу вверх и сверху вниз

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 126 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

4 АНАЛИЗ СНИЗУ ВВЕРХ И СВЕРХУ ВНИЗ “Сверху вниз” vs . “снизу вв ерх” , “прямой” vs . “обратный” , “ управляемый данными” vs . “движимый целью” - три пары определений для таких терминов , как “цепной анализ” , “парсинг” , “синтаксический разбор” , “ логический анализ” и “поиск” . В принципе , все эти термины отражают сходные отноше ния , и различие между ними состоит лишь в том , что они взяты из различ ных подобластей компьютерной науки и искусств енного интеллекта (парсинг , системы с заложенн ыми в них правилами , поисковые системы и системы , направленные на решение проблем и т.д .) Суть этих противопоставлений можно проиллюстриров ать на примере парадигмы поиска . Основная задача любого поиска состоит в том , чтобы определить маршрут , по которому вы будете перемещаться с настоящей позиции к вашей цели . Если вы начнете поиск с текущей позици и и будете продолжать ег о , пока не наткнетесь на желаемый результа т , - это так называемый прямой поиск или поиск снизу вверх . Если вы мысленно ста вите себя в то место , где вы хотите очутиться в результате поиска и определяет е маршрут , двигаясь в обратном н а правлении , т.е . туда , где вы действитель но находитесь в настоящий момент , - это пои ск в обратном направлении или поиск сверх у вниз . Обратите внимание на то , что , о пределив маршрут в результате обратного поиск а , вам все же предстоит добраться до с воей цели. Несмотря на то , что сейчас вы движетесь вперед , это не является прямым поиском , т.к . поиск уже был осуществ лен ранее , причем в обратном направлении. Эти же противопоставления можно рассмотреть на пр имере систем с встроенными правилами . Предста вим себе , чт о правило состоит из н абора антецедентов и набора следствий . Когда система определяет , что все антецеденты о пределенного правила удовлетворены , это правило вызывается и выполняется (выполняется ли ка ждое вызванное правило зависит от специфики конкретной с и стемы ). После этого в базу знаний заносятся утверждения , полу ченные в результате выполнения правила , и выполняются соответствующие операции . Данный проц есс происходит вышеописанным образом , независимо от того , применяет ли система прямой или обратный лог и ческий анализ . Чт обы проиллюстрировать различия между ними , сл едует отдельно рассмотреть процедуру активации правила . Вызываются только активированные прави ла . При прямом логическом анализе (снизу в верх ), когда в систему добавляются новые д анные , они срав н иваются со всеми антецедентами всех правил . Если данные со ответствуют антецеденту правила , то это прави ло активируется (если оно еще не является активированным ), и если подобраны все ант ецеденты определенного правила , то оно вызыва ется . Утверждения , получ е нные в ре зультате выполнения правила , заносятся в базу знаний и рассматриваются в качестве новы х данных , сравниваются с антецедентами и м огут вызвать активацию и вызов дополнительных правил . При обратном логическом анализе ( сверху вниз ) при добавлении дан н ых правила не активируются . Когда система по лучает запрос , он сравнивается со всеми сл едствиями всех правил . Если запрос совпадает со следствием , то это правило активируетс я , а все его антецеденты рассматриваются в качестве вторичных запросов и могут вызв а ть активацию дополнительных правил . Когда запрос соответствует не ограниченному условием утверждению базы знаний , на него поступает ответ , и если этот запрос и сходил от антецедента , считается , что он у довлетворяет последнему . Когда все антецеденты некот о рого правила будут удовлетво рены , правило вызывается и выполняется . При выполнении правила осуществляется ответ на запросы , которые его активировали , и теперь другие антецеденты считаются удовлетворенными и могут вызываться соответствующие им прав ила . Обр а тите внимание на то , ч то вызов и выполнение правила всегда прои сходит в прямой последовательности , а отличие прямого цепного анализа от обратного сос тоит в том , когда активируется правило . Примеры Парсинг . Попытаемся проиллюстрироват ь и объяснить разниц у между синтаксич еским анализом сверху вниз и снизу вверх на примере предложения “ They are flying planes ” и простой грамматики , пред ставленной в виде пронумерованных правил : 1. S NP VP 2. NP N 3. NP PRO 4. NP ADJ N 5. VP VT NP 6. VT V 7. VT AUX V 8. N planes 9. PRO they 10. ADJ flying 11. AUX are 12. V are 13. V flying Антецеденты указаны с правой стороны , а следствия - с левой . Например , правило 1 читается следующим образом : “Е сли последовательность состоит из именной группы (NP), за которой следует глагольная группа (VP), то эта последовательность является предложением (S).” Синтаксический разбор сверху вниз начи нается с символа S, который и будет являтьс я вершиной дерева раз бора . Эта процед ура эквивалентна процедуре постановки задачи , которая заключается в том , чтобы определить , является ли последовательность слов предложени ем . Правило 1 гласит , что каждое предложение состоит из именной группы (NP), за которой следует глаго л ьная группа (VP). При н аличии нескольких правил , сперва применяется правило с наименьшим номером , а затем оно расширяется слева направо . Таким образом следующим шагом является нахождение первой св язи , т.е . NP. Сперва активируется правило 2, а з атем правил о 8 (рис . 2 а ). Т.к . “ planes” не со ответствует ” they” , алгоритм срабатывает вновь , и теперь сперва активируется правило 3, а затем правило 9. Затем алгоритм возвращается к правилу 1 и следующей целью ставит о пределение VP. Сперва активируются правила 5, 6, а затем 12 (рис . 2 b ). Дальнейший ход разбора отржен на рисунке 2 ( с , d, e). Синтаксический разбор снизу в верх начинается со слов в предложении . Опя ть же разбор ведется слева направо , и сперва применяется правило с наименьшим номер ом . Итак , сначала первое слово предложени я “ they” соотносится с антецедентом правила 9, которое после выполнения выдает утверждение , что “ they” является местоимением (PRO). Затем выполняется правило 3 и выдает , что “ they” является NP. NP соответствует антецедентам правил 1 и 5, н о ни одно из этих пра вил еще не вызвано , поэтому разбор переход ит к “ are” . Выполняется правило 11 (несмотря на то , что правило 12 также вызвано , оно не выполняется в соответствии с правилом о последовательности выполнения правил ). Затем выполняются правила 10, 8 и 2 (рис . 3 а ). На данной стадии дальнейший разбор последовательности NP+AUX+ADJ+NP невозможен , поэтому мы возвращаемся к посл еднему вызванному , но еще не выполненному правилу , т.е . к правилу 4. Разбор последовательно сти NP+AUX+NP так же невозможен, поэтому опять выполняется последнее вызванное невыполненное правило . Сейчас это правило 13, которое выдает , что “ flying” является V. Затем выполняются правила 6 и 5 (рис . 3 с ). Ра збор последователльности NP+AUX+VP невозможен , поэтому выполняется пр авило 7 и выдает утверждение , что “ are flying” является VT. Затем снова выполняются правил а 5 и 1, на чем и заканчивается синтаксически й разбор (рис . 3 d ). Данный пример был приведен с целью сравнения механизмов синтаксического разбора с низу вверх и сверху вниз . Ус тановление строгого порядка разбора слева направо и нумерация правил обусловлены стремлением к применению в наибольшей степени сходного алгоритма , несмотря на то , что результаты разбора оказались различными . Системы со встроенными прави лами . Рассмотрим прямой и обратный цепной анализ на примере выдума нного набора правил о том , как следует провести вечер . Правила расположены в обычн ом порядке , антецедент располагается слева , а следствие - справа , все вызванные правила выполняются , а разбор ведется паралл е льно. 1. Хороший фильм по ТВ + Рано утром встреч нет Позднее кино 2. Рано утром в стреч нет + Нужно поработать Работа допоздна 3. Нужно поработать + Необходимы документы Работа в офисе 4. Позднее кино Не спать допоздна 5. Работа допоздна Не спать допоздна 6. Работа допоздна Возвращение в офис 7. Работа в офисе Возвращение в офис Например , пра вило 1 гласит , что если по ТВ идет хоро шее кино и у меня завтра рано утром встреч нет , тогда я следую режиму “Позд нее кино” . Расс мотр им сперва пример прямого цепного анализа . Допустим , система получила начальную информацию о том , что завтра рано уторм у меня нет встреч . Активируются правила 1 и 2. Допу стим , что далее система получила сообщение о том , что мне нужно поработать . Акти в ируется правило 3, а правило 2 вызыв ается и выполняетя , откуда следует вывод , что я нахожусь в режиме “Работа допоздна” , в результате чего вызываются и выполняют ся правила 5 и 6. В итоге система заключает , что я должна вернуться в офис и не спать допоздн а. Теперь рассмо трим эту же проблему с применением обратн ого цепного анализа . Допустим , что система получила исходную информацию о том , что у меня нет завтра утром встреч , но мне нужно еще поработать , а затем ее (сист ему ) спросили , следует ли мне вернуться в офис . Данный запрос активирует прави ла 6 и 7. В свою очередь возникнет вопрос “Работа допоздна” или “Работа в офисе” ? При этом активируются правила 2 и 3, и возни кает вопрос “Рано утром встреч нет” , “Нуж но поработать” или “Нужны документы” ? Первые д в а антецедента будут удовлетвор ены , таким образом правило 2 будет вызвано и выполнено , что повлечет за собой удовлет ворение антецедента “Работа допоздна” , вызов и выполнение правила 6, в результате чего с истема придет к заключению , что мне следуе т вернутьс я в офис. Обратите внимание на то , что при п рямом разборе порождается больше следствий , а при обратном - запросов . Т.к . в обоих пр имерах использовались одни и те же данные , то в ходе анализа выполнялись одни и те же правила , но активировались различны е. Ср авнение Эффективность . Выбор вида анализа (сверху вниз или снизу вверх ) зависит от конфиг урации дерева , по которому осуществляется пои ск . Если в среднем каждому элементу следует большее ко личество элементов , нежели пред шествует , то анализ сверху в низ (или обратный анализ ) будет более эффективным и наоборот . Рассмотрим крайний случай . Допустим , что поисковая область образу ет дерево с вершиной в начальном состояни и . Тогда при использовании прямого подхода нам придется осуществлять поиск практически по все м у дереву , тогда как при обратном подходе - только в его линейн ой части. Сравнение и унификация . В системах с заложенными правила ми или системах логического анализа выбор прямого или обратного цепного анализа влия ет на степень трудности процесса сравнения. При прямом цепном анализе системе постоянно предъявляются новые факты , не имеющ ие свободных переменных . Таким образом постоя нно проводится сравнение антецедентов , вполне вероятно обладающих свободными переменными , с фактами , не обладающими таковыми . С другой стороны , системам с обр атным цепным анализом често задают специальны е вопросы . Если правила изложены в логике предикатов , а не логике суждений , тогда производится сравнение вопроса с переменной со следствием с переменными . Вторичные запр осы также могут содержать переменные , поэтому , в общем , системы с обратным цепным анализом должны быть разработаны таким образом , чтобы они могли сравнивать две символьные структуры , каждая из которых м ожет содержать переменные , для чего потребует ся создание алгори т ма унификации . Смешанные стр атегии Поиск в двух направлениях . Если не я сно , какой вид поиска - прямой или обратный - является наиболее приемлимым для конкретног о приложения , следует осуществлять поиск в двух направлениях . В таком случае , отправным и точк ами становятся начальное и коне чное состояние , и поиск осуществляется по направлению к центру. Вывод по двум направлениям . При данном подходе изначаль ные данные применяются для активирования прав ил , котоые перебирают другие антецеденты в обратном порядке. Вторичные запросы , котор ые не соответствуют ни следствиям , ни данн ым , сохраняются в качестве “демонов” , которые могут быть удовлетворены позднее за счет новых или позднее поступивших данных . Сис тему можно разработать таким образом , что данные , удовлетвор я ющие “демонам” (ант ецеденты активированных правил ) не будут акти вировать дополнительные правила , что “заставит” систему при предстоящем прямом выводе скон центрироваться на правилах , учитывающих предыдущи й контекст. Разбор с началом в левом углу . Прим енив вышеописанный метод к парсингу , мы получим так называемый разбор с началом в левом углу . В терминах примера , прив еденного в разделе парсинг , система сначала рассмотрит “ they” , найдет правило 9 - единственн ое правило , которое можно применить к этом у слову, затем правило 3, объясняющее PRO, а затем правило 1, как единственное правило , сл едствие которого начинается с NP. Далее система попытается разобрать сверху вниз “ are flying planes” как VP. Заключение Обычно в системах искусственного интеллекта примен яет ся один из двух видов анализа . Первый - это анализ снизу вверх или прямой анализ , а второй - сверху вниз или обратный . Р азличие их определяется тем , в каком напра влении ведется поиск (от начала в конец или наоборот ) и какой элемент (следствие или антеце д ент ) активирует правила. Фактор эффективности и легкости внедрения может сыграть решающую роль при выборе вида анализа , который будет применяться в определенном приложении , но следует помнить , что использование смешанных стратегий также возможно. ПРИЛОЖЕНИ Е
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Мадам, ваши ручки - прекрасны, или я ничего не смыслю в канцелярии!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Анализ снизу вверх и сверху вниз", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru