Algorytmy i struktury danych
dr Zbigniew Gontar
wykład 5
ZAGADNIENIA
1. Wizualizacja algorytmu: sieć działań (schemat
blokowy)
2. Sortowanie tablic
3. Poprawność algorytmu
4. Analiza złozoności algorytmu
BIBLIOGRAFIA
1. Horowitz E., Sahni S. (1984), Fundamentals of Data Structures.
Computer Science Press.
2. Jones C.B. (1984), Konstruowanie oprogramowania metodą
systematyczną. Wydawnictwa Naukowo-Techniczne, Warszawa.
3. Wikipedia (2006), Algorytm.
http://pl.wikipedia.org/wiki/Algorytm.
4. Van Tassel D. (1982), Praktyka programowania. Wydawnictwa
Naukowo-Techniczne, Warszawa.
5. Brady J.M. (1983), Informatyka teoretyczna w ujęciu
programistycznym. Wydawnictwa Naukowo-Techniczne,
Warszawa.
6. Cormen T.H., Leiserson C.E., Rivest R.L. (1997), Wprowadzenie
do algorytmów. Wydawnictwa Naukowo-Techniczne,
Warszawa.
SIEĆ DZIAAAC
1. Schemat blokowy (ang. block diagram, flowchart)
- diagram, na którym procedura, system albo
program komputerowy, są reprezentowane przez
opisane figury geometryczne połączone liniami
zgodnie z kolejnością wykonywania czynności
wynikających z przyjętego algorytmu rozwiązania
zadania. Schemat blokowy pozwala dostrzec
istotne etapy algorytm i logiczne zale\ności między
nimi. Zale\nie od przedstawianego zagadnienia
stosowane są ró\ne zestawy figur geometrycznych
zwanych blokami, których kształty reprezentują
umownie rodzaje elementów składowych.
BLOKI SIEĆ DZIAAAC
(2) (3)
(1)
1. Blok graniczny - oznacza on początek, koniec, przerwanie
lub wstrzymanie wykonywania działania, np. blok startu
programu.
2. Blok wejścia-wyjścia - przedstawia czynność
wprowadzania danych do programu i przyporządkowania
ich zmiennym dla pózniejszego wykorzystania jak i
wyprowadzenia wyników obliczeń, np. czytaj z, pisz z+10.
3. Blok obliczeniowy - oznacza wykonanie operacji w
efekcie, której zmienią się wartości, postać lub miejsce
zapisu danych, np. z = z + 1.
BLOKI SIEĆ DZIAAAC
tak
(4)
(6)
(5)
nie
4. Blok decyzyjny - przedstawia wybór jednego z dwóch
wariantów wykonywania programu na podstawie
sprawdzenia warunku wpisanego w ów blok, np. a = b.
5. Blok wywołania podprogramu - oznacza zmianę
wykonywanej czynności na skutek wywołania
podprogramu, np. MAX(x,y,z).
6. Blok fragmentu - przedstawia część programu
zdefiniowanego odrębnie, np. sortowanie.
BLOKI SIEĆ DZIAAAC
(8)
(9)
(7)
7. Blok komentarza - pozwala wprowadzać komentarze
wyjaśniające poszczególne części schematu co ułatwia
zrozumienie go czytającemu, np. wprowadzenie danych.
8. Aącznik wewnętrzny - słu\y do łączenia odrębnych części
schematu znajdujących się na tej samej stronie, powiązane ze
sobą łączniki oznaczone są tym samym napisem, np. A1, 7.
9. Aącznik zewnętrzny - słu\y do łączenia odrębnych części
schematu znajdujących się na odrębnych stronach, powinien
być opisany jak łącznik wewnętrzny, poza tym powinien
zawierać numer strony, do której się odwołuje.
Badanie, czy liczba N jest pierwsza
1. Liczba jest pierwsza, gdy dzieli się tylko przez
1 i przez siebie
2. Algorytm polega na dzieleniu N przez 2, 3, 4,
..., N-1 a\ do osiągnięcia N lub do znalezienia
podzielnika
Badanie, czy liczba N (N > 1)
jest pierwsza
i = 2
1. Wejście: N
2. Wyjście: Komunikat o tym, czy N
jest pierwsza
Czytaj N
3. Ustal i równe 2
tak
4. Czytaj N
N=2
N pierwsza
5. Jeśli N=2 to Wypisz komunikat:
N pierwsza
nie
tak
6. W przeciwnym przypadku
i dzieli N
N nie pierwsza
7. Dopóki N nie jest podzielne przez i
nie
wykonaj
i=i+1
1. Ustal i = i+1
8. Koniec dopóki
nie
ie"N
9. Jeśli ie"N to Wypisz komunikat: N
pierwsza
tak
10. W przeciwnym przypadku:
N pierwsza
Wypisz komunikat: N nie
pierwsza
Badanie, czy liczba N (N > 1)
Czytaj N
jest pierwsza
tak 1. Wejście: N
2. Wyjście: Komunikat o tym, czy N
N=2, 3
N pierwsza
jest pierwsza
nie
tak
3. Ustal i równe 2
2 dzieli N
4. Czytaj N
nie
5. Jeśli N=2 to Wypisz komunikat:
N nie pierwsza N pierwsza
i=3
6. W przeciwnym przypadku
tak
7. Dopóki N nie jest podzielne przez i
i dzieli N
wykonaj
nie
1. Ustal i = i+1
i=i+2
8. Koniec dopóki
nie
9. Jeśli ie"N to Wypisz komunikat: N
ie"N
pierwsza
tak
10. W przeciwnym przypadku:
N pierwsza
Wypisz komunikat: N nie
pierwsza
Badanie, czy liczba N (N > 1)
Czytaj N
jest pierwsza
tak 1. Wejście: N
2. Wyjście: Komunikat o tym, czy N
N=2, 3
N pierwsza
jest pierwsza
nie
tak
3. Ustal i równe 2
2 dzieli N
4. Czytaj N
nie
5. Jeśli N=2 to Wypisz komunikat:
N nie pierwsza N pierwsza
i=3
6. W przeciwnym przypadku
tak
7. Dopóki N nie jest podzielne przez i
i dzieli N
wykonaj
nie
1. Ustal i = i+1
i=i+2
8. Koniec dopóki
nie
9. Jeśli ie"N to Wypisz komunikat: N
i>"N
pierwsza
tak
10. W przeciwnym przypadku:
N pierwsza
Wypisz komunikat: N nie
pierwsza
Schemat bez pętli
START
P Q Rezultat
nie
tak
P?
Prawda Prawda F
tak nie
Q?
Prawda Fałsz F
G H
Fałsz Prawda G
F
Fałsz Fałsz H
STOP
Schemat bez pętli
P Q R Rezultat
Prawda Prawda Prawda
Prawda Prawda Fałsz
Prawda Fałsz Prawda
Prawda Fałsz Fałsz
Fałsz Prawda Prawda
START
Fałsz Prawda Fałsz
Fałsz Fałsz Prawda
nie
tak
Fałsz Fałsz Fałsz
P?
tak
nie nie
Q? R?
tak
F
I
H
STOP
START
WEJŚCIE: Y, L
WYJŚCIE: x"{jest, nie ma}
Wez całą listę
wejściową L
Jest Y
Porównaj Y ze
Nie ma Y
środkowym elementem
rozwa\anej listy
Wez pierwszą albo drugą
połowę rozwa\anej listy, Wypisz jest
zale\nie od wyniku porównania
tak
nie
Czy rozwa\ana
Wypisz nie ma STOP
lista jest pusta
Schemat zawierający pętlę
START
nie
tak
P(x)?
tak nie
Q(x)?
G H
F
STOP
Technika asercji indukcyjnych
START
x"N
y = x
x"N '"y=x
nie tak
y=x '"x<0
ye"0
y=-y
y=x '"xe"0
y=-x '"x<0
y=|x|
STOP
Technika asercji indukcyjnych
START
x1 = a
x2 = b
a
nie
tak
x1e"x2
x3=x1
y=x '"xe"0
y=-x '"x<0
y=|x|
STOP
SORTOWANIE
Sortowanie to proces ustawiania zbioru obiektów
w określonym porządku, stosowany w celu
ułatwienia wyszukiwania elementów sortowanego
zbioru. Wynikiem algorytmu sortowania jest
oczywiście zbiór posortowany w ustalonym
porządku.
SORTOWANIE PRZEZ
WSTAWIANIE (A)
Zbiór kroków opisanych w języku polskim
tworzący algorytm sortowania przez wstawianie
przedstawia się następująco:
1. Wez pierwsze dwa elementy zbioru i ustaw je zgodnie
z porządkiem sortowania
2. Wez następny element zbioru i ustaw go zgodnie z
porządkiem sortowania względem poprzednich
uporządkowanych elementów
3. Powtórz krok drugi dla ka\dego następnego elementu
zbioru
SORTOWANIE PRZEZ
WSTAWIANIE
1. Rozwa\my przykład następującego zbioru {5, 2, 3, 8, 1}.
Posortujemy ten zbiór w porządku rosnącym. Wprowadzmy symbol
oddzielający zbiór posortowany od zbioru nieposortowanego | .
Część
Część
nieposortowana
posortowana
SORTOWANIE PRZEZ
WSTAWIANIE (A)
2. Pierwszy element zbioru (5) pozostaje na swojej pozycji
5
5 2 3 8 1
2
2
SORTOWANIE PRZEZ
WSTAWIANIE (A)
3. Drugi element zbioru (2) jest porównany z pierwszym zbioru posortowanego (5),
po czym trafia na pierwsze miejsce zbioru, wymieniając się pozycją z elementem
dotychczas okupującym to miejsce.
5
5 2 3 8 1
2
2
SORTOWANIE PRZEZ
WSTAWIANIE (A)
3. Drugi element zbioru (2) jest porównany z pierwszym zbioru posortowanego (5),
po czym trafia na pierwsze miejsce zbioru, wymieniając się pozycją z elementem
dotychczas okupującym to miejsce.
5
5 2 3 8 1
2
2
SORTOWANIE PRZEZ
WSTAWIANIE (A)
3. Drugi element zbioru (2) jest porównany z pierwszym zbioru posortowanego (5),
po czym trafia na pierwsze miejsce zbioru, wymieniając się pozycją z elementem
dotychczas okupującym to miejsce.
5
2 5 3 8 1
2
2
SORTOWANIE PRZEZ
WSTAWIANIE (A)
4. Trzeci element (3) jest porównany z pierwszym elementem zbioru posortowanego
(2). Poniewa\ zbiór {2, 3} jest uporządkowany, nie podejmujemy akcji.
2 5
2 5 3 8 1
2
2 3
SORTOWANIE PRZEZ
WSTAWIANIE (A)
4. Trzeci element (3) jest porównany z pierwszym elementem zbioru posortowanego
(2). Poniewa\ zbiór {2, 3} jest uporządkowany, nie podejmujemy akcji.
2 5
2 5 3 8 1
2
2 3
SORTOWANIE PRZEZ
WSTAWIANIE (A)
4. Przechodzimy do kolejnego elementu zbioru posortowanego (5) i porównujemy
element (3) z tym elementem, po czym element (3) zajmuje jego miejsce i
powoduje, \e pozostałe elementy zbioru posortowanego przesuwają się o jedną
pozycję.
2 5
2 5 3 8 1
2
2 3
SORTOWANIE PRZEZ
WSTAWIANIE (A)
4. Przechodzimy do kolejnego elementu zbioru posortowanego (5) i porównujemy
element (3) z tym elementem, po czym element (3) zajmuje jego miejsce i
powoduje, \e pozostałe elementy zbioru posortowanego przesuwają się o jedną
pozycję.
2 5 5
2 5 3 8 1
2
2 3 3
SORTOWANIE PRZEZ
WSTAWIANIE (A)
4. Przechodzimy do kolejnego elementu zbioru posortowanego (5) i porównujemy
element (3) z tym elementem, po czym element (3) zajmuje jego miejsce i
powoduje, \e pozostałe elementy zbioru posortowanego przesuwają się o jedną
pozycję.
2 5 5
2 3 5 8 1
2
2 3 3
SORTOWANIE PRZEZ
WSTAWIANIE (A)
5. Czwarty element (8) jest porównany z pierwszym elementem zbioru
posortowanego (2). Poniewa\ zbiór {2, 8} jest uporządkowany, nie podejmujemy
akcji.
2 5 5
2 3 5 8 1
2
2 3 3 8
SORTOWANIE PRZEZ
WSTAWIANIE (A)
5. Czwarty element (8) jest porównany z pierwszym elementem zbioru
posortowanego (2). Poniewa\ zbiór {2, 8} jest uporządkowany, nie podejmujemy
akcji.
2 5 5
2 3 5 8 1
2
2 3 3 8
SORTOWANIE PRZEZ
WSTAWIANIE (A)
5. Przechodzimy do kolejnego elementu zbioru posortowanego (3) i porównujemy
element (8) z tym elementem. Poniewa\ zbiór {3, 8} jest uporządkowany, nie
podejmujemy akcji.
2 3 5
2 3 5 8 1
2
2 3 3 8
SORTOWANIE PRZEZ
WSTAWIANIE (A)
5. Przechodzimy do kolejnego elementu zbioru posortowanego (3) i porównujemy
element (8) z tym elementem. Poniewa\ zbiór {3, 8} jest uporządkowany, nie
podejmujemy akcji.
2 3 5
2 3 5 8 1
2
2 3 3 8
SORTOWANIE PRZEZ
WSTAWIANIE (A)
5. Przechodzimy do kolejnego elementu zbioru posortowanego (5) i porównujemy
element (8) z tym elementem. Poniewa\ zbiór {5, 8} jest uporządkowany, nie
podejmujemy akcji.
2 3 5
2 3 5 8 1
2
2 3 3 8
SORTOWANIE PRZEZ
WSTAWIANIE (A)
5. Przechodzimy do kolejnego elementu zbioru posortowanego (5) i porównujemy
element (8) z tym elementem. Poniewa\ zbiór {5, 8} jest uporządkowany, nie
podejmujemy akcji.
2 3 5
2 3 5 8 1
2
2 3 3 8
SORTOWANIE PRZEZ
WSTAWIANIE (A)
5. Pozostawiamy element (8) na swoim miejscu.
2 3 5
2 3 5 8 1
2
2 3 3 8
SORTOWANIE PRZEZ
WSTAWIANIE (A)
6. Piąty element (1) jest porównany z pierwszym elementem zbioru posortowanego
(2), po czym element (1) zajmuje jego miejsce i powoduje, \e pozostałe elementy
zbioru posortowanego przesuwają się o jedną pozycję.
2 3 5
2 3 5 8 1
2
2 3 3 8 1
SORTOWANIE PRZEZ
WSTAWIANIE (A)
6. Piąty element (1) jest porównany z pierwszym elementem zbioru posortowanego
(2), po czym element (1) zajmuje jego miejsce i powoduje, \e pozostałe elementy
zbioru posortowanego przesuwają się o jedną pozycję.
2 3 5 8
2 3 5 8 1
2
2 3 3 8 1
SORTOWANIE PRZEZ
WSTAWIANIE (A)
6. Piąty element (1) jest porównany z pierwszym elementem zbioru posortowanego
(2), po czym element (1) zajmuje jego miejsce i powoduje, \e pozostałe elementy
zbioru posortowanego przesuwają się o jedną pozycję.
2 2 3 5 8
2 3 5 8 1
2
1 3 3 8 1
SORTOWANIE PRZEZ
WSTAWIANIE (A)
6. Piąty element (1) jest porównany z pierwszym elementem zbioru posortowanego
(2), po czym element (1) zajmuje jego miejsce i powoduje, \e pozostałe elementy
zbioru posortowanego przesuwają się o jedną pozycję.
2 2 3 5 8
1 2 3 5 8
2
1 3 3 8 1
SORTOWANIE PRZEZ
WSTAWIANIE (A)
1. dla j ! 2 do rozmiar [A]
2. wykonaj klucz ! A[j]
3. Wstaw A[j] do posortowanej tablicy A[1 . . j - 1].
4. i ! j - 1
5. dopóki i > 0 i A[i] > klucz
6. wykonaj A[i + 1] ! A[i]
7. i ! i - 1
8. A[i + 1] ! klucz
SORTOWANIE PRZEZ WSTAWIANIE
DLA TABLICY A=<5, 2, 4, 6, 1, 3>
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6
SORTOWANIE PRZEZ WSTAWIANIE CZAS
DZIAAANIA ALGORYTMU
n n n
T(n)= c1n + c2(n -1)+ c4(n -1)+ c5 j + c6 (t -1)+ c7 (t -1)+ c8(n -1)
"t " j " j
j=2 j=2 j=2
Koszt Liczba wykonań
1 C1 n
dla j ! 2 do rozmiar [A]
2 C2 n-1
wykonaj klucz ! A[j]
3 Wstaw A[j] do posortowanej tablicy A[1 . . j 1] 0 n-1
4 C4 n-1
i ! j 1
n
5 dopóki i > 0 i A[i] > klucz C5 "t j
j=2
n
6 C6
wykonaj A[i + 1] ! A[i] (t -1)
" j
j=2
n
(t -1)
7 C7 " j
i ! i - 1
j=2
8 C8 n-1
A[i + 1] ! klucz
SORTOWANIE PRZEZ WSTAWIANIE CZAS
DZIAAANIA ALGORYTMU
n n n
T(n)= c1n + c2(n -1)+ c4(n -1)+ c5 j + c6 (t -1)+ c7 (t -1)+ c8(n -1)
"t " j " j
j=2 j=2 j=2
1. Przypadek optymistyczny: funkcja liniowa
względem n
T(n)= c1n + c2(n -1)+ c4(n -1)+ c5(n -1)+ c8(n -1)= (c1 + c2 + c4 + c5 + c8)n -(c2 + c4 + c5 + c8)
1. Przypadek pesymistyczny: funkcja kwadratowa
względem n
n(n +1) n(n -1)ł + c7ł n(n -1)ł + c8(n -1)=
ł ł
T(n)= c1n + c2(n -1)+ c4(n -1)+ c5ł -1ł + c6ł
ł ł ł ł
2 2 2
ł łł ł łł ł łł
c5 c6 c7 c5 c6 c7
ł łn2 - łc + c2 + c4 + - - + c8 łn -(c2 + c4 + c5 + c8)
+ +
ł ł ł ł
1
2 2 2 2 2 2
ł łł ł łł
Wyszukiwarka
Podobne podstrony:
Sieci komputerowe wyklady dr Furtak
Wykład 05 Opadanie i fluidyzacja
WYKŁAD 1 Wprowadzenie do biotechnologii farmaceutycznej
mo3 wykladyJJ
ZARZĄDZANIE WARTOŚCIĄ PRZEDSIĘBIORSTWA Z DNIA 26 MARZEC 2011 WYKŁAD NR 3
Wyklad 2 PNOP 08 9 zaoczne
Wyklad studport 8
Kryptografia wyklad
Budownictwo Ogolne II zaoczne wyklad 13 ppoz
wyklad09
Sporzadzanie rachunku przepływów pienieżnych wykład 1 i 2
fcs wyklad 5
Wyklad08 Zaopatrz wWode
Wyklad3
więcej podobnych podstron