, projekte:vorkurs-informatik:mathe-versus-informatik

Mathematik, Programmieren und Informatik

  • Gemeinsamkeiten: die Sprache und Schreibweisen z.B. Zahlen, Variablen, Funktionen, Mengen, Vektoren…
  • aber große Unterschiede im Schwerpunkt: Zum Programmieren brauchen wir vor allem diskrete Mathematik (ganze Zahlen, Mengen) und Typen anstelle von Integralen, Ableitungen usw.
  • das Programmieren nutzt einige Schreibweisen der Mathematik, um übersichtlich zu bleiben und um Probleme/Aufgaben zu beschreiben.
  • die gute Nachricht: Das Arbeiten mit Variablen, Typen, Ausdrücken und Regeln üben, macht auch die Mathematik-VL verständlicher. Das liegt an der gemeinsamen Sprache.

Von Werten zu Variablen und Typen und zurück

Ziel: Warum lieben die Informatiker und Programmierer das Abstrakte so sehr? Warum so viele Variablen? Wozu sind diese Typen gut?

Wenn wir per Hand rechnen oder andere Probleme lösen, so machen wir dies in der Regel auf konkreten Werten. Zum Beispiel lösen wir die Gleichung wie durch Umstellen nach und rechnen dabei direkt mit den Werten 2,4,7 und so weiter. Das funktioniert ganz gut auf dem Papier, hilft aber wenig, wenn wir Computer so programmieren wollen, dass sie diese Arbeit für uns übernehmen. Der Grund ist, dass sich der Programmieraufwand erst lohnt, wenn das Programm für sehr viele ähnliche Aufgabenstellungen funktioniert – nicht nur für , sondern auch z.B. mit anderen Zahlenwerten. Aber zum Zeitpunkt des Programmierens kennen wir diese Werte noch nicht. Sie sollen erst später beim Benutzen des Programms festgelegt werden.

per Hand lösen: auf beiden Seiten 3 subtrahieren, dann beide Seiten durch 2 dividieren ⇒ . Und ist eine Lösung der Gleichung, weil ist.

Wie können wir ein Programm schreiben, dass Gleichungen wie löst, ohne dass wir dabei die konkreten Werte kennen? Der Trick besteht darin, die konkreten Werte durch Variablen zu ersetzen. Sie sind Platzhalter für die Werte die später vom Benutzer des Programms festgelegt werden. Nun haben wir eine allgemeinere Gleichung der Form mit den Variablen a, b, c und x, wobei die ersten drei vom Benutzer gegeben werden und ein Wert für vom Programm gesucht werden soll.

per Hand lösen: auf beiden Seiten subtrahieren, dann beide Seiten durch a dividieren ⇒ . Dies ist eine Lösung der Gleichung, weil ist.

Damit unser Programm sinnvoll arbeiten kann, müssen wir allerdings noch einschränken, welche Werte für a, b und c erlaubt sind. Zum Beispiel wissen wir nicht (und dadurch auch nicht das Programm), was gemacht werden muss, wenn der Benutzer irgendwelche Zeichenketten ("foo", "hallo", usw.) als Werte für a, b und c festlegt. Diese Einschränkung der erlaubten Werte machen wir mit Hilfe von Typen. Sie sagen auf der einen Seite dem Benutzer unseres Programms, welche Art von Werten er uns geben darf; und sie sagen uns, welche (Rechen-)Operationen wir mit diesen Werten machen dürfen.

Etwas ähnliches wie Typen sind Maßeinheiten z.B. beim Backen. Wenn in einem Rezept der Wert "50" alleine steht, können wir damit leider nichts sinnvolles anfangen. Viel hilfreicher sind Angaben wie "50 ml Wasser" und "100 g Mehl". Dabei stellen "ml Wasser" und "g Mehl" Typ-Informationen dar. Wir wissen, dass man Wasser und Mehl mischen kann. Die Anweisung "mische 50 ml Wasser und 100 g Mehr" liefert uns wahrscheinlich das Ergebnis "150 g Teig". Aber wir können diese Typen nicht beliebig mischen: "mische 1 liter Wasser und 50 ml Wasser" geht nicht direkt, weil "liter" und "ml" nicht zusammenpassen. Manchmal helfen uns dann Typ-Umwandlungen weiter: "1 liter" ist das selbe wie "1000 ml" und "mische 1000 ml Wasser und 50 ml Wasser" ergibt "1050 ml Wasser", was das selbe ist wie "1.05 liter Wasser".

