In einer Klasse mit 8 Mädchen und 6 Jungen ist die größtmögliche Clique zu suchen. Erstellen Sie einen Beispielgraphen, in dem die größte Clique 5 ist. (z. Bsp. Schüler, die sich untereinander zu Hause schon besucht haben).

Erklären Sie derzeitige Grenzen der Informatik im Bereich Hardware!

Erläutern Sie die Churchsche These!

Erläutern Sie das Behälterproblem / Knotenüberdekungsproblem / Rucksackproblem!

Erläutern Sie die Addition / Subtraktion auf einer Turingmaschine an einem Beispiel!

Was kann man alles mit einer Turingmaschine berechnen?

Nennen Sie die Bestandteile der Turingmaschine!

Erlutern Sie mithilfe der Aufgabe 4 + 5 die Arbeitsweise der Turingmaschine!

Was heißt berechenbar?

Was heißt nicht berechenbar?

Erklären Sie das Halteproblem, indem Sie einen Dialog zwischen zwei Schülern schreiben!

Worin besteht das Problem des Handelsreisenden? Erläutern Sie dieses an einem Beispiel!