Address
Jakob-Haringer-Str. 2
5020 Salzburg, Austria
Room 2.17
Phone
+43 (0)662 8044 6417
+43 (0)662 8044 611 (fax)
Skype ana_sokolova
Many thanks to Silviu Craciunas for the photo (RTAS 2010 in Stockholm) and his help with iWeb!
Formal Languages and Complexity Theory 511.022 (lectures)
Winter semester 2016/2017
Schedule: Tuesdays 11am-1pm starting 4.10.2016 in T01 see calendar
First meeting: Tuesday, October 4 at 1pm in T01
Language: Teaching in English, course material (mainly) in German
Office hours: Wednesdays 11am-12am
Literature:
-
•Textbook: Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Pearson/Addison-Wesley, 2007.
-
•Textbook: Introduction to the Theory of Computation, by Michael Sipser, Cengage, 2005.
The books can be ordered via Amazon.de . Some copies are available at the department library.
I will use the teaching materials of Prof. Robert Elsaesser (on sabbatical this semester), with small changes, and make them available via http://fl.cosy.sbg.ac.at
Prerequisites: The course material is self-contained, but knowledge of basics of theoretical computer science is expected.
Exam: The exam is written. In case a student wants to improve his/her grade, an additional oral exam can be scheduled. One can pass the exam by either (1) passing the two partial tests within the semester, or (2) passing one of the possible full exams that will be scheduled after the semester ends. The tests/exam consist of several excersises from the material covered during the course.
In order to pass via the partial tests (1) one needs to: have in sum a total of 55% of the maximal points available at both tests and no less than 20% of the maximal number of points at each one test. That is, if partial test 1 brings maximally 100 points and partial test 2 also 100 points, in order to pass one needs to have at least 20 points on each test and a total sum of at least 110 points on both tests.
In order to pass via one of the exam possibilities one needs to have 55% of the maximal points available at the exam. That is, if the exam brings maximally 100 points, in order to pass one needs to have at least 55 points.
Note that the exams cover the full course material, whereas each partial test covers one half of the material.
Exam dates: Test 1 on Friday, November 25, 2016, 2pm-5pm in T01.
Test 2 on Tuesday, February 7, 2017, 1pm-4pm in T01.
Exam on Friday, February 24, 2017, 1pm-4pm in T01.
Schedule:
-
•Week 1, Tuesday 4.10.16, Introduction; Turing machines, decideability. In class we worked out another example in full detail (TM for deciding {w#w| w in {0,1}*}). Please read the chapter on Turing machines in the book(s).
-
•Week 2, Tuesday 11.10.16. More on Turing machines: Multiple tape Turing machines; examples / techniques for constructing Turing machines; closure properties. Please read in the book(s).
-
•Week 3, Tuesday 18.10.16. Universal Turing Machine, recursively enumerable languages about Turing machines. Please read in the book(s).
-
•Week 4, Tuesday 25.10.16. More recursively enumerable languages, and one non-recursively enumerable language. Discussion and proofs on the blackboard. Please read in the book(s).
-
•Week 6, Tuesday 8.11.16 (no class in Week 5 due to public holiday). Reductions. Discussion and proofs on the blackboard. Please read in the book(s).
-
•Week 7, Tuesday 15.11.16. Undecideability (of the halting problem, various consequenes, Rice’s theorem). Discussion and proofs on the blackboard. Please read in the book(s).
-
•Week 8, Tuesday 22.11.16. Complexity - time complexity and the class P. Discussion / proofs on the blackboard. Please read in the book(s).
-
•Week 9, Tuesday 29.11.16. The class NP, nondeterministic Turing machines. Discussion, examples, proofs on the blackboard. Please read in the book(s), in particular in the book by Sipser you can find all that we discussed today.
-
•Week 10, Tuesday 6.12.16. Some more results about the class NP; polynomial reduction, NP-completeness. Definition of SAT. Please read in the book(s), in particular in the book by Sipser you can find all that we discussed today (Theorem 7.11 and 3.16, Theorem 7.20 -- Section 7.3 from here on, and Section 7.4 except for Theorem 7.32 and the Cook-Levin Theorem -- to be discussed next time).
-
•Week 11, Tuesday 13.12.16. NP-completeness, proofs of NP-complete languages. Please read in the book(s), in particular in the book by Sipser you can find all that we discussed today.
-
•Week 12, Tuesday 20.12.16. More proofs of NP-completeness; Context-Free Grammars and Context-Free Languages. Please read in the book(s), in particular in the book by Sipser you can find all that we discussed today.
-
•Week 13, Tuesday 17.1.17. Context-Free Grammars and Context-Free Languages - continued. Non-context-free languages (pumping lemma), examples; Closure properties of context free languages. Please read in the book(s), in particular in the book by Sipser you can find all that we discussed today.
-
•Week 14, Tuesday 24.1.17 as well as Friday 27.1.17 (1pm-3pm in T02). Deterministic push-down automata, Chomsky hierarchy (general, context-sensitive, context-free, regular grammars), connections to decidability and recursive enumerability. The slides are uploaded to fl... Please read in the books, or in other sources covering the topics (e.g. Wikipedia, but also the original papers by Chomsky).
Course description: This is a third-semester obligatory course on basics of theoretical computer science: computability, complexity, formal languages, automata.
In this course we will learn the basics of the theory of computation, necessary to understand the limits of computing and complexity theory. In particular we will learn Turing machines, (un)decideability, hard problems, complexity theory, formal languages, grammars and automata.
Slides: Will be uploaded to http://fl.cosy.sbg.ac.at
Ana Sokolova
Dr. TU Eindhoven, The Netherlands, 2005
Associate Professor
Department of Computer Sciences
Austria