In unserem Beispiel-Problem "Gleichung lösen" haben wir die Variablen a, b, c, und x. Als Typ für diese Variablen eignet sich in der Programmiersprache C++ der Typ float. Dieses sind so genannte Gleitkomma-Zahlen, also Werte wie z.B. 3.1516, 203.0, -0.5, 4711, 0. Mögliche Rechenoperationen sind zum Beispiel "+ - * /". Wenn a und b vom Typ float sind, ergibt der Ausdruck a + b einen Float-Wert, welcher der Summe der Werte in a und b entspricht.

Ein Beispiel-Programm

Das folgende (unvollständige) Programm zeigt die Definition einer Funktion namens "loese_mini_gleichung". Diese löst einfache Gleichungen der Form "a*x+b=c" wie oben besprochen. Sie bekommt Werte für die Variablen a, b und c gegeben und alle drei Werte müssen vom Typ float sein (Gleitkomma-Zahlen). Ihr Ergebnis ist wiederum ein Wert vom Typ float. Über Details sprechen wir später.

/** löst Gleichungen der Form "a*x+b=c" nach x auf. */
float loese_mini_gleichung(float a, float b, float c)
{
  return (c-b)/a;
}

Zum Beispiel könnte diese Funktion angewendet werden mit loese_mini_gleichung(2,3,7) und würde dann den Wert 2.0 als Ergebnis liefern.

Auswertungsschritt a b c Kommentar
loese_mini_gleichung(2,4,7) am Anfang war der Ausdruck, in der die Funktion angewendet wird
loese_mini_gleichung(float a, float b, float c) 2 4 7 die gegeben Werte in die Variablen legen
return (c-b)/a; 2 4 7 dies ist die erste Anweisung in der Funktion
return (7-4)/2; 2 4 7 aktuelle Werte aus den Variablen hier einsetzen
return 3/2; 2 4 7 rechnen, …
return 1.5; 2 4 7 rechnen und fertig
1.5 der Wert 1.5 wurde als Ergebnis zurückgegeben;
der Wert von loese_mini_gleichung(2,4,7) ist also 1.5;
hier sind die Variablen a,b,c nicht mehr sichtbar

Zusammenfassung

  • Wir wollen für viele verschiedene Aufgaben der gleichen Form unser Programm wiederverwenden.
  • Dafür müssen die konkreten Werte durch Variablen (Platzhalter, Container) ersetzt werden. Übrig bleibt nur die Form/Struktur der Aufgabe.
  • Typ-Angaben für die Variablen sagen, für welche Art von Werten das Programm funktionieren soll und welche Operationen wir auf diese Werte anwenden können.
  • Unser Programm arbeitet auf der Struktur der Aufgabe. Konkrete Werte liefert erst später der Benutzer des Programms. Wir schreiben die Arbeitsschritte zur Lösung der Aufgabe als Algorithmus in das Programm.
  • im Glossar nachlesen: Häufig verwendete Typen
  • im Glossar nachlesen: Häufig verwendete Operatoren
  • Das Programmieren ist zu einem großen Teil "Denken in Typen". Kompliziertere Aufgaben führen zu komplizierten Typen und mehr anwendbaren Operationen und Funktionen.
  • Typen sind eine sehr umfangreiche Vorstellung und nicht alle Typen kann man in einer Programmiersprache direkt ausdrücken. Man arbeitet dann mit allgemeineren, einfacheren Typen und schreibt in Kommentaren, welche zusätzlichen Einschränkungen gelten. Zum Beispiel sprechen wir auch über Gleichungen vom Typ und Gleichungen vom Typ . Das können wir erstmal nicht in der Programmiersprache angeben. Deswegen enthält das obige Beispiel einen Kommentar der sagt, welche Art/Typ Gleichung wir in der Funktion loese_mini_gleichung lösen.

