Algorytmy – Matematyka Dyskretna

Teoria grafów

Algorytm wyznaczania kodu Prufera

Aby wyznaczyć kod Prufera dla danego drzewa T na zbiorze wierzchołków
{1, ..., n}, należy:

1. Znaleźć najmniejszy wierzchołek stopnia jeden, powiedzmy „v”. Niech

„w” będzie wierzchołkiem połączonym z „v”;

2. Zapisać „w” oraz usunąć wierzchołek „v” wraz z krawędzią „vw”;

3. Jeśli w drzewie pozostała więcej niż jedna krawędź, to przejść do kroku

1., w przeciwnym razie zakończyć algorytm.

Otrzymany ciąg liczb jest kodem Prufera dla drzewa T.

Algorytm otrzymywania drzewa z kodu

Dla zadanego ciągu liczb (a1, a2, ..., an-2) wybranych w dowolny sposób ze
zbioru {1, ..., n}, aby wyznaczyć drzewo T , dla którego ciąg ten jest kodem
Prufera, należy:

1. Zapisać dwie listy; pierwszą (a1, a2, ..., an-2) oraz drugą {1,2, ..., n} i

rozpocząć ze zbiorem wierzchołków {1, ..., n} i pustym zbiorem
krawędzi.

2. Wyznaczyć z drugiej listy najmniejszą liczbę, powiedzmy „i”, która nie

występuje na pierwszej liście. Usunąć pierwszy element z pierwszej listy,
powiedzmy „j”, usunąć „i” z drugiej listy oraz dodać do zbioru krawędzi
„ji”.

3. Jeśli pierwsza lista zawiera co najmniej jedną liczbę, to przejść do punktu

2. Jeśli pierwsza lista jest pusta, to druga będzie się składać z dokładnie
dwóch liczb. Do zbioru krawędzi dodać ostatnią, której wierzchołkami są
właśnie te liczby i zakończyć algorytm.

1

Algorytm obliczania wartości wyrażenia w postaci postfixowej

Dla kolejnych elementów zapisu wyrażenia:

•

jeżeli element jest stałą lub zmienną, to wkładamy jego wartość na stos,

•

jeżeli element jest znakiem operacji, to:

•

zdejmujemy dwie wartości z wierzchu stosu,

•

wykonujemy operację na tych wartościach,

•

obliczoną wartość wkładamy na wierzch stosu,

•

po przejściu całego wyrażenia jego wartość znajduje się na stosie.

Algorytm przeszukiwania drzewa metodą „wgłąb”

Dane wejściowe: drzewo T .

•

Odwiedzamy korzeń  i wkładamy go na STOS; zaznaczamy  , jako
wierzchołek odwiedzony;

•

Dopóki STOS nie jest pusty, powtarzamy:

•

Jeżeli „v” jest wierzchołkiem na wierzchu STOSU to sprawdzamy,
czy istnieje syn „u” wierzchołka „v”, który nie był jeszcze
odwiedzany. Najpierw sprawdzamy „v0”, a potem „v1”.

•

Jeżeli takie „u” się znajdzie, to odwiedzamy „u”, wkładamy je na
wierzch STOSU i zaznaczamy, jako wierzchołek odwiedzony (np.
skreślamy).

•

Jeżeli takiego „u” nie ma, to zdejmujemy „v” ze STOSU i cofamy
się do wierzchołka będącego na stosie pod spodem.

Algorytm przeszukiwania drzewa metodą „wszerz”

•

Odwiedzamy korzeń drzewa  i wkładamy go do KOLEJKI;

•

Dopóki KOLEJKA nie jest pusta, powtarzamy:

•

bierzemy jeden wierzchołek „v” z początku KOLEJKI;

•

odwiedzamy wszystkich synów wierzchołka „v” i wkładamy je na
koniec kolejki.

2

Teoria liczb

Algorytm Euklidesa

Aby obliczyć największy wspólny dzielnik dwóch dodatnich liczb naturalnych a,
b, powtarzamy aż do skutku:

•

dopóki a×b≠0 , wykonuj:

•

jeżeli a0 , to a := a mod b,

•

w przeciwnym wypadku b := b mod a.

•

NWD(a, b) = ab ,

Rozszerzony algorytm Euklidesa

Dane wejściowe: dwie liczby naturalne a,b.

Dane wyjściowe: NWD(a, b) oraz liczby całkowite x,y takie, że

xa + yb = NWD(a, b).

•

podstaw: x

a

:=1, y

a

:=0, x

b

:=0, y

b

:=1,

•

dopóki a×b≠0 , wykonuj:

•

jeżeli a0 , to a := a mod b,

x

a

:= x

a

−

x

b

× 

a÷b  ;

y

a

:= y

a

−

y

b

× 

a÷b ;

•

w przeciwnym wypadku: b := b mod a,

x

b

:= x

b

−

x

a

× 

b÷a ;

y

b

:= y

b

−

y

a

× 

b÷a ;

•

NWD(a, b): = a + b.

•

Jeżeli a > 0 , to x := x

a

, y := y

a

;

•

Jeżeli b > 0 , to x := x

b

, y := y

b

.

3

Spis treści

Teoria grafów........................................................................................................................................1

Algorytm wyznaczania kodu Prufera..............................................................................................1
Algorytm otrzymywania drzewa z kodu..........................................................................................1
Algorytm obliczania wartości wyrażenia w postaci postfixowej....................................................2
Algorytm przeszukiwania drzewa metodą „wgłąb”........................................................................2
Algorytm przeszukiwania drzewa metodą „wszerz”.......................................................................2

Teoria liczb...........................................................................................................................................3

Algorytm Euklidesa.........................................................................................................................3
Rozszerzony algorytm Euklidesa.....................................................................................................3

4