Кук-Јангер-Касами алгоритам — разлика између измена
Садржај обрисан Садржај додат
м Bot: Migrating 17 interwiki links, now provided by Wikidata on d:q954821 (translate me) |
м разне исправке; козметичке измене |
||
Ред 8:
-{CYK}- алгоритам спада у ефикасније алгоритме синтаксичке анализе који имају широку применљивост.
Сложеност алгоритма је полиномска и спада у класу ''-{O(n<sup>3</sup>)}-''(због три угнежђене петље), где је -{n}- дужина анализиране ниске. Наравно, постоје и методе линеарне сложености, али су оне применљиве само на неке поткласе КСГ. Алгоритам припада [[парадигма|парадигми]] [[динамичко програмирање|динамичког програмирања]].
== Алгоритам ==
Ред 39:
==Модификације алгоритма и примене==
* Ради конструкције [[Дрво извођења|дрвета извођења]],-{CYK}- алгоритам се може модификовати тако да елементи матрице -{P}- не буду логичке вредности него чворови дрвета извођења. Како граматика може бити вишезначна, неопходно је памтити у матрици заправо листу чворова, а резултат ће бити не само једно дрво, већ читав низ могућих стабала.▼
* Теоретски значај -{CYK}- алгоритма лежи у могућности да се користи као конструктиван доказ да је проблем припадности КСЈ одлучив.▼
▲*Ради конструкције [[Дрво извођења|дрвета извођења]],-{CYK}- алгоритам се може модификовати тако да елементи матрице -{P}- не буду логичке вредности него чворови дрвета извођења. Како граматика може бити вишезначна, неопходно је памтити у матрици заправо листу чворова, а резултат ће бити не само једно дрво, већ читав низ могућих стабала.
* Ради синтаксичке анализе стохастичких КСГ(СКСГ), -{CYK}- алгоритам се може модификовати тако да елементи матрице -{P}- не буду логичке вредности, већ вероватноће. СКСГ су КСГ у којима се свака примена правила обавља уз неку вероватноћу; тачније, вероватноћа извођења је производ вероватноћа правила која се користе у тим извођењима. СКСГ се користе у области -{NLP}- (обрада природних језика) и проучавања -{[[RNK]]}- молекула у [[биоинформатика|биоинформатици]].▼
▲*Теоретски значај -{CYK}- алгоритма лежи у могућности да се користи као конструктиван доказ да је проблем припадности КСЈ одлучив.
▲*Ради синтаксичке анализе стохастичких КСГ(СКСГ), -{CYK}- алгоритам се може модификовати тако да елементи матрице -{P}- не буду логичке вредности, већ вероватноће. СКСГ су КСГ у којима се свака примена правила обавља уз неку вероватноћу; тачније, вероватноћа извођења је производ вероватноћа правила која се користе у тим извођењима. СКСГ се користе у области -{NLP}- (обрада природних језика) и проучавања -{[[RNK]]}- молекула у [[биоинформатика|биоинформатици]].
== Литература ==
Линија 51 ⟶ 50:
== Спољашње везе ==
* [http://www.matf.bg.ac.rs/~jelenagr/ASP/v22.htm -{CYK}- алгоритам], простор Јелене Грмуше, МатФ
== Види још ==
* [[Ерлијев анализатор|Ерлијев алгоритам]]
[[Категорија:Алгоритми]]
| |||