Algorytm- opis wykonywania pewnego działania .Jest podzielony na części .Musi być określony w liczbie kroków , wykonywalny i w jednoznacznie możliwy sposób do wykonania. Algorytm realizacji zadania - dokładny opis danego zadania na poszczególne czynności ich wykonywania Za algorytm efektywny uważa się taki ,który wykonuje swe zadanie w jak najkrótszym czasie przy wykorzystaniu ja najmniejszych zasobów komputerowych. Algorytm w sensie informatycznym powinien : posiadać dane wejściowe(w ilości x>=0),generować określony wynik, być precyzyjnie zdefiniowany, być skończony.
Sposoby zapisywania algorytmów: słowny opis algorytmu, lista kroków, schemat blokowy ,drzewo algorytmu, drzewo wyrażeń Lista kroków - zawiera opis operacji. Na początku zawsze występuje specyfikacja zadania. Schemat blokowy - składa się z bloków - klatek, połączeń pomiędzy nimi. W blokach zapisywane są operacje, które mamy wykonać .
Reguły łączenia bloków : do każdego bloku może dochodzić dowolna liczba strzałek, z każdego bloku(oprócz decyzyjnego) może wychodzić tylko jedna strzałka, blok graniczny lub łącznik może być pozbawiony jednej ze strzałek(dochodzącej lub wychodzącej).Pozostałe bloki muszą mieć zarówno strzałkę dochodzącą jak i wychodzącą,
Schemat blokowy powinien być uzupełniony o listę nazw z nazwami wszystkich zmiennych użytych w schemacie. Drzewo algorytmu (obliczeń):korzeń - wierzchołek, w którym rozpoczyna się działanie algorytmu. Wierzchołki pośrednie w których umieszczone są operacje w programie. Wierzchołki końcowe (liście) ,które odpowiadają różnym wynikom zakończenia obliczeń w algorytmie. Drzewo wyrażenia: ma ograniczone, zastosowanie jako reprezentacja algorytmu - jest przede wszystkim stosowana do obliczania wartości wyrażeń arytmetycznych zawierających nawiasy Rekurencja: wywołanie algorytmu przez samego siebie. Algorytm z rozgałęzieniami : ma na celu zabezpieczenie przed zabronionymi działaniami matematycznymi w algorytmach (warunki)
Algorytmy z rozgałęzieniami
Specyfikacja-jeżeli jest to algorytm rozgałęziony to nie należy sporządzać listy kroków , a schemat blokowy lub jego specyficzną odmianę-drzewo
Długość drogi algorytmu - liczba porównań prowadzących do danej odpowiedzi programu jest równa liczbie wierzchołków pośrednich na drodze z korzenia do wierzchołka końcowego ,zawierającego odpowiedź. Wysokość drzewa algorytmu : największą długość drogi z korzenia do wierzchołka .Jest ona równa największej liczbie operacji porównań wykonywanych w algorytmie dla danego zestawu danych. Wysokość drzewa nazywany również złożonością obliczeniową lub pracochłonnością algorytmu .Jest to złożoność pesymistyczna , bo określa złożoność najgorszego przypadku danych.
Algorytm optymalny - wykonuje zadanie za pomocą najmniejszej liczby porównań
Analiza struktury danych - wyodrębnianie zmiennych z algorytmu i określenie sposobu ich zapamiętywania
Algorytmy iteracyjne
Iteracja-powtarzanie pewnych operacji lub grupy operacji
Częstość-ilość powtórzeń danej w zbiorze
Rozpiętość zbioru-różnica pomiędzy największą i najmniejszą liczbą w zbiorze (min ,max zbioru)Miary centralności danych - statystyki zbioru(średnia , mediana, moda)
Mediana - środkowa wartość, zbioru w tym sensie , że jeżeli zbiór uporządkujemy , to występuje ona w środku tego uporządkowania
Moda - jest najczęściej występującą liczba w zbiorze .Zbiór może nie mieć modę ,gdy każda liczba występuje tylko 1 raz. Może mieć 2,3,4..mody.
Zbiór danych może być określony przez : wczytanie z klawiatury, zdefiniowanie w tablicy, zdefiniowany w taśmie Taśma - ciąg komórek liczbowych skojarzonych z plikiem. Zarówno tablica jak i taśma operują na ciągach elementów. Moc - ilość elementów zbioru. W przypadku taśmy określane są na dwa sposoby :na początku definiowania ciągu podajemy ile elementów zawiera zbiór i następnie określamy poszczególne jego elementy ,na końcu zbioru umieszczamy elementarnie należący do tego zbioru zwany wartownikiem. Wartownikiem może być dowolna liczba niedodatnia np.-1
Liniowe przeszukiwanie zbioru
Przeszukujemy element po elemencie. Algorytm-czy dany ciąg zawiera poszukiwany przez nas element? Lista kroków przeszukiwania liniowego z wartownikiem :
DANE: Zbiór elementów dany w postaci ciągu i y- poszukiwany element
WYNIK: Jeśli y należy do zbioru ,to podaj jego miejsce w ciągu ,a w przeciwnym razie sygnalizuj brak takiego elementu w zbiorze
KROK 1: (utworzenie wartownika na końcu na końcu ciągu).Utwórz na końcu ciągu wartownika i umieść w nim element y.
KROK 2: Dla kolejnego elementu w danym ciągu , jeśli z- y ,to przejdź do kroku 3 ,w przeciwnym wypadku powtórz ten krok.
KROK 3: Jeśli z jest wartownikiem , to zbiór nie zawiera elementu y, w przeciwnym wypadku - miejsce elementu z wskazuje pierwsze wystąpienie elementu y w ciągu .
Czy dany element jest w ciągu , wskazanie jego miejsca w ciągu. Zbiór przeszukiwany musi mieć taka sama nazwę jak projekt. Rekurencja - zaawansowana technika algorytmiczna ,polegająca na wywoływaniu procedury z wnętrza samej siebie .W wyniku rekurencji algorytm zostaje zagnieżdżony .Zakończenie procedury zewnętrznej wykonywane jest wtedy ,gdy zakończy się wywoływana przez nią procedura wewnętrzna.
Lista kroków przeszukiwania liniowego :
DANE: Tablica n liczb całkowitych tab[n]=tab[0],tab[1]…tab[n-1].
WYNIK: Odpowiedź na pytanie czy w tablicy tab znajduje się liczba x
KROK 1: Pobrać pierwszy niezbadany element tablicy n- elementowej
KROK 2: Jeśli pobrany element tablicy jest równy x wpisać `Sukces” i zakończ algorytm.
KROK 3: W przeciwnym wypadku zbadać pozostałą cześć tablicy n-1 elementowej
Warunkiem zakończenia programu jest znalezienie szukanego elementu x albo wyjście poza obszar przeszukiwań. Cechy algorytmu rekurencyjnego :zakończenie algorytmu musi być jednoznacznie określone (element znaleziony lub przekroczenie zakresu tablicy),rozbicie dużego problemu na problemy elementarne o mniejszym stopniu skomplikowania ,które możemy rozwiązać (z tablicy o rozmiarze n przechodzimy do tablicy o rozmiarze n-1)
Podstawowe błędy algorytmów rekurencyjnych : złe określanie zakończeń programu ,niewłaściwa (nieefektywna) dekompozycja problemu.
Lista kroków algorytmu głównego obliczania Silni :
DANE: Liczba naturalna n
WYNIK: Silnia zadanej liczby naturalnej n!
KROK 1: Wczytaj liczbę n
KROK 2: Wywołać funkcje rekurencyjną Silnia dla danego n
KROK 3: Wyprowadź wynik - wartość n!
KORK 4: Zakończ algorytm
Funkcję tę można zdefiniować jako silnia(1)=1, silnia(n)=silnia(n-1)*n
Ciąg Fibonacciego:
DANA: Liczba naturalna k równa 1.
WYNIK: wartość liczby fibonacciego Fk
KROK 1: Jeśli k=1 lub k=2 ,to przyjmij Fk=1 i zakończ algorytm
KROK 2: Przyjmij FIB:=1 oraz FIB2:=1
KROK 3: wykonaj k-2 razy następujące instrukcje przypisania
FIB:=FIB1 +FIB2
FIB2:=FIB1
FIB1:=FIB
KROK 4: Fk =FIB
FRAKTALE
Współczynnik redukcji-określa o ile zostanie pomniejszona figura w czasie procesu.
Zbiór Mandelbrota - Dane: Ciąg liczb zespolonych z0,z1,..., parametr zespolony c. Wynik: Zbiór Mandelbrota. Krok1: Dla każdego pkt-u leżącego wewnątrz kwadratu obliczamy N pierwszych wyrazów (N wystarczająco duże, np. kilkaset i sprawdzamy warunek ograniczoności powstałego zbioru punktów, czyli czy wszystkie wyrazy leżą wewnątrz narysowanego kwadratu. Krok2: Jeżeli TAK to domniemamy, że wszystkie następne punkty też będą leżeć wewnątrz-rysujemy punkt odpowiadający parametrowi c i przechodzimy do następnego punktu. Krok3: Gdy jakikolwiek punkt opuści koło, to przechodzimy do następnego bez żadnej akcji. I tak dalej.
Fraktal Julii - wzór Zn+1=Zn^3+c, zakładamy że I element nie jest 0. Dane: Ciąg liczb zespolonych z0,z1,…, parametr zespolony c. Krok1: Rysujemy układ współrzędnych. Krok2: Wybieramy zakres zmian jego zawartości, rysując w układzie zadany kwadrat. Krok3 : Dla każdego punktu zawartego w tym kwadracie obliczamy L pierwszych wyrazów ciągu z0,z1,z2 Krok4: Jeśli wszystkie L wyrazów mieści się wewnątrz koła-stawiamy punkt o współrzędnych rozważanego punktu z0 i przechodzimy do następnej wartości z0 i przechodzimy do następnej wartości z0. Krok4: Jeżeli warunek ten nie jest spełniony, to przechodzimy do następnej wartości z0 bez rysowania punktu.
DEREKURSYWACJA
Wadą większości funkcji rekurencyjnych jest intensywne wykorzystanie stosu ,który służy do przechowywania rekurencyjnych odwołań tej samej funkcji. Oprogramowanie tworzone jest w oparciu o eleganckie algorytmy rekurencyjne .Wersja końcowa (użyta w praktycznym zastosowaniu) powstaje wyniku transformacji algorytmu rekurencyjnego na iteracyjny
Zaletą transformacji jest jej pełna równoważność funkcyjna tzn. prawidłowo działający algorytm rekurencyjny po przetransportowaniu na algorytm iteracyjny dalej działa prawidłowo. Procedura iteracyjna jest równoważna procedurze rekurencyjnej P, jeśli wykonuje dokładnie to samo zadanie co P ,dając identyczne rezultaty. Wywoływanie rekurencyjne procedury P jest zwane terminalnym ,jeśli nie następuje po nim już żadna instrukcja tej procedury. Procedury P1 i P2 są wzajemnie równoważne pod warunkiem że P1 zawiera tylko jedno rekurencyjne wywołanie terminalne.
ALGORYTMY SORTUJĄCE
Za efektywność algorytmów sortujących przyjmuje się liczbę porównań wykonywanych między elementami danych.
Bąbelkowe - polega na porządkowaniu ciągów, kóra polega na przestawianiu sąsiednich par elementów znajdujących się w nieodpowiedniej kolejności, przy czym ciąg jest tak długo przeglądany w tym samym kierunku tak długo, jak może w nim wystąpić jeszcze para elementów o niewłaściwym porządku. Dane: liczba naturalna n i ciąg n liczb x1,x2.. Wynik: Uporządkowanie tego ciągu liczb od najmniejszej do największej. Krok1: Kres:=n {kres określa miejsce w ciągu stanowiące granicę poszukiwania pary elementów do przestawienia} Krok2: Przyjmij i:=1 oraz k:=0 {k jest wskaźnikiem przestawnej pary} Krok3: Dopóki i<Kres, wykonaj: jeśli xi>xi+1, to przestaw te elementy przyjmij k:=i , zwiększ i:=i+1. Krok4: Jeśli k>1, to przyjmij kres:=k i wróć do kroku 2, w przeciwnym razie zakończ algorytm.
Przez wybór - wybieramy I element, wstawiamy go na początku, zmniejszamy zbiór i. Dane: Liczba naturalna n i ciąg n liczb:x1,x2..xn Wynik: Uporządkowanie. K1: Dla i=1,2,..,n-1 wykonaj kroki 2,3. K2: Znajdź k takie że xk jest najmniejszym elementem w podciągu x1,..xn. K3: Zamień miejscami elementy xi oraz xk. Liczba przestawień algorytmu: [(n-1)n]/2
Kubełkowe (koszykowe) - Przykład sortowanie liter. K1: umieszczenie liter w kubełkach. K2: Ciąg liter po opróżnieniu kubełków.
Pozycyjne - stanowi rozszerzenie sort. Kubełkowego na porządkowanie całych słów przyjmuje się porządek leksykograficzny lub słownikowy.
Przez wstawianie -. Sortowanie przez wstawianie- algorytm rozpoczyna się od porównania dwóch pierwszych elementów sortowanej tablicy tab, którymi są tab[0] i tab[1] , jeśli nie są one ustawione we właściwej kolejności, to następuje zamiana miejsc. Następnie jest rozważany trzeci element tab[2], jeśli jest mniejszy niż tab[0] i tab[1] to te dwa elementy są przesuwane o jedna pozycję w prawo tab [0] umieszczamy na pozycji ,1, tab[1] na poz. 2, a tab[2] na poz. 0. Jeśli element tab[2] jest mniejszy niż tab[1] ale większy niż tab[0] to tab[1] wędruje na pozycję 2, jego miejsce zajmuje tab[2]. Jeśli tab[2] jest większy od tab[0] i tab[1] to pozostaje na swojej pozycji
Złożoność całkowita i częściowa algorytmu
WP- warunek początkowy-formuła logiczna definiująca dane wejściowe algorytmu
WK- warunek końcowy-formuła logiczna definiująca dane wyjściowe algorytmu uzyskane dla danych wejściowych spełniających WP
Definicje
Algorytm A jest częściowo poprawny wzglądem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek Wp, jeżeli algorytm A zatrzymuje się to dane wyjściowe algorytmu spełniają warunek WK
Algorytm A jest całkowicie poprawny- definicja wyżej, ale bez słowa „jeżeli”.
Przykład:
WP: n>0 i n należy do N
WKs=1+3+5+...+n i n mod 2<>0 lub
S=1+3+5+...+n-1 i n mod 2=0
Algorytm
S:=0 i i:=0
While i<>n+2 do
Begin
s:=s+i
i:=i+2
end
Algorytm jest poprawny częściowo, ponieważ gdy n jest parzyste - zapętla się
Złożoność obliczeniowa to ilość zasobów komputerowych potrzebnych do jego wykonania
Złożoność obliczeniowa-złożoność algorytmu, miara jakości algorytmu wyrażana liczbą wykonywanych w nim elementarnych operacji, takich jak +-* lub porównanie .Zbliżone do złożoności obliczeniowej jest pojęcie efektywności, czyli czasu działania wykonującego algorytm programu komputerowego.
Złożoność czasowa-czas działania algorytmu, wyrażony liczbą jego operacji
Złożoność asymptotyczna- oszacowanie dla dostatecznie dużych danych wejściowych tylko rzędu wielkości liczb.
Złożoność pamięciowa- zapotrzebowanie algorytmu na pamięć, wyrażona liczbą koniecznych do jego działania jednostek informacji
Złożoność czasowa pesymistyczna- ilość wykonywanych operacji elementarnych dla danych „najgorszego” przypadku.
Złożoność czasowa oczekiwana- ilość wykonywanych operacji elementarnych dla danych „typowego” przypadku.
Definicja
Oznaczenia:
Dn- zbiór zestawów danych wejściowych rozmiaru n
t(d)- liczba operacji elementarnych wykonywanych dla danych wejściowych ”d”
pr(d)-prawdopodobieństwo, że dane ”d” są danymi wejściowymi algorytmu
Pesymistyczna złożoność czasowa algorytmu to funkcja(max-to kres górny zbioru)
Tmax(n)=max{t(d):d należy do Dn}
Oczekiwana(średnia) złożoność czasowa algorytmu to funkcja
Tśr(n)=E(d należy do Dn) pr(d).t(d)
Tym, czy funkcje Tmax i Tśr(n) są reprezentowane dla wszystkich danych wejściowych rozmiaru n decydują miary wrażliwości algorytmu.
Miara wrażliwości pesymistycznej
Delta(n)=max{t(d1)-t(d2):d1,d2 należy do Dn}
Miara wrażliwości oczekiwanej
Sigma(n)=dev(Xn)
Gdzie dev(Xn)-odchylenie standardowe zmiennej losowej „xn” dev(Xn)=sqrt(var(Xn))
Var(Xn)-wariacja zmiennej losowej „Xn” var(Xn)=E(k>0)((k-are(Xn))^2 pr(d))
Are(Xn)wartość oczekiwanej zmiennej losowej Xn
Twierdzenie:
Im większe są wartości delta(n) i sigma(n), tym algorytm jest bardziej wrażliwy na dane wejściowe i tym bardziej jego zachowanie w wypadku rzeczywistych danych może odbiegać od zachowania opisanymi funkcjami pesymistycznej i oczekiwanej złożoności czasowej.
Przykład- przeszukiwanie sekwencyjne ciągu
Begin
i:=1;
L[N+1]:=a;
While L[j]<>a do
j:=j+1
if j<=N then p:=j
end
Rozmiar danych wejściowych- |d|=n
Operator porównania-L[j]<>a
Pesymistyczna złożoność czasowa- Tmax(n)=n+1
Pesymistyczna wrażliwość czasowa- delta(n)=n
Wyznaczanie oczekiwanej złożoności czasowej
Pr(d)=1/n; t(d)=k dla k=1,2,...,n
Wówczas oczekiwana(średnia) złożoność czasowa
Tśr(n)=E(od k=1 do n) pr(d)*t(d)=1/nE(od k=1 do n) t(d)= 1/nE(od k=1 do n) k
Tśr(n)=n(n+1)/2n =n+1/n
f(d)- liczba operacji elementarnych wykonanych dla danych wejściowych „d”
pr(d)- prawdopodobieństwo, ze dane d są danymi wejściowymi algorytmu
Wariacja zmiennej losowej Xn(are-wartość oczekiwana; Tśroczekwiana złożoność czasowa; p.(d)-prawdopodobieństwo)
Var(Xn)=E(od k>=0) (k-are(Xn))^2 pr(d)
Var(Xn)=E(od k>=0) (k-are(Xn))^2 pr(d)=1/n[(n(n+1)(n+2)/6)-(2(n+1)(n+1)n/2)+ n(((n+1)/2)^2)]=n^2/12
Miara wartości oczekiwanej: sigma(n)=dev(Xn)
Odchylenie standardowe zmiennej losowej Xn
Dev(Xn)=sqrt(var(Xn))
Stąd sigma(n)=sqrt(var(Xn))=~sqrt(n^2/12)=~0.29n
Funkcje wrażliwości powyższego algorytmu jak i funkcje jego złożoności są liniowe stąd duża wrażliwość liczb operacji.
RZĄD FUNKCJI
Funkcja f jest:1) co najwyżej rzędu g: f(n)=O(g(n)): 2) co najmniej rzędu g f(n)=Ω(g(n)), jeśli funkcja g jest co najwyżej rzędu f g(n)=O(f(n)) 3) dokładnie rzędu g, co zapisujemy jako f(n)=Θ(g(n)) jeśli zarówno f(n)=O(g(n)) jak i f(n)=Ω(g(n)) 4) jest asymptotycznie równoważna g, co oznaczamy jako f(n)≈g(n)
Rząd wielkości dwóch funkcji f(n) i g(n) mogą być porównywane przez obliczenie granicy E=lim[f(n)/g(n)]. Jeśli E=+∞, to g(n)=O(f(n)). Jeśli E=c>0 to f(n) ≈g(n). Jeśli E=0, to f(n)=O(g(n)).
Rodzaje złożoności czasowej:
-logarytmiczna: logn np. przeszukiwanie binarne (zadanie rozmiaru n zostaje sprowadzone do n/2)
-liniowa: n np. alg. Hornera (występuje stała liczba działań dla każdego z n-elementów wejściowych)
-liniowo-logarytmiczna: nlogn np. sort. Przez scalanie
-kwadratowa n^2 np. podwójna instr. iteracyjna (zł wielomianowa:n^3, podwykładnicza n^logn
-wykładnicza 2^n (stała liczba działań dla każdego podzbioru danych wejściowych)
-wykładnicza n! (stała liczba działań dla permutacji danych wejściowych)
Dziel i rządź: 1 Podzielić problem na podproblemy. 2 Znalezienie rozwiązania podproblemów. 3 Połączenie rozważanych podproblemów w rozwiązanie głównego problemu.
Sortowanie przez scalanie
Rekurencyjny algorytm sortowania wdrażający metodę dziel i zwyciężaj w sposób następujący:
n - elementowy ciąg dzieli się na dwa n/2 elementowe
otrzymane ciągi sortuje się używając rekurencyjnie sortowanie przez scalanie
na każdym poziomie scala się posortowane podciągi w jeden posortowany podciąg
zł. Sortowania przez scalanie wynosi 0 (nlogn)
lista kroków scalania dwóch ciągów uporządkowanych
DANE: dwa uporządkowane ciągi x,y
WYNIK: uporządkowany ciąg z będący scaleniem ciągów x,y
KROK 1: dopóki oba ciągi x i y nie są puste wykonuj następującą operacje:
przenieś mniejszy z najmniejszych elementów z ciągów x i y do nowego ciągu z
KROK 2: do końca ciągu z dopisz elementy pozostałe w jednym z ciągów x lub y
pseudokod w Pascalu
begin
if rozmiar >=z then
{podziel dane na dwie części}
{posortuj rekurencyjnie ciągi}
{scal oba}
Endif
End
- Lista kroków algorytmu porządkowania przez scalanie (i,p,x)
Dane: Ciąg liczb (Xi, Xi+1,X….,XP)
Wynik: uporządkowanie powyższego ciągu liczb od najmniejszej do największej
Krok 1: jeśli l<p to przyjmij x:=(l+p)dir2 wykonaj następne 3 kroki
Krok2: zastosuj ten sam algorytm dla (l,x,y)
Krok3: zastosuj ten algorytm dla (x+1,p,x)
Krok4: zastosuj algorytm scalania da ciągu X1 …..Xp
Sortowanie przez scalanie działa odwrotnie niż sortowanie kubełkowe ponieważ skupia się na łączeniu a nie na dzieleniu elementów w tym przypadku polega na podziale danych na 2 części
Liczba porównań t(n)
Zależność rekurencyjna
t(n) = 0 n=1
= 1 n=2
=2t(n/2)+(n-1) n>2
Gdy n =1 nie wykonujemy żadnego porównania
Gdy n=2 dokonujemy jednego porównania podczas scalania ciągów jedno elementowych
Gdy n>2 wykonujemy 2 razy porządkowanie tą samą metodą ciągów o połowę krótszych oraz scalamy te ciągi , wykonując co najwyżej n-1 porównań
T(n/2)=2t(n/4)+(n/2-1)
Algorytm sortowania szybkiego
W przypadku te metody sortowania jest wykorzystywana metoda dziel i zwyciężaj
- przypuśćmy że potrafimy podzielić dany ciąg na dwie takie części że elementy pierwszego ciągu są mniejsze od elementów drugiego ciągu czyli nie formalnie mówiąc na elementy małe i duże
-mając taki podział ciągu możemy każda z części uporządkować osobno(pomińmy na razie w jaki sposób to zrobić)
- otrzymamy ciąg składający się z uporządkowanych elementów małych a po nich następny z uporządkowanymi elementami dużymi czyli cały ciąg jest już uporządkowany
Quicksort - szybki algorytm sortowania jest realizowany w szeregu bibliotek
Algorytm ten polega na podziale uporządkowanego ciągu elementów r na dwie takie części, że w jednym znajdują się liczby nie większe niż r a w drugiej liczby nie mniejsze niż r
Następnie element r umieszczamy miedzy tymi podciągami i przechodzimy do sortowania obu podciągów tą sama metoda.
Kolejne wyniki wywołań rekurencyjnych - każdy następny wiersz zawiera o jeden element więcej, który w następnej iteracji zostanie wybrany do podziału i zajmuje swoją stałą pozycje w porządkowanym ciągu.
Lista kroków algorytmu szybkiego sortowania
DANE: ciąg liczb X1,Xi+1,…,Xp
WYNIK: uporządkowany ciąg od najmniejszego do największego
KROK 1: jeżeli l<p to przyjąć za element podziału r:=Xp podzielić tym elementem dany ciąg element r znajdzie się na pozycji elementu Xk dla pewnego K (l<=k<=p) i elementy na lewo będą od niego większe a na prawo nie mniejsze
KROK 2: zastosować ten sam algorytm dla podciągu (l,k-1,x)
Krok 3: zastosować ten sam algorytm dla podciągu (y,k+1,p)
Ze względu na właściwości metody dziel i zwyciężaj element do podział powinien zapewnić podział ciągu na prawie dwie równe części - mediana. Nie znajduje jednak szybki algorytm znajdowania mediany
Drzewo binarne jest kopcem, jeśli każdy element jest większy lub równy niż elementy w drzewie leżące pod nim na poziomach wyższych
Bardzo ważna procedurą w algorytmie, który chcemy opisać jest przywracanie własności kopca dla pewnego elementu a[i] przy wywołaniu tej procedury zakłada się że drzewa zaczepione w lewym i prawym szyku wierzchołka zawierającego a[i] są kopcami. Po zakończeniu działania procedury, drzewo zaczepione w wierzchołku zawierającym[i] będzie spełniać własności kopca
Lista kroków sortowani stogowego
Dane: a[1.n] będącą kopcem, wobec tego element a[1] jest maksymalny
Wynik: uporządkowanie powyższej tablicy
Krok 1: niech m oznacza ostatni element kopca na początku kopiec obejmuje całą tablice wiec m=n
Krok 2: zamień ze sobą elementy a[1] i a[m]
Krok 3: zmniejsz M o 1
Krok 4: przywróć własności kopca dla tablicy a[1…m]
Krok 5: wróć do kroku 2
Grupy - właściwości algorytmów sortowania
Algorytmy wynikające z definicji problemu
-Algorytm bąbelkowy
-Algorytm sortowania przez wybór
Algorytmy wykorzystujące drzewa
Algorytmy oparte na technice dziel i zwyciężaj
- przez umieszczanie
- przez scalanie
- alg szybkiego sortowania
Algorytmy wykorzystujące wartości początkowych elementów
-kubełkowe
-sortowanie w miejscu - nie jest wykorzystywana dodatkowa pamięć (zapis w tym samym miejscu gdzie ciągi do scalenia)
Algorytmem działającym w miejscu można porządkować w tej samej pamięci operacyjnej dwa razy dłuższe ciągi niż algorytmem porządkowania przez scalanie)
SORTOWANIE STABILNE
Stabilnymi algorytmami nazywamy algorytmy w których jeśli 2 elementy w porządkowanym ciągu mają taka samą wartość pewnej cechy , wg której odbywa się porządkowanie to ich kolejność względem siebie w uporządkowanym ciągu jest taka sama jak w danym ciągu danym do posortowania
Złożoność i efektywność algorytmu sortowania
1 algorytmy w których liczba porównań jest proporcjonalna do kwadratu liczby elementów n^2
1 sortowanie bąbelkowe
2 przez umieszczanie (l.por<n^2 ale l. przestawień może być tego rzędu)
3 algorytm szybki
Algorytm w których liczba porównań i zamian jest proporcjonalna do nlogn - alg przez scalanie
Od wyboru właściwej struktury danych zależy
- szybkość działania algorytmu
- możliwość jego modyfikacji
- czytelność zapisu algorytmu
Przez DANA rozumiemy uporządkowaną parę <n,i> której pierwszym elementem jest nazwa danej a drugim jej wartość
Wartość
- wartości prostych - niepodzielne
- wartości złożonych - są strukturami ( uporządkowanymi zbiorami danych których wartości mogą być wartościami prostymi lub klejonymi wartościami złożonymi
Uznanie wartości za wartości proste jest w pewnym sensie zależne od celów danego przetwarzania
Dana d=<n,r> nazywamy dana elementarna, jeżeli r jest wartością prostą. Dane elementowe są najmniejszymi adresowalnymi jednostkami informacji.
Dane, które nie są danymi elementami nazywamy danymi złożonymi
Lista - uporządkowany ciąg elementów, przykładami list są wektory lub tablice jednowymiarowe. W wektorach mamy dostęp do elementu poprzez podanie indeksu elementu. Lista to liniowo uporządkowany zbiór elementów z których dowolny element można usunąć lub dodać w dowolnym miejscu, pierwszy i ostatni element listy nazywamy końcami listy. Szczególne przypadki list Stos i kolejka.
Listy dzielą się na: posortowane i nieposortowane.
Lista jednokierunkowa jest oszczędną pamięciowo strukturą danych pozwalającą grupować dowolną - ograniczoną ilość dostępnej pamięci. Do budowy list jednokierunkowej używane są dwa typy komórek pamięci. Pierwszy jest zwykłym rekordem natury informacyjnej, drugi jest rekordem lecz ma on charakter roboczy.
Własności listy jednokierunkowej: Jeżeli list jest pusta to struktura informacyjna zawiera dwa wskaźniki null.
Podczas dołączania nowego elementu do listy jednokierunkowej możliwe są dwa podejścia: Listę traktujemy jako worek; lista jest nieuporządkowana; nowe elementy będą na liście we właściwej kolejności.
Dodawanie elementu do listy jednokierunkowej posortowanej:
Nowy element może zostać wstawiony na początek, koniec lub w środku listy posortowanej; należy znaleźć miejsce wstawienia;
Dekrementacja- jest to usuwanie ostatniego elementu z listy jednokierunkowej.
Listy dwukierunkowe: maja dwa wskaźniki co przyspiesza wszystkie operacje.
Stos- liniowa struktura danych dostępna do zapisywania, odczytywania tylko końca wierzchołka. Struktura LIFO.
Operacje na stosie: initializa, opróżnienie stosu, empty sprawdzenie stosu czy jest pusty, full- sprawdzenie stosu czy jest zapełniony, push- umieszczenie elementu na stosie, pop- zdjęcia najwyższego elementu ze stosu.
Kolejka- lista elementów zwiększająca się przed dodawanie elementu na jej końcu, a malejąca przy wyjmowaniu elementu z początku, FIFO
Operacje na kolejce: initializa, opróżnienie kolejki, empty sprawdzenie stosu czy jest pusty, full- sprawdzenie kol czy jest zapełniony, push- umieszczenie elementu w kolejce, pop- zdjęcie najwyższego elementu z kolejki. Enq- powoduje umieszczenie elementu na końcu kolejki, deq- usuniecie pierwszego elementu. Jedna z możliwych implementacji kolejki jest tablica.
Kolejka priorytetowa- elementy w kolejce maja różne priorytety
Kopiec (ang. heap) to drzewo binarne o następujących cechach:
klucze potomków węzła są w stałej relacji z kluczem rodzica, drzewo jest prawie pełne tzn. liście występują na ostatnim i ewentualnie przedostatnim poziomie w drzewie, liście na ostatnim poziomie są ściśle ułożone od lewej do prawej.
Dwukopiec- swoja budowa przypomina kopiec, posiada dwóch potomków i dwóch przodków, na pierwszym miejscu jest korzeń, interpretacja- tablica, kopiec jest drzewem binarnym
Lista incydencji
Lista krawędzi - jest to lista, na której przechowujemy wszystkie krawędzie występujące w grafie.
Macierz incydencji to tablica o rozmiarach V*E. Składa się z E kolumn i V wierszy
- jeśli krawędź wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie l-1
-jeśli do niego wchodzi piszemy l+1
jeśli wierzchołek nie należy do krawędzi piszemy 0
jeśli jest to pętla własna piszemy 2
Macierz grafu: tablica o rozmiarach (V+2)^2. Wierzchołki i krawędzie numerujemy od 0 do v+1
CYKL EULERA w grafie.
Cykl l- droga która zaczyna się i kończy w tym samym wierzchołku l, który zawiera każda krawędź dokładnie raz.
Łańcuchem Eulera w grafie nazywamy drogę który zawiera każda krawędź dokładnie raz
Warunki istnienia C.EULERA:
- graf musi być spójny (musi istnieć droga łącząca każdą parę wierzchołków) i skierowany (wektory)
- jeżeli graf jest spójny i niekierowany, to liczba wychodzących krawędzi z każdego wierzchołka musi być parzysta.
MINIMALNE DRZEWO ROZPINAJACE
Niech będzie dany spójny graf nie skierowany o wierzchołkach v i krawędziach E.
Ponad to z każdą krawędzią będzie związana także waga określana przez funkcje, która oznacza długość danej krawędzi
Jeżeli znajdziemy taki podział T zawarty w zbiorze krawędzi E, który łączy wszystkie wierzchołki i taki, ze suma wszystkich wag krawędzi wchodzących w skład T jest możliwie najmniejszy, to znajdziemy tzw. min. drzewo rozpinające.
METODA ZACHLANNA
Jeżeli mamy dana kombinacje danych, które mogą być rozwiązaniem danego problemu można się posłużyć metoda zachłanna, Polega na rozpatrywaniu danych w kolejności uporządkowanej np. posortowane. W danym kroku wybierane SA te dane, które SA najodpowiedniejsze.
ALG. KRUSKALA
Polega na łączeniu wielu poddrzew w jedno za pomocą krawędzi o najmniejszej wadze. W rezultacie powstałe drzewo będzie minimalne. Algorytm oparty jest na metodzie zachłannej
Kroki dla K;
-posortować wszystkie krawędzie w porządku niemalejącym
-tworzenie drzewa - rozrastanie lasu drzew
-wybieramy krawędzie o najmniejszej wadze i jeśli wybrana krawędź należy do dwóch różnych drzew należy je scalić (dodać do lasu)
-krawędzie wybieramy tak długo Az wszystkie wierzchołki nie będą należały do jednego drzewa
ALG. PRIMA
W alg. prima zawsze dodajemy do drzewa krawędź o najmniejszej wadze, osiągalną (w przeciwieństwie do Kruskala) z jakiegoś wierzchołka tego drzewa. Po każdym dodaniu krawędzi lista musi być posortowana.
Kroki dla P:
- budowę minimalnego drzewa rozpinającego zaczynamy od dowolnego wierzchołka
- dodajemy wierzchołek do drzewa a wszystkie krawędzie incydentne umieszczamy na posortowanej wg. wag liście
- następnie zdejmujemy z listy pierwsza krawędź (o najmniejszej wadze)
- sprawdzamy czy drugi wierzchołek tej krawędzi należy do tworzonego drzewa:
- jeśli tak - nie dodajemy jej, porzucamy i pobieramy z listy następna.
- jeżeli nie - dodajemy krawędź
- następnie dodajemy do posortowanej listy wszystkie krawędzie incydentne z dodanym wierzchołkiem i pobieramy z niej kolejny element
CYKL HAMILTONA
Graf go posiada jeśli istnieje w nim cykl droga, która zaczyna się i kończy w tym samym wierzchołku), który zawiera każdy wierzchołek dokładnie raz.
GRAFY
Stopień wierzchołka - l. krawędzi do niego przyległych
Graf regularny - w którym każdy wierzchołek ma taki sam stopień
Graf planarny - w którym można przedstawić na płaszczyźnie tak, by żadne dwie krawędzie się nie przecinały
f - graf - z ograniczonym stopniem wierzchołka tzn. jego stopień nie może być większy niż f.
Graf prosty - bez pętli własnych i krawędzi równoległych.
Niezmiennik grafu - to liczba lub ciąg liczb który zależy tylko od struktury grafu a nie od sposobu jego poetykietowania (np. liczba wierzchołków, liczba krawędzi)
Liczba chromatyczna grafu - to najmniejsza liczba kolorów potrzebnych do pokolorowania wierzchołków grafu tak, by żadne dwa przylegle wierzchołki nie były tego samego koloru.