S-Analiza algorytmow - Z.Czech -PĹš .pdf

(290 KB) Pobierz
calosc.dvi
Instytut Informatyki
Politechnika ‘l¡ska
Analizaalgorytmów
Opracował: Zbigniew Czech
Materiały dydaktyczne
Gliwice, wrzesie« 2004
Spis tre±ci
1 Dowodzenie poprawno±ci algorytmów 4
1.1 Aksjomaty arytmetyki liczb . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Prawa rachunku zda« . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Reguły dowodzenia (wnioskowania) . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Dowodzenie sko«czono±cialgorytmów . . . . . . . . . . . . . . . . . . . . . . 8
2 Zło»ono±¢ obliczeniowa algorytmów 8
2.1 Obliczanie warto±ci wielomianu . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Mno»enie liczb całkowitych . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Znajdowanie maksymalnego (minimalnego) elementu . . . . . . . . . . . . . . 9
2.4 Jednoczesne znajdowanie maksymalnego i minimalnego elementu . . . . . . . 10
2.5 Mno»enie dwóch n -bitowych liczb dwójkowych . . . . . . . . . . . . . . . . . 10
2.6 Sortowanie przez ł¡czenie . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Kopce i kolejki priorytetowe 11
3.1 Procedury operuj¡ce na kopcu . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Operacje na kolejkach priorytetowych . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Sortowanie przez kopcowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Wyszukiwanie 14
4.1 Wyszukiwanie liniowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Wyszukiwanie liniowe z zastosowaniemwartownika . . . . . . . . . . . . . . . 14
4.3 Wyszukiwanie liniowe w uporz¡dkowanejtablicy . . . . . . . . . . . . . . . . 15
4.4 Wyszukiwanie binarne (logarytmiczne) . . . . . . . . . . . . . . . . . . . . . . 15
4.5 Drzewa poszukiwa« binarnych . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.6 Haszowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.6.1 Haszowanie otwarte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.6.2 Haszowanie zamkni¦te . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.7 Minimalne, doskonałe funkcje haszuj¡ce . . . . . . . . . . . . . . . . . . . . . 22
5 Operacje na tekstach 24
5.1 Wyszukiwanie „naiwne” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2 Algorytm Knutha, Morrisa i Pratta (KMP) . . . . . . . . . . . . . . . . . . . 25
5.3 Wyszukiwanie niezgodno±ciowe . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.4 Algorytm Boyera i Moora (BM). . . . . . . . . . . . . . . . . . . . . . . . . . 26
6 Sortowanie 27
6.1 Sortowanie przez proste wstawianie . . . . . . . . . . . . . . . . . . . . . . . 27
6.2 Algorytm Shella, czyli sortowanie za pomoc¡ malej¡cych przyrostów . . . . . 29
6.3 Sortowanie przez proste wybieranie . . . . . . . . . . . . . . . . . . . . . . . 30
6.4 Sortowanie przez prosta zamian¦ . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.5 Sortowanie szybkie – algorytm Quicksort. . . . . . . . . . . . . . . . . . . . . 34
6.6 Inna wersja algorytmu Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.7 Czasy wykonania programów sortowania . . . . . . . . . . . . . . . . . . . . . 38
7 Selekcja
39
8 Sortowanie przy uwzgl¦dnieniu szczególnych własno±ci kluczy 39
8.1 Sortowanie kubełkowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
8.2 Sortowanie pozycyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
9 Algorytmy zachłanne 43
9.1 Kolorowaniezachłanne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
9.2 Problem komiwoja»era . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
9.3 Znajdowanie najta«szych dróg — algorytm Dijkstry . . . . . . . . . . . . . . 44
2
10 Algorytmy grafowe 44
10.1 Przeszukiwanie grafu w gł¡b. . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10.2 Przeszukiwanie grafu wszerz . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
10.3 Wyznaczanie cykli podstawowych (fundamentalnych) . . . . . . . . . . . . . . 47
10.4 Minimalne drzewa rozpinaj¡ce . . . . . . . . . . . . . . . . . . . . . . . . . . 48
10.5 Wyznaczanie cykli Eulera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
11 Wyszukiwanie wyczerpujace. Algorytm z powrotami
49
12 Przeszukiwanie heurystyczne 49
12.1 Przeszukiwanie wszerz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
12.2 Przeszukiwanie w gł¡b z iteracyjnym pogł¦bianiem . . . . . . . . . . . . . . . 50
12.3 Przeszukiwanie według strategii „najlepszy wierzchołek jako pierwszy” . . . . 50
13 Generowanie permutacji
51
14 Pytania
53
15 Podzi¦kowania
56
Literatura
56
3
1 Dowodzenie poprawno±ci algorytmów
Przed dowodem poprawno±ci
{ ( n> 0) and ( m> 0) } warunek wst¦pny (asercja wej±ciowa)
begin
iloczyn :=0;
N := n ;
repeat
iloczyn := iloczyn + m ;
N := N − 1;
until N =0;
end ;
{ iloczyn = n m } warunek ostateczny (asercja wyj±ciowa)
Po przeprowadzeniu dowodu
{ ( n> 0) and ( m> 0) }
begin
iloczyn :=0;
N := n ;
repeat
{ Niezmiennik: ( iloczyn + N m = n m ) and ( N > 0) }
iloczyn := iloczyn + m ;
N := N − 1;
{ ( iloczyn + N m = n m ) and ( N - 0) }
until N =0;
{ ( iloczyn + N m = n m ) and ( N =0) }
end ;
{ iloczyn = n m }
Proces obliczeniowy
Instrukcje
Wyniki oblicze«
Niezmiennik iteracji
n= 5 m= 8
iloczyn:=0; N :=n; iloczyn= 0,N = 5,m= 8 ( 0+5 8=40) and (N > 0)
iloczyn:= iloczyn+m N :=N −1 iloczyn= 8,N = 4,m= 8 ( 8+4 8=40) and (N > 0)
iloczyn:= iloczyn+m N :=N −1 iloczyn= 16,N = 3,m= 8 (16+3 8=40) and (N > 0)
iloczyn:= iloczyn+m N :=N −1 iloczyn= 24,N = 2,m= 8 (24+2 8=40) and (N > 0)
iloczyn:= iloczyn+m N :=N −1 iloczyn= 32,N = 1,m= 8 (32+1 8=40) and (N > 0)
iloczyn:= iloczyn+m N :=N − 1 iloczyn= 40,N = 0,m= 8 (40+0 8=40) and (N = 0)
Procedura assert oraz przykład jej u»ycia
procedure assert ( b : Boolean ; t : string );
if not b then write ( t );
assert (( n> 0) and ( m> 0), “not 1”);
begin
iloczyn :=0;
N := n ;
repeat
assert (( iloczyn + N m = n m ) and ( N > 0), “not 2”);
iloczyn := iloczyn + m ;
N := N − 1;
assert (( iloczyn + N m = n m ) and ( N - 0), “not 3”);
until N =0;
4
assert (( iloczyn + N m = n m ) and ( N =0), “not 4”);
end ;
assert ( iloczyn = n m , “not 5”);
1.1 Aksjomaty arytmetyki liczb
Przemienno±¢ dodawania i mno»enia
x + y = y + x
x y = y x
ł¡czno±¢ dodawania i mno»enia
( x + y )+ z = x +( y + z )
( x y ) z = x ( y z )
Rozdzielno±¢ dodawania i odejmowania wzgl¦dem mno»enia
x ( y + z )= x y + x z
x ( y−z )= x y−x z
Inne
x +0= x
x 0=0
x 1= x
1.2 Prawa rachunku zda«
e1, e2, e3 — zdania
1. Prawa przemienno±ci
( e 1 ^e 2) ( e 2 ^e 1)
( e 1 _e 2) ( e 2 _e 1)
( e 1 e 2) ( e 2 e 1)
2. Prawa łaczno±ci
e 1 ^ ( e 2 ^e 3) ( e 1 ^e 2) ^e 3
e 1 _ ( e 2 _e 3) ( e 1 _e 2) _e 3
3. Prawa rozdzielno±ci
e 1 _ ( e 2 ^e 3) ( e 1 _e 2) ^ ( e 1 _e 3)
e 1 ^ ( e 2 _e 3) ( e 1 ^e 2) _ ( e 1 ^e 3)
4. Prawa De Morgana
¬ ( e 1 ^e 2) ¬e 1 _¬e 2
¬ ( e 1 _e 2) ¬e 1 ^¬e 2
5. Prawo podwójnego przeczenia
¬ ( ¬e 1) e 1
6. Prawo wył¡czonego ±rodka
e 1 _¬e 1 true
7. Prawo zaprzeczenia
e 1 ^¬e 1 false
8. Prawo implikacji
e 1 )e 2 ¬e 1 _e 2
9. Prawo równowa»no±ci
( e 1 e 2) ( e 1 )e 2) ^ ( e 2 )e 1)
10. Prawa upraszczania alternatywy
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin