| last update: | 14th of Dec 2020 |
|---|---|
| Author: | Lukas Prokop |
| license: | Public Domain |
| Version: | 1.0.1 "pr" |
Script for the course “Foundations of Computer Science”.
- 1.0
- Accepted by Q&A.
- 1.0.1
- Accepted pull requests regarding famous computer scientists.
- 1.1
- Consider future of encoding chapter.
- Introduce proof of halting problem.
- 1.2
Release if the following sections are ready:
- Redesign of tables 3.10, 3.11 and 3.12 to make them more self-explanatory.
- Check whether or not a nice cheatsheet for boolean logic is given including all laws by DeMorgan.
- Fix TODO flags of boolean logic section and make section more axiomatic.
- Introduce notes how to cope with NP-complete problems in programming.
- Better description for Chomsky hierarchy (more precise description of distinction of classes).
- 1.4 Release if the following sections are ready:
- Elaborate a bit more on Church-Turing thesis.
- "Solving logic problems" (by examples).
- 1.6 Release if the following sections are ready:
- Provide a more formally description for an NTM. Describe SAT-problem better.
- Elaborate on NP-hardness.
- Show hardness of SAT.
- 2.0 Release if the following sections are ready:
- Introduce known problems: 3SAT, 2SAT, HORNSAT, KNAPSACK, TSP.
- English translation available.
greets, prokls