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 √

szerkesztés

Definíciók és magyarázatok

szerkesztés
O(g(n))
{f(n) : (∃c, n0 ≥ 0)(∀n ≥ n0)(0 ≤ f(n) ≤ c*g(n))}
Azon f(n)függvények halmaza, amelyekhez létezik olyan c konstans és n0 kezdőindex, nemnegatív számok, hogy minden n-re, ami n0-nál nagyobb-egyenlő, az f(n) függvény c*g(n) alatt van.
Ω(g(n))
{f(n) : (∃c, n0 ≥ 0)(∀n ≥ n0)(0 ≤ c*g(n) ≤ f(n))}
Azon f(n)függvények halmaza, amelyekhez létezik olyan c konstans és n0 kezdőindex, nemnegatív számok, hogy minden n-re, ami n0-nál nagyobb-egyenlő, az f(n) függvény c*g(n) felett van.
Θ(g(n))
{f(n) : (∃c1, c2, n0 ≥ 0)(∀n ≥ n0)(0 ≤ c1*g(n) ≤ f (n) ≤ c2*g(n))}
O és Ω együtt teljesül
Azon f(n) függvények halmaza, amelyekhez léteznek olyan c1, c2 konstansok és n0 kezdőindex, nemnegatív számok, hogy minden n-re, ami n0-nál nagyobb-egyenlő, az f(n) függvény c1*g(n) és c2*g(n) között fut.
o(g(n))
{f(n) : (∀c > 0)(∃n0 > 0)(∀n ≥ n0)(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 n0 kezdőindex, hogy minden n-re, ami n0-nál nagyobb-egyenlő teljesül, hogy a függvény szigorúan c * g(n) alatt van.
ω(g(n))
{f(n) : (∀c > 0)(∃n0 > 0)(∀n ≥ n0)(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 n0 kezdőindex, hogy minden n-re, ami n0-nál nagyobb-egyenlő teljesül hogy a függvény szigorúan c * g(n) felett van.

Kiegészítés

szerkesztés
O, Ω, Θ, o, ω tranzitív
f(n) = *(g(n)) ∧ g(n) = *(h(n)) ⇒ f(n) = *(h(n))
mégpedig a nagyobb n0-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 √

szerkesztés
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 √

szerkesztés
Előtte Művelet Utána
{V = <a1, ..., an>} VeremBe(V, x) {V = <a1, ..., an, x>}
{0 < n ∧ V = <a1, ..., an>} VeremBől(V, x) {V = <a1, ..., an - 1> ∧ x = an}
{S = <a1, ..., an>} SorBa(S, x) {S = <a1, ..., an, x>}
{0 < n ∧ S = <a1, ..., an>} SorBól(S, x) {x = a1 ∧ S = <a2, ..., an>}
{P = {a1, ..., an}} 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 √

szerkesztés

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 = {a1, ..., an}} 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 √

szerkesztés

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 √

szerkesztés

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)

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

szerkesztés
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övetk(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övetn − 1(fej) = láncvég
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övetk(x))
bármely x ∈ M-re az <x = x0, x1, ..., xn−1> sorozat, ahol xi = követ(xi−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) √

szerkesztés

Bináris reláció

szerkesztés
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

szerkesztés
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)(Apak(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 fi függvényekkel √

szerkesztés
Legyen A = (M, R, Adat) olyan absztrakt adatszerkezet, hogy R = {f}, f : M → (M ∪ {ø})*.
x ∈ M, f(x) = <y1, ..., yk>, yi ∈ M ∪ {ø}, i = 1, ..., k.
Minden i > 0 természetes számra definiáljuk az fi : M → M ∪ {ø} függvényt a következőképpen:
 
Tehát fi(x) az x i-edik fiát adja. Ha fi(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
  1. a gyökér nem fia egyetlen pontnak sem:
     
  2. minden, gyökértől különböző pont fia valamely pontnak:
     
  3. minden pontnak legfeljebb egy apja lehet:
     
  4. minden pont elérhető a gyökérből:
     

Fa absztrakt adatszerkezet algebrai definíciója √

szerkesztés

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)(∀t1, ..., tk ∈ Fa(E))(a(t1, ..., tk) ∈ Fa(E))

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

szerkesztés
Olyan A = (M, R, Adat) rendezett hármas, ahol
  1. M az absztrakt memóriahelyek, cellák halmaza.
  2. R = {r1, ..., rk} a cellák közötti szerkezeti kapcsolatok, ri : M → (M ∪ {ø})*
  3. Adat : M → E parciális függvény, a cellák adattartalma.
x ∈ M, r ∈ R és r(x) = <y1, ..., yi, ..., yk> esetén az x cella r kapcsolat szerinti szomszédai {y1, ..., yk}, yi pedig az x cella i-edik szomszédja.
Ha yi = ø, 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)

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

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

szerkesztés

Kapcsolati tömb

szerkesztés
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)
szerkesztés

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
 
 , 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

szerkesztés
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 √

szerkesztés

Elsőfiú-testvér

szerkesztés
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

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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) √

