Algoritmuselmélet gyakorlat (1)

1999. szeptember 13., hétfő

1. Hány összehasonlítással lehet megtalálni n különböző elem közül a legnagyobbat?
(Úgy értve, hogy mennyi elég biztosan és mennyi kell biztosan. Tehát ez két kerdés.)

2. Adjuk meg azt a T(n) függvényt zárt alakban, amely a nemnegatív egész számokon van értelmezve és eleget tesz a következő feltételeknek:
T(1)=2 és $n\geq 2$ esetén T(n)=T(n-1)+3

3. Ugyanaz a feladat, mint az előbb, csak most
T(1)=2 és $n\geq 2$ esetén T(n)=3T(n-1)+1

4. Ezt kell otthon megoldani és beadni írásban
Adjuk meg azt a T(n) fűggvényt zárt alakban, amely a 3^k alakú számokon van értelmezve és eleget tesz a következő feltételeknek:
T(1)=1 és $n\geq 3$ esetén T(n)=4T(n/3)+n².
(Segítség: gondoljunk arra, hogy n=3^k valami k-ra + a mértani sor összegképlete.)

5. Tegyük fel, hogy van egy számítógépes programunk, ami egy k méretű feladaton a jelenlegi gépünkön 1 nap alatt fut le. Beszereztünk egy százszor gyorsabb számítógépet. Ugyanazon programmal mekkora feladatot lehet az új gépen egy nap alatt megoldani, ha a program lépésszáma n méretű feladat esetén
(a) n-nel
(b) n³-bel
(c) 2ⁿ-nel arányos?

6. Bizonyítsuk be, hogy

• $\log_2 f(n)=\Theta(\log_{100} f(n))\;\;(f(n)>0).$
• 2ⁿ⁺¹=O(2ⁿ), de $2^{2n}\not=O(2^n).$
• $\max(f(n),g(n))=\Theta(f(n)+g(n))\;\; (f(n),g(n)>0).$

7. Négy elem rendezéséhez hány összehasonlítás kell?

Gondolkozni való feladat
8. (a) (*) Javasoljunk egy olyan algoritmust, ami $\lceil 1.5n \rceil-2$összehasonlítással megtalálja egy n-elemű halmaz legnagyobb és legkisebb elemét!
(b) (**) Igazoljuk, hogy $\lceil 1.5n \rceil-2$ összehasonlítás szükséges is a fenti feladat megoldására!

Gyakorlásnak
9. Tegyük fel, hogy a T(n) függvény csak a 2^k alakú számokon van értelmezve és tudjuk róla, hogy $T(n)\leq n-1 +2T(n/2)$. Mutassuk meg, hogy $T( n)\leq n\;{log}_2 n$fennáll!

10. Bizonyítsuk be, hogy
(a) $6n^2-2n+7=\Theta(n^2).$
(b) $\log_2 f(n)=\Theta(\log_{100} f(n))\;\;(f(n)>0).$