Algorytm - procura opisująca sposób rozwiązania problemu
Cechy algorytmu
Skończoność (skończona liczba kroków)
Określoność (każdy krok jednoznacznie określa sposób działania)
Dane wejściowe (ilość, typ, zakres)
Dane wyjściowe (wynik konkretnej postaci)
Efektywność
Algorytm Euklidesa (wyznaczyć największy wspólny dzielnik liczb całkowitych m ,n )
Problem
Algorytm
E1 (wyznaczenie reszty z dzielenia m przez n )
E2 Sprawdzamy resztę z dzielenia. Jeżeli r=0 to kończymy algorytm i n jest największym wspólnym dzielnikiem. Jeżeli r =/ 0 to
E3 podstawiamy za m wartość n , za n resztę r i przechodzimy do E1
M, n
M=k*n+r
K iloraz, r reszta 0<=r<=n
W tym algorytmie m się zmniejsza co z kolei prowadzi do zmniejszenia r. W konsekwencji r będzie 0 co skończy algorytm.
Zapis algorytmu
Opisowy - opisujemy słownie każdy krok postępowania
Schematy blokowe
W postaci programu w „pseudo-języku”
Dane Typy danych
Typ danych proste (obiekt reprezentuje pojedynczą daną)
złożone ( strukturę, zbiór danych)
typy standardowe (integer - dokładne operacje, real - obiekty rzeczywiste, boolean - logiczny typ, char - znaki )
typ wyliczeniowy, typ okrojony, tablice, recordy, zbiory, pliki
Każdy typ określa rodzaj operacji jaki można wykonać na danym typie.
Algorytmy sortowania
Dany jest ciąg wejściowy a1,a2,...,an. Dana jest funkcja porządkująca f. Sortowanie polega na ustawieniu elementów ciągu wejściowego w sposób ak1,ak2,..akn, gdzie f(ak1)<=F(ak2)
Mamy sortowanie : wewnętrzne tablice (dostęp do wszystkich elementów naraz), zewnętrzny pliki (nie ma t.dostępu)
Sortowania wewnętrzne sortowanie tablic. W ramach działania na jednej tablicy otrzymamy tą samą tablice uporządkowaną.
Metoda sortowania przez proste wstawianie a1,a2,...ai-1,(wynikowy) | ai ,.....an;(źródłowy). Ciąg dzielimy na dwie części :ciąg źródłowy i wynikowy. Element ai wstawiamy do ciągu wynikowego. Pierwszy element ciągu źródłowego wstawiany jest poprawnie w ciąg wynikowy.
Np. 5, 7, 3, 12, 9
5, 7, 3, 12, 9
3, 5, 7, 12, 9
3, 5, 7, 12, 9
3, 5, 7, 9, 12
Analiza algorytmu przez proste wstawianie. Po - porównań. Pr - liczba przestawień elementów tablicy. W i-tym przebiegu liczba porównań wynosi -co najwyżej i-1 (wtedy gdy dane są w odwrotnej kolejności). - co najmniej 1 (gdy dane są uporządkowane). - średnio i/2 (przy ciągu losowym). Liczba przesunięć wynosi Po1+2
Pomin=1,Pomax=1/2(n^2-n), Pośred=1/4(n^2+n-2),Pr.max=1/2(n^2+3n-4),Prmin=2(n-1),Prśred=1/4(n^2+9n-10). Obliczenia te są potrzebne by zdecydować się jaki algorytm jest najefektywniejszy do danego ciągu.
Sortowanie przez proste wybieranie - z ciągu ai,ai+1,..an wybieramy element najmniejszy i zamieniamy go z elementem a1.Analiza - liczba porównań (nie zależy od danych wejściowych) Po=n(n+1)/2. - liczba przestawień Pr=3(n-1),Prmax=3(n-1)+n^2/4.Sortowanie przez prostą zamiane(bąbelkowe) dany jest ciąg (n-1) razy powtarzamy przeglądanie tabeli wymieniając elementy ai-1 z a1 dla i=2....n. Poprawa algorytmu do sortowania bąbelkowego 1 - sprawdzenie czy w trakcie przebiegu dokonano jakiejś zamiany i jeżeli nie eto zakończenie elementu. 2 - Zapamiętanie indeksu ostatniej zamiany i przeprowadzenie następnego przebiegu tylko od tego elementu. 3 - zamiana kierunku kolejnych przejść ciągu. Grupa algorytmu. DZIEL I ZWYCIĘŻAJ 1 - Sortowanie przez podział (quicksort) a) procedure quicksort (l,p : index); procedura wywołana z parametrami opiera się na dwóch algorytmach - algorytm podziału. - posortowanie podzbiorów otrzymanych w wyniku podziału. Założenia algorytmu podziału - losowo wybieramy z elementów ciągu. - procedura podziału musi rozbić wektor danych na dwa podzbiory, tak że aj >= ai , i=1,2,3,...j-1 aj<=a1 i = j+1 ,j+2,...n. Założenia algorytmu posortowania - wywołany podział dla wektorów a1,....aj-1, aj+1,.....,an. Sortowanie przez łączenie niech dany będzie ciąg a1,a2,....,an połączymy dwa posortowane wektory. Założenia 1 - dzielimy ciąg na dwie części, 2 - łączymy ze sobą te części składając pojedyncze elementy w pary uporządkowane, 3 - powtarzamy łączenie w ten sposób, że łączymy ciągi dwuelementowe, później czteroelementowe. Sortowanie przez zliczanie tablica zlicza liczby całkowite, - wymaga dodatkowej pamięci. Niech dany będzie ciąg wejściowy a1,a2,...,an. Niech k=max(a1,a2,..an). przez b1,b2,..,bn oznaczamy tablicę wyjściową. Natomiast c1,c2,..ck tablice pomocniczą. 1 - zerujemy tablicę c,2 - wypełniamy tablice c ilościami powtórzeń każdego elementu,3 - wyznaczamy dla każdego i=1,2,....,k ile elementów jest mniejszych lub równych i,4 - wszystkie elementy aj zostają umieszczone w tablicy wynikowej b1,b2,....,bn. Przeszukiwanie tablic 1)liniowe (przeglądamy element po elemencie tablicy danych i robimy porównanie z dany elementem aż do znalezienia szukanego elementu lub osiągnięcia końca tablicy),2 - metoda binarna (tablica musi być posortowana a1<=a2. Losujemy k z zakresu 1..n (dzielimy ciąg na dwa podciągi) porównujemy wartość x z elementem ak (wiadomo, w którym podciągu należy szukać x) i przeprowadzamy procedurę dla ciągu a1..ak lub ak,ak+1 ...an. Statystyki pozycyjne w uporządkowanym zbiorze n elementowym i-ty co do wielkości element nazywamy i-tą statystyką pozycyjną. Medianą nazywamy środkowy element zbioru gdy n- nieparzyste to mediana jest 1+n/2, gdy parzyste to istnieja dwa mediany n/2 statystyka pozycyjna n/2+1 statystyka pozycyjna. Wyznaczanie k-tej statystyki pozycyjnej (Hoare),opiera si na algorytmie podziału z qicksort'a, wywołujemy procedure podziału dla elementu a[k]=x. Otrzymane wyniki podziału wartości i,j są takie ,że a[h]<=x dla h <i, a[h]>=x Dla h >j, i >j. Mogą wystąpić trzy przypadki 1)pozycja x jest mniejsza niż k , wtedy stosujemy algorytm na wektorach a[i],a[i+1],...,a[n],2)pozycja x jest większa niż k wtedy stosujemy algorytm dla a[1],a[2],a[3],...,a[j],3) pozycja x jest równa k wtedy x jest szukaną statystyką. Sortowania zewnętrzne - sortowanie plików 1)koszt dostępu do danych większy niż w przypadku sortowania wewnętrznego, 2)dostęp do danych sekwencyjny - w danym momencie dostęp do pojedynczej danej. Sortowanie przez proste łączenie zakładamy ,że plikiem wejściowym jest c i istnieją dwa pliki pomocnicze a ,b. Wykonujemy operacje rozdzielenia elementów z C na dwa pliki a, b po 2 elementów, następnie wykonujemy operacje łączenia zbiorów uporządkowanych z zachowaniem uporządkowania. 2) sortowanie przez łączenie naturalne. Struktury danych. Typy proste (pod zmienna jest tylko jedna wartość) złożone (zbiory elementów). Listy jest skończonym ciągiem elementów (tzw.węzły) l=[x1...xn]. skrajne elementy listy są wyróżnione. Podstawowe operacje dla listy to : pobieranie lewego krańca, pobieranie prawego krańca, ustawianie elementów na lewy koniec listy lub prawy koniec, usuwanie elementów z prawego albo lewego końca listy. Stos z listy usuwany jest elemrnt, który został wprowadzony najpóźniej, usuwanie i pobieranie odbywa ssięz tego samego końca. Kolejka z list usuwany jest element, który został dodany najwcześniej, ustawianie i pobieranie odbywa się z różnych końców listy. Implementacje list - tablice (wielkość listy zadeklarowana przy deklaracji tablicy typ statystyczny) - listy z dowiązaniami (z przydzielaniem pamięci na żądanie i wskazaniem gdzie jest element następny). Lista z dowiązaniami - lista jednokierunkowa (pokazuje gdzie jest kolejny element) - lista jednokierunkowa cykliczna (każdy element gdzie jest kolejny i ostatni) - lista dwukierunkowa (każdy element wie gdzie jest kolejny i poprzedni) - lista dwukierunkowa cykliczna (każdy element pamięta poprzednika i następnika i ostatni wie o pierwszym i odwrotnie). Listy z dowiązaniami listy z dowiązaniami („linked list”) struktura danych w której elementy są ułożone w porządku liniowym, porządek na liście określają wskaźniki związane z każdym elementem.