Ciele
- Zvládnuť návrh algoritmov a ladenie programov pre stroj RAM s využitím platformy emuStudio.
- Zvládnuť určovanie zložitosti RAM programov.
Úvod
-
Doposiaľ nadobudnuté a precvičené poznatky z oblasti návrhu a implementácie
algoritmov na stroji RAM rozšírime o oblasť určovania zložitosti navrhnutých
a implementovaných algoritmov.
Postup
-
Návrh algoritmov a ladenie programov pre stroj RAM s využitím emulátora.Úloha: Navrhnite algoritmus a odlaďte program pre stroj RAM.
Opis: Výpočet súčtu postupnosti 1,2,...,n, kde n>0.
Vstup: n. Výstup: 1+2+...+n. -
Určovanie zložitosti RAM programov.
Zložitosť algoritmov:
- časová a priestorová,
- najhoršia a priemerná (očakávaná),
- asymptotická zložitosť,
- zložitosť RAM programov - uniformné a logaritmické cenové kritérium.
Logaritmická cenová funkcia:
Logaritmická cena RAM operandov:
Logaritmická cena RAM inštrukcií:
Príklad: Stanovte asymptotickú časovú a priestorovú zložitosť RAM programu pre výpočet faktoriálu čísla n (cvičenie č.1). Použite uniformné aj logaritmické cenové kritérium.
-
Uniformné cenové kritérium:
Časová zložitosť (daná počtom vykonaných inštrukcií)
Priestorová zložitosť (daná počtom použitých registrov)
-
Logaritmické cenové kritérium:
Časová zložitosť (pre inštrukciu MUL 2, i-tá iterácia cyklu)
pre n-1 opakovaní cyklu:
po úprave:
Stirlingova aproximácia:
Priestorová zložitosť
Úloha: Stanovte asymptotickú časovú a priestorovú zložitosť RAM programu pre výpočet súčtu postupnosti 1,2,...,n. (cvičenie č.2). Použite uniformné aj logaritmické cenové kritérium (inštrukcia ADD).
Zdroje
- Logaritmy a ich vlastnosti.