WEBVTT

00:15.960 --> 00:19.300
Ich begrüße Sie zur Vorlesung Informatik 1.

00:19.960 --> 00:25.220
Wir sind stehen geblieben bei dem Begriff der statischen und

00:25.220 --> 00:26.200
dynamischen Bindung.

00:27.760 --> 00:32.640
Und ich habe Ihnen das auf einer nachfolgenden Folie ein bisschen

00:32.640 --> 00:35.220
näher gebracht, was denn hier der Unterschied ist.

00:35.280 --> 00:37.040
Das können wir nochmal zeigen.

00:38.000 --> 00:42.820
Nämlich der wesentliche Unterschied ist der, dass wir entweder von der

00:42.820 --> 00:49.560
Funktionsdefinition ausgehen, wenn wir sozusagen die nächstäußere

00:49.560 --> 00:53.840
Deklaration suchen, oder wir gehen von der Funktionsapplikation aus.

00:53.960 --> 00:59.360
Das sind zwei ganz unterschiedliche Vorgehensweisen, die also ganz

00:59.360 --> 01:05.300
grundsätzlich eben auch auf den Auswertungsalgorithmus, den der

01:05.300 --> 01:08.900
Compiler vorsieht, Rücksicht nehmen muss.

01:09.560 --> 01:10.320
Und was haben wir hier?

01:10.700 --> 01:14.060
Wenn wir uns das Beispiel anschauen, sollte jeder von Ihnen in der

01:14.060 --> 01:19.620
Lage sein, die Funktionsdefinition und die Funktionsapplikation hier

01:19.620 --> 01:20.480
rauszulesen.

01:21.760 --> 01:24.140
Und das sind folgende Stellen.

01:25.200 --> 01:30.040
Diese Stelle hier, wo wir das Frankischen F haben, das ist die

01:30.040 --> 01:33.260
Funktionsdefinition.

01:34.780 --> 01:36.320
Hier wird die Funktion definiert.

01:38.200 --> 01:43.700
Und hier, an dieser Stelle haben wir die Funktionsapplikation.

01:44.680 --> 01:48.540
Sie sehen also, Applikation heißt eigentlich nichts anderes als der

01:48.540 --> 01:50.880
Aufruf dieser Funktion.

01:53.080 --> 01:57.120
Und entsprechend, jetzt kann man das mal vielleicht mit einer anderen

01:57.120 --> 02:03.780
Farbe markieren, muss man sich jetzt an der Stelle überlegen, nimmt

02:03.780 --> 02:11.000
man diese Festlegung von dem X, diese Deklaration von dem X, oder

02:11.000 --> 02:18.840
nimmt man diese Deklaration von dem X, das wäre eben hier statisch.

02:22.060 --> 02:30.360
Und dieses wäre der dynamische Fall, nämlich entweder im dynamischen

02:30.360 --> 02:34.760
Fall die Funktionsapplikation, also Funktionsaufruf, oder eben im

02:34.760 --> 02:38.720
statischen Fall die Funktionsdeklaration, das ist eben genau diese

02:38.720 --> 02:39.220
Stelle hier.

02:40.240 --> 02:44.760
Warum heißt das jetzt statisch und das andere dynamisch, das kann man

02:44.760 --> 02:49.900
sich auch noch recht gut klar machen, weil wenn ich von der

02:49.900 --> 02:55.240
Funktionsdefinition ausgehe, dann gehe ich von der Aufschreibung aus.

02:55.760 --> 02:59.780
Dann habe ich genau dieses Vorgehen, dass ich mir sozusagen den

02:59.780 --> 03:04.780
Programmtext anschaue und in dem Programmtext an einer bestimmten

03:04.780 --> 03:11.180
Stelle die Funktionsdefinition vorgegeben und ich kann statisch

03:11.180 --> 03:14.880
sozusagen zurückgehen auf die nächstäußere Deklaration.

03:15.060 --> 03:21.560
Das kann ich also zur Übersetzungszeit festlegen.

03:22.040 --> 03:28.260
Das heißt, diese Heraussuchung der nächstäußeren Deklaration kann ich

03:28.260 --> 03:29.600
zur Übersetzungszeit machen.

03:31.740 --> 03:38.640
Da brauche ich ausschließlich den Programmtext.

03:40.240 --> 03:45.940
Jetzt könnte man sich vorstellen, dass die Funktionsapplikation auch

03:45.940 --> 03:47.240
im Programmtext auftritt.

03:47.320 --> 03:51.620
Man könnte sagen, ich kann ja dieses hier auch jetzt identifizieren

03:51.620 --> 03:54.860
und entsprechend suche ich da die nächstäußere Deklaration.

03:55.900 --> 03:58.500
Müssten Sie sich jetzt einfach mal vorstellen, dass Sie eben mehr als

03:58.500 --> 04:03.120
eine Funktionsapplikation, mehr als einen Funktionsaufruf haben, dann

04:03.120 --> 04:03.980
fällt Ihnen das schwer.

04:04.400 --> 04:08.300
Schon auch bei diesem Beispiel ist das also nicht mehr rein statisch

04:08.300 --> 04:08.720
zu machen.

04:09.020 --> 04:11.760
Aber Sie können sich also klar machen, dass das mit der statischen

04:11.760 --> 04:16.140
Aufschreibung nicht mehr ausreicht, wenn Sie mehrere Aufrufe haben.

04:16.960 --> 04:22.160
Und das führt eben dazu, dass man an der Stelle sozusagen das

04:22.160 --> 04:27.900
Laufzeitverhalten mit einbeziehen muss, um die nächstäußere

04:27.900 --> 04:29.060
Deklaration zu finden.

04:29.260 --> 04:35.180
Das heißt, diese Festlegung kann ich erst zur Laufzeit treffen.

04:36.580 --> 04:41.140
Ich kann auch sagen, das ist abhängig von dem konkreten Arbeiten des

04:41.140 --> 04:43.920
Algorithms, von den konkreten Eingabeparametern, die ich wähle.

04:44.760 --> 04:47.240
Das ist also nicht mehr zur Übersetzungszeit machbar.

04:47.240 --> 04:51.780
Und was letztendlich erreicht wird oder durchgeführt wird, ist

04:51.780 --> 04:54.020
folgendes, dass ich im Laufzeitkeller

04:57.040 --> 04:59.960
lege ich meine Daten ab, lege ich meine Deklarationen auch

04:59.960 --> 05:00.700
entsprechend ab.

05:01.540 --> 05:04.900
Und ich habe dann hier, wenn ich an dem Beispiel bleibe, irgendwo habe

05:04.900 --> 05:07.040
ich hier x und da habe ich 2 eingetragen.

05:07.160 --> 05:11.280
Das ist jetzt genau diese rote Deklaration hier.

05:11.880 --> 05:15.780
Und ich wähle zu einem bestimmten Zeitpunkt, wo ich jetzt eben sage,

05:15.860 --> 05:20.020
ich brauche das x, da wähle ich letztendlich im Laufzeitkeller, da

05:20.020 --> 05:23.300
marschiere ich hier nach oben und da wähle ich den ersten Eintrag von

05:23.300 --> 05:23.700
dem x.

05:24.220 --> 05:31.160
Das ist also das, wie ich diese dynamische Bindung durchführen kann.

05:32.680 --> 05:38.300
Die dynamische Bindung hat folgende Eigenschaft, also das lässt sich

05:38.300 --> 05:38.640
machen.

05:39.080 --> 05:44.760
Dynamisch binden ist von der rein mechanischen Seite und von dem, wie

05:44.760 --> 05:47.560
der Compiler zu arbeiten hat, überhaupt kein Problem.

05:47.760 --> 05:51.380
Ich habe sogar größere, weniger Schwierigkeiten, weil ich tatsächlich

05:51.380 --> 05:53.740
in den Laufzeitkeller hochgehe und schaue mir den ersten Eintrag von

05:53.740 --> 05:54.280
dem x an.

05:54.960 --> 06:04.260
Aber wir haben ein Problem, also ein Nachteil der dynamischen Bindung.

06:06.560 --> 06:09.440
Der sieht folgendermaßen aus.

06:10.960 --> 06:30.520
Die Analyse von Programmen wird extrem erschwert und das ist

06:30.520 --> 06:31.640
entscheidend.

06:31.780 --> 06:40.960
Zum Beispiel Korrektheitsbeweise können Sie eigentlich auf der Basis

06:40.960 --> 06:45.760
von dynamischen Bindungen vergessen, weil Sie einfach nicht auf der

06:45.760 --> 06:49.360
Basis des aufgeschriebenen Algorithmus vernünftig analysieren können,

06:49.440 --> 06:52.240
sondern Sie müssen sozusagen immer den ablaufen lassen.

06:53.240 --> 06:58.820
Und hat man sich früher eigentlich gedacht, das ist eine schöne Sache,

06:58.960 --> 07:03.300
da kann ich nämlich tolle Programmlösungen auch auf dieser Basis

07:03.300 --> 07:03.960
realisieren.

07:04.600 --> 07:09.820
Aber aufgrund dieses Nachteils ist man eigentlich heute dazu

07:09.820 --> 07:16.780
übergegangen, dass das allgemein als ungünstig angesehen wird.

07:19.120 --> 07:25.600
Und man versucht, dieser Art der Bindung nicht mehr im Rahmen eines

07:25.600 --> 07:26.960
Sprachkonzepts vorzusehen.

07:27.380 --> 07:30.520
Obwohl, wenn Sie also auch im Zusammenhang mit objektorientierter

07:30.520 --> 07:34.300
Programmierung sehen, gerade solche dynamische Bindungen an vielen

07:34.300 --> 07:43.560
Stellen von der Programmierlösung zu schönen, effizienten Konzepten

07:43.560 --> 07:43.860
führen.

07:44.300 --> 07:48.440
Aber diese Analyse hier ist doch auch erheblich, gerade wenn Sie

07:48.440 --> 07:51.400
Fehler in Ihrem Programm haben, wenn Sie wollen gewisse Tools

07:51.400 --> 07:54.100
anwenden, gewisse Konzepte, Korrektheitsbeweise anwenden und die

07:54.100 --> 07:58.080
greifen nicht, dann überlegen Sie sich das dann doch dreimal, ob Sie

07:58.080 --> 08:01.480
diese Art von Sprachkonzept wirklich unterstützen wollen.

08:08.380 --> 08:12.940
Kommen wir zu dem Abschnitt 4.5.

08:14.400 --> 08:18.760
Und jetzt beschäftigen wir uns mit präkorsiven Funktionsdeklarationen.

08:18.980 --> 08:21.780
Und was Sie jetzt in dem Abschnitt kennenlernen werden, das ist

08:21.780 --> 08:27.980
eigentlich, wenn Sie die Algorithmen und die Programme als Kern der

08:27.980 --> 08:31.680
Informatik ansehen, dann ist das jetzt der mathematische Kern der

08:31.680 --> 08:37.000
Informatik, nämlich wir beschäftigen uns jetzt damit, wie wir rekursiv

08:37.000 --> 08:41.800
definierte Funktionen semantisch packen können, wie wir denen eine

08:41.800 --> 08:43.580
vernünftige Semantik zuordnen können.

08:44.620 --> 08:49.700
Und wir haben das ja schon mit nichtrekursiven Funktionen gemacht und

08:49.700 --> 08:53.880
da hat uns das auch keine Probleme bereitet, da wissen wir, dass wir

08:53.880 --> 08:57.120
sozusagen einfach die rechte Seite expandieren oder die rechte Seite

08:57.120 --> 09:01.800
einsetzen und weil das eben eine nichtrekursive Funktion ist, kommt

09:01.800 --> 09:04.280
diese Funktion nicht mehr vor und dann ist das eigentlich eine

09:04.280 --> 09:07.540
Ersetzung des Rundfusses gegen den Funktionsaufwurf.

09:07.640 --> 09:10.200
Und da tun wir uns hier jetzt eben bei den rekursiven

09:10.200 --> 09:15.260
Funktionsdeklarationen beliebig schwer und da müssen wir irgendwie mit

09:15.260 --> 09:19.740
einer gewissen mathematischen Methode an diese Semantikbeschreibung

09:19.740 --> 09:23.000
rangehen und das führt zur induktiven Deutung beziehungsweise zur

09:23.000 --> 09:23.780
Fixpunkttheorie.

09:24.760 --> 09:27.900
So viel jetzt mal als Vorrede, jetzt wollen wir aber erstmal mit

09:27.900 --> 09:32.740
konkreten praktischen Beispielen von Funktionsdeklarationen beginnen.

09:34.000 --> 09:40.180
Erstmal noch zwei Beobachtungen, die auch schon an früherer Stelle

09:40.180 --> 09:42.020
durchgeführt worden sind.

09:42.680 --> 09:49.640
Wir stellen fest, dass wir bei nichtrekursiven, wenn wir rekursive

09:49.640 --> 09:56.180
Funktionen nicht zulassen, dass die Länge der Berechnungssequenzen

09:57.300 --> 09:58.440
statisch beschränkt sind.

09:59.620 --> 10:05.320
Also wir können da keine Zyklen reinbauen, wir ersetzen sozusagen

10:05.320 --> 10:09.840
immer die Rümpfe, setzen die ein und irgendwann mal sind wir bei der

10:09.840 --> 10:13.140
algorithmischen Basis angekommen und das ist dann für uns die

10:13.140 --> 10:16.460
Normalform und dann ist die Berechnungssequenz beendet.

10:16.460 --> 10:22.520
Also da haben wir schon mal gute Karten, kann eigentlich nicht viel

10:22.520 --> 10:27.480
passieren bei nichtrekursiven Funktionen, was jetzt diese unendlichen

10:27.480 --> 10:28.880
Berechnungssequenzen angeht.

