Person in charge:  () 
Others:  () 
Credits  Dept.  Type  Requirements 

9.0 (7.2 ECTS)  CS 

PS
 Prerequisite for DCSFW 
Person in charge:  () 
Others:  () 
Upon finishing this subject, students should have an understanding of the basic elements of Theory of Computation, including Automata and Formal Language Theory, Computability Theory, Complexity Theory and Algorithmics. Students gain the understanding and the experience needed to be able to classify problems. Problems are classified according to the existence or absence of algorithms for solving them, and, in the case of the latter, based on the possibility of finding an efficient alfgorithmic solution.
Estimated time (hours):
T  P  L  Alt  Ext. L  Stu  A. time 
Theory  Problems  Laboratory  Other activities  External Laboratory  Study  Additional time 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

12,0  12,0  0  0  0  24,0  0  48,0  
Mathematical notions.
Decidability. Complexity. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

12,0  12,0  0  0  0  24,0  0  48,0  
Exhaustive search.
Greedy algorithms. Dynamic programming. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

12,0  12,0  0  0  0  24,0  0  48,0  
NPcompleteness.
String matching. Parsing. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

1,0  11,0  0  0  0  12,0  0  24,0  
Language classification.

Total per kind  T  P  L  Alt  Ext. L  Stu  A. time  Total 
37,0  47,0  0  0  0  84,0  0  168,0  
Avaluation additional hours  9,0  
Total work hours for student  177,0 
The first half of each twohour class covers theory and the second half is spent doing exercises. Moreover, there will be a continued evaluation which will consist of three exams (for parts IIII) undertaken during class time.
The subject has a continued evaluation system and a final exam. The continued evaluation consists of 3 tests made during the semester, while the final exam contains 4 parts.
If the grades of the tests are p1, p2, p3, and the grades of the problems of the final exam are f1, f2, f3, f4, then the global grade of the subject is
max(p1,f1) + max(p2,f2) + max(p3,f3) + f4
The four values of the previous summation respectively correspond to the four parts in which the subject is divided. Parts IIII contribute with 3 points each, while part IV contributes with 1 point.
The tests will take place at usual classroom hours, shortly after finishing the topics they include. They will be announced at Racó at the beginning of the course.
Programming knowledge and data structures.
Familiarity with logicomathematical reasoning.