Algorytmy - Matematyka Dyskretna

[ Pobierz całość w formacie PDF ]
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
[ Pobierz całość w formacie PDF ]