327

Durch das Erzeugen eigener Begriffe und Konzepte bereichert sie zusätzlich auch die Mathematik in ihrer Grundlagenforschung. Die mit der Informatik entstandenen Informationstechnologien machen sie zum gleichwertigen Partner, nicht nur auf vielen naturwissenschaftlichen Gebieten der Grundlagenforschung, sondern auch in wissenschaftlichen Disziplinen wie Ökonomie, Soziologie, Didaktik oder Pädagogik, die sich lange gegen die Nutzung formaler Methoden und mathematischer Argumentation gewehrt haben.

Deswegen bieten die Spezialisierungen in der Informatik die Möglichkeit einer faszinierenden und interdisziplinären Grundlagenforschung sowie eine attraktive Arbeit in der Entwicklung von unterschiedlichen Systemen zur Speicherung und Bearbeitung von Informationen.

Zusammenfassung

Die Begriffsbildung ist maßgeblich für das Entstehen und die Entwicklung der wissenschaftlichen Disziplinen. Mit der Einführung des Begriffes Algorithmus wurde die Bedeutung des Begriffes Methode genau festgelegt (ein formaler Rahmen für die Beschreibung mathematischer Berechnungsverfahren wurde geschaffen) und damit die Informatik gegründet. Durch diese Festlegung konnte man mit klarer Bedeutung die Grenze zwischen automatisch (algorithmisch) Lösbarem und Unlösbarem untersuchen. Nachdem man viele Aufgaben bezüglich der algorithmischen Lösbarkeit erfolgreich klassifiziert hatte, kam der Begriff der Berechnungskomplexität auf, der die Grundlagenforschung in der Informatik bis heute bestimmt. Dieser Begriff ermöglicht es, die Grenze zwischen „praktischer“ Lösbarkeit und „praktischer“ Unlösbarkeit zu untersuchen. Er hat der Kryptographie eine Basis für den Begriff der Sicherheit und damit die Grundlage für die Entwicklung moderner Public-Key-Kryptosysteme gegeben und ermöglicht es, die Berechnungsstärke von Determinismus, Nichtdeterminismus, Zufallssteuerung und Quantenberechnungen im Vergleich zu studieren. Auf diese Weise trug und trägt die Informatik nicht nur zum Verständnis der allgemeinen wissenschaftlichen Kategorien wie

Determiniertheit, Nichtdeterminiertheit, Zufall, Information, Wahrheit,

Unwahrheit, Komplexität, Sprache, Beweis, Wissen, Kommunikation, Algo-

rithmus, Simulation usw.

bei, sondern gibt mehreren dieser Kategorien einen neuen Inhalt und damit eine neue Bedeutung. Die spektakulärsten Ergebnisse der Informatik sind meistens mit dem Versuch verbunden, schwere Aufgabenstellungen zu lösen.

Kontrollfragen

1.Warum entstand ein Bedarf, den Begriff der Methode genau zu definieren?

2.Was strebte David Hilbert an, und woran haben viele Mathematiker am Anfang des zwanzigsten Jahrhunderts geglaubt?

3.Was war die wichtigste Entdeckung von Kurt Gödel?

4.Was verstand man unter den „Dämonen“ in der Physik?

5.Was misst man mittels der Berechnungskomplexität?

6.Gibt es algorithmisch lösbare Aufgaben, die man praktisch nicht lösen kann?

7.Wo gibt es gemeinsame Interessen zwischen Informatik und Biologie?

8.In welchem Bereich treffen sich Physik und Informatik?

9.Was ist die Ausdrucksstärke einer mathematischen Theorie? Was ist die Beweisstärke einer mathematischen Theorie? Kann man sie vergleichen?

10.Welches sind die fundamentalen Begriffe der Informatik? Gib Beispiele für den Einfluss der Begriffsbildung in der Informatik auf andere Wissenschaften.

Nehmen wir das Rezept für einen Aprikosenkuchen von 26 cm Durchmesser.

Zutaten:

Rezept:

1.Ein Pergamentpapier in die Springform einspannen.

