Programozás/Algoritmusok

Algoritmusok és adatszerkezetek I. IB304, vizsgakérdések

Az oldalt bárki szerkesztheti. Nem kell hozzá regisztráció. Kérlek, te is segíts kitölteni a tételeket. Ha valami hibát veszel észre, azt javítsd ki, vagy ha nem tudod, akkor jelezd a végén levő Hibák-nál.

Az itt közölt anyagok nagyrészt a /pub-ban levő jegyzetekből vannak. Az algoritmusok vagy a Java kódok átíratai, vagy a WikiPedia-n és egyéb helyeket fellelt [pszeudó]kódok-ból lettek kialakítva. Kommentekkel próbáltam érthetőbbé tenni az anyagot, több-kevesebb sikerrel. Az ø minden esetben - ahol nincs más írva - a "nincs értelmezve"-t (fordított T) jelenti.

Semmilyen felelősséget nem vállok az oldalon található hibákból származó hátrányok miatt.

Papp Róbert

"Én, mint a pub-ban található anyag szerzője, egyébként hozzájárulok az ilyen felhasználáshoz."

Horváth Gyula

Gyorstalpaló a szerkesztéshez:


=1. szintű címsor=
==2. szintű címsor==
''dőlt betű''
'''vastag betű'''
'''''vastag dőlt betű'''''
;definíció
:bekezdés
::még beljebb kezdés
<pre>
kód
kód
<{per}pre>
#számos felsorolás
*jeles felsorolás

Az O, Ω, Θ, o, ω jelölések definíciója √

Definíciók és magyarázatok

O(g(n)): {f(n) : (∃c, n₀ ≥ 0)(∀n ≥ n₀)(0 ≤ f(n) ≤ c*g(n))}; Azon f(n)függvények halmaza, amelyekhez létezik olyan c konstans és n₀ kezdőindex, nemnegatív számok, hogy minden n-re, ami n₀-nál nagyobb-egyenlő, az f(n) függvény c*g(n) alatt van.

Ω(g(n)): {f(n) : (∃c, n₀ ≥ 0)(∀n ≥ n₀)(0 ≤ c*g(n) ≤ f(n))}; Azon f(n)függvények halmaza, amelyekhez létezik olyan c konstans és n₀ kezdőindex, nemnegatív számok, hogy minden n-re, ami n₀-nál nagyobb-egyenlő, az f(n) függvény c*g(n) felett van.

Θ(g(n)): {f(n) : (∃c₁, c₂, n₀ ≥ 0)(∀n ≥ n₀)(0 ≤ c₁*g(n) ≤ f (n) ≤ c₂*g(n))}; O és Ω együtt teljesül; Azon f(n) függvények halmaza, amelyekhez léteznek olyan c₁, c₂ konstansok és n₀ kezdőindex, nemnegatív számok, hogy minden n-re, ami n₀-nál nagyobb-egyenlő, az f(n) függvény c₁*g(n) és c₂*g(n) között fut.

o(g(n)): {f(n) : (∀c > 0)(∃n₀ > 0)(∀n ≥ n₀)(0 ≤ f(n) < c*g(n))}; O szigorítása; Azon f(n) függvények halmaza, amelyekre teljesül, hogy minden pozitív c konstanshoz létezik pozitív n₀ kezdőindex, hogy minden n-re, ami n₀-nál nagyobb-egyenlő teljesül, hogy a függvény szigorúan c * g(n) alatt van.

ω(g(n)): {f(n) : (∀c > 0)(∃n₀ > 0)(∀n ≥ n₀)(0 ≤ c*g(n) < f(n))}; Ω szigorítása; Azon f(n) függvények halmaza, amelyekre teljesül, hogy minden pozitív c konstanshoz létezik pozitív n₀ kezdőindex, hogy minden n-re, ami n₀-nál nagyobb-egyenlő teljesül hogy a függvény szigorúan c * g(n) felett van.

Kiegészítés

O, Ω, Θ, o, ω tranzitív: f(n) = *(g(n)) ∧ g(n) = *(h(n)) ⇒ f(n) = *(h(n)); mégpedig a nagyobb n₀-tól kezdődően

O, Ω, Θ reflexív: f(n) = *(f(n)); önmagában relációban áll, mivel az egyenlőség is megengedett

Θ szimmetrikus: f(n) = Θ(g(n)) ⇔ g(n) = Θ(f(n))

O, Ω, o, ω antiszimmetrikus: ha f(n) = *(g(n)) ∧ g(n) = *(f(n)) ⇒ f(n) = g(n); tehát egyszerre, csak az egyik lehet kisebb, vagy nagyobb mint a másik (f és g közül); f(n) = o*(g(n)) ⇔ g(n) = ω*(f(n)); a fenti képlet kifejezi, hogy az ordó és az omega jelölések egymás ellentettjei

A partíciószám kiszámításának rekurzív algoritmusa √

int Partíció(int n) {
	return Partíció2(n, n);
}
int Partíció2(int n, int k) {
	// 1-et csak egyféleképp lehet felbontani, és bármilyen számot 1-esekből csak 1 féleképp lehet felépíteni
	if (n == 1 || k == 1)
		return 1;
	// n-nél nagyobb partíciója nem lehet n-nek:
	// az n-nél kisebb számokat tartalmazó partíciók, és a csak n-et tartalmazó partíció
	if (k >= n)
		return Partíció2(n, n - 1) + 1;
	return
		// azon partíciók, amelybe nem vesszük bele a k-t
		Partíció2(n, k - 1) 
		// és azon partíciók, amelybe belevesszük a k-t
		+ Partíció2(n - k, k);
}
//////////////megjegyzés
if (k >= n)
		return Partíció2(n, n - 1) + 1;
helyett egyszerűbb 
if (n<1) return 0; 
if (k > n)	return Partíció2(n,n);
Ez főleg a probléma változatainak tárgyalása során egyszerűsítés.
Például, ha k-nak vagy 3-al vagy  5-el oszhatónak kell lennie.

VeremBol, VeremBe, SorBol, SorBa és a Prioritási sor adattípus SorBol, SorBa műveletek specifikációja √

Előtte	Művelet	Utána
{V = <a₁, ..., a_n>}	VeremBe(V, x)	{V = <a₁, ..., a_n, x>}
{0 < n ∧ V = <a₁, ..., a_n>}	VeremBől(V, x)	{V = <a₁, ..., a_{n - 1}> ∧ x = a_n}
{S = <a₁, ..., a_n>}	SorBa(S, x)	{S = <a₁, ..., a_n, x>}
{0 < n ∧ S = <a₁, ..., a_n>}	SorBól(S, x)	{x = a₁ ∧ S = <a₂, ..., a_n>}
{P = {a₁, ..., a_n}}	PriSorBa(P, x)	{P = Pre(P) ∪ {x}}
{P ≠ ø}	PriSorBól(P, x)	{x = min(Pre(P)) ∧ P = Pre(P) \ {x}}

A Halmaz adattípus specifikációja √

Nem biztos, hogy ez az!, Az ø itt üres halmazt jelent!

Értékhalmaz: Halmaz = { H : H ⊆ E}
Műveletek: H: Halmaz, x: E, I: Iterator

Előtte	Művelet	Utána
{Igaz}	Létesít(H)	{H = ø}
{H = H}	Megszüntet(H)	{Igaz}
{H = H}	Üresít(H)	{H = ø}
{H = {a₁, ..., a_n}}	Elemszám(H)	{Elemszám = n}
{H = H}	Eleme(H, x)	{Eleme = x ∈ Pre(H)}
{H = H}	Bővít(H, x)	{H = Pre(H) ∪ {x}}
{H = H}	Töröl(H, x)	{H = Pre(H) \ {x}}
{H = H}	IterKezd(H, I)	{}
{I = I}	IterAd(I, x)	{}
{I = I}	IterVege(I)	{}

A Függvény adattípus Kiolvas, Modosit, Bovit és Torol műveleteinek specifikációja √

Java-ban java.util.Map, C++-ban std::map

Műveletek: F: Függvény, k: K, x: A

