Szamitaselmelet alapjai 2 EA
Fundamentals of Computational Theory Quiz
Test your knowledge on the fundamental concepts of computational theory with this comprehensive quiz. Covering topics ranging from graph theory to Turing machines, this quiz is designed for students and enthusiasts alike.
• 66 challenging questions
• Multiple choice format
• Instant feedback on your answers
• Ideal for self-assessment and study.
A (¬x ∧ y) ∨ (x ∧ ¬y ∧ z) nulladrend˝u formula konjunkt´ıv norm´alform´aj´u
True
False
Legyen p egy els˝orend˝u logika 2 arit´as´u predik´atumszimb´oluma tov´abb´a x ´es y individuumv´altoz´ok. Ekkor p(x, p(y, x)) els˝orend˝u formula
True
False
Legyen M = hQ, Σ, Γ, δ, q0, qi , qni egy nemdeterminisztikus Turing g´ep. Ekkor b´armely q ∈ Q \ {qi , qn}, a ∈ Γ eset´en |δ(q, a)| ≥ 1
True
False
{0, 1} ∗ hatv´anyhalmaza continuum sz´amoss´ag´u
True
False
Ha L felismerhet˝o veremautomat´aval, akkor Turing g´eppel is
True
False
Minden line´arisan korl´atolt automat´aval eld¨onthet˝o nyelv gener´alhat´o 0-t´ıpus´u grammatik´aval
True
False
Legyen V = {p, q, r} egy rendezett ´ab´ec´e, ahol p < q < r. Ekkor V ∗ hosszlexikografikus rendez´es´eben a qqpqp sz´o el˝or´ebb van, mint qrrp
True
False
Ha L ∈ RE ´es L ≤ L 0 , akkor L 0 ∈ RE
True
False
Ha L NP-teljes, akkor minden NP-beli nyelv visszavezethet˝o r´a
True
False
Ha a G egyszer˝u gr´af 4-sz´ınezhet˝o, akkor 7-sz´ınezhet˝o is
True
False
Ha a 10 cs´ucs´u G egyszer˝u gr´afban van 6 m´eret˝u klikk, akkor G minden lefog´o ponthalmaza legal´abb 5 elem˝u
True
False
Ha k´esz´ıt¨unk egy az IHK nyelvet polinom id˝oben eld¨ont˝o determinisztikus Turing g´epet, akkor 1 milli´o doll´ar ¨uti a markunkat.
True
False
Tudjuk, hogy l´eteznek NP-k¨oztes nyelvek
True
False
Ha L NP-teljes, akkor L coNP-teljes
True
False
Minden f : N → R + 0 f¨uggv´enyre SPACE(f(n)) ⊆TIME(f(n))
True
False
Tegyük fel hogy valamely f,g:N -> R0+ fuggvenyekre lim fn/gn = 5/3 Ekkor f(n) = omega(g(n)))
True
False
X -> y -> z hullam0 (x->y)->z (x,y,z iteletvaltozok)
True
False
Legyen f egy elsorendu logika 2 aritasu fuggvenyszimboluma tovabba legyenek x es y individuumvaltozok. Ekkor mindenxf(x,y) elsorendu formula.
True
False
Legyen M = egy nemdet Turing gep. Ha Mnek van uESummra nem terminalo es elfogado konfiguracioban veget ero szamitasa is akkor unem eleme L(M)
True
False
Ha A valodi reszhalmaza a B halmaznak akkor B nek nagyobb a szamossaga mint A nak
True
False
RE C R
True
False
Ha L nemeleme R es L <= L' akkor L' nemeleme R
True
False
Ha a 10 csucsu G egyszeru grafban van 6 meretu fuggetlen ponthalmaz akkor G minden lefogo ponthalmaza legalabb 4 elemu
True
False
Ha tudunk kesziteni egy RESZLETOSSZEG nyelvet polinom idoben eldonto determinisztikus turing gepet akkor minden mas np beli nyelvhez is keszitheto ot polinom idoben eldonto determinisztikus turing gep
True
False
Minden np teljes nyelv eldontheto determinisztikus turing geppel
True
False
Tudjuk hogy P C NP
True
False
Tudjuk hogy grafpolimorfizmus nyelv NP teljes
True
False
CoNP = NP
True
False
Az offline turing gepek nem irhatnak az 1. szalagjukra
True
False
Minden linearisan korlatolt automataval eldontheto nyelv kornyezetfuggo
True
False
13log7n = omega(7log13n)
True
False
Ha f(n) = O(g(n)) akkor f(n) = omega(g(n))
True
False
Egy elsorendu logikaban Pred = {p,q}, Func = {f,g} Cnst = 0 p,q,f,g mindegyikenek az aritasa 2. Ekkor van ennek a logikanak olyan terme ami egyuttal formula is.
True
False
Legyen M = egy nemdet Turing gep. Ha Mnek van uESummra van elutasito konfiguracioban veget ero szamitasa akkor unem eleme L(M)
True
False
Ha L nemeleme R es L' <= L akkor L' nemeleme R
True
False
Tudjuk hogy R valodi reszhalmaza REnek
True
False
Minden kornyezetfuggetlen nyelv eldontheto determinisztikus turing geppel.
True
False
Ha a 10 csucsu G egyszeru grafban van 7 meretu lefogo ponthalmaz, akkor G minden fuggetlen ponthalmaza legfeljebb 3 elemu.
True
False
Ha tudunk kesziteni egy RESZGRAFIZOMORFIZMUS nyelvet polinom idoben eldonto determinisztikus turing gepet akkor minden mas np beli nyelvhez is keszitheto ot polinom idoben eldonto determinisztikus turing gep
True
False
Tudjuk hogy letezik NP \ P beli nyelv
True
False
Az ELER nyelv NP beli
True
False
P C PSPACE
True
False
Az irracionalis szamok halmazanak szamossaga megszamlalhatoan vegtelen
True
False
P = coP
True
False
P C NP metszet coNP
True
False
TIME(f(n)) C NTIME(f(n))
True
False
NTIME(f(n)) C TIME (f(n))
True
False
KNF?: x es y v nemx es y
True
False
KNF?: nem(x v y) es (x v nemy)
True
False
Hamilton kor problema NP teljes?
True
False
2SAT problema NP teljes?
True
False
ELER problema NP teljes?
True
False
2 szinezes problema NP teljes?
True
False
Egy offline TG többlet tárigényébe beleszámítanak az input által elfoglalt cellák.
True
False
Létezik olyan nyelv, ami determinisztikus OTG-vel nem felismerhető de nem-determinisztikus OTG-vel felismerhető.
True
False
Q Megszámlálhatóan végtelen
True
False
Z Megszámlálhatóan végtelen
True
False
N Megszámlálhatóan végtelen
True
False
TIME (f(n)) C SPACE (f(n))
True
False
SPACE(f(n)) C TIME(f(n))
True
False
NL = coNL
True
False
SPACE(f(n)) = coNSPACE(f(n))
True
False
Minden kornyezetfuggetlen nyelv felismerheto linearisan korlatolt automataval
True
False
Minden linearisan korlatolt automata altal felismert nyelv kornyezetfuggetlen.
True
False
Letezik eldonthetetlen kornyezefuggo nyelv
True
False
Letezik eldontheto nem kornyezetfuggo nyelv
True
False
{"name":"Szamitaselmelet alapjai 2 EA", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Test your knowledge on the fundamental concepts of computational theory with this comprehensive quiz. Covering topics ranging from graph theory to Turing machines, this quiz is designed for students and enthusiasts alike.• 66 challenging questions• Multiple choice format• Instant feedback on your answers• Ideal for self-assessment and study.","img":"https:/images/course1.png"}
More Quizzes
Érvkvíz
520
C Programming Quiz
2412138
Dsaasddsa
11620
EAG 2018/2019 PRACTICE QUIZ 2
158137
Would I have bullied you in middle school?
7444464
What HomeWorld Gem Are You?
147382
Am I controlling?
158147
What do the Harry Potter characters think of YOU?
1265458
ACCONTING 1 QUIZ
158148
Modern Family Quiz
158688
امتحان الوحدة السابعة/ اللغة الانكليزية/ السادس الاعدادي/ الاستاذ هادي سعد الحسيني
1780
Engaging Story Quiz
1780