ADS-проекти-2007
от Съзтезателно програмиране
ADS проекти - 2006-2007година
ОКОНЧАТЕЛНИТЕ ДАТИ ЗА ЗАЩИТА НА ПРОЕКТИТЕ СА 26.01 и 16.02 от 10:00 часа в 321 зала (голямата компютърна).
ВАЖНО: Ако четете тази страница без да сте прочели новина свързана с проектите в moodle, има вероятност да направите грешка. Първо прочетете в moodle. Ако още няма новина в moodle, значи четете твърде рано.
Разпределение на проектите: Ако сте записал(а) курса по ADS, можете да правите проект по ваш избор след заявка в новинарския форум в moodle и ако получите потвърждение. В случай, че не направите заявка до определено време, ще ви бъде разпределен проект.
Групова работа: Някои проекти изискват групова дейност, но това е само за определена в условието на проекта част и по останалата част трябва да се работи самостоятелно. По останалите проекти също трябва да се работи самостоятелно. В случай на нарушения при проектите, това ще бъде директно отнесено до деканата със съответните последствия за нарушителите.
Теми
Идеята на темите е, всеки студент да напише статийка някъде тук. По този начин:
- Студентите ще изследват по-задълбочено определен проблем.
- Ще се създаде ресурс за подговтовка за следващите издания на курса с по-добро качество от хвърчащи линкове...
Всеки студент избира една тема която прави в статия в уики формат. Не пишете статии на Word или нещо такова, тъй като после ще ви е много трудно да ги преобразувате. Пишете ги директно тук. В случаите когато не може да работите изцяло в интернет, ви препоръчвам да ги пишете на чист текст защото по-лесно ще оправите форматирането после.
Темите са по лекциите които са проведени, като една тема означава приблизително 1.5 лекционни часа.
Мисля, че е удачно да дефинираме следните изисквания:
- Една тема да бъде 10-15 килобайта текст, (без сорс кодовете приложени към нея ако има такива).
- Студентите могат да пишат тема която е свързана с проекта им за реализация, или пък такава която не е свързана. Разбира се по-лесно ще им бъде ако са свързани.
- Гледайте нещата да са добре разделени и лесни за четене. Ако имате формули ги пишете в tex формат.
- По-важно е да направите ресурс който да бъде полезен, и вашият принос да е приблизително колкото са изискванията. Ако искате да копирате и т.н. от други статии в уики-то правете го. Просто в този случай ще се гледа вашият принос а не цялата статия.
- Не се отплесвайте прекалено много в съдържание. По-добре е да напишете малко неща, но статията да е завършена, отколкото много неща които да не успеете да напишете.
- Сложете линкове към ресурсите които сте използвали, или други които мислите, че имат връзка и са полезни. Това е с особена полезност и е задължително.
Кратък преговор на абстрактните типове данни и основните такива.
- Абстрактни типове:
- Стек, опашка, приоритетна опашка, списък, дек.
- Set, Multiset, Map, Multimap.
- Графи и дървета.
- Итератори.
- Проектиране на АДТ.
Дадохме примери за различни видове реализации, примерни сложности за операциите при тях.
Три метода за амортизиран анализ
- the aggregate method
- the accounting method
- the potential method
Представяния на графи и дървета
- Графи:
- Видове графи
- Представяния. Сложности на операции и памет при всяко:
- матрица на съседство
- списък на съседство
- списък от ребрата
- set от ребра
- map <ребро->тегло>
- Дървета:
- Видове дървета
- Представяния. Сложности на операции и памет при всяко:
- като граф
- списък на родителите
- списък на наследниците
- ляв син - десен брат
Tiered Vector
- Добавяне на елемент и извършване на "разширяване на вектора".
- Изтриване на елемент и извършване на "свиване на вектора".
- Намиране на k-тия по големина елемент във вектора.
Skip List
Беше разгледана структурата Skip List.
- Skip List, в който всеки втори елемент е с височина 2.
- Skip List, в който елементите са с височини максималната степен на двойката която дели индексите им, но е затруднено добавянето и изтриването на елементи.
- Skip List, в който произволно се избират височините на новите елементи и очакваната сложност на операциите е O(logn).
- Това беше 3 часа така ли? --Milo 12:33, 5 яну 2007 (EET)
- До колкото помня тогава ти и Антон водихте и той води 2 часа и малко, а ти после ми каза, че си говорил общи приказки за хешове, така че може и за 1.5 часа да мине май --Gogov 15:03, 6 яну 2007 (EET)
Хеш функции
- Дефиниции, свойства, видове.
- Приложения:
- Реализация на Map и Set
- Криптография
- Integrity
- Идентификация
- Индексиране
- Стрингове
Хеш структури
- Хеш таблици
- Bloom filter
- Distributed Hash Table
АVL Дървета
- Height-Balanced Trees
- Добавяне в AVL дърво
- Изтриване от AVL дърво
- Търсене в AVL дърво
Splay Дървета
- Предимства и недостатъци
- Операцията Splay
- Добавяне в Splay дърво
- Изтриване от Splay дърво
- Търсене в Splay дърво
Червено-черни Дървета
- Дефиниция на червено черно дърво
- Свойства на червено-черните дървета
- Свойства на оцветеността
- Доказателство на максималната дълбочина на дървото
- Операции над червено-черни дървета
- Търсене на елемент
- Вмъкване
- Изтриване
Б-Дървета
- Дефиниция на Б-дърво
- Приложение на Б-дърветата
- Операции над Б-дървета
- Търсене
- Вмъкване
- Изтриване
RMQ
Беше представена темата за проблема Range Minimum Query (RMQ). Споменати бяха два алгоритъма за решаване на задачата. Можете да прочетете материали свързани с темата
- Това някак да го разделим на 2? --Milo 12:43, 5 яну 2007 (EET)
Непресичащи се множества
- Oперации:
- MakeSet(x) - Union(x,y) - FindSet(x)
- Приложения:
- Намиране на свързаните компоненти в граф - Построяване на минимално обхващащо дърво чрез алгоритъм на Крускал
- Реализации:
- Чрез свързан списък:
- Weighted union евристика
- Сложности на операциите
- Псевдокод на операциите
- Чрез Disjoint Set Forest:
- Union by rank евристика
- Path compression евристика
- Сложности на операциите
- Псевдокод на операциите
Dynamic Ordered Statistics
- Дефиниция - Реализация чрез модифициране на RB tree:
- Сложности на операциите - Псевдокод на операциите
- Индексно дърво
- Видове операции - Сложности на операциите - Псевдокод на операциите - Сложност по памет
- Реализация на DOS чрез индексно дърво
Trie
- Дефиниции, свойства, операции.
- Приложение на структурата Trie в алгоритъма на Aho-Corasick
Компресиране на Trie, Patricia trie
- Същност
- Недостатъци на trie
- Компресиране
- Операции в Patricia trie
- Търсене
- Добавяне
- Изтриване
- Сложности
- Сравнение с други структури от данни
- Реализация
- Приложения
Suffix Tree
Дефиниция, свойства, приложения. Suffix Tree
Suffix Array
част 1 (default)
Дефиниция, свойства, приложения, конструиране.
част 2
Линейно смятане на LCP по построен Suffix Array. Търсене на подстринг в текста чрез търсене в Suffix Array-а, оптимизация на търсенето с използване на LCP.
Двоична пирамида
- Дефиниция на ефективните операции на структурата "пирамида"
- Пример как може да се ползва пирамида за забързване на алгоритъма на Дийкстра за намиране на най-кратко разстояние от даден връх до всички останали
- Дефиниция на пирамидална нареденост на дърво
- Дефиниция на двоична пирамида
- Операции с биномна пирамида
- Вмъкване в двоична пирамида
- Изтриване на най-малкият елемент от двоична пирамида
- Вземане на най-малкият елемент в двоична пирамида
- Намаляне на даден елемент в двоична пирамида
- Сливане на двоични пирамиди
- Имплементация на двоична пирамида с масив
Биномна пирамида
- Дефиниция на биномно дърво
- Дефиниция на биномна пирамида
- Свойства на биномната пирамида
- Операции върху биномна пирамида
- Намиране на най-малкият елемент в пирамидата
- Сливане на две пирамиди
- Изтриване на най-малкият елемент
- Вмъкване на елемент
- Намаляне на даден елемент
- Изтриване на даден елемент
- Сравнение на сложностите между двоична и биномна пирамиди
Фибоначиева пирамида
- История
- Сложности
- Структура на пирамидата
- Реализиране на операциите
- Намиране на най-малкият елемент в пирамидата
- Сливане на две пирамиди
- Вмъкване на елемент
- Изтриване на най-малкият елемент
- Намаляне на даден елемент
- Изтриване на даден елемент
- Емпирични резултати
Реализации
Проекти 1 и 2. Двоични дървета
Да се реализират описаните балансирани дървета. Всяка от реализациите, трябва да брои върховете на дървото, през които се преминава за изтривания и за добавяния. Също така трябва да се броят ротациите.
Групова част
Да се напише тестващ код и големи по размер тестове (може и като външни файлове, четени от тестващия код), за които различните дървета да показват различни показатели - например за даден тест RedBlack-tree извършва повече ротации, но да се построи и друг тест, при който AVL да извършва повече ротации. Тестовете са част от оценката, не ги пропускайте.
Препоръки: Изберете хранилище на проекта. Може да трябва да си обменяте сорса от време на време (openfmi.net ?). По възможност уточнете интерфейсът в началото. Напишете кратък тестващ код с прости тестове и може да напишете и проста имплементация на интерфейсът (т.е. да направите интерфейс с действията на структурите данни преди да сте започнали да ги пишете)
Проект 1
Да се реализира AVL дърво, което да поддържа операции добавяне и изтриване.
Проект 2
Да се реализира Red-Black дърво, което да поддържа операции добавяне и изтриване. Да се реализира Splay дърво, което да поддържа операции добавяне и изтриване.
Проекти 3 и 4. Heap-ове
Да се реализира алгоритъм на Dijkstra с помощтта на heap.
Групова част
Да се реализира алгоритъм на Dijkstra. Да се напише тестващ код и тестове (може и като външни файлове, четени от тестващия код), за които dijkstra да работи по-добре с heap и тестове, при които работи по-добре без heap.
Препоръки: Изберете хранилище на проекта. Може да трябва да си обменяте сорса от време на време (openfmi.net ?). По възможност уточнете интерфейсът в началото. Напишете кратък тестващ код с прости тестове и може да напишете и проста имплементация на интерфейсът (т.е. да направите интерфейс с действията на структурите данни преди да сте започнали да ги пишете)
Проект 3
да се реализира биномен heap
Проект 4
да се реализира фибоначиев heap
Проект 5. SMS (Web) игра
Да се реализира игра за SMS "търг", при който участници изращат цена в брой стотинки, за които искат да закупят дадена стока. Стоката се продава за най-ниската цена, която е предложна само от 1 участник.
Програмата трябва да може да отговаря на 2 вида заявки: 1.ново предложение за цена 2.текущата цена, за която би се продала стоката. Заявките може да се срещат в произволен ред.
Да се реализира B дърво или разновидност на B дърво за съхранение на данните на диска. Програмата трябва да съхранява всичко във файлове, да може да се терминира по всяко време и след това да се стартира и да продължи от предишното състояние. Може да реализирате програмата като cgi приложение на debian.fmi.uni-sofia.bg, приемащо заявки през web интерфейс. За повече информация ми пишете. Vesu 16:49, 28 дек 2006 (EET)
Проект 6. Dynamic Ordered Statistics върху Trie
Да се реализира структура данни, която позволява следните действия:
1. Добавяне на елемент със стойност N.
2. Изтриване на елемент със стойност N.
3. Преброяване на елементите в интервал [N, M].
N и M са естествени числа, събиращи се в 32-битов integer. Структурата данни трябва да се реализира като trie, в което string-овете са двоичното представяне на N (допълнено до 32 знака с нули отпред). На това trie му добавете dynamic ordered statistics за да решите задачата. Тествайте с тестове с голям размер (поне няколко десетки милиона операции и наличие на всички видове операции). Тестването също се оценява.
Проект 7. Aho Corasick
Да се реализира програма, която търси всички срещания на string A в string B. За срещане ще считаме ако като substring на B се намери точно string A или string, който е близък до A. Два string-а са близки ако има точно 1 от следните разлики:
1. Една липсваща буква
2. Една променена буква
3. Една буква в повече
За целта да се построи Trie подобно на това в алгоритъма на Aho Corasick от всички близки string-ове близки до A. След това с това множество да се търси в B.
За улеснение string-овете се състоят само от малки латински букви.
Пример:
abba и babami
abba се среща веднъж в babami приблизително като aba
Проект 8. Rabin-Karp (хештаблици)
Да се реализира програма, която намира всички срещания на string A или друг string подобен на A с най-много две сменени букви в string B.
Пример:
A=mobil, B=lozetoneshtemolitvaamotika
подобен на A string в B се среща на следните позиции:
mobil lozetoneshtemolitvaamotika
mobil lozetoneshtemolitvaamotika
За целта да се използва алгоритъм на Rabin-Karp, който търси наведнъж множеството от подобни на A string-ове в B.
Да се съставят големи по размер тестове и да се сравнят времената на тях при използване на поне два вида хеш функции и поне 3 различни размера на хештаблицата. Да се подготви обяснение на наблюдаваните резултати.
Проект 9. PATRICIA
Даден е списък с файлове в една директория. Съставете структура данни от имената на файлове, която отговаря на следните заявка: по wildcard pattern, намира файловете, които match-ват с wildcard pattern-а (за тестване, намерете само техния брой - т.к. няма да имплементирате цяла файлова система). За целта поставете файловете в PATRICIA и извършвайте търсенията чрез обхождане на дървото.
wildcard pattern е дума, която съдържа букви, цифри, _, . и два специални символа * и ?. * match-ва с произволен string включително и празен string, ? match-ва с произволен единствен знак. Например babami123 match-ва с wildcard pattern-а b?ba*123. Но също така match-ва и с wildcard pattern-а *123 или с babami123*
Пример:
файлове:
file1 file2 file13 otherthing
заявки със съответни отговори:
file* 3 files match *i* 4 files match file? 2 files match
Съставете тестове за вярност както и големи по размер тестове, с които да тествате за време.
Проект 10. Skip List
Да се напише реализация на Skip List със сложност на операциите O(logN). Да се направят тестове, при които в структурата се съдържат различен брой елементи, за да се изпробрва въздействието на избраната максимална височина на елементите в Skip List-а. Броят на избраните тестове да бъде минимум 3. За всеки да се изпробва със смятаната за оптимална височина, както и с други две, едната от които е по-малка, а другата по-голяма.
Проект 11. Tiered Vector
Да се напише реализация на Tiered Vector със сложност на операциите O(sqrt(N)). Трябва да бъдат подготвени тестови премери, с които да се демонстрира работата на структурата. Тестовете трябва да са поне 5 на брой. С тях трябва да се демонстрира скоростта на работа при различни операции със структурата. Например трябва да има тест, при който главно се извършва операция вмъкване и изтриване на елемент, друг с операция запитване. Хубаво е да има и тестове, в които различните операции са приблизително по-равен брой. По този начин емпирично ще могат да се изследват константите при различните операции и да се провери скоростта на структурата за различни видове ситуации.
Проект 12. LCA/RMQ
Да се реализира Range Minimum Query като сложността на първата част е О(N), а отговарянето на заявки е с O(1). Реализирайте и алгоритъма със сложност на първата част O(NlogN). Направете тестове, с които да се провери разликата в скоростите на двата подхода. Можете да използвате информацията от тази статия за RMQ.
Проект 13. Suffix Array
Да се реализира конструиране на Suffix Array, както и някои основни операции в него (примерно търсене).
- А дали да се строи и LCP?
Проект 14. Suffix Tree
Да се реализира конструиране на Suffix Tree, както и някои основни операции в него (примерно търсене).
Проект 15. Index Tree
Да се имплементира DOS чрез индексно дърво с памет <math>\Theta(N)</math> (а не <math>\Theta(2 * N)</math>). Да се реализират основните операции за индексното дърво, както и основните операции за DOS. Да се измисли и реши практическа задача, в която се използва готовата структура.
Проект 16. Disjoint Sets
Да се имплементират две структури за представяне на непресичащи се множества:
- чрез свързан списък, като се използва евристиката weighted union - чрез гора от дървета, като се използват евристиките path compression и union-by-rank
Чрез готовите структури да се реализира алгоритъма на Крускал за построяване на минимално покриващо дърво. Да се сравни поведението на двете структури (по сложност на операциите и сложност на паметта) върху достатъчно големи тестове.
Research Проект 1
Да се реализира структурата данни Scapegoat tree. За да правите такъв проект, трябва да получите съгласие от някои правещи проекти 1 и 2. Трябва да включите вашите резултати върху тестовете (можете да се включите в правенето на тестове) към техните. Сравнете за няколко стойности на <math>\alpha</math>. При нужда от статия, която не се разпространява свободно се свържете с мен. Vesu 17:02, 28 дек 2006 (EET).
Research Проект 2
Да се реализира 2-3 heap. Ако е възможно го вградете в Dijkstra с хора, работещи по проекти 3 и 4. Пригответе се да обяснявате структурата данни на недоумяващи преподаватели.
