У твърдил: …………………..
Декан
Дата .............................
СОФИЙСКИ УНИВЕРСИТЕТ “СВ. КЛИМЕНТ ОХРИДСКИ”
Специалност: (код и наименование)
Информатика
Магистърска програма: (код и наименование)
Компютърна лингвистика УЧЕБНА ПРОГРАМА Дисциплина: Бързи алгоритми върху структури от данни Преподавател: гл. ас. д-р Петър Митанкин, ас. Стефан Герджиков Асистент:
Учебна заетост
|
Форма
|
Хорариум
|
Аудиторна заетост
|
Лекции
|
30
|
Семинарни упражнения
|
30
|
Практически упражнения (хоспетиране)
|
0
|
Обща аудиторна заетост
|
60
|
Извънаудиторна заетост
|
Подготовка на домашни работи
|
0
|
Контролни работи и подготовка за тях
|
30
|
Учебен проект
|
30
|
Самостоятелна работа в библиотека или с интернет ресурси
|
30
|
Доклад/Презентация
|
0
|
Подготовка за изпит
|
30
|
|
|
|
|
|
Обща извънаудиторна заетост
|
120
|
ОБЩА ЗАЕТОСТ
|
180
|
Кредити аудиторна заетост
|
3
|
Кредити извънаудиторна заетост
|
3
|
ОБЩО ЕСТК
|
6
|
№
|
Формиране на оценката по дисциплината1
|
% от оценката
| -
|
Контролни работи
|
25
| -
|
Участие в час
|
0
| -
|
Домашни работи
|
0
| -
| Учебен проект |
25
| -
| Тестова проверка |
0
| -
| Текуша самостоятелна работа /контролно |
0
| -
|
Workshops {информационно търсене и колективно обсъждане на доклади и реферати)
|
0
| -
| |
| -
|
|
| -
| |
| -
| Изпит – практика (решаване на задачи) |
0
| -
| Изпит - теория |
50
|
Анотация на учебната дисциплина:
|
|
Предварителни изисквания: |
В курса ще се разглеждат варианти на следния общ проблем – за търсене в структура от данни. По дадена структура от елементи D, да се намери елемент на D, който притежава определено свойство P. Целта на курса е да се представи букет от разнообразни техники, които позволяват създаването на ефективни алгоритми за решаването на такъв тип проблеми, като постигат компромис между време и памет. Слушателят на курса ще има възможност да се запознае с техниката на „четиримата руснаци” в нейни различни варианти, въведената от Tarjan концепция за тежки пътища в дървета, приложения в нетипични ситуации на приома „разделяй и владей”.
Курсът започва с обзор на основни резултати върху структурата хеш заедно със свойствата търсене по ключ и най-близък по ключ. След което се разглеждат дървета заедно със свойствата най-близък маркиран предшественик, предшественик от определена дълбочина и най-близък общ предшественик. Курсът продължава със структурата речник за крайно множество от думи и свойството съдържа като поддума. Ще бъдат изучени алгоритми за решаването на съответните проблеми, които освен че илюстрират основните техники, постигат оптимална или близка до оптималната времева сложност, като използват памет, която е линейна относно размера на данните. Курсът ще завърши с представянето на алгоритъма на Myers за приближено търсене на подниз в низ и ще се докажат оценки за неговите сублинейна очаквана времева сложност O(DNpow()log N + Hits) и линейна памет O(N).
Въпреки че курсът е концентриран основно върху проблема за търсене в структура от данни, ще се разгледа и обща постановка, въведена от Bentley и развита от Overmars, Leeuwen и Mehlhorn, която позволява разширяването на структурата от данни с операции за вмъкване и триене, като при това операцията за търсене се влошава с фактор от логаритъм.
|
Очаквани резултати:
|
Слушащите курса студенти да придобият задълбочени познания.
|
Учебно съдържание
№
|
Тема:
|
Хорариум
|
1
|
Хеш. Оптимален хеш. Сложност.
|
2+3
|
2
|
Алгоритъм на Willard.
|
2+2
|
3
|
Оптимални алгоритми за предшественици в дървета.
|
8+9
|
4.
|
Суфиксни структури. Оптимални алгоритми за конструиране.
|
8+9
|
5.
|
Разширяване на структури от данни за търсене с операции за вмъкване и триене.
|
4+4
|
6.
|
Приближено търсене. Алгоритъм на Myers.
|
6+3
|
Конспект за изпит
№
|
Въпрос
|
1
|
Хеш. Оптимален хеш. Сложност.
|
2
|
Алгоритъм на Willard.
|
3.
|
Намиране на най-близък маркиран предшественик.
|
4.
|
Намиране на k-ти предшественик.
|
5.
|
Намиране на най-близък общ предшественик. Намиране на минимален елемент в отрез.
|
6.
|
Насочен ацикличен граф за дума. Алгоритъм на Blumer-Blumer-Haussler-Ehrenfeucht-Chen-Seiferas.
|
7.
|
Суфиксно дърво. Алгоритъм на Ukkonen.
|
8.
|
Суфиксен масив.
|
9.
|
Разширяване на структури от данни за търсене с операции за вмъкване и триене.
|
10.
|
Приближено търсене. Алгоритъм на Myers.
|
Библиография
Основна:
-
Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, Introduction to Algorithms, 2009, 3rd edition, The MIT Press
-
Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, 1997, Cambridge University Press
-
Michael A. Bender, Martin Farach-Colton, The level ancestor problem simplified, Theoretical Computer Science, 2004, 321(1), 5-12
-
Michael A. Bender, Martin Farach-Colton, The LCA Problem Revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, 2000, 88-94
-
Eugene W. Myers, A Sublinear Algorithm for Approximate Keyword Searching, Algorithmica, 1994, 12(4/5), 345-374
-
Dan E. Willard, Log-logarithmic worst case range queries are possible in space O(N). Information Processing Letters, 1983, 17(2):81-84.
-
Stephen Alstrup, Thore Husfeldt, Theis Rauhe, Marked Ancestor Problems, IEEE Symposium on Foundations of Computer Science, 1998, 534-544.
-
Mark Overmars, Jan van Leeuwen, Dynamization of decomposable searching problems yielding good worst-case bounds. Theoretical Computer Science, 1981, 104, 224-233.
-
Kurt Mehlhorn, Data Structures and Algorithms, Springer Verlag, EATCS Monographs, 1984.
Допълнителна:
Дата: 10.01.2013 г. Съставили: Петър Митанкин и Стефан Герджиков
Сподели с приятели: |
