Scribd
Încărcați
12 vizualizări1 pagină

Subiect e

Documentul prezintă cinci subiecte legate de mașinile Turing și teoria complexității: 1) tipuri de mașini Turing, 2) funcții calculabile, 3) mulțimi recursiv enumerabile, 4) clasa de complexitate timp și 5) clasa de complexitate spațiu.

Încărcat de

Rareș Cristea
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca TXT, PDF, TXT sau citiți online pe Scribd
12 vizualizări1 pagină

Subiect e

Documentul prezintă cinci subiecte legate de mașinile Turing și teoria complexității: 1) tipuri de mașini Turing, 2) funcții calculabile, 3) mulțimi recursiv enumerabile, 4) clasa de complexitate timp și 5) clasa de complexitate spațiu.

Încărcat de

Rareș Cristea
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca TXT, PDF, TXT sau citiți online pe Scribd

1. Masini Turing deterministe si nedeterministe.

Nota 6:
- definitii pentru toate tipurile de masini Turing (deterministe, nedeterministe
, cu mai multe benzi)
- limbaj acceptat si functie Turing calculabila
- relatiile intre ele tipurile de masini Turing (enunturi)
Fiecare demonstratie, la alegere: 2p

2. Functii recursive, calculabile cu programe standard, Turing calculabile.


Nota 6:
- definitiile celor 3 tipuri de functii
- relatiile intre ele (enunturi)
Fiecare demonstratie, la alegere: 2p

3. Multimi recursive, recursiv enumerabile, nerecursiv enumerabile.


Nota 6:
- definitiile celor 3 tipuri de multimi
- relatiile intre ele (enunturi si exemple de limbaje, fara demonstratii)
Fiecare demonstratie, la alegere: 2p

4. Clasa de complexitate timp.


Nota 6:
- modelul de masina Turing pe care se face evaluarea masurii timp
- definitia masurii timp
- definirea claselor de complexitate timp
- comprimarea benzilor (enunturi)
- eliminarea constantelor (enunturi)
- ierarhii de complexitate (enunturi
Fiecare demonstratie, la alegere: 2p

5. Clasa de complexitate spatiu.


Nota 6:
- modelul de masina Turing pe care se face evaluarea masurii spatiu
- definitia masurii spatiu
- definirea claselor de complexitate spatiu
- comprimarea benzilor (enunturi)
- eliminarea constantelor (enunturi)
- ierarhii de complexitate (enunturi
Fiecare demonstratie, la alegere: 2p

S-ar putea să vă placă și