Українські рефератиучбові матеріали на українській мові

RefBaza.com.ua пропонує студентам та абітурієнтам найбільшу базу з рефератів! Також ви можете ділитися своїми рефератами для поповнення бази.

Аналіз знизу вгору й за згори донизу

Реферат: Аналіз знизу вгору й за згори донизу

“Згори донизу” vs. “знизу вгору”, “прямий” vs. “зворотний”, “керований даними” vs. “спонукуваний метою” - три пари визначень для таких термінів, як “ланцюгової аналіз”, “парсинг”, “синтаксичний розбір”, “логічний аналіз” і “пошук”. У принципі так, всі ці терміни відбивають подібні відносини, і розбіжності з-поміж них лише у цьому, що вони взяті з різних подобластей комп'ютерна наука і штучного інтелекту (парсинг, системи з закладені у них правилами, пошукові системи та системи, створені задля розв'язання проблеми тощо.)

Суть цих протиставлень можна проілюструвати з прикладу парадигми пошуку. Основне завдання будь-якого пошуку у тому, щоб визначити маршрут, яким ви переміщатися зі справжньою позиції до вашої мети. Якщо ви і почнете пошук із поточною позиції і продовжуватимете його, доки наткнетеся на бажаного результату, - це званий прямий пошук чи пошук знизу вгору. Якщо ви хоч подумки ставите себе у те місце, де ви бажаєте опинитись у результаті пошуку істини та визначаєте маршрут, рухаючись у напрямі, тобто. туди, де справді перебуваєте у сьогодні, - це пошук у напрямі чи пошук згори донизу. Зверніть увагу, що, визначивши маршрут внаслідок зворотного пошуку, вам все-таки доведеться дістатись своєї мети. Попри те що, що зараз рухаєтеся вперед, не є прямим пошуком, т.к. пошук вже було здійснено раніше, причому у напрямку.

Ці самі протиставлення можна розгледіти з прикладу систем із вбудованими правилами. Уявімо, що правило складається з набору антецедентов і набору наслідків. Коли система визначає, що це антецеденты певного правила задоволені, цього правила викликається і виконується (виконується чи кожне викликане правило залежить від специфіки конкретної системи). Після цього, у базу знань заносяться затвердження, отримані у виконання правила, і виконуються відповідні операції. Цей процес відбувається вищеописаним чином, незалежно від цього, застосовує чи система прямій чи зворотний логічний аналіз. Щоб проілюструвати різницю між ними, слід окремо розглянути процедуру активації правила. Вызываются лише активовані правила. При прямому логічному аналізі (знизу вгору), як у систему додаються нові дані, вони порівнюються з усіма антецедентами всіх правил. Якщо є відповідають антецеденту правила, це правило активується (коли вона ще є активованим), і якщо підібрані все антецеденты певного правила, воно викликається. Твердження, отримані у виконання правила, заносять у базу знань і розглядаються як нових даних, порівнюються з антецедентами і може викликати активацію і виклик додаткових правил. При зворотному логічному аналізі (згори донизу) при додаванні даних правила не активуються. Коли система отримує запит, він порівнюється з усіма наслідками всіх правил. Якщо запит збігається з наслідком, це правило активується, проте його антецеденты розглядаються як вторинних запитів і може викликати активацію додаткових правил. Коли запит відповідає не обмеженому умовою утвердженню бази знань, нею надходить відповідь, і коли цей запит виходив від антецедента, вважається, що він задовольняє останньому. Коли всі антецеденты деякого правила задовольняться, правило викликається і виконується. За виконання правила здійснюється у відповідь запити, що його активували, і тепер інші антецеденты вважаються задоволеними і може викликатися відповідні їм правила. Зверніть увагу, що виклик і виконання правила завжди відбувається у прямий послідовності, а відмінність прямого ланцюгового аналізу протилежного у тому, коли активується правило.

Приклади

