Algorytm (pochodzenie)



Pobieranie 150,31 Kb.
Data16.12.2017
Rozmiar150,31 Kb.


Algorytm (pochodzenie)

Słowo algorytm pochodzi od brzmienia fragmentu nazwiska: Muhammad ibn Musa al-Chorezmi, arabskiego matematyka i astronoma, żyjącego na przełomie VIII i IX wieku. Jest on uznawany za prekursora metod obliczeniowych w matematyce. Od fragmentu tytułu jego dzieła pochodzi inne słowo, algebra. Upowszechnił on również stosowanie systemu dziesiętnego i posługi-wanie się zerem.

Algorytm (wg M. Sysły)

jest przepisem opisującym krok po kroku rozwiązanie problemu lub osiągniecie jakiegoś celu. Z problemami stykamy się na każdym kroku i aby umieć je rozwiązywać, warto poznać odpowiednie algorytmy. Można wybrać jedną z dróg: spróbować rozwiązać problem samodzielnie lub skorzystać z gotowego rozwiązania. W tym drugim przypadku, gdy wybiera się gotowe rozwiązanie, dobrze jest je zrozumieć. Najczęściej znajdujemy się jednak w sytuacji, gdy dla rozważanego przez nas problemu nie ma w pełni gotowego rozwiązania, a jeśli jest - to mamy kłopoty z jego zrozumieniem. Okazuje się, że najlepszą drogą do tego, by móc rozwiązywać problemy i rozumieć ich rozwiązania, jest poznanie sposobów prowadzących do ich otrzymywania.

Algorytm (wg Niklausa Wirtha)

Programy stanowią skonkretyzowane sformułowania abstrakcyjnych algorytmów na podstawie określonej reprezentacji i struktury danych. Jakiekolwiek decyzje dotyczące struktury danych mogą być podjęte jedynie na podstawie znajomości algorytmów zastosowanych do danych i vice versa, struktura i wybór algorytmów zależą często ściśle od struktury danych.

z Hoare “Notes on data structuring"

Algorytm

algorytm jest pewną ściśle określoną procedurą obliczeniową, która dla właściwych danych wejściowych “produkuje" żądane dane wyjściowe zwane wynikiem działania algorytmu.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

„Wprowadzenie do algorytmów”

Algorytm (T.H. Cormen, Ch.E. Leiserson, R.L. Rivest)

Algorytm jest więc

ciągiem kroków obliczeniowych

prowadzących do przekształcania

danych wejściowych w wyjściowe.

Algorytm (T.H. Cormen, Ch.E. Leiserson, R.L. Rivest)

Algorytm możemy również traktować jako sposób rozwiązania konkretnego

problemu obliczeniowego.

Algorytm (T.H. Cormen, Ch.E. Leiserson, R.L. Rivest)

Postawienie problemu polega na sprecyzowaniu wymagań dotyczących relacji miedzy danymi wejściowymi i wyjściowymi, a algorytm opisuje właściwą procedurę obliczeniową, która zapewnia,

że ta relacja zostanie osiągnięta.

Algorytmika

jest nazwą dziedziny zajmującej się algorytmami i ich własnościami.

Po raz pierwszy tego terminu użył Dawid Harel

w tytule swojej książki

Rzecz o istocie informatyki - algorytmika.

Powstała ona na kanwie pogadanek o algorytmach, prowadzonych przez autora w izraelskim radiu.

Algorytm

Najstarszy algorytm,

to algorytm Euklidesa,

ma ponad 2000 lat.

Algorytm

Wiele innych algorytmów

i metod ich tworzenia opracowano

przed pojawieniem się

pierwszych komputerów.

Algorytm

Wśród prekursorów algorytmów komputerowych poczesne miejsce zajmuje

Ada Augusta (1815-1852),

hrabina Lovelace, córka Byrona.

Algorytm (Ada Augusta Lovelace)

Zachwycona konstrukcją analitycznej maszyny Ch. Babbage'a uważała,

że będzie ona “tkać wzory algebraiczne,

jak krosna Jacquarda tkają liście i kwiaty".

Algorytm (Ada Augusta Lovelace)

