Mathematische Grundlagen der Informatik  


Grundbegriffe, Logik, Kombinatorik + Algebra und Modulare Arithmetik + Analysis, Stochastik, Lineare Algebra.

 

Das  Buch

       Das frühere Skript ist langsam zu einem Buch aufgewachsen.
Hier ist die Ank�ndigung des Teubner-Verlags.

 

Testfragen

      

Zusatzmaterialien fuer die Zwischenpruefung  "Theoretische Informatik I + Math. Grundlagen der Informatik"
fuer  Studierenden des Informatik-Lehramts (L3):

 

 

Einige Links

 

Einige Beispiele

Aussagen (Bedeutung der logischen Implikation A ==> B):

                                  ``Wenn    1=0  ist, bin ich der Papst!''

Beweis: Aus   1=0   folgt   2=1. Da der Papst und ich   2  Personen sind,  sind wir  1  Person.
 

Graphen und Kombinatorik:

Sehen Sie, dass diese verschiedene Bilder letztendlich dasselbe mathematisches Objekt  (dieselbe binaere Relation) darstellen?

Es gibt eine Sandkiste, die als ein gleichseitiges Dreieck mit jeder Seite der Laenge 2 meter aussieht .In dieser Sandkiste wollen 5 Kinder speilen. Das Problem ist nur, dass die Kinder sollen um mehr als 1 metervon einander enfehrnt sein, da sonst werden sie kraeftig streiten. Ist es moeglich, die 5 Kinder in die Sandkiste so zu verteilen, dass da endlich Ruhe herrschen wird?
Antwort: Nein! 

Zahlentheorie:

Sie wollen eine sterng geheime Nachricht an Ihre Bank per E-Mail verschicken, so dass kein Unbefuegter sie vertehen kann.
Aber das E-Mail  ist fuer jeden Hacker lesbar.  Sie  sind im Ausland und koennen sich nicht mit dem Bankangestellte treffen,
um einen Verschluesselungs-Code zu vereinbaren.  Was nun? Ist es moeglich, eine  von der Bank in dem Zeitschrift veroeffentlichte
(und fuer jederman bekannte) Code zu benutzen, um eine Nachricht so zu kodieren, dass kein anderer  sie verstehen kann?

Ja, es ist moeglich.  Und zwar mit Hilfe des RSA-Verfahrens, der nur  einen einfachen Satz (den kleinen Satz von Fermat)
aus der modularen Zahlentheorie braucht!


Asymptotische Analyse:

Sie schliessen mit Ihrer Bank einen Ratensparvertrag ueber 10 Jahre und zu einem Zinsfuss von  6 % ab. Zu begin des ersten Jahres zahlen Sie einen Einmalbetrag von 1500,- Euro ein und anschliessend jeweils am Ende des Jahres eine Rate von 200,- Euro.
Welchen Wert hat das Kapital nach 10 Jahren?
Antwort: 5.322,- Euro. 
Das von Ihnen eingezahlte Kapital betraegt  nur 3.500,-. Der Rest stammt aus den Zinseszinsen!

Wie kann man das Wachstum von zwei Funktionen f(x) und g(x) vergleichen? Dazu hat sich die sogenannte "gross-O" und "klein-o" Notation von Bachmann und Landau als sehr hilfreich bewiesen. Sie werden spaeter diese Notationen sehr oft treffen!

Bachman-Landau Notation


Stochastik:

Das  "`Monty Hall Problem"':
In einer Game Show ist hinter einer von drei Tueren ein Hauptpreis (rein zufaellig) verborgen. Ein Zuschauer raet eine der drei Tueren und der Showmaster Monty Hall wird daraufhin eine weitere Tuer "offnen, hinter der sich aber kein Hauptpreis verbirgt.  Der Zuschauer erhaelt jetzt die Moeglichkeit, seine Wahl zu aendern. Sollte er dies tun?

Antwort: Der Zuschauer gewinnt mit Wahrscheinlichkeit 2/3, falls er die Tuer aendert, und nur mit  Wahrscheinlichkeit  1/3, falls er das nicht tut!

Das "Sekretaerinen Problem an der Boerse":
Wie waehlt man unter 10 Sekretaerinnen die beste aus, wenn waehrend des Bewerbungsgespraeches die Zusage erteilt werden soll?
Die Loesungsstrategie zum Sekretaerinnenproblem wird beim Aktienhandel angewandt, wenn der Kurs einer Aktie staendig schwankt und nicht
vorhersagbar ist. Wenn ich innerhalb von einem Monat entsprechende Aktien verkaufen moechte, wie kann ich mit dieser Strategie den
guenstigsten Verkaufstag finden?

Antwort: Wenn die Anzahl der Handelstage n gross ist, dann sollten die Aktienkurse der ersten  n/e (knapp  37%) Tage lediglich
notiert sein und dann die naechste bessere Gelegenheit ausgewaehlt werden. Die Wahrscheinlichkeit, dann den guenstigsten Verkaufstag zu
erwischen, betraegt    1/e=0,367 .  Beachte, dass das viel besser  ist als einfach einen Verkaufstag rein zufaellig mit Wahrscheinlichkeit  1/n  auszuwaehlen!
 


Lineare Algebra:

Eine kleine Stadt Namens ``Eventown'' hat n (erwachsene) Einwohner, deren einziges Hobby  ist, so wiel wie moeglich verschiedene Clubs (Vereine) zu bilden.  Da zu viele Clubs schwer zu koordinieren sind, hat das Rathaus eine Regelung herausgegeben:

    1.  Die Anzahl der Mitglieder in jedem Club muss  gerade sein
    2. Je zwei Clubs mussen auch  gerade Anzahl gemeisamer Mitglieder haben.

Wie viele Clubs koennen die Bewohner unter dieser Regelung bilden? Antwort: mindestens  2n/2  (jeder Mann nimmt auch seine Frau mit).   Viel zu viel fuer  so eine kleine Stadt!

Deshalb hat das Rathaus die Regelung  geringfuegig geaendert:  Anstatt  gerade in Regel 1 hat es das Wort  ungerade  geschrieben.
Unter dieser neuen Regelung koennten die Bewohner hoechstens  n  Clubs bilden!  Warum? Koennen Sie das zeigen?