Парсинг. Спробуємо проілюструвати і пояснити відмінність між синтаксичним аналізом згори донизу і знизу вгору з прикладу пропозиції “They are flying planes” та простий граматики, представленої у вигляді пронумерованих правил:

1. P.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), ця послідовність є пропозицією (P.S).”

Синтаксический розбір згори донизу починається з символу P.S, що й буде вершиною дерева розбору. Цю процедуру еквівалентна процедурі постановки завдання, що полягає у тому, щоб визначити, чи є послідовність слів пропозицією. Правило 1 говорить, що кожен пропозицію складається з іменний групи (NP), яку слід глагольная група (VP). За наявності кількох правил, спочатку застосовується правило з найменшою номером, та був воно розширюється зліва-направо. Отже наступним кроком є перебування першої зв'язку, тобто. NP. Спочатку активується правило 2, та був правило 8 (рис. 2а). Т.к. “planes” відповідає ”they”, алгоритм спрацьовує знову, і тепер спочатку активується правило 3, та був правило 9. Потім алгоритм повертається до правилу 1 і такий метою ставить визначення VP. Спочатку активуються правила 5, 6, та був 12 (рис. 2b). Подальший хід розбору отржен малюнку 2 (з, d, e).

Синтаксический розбір знизу вгору починається зі слів у пропозиції. Знову-таки розбір ведеться зліва-направо, і спочатку застосовується правило з найменшою номером. Отже, спочатку перше слово пропозиції “they” співвідноситься з антецедентом правила 9, яке після виконання видає твердження, що “they” є займенником (PRO). Потім виконується правило 3 видає, що “they” є NP. NP відповідає антецедентам правил 1 і п'яти, але й одна з цих правил ще викликано, тому розбір переходить до “are”. Виконується правило 11 (як і раніше, що правило 12 також викликано, він виконується відповідно до правилом про послідовності виконання правил). Потім виконуються правила 10, 8 і 2 (рис. За). На даної стадії подальший розбір послідовності NP+AUX+ADJ+NP неможливий, тому ми повертаємося до останнього викликаного, але ще виконаного правилу, тобто. до правилу 4. Розбір послідовності NP+AUX+NP як і неможливий, тому знову виконується останнє викликане невиконану правило. Нині це правило 13, яке видає, що “flying” є V. Потім виконуються правила 6 і п'яти (рис. 3с). Розбір последователльности NP+AUX+VP неможливий, тому виконується правило 7 видає твердження, що “are flying” є VT. Потім знову виконуються правила 5 і одну, тоді і закінчується синтаксичний розбір (рис. 3d).

Цей приклад було наведено із єдиною метою порівняння механізмів синтаксичного розбору знизу вгору й за згори донизу. Встановлення суворого порядку розбору зліва праворуч і нумерація правил зумовлені намаганням до застосування найбільше подібного алгоритму, як і раніше, що результати розбору виявилися різними.

Системи з умонтованими правилами. Розглянемо прямий і зворотний ланцюгової аналіз з прикладу вигаданого набору правил у тому, як слід провести вечір. Правила перебувають у звичайному порядку, антецедент розташовується зліва, а слідство - справа, все викликані правила виконуються, а розбір ведеться паралельно.

1. Хороший фільм на ТБ + Раннього ранку зустрічей немає ® Пізніше кіно

2. Раннього ранку зустрічей немає + Потрібно попрацювати ® Робота допізна

3. Потрібно попрацювати + Необхідні документи ® Праця у офісі

4. Пізніше кіно ® Не спати допізна

5. Робота допізна ® Не спати допізна

6. Робота допізна ® Повернення до офісу

7. Праця у офісі ® Повернення до офісу

Наприклад, правило 1 говорить, що й на ТБ йде хороше кіно України й в мене завтра рано-вранці зустрічей немає, тоді вже іду режиму “Пізніше кіно”.


Схожі реферати

Статистика

[1] 2