У твърдил: …………………..
Декан
Дата .............................
СОФИЙСКИ УНИВЕРСИТЕТ “СВ. КЛИМЕНТ ОХРИДСКИ”
Специалност: (код и наименование)
Информатика
Магистърска програма: (код и наименование)
Компютърна лингвистика
УЧЕБНА ПРОГРАМА
Дисциплина: Приложения на крайните автомати
Преподавател: доц. д-р Стоян Михов
Асистент: ас. Стефан Герджиков
Учебна заетост
|
Форма
|
Хорариум
|
Аудиторна заетост
|
Лекции
|
45
|
Семинарни упражнения
|
30
|
Практически упражнения (хоспетиране)
|
0
|
Обща аудиторна заетост
|
75
|
Извънаудиторна заетост
|
Подготовка на домашни работи
|
0
|
Контролни работи и подготовка за тях
|
35
|
Учебен проект
|
85
|
Самостоятелна работа в библиотека или с интернет ресурси
|
0
|
Доклад/Презентация
|
0
|
Подготовка за изпит
|
45
|
|
|
|
|
|
|
|
Обща извънаудиторна заетост
|
165
|
ОБЩА ЗАЕТОСТ
|
240
|
Кредити аудиторна заетост
|
2.5
|
Кредити извънаудиторна заетост
|
5.5
|
ОБЩО ЕСТК
|
8
|
№
|
Формиране на оценката по дисциплината1
|
% от оценката
| -
|
Контролни работи
|
25
| -
|
Участие в час
|
0
| -
|
Домашни работи
|
0
| -
| Учебен проект |
50
| -
| Тестова проверка |
0
| -
| Текуша самостоятелна работа /контролно |
0
| -
|
Workshops {информационно търсене и колективно обсъждане на доклади и реферати)
|
0
| -
| |
| -
|
|
| -
| |
| -
| Изпит – практика (решаване на задачи) |
0
| -
| Изпит - теория |
25
|
Анотация на учебната дисциплина:
|
След кратък обзор на основните резултати в теорията на крайните автомати, курсът продължава с разглеждането на някои от най-разпространените приложения. Такива са задачата за търсене по шаблон (зададен чрез регулярен израз или множество от думи) в текст, задачата за представяне на краен речник и задачата за перфектен хеш. След това се въвежда теорията на моноидните автомати и регулярните релации. Показват се някои интересни техни свойства като липсата на затвореност относно сечение и начин за детерминизацията (на техен подклас) чрез секвенциални преобразуватели. Разглеждат се приложения на секвенциалните преобразуватели. Накрая се представя алгоритъма на Блумер и сие за построяване на минимален суфиксен автомат. Успоредно с теоретичния материал курсът цели реализацията на софтуерна библиотека за автомати и конкретно реализиране на дадени практически задачи с нея.
|
Предварителни изисквания: |
Предварителни знания, излизащи извън рамките на задължителните курсове от бакалавърските програми на ФМИ, не се предполагат. Предполага се успешно взет изпит по Езици, автомати и изчислимост или подобен курс.
|
Очаквани резултати:
|
Слушащите курса студенти да придобият практически умения и задълбочени познания в реализацията на ефективни алгоритми с помощта на крайни автомати
|
Учебно съдържание
№
|
Тема:
|
Хорариум
|
1
|
Крайни автомати и регулярни езици.
|
6л+2у
|
2
|
Построяване на краен автомат по регулярен израз. Алгоритми на Томсън и Бери-Сети
|
6л+4у
|
3
|
Търсене на поднизове в низ. Алгоритми на Ахо-Корасик и Кнут-Морис-Прат
|
3л+4у
|
4.
|
Минимален ацикличен автомат, разпознаващ даден краен език
|
6л+4у
|
5.
|
Моноидни автомати и техните свойства
|
6л+4у
|
6.
|
Перфектен хеш
|
3л+2у
|
7.
|
Представяне на двустранен речник чрез секвенционален преобразувател
|
3л+2у
|
8.
|
Представяне на презаписващ речник чрез секвенционален преобразувател
|
6л+2у
|
9.
|
Алгоритъм на Блумер и сие
|
6л+6у
|
Конспект за изпит
№
|
Въпрос
|
1
|
Крайни автомати и регулярни езици.
|
2
|
Построяване на краен автомат по регулярен израз. Алгоритми на Томпсън и Бери-Сети.
|
3
|
Търсене на подниз в низ. Алгоритми на Ахо-Корасик и Кнут-Морис-Прат.
|
4.
|
Минимален ацикличен автомат, разпознаващ даден краен език.
|
5.
|
Моноидни автомати.
|
6.
|
Перфектен хеш.
|
7.
|
Секвенциални преобразуватели.
|
8.
|
Представяне на двустранен речник чрез секвенционален преобразувател.
|
9.
|
Представяне на презаписващ речник чрез секвенционален преобразувател.
|
10.
|
Алгоритъм на Блумер и сие за построяване на минимален суфиксен автомат.
|
Библиография
Основна:
-
Stoyan Mihov, Direct Building of Minimal Automaton for Given List, Annuaire de l'Universite de Sofia ``St. Kl. Ohridski", Faculte de Mathematique et Informatique, volume 91, livre 1, pp. 33 -- 40, 1997.
-
Stoyan Mihov, Denis Maurel, Direct Construction of Minimal Acyclic Subsequential Transducers, Implementation and Application of Automata, S. Yu, A. Pun (Eds.), Lecture Notes in Computer Science 2088, Springer 2001, pp 217-229.
-
Stoyan Mihov, Klaus U. Schulz: Efficient dictionary-based Text rewriting using subsequential transducers. Natural Language Engineering, Volume 13, Issue 04, pp 353-381, December 2007.
-
Hristo Ganchev, Stoyan Mihov and Klaus U. Schulz: One-Letter Automata: How to Reduce k Tapes to One. in Firtz Hamm and Stephan Kepser (eds.). Logics for Linguistic Structures,. Trends in Linguistics 201, pp. 35-56, Mouton de Gruyter, 2008.
-
Anselm Blumer, J. Blumer, David Haussler, Andrzej Ehrenfeucht, M. T. Chen, Joel I. Seiferas: The Smallest Automaton Recognizing the Subwords of a Text. Theoretical Computer Science. Vlume 40, pp. 31-55 (1985)
Допълнителна:
-
A. Aho, R. Sethi, J. Ullman. Compilers, Principles, Techniques, and Tools. Addison-Westley, 1988.
-
J.E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation Second Edition. Addison-Wesley (2001).
-
Dan Gusfield: Algorithms on Strings, Trees and Sequences, Computer Science and Computational Biology, Cambridge University Press, 1997.
Дата: 10.12.2012 г. Съставил: Стоян Михов
Сподели с приятели: |