Przełomowe znaczenie tej maszyny upatrywała “w możliwości wielokrotnego wykonywania przez nią danego ciągu instrukcji, z liczbą powtórzeń z góry zadaną lub zależną od wyników obliczeń".

Dzisiaj tak określa się podstawowe

cechy algorytmów komputerowych.

Algorytm
podstawa programu

to przepis rozwiązania zadania, zawierający opis danych wraz z opisem czynności, które należy wykonać z tymi danymi, aby osiągnąć zamierzony cel.

Z czego składa się algorytm?


Zawiera on opis danych, opis wyników oraz plan działania, czyli przetworzenia danych. Plan ten można przedstawić w postaci ciągu czynności, które muszą być wykonane w określonej kolejności. Opis czynności występujących w algorytmie nazywamy instrukcjami.

Cechy algorytmów:

- poprawność (algorytm daje dobre wyniki),
- jednoznaczność (daje takie same wyniki przy takich samych danych),
- skończoność (wykonuje się w skończonej ilości kroków),
- sprawność (czasowa - szybkość działania i pamięciowa - "zasobożerność")

Techniki algorytmiczne
(budowanie algorytmów):

  • wybór,

  • powtarzanie - iteracja,

  • rekurencja,

  • przeszukiwanie (liniowe i binarne-połowienie),

  • przeszukiwanie z nawrotami (wyczerpujące),

  • "dziel i zwyciężaj" - funkcje i procedury rekurencyjne

  • metoda zachłanna (otrzymanie jak najszybciej jak najlepszego wyniku).

Etapy rozwiązywania problemów:

  • Sformułowanie zadania

  • Określenie danych wejściowych

  • Określenie celu, czyli wyniku

  • Poszukiwanie metody rozwiązania, czyli algorytmu

  • Przedstawienie algorytmu w wybranej postaci

  • Analiza poprawności rozwiązania

  • Testowanie rozwiązania dla różnych danych. Ocena efektywności przyjętej metody

Sposoby zapisywania algorytmów:

Algorytmy powinny być tak przedstawiane,


aby było możliwe ich jednoznaczne odczytanie i zastosowanie.
Można prezentować je poprzez:

  • opis słowny

  • lista kroków

  • schemat blokowy

  • język programowania

  • metajęzyk

Algorytm liniowy

Ma on prostą postać. Składa się z ciągu instrukcji, które są wykonywane jedna po drugiej w kolejności, jaka wynika z ich następstwa w zapisie algorytmu. Taki algorytm nosi także nazwę algorytmu sekwencyjnego.

Instrukcja warunkowa

W rzeczywistości, większość algorytmów ma bardziej rozbudowaną strukturę. Często występują w nich instrukcje, których wykonanie uzależnione jest od spełnienia pewnego warunku lub też spełnienie pewnego warunku powoduje wykonanie jednej instrukcji, a niespełnienie go -innej. Taką instrukcję nazywamy instrukcją warunkową. Działa ona według jednego z dwóch przedstawionych schematów:

Jeśli spełniony jest warunek W, wykonaj instrukcję A.

Jeśli spełniony jest warunek W, to wykonaj instrukcję A; w przeciwnym razie wykonaj instrukcję B.

Instrukcja A i B opisuje jedną instrukcję lub instrukcję składającą się z ciągu instrukcji wykonywanych sekwencyjnie. Instrukcja warunkowa pozwala dokonać wyboru jednej z dwóch dalszych dróg wykonania algorytmu.

Iteracja

Iteracja to technika algorytmiczna polegająca na wykonaniu tej samej instrukcji dla n zmiennych

Instrukcja iteracyjna


- ze znaną ilością powtórzeń

wielokrotne powtarzanie niektórych instrukcji jest cechą charakterystyczną wielu algorytmów, jednak nie zawsze (tak jak w tym algorytmie) możemy określić dokładnie liczbę powtórzeń. Może ona zależeć od spełnienia pewnych warunków. Wielokrotne powtarzanie instrukcji umożliwiają instrukcje iteracyjne (pętle) . Działa ona według schematu:

Wykonuj instrukcję A dokładnie n razy.