2.Den Backofen auf 180◦C vorheizen.

3.6 Esslö el Wasser erwärmen.

4.Die drei Eiweiße mit einer Prise Salz und dem heißen Wasser zu steifem Schnee schlagen.

5.100g Zuckerrohrgranulat und die Eigelbe nach und nach unterrühren. Danach solange rühren, bis eine feste, cremige Masse entstanden ist.

6.1 Teelö el abgeriebene Zitronenschale dazugeben und vermischen.

-Was bedeutet hellbraun backen (Schritt 10)?

-Was bedeutet nach Belieben bestäuben (Schritt 12)?

Eine erfahrene Köchin würde sagen: „Alles ist klar, genauer kann man es nicht angeben.“ Jemand, der das erste Mal in seinem Leben einen Kuchen backen will, könnte noch mehr Rat und Hilfe brauchen, bis er sich an die Arbeit traut. Und dabei ist unser Rezept einfacher formuliert als in den meisten Kochbüchern. Was denkst du z. B. über Anweisungen wie:

Die leicht abgekühlte Gelatinemasse zügig unter die Quarkmasse geben und gut durchrühren.

Wir dürfen natürlich nicht zulassen, dass nur Erfahrene das Rezept für einen Algorithmus halten und der Rest der Welt nicht. Man muss eine Möglichkeit suchen, eine Einigung zu erzielen. Wir verstehen schon, dass ein Algorithmus eine Folge von Anweisungen ist, wobei jede angegebene Tätigkeit von jeder Person korrekt durchführbar sein muss. Dies bedeutet:

Man muss sich zuerst auf eine Liste der Tätigkeiten (Operationen) einigen, die jede oder jeder der kochund backwilligen Menschen mit Sicherheit beherrscht.

So eine Liste kann zuerst z. B. folgende Tätigkeiten enthalten, die möglicherweise sogar ein für diese Zwecke gebauter Roboter ohne jedes Verständnis der Kochkunst und ohne jede Improvisationsfähigkeit realisieren kann.

•Gib x Löffel Wasser in ein Gefäß.

•Trenne ein Ei in Eiweiß und Eigelb.

•Heize den Ofen auf x Grad vor mit einer angegebenen Temperatur von x Grad.

•Backe y Minuten mit x Grad.

•Wiege x g Mehl ab und gib es in eine Schüssel.

•Gieße x l Milch in eine Kanne.

333

•Koche y Minuten.

•Mische mit dem Schneebesen x Minuten.

•Rühre mit einer Gabel x Minuten.

•Fülle eine Form mit einem Teig.

•Schäle x kg Kartoffeln.

•Mische den Inhalt zweier Gefäße.

Sicherlich fallen dir viele weitere Tätigkeiten ein, die du für so einfach hälst, dass du sie jedem, der backen will, ohne weitere Erklärung zutraust. Im Folgenden geht es darum, ein Rezept so umzuschreiben, dass dabei die Befehle (Anweisungen) nur ausgewählte, einfache Basistätigkeiten verwenden.

Aufgabe 4.1 Versucht euch in 4- bis 5-köpfigen Gruppen auf eine Liste von Tätigkeiten zu einigen, die eurer Meinung nach jede und jeder aus der Klasse in der Küche beherrschen müsste. Überprüft eure Wahl, indem ihr eure Liste dem Rest der Klasse vorstellt und nachfragt, ob jede Person damit zurecht kommen würde. Überprüft eure Liste auf Vollständigkeit. Jede gewöhnliche Kochtätigkeit müsste durch eine Folge der Tätigkeiten aus der Liste darstellbar sein.

Versuchen wir jetzt, den Schritt 4 des Rezeptes in eine Folge einfacher Anweisungen umzuschreiben:

4.1Gib die drei Eiweiße in das Gefäß G.

4.2Gib 1g Salz in das Gefäß G.

4.3Gib 6 Löffel Wasser in den Topf T.

4.4Erwärme das Wasser im Topf T auf 60◦C.

4.5Gieße das Wasser aus T in G.

