gdi_doc

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”.

Roadmap

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