Grafi in časovna zahtevnost
Osnutek odseka
-
Na nekaj algoritmih na grafih bomo pokazali problem eksponentne časovne zahtevnosti, NP polnosti... Opazimo tudi, kako se lahko navidez povsem različni problemi prevedejo na isti problem, ki ga rešujemo z istim algoritmom.
-
Problem, za katerega lahko hitro poiščemo algoritem, ki pa ne da nujno optimalne rešitve.Primer problema, za katerega očitno znamo najti algoritem, a z eksponentno zahtevnostjo. Obenem pa sestavljalec problema pozna optimalno rešitev.
Nekaj videov Splača se pogledati tudi iste avtorice. (Hvala, Urša!)
-