X hits on this document

290 views

0 shares

0 downloads

0 comments

91 / 145

DOMENIUL / SPECIALIZAREA: CALCULATOARE ŞI TEHNOLOGIA INFORMAŢIEI

Anul de studii: III

Semestrul: 2

Titularul cursului: prof. dr. ing. Marius Crişan

Colaboratori:

Numar de ore/saptamana/Verificarea/Credite

Curs

Seminar

Laborator

Proiect

Examinare

Credite

2

0

2

0

Distribuită

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.

Modele generale ale calculabilitatii: Maşina Turing. Teza Curch-Turing. Maşina Turing universală. Functii calculabile prin Masini Turing. Variante de maşini Turing.

Decidabilitate: Limbaje decidabile. Problema opririi. Probleme indecidabile.

Teoria complexităţii: Măsurarea complexităţii. Clasa P. Clasa NP. Clasa PSPACE. Completitudine. Complexitatea algoritmică. Aleatorism şi incompresibilitate. Teoria algoritmică a informaţiei.

Modele fizice ale calculabilitatii: Calcul reversibil. Termodinamica informaţiei. Entropia algoritmică.

C. SUBIECTELE APLICATIILOR (laborator, seminar, proiect)

Laborator: Modelarea maşinilor FSM deterministe. Modelarea mşinilor NFSM. Modelarea maşinilor PDA. Modelarea maşinlori RAM. Modelarea maşinlor Turing.

Seminar: Aplicaţii ale algoritmilor nedeterminişti. Aplicaţii cu maşini FSM. Aplicaţii cu maşini PDA şi RAM. Evaluarea complexităţii sub diferite metrici.

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

Data: 23.02.2007

  DIRECTOR/SEF  DEPARTAMENT/CATEDRA                    TITULAR DE DISCIPLINĂ,

  Prof.dr.ing. Vladimir Creţu                                                                          Prof.dr.ing. Marius Crişan

UNIVERSITATEA „POLITEHNICA”DIN TIMIŞOARA                                         

SYLLABUS

pentru disciplina:

“PROIECTAREA ŞI ARHITECTURA SISTEMELOR SOFTWARE COMPLEXE”

Document info
Document views290
Page views290
Page last viewedSat Dec 03 10:30:29 UTC 2016
Pages145
Paragraphs4938
Words34649

Comments