An dieser Stelle ist aber nicht klar, wann die Anweisung „zu steifem Schnee schlagen“ umgesetzt wurde. Wir sollen rühren, bis der Eischnee steif ist. Ein Ausweg können

Erfahrungswerte sein. Es dauert ungefähr zwei Minuten, bis das Eiweiß steif ist. Dann könnte man schreiben:

4.6 Rühre den Inhalt von G 2 Minuten lang.

Eine solche Anweisung birgt aber auch gewisse Risiken in sich. Die Fertigungszeit hängt davon ab, wie schnell und mit welchen Hilfsmitteln man rührt. Also wäre es uns lieber, wirklich ungefähr dann aufzuhören, wenn das gerührte Material steif geworden ist. Was brauchen wir dazu? Die Fähigkeit, Tests durchzuführen (um den Zeitpunkt zu erkennen, an dem die Anweisung „zu steifem Schnee schlagen“ umgesetzt worden ist) und abhängig von dem Resultat die Entscheidung zu treffen, wie man weiter vorgehen soll. Wenn der Schnee noch nicht steif ist, soll man noch gewisse Zeit rühren und dann wieder testen. Wenn der Schnee steif ist, ist Schritt 4 abgeschlossen und wir sollen mit dem Schritt 5 die Arbeit fortsetzen.

Wie kann man dies als eine Befehlsfolge schreiben?

4.6Rühre den Inhalt von G 10s lang.

4.7Teste, ob der Inhalt von G „steif“ ist. Falls JA, setze mit 5 fort.

Falls NEIN, setze mit 4.6 fort.

Damit kehrt man zum Rühren in 4.6 so oft zurück, bis der gewünschte Zustand erreicht ist. In der Fachterminologie der Informatik nennt man 4.6 und 4.7 eine Schleife, in der man 4.6 so lange wiederholt, bis die Bedingung 4.7 erfüllt ist. Um dies zu veranschaulichen, benutzen wir oft eine graphische Darstellung wie in Abb. 4.1 auf der nächsten Seite, die man Flussdiagramm nennt.

Ist aber der Test in 4.6 so leicht durchführbar? Wir müssen uns, genau wie bei der Tätigkeitsanweisung, auf eine sorgfältig gewählte Liste von einfachen Tests einigen. Den Test 4.6 kann man zum Beispiel so realisieren, dass man in die Masse einen kleinen, leichten Kunststofflöffel stecken kann, und wenn er stecken bleibt, betrachten wir die Masse als steif. Beispiele von einfachen Tests könnten Folgende sein:

•Teste, ob die Flüssigkeit im Topf mindestens x◦C hat.

•Teste, ob die Masse im Gefäß „löffelfest“ ist.

335

4.4

4.5

4.6 R¨uhre 10s lang

den Inhalt von G

NEIN

Ist der Inhalt von G steif?

JA

5

Abbildung 4.1 Flussdiagramm

• Wiegt der Inhalt eines Gefäßes genau x g?

Aufgabe 4.2 Setzt die Arbeit in Gruppen fort und stellt eine Liste von Testfragen her, die man beim Kuchenbacken braucht und jeder Person in der Klasse zumutbar sind.

Aufgabe 4.3 Schreibt den Schritt 5 des Rezeptes für den Aprikosenkuchen so um, dass in der Beschreibung dieser Tätigkeiten nur jene Tätigkeiten und Tests aus Euren Listen vorkommen.

Aufgabe 4.4 Schreibe ein Rezept für die Herstellung deines Lieblingsessens aus dem Kochbuch ab. Liste deiner Meinung nach einfache Anweisungen und Tests auf und schreibe dein Rezept so um, dass es nur Tätigkeiten aus einer Liste enthält.

Aufgabe 4.5 Wir wollen 1 l Wasser auf 90 ◦C erwärmen. Folgende Operationen hast du zur Verfügung:

„Stelle den Topf T für x Sekunden auf eine heiße Herdplatte und nimm ihn dann weg.“

und „Gieße y l Wasser in einen Topf T .“