Instrukcja iteracyjna
– ze spełnieniem warunku

Powtarzaj wykonywanie instrukcji A aż do spełnienia warunku W.

W informatyce możemy realizować szczególny rodzaj powtórzeń bez konieczności stosowania pętli.
Jest to technika rekurencji .

O rekurencji mówimy wtedy, gdy definiując pojęcie odwołujemy się do niego samego

Schemat blokowy to graficzny zapis algorytmu rozwiązania zadania, przedstawiający opis i kolejność wykonywania czynności realizujących dany algorytm.

Przykłady skrzynek do prezentacji algorytmu w postaci graficznej

Zasady budowania schematu blokowego:

  • Każda operacja jest umieszczona w skrzynce schemat ma tylko jedną skrzynkę "Start" i przynajmniej jedną skrzynkę "Stop"

  • Skrzynki są ze sobą połączone

  • Ze skrzynki wychodzi jedno połączenie; wyjątek stanowią skrzynki "Stop" (z której nie wychodzą już żadne połączenia) oraz "warunkowa" (z której wychodzą dwa połączenia opisane Tak i Nie - w zależności od tego czy warunek jest spełniony czy też nie; można wyjść jedną z dwóch dróg).

Algorytm sortowania

Sortowanie polega na ustawieniu liczb

z danego ciągu w porządku niemalejącym.

Problem ten występuje często w praktyce

i jest źródłem wielu standardowych

metod projektowania i narzędzi

analizy algorytmów.

definicja problemu sortowania

  • Dane wejściowe:

Ciąg n liczb <a1 , a2,, ..., an >.

  • Wynik:

Permutacja (zmiana uporządkowania)

<a'1, a'2, ..., a'n >

ciągu wejściowego taka, że

a'1 a'2 ... a'n .

Algorytm sortowania

Dla ciągu wejściowego

<31, 41, 59, 26, 41, 58>

wynikiem działania algorytmu sortowania będzie ciąg wyjściowy

<26, 31, 41, 41, 58, 59>

Algorytm sortowania

ciąg wejściowy jest nazywany

“egzemplarzem" problemu sortowania.

Ogólnie, egzemplarz problemu składa się

z określonych danych wejściowych

spełniających wszystkie warunki podane

w opisie problemu.

Optymalność algorytmu sortowania

Optymalność algorytmu w danym zastosowaniu zależy od:

  • liczby sortowanych elementów,

  • stopnia posortowania elementów na wejściu,

  • rodzaju użytej pamięci:

  • RAM,

  • dysk,

  • taśma.

Algorytm sortowania

Algorytm jest poprawny,

gdy dla każdego egzemplarza problemu

algorytm zatrzymuje się i daje dobry wynik.

Mówimy wtedy, że poprawny algorytm “rozwiązuje" zadany problem obliczeniowy.

Zapis algorytmu

Algorytmy będziemy przeważnie zapisywać

w pseudojęzyku programowania,

który jest bardzo podobny do

C, Pascala lub Algolu.

Zapis algorytmu

Pseudojęzyk różni się też tym od “prawdziwego" języka, że nie uwzględnia się tu technik programowania. Problemy abstrakcji danych, modularności i obsługi błędów są często ignorowane w celu uproszczenia opisu algorytmu.

sortowanie przez wstawianie

Jest to efektywny algorytm sortowania dla niewielkiej liczby elementów. Algorytm ten działa w taki sposób, w jaki często ludzie porządkują talię kart. Zaczynamy od “pustej" lewej ręki, po czym bierzemy ze stołu kolejne karty i wstawiamy je we właściwe miejsca w talii kart, trzymanej w lewej ręce. Aby znaleźć właściwe miejsce dla danej karty, porównujemy ją z kartami, które już mamy w ręce, przesuwając się od strony prawej do lewej.

sortowanie przez wstawianie

sortowanie przez wstawianie

