Lecture Slides
| No | Topic | Date | Slides |
|---|---|---|---|
| A1 | Organizational Matters | 17.2. | screen print 4 print 1 |
| A2 | Mathematical Foundations | 17.2. | screen print 4 print 1 |
| A3 | Proof Techniques | 17.2./ | screen print 4 print 1 |
| B1 | Propositional Logic I | 19.2. | screen print 4 print 1 |
| B2 | Propositional Logic II | 24.2. | screen print 4 print 1 |
| B3 | Propositional Logic III | 26.2. | screen print 4 print 1 |
| B4 | Predicate Logic I | 9.3. | screen print 4 print 1 |
| B5 | Predicate Logic II | 16.3. | screen print 4 print 1 |
| C1 | Formal Languages & Grammars | 18.3. | screen print 4 print 1 |
| C2 | Regular Languages: Finite Automata | 23.3. | screen print 4 print 1 |
| C3 | Regular Languages: Regular Expressions | 25.3. | screen print 4 print 1 |
| C4 | Regular Languages: Pumping Lemma, Closure Properties & Decidability | 30.3. | screen print 4 print 1 |
| C5 | Context-free Languages: Chomsky Normal Form & PDAs | 1.4. | screen print 4 print 1 |
| C6 | Context-free Languages: Closure Properties & Decidability | 6.4. | screen print 4 print 1 |
| C7 | Type 1 and Type 0 Languages: Turing Machines | 8.4. | screen print 4 print 1 |
| C8 | Type 1 and 0: Connection to TMs, Closure Properties & Decidability | 15.4. | screen print 4 print 1 |
| D1 | Turing-computability | 20.4. | screen print 4 print 1 |
| D2 | Decidability | 22.4. | screen print 4 print 1 |
| D3 | Special Halting Problem & Reduction | 27.4. | screen print 4 print 1 |
| D4 | Halting Problem Variants & Rice's Theorem | 29.4. | screen print 4 print 1 |
| D5 | Post Correspondence Problem | 4.5. | screen print 4 print 1 |
| E1 | Complexity Theory: Introduction | 6.5. | screen print 4 print 1 |
| E2 | P, NP and Polynomial Reductions | 11.5. | screen print 4 print 1 |
| E3 | SAT und 3SAT | 13.5. | screen print 4 print 1 |
| E4 | NP-complete Problems I | 18.5. | screen print 4 print 1 |
| E5 | NP-complete Problems II | 20.5. | screen print 4 print 1 |
| E6 | Beyond NP | 25.5. | screen print 4 print 1 |
| F1 | Other Models of Computability | 27.5. | screen print 4 print 1 |
Exercises
| No | Due Date | Exercise | Solution |
|---|---|---|---|
| 1 | 26.2. | English Deutsch | English Deutsch |
| 2 | 11.3. | English Deutsch code | English Deutsch |
| 3 | 18.3. | English Deutsch | English Deutsch |
| 4 | 25.3. | English Deutsch | English Deutsch |
| 5 | 1.4. | English Deutsch | English Deutsch |
| 6 | 8.4. | English Deutsch | English Deutsch |
| 7 | 15.4. | English Deutsch | English Deutsch |
| 8 | 22.4. | English Deutsch Code | English Deutsch Code |
| 9 | 29.4. | English Deutsch | English Deutsch |
| 10 | 6.5. | English Deutsch | English Deutsch |
| 11 | 13.5. | English Deutsch | English Deutsch |
| 12 | 20.5. | English Deutsch | English Deutsch |
Additional Material
| Description | Files |
|---|---|
| Example: Exercise submission in LaTeX | LaTeX source code (english) resulting PDF (english) LaTeX source code (german) resulting PDF (german) |
| LaTeX Cheat Sheet |