Foundations of Informatics - A Bridging Course
The course provides an introduction to foundations of informatics and is organized in cooperation with b-it and University of Bonn. For the main site please see [this page].
Week 4: Computability and Complexity
Monday, March 24:
9:00-9:30h: [Kick-Off Meeting via Zoom], Organizational Topics
Remainder of the day self-paced learning:- Introduction to Computability
- Countable Sets
- Basics of Computability
- Undecidability
- Theorem of Rice
Tuesday, March 25:
9:00-10:30h: [Zoom meeting], Questions and Exercises
Remainder of the day self-paced learning:- Post Correspondence Problem
- Recursive Enumerability
- The Total Halting Problem
- Hilbert's Tenth Problem
[Videos] and [Slides] for Tuesday
Some further [exercises] for computabilityWednesday, March 26:
9:00-10:30h: [Zoom meeting], Questions and Exercises
Remainder of the day self-paced learning:- Introduction to Complexity
- P and NP
- Polynomial-Time Reductions
- NP-Completeness
Thursday, March 27:
9:00-10:30h: [Zoom meeting], Questions and Exercises
Remainder of the day self-paced learning:- More NP-Complete Problems
- Even more NP-Complete Problems
Friday, March 28:
9:00-11:00h: [Zoom meeting], Questions and Exercises