Jelölések (Notations)

Alapvető jelölések:

• $\mathbb{B} = \{ false; true \}$ a logikai (boolean) értékek halmaza
• $\mathbb{N} = \{0; 1; 2; 3;...\}$ a természetes számok halmaza
• $\mathbb{Z} = \{...-3; -2, -1; 0; 1; 2; 3;...\}$ az egész számok halmaza

• $\mathcal{T}$ valamilyen ismert típust jelöl, amelyen az értékadás és az összehasonlító operátorok értelmezve vannak

Struktogram jelölések:

$algoritmusNeve(parameterek) : visszateresiErtek$

---

$...$
$...$		$...$
$...$

Függvényfejnél használt jelölések:

Visszatérési érték:

Visszatérési érték lehet $\mathbb{N}$, $\mathbb{B}$, $\mathbb{R}$, $E1^*$, stb....

• $Algoritmus() : \mathbb{B}$ függvény visszatérési értéke logikai típusú
• $Algoritmus() : \mathbb{N}$ függvény visszatérési értéke természetes szám
• $Algoritmus()$ függvénynek nincs visszatérési értéke, az ilyen függvényt eljárásnak is hívjuk

Paraméterek:

• $x : \mathcal{T}$ $x$ nevű, $\mathcal{T}$ típusú változó
• $\&x : \mathcal{T}$ cím szerinti átvett, $x$ nevű, $\mathcal{T}$ típusú változó
• $A/1 : \mathcal{T}[n]$ $A$ nevű, 1-től indexelt, $n$ méretű, $\mathcal{T}$ típusokat tároló tömb
• $Z : \mathcal{T}[n]$ $Z$ nevű, 0-tól indexelt, $n$ méretű, $\mathcal{T}$ típusokat tároló tömb

Alprogram törzsében használt jelölések:

• $:=$ értékadás
• $=$ egyenlőségvizsgálat
• $\land$ és
• $\lor$ vagy
• $\neg$ negálás

• $p : \mathcal{T}$ változó deklaráció, vagy ha paraméterként szerepel, akkor a paraméter specifikálása, $p$ $\mathcal{T}$ típusú
• $p : E1^*$ változó deklaráció, vagy ha paraméterként szerepel, akkor a paraméter specifikálása, $p$ $E1$ típusú pointer
• $P := \text{new} \space \mathcal{T}[n]$ létrehoztunk egy tömb-objektumot és a címét értékül adjuk a $P$ pointernek
• $\text{delete} \space P$ dinamikusan létrehozott objektum törlése

• $Write()$ kiírás
• $Read()$ beolvasás
• $A.length$ tömb hossza
• $\otimes$ valamilyen operátort jelöl, pl.: $+, -, *, /$, stb. (lengyel forma)
• bal $\otimes$ jobb elvégezzük a műveletet (lengyel forma)
• $v : Stack(n)$ $v$ nevű, $n$ méretű verem deklarálása
• $q : Queue()$ $q$ nevű sor deklarálása

Ciklusokban:

• $i := 1 \space to \space n$ növekvő for ciklus, 1-től n-ig
• $i := n \space downto \space 1$ csökkenő for ciklus, n-től 1-ig
• $i < n$ feltétel a while ciklusban

Futási időhöz kapcsolódó jelölések:

• $T(n) \in \Theta(n^2)$ az algoritmus futási ideje
• $T_{MS}(n) \in \Theta(n^2)$ az $MS$ nevű (MergeSort) algoritmus futási ideje
• $mT(n) \in \Theta(n^2)$ minimális futási ideje az algoritmusnak (legjobb eset), $n$ darab bemenet esetén $\Theta(n^2)$
• $MT(n) \in \Theta(n^2)$ maximális futási ideje az algoritmusnak (legrosszabb eset), $n$ darab bemenet esetén $\Theta(n^2)$
• $AT(n) \in \Theta(n^2)$ átlagos futási ideje az algoritmusnak, $n$ darab bemenet esetén $\Theta(n^2)$