szerkesztés

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 √

szerkesztés
Probléma
Pénzváltás
Bemenet
P = {p1, ..., pn} 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  .
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
 , tehát a megoldásban szereplő pénzérmék egy sorrendje
egy megoldása a feladatnak. Ekkor
 
megoldása lesz annak a feladatnak, amelynek bemenete a felváltandó   érték, és a felváltáshoz legfeljebb a első ik - 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ő p1, ..., pi 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 == pi), 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 > pi) ∧ V(X - pi, 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

szerkesztés
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

szerkesztés

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

szerkesztés

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

szerkesztés

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

szerkesztés

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

szerkesztés

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)

szerkesztés

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

szerkesztés

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

szerkesztés

A Graf adattípus specifikációja √

szerkesztés
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 √

szerkesztés

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

szerkesztés
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.
int G[|V|, |V|];
int KiFok[|V|];
Lánc<int> G[|V|];
Általános
szerkesztés
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)|)

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

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

szerkesztés

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 π = <p0, p1, ..., pk> pontsorozat, ahol p = p0, q = pk és pi ≠ pj, ha i ≠ j, vagy p = q = p0, továbbá teljesül (∀i ∈ {1, ..., k})((pi-1, pi) ∈ 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
π = <p0, p1, ..., pk> = 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
 .
p és q távolsága, p-ből q-ba vezető legrövidebb út hossza
 

Szélességi keresés algoritmusa √

szerkesztés

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 √

szerkesztés
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"

szerkeszté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

szerkesztés

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) √

szerkesztés
(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

szerkesztés
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

szerkesztés
  1. Végrehajt egy mélységi keresés az f elhagyási időkkel
  2. amikor egy pont vizsgálatát befejezzük, akkor egy lánc elejére beszúrjuk
  3. 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 √

szerkesztés
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
GT = (V, ET), ahol ET = {(u, v) : (v, u) ∈ E}

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

szerkesztés
Elvi algoritmus
  1. Számítsuk ki a Mélykeresés algoritmussal az f(u) elhagyási értékeket.
  2. A GT 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.
  3. 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 GT;
	for(él : G.élek)
		GT.bővít(él.be, él.ki);
	return GT;
}

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 √

szerkesztés
É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)}
É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} }
É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

szerkesztés

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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
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) √

szerkesztés
Tegyük fel, hogy a rendezendő A = {a1, ..., an} 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)

szerkesztés
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)

szerkesztés
Tegyük fel, hogy a rendezendő H = {a1, ..., an} 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 √

szerkesztés

Visszatér a és b legnagyobb közös osztójával és p, q kimeneti paraméterekben megadja p * a0 + q * b0 = 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 √

szerkesztés

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
  1. F bináris fa,
  2. Adat : M → ElemTípus és ElemTípus-on értelmezett egy ≤ lineáris rendezési reláció,
  3. (∀x ∈ M)(∀p ∈ Fbal(x))(∀q ∈ Fjobb(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 √

szerkesztés
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 √

szerkesztés
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 √

szerkesztés
  • 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++;