Szamitaselmelet alapjai 2 EA

Create an illustrative image depicting abstract concepts in computational theory, featuring elements like Turing machines, graphs, and mathematical logic in a modern, engaging style.

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.

66 Questions16 MinutesCreated by SolvingLogic321

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

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 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

Unlock and Upgrade

Remove all limits from your Quizzes

Szamitaselmelet alapjai 2 EA

Fundamentals of Computational Theory Quiz

More Quizzes