10:29.720 --> 10:34.060
Jetzt müssen wir uns nochmal bezüglich Terminierung an der Stelle

10:34.060 --> 10:36.460
Gedanken machen.

10:38.060 --> 10:43.040
Terminierung ist hier das Fragezeichen, eigentlich kann man sagen, das

10:43.040 --> 10:46.740
terminiert dann auch, wir haben nur endliche Berechnungssequenzen.

10:48.160 --> 10:52.060
Sie müssen immer beachten, das bringen manche immer wieder

10:52.060 --> 10:52.660
durcheinander.

10:53.260 --> 10:56.720
Auf der einen Seite haben wir diese Endlichkeit der Aufschreibung des

10:56.720 --> 10:59.160
Algorithmus, das ist die eine Seite.

10:59.560 --> 11:02.180
Jeder Algorithmus ist endlich in der Aufschreibung, auch rekursive

11:02.180 --> 11:04.240
Algorithmen sind natürlich endlich in der Aufschreibung.

11:04.620 --> 11:07.640
Wo wir jetzt aber darüber reden ist sozusagen der Ausführungsaspekt.

11:07.760 --> 11:10.820
Die Berechnungssequenz ist der Ausführungsaspekt und hier haben wir

11:10.820 --> 11:15.080
tatsächlich die Eigenschaft, wenn wir auf rekursive Funktionen

11:15.080 --> 11:19.440
verzichten, dass auch die Berechnungssequenz, auch die Ausführung

11:19.440 --> 11:20.620
endlich ist.

11:21.000 --> 11:23.840
Und damit kommen wir eigentlich genau in die Richtung der

11:23.840 --> 11:24.540
Terminierung.

11:25.420 --> 11:27.820
Statisch beschränkt kommen wir irgendwo in Richtung Terminierung.

11:28.380 --> 11:33.920
Das können wir gleichsetzen unter folgender Bedingung und von der

11:33.920 --> 11:34.740
gehen wir immer aus.

11:34.740 --> 11:41.860
Die Bedingung lautet hier, dass die algorithmische Basis, dass die

11:41.860 --> 11:46.260
Operationen der algorithmischen Basis auch stets terminieren.

11:46.520 --> 11:51.180
Wenn das gegeben ist, dann können wir hier schließen, aufgrund der

11:51.180 --> 11:54.560
statisch begrenzten Berechnungssequenz haben wir auch kein Problem mit

11:54.560 --> 11:55.180
der Terminierung.

11:55.320 --> 11:57.880
Also da kann nun aber schief gehen, wenn wir sozusagen in der

11:57.880 --> 12:01.600
algorithmischen Basis nicht terminierende Operationen zulassen.

12:02.980 --> 12:05.940
Das ist gar nicht so ganz abwegig, nämlich denken Sie zum Beispiel an

12:05.940 --> 12:07.000
die Division durch Null.

12:07.720 --> 12:08.540
Was machen Sie da?

12:08.960 --> 12:10.920
Das führt zu einem undefinierten Ergebnis.

12:11.220 --> 12:14.240
Also hier ist schon noch ein bisschen ein Weg gegeben mit der

12:14.240 --> 12:17.260
algorithmischen Basis, dass wir dann auch tatsächlich die Terminierung

12:17.260 --> 12:20.740
des gesamten Programmes zusichern können.

12:20.840 --> 12:24.640
Aber im Grundsatz haben wir uns da ganz viele Probleme mit vom Hals

12:24.640 --> 12:25.040
geschaffen.

12:26.140 --> 12:32.260
Wenn wir jetzt die rekursiven Deklarationen von Funktionen zulassen,

12:34.280 --> 12:37.520
dann ergeben sich ganz neue Fragestellungen, nämlich dann ergibt sich

12:37.520 --> 12:42.200
die Frage, besteht hier jetzt die Möglichkeit, dass wir zur Nicht

12:42.200 --> 12:45.240
-Terminierung kommen, dass wir sozusagen aus diesem Zyklus des immer

12:45.240 --> 12:49.240
wieder sich Aufrufens von der gleichen Funktion, dass wir da nie

12:49.240 --> 12:49.760
rauskommen.

12:50.240 --> 12:52.580
Da kommt genau diese Terminierung ins Spiel.

12:52.580 --> 13:00.180
Und das ist also eine ganz zentrale Fragestellung, sich mit dieser

13:00.180 --> 13:03.960
Problematik vernünftig und mathematisch fundiert auseinanderzusetzen.

13:04.060 --> 13:10.900
Deswegen werden wir eben diesen Ansatz hier miteinander bearbeiten und

13:10.900 --> 13:13.220
auch am Beispiel in der zentralen Übung heute vertiefen.

13:14.280 --> 13:20.100
Schauen wir uns mal einfache erste rekursive Funktionen an.

13:20.100 --> 13:23.040
Wir haben also jetzt hier die Addition.

13:24.340 --> 13:27.680
Sie sehen, dass das eben eine rekursive Funktion ist, dadurch, dass

13:27.680 --> 13:29.540
wir hier nochmal die Addition aufrufen.

13:31.260 --> 13:37.420
Solche Art von einfachen Algorithmen werden wir von Ihnen abverlangen.

13:37.680 --> 13:41.820
Sie sollen also in der Lage sein, solche Art von Algorithmen

13:41.820 --> 13:43.380
hinschreiben zu können.

13:43.380 --> 13:48.440
Und auch die folgenden, die ich Ihnen jetzt angebe, die sollten Ihnen

13:48.440 --> 13:54.460
durchaus Teil eines prüfungsrelevanten Inhaltes sein.

13:55.020 --> 13:56.260
So etwas müssen Sie hinschreiben können.

13:56.400 --> 14:00.200
Wenn wir eine Klausuraufgabe haben, beschreiben Sie die

14:00.200 --> 14:02.460
Additionsfunktion rekursiv.

14:02.800 --> 14:05.560
Dann verlangen wir genau diese Art von Lösung.

14:06.500 --> 14:10.180
Das sollten Sie sich also durchaus intensiv mit dem auseinandersetzen,

14:10.280 --> 14:12.520
mit diesen einfachen, sehr einfachen Algorithmen.

14:12.520 --> 14:16.240
Und ich gebe Ihnen da nochmal den Hinweis, viele von Ihnen sagen, das

14:16.240 --> 14:20.580
ist überhaupt kein Problem, das kann ich ja schon von der Schule her.

14:22.080 --> 14:28.280
Ich habe festgestellt, insbesondere in mündlichen Prüfungen, es gab

14:28.280 --> 14:32.440
tatsächlich Leute, die hier drin sitzen in der Informatik 1 Vorlesung

14:32.440 --> 14:34.500
und keinen Algorithmus hinschreiben können.

14:35.500 --> 14:38.560
Das kann nicht sein, das ist die Grundlage, die Basis, dass Sie

14:38.560 --> 14:39.880
komplexere Sachen machen können.

14:39.880 --> 14:43.360
Also nehmen Sie das wirklich ernst, machen Sie mal für sich den Test

14:43.360 --> 14:46.940
und geben Sie sich zum Beispiel mal eine Aufgabe vor, ich schreibe

14:46.940 --> 14:50.800
jetzt einen Algorithmus rekursiv hin, was weiß ich, für das kleinste

14:50.800 --> 14:51.780
gemeinsame Vielfache.

14:52.240 --> 14:55.540
Überlegen Sie sich, wie Sie das aufbauen, beschreiben Sie es wirklich

14:55.540 --> 14:58.580
mal hin, mit der ganzen Syntax, die Sie brauchen, mit den ganzen

14:58.580 --> 15:01.800
Klammern, mit den Parametern, mit dem rekursiven Aufruf.

15:02.260 --> 15:05.120
Und das ist eine gute Übung, die Sie nicht nur für die Klausur sich

15:05.120 --> 15:08.640
stellen sollten, sondern die Sie wirklich brauchen für Ihr weiteres

15:08.640 --> 15:08.820
Tun.

15:08.820 --> 15:11.780
Das muss Ihnen von der Hand gehen, ohne Probleme.

15:12.480 --> 15:15.560
So, wir gucken uns mal diese Addition hier an.

15:16.060 --> 15:19.580
An der Stelle möchte ich auf eine Sache noch mal rauskommen, die

15:19.580 --> 15:23.340
nämlich sehr wichtig ist, was jetzt Analyse von rekursiven Funktionen

15:23.340 --> 15:23.780
angeht.

15:24.500 --> 15:30.320
Nämlich, wenn wir uns beispielsweise so einen Aufruf überlegen,

15:32.260 --> 15:37.940
Addition Add 3, 2, dann können Sie da die rechte Seite einsetzen, dann

15:37.940 --> 15:41.660
können Sie entsprechend hier zumindest den Predecessor ausrechnen, der

15:41.660 --> 15:42.320
hier folgt.

15:43.020 --> 15:46.200
Nämlich, Predecessor von 3 wäre das ja dann entsprechend.

15:46.680 --> 15:52.140
Und Sie kommen dann auf so ein Konstrukt, das folgendermaßen aussieht,

15:52.200 --> 15:55.680
oder auf eine Operationenfolge, die folgendermaßen aussieht.

15:55.800 --> 16:01.280
Successor von Addition von 2, 2.

16:02.340 --> 16:04.060
Und das geht dann weiter.

16:04.860 --> 16:10.340
Und Sie kommen dann erst an einen bestimmten Punkt, wo sich das Ganze

16:10.340 --> 16:11.060
auflöst.

16:11.800 --> 16:18.480
Nämlich, wenn Sie dreimal hintereinander den Successor hier aufrufen,

16:18.880 --> 16:20.280
wo der Aufruf da steht.

16:20.820 --> 16:25.960
Und dann kommen Sie eben zu einer Addition von 0, 2.

16:26.800 --> 16:29.000
Und dann geht es eigentlich erst mit der Auflösung weiter.

16:29.520 --> 16:31.740
Nämlich, dann kommen Sie erst in den Sendfall.

16:31.740 --> 16:36.820
Nämlich, so lange kommen Sie in den rekursiven Elsefall, bis Sie

16:36.820 --> 16:38.960
sozusagen bei der 0 angekommen sind.

16:39.320 --> 16:43.280
Und dann können Sie entsprechend jetzt hier diese Successors

16:43.280 --> 16:44.800
ausrechnen.

16:45.500 --> 16:58.300
Und diese Art von noch nicht bearbeitbaren Operationen, das nennt man

16:58.300 --> 17:02.960
sogenannte nachklappernde Operation oder ein Nachklappern.

17:06.560 --> 17:11.820
Und das ist ziemlich wichtig, um zu verstehen, wie der Algorithmus,

17:13.120 --> 17:16.840
wenn man Effizienzbetrachtungen anstellt, wie der Algorithmus dann

17:16.840 --> 17:21.400
sozusagen auch im Sinne des Laufzeitverhaltens und im Sinne der

17:21.400 --> 17:23.660
Aufstellung des Laufzeitkellers sich verhält.

17:24.740 --> 17:31.240
Das ist höchst ärgerlich, diese Art von Operation, die Sie sozusagen

17:31.240 --> 17:34.480
auf den Keller legen müssen und wo Sie warten müssen, bis Sie an einer

17:34.480 --> 17:36.040
bestimmten Stelle das auflösen können.

17:36.160 --> 17:39.920
Und dann müssen Sie sozusagen, diese Successor-Operation können Sie

17:39.920 --> 17:40.700
erst hier ausführen.

17:40.840 --> 17:43.920
Nämlich, was Sie letztendlich haben, um nochmal den Keller-Gedanken

17:43.920 --> 17:45.920
hier zu verdeutlichen.

17:46.300 --> 17:51.780
Sie legen einen Successor nach dem anderen auf den Laufzeitkeller

17:51.780 --> 17:52.240
drauf.

17:53.400 --> 17:56.980
Sie gehen also von oben nach unten, wächst der jetzt, dieser Keller.

17:57.980 --> 18:01.280
Und endlich an der Stelle, und da würden Sie beliebig weitermachen,

18:01.380 --> 18:06.560
wenn Sie jetzt eine Art von, was weiß ich, 100 aufrufen würden und

18:06.560 --> 18:07.460
irgendwas anderes.

18:08.160 --> 18:13.820
Dann müssten Sie 100 Mal erst mal diese Operation, also diesen ELF

18:13.820 --> 18:14.380
-Fall ausführen.

18:14.520 --> 18:17.440
Sie würden 100 Mal diesen Successor hier auf den Laufzeitkeller

18:17.440 --> 18:17.860
bekommen.

18:17.860 --> 18:21.140
Und erst auf einer bestimmten Stelle, nämlich wenn Sie in einem SEND

18:21.140 --> 18:25.160
-Fall sind, wenn Sie ab 0 von irgendwas ausrechnen, können Sie

18:25.160 --> 18:29.060
anfangen hier wieder zurückzugehen und sich diese Successors

18:29.060 --> 18:30.020
vorzunehmen.

18:31.040 --> 18:34.040
Nachklappende Operationen haben also den großen Nachteil, dass das

18:34.040 --> 18:38.340
Ganze höchst, ja, in Anführungsstellen ineffizient wird.

18:38.880 --> 18:41.420
Dass Sie diesen Keller belasten, dass Sie da immer was draufschreiben

18:41.420 --> 18:46.480
müssen, dass Sie eigentlich diese Auflösung von diesen Operationen gar

18:46.480 --> 18:48.540
nicht unmittelbar lokal machen können.

18:48.880 --> 18:53.120
Das ist also mal nur ein Aspekt, der jetzt hier reinkommt, der eben

18:53.120 --> 18:57.080
durch dieses sozusagen vorne stehende Successor-Operationen gegeben

18:57.080 --> 19:01.600
ist und erst dann verarbeitet werden kann, wenn Sie dieses bei dem

19:01.600 --> 19:02.520
SEND -Fall angekommen ist.

19:02.600 --> 19:04.360
Ganz anders ist es mit dem Predecessor hier.

19:05.420 --> 19:07.120
Der hat eine sehr schöne Eigenschaft.

19:07.120 --> 19:11.220
Den kann ich nämlich unmittelbar ausrechnen.

19:11.740 --> 19:15.560
Da muss ich nicht warten, bis ich sozusagen zu einem Terminierungsfall

19:15.560 --> 19:19.400
oder zu einem Nicht-Rekursionsfall von dieser Additionsfunktion

19:19.400 --> 19:19.980
gekommen bin.

19:21.200 --> 19:26.020
Und da werden wir also auch noch eine Technik feststellen, mit der wir

19:26.020 --> 19:32.220
in gewissen Fällen zumindest es erreichen oder versuchen, sozusagen

19:32.220 --> 19:36.380
diesen Nachklappern der Operation irgendwie in die Parameter mit

19:36.380 --> 19:37.000
reinzubringen.

19:37.140 --> 19:40.000
Nämlich immer, wenn Sie auf den Parametern das ausführen können, so

19:40.000 --> 19:42.720
wie bei dem Predecessor, dann haben Sie gute Karten, dann haben Sie

19:42.720 --> 19:44.880
auch einen effizienten rekursiven Algorithmus.

19:45.000 --> 19:50.260
Also das ist eine unschöne Konstellation, lässt sich aber an vielen

19:50.260 --> 19:53.040
Stellen, also für viele Probleme lässt sich diese Art der Rekursion

19:53.040 --> 19:53.700
nicht vermeiden.

19:53.700 --> 19:55.940
Wir werden auch feststellen, dass wir eben...

19:55.940 --> 19:59.600
Das heißt, im Klartext oder zwischen den Zeilen können Sie jetzt

19:59.600 --> 20:04.560
lesen, es gibt also Probleme, die Sie immer nur mit nachklappenden

20:04.560 --> 20:05.780
Operationen lösen können.

20:06.100 --> 20:09.520
Das ist also auch eine Erkenntnis, die Sie im Rahmen von

20:09.520 --> 20:13.040
Algorithmetheorie sich erarbeiten können.

20:13.860 --> 20:17.830
Gehen wir nochmal zu weiteren rekursiven Funktionen.

20:18.360 --> 20:22.100
Sie können auf der Addition jetzt beispielsweise die Multiplikation

20:22.100 --> 20:22.660
aufbauen.

20:24.060 --> 20:29.560
Dass das jetzt was Effizienzfragen angeht nicht unbedingt der Weisheit

20:29.560 --> 20:32.840
letzter Schlüsse ist, ist klar, aber Sie sehen an dem Beispiel dieser

20:32.840 --> 20:38.160
einfachen arithmetischen Operation, dass Sie sozusagen schrittweise zu

20:38.160 --> 20:40.080
komplexeren Operationen kommen können.

20:40.560 --> 20:46.500
Sie sehen hier, dass Sie also diese Addition an der Stelle nutzen.

20:47.500 --> 20:52.260
Und hier ist nochmal der rekursive Aufruf, die Multiplikation, das

20:52.260 --> 20:55.220
Mult, das Sie hier eben auch einsetzen.

20:55.800 --> 20:59.020
Schauen Sie sich mal die Analyse an, wieder an einem Beispiel.

20:59.680 --> 21:08.640
Wenn wir jetzt hier einen Aufruf haben, Mult von 3,2, wieder die

21:08.640 --> 21:13.040
gleichen Parameter, dann stellen Sie fest, dass Sie eben hier, wenn

21:13.040 --> 21:20.100
Sie das weiter entwickeln, dass Sie eben zu einem solchen Ausdruck

21:20.100 --> 21:20.400
kommen.

21:20.920 --> 21:31.460
Addition von 2, Addition 2, Ab 2, 0 und eine ganze Menge

21:31.460 --> 21:33.300
anschließenden Klammern.

21:35.440 --> 21:41.900
Und was Sie jetzt hier also sehen, also was man informell hinschreiben

21:41.900 --> 21:49.600
kann, die Multiplikation wird auf die Addition zurückgeführt, indem

21:49.600 --> 21:54.240
man jetzt hier sagt, wenn ich 3 mal 2 ausrechne, eine dreimalige

21:54.240 --> 21:55.940
Addition von 2.

21:56.940 --> 22:02.300
Das ist genau das, was hier dieser Ausdruck angibt.

22:02.980 --> 22:07.840
Dreimal wird hier diese Addition mit der 2 auf die ersten

22:07.840 --> 22:13.940
Parameterstelle angewendet und das Ergebnis wird hier in dieser

22:13.940 --> 22:17.140
Ergebnissorte abgeliefert.

22:17.640 --> 22:22.900
Also hier können Sie daran erkennen, dass man eben sozusagen rekursive

22:22.900 --> 22:24.340
Hierarchien aufbauen kann.

22:24.340 --> 22:31.420
Jede dieser Additionen führt ja wieder zu den bekannten rekursiven

22:31.420 --> 22:33.180
Aufrufe auf der Additionsebene.

22:33.840 --> 22:35.800
Und entsprechend können Sie sich dann jetzt auch zum Beispiel mal

22:35.800 --> 22:43.220
überlegen, wenn Sie jetzt hier dieses 0, 3, 2 sich anschauen, da

22:43.220 --> 22:50.120
können Sie sich zum Beispiel als Frage stellen, wie viele rekursive

22:50.120 --> 22:56.660
Aufrufe Das könnte eben auch so eine Analyse sein, da müssen Sie sich

22:56.660 --> 23:00.540
überlegen, Multiplikation, Addition müssen Sie trennen, Successor ist

23:00.540 --> 23:01.980
ja dann kein rekursiver Aufruf mehr.

23:02.040 --> 23:08.980
Das könnte eben auch so eine Analysefrage sein, die Sie durchaus lösen

23:08.980 --> 23:12.680
können müssen, wo Sie also entsprechend sich systematisch an diese

23:12.680 --> 23:13.520
Sache herangehen müssen.

23:14.200 --> 23:18.460
Jetzt haben wir noch ein weiteres Beispiel, bei der Multiplikation

23:18.460 --> 23:22.200
haben wir diesen Aspekt, ich kann auch schon bestehende rekursive

23:22.200 --> 23:26.340
Funktionen aufsetzen, kann etwas noch Komplexeres draufsetzen.

23:27.040 --> 23:31.640
Und bei der Division mit Rest oder der ganzzahligen Division sagen wir

23:31.640 --> 23:31.940
auch.

23:38.640 --> 23:45.540
Da kommen wir jetzt zu einem weiteren Aspekt, der bei rekursiven

23:45.540 --> 23:49.900
Funktionen auftritt, nämlich hier dieser Teil, der ist jetzt in dem

23:49.900 --> 23:54.020
Kopf, kann ich eine Ergänzung durchführen, in der Form, dass ich sage,

23:54.280 --> 23:57.660
aber hier dürfen nicht beliebige Parameterpositionen oder

23:57.660 --> 24:00.260
Parameterwerte eingetragen werden.

24:00.760 --> 24:05.760
Und an der Stelle ist eben der Nenner, der soll doch an der hier bitte

24:05.760 --> 24:11.020
größer 0 immer sein, insbesondere ungleich 0 an der Stelle und das

24:11.020 --> 24:13.940
kann man sich sehr schnell eben an dem Beispiel überlegen.

24:13.940 --> 24:19.800
Das heißt nämlich, wenn ich jetzt an der Stelle einsetzen würde Diff x

24:19.800 --> 24:26.500
,0, das führt, ich muss jetzt die rechte Seite einsetzen, Diff x

24:26.500 --> 24:41.380
kleiner 0 sein 0, als Diff x minus 0,0 und das ist ja nichts anderes

24:41.380 --> 24:47.820
als Diff x,0 plus 1 und jetzt sehen Sie,

24:52.180 --> 24:59.900
dass Sie hier ausgehend von dieser Funktion zum gleichen

24:59.900 --> 25:02.760
Funktionsaufruf gelangen.

25:03.580 --> 25:07.960
Und das zeigt, dass wir also unmittelbar, wenn Sie so eine

25:07.960 --> 25:10.480
Konstellation haben, nicht Terminierung.

25:10.480 --> 25:16.560
Und die wollen Sie an der Stelle verhindern.

25:17.160 --> 25:19.820
Und was Sie nochmal hier auch sehen ist, das habe ich an verschiedenen

25:19.820 --> 25:25.260
Stellen schon darauf hingewiesen, dass dieses Diff x,0 würde man

25:25.260 --> 25:31.980
mathematisch mit diesem Bottom-Symbol kennzeichnen.

25:32.100 --> 25:37.000
Das ist jetzt hier, das eine ist eher die funktionale Sicht und das

25:37.000 --> 25:38.540
hier ist die operationale Sicht.

25:38.540 --> 25:42.840
Also das hier wäre eher, dieses Bottom-Symbol wäre die funktionale

25:42.840 --> 25:46.560
Sicht, währenddessen das ist eben eher diese operationale Sicht.

25:47.440 --> 25:50.880
Die operational, wenn wir zu nicht Terminierung kommen, heißt das

25:50.880 --> 25:54.600
funktional, ich setze hier das Bottom-Element drauf.

25:54.900 --> 25:58.100
Also das heißt eigentlich immer, wenn ich hier Bottom angebe, das

25:58.100 --> 26:01.960
terminiert nicht operational, liefert zu keinem definierten Ergebnis.

26:04.420 --> 26:10.940
Also das ist hier, an der Stelle setzen wir das ein und das nennen wir

26:10.940 --> 26:13.660
dann eben eine Zusicherung auch.

26:14.560 --> 26:19.920
Eine Zusicherung, die wir hier machen, der englische Begriff ist

26:19.920 --> 26:20.620
Assertion.

26:21.540 --> 26:31.060
Eine Assertion Zusicherung, das heißt wir führen eine Restriktion der

26:31.060 --> 26:36.200
Parameterwerte durch, um solche Nicht-Terminierungen zu verhindern,

26:36.400 --> 26:38.480
weil das eben keinen Sinn macht.

26:38.780 --> 26:45.380
So, das Gegenstück zu der ganzteiligen Division ist eben der Rest, den

26:45.380 --> 26:47.500
wir hier angeben, den wir hier berechnen können.

26:47.500 --> 26:53.340
Das ist also ein ganz ähnliches Schema wie die ganzteilige Division.

26:55.440 --> 26:58.780
Das werden wir gleich auch nochmal als Beispiel verwenden, wenn wir

26:58.780 --> 27:04.060
uns eben überlegen, was die Semantik von so einer rekursiven Funktion

27:04.060 --> 27:04.400
ist.

27:06.020 --> 27:17.220
Die Idee ist klar, ich ziehe immer das m von dem n ab, solange bis das

27:17.220 --> 27:19.980
m in das n gar nicht mehr reinpasst und dann habe ich das m, das ist

27:19.980 --> 27:20.780
dann genau der Rest.

27:23.020 --> 27:30.560
Das letzte Beispiel einer rekursiven Funktion geht jetzt mal von den

27:30.560 --> 27:32.340
arithmetischen Operationen ab.

27:32.940 --> 27:39.840
Wir haben hier also immer die Addition, Subtraktion und Multiplikation

27:39.840 --> 27:41.460
und dergleichen an Operationen.

27:41.460 --> 27:46.980
Sie können sich aber auch eine andere algorithmische Basis vorstellen,

27:47.440 --> 27:49.460
die Sie hier als Grundlage nehmen.

27:49.580 --> 27:54.520
Und das wäre jetzt an der Stelle eine Operation für Bearbeiten von

27:54.520 --> 27:55.600
Sequenzen.

27:56.260 --> 28:00.580
Und Sie sehen jetzt hier, dass Sie also sozusagen müssen sich

28:00.580 --> 28:02.600
überlegen, was ist die algorithmische Basis.

28:04.020 --> 28:11.540
Die algorithmische Basis von diesem Algorithmus, und das ist einmal

28:11.540 --> 28:21.800
ein Gleichheitsoperator, der jetzt aber eben auf Sequenzen arbeitet,

28:22.580 --> 28:23.680
das ist jetzt dieser hier.

28:25.820 --> 28:30.220
Den wissen Sie, der ist anders definiert als der Gleichheitsoperator

28:30.220 --> 28:34.120
auf irgendwelchen natürlichen, ganzen oder reellen Zahlen.

28:35.220 --> 28:45.040
Und Sie haben hier noch einen zweiten, das ist hier der Rest einer

28:45.040 --> 28:45.680
Sequenz.

28:49.080 --> 28:53.140
Sie können sich jetzt entweder vorstellen, dass der Rest der Sequenz

28:53.140 --> 28:55.880
tatsächlich zur algorithmischen Basis gehört.

28:56.160 --> 28:59.780
Wenn er nicht zur algorithmischen Basis gehören würde, dann würden Sie

28:59.780 --> 29:05.100
entsprechend hier eine Funktion schreiben können, die Ihnen diesen

29:05.100 --> 29:05.720
Rest berechnet.

29:06.940 --> 29:14.000
Das ist nichts anderes, als wenn ich eben das als eine Sequenz ansehe.

29:14.000 --> 29:18.760
Die tun wir in eckigen Klammern schreiben, x1, x2, x3.

29:19.380 --> 29:23.720
Dann würde eben genau das erste Element weggenommen und es würde der

29:23.720 --> 29:27.920
Rest als Sequenz ausgegeben.

29:28.340 --> 29:32.560
Also auch das wäre wieder so eine Übung, dass Sie den Rest einfach mal

29:32.560 --> 29:35.600
als Algorithmus hinschreiben, als Funktion hinschreiben.

29:36.220 --> 29:39.940
Das wäre eine Übung, die Sie sich selber mal geben könnten.

29:39.940 --> 29:44.600
Und hier wird auf diese Funktion aufgesetzt.

29:45.380 --> 29:49.280
Die Funktionsweise oder die Arbeitsweise von diesem Algorithmus ist

29:49.280 --> 29:49.780
auch klar.

29:50.420 --> 29:57.860
Ich nehme immer das erste Element weg und ergänze stattdessen hier im

29:57.860 --> 29:58.800
Ergebnis eine 1.

29:58.880 --> 30:04.080
Ich zähle sozusagen nacheinander durch und gebe dann das Ergebnis hier

30:04.080 --> 30:05.100
zurück.

30:05.100 --> 30:10.980
Sobald ich alles abgearbeitet habe, wird eben 0 an der Stelle jetzt

30:10.980 --> 30:11.420
addiert.

30:11.640 --> 30:14.840
Es wird also nicht 0 zurückgegeben, sondern ich sammle ja sozusagen

30:14.840 --> 30:22.480
das Ergebnis in der Sorte, die ich zurückgebe, in meinem

30:22.480 --> 30:23.400
Funktionsergebnis.

30:23.680 --> 30:26.160
Das ist auch sowas, was Sie sich einfach nochmal genauer angucken

30:26.160 --> 30:30.640
sollten bei rekursiven Funktionen, wie hier dieses Ergebnis

30:30.640 --> 30:31.680
weitergegeben wird.

30:31.680 --> 30:37.360
Nämlich durch diese Addition, die geht nicht verloren, sondern die

30:37.360 --> 30:40.420
wird sozusagen im Funktionsergebnis weitergegeben.

30:40.960 --> 30:45.040
Solche einfachen Mechanismen können Sie sich anhand dieser Beispiele

30:45.040 --> 30:48.000
erlernen.

30:48.880 --> 30:52.660
Das waren jetzt ein paar einfache Beispiele.

30:52.660 --> 31:00.540
Diese Beispiele können Sie auch als Übung, als Java-Programm oder als

31:00.540 --> 31:02.040
Gopher -Programm mal hinschreiben.

31:02.420 --> 31:05.260
Das hilft ja auch mit den Programmiersprachen ein bisschen, sich

31:05.260 --> 31:06.400
nochmal vertraut machen.

31:06.480 --> 31:10.340
Das sind also alles so Übungen, die in dem Zusammenhang für Sie

31:10.340 --> 31:11.320
relevant sein könnten.

31:11.900 --> 31:19.360
Jetzt kommen wir zu der mathematischen Sichtweise wieder auf diese

31:19.360 --> 31:23.740
rekursiven Funktionsvereinbarungen, nämlich die semantische Deutung.

31:25.040 --> 31:28.960
Was steht jetzt auf der Folie drauf?

31:29.560 --> 31:34.000
Als Quintessenz mal vorweggenommen mit dem Verfahren, wie wir es

31:34.000 --> 31:35.600
bisher gemacht haben.

31:35.600 --> 31:39.900
In dem letzten Abschnitt, da kommen wir nicht weiter.

31:42.260 --> 31:46.760
Das führt zu einem Zyklus, das ist eben nicht die Lösung.

31:48.800 --> 31:53.540
Und wir haben schon festgestellt, allein durch diese Beispiele mit der

31:53.540 --> 31:59.520
Division, wir können also, wenn es dumm läuft, unbeschränkt lange

31:59.520 --> 32:02.920
Berechnungen produzieren.

32:04.140 --> 32:07.840
Jetzt könnte man sich vorstellen, das möchte man nicht.

32:07.920 --> 32:12.400
Da möchte man sozusagen einen Bogen drum machen und die rekursiven

32:12.400 --> 32:13.420
Funktionen verbannen.

32:14.040 --> 32:15.100
Das funktioniert aber nicht.

32:15.160 --> 32:20.040
Die sind also ein ganz elementarer Bestandteil von funktionaler

32:20.040 --> 32:23.420
Programmierung oder auch Programmierung im Allgemeinen.

32:24.000 --> 32:28.060
Und deswegen muss man sich eben mit diesen rekursiven Deklarationen

32:28.060 --> 32:30.040
und deren Interpretation auseinandersetzen.

32:30.040 --> 32:34.100
Man muss die Frage stellen und eine Lösung dazu finden.

32:34.900 --> 32:39.500
Und wie gesagt, die Lösung, die wir bisher hatten, sah ja so aus, dass

32:39.500 --> 32:46.720
wir so vorgegangen sind, dass wir hier so eine Funktion f1 eingeführt

32:46.720 --> 32:53.900
haben und die Belegung entsprechend so geändert haben, also diese

32:53.900 --> 32:58.720
Belegung so geändert haben, dass wir dieses f gegen das f1 ersetzt

32:58.720 --> 33:01.740
haben oder f1 für das f1 gesetzt haben.

33:02.320 --> 33:08.380
Aber die ganze Geschichte, die führt nicht sehr weit aus folgendem

33:08.380 --> 33:14.200
Grund, weil eben hier in diesem e, auf dieser rechten Seite, in dem

33:14.200 --> 33:20.280
Rumpf, kommt f wieder vor, f in e enthalten.

33:22.140 --> 33:29.140
Das ist ja genau die Eigenschaft einer rekursiven Funktion, das f ist

33:29.140 --> 33:29.960
in e enthalten.

33:32.120 --> 33:36.740
Und das führt jetzt zu dem Problem mit diesem Beta.

33:37.740 --> 33:55.360
Man benötigt in dem Beta eine Wertebelegung von f.

33:57.460 --> 34:03.940
Das heißt also, man hat das Problem sozusagen nur eins weiter

34:03.940 --> 34:07.720
geschaltet, man ist kein Schritt weiter mit dieser Art der

34:07.720 --> 34:08.600
Vorgehensweise.

34:09.520 --> 34:16.500
Man ist genauso weit mit dem f1, an dem Punkt wo man gestartet ist,

34:16.640 --> 34:18.900
man müsste jetzt einen f2 einführen, einen f3 einführen, einen f4

34:18.900 --> 34:23.220
einführen, es führt aber zu nichts, man kriegt also keinen Fortschritt

34:23.220 --> 34:25.200
in der Beantwortung dieser Frage.

34:25.840 --> 34:30.100
Das heißt, man muss ein bisschen anders vorgehen, um jetzt hier dieses

34:30.100 --> 34:32.360
Problem zu behandeln.

34:33.340 --> 34:37.660
Wie gesagt, wir werden also jetzt ein Verfahren angeben, das Sie auch

34:37.660 --> 34:41.520
in der Übung nochmal anhand von einem weiteren Beispiel, ich werde

34:41.520 --> 34:44.300
auch hier ein Beispiel angeben, das Sie aber nochmal vertiefen, das

34:44.300 --> 34:47.320
Sie also dann auch selber anwenden können.

34:48.220 --> 34:55.280
Und dieses Verfahren oder Techniken, durch die wir eben genau diese

34:55.280 --> 35:02.160
Abbildung erreichen können, wir wollen ja den rekursiven

35:02.160 --> 35:06.400
Funktionsidentifikator, dem wollen wir eine mathematische Bedeutung

35:06.400 --> 35:07.040
zuordnen.

35:08.180 --> 35:13.300
Und da gibt es jetzt zwei Techniken, einmal die induktive Deutung und

35:13.300 --> 35:14.820
die Deutung durch Fixpunktgleichung.

35:14.820 --> 35:19.740
Und da werden Sie sehen, dass die sehr viele Ähnlichkeiten haben.

35:20.020 --> 35:22.800
Wir werden mit der induktiven Deutung beginnen und wir werden sehr

35:22.800 --> 35:27.400
viele ähnliche Konstrukte, die wir jetzt in der induktiven Deutung

35:27.400 --> 35:29.840
dann uns erarbeitet haben, die werden wir in der Fixpunktgleichung

35:29.840 --> 35:30.500
dann aufnehmen.

35:31.160 --> 35:34.700
Und der wesentliche Unterschied an der Stelle, das sei auch schon mal

35:34.700 --> 35:39.960
vorab bemerkt, ist derjenige, dass diese Fixpunktgleichung oder die

35:39.960 --> 35:47.680
Fixpunkttheorie, die liefert ein konstruktives Verfahren,

35:53.240 --> 35:55.860
wie wir das machen können, also eigentlich ein mechanisierbares

35:55.860 --> 35:56.320
Verfahren.

35:57.160 --> 36:01.880
Aber Sie werden sehen, dass dieses konstruktive Verfahren letztendlich

36:01.880 --> 36:04.660
von der induktiven Deutung abgeschaut ist.

36:04.660 --> 36:07.540
Da steckt auch ein Verfahren dahinter.

36:07.620 --> 36:10.540
Nur an einer Stelle, das würde ich Ihnen auch sagen, an welcher das

36:10.540 --> 36:15.980
dann eben ist, muss man sich sozusagen diese Lösung selber erarbeiten,

36:16.860 --> 36:24.880
die diese Fixpunkttheorie automatisch erarbeitet oder automatisch

36:24.880 --> 36:25.300
berechnet.

36:25.780 --> 36:27.020
Das ist der wesentliche Unterschied.

36:27.140 --> 36:31.060
Aber im Grundsatz, wenn Sie mal die induktive Deutung zumindest

36:31.060 --> 36:34.580
verstanden haben, dann sind wir schon zufrieden.

36:35.020 --> 36:38.300
Diese Feinheit dann Richtung Fixpunkttheorie werden wir auf zwei, drei

36:38.300 --> 36:41.120
Folien zumindest andeuten.

36:43.740 --> 36:49.580
Wir nehmen wieder mal dieses Beispiel, legen wir wieder zu Gründe und

36:49.580 --> 36:55.300
jetzt wollen wir nochmal diese operationale Behandlung der rekursiven

36:55.300 --> 37:01.500
Funktion verdeutlichen oder nochmal konkretisieren anhand von diesem

37:01.500 --> 37:01.860
Beispiel.

37:02.020 --> 37:03.140
Sollten Sie das dann selber machen.

37:03.260 --> 37:06.660
Ich werde das nochmal hier angeben, was eigentlich operationale

37:06.660 --> 37:09.160
Behandlung jetzt bezogen ist.

37:10.380 --> 37:23.480
Operationale Behandlung und zwar bezogen auf rekursive Funktionen.

37:26.240 --> 37:31.000
Sollten sofort die Assoziation bei operationaler Behandlung haben

37:31.000 --> 37:37.680
Richtung Thermeersetzung und Ersetzung von Einsätzen von rechter

37:37.680 --> 37:38.120
Seite.

37:38.660 --> 37:42.520
Das wollen wir hier auch jetzt entsprechend in dem ersten Schritt

37:42.520 --> 37:43.440
sehen.

37:43.540 --> 37:47.320
Das kann man als Art Rezept hier hinschreiben.

37:52.380 --> 37:54.740
Einsetzen der rechten Seite.

38:00.840 --> 38:06.100
Jetzt ist es in dem Fall Rekursiven Funktionen.

38:06.780 --> 38:13.300
Das nennen wir den Begriff Expansion, den kennen Sie schon.

38:14.480 --> 38:24.160
Man redet auch von einem Entfalten oder englisch ein Unfold.

38:25.240 --> 38:26.120
Das sind die Begriffe.

38:31.440 --> 38:46.170
Zweitens Ausnutzung der Semantik der Funktionsapplikation.

38:53.110 --> 39:00.570
Und zwar haben Sie hier genau diese rekursiven Aufrufe auf der rechten

39:00.570 --> 39:00.970
Seite.

39:01.690 --> 39:05.090
Das bezieht sich also auf die rekursiven Aufrufe.

39:06.210 --> 39:09.810
Auf den rekursiven Aufruf, einer oder mehr, können auf der rechten

39:09.810 --> 39:11.530
Seite enthalten sein.

39:11.530 --> 39:36.180
Das dritte ist das Ausnutzen der Regeln, der Arithmetik und der

39:36.180 --> 39:42.060
bedingten Ausdrücke.

39:44.280 --> 39:47.640
Das Regeln der Arithmetik und Regeln für die bedingten Ausdrücke, so

39:47.640 --> 39:50.540
würde man das genauer sagen.

39:51.220 --> 39:55.020
Also Regeln, wie man die bedingten Ausdrücke auswertet.

39:55.800 --> 39:58.400
Das ist überhaupt nichts Neues.

39:58.740 --> 40:01.340
Ist jetzt nur auf diese rekursiven Funktionen angewendet.

40:01.340 --> 40:13.800
Diese Regeln sollten Sie dann mal auf das Modulo-Beispiel anwenden und

40:13.800 --> 40:15.340
Schritt für Schritt durchgehen.

40:16.100 --> 40:19.480
Das haben Sie im Lambda-Kalkül schon in der Art und Weise behandelt,

40:19.560 --> 40:20.040
mit dem Gopher.

40:21.660 --> 40:24.360
Das müssen Sie jetzt nur auf diese rekursiven Funktionen anwenden.

40:24.360 --> 40:29.160
Das ist also hier an der Stelle sozusagen das Kochrezept, wie Sie hier

40:29.160 --> 40:35.580
vorgehen, um die operationale Semantik zu behandeln.

40:35.860 --> 40:39.600
Das ist Thermersetzung, nichts anderes als Thermersetzung, was Sie

40:39.600 --> 40:41.880
jetzt hier konkret durchführen.

40:43.280 --> 40:49.400
Wir werden eine etwas andere Schreibweise dann brauchen, jetzt für

40:49.400 --> 40:51.440
noch ein anderes Beispiel, das wir einführen.

40:51.440 --> 40:56.680
Wir werden das also eher so in dieser mathematischen Schreibweise

40:56.680 --> 41:01.740
erstmal umsetzen, diese rekursiven Funktionen.

41:02.060 --> 41:05.940
Und die sehen dann eben, wie wir es auch schon an vielen verschiedenen

41:05.940 --> 41:08.060
Stellen durchgeführt haben.

41:08.200 --> 41:13.200
In der Form aus, dass wir jetzt erstmal gucken müssen, diesen

41:13.200 --> 41:15.620
undefiniert Fall müssen wir uns vom Hals schaffen.

41:16.380 --> 41:20.280
Kann sein, dass irgendwo durch das A und B was undefiniertes

41:20.280 --> 41:20.840
reinkommt.

41:21.320 --> 41:25.860
Und dann können wir den IF, den SEND und den ELSE-Fall behandeln.

41:26.160 --> 41:28.820
Falls a kleiner b.

41:30.220 --> 41:34.200
Und jetzt kommen wir genau zu dem Beispiel, oder zu dem Fall, dass wir

41:34.200 --> 41:35.640
hier einen rekursiven Aufruf haben.

41:35.740 --> 41:38.660
a minus b, b.

41:39.460 --> 41:43.500
Falls, ne, dann machen wir ELSE, das ist der Sonstfall.

41:44.200 --> 41:47.600
Das ist auch sowas, was Sie einüben können.

41:47.600 --> 41:54.780
Können Sie sich auch vorstellen, dass bei komplexeren Funktionen, Sie

41:54.780 --> 41:58.700
hier einfach mehrere Fälle betrachten müssen.

41:58.840 --> 42:02.160
Nicht so, dass Sie jetzt nur mit einem IF, SEND, ELSE arbeiten müssen,

42:02.280 --> 42:05.700
sondern Sie müssen das auch noch weiter vertiefen und konkretisieren.

42:06.200 --> 42:07.660
Kriegen Sie halt ein paar mehr Fälle mit rein.

42:08.720 --> 42:12.320
Dass das dann in Schreibarbeit ausartet, das ist auch klar.

42:12.540 --> 42:16.440
Deswegen lässt man die Beispiele in der Regel relativ klein.

42:16.440 --> 42:18.980
Aber im Grundsatz lässt sich das, was wir jetzt auch hier behandeln,

42:19.420 --> 42:23.160
an einem Beispiel, das Sie also auf beliebig komplexe Funktionen

42:23.160 --> 42:23.740
übertragen.

42:24.080 --> 42:26.780
Natürlich brauchen Sie dann entsprechende Werkzeugunterstützung, das

42:26.780 --> 42:28.280
machen Sie entsprechend auf dem Rechner dann.

42:28.940 --> 42:31.480
Aber im Grundsatz ist das genau die gleiche Geschichte.

42:32.680 --> 42:39.000
So, kommen wir jetzt noch mal zu der induktiven Deutung von rekursiven

42:39.000 --> 42:40.440
Funktionsdeklarationen.

42:40.960 --> 42:47.260
Erst noch mal die Erkenntnis, Rekursion haben wir an vielen Stellen

42:47.260 --> 42:48.120
schon kennengelernt.

42:48.860 --> 42:52.920
Ich erinnere an diese formalen Sprachen, an diese BNF-Regeln.

42:54.840 --> 42:57.120
Schauen Sie sich dann noch mal an, wie wir das aufgelöst haben.

42:57.840 --> 43:02.000
Das Verfahren, dieses induktive Vorgehen, das haben wir da schon

43:02.000 --> 43:02.800
kennengelernt.

43:03.600 --> 43:09.080
Da können Sie einige Teile von jetzt auch übernehmen, wenn wir uns an

43:09.080 --> 43:11.480
die induktive Deutung von rekursiven Funktionen machen.

43:13.100 --> 43:17.340
Was wir auch noch vertiefen werden im Kapitel 6, das sind rekursive

43:17.340 --> 43:18.740
Sortendeklarationen.

43:18.880 --> 43:24.060
Ich gebe Ihnen nur an der Stelle kurz ein Beispiel.

43:25.080 --> 43:30.500
Wenn Sie eine Liste sich betrachten, dann können Sie das auffassen als

43:30.500 --> 43:33.860
ein Element und wieder eine Liste.

43:35.260 --> 43:35.880
Nämlich den Rest.

43:36.720 --> 43:40.380
Aber es ist auch nichts anderes von der Sorte her als eine Liste.

43:41.020 --> 43:43.680
Oder Sie nehmen einen Binärbaum.

43:44.540 --> 43:46.460
Nehme ich jetzt einfach mal hier B-Baum.

43:47.980 --> 43:58.300
Das ist ein Binärbaum, ein Element, Element und wieder ein Binärbaum.

44:02.980 --> 44:07.580
Das sind jetzt sozusagen zwei, das sind ja keine rekursiven Aufrufe,

44:07.760 --> 44:12.040
sondern das sind zwei rekursive Elemente hier enthalten.

44:12.600 --> 44:14.000
Bei der Liste ist es eben einer.

44:15.060 --> 44:20.120
Gut, ich würde jetzt mal fünf Minuten Pause machen, damit wir dann auf

44:20.120 --> 44:22.220
das Thema mit der induktiven Deutung eingehen können.

44:36.880 --> 44:38.420
So, ich würde gerne weitermachen.

44:42.680 --> 44:43.800
Induktive Deutung.

44:48.360 --> 44:49.440
So, was haben wir?

44:51.020 --> 44:53.780
Schauen wir uns doch mal die Ausgangssituation an.

44:53.820 --> 44:56.200
Wir haben eine Funktionsdeklaration.

44:58.100 --> 45:02.700
Function f ist gleich, dann kommt der formale Parameter.

45:02.780 --> 45:07.260
Hier ist das x von der Sorte n, das Ergebnis Sorte n.

45:07.980 --> 45:10.700
Und dann kommt ein Ausdruck, e steht da für expression.

45:11.700 --> 45:18.980
Und das Problem an der Stelle ist, dass in e das f, das

45:18.980 --> 45:23.120
Funktionssymbol f, wieder frei auftritt oder auftreten darf.

45:27.960 --> 45:40.500
Jetzt begreifen wir diese Funktion sinnvollerweise als ein Funktional.

45:42.560 --> 45:50.320
Denn wir kriegen jetzt nicht sozusagen als Ergebnis einen Wert, einen

45:50.320 --> 45:55.060
Funktionswert der Sorte n heraus.

45:55.340 --> 45:57.460
Das ist ja unsere Ergebnissorte.

45:58.340 --> 46:02.260
Sondern wir haben das Problem, dass wir eine ganze Funktion als

46:02.260 --> 46:04.460
Ergebnis herausbekommen.

46:04.460 --> 46:11.260
Und das drückt genau dieses Funktional aus, dass wir hier sozusagen

46:11.260 --> 46:18.440
als Ergebnis eine ganze Funktion wieder herausbekommen.

46:18.800 --> 46:23.540
Also tau liefert für Funktionen g von m nach n wieder eine Funktion.

46:24.760 --> 46:27.980
Das kommt dieser Rekursion ja auch sehr nahe.

46:27.980 --> 46:32.660
Das ist genau das, was die Rekursion ausmacht, dass ich hinten raus

46:32.660 --> 46:37.460
mit der Funktion wieder ende und nicht mit einem Ergebnis oder einem

46:37.460 --> 46:38.980
Wert der Sorte n.

46:41.420 --> 46:46.720
Und jetzt müssen wir uns überlegen, wie wir mit diesem Funktional

46:46.720 --> 46:48.300
arbeiten können.

46:48.640 --> 46:52.140
Also die Beobachtung, dass wir hier mit dem Funktional an die Sache

46:52.140 --> 46:53.980
rangehen, das ist nachvollziehbar.

46:53.980 --> 46:59.460
Das lässt sich also durchaus mit diesem Rekursiven Aufruf der

46:59.460 --> 47:01.860
Rekursiven Funktion erklären.

47:02.400 --> 47:05.260
Aber jetzt müssen wir natürlich noch überlegen, wie wir mit dem

47:05.260 --> 47:11.220
Funktional in eine Berechnung kommen, dass wir diese semantische

47:11.220 --> 47:14.340
Interpretation, diese Semantik von den Rekursiven Funktionen auch

47:14.340 --> 47:15.420
hinbekommen.

47:15.760 --> 47:17.980
Und das ist genau jetzt hier diese untere Aussage.

47:17.980 --> 47:23.280
Dass wir nämlich jetzt hier induktiv mit unserem Funktional arbeiten

47:23.280 --> 47:27.560
können und zu einer Funktionenfolge kommen können.

47:27.560 --> 47:31.020
Und das sieht also folgendermaßen aus.

47:35.800 --> 47:55.180
Die induktiv definierten Funktionen, die nennen wir eben jetzt fi, f

47:55.180 --> 47:55.940
mit Index i.

47:55.940 --> 48:10.820
Die sind durch folgende Gleichungen definiert.

48:14.440 --> 48:20.400
Wir fangen an mit f0 von x.

48:22.860 --> 48:24.340
Das ist undefiniert.

48:25.140 --> 48:30.300
Für alle x, die wir da einsetzen, könnt ihr auch jetzt hier

48:30.300 --> 48:39.920
hinschreiben, f0 spricht von unserem Omega, was wir jetzt hier schon

48:39.920 --> 48:40.700
eingeführt haben.

48:45.000 --> 48:46.700
Das ist also eigentlich der Induktionsbeginn.

48:48.920 --> 48:51.180
Vollständig undefinierte Funktionen.

48:52.080 --> 48:53.820
Und wie sieht jetzt der Induktionsschritt aus?

48:55.380 --> 49:01.020
Irgendwo sollte jetzt hier das Funktional mal mit ins Spiel kommen.

49:01.640 --> 49:05.700
An der Stelle ist genau beim Induktionsschritt bringt er das

49:05.700 --> 49:06.720
Funktional mit ein.

49:07.600 --> 49:17.960
Und wir setzen jetzt hier genau die Funktion, zu der wir bisher

49:17.960 --> 49:21.040
gekommen sind in der Folge, die setzen wir hier ein.

49:22.060 --> 49:27.140
Entsprechend heißt also, wenn Sie sich das mal hier eingesetzt

49:27.140 --> 49:32.640
vorstellen, fangen Sie mit dem f0 an, dann setzen Sie da, indem Sie

49:32.640 --> 49:35.660
das f0 in das Funktional einsetzen, kommen Sie zum f1.

49:36.320 --> 49:39.200
Indem Sie das f1 in das Funktional einsetzen, kommen Sie in das f2.

49:39.720 --> 49:45.200
Dann kommen Sie genau zu dem Ergebnis, zu dem Bildungsgesetz von dem

49:45.200 --> 49:45.560
fi.

49:45.560 --> 49:51.880
Das ist nämlich das tau hoch i, das ist also i mal das tau, eingesetzt

49:51.880 --> 49:54.940
von f0.

49:56.260 --> 50:04.000
Das ist also nichts anderes als tau i mal eingesetzt von f0.

50:05.040 --> 50:07.280
Und das ist genau i mal.

50:08.900 --> 50:14.600
Das ist also die Induktionsfolge, die wir jetzt hier vorsehen.

50:15.600 --> 50:22.000
So bauen wir also sozusagen unsere Funktion entsprechend des

50:22.000 --> 50:22.760
Funktionales auf.

50:22.840 --> 50:25.360
Macht doch irgendwo Sinn, ich fange also mit der vollständig

50:25.360 --> 50:27.580
undefinierten Funktion an.

50:27.920 --> 50:31.080
Das bedeutet jetzt mal informell gesprochen, ich weiß überhaupt nichts

50:31.080 --> 50:31.820
über die Funktion.

50:32.460 --> 50:34.020
Ich kann keine Aussage machen.

50:35.480 --> 50:38.860
Und hoffe jetzt, und das werden wir gleich sehen, dass die Hoffnung

50:38.860 --> 50:45.580
berechtigt ist, dass ich jetzt das Funktional mit ins Spiel bringe.

50:46.000 --> 50:48.720
Da steckt ja jetzt dann auch die Funktion drin.

50:49.120 --> 50:56.480
Da steckt der Funktionsaufbau drin, dass ich da weiterkomme, was jetzt

50:56.480 --> 50:57.840
definierte Stellen angeht.

50:58.000 --> 51:00.820
Das ist die Idee und das ist das Vorgehen.

51:00.820 --> 51:04.160
In dem Tau steckt die Funktion drin und dadurch, dass ich jetzt

51:04.160 --> 51:08.340
anfange mit der vollständig undefinierten Funktion, ist die Hoffnung,

51:08.420 --> 51:10.560
dass ich jetzt bei f1 ein bisschen weiterkomme.

51:10.760 --> 51:15.000
Dass ich bei f2 noch mehr definierte Stellen rausbekomme, bei f3 noch

51:15.000 --> 51:16.000
mehr definierte Stellen.

51:16.500 --> 51:22.700
Und dass ich dann mich sozusagen an die Funktion annähere, die genau

51:22.700 --> 51:26.000
diese rekursive Funktionsbeschreibung darstellt.

51:26.000 --> 51:29.120
Wir werden dann auch sehen, insbesondere jetzt mit der

51:29.120 --> 51:32.780
Fixpunkttheorie, dass wir gewisse Eigenschaften, mathematische

51:32.780 --> 51:35.920
Eigenschaften für dieses Funktional festlegen können.

51:36.080 --> 51:40.520
Nämlich die Monotonie und die Stetigkeit, die dann dazu führen, dass

51:40.520 --> 51:43.640
wir tatsächlich mit diesem Vorgehen immer zum Ziel kommen.

51:44.000 --> 51:48.680
Dass wir also zu einem irgendwann mal in dieser Kette zu einer

