Курсовая работа: Оптимизация алгоритмов синтаксического анализа, основанных на матричных операциях
Описание
Оглавление
3
Введение
Теория формальных языков активно изучается и находит широ-кое применение во многих областях, прежде всего, для формализации языков программирования и естественных языков. Также существует множество исследований, которые показывают эффективность исполь-зования формальных языков в биоинформатике для решения задач распознавания и классификации, некоторые из которых основаны на том, что вторичная структура геномных последовательностей содер-жит в себе важную информацию об организме. Характерные особенно-сти вторичной структуры могут быть описаны с помощью некоторой контекстно-свободной (КС) грамматики, что позволяет свести пробле-му распознавания и классификации к задаче синтаксического анализа (определения принадлежности некоторой строки к языку, заданному грамматикой) [4, 9, 14]. Часто необходимо не просто проверить выво-димость конкретной строки, но и найти все подстроки, принадлежащие некоторому формальному языку [3].
Большинство подходов к анализу биологических цепочек, которые основаны на синтаксическом анализе, сталкиваются проблемой низкой производительности. Чаще всего в этих подходах применяется алго-ритм CYK [8, 16], который работает за кубическое время и неэффекти-вен на длинных строках
| Введение | 4 | ||
| 1. | Постановка задачи | 6 | |
| 2. | Обзор | 7 | |
| 2.1. | Терминология ......................... | 7 | |
| 2.2. | АлгоритмВалианта...................... | 7 | |
| 2.3. | АлгоритмЯвейн........................ | 9 | |
| 2.4. | Применение в биоинформатике и задача поиска подстрок | 12 | |
- Доказательство корректности и оценка сложности алгоритма
| Явейн | 13 |
- Анализ эффективности применения к задаче поиска подстрок
| алгоритмов Валианта и Явейн | 18 | ||
| 5. | Реализация алгоритмов Валианта и Явейн | 20 | |
| 5.1. | Последовательнаяверсия. . . . . . . . . . . . . . . . . . . | 20 | |
| 5.2. | Параллельнаяверсия..................... | 20 | |
| 6. | Эксперименты | 21 | |
| 6.1. | Сранительныйанализ..................... | 23 | |
| 6.2. | Применимость к задаче поиска подстрок . . . . . . . . . | 24 | |
| 7. | Заключение | 26 | |
| Список литературы | 27 | ||
3
Введение
Теория формальных языков активно изучается и находит широ-кое применение во многих областях, прежде всего, для формализации языков программирования и естественных языков. Также существует множество исследований, которые показывают эффективность исполь-зования формальных языков в биоинформатике для решения задач распознавания и классификации, некоторые из которых основаны на том, что вторичная структура геномных последовательностей содер-жит в себе важную информацию об организме. Характерные особенно-сти вторичной структуры могут быть описаны с помощью некоторой контекстно-свободной (КС) грамматики, что позволяет свести пробле-му распознавания и классификации к задаче синтаксического анализа (определения принадлежности некоторой строки к языку, заданному грамматикой) [4, 9, 14]. Часто необходимо не просто проверить выво-димость конкретной строки, но и найти все подстроки, принадлежащие некоторому формальному языку [3].
Большинство подходов к анализу биологических цепочек, которые основаны на синтаксическом анализе, сталкиваются проблемой низкой производительности. Чаще всего в этих подходах применяется алго-ритм CYK [8, 16], который работает за кубическое время и неэффекти-вен на длинных строках
Характеристики курсовой работы
Учебное заведение
МГУ им. ЛомоносоваСеместр
Просмотров
1
Размер
394 Kb
Список файлов
Оптимизация алгоритмов синтаксического анализа, основанных на матричных операциях.doc
Tortuga
18 июля 2024 в 09:07
Комментарии
Нет комментариев
Стань первым, кто что-нибудь напишет!
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