Előtte	Művelet	Utána
{(∃a ∈ A)((k,a) ∈ F)}	Kiolvas(F, k, x)	{x = a ∧ F = Pre(F)}
{(∀a ∈ A)((k,a) ∉ F)}	Kiolvas(F, k, x)	{F = Pre(F) ∧ x = Pre(x)}
{(∃a ∈ A)((k,a) ∈ F)}	Módosít(F, k, x)	{F = Pre(F) \ {(k,a)} ∪ {(k,x)} }
{(∀a ∈ A)((k,a) ∉ F)}	Módosít(F, k, x)	{F = Pre(F) ∧ x = Pre(x)}
{(∀a ∈ A)((k,a) ∉ F)}	Bővít(F, k, x)	{F = Pre(F) ∪ {(k,x)} }
{(∃a ∈ A)((k,a) ∈ F)}	Bővít(F, k, x)	{F = Pre(F) ∧ x = Pre(x)}
{(∃a ∈ A)((k,a) ∈ F)}	Töröl(F, k)	{F = Pre(F) \ {(k,a)} }
{(∀a ∈ A)((k,a) ∉ F)}	Töröl(F, k)	{F = Pre(F)}

A Reláció adattípus APar, KPar, ATorol, KTorol műveleteinek specifikációja √

Java-ban java.util.Map, C++-ban std::map, vagy ha több érték megengedett egy kulcshoz: java.util.Map<java.util.List>, std::multimap

Előtte	Művelet	Utána
{R = R}	KPar(R, k)	{KPar = {a : (k, a) ∈ Pre(R)} }
	APar(R, a)	{APar = {k : (k, a) ∈ Pre(R)} }
	KTöröl(R, k)	{R = Pre(R) \ {(k,a) : (k,a) ∈ Pre(R)} }
	ATöröl(R, a)	{R = Pre(R) \ {(k,a) : (k,a) ∈ Pre(R)} }

Lánc és körlánc absztrakt adatszerkezetek definíciói √

Lánc

A = (M, R, Adat) lánc, ha R = {követ},

követ

M → M parciális függvény, amelyre teljesül:

(∃ fej ∈ M)(∀ x ∈ M)(∃! k ≥ 0)(x = követ^k(fej))

láncvég: Pontosan egy olyan c ∈ M cella van, amelyre követ(c) = ø (NULL).

Lánc hosszán az n számot értjük, mely a cellák számát adja meg.

Ha n > 0, akkor követ^{n − 1}(fej) = láncvég

Körlánc

A = (M, R, Adat) körlánc, ha R = {követ},

követ

M → M (totális) függvény, amelyre teljesül:

(∀x, y ∈ M)(∃k ≥ 0)(y = követ^k(x))

bármely x ∈ M-re az <x = x₀, x₁, ..., x_n−1> sorozat, ahol x_i = követ(x_i−1), i = 1, ..., n − 1, az M halmaz elemeinek egy ciklikus permutációja.

A nem rendezett fa definíciói (bináris reláció, és apa függvény) √

Bináris reláció

A = (M, R, Adat) nem-rendezett fa, ha R = {r}, r ⊆ M × M bináris reláció, és van olyan g ∈ M, hogy a G = (M, r) irányított gráfban bármely x ∈ M-re pontosan egy g ~> x út vezet. g-t a fa gyökerének nevezzük.

Apa függvény

Minden nem-rendezett fa egyértelműen megadható egy olyan Apa : M → M parciális függvénnyel, amelyre teljesül a következő feltétel:

(∃ g ∈ M)((Apa(g) = ø) ∧ (∀x ∈ M)(∃!k ≥ 0)(Apa^k(x) = g))

Ha y = Apa(x), akkor azt mondjuk, hogy x apja y és y-nak fia x.

Az így megadott szerkezeti kapcsolat nem definiál rendezettséget adott x cella {y : Apa(y) = x} fiainak halmazán.

A rendezett fa absztrakt adatszerkezet definíciója f_i függvényekkel √

Legyen A = (M, R, Adat) olyan absztrakt adatszerkezet, hogy R = {f}, f : M → (M ∪ {ø})^*.

x ∈ M, f(x) = <y₁, ..., y_k>, y_i ∈ M ∪ {ø}, i = 1, ..., k.

Minden i > 0 természetes számra definiáljuk az f_i : M → M ∪ {ø} függvényt a következőképpen:

f_{i}(x)={\begin{cases}y_{i},&{\mbox{ha }}f(x)=\left\langle y_{1},...,y_{k}\right\rangle \land i\leq k;\\\emptyset ,&{\mbox{ha }}i>k;\end{cases}}

Tehát f_i(x) az x i-edik fiát adja. Ha f_i(x) = ø, akkor hiányzik az i-edik fiú.

Az A adatszerkezetet fának nevezzük, ha van olyan g ∈ M, hogy teljesül az alábbi négy feltétel

a gyökér nem fia egyetlen pontnak sem:
$(\forall x\in M)(\forall i)(g\neq f_{i}(x))$
minden, gyökértől különböző pont fia valamely pontnak:
$(\forall y\neq g\in M)(\exists x\in M)(\exists i)(f_{i}(x)=y)$
minden pontnak legfeljebb egy apja lehet:
$(\forall x,y\in M)(\forall i,j)(f_{i}(x)=f_{j}(y))(x=y\land i=j))$
minden pont elérhető a gyökérből:
$(\forall x\neq g\in M)(\exists i_{1},...,i_{k})(x=f_{i_{k}}(...(f_{i_{1}}(g))))$

Fa absztrakt adatszerkezet algebrai definíciója √

Legyen E tetszőleges adathalmaz. Az E-feletti fák Fa(E) halmaza az a legszűkebb halmaz, amelyre teljesül az alábbi három feltétel:

ø ∈ Fa(E), az E-feletti fák része az üres halmaz
(∀a ∈ E)a ∈ Fa(E), ha egy adat benne van az adathalmazban, akkor benne van az E-feletti fákban is
(∀a ∈ E)(∀t₁, ..., t_k ∈ Fa(E))(a(t₁, ..., t_k) ∈ Fa(E))

Általános absztrakt adatszerkezet definíciója √

Olyan A = (M, R, Adat) rendezett hármas, ahol

M az absztrakt memóriahelyek, cellák halmaza.
R = {r₁, ..., r_k} a cellák közötti szerkezeti kapcsolatok, r_i : M → (M ∪ {ø})^*
Adat : M → E parciális függvény, a cellák adattartalma.

x ∈ M, r ∈ R és r(x) = <y₁, ..., y_i, ..., y_k> esetén az x cella r kapcsolat szerinti szomszédai {y₁, ..., y_k}, y_i pedig az x cella i-edik szomszédja.

Ha y_i = ø, akkor azt mondjuk, hogy x-nek hiányzik az r szerinti i-edik szomszédja.

Különbségek a gráf és általános absztrakt adatszerkezetek között (nem anyag)

A gráf csak egy szerkezeti kapcsolatot ad meg.
Gráf esetén a szomszédok halmaza nem rendezett.
Gráfban nem tudunk hiányzó kapcsolatot megadni.

Fa adatszerkezet kapcsolati tömb, kapcsolati lánc ábrázolásai √

Kapcsolati tömb

Statikus

struct FaPont {
	ElemTípus elem;
	FaPont* fiuk[MAXHOSSZ];
	int hossz;
}

Memóriaigény: n * (sizeof(ElemTipus) + MAXHOSSZ * sizeof(FaPont*) + sizeof(int)); Feltéve, hogy sizeof(FaPont*) = 4 és ElemTípus = int32: 4 * n * (MAXHOSSZ + 2)
Az ábrázolás előnye: Minden pont i-edik fia közvetlenül (konstans időben) elérhető.
Az ábrázolás hátránya: Statikus, azaz nem lehet konstans időben bővíteni és törölni.

Dinamikus (nem anyag)

Ha előre tudjuk a bizonyos pontok gyerekeinek számát, akkor dinamikus foglalással:

struct FaPont {
	ElemTípus elem;
	FaPont** fiuk;
	int hossz;
}

Memóriaigény: $n*(\operatorname {sizeof} (ElemTipus)+\operatorname {sizeof} (int)+\operatorname {sizeof} (FaPont**))+\operatorname {sizeof} (FaPont*)*\sum _{i=1}^{n}{\operatorname {FiukSzama} (i)}$; $\sum _{i=1}^{n}{\operatorname {FiukSzama} (i)}=n-1$ , mivel minden gyereknek legfeljebb egy apja van (gyökérnek nincs).; Feltéve, hogy sizeof(T*) = 4 és ElemTípus = int32: 16 * n - 4
Az ábrázolás előnye: Minden pont i-edik fia közvetlenül (konstans időben) elérhető.
Az ábrázolás hátránya: Statikus, azaz nem lehet konstans időben bővíteni és törölni.

Kapcsolati lánc

struct FaPont {
	int n;
	struct kapcsolo {
		FaPont* gyerek;
		kapcsolo* kovetkezo;
	};
	kapcsolo* kapocs;
};

