• машинство и информационе технологије , 2. семестар, позиција 1

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

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

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

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

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

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

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

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

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

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

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

М. Живковић, Алгоритми, Математички факултет, Београд, 2000.; T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, The MIT Press, Cambridge, 2009.;