• $mT(n) \leq AT(n) \leq MT(n)$

Láncolt listákhoz kapcsolódó jelölések:

• $p := \emptyset$ $p$ nevű, nullpointer létrehozása
• $\text{delete} \space p$ $p$ pointer által mutatott listaelem törlése
• $p \rightarrow key$ $p$ pointer által mutatott listaelem $key$ adattagjának elérése
• $p \rightarrow next$ $p$ pointer által mutatott listaelem $next$ adattagjának elérése
• $p := \text{new} \space E1$ új listaelem létrehozása

Hasító táblához kapcsolódó jelölések:

• $m$ hasító tábla mérete
• $T[0..m)$ hasító tábla
• $T[x]$ hasító tábla $x$-edik helye, más néven rése
• $\emptyset$ üres rés a hasító táblában
• $n$ hasító táblában tárolt adatok száma
• $\alpha = \frac{n}{m}$ tábla kitöltöttségi aránya
• $U$ kulcsok univezuma
• $h : U \rightarrow 0..(m-1)$ hasító függvény

• $E$ nyílt címzésnél üres rés
• $D$ nyílt címzésnél törölt rés

Tömörítéshez kapcsolódó jelölések:

• $\sum$ az eredeti abc-ből használt betűk halmaza
• $d$ az abc betűinek számossága, hányféle karaktert használunk
• $n$ tömörítendő szöveg hossza
• $T$ kódszavak nem üres halmaza
• $r$ az információ alapegysége

Gráfokhoz kapcsolódó jelölések:

• $G = (V, E)$ $G$ nevű gráf, amelyet egy rendezett párosként értelmezünk, ahol $E \subseteq V \times V$ az élek halmaza, kivéve a hurokéleket, $V$ a csúcsok halmaza
• $A/1:bit[n,n]$ $n$-szer $n$ méretű, "bit mátrix", tehát csak 0-ákat és 1-eseket tartamazó mátrix, amit az élsúlyozatlan, csúcsmátrixos gráfábrázolásnál használunk

• $G : \mathcal{G}$ $G$ nevű élsúlyozatlan gráf
• $G : \mathcal{G}_w$ $G$ nevű élsúlyozott gráf

• $A : \mathcal{E} \{\}$ $A$ nevű élhalmaz
• $A := \{\}$ $A$ legyen egy üres halmaz
• $e : \mathcal{E}$ $e$ nevű él
• $A \cup \{ (u,v) \}$ az $A$ élhalmazhoz hozzávesszük az $(u, v)$ élt

• $d(u)$ az $u$ csúcsba mekkora költséggel jutunk el
• $e(u)$ az $u$ csúcsba hány élen keresztül jutunk el (Sor-alapú Bellman-Ford algoritmus)
• $\pi(u)$ melyik csúcsból jutunk el az $u$ csúcsba, ki a szülője

• $c(u)$ az $u$ csúcsba mekkora költséggel jutunk el (Prim algoritmusa)
• $p(u)$ melyik csúcsból jutunk el az $u$ csúcsba, ki a szülője (Prim algoritmusa)

Mintaillesztésnél használt jelölések:

• $T:\sum[n]$ $T$ nevű, nullától indexelt, $n$ méretű karakterek tömbje, ez a szöveg amelyben keresünk
• $P:\sum[m]$ $P$ nevű, nullától indexelt, $m$ méretű karakterek tömbje, ez a szöveg amelyet keresünk $T$-ben
• $s \in 0..(n-m)$ természetes szám, amely egy eltolást határoz meg
• $S : \mathbb{N} \{\}$ érvényes eltolások halmaza

• $\underline{B}$ az aláhúzás jelenti azt, hogy sikeres volt a mintaillesztés
• $\cancel{B}$ az áthúzás jelenti azt, hogy sikertelen volt a mintaillesztés