Memóriaigény: n * (sizeof(ElemTípus) + sizeof(kapcsolo*)) + (n - 1) * (sizeof(FaPont*) + sizeof(kapcsolo*)); Feltéve, hogy sizeof(T*) = 4 és ElemTípus = int32: 16 * n - 8

Fa adatszerkezet elsőfiú-testvér, elsőfiú-testvér-apa ábrázolásai √

Elsőfiú-testvér

struct Fa {
	ElemTípus adat;
	Fa* elsőfiú;
	Fa* testvér;
};

Memóriaigény: n * (sizeof(ElemTípus) + 2 * sizeof(Fa*)); Feltéve, hogy sizeof(Fa*) = 4 és ElemTípus = int32: 12 * n

Elsőfiú-testvér-apa

struct Fa {
	ElemTípus adat;
	Fa* elsőfiú;
	Fa* testvér;
	Fa* apa;
};

Memóriaigény: n * (sizeof(ElemTípus) + 3 * sizeof(Fa*)); Feltéve, hogy sizeof(Fa*) = 4 és ElemTípus = int32: 16 * n

Preorder rekurzív fabejáró algoritmus √

PreOrder(Fa fa, Művelet M) {
	M(fa);
	for(gyerek : fa.gyerekek)
		PreOrder(gyerek, M);
}

C++-os megvalósítás, elsőfiú-testvér ábrázolással:

struct FaPont {
	int adat;
	FaPont* elsőfiú;
	FaPont* testvér;
};
void PreOrder(FaPont* p, void(Művelet*)(FaPont*)) {
	if (p == NULL) return;
	Művelet(p);
	if (p->elsőfiú != NULL) // az if elhagyható, úgyis visszatér ha NULL-t kap
		PreOrder(p->elsőfiú, M);
	if (p->testvér != NULL) // az if elhagyható, úgyis visszatér ha NULL-t kap
		PreOrder(p->testvér, M);
}

Szintszerinti fabejáró algoritmus √

void SzintSzerint(Fa fa, Művelet M) {
	Sor<Fa> S;
	S.push(fa);
	while(!S.empty()) {
		Fa f = S.pop();
		M(f);
		for(gyerek : f.gyerekek)
			S.push(gyerek);
	} 
}

Partíció probléma megoldása rekurziómemorizálással √

long Particio[][];
long Partíció(int n) {
	Particio = new long[n][n];
	return Partíció2(n,n);
}

long Partíció2(int n, int k){
	if (Particio[n][k] != 0) // Partíció2(n, k)-t már kiszámítottuk
		return Particio[n][k];
	long P_nk;
	if (k == 1 || n == 1)
		P_nk = 1;
	else if (k >= n)
		P_nk = Partíció2(n, n - 1) + 1;
	else
		P_nk = Partíció2(n, k - 1) + Partíció2(n - k, k);
	Particio[n][k] = P_nk; //memorizálás
	return P_nk;
}

Algoritmust kommentezve lásd: Partíciószám rekurzív algoritmusa

Partíció probléma dinamikus programozási megoldása (táblázat-kitöltéssel) √

Az indexelés [oszlop, sor] szerint van. Csak a mátrix felső háromszögét tölti ki, a főátlót és fölötte.

long P(int N) {
	long tabla[1..N, 1..N];
	for (int i = 1; i <= N; i++) // első sor
		tabla[i, 1] = 1;
	for (int k = 2; k <= N; k++) { // a k. sor kitöltése
		tabla[k, k] = tabla[k, k - 1] + 1; // P2(n, n) = P2(n, n - 1) + 1
		// P2(n, k) = T2[n, k] számítása
		for (int n = k + 1; n <= N; n++) {
			// P2(n, k) = P2(n, n), ha k > n
			int n1 = (n - k < k)? n - k : k; 
			// P2(n, k) = P2(n, k - 1) + P2(n - k, k)
			tabla[n, k] = tabla[n, k - 1] + tabla[n - k, n1]; 
		}
	}
	return tabla[n, n];
}

Algoritmust kommentezve lásd: Partíciószám rekurzív algoritmusa

Pénzváltási probléma definíciója, részproblémák definíciója, a közöttük levő összefüggések √

Probléma: Pénzváltás

Bemenet: P = {p₁, ..., p_n} pozitív egészek halmaza, és E pozitív egész szám.; Tehát P = pénzérmék, és E hogy mennyit szeretnénk kirakni P-ből

Kimenet: Olyan S ⊆ P, hogy $\sum _{p\in S}=E$ .; Tehát azon érmék halmaza, melyek összege kiadja E-t

Megjegyzés: A pénzek tetszőleges címletek lehetnek, nem csak a szokásos 1, 2, 5 10, 20, stb., és minden pénz csak egyszer használható a felváltásban.

Először azt határozzuk meg, hogy van-e megoldás.

Tegyük fel, hogy

E=p_{i_{1}}+...+p_{i_{k}},i_{1}<...<i_{k}

, tehát a megoldásban szereplő pénzérmék egy sorrendje

egy megoldása a feladatnak. Ekkor

E-p_{i_{k}}=p_{i_{1}}+...+p_{i_{k-1}}

megoldása lesz annak a feladatnak, amelynek bemenete a felváltandó

E-p_{i_{k}}

érték, és a felváltáshoz legfeljebb a első i_{k - 1}

(p_{i_{1}}+...+p_{i_{k-1}})

pénzeket használhatjuk.

Részproblémákra bontás: Bontsuk részproblémákra a kiindulási problémát:; Minden (X, i)(1 ≤ X ≤ E, 1 ≤ i ≤ N) számpárra vegyük azt a részproblémát, hogy az X érték felváltható-e legfeljebb az első p₁, ..., p_i pénzzel. Jelölje V(X, i) az (X, i) részprobléma megoldását, ami logikai érték:; V(X, i) = IGAZ, ha az X összeg előállítható legfeljebb az első i pénzzel, egyébként HAMIS.

Összefüggések a részproblémák és megoldásaik között

V(X, i) = (X == p_i), ha i = 1

egyetlen érménk van

ha megegyezik a kirakandó értékkel, akkor IGAZ
egyébként HAMIS

V(X, i) = V(X, i - 1) ∨ (X > p_i) ∧ V(X - p_i, i - 1) ha i > 1

több érménél

kirakható 1-gyel kevesebb érméből
vagy az érték nagyobb, mint az utolsó érme
és a vele csökkentett érték kirakható a maradék érmékből

Pénzváltási probléma egy megoldásának előállítása táblázat-kitöltéssel

kötelező mindkét kód, választható, egyébként is egyanaz, csak az egyik Pseudokódan a másik meg Javában van.

int[] PénzVáltás(int E, int P[n]){
	boolean kirakhato[0..E][0..n];
	for (x = 1..E) // ???
		kirakhato[x, 0] = false;
	kirakhato[0, 0] = true; // semmit, érmék nélkül ki lehet rakni
	kirakhato[P[0], 0] = true; // ???
	for (i = 1..n-1)
		for (x = 1..E)
			kirakhato[x, i] =
		// az aktuális érme kiadja az értéket:
				P[i] == x 
		// vagy e nélkül az érme nélkül is ki lehet rakni:
			||	kirakhato[x, i - 1] 
		// vagy belevehető az P[i] érme, és belevéve kiarkható:
			||	x > P[i] && kirakhato[x - P[i], i - 1]; 
	int db = 0; x = E; i = n - 1;
	if (!kirakhato[E, n - 1]) return NULL;
	//megoldás visszafejtése érmék tömbbe
	int érmék[0..n] = 0;
	do {
		while (i >= 0 && kirakhato[x, i])
			i--;
		érmék[db++] = ++i;
		x -= P[i]; // csökkenti a kirakandó értéket
	} while(x > 0); // amíg van mit kirakni
	return érmék; // 0..db-1 -ig lesz a megoldás, utána 0-k
}

A táblázat kitöltésének logikája:

Olyan kiszámítási sorrendet kell megállapítani, amelyre teljesül, hogy amikor az (X, i) rész- problémát számítjuk, akkor ennek összetevőit már korábban kiszámítottuk. Mivel az (X, 1) részproblémáknak nincs összetevőjük, ezért közvetlenül kiszámíthatóak, azaz a táblázat első sorát számíthatjuk eloször. Ha i > 1, akkor az (X i) részprobléma összetevoi az (X, i − 1) és (X − pi , i − 1), ezért az i-edik sor bármely elemét ki tudjuk számítani, ha már kiszámítottuk az i − 1-edik sor minden elemét. Tehát a táblázat-kitöltés sorrendje: soronként (alulról felfelé), ̋ balról-jobbra haladó lehet.

