IDENTIFYING DATA 2012_13
Subject (*) MODELS ABSTRACTES DE CÀLCUL Code 17081006
Study programme
Enginyeria Tècnica en Informàtica de Sistemes (1998)
 Cycle 1r
Descriptors Credits Theory credits Practical credits Type Year Period Exam timetables and dates
4.5 3 1.5 Troncal Segon Segon
Modality and teaching language See working groups
Department Enginyeria Informàtica i Matemàtiques
Coordinator
RIAÑO RAMOS, DAVID
 E-mail david.riano@urv.cat
Lecturers
RIAÑO RAMOS, DAVID
Web
General description and relevant information Aproximació al model computacional de les Màquines de Turing, així com una intro-ducció a la problemàtica de la Computabilitat i de la Calculabilitat
In this subject you only have the right to make the exam, because the degree you are studying is going to be extinguished. You have to take a look the timetable of the subject to know the exam's date. If you need an extraordinary exam session, you have to enrol for this, presenting an application to the secretariat of your campus or faculty.

Continguts
Topic Sub-topic
Introduction Motivation and Objectives of this subject
Chomsky's hierarchy
Turing Machine Description and Representations
TM to recognize Formal Languages
TM to compute Mathematical Functions
The TM Execution Cycle
Deterministic TM
Non-Deterministic TM
The Universal TM
An Introduction to the Theory of Calculability Some Limitations of TM
Calculability Principles
The Theory of Calculability
An Introduction to the Theory of Complexity Computational Complexity
Basic Complexity Classes
The Classes L and NL
The Classes P, NP i CoNP
The Classes EXP i NEXP
Complexity Principles
The Theory of Complexity

Atenció personalitzada
Description
Els alumnes seran atesos individualment o en grup en l'horari de consultes publicat per l'ETSE.

Avaluació
 
Other comments and second exam session

Hi haurà un procés d'avaluació de l'assignatura en base a 3 o 4 proves individuals, una d'elles de caràcter global.

Hi haurà una opció d'avaluació en segona convocatòria.

Fonts d'informació
Bàsica D. Riaño, "Models Abstractes de Càlcul", Edicions URV, 2000
J. E. Hopcroft, R. Motwani, J. D. Ullman, "Introducción a la Teoría de Autòmatas, Lenguajes y Computación", Addison-Wesley, 2002
H. R. Lewis i C. H. Papadimitriou, "Elements of the Theory of Computation", Prentice-Hall, 1981

Complementària M. Garey i D. Johnson, Computers and Intractability. A Guide to Theory of NP-Completeness”, Freeman,, 1978

(*)The teaching guide is the document in which the URV publishes the information about all its courses. It is a public document and cannot be modified. Only in exceptional cases can it be revised by the competent agent or duly revised so that it is in line with current legislation.