ФИНКИ / Основи и алгоритмиДизајн на алгоритми.
Развивај ефикасни алгоритми и научи како да ја аргументираш избраната стратегија за решавање на проблемот.
<>РАЗБЕРИ. ПРИМЕНИ. НАПРЕДУВАЈ.+
- 01Динамичко програмирање, мемоизација и алчни стратегии
- 02Пребарување во графови и најкратки патишта
- 03Мрежен проток и напредни податочни структури
- 04Алгоритми за текст, геометрија и анализа на сложеност
02 / РАЗБЕРИ ГО КОНЦЕПТОТ
Логиката зад
решението.
Дизајнот на алгоритми бара стратегија, а не само точен код. Алчниот пристап го избира моментално најдобриот чекор, но не гарантира глобално решение за секој проблем. Динамичкото програмирање ги користи повторливите потпроблеми и ги чува нивните резултати. Важно е да ја дефинираме состојбата и преминот.
ПРИМЕР ОД СЕКОЈДНЕВНАТА ПРАКТИКАИЛУСТРАТИВЕН ПРИМЕР
Најдобар избор со ограничен буџет
Работилница има буџет од 7 единици. Машините A, B и C чинат 4, 3 и 5, а носат корист 5, 4 и 8. Секоја може да се купи најмногу еднаш.
- 01
Ги споредуваме комбинациите што не го надминуваат буџетот.
- 02
Самата C дава корист 8; A и B заедно чинат 7 и даваат 9.
- 03
За поголем список ја чуваме најдобрата корист за секој разгледан префикс и буџет.
↳Што добиваме?Најдобар избор е A + B со корист 9. Изборот само на машината со најголема поединечна корист би пропуштил подобро решение.
Сценариото и податоците се поедноставени за учење. Примерот не претставува конкретен клиентски проект или измерени резултати од продукциски систем.
03 / СТУДЕНТСКИ ПРАШАЊА
Прашај.
Разбери подобро.
Како препознавам динамичко програмирање?+
Побарај повторливи потпроблеми и можност оптималното решение да се изгради од нив. Потоа дефинирај што точно претставува една состојба.
Дали Дејкстра работи со негативни тежини?+
Стандардниот алгоритам бара ненегативни тежини. За негативни ребра треба друг соодветен алгоритам и проверка на условите.
Зошто не ги пробаме сите комбинации?+
Тоа е корисна проверка за мал пример, но бројот на комбинации може да расте експоненцијално со бројот на ставки.
Твојот материјал.
Нашата следна задача.
Работиме на делот што ти е најпотребен: основни концепти, практични задачи или подготовка за колоквиум и испит. Содржината ја усогласуваме со материјалите што ги учиш во твојата генерација.
REC ТВОЈОТ ЧАС
▶
РАЗБЕРИ. ПОВТОРИ. ПРИМЕНИ.↺
НЕ САМО ЕДНАШ. КОЛКУ ШТО ТИ ТРЕБА.Часот завршува.
Знаењето останува.
Секој час се снима. Врати се на објаснувањата, паузирај кај потешките делови и повтори ги задачите со свое темпо.
↺Снимките се достапни најмалку
во текот на еден семестар.
Снимките се наменети за твоето учење. Споделување и објавување се дозволени само по претходен договор.