Akkor és csak akkor van megoldása a problémának, ha a VT táblázat kitöltése után VT[E,N] értéke igaz. Ekkor az (1-2.) képletek szerint a legnagyobb i indexű pi pénz, amely szerepelhet E eloállításában, az a legnagyobb index, amelyre

VT[E,i] = True ∧ (VT[E,i − 1] = False)

Java kód

public class PenzValt1{
 public static int[] Valto(int E, int[] P){
   int n=P.length;
   int MaxE=1000;
   boolean VT[][]=new boolean[E+1][n+1];
   int i,x;
   for (x=1; x<=E; x++)                //inicializálás
       VT[x][0]=false;                 //0 sor végig false
   VT[0][0]=true;                      //semmit, érmék nélkül ki lehet rakni
   VT[P[0]][0]=true;                   //inicializálás vége
   for (i=1; i<n; i++)                 //kitöltjük a táblázatot az összes lehetséges P-re balról-jobbra
       for (x=1; x<=E; x++)            //kitöltjük a táblázatot az összes lehetséges X-re alulról-fölfele
          VT[x][i]= P[i]==x || VT[x][i-1] || x>=P[i] && VT[x-P[i]][i-1];
   int db=0; x=E; i=n-1;
   if (!VT[E][n-1]) return null;       //a fenti összefügének megfelelően eldönti ki lehet-e rakni E-t
   int C[]=new int[n];                 //felhasznált érmék
   do{                                 //megoldás visszafejtés
       while (i>=0 && VT[x][i])
          i--;                         //kikeresi az x-hez az i-k közül a legnagyobb olyat amelyik
                                       //esetén az x-et nem lehet kirakni
       C[db++]=++i;                    //ekkor az etől 1-gyel nagyobb benne lesz a megoldási listában
       x-=P[i];                        //csökkenti a kirakandó értéket
   }while(x>0);
   for (i=db; i<n; i++)
       C[i]=0;
   return C;
 }
}

Optimális pénzváltási probléma definíciója, részproblémák definíciója, a közöttük levő összefüggések

Optimális pénzváltási probléma megoldása táblázat-kitöltéssel (egy megoldást is előállítani)

Mátrixszorzás probléma definíciója, részproblémák definiálása, a közöttük levő összefüggések

Hátizsák probléma definíciója, részproblémák definiálása, a közöttük levő összefüggések

Optimális bináris keresőfa definíciója, részproblémák definíciója, a közöttük levő összefüggések

Optimális bináris keresőfa megoldása táblázat-kitöltéssel (egy optimális bináris keresőfa előállítása)

Eseménykiválasztási probléma definíciója, megoldó algoritmus

Optimális prefix kód probléma definícója, Huffman-kód szerkesztő algoritmus

A Graf adattípus specifikációja √

Irányítatlan gráf: G = (V, E), E rendezetlen {a, b}, a, b ∈ V párok halmaza.
Irányított gráf: G = (V, E), E rendezett (a, b) párok halmaza; E ⊆ V × V.
Multigráf: G = (V, E, Ind, Érk), Ind, Érk : E → V; Ind(e) az e él induló, Érk(e) az érkező pontja.

Ki(G, p) = {q ∈ V : (p, q) ∈ E}

Be(G, p) = {q ∈ V : (q, p) ∈ E}

Értékhalmaz: Gráf = {G = (V, E) : V ⊆ PontTípus, E ⊆ V × V}
Műveletek: G : Gráf; p, p1, p2 : PontTípus; I : Iterator; irányított: boolean

Előtte	Művelet	Utána
{Igaz}	Létesít(G, irányított?)	{G = (ø, ø)}
{G = G}	Megszüntet(G)	{Igaz}
	Üresít(G)	{G = (ø, ø)}
	Irányított(G)	{¬Irányított(G) ⇒ (p, q) ∈ E ⇒ (q, p) ∈ E)}
	PontokSzáma(G)	{= \|V\|}
	ÉlekSzáma(G)	{= \|E\|}
	KiFok(G, p)	{= \|Ki(G, p)\|}
	BeFok(G, p)	{= \|Be(G, p)\|}
{G = (V, E)}	PontBővít(G, p)	{V = Pre(V) ∪ {p} ∧ E = Pre(E)}
{G = (V, E) ∧ p ∈ V}	PontTöröl(G, p)	{V = Pre(V) \ {p} ∧ E = Pre(E) \ ( {(p,q) : q ∈ Ki(G, p)} ∪ {(q, p) : q ∈ Be(G, p)} ) }
{G = (V, E), p1, p2 ∈ V}	ÉlBővít(G, p1, p2)	{E = Pre(E) ∪ {(p1, p2)} ∧ V = Pre(V)}
	ÉlTöröl(G, p1, p2)	{E = Pre(E) \ {(p1, p2)} ∧ V = Pre(V)}
	VanÉl(G, p1, p2)	{= (p1, p2) ∈ E ∧ E = Pre(E) ∧ V = Pre(V)}
{G = G}	KiÉl(G, p)	{= {q : VanÉl(p,q)}}
	PIterator(G, I)	{}
	KiIterator(G, p)
	ÉlIterator(G, I)

Kapcsolatmátrix, éllista gráf-reprezentációk, Tárigény, VanEl, Eliteráció, KiIteráció időigénye √

Kapcsolatmátrix (szomszédsági mátrix)

bool G[|V|, |V|];: (p, q) akkor és csak akkor éle a gráfnak, ha G[p, q] = true.
Címkézett (súlyozott) gráf ábrázolására:

boolean[][] G; //
Cimke[][] G;   //címkézett (súlyozott) gráf ábrázolására

Címkézett gráf esetén választani kell egy nem ∈ dom(CímkeTípus) értéket, amely nem fordul elő semmilyen él címkéjeként.

(p, q) akkor és csak akkor éle a címkézett gráfnak, ha G[p, q] != nem, és a (p, q) él címkéjének értéke G[p, q].

Multi-gráf nem ábrázolható szomszédsági mátrix-al.

Éllista

Statikus

int G[|V|, |V|];
int KiFok[|V|];

Dinamikus

Lánc<int> G[|V|];

Általános

Az általános éllistás ábrázolás előnye, hogy a gráf pontjai tetszőleges (de rögzített) típusú értékek lehetnek.

Címkézett gráf esetén a ki-lánc (a vízszintes lánc) minden cellája a pont mellett egy címke értéket is tartalmaz.

template<typename PontTípus> struct GráfLánc {
	PontTípus címke;
	GráfLánc<PontTípus>* csat;
	Lánc<PontTípus> ki;
}

Igények (n = |V|, m = |E|, k = |Ki(G, p)|)

Reprezentáció	Tárigény	VanÉl	Él-iteráció	Ki-iteráció
Kapcsolati mátrix	Θ(n²)	Θ(1)	Θ(n²)	Θ(n)
Statikus éllista	Θ(n²)	T_lr = O(n)	Θ(m)	Θ(k)
Dinamikus éllista	Θ(n + m)			Θ(k)
Általános éllista	Θ(n + m)			T_lr = O(n) + Θ(k)

Út, legrövidebb út definíciója súlyozott és súlyozatlan gráfokban √

Legyen G = (V,E) irányított (irányítatlan) gráf.

Út

p, q ∈ V-re egy p-ből q-ba vezető út G-ben, olyan π = <p₀, p₁, ..., p_k> pontsorozat, ahol p = p₀, q = p_k és p_i ≠ p_j, ha i ≠ j, vagy p = q = p₀, továbbá teljesül (∀i ∈ {1, ..., k})((p_i-1, p_i) ∈ E).

Olyan pontsorozat, melynek az eleje p, a vége q és minden eleme különböző vagy a kezdőpont megegyezik a végponttal (kör), továbbá az egymást követő pontokat összekötő él benne van a gráfban.

Legrövidebb út

π = <p₀, p₁, ..., p_k> = p ~> q út hossza: |π| = |p ~> q| = k
Ha G = (V, E, C) élei a C : E → R függvénnyel súlyozottak, akkor a p ~> q út hossza: $\left|p\sim >q\right|=\sum _{i=1}^{k}C(p_{i-1},p_{i})$ .
p és q távolsága, p-ből q-ba vezető legrövidebb út hossza: $\delta (p,q)={\begin{cases}\infty ,&{\mbox{ha nincs }}p\sim >q;\\\min(\left|\pi :p\sim >q\right|)&\forall \pi :p\sim >q;\end{cases}}$

Szélességi keresés algoritmusa √

Egy adott súlyozatlan irányított vagy irányítatlan gráf egy pontjából keressük az elérhető pontokat, és az azokhoz vezető legrövidebb utakat.