Sortowanie przez wstawianie (zapisane w naszym pseudojęzyku) jest przedstawione jako procedura o nazwie INSERTION-SORT, której parametrem jest tablica A[1 . . n] zawierająca ciąg długości n, który mamy posortować. (W pseudojęzyku liczba n elementów tablicy A jest oznaczona przez length[A]). Elementy wejściowej tablicy są sortowane w miejscu, to znaczy, że są one przechowywane cały czas w tej samej tablicy, z wyjątkiem stałej liczby elementów. Kiedy procedura jest zakończona, tablica A zawiera posortowany ciąg wyjściowy.

sortowanie przez wstawianie

  • INSERTION-SORT(A)

  • l for j := 2 to length[A]

  • 2 do key := A[j]

  • 3 { Wstaw A[j] w posortowany ciąg A[1 . . j — 1] }

  • 4 i := j - 1

  • 5 while i > 0 i A[i] > key

  • 6 do A[i + 1] := A[i]

  • 7 i := i - 1

  • 8 A[i + 1] := key

Konwencje metajęzyka

1. Wcięcia odpowiadają strukturze blokowej. Na przykład treść pętli for, która zaczyna się w wierszu l, zawiera się w wierszach 2-8, a treść pętli while, która zaczyna się w wierszu 5, zawiera się w wierszach 6-7, ale nie obejmuje wiersza 8. Nasz styl wcięć odnosi się również do instrukcji if-then-else. Zastosowanie wcięć zamiast normalnych oznaczeń struktury blokowej, takich jak begin i end, znacznie redukuje liczbę detali, zachowując (a nawet podnosząc) klarowność prezentacji.

Konwencje metajęzyka

2. Konstruktory iteracji while, for i repeat oraz warunkowe if, then i else mają tutaj tę samą interpretację co w Pascalu.

Konwencje metajęzyka

3. Tekst w nawiasach klamrowych jest komentarzem.

Konwencje metajęzyka

4. Wielokrotne przypisywanie w formie

i := j := e

oznacza przypisanie zmiennym i oraz j wartości wyrażenia e;

jest ono równoważne przypisaniu:

j := e łącznie z przypisaniem i := j.

Konwencje metajęzyka

5. Zmienne (takie jak i, j oraz key) są lokalne w danej procedurze. Nie używamy zmiennych globalnych bez zaznaczania tego explicite.

Konwencje metajęzyka

6. Dostęp do elementu tablicy odbywa się przez podanie jej nazwy i indeksu żądanego elementu. Na przykład A[i] jest i - tym elementem tablicy A. Notacja „ .. ” służy do wyznaczania podtablicy. Tak więc A[1 .. j] jest podtablicą składającą się z elementów a[1], a[2], ..., A[j].

Konwencje metajęzyka

7. Dane złożone z kilku części są organizowane jako obiekty, składające się z atrybutów lub pól. Konkretne pole jest podane przez nazwę pola, a następnie identyfikator obiektu w nawiasach kwadratowych. Tablica może być na przykład obiektem z atrybutem length mówiącym o liczbie jej elementów. Aby określić liczbę elementów w tablicy A, piszemy length[A]. Sposób użycia nawiasów kwadratowych będzie zawsze jednoznacznie wynikać z kontekstu.

Konwencje metajęzyka

cd 7. Zmienna odpowiadająca tablicy lub obiektowi jest traktowana jako wskaźnik do danych reprezentujących tę tablicę lub ten obiekt. Dla wszystkich pól/obiektu x, przypisanie y := x powoduje f[x] = f[y]. Ponadto jeśli teraz wykonamy f[x] = 3, to w następstwie nie tylko f[x] = 3, lecz także f[y] = 3. Inaczej mówiąc, x i y wskazują na te same obiekty (są tymi samymi obiektami) po przypisaniu y := x.

Czasami wskaźnik na nic nie wskazuje; ma wtedy specjalną wartość nil.

Konwencje metajęzyka

8. Parametry są przekazywane do procedury przez wartość: wywoływana procedura otrzymuje swoją kopię parametrów, a zmiany wewnętrzne tych kopii nie są widoczne przez program wywołujący. Obiekty są przekazywane przez wskaźniki do nich. Jeśli na przykład x jest parametrem procedury, to przypisanie x := y wewnątrz procedury jest niewidoczne na zewnątrz. Jednakże przypisanie f[x] := 3 jest widoczne.

