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

ID: 0390
врста предмета: научно-стручни
носилац предмета: Бенгин Ч. Александар
извођачи: Бенгин Ч. Александар, Митровић Б. Часлав
контакт особа: Бенгин Ч. Александар
ниво студија: мастер академске студије
ЕСПБ: 6
облик завршног испита: писмени
катедра: катедра за ваздухопловство

извођења

циљ

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

исход

После успешног одлушаног програма који је предвиђен овим предметом студент може: • да препозна и одабере одговарајућу структуру података за податке које треба обрађивати, • да одабере најбржи, најефикаснији или најтачнији алгоритам за одговарајући проблем, • да одабере алгоритам из класе итеративних или рекурзивних алгоритама.

садржај теоријске наставе

Дефиниције алгоритма. Анализа алгоритама. Запис алгоритама. Појам апстрактног типа података. Елементи од којих се граде структуре података. Листа. Стек. Ред. Стабла. Бинарна стабла. Бинарно стабло за претраживање. Бинарни хип. Скуп. Речник. Хеширање. Редови приоритета. Пресликавање. Релација. Сортирање заменом елемената. Сортирање уметањем. Рекурзивни алгоритми за сортирање. Сортирање помоћу бинарног стабла. Секвенцијално претраживање. Бинарно претраживање. Претраживање помоћу бинарног стабла. Црвено-црно стабло. Основни појмови. Усмерени и неусмерени графови. Петрага у дубину и ширину. Примене претраге у дубину и ширину. Завади па владај. Ханојске куле. Сортирање сажимањем. Брзо сортирање. Тражење елемента у листи. Множење великих целих бројева. Фибоначијеви бројеви. Биномни коефицијенти. Најдужи заједнички подниз. Триангулација полигона. Одређивање шансе за победу у такмичењу. Проблем ранца. Проблем враћање кусура. Проблем бојења атласа. Оптимално сжимање сортираних листа. Проблем ранца. Проблем распореда часова. Проблем n краљица. Проблем трговачког путника. Проблем стабилних бракова.

садржај практичне наставе

Састоји се из аудиторних, лабораторијских вежби које прате садржај предмета.

услов похађања

Знање С/С++ језика. Познавање основа методологије пројектовања програма. Основе софтверског инжењерства.

ресурси

Неопходан софтвер за овај предмет је под GNU лиценцом - бесплатан је. Уколико користите LINUX неопходни С/C++ Вам је одмах доступна. Уколико користите други оперативни систем С/C++ можете преузети са одговарајуће WEB локације (види URL) или на самом URL-u. За покретање неопходног софтвера довољно је поседовати најједноставнији PC рачунар.

фонд часова

укупан фонд часова: 75

активна настава (теоријска)

ново градиво: 20
разрада и примери (рекапитулација): 0

активна настава (практична)

аудиторне вежбе: 6
лабораторијске вежбе: 13
рачунски задаци: 0
семинарски рад: 15
пројекат: 3
консултације: 0
дискусија/радионица: 3
студијски истраживачки рад: 0

провера знања

преглед и оцена рачунских задатака: 0
преглед и оцена лабораторијских извештаја: 0
преглед и оцена семинарских радова: 3
преглед и оцена пројекта: 3
колоквијум са оцењивањем: 0
тест са оцењивањем: 4
завршни испит: 5

провера знања (укупно 100 поена)

активност у току предавања: 5
тест/колоквијум: 35
лабораторијска вежбања: 0
рачунски задаци: 0
семинарски рад: 15
пројекат: 15
завршни испит: 30
услов за излазак на испит (потребан број поена): 35

литература