Bemenet: a G = (V, E) gráf és egy kiindulási pont start ∈ V . Kimenet: a legrövidebb utak fája, egy Apa függvény által megadva, és egy d függvény, amelyre d(p) = δ(p) minden p ∈ V -re.

Megj.: A tombnev[1...Valami.size()] = 0; jelentése, hogy felveszünk egy Valami.size méretű tömböt, és elemeit kinullázzuk 1-től egészen végéig.

szelkeres(Graf G, start) {
	Sor S;                                     //Inicializálás
	int apa[1..G.size()] = -1;                 //A tömb fogja tárolni a G pontjaihoz az apjukat. Egyelőre mind -1
	int d[1..G.size()] = ∞;              //A tömb fogja tárolni a mélységét a pontnak. Ha végtelen akkor elérhetetlen
	apa[start] = 0;
	d[start] = 0;                              //Inicializálás vége
	S.push(start);
	while(!S.empty()) {
		u = S.pop();
		for(v : G[u].ki) {                 //v végigmegy az u "gyermekein"
			if(apa[v] == -1) {         //megvizsgálja hogy v-hez van-e már apa eltárolva. Ha nincs,
                                                   //akkor ez lesz a legrövidebb út
				apa[v] = u;        //bejegyzi u-t v apjának. Legrövidebb út
				d[v] = d[u] + 1;   //feljegyzi v mélységi szintjét, u szintjétől eggyel mélyebb szinten lesz
				S.push(v);
			}
		}
	}
}

Mélységi keresés algoritmusa √

Gráfpontok 1-től indexelve

apa == -1: fa-gyökér
apa == 0: még nem bejárt pont

Megj.: A tombnev[1...Valami.size()] = 0; jelentése, hogy felveszünk egy Valami.size méretű tömböt, és elemeit kinullázzuk 1-től egészen végéig.

int idő;                                //globális változó, ezzel számoljuk hogy mennyit mozogunk a gráfban
void MélyKeres(Graf G) {                //inicializálás
	d[1..G.size()];                 //érkezési idő
	f[1..G.size()];                 //elhagyási idő
	apa[1..G.size()] = 0;           //a pontok apját tároló tömb ki nullázása
	idő = 0;                        //inicializálás vége
	for(p: G.V) if(!apa[p]) {       //végig lépked a gráfban lévő fák gyökrein
		apa[p] = -1;            //feljegyzi az apa tömbben hogy gyökerek
		MélyBejár(G, p);        //bejárja a gyökerekhez tartozó fákat
	}	
}
void MélyBejár(Graf G, int u) {
	d[u] = ++idő;                   //növeli eggyel az időt, majd tárolja a ponthoz az érkezési táblán
	for (v: G[u].ki) if(!apa[v]) {  //kiválasztja sorba a pont fiait, és ha nem lett még bejárva bejárja öket sorban
		apa[v] = u;             //feljegyzi az apa táblán v fiuhoz hogy u az apja
		MélyBejár(G, v);        //rekurzivan meghívja magát v-re amíg be nem járja a részfát
	}
	f[u] = ++idő;                   //feljegyzi az elhagyási időt, ekkora u összes részfája be lett járva
}

"Színezős MélyKeresés"

int idő;
void MélyKeres(Graf G) {
	d[1..G.size()];
	f[1..G.size()];
	apa[1..G.size()] = -1;
	szín[1..G.size()] = fehér;
	idő = 0;
	for(p: G.V) if(szín[p] == fehér)
		MélyBejár(p);
}
void MélyBejár(Graf G, int u) {
	szín[u] = szürke;
	d[u] = ++idő;
	for (v: G[u].ki) if(szín[u] == fehér) {
		apa[v] = u;
		MélyBejár(v);
	}
	f[u] = ++idő;
	szín[u] = fekete;
}

Zárójelezési tétel

Mélységi keresést alkalmazva a G = (V,E) gráfra, a következő három feltétel közül pontosan az egyik teljesül minden u és v pontra:

1. A [ d(u) , f(u) ] és [ d(v) , f(v) ] intervallumok diszjunktak és az u és v pontok egyike sem leszármazottja a másiknak a Mélységi Feszítő Erdőben (MFE).

2. [ d(v) , f(v) ] ⊆ [ d(u) , f(u) ] és v leszármazottja u-nak a MFE-ben.

3. [ d(u) , f(u) ] ⊆ [ d(v) , f(v) ] és u leszármazottja v-nek a MFE-ben.

/* d -> elérési-, f -> elhagyási idő , MFE = (V,F) : F = {(p,q) : Apa(q) = p} */

Élek osztályozása (faél, előre él, visszaél, keresztél definíciója) √

(u, v) ∈ V , (MFE = Mélységi Feszítő Erdő)

Faél: ha bekerül a MFE élei közé, azaz Apa(v) = u; u → v él vizsgálatakor Szín(v) = fehér; vagy másképp: ∃ u ~> v ∈ MFE út és |u ~> v| = 1
Visszaél: ha u leszármazottja v-nek a MFE-ben; u → v él vizsgálatakor Szín(v) = szürke
Előreél: ha v leszármazottja u-nak a MFE-ben és nem faél , azaz Apa(v) ≠ u;; u → v él vizsgálatakor Szín(v) = fekete és d(u) < d(v); vagy másképp: ∃ u ~> v út és |u ~> v| > 1
Keresztél: Minden más esetben; u → v él vizsgálatakor Szín(v) = fekete és d(u) > d(v)

Topologikus rendezés definíciója, a körmentesség és a visszaélek kapcsolata

Topológikus rendezés

Egy G = (V, E) irányított gráf topologikus rendezésén a V pontjainak egy olyan <v1,v2...vn> (n = |V|) felsorolását értjük, amelyre teljesül, hogy minden (u, v) ∈ E élre, u előbb áll a felsorolásban mint v.

A G = (V, E) irányított gráfnak akkor és csak akkor van topologikus rendezése, ha G körmentes.

A G = (V, E) irányított gráfban akkor és csak akkor van kör, ha van vissza-éle.

Topologikus rendezést megadó algoritmus

Végrehajt egy mélységi keresés az f elhagyási időkkel
amikor egy pont vizsgálatát befejezzük, akkor egy lánc elejére beszúrjuk
A rendezés a lánc szerint Megj.: a pontok csökk. F érték szerint vannak

Ha a G irányított gráf körmentes, akkor pontjainak minden olyan <v1,...vn> felsorolása, amelyre

                             f (vi ) > f (vi+1 ); i = 1,...n − 1

G egy topologikus rendezése lesz bármely mélységi bejárással kiszámított f elhagyási függvényre.

Ennek függvényében a következő kódban R[] egy olyan tömb lesz melynek mérete megegyezik a V pontjainak számával. Ez a tömb hátulról lesz kitöltve, úgy hogy az a pont kerül bele legelösször (hátra, n helyre) amelyiket elösször hagyjuk el (jelöljük feketével). A legelső elem a tömben (R[0]) tehát az a pont lesz amelyiket legutoljára hagytuk el, azaz a legnagyobb elhagyási számmal rendelkező.

Java kód

public class TopRend
{
  private: 
    enum Paletta {Feher, Szurke, Fekete};   //Osztályra scope-ban érvényes változók
    static Paletta[] Szin;

    int[] R;
    int n;

    boolean MelyBejar(Graf G, int p)
    {
       Szin[p]=Paletta.Szurke;              //p pontot szürkével jelöli
       for (int q:G.Ki(p))                  //p->q él vizsgálatának kezdete
       {
           if (Szin[q]==Paletta.Szurke)     //kört találtunk, nem lehet rendezést csinálni hiba!
           return false;

           if (Szin[q]==Paletta.Feher)
           {
              if (!MelyBejar(G,q))          //Rekurzív hivás p pont q fiára
                  return false;             //hiba hogyha találunk kört a leszármazottakban
           }
       }
       R[n--] = p;                          //beirjuk a pontott az R lánc elejére. n-et a Rendez() a
       Szin[p] = Paletta.Fekete;            //G pontjainak számával teszi egyenlővé.
       return true;                         //feketével jelöljük a sikeresen elhagyott pontot
    }

  public int[] Rendez(Graf G)              //publikusan elérhető Rendezést végrehajtó metódus
    {
       n = G.Pontokszama();
       Szin = new Paletta[n+1];            //szineket tároló tömb, mint a szinezős bejárásnál
       R = new int[n+1];                   //pontok rendezett sorrendjét tárolja

       for (int p:G)                       //minden pontot a Szin táblán fehérrel jelöl, kifehérit
           Szin[p]=Paletta.Feher;

       for (int p:G)
       {
          if (Szin[p] == Paletta.Feher)     
             if (!MelyBejar(G,p))          //meghívja MelyBejart()-t és ellenörzi hogy nem-e talált kört.
             {
               R=null;                     //ha sikertelen volt akkor talált kör, üres R-el kilép
               break;
             }
       }

       return R;
    }
}

