http://www.inf.unibz.it/~calvanese/teaching/17-18-tc/
Free University of Bozen-Bolzano
Faculty of Computer Science
Master of Science in Computer Science
European Master in Computational Logic
Home page of the course
Theory of Computing
A.Y. 2017/2018
News
Course description
Objectives. The objective of the Theory of Computing course is to
introduce and study abstract, mathematical models of computation (such as
Turing machines, formal grammars, recursive functions), and to use the abstract
computation models to study the ability to solve computational problems, by
identifying both the intrinsic limitations of computing devices, and the
practical limitations due to limited availability of resources (time and
space). A second objective is to show how to reason and prove properties about
computations in a precise, formal, abstract way.
Prerequisites. There are no prerequisites in terms of courses to
attend. Students should be familiar with notions of mathematics and set theory,
and with basic proof techniques, as taught in the mathematics courses of a
bachelor in computer science.
Teaching material
[M1] Introduction to Automata Theory,
Languages, and Computation (3rd edition). J.E. Hopcroft, R. Motwani,
J.D. Ullman. Addison Wesley, 2007.
[M2] Lecture
Notes for Theory of Computing. Diego Calvanese. 2013. Available
as scanned pages in pdf.
[M3] Languages and Machines (3rd
edition). Thomas A. Sudkamp. Addison Wesley, 2005.
Only Chapter 13.
[M4]
The Convenience of
Tilings. Peter van Emde Boas. In Complexity, Logic, and
Recursion Theory, volume 187 of Lecture Notes in Pure and
Applied Mathematics, pages 331-363, 1997.
[M5]
Exercises on Theory of
Computing. Available as scanned pages in pdf.
Additional reading material
- Elements of the Theory of Computation (2nd edition).
H.R. Lewis, C.H. Papadimitriou. Prentice Hall. 1998.
- Introduction to the Theory of Computation. M. Sipser. PWS
Publishing Company. 1997.
- Computational Complexity. C.H. Papadimitriou. Addison Wesley.
1995.
- The Universal Computer: The Road from Leibniz to Turing.
M. Davis. A K Peters/CRC Press. 2011.
Full text accessible to all unibz users at Safari Books Online.
- The
Church-Turing Thesis. Copeland, B. Jack. The Stanford
Encyclopedia of Philosophy. Fall 2008 Edition.
- The Status of the P
versus NP Problem. Lance Fortnow. Communications of the ACM.
Vol. 52 No. 9, Pages 78-86, September 2009.
pdf
- On
P, NP, and Computational Complexity. Moshe Y. Vardi.
Communications of the ACM. Vol. 53 No. 11, Page 5, November 2010.
pdf
- Solving
the Unsolvable. Moshe Y. Vardi.
Communications of the ACM. Vol. 54 No. 7, Page 5, July 2011.
pdf
- Who
Begat Computing? Moshe Y. Vardi.
Communications of the ACM. Vol. 56 No. 1, Page 5, January 2013.
pdf
- Would
Turing Have Won the Turing Award? Moshe Y. Vardi.
Communications of the ACM. Vol. 60 No. 11, Page 7, November 2017.
pdf
- What is an Algorithm? Moshe Y. Vardi.
Communications of the ACM. Vol. 55 No. 3, Page 5, March 2012.
pdf
- What Is an Algorithm? Yuri Gurevich.
In Proc. of the 38th Conference on Current Trends in Theory and Practice of
Computer Science (SOFSEM 2012). Springer LNCS Vol. 7147, Pages 31-42,
2012.
pdf
- On
founding the theory of algorithms. Yiannis N. Moschovakis.
In Truth in Mathematics. Clarendon Press, Oxford, Pages 71-104, 1998.
pdf
- An
Interview with Stephen A. Cook. Philip L. Frana.
Communications of the ACM. Vol. 55 No. 1, Pages 41-46, January 2012.
pdf
- Rosser's Theorem
via Turing machines. Scott Aaronson. Shtetl-Optimized - The
Blog of Scott Aaronson. 21 July 2011
- P =? NP Scott Aaronson. 2017.
pdf
- A
Hitchhiker"s Tour Through Computational Complexity in KR&R.
Thomas Eiter. Invited talk at KR 2020. 16 September 2020.
- The
Different Kinds of Mathematical Proofs. Kasper Müller.
Cantor’s Paradise. 2 May 2021.
- Let's be
honest. Seeking to rectify the two mutually exclusive ways
of comparing computational power—encoding and simulation.
Nachum Dershowitz.
Communications of the ACM. Vol. 64 No. 5, Pages 37-41, April 2021.
pdf
Further interesting and fun material
- Office hours
- Teaching assistant: there is no teaching assistant for this course. The
exercise hours are taught by the lecturer.
- Schedule: The course is taught in the 1st semester: from October 4,
2017 to January 17, 2018.
- Lectures (Lecture Room E223,
Sernesi E):
- Tuesday 8:30-10:30
- Wednesday 8:30-10:30
- Exercises (Lecture Room E220, usually): Tuesday 14:00-16:00
See also the
on-line
timetable page for changes.
- Additional teaching material
- Lecture notes (made available during
the course)
- Esercises solved in
class (made available during the course)
- Course program
- Exam esercises from the last years (in
part with solutions).
Note that Part 1 of the exams up to June 2007 deals with topics that
are not covered anymore in this course. Also, Part 2 of some exams
contains exercises on circuit complexity, which is currently not part
of the course program, and has been substituted by the part on tiling
problems.
- Exam dates
- Midterm: end of November (precise date to be announced)
- Winter session: Tuesday, 12/2/2018, 14:00-18:00
- Summer session: Monday, 18/6/2018, 14:00-18:00
- Autumn session: Tuesday, 18/9/2018, 8:30-12:30
- Rules for the exam
- At the exam, the student has to solve exercises and/or
answer questions on the course topics in written or oral form.
- The exam is divided into two parts:
- The two parts of the exam can be taken together in the same
exam session, or separately in different exam sessions.
- Even when the two parts of the exam are taken together, they
can be passed separately.
- For a part to be passed, a minimum of 18/30 points is required
(half marks are rounded upwards).
- A passed part of the exam (or the passed midterm) is valid
until the end of the academic year (i.e., exam session of September).
If the other part is not passed by then, the passed part is lost
and cannot be carried over to the next academic year.
- For the written exam, each part has a duration of 90 minutes, with 15
minutes break between the two parts. During the exam, it
will not be possible to consult any kind of material, to use
laptops, smartphones, or tablets, or to leave the exam room before the
break/end of the exam.
teaching page of Diego Calvanese
Last modified:
Friday, 9-Feb-2024 15:40:30 CET