Course Details for A.Y. 2015/2016
Name:
Teoria della Calcolabilità e Complessità / Introduction to Computability and Complexity
Basic information
Credits:
: Bachelor Degree in Computer Science 6 CFU (b)
Degree(s):
Bachelor Degree in Computer Science 3rd anno curriculum General Compulsory
Language:
Italian
![[info]](img/info16.png)
Course Objectives
The course aims to provide motivation , definitions and basic techniques of the Theory of Computability
and of the Complexity Theory . At the end of the course, after passing the exam, the student must
be able to know the notion of algorithm and several of its equivalent formulations. The student must also
know the boundaries of this notion. The student must know the main classes of languages and their main properties
both in theory of Computability and in Complexity Theory. The student must also know the main
techniques used in these theories, such as the techniques of diagonalization, the notion of reduction and
of polynomial reduction.
Course Content
- The Theory of computability. Countability, models of computation and Church's thesis, Turing machine, nondeterministic computation. Counters machine.
- Calculable and non-calculable functions and languages, recursive and recursively enumerable sets. Languages and problems, acceptability and decidability of languages.
- Diagonalization techniques, reductions, universal language, Rice's theorem.
- Elements of the theory of complexity : static and dynamic measures, time and space
complexity classes, the classes P and NP. The conjecture P = NP? NP-completeness.
- Polynomial reductions. Theorems concerning NP-completeness. Statement of the
Cook's theorem. CSAT, 3SAT and other NP-complete problems.
- Class PS and NPS, Savitch's theorem. Elements of modular arithmetic and cryptography.
Learning Outcomes (Dublin Descriptors)
On successful completion of this course, the student should
- have acquired motivation, definitions and basic techniques of the Theory of Computability and
of
the
Complexity Theory.
The student should be able to understand and read literature concerning the
basics of
both theories . The student should be able to use the language adopted by the scientific community
that concerns these two theories.
- be able to recognize and organize autonomously basic topics of both theories treated in the course
in
related
applications. In particular the student should know the notion of algorithm and several
of
its equivalent
formulations. The student should also know the boundaries of this notion.
The student
should know the
main classes of languages and their main properties both in Theory of Computability
and in Complexity
Theory. The student should also know the main techniques used in
these theories, such
as the techniques
of diagonalization, the notion of reduction and of polynomial
reduction. The student
should be able to apply this knowledge mainly in order to avoid impossible or
almost impossible requests
(such as "create a program that checks if another generic program perform the
desired task" or "create a
fast program that tell us if a TSP instance has an affermative answer) and direct
his energy in other
directions that can be valid under stronger assumption.
- be able to understand that the choice of a particular programming language
depends
mainly on the
productivity and not on its computational power.
The student should also be able to assess the
relevance the main topics of
both theories and to link the theoretical aspects of both theories
with
the practical aspects.
- be able to describe the main results of the Theory of Computability and of
the
Complexity
Theory to other non-specialist people in the scientific community.
- be able to read and understand books and papers concerning the arguments
treated in the course.
The student should be able, using also the knowledge acquired in this course, to
follow more advanced
studies in Computer Science (such as masters or second-level university degrees)
and also other more
complex courses and/or seminars related to both theories treated in the course.
Prerequisites and Learning Activities
The student must have had prior experiences in programming and mast have at least an intuitive notion of
what is an algorithm.
The student must have a good knowledge of recursive algorithms and a good
knowledge on how to visit trees and graphs by using
recursive algorithms and by using classic data
structures such as stacks and queues.
Assessment Methods and Criteria
The exam will be both written and oral. The written represent a filter in order to allow to make the oral exam
only to the students that have a sufficient knowledge of the basic definitions and of the main theorems. During
the oral exam the questions to the student will cover the whole program of the course.
Textbooks
- Hopcroft, Motwani, Ullman, AUTOMI LINGUAGGI E CALCOLABILITA' , Pearson, Addison Wesley. PARTE DEI CAPITOLI 1, 8, 9, 10 e 11.
- Arora, Barak, Computational Complexity: a modern approach , Cambridge University press. Testo di approfondimento
Notes
- This course treats some aspects of the theory of Computability and of the Complexity theory and, further,
some relations among these two theories.
Course page updates
This course page is available (with possible updates) also for the following academic years:
To read the current information on this course, if it is still available, go to the university course catalogue .
Course information last updated on: 12 novembre 2015, 17:11
Italian version
sad
strutture.univaq