Erősen összefüggő komponensek, és a transzponált gráf definíciója √

u ~ v ha u ~> v és v ~> u; u akkor és csak akkor van egy komponensben v-vel, ha u-ból vezet út v-be és v-ből is vezet út u-ba
Egy u pontot tartalmazó erősen összefüggő komponens: C(u) = {v ∈ V : u ~ v}
A G = (V, E) gráf transzponáltja: G^T = (V, E^T), ahol E^T = {(u, v) : (v, u) ∈ E}

Erősen összefüggő komponenseket előállító algoritmus √

Elvi algoritmus

Számítsuk ki a Mélykeresés algoritmussal az f(u) elhagyási értékeket.
A G^T transzponált gráfra alkalmazzuk a Mélykeresés eljárást úgy, hogy a pontokra a Mélybejár eljárást f szerint csökkenő sorrendben hívjuk.
A 2. pontban az egy mélységi feszítőfába kerülő pontok alkotnak egy erősen összefüggő komponenst.

bejárt: tömb, mely meghatározza, hogy egy pontban voltunk-e már
csökkenőF: verem, melyből csökkenő f szerint jönnek ki a pontok

Halmaz<Halmaz<int>> EÖK(Gráf G) {
	mélyKeres(G);
	return mélyKeresT(transzponál(G));
}

Gráf transzponál(Gráf G) {
	Gráf G^T;
	for(él : G.élek)
		G^T.bővít(él.be, él.ki);
	return G^T;
}

bool bejárt[n];
Verem<int> csökkenőF;
void mélyBejár(Gráf G, int u) {
	bejárt[u] = true;
	for(v : G[u].ki)
		if(!bejárt[v]) mélyBejár(v);
	csökkenőF.push(u);
}
void mélyKeres(Gráf G) {
	∀i bejárt[i] = false;
	for(v : G)
		if(!bejárt[v]) mélyBejár(v);
}

Halmaz<int> mélyBejárT(int p, Halmaz<int> komponens) {
	bejárt[p] = true;
	for(int i = 0; i < grafT[p].size(); ++i)
		if(!bejárt[grafT[p][i]])
			mélyBejárT(grafT[p][i], komponens);
	komponens.insert(p);
	return komponens;
}
Halmaz<Halmaz<int>> mélyKeresT(Gráf G) {
	bejárt = false;
	Halmaz<Halmaz<int>> komponensek;
	while(!csökkenő.empty()) {
		int p = csökkenőF.pop();
		Halmaz<int> komponens;
		if(!bejárt[p]) {
			komponens = mélyBejárT(p, komponens)
			komponensek.insert(komponens);
		}
	}
	return komponensek;
}

A súlyozott gráf (SGraf) adattípus specifikációja √

Értékhalmaz: Gráf = {G = (V, E, C) : V ⊆ PontTípus, E ⊆ V × V, C : E → CímkeTípus}
Műveletek: Gráfműveletek +

G : Gráf; p, p1, p2 : PontTípus; c : CímkeTípus; I : ÉlIterator

Előtte	Művelet	Utána
{G = (V, E), p1, p2 ∈ V}	ÉlBővít(G, p1, p2, c)	E = Pre(E) ∪ {(p1, p2)} ∧ C(p1, p2) = c;}
{G = (V, E), (p1, p2) ∈ E}	ÉlCímke(G, p1, p2, c)	{c = Pre(C)(p1, p2) ∧ E = Pre(E)}
{G = (V, E), (p1, p2) ∈ E}	ÉlCímkéz(G, p1, p2, c)	{C(p1, p2) = c ∧ E = Pre(E)}
{G = G}	KiCímkézettÉl(G, p)	{ = {(q, s) : VanÉl(p, q) ∧ C(p, q) = s} }
{G = G}	ÉlIterátor(G, I)	{ = {(p1, p2) : (p1, p2) ∈ E} }

Minimális feszítőfa problémája, a vágások és a biztonságos élek kapcsolatát leíró tétel

A vágások és biztonságos élek kapcsolata: Legyen G = (V,E) egy összefüggő, írányítatlan, a w : E -> R függvénnyel élsúlyozott gráf. Legyen A egy olyan részhalmaza E-nek, amelyik G valamelyik minimális feszítőfának is része. Legyen (S,V-S) tetszőleges A-t elkerülő vágása a G-nek. Legyen (u,v) az (S,V-S) vágást keresztező könnyű él. Ekkor az (u,v)él biztonságos az A-ra nézve.

Kruskal algoritmus √

fa, unioholvan, prisorba(minden él)

kivesz egy él, ha különböző fában vannak akkor két fát összekötni

Gráf Kruskal(SúlyozottGráf G){
	Gráf feszítőFa;
	UnioHolvan H(G.size());
	
	PriSor<SúlyozottGráfÉl> S(G.size());
	for(él : G.élek) S.push(él);

	while (!S.empty()) {
		SúlyozottGráfÉl él = S.pop();
		int fa1 = H.Holvan(él.ki);
		int fa2 = H.Holvan(él.be);
		if (fa1 != fa2) {
			H.Unio(fa1, fa2);
			feszítőFa.ÉlBővit(él.ki, él.be);
		}
	}
	if (H.size() != 1) //G nem összefüggő!
		feszítőFa = NULL;
	return feszítőFa;
}

Prim algoritmus √

Prim(SúlyozottGráf<double> G, int start) {
	int n = G.size();
	int apa[1..n] = -1;
	double d[1..n] = ∞;
	bool fa[1..n] = false;
	ModPriSor<double> S(n);
	fa[start] = true;
	d[start] = apa[start] = 0;
	for (v : G)
		S.push( (d[v], v) );
	while (!S.empty()) {
		u = S.pop();
		// kiveszi a minimális elemet, és beveszi a fába
		fa[u.adat] = true;
		for (v : G[u.adat].ki) {
			// még nincs a fában és jobb, mint ami van, akkor update
			if (!fa[v.pont] && súly(u, v) < d[v.pont]) {
				d[v.pont] = súly(u, v);
				apa[v.pont] = u.adat;
				S.modify(v.pont, d[v.pont]);
			}
		}
	}
}

Dijsktra algoritmus √

Dijkstra(SúlyozottGráf<double> G, int start/*, int end*/) {
	int n = G.size();
	int apa[1..n] = -1;
	double d[1..n] = ∞;
	bool kész[1..n] = false;
	ModPriSor<double> S(n);
	fa[start] = true;
	d[start] = apa[start] = 0;
	for (v : G)
		S.push( (d[v], v) );
	while (!S.empty()) {
		u = S.pop();
		kész[u.adat] = true;
		// if(u.adat == end) return; // elértük a keresett pontot
		for (v : G[u.adat].ki) {
			if (!kész[v.pont]) {
				double d_uv = d[u.adat] + v.súly;
			 	if(d_uv < d[v.pont]) {
					d[v.pont] = d_uv;
					apa[v.pont] = u.adat;
					
					v.kulcs = d_uv;
					S.modify(v);
				}
			}
		}
	}
}

A legrövidebb utak felső korlát és konvergencia tulajdonságai √

Felső korlát tulajdonság: D[v] > δ(s, v) és ha egyszer D[v] = δ(s, v), akkor ezután mindig teljesül a D[v] = δ(s, v) egyenlőség.
Konvergencia tulajdonság: Ha s ~> u → v egy legrövidebb út és D[u] = δ(s, u) Közelít(u, v) végrehajtása előtt, akkor Közelít(u, v) után D[v] = δ(s, v).

Floyd-Warshall algoritmus √

void FW(SúlyozottGráf G) {
	int n = G.Pontokszáma();
	double D[1..n, 1..n] = ∞;
	int előző[1..n, 1..n] = 0;
	for (int u : G){
		D[u, u] = 0.0;
		for (v : G[u].ki) {
			D[u, v] = G[v].súly;
			előző[u, v] = v;
		}
	}
	for (k = 1..n)
		for (i = 1..n)
			for (j = 1..n) {
				double Dikj=D[i, k]+D[k, j];
				if (Dikj < D[i, j]) {
					D[i, j]=Dikj;
					előző[i, j] = előző[i, k];
				}
			}
}

void ÚtKiír(int[][] előző, int u, int v) {
	if (előző[u, v] == 0) {
		kiír("Nincs " + u + "->"+ v + " út!");
		return;
	}
	do {
		kiír(u + "->");
		u = előző[u, v];
	} while (u != v);
	kiír(u);
}