Analiza algorytmów

to dział informatyki zajmujący się szukaniem najlepszych algorytmów dla zadań komputerowych.

Analiza algorytmów

polega między innymi na znalezieniu

odpowiedzi na podane tu pytania:

  • Czy dany problem może być rozwiązany na komputerze w dostępnym czasie i pamięci?

  • Który ze znanych algorytmów należy zastosować w danych okolicznościach?

  • Czy istnieje lepszy algorytm od rozważanego? A może jest on optymalny?

  • Jak uzasadnić, że stosując dany algorytm, rozwiąże się zamierzone zadanie?

Analiza algorytmów

Dokonując analizy algorytmu, zwracamy uwagę na jego poprawność semantyczną, prostotę, czas działania, ilość zajmowanej pamięci, optymalność oraz okoliczności, w jakich należy go używać, a w jakich nie.

Złożoność obliczeniowa

Złożoność obliczeniową algorytmu definiuje się jako ilość zasobów komputerowych, potrzebnych do jego wykonania.

Podstawowymi zasobami rozważanymi w analizie algorytmów są:

  • czas działania,

  • ilość zajmowanej pamięci.

Złożoność obliczeniowa

Na ogół nie jest możliwe wyznaczenie złożoności obliczeniowej jako funkcji danych wejściowych.

(Takich jak:

ciągi,

tablice,

drzewa

czy grafy.)

Złożoność obliczeniowa

Z zestawem danych wejściowych jest związany jego rozmiar, rozumiany

- mówiąc ogólnie -

jako liczba pojedynczych danych wchodzących w jego skład.

Złożoność obliczeniowa

Rozmiar zestawu danych d

będziemy oznaczać przez

|d|.

Złożoność obliczeniowa

Na przykład w problemie :

  • sortowania za rozmiar przyjmuje się zazwyczaj liczbę elementów w ciągu wejściowym,

  • przejścia drzewa binarnego - liczbę węzłów w drzewie,

  • wyznaczenia wartości wielomianu - stopień wielomianu.

Złożoność pamięciowa

za jej jednostkę przyjmuje się zwykle:

słowo pamięci maszyny.

Złożoność czasowa

Sytuacja jest nieco bardziej skomplikowana w wypadku złożoności czasowej.

Złożoność czasowa powinna być własnością samego tylko algorytmu jako metody rozwiązania problemu - niezależnie od:

komputera,

języka programowania

czy sposobu jego zakodowania.

Złożoność czasowa

W tym celu wyróżnia się w algorytmie charakterystyczne dla niego operacje, nazywane operacjami dominującymi -

takie, że łączna ich liczba jest proporcjo-nalna do liczby wykonań wszystkich operacji jednostkowych w dowolnej komputerowej realizacji algorytmu.

Złożoność czasowa

Za jednostkę złożoności czasowej

przyjmuje się

wykonanie jednej operacji dominującej.

Złożoność czasowa

Na przykład dla algorytmów:

  • sortowania za operację dominującą przyjmuje się zwykle porównanie dwóch elementów w ciągu wejściowym, a czasem też przestawienie elementów w ciągu;

  • przeglądania drzewa binarnego przyjmuje się przejście dowiązania między węzłami w drzewie,

  • wyznaczania wartości wielomianu - operacje arytmetyczne +, -, * i /.

Złożoność czasową

algorytmu

traktuje się jako

funkcję rozmiaru danych n

Pesymistyczna złożoność algorytmu

definiowana jest jako:

ilość zasobów komputerowych,

potrzebnych przy “najgorszych”

danych wejściowych rozmiaru n

Oczekiwana złożoność algorytmu

definiowana jest jako:

ilość zasobów komputerowych,

potrzebnych przy “typowych”

danych wejściowych rozmiaru n

Dla precyzyjnej definicji pojęcia pesymistycznej i oczekiwanej złożoności czasowej, wprowadzimy następujące oznaczenia:

  • Dn - zbiór zestawów danych wejściowych rozmiaru n;

  • t(d) - liczba operacji dominujących dla zestawu danych wejściowych d;

  • Xn - zmienna losowa, której wartością jest t(d) dla d Dn;

  • pnk - rozkład prawdopodobieństwa zmiennej losowej Xn, tzn. prawdopodobieństwo, że dla danych rozmiaru n algorytm wykona k operacji dominujących (k  0).

