Ferrero, 2013. január 29., 19:06-n

2013-01-29T19:06:33Z

← Régebbi változat		A lap 2013. január 29., 21:06-kori változata
1. sor:		1. sor:
	~~{{GlobalTemplate\|Infoalap\|AlgElDefiniciok}}~~


	==Rendezés, keresés==		==Rendezés, keresés==

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElDefiniciok}} ==Rendezés, keresés== * Keresés és rendezés összefoglaló * [[AlgElKeresofaOss…”

2012-10-21T19:52:04Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElDefiniciok}} ==Rendezés, keresés== * Keresés és rendezés összefoglaló * [[AlgElKeresofaOss…”

Új lap

{{GlobalTemplate|Infoalap|AlgElDefiniciok}}

==Rendezés, keresés==

* [[AlgElRendezesKeresesOsszefoglalo|Keresés és rendezés összefoglaló]]
* [[AlgElKeresofaOsszefoglalo|Keresőfa összefoglaló]]

==Bonyolultságelmélet==

===TG helyzete===
(Nem hivatalos def, de könnyebb vele fogalmazni): a TG aktuális állapota, fejeinek állása, a fejek alatt lévő karakterek.

===TG megáll===
Az adott helyzetre nincs szabály, így nem tud továbblépni.

===TG elfogad===
Az adott bemenetre a gép megáll, mégpedig elfogadó állapotban. Nem determinisztikus esetben: van legalább egy végrehajtási út, amin megáll elfogadó állapotban.

===TG nem fogad el===
Az adott bemenetre a gép nem áll meg, vagy nem elfogadó állapotban áll meg. Nem determinsztikus: nincsen olyan végrehajtási út, amin elfogad.

===Nem determinisztikus turing gép===
Olyan TG, melynek van többértékű szabálya. (képletesen: van olyan helyzet, melyből több másikba is léphet)

===co előtag===
coX az X-be tartozó nyelvek koplementereiból képzett halmaz.

===RE : rekurzíve felsorolható nyelvek===
Azok a nyelvek, melyhez létezik TG, ami pontosan a nyelv szavait fogadja el. (A nyelven kívüli szavakra nem kötelező megállnia.)

===R : rekurzív nyelvek===
Azok a nyelvek, melyhez létezik TG, ami pontosan a nyelv szavait fogadja el, és mindig megáll.
(R részhalmaza RE-nek)

===R = coR===
Egy R-beli nyelvet felisemrő automata elfogadás és elutasítás esetén is kötelezően megáll. Így a nyelv komplementerét is felismerhetjük ezzel a géppel, ha felcseréljük az elfogadó és elutasító állpotokat, és ez is mindig meg fog állni.

===R = (RE ∩ coRE)===
Vegyünk egy tetszőleges nyelvet a halmazból! 
* A nyelv eleme RE, így TG1 a nyelv szavaira mindig megáll elfogadó állapotban.
* A nyelv eleme coRE, így TG2 a nyelven kívüli szavakra mindig megáll elfogadó állapotban.
Írjunk egy olyan TG-t, ami TG1-et és TG2-t futtatja párhuzamosan (egy lépést az egyik, egyet a másik). TG1 és TG2 valamelyike biztosan megáll. Ha TG1 elfogad, akkor elfogadunk. Ha TG2 fogad el, elutasítunk.

===Időkorlátos TG===
Ha n hosszú inputon legfeljebb t(n) lépést tesz meg.

===TIME(t(n)) nyelosztály===
Azok a nyelvek, melyekhez létezik c*t(n) időkorlátos TG. c nyelvenként más. (TIME(t(n)) eleme R)

===P nyelvosztály===
Polinom időben felismerhetőek. Azok a nyelvek, melyekhez létezik c*t(n) időkorlátos TG, ahol t(n) egy polinom.

===NP nyelvosztály===
'''Nem determinisztikus''' TG-pel polinom időben felismerhetőek. Azok a nyelvek, melyekhez létezik c*t(n) időkorlátos nem determinisztikus TG, ahol t(n) egy polinom.

-- [[SzaMa|SzaMa]] - 2005.05.22.

===Univerzális Turing-gép===
Képes szimulálni más gépeket. w#s bemenetre U(w#s) = elutasít, ha nem létezik w kódú TG; egyébként U(w#s) = Mw(s).

===Univerzális nyelv===
Az univerzális Turing-gép által elfogadott nyelv, azaz azon w#s szavak halmaza, melyre létezik w kódú Turing-gép, továbbá ez a gép s bemenetre elfogad.
(Lu ∈ RE, hiszen az Univerzális Turing-gép elfogadja; de Lu ∉ R)

===Diagonális nyelv===
Azon w szavak halmaza, melyre létezik w kódú Turing-gép, és ez a gép nem fogadja el a w szót.
(Ld ∉ RE)

===Megállási nyelv===
Azon w#s szavak halmaza, melyre létezik w kódú Turing-gép, és ez a gép megáll az s bemenetre.
(Lh ∈ RE, de Lh ∉ R)

===függvény ((parciálisan) rekurzív)===
Ez egy olyan TG ami tartalmazási kérdés helyett függvényt számol ki (egy output szalagra), és nem biztos hogy megáll.

-- [[PappGergely|P.G.]] - 2005.06.11.

[[Category:Infoalap]]

Algel definíciók - Laptörténet

Ferrero, 2013. január 29., 19:06-n

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElDefiniciok}} ==Rendezés, keresés== * Keresés és rendezés összefoglaló * [[AlgElKeresofaOss…”