Model Examen CDC


Subiect examen CDC, 2 februarie 2012. Multumiri lui Sorin Pavel.

1.     1.  Clase de complexitate.

a)      a) Consideram clasele de complexitate:

TIME(f(n)), NTIME(f(n)), TIME(2^O(f(n))), SPACE (f(n)), NSPACE(f(n)), SPACE(f^2(n))

Care sunt relatiile corecte intre aceste clase?

b)      b) Definiti clasele de complexitate:

P, PSPACE, NP, L, NL, EXPTIME, NEXPTIME si precizati relatiile dintre ele.

2.       2. Utilizand problema corespondetei lui Post, aratati ca problema intersectiei limbajelor de tip 2 e nedecidabila.

3.       3. Se dau urmatoarele probleme:

Problema Incluziunii (CP)

Intrare: Doua automate finite deterministe A si B

Intrebare: L(A) inclus egal L(B) ?

Problema Universalitatii (UP)

Intrare: Un automat finit A peste un alfabet Σ

Intrebare: L(A)= Σ*?

 

Se stie ca CP este in PSPACE, UP este PSPACE-Completa. Este CP o problema PSPACE-Completa?

ALTERNATIV la ex 2: (daca nu voiai sa faci 2)

Aratati ca CP este in clasa PSPACE.

 

Punctaje: 1a) 2.5p, b 2.5p | 2. 2pct | 3. 2pct.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: