9. 6. 2016 - Hric

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Jankus

9. 6. 2016 - Hric

Příspěvek od Jankus »

Pisomka mala 4 otazky, kazda za 5 bodov
1) Master Theorem:
a) formulacia - predpoklady, podmienky, jednotlive pripady
b) aplikacia na konkretnu rekurenciu s parametrom a - rozpisat pripady podla parametru (iba sa to dosadilo)
2) AVL stromy: a) popisat co to je b) delete
3) Jarnikov algoritmus: a) popisat ako funguje (vratane datovej struktury na vyberanie minima - vkladaju sa do nej vrcholy, nie hrany!) b) dokaz spravnosti
4) vymysliet algoritmus a datovu strukturu: dane cislo x, postupnost cisel b1..bn. chceme najst take bi, bj, ze bi+bj=x.

v 1 mi chybali nejake predpoklady, v 3 ta struktura. na ustnej som sice vymyslel haldu, ale ukladal smo do nej hrany.
v 4 je O(n^2) trivialne, ja som z beciek postupne staval BVS a vzdy sa pytal, ci tam je rozdiel x-bi, co dava O(n*log n), ale vravel, ze to ide linearne. 18 bodov z 20

na ustnej daval nahodne temy, snazil sa vraj take, co este nedal. vzdy je tam cas na pripravu (tie skusania sa celkom natiahnu...). dostal som rychle nasobenie dlhych cisiel. spomenul som si, ze to ma mat zlozitost n^log3, ale ako sa to robi mi musel poradit potom, aj tu rekurenciu. nakoniec za 2
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“