Złożoność czasowa

Rozkład prawdopodobieństwa zmiennej losowej Xn wyznacza się na podstawie informacji o zastosowaniach rozważanego algorytmu.

Gdy na przykład zbiór Dn jest skończony, przyjmuje się często model probabilistyczny, w którym każdy zestaw danych rozmiaru n może się pojawić na wejściu do algorytmu z jednakowym prawdopodobieństwem.

Pesymistyczna złożoność
czasowa algorytmu

definiowana jest jako funkcja:

W(n) = sup { t(d): d Dn },

gdzie sup oznacza kres górny zbioru.

Oczekiwana złożoność
czasowa algorytmu

definiowana jest jako funkcja:

tzn. wartość oczekiwaną E(Xn) zmiennej losowej Xn.

Reprezentatywność W(n) i A(N)

dla wszystkich danych wejściowych

definiowana jest za pomocą:

Miara wrażliwości pesymistycznej

Miara wrażliwości oczekiwanej

(n) = dev(Xn)

gdzie:

  • dev(Xn) jest standardowym odchyleniem zmiennej losowej Xn

  • var(Xn) jest wariancją zmiennej losowej Xn

Przykład: Przeszukiwanie sekwencyjne ciągu

  • Dane wejściowe: L, N, a, gdzie N jest liczbą naturalną N  0, a jest poszukiwanym elementem, L[1 .. N+ l] jest tablicą, w której na miejscach od l do N znajdują się elementy ciągu.

  • Wynik: Zmienna logiczna p taka,

że p = true

a znajduje się w L[1..N]

Algorytm: Przeszukiwanie sekwencyjne ciągu

begin

j := 1;

L[N+1] := a;

while L[j]  a do j := j + 1;

p := j N

end;

Przykład: Przeszukiwanie sekwencyjne ciągu

  • Rozmiar danych wejściowych: n = N

  • Operacja dominująca: porównanie: L[j]  a

  • Pesymistyczna złożoność czasowa: W(n) = n + l

  • Pesymistyczna wrażliwość czasowa: A(n) = n

Jaka jest oczekiwana złożoność czasowa?

A jaka jest oczekiwana złożoność czasowa? Załóżmy, że prawdopodobieństwo znalezienia a na każdym z n możliwych miejsc jest takie samo i wiadomo, że a jest w L[l .. N], tzn. że

pnk=1/N, dla k= l, 2, ..., n

Jaka jest oczekiwana złożoność czasowa?

Przy powyższym założeniu:

Jaka jest oczekiwana wrażliwość czasowa?

Pojęcie typu danych

Typ danych określa zbiór wartości,

do którego należy:

  • stała

  • które może przyjmować zmienna

  • które może przyjmować wyrażenie

  • które może być generowane przez operator

  • które może być generowane przez funkcje

Określenie typu wartości

Typ wartości oznaczonej przez stałą, zmienną lub wyrażenie można określić na podstawie ich postaci lub deklaracji, bez konieczności wykonywania procesu obliczeniowego.

Ustalenie typu

Każdy operator lub funkcja ma argumenty ustalonego typu. Jeśli operator dopuszcza argumenty wielu typów (np. znak „+” oznacza dodawanie zarówno liczb całkowitych jak i rzeczywistych), to typ wyniku określony jest pewnymi specyficznymi dla języka regułami.

Proste typy danych

Standardowe:

  • integer

  • boolean

  • char

  • real

Proste typy danych

Wyliczeniowe:

type T = (c1, c1, ... , cn)

Złożony typy danych

  • Tablice

  • Rekordy (z wariantami)

  • Zbiory

  • Teksty

Podstawowe struktury danych

  • Lista

  • Zbiór

  • Graf

  • Notacja funkcyjna dla atrybutów obiektów

  • Drzewo

Lista

Lista to skończony ciąg elementów:

q = [x1, x2, ..., xn]

Lista

Skrajne elementy listy nazywają się końcami listy

(odpowiednio - lewym i prawym),

a wielkość  q  = n

długością (lub rozmiarem) listy.

Szczególnym przypadkiem listy jest

lista pusta: q =[ ].

Lista

Weźmy dwie listy:

q = [x1, x2, ..., xn]

r = [y1, y2, ..., ym]

i niech 0  i  j  n

Podstawowymi abstrakcyjnymi operacjami na listach są:

dostęp do elementu listy:

q[i] =xi

podlista

q[i..j] = [xi, xi+1, ..., xj]

złożenie

q & r = [x1, x2, ..., xn, y1, y2, ..., yn].

Listy używa się zwykle w specjalny sposób, ograniczając się do zmian jej końców:

(a) front(q) = q[1] (pobieranie lewego końca listy);

(b) push(q, x) = [x] & q (wstawienie elementu x na lewy koniec listy);

(c) pop(q) = q[2..q] (usunięcie bieżącego lewego końca listy);

(d) rear(q) = q[q |] (pobieranie prawego końca listy);

(e) inject(q, x) = q&[x} (wstawienie elementu x na prawy koniec listy);

(f) eject{q) = q[1..q-1] (usunięcie bieżącego prawego końca listy).

Rodzaje list:

  • kolejka podwójna (a) - (f)

  • stos (a) - (c)

  • Kolejka (a), (c), (e)

Rodzaje list:

  • Pojedyncza liniowa

  • Pojedyncza cykliczna

  • Podwójna liniowa

  • Podwójna cykliczna

Lista pojedyncza liniowa

Lista pojedyncza cykliczna

Lista podwójna liniowa

Lista podwójna cykliczna

Następujące operacje na listach mają stałą złożoność czasową:

• w implementacji pojedynczej liniowej: operacje stosu, wstawianie jednego elementu za drugi, usuwanie następnego elementu;

• w implementacji pojedynczej cyklicznej: te operacje co wyżej plus złożenie oraz operacje rear i inject;

• w implementacji podwójnej cyklicznej: te operacje co wyżej plus eject, wstawianie jednego elementu za drugim, usuwanie danegi elementu, odwracanie listy.

Zbiór

Zbiór nie ma podanych elementów

w żadnym ustalonym porządku:

S = {x1, x2, ..., xn}

Rozmiar zbioru

Rozmiarem zbioru S nazywamy

liczbę jego elementów i oznaczamy:

| S |

Rozważać będziemy tylko zbioru skończone

Podstawowe operacje na zbiorach:

  • insert(x. S):

S := S  {x} (wstawienie elementu x do zbioru S)

(b) delete(x, S):

S := S — {x} (usunięcie elementu x ze zbioru S),

(c) member(x, S):

wynikiem jest wartość true gdy x  S

false, gdy x  S

(d) min(S): zwrócenie najmniejszego elementu w zbiorze S z uwzględnieniem pewnego ustalonego liniowego porządku

(e) deletemin(S): S := S - {min(S)};

(f) union(S1, S2): obliczenie S1 S2 (przy założeniu, że zbiory S1 i S2 są rozłączne).

Implementacja zbioru

Wektor charakterystyczny

Przy założeniu, że uniwersum U może służyć jako zbiór indeksów dla tablicy C,

Implementacja zbioru

Implementacje listowe

Ustawiając elementy zbioru S w pewnym porządku, otrzymujemy listę.

Wszystkie implementacje listy mogą być użyte do reprezentowania zbioru.

Implementacja zbioru

Implementacje listowe

Przy implementacjach listy pesymistyczna złożoność czasowa podstawowych operacji na zbiorach jest proporcjonalna do rozmiaru zbiorów.

Abstrakcja algorytmiczna

for each x in S do I

Abstrakcja algorytmiczna
(przykład)

suma := 0;

for each x in S do

suma := suma + x

Graf

Graf to system:

G = (V, E)

gdzie:

V oznacza zbiór skończony, którego elementy są nazywane wierzchołkami (gdy będzie nam zależało na podkreśleniu, że graf jest strukturą danych, używać też będziemy nazwy węzły),

