Algoritmusok és adatszerkezetek 1. > Aszimptotika és jelölések > Jelölések

Jelölések (Notations)

Ez az oldal egy gyakorlati jegyzet, amelynek anyagára a saját gyakorlati óráimat is építem. Fontos azonban, hogy vizsgára ne kizárólag ebből készülj!

Az elmúlt időszakban többször előfordult, hogy hallgatók az oldalon található anyagból készültek a vizsgára, és emiatt bizonyos feladatokra nem kaptak pontot. Ennek oka, hogy az itt szereplő anyagokat a tantárgyfelelősök nem ellenőrizték és nem lektorálták, így előfordulhatnak benne pontatlanságok, illetve olyan megfogalmazások vagy megközelítések, amelyek nem feltétlenül egyeznek a vizsgán elvárttal.

Az oldalt szabadidőmben készítettem azzal a céllal, hogy segítsem a hallgatók tanulását. A tartalom összeállítását hosszas anyaggyűjtés, könyvek és egyéb szakmai források áttekintése előzte meg, ennek ellenére hibák természetesen előfordulhatnak.

Folyamatosan igyekszem javítani a hibákat és pontosítani az anyagot.

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