1. Podać definicje pojęć: rozmiar danych, działanie dominujące, złożoność czasowa algorytmu, złożoność pamięciowa algorytmu. Wymienić typowe funkcje określające złożoności obliczeniowe algorytmów. Po co wyznacza się złożoność obliczeniową algorytmu?

Rozmiar danych: Liczba pojedynczych danych wchodząca w skład algorytmu. W sortowaniu np. za rozmiar |d| przyjmuje się zazwyczaj liczbę elementów w ciągu wejściowym.

Działanie dominujące: są to charakterystyczne operacje w algorytmie takie, że łączna ich ilość jest proporcjonalna do liczby wykonań wszystkich operacji jednostkowych Złożoność dowolnej komputerowej realizacji algorytmu. Złożoność algorytmie sortowania np. za działanie dominujące przyjmuje się porównanie 2 elementów, Złożoność czasem przestawienie elementów Złożoność ciągu.

Złożoność czasowa: nie malejąca funkcja, która obrazuje jak zmienia się czas działania algorytmu w zależności od rozmiaru danych wejściowych. T(n).

Złożoność pamięciowa: niemalejąca funkcja, która pokazuje jak zmienia się liczba miejsc pamięci niezbędna do wykonania algorytmu w zależności od rozmiaru danych wejścowych. S(n)

Typowe funkcje złożoności: 1 - log n - n - n log n - n² - n³ - … - 2ⁿ - n!

Złożoność obliczeniową algorytmu wyznaczamy aby określić czas działania i ilości zajmowanej pamięci.

2. Podać definicje złożoności pesymistycznej i średniej algorytmu. Udowodnić, że

W(n) = a mn^m + ... + a 1n¹ + a 0 = O(n^m), dla n>0.

Złożoność pesymistyczna: ilość zasobów komputerowych potrzebnych przy najgorszych danych wejściowych rozmiaru n.

Złożoność średnia: ilość zasobów komputerowych potrzebnych przy typowych danych wejściowych rozmiaru n.

A więc podstawiamy za n np.1 jest większe od zera wtedy możemy zauważyć że największą funkcją określającą ten algorytm jest mn^m bierzemy o-notacje z tego i wychodzi że O(n^m)

3. Jak brzmi definicja O-notacji? Podać trzy dowolne własności rzędu funkcji.

Definicja O-notacji: f(n) jest rzędu co najwyżej funkcji g(n), co zapisujemy f(n)=O(g(n)) jeśli

|f(n)| <= |g(n)|

Własności:

1. f(n) , g(n) - dodatnie i rosnące funkcje a>0, b O(a* g(n)+b)=O(g(n)) Jeśli f(n)=O(a*g(n)+b) to f(a)=O(g(n))

2. Reguła dla Sum Jeśli f(n)=O(S(n)) oraz g(n)=O(t(n)) to F(n)+g(n)=O(max(S(n),t(n))

3. Reguła dla Iloczynu Jeśli f(n)=O(S(n)) oraz g(n)=O(t(n)) to F(n)*g(n)=O(S(n),t(n))

4. Podać algorytmy oraz określić ich złożoności obliczeniowe dla wyznaczania wartości wielomianu dla przypadków: a) korzystając bezpośrednio ze wzoru, b) korzystając ze schematu Hornera.

Dla wielomianu n-tego stopnia w zwykłej postaci należy wykonać n*(1+n)/2 mnożeń, a dla wielomianu po zastosowaniu schematu Hornera tylko n mnożeń! Różnica jest olbrzymia.

5. Podać dwa algorytmy (z wartownikiem i bez) znajdowania maksymalnego elementu w tablicy. Wyznaczyć i porównać ich złożoności.

Złożoność T(n) = Tśr(n) = Tpes(n)= n-1 = O(n) Złożoność Tśr(n) = Tpes(n)=n

T(n)=n-1+1=2n-1=O(n)

Średnia liczba porównań znaki sterujące= n Średnia liczba porównań znaki sterujące lnn+0.577+1

Średnia liczba przypisań = lnn+0.577 Średnia liczba przypisań lnn+0.577

Liczba porównań elementu(A[i]:=Max) n Liczba porównań elementu(A[i]:=Max) n-1

6. Podać algorytmy jednoczesnego znajdowania elementu maksymalnego i minimalnego w zadanym zbiorze dla przypadków: a) kolejne znajdowanie elementu maksymalnego a następnie minimalnego, b) dzielenie zadania na podzadania. Określić złożoności obliczeniowe algorytmów.

