PROG1 - prednaska 10

Zhrnutie prednášky

Prednáška nadväzuje na organizačné informácie o výsledkoch prvého testu a pláne kurzu vrátane termínu projektu a druhého testu v 12. týždni, a následne sa venuje téme efektívnosti algoritmov pri práci so zoznamami. Na príklade hľadania najväčšieho čísla sú porovnané dve riešenia – s pomocnou premennou a so zoznamom – s dôrazom na to, že druhé má výrazne horšiu pamäťovú zložitosť. Vysvetľuje sa rozdiel medzi časovou a pamäťovou zložitosťou algoritmov a ich význam najmä pri obmedzených zariadeniach ako mikrokontroléry. Na úlohách z cvičenia (napríklad práca so súborom words.txt) sa demonštruje, ako výber metódy (append verzus zreťazenie) alebo návrhu algoritmu (skúšanie všetkých dvojíc verzus iba 100 000 prípadov) môže dramaticky ovplyvniť rýchlosť programu. Zdôrazňuje sa, že zoznamy sú síce univerzálne, no nie vždy najefektívnejšie riešenie daného problému.

• - Rekapitulácia výsledkov prvého testu a oprava chyby v jednej z úloh testu
• - Organizačné info: projekt do 13.12, príprava na druhý test v 12. týždni, domáca úloha na 10. týždeň
• - Porovnanie dvoch riešení hľadania maxima – s premennou vs. so zoznamom – z hľadiska pamäťovej zložitosti
• - Vysvetlenie pojmov časová a pamäťová zložitosť algoritmov a ich praktický význam
• - Dôležitosť efektívnosti algoritmov najmä pri zariadeniach s obmedzenými zdrojmi (mikrokontroléry)
• - Príklad z cvičenia 10: rozdiel v rýchlosti medzi append a zreťazovaním reťazcov pri načítaní 100 000 slov
• - Úloha hľadania párov slov (words.txt) ako ukážka výrazného zrýchlenia algoritmu voľbou lepšieho prístupu (100 000 vs. 5 miliárd prípadov)

Zhrnutie pripravené s pomocou AI z prepisu videa.