Prinzipielle Grenzen der Berechenbarkeit
Inhaltsverzeichnis |
Algorithmus
Definition
Ein Algorithmus ist eine Verarbeitungsvorschrift, die aus einer endlichen Folge von eindeutig ausführbaren Anweisungen besteht, die aus endlich vielen Eingabedaten endlich viele Ausgabedaten erzeugt und mit der man eine Vielzahl gleichartiger Aufgaben lösen kann.
Wie du sicher bemerkt hast, kommt in dieser Definition sehr oft der Begriff "endlich" vor. Dies wird später noch eine entscheidende Rolle spielen!
Wobei handelt es sich um einen Algorithmus? (Lösen einer quadratischen Gleichung) (!Auflistung aller Primzahlen) (Konstruieren eines Kreises durch 3 Punkte, die nicht auf einer Gerade liegen) (Wechseln eines Autoreifens) (!Schreiben einer Eins in der Schulaufgabe)
Entscheidbarkeit
Berechenbarkeit
Fleißige Biber
Halte-Problem
Aufgabe
Die Schüler der Kollegstufe besuchen |
verschiedene Kurse. Jeder Kurs findet einmal pro Woche statt. Belegt ein Schüler zwei Kurse, so dürfen diese nicht gleichzeitig stattfinden. Kann man mit 
verschiedenen Terminen auskommen?
Erstelle hierzu eine Graphen, wobei ein Knoten einem Kurs entspricht. Zwei Knoten werden genau dann miteinander verbunden, wenn ein Schüler die beiden entsprechenden Kurse besucht.
Man kann die Aufgabe als sogenanntes 