Złożoność T(n)= 2(n-1)=2n-2 T(n)= 1 gdy n=2 2T(
)+2 gdy n>1 T(2
)=
n-2 = O(n)

7. Podać rozwiązania równań rekurencyjnych: T(n) = b, dla n = 1, oraz T(n) = aT(n/c) + bn, dla n > 1. Podać interpretację rozwiązań.

a,b,c - są nieujemnymi stałymi to T(n)= O(n) jeśli a<c, O(n log n) jeśli a=c, O( n log_ca) jeśli a>c

8. Omówić zasadę równoważenia rozmiarów podzadań na przykładzie zadania sortowania, rozważając algorytm sortowania przez wybór prosty oraz rekursywny algorytm sortowania przez łączenie. Określić złożoności obliczeniowe algorytmów.

Sortowanie przez wybór:

Złożoność pamięciowa O(1) - algorytm sortuje w miejscu, wymaga bowiem jedynie kilku zmiennych prostych (i, j, min;  tmp).

 

Złożoność czasowa

- ilość porównań:

           

- ilość przestawień

           

Własności:

• stabilny

• liniowa ilość przestawień (optymalny)

• stała ilość porównań (kwadratowa i nie zależy początkowego posortowania danych)

• prosty i szybki dla małych n

 

Sortowanie przez łączenie:

Złożoność: T(n) = 0 dla n=1, 2T(n/2)+(*n-1) dla n>1, T(n)=O(n log₂n)

9. Podać własności kopca oraz omówić sposób jego implementacji. Podać i wyjaśnić działanie procedur: przemieść w górę i przemieść w dół. Wyznaczyć złożoności procedur.

Kopcem nazywamy etykietowane, doskonałe drzewo binarne częściowo uporządkowane. Etykietowane drzewo binarne D = <V, E, et> jest kopcem wtedy i tylko wtedy, gdy

1 D jest drzewem częściowo uporządkowanym: et(v) < et(v.lewy) i et(v)< et(v.prawy) dla wszystkich wierzchołków v ∈V,

2 D jest drzewem doskonałym: wszystkie poziomy drzewa, z wyjątkiem co najwyżej ostatniego poziomu, są maksymalnie zapełnione, a na ostatnim poziomie wszystkie liście są zgrupowane maksymalnie na lewo.

Własności:

1. Etykiety na dowolnej drodze od korzenia do liścia tworzą ciąg uporządkowany rosnąco.

2. Element najmniejszy wśród etykiet wierzchołków znajduje się w korzeniu drzewa.

Dla każdego węzła na poziomie i (liczonym od dołu) maksymalna ilość porównań i przestawień przy poprawianiu w dół jest równa i, zaś ilość węzłów na tym poziomie n/2ⁱ. Pesymistyczna złożoność budowania kopca jest zatem:

kopiec w dół : T(n) = O(log n) kopiec w górę: T(n) = O(log n)

10. Podać abstrakcyjny opis kolejki priorytetowej. Podać i wyjaśnić działanie procedur zeruj, wstaw i usuń min dla kolejki implementowanej za pomocą kopca. Jakie są inne możliwe implementacje kolejki? Porównać je ze sobą pod kątem złożoności obliczeniowej.

Kolejkajest strukturą liniowo uporządkowanych danych w której dołączać nowe dane można jedynie na koniec kolejki a usuwać z początku. Procedura usunięcia danych z końca kolejki jest taka sama, jak w przypadku stosu, z tą różnicą, że usuwamy dane od początku a nie od końca. Pierwszy element (a dokładniej wskaźnik do jego miejsca w pamięci) musi zostać zapamiętany, by możliwe było usuwanie pierwszego elementu w czasie stałym O(1). Gdybyśmy tego nie zrobili, aby dotrzeć do pierwszego elementu należałoby przejść wszystkie od elementu aktualnego (czyli ostatniego), co wymaga czasu O(n). Działanie na kolejce jest intuicyjnie jasne, gdy skojarzymy ją z kolejką ludzi np. w sklepie. Każdy nowy klient staje na jej końcu, obsługa odbywa się jedynie na początku.

11. Sformułować zadanie wyszukiwania. Podać algorytmy wyszukiwania liniowego bez wartownika i z wartownikiem oraz określić ich złożoności średnie i pesymistyczne.

12. Podać algorytm obliczania wartości współczynnika dwumianowego metodą programowania dynamicznego. Wyznaczyć złożoność obliczeniową algorytmu.

