Lecture Slides
| No | Topic | Date | Slides |
|---|---|---|---|
| A1 | Organizational Matters | 18.2. | screen print 4 print 1 |
| A2 | Mathematical Foundations | 18.2. | screen print 4 print 1 |
| A3 | Proof Techniques | 20.2. | screen print 4 print 1 |
| B1 | Propositional Logic I | 25.2. | screen print 4 print 1 map.pl |
| B2 | Propositional Logic II | 27.2. | screen print 4 print 1 |
| B3 | Propositional Logic III | 4.3. | screen print 4 print 1 |
| B4 | Predicate Logic I | 4.3. | screen print 4 print 1 |
| B5 | Predicate Logic II | 6.3. | screen print 4 print 1 |
| C1 | Formal Languages and Grammars | 18.3. | screen print 4 print 1 |
| C2 | Regular Languages: Finite Automata | 20.3. | screen print 4 print 1 |
| C3 | Regular Languages: Regular Expressions & Pumping Lemma | 25.3. | screen print 4 print 1 |
| C4 | Regular Languages: Minimal Automata, Closure Properties & Decidability | 27.3. | screen print 4 print 1 |
| C5 | Context-free Languages: Normal Form & PDA | 1.4. | screen print 4 print 1 |
| C6 | Context-free Languages: Closure & Decidability | 3.4. | screen print 4 print 1 |
| C7 | Type-1 and Type-0 languages: Turing Machines | 3.4 | screen print 4 print 1 |
| C8 | Type-1 and Type-0 languages: Closure & Decidability | 8.4. | screen print 4 print 1 |
| D1 | Turing-Computability | 8.4. | screen print 4 print 1 |
| D2 | Recursive Enumerability & Decidability | 10.4. | screen print 4 print 1 |
| D3 | Halting Problem & Reductions | 15.4. | screen print 4 print 1 |
| D4 | Halting Problem Variants & Rice’s Theorem | 17.4. | screen print 4 print 1 |
| E1 | Complexity Theory: Introduction | 24.4. | screen print 4 print 1 |
| E2 | P, NP & Polynomial Reductions | 29.4. | screen print 4 print 1 |
| E3 | Proving NP-Completeness | 6.5. | screen print 4 print 1 |
| E4 | NP-complete Problems I | 8.5. | screen print 4 print 1 |
| E5 | NP-complete Problems II | 13.5. | screen print 4 print 1 |
| E6 | Beyond NP | 15.5. | screen print 4 print 1 |
| F1 | LOOP-computability | 15.5. | screen print 4 print 1 |
| F2 | WHILE-computability | 20.5. | screen print 4 print 1 |
| F3 | GOTO-computability | 22.5. | screen print 4 print 1 |
Exercises
| No | Due Date | Exercise | Solution |
|---|---|---|---|
| 1 | 27.2. | English Deutsch | English Deutsch |
| 2 | 6.3. | English Deutsch | English Deutsch |
| 3 | 20.3. | English Deutsch | English Deutsch |
| 4 | 27.3. | English Deutsch | English Deutsch |
| 5 | 3.4. | English Deutsch | English Deutsch |
| 6 | 10.4. | English Deutsch | English Deutsch |
| 7 | 22.4. | English Deutsch | English Deutsch |
| 8 | 24.4. | English Deutsch | English Deutsch |
| 9 | 1.5. | English Deutsch | English Deutsch |
| 10 | 8.5. | English Deutsch | English Deutsch |
| 11 | 15.5. | English Deutsch | English Deutsch |
| 12 | 22.5. | English Deutsch | English Deutsch |
| model exam Probeklausur |