Definíciók
1.
Definiálja a bináris kupacot!
Def.: A bináris kupac egy szép bináris fa, melynek csúcsaiban 1-1 rekord van egy kitüntetett KULCS mezővel. Jelölje a csúcsban lévő rekord kulcsát.
Továbbá, teljesül a kupacrendezetttség: minden gyökértől különböző csúcsra igaz, hogy
Azaz, minden gyökértől különböző csúcsra igaz, hogy a szülőjében tárolt rekordnak a kulcsa klegfeljebb akkora, mint a csúcsban tárolt rekord kulcsa.
2.
Definiálja a szomszédsági mátrixot és az éllístás tárolást!
A gráf (ahol , amit továbbiakban végig felteszünk), szomszédsági mátrixa a következő -es mátrix:
Ugyanennek a gráfnak az éllistás megadása a következő:
A gráf minden csúcsához egy láncolt lista tartozik, a listafejeket egy tömbben tároljuk. Az csúcs listájában tároljuk az -ből kimenő éleket (az adat részben a végpont), és ha az éleken súly (vagy költség vagy hossz) is adot, akkor azt is (ekkor az adatrész 2 mezőből áll). Irányítatlan gráfnál minden élet mindkét végpontjánál tárolunk.
3.
Definiálja, hogy egy irányított gráf élsúlyozása konzervatív!
Def.: Egy irányítatlan gráf egy súlyozását konzervatívnak nevezzük, ha minden körének összsúlya nemnegatív.
4.
Definiálja a rendezési feladatot és a stabil rendezést!
Def.: Rendezési feladat:
Input: ahol egy tetszőleges rendezett univerzum.
Output: az indexek egy permutációja, amelyre igaz, hogy .
Egy rendezés stabil, ha az egyforma értékű elemek közül a később érkezett kerül későbbre.
pl.:
Input:
Output:
Magyarázat: és mivel és mivel előbb volt az inputban, mint ezért ebben a sorrendben lesznek az outputban is.
5.
Definiálja a bináris keresőfát!
Def.: Adott egy rendezett univerzum. Egy halmazt szótárnak nevezünk. A bináris keresőfa egy olyan bináris fa, amelynek csúcsaiban rekordok vannak, amelyek kulcsa a szótár egy eleme (minden csúcsra jelöli a csúcsban tárolt rekord kulcsát).
Továbbá, teljesül a keresőfatulajdonság: az összes csúcsra, a bal gyerekének minden leszármazottjára igaz, hogy és a jobb gyerekének minden leszármazottjára igaz, hogy .
6.
Definiálja az AVL-fákat!
Def.: Egy bináris keresőfa AVL-fa, ha minden csúcsra igaz, hogy
ahol a csúcs magassága, azaz a belőle lefele vezető leghosszabb út hossza, és
7.
Definiálja a blokkoló élet és a stabil párosítást!
Def.: Egy él blokkoló párosításra nézve, ha
a) és
b) és kölcsönösen jobban szeretik egymást, mint az -beli párjukat
Egy párosítás stabil, ha nem létezik -re nézve blokkoló él.
8.
Definiálja, hogy hash függvények egy halmaza mikor univerzális!
Def.: Hash függvények egy halmaza univerzális, ha -ra és -ra .
Ahol hash függvények halmaza, amik értéket vesznek fel.
9.
Írja le egy nyelv eldönthetőségének definícióját!
Def.: Egy Turing-gép eldönit az nyelvet, ha minden inputra leáll véges sok lépésben és egy inputra pontosan akkor áll meg ELF(ogad) állapotban, ha .
Egy nyelv algoritmikusan eldönthető, ha van olyan Turing-gép, ami őt eldönti.
10.
Írja le a DTIME oszályok és a P oszály definícióját!
Def.: Nyelvosztály:
Azaz minden inputra legfeljebb lépést tesz.
11.
Írja le az NP oszály definícióját!
Def.: NP osztály: egy nyelv az NP oszályban van, ha minden -ra létezik egy polinom hosszú és polinomiális időben ellenőrozhető bizonyíték. Azaz pontosabban, ha -hez létezik polinomiális lépésszámú ellenőrző Turing-gép és konstans, hogy:
Ha , akkor , hogy és az párt ELF(ogadja).
Ha , akkor -ra az párt ELUT(asítja).
12.
Írja le az NP-teljesség definícióját és adjon 4 pédát NP-teljes problémára!
Def.: Az nyelvet NP-teljesnek hívjuk, ha , és ha igaz lenne, akkor minden nyelvre következne.
például:
- Hamilton kör
- 3-SAT és csak simán SAT
- nonogram játék
- Leghosszabb út
- -nál hosszabb út
- hátizsák feladat
related: AlgTerv 1