13. Podać algorytm sortowania przez proste wybieranie oraz określić jego złożoność średnią i pesymistyczną.

T_pes = T_śr=
(n-1)(n-2)(n-1+1)=
O(n²)

14. Podać algorytm sortowania przez proste wstawianie z wartownikiem oraz określić jego złożoność średnią i pesymistyczną.

15. Omówić algorytm sortowanie szybkiego - quicksort - oraz określić jego złożoność średnią i pesymistyczną. Co warunkuje szybkie działanie algorytmu?

Algorytm sortowania szybkiego zaprojektowany został na podstawie zasady `dziel i zwyciężaj'. Polega zatem na rozbiciu zadania na dwa mniejsze, wykonaniu sortowania niezależnie dla obu części i połączenia wyniku. Ogólny schemat algorytmu można zapisać następująco:

 

Quick_sort(S);

 

if |S | =1 then return(S) else

begin

     wybierz dowolny element vS;

     podziel S na S₁ i S₂ takie, że wS₁ wv  wS₂ w>v;

     Quick_sort(S₁); Quick_sort(S₂);

     połącz S₁ i S₂;

end;

Proces podziału polega na:

• przeglądaniu ciągu od lewej i wyszukiwaniu elementów większych od v,

• przeglądaniu ciągu od prawej i wyszukiwaniu elementów mniejszych od v,

• zamianie znalezionych elementów.

aż do rozdziału ciągu na dwa podciągi. Wybór elementu v jako pierwszego elementu ciągu i wstawienie go w miejsce zejścia się obu procesów przeglądania pozwala na rozdział ciągu w tej samej strukturze danych (tablicy) i sortowanie niezależne obu fragmentów w tej samej tablicy. Zapewnia to, że proces łączenia nie wymaga żadnych operacji.

Wybór pierwszego elementu tablicy jako elementu podziału powoduje dodatkowo konieczność wstawienia wartownika na końcu tablicy, aby zapewnić zakończenie pierwszej pętli wewnętrznej, gdy element v jest największy w tablicy.

Złożoność czasowa algorytmu.

 - złożoność pesymistyczna:

 

           

 - złożoność oczekiwana:

   

Ponieważ podział ciągu jest jednakowo prawdopodobny w każdym miejscu tablicy, zatem

           

Stąd

           

Ponieważ    

Zatem

           

 

Sortowanie szybkie sortuje zatem w czasie średnim O(nlog(n)).

 

Własności:

• algorytm niestabilny

• złożoność pamięciowa ze względu na rekurencję w przypadku pesymistycznym O(n).

• testy wykazują najlepszą efektywność tej metody sortowania

Wybór elementu może być przyczyną poprawienia efektywności w pewnych przypadkach, np.

• wybór pierwszego elementu daje złożoność O(n²) dla ciągu uporządkowanego.

• wybór losowy wydaje się bardziej korzystny, lecz wymaga przeprogramowania (wartownik z oby stron)

• wybór mediany z dowolnych trzech elementów (np. pierwszy, ostatni i środkowy) zapewnia, że zawsze będzie podział na dwie części, z których krótsza będzie miała co najmniej jeden element.

16. Omówić sposoby reprezentowania grafów w komputerze. Jakie są ich złożoności pamięciowe?

W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków, oznaczanych przez V) wzajemnie połącznonych za pomocą krawędzi (oznacznych przez E).
Grafy dzielimy na grafy skierowane i nieskierowane

niekierowany graf
skierowany graf

Omówmy najpierw macierz sąsiedztwa.
Budujemy tablicę o rozmiarach V*V, gdzie V-liczba wierzchołków. Następnie wypełniamy ją zerami- jeśli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki są połączone.

Złożoność pamięciowa O(V
)

Lista incydencji.
Należy utworzyć listę dla każdego wierzchołka v, w której przechowujemy zbiór wierzchołków połączonych krawędzią z v. Lista dla grafu z rysunku 1 wygląda następująco:

1: 2, 3, 5 4: 2, 3, 5
2: 1, 3, 4

3: 1, 2, 4 5: 4, 1   

Złożoność pamięciowa O(V+E)

Lista krawędzi jest to lista, na której przechowujemy wszystkie krawędzie występujące w grafie.
Przykład dla grafu skierowanego z rys.2:

1 - 2 3 - 2

2 - 4 4 - 3

2 - 5 5 - 1

3 - 1 5 - 4

Złożoność pamięciowa O(E)

Macierz incydencji to tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy, jeśli krawędź wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie (-1), jeśli do niego wchodzi piszemy (+1), jeśli wierzchołek nie należy do krawędzi piszemy 0, jeśli jest to pętla własna piszemy 2.

Złożoność pamięciowa O(E*V)

17. Omówić algorytm przeszukiwania grafu w głąb. Jaka jest złożoność algorytmu? Podać zastosowanie tego przeszukiwania do rozwiązywania problemu znajdowania składowych spójności grafu.

18. Omówić algorytm przeszukiwania grafu wszerz. Jaka jest złożoność algorytmu? Podać zastosowanie tego przeszukiwania do rozwiązywania problemu znajdowania najkrótszej drogi w grafie (długość drogi liczona liczbą krawędzi).

19. Podać i omówić algorytm Kruskala znajdowania minimalnego drzewa rozpinającego. Jaka jest jego złożoność?

VS- rodzina rozłącznych zbiorów wierzchołków. Każde V
Vs reprezentuje pewne drzewo rozpinające należącego do lasu rozpinającego.

1.Rozpatrujemy krawędzie w kolejności kosztu

2.Niech (v,w) to kolejna rozpatrująca krawędź

a) (v,w) należą do tego samego zbioru Vs to krawędź tą pomijamy

b) (v,w) należą do dwóch różnych zbiorów Vs(w1,w2) to krawędź wędruje do drzewa i scalamy zbiory w1 i w2

Złożoność: 1.O(e) 2.Inicializacja O(n) 3.while: a) O(loge) b) FIND I UNION O(elog*e)

Czyli

Tsr = O(elog e)

T(n) = O(n
logn)

20. Omówić ideę algorytmu zachłannego na przykładzie problemu wydawania reszty oraz problemu plecakowego. Na czym polega problem kolorowania grafu?

Dodawanie reszty:

25zł,10zł.5zł,1zł

63zł-reszty

Wydajemy resztę w ten sposób:

2*25, 1 *10, 3*1

2+1+3=6

A)wybrać monetę , której wartość nie przekracza 63zł, to jest 25zł.

B)wstawić monetę na listę i odjąć jej wartość od 63zł - otrzymujemy 38zł

C)powtórzyć kroki A i C dla reszty równej 38,13 i3 zł.

Zadanie pakowania plecaka

W-ciężar maksymalny plecaka

A = {a₀,a₁, … ,a_n-1}

{ w₀,w₁, … ,w_n-1}- waga

{ p₀,p₁, … ,p_n-1}- zyski dane

Wybieramy taki produkt żeby całkowity ciężar obiektów
w oraz całkowity zysk był jak największy.

Formalnie 2n+1

{ w₀,w₁, … ,w_n-1}

W

{ p₀,p₁, … ,p_n-1}-

Q=

Przy ograniczeniach

1. z
   = (0,1) dla
   i

2. 
   

Polega na przyporządkowaniu każdemu wierzchołkowi koloru tak aby:

• Każde 2 wierzchołki połączone krawędzią miały różne koloru

• Liczba kolorów była minimalna

Graf jest k - kolorowalny jeśli istnieje przyporządkowanie wierzchołkom G liczb całkowitych nazywanych kolorami w ten sposób że żadne 2 sąsiednie wierzchołki nie mają tego samego koloru.

21. Sformułować problem komiwojażera. Podać: a) algorytm typu "sprawdź wszystkie możliwości", b) algorytm heurystyczny oparty na postępowaniu zachłannym. Jakie są złożoności algorytmów?

Problem komiwojażera
Zbudujmy graf ważony, którego wierzchołki są miastami. Każda parę miast połączmy krawędziami. Każdej krawędzi nadajemy wagę równa 'odległości' miedzy miastami odpowiadającymi wierzchołkom, które są końcami tej krawędzi. Otrzymujemy w ten sposób graf pełny, który ma tyle wierzchołków ile miast musi odwiedzić komiwojażer (wliczając w to miasto, z którego wyrusza). Odwiedzenie wszystkich miast odpowiada cyklowi, który przechodzi przez każdy wierzchołek danego grafu dokładnie raz. Cykl taki nazywamy cyklem Hamiltona. Poszukujemy wiec w grafie pełnym cyklu Hamiltona o minimalnej sumie wag krawędzi.

a)

min:=

for i:=1 to (n-1) do

p:= i-ta permutacja wierzchołków
,
, …,

Niech d(p) jest drogą w grafie odpowiadającym permutacji p jego wierzchołków

If koszt (d(p))<min then

Droga:= d(p);

Min:= koszt(d(p));

End If;

End for;

Złożoność tego algorytmu to n silnia/2.

b)

1. Rozpatrzmy wszystkie krawędzie grafu w kolejności wzrostu ich kosztów.

2. Włączyć krawędzie do poszukiwanej drogi wtedy gdy spełnione są warunki:

• Włączenie krawędzi nie powoduje że któryś z wierzchołków drogi ma stopień większy niż 2

• Włączenie krawędzi nie powoduje powstania cyklu chyba że liczba krawędzi dogi równa jest liczbie wierzchołków grafu

Złożoność tego algorytmu O(n
)

22. Sformułować i porównać problemy znalezienia marszruty komiwojażera, cyklu Hamiltona i cyklu Eulera.

Cykl Eulera

Do powstania cyklu Eulera przyczynił się tzw. problem mostów królewieckich. Przez Królewiec (dziś Kaliningrad) przepływała rzeka, w rozwidleniu której znajdowały się 2 wyspy. Na rzece znajdowało się 7 mostów (patrz rys.). Miejscowa ludność co rok urządzała zabawę, która polegała na próbowaniu przebycia wszysktkich mostów dokładnie raz. Problemem tym zajął się Leonhard Euler, szwajcarski matematyk, fizyk i astronom. Udowodnił on, że nie jest to możliwe, powodem tego jest nieparzysta liczba wejść na mosty na wyspach oraz po obu stronach rzeki.

Cyklem Eulera w grafie nazywamy cykl (drogę, która zaczyna się i kończy w tym samym wierzchołku), który zawiera każdą krawędź dokładnie raz.

Warunek istnienia cyklu Eulera: po pierwsze graf musi być spójny (musi istnieć droga łącząca każdą parę wierzchołków). Jeżeli graf jest spójny i skierowany to do każdego wierzchołka musi wchodzić i wychodzić tyle samo krawędzi. Jeżeli graf jest spójny i nieskierowany to liczba wychodzących krawędzi z każdego wierzchołka musi być parzysta.

Warunek istnienia drogi Eulera: istnieje wtedy i tylko wtedy gdy graf jest spójny i zawiera co najwyżej 2 wierzchołki stopnia nieparzystego.

Cykl Hamiltona

Jest to droga Hamiltona zamknięta. O(kⁿ)

Problem komiwojażera j.w 21

b)

procedure wiel2;

begin

W := a[n];

for i := n - 1 downto 0 do

W := W * x + a[i];

end for;

end.

a)

procedure wiel1;

begin

W := a[0];

for i := 1 to n do

p := x;

for j := 1 to i - 1 do

p := p* x;

end for;

W := a[i] * p +W;

end for;

end.

Var A:array [1..n] of typ_elementu.

Max := A[1];

For i:=2 to n do

If A[i] > max then

Max:= A[i];

End if;

End for

Min := A[1];

For i:=2 to n do

If A[i] < min then

Min:= A[i];

End if;

End for

For i:=1 to n-1 do

K:=1; x:=A[i];

For j:=i+1 to n do

If A[i].klucz < x.klucz then

K:=j; x:=A[j];

End if;

End for;

A[k] := A[i];

A[i] := x;

End for;

For i:=2 to n do

x:=A[i]; A[0] :=x;

j:=i-1

while x.klucz < A[j].klucz do

A[j+1] := A[j]; j:=j-1;

End while

A[j+1] := x;

End for;

procedure quicksort(d, g);

begin

if d < g then

t := A[d]; {t jest kluczem osiowym}

s := d;

for i := d + 1 to g do {przemieszczanie elementów wokół klucza osiowego}

if A[i] < t then

s := s + 1;

zamiana(A[s], A[i]);

end if;

end for;

zamiana(A[d], A[s]);

quicksort (d, s - 1); {wywołania rekursywne dla obu czesci tablicy}

quicksort (s + 1, g);

end if;

end.

procedure wg(v);

begin

znacznik[v] := odwiedzony;

for u 2 listy incydencji[v] do

if znacznik[u] = nieodwiedzony then

{Krawedz (u, v) wstawiana jest do drzewa rozpinajacego}

wg(u);

end if;

end for;

end.

procedure graf w głab;

begin

for v 2 V do

znacznik[v] := nieodwiedzony;

end for;

for v 2 V do

if znacznik[v] = nieodwiedzony then

wg(v);

end if;

end for;

end.

procedure wsz(v);

var K : kolejka wierzchoków FIFO

begin

znacznik[v] := odwiedzony;

wstaw do kolejki(v,K);

while not pusta kolejka(K) do

x := pierwszy(K);

usun pierwszy z kolejki(K);

for y 2 lista incydencji[x] do

if znacznik[y] = nieodwiedzony then

znacznik[y] := odwiedzony;

wstaw do kolejki(y,K);

{Krawedz (x, y) jest wstawiana do drzewa rozpinajacego}

end if;

end for;

end while;

end.

procedure graf wszerz;

begin

for v 2 V do

znacznik[v] := nieodwiedzony;

end for;

for v 2 V do

if znacznik[v] = nieodwiedzony then

wsz(v);

end if;

end for;

end.

Vs<=0; T<=0;

Skonstruuj kolejkę priorytetową Q zawierającą wszystkie krawędzie zbioru S.

For dla każdego v
V do

Dodaj {V} do Vs

End for;

While (Vs)>1 do

Wybierz z kolejki Q krawędź Vw o najmniejszym koszcie

Usuń Vw ze zbioru Q

If v,w należą do różnych zbiorów w1 i w2 w Vs then

Zastąp w1 i w2 i dodaj (v,w) do T

End If;

End while;

Max := A[1];

I:=1;

While i<n do

i:=i+1;

If A[i] > max then

Max:= A[i];

End if;

End while

I:=1;

While i<=n do

Max := A[i];

i:=i+1;

While A[i]<Max do

I:i+1;

End while

End while

procedure kopiec w dół (p: integer);

{element A[1] przemieszczany jest w dół kopca}

var d,r: integer;

begin

r:=1;

loop

d:=2*r; {lewe dziecko}

if d>p then break end if;

if (d+1<=p) cand (A[d+1]<A[d]) then

D:=d+1; {d-największe dziecko r}

End if;

if A[r] <= A[d] then break end if

zamiana( A[r], A[d]);

R:=d;

end loop;

end.

procedure kopiec w górę (p: integer);

var d,r: integer; x: typ zgodny z A;

begin

x:=A[p];

A[0] := x; {ustawienie wartownika}

D:=p;

Loop

R:=d div 2;

if A[r] <= x then break end if;

A[d] := A[r];

D:=r;

end loop;

A[d] := x;

end.

Procedure zeruj

Warunek wstępny: brak

Warunek ostateczny k=0

End.

Procedure wstaw

Warunek wstępny: |K| < max rozmiarów

Warunek ostateczny: bierząca k=poprzednia k U [t]

End.

Procedure usuń

Warunek wstępny: |k| >0

Warunek ostateczny: bierząca k=poprzednia k U [t] oraz t=min

End.

procedure graf kolorowanie zachłanne (G : graf; nowy kolor : zbiór);

var jest : boolean; kolor : integer; v,w : integer;

begin

kolor := 0;

while istnieja niepokolorowane wierzhołki w G do

nowy kolor := ;;

kolor := kolor + 1;

v := pierwszy niepokolorowany wierzchołek w G;

while v <> null do

jest := false;

w := pierwszy wierzchołek w zbiorze nowy kolor;

while w <> null do

if istnieje krawedz pomiedzy v i w w G then

jest := true;

end if;

w := nastepny wierzchołek w zbiorze nowy kolor;

end while;

if not jest then

oznacz v jako pokolorowany kolorem kolor;

dołacz v do zbioru nowy kolor;

end if;

v := nastepny niepokolorowany wierzchołek w G;

end while;

end while;

end.

Procedure MaxMin(s);

If
|S|=2 then

If a>b then return(a,b)

Else return (b,a)

Else

Podzielić S na 2 równe podzbiory S₁ i S₂

(Max1,Min1)=MaxMin(S₁);

(Max2,Min20= MaxMin(S₂);

return (MAX(Max1,Max2),MIN(Min1,Min2));

end if;

procedure Selection_sort;

var i, j, min: integer;

     tmp: elem_type;

begin

   for i := 1 to n-1 do

   begin

      min:=i;

      for j:=i+1 to n do

         if A[j] < A[min] then min:=j;

      tmp:=A[i];   A[i]:=A[min];  

A[min]:=tmp;

   end;

end;

procedure Sort (i,j);

if i=j then return vi;

else m:=(i+j-1)/2;

łączenie(Sort(i,m), Sort(m+1,j));

end if;

end;

Function wsp (m,n: integer)

{ 0<=m<n

begin

if (n=m) or (m=0) then wsp :=1;

else wsp:=wsp(n-1,m)+wsp(n-1,m-1);

end

---