Automaten en Complexiteit 2011-2012

Hoorcollege

Werkcollege

Boek

Extra stof

Tentamen

Inleveropgaven

1. 1e collectie inleveropgaven (Deadline: 3 oktober, 10:45 uur)
2. 2e collectie inleveropgaven (Deadline: 17 oktober, 10:45 uur)

Slides van het hoorcollege

Stof hoorcollege

1. 1.1 (vanaf blz 10, "Proof Techniques"), 1.2, 2.1, 2.2, 2.3: Talen als verzamelingen, grammatica's, deterministische eindige automaten, nondeterministische eindige automaten, equivalentie van deterministische en nondeterministische eindige automaten
2. 3.1, 3.2, 3.3, 4.1, 4.2: Equivalentie van rechts-lineaire grammatica's en eindige automaten, equivalentie van reguliere expressies en eindige automaten, elementaire eigenschappen van reguliere talen
3. 2.4, 4.3, 5.1, 5.2: String matching, minimale dfa's, lexicale analyse, pompstelling voor reguliere talen, contextvrije talen, afleidingsbomen, ambiguiteit
4. 5.2, 6.1, 6.2, 6.3, : Simpele grammatica's, vereenvoudigen van contextvrije grammatica's, Chomsky normaalvorm, CYK parseer-algoritme, LL parseren
5. <9.4, 9.5, 9.6 uit Grune en Jacobs>: LR(0) parseren, SLR(1) parseren, LR(1) parseren, LALR parseren
6. 7.1, 7.2, 7.3, <3.4 uit Lewis en Papadimitriou>: Nondeterministische pushdown automaten, deterministische pushdown automaten, equivalentie van contextvrije grammatica's en nondeterministische pushdown automaten
7. 8.1, 8.2, 9.1, 9.3, 10.2, 10.3, 10.4: Elementaire eigenschappen van contextvrije talen, pompstelling voor contextvrije talen, deterministische Turing machines, recursief opsombare talen, Church-Turing these, Turing machines met meerdere tapes, nondeterministische Turing machines, universele Turing machine
8. 10.5, 11.1, 11.2, 11.3, 11.4: Onbeperkte grammatica's, context-sensitieve grammatica's, lineaire begrensde automaten, recursieve talen, Chomsky hierarchie
9. 12.1, 12.2, 12.3, <12.4 uit Sudkamp>: Onbeslisbaarheid, halting probleem, stelling van Rice, Post correspondence probleem, onbeslisbare problemen voor contextvrije talen
10. Hoofdstuk 14, <7.2 uit Lewis en Papadimitriou>, <17.3, 17.4 uit Sudkamp>: Complexiteitsklassen P en NP, polynomiale-tijd reductie, NP-compleetheid, bounded tiling probleem, satisfiability probleem, PSpace, stelling van Savitch, PSpace-compleetheid, EXP en NEXP
11. <10.1, 10.2, 10.3 uit Arora en Barak>: Qubits, verstrengeling, quantum-operaties, pariteit-spel
12. <10.5, 10.7 uit Arora en Barak>: Quantum-circuits, superdense coding, algoritme van Simon, complexiteitsklassen BQP en BPP
13. vragenuurtje

Opgaven werkcollege (4e en 5e editie)

1. 1.2: 2,4,8,10,11(a,b,c),13,14(a,b,e,f,h)
   2.1: 1,2(d),3,7(b),9(b,f),11
   2.2: 12
   2.3: 2,3,6,12
2. 3.1: 5,7,13,16(a,b)
   3.2: 1,2,4(b,d),9,10(a,c),13(a)
   4.2: 5,12
   3.3: 1,3,6,12
   4.1: 17,20,26 (''regular'' moet ''right-linear'' zijn, 2x)
3. 2.4: 1,4,6
   4.3: 1,3,4(e,f)
   5.1: 2,7(b,e),8(b,h),21,22
   5.2: 9,14
4. JFLAP practicum opdracht
5. 5.2: 3,5

6.1: 6,7,9,15,16
6.2: 3,4
6.3: 1,2,3
4 opgaven over LL en LR parseren

6. 7.1: 3(a),4(c,g),5,11
   7.2: 5,6,15
   7.3: 3,5,8
7. 8.1: 2,3,5,8(c)
   8.2: 1,11,22,23
   7.3: 16,18
8. 1e collectie inleveropgaven
   9.1: 4,5,7(d,e),8
9. 11.1: 3,6,7,8,10
   11.2: 6,7
   11.3: 1(b,d),3
   10.5: 4(c,d)
   12.1: 3,7,9
   12.3: 1,3
   12.4: 3,7,8
10. 14.2: 5
    14.3: 2,3
    7 opgaven over complexiteit
11. Voorbeeldtentamen: tentamen uit 2005
12. 8 opgaven over quantum computing
13. 2e collectie inleveropgaven

Opgaven werkcollege (3e editie)

1. 1.2: 2,4,7,9,10(a,b,c),12,13(a,b,e,f,h)
   2.1: 1,2(d),3,7(b),9(b,f),11
   2.2: 11
   2.3: 2,3,6,12
2. 3.1: 4,6,12,14(a,b)
   3.2: 1,2,4(b,d),9,10(a,c),12(a)
   4.2: 5,12
   3.3: 1,3,5,11
   4.1: 17,20,26 (''regular'' moet ''right-linear'' zijn, 2x)
3. 2.4: 1,4,6
   4.3: 1,3,4(e,f)
   5.1: 2,7(b,e),8(b,h),20,21
   5.2: 3,5,9,14
4. JFLAP practicum opdracht
5. 6.1: 6,7,9 (``Exercise 7'' moet ``Exercise 6'' zijn),14,15
   6.2: 3,4
   6.3: 1,2,3
   4 opgaven over LL en LR parseren
6. 7.1: 3(a),4(c,g),5,11
   7.2: 5,6,15
   7.3: 3,5,8
   
7. 8.1: 2,3,5,8(c)
   8.2: 1,11,22,23
   7.3: 16,18
8. 1e collectie inleveropgaven
   9.1: 4,5,7(d,e),8
9. 11.1: 3,6,7,8,10
   11.2: 6,7
   11.3: 1(b,d),3
   10.5: 4(c,d)
   12.1: 3,7,9
   12.3: 1,3
   12.4: 3,8,9
10. 14.2: 6
    14.3: 2,3
    7 opgaven over complexiteit
11. Voorbeeldtentamen: tentamen uit 2005
12. 8 opgaven over quantum computing
13. 2e collectie inleveropgaven

Oude tentamens

Nuttige links