UNIVERSITATEA „POLITEHNICA”DIN TIMIŞOARA · PDF fileVariante de maşini Turing....

"UNIVERSITATEA „POLITEHNICA”DIN TIMIŞOARA SYLLABUS pentru disciplina: “COMPLEXITATE ŞI CALCULABILITATE” FACULTATEA AUTOMATICĂ ŞI CALCULATOARE DOMENIUL /SPECIALIZAREA CALCULATOARE SI TEHNOLOGIA INFORMATIEI Anul de studii: III Semestrul 2 Titularul cursului: (Titlul şi numele) Prof.dr.ing. Marius Crişan Colaboratori: (Titlul şi numele asistenţilor) Numar de ore/saptamana/Verificarea/Credite Curs Seminar Laborator Proiect Examinare Credite 2 0 2 0 D 4 A. OBIECTIVELE CURSULUI Cursul examinează bazele teoretice ale informaticii prezentând modelele calculabilităţii şi gramaticile aferente. Se studiază problema decidabilităţii şi a claselor de probleme decidabile şi indecidabile. Se prezintă bazele teoriei complexităţii cu clasele de complexitate aferente. Se introduce problema modelării fizice a calculabilităţii. Disciplina contribuie cu 3% la formarea competenţei în domeniul specializării. B. SUBIECTELE CURSULUI Automate şi limbaje: Limbaje regulate. Automate finite. Nedeterminism. Expresii regulate. Limbaje neregulate. Limbaje libere de context. Gramatici. Automate PDA. 6 ore Modele generale ale calculabilitatii: Maşina Turing. Teza Curch-Turing. Maşina Turing universală. Functii calculabile prin Masini Turing. Variante de maşini Turing. 6 ore Decidabilitate: Limbaje decidabile. Problema opririi. Probleme indecidabile. 4 ore Teoria complexităţii: Măsurarea complexităţii. Clasa P. Clasa NP. Clasa PSPACE. Completitudine. Complexitatea algoritmică. Aleatorism şi incompresibilitate. Teoria algoritmică a informaţiei. 8 ore Modele fizice ale calculabilitatii: Calcul reversibil. Termodinamica informaţiei. Entropia algoritmică. 4 ore Total 28 ore C. SUBIECTELE APLICATIILOR (laborator) Modelarea maşinilor FSM deterministe. 4 ore. Modelarea mşinilor NFSM. 4 ore Modelarea maşinilor PDA. 4 ore Modelarea maşinlori RAM. 4 ore Modelarea maşinlor Turing. 8 ore Evaluarea complexităţii sub diferite metrici. 4 ore Total 28 ore D. BIBLIOGRAFIE Se indică maximum trei titluri bibliografice de referinţă 1. J.E. Savage: “Models of Computation”, Addison-Wesley, 1998. 2 M. Sipser: “Introduction to the Theory of Computation”, PWS Publ. Co. Boston, MA, 1997. 3. D.P. Bovet, P. Crescenzi: „Introduction to the Theory of Complexity”, Prentice Hall, UK, 1994. E. PROCEDURA DE EVALUARE Examenul este scris, cu durata de 100 min. si consta dintr-un set de 10 intrebari avand fiecare ponderea de 1 punct. Nota finala e formata din 40% rezultând din activitatea pe parcurs si teme de casă si 60% din examenul final. F.COMPATIBILITATE INTERNATIONALA Se indică 3 universităţi străine de prestigiu in care funcţioneaza discipline comparabile 1. Massachusetts Institute of Technology: Theory of Computation. 2. Princeton University: Theory of Computation 3. Harvard University: Computational Complexity

Upload
truongkhue
Category

Documents
view
215
download
2

Embed Size (px):

Transcript of UNIVERSITATEA „POLITEHNICA”DIN TIMIŞOARA · PDF fileVariante de maşini Turing....

"UNIVERSITATEA „POLITEHNICA”DIN TIMIŞOARA

SYLLABUSpentru disciplina:

“COMPLEXITATE ŞI CALCULABILITATE”

FACULTATEA AUTOMATICĂ ŞI CALCULATOAREDOMENIUL /SPECIALIZAREA CALCULATOARE SI TEHNOLOGIA INFORMATIEI

Anul de studii: IIISemestrul 2

Titularul cursului: (Titlul şi numele) Prof.dr.ing. Marius CrişanColaboratori: (Titlul şi numele asistenţilor)

Numar de ore/saptamana/Verificarea/Credite Curs Seminar Laborator Proiect Examinare Credite2 0 2 0 D 4

A. OBIECTIVELE CURSULUI

Cursul examinează bazele teoretice ale informaticii prezentând modelele calculabilităţii şi gramaticile aferente. Se studiază problema decidabilităţii şi a claselor de probleme decidabile şi indecidabile. Se prezintă bazele teoriei complexităţii cu clasele de complexitate aferente. Se introduce problema modelării fizice a calculabilităţii.Disciplina contribuie cu 3% la formarea competenţei în domeniul specializării.

B. SUBIECTELE CURSULUI

Automate şi limbaje: Limbaje regulate. Automate finite. Nedeterminism. Expresii regulate. Limbaje neregulate. Limbaje libere de context. Gramatici. Automate PDA. 6 oreModele generale ale calculabilitatii: Maşina Turing. Teza Curch-Turing. Maşina Turing universală. Functii calculabile prin Masini Turing. Variante de maşini Turing. 6 oreDecidabilitate: Limbaje decidabile. Problema opririi. Probleme indecidabile. 4 oreTeoria complexităţii: Măsurarea complexităţii. Clasa P. Clasa NP. Clasa PSPACE. Completitudine. Complexitatea algoritmică. Aleatorism şi incompresibilitate. Teoria algoritmică a informaţiei. 8 oreModele fizice ale calculabilitatii: Calcul reversibil. Termodinamica informaţiei. Entropia algoritmică. 4 ore

Total 28 ore C. SUBIECTELE APLICATIILOR (laborator)Modelarea maşinilor FSM deterministe. 4 ore.Modelarea mşinilor NFSM. 4 oreModelarea maşinilor PDA. 4 ore Modelarea maşinlori RAM. 4 ore Modelarea maşinlor Turing. 8 oreEvaluarea complexităţii sub diferite metrici. 4 ore

Total 28 ore

D. BIBLIOGRAFIE Se indică maximum trei titluri bibliografice de referinţă

1. J.E. Savage: “Models of Computation”, Addison-Wesley, 1998.2 M. Sipser: “Introduction to the Theory of Computation”, PWS Publ. Co. Boston, MA, 1997.3. D.P. Bovet, P. Crescenzi: „Introduction to the Theory of Complexity”, Prentice Hall, UK, 1994. E. PROCEDURA DE EVALUARE

Examenul este scris, cu durata de 100 min. si consta dintr-un set de 10 intrebari avand fiecare ponderea de 1 punct. Nota finala e formata din 40% rezultând din activitatea pe parcurs si teme de casă si 60% din examenul final.

F.COMPATIBILITATE INTERNATIONALA

Se indică 3 universităţi străine de prestigiu in care funcţioneaza discipline comparabile1. Massachusetts Institute of Technology: Theory of Computation.

2. Princeton University: Theory of Computation

3. Harvard University: Computational Complexity