Das komplette Programm

#include "vorkurs.hpp"
 
/** löst Gleichungen der Form "a*x+b=c" nach x auf. */
float loese_mini_gleichung(float a, float b, float c)
{
  return (c-b)/a;
}
 
/** das Hauptprogramm: fragt die Werte vom Benutzer, gibt Ergebnis aus. */
void main() 
{
  float w1 = vk::ask_float("Wert für a");
  float w2 = vk::ask_float("Wert für b");
  float w3 = vk::ask_float("Wert für c");
  float x = loese_mini_gleichung(w1,w2,w3);
  vk::print("Die Lösung ist ", x);
}
Auswertungsschritt w1 w2 w3 x a b c Kommentar
main() Ein Programm wird immer mit
der Haupt-Funktion "main" gestartet.
float w1 = vk::ask_float("Wert für a"); 2 ? ? ? Benutzer fragen und Antwort in Variable w1 ablegen.
Eingabe ist z.B. 2
float w2 = vk::ask_float("Wert für b"); 2 4 ? ? Benutzer fragen und Antwort in Variable w2 ablegen.
Eingabe ist z.B. 4
float w3 = vk::ask_float("Wert für c"); 2 4 7 ? Benutzer fragen und Antwort in Variable w3 ablegen.
Eingabe ist z.B. 7
float x = loese_mini_gleichung(w1, w2, w3); 2 4 7 ? "Funktion anwenden, danach Ergebnis nach x"
float x = loese_mini_gleichung(2, 4, 7); 2 4 7 ? die aktuellen Werte der Variablen einsetzen
→→loese_mini_gleichung(float a, float b, float c) 2 4 7 die gegeben Werte in die Variablen a,b,c legen;
w1,w2,w3,x sind hier nicht mehr sichtbar
→→return (c-b)/a; 2 4 7 dies ist die erste Anweisung in der Funktion
→→return (7-4)/2; 2 4 7 aktuelle Werte aus den Variablen hier einsetzen
→→return 3/2; 2 4 7 rechnen, …
→→return 1.5; 2 4 7 rechnen und fertig
float x = 1.5; 2 4 7 1.5 der Wert 1.5 war das Ergebnis und wurde in x gelegt.
hier sind die Variablen a,b,c nicht mehr sichtbar
vk::print("Die Lösung ist ", x); 2 4 7 1.5 die letzte Zeile in main
vk::print("Die Lösung ist ", 1.5); 2 4 7 1.5 für Variable x ihren aktuellen Wert einsetzen
; 2 4 7 1.5 Die Funktion vk::print anwenden. Hat kein Ergebnis,
aber der Benutzer sieht "Die Lösung ist 1.5".
Die Funktion "main" ist fertig und hat kein Ergebnis
(außer die Bildschirmausgaben).

Algorithmen: Arbeitsschritte zum Lösen von bestimmten Aufgaben

  • Lösen von Gleichungen wie nach .
  • Den größten gemeinsamen Teiler ggT(a,b) von und finden. (Beide vom Typ int)
  • Lösen von linearen Gleichungssystemen
  • Sortieren von Daten
  • Berechnen von Statistiken über gegebene Daten
  • Vorhersage von Aktienkursen
  • Künstliche Intelligenz für Spiele: TicTacToe, Dame, Schach, Doom3, …
  • usw.
  1. Struktur des Problems (der Aufgabe) beschreiben:
    • Welche Struktur hat die Aufgabenstellung? also: Welche Variablen sind gegeben? Welchen Typ haben sie?
    • Welche Struktur haben Lösungen? Woran erkenne ich eine richtige Lösung? Woran erkenne ich eine falsche Lösung?
    • Beispiele konstruieren: Eingabe → Lösung; hilft dem Verständnis und kann später benutzt werden, um das Programm zu testen.
  2. Strategie (Algorithmus) zum Finden einer Lösung überlegen: Zerlegen in bekannte Teilprobleme, schrittweise Reduktion auf einfachere Probleme, systematisches Suchen, Fixpunkt berechnen, Literatur-Recherche
  3. Programm schreiben: die Strategie in Anweisungen der Programmiersprache übersetzen; braucht eigentlich nur Übung
  4. Testen: Findet mein Programm wirklich richtige Lösungen?