Kiválasztó rendezés algoritmusa √

template<typename T> void KiválasztóRendezés(T* tömb, int n /*hossz*/) {
	for(int i = 0; i < n; ++i) {
		// minimum kiválasztás
		int minIndex = i;
		for(int j = i + 1; j < n; ++j)
			if(tömb[j] < tömb[minIndex])
				minIndex = j;
		// csere a minimum és az aktuális eleje
		swap(tömb[minIndex], tömb[i]);
		// így a sor aktuális elején mindig a minimális elem lesz
	}
}

Beszúró rendezés algoritmusa √

template<typename T> BeszúróRendezés(T* tömb, int n /*hossz*/) {
	for(int i = 1; i < n; ++i) {
		T temp = tömb[i];
		j = i - 1;
		while (0 <= j && temp < tömb[j])
			tömb[j + 1] = tömb[j--];
		tömb[j + 1] = temp;
	}
}

Kupac adatszerkezet definíciója, süllyeszt algoritmus √

Kupac: Olyan (bináris) fa, amely teljesíti a kupactulajdonságot.
Kupactulajdonság: Ha B A gyereke, akkor a (maximális) kupactulajdonság: kulcs(A) ≥ kulcs(B)

template<typename T> void Sullyeszt(T* kupac, int pont, int vege){
	int apa = pont;
	int fiu;
	T temp = kupac[pont];
	while ((fiu = 2*apa + 1) < vege ) {          //a nulla indexelés miatt a 2*apa + 1 adja a bal gyereket
//pelda: 8, 2, 5, 7, 6.     a 0 indexelés szerinti 1. elem azaz a "2" bal gyermeke a "2*1 + 1 = 3" indexű elem, azaz a "7".
		// ha jobb gyerek > bal gyerek, akkor átlép jobb gyerekre
		if (kupac[fiu + 1] > kupac[fiu]) fiu++;
		// ha teljesül a kupac tulajdonság, akkor megáll
		if (temp >= kupac[fiu]) break;
		// a gyereket feljebb hozza
		kupac[apa] = kupac[fiu];
		apa = fiu;
	}
	// a javítandó elemet beteszi az utolsó emelt gyerek helyére
	kupac[apa] = temp;
}

Kupacrendezés algoritmusa, a süllyeszt algoritmussal együtt √

template<typename T> void KupacRend(T* tomb, int n /*hossz*/) {
	n = n - 1; // nulla indexelés miatt
	// épít egy kupacot
	for (int i = n / 2; i >= 0; --i)
		Sullyeszt(tomb, i, n);

	// a kupac legnagyobb elemét kicseréli az utolsó elemmel
	// majd kijavítja a kupacot, ami mostmár nem a teljes, hossz, hanem csak az "utolsó" előtti elemtől számít
	for (int i = n; i >= 0; --i) {
		swap(tomb[0], tomb[i]); 
		Sullyeszt(tomb, 0, i - 1);
	}
}

Gyorsrendezés algoritmusa, a feloszt algoritmussal együtt, egy tömbben megvalósítva √

template<typename T> int Feloszt(T* tömb, int bal, int jobb) {
	T osztó = tömb[bal];
	int b = bal;
	// H = tömb[bal..jobb]
	for (int j = bal + 1; j <= jobb; j++) {
		// invariáns: H_bal = tömb[bal..j] < osztó ≤ H_jobb = tömb[j + 1..jobb]
		if (tömb[j] < osztó) {
			tömb[b] = tömb[j];
			tömb[j] = tömb[++b];
		}
	}
	tömb[b] = osztó;
	return b;
}

template<typename T> void GyorsRendezés(T* tömb, int bal, int jobb) {
	int felosztás = Feloszt(tömb, bal, jobb);
	if (bal < felosztás)
		GyorsRendezés(tömb, bal, felosztás - 1);
	if (felosztás + 1 < jobb)
		GyorsRendezés(tömb, felosztás + 1, jobb);
}
template<typename T> void GyorsRendezés(T* tömb, int hossz) {
	GyorsRendezés(tömb, 0, hossz - 1);
}

Számláló rendezés (input specifikációval) √

Tegyük fel, hogy a rendezendő A = {a₁, ..., a_n} halmaz elemei (kulcs, adat) pár és a halmazt a kulcs szerint kell rendezni. Legyen min a legkisebb, max pedig a legnagyobb kulcsérték, m = max - min. Ekkor a rendezés elvégezhető O(m + n) időben.
Teljes megvalósítás

pair<KulcsTípus, AdatTípus>[] szamlalo(pair<KulcsTípus, AdatTípus> A[n]) {
	KulcsTípus min, max;
	for(int i = 0; i < n; ++i) {
		if(A[i].kulcs > max) max = A[i].kulcs;
		if(A[i].kulcs < min) min = A[i].kulcs;
	}
	int m = max - min + 1;
	KulcsTípus C[m] = 0;

	for(int i = 0; i < n; ++i) C[ A[i].kulcs - min ]++;
	for(int i = 1; i < m; ++i) C[i] += C[i - 1];
	pair<KulcsTípus, AdatTípus> B[n];
	for(int i = 0; i < n; ++i) B[ --C[ A[i].kulcs - min ] ] = A[i];
	return B;
}

Rövidített megvalósítás: Tegyük fel hogy a rendezés kap egy tömböt, melyben a számok 0 ≤ A[i] ≤ max, ∀ 0 ≤ i < n-re, ahol n a tömb hossza.

int[] szamlalo(int A[n], int max) {
	int C[max] = {0};
	// megszámolja hogy adott elemből mennyi van
	for(int i = 0; i < n; ++i) C[ A[i] ]++;
	// összeszámolja, hogy adott elemnél kisebb-egyenlő mennyi van
	for(int i = 1; i < max; ++i) C[i] += C[i - 1];

	int B[n];
	// feltölti az új - leendő rendezett - tömböt C-nek megfelelően
	for(int i = 0; i < n; ++i) B[ --C[ A[i] ] ] = A[i];
	return B;
}

Radix rendezés (input specifikációval)

Példa

Rendezetlen		Utolsó jegy szerint		Középső jegy szerint		Első jegy szerint
329	→	720	→	720	→	329
457		355		329		355
657		436		436		436
839		457		839		457
436		657		355		657
720		329		457		720
355		839		657		839

Vödrös rendezés (input specifikációval)

Tegyük fel, hogy a rendezendő H = {a₁, ..., a_n} halmaz elemeinek kulcsai a [0,1) intervallumba eső valós számok (float vagy double).

Pszeudo kód wiki-ről: Vödrös rendezés, de szerintem ez kevés:

lista VödrösRendezés(tömb[n], vödrökSzáma) {
	lista vödrök[vödrökSzáma];
	for(i = 0..n-1)
		vödrök[(int)(tömb[i] * vödrökSzáma)].beszúr(tömb[i]);
	for(i = 0..n-1)
		next-sort(vödrök[i]);
	return vödrök[0] + ... + vödrök[n-1];
}

Kibővített euklideszi algoritmus √

Visszatér a és b legnagyobb közös osztójával és p, q kimeneti paraméterekben megadja p * a₀ + q * b₀ = lnko(a, b) paramétereit

int euclid(int a, int b, int& p, int& q) {
	// We maintain the invariant:
	// p * a0 + q * b0 = a
	// r * a0 + s * b0 = b.
	if(a < b) swap(a, b);
	int s = p = 1, r = q = 0;
	while (b != 0) {
		int rem = a % b, quot = a / b;
		a = b; b = rem;
		int new_r = p - quot * r;
		int new_s = q - quot * s;
		p = r; q = s;
		r = new_r; s = new_s;
	}
	return a;
}

Bináris keresőfa definíciója , Keres algoritmus √

Az F fát bináris fának nevezzük, ha (∀p ∈ F)(Fok(p) ≤ 2).

Ábrázolás

struct Fa {
	ElemTípus adat;
	Fa* bal;
	Fa* jobb;
//	Fa* apa;
};

A F = (M, R, Adat) absztrakt adatszerkezetet bináris keresőfának nevezzük, ha

F bináris fa,
Adat : M → ElemTípus és ElemTípus-on értelmezett egy ≤ lineáris rendezési reláció,
(∀x ∈ M)(∀p ∈ F_bal(x))(∀q ∈ F_jobb(x))(Adat(p) ≤ Adat(x) ≤ Adat(q))

Fa* Keres(Fa* fa, ElemTípus adat){
	while (fa != NULL) && (adat != fa->adat)
		if (adat < fa->adat)
			fa = fa->bal;
		else
			fa = fa->jobb;
	return fa;
}

