Szerkesztő:TWiStErRob/Alga

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 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 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:
	// a 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);
}

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; ki++) { // 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

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
}

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

A mátrixszorzás probléma feladata egy adott szorzás optimális zárójelezésének megadása. Input: A1,A2,...,An ahol Ai mérete pi-1 × pi .

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

Minden j-edik tárgy súlya wj, értéke cj; a hátizsák kapacitása C.

Cél: a tárgyak olyan I halmazát belepakolni a hátizsákba, hogy ∑ wi ≤ C és ∑cj → max (i és j eleme I).
Rekurzív összefüggések: R(i,s) = max {R(i-1,s), ci+R(i-1,s-wi)}

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

Prefíx kód: olyan kód, amire igaz, hogy egyik kód sem kezdőszelete a másiknak.
Feladat: olyan prefix kód szerkesztése, hogy minimális legyen a szöveg várható hossza.
- Adottak karakterek és gyakoriságok.

Huffman (c: karakterek, f: gyakoriságok) {
    Létesít Prisor Q
    Q:=C
    for i=1 to n-1 {
	x:=Sorbol(Q)        //két legkisebb elem, x ≤ y
	y:=Sorbol(Q)
	Lértehoz pont z
	z.bal:=x            //fapont "felfűzése"
	z.jobb:=y           //fapont "felfűzése"
	f(z):=f(x)+f(y)
	Sorba(Q,z)
    }
}

C a karakterek n elemű halmaza. A fát alulról építi fel, mindig a két legkisebb Q-beli elemet adjuk össze.

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: CímkeTípus G[|V|, |V|];: 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 √

szelkeres(Graf G, start) {
	Sor S;
	int apa[1..G.size()] = -1;
	int d[1..G.size()] = ∞;
	apa[start] = 0;
	d[start] = 0;
	S.push(start);
	while(!S.empty()) {
		u = S.pop();
		for(v : G[u].ki) {
			if(apa[v] == -1) {
				apa[v] = u;
				d[v] = d[u] + 1;
				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

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

"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[v] == 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

Irányított, körmentes gráf
Sorba kell rendezni az éleit úgy, hogy minden él előre mutasson

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

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

u ~ v acsa, 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.

Legyen G = (V,E,c), c : E ->R súlyozott irányítatlan gráf. Terjesszük ki a c súlyfüggvényt a T⊆E élhalmazokra: C(T) = Szumma (u,v) eleme T-re c(u,v)

Az F = (V,T) gráf minimális feszítőfája G-nek, ha 1. F feszítőfája G-nek, és 2. C(T)-> minimális

Input: G = (V,E,c); c : E ->R irányítatlan gráf

Output: MFF = (V,F); minimális feszítőfája G-nek

Legyen A⊆F valamely MFF = (V,F) M.F.F.-nak és (u,v)∈E.

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

legrövidebb út súlya: δ(s, v)

legrövidebb-út-becslése: D[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 ) {
		// 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}
Párat a közepén bemásoltam PDF-ből (részben és egészben), plussz 3-4 def-be belenyúltam (csak mondat tagolás és pontosvesszőket javítottam). Ha ezekkel baj van, engem tessék szidni: Balog Zoltán.
...

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

Szerkesztő:TWiStErRob/Alga

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