Проектиране и анализ на компютърни алгоритми 2

(изборен курс към ФМИ, СУ, летен семестър 2003-04)

Тестове & проекти:

• Септемврийска сесия:
  Проекта трябва да се предаде на сайта до 0:00h в деня преди защитата.
  По време на защитата носете разпечатка на документацията.
     10 септември (петък), 09:00h, зала 306 (Аристотел)
• Резултати от юнска сесия.
• Студенти не предали проект няма да има оценка, дори и да имат точки за 3 ! ! !
• Проекти: тип A, тип B
  Разпределение на проектите (зададен проект може да се смени с изборен стига да се запази буквата - типа на проекта)
  Допустими езици C++ (MS Visual C++ 7.1, GNU C++ 3.3) и JAVA 1.4. Няма да се използват други компилатори по време на проверката!
  Форма за предаване на проекти.
  Шаблон за документация на проектите.
• Защита на проектите:
  Проекта трябва да се предаде на сайта до 0:00h в деня преди защитата.
  По време на защитата носете разпечатка на документацията.
     13 юни (неделя), 10:00h, зала 306 (Аристотел)
     10 юли (събота), 09:00h, зала 306 (Аристотел)

Учебни занятия:

• Понеделник - 17-19h, зала 325 - лекции
• Сряда - 17-19h, зала 325 - лекции
• Събота - 15-16h, зали 319/320 - практически упражнения

Преподавателски екип:

Кристиян Хараламбиев, е-mail:

Милослав Средков, е-mail:

Красимир Добрев, е-mail:

Анотация:

Курсът “Проектиране и анализ на компютърни алгоритми 2” е предназначен за студенти от всички курсове, специалности и специализации във ФМИ на СУ, които се интересуват от сложни компютърни алгоритми и техните приложения. Той е разделен на три основни части: сложни структури от данни (дървета, пирамиди и други), алгоритми за точно съчетаниe на низове (класическите алгоритми, суфиксни дървета и техни модификации) и алгоритми за неточно съчетание на низове (разстояние между низове, сходство, празнини и други). При разглеждане на алгоритмите се дава анализ на техните свойства, приложения, предимства и недостатъци. В курса се разглеждат теми за напреднали и се очаква студентите да имат основни познания по структури от данни и алгоритми.

Course Description:

The course “Design and Analysis of Computer Algorithms 2” aims to introduce advanced computer science algorithms and their applications to interested students from all courses and majors. The course material is divided in three main parts: advanced data structures (trees, heaps, etc.), exact matching algorithms (the classical algorithms, suffix trees and modifications), and inexact matching algorithms (distance between strings, similarity, gaps and others). We present algorithms and analyze their complexity, applications, advantages, and disadvantages.

Изисквания към студентите:

• Владеене на английски език – всички учебни материали са на английски език
• Добро познаване на материала преподаван в първата част на курса – воден по книгата "Програмиране = ++Алгоритми"

Изпити и оценки:

Крайната оценка се формира от един или два теста, както и курсов проект, направени по време на семестъра. Темите на курсовите проекти се задават от преподавателите в края на месец май. Курсовите проекти се разработват за домашно (вкъщи) за предварително определен срок от време. Курсовият проект и тестовете са задължителни.

Учебна програма:

• 1. (Сложни) структури от данни
  • 1.1. Двоични дървета. Подредени двоични дървета за претърсване - [1]: chapter 13
  • 1.2. Балансирани двоични дървета: червено-черни и AVL дървета - Red-Black([1]: chapter 14), AVL(линк 1, линк 2)
  • 1.3. Някои разширения на балансираните двоични дървета - [1]: chapter 15
  • 1.4. Splay дървета - линк
  • 1.5. Б-дървета - [1]: chapter 19
  • 1.6. Двоични пирамиди - [1]: chapter 7
  • 1.7. Биномни пирамиди - [1]: chapter 20
  • 1.8. Фибоначиеви пирамиди - [1]: chapter 21
  • 1.9. Структури от данни за представяне на разделени множества - [1]: chapter 22
  • 1.10. Други интересни структури от данни - Tiered Vector
• 2. Алгоритми за символни низове: точно съчетание, суфиксни дървета, приложения и модификации на суфиксните дървета
  • 2.1. Фундаментална предварителна обработка и първи алгоритми - [2]: chapters 1.1-1.5
  • 2.2. Класически методи чрез сравнение - [2]: chapters 2.1-2.4
  • 2.3. Задълбочен поглед върху класическите методи - [2]: chapters 3.3-3.5
  • 2.4. Получислено низово съчетание - [2]: chapters 4.1-4.4
  • 2.5. Суфиксни дървета - [2]: chapters 5.1, 5.2, 5.3, 5.4, 6.1, 6.4, 6.5
  • 2.6. Първи приложения и модификации на суфиксните дървета - [2]: chapters 7.1, 7.2, 7.4, 7.6, 7.8, 7.9, 7.13
  • 2.7. Ефективно намиране на най-близкия общ предшественик - [3]  (допълнителен материал - [2]: chapter 8 - не се включва на теста)
  • 2.8. Още приложения и модификации на суфиксните дървета - [2]: chapters 9.1, 9.2, 9.3, 9.4
• 3. Низови Алгоритми: неточно съчетание, налагане на последователности, динамично оптимиране
  • 3.1. Разстояние между два низа - [2]: chapters 11.2, 11.3, 11.4
  • 3.2. Претеглено разстояние между два низа - [2]: chapter 11.5
  • 3.3. Сходство на низове - [2]: chapter 11.6
  • 3.4. Локално налагане: намиране на поднизове с голяма сходство - [2]: chapter 11.7
  • 3.5. Празнини - [2]: chapter 11.8
  • 3.6. Намиране на налагане с линейна памет - [2]: chapter 12.1
  • 3.7. По-бързи алгоритми, когато броят на разликите е ограничен - [2]: chapter 12.2 -> 12.2.3, 12.2.4
  • 3.8. Методи чрез изключване: очаквано бързо изпълнение - [2]: chapter 12.3 -> 12.3.1, 12.3.3
  • 3.9. По-бърз (комбинаторен) алгоритъм за намиране най-дълга обща подпоследователност - [2]: chapter 12.5
  • 3.10. Техника на “четиримата руснаци” - [2]: chapter 12.7

Учебни материали:

Срещу всяка тема от курса преподадена до момента е означен съответния учебен материал. Повечето материали са от [1], [2] и [3] (виж "Литература" по-долу), които могат да се намерят в електронен вариант тук.

Литература:

• [1] Introduction to Algorithms (First Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
• [2] Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology by Dan Gusfield
• [3] The LCA Problem Revisited by Michael A. Bender and Martin Farach-Colton

Интересни линкове:

• Java Models - аплет демонстриращ двоични дървета за претърсване, балансиране и "splay"-ване
• InfoMan - информатически портал, списание и онлайн библиотека