Rákövetkező elem megtalálása bináris keresőfában √

Fa* Következő(Fa* fa) {
	// ha van jobb részfája
	if(fa->jobb != NULL) {
		fa = fa->jobb;
		// megkeresi annak minimális elemét
		while (fa->bal != NULL)
			fa = fa->bal;
		return fa;
	} else {
		Fa* fiu = fa;
		Fa* apa = fiu->apa;
		// felmegy a fában amíg a fiú nem lesz bal fiú
		while (apa != NULL && fiu != apa->bal) {
			fiu = apa;
			apa = fiu->apa;
		}
		return apa;
	}
}

Beszúrás bináris keresőfába √

struct Fa {
	int adat;
	Fa* bal, jobb;
	Fa(int n): adat(n) {}
};
void beszur(Fa* gyoker, int n) {
	Fa* jelen = NULL;
	Fa* kov = gyoker;
	// megkeresi a beszúrás helyét, jelen-ben a beszúrandó elem apja lesz
	while(kov) {
		jelen = kov;
		if(n < kov->adat)
			kov = kov->bal;
		else
			kov = kov->jobb;
	}
	// létrehozza az új pontot
	kov = new Fa(n);
	if(jelen == NULL) // üres fa
		gyoker = kov;
	else // normál fa, beszúrja a megfelelő helyre
		if(n < jelen->adat)
			jelen->bal = kov;
		else
			jelen->jobb = kov;
}

Törlés bináris keresőfában √

levél

egyszerű törlés

egy gyerek

csere a másik gyerekre, majd törlés

két gyerek

kicseréljük az értékét
- vagy inorder következővel (jobb részfa min)
- vagy inorder előzővel (bal részfa max)
majd törlés

struct Pont {
	Pont* bal;
	Pont* jobb;
	int érték;
};
void Töröl(Pont* pont) {
	Pont* temp = pont;
	// egy gyerek: jobb, (és levél, ha pont = pont->jobb NULL)
	if (pont->bal == NULL) {
		*pont = *pont->jobb; // copy constructor
		delete temp;
	// egy gyerek: bal
	} else if (pont->jobb == NULL) {
		*pont = *pont->bal; // copy constructor
		delete temp;
	// két gyerek
	} else {
		temp = pont->jobb;
		while (temp->bal != NULL)
			temp = temp->bal;
		// csere helyett, elég lementeni a következő elemet, mivel a jelenlegit úgyis töröljük
		pont->érték = temp->érték;
		Töröl(temp); // lehet hogy van neki 1 gyereke
	}
}

//===Hibák, észrevételek=== //#n3.pdf: 3.3 PriSor.SorBol() művelet végeredménye nem Pre(S) ∪ {x}, hanem Pre(S) \ {x} //#...

kikommenteztem, mert nincs benne hiba.

A Sullyeszt algoritmusban az alábbi utasításban azt is ellenőrizni kellene, hogy van-e jobb gyermeke is az apa-nak (fiu + 1 < vege). if (kupac[fiu + 1] > kupac[fiu]) fiu++;

Rendezetlen		Utolsó jegy szerint		Középső jegy szerint		Első jegy szerint
329	→	720	→	720	→	329
457		355		329		355
657		436		436		436
839		457		839		457
436		657		355		657
720		329		457		720
355		839		657		839

Rendezetlen		Utolsó jegy szerint		Középső jegy szerint		Első jegy szerint
329	→	720	→	720	→	329
457		355		329		355
657		436		436		436
839		457		839		457
436		657		355		657
720		329		457		720
355		839		657		839

Programozás/Algoritmusok

Az O, Ω, Θ, o, ω jelölések definíciója √

Definíciók és magyarázatok

Kiegészítés

A partíciószám kiszámításának rekurzív algoritmusa √

VeremBol, VeremBe, SorBol, SorBa és a Prioritási sor adattípus SorBol, SorBa műveletek specifikációja √

A Halmaz adattípus specifikációja √

A Függvény adattípus Kiolvas, Modosit, Bovit és Torol műveleteinek specifikációja √

A Reláció adattípus APar, KPar, ATorol, KTorol műveleteinek specifikációja √

Lánc és körlánc absztrakt adatszerkezetek definíciói √

Lánc

Körlánc

A nem rendezett fa definíciói (bináris reláció, és apa függvény) √

Bináris reláció

Apa függvény

A rendezett fa absztrakt adatszerkezet definíciója fi függvényekkel √

Fa absztrakt adatszerkezet algebrai definíciója √

Általános absztrakt adatszerkezet definíciója √

Különbségek a gráf és általános absztrakt adatszerkezetek között (nem anyag)

Fa adatszerkezet kapcsolati tömb, kapcsolati lánc ábrázolásai √

Kapcsolati tömb

Statikus

Dinamikus (nem anyag)

Kapcsolati lánc

Fa adatszerkezet elsőfiú-testvér, elsőfiú-testvér-apa ábrázolásai √

Elsőfiú-testvér

Elsőfiú-testvér-apa

Preorder rekurzív fabejáró algoritmus √

Szintszerinti fabejáró algoritmus √

Partíció probléma megoldása rekurziómemorizálással √

Partíció probléma dinamikus programozási megoldása (táblázat-kitöltéssel) √

Pénzváltási probléma definíciója, részproblémák definíciója, a közöttük levő összefüggések √

Pénzváltási probléma egy megoldásának előállítása táblázat-kitöltéssel

Optimális pénzváltási probléma definíciója, részproblémák definíciója, a közöttük levő összefüggések

Optimális pénzváltási probléma megoldása táblázat-kitöltéssel (egy megoldást is előállítani)

Mátrixszorzás probléma definíciója, részproblémák definiálása, a közöttük levő összefüggések

Hátizsák probléma definíciója, részproblémák definiálása, a közöttük levő összefüggések

Optimális bináris keresőfa definíciója, részproblémák definíciója, a közöttük levő összefüggések

Optimális bináris keresőfa megoldása táblázat-kitöltéssel (egy optimális bináris keresőfa előállítása)

Eseménykiválasztási probléma definíciója, megoldó algoritmus

Optimális prefix kód probléma definícója, Huffman-kód szerkesztő algoritmus

A Graf adattípus specifikációja √

Kapcsolatmátrix, éllista gráf-reprezentációk, Tárigény, VanEl, Eliteráció, KiIteráció időigénye √

Kapcsolatmátrix (szomszédsági mátrix)

Éllista

Statikus

Dinamikus

Általános

Igények (n = |V|, m = |E|, k = |Ki(G, p)|)

Út, legrövidebb út definíciója súlyozott és súlyozatlan gráfokban √

Szélességi keresés algoritmusa √

Mélységi keresés algoritmusa √

"Színezős MélyKeresés"

Zárójelezési tétel

Élek osztályozása (faél, előre él, visszaél, keresztél definíciója) √

Topologikus rendezés definíciója, a körmentesség és a visszaélek kapcsolata

Topologikus rendezést megadó algoritmus

Erősen összefüggő komponensek, és a transzponált gráf definíciója √

Erősen összefüggő komponenseket előállító algoritmus √

A súlyozott gráf (SGraf) adattípus specifikációja √

Minimális feszítőfa problémája, a vágások és a biztonságos élek kapcsolatát leíró tétel

Kruskal algoritmus √

Prim algoritmus √

Dijsktra algoritmus √

A legrövidebb utak felső korlát és konvergencia tulajdonságai √

Floyd-Warshall algoritmus √

Kiválasztó rendezés algoritmusa √

Beszúró rendezés algoritmusa √

Kupac adatszerkezet definíciója, süllyeszt algoritmus √

Kupacrendezés algoritmusa, a süllyeszt algoritmussal együtt √

Gyorsrendezés algoritmusa, a feloszt algoritmussal együtt, egy tömbben megvalósítva √

Számláló rendezés (input specifikációval) √

Radix rendezés (input specifikációval)

Példa

Vödrös rendezés (input specifikációval)

Kibővített euklideszi algoritmus √

Bináris keresőfa definíciója , Keres algoritmus √

Rákövetkező elem megtalálása bináris keresőfában √

Beszúrás bináris keresőfába √

Törlés bináris keresőfában √

A rendezett fa absztrakt adatszerkezet definíciója f_i függvényekkel √

Rendezetlen		Utolsó jegy szerint		Középső jegy szerint		Első jegy szerint
329	→	720	→	720	→	329
457		355		329		355
657		436		436		436
839		457		839		457
436		657		355		657
720		329		457		720
355		839		657		839