51:48.680 --> 51:53.820
Funktion kommen, die sozusagen nicht mehr weitere Stellen ergibt, wo

51:53.820 --> 51:57.900
ich jetzt, wenn ich die Funktion fi einsetze, in das Funktional, also

51:57.900 --> 52:02.940
das fi plus 1 errechne, wie wir da zu einem stabilen Zustand kommen,

52:03.080 --> 52:05.660
wo fi plus 1 gleich fi ist und dann sind wir am Ende.

52:06.300 --> 52:10.700
Und das ist sozusagen dann das Ziel auch der Theorie, die wir hier

52:10.700 --> 52:11.600
entwickeln.

52:12.420 --> 52:17.300
Versuchen wir aber erstmal, dieses Vorgehen zu verstehen.

52:18.180 --> 52:20.480
Und zwar anhand von einem einfachen Beispiel.

52:22.420 --> 52:24.360
Nämlich wir nehmen die Fakultätsfunktion.

52:27.000 --> 52:33.840
Die sieht ja so aus, dass wir eben, wenn 0 Fakultät ist 1 und wenn x

52:33.840 --> 52:39.080
jetzt größer ist, dann kommen wir entsprechend zu, ist ja nut, sehen

52:39.080 --> 52:43.440
Sie hier, wir müssen also keine Assertion machen, keine Zusicherung

52:43.440 --> 52:47.300
machen, dass dann x größer als 0 sein muss.

52:48.020 --> 52:50.440
Da wenn es ein Integer wäre, würden wir das hier oben reinschreiben

52:50.440 --> 52:51.180
müssen.

52:51.400 --> 52:55.360
Also beispielsweise, wenn wir jetzt int x hätten, dann müssten wir

52:55.360 --> 52:59.040
hier an der Stunde immer sagen, x größer gleich 0, das wäre so eine

52:59.040 --> 53:02.060
Assertion, die wir hier ja vorher auch eingeführt haben, aber wir

53:02.060 --> 53:03.640
haben ja natürlichen Zahlen.

53:03.640 --> 53:07.160
Und wenn wir eben noch nicht bei 0 sind, dann sind wir in dem

53:07.160 --> 53:10.180
rekursiven Fall, x mal Fakultät, x minus 1.

53:11.060 --> 53:15.220
So, jetzt, wie sieht das funktional aus?

53:16.680 --> 53:19.060
Das ist also die Frage.

53:19.840 --> 53:23.860
Und hier sehen Sie das, was ich also bei der Modulo-Funktion angegeben

53:23.860 --> 53:24.120
habe.

53:24.520 --> 53:28.760
Das ist eigentlich nichts anderes als diese Beschreibung hier, die

53:28.760 --> 53:32.960
insbesondere der Rumpf in dieser mathematischen Schreibweise

53:32.960 --> 53:37.940
aufgeschrieben, in dieser mathematischen Schreibweise formuliert, wo

53:37.940 --> 53:41.560
wir uns dieses undefiniert erstmal vornehmen müssen.

53:41.740 --> 53:46.100
Und dann sind immer die gleichen Fälle undefiniert.

53:46.820 --> 53:49.440
In dem Fall der Zen-Fall und der Els-Fall.

53:50.220 --> 53:54.900
Und der Els-Fall ist jetzt hier das rekursive Auftreten.

53:54.900 --> 53:59.200
Das können Sie also auch fast mechanisieren, dass Sie diese Art von

53:59.200 --> 54:03.740
Aufschreibung für den betrachteten Algorithmus durchführen können.

54:03.880 --> 54:08.200
Da steckt also nichts weiter drin, als eigentlich diese Funktion

54:08.200 --> 54:12.680
entsprechend der Funktional-Schreibweise behandelt und aufgeschrieben.

54:13.320 --> 54:17.320
Und das entspricht genau dem, was ich an der Stelle hier gesagt habe,

54:17.940 --> 54:22.220
dass hier an der Stelle also auch meine Funktion enthalten ist.

54:22.220 --> 54:25.720
Dass da das Wissen über die Funktion mit reinkommt.

54:26.080 --> 54:31.040
Wir sehen das an dem Beispiel, es wird sozusagen die Funktion in

54:31.040 --> 54:33.140
dieser Art und Weise in das Funktional mit aufgenommen.

54:33.560 --> 54:34.820
Fallunterscheidungen durchgeführt.

54:35.650 --> 54:44.940
So, und an der Stelle müssen wir jetzt uns überlegen, wie eigentlich

54:44.940 --> 54:53.040
diese Fakultät mit dem Index i, wie die aufgebaut ist.

54:53.040 --> 54:59.480
Und jetzt kommt genau diese Stelle in der induktiven Deutung, wo Sie

54:59.480 --> 55:04.960
mal erste Einsetzungen durchführen müssen.

55:05.100 --> 55:07.160
Das wird also in der Zentralübung aber vertieft.

55:07.540 --> 55:11.220
Dass Sie also sozusagen mal mit diesem Funktional spielen müssen, um

55:11.220 --> 55:14.280
zu sehen, wie entwickelt sich denn eigentlich diese Funktion.

55:14.280 --> 55:21.960
Also wenn ich von Fakultät 0, von der undefinierten Funktion losstarte

55:21.960 --> 55:26.060
und das mal ins Funktional einsetze, das Ergebnis von dem ins

55:26.060 --> 55:32.100
Funktional einsetze, dann bekommt man so ein Gefühl dafür, wie sich

55:32.100 --> 55:32.780
das entwickelt.

55:33.540 --> 55:38.600
Und das ist jetzt in dem Verfahren eine Kunst, dass man das jetzt dann

55:38.600 --> 55:42.160
entsprechend in eine richtige Funktion einkleidet.

55:42.160 --> 55:48.740
Und ich gebe Ihnen einfach mal hier das Ergebnis, was Sie daraus

55:48.740 --> 55:54.700
destillieren können, nachdem Sie es ein bisschen mit dem Funktional

55:54.700 --> 55:55.560
beschäftigt haben.

55:56.120 --> 56:02.080
Dann sagen Sie nämlich folgendes, Sie kommen zu der Erkenntnis, dass

56:02.080 --> 56:07.560
dieses Fakultät i, Sie müssen hier noch das x angeben,

56:12.600 --> 56:19.320
Fakultät i von x ist also folgendermaßen definiert, beachten Sie, dass

56:19.320 --> 56:26.860
unten dieses i, das kommt von der Folge der Funktion, das kommt also

56:26.860 --> 56:33.780
hier von dieser Induktion.

56:34.520 --> 56:40.600
Daher kommt dieser Index hier und das müssen Sie sozusagen erstmal

56:40.600 --> 56:44.680
sich überlegen, ein paar mal ausprobieren und jetzt gehen Sie davon

56:44.680 --> 56:49.060
aus, dass Sie sagen, Sie sind zu einem Ergebnis gekommen und das

56:49.060 --> 56:54.040
Ergebnis sieht folgendermaßen aus, dass Fakultät mit Index i von x

56:54.040 --> 57:07.700
immer dann undefiniert liefert, falls x aus n, das können Sie

57:07.700 --> 57:15.600
eigentlich an der Stelle weglassen, ist klar, x muss aus n sein, dann

57:15.600 --> 57:25.220
haben wir hier an der Stelle i kleiner gleich, falls i kleiner gleich

57:25.220 --> 57:38.340
x oder x gleich Omega ist.

57:40.280 --> 57:45.500
Das ist die Erkenntnis, die hier drin steckt, das ist klar, x gleich

57:45.500 --> 57:50.100
undefiniert, x gleich bottom an der Stelle.

57:50.100 --> 57:57.360
Aber hier steckt eine Erkenntnis drin, i kleiner gleich x, also Sie

57:57.360 --> 58:07.280
stellen fest, dass solange der Funktionswert, den Sie hier einsetzen,

58:07.360 --> 58:12.360
dieser Parameter, den Sie hier einsetzen, solange der noch größer oder

58:12.360 --> 58:18.260
gleich diesem Index ist, der sich ja ständig erhöht mit der induktiven

58:18.260 --> 58:25.340
Folge, aber solange dieses x größer ist oder gleich ist, liefert das

58:25.340 --> 58:26.960
keinen definierten Wert.

58:28.440 --> 58:35.780
Erst dann, nur dann, wenn Sie unter diesem Wert, wie Sie sich

58:35.780 --> 58:40.800
befinden, mit Ihrem Wert x, den Sie einsetzen, liefert das das

58:40.800 --> 58:42.940
Ergebnis, wie Sie es wünschen, nämlich x Fakultät.

58:44.580 --> 58:51.540
Das heißt also, Sie entwickeln diese induktive Folge, so gekommen mit

58:51.540 --> 58:58.860
jedem Schritt kommen Sie den nächsten Funktionswert mit in den

58:58.860 --> 58:59.260
Wertebereich.

59:00.140 --> 59:07.820
Also einem Beispiel mal festgemacht, wenn Sie jetzt Fakultät 7,

59:08.460 --> 59:13.400
Fakultät von 6 berechnen wollen.

59:14.400 --> 59:25.800
Und Sie sind hier unten schon bis zum Schritt 7 gekommen, dann liefert

59:25.800 --> 59:31.060
das tatsächlich die 6 Fakultät.

59:31.060 --> 59:37.100
Wenn Sie aber jetzt erst beim Schritt 6 angekommen sind oder noch

59:37.100 --> 59:40.500
schlimmer beim Schritt 5 oder beim Schritt 4, dann liefert das

59:40.500 --> 59:41.180
undefiniert.

59:41.440 --> 59:46.080
Das können Sie jetzt mit jedem anderen Wert auch machen, Fakultät von

59:46.080 --> 59:50.080
100, erst ab dem 100.

59:50.300 --> 59:55.100
Schritt in der induktiven Folge kommen Sie sozusagen zu einem

59:55.100 --> 59:55.960
definierten Ergebnis.

59:55.960 --> 01:00:03.400
Das heißt, in jedem Schritt bekommen Sie ein definiertes Ergebnis mehr

01:00:03.400 --> 01:00:05.120
in den Wertebereich.

01:00:05.870 --> 01:00:16.380
Diese Sache lässt sich beweisen, dass die Funktion das tatsächlich

01:00:16.380 --> 01:00:16.700
tut.

01:00:16.820 --> 01:00:21.120
Das wollen wir mal kurz andeuten, wie das aussieht.

01:00:21.120 --> 01:00:25.720
Da brauchen wir nochmal ein Blatt.

01:00:27.560 --> 01:00:33.320
Nämlich, Sie müssen jetzt sozusagen eine Induktion führen, und zwar

01:00:33.320 --> 01:00:44.660
führen ein Beweis durch Induktion, und zwar über dem i.

01:00:45.880 --> 01:00:47.800
Über dem i, das ist klar.

01:00:50.800 --> 01:00:57.620
Und Sie müssen jetzt den Anfang, wie Sie sich klar machen, dass

01:00:57.620 --> 01:01:02.040
Fakultät 0 von x undefiniert ist, das ist klar.

01:01:02.040 --> 01:01:04.320
Interessant ist jetzt der Induktionsschritt.

01:01:06.680 --> 01:01:24.880
Der Schritt sieht so aus, dass die Behauptung 2, 4, Fakultät i richtig

01:01:24.880 --> 01:01:26.040
ist.

01:01:27.260 --> 01:01:38.840
Das heißt also, diese Definition, die Sie hier angegeben haben, das

01:01:38.840 --> 01:01:48.460
gibt es für Fakultät von i, sei das also die richtige Bewertung oder

01:01:48.460 --> 01:01:50.680
Wertebelegung für diese Fakultät.

01:01:50.680 --> 01:01:56.760
Jetzt müssen Sie sich überlegen, wie sieht das für Fakultät i plus 1

01:01:56.760 --> 01:02:06.100
von x aus, und dann müssen Sie an der Stelle das Funktional mit

01:02:06.100 --> 01:02:07.160
einbeziehen.

01:02:07.160 --> 01:02:13.500
Diese Fakultät i müssen Sie jetzt hier entsprechend einsetzen von x,

01:02:14.500 --> 01:02:20.140
und das ist gleich, das müssen Sie sich nicht die definierte Funktion

01:02:20.140 --> 01:02:21.400
anschauen, sondern das Funktional.

01:02:22.060 --> 01:02:24.200
Das haben Sie sich nicht irgendwie überlegt, sondern das ist ja aus

01:02:24.200 --> 01:02:28.700
der Funktion direkt herausgekommen, das ist also auf der Folie

01:02:28.700 --> 01:02:29.660
enthalten, ich zeige es nochmal.

01:02:30.540 --> 01:02:36.180
Das ist genau dieses hier, das müssen Sie sich jetzt hier einsetzen,

01:02:37.840 --> 01:02:49.180
und das führt dann genau zu bottom, falls x gleich bottom führt zu 1,

01:02:49.180 --> 01:03:02.600
falls x gleich 0 und führt eben zu x, Fakultät i von x minus 1, sonst.

01:03:03.250 --> 01:03:11.740
So, und jetzt können Sie hier an der Stelle die Induktionsbehauptung

01:03:11.740 --> 01:03:22.760
einsetzen, und sozusagen hier dieses entsprechend nochmal aufteilen.

01:03:22.760 --> 01:03:27.800
Das ist nämlich, das möchte ich jetzt an der Stelle gar nicht mehr

01:03:27.800 --> 01:03:39.860
vertiefen, x mal bottom oder x mal x minus 1, Fakultät für diese

01:03:39.860 --> 01:03:43.780
beiden Fälle, das ist ja genau definiert.

01:03:43.780 --> 01:03:48.980
Und dann kommen Sie also im nächsten Schritt genau zu der Erkenntnis,

01:03:48.980 --> 01:03:54.040
das kann ich vielleicht auch nochmal zusammenfassen, das ist dann

