Cursul se incheie cu un examen scris la sfârşitul semestrului cu durata de 2 ore si care va trata un numar de subiecte pe baza celor tratate la curs (2-4 subiecte). În nota finală se iau în considerare activitatea la laborator (40%) şi nota la examenul scris (60%)..
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)
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”
FACULTATEA: AUTOMATICĂ ŞI CALCULATOARE
DOMENIUL / SPECIALIZAREA: CALCULATOARE ŞI TEHNOLOGIA INFORMAŢIEI Anul de studii: III
Semestrul: 2
Titularul cursului: conf. dr. ing. Ioana Şora
Colaboratori:
Numar de ore/saptamana/Verificarea/Credite
Curs
Seminar
Laborator
Proiect
Examinare
Credite
2
0
2
0
Distribuită
4
A. OBIECTIVELE CURSULUI
Analiza si proiectarea sistemelor software complexe, alegerea arhitecturilor adecvate, utilizarea de tipare arhitecturale si cadre de aplicatii.
B. SUBIECTELE CURSULUI
Metode de modelare si proiectare software la nivel arhitectural; Elemente de baza ale MDA (Model Driven Architecture); Stiluri arhitecturale; Application Frameworks; Middleware.
C. SUBIECTELE APLICATIILOR (laborator, seminar, proiect)