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

Bijdragen tot het eindcijfer (aangepast):

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

• Tentamen: 7 november, 14:00-16:00, Educatorium Beta, open boek.
• Herkansing: 21 november, 14:00-16:00, BG 048.
• Extra WG's: woensdag (Rinke) en donderdag (Wilco), 13:15-15:00, Ruppert 129.
• Tussentoets: maandag, 10 october, 13:15, Ruppertgebouw, zaal Wit. Open boek. Stof: Deel I en II (zie Syllabus).
• Tussentoets van 2003. Zijn uitwerking.
• Tussentoets: resultaten.
• proeftentamen.
• Uitwerking van het proeftentamen.
• Aanmerking tot herkansing: een positief resultaat bij tussentoets en/of huiswerk.
• New! Eindcijfers na herkansing: .xls

Lecture 1: Finite automata. Language recognized by an automaton. Closure of regular languages under union, intersection, complement. Cartesian product construction. (Section 1.1.)

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.

Lecture 3: Regular expressions. Converting a regular expression into a finite automaton. Examples of non-regular languages. Pumping lemma.

Lecture 4: 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: Probabilistic computation. Class BPP. Amplification theorem. Calculating modulo n. Euclid algorithm. Invertible elements in Z_n. Calculating the inverse. Chinese remainder theorem. Fermat's little theorem. we are now here!

Lecture 13: Euler function, Euler theorem. Pseudoprimality. Probabilistic test of pseudoprimality. Miller-Rabin primality test.

Lecture 14: Cryptography. One-time pad cryptosystem. Public key criptosystems. RSA system. Electronic signatures in RSA.

1. Class: 1.1, 1.2, 1.3, 1.4(abcfi),
   Inleveropgave
   
2. Class: 1.5(ab), 1.8(a), 1.9, 1.10, 1.14(b), 1.15(ab), 1.17(a)
   Inleveropgave: 1.12 (a), 1.17(b)
3. Class: 1.23(ab), 2.1, 2.2(a), 2.3, 2.4(a,b,c), 2.10, 2.13; Opgaven 1-3 van problem set 1.
   Inleveropgave: 2.4(e) (nieuwe editie boek) of 2.4 (f) (oude editie); opgave 4 van problem set 1.
4. Class: Opgaven 8-16 van problem set 1, except for 12. An additional problem: prove that every context-free language is decidable.
   Inleveropgave: opgave 12.
5. Class: Opgaven 1,2,4,5,6,7 van problem set 3.
   Inleveropgave: 3,8 from problem set 3.
6. Class: Opgaven 2-9 van Computational complexity 3.
   Inleveropgave: Problem 2 from Computational Complexity 3.
7. 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)