Алгоритми и структуре података

Циљ и исход предмета

Упознавање са логичком организацијом и меморијском репрезентацијом линеарних и нелинеарих структура података, основним операцијама и типичним применама ових структура. Студенти су оспосебљени за за програмску имплементацију линеарних и нелинераних структура података, као и алгоритама за рад са њима у типичним применама, као што су претраживање и сортирање.

Теоријска настава

Линеарне структуре. Низови. Листе. Стекови. Редови чекања. Нелинеарне структуре. Стабла: бинарна стабла, обилазак стабла, минимизација дужине пута. Графови. Начини представљања, обилазак графа по ширини и по дубини, одређивање артикулационих тачака повезаног графа, одрђивање мостова графа, издвајање двоструко повезаних компоненти, издвајање компоненти јаке повезаности. одређивање тополошког поретка и критичног пута, повезујућа стабла и минимална повезујућа стабла, одређивање достижности и најкраћих растојања. Претраживање. Основни метод и побољшања. Стабло бинарног претраживања, AVL стабла, оптимално стабло. Стабло m-арног претраживања. B, B* i B+ стабла, стабла дигиталног претраживања. Хеширање. Хеш функције, разрешавање колизија, спољашње хеширање. Сортирање. Сортирање поређењем - методи уметања, селекције, замене, методи линеарне сложености. Алгоритми сортирања временске сложености O(N log N). Доња граница сложености сортирања.

Практична настава

Имплементација неких од структура које су приказане на предавањима: повезане листе, стек, ред, бинарно стабло, приоритетни ред, бинарно претраживачко стабло, AVL стабло, B стабло, хеш табеле. Имплементација алгоритама за сортирање. Дизајн и анализа алгоритама за разне алгоритамске проблеме уз примену структура података и алгоритама који су приказани на предавањима (при анализи посебан акценат ставити на процени најмање повољног случаја, као и просечног случаја).