Tentamen en tussentoets: open boek (1-2 theoretische vragen, 4-5 opgaven)

Bijdragen tot het eindcijfer (aangepast):

• Tussentoets: 15%
• Huiswerkopgaven: 15%
• Tentamen: 70%

• Maandag 1.11, hoorcollege: voorbereiding voor het tentamen.
• Donderdag 4.11, geen hoorcollege, wel een proeftentamen. .pdf
  Werkgroepen: uitwerking van het proeftentamen. .pdf
• Belangrijk: Degenen die de tussentoets niet hebben gehaald kunnen wel het eindtentamen doen. Zij mogen dan niet herkansen.
• Tussentoets: 30.09, 11:00-12:45 (in de werkgroepen).
• Results: .xls
• Tentamen: 8.11, 14:00-17:00, Educatorium Alpha.
• Gido's page with exercises
• Examination Results: .xls
• New! Herkansingresultaten zijn in de aangepaste lijst: .xls

Lecture 1: Finite automata. Language recognized by an automaton. Closure of regular languages under union, intersection, complement (cartesian product construction). Operations concatenation and star. (Sections 1.1 and 1.2 until Page 53.)

Lecture 2: Non-deterministic automata. Computation trees. Converting a non-deterministic automaton into a deterministic one. Subset construction. Closure of the class of regular languages under concatenation and star. Regular expressions. Converting a regular expression into a finite automaton.

Lectures 3-4: Examples of non-regular languages. Pumping lemma. Context-free grammars and languages. Regular languages are context-free. Pushdown automata. (Pages 91-97, 101-106.)

Lecture 5: Turing machines. Computable (partial) functions. Acceptors and Deciders. Decidable and r.e. languages. (Section 3.1)

Lecture 6: Encoding computational problems as languages. Famous undecidable problems: Entscheidungsproblem, solvability of Diophantine equations. Computable encoding of pairs and sequences of numbers. Characterizations of decidable and r.e. languages. (Theorem 3.13, p. 141.)

Lecture 7: Universal Turing machine. Undecidability of the halting problem (with a proof).

Lecture 8: Time and space complexity measures. Big O, small o notation. Complexity classes. Estimating the complexity of some algorithms. Class P. Euclid algorithm.

Lecture 9: Encoding of graphs and other objects. Class NP. Examples of problems from NP: SAT, HAMPATH, CLIQUE. Equivalent characterizations of NP.

Lecture 10: P-reducibility. NP-completeness. P-reduction of 3SAT to CLIQUE. Cook-Levin Theorem (NP-completeness of SAT).

Lecture 11: Class PSPACE. Savitch theorem. TQBF problem. PSPACE-completeness of TQBF. P-reduction of TQBF to Generalized Geography.

Lecture 12: Cryptography. One-time pad cryptosystem. Calculating modulo n. Euclid algorithm. Invertible elements in Z_n. Calculating the inverse.

Lecture 13: Euler function. Euler theorem and Fermat's little theorem. Pseudoprimality. Probabilistic test of pseudoprimality. Miller-Rabin primality test.

Lecture 14: Public key criptosystems. RSA system. Electronic signatures in RSA.

1. Class: 1.1, 1.2, 1.3, 1.4(abcfi),
   Inleveropgave:
   Design a DFA that recognises all strings with an uneven number of 0's or ending in two 1's. For example, it should recognise "01011", "1110" and "0", but not "00", "1001" or the empty string.
   
   
2. Class: 1.5(ab), 1.8(ab), 1.9, 1.10, 1.12(a), 1.14(a), 1.15(abc)
   
   
3. Class: 1.17(ac), 1.23(ab), 1.24
   Inleveropgave: 1.17(b)
   
   
4. Class: 2.1, 2.3, 2.4, 2.5, (2.15)
   
   
5. Class: Opgaven 1-9 van problem set 1.
   
   
6. Class: Opgaven 1,2,4,5,6,7 van problem set 3.
   Inleveropgave: 3,8 from problem set 3.
   
   
7. Class: Opgaven 2-9 van Computational complexity 3.
   Inleveropgave: Problem 2 from Computational Complexity 3.
   
   
8. Class: Opgaven 1,2,4,5,6,7 van Cryptography.
   
   

Part 1. Basic formal language theory

• Automata. Regular languages. (1.1)
• Deterministic and non-deterministic automata. (1.2)
• Regular expressions. (1.3) Non-regular languages and pumping lemma. (1.4)
• Context-free grammars. Pushdown automata. (2.1, 2.2)
• Chomsky hierarchy.

Part 2. Basic computation theory

• Turing machines, computable functions   (3.1)
• Decider and acceptor Turing machines; decidable and r.e. languages and sets (3.1)
• Church-Turing thesis, Entscheidungsproblem (3.3)
• Equivalent formulations of r.e. sets, graph theorem (Theorem 3.13, p. 141)
• Universal Turing machine (4.2, beginning)
• Undecidability of the halting problem (4.2, 5.1)
• Decidable and undecidable logical theories, Goedel Theorem, Diophantine equations, Matiyasevich theorem (without proofs)

• Assimptotic O and o notations. Time and space complexity measures.  (7.1 + p.277-279)
• Classes P and PSPACE. (7.2, 8.2)
• Robustness of complexity classes, reasonable encodings. (7.2, beginning)
• Examples of problems in P: testing connectivity of a graph. (7.2, p.236-238)
• Class NP, nondeterministic Turing machines.  (7.3, Theorem 7.17)
• Satisfyiability problem. Clique and Hamiltonian path problems. (p.242, 246, 249)
• Polynomial reducibility. NP-completeness. (7.4, beginning)
• Cook's Theorem. (7.4, p.254)
• PSPACE-completeness. (8.3, p.283)
• Quantified boolean formulas, TQBF problem, generalized geography. (8.3, the rest)

Part 4. Elements of cryptography

• Calculating modulo n. Ring Z_n. Inverible elements. Euclid algorithm.
• Euler function. Euler theorem and Fermat's little theorem. (not in the texbook, no proof obligatory)
• Pseudoprimes. Probabilistic polynomial algrothms for testing pseudoprimality and primality.  (p. 339-343)
• Cryptosystems, one time pad cryptosystem, information-theoretic security (p.372-273)
• Public key cryptosystems (p.374-376)
• RSA cryptosystem (p.377)