WEBVTT 00:01.340 --> 00:05.000 So, ich möchte euch herzlich begrüßen zur heutigen Zentralübung. 00:05.980 --> 00:09.120 Der Herr Scholderer lässt sich entschuldigen, der ist vorhin dort. 00:09.880 --> 00:13.180 Wir fangen heute ziemlich pünktlich an, weil wir viel Stoff haben. 00:14.720 --> 00:16.860 Trotzdem noch zwei Anmerkungen. 00:17.660 --> 00:19.480 Das eine Mal ist zur Klausuranmeldung. 00:19.940 --> 00:22.320 Ihr habt es ja schon fast alle gesehen, der Karton liegt hier vorne. 00:22.880 --> 00:25.640 Der wird auch das nächste Mal noch, sprich am Montag und Mittwoch hier 00:25.640 --> 00:25.940 liegen. 00:26.660 --> 00:29.760 Ansonsten wird es auch nochmal Hinweise geben, hauptsächlich für die 00:29.760 --> 00:30.680 Nicht -Informatiker. 00:31.260 --> 00:33.080 Auf unserer Webseite, das werde ich mit dem Herr Scholderer 00:33.080 --> 00:33.600 absprechen. 00:34.220 --> 00:36.660 Das schauen wir, dass wir die ab morgen auf der Webseite haben. 00:37.080 --> 00:39.060 Da können die Nicht-Informatiker nochmal nachlesen. 00:40.080 --> 00:42.540 Beim Fragebogen habe ich gerade nochmal einen interessanten Hinweis 00:42.540 --> 00:43.200 bekommen. 00:43.740 --> 00:47.080 Es haben bisher sehr viele mitgemacht, das finde ich wirklich klasse. 00:47.720 --> 00:49.300 Ich möchte mich auch jetzt schon mal dafür bedanken. 00:50.360 --> 00:53.840 Trotzdem der Aufruf, die, die es noch nicht gemacht haben, bitte 00:53.840 --> 00:54.440 ausfüllen. 00:55.300 --> 01:00.100 Der Fragebogen ist so strukturiert, dass sie nur mal das Lernsystem 01:00.100 --> 01:03.380 und die Technologie, die wir hier haben, mit dem Plasma-Bildschirm und 01:03.380 --> 01:07.440 Beamer, sowie im Remote-Hörsaal drüben im Informa-Neubau evaluieren. 01:08.560 --> 01:11.780 Es wird am Ende der Vorlesung nochmal ein extra Fragebogen geben. 01:12.180 --> 01:15.440 Da könnt ihr euch dann wirklich über die Übung, über die Vorlesung, 01:15.520 --> 01:19.080 über das Skript, über die Art und Weise, wie die Veranstaltung auch 01:19.080 --> 01:21.780 inhaltlich abgelaufen ist, da könnt ihr euch dann nochmal auslassen. 01:21.780 --> 01:25.140 Das heißt, wir können zwar auch jetzt schon Anmerkungen reinschreiben, 01:25.220 --> 01:27.200 ist aber nicht so sinnvoll, weil es am Schluss nochmal von der 01:27.200 --> 01:30.800 Fachschaft eine separate Befragung darüber geben wird. 01:38.600 --> 01:44.700 Wir werden heute hauptsächlich Beispiele sehen für das Übungsblatt 01:44.700 --> 01:45.300 Nummer 13. 01:46.560 --> 01:50.820 Hier werden wir auf die einzelnen Themen eingehen, wie Semantik, 01:50.880 --> 01:52.700 Recursul für Funktionsdeklaration. 01:53.380 --> 01:55.800 Das ist auch eine Aufgabe, sprechen auf dem Übungsblatt. 01:56.360 --> 01:59.200 Wir machen einen Beweis mittels Parameterinduktion. 02:00.280 --> 02:04.220 Dann zum Schluss mit den Beweisen einen Terminierungsbeweis. 02:04.860 --> 02:06.340 Der wird nicht ganz einfach sein. 02:07.260 --> 02:11.280 Ich weiß, auch im letzten Jahr, es werden dann ein oder andere hier 02:11.280 --> 02:11.700 verlassen. 02:12.160 --> 02:13.520 Lasst euch aber davon nicht abschrecken. 02:13.520 --> 02:16.520 Er ist schlimmer, als er aussieht. 02:16.940 --> 02:18.700 Das Prinzip ist eigentlich ziemlich einfach. 02:24.120 --> 02:27.880 Nur der ganze Formalismus, der dahinter steckt, der ist natürlich eher 02:27.880 --> 02:28.780 was Abschreckendes. 02:29.400 --> 02:31.020 Also ich kann das dann eher nachvollziehen. 02:32.080 --> 02:34.640 Dann haben wir noch eine leichte Aufgabe, Gültigkeit und Lebensdauer. 02:36.000 --> 02:39.940 Danach möchte ich eine kurze Pause machen, damit auch diejenigen eine 02:39.940 --> 02:43.520 Chance haben, die Java schon auf dem FF-Beherrschenden den Hörsaal 02:43.520 --> 02:44.240 verlassen zu können. 02:44.360 --> 02:47.680 Damit die anderen, die noch ein bisschen was über Java lernen möchten, 02:47.800 --> 02:51.160 dann auch in Ruhe der Aufgabe folgen können. 02:51.480 --> 02:55.360 Hier geht es hauptsächlich darum, wie definiere ich Funktionen und 02:55.360 --> 02:56.180 Prozeduren. 02:56.300 --> 02:57.580 Java heißen ja Methoden. 02:58.420 --> 03:00.860 Und wie kann ich die dann aus dem Programm heraus aufrufen. 03:04.160 --> 03:06.300 So, fangen wir mit der ersten Aufgabe an. 03:07.400 --> 03:11.080 Wir haben hier eine ganz kleine rekursive Funktion. 03:13.000 --> 03:14.660 Die dürfte eigentlich jedem bekannt sein. 03:15.880 --> 03:18.060 Und was wir hier machen müssen, ist einmal die geschlossene Form 03:18.060 --> 03:21.740 dieser Funktion zu finden und diese dann über Induktion zu beweisen. 03:24.360 --> 03:28.760 Das heißt, die Funktion dürfte wahrscheinlich aus der Analysis oder HM 03:28.760 --> 03:29.480 bekannt sein. 03:29.480 --> 03:36.960 Die macht also nichts anderes, als dass ich natürliche Zahlen von 1 03:36.960 --> 03:41.120 angefangen bis zu einem n addiere und daraus das Ergebnis bekomme. 03:41.280 --> 03:45.360 Also wenn ich n3 habe, dann heißt das 1 plus 2 plus 3 als Ergebnis 6. 03:46.520 --> 03:48.940 Und hierfür kann man eine geschlossene Formel finden und die dann 03:48.940 --> 03:49.660 wiederum beweisen. 03:52.740 --> 03:55.060 So, wie sieht so eine geschlossene Formel aus? 03:56.560 --> 03:59.420 Geschlossene Formeln zu finden, ist eigentlich eher probieren. 03:59.560 --> 04:00.780 Da gibt es kein Rezept dazu. 04:01.780 --> 04:04.880 In der Analysis oder höherer Mathematik sieht man das auch immer 04:04.880 --> 04:05.200 wieder. 04:05.920 --> 04:09.920 Es sind entsprechende Sachverhalte und der Dozent schreibt einfach die 04:09.920 --> 04:10.420 Form hin. 04:10.880 --> 04:13.140 Man meint man, der hätte sie sich so einfach aus dem Finger gezogen. 04:13.500 --> 04:14.280 So einfach ist es nicht. 04:14.420 --> 04:16.580 Da ist teilweise jahrelanger Arbeit dahinter in der Wissenschaft. 04:17.380 --> 04:20.540 Das heißt, so eine geschlossene Formel, die fällt nicht einfach vom 04:20.540 --> 04:22.640 Himmel, sondern die wird auch wirklich rumprobiert. 04:22.640 --> 04:27.060 Ich gebe es jetzt einfach mal an, wie die hier aussieht. 04:28.240 --> 04:33.800 Wir haben Sum n ist gleich, da müssen wir eine Fallunterscheidung 04:33.800 --> 04:45.740 machen, da das n Element n sein kann und das x Element n mit 04:45.740 --> 04:46.500 undefiniert. 04:47.300 --> 04:49.540 Gehen wir nochmal eins zurück, dann sehen wir auch warum. 04:49.540 --> 04:55.340 Ich habe hier eine natürliche Zahl. 04:55.520 --> 04:58.060 Wenn ich hier einen Integer-Wert eingebe, ist das Ergebnis natürlich 04:58.060 --> 04:58.720 undefiniert. 04:59.000 --> 05:00.620 Deshalb muss ich dieses Symbol mit einführen. 05:02.940 --> 05:08.600 Das heißt, wenn ich undefiniert eingebe, das heißt x gleich 05:08.600 --> 05:10.940 undefiniert, kommt natürlich undefiniert heraus. 05:12.180 --> 05:16.200 Oder, da ich jetzt mal die Summenformel nur bis zu einem bestimmten n 05:16.200 --> 05:22.040 betrachte, ist es natürlich dann auch der Fall, wenn x größer n ist. 05:22.820 --> 05:25.340 Das heißt, wenn ich meine Summenformel nur bis 5 definiere und ich 05:25.340 --> 05:27.720 gebe 6 ein, dann funktioniert es natürlich nicht mehr. 05:28.840 --> 05:30.980 So, die geschlossene Formel sieht dann wie folgt aus. 05:31.640 --> 05:36.600 Ich habe x mal x plus 1 durch 2. 05:37.380 --> 05:45.120 Und dies gilt, wenn x gültig ist, also undefiniert, und x im 05:45.120 --> 05:47.600 Wertebereich liegt, also x kleiner gleich n. 05:49.100 --> 05:51.620 Die Formel kann man wieder an dem Beispiel 3 nachvollziehen. 05:52.100 --> 05:56.360 3 plus 1 ist 4 durch 2 ist 2 mal 3 ist 6. 05:56.560 --> 05:58.500 Das heißt, das, was ich vorher summiert habe, kann ich jetzt direkt 05:58.500 --> 05:59.560 über die Formel ausrechnen. 06:00.580 --> 06:04.500 So, wie beweise ich nun, dass diese geschlossene Formel für die vorher 06:04.500 --> 06:07.680 präkursiv definierte Funktion korrekt ist? 06:08.260 --> 06:11.380 Hierzu haben wir erstmal unseren Induktionsanfang. 06:13.180 --> 06:14.120 n gleich 1. 06:15.220 --> 06:22.000 Das heißt, für alle x, die aus der entsprechenden Menge n kommen, mit 06:22.000 --> 06:26.660 undefiniert, habe ich nun folgendes. 06:27.200 --> 06:29.000 Ich muss jetzt die Fälle abarbeiten. 06:29.220 --> 06:31.980 Das heißt, es kommt eine ungültige Eingabe, sprich x gleich 06:31.980 --> 06:32.680 undefiniert. 06:34.960 --> 06:40.440 Dann gilt für n gleich 1, das wäre in dem Fall Sum 1 von x. 06:44.000 --> 06:48.300 Nach meiner oberen Behauptung, das zeige ich mal mit 06:48.300 --> 06:52.300 Induktionshypothese, nach meiner oberen Behauptung setze ich 06:52.300 --> 06:54.180 undefiniert ein, habe ich den ersten Fall. 06:54.620 --> 06:58.220 Das heißt, es kommt wieder undefiniert heraus, was ja auch zu erwarten 06:58.220 --> 06:58.460 war. 06:59.560 --> 07:03.680 Ist x nun größer 1, habe ich genau das gleiche. 07:04.820 --> 07:08.720 Das heißt, x liegt nicht mehr in meinem Wertebereich und ich bekomme 07:08.720 --> 07:09.840 ebenfalls undefiniert. 07:11.340 --> 07:18.240 So, für den Fall x gleich 1, auch wieder setze ich ein. 07:19.160 --> 07:23.240 In Sum 1 kann ich das x direkt in die Formel einsetzen. 07:23.340 --> 07:24.320 Ich mache es mal hier ausführlich. 07:24.320 --> 07:30.540 Habe ich 1 mal 1 plus 1 halbe und ich bekomme raus 1. 07:30.620 --> 07:35.120 Ist natürlich klar, 1 addiert, in dem Fall ohne nichts ist natürlich 07:35.120 --> 07:35.680 wieder 1. 07:36.940 --> 07:40.860 Also den Induktionsanfang haben wir soweit hinter uns gebracht. 07:50.540 --> 07:52.360 Zurück kommen wir zum Induktionsschluss. 07:53.200 --> 07:56.720 Induktionsschluss heißt, ich muss jetzt die Funktion, die geschlossene 07:56.720 --> 08:00.500 Formel beweisen, indem ich von n auf n plus 1 schließe. 08:03.860 --> 08:09.880 Das heißt, n nach n plus 1, das habe ich in meiner geschlossenen 08:09.880 --> 08:10.340 Formel. 08:10.820 --> 08:14.360 Das heißt, hier kommt jetzt meine Induktionsbehauptung ins Spiel, die 08:14.360 --> 08:15.220 ich hier oben habe. 08:18.120 --> 08:21.280 In dem Fall aber mit n plus 1. 08:23.060 --> 08:24.860 Das heißt dann wie folgt, 08:27.920 --> 08:34.440 Sum n plus 1 von x, hier muss ich wieder meine Fallunterscheidung 08:34.440 --> 08:44.280 machen, ist natürlich undefiniert, falls x selber undefiniert ist oder 08:44.280 --> 08:45.920 x nicht im Wertebereich liegt. 08:46.380 --> 08:48.800 Der Wertebereich ist diesmal n plus 1. 08:51.980 --> 08:55.660 Ansonsten kann ich natürlich die vorherige Funktion nehmen. 08:56.280 --> 08:59.800 Das heißt, bei Sum n plus 1 kann ich ja ein x mehr nehmen. 08:59.940 --> 09:02.420 Das heißt, wenn ich vorher 5 hatte, kann ich jetzt mit 6 weitermachen. 09:02.880 --> 09:04.760 Für 5 kenne ich ja das Ergebnis. 09:05.480 --> 09:13.080 Da kann ich nämlich Sum n nehmen und diesmal von x minus 1 und dazu 09:13.080 --> 09:14.900 addiere ich einfach mein x. 09:15.900 --> 09:22.480 Und dies gilt, wenn x gültig ist und im Wertebereich liegt. 09:25.840 --> 09:28.760 Das heißt, x kleiner gleich n plus 1. 09:30.520 --> 09:34.000 So, als nächsten Schritt kommt jetzt nur noch reine Mathematik. 09:35.280 --> 09:37.700 Das heißt, ich muss eigentlich diesen Term nur noch entsprechend 09:37.700 --> 09:41.880 umformen und dann entsprechend auf mein Ergebnis kommen, was da heißen 09:41.880 --> 09:45.860 soll, dass Sum n plus 1 natürlich der Induktionshypothese genügt. 09:46.260 --> 09:48.860 In dem Fall natürlich wieder die geschlossene Formel herauskommt, x 09:48.860 --> 09:50.040 mal x plus 1 halber. 09:51.460 --> 09:52.440 So, wie kommt man da hin? 09:54.380 --> 10:00.300 Wir nehmen wieder die geschlossene Formel, Sum n plus 1 von x. 10:03.500 --> 10:06.760 Mit der Fallunterscheidung, dies wieder wie oben. 10:13.980 --> 10:16.740 So, nun kommt der interessantere Teil, der gültige Teil. 10:18.020 --> 10:22.980 Das heißt, mein x plus bleibt und mein Sum n von x minus 1 kann ich 10:22.980 --> 10:25.280 nun durch die Induktionsbehauptung natürlich ersetzen. 10:27.720 --> 10:32.260 Das heißt, hier bekomme ich dann diesmal aber eingesetzt x minus 1. 10:33.360 --> 10:35.560 Das heißt, ich muss dieses hier einsetzen. 10:37.540 --> 10:41.980 Das heißt, x minus 1 in meine Formel eingesetzt mal 10:45.670 --> 10:51.930 x plus 1 minus 1 halber. 10:53.070 --> 10:59.730 Gilt natürlich hier auch wieder, wenn x definiert ist und wenn x im 10:59.730 --> 11:00.850 Gültigkeitsbereich ist. 11:03.010 --> 11:05.070 So, jetzt machen wir eine kleine Nebenrechnung. 11:06.930 --> 11:12.910 Jetzt nehme ich genau diesen Term hier heraus und kann den nun 11:12.910 --> 11:14.130 entsprechend umformen. 11:14.430 --> 11:29.190 Das heißt, ich habe x plus x minus 1 mal x plus 1 minus 1 durch 2. 11:29.870 --> 11:31.910 Jetzt kann ich entsprechend die Mathematik anwenden. 11:35.940 --> 11:44.680 Das heißt, das hier wird natürlich zu 0 und was ich dann habe ist x 11:44.680 --> 11:48.880 mal x minus 1 in diesem Term. 11:51.380 --> 11:59.000 Als Ergebnis bekomme ich hier x plus das gleich ausgerechnet x Quadrat 11:59.000 --> 12:01.860 minus x durch 2. 12:04.640 --> 12:08.440 Ist in diesem Fall ein 12:11.820 --> 12:12.880 kleiner Zwischenschritt noch. 12:13.040 --> 12:20.700 Das heißt, ich kann dieses x hier entsprechend erweitern mit 2x durch 12:20.700 --> 12:30.780 2 plus x Quadrat halber minus x halber. 12:31.060 --> 12:31.980 Wir kommen dann raus. 12:32.480 --> 12:35.060 x Quadrat plus x halber. 12:37.000 --> 12:41.140 Das x kann ich wieder ausklammern und ich bekomme x mal x plus 1 12:41.140 --> 12:42.180 halber. 12:42.580 --> 12:44.400 Das ist genau das, was ich eigentlich bekommen möchte. 12:47.120 --> 12:49.880 Jetzt warte ich noch einen Moment, bevor ich die neue Folie anfange. 12:52.980 --> 12:55.220 Für diejenigen, die es hier von uns abschreiben möchten. 12:57.780 --> 13:00.260 Das heißt, genau diesen Term, den ich jetzt hier unten habe, 13:05.740 --> 13:12.080 diesen Term setze ich jetzt entsprechend hier oben ein. 13:12.700 --> 13:13.880 Das ist ja genau das Ergebnis. 13:13.880 --> 13:24.220 Und ich habe durch Induktion dann bewiesen, dass die geschlossene 13:24.220 --> 13:26.940 Formel so stimmt, wie ich mir vorher ausgedacht habe. 13:27.740 --> 13:36.260 Das heißt, als Ergebnis bekomme ich raus, zum n plus 1 von x ist 13:36.260 --> 13:39.000 gleich wieder der undefinierte Fall. 13:42.280 --> 13:46.340 Das heißt, x undefiniert oder x nicht im Wertebereich. 13:51.000 --> 14:00.040 Und für den definierten Fall x mal x plus 1 halber, wenn x definiert 14:00.040 --> 14:01.740 ist und im Wertebereich liegt. 14:05.780 --> 14:12.100 Zur Vollständigkeit kann man natürlich jetzt die richtig geschlossene 14:12.100 --> 14:13.600 Formel angeben ohne die n. 14:13.820 --> 14:16.220 Das heißt, für alle n Elementen der natürlichen Menge. 14:17.020 --> 14:20.100 Das würde dann heißen, zum x ist gleich, indem ich einfach den 14:20.100 --> 14:21.220 Wertebereich aufhebe. 14:21.860 --> 14:26.600 Das heißt, der Wertebereich von 14:30.660 --> 14:35.260 x war ja x kleiner gleich n plus 1. 14:35.580 --> 14:39.240 Den hebe ich einfach auf und daraus kann ich dann die geschlossene 14:39.240 --> 14:40.580 Formel für alle n hinschreiben. 14:41.060 --> 14:42.500 Wieder der undefinierte Fall. 14:43.500 --> 14:46.360 In dem Fall natürlich nur undefiniert, denn den Wertebereich habe ich 14:46.360 --> 14:46.960 aufgehoben. 14:47.360 --> 14:49.920 Das heißt, diese Bedingung hier ist nicht mehr gültig. 14:51.560 --> 14:57.940 Und für den definierten Fall heißt es dann entsprechend die Formel. 14:58.660 --> 15:01.500 Für den Fall x ist definiert. 15:03.600 --> 15:06.740 So, das war jetzt nun der Beweis für die Semantik Rekursiver 15:06.740 --> 15:07.620 Funktionsdeklaration. 15:08.360 --> 15:10.520 Auf dem Übungsblatt haben wir ein bisschen eine andere Rekursiver 15:10.520 --> 15:10.860 Funktion. 15:11.000 --> 15:12.140 Da haben wir auch zwei Parameter. 15:12.780 --> 15:14.420 Da gibt es dann einige Fallunterscheidungen. 15:14.760 --> 15:16.760 Das heißt, ihr müsst den Beweis dann komplett mit den 15:16.760 --> 15:19.700 Fallunterscheidungen durchführen, um entsprechend auf die Lösung zu 15:19.700 --> 15:19.940 kommen. 15:20.500 --> 15:23.900 Die geschlossene Formel ist schon vorgegeben auf dem Übungsblatt. 15:24.260 --> 15:26.640 Das heißt, die braucht ihr euch nicht mal neu überlegen. 15:30.260 --> 15:33.040 So, bevor wir zur nächsten Aufgabe kommen... 15:37.780 --> 15:38.820 Tut mir leid. 15:40.800 --> 15:42.440 Wenn jetzt der ganze Hörsaal Hey! 15:42.540 --> 15:43.860 geschrien hätte, wäre ich zurückgegangen. 15:48.380 --> 15:48.740 So. 15:51.880 --> 15:53.200 So, ihr habt eine gute Lobby. 15:59.920 --> 16:01.580 So, dann hoffe ich, dass wir soweit sind. 16:02.100 --> 16:03.140 Dann können wir nämlich weitermachen. 16:03.800 --> 16:07.520 Ich werde nochmal ganz kurz die Definition von der repetitiven 16:07.520 --> 16:08.680 Rekursion zeigen. 16:09.080 --> 16:12.100 Von der Vorlesung, weil die nun Grundlage ist für den nächsten Beweis. 16:12.660 --> 16:14.720 Und zwar für den Beweis mit der Parameterinduktion. 16:18.090 --> 16:25.330 So, bei der repetitiven Funktion haben wir ja eine entsprechende neue 16:25.330 --> 16:25.970 Eigenschaft. 16:26.690 --> 16:32.770 Die Eigenschaft lautet, dass bei jedem rekursiven Aufruf die 16:32.770 --> 16:37.490 eigentliche Berechnung in der äußerst letzten Aktion erfolgt. 16:37.490 --> 16:43.150 Das heißt, in dem Fall ist das hiermit versteckt. 16:43.850 --> 16:46.930 Und in meiner repetitiven Rekursion muss ich das entsprechend 16:46.930 --> 16:47.630 umformulieren. 16:48.170 --> 16:49.730 Dazu brauche ich einen neuen Parameter. 16:49.830 --> 16:52.470 Der neue Parameter heißt R, den ich hiermit einführen muss. 16:57.950 --> 17:00.790 Und wenn ich das umformuliere, dann bekomme ich Folgendes raus. 17:02.630 --> 17:05.810 Ich nenne jetzt einfach die Summe X-Sum. 17:07.390 --> 17:09.250 Macht aber natürlich genau das Gleiche. 17:10.010 --> 17:12.110 Ich habe den Parameter X nach wie vor. 17:13.010 --> 17:16.830 Den neuen Parameter R vom gleichen Wertebereich, sprich natürliche 17:16.830 --> 17:18.270 Zahlen, zurück. 17:18.690 --> 17:20.790 Kommen soll natürlich eine natürliche Zahl. 17:21.390 --> 17:22.950 Habe nun meine Fallunterscheidung. 17:24.790 --> 17:30.830 Das heißt, wenn X gleich 1 ist, dann soll R plus 1 zurückgegeben 17:30.830 --> 17:31.090 werden. 17:31.230 --> 17:32.010 Kommen wir gleich dazu. 17:34.490 --> 17:38.150 Ansonsten wird die Funktion X-Sum wieder aufgerufen. 17:39.290 --> 17:45.110 Mit X minus 1 und dem neuen Parameter R plus X. 17:47.130 --> 17:50.390 Das heißt, die Rekursion ist jetzt hier unten versteckt. 17:52.010 --> 17:56.030 Ich muss natürlich jetzt, wenn ich die Rekursion aufrufe, mit R gleich 17:56.030 --> 17:56.790 0 aufrufen. 17:57.250 --> 18:04.790 Wenn ich hier als Beispiel wieder X gleich 3 eingebe und R 0, bekomme 18:04.790 --> 18:06.450 ich natürlich 6 heraus. 18:06.450 --> 18:09.370 Das heißt, 3, ich gehe hier unten rein, habe ich 2. 18:10.430 --> 18:11.810 Läuft die Rekursion durch. 18:12.930 --> 18:14.590 Hier unten wird die ganze Sache addiert. 18:15.190 --> 18:17.030 Nächstes Mal hat sich der Parameter verringert. 18:17.630 --> 18:19.970 Das heißt, hier unten kriege ich dann immer mein einiges 18:19.970 --> 18:20.830 Rechenergebnis. 18:21.450 --> 18:24.430 Und ganz zum Schluss, wenn natürlich X 1 ist, komme ich hier nicht 18:24.430 --> 18:26.270 mehr rein auf den Aufruf, sondern lande hier. 18:26.610 --> 18:28.330 Und muss deshalb diese 1 hier dazu addieren. 18:29.370 --> 18:32.430 Wenn das R natürlich von vornherein nicht 0 ist, dann habe ich 18:32.430 --> 18:34.830 natürlich entsprechend dem R höheres Ergebnis. 18:38.290 --> 18:41.670 So, das war jetzt die Voraussetzung für den Beweis mittels 18:41.670 --> 18:42.770 Parameterinduktion. 18:44.030 --> 18:53.170 Da werden wir jetzt genau diese repetitive Rekursion mit der 18:53.170 --> 18:54.490 Parameterinduktion beweisen. 18:55.550 --> 18:59.210 Das heißt, der Beweis geht nun über das R. 18:59.870 --> 19:06.930 Das heißt, wir machen eine Induktion entsprechend dieser repetitiven 19:06.930 --> 19:07.550 Rekursion. 19:12.750 --> 19:15.690 So, ich habe es hier nochmal in Klartext hingeschrieben. 19:16.730 --> 19:19.630 Wir verwenden das Prinzip der Parameterinduktion, wie erwähnt. 19:21.190 --> 19:25.510 Das heißt, was ich eigentlich beweisen möchte, ist, dass meine 19:25.510 --> 19:30.850 ursprüngliche Rekursion, die ich hatte, mit dem Zusatz des Parameters 19:30.850 --> 19:36.050 R nun auch gilt für meine neue Rekursion, die repetitive Rekursion. 19:37.450 --> 19:39.890 Und das mache ich natürlich jetzt mittels Induktion. 19:42.090 --> 19:45.870 So, mein Induktionsanfang ist x gleich 1. 19:47.970 --> 19:50.690 Meine Induktionsbehauptung habe ich nochmal hier oben hingeschrieben, 19:50.970 --> 19:52.030 das ist die Gleichung 1. 19:54.250 --> 20:02.130 Das heißt, R von Sum 1, ist natürlich klar, ist R plus 1, ist auch 20:02.130 --> 20:07.890 ganz einfach, ist diesmal x Sum von 1, R. 20:08.650 --> 20:11.750 Das heißt, ich kann das R auch wirklich ganz allgemein betrachten, ich 20:11.750 --> 20:13.370 muss gar keine konkreten Werte hier angeben. 20:14.710 --> 20:21.930 So, die Induktionshypothese ist dann hier oben nochmal angedeutet und 20:21.930 --> 20:25.170 für den Induktionsschluss habe ich x nach x plus 1. 20:26.370 --> 20:32.810 Das heißt, ich versuche nun zu beweisen, dass R plus Sum x plus 1 20:32.810 --> 20:35.010 entsprechend gilt. 20:35.790 --> 20:38.230 Bei den Rekursionen kann man sicher immer ein kleines Hilfsmittel 20:38.230 --> 20:41.650 nehmen, in der Mathematik ist das auch immer zulässig. 20:41.650 --> 20:43.730 Wenn ich einen Beweis führe, kann ich den von oben und von unten 20:43.730 --> 20:44.490 zusammenführen. 20:44.970 --> 20:48.990 Das heißt, mein Ziel unten, was rauskommen soll, das weiß ich 20:48.990 --> 20:53.770 natürlich, das muss ich beweisen, x Sum x plus 1, R. 20:54.930 --> 20:59.190 Das heißt, wenn ich jetzt in meiner Berechnung, wenn ich hier von oben 20:59.190 --> 21:02.050 herkomme in die Richtung, irgendwann ein Sturmgerät, ist es natürlich 21:02.050 --> 21:04.670 absolut legitim, von unten herzukommen. 21:05.390 --> 21:08.150 Das ist auch eigentlich wichtig für die Klausur, wenn so ein Beweis 21:08.150 --> 21:08.690 drankommt. 21:08.690 --> 21:11.310 Dann kann man nämlich damit deutlich machen, dass man es im Grundsatz 21:11.310 --> 21:12.890 eigentlich verstanden hat, um was es geht. 21:13.290 --> 21:15.990 Aber man hat es vielleicht aus mathematischen Gründen nicht geschafft, 21:16.050 --> 21:19.290 die beiden Gleichungen so zu zeigen, dass sie auch wirklich gleich 21:19.290 --> 21:19.530 sind. 21:22.250 --> 21:23.470 So, was heißt es nun? 21:26.510 --> 21:28.790 R plus bleibt stehen, Sum x plus 1. 21:29.330 --> 21:36.990 Das x plus 1 kann ich hier rausziehen und habe noch als zweiten 21:36.990 --> 21:38.130 Summand Sum x. 21:39.370 --> 21:41.730 Jetzt habe ich eigentlich nur noch mathematische Umformen. 21:42.910 --> 21:45.690 Das x plus 1 ziehe ich nach vorne, vertausche es gerade mit R. 21:49.790 --> 21:51.750 Das heißt, hier hat sich nichts groß geändert. 21:53.610 --> 22:02.030 Ziehe das R und das Sum x zusammen, das heißt x plus 1 bleibt stehen. 22:02.710 --> 22:08.990 Schreibe nun in Klammer R plus x Sum von x. 22:10.790 --> 22:15.310 Und bekomme dann heraus x 22:19.180 --> 22:28.700 plus 1 plus x Sum mit dem Parameter nun x von R. 22:32.420 --> 22:37.100 Ja, Entschuldigung, dieses hier, das ist zu viel. 22:38.200 --> 22:43.360 So, und damit habe ich die Sache eigentlich bewiesen. 22:43.820 --> 22:45.880 Was ich nun habe, ist natürlich ganz klar. 22:47.000 --> 22:48.980 Der letzte Schritt ist ja schon angedeutet hier unten. 22:50.640 --> 22:54.420 Ich habe das x plus 1, das ich jetzt nun hier mit dem x Sum x und R 22:54.420 --> 22:57.860 hereinziehen kann und bekomme daraus x Sum x plus 1, R. 22:58.260 --> 22:59.560 Genau das, was zu beweisen war. 23:01.820 --> 23:04.260 Gut, dann lasst es noch einen Moment stehen, damit ihr wieder alle 23:04.260 --> 23:04.960 abschreiben könnt. 23:06.440 --> 23:11.980 Wir kommen nun zu dem schwersten Beweis für heute, für den 23:11.980 --> 23:12.940 Terminierungsbeweis. 23:14.040 --> 23:18.080 Herr Abeck hat es ganz kurz am Ende seiner Vorlesung heute angedeutet, 23:18.140 --> 23:19.140 was die Bedingung ist. 23:19.800 --> 23:25.880 Die Bedingung ist einfach, ich muss nun beweisen, dass meine Rekursion 23:25.880 --> 23:26.220 terminiert. 23:26.980 --> 23:28.880 Dazu brauche ich eine Abstiegsfunktion. 23:28.880 --> 23:32.880 Diese Abstiegsfunktion ist meine Obergrenze. 23:34.600 --> 23:39.680 Das heißt, wenn ich beweisen kann, dass die Abstiegsfunktion nun und 23:39.680 --> 23:43.600 wo entfallend ist und ich noch zusätzlich beweisen kann, dass meine 23:43.600 --> 23:47.220 eigentliche Rekursion immer kleiner ist wie die Abstiegsfunktion, dann 23:47.220 --> 23:50.040 kann ich daraus folgern, dass auch meine eigentliche Rekursion 23:50.040 --> 23:50.620 terminiert. 23:51.520 --> 23:52.900 Dies wollen wir jetzt einfach mal versuchen. 23:55.260 --> 23:57.720 Hierzu erst noch mal ein praktisches Beispiel. 23:58.200 --> 24:00.880 Die Schwierigkeit hier dran ist nämlich, wie finde ich so eine 24:00.880 --> 24:02.800 Abstiegsfunktion, die diese Bedingungen erfüllt. 24:03.360 --> 24:05.220 Das ist eigentlich gar nicht so leicht, da muss man auch wieder 24:05.220 --> 24:05.860 herumprobieren. 24:06.360 --> 24:09.000 Die fällt einem eigentlich gar nicht einfach in den Schoß, sondern 24:09.000 --> 24:10.260 muss man einfach ein bisschen beobachten. 24:10.840 --> 24:13.680 Und ich gebe jetzt mal so ein kleines Schema vor, das euch hoffentlich 24:13.680 --> 24:17.060 auch hilft für die Lösung auf dem Übungsplatz, weil da die 24:17.060 --> 24:19.000 Abstiegsfunktion natürlich ein bisschen anders aussieht. 24:20.080 --> 24:22.080 So, nehmen wir mal das Beispiel 5. 24:23.300 --> 24:27.840 Dann habe ich eigentlich folgendes, dass ich pro Rekursion, wenn ich 24:27.840 --> 24:32.400 hier reingehe, ich male es mal mit blau, pro Rekursion, die ich 24:32.400 --> 24:36.180 reingehe, verringert sich natürlich meine ursprüngliche Parameter um 24:36.180 --> 24:36.600 1. 24:37.080 --> 24:42.740 Das heißt hier habe ich x-1, nächsten Rekursionsschritt habe ich 4, 3, 24:43.100 --> 24:47.480 2, 1 und dann terminiert ja die Rekursion. 24:48.500 --> 24:50.760 So, hier kann ich jetzt folgende Beobachtung machen. 24:52.740 --> 24:58.200 Von diesen Werten hier muss ich eine Obergrenze finden und die 24:58.200 --> 25:00.360 Obergrenzen bei diesem Beispiel ist natürlich 5. 25:00.620 --> 25:03.000 Das heißt, keiner dieser Werte wird jemals größer als 5. 25:04.300 --> 25:08.180 Das heißt, ich mache eine Abschätzung, jeweils mit 5. 25:08.180 --> 25:17.790 Und wenn ich das jetzt mal betrachte, dann habe ich hier 5 mal 5 25:17.790 --> 25:23.270 stehen und 5 mal 5 ist 25. 25:23.850 --> 25:25.990 Wenn ich das jetzt noch für andere Beispiele mache, dann bekomme ich 25:25.990 --> 25:27.050 was ganz ähnliches raus. 25:27.670 --> 25:33.410 Wenn ich 4 einsetze, ist unten die obere Grenze ebenfalls immer 4 und 25:33.410 --> 25:34.430 das Ergebnis ist 16. 25:36.210 --> 25:41.630 Das heißt, bei 4 habe ich 16, bei 3 habe ich 9 und so weiter. 25:42.410 --> 25:46.090 Das heißt, ich könnte daraus schließen, dass meine Abstiegsfunktion x² 25:46.090 --> 25:46.570 ist. 25:47.010 --> 25:51.510 Im allgemeinen Fall würde das einfach heißen, ich setze hier mein x 25:51.510 --> 25:59.170 ein, im nächsten Rekursionsschritt habe ich x-1, x-2, x-3 und so 25:59.170 --> 25:59.430 weiter. 25:59.550 --> 26:01.910 Das heißt, mein x wird immer kleiner, es wird nie größer als x. 26:01.910 --> 26:04.770 Und das kann ich natürlich entsprechend abschätzen, jedes Mal durch x 26:04.770 --> 26:07.510 und das x Mal. 26:08.970 --> 26:13.090 Und meine Vermutung ist nun einfach, dass die Abstiegsfunktion x² ist. 26:14.050 --> 26:16.910 Ich gebe nachher auch nochmal einen Hinweis für die eigentliche 26:16.910 --> 26:19.210 Aufgabe auf dem Übungsblatt, wie man da eigentlich am geschicktesten 26:19.210 --> 26:21.650 vorgeht, damit ihr genau diese Abstiegsfunktion herausfindet. 26:22.950 --> 26:26.450 Das heißt, unsere Beobachtung ist einfach, dass wir versuchen nun 26:26.450 --> 26:29.010 diese Rekursion mit x² abzuschätzen. 26:29.730 --> 26:31.270 Schreiben wir das mal formal hin. 26:32.010 --> 26:37.170 Die Abstiegsfunktion ist h, geht hier von den natürlichen Zahlen auf 26:37.170 --> 26:45.630 die natürliche Zahl und wird nun dargestellt durch h von x gleich x². 26:49.170 --> 26:51.170 Das soll unsere Gleichung 1 sein. 26:55.780 --> 26:58.120 So, ich glaube diesmal gab es nicht so viel zu schreiben, könnte ich 26:58.120 --> 26:58.840 gleich weitermachen. 26:59.900 --> 27:01.960 So, jetzt kommen die Induktions... 27:05.160 --> 27:06.300 Gehen wir nochmal zurück. 27:07.080 --> 27:09.560 Also bisher war es wirklich noch leicht, jetzt wird es erst schwierig. 27:11.760 --> 27:15.180 Ich glaube die Beobachtung, die sollte man auch zumindest jeder selber 27:15.180 --> 27:15.700 hinbekommen. 27:16.100 --> 27:18.680 Wenn nachher der Beweis scheitert, würde ich sagen, das ist noch 27:18.680 --> 27:21.320 akzeptabel, aber die Beobachtung, da sollte man auch glaube ich drauf 27:21.320 --> 27:21.560 kommen. 27:22.880 --> 27:25.920 Weil letztendlich, wenn man so eine Funktion, so eine rekursive 27:25.920 --> 27:28.460 Funktion mal selber definiert, muss man sich ja auch schließlich 27:28.460 --> 27:31.720 Gedanken machen, was die rekursive Funktion natürlich letztendlich 27:31.720 --> 27:32.260 machen soll. 27:35.080 --> 27:42.380 Okay, das heißt, meine Induktionshypothese ist, dass meine 27:42.380 --> 27:46.320 Abstiegsfunktion immer kleiner ist einer gewissen oberen Schranke und 27:46.320 --> 27:52.920 dass ich daraus folgern kann, dass meine Funktion, in diesem Fall sum 27:52.920 --> 27:54.600 von x, terminiert. 27:55.220 --> 27:59.680 Das stellen wir dar, indem ein korrektes Ergebnis rauskommt, das heißt 27:59.680 --> 28:00.880 kein undefiniertes Ergebnis. 28:00.880 --> 28:04.840 Ein undefiniertes Ergebnis wäre natürlich auch, wenn die Rekursion 28:04.840 --> 28:05.540 nicht terminiert. 28:05.700 --> 28:08.200 Das heißt, da können die stundenlang vorm Rechner sitzen, ich würde 28:08.200 --> 28:10.200 einfach kein Ergebnis bekommen. 28:11.880 --> 28:18.960 Das muss natürlich gelten für die obere Schranke aus n, das heißt für 28:18.960 --> 28:26.760 alle obere Schranken existiert ein x, muss es ein x geben aus n, die 28:26.760 --> 28:28.040 genau diese Gleichung erfüllt. 28:31.770 --> 28:34.570 So, diese Gleichung ist unsere Gleichung 2. 28:37.150 --> 28:40.070 Informell heißt das einfach, ich hab's vorher schon mal erwähnt, die 28:40.070 --> 28:42.550 Abstiegsfunktion muss monoton fallen sein. 28:43.930 --> 28:50.810 Das heißt, h von xk, dazu komme ich gleich, muss immer größer sein als 28:50.810 --> 28:52.950 h von xk plus 1. 28:53.750 --> 28:57.810 Das k soll ja andeuten, dass ich vom einen Rekursionsschritt zum 28:57.810 --> 28:58.470 anderen komme. 28:59.250 --> 29:03.910 Das ist mein k der Rekursionsschritt, das ist mein k plus 1 erster 29:03.910 --> 29:04.190 Rekursionsschritt. 29:05.410 --> 29:09.810 Wenn ich bei 5 bin, dann habe ich also insgesamt 5 Rekursionsschritte, 29:10.290 --> 29:14.710 das heißt k wäre in dem Fall 1, mein erster Rekursionsschritt, k plus 29:14.710 --> 29:16.190 1 wäre mein zweiter Rekursionsschritt. 29:17.370 --> 29:21.510 Und genau über diese Rekursionsschritte werden wir nun den Beweis 29:21.510 --> 29:22.670 mittels Induktion führen. 29:22.950 --> 29:31.330 Das heißt, mein Induktionsanfang liegt beim ersten Rekursionsschritt. 29:32.530 --> 29:38.150 Das heißt, meine Abstiegsfunktion h von x muss kleiner gleich sein, 29:38.430 --> 29:42.250 der ersten oberen Grenze von dem Rekursionsschritt. 29:43.390 --> 29:47.950 Wenn ich nochmal zurückgehe, dann haben wir gesehen, der erste obere 29:47.950 --> 29:51.330 Grenze des Rekursionsschritts ist 5 und wird stetig kleiner. 29:52.470 --> 29:57.190 Das heißt, ich kann das ja ganz allgemein hinschreiben, dass meine 29:57.190 --> 29:59.910 obere Grenze natürlich abhängig ist vom ersten Rekursionsschritt. 30:02.470 --> 30:08.770 Setze ich meine Werte ein, heißt das, x Quadrat muss kleiner sein als 30:08.770 --> 30:09.610 die obere Grenze. 30:11.330 --> 30:16.130 Wenn ich hier dies nun für x gleich 1 mache, was ja identisch ist mit 30:16.130 --> 30:19.630 dem ersten Rekursionsschritt für den Induktionsanfang, 30:23.190 --> 30:29.770 habe ich h von 1 ist gleich 1 mal 1, also 1 Quadrat ist 1, ist kleiner 30:29.770 --> 30:30.690 gleich o von k. 30:30.690 --> 30:36.890 Gilt natürlich immer, da o aus den natürlichen Zahlen ist und ich 30:36.890 --> 30:41.450 somit diese Bedingung für alle o von k natürlich richtig ist. 30:42.190 --> 30:45.290 Daraus kann ich dann auch die Schlussfolgerung ziehen, die notwendig 30:45.290 --> 30:45.610 ist. 30:47.430 --> 30:54.390 Das heißt, Sum von 1 ist 1, das heißt determiniert und ist somit 30:54.390 --> 30:56.610 ungleich undefiniert. 30:58.010 --> 31:02.710 Das war der Induktionsanfang, für den Induktionsschritt kommt nun k 31:02.710 --> 31:05.050 nach k plus 1. 31:06.230 --> 31:09.870 Das heißt, was ich jetzt zeigen muss, ist genau wieder das gleiche wie 31:09.870 --> 31:13.710 oben, nur diesmal wie oben heißt wie diese Funktion. 31:15.410 --> 31:18.710 Das heißt, hieran ändert sich nichts. 31:19.650 --> 31:29.530 Zu zeigen, h von xk, größer, h von xk plus 1, diesmal für einen 31:29.530 --> 31:30.730 beliebigen Rekursionsschritt. 31:32.230 --> 31:34.990 Das heißt, die Rekursionsschritte, die erhöhen sich ja. 31:35.990 --> 31:40.890 Machen wir das mal an einem Beispiel, mit unserem x gleich 5. 31:42.330 --> 31:43.790 Da habe ich als obere Schranke, 31:48.080 --> 31:56.200 obere Schranke 25, Entschuldigung, x gleich 4. 31:56.920 --> 32:02.680 Jetzt fällt die obere Schranke, ist 16 und so weiter. 32:06.080 --> 32:08.260 So, jetzt lasse ich euch noch einen Moment Zeit, dass ihr nochmal 32:08.260 --> 32:09.220 hiermit abschreiben könnt. 32:15.090 --> 32:17.470 Also letztendlich kommt es da wirklich auch drauf an, das steht auch 32:17.470 --> 32:20.730 im Skript auf der einen Folie, dass man die Eigenschaften nachweist. 32:21.030 --> 32:23.750 Das heißt, ich muss so eine Abstiegsfunktion finden, die auch die 32:23.750 --> 32:24.550 Eigenschaft hat. 32:25.890 --> 32:28.390 In dem Beweis mache ich dann im Prinzip zwei Sachen auf einmal. 32:28.770 --> 32:31.690 Ich beweise, dass die Rekursion terminiert und beweise gleichzeitig, 32:31.870 --> 32:34.090 dass die Abstiegsfunktion die entsprechenden Eigenschaften hat. 32:36.690 --> 32:39.490 So, ich gehe mal weiter auf die nächste Folie, wenn es okay ist. 32:43.940 --> 32:57.160 Das heißt, meine obere Schranke des ersten Rekursionsschrittes OK, 33:05.900 --> 33:08.120 beziehungsweise zu der Bezeichnung komme ich gleich, dann hat man es 33:08.120 --> 33:12.420 nachher ein bisschen einfacher, xk gleich z. 33:13.000 --> 33:16.580 Das xk meint jetzt bloß, dieses x, dass es gültig ist in diesem 33:16.580 --> 33:17.080 Rekursionsaufruf. 33:20.640 --> 33:25.760 Wobei z natürlich hier wieder der Vollständigkeit halber aus n ist. 33:27.640 --> 33:33.420 Das heißt, meine Abstiegsfunktion h von x von k muss kleiner gleich 33:33.420 --> 33:35.480 sein der oberen Grenze. 33:36.460 --> 33:44.600 Das heißt, h von z, das wäre jetzt genau mein x in dem ersten 33:44.600 --> 33:50.680 Rekursionsschritt, ist natürlich z mal z, ist gleich z Quadrat. 33:56.060 --> 34:02.890 So, meine obere Schranke im zweiten Rekursionsschritt, 34:14.210 --> 34:17.210 da wäre die obere Grenze OK plus 1. 34:17.210 --> 34:19.790 Hier darf man sich jetzt nicht verwirren lassen, dass der Indizier 34:19.790 --> 34:22.230 natürlich steigt, aber die eigentliche Schranke fällt natürlich. 34:22.650 --> 34:26.150 Das heißt, ich bin im zweiten Rekursionsschritt, meine obere Grenze 34:26.150 --> 34:26.870 fällt natürlich. 34:27.570 --> 34:30.930 Wieder mit dem Beispiel mit 5, 5 ist der erste Rekursionsschritt, habe 34:30.930 --> 34:35.810 ich obere Schranke 25, zweiter Rekursionsschritt 4, obere Schranke 16. 34:36.930 --> 34:44.490 Das heißt, mein x, habe ich ein neues, das wäre das x k plus 1, ist 34:44.490 --> 34:47.010 natürlich in dem Fall dann z minus 1. 34:47.850 --> 34:53.150 Das heißt, was ich hier herausbekomme, ist meine Abstiegsfunktion für 34:53.150 --> 34:57.570 den zweiten Rekursionsschritt, kleiner gleich der oberen Schranke in 34:57.570 --> 34:58.730 dem zweiten Rekursionsschritt. 34:59.910 --> 35:04.610 Daraus folgt h mit meinem neuen x in dem Rekursionsschritt, in dem 35:04.610 --> 35:05.850 Fall z minus 1. 35:08.050 --> 35:13.210 Das angewandt auf die quadratische Funktion, wäre z minus 1 zum 35:13.210 --> 35:26.350 Quadrat, z minus 1 zum Quadrat, binomische Formel, z Quadrat minus 2z 35:26.350 --> 35:28.270 plus 1. 35:28.930 --> 35:33.230 So, jetzt kommt, das waren alles noch Vorarbeiten, jetzt kommt der 35:33.230 --> 35:34.710 eigentliche Beweis hierfür. 35:35.930 --> 35:37.290 Jetzt haben wir es aber auch nicht mehr weit. 35:42.400 --> 35:44.040 Ich mache das mal in Anführungsstrichen. 35:46.020 --> 35:52.060 Das heißt, was ich hier zeigen muss, ist, dass meine Funktion monoton 35:52.060 --> 35:52.760 fallend ist. 35:53.240 --> 35:56.880 Das heißt, meine Abstiegsfunktion vom ersten Rekursionsschritt muss 35:56.880 --> 36:01.140 größer sein, als die im zweiten Rekursionsschritt. 36:03.560 --> 36:05.660 So, jetzt kann ich die Sachen entsprechend einsetzen. 36:06.920 --> 36:08.720 Hier haben wir z Quadrat rausbekommen. 36:10.560 --> 36:19.140 Und hier haben wir z Quadrat minus 2z plus 1 rausbekommen. 36:19.720 --> 36:21.420 Und jetzt sieht man es eigentlich auch schon sofort. 36:22.060 --> 36:26.880 Das heißt, diese Ungleichung muss wahr sein. 36:27.740 --> 36:30.160 Diese Umformung bekomme ich raus. 36:31.380 --> 36:35.140 0 größer, minus 2z plus 1. 36:35.740 --> 36:37.180 Die ist natürlich immer wahr. 36:40.140 --> 36:41.420 Für jedes z. 36:43.040 --> 36:46.520 Da z größer 1 ist, aus dem natürlichen Bereich komme. 36:46.700 --> 36:50.380 Das kleinste, was ich hier einsetzen kann, für z ist 1. 36:52.360 --> 36:55.640 Das heißt, minus 2 mal 1 plus 1 gibt minus 1. 36:55.640 --> 36:58.060 Das heißt, 0 ist immer größer als eine negative Zahl. 37:00.540 --> 37:01.860 So, das war eigentlich schon der Beweis. 37:01.980 --> 37:04.320 Jetzt muss ich es bloß noch vollständigkeitshalber richtig 37:04.320 --> 37:04.860 hinschreiben. 37:08.180 --> 37:10.440 Dann werde ich eine neue Folie anfangen, deshalb warte ich noch mal 37:10.440 --> 37:11.080 einen kurzen Moment. 37:19.880 --> 37:21.480 So, ich glaube, ich kann umwechseln, oder? 37:26.170 --> 37:28.030 Auf die Gefahr hin, dass sich die anderen langweilen. 37:39.300 --> 37:41.580 So, das heißt... 37:43.360 --> 37:45.200 Mein h von x, meine Abstiegsfunktion... 37:47.780 --> 37:50.000 ist kleiner gleich einer oberen Schranke. 37:55.040 --> 37:56.160 Daraus folgt... 37:56.160 --> 37:57.040 Sum von x... 37:59.260 --> 38:00.280 ist dann undefiniert. 38:01.200 --> 38:04.340 Hier ist ganz wichtig, deshalb können wir das auch machen, weil wir 38:04.340 --> 38:06.160 die Ungleichung entsprechend bewiesen haben. 38:07.460 --> 38:09.900 Dass wir jetzt nicht die nächste obere Schranke haben. 38:10.400 --> 38:12.960 Und die nächste obere Schranke ist ja immer kleiner als die vorherige. 38:13.260 --> 38:16.680 Das ist genau die fallende Monotonie der Abstiegsfunktion x². 38:17.560 --> 38:20.420 Wenn wir das jetzt für jedes k weitermachen, das ist jetzt auch der 38:20.420 --> 38:24.300 Sinn des Induktionsbeweises, dann können wir natürlich sicher sein, 38:24.380 --> 38:26.040 dass wir irgendwann mal auf die 1 kommen. 38:26.580 --> 38:28.220 Und damit terminiert die Rekursion. 38:33.350 --> 38:34.310 Das heißt... 38:34.910 --> 38:36.890 h von xk plus 1... 38:38.010 --> 38:40.010 ist kleiner als h von... 38:41.470 --> 38:42.670 x von k. 38:44.190 --> 38:46.070 Kleiner gleich o von k. 38:49.030 --> 38:50.350 Daraus folgt... 38:50.350 --> 38:53.010 Sum von xk plus 1... 38:54.670 --> 38:55.610 terminiert auch. 38:56.810 --> 38:58.010 So, das war der Beweis. 38:59.850 --> 39:02.180 An diesem einfachen Beispiel... 39:03.090 --> 39:05.550 um das nochmal vielleicht grafisch zu verdeutlichen, kann man sich 39:05.550 --> 39:06.010 auch... 39:07.370 --> 39:09.310 folgendes Bild mal aufmalen. 39:09.890 --> 39:12.030 Ich habe ja zwei quadratische Funktionen. 39:12.790 --> 39:14.630 Die eine war meine Abstiegsfunktion h. 39:16.050 --> 39:18.130 Die hatte ich ja als x² definiert. 39:18.730 --> 39:20.970 Und meine eigentlich geschlossene Form, die haben wir ja vorher schon 39:20.970 --> 39:24.010 mal gesehen, das war x mal... 39:24.890 --> 39:26.110 x plus 1 halbe. 39:27.510 --> 39:30.050 Das ist natürlich auch eine quadratische Funktion, bloß mit anderen 39:30.050 --> 39:30.710 Parametern. 39:31.150 --> 39:33.710 Das heißt, wenn ich die mal ungefähr in meinem Koordinatensystem hier 39:33.710 --> 39:36.150 aufzeichne, dann habe ich meine Normalparabel. 39:37.010 --> 39:40.650 Und die andere, ich schätze das jetzt mal einfach ab, die wird 39:40.650 --> 39:41.610 irgendwie so aussehen. 39:43.810 --> 39:46.370 Das heißt, hier an dem Bild sehe ich schon, dass meine 39:46.370 --> 39:49.610 Abstiegsfunktion die Eigenschaften erfüllt, die ich vorher erwähnt 39:49.610 --> 39:49.850 habe. 39:49.950 --> 39:53.150 Das heißt, sie ist an jedem Punkt, wir sind hier bei den natürlichen 39:53.150 --> 39:59.110 Zahlen, immer größer wie die eigentliche Funktion, die ich in der 39:59.110 --> 40:00.410 Rekursion definiert habe. 40:00.650 --> 40:02.390 Und sie sind beide monoton fallend. 40:04.370 --> 40:08.050 Entsprechend in unserem Fall hier unten bei 1. 40:10.250 --> 40:10.830 Gut. 40:12.210 --> 40:17.410 Jetzt gebe ich die Hinweise, wie man auf die Abstiegsfunktion für die 40:17.410 --> 40:18.910 Aufgabe am Übungsblatt kommt. 40:19.550 --> 40:22.810 Dafür muss man sich eigentlich nur mal die Funktion anschauen, die auf 40:22.810 --> 40:24.150 dem Übungsblatt definiert ist. 40:24.890 --> 40:27.170 Und sich mal überlegen, was macht eigentlich die Funktion. 40:27.730 --> 40:28.950 Und die sich einfach mal anschauen. 40:31.710 --> 40:34.250 Hier haben wir unsere Funktion Ausdruck. 40:34.370 --> 40:39.970 Wenn man sich das mal genau anschaut, dann ist das eine Integer 40:39.970 --> 40:40.590 -Division. 40:44.310 --> 40:49.630 Integer -Division heißt, ich habe eine normale Division ohne Rest mit 40:49.630 --> 40:51.870 der Eigenschaft, dass sie abrundend ist. 40:52.410 --> 40:57.370 Wenn ich hier ein Beispiel mache und mal dividiere 5 durch 2, das 40:57.370 --> 41:00.930 heißt, mein x wäre 5 und mein y 2, 41:04.370 --> 41:05.310 das heißt, 41:09.610 --> 41:15.010 5 plus 2 gibt 7 durch 2, das werden wir nachher nochmal sehen am 41:15.010 --> 41:17.910 Beispiel, wird dann entsprechend wieder neu aufgerufen und dadurch 41:17.910 --> 41:21.730 erhalte ich dann im Endeffekt mein Ergebnis halbe. 41:21.870 --> 41:25.970 Das heißt, 5 durch 2 wäre 2, 7 durch 2 wäre 3 usw. 41:29.510 --> 41:37.070 Jetzt machen wir das Beispiel mit x gleich 2 und y gleich 6 und 41:37.070 --> 41:39.350 schreibe das einfach mal rein, was meine Funktion hier macht. 41:40.830 --> 41:47.770 Das heißt, mein f von x, y mit x gleich 2 und y gleich 6 würde zu f 41:47.770 --> 41:54.470 von 2,4 mal f von 5,6 werden. 41:56.050 --> 42:02.210 Das heißt, ich muss beide hier wieder einsetzen, da ich noch nicht 42:02.210 --> 42:02.990 terminiert bin. 42:04.110 --> 42:07.330 Terminieren tut es erst, wenn hier gleiche Funktionsparameter 42:07.330 --> 42:07.910 drinstehen. 42:08.030 --> 42:09.490 Das heißt, wenn x gleich y ist. 42:10.430 --> 42:14.610 Das heißt, im zweiten Fall wäre nun oder in der zweiten Rekursion 42:14.610 --> 42:21.530 besser gesagt x gleich 2 und y gleich 4 wieder eingesetzt. 42:22.850 --> 42:32.490 f von x, y würde dann abgebildet auf f von 2,3 mal f von 4,4 Hier habe 42:32.490 --> 42:34.750 ich jetzt das direkte Ergebnis, würde 4 rauskommen. 42:35.570 --> 42:41.030 In dem linken Ast müsste ich einfach weitermachen x gleich 2, y gleich 42:41.030 --> 42:41.390 3. 42:42.550 --> 42:48.630 Der rechte Ast wäre x gleich 5 und y gleich 6. 42:49.430 --> 42:52.890 Wieder auf die Funktion angewandt. 42:53.850 --> 43:07.330 Hätte ich nun 5,5 und f von 6,6 Das heißt, hier terminiere ich 43:07.330 --> 43:11.130 ebenfalls, da x und y gleich ist und auf der rechten Seite ebenso. 43:12.130 --> 43:15.290 Wenn ich mir jetzt mal die Eigenschaften von x und y anschaue und die 43:15.290 --> 43:18.370 mal in Beziehung setze, dann komme ich genau auf die Abstiegsfunktion. 43:18.470 --> 43:21.670 Das heißt, ich muss jetzt genau beobachten, was ändert sich eigentlich 43:22.370 --> 43:24.490 bei jedem Rekursionsschritt mit dem x und y. 43:26.890 --> 43:28.070 Das wäre die Vorranzgehensweise. 43:28.650 --> 43:30.750 Der nächste Schritt wäre eigentlich schon die Lösung, den verrate ich 43:30.750 --> 43:31.370 euch nicht mehr. 43:31.750 --> 43:35.910 Ihr müsst eigentlich bloß noch hinschauen, was passiert mit x und y, 43:36.670 --> 43:37.890 wenn ich hier weiter runtergehe. 43:40.590 --> 43:43.730 Ich glaube, das sollte genügen, um mal die Abstiegsfunktion zu 43:43.730 --> 43:44.070 bekommen. 43:44.690 --> 43:47.830 Ansonsten muss man den Beweis eigentlich ganz formal entsprechen, wie 43:47.830 --> 43:48.690 ich es vorher gemacht habe. 43:48.770 --> 43:51.970 Ich habe am Anfang gesagt, der Beweis schreckt eher ab. 43:52.930 --> 43:57.450 Das liegt leider an der Formalität, die der Beweis auszeigen muss. 43:58.190 --> 44:01.290 Aber der eigentliche Sinn und Zweck ist dann nachher entsprechend bei 44:01.290 --> 44:04.370 der Abstiegsfunktion die Eigenschaften herauszufinden, monoton 44:04.370 --> 44:04.890 fallend. 44:05.330 --> 44:08.530 Und dass es immer größer ist, wie die eigentliche Funktion, ich 44:08.530 --> 44:10.130 glaube, das sollte kein Problem mehr sein. 44:12.310 --> 44:13.870 Jetzt lasse ich das soweit hier noch stehen. 44:15.490 --> 44:18.770 Wenn jemand Fragen hat, kann er gerne mal eine Frage stellen. 44:20.810 --> 44:23.710 Ansonsten würde ich jetzt zu einer ziemlich einfachen Aufgabe gehen. 44:26.890 --> 44:30.770 Die vielleicht nicht in dieser Einfachheit in der Klausur vorkam, aber 44:30.770 --> 44:33.410 vom Prinzip her war das eine Klausuraufgabe vom letzten Jahr. 44:33.970 --> 44:36.610 Hier geht es nun um Gültigkeit und Lebensdauer. 44:38.550 --> 44:42.870 Hier heißt es ganz einfach, ich muss mir mein Programmfragment bzw. 44:43.230 --> 44:48.450 in dem Fall wieder meine Rekursion anschauen und nun sagen, was 44:48.450 --> 44:52.210 passiert eigentlich mit der Variable x, die hier ziemlich häufig drin 44:52.210 --> 44:52.770 vorkommt. 44:53.890 --> 44:58.610 Wenn man sich mal anschaut, wie oft die Variablen hier vorkommen, dann 44:58.610 --> 45:00.450 stellt das schon manch einen vor ein Problem. 45:01.110 --> 45:03.510 Zumindest war das so in der Klausurkorrektur, es hatten noch nicht mal 45:03.510 --> 45:05.570 alle geschafft, alle x hier zu identifizieren. 45:09.580 --> 45:12.120 Das heißt, die x kommen hier ziemlich häufig vor und nun muss ich 45:12.120 --> 45:17.060 einfach schauen, was kann ich über die Lebensdauer der einzelnen x 45:17.060 --> 45:19.180 sagen und was kann ich über die Gültigkeit sagen. 45:20.160 --> 45:21.800 In dem ersten Fall, das heißt im ersten 45:28.360 --> 45:32.260 Fall wäre es mit einem Wert belegen, in dem Fall mit 6, das heißt ab 45:32.260 --> 45:33.460 hier beginnt die Lebensdauer. 45:34.140 --> 45:36.260 Das markiere ich hier einfach mit einem Punkt oder einem Kreuz. 45:40.540 --> 45:42.600 Gültigkeit habe ich hier natürlich auch schon, das heißt nach 45:42.600 --> 45:45.320 Ausführung dieses Programmschritt ist dieses x natürlich gültig. 45:46.400 --> 45:50.720 Mein x-Stern, das ist jetzt was Neues, und zwar das x-Stern kommt es 45:50.720 --> 45:54.120 nämlich hier mit rein, das ist im Programmcode natürlich auch wieder 45:58.360 --> 45:58.380 ein x-Stern. 45:58.380 --> 46:00.980 Und was das ist, haben wir hier einfach ein x-Stern daraus gemacht, 46:01.300 --> 46:05.020 dass man jetzt sieht, dieses x-Stern gehört, ist das x von der 46:05.020 --> 46:05.600 Rekursion. 46:06.640 --> 46:11.460 Das heißt hier habe ich jetzt auch wieder meine Instanzierung dieses 46:11.460 --> 46:15.320 x, x-Sterns, das heißt, das ist ganz klar, das hat hier natürlich 46:15.320 --> 46:19.420 jetzt eine gültige Lebensdauer und ist natürlich auch gültig. 46:21.720 --> 46:25.880 Nichtsdestotrotz hat mein Rechner natürlich das andere x immer noch im 46:25.880 --> 46:26.300 Speicher. 46:28.360 --> 46:28.980 Das ist in der Aussage getroffen. 46:29.660 --> 46:33.360 Und ist in dem Fall natürlich genauso. 46:34.400 --> 46:38.760 Das kann man sich daraus verdeutlichen, dass dieses x hier unten, das 46:38.760 --> 46:41.940 von da oben ist und das bleibt natürlich die ganze Zeit über 46:42.660 --> 46:43.680 entsprechend gültig. 46:44.340 --> 46:51.660 Das x-Stern, das bezieht sich nun alles auf die hier oben, möchte ich 46:51.660 --> 46:56.040 nochmal rot angreifen, das heißt, die anderen x-Stern, in unserem Fall 46:56.040 --> 46:58.520 x -Stern, beziehen sich hier oben. 47:00.840 --> 47:04.140 So, im nächsten Programmschritt habe ich wieder ein x. 47:05.980 --> 47:09.300 Dieses x habe ich gerade angedeutet, das ist dieses hier, 47:12.320 --> 47:13.960 also Prinzip x-Stern. 47:15.920 --> 47:18.160 Darüber kann ich natürlich auch sagen, ich habe hier immer noch eine 47:18.160 --> 47:20.480 Lebensdauer und es ist nach wie vor gültig. 47:23.900 --> 47:27.460 So, für mein anderes x, das außen steht, 47:30.480 --> 47:34.280 das ist natürlich nach wie vor eine Lebensdauer, das heißt, es ist 47:34.280 --> 47:37.380 nach wie vor ein Speicher hier, ist aber nicht gültig. 47:37.820 --> 47:39.780 Das heißt, nicht gültig, ist ganz klar, es wird natürlich nicht 47:39.780 --> 47:42.000 verwendet, weil das andere x im Kontext verwendet wird. 47:43.040 --> 47:46.920 Bei der nächsten Zeile ist es ebenfalls genau das gleiche, das heißt, 47:47.060 --> 47:50.660 beide x-Sterne existieren noch, haben also entsprechend eine 47:50.660 --> 47:51.300 Lebensdauer. 47:51.900 --> 47:54.920 Gültig ist aber allerdings nur dieses x für die Rekursion, 47:58.360 --> 47:59.740 bei der nächsten Zeile wird es jetzt natürlich interessant. 48:01.400 --> 48:08.220 Das heißt, jetzt beende ich die Rekursion, das heißt, mein 48:08.220 --> 48:12.100 ursprüngliches x, das ganz oben in der Zeile stande, hat nach wie vor 48:12.100 --> 48:15.440 die Lebensdauer, aber mein x-Stern hat nun keine Lebensdauer mehr. 48:16.160 --> 48:23.560 Das heißt, hier ist die Funktion sum einfach abgeschlossen, das x ist 48:23.560 --> 48:28.460 nicht mehr vorhanden, wird auch aus dem Speicher herausgelöscht und 48:28.460 --> 48:28.800 wird wieder gültig. 48:29.500 --> 48:32.380 Jetzt kommt aber wieder das andere x und wird wieder gültig. 48:33.360 --> 48:35.900 Ich glaube, diese Aufgabe ist ziemlich einfach. 48:36.300 --> 48:38.620 Die einzigste Problematik, die man hierbei hat, das hat sich auch 48:38.620 --> 48:41.800 gezeigt in der Klausurkorrektur ist, dass man eigentlich höllisch 48:41.800 --> 48:44.520 aufpassen muss, dass man die x nicht durcheinander bringt, dass man 48:44.520 --> 48:49.040 genau weiß, welches x gehört in welchen Kontext und erschwerend kommt 48:49.040 --> 48:51.260 meistens noch hinzu, dass es nicht nur ein x ist, sondern dass auch 48:51.260 --> 48:52.920 noch ein y oder ein z dabei ist. 49:00.340 --> 49:04.620 Hier möchte ich jetzt eine kurze Pause machen, weil wir jetzt zu der 49:04.620 --> 49:08.840 Java -Aufgabe kommen und möchte diejenigen die Gelegenheit geben, zu 49:08.840 --> 49:11.420 sagen, ich möchte nicht mehr teilnehmen, die können natürlich gerne 49:11.420 --> 49:12.200 den Hörsaal verlassen. 49:22.160 --> 49:23.900 Pause würde ich sagen fünf Minuten. 54:48.890 --> 54:50.790 So, da würde ich vorschlagen, wir machen weiter. 54:53.050 --> 54:55.310 Ein Kommilitone von euch hat mich gerade auf eine Kleinigkeit 54:55.310 --> 54:55.510 hingewiesen. 54:59.190 --> 55:02.270 Es ändert aber grundsätzlich nichts an der ersten Aufgabe. 55:08.680 --> 55:13.380 Und zwar hat er mir gesagt, dass in der Vorlesung die Definition mit 55:13.380 --> 55:17.040 dem vermerkt war, dass es strikt ist, das heißt, wenn es strikt ist, 55:18.460 --> 55:20.700 gilt natürlich das Gleichheitszeichen hier nicht mehr. 55:21.740 --> 55:25.900 Das Gleichheitszeichen muss ich natürlich entsprechend bei undefiniert 55:25.900 --> 55:26.540 mit angeben. 55:28.200 --> 55:29.780 Das heißt, das würde ich auch hochwandern. 55:30.440 --> 55:31.680 Aber das ist bloß eine Kleinigkeit. 55:32.600 --> 55:34.840 Wie gesagt, wenn es strikt dabei ist, ändert sich das 55:34.840 --> 55:35.580 Gleichheitszeichen. 55:35.660 --> 55:37.900 Wenn es nicht dabei ist, dann bleibt das Gleichheitszeichen unten. 55:46.400 --> 55:48.080 So, dann würde ich jetzt zu Java kommen. 55:49.240 --> 55:53.280 Ich werde euch zeigen, wie man Methoden definiert, wie man sie aufruft 55:53.280 --> 55:55.120 innerhalb von einem Java-Programm. 55:55.120 --> 55:58.900 Dazu habe ich mal eine kleine Klasse geschrieben, die ich jetzt 55:58.900 --> 56:01.040 einfach mal so hinschreiben werde. 56:03.880 --> 56:08.280 Die Klasse ist einfach so entstanden, und die habe ich mal Just-for 56:08.280 --> 56:09.000 -Fun genannt. 56:14.220 --> 56:21.600 Die hat natürlich den üblichen Aufruf mit public static void main, 56:26.340 --> 56:29.740 den üblichen Eingabe-Parametern, 56:32.820 --> 56:36.680 den Arguments, Args hier. 56:40.350 --> 56:44.870 So, und die soll eigentlich nichts anderes machen, als das Ergebnis 56:44.870 --> 56:50.790 einer Methode auf der Konsole ausgeben. 56:54.270 --> 56:58.830 Dazu benutze ich bereits eine Methode, die ihr nicht selber definiert 56:58.830 --> 57:03.090 habt, aber die es entsprechend in dem Java-Developer-Kit schon gibt, 57:03.510 --> 57:04.870 und zwar ist das die Printline-Methode. 57:06.730 --> 57:10.330 Und in diese Methode mache ich einfach einen neuen Methodenaufruf, das 57:10.330 --> 57:11.290 wäre das JFF. 57:17.470 --> 57:21.530 So, Methoden aufrufen muss ich innerhalb meiner Klasse mit angeben. 57:22.370 --> 57:26.630 Das heißt, so wäre das Programm ja syntaktisch falsch, weil ich hier 57:26.630 --> 57:29.330 die schließende Klammer vergessen habe, die würde ganz zum Schluss 57:29.330 --> 57:32.590 kommen, das heißt ganz da unten. 57:33.550 --> 57:38.510 Und hier zwischendrin würde ich jetzt meine Methode definieren, das 57:38.510 --> 57:39.970 heißt wie die aussieht und was die macht. 57:44.670 --> 57:51.510 So, Methoden definiere ich ganz ähnlich wie hier oben. 57:52.350 --> 57:55.670 Meine Main-Methode, die ein bisschen einen Sonderstatus hat. 57:57.970 --> 58:01.530 Bei meiner Main-Methode habe ich ja keinen Rückgabewert, deshalb steht 58:01.530 --> 58:04.310 auch hier Void. 58:07.110 --> 58:09.630 Static eigentlich nur deshalb, weil mich ja noch nicht 58:09.630 --> 58:13.630 objektorientiert programmieren, und Main ist der Methodenamen und 58:13.630 --> 58:14.850 Public heißt, sie ist öffentlich. 58:15.290 --> 58:18.430 Das heißt, es gibt überhaupt keine Beschränkungen, wer die Methode 58:18.430 --> 58:19.290 aufrufen darf. 58:19.750 --> 58:23.430 Wer heißt einfach andere Klassen, andere Methoden. 58:24.570 --> 58:26.390 Das heißt, ich habe hier den allgemeinsten Fall. 58:28.110 --> 58:33.550 Das heißt, meine neue Methode heißt nun Public, Static. 58:35.410 --> 58:38.730 Nun gebe ich an, nicht Void, wie oben, sondern ich habe ja einen 58:38.730 --> 58:40.690 Rückgabewert, ich möchte ja was ausdrucken. 58:41.250 --> 58:45.470 Mein Rückgabewert soll vom Typ String sein, das heißt, ich möchte eine 58:45.470 --> 58:49.350 Zeichenfolge ausdrucken, und nun noch meinen Methodenamen, der ist 58:49.350 --> 58:53.870 oben schon erwähnt worden, JFF, und ich habe keine Eingabeparameter 58:53.870 --> 58:54.690 bei dieser Methode. 58:57.510 --> 59:00.990 Danach muss ich wieder meine geschweifte Klammer machen, die ich hier 59:00.990 --> 59:04.650 unten natürlich wieder schließen muss, und zwischendrin kann ich nun 59:04.650 --> 59:08.190 natürlich wieder beliebige Java-Anweisungen hinschreiben. 59:09.150 --> 59:12.010 Wichtig ist, wenn ich so eine Methode definiere, und ich habe 59:12.010 --> 59:17.010 angegeben, dass ich was erwarte, in unserem Fall einen Wert vom Typ 59:17.010 --> 59:21.810 String, muss ich natürlich auch dem Compiler sagen, dass es sowas 59:21.810 --> 59:22.570 zurückgeben soll. 59:22.910 --> 59:25.190 Das mache ich mit der Anweisung Return. 59:28.830 --> 59:32.350 Hier kann ich Variablen hinschreiben vom Typ String, oder ich kann es 59:32.350 --> 59:35.370 auch direkt machen, indem ich einfach den String angebe. 59:37.230 --> 59:39.810 Bei uns heißt er einfach Just for Fun, 59:43.130 --> 59:46.610 in der üblichen Notation mit den Anführungsstrichen, und hier wieder 59:46.610 --> 59:49.210 Java üblich, das Semikolon nicht vergessen. 59:49.990 --> 59:53.850 Das heißt, dieses Programm, wenn ihr das so eingebt, bringt euch auf 59:53.850 --> 59:57.870 der Konsole Just for Fun heraus, mit einem Seilenumbruch. 01:00:01.460 --> 01:00:08.280 So, jetzt gehen wir mal auf eine kleine Eigenheit von dem Java-Schiffe 01:00:08.280 --> 01:00:09.080 -Versenken ein. 01:00:10.800 --> 01:00:14.960 Da solltet ihr nämlich unter anderem auch mal die Rekursion anwenden, 01:00:15.080 --> 01:00:18.480 und ich werde euch einfach mal zeigen, wie man vorher so ein bisschen 01:00:18.480 --> 01:00:21.440 abstrakter schreibweise eine Rekursion hat, und wie man das jetzt 01:00:21.440 --> 01:00:23.700 konkret in Java implementiert. 01:00:24.320 --> 01:00:28.420 Dazu habe ich einfach die Rekursion von vorher genommen, die 01:00:28.420 --> 01:00:35.260 Summenfunktion, und die mal auf zwei verschiedene Arten implementiert, 01:00:35.720 --> 01:00:38.720 um euch einfach mal zu zeigen, dass es immer nicht nur die eine Lösung 01:00:38.720 --> 01:00:41.000 gibt, sondern man kann eine Rekursion in Java auch in 01:00:41.000 --> 01:00:43.720 unterschiedlichen Arten und Weisen definieren. 01:00:45.780 --> 01:00:49.820 Meine Klasse heißt Sum. 01:00:52.400 --> 01:00:56.500 Hier führe ich jetzt erst mal ein Parameter ein. 01:00:57.600 --> 01:01:00.800 Parameter werden ähnlich deklariert wie Methoden. 01:01:03.040 --> 01:01:05.840 Hier auch ein neues Schlüsselwort, private. 01:01:07.640 --> 01:01:10.280 Static, weil wir wieder nicht objektorientiert sind. 01:01:11.720 --> 01:01:13.760 Den Typ, in Ketchup in dem Fall. 01:01:14.540 --> 01:01:16.560 Den Namen, das wäre S. 01:01:16.560 --> 01:01:19.780 Und ich kann hier gleich noch eine Wertzuweisung machen, 5. 01:01:22.060 --> 01:01:24.900 Private, einfach nur deshalb, dass ihr mal seht, es gibt außer Public 01:01:24.900 --> 01:01:25.680 auch noch was anderes. 01:01:25.860 --> 01:01:28.400 Man hätte hier genauso gut Public hinschreiben können. 01:01:29.820 --> 01:01:32.440 Entschuldigung, man darf hier nicht Public hinschreiben, man muss hier 01:01:32.440 --> 01:01:35.020 Private hinschreiben, das ist eine Java-Eigenheit, weil es sich hier 01:01:35.020 --> 01:01:36.220 um eine Konstante handelt. 01:01:38.900 --> 01:01:42.060 Das heißt, das war von anderen Programmiersprachen mit dem 01:01:42.060 --> 01:01:46.020 Schlüsselwort Kunst für Konstante definiert, muss man in Java immer 01:01:46.020 --> 01:01:48.240 mit den zwei Schlüsselwörtern Private, Static machen. 01:01:49.360 --> 01:01:51.870 Das heißt, Private, Static ist nicht veränderbar. 01:01:52.700 --> 01:01:55.560 Wenn ich jetzt noch einmal eine Zuweisung machen würde mit S gleich 6, 01:01:55.640 --> 01:01:56.720 würde ich eine Fehlermeldung bekommen. 01:01:57.180 --> 01:02:01.680 Ich kann nur noch der Variable eine neue Zuweisung machen, indem ich 01:02:01.680 --> 01:02:02.890 zum Beispiel folgendes hinschreibe. 01:02:04.100 --> 01:02:06.240 Das wische ich jetzt aber gleich wieder weg, weil das jetzt nicht 01:02:06.240 --> 01:02:07.520 Bestandteil des Programms ist. 01:02:07.520 --> 01:02:16.280 Das wäre dann Public Static Integer S gleich 5 und ich könnte als 01:02:16.280 --> 01:02:18.800 nächste Anweisung machen S gleich 6. 01:02:19.300 --> 01:02:20.360 Das wäre also gültig. 01:02:21.140 --> 01:02:25.160 Wenn ich diese Zeile hier wegwische, dann bekomme ich einen Fehler. 01:02:29.920 --> 01:02:34.160 Gut, jetzt machen wir unser ganz normales Programm weiter. 01:02:35.160 --> 01:02:42.820 Die obligatorische Public Static Void Main mit 01:02:46.390 --> 01:02:47.730 meinen Eingabeparametern. 01:02:50.930 --> 01:02:55.770 String Array und die Benammung ARGS für Arguments. 01:02:57.970 --> 01:03:00.230 So, mein Programm soll eigentlich folgendes machen. 01:03:01.890 --> 01:03:07.090 Es soll mir nun auf der Konsole folgendes ausgeben. 01:03:12.970 --> 01:03:22.190 Und zwar die Summe 1 von der Funktion, die ich nachher zu definieren 01:03:22.190 --> 01:03:23.150 habe, von der Methode. 01:03:25.450 --> 01:03:29.750 Summe 1 heißt die, mit dem Parameter Mert S. 01:03:31.650 --> 01:03:34.850 Und das konkateniert mit meinem festen String hier vorne. 01:03:36.710 --> 01:03:38.190 Summe 1 Doppelpunkt. 01:03:38.190 --> 01:03:41.230 Die Konkatenation mache ich über das Additionszeichen. 01:03:42.890 --> 01:03:44.210 Ist also bei Java zulässig. 01:03:44.530 --> 01:03:47.190 Strings kann ich mit dem Plus-Symbol verbinden. 01:03:49.490 --> 01:03:53.690 Ich habe gesagt, wir machen die Funktion auf zwei verschiedene Arten 01:03:53.690 --> 01:03:54.230 und Weisen. 01:03:54.890 --> 01:04:00.090 Deshalb die gleiche Zeile nochmal, nur diesmal mit dem zweiten 01:04:00.090 --> 01:04:00.410 Methodenaufruf. 01:04:03.830 --> 01:04:11.250 Das heißt diesmal gebe ich auf der Konsole aus, Summe 2 ist 2 der 01:04:11.250 --> 01:04:12.270 Methodenaufruf. 01:04:13.190 --> 01:04:19.190 Summe 2 mit dem obligatorischen Strichpunkt. 01:04:20.130 --> 01:04:24.610 Das ist meine Methode Main. 01:04:25.130 --> 01:04:26.250 Die muss ich hier wieder schließen. 01:04:26.250 --> 01:04:31.830 Und jetzt kann ich herangehen und mir entsprechend meine Methoden 01:04:31.830 --> 01:04:32.350 definieren. 01:04:33.150 --> 01:04:36.790 Bevor ich die Methode jetzt definiere, machen wir das auch in der Java 01:04:36.790 --> 01:04:38.490 -Annotation mit einem kleinen Remark. 01:04:39.610 --> 01:04:41.110 Was macht diese Methode überhaupt? 01:04:43.730 --> 01:04:54.490 Das heißt, Summe 1 habe ich einen Integer-Wert, der mir wieder einen 01:04:54.490 --> 01:04:55.670 Integer -Wert zurückgibt. 01:04:57.090 --> 01:05:05.930 Das heißt Sum 1 von n wäre, das mache ich jetzt nochmal in der 01:05:05.930 --> 01:05:07.590 abstrakten Schreibweise von vorher. 01:05:09.330 --> 01:05:13.210 If n 1, das heißt die Rekursion ist beendet, dann soll er 1 01:05:13.210 --> 01:05:13.770 zurückgeben. 01:05:17.390 --> 01:05:24.370 Ansonsten soll er n plus Sum 1 von n minus 1. 01:05:24.950 --> 01:05:27.550 Diese abstrakte Schreibweise müssen wir natürlich jetzt umsetzen in 01:05:27.550 --> 01:05:27.850 Java. 01:05:28.750 --> 01:05:31.190 Und wie das jetzt korrekt aussieht, werde ich jetzt auf dem nächsten 01:05:31.190 --> 01:05:34.250 Blatt Papier zeigen, beziehungsweise auf der nächsten Folie. 01:05:38.370 --> 01:05:40.990 Wenn ich umblättern kann, ich glaube, ihr seid soweit. 01:05:43.150 --> 01:05:44.150 Lade ich noch einen Moment. 01:05:50.100 --> 01:05:53.680 Das heißt, hier werden wir jetzt entsprechend die neue Methode 01:05:53.680 --> 01:05:54.760 definieren. 01:05:59.960 --> 01:06:04.200 Diese machen wir jetzt nochmal mit Private, hier wäre genauso zulässig 01:06:04.200 --> 01:06:04.940 Public. 01:06:05.680 --> 01:06:08.380 Private heißt in diesem Fall nur, ich kann sie nur innerhalb dieser 01:06:08.380 --> 01:06:09.220 Klasse aufrufen. 01:06:13.160 --> 01:06:20.080 Mein Rückgabewert ist Integer, mein Methodenamen ist Sum 1, mein 01:06:20.080 --> 01:06:23.940 Eingabewert ist auch ein Integer und heißt n. 01:06:23.940 --> 01:06:28.100 In diesem Fall mache ich es wie bei Void Main. 01:06:28.420 --> 01:06:32.900 Bei Void Main hatte ich ja String Args, das heißt ich hatte den 01:06:32.900 --> 01:06:36.420 Variablenamen Args und den Typ String Array. 01:06:36.960 --> 01:06:41.380 Hier habe ich nun den Variablenamen n und zuvor muss immer der Typ 01:06:41.380 --> 01:06:42.740 stehen, in diesem Fall Integer. 01:06:45.560 --> 01:06:46.960 Meine geschweifte Klammer. 01:06:48.380 --> 01:06:49.860 Und nun kommt die eigentliche Berechnung. 01:06:50.800 --> 01:06:54.220 Das heißt, jetzt muss ich mein if-Statement aufbauen. 01:06:55.620 --> 01:06:59.960 Das heißt, if n gleich 1, einen Vergleich mache ich mit einem 01:06:59.960 --> 01:07:05.340 Doppelgleichheitszeichen in Klammer, dann soll er folgendes machen. 01:07:05.920 --> 01:07:09.300 Hier empfiehlt es sich immer die geschweifte Klammer zu machen, sie 01:07:09.300 --> 01:07:12.820 ist nicht immer nötig, erhöht aber die Übersicht des Programms. 01:07:13.260 --> 01:07:17.380 Wenn 1 ist, muss natürlich 1 zurückgegeben werden, weil ich dann bei 01:07:17.380 --> 01:07:18.320 meiner Terminierung bin. 01:07:19.320 --> 01:07:20.720 Mit dem Strichpunkt. 01:07:22.740 --> 01:07:27.980 Ansonsten ist dieser Programmblock zwischen dieser geschweiften 01:07:27.980 --> 01:07:29.220 Klammer und dieser abgeschlossen. 01:07:29.740 --> 01:07:33.420 Ich mache nun meinen else und mache einen neuen Programmblock, wieder 01:07:33.420 --> 01:07:36.840 mit geschweifter Klammer und gebe folgendes zurück. 01:07:37.760 --> 01:07:38.180 Return. 01:07:39.820 --> 01:07:44.000 Und hier hinten muss natürlich ein Wert stehen, der vom Typ Integer 01:07:44.000 --> 01:07:46.240 ist, diesen Wert kann ich aber direkt berechnen lassen. 01:07:46.240 --> 01:07:55.080 Das heißt, ich kann hier hinten n plus neuer Methodenaufruf sum 1 von 01:07:55.080 --> 01:07:56.360 n -1 angeben. 01:07:56.660 --> 01:07:58.660 Das heißt, hier genau kommt nun meine Regression herein. 01:08:00.400 --> 01:08:03.240 Den Programmblock muss ich hier natürlich wieder abschließen. 01:08:05.480 --> 01:08:08.180 Das heißt, nun ist meine if-Anweisung abgeschlossen. 01:08:08.880 --> 01:08:13.660 Ich habe die Zuordnung von den geschweiften Klammern dann wie folgt. 01:08:13.660 --> 01:08:18.320 Diese gehört zu dieser und diese zu dieser. 01:08:18.700 --> 01:08:22.320 Und meine eigentlich eröffnete und geschweifte Klammer von der 01:08:22.320 --> 01:08:25.000 Methodendeklaration muss ich jetzt auch noch schließen. 01:08:29.410 --> 01:08:30.910 Das sind immer berühmte Fehlerquellen. 01:08:32.010 --> 01:08:34.990 Besonders wenn man in normalen Editoren arbeitet, dann sieht man das 01:08:34.990 --> 01:08:35.570 nicht sofort. 01:08:35.990 --> 01:08:38.210 Hat man ein bisschen Unterstützung mit den Editoren, dann macht der 01:08:38.210 --> 01:08:41.250 immer aufmerksam, dass hier entsprechend die geschweiften Klammern 01:08:41.250 --> 01:08:41.610 fehlen. 01:08:41.610 --> 01:08:45.650 So, jetzt haben wir unsere Sum-Funktion 1 definiert, rekursiv. 01:08:46.210 --> 01:08:48.270 Jetzt fehlt uns noch unsere zweite Sum-Funktion. 01:08:49.610 --> 01:08:51.370 Die können wir in einer Zeile definieren. 01:08:51.910 --> 01:08:55.050 Da füge ich auch ein neues Java-Konstrukt ein, einfach mal zu zeigen, 01:08:55.490 --> 01:08:56.970 dass Java auch flexibel ist. 01:09:02.130 --> 01:09:09.760 Da werde ich auch gleich die abstrakte Definition nochmal 01:09:09.760 --> 01:09:10.320 hinschreiben. 01:09:12.800 --> 01:09:19.820 Das heißt, mein Sum 2 von 1 soll 1 ergeben. 01:09:21.300 --> 01:09:32.780 Und mein Sum 2 von n soll n plus Sum 2 von n-1 ergeben. 01:09:34.460 --> 01:09:37.300 So, meine übliche Methodendeklaration. 01:09:38.000 --> 01:09:39.400 Hier wieder mit private. 01:09:42.220 --> 01:09:42.740 Static. 01:09:43.800 --> 01:09:46.000 Ich gebe wieder einen Wert vom Typ Integer zurück. 01:09:46.780 --> 01:09:50.120 Int, den Methodennamen Sum 2. 01:09:51.520 --> 01:09:53.600 Hier bekommt ihr übrigens eine Fehlermeldung, falls ihr den 01:09:53.600 --> 01:09:56.680 Methodennamen wiederholt versucht, hier zu definieren. 01:09:56.820 --> 01:09:59.640 Also wenn ich nochmal zum 1 stehen würde, würde man einen 01:09:59.640 --> 01:10:00.580 entsprechenden Fehler bekommen. 01:10:01.450 --> 01:10:04.680 Als Eingabeparameter hat man wieder n vom Typ Integer. 01:10:05.560 --> 01:10:07.020 Und meine öffnende, geschweifte Klammer. 01:10:08.700 --> 01:10:12.260 So, jetzt kann ich die ganze Rekursion in einer Zeile machen und auch 01:10:12.260 --> 01:10:13.060 sofort zurückgeben. 01:10:13.500 --> 01:10:15.080 Mit folgendem Konstrukt. 01:10:17.340 --> 01:10:20.080 Ich mache den Vergleich einfach in einer Klammer. 01:10:22.260 --> 01:10:23.440 Ist das wahr? 01:10:23.900 --> 01:10:27.620 Kommt der erste Teil, der folgt nach einem Fragezeichen. 01:10:28.380 --> 01:10:30.440 1, ist es falsch? 01:10:30.700 --> 01:10:34.840 Kommt nach dem zweiten Teil, der mit einem Doppelpunkt angegeben wird. 01:10:35.400 --> 01:10:41.880 Und hier hinten wiederum entsprechend meine Berechnung. 01:10:42.620 --> 01:10:44.460 In diesem Fall die Rekursion. 01:10:45.100 --> 01:10:46.480 Abgeschlossen mit einem Strichpunkt. 01:10:47.360 --> 01:10:50.280 Das heißt, das Konstrukt sieht dann wie folgt aus. 01:10:52.200 --> 01:10:54.460 Ich habe vorne den Vergleich. 01:10:58.120 --> 01:11:04.280 Dann hier habe ich den True-Teil und nach dem Doppelpunkt habe ich den 01:11:04.280 --> 01:11:04.980 False -Teil. 01:11:05.960 --> 01:11:08.800 Hier ist natürlich ganz wichtig, dass hier entsprechend Werte stehen. 01:11:11.200 --> 01:11:12.340 Hier und hier. 01:11:13.740 --> 01:11:17.000 Die nicht vom Typ Boolean sind, sondern die genau von diesem Typ sind, 01:11:17.320 --> 01:11:18.600 die das Return zurückgeben muss. 01:11:18.960 --> 01:11:20.600 Also es müssen beides Integer-Typen sein. 01:11:23.620 --> 01:11:29.060 So, das war eigentlich die Deklaration dieser Methode. 01:11:29.360 --> 01:11:32.100 Uns fehlt noch die geschweifte Klammer von dieser Methode. 01:11:32.680 --> 01:11:35.700 Und uns fehlt noch von den zwei Folien zuvor natürlich die geschweifte 01:11:35.700 --> 01:11:37.220 Klammer von der Klasse. 01:11:37.880 --> 01:11:42.180 Das heißt, dieses Programm würde dann entsprechend zweimal der Eingabe 01:11:42.180 --> 01:11:47.400 S gleich 5, beides mal 25 herausgeben. 01:11:47.400 --> 01:11:50.780 Wer möchte, kann das Programm natürlich ändern und mal größere Zahlen 01:11:50.780 --> 01:11:53.700 eingeben und mal schauen, welche Methode schneller ist. 01:11:55.200 --> 01:11:58.560 So, dann bedanke ich mich für die Aufmerksamkeit und möchte damit abschließen.