KSIEGA PYTAN

W1

• Co to jest specyfikacja algorytmu?
• Podaj definicje częściowej poprawnosci algorytmu.
• Podaj definicje całkowitej poprawnosci algorytmu.
• Sformuluj problem stopu.
• Podaj przyklad algorytmu, który jest czesciowo poprawny ze wzgledu na pewna specyfikacje ale nie jest calkowicie poprawny.
• Uzasadnij, ze jezeli algorytm A jest calkowicie poprawny zarówno ze wzgledu na specyfikacje <a,b> jak i na specyfikacje <a',b'>, to jest równiez poprawny ze wzgledu na specyfikacje <a & a', b & b'>.
• Jezeli algorytm A1 jest calkowicie poprawny ze wzgled na specyfikacje <a,b1> a algorytm A2 jest calkowicie poprawny ze wzgledu na specyfikacje <a,b2>, to algorytm if gamma then A1 else A2 fi jest calkowicie poprawny ze wzgledu na specyfikacje <a, b1 lub b2> .
• Uzasadnij, ze jezeli algorytm A1 jest calkowicie poprawny ze wzgledu na specyfikacje <a1,b1> a algorytm A2 jest calkowicie poprawny ze wzgledu na specyfikacje <a2,b2> oraz (b1 => a2), to algorytm begin A1 ; A2 end jest calkowicie poprawny ze wzgledu na specyfikacje <a1, b2> .
• Czy odpowiedzi na pytania 6,7,8 pozostana takie same, jesli zastapimy pojecie calkowitej poprawnosci, poprawnoscia czesciowa?
• Jezeli a(x) jest warunkiem spelnionym przed wykonaniem instrukcji x := x+1 to po wykonaniu tej instrukcji spelniony jest warunek a(x/x-1) czy a(x/x+1)?Czym mierzymy koszt algorytmu?
• Jaki jest koszt czasowy algorytmu poszukiwan sekwencyjnych w ciagu n-elementowym.
• Wytlumacz na czym polega metoda "dziel i zwyciezaj"?
• Wytlumacz pojecie O(f), gdzie f jest funkcja okreslona na zbiorze liczb naturalnych i o wartosciach w zbiorze R+.
• Uzasadnij, ze jezeli f,g,h :N->R+, g =O(f) oraz h =O(f) , to g+h = O(f).
• Czy z tego ze g =O(f) oraz h =O(f) wynika, ze g*h= O(f)?
• Udowodnij, ze 4^n = Omega(2^n) ale nie jest prawda, ze 4^n = O(2^n).
• Porównaj rzedy wielkosci funkcji logarymicznej przy różnych podstawach.
• Która z równosci jest prawdziwa: lg n =O(n), czy n= O(lg n)?
• Udowodnic, korzystajac z lematu o porównywaniu rzedów funkcji, ze funkcja
(3n^4 + lg n + 700 )/(n^3+2n+3)
ma koszt liniowy.
vers Spis Tresci


---

W2

• Jaki jest koszt optymalnego algorytmu wyszukiwania elementu najmniejszego w ciągu uporządkowanym?
• Ile porównań musi wykonać w najgorszym razie algorytm bisekcji (wyszukiwania dowolnego elementu) zastosowany do ciągu o 64 elmentach?
• Opisz optymalną metodę wyszukiwania konkretnej osoby w książce telefonicznej.
• Zaprojektuj algorytm rekurencyjny wyszukiwania dowolnego elementu w ciągu uporządkowanym, oparty na zasadzie "dziel i zwyciężaj".
  

• ---

W3