E – zbiór krawędzi, czyli par wierzchołków ze zbioru V

Graf zorientowany

Graf zorientowany to taki,

w którym E jest podzbiorem zbioru par uporządkowanych:

{(x, y): x, yV ^ x  y}

Krawędzie oznaczamy strzałkami

Graf niezorientowany

Graf niezorientowany to taki,

w którym E jest podzbiorem zbioru wszystkich dwuelementowych podzbiorów zbioru V

Krawędzie oznaczamy liniami

Implementacja grafu G = (V, E)

Lista sąsiedztwa:

Dla każdego xV budujemy listę wierzchołków y będących sąsiadami x (tj (x, y)E)

i oznaczamy ja przez L[x]

Wymagana pamięć to O(n+m)

n = |V| m = |E|

Graf niezorientowany

Macierz sąsiedztwa:

1, jeśli (x, y)  E

A[x, y] =

0, jeśli (x, y)  E

W tej implementacji potrzebna jest pamięć O(n2)

Algorytm przechodzenia grafu

Niech:

G = (V, E),

|V| = n,

|E| = m,

p V.

Wychodząc od wierzchołka p, należy odwiedzić każdy wierzchołek i każdą krawędź, które są osiągalne z p. Dozwolonym ruchem jest przejście krawędzią grafu wychodzącą z odwiedzonego już wierzchołka.

Algorytm przechodzenia grafu

W jednym kroku będziemy odwiedzać jeden z wierzchołków oraz jedną z krawędzi grafu i zaznaczać je jako odwiedzone. Na początku wszystkie wierzchołki i wszystkie krawędzie są zaznaczone jako nie odwiedzone.

Algorytm przechodzenia grafu

  • Odwiedź wierzchołek p i zaznacz go jako odwiedzony.

  • Dopóki z jednego z odwiedzonych wierzchołków wychodzi nie odwiedzona jeszcze krawędź, wykonuj podane czynności:

a) wybierz odwiedzony wierzchołek, powiedzmy v, z którego wychodzi nie odwiedzona krawędź;

b) wybierz nie odwiedzoną krawędź, powiedzmy (v, w), wychodzącą z wierzchołka v;

c) zaznacz krawędź (v, w) jako odwiedzoną;

d) jeśli wierzchołek w nie został odwiedzony, odwiedź go i zaznacz jako odwiedzony.

Algorytm przechodzenia grafu

Stosując indukcję względem odległości danego wierzchołka od wierzchołka początkowego p, możemy udowodnić, że w każdym algorytmie stosującym się do powyższego schematu musi nastąpić odwiedzenie jeden raz każdego wierzchołka i każdej krawędzi grafu G osiągalnej z p. Nie biorąc pod uwagę samej procedury odwiedzania wierzchołków i krawędzi, złożoność każdego takiego algorytmu jest proporcjonalna do łącznej liczby wierzchołków i krawędzi (a więc jest liniowa względem rozmiaru grafu).

Algorytm przechodzenia grafu

1. Przyjąć odpowiednią reprezentację grafu, na przykład V = {1,2, ..., n} i listy sąsiedztwa L[v] dla v V.

2. Określić, co to znaczy „zaznacz wierzchołek jako odwiedzony". Można na przykład dołączyć do każdego wierzchołka v pole visited[v] i przyjąć, że false oznacza „wierzchołek nie odwiedzony", a true „wierzchołek odwiedzony".

3. Określić sposób wyboru odwiedzanego wierzchołka, z którego wychodzi nie odwiedzona krawędź. Można na przykład przechowywać takie wierzchołki w kolejce lub na stosie.

4. Określić sposób odróżniania (dla danego wierzchołka) krawędzi odwiedzonych od nie odwiedzonych. Można na przykład trzymać na liście sąsiedztwa danego wierzchołka v wskaźnik current[v] do pierwszej nie odwiedzonej krawędzi (current[v] = nil oznacza, że wszystkie krawędzie wychodzące z danego wierzchołka zostały odwiedzone)





©operacji.org 2017
wyślij wiadomość

    Strona główna