Probleme zerlegen

Probleme reduzieren

Fixpunkte: Daten sammeln bis Lösung dabei

Notizen

Def. Eine Gleichung ist ein Ausdruck der Form <Term> "=" <Term>, wobei <Term> beliebige Ausdrücke sein können, die man zu einem Wert auswerten kann. Wichtig ist das "=" Gleichheitszeichen, welches den Ausdruck in eine linke und rechte Seite trennt.

Bsp. , . .

Def. Eine Gleichung ist erfüllt, wenn sie keine Variablen enthält und der Ergebnis-Wert der linken Seite gleich dem Ergebnis-Wert der rechten Seite ist. Ansonsten ist sie nicht erfüllt.

Bsp. ist nicht erfüllt. ist erfüllt.

Def. Ein Gleichungssystem ist eine Kombination aus ein oder mehreren Gleichungen.

Def. Eine Lösung eines Gleichungssystems ist eine Belegung der Variablen mit Werten, so dass alle Gleichungen des Systems dadurch gleichzeitig erfüllt werden. Ein Gleichungssystem wird lösbar genannt (oder "erfüllbar"), wenn mindestens eine Lösung existiert. Ein Gleichungssystem wird eindeutig lösbar genannt, wenn genau eine Lösung existiert.

Bsp. Eine Lösung von ist . Sie ist also lösbar. Sie ist aber nicht eindeutig lösbar, weil auch eine Lösung ist.

Bsp. FIXME Differenzialgleichungssystem, Lösungen sind dann nicht Werte sondern Funktionen!

Eine typische Aufgabe mit Gleichungssystemen ist, sie zu lösen (als Tätigkeit), also nach einer oder allen Lösungen zu suchen. Die einfachste und langsamste Strategie dafür wäre, alle möglichen Variablenbelegungen systematisch auszuprobieren. Dies nennt man "brute force" bzw. auf deutsch "brutale Suche". Es ist schnell einzusehen, dass dies keine praktisch verwendbare Strategie ist um Gleichungssysteme zu lösen, weil viel zu viele Variablenbelegungen existieren, die alle ausprobiert werden müssten. Es müssen also andere, schnellere Strategien entwickelt werden. Dies ist Aufgabe der Mathematik (und manchmal auch der Informatik).

Def. Ein lineares Gleichungssystem ist ein Gleichungssystem, in dem keine Produkte von Variablen auftreten, sondern nur Summen über "Konstante * Variable".

Bsp. . Anmerkung: man kann lineare Gleichungssysteme in eine Normalform bringen, wobei eine Matrix, der Vektor der Variablen und ein Vektor aus Werten ist.

Def. Zwei Gleichungssysteme sind äquivalent, wenn sie genau die selben Lösungen besitzen.

Bessere Strategie zum Lösen: Forme das Gleichungssystem in "leichtere", äquivalente Gleichungssysteme um, bis es so leicht ist, dass die Lösung(en) offensichtlich sind. Das ist "auf leichtere Probleme reduzieren". Für lineare Gleichungssysteme ergibt dies den bekannten "Gauss-Algorithmus": FIXME verbale Beschreibung.

zweites Beispiel: FIXME größter gemeinsamer Teiler und Äquivalenzen.

projekte/vorkurs-informatik/mathe-versus-informatik.txt · Zuletzt geändert: 08.07.2010 09:45 von btu_rottaran