01:03:54.040 --> 01:03:56.820
gleich, ich zeige es Ihnen gleich wieder.

01:03:56.820 --> 01:04:16.920
So, bottom, falls i plus 1 kleiner gleich x oder x gleich bottom und x

01:04:16.920 --> 01:04:25.480
Fakultät sonst, und das ist genau das, was Sie sozusagen hier beweisen

01:04:25.480 --> 01:04:25.860
wollten.

01:04:29.640 --> 01:04:37.260
Wichtig ist an der Stelle zu verstehen, warum da eigentlich immer ein

01:04:37.260 --> 01:04:38.140
Wert dazu kommt.

01:04:39.100 --> 01:04:43.960
Und das hängt mit dem Funktional zusammen und das hängt genau mit

01:04:43.960 --> 01:04:46.480
dieser mittleren Zeile zusammen.

01:04:46.480 --> 01:04:49.640
Das müssen Sie sich nochmal überlegen, da werden wir also in der

01:04:49.640 --> 01:04:54.580
Zentralübung heute auch nochmal auf das Fakultätsbeispiel eingehen und

01:04:54.580 --> 01:04:57.660
dann nochmal ein zweites Beispiel konkretisieren.

01:04:58.320 --> 01:05:02.340
Und da kommen Sie dann drauf, warum hier sozusagen ein Zuwachs an

01:05:02.340 --> 01:05:03.620
Werten eigentlich gegeben ist.

01:05:04.240 --> 01:05:07.900
Wenn Sie das nochmal nachvollziehen, dann können Sie genau, wenn Sie

01:05:07.900 --> 01:05:11.480
sehen, dass das eben hier mit dieser mittleren Zeile zu tun hat.

01:05:12.240 --> 01:05:14.440
So, und das ist das Ergebnis.

01:05:19.080 --> 01:05:34.200
So, jetzt wollen wir uns im Folgenden nochmal mit der induktiven

01:05:34.200 --> 01:05:40.840
Deutung zusammenfassen und das führt eben zu dem sogenannten F

01:05:40.840 --> 01:05:41.520
-Unendlich.

01:05:41.520 --> 01:05:52.100
Das heißt, wir induzieren über endliche Schritte, aber unendlich

01:05:52.100 --> 01:05:54.980
häufig wenden wir diese induktive Folge an.

01:05:56.540 --> 01:06:01.100
Und jetzt können wir an der Stelle diese schon genannte Monotonie

01:06:01.100 --> 01:06:03.900
-Eigenschaft, die wollen wir dann auch gleich in der Fixpunkttheorie

01:06:03.900 --> 01:06:07.920
nochmal vertiefen, können wir hier also definieren.

01:06:08.920 --> 01:06:17.640
Und da muss man sich jetzt etwas anders mit der Eigenschaft der

01:06:17.640 --> 01:06:25.700
Monotonie aufstellen, um hier diese monoton steigende Folge zu

01:06:25.700 --> 01:06:26.320
definieren.

01:06:26.900 --> 01:06:32.060
Das sieht folgendermaßen aus, hier möchte ich mal die Definition mit

01:06:32.060 --> 01:06:34.180
Ihnen kurz durchgehen.

01:06:34.180 --> 01:06:41.080
Wir sagen, i ist kleiner gleich j, also i, das ist unser Index, wie

01:06:41.080 --> 01:06:42.780
Sie das auf der rechten Seite sehen werden.

01:06:44.540 --> 01:06:50.020
Und wenn i kleiner gleich j ist, dann folgt daraus, dass für die

01:06:50.020 --> 01:06:56.460
beiden Funktionen f i von x und f j von x, das gilt f i von x ist

01:06:56.460 --> 01:07:03.160
bottom oder f i von x und f j von x stimmen überein.

01:07:04.920 --> 01:07:11.080
Da sollte man sich folgendes Bild vor Augen haben, man hatte hier

01:07:11.080 --> 01:07:16.680
diese Folge f 0, f 1, f 2, f 3 und so weiter.

01:07:17.740 --> 01:07:24.320
Und was hier jetzt ausgedrückt wird, ist folgendes, bei einer

01:07:24.320 --> 01:07:30.260
Funktion, die weiter links steht, das ist i kleiner gleich j, drückt

01:07:30.260 --> 01:07:31.040
das hier aus.

01:07:32.860 --> 01:07:45.920
Für die gilt, dass an einer Stelle x diese Funktion entweder bottom

01:07:45.920 --> 01:07:55.360
ist oder sie stimmt mit der Funktion an dieser Stelle im Ergebniswert

01:07:55.360 --> 01:07:55.900
überein.

01:07:56.680 --> 01:08:03.200
Das bedeutet nichts anderes, was hier steht, als dass Sie, wie es

01:08:03.200 --> 01:08:07.780
schon angedeutet wurde, immer mehr Werte hinzubekommen.

01:08:09.160 --> 01:08:14.880
Und an den Werten, die sozusagen schon definiert sind, da ändert sich

01:08:14.880 --> 01:08:16.900
bezüglich des Ergebnisses nichts.

01:08:17.860 --> 01:08:22.800
Die Funktion bleibt an den Stellen, wo sie schon definiert ist, ab

01:08:22.800 --> 01:08:23.840
einer bestimmten Stelle.

01:08:24.680 --> 01:08:29.840
Bleibt sie also stabil und Sie kriegen nur sozusagen immer mehr

01:08:29.840 --> 01:08:31.120
definierte Stellen hinzu.

01:08:31.360 --> 01:08:34.220
Das ist das, was hier mit ausgedrückt ist.

01:08:35.000 --> 01:08:40.740
Und jetzt können wir entsprechend dieses Ordnungsprinzip, dieser

01:08:40.740 --> 01:08:45.660
Ordnung, die wir hier jetzt aufgebaut haben, auch das f-unendlich von

01:08:45.660 --> 01:08:51.000
x bestimmen, indem wir hier wieder auf die Indizes zurückgehen.

01:08:52.660 --> 01:08:55.160
Das ist undefiniert, dieses f-unendlich von x.

01:08:56.040 --> 01:09:04.180
Falls wir keine Stelle finden, keinen Index finden, ab dem eine der

01:09:04.180 --> 01:09:10.060
Funktionen in der induktiven Folge einen Wert liefert, der nicht

01:09:10.060 --> 01:09:10.920
undefiniert ist.

01:09:11.020 --> 01:09:19.840
Oder andersrum, falls für alle Funktionen in dieser Folge gilt, die

01:09:19.840 --> 01:09:20.480
liefern Bottom.

01:09:20.480 --> 01:09:21.780
Das ist hier ausgedrückt.

01:09:22.560 --> 01:09:28.760
Wir werden nie eine Stelle finden in unserer Abfolge von Funktionen,

01:09:28.880 --> 01:09:33.440
der sozusagen an dieser Stelle x einen Wert ungleich undefiniert

01:09:33.440 --> 01:09:34.200
angegeben wird.

01:09:34.780 --> 01:09:41.520
Und andersrum, falls es eben so ein j aus den natürlichen Zahlen gibt,

01:09:42.480 --> 01:09:46.320
das fj von x ungleich undefiniert ist, dann ist das das fj von x.

01:09:47.060 --> 01:09:53.520
Was jetzt hier noch mit enthalten ist, was implizit durch diese Angabe

01:09:53.520 --> 01:10:04.100
festgelegt ist, dass das gleich fj plus 1 von x ist, das ist gleich fj

01:10:04.100 --> 01:10:05.740
plus 2 von x und so weiter.

01:10:06.500 --> 01:10:09.940
Das heißt, hier ändert sich dieser Wert nicht.

01:10:10.040 --> 01:10:14.120
Das heißt, wenn das mal an einer bestimmten Stelle definiert ist, dann

01:10:14.120 --> 01:10:18.060
bleibt das eben in dieser Form definiert und mit dem gleichen Wert in

01:10:18.060 --> 01:10:18.600
dieser Folge.

01:10:19.800 --> 01:10:22.440
Deswegen können wir hier fj von x hinschreiben, das ist auch

01:10:22.440 --> 01:10:23.040
eindeutig.

01:10:24.140 --> 01:10:29.120
Und das ist genau die induktive Deutung, die wir eben suchen.

01:10:30.360 --> 01:10:34.840
Durch diese Ordnung, die wir hier oben angegeben haben, ist das eben

01:10:34.840 --> 01:10:35.120
erfolgt.

01:10:36.160 --> 01:10:44.180
Und was wir jetzt im Folgenden uns überlegen werden, ist folgendes.

01:10:45.660 --> 01:10:49.680
Das Ziel, was wir jetzt mit den nächsten zwei Folien erreichen wollen.

01:10:50.680 --> 01:11:06.020
Das ist eine mathematische Abstützung dieser induktiven Deutung.

01:11:10.380 --> 01:11:17.340
Also letztendlich von dem f und endlich, was wir gerade behandelt

01:11:17.340 --> 01:11:23.050
haben mittels einer partiellen Ordnung.

01:11:27.170 --> 01:11:32.050
Das ist ja bekanntlich eine Ordnung, eine partielle Ordnung, die für

01:11:32.050 --> 01:11:36.610
nicht je zwei Elemente der Menge, auf der wir diese Ordnung

01:11:36.610 --> 01:11:40.590
definieren, definiert sein muss.

01:11:41.750 --> 01:11:43.030
Deswegen partiell.

01:11:44.030 --> 01:11:50.030
Und diese mathematische Abstützung und die partielle Ordnung, das ist

01:11:50.030 --> 01:11:56.010
sozusagen die Grundlage für die Fixpunkttheorie.

01:12:02.670 --> 01:12:03.770
Das brauchen wir.

01:12:05.750 --> 01:12:11.550
Einerseits werden wir da eine mathematische Definition, eine saubere

01:12:11.550 --> 01:12:15.170
Definition von diesem f und endlich erarbeiten.

01:12:16.150 --> 01:12:19.630
Aber noch viel wichtiger ist, dass wir jetzt da eigentlich die ganzen

01:12:19.630 --> 01:12:24.870
Überlegungen anstellen, um die Fixpunkttheorie aufbauen zu können.

01:12:24.870 --> 01:12:31.070
Und dann eben zwei wichtige Sätze davon ausgehend formulieren können.

01:12:31.410 --> 01:12:33.410
Das ist also das Vorgehen.

01:12:34.890 --> 01:12:40.270
Kommen wir mal zu der partiellen Ordnung, die wir jetzt hier

01:12:40.270 --> 01:12:41.990
betrachten.

01:12:41.990 --> 01:12:48.270
Sie werden sehen, dass diese Definition, diese Festlegung sehr nah an

01:12:48.270 --> 01:12:53.030
dem ist, was wir eben im Zusammenhang mit unserer Funktion induktiven

01:12:53.030 --> 01:12:55.930
Folge schon durchgeführt haben.

01:12:56.770 --> 01:13:02.530
Wir legen fest, dass also x1 kleiner gleich, das ist eckig

01:13:02.530 --> 01:13:09.990
geschrieben, kleiner gleich x2 ist genau dann, wenn...

01:13:10.710 --> 01:13:18.490
und das ändert jetzt sehr an diese Ordnung der Funktion der induktiven

01:13:18.490 --> 01:13:23.710
Folge, genau dann, wenn x1 gleich Bottom ist oder wenn es nicht Bottom

01:13:23.710 --> 01:13:26.810
ist, dann ist x1 gleich x2.

01:13:28.150 --> 01:13:31.990
Die haben wir schon in der Art und Weise, haben wir uns schon mal mit

01:13:31.990 --> 01:13:35.090
genau dieser Ordnung beschäftigt und die haben wir hier schon

01:13:35.090 --> 01:13:35.770
eingeführt.

01:13:35.770 --> 01:13:39.390
Und die sieht folgendermaßen aus, sie haben also dieses Bottom

01:13:39.390 --> 01:13:45.610
-Element, ist undefiniert und entsprechend können sie jetzt hier unten

01:13:45.610 --> 01:13:51.010
sozusagen diese Werte vergeben, xn.

01:13:53.710 --> 01:14:04.010
Und das ist also eine sogenannte flache Struktur, die wir jetzt hier

01:14:04.010 --> 01:14:08.230
einführen oder die eigentlich schon früher eingeführt worden ist, die

01:14:08.230 --> 01:14:09.570
wir jetzt an der Stelle benötigen.

01:14:09.570 --> 01:14:16.490
Die benötigen wir nämlich deswegen, weil hier eine partielle Ordnung

01:14:16.490 --> 01:14:21.390
dadurch auf Abbildung auch induziert wird, dergestalt, dass wir sagen,

01:14:21.610 --> 01:14:28.350
f ist in dieser Ordnung kleiner gleich g, liegt vor g, genau dann,

01:14:28.430 --> 01:14:37.490
wenn für alle x aus m gilt, dass diese Werte gemäß dieser partiellen

01:14:37.490 --> 01:14:44.790
Ordnung angeordnet sind und entsprechend sehen sie, dass wir also

01:14:44.790 --> 01:14:50.790
diese partielle Ordnung auf Elementebene, dass wir die jetzt auf die

01:14:50.790 --> 01:14:52.750
Funktionsebene anheben.

01:14:53.750 --> 01:14:58.030
Diese flache Struktur, die wir hier aufgebaut haben, ermöglicht uns

01:14:58.030 --> 01:15:02.790
auf Elementebene sozusagen, das jetzt auch auf Funktionsebene

01:15:02.790 --> 01:15:03.390
durchzuführen.

01:15:03.390 --> 01:15:07.790
Und wenn Sie sich anschauen, wie wir das in einer der vorhergehenden

01:15:07.790 --> 01:15:14.910
Folien behandelt haben, wenn Sie sich diese Funktionsfolge oder diese

01:15:14.910 --> 01:15:19.590
Ordnung auf der Folge nochmal vergegenwärtigen, dann ist das

01:15:19.590 --> 01:15:24.470
eigentlich genau das gleiche mathematische Vorgehen, was wir jetzt

01:15:24.470 --> 01:15:28.830
hier über diese partielle Ordnung der Elemente erreicht haben.

01:15:28.890 --> 01:15:32.990
Da steht genau das gleiche nur sozusagen auf der Basis dieser

01:15:32.990 --> 01:15:34.270
partiellen Ordnung angegeben.

01:15:34.270 --> 01:15:43.890
So, und jetzt können wir uns an der Stelle noch mit einer Eigenschaft

01:15:43.890 --> 01:15:50.470
beschäftigen, die wir gerichtet nennen, denn für jedes Paar xy aus

01:15:50.470 --> 01:15:56.110
einer nicht leeren Teilmenge z0 eine obere Schanke existiert.

01:15:56.110 --> 01:16:02.610
Das brauchen wir an der Stelle, um diese Ketten letztendlich zu

01:16:02.610 --> 01:16:02.970
bilden.

01:16:03.210 --> 01:16:08.930
Das sind nämlich speziell gerichtete Mengen, die eben diese Form

01:16:08.930 --> 01:16:16.210
haben, xy aus den natürlichen Zahlen mit xy ist kleiner gleich xy plus

01:16:16.210 --> 01:16:16.470
1.

01:16:16.470 --> 01:16:19.450
Also Sie sehen an der Stelle möchte ich gar nicht tiefer darauf

01:16:19.450 --> 01:16:25.110
eingehen, dass wir letztendlich diese Eigenschaft des Gerichtetseins

01:16:25.110 --> 01:16:28.730
auf die letztendlich benötigen, um auf die Ketten zu kommen.

01:16:28.730 --> 01:16:33.450
Und die Ketten sind genau das, was diese induktiven Funktionsfolgen

01:16:33.450 --> 01:16:33.890
ausmacht.

01:16:33.990 --> 01:16:37.890
Das sind nämlich genau, wenn wir das so hinschreiben wollen, dann ist

01:16:37.890 --> 01:16:43.090
eben f0 kleiner gleich f1 kleiner gleich f2.

01:16:43.370 --> 01:16:49.250
Das ist das, was wir genau bei der induktiven Deutung realisiert haben

01:16:49.250 --> 01:16:51.890
mit diesem konstruktiven Verfahren, was ich Ihnen hier angegeben habe.

01:16:51.890 --> 01:16:57.490
Sie sehen an der Stelle, das sollten Sie nochmal vertiefen, wir haben

01:16:57.490 --> 01:17:01.150
von der Informatikseite ein ganz konstruktives Vorgehen angegeben, wie

01:17:01.150 --> 01:17:05.510
wir uns also sozusagen in dieser Funktionsfolge fortbewegen.

01:17:05.510 --> 01:17:10.410
Und letztendlich können wir jetzt eine mathematische Sichtweise auf

01:17:10.410 --> 01:17:16.030
diese Vorgehensweise werfen und mit den ganzen Eigenschaften und

01:17:16.030 --> 01:17:20.550
Ordnungsprinzipien hier an die Sache rangehen, die wir eben in einem

01:17:20.550 --> 01:17:22.670
der Grundlagenkapitel behandelt haben.

01:17:22.670 --> 01:17:25.850
Das ist also jetzt hier das grundsätzliche Vorgehen.

01:17:27.270 --> 01:17:33.210
Wir kommen jetzt zu dem eigentlichen ersten Ergebnis, was wir uns aus

01:17:33.210 --> 01:17:39.730
dieser mathematischen Sichtweise erarbeiten, nämlich das monotone

01:17:39.730 --> 01:17:41.230
Funktional.

01:17:42.490 --> 01:17:47.810
Das ist also eine erste wesentliche Eigenschaft von Funktionalen, die

01:17:47.810 --> 01:17:50.390
wir dann für die Fixpunkttheorie benötigen.

01:17:51.390 --> 01:17:57.450
Vorher müssen wir nochmal eine Eigenschaft einführen und zwar die

01:17:57.450 --> 01:17:59.190
Eigenschaft der Vollständigkeit.

01:18:00.030 --> 01:18:03.690
Und wir sagen, dass eine partiell geordnete Menge vollständig ist,

01:18:04.610 --> 01:18:09.650
wenn es zu jeder wiedergerichteten Menge, siehe Definition auf der

01:18:09.650 --> 01:18:14.290
vorhergehenden Folie, zu jeder wiedergerichteten Menge eine kleinste

01:18:14.290 --> 01:18:17.170
obere Schranke, ein sogenanntes Supremum, existiert.

01:18:17.770 --> 01:18:21.270
Haben wir alles in den Grundlagen behandelt, was Supremum ist,

01:18:21.310 --> 01:18:24.630
Infinium ist, das werden wir hier jetzt eben in die Waagschale werfen

01:18:24.630 --> 01:18:29.130
und das nutzen wir für die sogenannte Eigenschaft der Vollständigkeit

01:18:29.130 --> 01:18:29.510
aus.

01:18:29.510 --> 01:18:36.510
Und das können Sie sehr schnell nachvollziehen, jede durch dieses

01:18:36.510 --> 01:18:42.470
eckige, kleiner, gleich, flach geordnete Menge ist vollständig.

01:18:42.850 --> 01:18:47.750
Sollten Sie sich einfach als Übung nochmal vergegenwärtigen, dass das

01:18:47.750 --> 01:18:49.190
also diese Eigenschaft erfüllt.

01:18:50.030 --> 01:18:52.690
Wir waren also, das brauche ich jetzt nicht hier hinschreiben, das

01:18:52.690 --> 01:18:54.630
können Sie auf der vorhergehenden Folie entsprechend nochmal

01:18:54.630 --> 01:18:56.430
nachvollziehen.

01:18:56.790 --> 01:18:59.690
Und jetzt kommt das Eigentliche, wo wir raus wollen, das ist das, was

01:18:59.690 --> 01:19:03.670
wir jetzt eigentlich hier mal als erstes Ergebnis uns erarbeiten

01:19:03.670 --> 01:19:07.470
wollen, nämlich die Eigenschaft der Monotonie von Funktionalen.

01:19:08.450 --> 01:19:15.110
Ein Funktional-Tau heißt Monoton, wenn für alle Funktionen f und g

01:19:15.110 --> 01:19:16.370
folgende Aussage gilt.

01:19:18.050 --> 01:19:25.670
Wenn vorher die Funktionen nach diesem Ordnungsprinzip aufgebaut sind,

01:19:25.770 --> 01:19:29.870
also sozusagen f kleiner gleich g oder f steht vor dem g. Bitte

01:19:29.870 --> 01:19:32.930
beachten Sie die Definition, die wir dafür angegeben haben, das haben

01:19:32.930 --> 01:19:35.870
wir hier auf die Elemente sozusagen runtergedrückt.

01:19:35.870 --> 01:19:41.250
Wenn das vorher sozusagen gilt, dann verändert das Funktional-Tau

01:19:41.250 --> 01:19:46.990
diese Eigenschaft nicht, sondern wenn wir das f in das Tau reinstecken

01:19:46.990 --> 01:19:50.290
und das g in das Tau reinstecken, dann gilt nach wie vor diese

01:19:50.290 --> 01:19:50.870
Eigenschaft.

01:19:51.550 --> 01:19:56.810
Also Sie sehen, diese Monotonie-Eigenschaft basiert ganz stark auf

01:19:56.810 --> 01:20:04.010
dieser Überlegung, an welchen Stellen ist die Funktion undefiniert.

01:20:04.010 --> 01:20:07.570
Nämlich, das ist ja auch genau hier angegeben, f kleiner gleich g, was

01:20:07.570 --> 01:20:08.090
heißt das?

01:20:08.870 --> 01:20:12.830
Jetzt mal wieder umgangssprachlich, f kleiner gleich g nach diesem

01:20:12.830 --> 01:20:19.230
kleiner gleich Operator bedeutet, g ist an mindestens so vielen

01:20:19.230 --> 01:20:20.430
Stellen definiert wie f.

01:20:22.470 --> 01:20:28.930
Das heißt das, f ist entweder undefiniert oder wenn f definiert ist,

01:20:29.030 --> 01:20:32.510
dann hat es die gleichen Werte wie g. Das heißt, g ist an mindestens

01:20:32.510 --> 01:20:36.430
so vielen Stellen definiert wie f und wenn die beiden definiert sind,

01:20:36.550 --> 01:20:37.530
dann haben sie die gleichen Werte.

01:20:37.810 --> 01:20:40.730
Das bedeutet das und das ändert hier dieses Funktional nicht.

01:20:41.250 --> 01:20:45.790
Das heißt, auch wieder jetzt informell umgangssprachlich ausgedrückt,

01:20:45.990 --> 01:20:47.930
das Funktional liefert eher mehr.

01:20:48.550 --> 01:20:50.870
Es kann also nicht weniger liefern.

01:20:51.630 --> 01:20:55.530
Und das ist ja genau das, was wir uns wünschen im Zusammenhang mit der

01:20:55.530 --> 01:20:56.630
semantischen Deutung.

01:20:56.930 --> 01:21:00.070
Wir wollen Funktionen in das Tau reinstecken, wir wollen jetzt nicht

01:21:00.070 --> 01:21:02.250
einen Rückschritt machen, sondern wir wollen eher immer mehr.

01:21:02.250 --> 01:21:05.110
Das heißt eben monoton steigen im Sinne, wir kriegen immer mehr

01:21:05.110 --> 01:21:10.770
definierte Stellen in unsere Darstellung, in unseren

01:21:10.770 --> 01:21:11.550
Berechnungsvorgang.

01:21:12.550 --> 01:21:22.670
Für ein monotones Funktional gilt, fi ist enthalten in fi plus 1.

01:21:22.670 --> 01:21:25.010
Jetzt kommen wir zurück zu der induktiven Deutung.

01:21:25.830 --> 01:21:34.410
Das heißt, diese Monotonie-Eigenschaft führt genau zu diesem

01:21:34.410 --> 01:21:38.110
Ordnungsprinzip, dass wir tatsächlich zu dieser Kette kommen.

01:21:38.410 --> 01:21:41.550
Das ist also der Zusammenhang jetzt zu der induktiven Deutung.

01:21:41.550 --> 01:21:45.530
Das ist eine ganz einfache Geschichte, das können Sie durch Induktion

01:21:45.530 --> 01:21:45.970
beweisen.

01:21:46.470 --> 01:21:49.530
Wenn Sie das verstanden haben, wie die induktive Deutung funktioniert,

01:21:49.890 --> 01:21:52.550
dann können Sie das in einer Zeile hinschreiben und dann haben Sie das

01:21:52.550 --> 01:21:52.910
Ergebnis.

01:21:54.090 --> 01:21:58.070
Und jetzt kommen wir hier nochmal zurück zu unserem f-unendlich.

01:21:58.910 --> 01:22:06.410
Und das ist genau das Supremum der fi aus den natürlichen Zahlen, das

01:22:06.410 --> 01:22:08.330
ist die kleinste obere Schranke.

01:22:09.410 --> 01:22:15.090
Gut, ich werde nochmal zumindest die nächste Folie kurz andeuten.

01:22:16.410 --> 01:22:20.910
Damit Sie auch ein bisschen Freude für nächste Woche haben, müssen wir

01:22:20.910 --> 01:22:23.890
uns mit der Fixpunkttheorie auseinandersetzen.

01:22:24.790 --> 01:22:30.430
Wir werden jetzt sozusagen diese ganzen mathematischen

01:22:30.430 --> 01:22:33.130
Begriffsbildungen in die Waagschale werfen.

01:22:33.130 --> 01:22:38.470
Und wir kommen letztendlich zu zwei Theoremen, das wird Sie auch

01:22:38.470 --> 01:22:41.010
wahrscheinlich interessieren.

01:22:41.610 --> 01:22:44.850
Das eine ist von Knaster-Tarski.

01:22:47.770 --> 01:22:56.530
Der benutzt die Monotonie-Eigenschaft, um zu sagen, diese

01:22:56.530 --> 01:22:59.930
Fixpunktgleichung, die ist zumindestens lösbar.

01:23:01.330 --> 01:23:06.970
Und wir werden dann noch eins weitergehen und wir werden dann noch den

01:23:06.970 --> 01:23:08.250
Klini uns anschauen.

01:23:09.410 --> 01:23:12.550
Und der sagt, nochmal ganz ruhig, damit es noch ein bisschen Ruhe,

01:23:12.610 --> 01:23:15.970
weil ich gebe Ihnen immer schön viel Pause, da können Sie auch noch

01:23:15.970 --> 01:23:17.930
eine Minute vielleicht ausharren.

01:23:19.170 --> 01:23:23.370
Der Tarski-Knaster, der sagt, wenn es monoton ist, das Funktional,

01:23:23.650 --> 01:23:24.730
dann kriegen wir eine Lösung.

01:23:24.730 --> 01:23:29.990
Der Klini, der sagt jetzt, und wenn es auch noch stetig ist, unser

01:23:29.990 --> 01:23:34.030
Funktional, dann kriegen wir ein konstruktives Vorgehen.

01:23:34.330 --> 01:23:38.210
Dann kann ich sogar sagen, wie ich zu diesem Fixpunkt komme.

01:23:38.610 --> 01:23:41.850
Und der Fixpunkt, das ist genau die semantische Deutung von der

01:23:41.850 --> 01:23:42.730
rekursiven Funktion.

01:23:43.130 --> 01:23:45.170
Schöne Zentralübung und bis nächste Woche.

01:23:45.490 --> 01:23:45.710
Danke.