WEBVTT 00:10.040 --> 00:13.480 So, einen wunderschönen guten Morgen. 00:13.820 --> 00:23.060 Nachdem wir jetzt also letztes Mal fast das Kapitel der Aussagenlogik 00:23.060 --> 00:25.840 beendet hatten, blieb noch ein Beweis übrig. 00:27.400 --> 00:35.520 Und das ist ein sehr wichtiger Beweis, den man sich auf alle Fälle gut 00:35.520 --> 00:36.600 anschauen sollte. 00:39.180 --> 00:44.880 Dieser Beweis ist etwas, das in der Mathematik sehr interessant ist 00:44.880 --> 00:48.420 und der sich mit einer Frage beschäftigt, mit der sich auch schon 00:48.420 --> 00:49.920 Gödel beschäftigt hat. 00:50.220 --> 00:55.140 Gödel, bekannter Mathematiker, noch erst vor kurzem verstorben. 00:55.260 --> 00:57.200 Einer der bekannten modernen Mathematiker. 00:57.620 --> 00:59.960 Wer hat schon mal was von Kurt Gödel gehört? 01:01.500 --> 01:02.940 Immerhin doch ein paar. 01:03.580 --> 01:05.060 Was haben Sie über Kurt Gödel gehört? 01:05.180 --> 01:06.860 Was ist der wichtigste Satz von Kurt Gödel? 01:10.080 --> 01:11.400 Der Unvollständigkeitssatz. 01:11.640 --> 01:16.100 Der Unvollständigkeitssatz beschäftigt sich grob damit, was kann ich 01:16.100 --> 01:18.360 beweisen und was kann ich nicht beweisen. 01:19.380 --> 01:25.360 Und ganz vereinfacht gesagt, sagt er, dass in mathematischen Systemen, 01:25.380 --> 01:30.080 die bestimmte Eigenschaften haben, man zeigen kann, dass es Sätze 01:30.080 --> 01:34.500 gibt, die wahr sind, die sich aber nicht beweisen lassen. 01:35.920 --> 01:39.200 Und das ist durchaus eine interessante Sache und das ist auch etwas, 01:39.360 --> 01:42.060 damit müssen wir uns in der theoretischen Informatik beschäftigen, 01:42.140 --> 01:45.160 weil wir unter Umständen uns auch hinterher, das wird so der Höhepunkt 01:45.160 --> 01:48.860 der gesamten GBI-Vorlesung sein, mit der Frage beschäftigen, welche 01:48.860 --> 01:53.960 Probleme können wir überhaupt mit dem Rechner lösen und welche nicht. 01:54.500 --> 01:57.620 Jetzt hatten wir letztes Mal kennengelernt das Aussagenkalkül als 01:57.620 --> 02:01.640 Spezialform eines Kalküls und merken Sie sich immer erstmal, was ist 02:01.640 --> 02:02.320 ein Kalkül? 02:02.320 --> 02:05.980 Ein Kalkül hat zum Beispiel so etwas wie Aktionen, hat ein Alphabet, 02:06.660 --> 02:09.500 hat korrekte Formeln und hat eine Schlussregel. 02:10.040 --> 02:12.720 Und im Aussagenlogischen Kalkül haben wir halt auch ein Alphabet 02:12.720 --> 02:13.740 kennengelernt. 02:13.840 --> 02:16.780 Wir haben die Menge, die formale Sprachen der korrekten Formeln 02:16.780 --> 02:17.400 kennengelernt. 02:17.960 --> 02:21.140 Wir hatten drei Aktionen kennengelernt und als Schlussregel den Modus 02:21.140 --> 02:21.600 Pronens. 02:22.420 --> 02:28.180 Und mit diesem Kalkül sind wir zum Beispiel hergegangen und haben 02:28.180 --> 02:28.980 Dinge bewiesen. 02:30.440 --> 02:34.920 Wir haben zum Beispiel bewiesen, dass bestimmte Sachen eine Tautologie 02:34.920 --> 02:35.280 sind. 02:36.080 --> 02:41.080 Und wenn wir etwas in diesem Kalkül ableiten können, ohne Prämisse, 02:41.440 --> 02:44.480 also rein aus den Aktionen, dann haben wir das Ganze ein Theorem 02:44.480 --> 02:44.980 genannt. 02:47.080 --> 02:58.240 Und dann hatten wir dieses Theorem aufgestellt, das sagt, alle 02:58.240 --> 03:02.200 Aktionen sind Tautologien und der Modus Pronens erhält die 03:02.200 --> 03:03.420 Allgemeingültigkeit. 03:04.120 --> 03:07.540 Das heißt also, alles, das ich ableiten kann, nur aus den Aktionen, 03:07.700 --> 03:11.920 ohne dass ich eine Prämisse habe, ist damit logischerweise automatisch 03:11.920 --> 03:13.020 auch eine Tautologie. 03:15.660 --> 03:18.120 Frage ist, die Umkehrrichtung gilt das auch. 03:19.020 --> 03:23.820 Ist auch jede Tautologie in der Aussagenlogik ein Theorem des Kalküls? 03:23.880 --> 03:27.720 Das heißt, kann ich eine Ableitung aufstellen für jede beliebige 03:27.720 --> 03:30.540 Tautologie, von der ich nachweisen kann, dass es eine Tautologie ist, 03:30.580 --> 03:32.320 zum Beispiel indem ich die Wertetabelle aufstelle. 03:34.300 --> 03:37.320 Und das ist eben gerade jetzt die interessante Frage, ist das 03:37.320 --> 03:40.780 Aussagenlogische Kalkül in dieser Hinsicht vollständig? 03:40.780 --> 03:44.380 Also gilt da zum Beispiel das, was Gödel gesagt hat, im Allgemeinen 03:44.380 --> 03:44.720 nicht. 03:45.160 --> 03:49.460 Gibt es also für jede Tautologie, gibt es da eine Herleitung in diesem 03:49.460 --> 03:50.220 Beweissystem. 03:50.980 --> 03:53.940 Und das ist das Interessante, das kann man zeigen. 03:54.840 --> 03:58.740 Der Satz, den wir also beweisen, lautet, für jede Formel G und H aus 03:58.740 --> 04:02.660 der Menge der aussagenlogischen Formeln gilt diese genau dann, wenn 04:02.660 --> 04:03.180 Beziehung. 04:03.180 --> 04:14.780 Wenn H ableitbar ist aus G, genau dann, wenn aus G, aus G folgt H, 04:14.860 --> 04:17.200 wenn G dann H, ist eine Tautologie. 04:21.080 --> 04:21.980 Einfache Richtung. 04:22.540 --> 04:23.280 Achso, Entschuldigung. 04:26.100 --> 04:29.860 Das beweisen wir nicht, diesen Satz. 04:29.860 --> 04:32.900 Was wir beweisen, ist erstmal dieses Theorien. 04:34.080 --> 04:37.620 Dass wir also erstmal dieses genau dann, wenn zeigen können. 04:37.820 --> 04:42.440 Dass das also dann eine Tautologie ist, wenn wir G als Prämisse haben 04:42.440 --> 04:43.840 und H daraus ableiten wollen. 04:45.000 --> 04:48.940 Und wenn wir das gezeigt haben, dann gilt das auch automatisch für 04:48.940 --> 04:54.940 Tautologien, weil wir dann einfach als Prämisse die leere Menge haben. 04:56.260 --> 05:02.220 Also, die einfache Richtung ist, aus G folgt H, dann muss auch H aus G 05:02.220 --> 05:03.100 ableitbar sein. 05:03.680 --> 05:05.680 Jetzt ist die Frage, wie beweist man so etwas? 05:06.200 --> 05:08.800 Jetzt muss man irgendwie das im Allgemeinen beweisen. 05:09.620 --> 05:13.120 Und da ist das sozusagen ein bisschen ein Meta-Beweis. 05:13.400 --> 05:15.840 Man zeigt, dass es solche Ableitungen gibt. 05:16.180 --> 05:18.060 Eine Ableitung an sich auch ein Beweis. 05:18.500 --> 05:22.800 Man zeigt also, dass es einen Beweis gibt, um das hier beweisen zu 05:22.800 --> 05:23.060 können. 05:23.060 --> 05:25.060 Und so ein Beweis ist eben eine Ableitung. 05:25.240 --> 05:28.840 Das heißt, wenn ich also, wenn G folgt H ableiten möchte aus leeren 05:28.840 --> 05:32.440 Prämissen, dann muss es eben gerade so eine Ableitung geben. 05:32.560 --> 05:33.920 Hatten wir als so ein Tupel dargestellt. 05:34.020 --> 05:37.140 G1 bis Gn, das muss ein Beweis sein. 05:38.220 --> 05:40.360 Gut, was heißt, das muss ein Beweis sein? 05:40.460 --> 05:47.560 Das heißt, dass die letzte Formel Gn, die muss lauten, wenn G dann H. 05:49.260 --> 05:51.060 Muss nicht unbedingt die letzte sein. 05:51.340 --> 05:54.260 Es kann auch eine vorherige sein. 05:54.520 --> 05:57.240 Kann auch irgendein Gi sein mit i kleiner gleich n. 05:58.260 --> 06:00.580 Aber das muss da irgendwo auftauchen. 06:00.860 --> 06:03.460 Nehmen wir den Beweis so, dass wir ihn halt beenden dann, wenn das 06:03.460 --> 06:06.240 erste Mal aus G folgt H auftaucht. 06:06.380 --> 06:07.440 Also sowas muss es geben. 06:09.020 --> 06:17.320 Wie können wir jetzt daraus, aus G folgt H, eine Ableitung finden, 06:17.400 --> 06:19.640 sodass wir aus G H folgern. 06:20.340 --> 06:22.320 Und da H ableiten können. 06:22.780 --> 06:26.100 Und was wir da machen können, ist eben, dass wir diesen Beweis, von 06:26.100 --> 06:28.860 dem wir wissen, dass es existiert, dass wir ihn einfach um zwei 06:28.860 --> 06:29.620 Formeln verlängern. 06:30.220 --> 06:34.400 Wir schreiben jetzt Gn plus 1 gleich G hin, weil G ist ja eben gerade 06:34.400 --> 06:35.120 unsere Prämisse. 06:35.120 --> 06:37.620 Wir hatten gesagt, bei einer Ableitung dürfen wir hinschreiben 06:37.620 --> 06:42.100 Aktionen, Prämissen und alles, was wir mit dem Modus Ponens ableiten. 06:42.640 --> 06:46.900 Und dann haben wir eben gerade da stehen für Gn, wenn G dann H und 06:46.900 --> 06:47.980 dann noch die Prämisse G. 06:48.420 --> 06:52.180 Und dann kann man einfach den Modus Ponens anwenden und kann H 06:52.180 --> 06:54.980 ableiten aus Gn und Gn plus 1. 06:54.980 --> 07:03.460 Und dann da stehen als zweites hinzugefügt ist dann entsprechend H, 07:03.620 --> 07:04.660 gemäß des Modus Ponens. 07:05.120 --> 07:06.580 Das ist die einfache Richtung. 07:06.760 --> 07:11.040 Also wir wissen, wenn aus G folgt H eine Tautologie ist, dann kann ich 07:11.040 --> 07:14.380 H aus G entsprechend ableiten. 07:15.900 --> 07:19.260 Die umgekehrte Richtung ist ein bisschen komplizierter. 07:19.400 --> 07:20.880 Das müssen wir uns ein bisschen genauer anzeigen. 07:20.880 --> 07:26.700 Jetzt wollen wir also zeigen, ich kann aus G H ableiten und dann muss 07:26.700 --> 07:30.340 eben gerade, wenn G dann H, eine Tautologie sein. 07:30.440 --> 07:32.300 Es muss also auch ableitbar sein. 07:33.280 --> 07:38.680 Was wir jetzt machen müssen, ist also einen Beweis konstruieren, der 07:38.680 --> 07:43.400 aus nichts, wenn G dann H ableitet. 07:44.140 --> 07:47.920 Gut, wir wissen, wir können H aus G ableiten. 07:48.040 --> 07:51.500 Das heißt, wir haben wieder so einen Beweis, der aussieht G1 bis Gn, 07:54.300 --> 08:04.040 sodass daraus dann folgt, dass irgendwo das Gn irgendwo H sein muss 08:04.040 --> 08:07.440 und irgendwo ein oberes von den Gs muss halt ein G sein. 08:07.440 --> 08:10.660 Und was wir jetzt machen wollen ist, wir wollen halt so einen Beweis 08:10.660 --> 08:15.480 H1 bis Hm konstruieren und wir würden den gerne konstruieren aus 08:15.480 --> 08:20.420 dieser ursprünglichen Ableitung von, wenn aus G wird H abgeleitet. 08:20.860 --> 08:22.660 Und dafür müssen wir eine Fallunterscheidung machen. 08:23.740 --> 08:28.600 Wir müssen uns unterscheiden, jedes beliebige Gi in dieser Ableitung, 08:28.740 --> 08:29.940 welche Form kann das haben? 08:30.670 --> 08:32.860 Wir hatten gesagt, es können Aktionen sein. 08:33.160 --> 08:41.660 Also, wenn jetzt Gi Aktion ist, dann kann es eines von drei Formeln 08:41.660 --> 08:41.960 sein. 08:45.560 --> 08:52.740 Also, wenn ich sowas habe, wie, wenn Gi, dann G, dann Gi, das wäre es, 08:53.080 --> 08:57.960 das Aktion 1 und Gi entsprechend A. 08:59.340 --> 09:05.920 Also nochmal, wenn Gi, fangen wir nochmal an. 09:06.700 --> 09:11.520 Also, ich möchte zeigen, dass ich so einen Beweis habe und damit ich 09:11.520 --> 09:15.900 so einen Beweis habe, für aus nichts folgt, wenn G dann H, dann muss 09:15.900 --> 09:25.320 ich dieses H1 bis Hm H machen und irgendeines dieser Hi´s muss, müsste 09:25.320 --> 09:29.000 ich zeigen aus, wenn G folgt Gi. 09:29.380 --> 09:33.540 Und das mache ich, dass, wenn ich irgendeines der Gi´s nehme, dann 09:33.540 --> 09:39.280 gibt es ein Hi´ aus diesem Beweis, der eben die Form hat, wenn G, dann 09:39.280 --> 09:39.660 Gi. 09:39.660 --> 09:45.300 Wenn Gi also ein Aktion ist, dann kann ich mithilfe des 09:45.300 --> 09:52.000 aussagenlogischen Aktion´s AL1 entsprechend sowas einfügen, wie, wenn 09:52.000 --> 09:55.060 Gi, dann Gi. 09:56.000 --> 10:02.540 Das Gi ist eben ein Aktion und dann kann ich einfach, indem ich dieses 10:02.540 --> 10:09.260 Aktion 1, das ich aufbaue aus dem Aktion Gi, mithilfe dessen dann 10:09.260 --> 10:13.020 diese beiden Formeln hinzufügen, dann Modus Ponens aus diesen beiden 10:13.020 --> 10:19.160 machen und dann habe ich entsprechend da diese Darstellung, dass da 10:19.160 --> 10:23.860 eben ein, wenn Gi, dann Gi folgt, mithilfe des Modus Ponens. 10:23.860 --> 10:28.380 Das also aus diesem, in diesem Beweis ein Hi gibt, wo eben gerade 10:28.380 --> 10:30.340 dieses, wenn Gi, dann Gi drin steht. 10:31.560 --> 10:38.040 Wenn jetzt dieses Gi gleich Gi Formeln sind für den Beweis der 10:38.040 --> 10:42.980 Tautologie, dann kann ich eben, wenn Gi, dann Gi ableiten. 10:47.380 --> 10:58.420 Oder, dritter Fall, wenn jetzt das Gi einer Formel K2 sei und diese 10:58.420 --> 11:01.380 Formel K2 habe ich durch den Modus Ponens abgeleitet. 11:01.380 --> 11:06.300 Das heißt, es gibt irgendwo eine Formel Gi1, die vor diesem Gi steht, 11:06.780 --> 11:11.200 die lautet, wenn K1, dann K2 und es muss irgendeinen Gi2 geben, das 11:11.200 --> 11:12.160 lautet K1. 11:12.860 --> 11:17.600 Dann, wenn das also drin, wenn also die Voraussetzung gegeben ist, das 11:17.600 --> 11:20.840 Gi ist gleich K2 und ist durch Modus Ponens aus zwei solchen 11:20.840 --> 11:22.720 vorhergehenden Formeln abgeleitet. 11:22.720 --> 11:27.140 Dann muss irgendwo in dieser Kette schon mal drinstehen, wenn Gi, dann 11:27.140 --> 11:34.300 Gi1 und es muss irgendwo schon mal drinstehen, wenn Gi, dann Gi2 und 11:34.300 --> 11:39.440 dann kann ich das mithilfe des dritten Aktions einsetzen, mir daraus 11:39.440 --> 11:44.220 erstmal konstruieren, diesen komplizierten Ausdruck, wenn Gi, dann K1, 11:44.320 --> 11:50.680 dann K2 und dann, wenn Gi, dann K1, dann Gi, dann K2. 11:51.260 --> 11:54.740 Kann ich ein bisschen umformen und dann kann ich darauf zweimal den 11:54.740 --> 11:59.680 Modus Ponens anbinden, weil ich weiß, dass oben diese beiden Formeln 11:59.680 --> 12:04.220 schon vorhanden sind und kann daraus wieder dieses Gi nach Gi1 12:04.220 --> 12:05.200 ableiten. 12:06.340 --> 12:11.500 Das heißt also, für alle drei Fälle, die ich haben kann, das Gi in 12:11.500 --> 12:16.440 diesem Beweis ist eine Aktion, kann ich herleiten, dass dann irgendwo 12:16.440 --> 12:23.120 ich ein Hi haben muss, Hi' haben muss, das heißt, wenn Gi, dann Gi1. 12:23.120 --> 12:27.660 Wenn das Gi gleich Gi ist, also meine Prämisse, dann kann ich zeigen, 12:28.180 --> 12:32.960 dass ich diesen Beweis der Tautologie, wenn Gi, dann Gi nehmen kann, 12:33.160 --> 12:36.240 um eben zu zeigen, dass das Ganze funktioniert, weil wir wissen, wenn 12:36.240 --> 12:42.300 Gi, dann Ha', kann man als Beweis der Tautologie, hat man einen Beweis 12:42.300 --> 12:42.940 der Tautologie. 12:42.940 --> 12:48.420 Das ist eben gerade, kann man entsprechend hernehmen, also das hatten 12:48.420 --> 12:51.660 wir letzte Woche bewiesen, dass dieses Wenn Gi, dann Gi eine 12:51.660 --> 12:52.520 Tautologie ist. 12:52.900 --> 12:55.640 Und dann im dritten Fall, wenn es irgendeine beliebige Formel ist, die 12:55.640 --> 12:58.700 ich durch Modus Ponens hergeleitet habe, dann kann ich auch 12:58.700 --> 13:04.240 entsprechend einen Hi konstruieren, sodass dieses Wenn Gi, dann Gi bei 13:04.240 --> 13:04.740 rauskommt. 13:06.140 --> 13:09.140 Das heißt, auf diese Art und Weise hat man beide Richtungen dieses 13:09.140 --> 13:13.940 Theorems gezeigt und kann dann halt, das bedeutet halt, dass, wenn ich 13:13.940 --> 13:18.400 Ha' aus Gi ableiten kann, dann gilt auch die Formel Wenn Gi, dann Ha', 13:18.400 --> 13:20.360 das ist eine entsprechende Tautologie. 13:23.940 --> 13:24.520 Genau. 13:25.100 --> 13:29.180 Das also noch zum letzten Thema der Aussagenlogik. 13:30.260 --> 13:34.160 Was Sie jetzt mitnehmen sollten, ganz wichtig, erstmal rein, 13:34.300 --> 13:37.840 fundamental, wenn wir die Aussagenlogik aufbauen, unterscheiden wir 13:37.840 --> 13:38.360 zwei Dinge. 13:38.520 --> 13:40.980 Das eine ist die Syntax und das andere ist die Semantik. 13:40.980 --> 13:44.340 Wir haben uns erst angeschaut, wie kann ich erstmal syntaktisch 13:44.340 --> 13:47.520 korrekte Formen aufbauen, unabhängig davon, was sie bedeuten. 13:48.220 --> 13:50.960 Und wir haben das gemacht, indem wir mit formalen Sprachen gearbeitet 13:50.960 --> 13:51.480 haben. 13:51.600 --> 13:53.860 Das heißt also, die Definition der syntaktisch korrekten 13:53.860 --> 13:59.480 Aussagenlogischen Formeln ist nichts anderes als ein Spezialfall, als 13:59.480 --> 14:01.880 ein Anwendungsfall für formale Sprachen. 14:02.000 --> 14:04.340 Das ist also etwas, wo formale Sprachen mal nützlich sein können. 14:04.340 --> 14:06.660 Und dann haben wir uns die Semantik angeschaut. 14:06.780 --> 14:10.460 Und bei der Semantik haben wir uns halt angeschaut, erstmal was ist 14:10.460 --> 14:14.140 eine Interpretation, eine Interpretation als Belegung der Variablen 14:14.140 --> 14:19.740 und dann diese Funktion Value als Auswertung der gesamten Formeln in 14:19.740 --> 14:22.240 Abhängigkeit von einer konkreten Interpretation. 14:23.100 --> 14:26.180 Die Auswertung ist die gesamte Formel wahr oder falsch. 14:26.180 --> 14:29.700 Und dann haben wir so spezielle Namen zugeordnet, dann gab es so etwas 14:29.700 --> 14:32.520 wie ein Modell, es gab so etwas wie eine Tautologie. 14:33.100 --> 14:37.960 Und dann haben wir uns halt das Kalkül angeschaut, mit dem wir Formeln 14:37.960 --> 14:44.680 beweisen können und gesehen, dass also diese Allgemeingültigkeit durch 14:44.680 --> 14:46.560 das Kalkül erhalten wird. 14:49.610 --> 14:53.570 Die boolischen Funktionen waren der Bestandteil, mit dem wir die 14:53.570 --> 14:55.530 Semantik aufbauen konnten. 14:56.050 --> 14:59.350 Und dann gab es neben den boolischen Funktionen bei der Syntax diese 14:59.350 --> 15:04.330 Konstruktionsformeln, mit der wir aussagenlogische Formeln syntaktisch 15:04.330 --> 15:08.670 zusammensetzen konnten, aber hatten das Problem, dass wir damit mehr 15:08.670 --> 15:10.810 Formeln zusammensetzen konnten, als wir wollten. 15:10.810 --> 15:13.670 Wir konnten im Prinzip beliebige Wörter über dem Alphabet 15:13.670 --> 15:14.430 zusammensetzen. 15:14.990 --> 15:19.090 Wir wollten aber nur eine Teilmenge haben, eine formale Sprache aller 15:19.090 --> 15:21.230 Wörter über dem Alphabet, der Aussagenlogik. 15:21.690 --> 15:24.370 Und das haben wir dann noch mit einer anderen Technik gemacht, und 15:24.370 --> 15:26.810 zwar mit Hilfe der induktiven Definition. 15:26.810 --> 15:29.930 So wie Sie induktive Definition schon kennengelernt hatten bei 15:29.930 --> 15:35.250 Potenzen von Wörtern, haben wir da jetzt mit Hilfe der Anwendung von 15:35.250 --> 15:39.350 induktiver Definition und diesen Konstruktionsformeln die formale 15:39.350 --> 15:41.550 Sprache dann induktiv definiert. 15:42.710 --> 15:48.410 Und dieses induktive Definieren ist halt schon mehrmals erwähnt 15:48.410 --> 15:53.510 worden, ist halt so wichtig, dass wir dem halt entsprechend ein ganzes 15:53.510 --> 15:57.210 Kapitel widmen, wo wir nochmal so einzelne Aspekte des induktiven 15:57.210 --> 15:58.390 Vorgehens uns anschauen. 16:01.830 --> 16:04.390 Deswegen schauen wir uns dann nochmal an die vollständigen 16:04.390 --> 16:07.690 Induktionen, sowohl für die Definition als auch für den Beweis. 16:08.250 --> 16:11.930 Und dann interessanter insbesondere auch Varianten der vollständigen 16:11.930 --> 16:14.530 Induktion, also was kann man unter Umständen noch anders machen. 16:15.430 --> 16:18.190 Und wie gesagt, nochmal ein bisschen was zum Thema induktive 16:18.190 --> 16:18.810 Definition. 16:20.790 --> 16:27.230 Also Potenzen von Wörtern hatten wir schon entsprechend definiert. 16:28.350 --> 16:32.770 Wir hatten gesagt, für jedes Wort über einem Alphabet sei halt w hoch 16:32.770 --> 16:36.010 0 gleich y und w hoch n plus 1 ist gleich wn mal wn. 16:38.290 --> 16:43.310 Und wir hatten diesen einfachen Satz, dass für jedes Wort aus a 16:43.310 --> 16:48.170 Sternchen und für jedes n aus den natürlichen Zahlen halt gilt, dass 16:48.170 --> 16:53.850 die Länge des Wortes w hoch n eben gleich n mal der Länge des Wortes w 16:53.850 --> 16:55.110 sein sollte. 16:57.230 --> 17:00.810 Jetzt ist die Frage, das leuchtet einem ein, wie beweist man das? 17:01.490 --> 17:05.690 Standard Vorgehen, wenn man schon eine induktive Definition hat, dann 17:05.690 --> 17:09.530 könnte wahrscheinlich induktiver Beweis, Beweis durch vollständige 17:09.530 --> 17:10.710 Induktion wichtig sein. 17:11.630 --> 17:16.870 Also, wenn man es ein bisschen rechnet, w hoch 0 gleich y, ja, hat 17:16.870 --> 17:18.550 Länge 0, passt. 17:19.250 --> 17:24.190 Dann w hoch n plus 1 gleich w hoch n mal w, also w1 ist gleich y, 17:24.570 --> 17:28.550 konkateniert mit w, ist also gleich w, hat Länge 1 mal w, passt. 17:28.550 --> 17:33.690 w2 ist halt w hoch 1, konkateniert mit w, ist w, konkateniert mit w, 17:33.790 --> 17:37.410 hat Länge 2 mal w, w hoch 3 und so weiter und so fort, hat 17:37.410 --> 17:41.810 dementsprechend auch Länge 3w, wenn man das in diese induktive 17:41.810 --> 17:46.030 Definition der Potenzierung von Wörtern halt einsteckt. 17:47.390 --> 17:52.750 Also, das ist offensichtlich einfach und kann man damit rechnen und 17:52.750 --> 17:56.110 was einem halt auffällt, wenn man das für n gleich 2 durchrechnet, 17:56.510 --> 18:02.550 dann ist n2 genau deswegen richtig, weil nämlich das Ganze für n 18:02.550 --> 18:04.110 gleich 1 auch richtig war. 18:04.110 --> 18:07.510 Und wenn man n gleich 3 durchrechnet, dann sieht man halt, wenn man 18:07.510 --> 18:10.550 ausrechnet, das ist gerade deshalb wichtig, weil es für n gleich 2 18:10.550 --> 18:12.650 auch richtig war. 18:13.410 --> 18:16.310 Und wir hatten schon kennengelernt, das Prinzip der vollständigen 18:16.310 --> 18:16.950 Induktion. 18:16.950 --> 18:21.130 Angenommen, wir haben eine Menge m, die enthält Zahlen aus den 18:21.130 --> 18:26.650 natürlichen Zahlen, 0 ist in der Menge m und wir können für jedes n 18:26.650 --> 18:32.950 aus n0 anzeigen oder annehmen, dass wenn n aus der Menge m ist, dann 18:32.950 --> 18:34.970 ist auch n plus 1 n aus der Menge m. 18:34.970 --> 18:39.590 Und wenn wir das zeigen können, dann ergibt sich eben gerade, dass 18:39.590 --> 18:42.490 diese Menge m gleich der Menge der natürlichen Zahlen ist. 18:44.230 --> 18:49.310 Wenn man das Ganze jetzt auf das Beweisen von Aussagen festlegt, dann 18:49.310 --> 18:52.010 macht man das eben so, dass diese Aussage, die man beweisen will, 18:52.090 --> 18:53.850 irgendwie parametrisiert ist über ein n. 18:53.850 --> 18:58.490 Das ist also eine Aussage a, die irgendwie abhängig ist von einem n 18:58.490 --> 19:02.210 aus den natürlichen Zahlen und man würde gerne beweisen, dass diese 19:02.210 --> 19:06.130 Aussage an für jedes n aus den natürlichen Zahlen gilt. 19:06.670 --> 19:12.610 Das heißt, man zeigt, dass n0 gerade die Menge der n aus n0 ist, für 19:12.610 --> 19:15.610 die dieses a abhängig von dem n wahr ist. 19:17.950 --> 19:25.490 Also, wenn also gilt a0 und wenn also gilt für jedes n, wenn an gilt, 19:25.630 --> 19:32.550 dann gilt auch an plus 1, dann gilt auch für jedes n Element n0 an, 19:32.790 --> 19:35.610 gemäß dem Prinzip der vollständigen Induktion. 19:35.610 --> 19:39.230 Und das ist dieses Beweisschema, das wir dann halt entsprechend immer 19:39.230 --> 19:39.930 anwenden werden. 19:40.730 --> 19:43.490 Wenn man also einen induktiven Beweis hinschreibt, dann muss das ein 19:43.490 --> 19:44.510 Automatismus werden. 19:44.630 --> 19:48.730 Man schreibt hin, was ist der Induktionsanfang und macht dann den 19:48.730 --> 19:49.890 Induktionsschritt. 19:50.750 --> 19:56.470 Und den Induktionsschritt zeigt man für jedes n Element n0, wenn an, 19:57.010 --> 19:58.410 dann an plus 1. 19:58.410 --> 20:02.590 Und dieses an ist eben gerade die Induktionsvoraussetzung. 20:03.570 --> 20:08.110 Und da hapert es manchmal, wenn man da Beweise sieht, wie diese 20:08.110 --> 20:10.470 Induktionsvoraussetzung hingeschrieben wird. 20:11.070 --> 20:14.090 Und das ist dann ein Satz, den müssen Sie sich einfach merken, wenn 20:14.090 --> 20:16.790 Sie hinschreiben die Induktionsvoraussetzung. 20:17.710 --> 20:23.830 Dann schreiben Sie, es sei n ein beliebiges, aber festes Element aus 20:23.830 --> 20:30.150 n0 und es gelte für dieses feste und beliebige n aus n0 die Aussage 20:30.150 --> 20:30.510 an. 20:31.150 --> 20:33.090 Das ist die Induktionsvoraussetzung. 20:33.530 --> 20:40.950 Es gibt häufig Leute, die sagen, naja für alle n aus n0 gelte die 20:40.950 --> 20:42.610 Induktionsvoraussetzung. 20:43.250 --> 20:47.830 Das kann man eben nicht machen, weil, wenn es ja eh schon für alle n 20:47.830 --> 20:50.290 gilt, dann brauche ich nicht mehr zu beweisen, dass es für alle n 20:50.290 --> 20:50.550 gilt. 20:50.550 --> 20:54.750 Sondern was ich machen will bei der Voraussetzung, es gilt für ein n. 20:55.410 --> 20:58.430 Es ist ein beliebiges n aus den natürlichen Zahlen, aber es gilt nur 20:58.430 --> 20:59.550 für dieses eine n. 21:00.070 --> 21:03.670 Und wenn es für dieses eine n gilt, dann zeige ich, dass es auch für 21:03.670 --> 21:04.990 das an plus 1 gilt. 21:05.490 --> 21:10.190 Und wenn es dann zusätzlich noch für a0 gilt, dann habe ich den Beweis 21:10.190 --> 21:11.910 nach der vollständigen Induktion gemacht. 21:16.310 --> 21:20.050 Also unsere Aussage in unserem konkreten Beispiel lautet halt, die 21:20.050 --> 21:25.170 Länge des Wortes w hoch n mit n aus den natürlichen Zahlen sei n mal 21:25.170 --> 21:27.510 Länge des Wortes w. 21:28.430 --> 21:34.390 Das sei die Induktionsannahme oder die zu beweisende Aussage. 21:34.390 --> 21:38.490 Den Induktionsanfang zeigen wir für n gleich 0, hatten wir schon 21:38.490 --> 21:39.930 gerechnet, passt. 21:40.950 --> 21:44.990 Dafür gilt die Aussage 0 mal Länge des Wortes ist gleich die Länge 21:44.990 --> 21:47.790 Worte von w hoch 0 gleich y, gemäß Definition. 21:49.910 --> 21:55.710 Und jetzt müssen wir eben das zeigen, dass für jedes n gilt, wenn für 21:55.710 --> 21:59.870 ein festes, aber beliebiges n aus den natürlichen Zahlen gilt Länge 21:59.870 --> 22:03.730 von w hoch n gleich n mal w, dann müssen wir zeigen, dass auch die 22:03.730 --> 22:08.110 Länge von w hoch n plus 1 gleich n plus 1 mal die Länge von w ist. 22:08.850 --> 22:14.890 Und da wir halt das ganze Induktiv definiert hatten, wie dieses w hoch 22:14.890 --> 22:20.070 n plus 1 aufgebaut ist, wendet man jetzt an dieser Stelle bei dem 22:20.070 --> 22:24.370 Induktionsschritt eben gerade die Definition, die induktive Definition 22:24.370 --> 22:24.650 an. 22:24.650 --> 22:30.290 Das heißt, wir zerlegen die Länge von w hoch n plus 1 gleich die Länge 22:30.290 --> 22:33.970 von, gemäß der induktiven Definition, w hoch n mal w. 22:35.610 --> 22:39.950 Und das ist eben gerade nach der Definition von Induktion und Betrag 22:39.950 --> 22:42.910 die Länge von w hoch n plus die Länge von w. 22:43.490 --> 22:46.110 Und jetzt können wir die Induktionsvoraussetzung anwenden. 22:46.550 --> 22:51.470 Die Länge von w hoch n ist gerade gleich n mal die Länge von w, darauf 22:51.470 --> 22:54.410 kommt nochmal die Länge von w und das ist entsprechend nach der 22:54.410 --> 22:57.050 Arithmetik in den natürlichen Zahlen, weil die Längen sind natürliche 22:57.050 --> 23:00.690 Zahlen, n plus 1 mal die Länge w. 23:00.690 --> 23:02.830 Das ist der Induktionsschritt. 23:06.450 --> 23:08.990 Und hier ist es halt wichtig, hier ist es halt sehr ausführlich 23:08.990 --> 23:09.290 gesprochen. 23:09.730 --> 23:11.450 Es sei n Element null. 23:12.750 --> 23:17.770 Es sei, wenn man es aussprüchlich sprechen möchte, es sei n ein 23:17.770 --> 23:20.130 beliebiges, aber festes Element aus n null. 23:20.390 --> 23:22.250 Das heißt, es sei n Element null. 23:25.150 --> 23:26.890 So weit, so einfach. 23:27.410 --> 23:31.750 Was man jetzt anfangen kann, ist, dass man ein bisschen variiert. 23:32.230 --> 23:35.550 Eine Variation ist zum Beispiel, dass man den Induktionsanfang 23:35.550 --> 23:36.510 woanders hinlegt. 23:37.230 --> 23:43.450 Also bisher Induktionsanfang immer bei n gleich 0, aber was ist, wenn 23:43.450 --> 23:46.090 ich ein n größer gleich 1 wähle? 23:46.870 --> 23:49.830 Das kann zum Beispiel dann nützlich sein, wenn ich zeigen will, dass 23:49.830 --> 23:53.510 eine Aussage nicht für alle n aus n null gilt, sondern zum Beispiel 23:53.510 --> 23:57.650 für ein n, das größer gleich einem bestimmten Wert, einer bestimmten 23:57.650 --> 23:58.690 Konstante c ist. 23:59.030 --> 24:16.050 Zum Beispiel größer gleich 1 wollen wir a n zeigen. 24:16.050 --> 24:17.870 Dann ist auch a n plus 1 wahr. 24:18.790 --> 24:22.570 Und da kann man jetzt durchaus auch die Annahme machen, dass das a n 24:22.570 --> 24:26.470 größer gleich 1 ist. 24:26.570 --> 24:31.670 Also dieses beliebige, feste n aus Element der natürlichen Zahlen, das 24:31.670 --> 24:34.590 soll halt 1 sein, für die a n wahr ist. 24:34.670 --> 24:38.030 Und dann kann man durchaus verwenden, dass das größer gleich im 24:38.030 --> 24:41.710 Induktionsanfang ist, also größer gleich 1 ist. 24:43.150 --> 24:47.110 Oder, dass wenn man jetzt diesen Induktionsschritt durchführt, dann 24:47.110 --> 24:50.870 benutzt man nicht nur das, was man vorher schon gezeigt hat, das man 24:50.870 --> 24:54.890 also gezeigt hat, es gilt für a n, also gilt es auch für a n plus 1, 24:55.350 --> 24:59.610 sondern wenn man diesen Schritt macht von n nach n plus 1, dann sagt 24:59.610 --> 25:06.430 man, sei die Aussage a n wahr für alle n kleiner gleich einer 25:06.430 --> 25:07.430 Konstanten c. 25:08.070 --> 25:11.370 Und dann zeige ich das Ganze für a c plus 1. 25:12.190 --> 25:18.290 Oder sei halt in anderen Worten, sei die Aussage a i wahr für alle i 25:18.290 --> 25:19.210 kleiner gleich n. 25:19.670 --> 25:23.130 Und daraus folgt, kann ich dann zeigen, dass a n plus 1 wahr ist. 25:23.970 --> 25:28.510 Und wenn ich das machen kann, dann habe ich auch gezeigt, dass es für 25:28.510 --> 25:29.830 alle natürlichen Zahlen gilt. 25:31.030 --> 25:33.490 Manchmal braucht man auch mehrere Induktionsanfänge. 25:33.790 --> 25:37.270 Das heißt zum Beispiel, es kann sein, dass a 1 nicht automatisch aus a 25:37.270 --> 25:37.910 0 folgert. 25:38.250 --> 25:40.970 Oder dass a 2 nicht automatisch aus a 1 folgt. 25:41.450 --> 25:45.470 Sondern ich muss erstmal für eine bestimmte endliche Anzahl, a 0, a 1, 25:45.530 --> 25:50.450 a 2 und so weiter, a 3, irgendwas Überschaubares beweisen, dass die 25:50.450 --> 25:51.410 Aussage wahr ist. 25:51.730 --> 25:56.110 Und erst dann kann ich mit Hilfe vollständiger Induktion anfangen, das 25:56.110 --> 25:56.730 zu beweisen. 25:57.590 --> 26:01.370 Das kann zum Beispiel dann sein, wenn ich eine induktive Definition 26:01.370 --> 26:05.850 habe, bei der halt nicht nur ein Induktionsanfang festgelegt ist, 26:06.030 --> 26:10.030 sondern bei dem am Anfang erstmal a 1, a 2, a 3 festgelegt ist. 26:10.450 --> 26:14.530 Und aus den drei per Hand festgelegten Dingern kann ich dann die 26:14.530 --> 26:17.370 anderen Sachen ableiten, definieren. 26:18.750 --> 26:21.570 Jetzt ist das ja erstmal prinzipiell was anderes, als dieses 26:21.570 --> 26:23.070 ursprüngliche Induktionsschema. 26:23.230 --> 26:27.170 Und dieses Prinzip der vollständigen Induktion gilt erstmal 26:27.170 --> 26:28.250 theoretisch nicht. 26:28.810 --> 26:31.870 Das Schöne ist aber, dass man all diese Varianten in das 26:31.870 --> 26:34.730 Originalschema pressen kann, wenn man das denn möchte. 26:35.250 --> 26:38.530 Man kann das zum Beispiel dadurch machen, dass man die Aussage 26:38.530 --> 26:43.150 umformuliert in eine Aussage, die dann wieder reinpasst mit nur einem 26:43.150 --> 26:44.210 Induktionsanfang. 26:44.730 --> 26:48.190 Oder wenn man zum Beispiel nur für n größer gleich 1 das machen will, 26:48.530 --> 26:51.330 dann kann ich das einfach reinpressen, indem ich sage, okay, ich habe 26:51.330 --> 26:55.230 hier eine Aussage, die ist parametrisiert über n minus 1. 26:56.750 --> 26:58.710 Und dann passt es plötzlich wieder von 0. 26:58.810 --> 27:01.390 Oder wenn ich bei 3 anfange, dann ist sie halt nicht parametrisiert 27:01.390 --> 27:07.230 über a n, sondern ist sie parametrisiert über a n plus 3, a n minus 3. 27:07.330 --> 27:10.350 Damit kann ich dann sozusagen den Anfang, an dem ich die Induktion 27:10.350 --> 27:12.930 laufen lasse, nach links und rechts verschieben. 27:16.070 --> 27:19.290 Dementsprechend kann man also diese vollständige Induktion ein 27:19.290 --> 27:20.930 bisschen vereinfachen. 27:22.170 --> 27:28.110 Sei also b n eine Aussage, die gelten soll für jedes n aus n 0. 27:28.650 --> 27:33.510 Das will man beweisen, dass diese Aussage b n für jedes n Element in 0 27:33.510 --> 27:35.950 existiert, wahr ist. 27:35.950 --> 27:41.610 Dann definiert man jetzt sich eine Aussage a n, eine Art Hilfsaussage, 27:42.310 --> 27:48.190 die lautet für jedes i aus n 0 mit i kleiner gleich n ist b i wahr. 27:49.470 --> 27:53.450 Und das ist dann wieder eine Aussage, die ist rein parametrisiert über 27:53.450 --> 27:57.590 a n und kann jetzt wieder mit vollständiger, mit der ursprünglichen 27:57.590 --> 28:00.790 Schema vollständiger Induktion bewiesen werden. 28:01.730 --> 28:04.550 Beweise also, dass jedes n 0 b a n wahr ist. 28:04.630 --> 28:07.070 Ich habe einen Induktionsanfang und mache dann immer nur den Schritt 28:07.070 --> 28:10.830 von, es gelte a n und mache den Schritt auf a n plus 1. 28:12.710 --> 28:15.150 Denn aus a n folgt b n. 28:15.310 --> 28:19.230 Wenn a n wahr ist, dann ist gleichzeitig auch b n wahr. 28:19.350 --> 28:22.150 Und wenn ich a n gezeigt habe, nach dem ursprünglichen Schema der 28:22.150 --> 28:25.090 vollständigen Induktion, dann habe ich eben b n gezeigt. 28:25.090 --> 28:27.950 Und wenn man es sich anschaut, dann macht man eben gerade nichts 28:27.950 --> 28:31.650 anderes, als dass man versteckt beim Induktionsschritt halt darauf 28:31.650 --> 28:36.490 zurückgreift, dass alle Aussagen kleiner gleich n gelten und dass ich 28:36.490 --> 28:40.370 daraus dann n plus 1 herleite und nicht einfach nur aus n nach n plus 28:40.370 --> 28:40.730 1. 28:41.150 --> 28:46.450 Durch diesen Zwischenschritt mache ich halt eine Hilfsaussage, die das 28:46.450 --> 28:49.710 gerade wieder in dieses ursprüngliche Schema reinpasst. 28:50.990 --> 28:52.390 Ja, das ist das, was ich sage. 28:52.470 --> 28:56.670 Also hier macht man halt jetzt für a n wieder den Standardbeweis für n 28:56.670 --> 28:57.190 gleich 0. 28:57.410 --> 29:00.950 Dann zeigen wir den Induktionsschritt, wenn n gilt, dann gilt n plus 29:00.950 --> 29:01.370 1. 29:02.050 --> 29:09.150 Und wenn a n plus 1 gilt, dann gilt halt entsprechend auch, für jedes 29:09.150 --> 29:11.610 i gilt, dann gilt entsprechend auch b i. 29:20.980 --> 29:24.320 Und dementsprechend haben wir auch gesehen, diese induktiven 29:24.320 --> 29:25.300 Definitionen. 29:25.660 --> 29:28.580 Was man jetzt noch ein bisschen darauf achten muss, wenn man mal eine 29:28.580 --> 29:31.520 induktive Definition sieht oder wenn man selber eine induktive 29:31.520 --> 29:34.440 Definition macht, ist diese Festlegung sinnvoll. 29:35.340 --> 29:39.200 Sehr gut, dieses einfache Beispiel mit den Potenzen von Wörtern, da 29:39.200 --> 29:41.380 sieht man, ja, das ist sinnvoll. 29:41.460 --> 29:42.460 Und warum ist es sinnvoll? 29:43.340 --> 29:49.000 Es wird eben immer für jedes w hoch n festgelegt, was es sein kann. 29:49.700 --> 29:53.940 Und für jedes w hoch n wird auch nur ein Wert festgelegt, der es sein 29:53.940 --> 29:54.220 kann. 29:54.220 --> 29:57.320 Bei so einer einfachen Definition kann man das einfach machen durch 29:57.320 --> 29:57.880 drauf gucken. 29:58.340 --> 30:02.420 Und lange Zeit hat man auch gedacht in der theoretischen Informatik, 30:02.760 --> 30:05.700 die meisten Sachen und Programme und Probleme, die ich so beschreiben 30:05.700 --> 30:09.220 kann, die kann man häufig mit so einfachen Induktionen beschreiben und 30:09.220 --> 30:10.980 dann ist das auch schön definiert. 30:13.880 --> 30:18.160 Allerdings ist man dann später draufgekommen, dass es unter Umständen 30:18.160 --> 30:21.500 Sachen gibt, die vielleicht ein bisschen komplizierter sind, die nicht 30:21.500 --> 30:24.780 so einfache Induktionen sind, wo man nicht einfach so durch drauf 30:24.780 --> 30:30.060 blicken sieht, dass wirklich alles schön vollständig definiert ist. 30:30.060 --> 30:36.760 Das sind dann sogenannte komplexe induktive Definitionen und komplex 30:36.760 --> 30:41.240 induktive Funktionen, mit denen man sich lange Zeit sehr schwer getan 30:41.240 --> 30:41.660 hat. 30:43.220 --> 30:47.920 Und eine ganz berühmte komplex induktiv definierte Funktion ist die 30:47.920 --> 30:49.120 sogenannte Ackermann Funktion. 30:49.220 --> 30:50.820 Hat die irgendjemand schon mal in der Schule gesehen? 30:51.820 --> 30:52.980 Weil die ist ganz lustig. 30:52.980 --> 30:55.820 Ein, zwei, drei Leute haben die schon mal gesehen. 30:56.660 --> 30:57.160 Vier Leute. 30:57.580 --> 31:00.980 Also so ein paar, manchmal in der Mathematik und in der Informatik im 31:00.980 --> 31:04.020 Unterricht wird die verwendet, weil die ist eigentlich eine relativ 31:04.020 --> 31:05.200 faszinierende Funktion. 31:05.800 --> 31:09.340 Die gibt es in unterschiedlichen Definitionen, weil am Anfang der Herr 31:09.340 --> 31:13.840 Ackermann hatte die ein bisschen komplizierter definiert und hinterher 31:13.840 --> 31:17.380 kamen andere Forscher, zum Beispiel der Herr Peter, der hat gezeigt, 31:17.520 --> 31:20.700 dass es eine Definition gibt, die äquivalent ist, aber deutlich 31:20.700 --> 31:21.260 einfacher. 31:21.260 --> 31:23.840 Und das ist eine, die man heutzutage gerne verwendet. 31:24.500 --> 31:28.780 Und das ist eindeutig irgendwie eine induktive Definition, aber wir 31:28.780 --> 31:31.300 haben jetzt halt hier zwei Variablen, über die gelaufen wird. 31:31.300 --> 31:35.820 Wir definieren erstmal, dass für jedes Y aus den natürlichen Zahlen, 31:35.940 --> 31:39.000 sei halt die Ackermann-Funktion, die über zwei Parameter definiert 31:39.000 --> 31:42.920 ist, A von 0 und Y sei gleich Y plus 1. 31:44.200 --> 31:48.780 Das ist offensichtlich eine Art Induktionsanfang für jeden Wert von Y 31:48.780 --> 31:55.500 und für X gleich 0 wird ein eindeutig fester Wert festgelegt. 31:55.840 --> 31:57.220 Da passiert nichts mehr Induktives. 31:57.220 --> 32:02.700 Und dann folgen zwei Induktive, noch eine zweite 32:02.700 --> 32:08.420 Induktionsanfangsdefinition, das ist dieses AX plus 1 und 0, das ist 32:08.420 --> 32:09.920 eben gleich A von X und 1. 32:10.020 --> 32:11.840 Und das ist jetzt schon eine induktive Definition. 32:12.040 --> 32:16.720 Das heißt, ich definiere für AX plus 1, was ist der Wert in 32:16.720 --> 32:17.900 Abhängigkeit von X. 32:18.760 --> 32:23.840 Nämlich AX plus 1 von 0 soll eben gerade sein AX von 1. 32:24.960 --> 32:30.800 Und dann habe ich eine weitere Definition, die mir jetzt auch noch das 32:30.800 --> 32:33.920 Y mit einschließt und da macht man dann einen Schritt sowohl in dem X 32:33.920 --> 32:38.620 als auch in dem Y und sagt halt AX plus 1 und Y plus 1, das ist eben 32:38.620 --> 32:43.760 gleich A von X und an der zweiten Stelle kommt rein der Wert AX plus 1 32:43.760 --> 32:44.980 von Y. 32:47.460 --> 32:50.940 Und dann sieht das Ganze schon ein bisschen komplizierter aus. 32:51.020 --> 32:53.480 So beim drüberblicken sieht man ja auch, das ist relativ einfach 32:53.480 --> 32:57.360 definiert, das kann ja gar nicht so wild sein. 32:58.280 --> 33:01.040 Und dann kann man mal anfangen ein bisschen mit der Funktion 33:01.040 --> 33:02.980 rumzuspielen und zum Beispiel was auszurechnen. 33:03.780 --> 33:07.060 Und jetzt nimmt man einen relativ harmlosen Wert und guckt sich mal 33:07.060 --> 33:10.020 an, was ist denn A2,2? 33:10.860 --> 33:13.660 Das ist ja relativ niedrige Werte, da sind wir noch nicht sonderlich 33:13.660 --> 33:17.160 weit in der Funktion und dann fängt man mal an zu rechnen. 33:17.160 --> 33:22.200 Und dann sieht man, okay A2,2, das ist hier der dritte Fall, da wird 33:22.200 --> 33:29.360 das eben zurückgeführt, das X geht auf 1 runter an der ersten Stelle 33:29.360 --> 33:32.000 und an der zweiten Stelle kommt halt diese Akkumentfunktion von dem 33:32.000 --> 33:36.200 ursprünglichen X, also von 2 und das Y geht um 1 runter von 1. 33:36.960 --> 33:38.460 Gut, muss man weiter rechnen. 33:38.580 --> 33:46.640 Also A1 von irgendwas muss man sich erstmal innen drin anschauen, dass 33:46.640 --> 33:50.480 man sich diese Akkumentfunktion, die innen drin ist, auflöst, bevor 33:50.480 --> 33:53.300 man beantworten kann, was A1 von irgendwas ist, weil ich muss ja 33:53.300 --> 33:56.960 wissen, was ist der Wert von A2,1, bevor ich nachgucken kann, welcher 33:56.960 --> 33:59.980 Fall ist es da oben, wenn zum Beispiel der Fall 0 ist, dann muss ich 33:59.980 --> 34:03.520 was anderes einsetzen, als wenn es ein anderer Wert ist. 34:04.260 --> 34:08.000 Also muss ich A2,1 ausrechnen, okay, das ist wieder hier der gleiche 34:08.000 --> 34:17.800 Fall, das ist eben gerade A von 1, das ist A von 1, also das X wird 34:17.800 --> 34:20.900 von 1 runtergezählt und dann wieder Akkumentfunktion vom 34:20.900 --> 34:23.520 ursprünglichen X,2 und das 1 wird runtergezählt, ist 0. 34:24.740 --> 34:27.680 Gut, das ist schon mal nicht verkehrt, dann bin ich da oben dann jetzt 34:27.680 --> 34:31.100 im mittleren Fall, den ich hinten für das A2,0 einsetzen muss und dann 34:31.100 --> 34:37.780 kommt da gerade raus, das ist eben nach der Definition A von 1,1, nach 34:37.780 --> 34:41.980 der mittleren Definition, okay, A von 1,1, da geht dann wieder das 34:41.980 --> 34:48.420 Spiel los mit dem dritten Fall, da kommt dann drin A von 1,0, A von 1 34:48.420 --> 34:51.460 ,0 ist wieder der mittlere Fall, das wird A von 0,1. 34:52.020 --> 34:55.960 Das ist wiederum dann endlich mal der obere Fall, das heißt, da kann 34:55.960 --> 35:00.020 ich was vernünftiges reinsetzen, A von 0,1, das weiß ich, das ist 1 35:00.020 --> 35:00.920 plus 1 ist 2. 35:01.460 --> 35:03.480 Dann kann ich das erste Mal ein Stück hoch gehen. 35:04.200 --> 35:06.760 Dann habe ich das ein bisschen verkürzt und dann muss ich weiter 35:06.760 --> 35:09.460 rechnen und weiter rechnen und weiter rechnen und weiter rechnen. 35:09.920 --> 35:12.480 Man sieht schon, da rechnet man relativ lange. 35:13.280 --> 35:17.340 Das ist zwar eine relativ kurze Definition und relativ niedrige Werte, 35:17.740 --> 35:20.500 aber ich muss da relativ lange rechnen. 35:21.920 --> 35:25.180 Und jetzt setzt man sich hin und überlegt mal, was passiert denn 35:25.180 --> 35:27.740 überhaupt bei diesen drei Fällen, die ich habe. 35:27.920 --> 35:30.480 Was ist, wenn ich sowas zum Beispiel ausrechnen möchte, wie mache ich 35:30.480 --> 35:33.280 das, wie fasse ich das geschickt in ein kleines Programm. 35:34.060 --> 35:36.180 Und dann habe ich halt drei Fälle. 35:38.500 --> 35:45.860 Der erste Fall ist der einfache, wenn irgendwas 0,1 Wert dasteht und 35:45.860 --> 35:47.280 zwar an der ganz letzten Stelle. 35:47.560 --> 35:51.380 Also diese A-Rekursion funktioniert ja immer an der zweiten Stelle. 35:51.640 --> 35:54.700 Man sieht also, man immer an der zweiten Position von der 35:54.700 --> 35:58.640 ursprünglichen Ackermannfunktion wird was eingesetzt und dann in 35:58.640 --> 36:01.600 dieser inneren Ackermannfunktion wird wieder an der zweiten Stelle 36:01.600 --> 36:02.660 irgendwas erweitert. 36:02.660 --> 36:06.180 Und da wird wieder immer dann, wenn also dieser dritte Fall greift, 36:06.540 --> 36:09.720 wird immer an der zweiten Stelle der innersten Ackermannfunktion das 36:09.720 --> 36:11.940 Ganze nochmal um eine Ackermannfunktion erweitert. 36:13.140 --> 36:15.340 Das passiert mir nie bei der ersten Stelle. 36:15.440 --> 36:17.220 Bei der ersten Stelle kann das nie funktionieren. 36:17.680 --> 36:18.340 Passiert das nie. 36:19.120 --> 36:20.880 Bei der ersten Stelle wird das nie eingesetzt. 36:20.880 --> 36:26.280 Und wenn irgendwann der zweite Wert bei 0 ist, dann wird das Ganze 36:26.280 --> 36:28.420 wieder durch eine andere Ackermannfunktion ersetzt. 36:28.540 --> 36:31.260 Dann wird sozusagen die letzten beiden Parameter, die da ganz innen 36:31.260 --> 36:33.460 stehen, durch zwei andere Parameter ersetzt. 36:33.680 --> 36:35.840 Wird beim mittleren Fall eine Ackermannfunktion durch eine andere 36:35.840 --> 36:36.980 Ackermannfunktion ersetzt. 36:36.980 --> 36:42.600 Und erst wenn sozusagen der vorletzte, die vorletzte Zahl bei 0 ist, 36:43.480 --> 36:49.800 dann kann ich das Ganze ersetzen durch die letzte Zahl, die ich, wenn 36:49.800 --> 36:51.700 ich das hinschreibe, plus 1. 36:52.620 --> 36:56.040 Das heißt, wenn ich mir sozusagen hier die ganzen a's und die ganzen 36:56.040 --> 37:01.600 Klammern wegstreiche, dann sehe ich da immer Listen von Zahlen. 37:01.600 --> 37:04.480 Und es können drei Fälle passieren. 37:05.380 --> 37:09.760 Entweder ganz am Ende die letzten beiden Zahlen der Liste lauten 0 und 37:09.760 --> 37:10.560 irgendein Wert. 37:11.060 --> 37:14.820 Dann kann ich diese 0 und diesen irgendeinen Wert ersetzen durch 37:14.820 --> 37:16.060 letzter Wert plus 1. 37:16.840 --> 37:20.900 Oder der letzte Wert lautet 0. 37:21.880 --> 37:27.420 Dann kann ich die letzten beiden Werte ersetzen durch vorletzter Wert 37:27.420 --> 37:30.240 minus 1 und 1 als letzten Wert. 37:30.240 --> 37:34.540 Oder es passiert, dass eben keiner von diesen beiden Fällen zutrifft 37:34.540 --> 37:40.280 und dann muss ich die letzten beiden Werte nehmen und ersetze die. 37:40.460 --> 37:45.120 Der vorletzte Wert wird ersetzt durch vorletzter Wert minus 1 und 37:45.120 --> 37:48.120 hintendran der letzte Wert wird ersetzt durch zwei Zahlen. 37:48.220 --> 37:53.720 Der wird ersetzt durch den vorletzten Wert plus 1 und den letzten Wert 37:53.720 --> 37:54.500 minus 1. 37:55.240 --> 37:58.540 Und so hat man dann so Listen von Zahlen, die wachsen eine ganze 37:58.540 --> 38:02.340 Weile, bis ich dann irgendwann diesen Nullfall erreiche, wo ich es 38:02.340 --> 38:03.140 dann wieder schrumpfe. 38:03.560 --> 38:06.320 Und dann kann es sein, dass es wieder wächst und wieder schrumpft und 38:06.320 --> 38:08.700 wieder wächst und wieder schrumpft, je nachdem wie der mittlere und 38:08.700 --> 38:09.740 der letzte Fall anschlagen. 38:10.240 --> 38:13.800 Und irgendwann muss das Ganze wieder zusammen kollabieren in einer 38:13.800 --> 38:14.640 einzige Zahl. 38:15.860 --> 38:20.420 Und das kann man sich zum Beispiel mal anschauen in einem einfachen 38:20.420 --> 38:21.020 kleinen Programm. 38:24.660 --> 38:28.220 Das hier ist die Ackermann-Funktion als einfaches Python-Programm 38:28.220 --> 38:28.520 geschrieben. 38:29.220 --> 38:32.260 Selbst wenn man Python nicht kann, kann man da schon ungefähr erahnen, 38:32.360 --> 38:35.880 was es tut. 38:36.880 --> 38:40.020 Ich habe da eine Liste, die heißt L und die initialisiere ich. 38:40.240 --> 38:41.900 Und das sind immer Listen von Werten. 38:42.340 --> 38:44.820 Und die initialisiere ich zum Beispiel mit dem Wert 2,3. 38:45.160 --> 38:48.400 Das heißt, ich würde gerne Ackermann-Funktionen von 2 und 3 38:48.400 --> 38:50.900 ausrechnen. 38:51.900 --> 38:55.540 Und solange jetzt diese Liste noch mindestens zwei Zahlen enthält, 38:56.800 --> 38:59.420 habe ich einen von diesen drei Fällen. 39:00.460 --> 39:03.740 Erster Fall, dass x gleich 0, die vorletzte Zahl. 39:04.540 --> 39:06.020 x ist gleich die vorletzte Zahl. 39:06.620 --> 39:07.960 Die sei 0. 39:08.620 --> 39:15.960 Wenn das der Fall ist, dann kommt hinten an die Liste eben dieses y 39:15.960 --> 39:18.120 plus 1 dran. 39:18.120 --> 39:22.840 Dann wird das x gleich 0 weggenommen und das vorletzte wird 39:22.840 --> 39:23.340 weggenommen. 39:23.900 --> 39:27.160 Also die Liste, ich nehme mir den vorletzten Wert in x, den letzten 39:27.160 --> 39:30.520 Wert in y und schneide die letzten beiden Werte von der Liste ab. 39:31.100 --> 39:35.040 Und wenn halt dieser vorletzte Wert 0 war, dann kommt hinten an die 39:35.040 --> 39:36.980 Liste y plus 1 dran. 39:37.460 --> 39:39.220 Also letzter Wert plus 1. 39:39.900 --> 39:46.620 Wenn der letzte Wert 0 war, dann kommt hinten an die Liste einmal x 39:46.620 --> 39:48.840 minus 1 dran und einmal 1 dran. 39:50.140 --> 39:55.700 Und ansonsten, wenn das nicht der Fall war, dann muss ich nach der 39:55.700 --> 39:57.540 Definition hinten drei Werte dran schreiben. 39:57.640 --> 40:02.080 Dann kommt wieder x minus 1 dran, dann kommt x dran und dann kommt y 40:02.080 --> 40:02.920 minus 1 dran. 40:03.000 --> 40:06.860 Das sind die drei Werte, die da vorkommen können. 40:10.060 --> 40:17.860 Wenn man das Ganze jetzt mal ausführt für 2, 3, dann sieht das Ganze 40:17.860 --> 40:18.340 so aus. 40:18.960 --> 40:22.900 Dann sieht man, das Ganze wächst erstmal eine ganze Weile, bis ich 40:22.900 --> 40:33.200 dann hier an der Stelle das erste Mal diesen mittleren Fall treffe, wo 40:33.200 --> 40:36.680 ich halt nur Ersetzungen mache, bis ich dann hier hinkomme, dass ich 40:36.680 --> 40:38.560 endlich mal was verkürzen kann. 40:38.560 --> 40:42.200 Nochmal verkürzen kann, dann wächst das Ganze wieder, dann kann ich es 40:42.200 --> 40:45.680 irgendwann wieder verkürzen, dann wächst das Ganze wieder und weiter 40:45.680 --> 40:46.740 und so weiter und so fort. 40:47.160 --> 40:51.340 Und das geht drei, vier Mal so und am Ende kommt irgendwann der Wert 9 40:51.340 --> 40:51.680 raus. 40:51.820 --> 40:56.960 Das heißt, ich weiß dann, dass Ackermann von 2, 3 der Wert 9 ist. 40:58.300 --> 41:03.760 Und jetzt hat diese Ackermann-Funktion eine ziemlich unangenehme 41:03.760 --> 41:04.240 Eigenschaft. 41:05.060 --> 41:10.320 Die Werte werden sehr schnell relativ groß und zwar in Abhängigkeit 41:10.320 --> 41:13.100 insbesondere von dem X-Wert. 41:13.460 --> 41:18.000 Und wenn ich den X-Wert ansteigen lasse, dann explodieren mir die 41:18.000 --> 41:19.200 Werte der Ackermann-Funktion. 41:21.180 --> 41:24.600 Wenn ich also den nur um 1 erhöhe, wird aus 9 eine 61. 41:25.080 --> 41:26.120 Das ist ja noch in Ordnung. 41:27.980 --> 41:31.080 Jetzt schauen wir mal, ob wir das in erträglicher Zeit hinbekommen, 41:31.160 --> 41:32.380 wenn ich daraus eine 4 mache. 41:37.210 --> 41:37.690 So. 41:37.690 --> 41:39.950 Und das wird jetzt auch noch eine ganze Weile so weitergehen. 41:40.970 --> 41:46.950 Das heißt, wenn ich da vorne aus der 3 eine 4 mache, kann ich den Wert 41:46.950 --> 41:48.150 eigentlich gar nicht mehr ausrechnen. 41:48.470 --> 41:51.750 Also wenn man da so in Tabellen nachschaut, wird man gar keinen Wert 41:51.750 --> 41:57.130 mehr finden, einen vernünftigen Wert vorne, wo X gleich 4 ist. 41:57.810 --> 41:58.250 So. 41:58.570 --> 42:00.750 Ich muss das mal ein bisschen abbrechen, weil sonst müllt mir 42:00.750 --> 42:03.410 irgendwann der Speicher voll beim Rechnen. 42:07.390 --> 42:08.850 Jetzt wollen wir mal eben gucken. 42:09.470 --> 42:10.170 Was haben wir hier? 42:10.250 --> 42:10.950 Habe ich es noch offen? 42:12.410 --> 42:13.370 Den will ich nicht. 42:14.370 --> 42:15.890 Den will ich auch nicht. 42:21.260 --> 42:28.380 Für so die ersten Fälle von X kann man noch Werte angeben. 42:29.660 --> 42:36.660 Schaut man in der Enzyklopädie seines Vertrauens nach, wobei man bei 42:36.660 --> 42:38.380 Wikipedia immer sehr vorsichtig sein muss. 42:38.380 --> 42:39.640 Da steht auch manchmal Unsinn drin. 42:40.740 --> 42:47.780 Und dann sieht man, für X 0, 1, 2 kann man schöne geschlossene Formeln 42:47.780 --> 42:48.200 angeben. 42:48.660 --> 42:52.880 Und zum Beispiel der Wert für X gleich 2 in Abhängigkeit von dem Y, 42:53.160 --> 42:54.940 der wächst halt linear in X. 42:55.220 --> 42:56.740 Das ist dann sowas wie 2X plus 3. 42:56.880 --> 42:57.720 Das ist noch handhabbar. 42:58.460 --> 43:02.600 Wenn ich dann auf 3 übergehe, dann wird es schon exponentiell. 43:02.600 --> 43:06.580 Dann wächst der Wert schon exponentiell in der Abhängigkeit von Y. 43:06.800 --> 43:08.700 Das ist dann 8 mal 2 hoch Y minus 3. 43:09.340 --> 43:15.120 Da kann für wenige, für kleine M, kann das Ganze schon relativ schnell 43:15.120 --> 43:16.000 sehr groß werden. 43:16.980 --> 43:21.080 Und wenn ich dann 4 hernehme, dann wird es unangenehm. 43:21.160 --> 43:25.560 Also es geht los mit 13, dann wenn ich schon Y1 habe, dann bin ich 43:25.560 --> 43:27.560 schon bei diesen 65.000 irgendwas. 43:28.360 --> 43:34.180 Wenn ich dann 2 annehme, dann ist es schon 2 hoch so 65.000 minus 3 43:34.180 --> 43:34.700 mal was. 43:36.360 --> 43:39.860 Den Wert hier, den kann man schon gar nicht mehr vernünftig angeben. 43:40.020 --> 43:43.040 Also das geht halt nicht irgendwie, kann man nicht angeben. 43:43.280 --> 43:47.060 Aber immerhin für Y gleich 4 kann man noch eine geschlossene Formel 43:47.060 --> 43:47.400 finden. 43:48.040 --> 43:50.240 Die arbeitet mit sowas, das nennt sich ein Potenzturm. 43:50.880 --> 43:56.760 Das ist 2 hoch 2 hoch 2 hoch 2 und das Ganze insgesamt M plus 3 Zwein 43:56.760 --> 43:57.340 in diesem Potenzturm. 43:58.360 --> 44:01.000 Und das muss man sich so vorstellen, das muss man so auswerten, dass 44:01.000 --> 44:02.720 man immer von oben nach unten runter geht. 44:03.260 --> 44:06.360 Wenn ich also sowas habe wie 2 hoch 2 hoch 2 hoch 2 hoch 2, dann nehme 44:06.360 --> 44:09.240 ich mir die obersten 2 hoch 2 her, werte die aus. 44:09.600 --> 44:12.380 Dann gehe ich eins runter, mach 2 hoch das, gehe ich eins runter, mach 44:12.380 --> 44:14.160 2 hoch das und so weiter und so fort. 44:14.990 --> 44:23.300 Das heißt, für das Y ist dann halt 2 hoch Y plus 3 mal, also so 2 hoch 44:23.300 --> 44:25.860 2 hoch 2 mit Y plus 3 Zwein. 44:26.040 --> 44:28.820 Und dann wird ja noch ledigerweise 3 abgezogen. 44:29.460 --> 44:36.000 Das ist schon für, ich glaube sowas, für 3 ist es definitiv mehr Atome 44:36.000 --> 44:37.200 als es im Universum gibt. 44:37.480 --> 44:40.720 Und hier hinten, da kann man irgendwie gar nicht mehr vernünftig 44:40.720 --> 44:42.820 irgendwie zahlenwertig hinschreiben. 44:42.820 --> 44:46.540 Und für 5 und 6 kennt man also anscheinend bisher auch noch keine 44:46.540 --> 44:47.440 geschlossenen Formen. 44:48.880 --> 44:51.640 Das macht die schon ganz interessant. 44:52.040 --> 44:59.080 Also es ist eine extrem schnell wachsende, schnell wachsende, 45:02.230 --> 45:05.090 schnell wachsende Funktion. 45:06.450 --> 45:13.130 Und da jetzt zu beweisen, dass die wirklich A überall definiert ist 45:13.130 --> 45:16.530 und dass auch überall wirklich nur ein Wert definiert ist, das ist 45:16.530 --> 45:17.830 relativ anspruchsvoll. 45:18.290 --> 45:23.650 Aber man kann sich zumindest schon mal überlegen, dass man dieses ist 45:23.650 --> 45:29.070 für jedes X und für jedes Y definiert, dass man das machen könnte 45:29.070 --> 45:32.050 mithilfe von einem induktiven Beweis und zwar braucht man da einen 45:32.050 --> 45:33.830 doppelt geschachtelten induktiven Beweis. 45:33.830 --> 45:37.010 Da wir da so eine doppelt geschachtelte induktive Definition haben, 45:37.490 --> 45:40.190 wird man halt einmal eine Induktion machen, die über die X läuft und 45:40.190 --> 45:43.050 einmal dann innen drin eine Induktion, die über die Y läuft. 45:43.450 --> 45:48.070 Und dann kann man das Ganze entsprechend, wenn man das denn so will, 45:49.670 --> 45:50.150 beweisen. 45:52.910 --> 45:55.950 Das Ganze ist also relativ interessant, weil das mal eine Funktion 45:55.950 --> 45:57.730 ist, wo es schwierig ist, die auszurechnen. 45:57.730 --> 46:03.350 Also wo auch ein ganz großer, kräftiger Supercomputer das Ding einfach 46:03.350 --> 46:04.610 nicht mehr ausrechnen können. 46:05.490 --> 46:08.710 Das Ganze ist aber auch von einem gewissen praktischen Nutzen. 46:09.090 --> 46:12.910 Man verwendet das nämlich in der Informatik gerne, um was zu testen. 46:12.950 --> 46:14.650 Und das schon so seit den 70er Jahren. 46:15.370 --> 46:19.230 Wenn man sich das anschaut, dieses Ding, da hat man ja letztendlich 46:19.230 --> 46:19.850 einen Stack. 46:20.230 --> 46:23.010 Den lässt man immer nach oben wachsen oder halt wieder schrumpfen. 46:23.010 --> 46:25.670 Man legt also entweder Zahlen drauf oder man lässt die runter. 46:26.210 --> 46:29.090 Oder man macht das halt durch Hilfe von solchen indirekursiven 46:29.090 --> 46:30.870 Funktionsaufrufen. 46:31.010 --> 46:33.210 Das heißt, dann wird dann immer, wenn man sich ein bisschen 46:33.210 --> 46:36.810 auseinandersetzt mit Compiler, ein Frame irgendwo in diesen Stack 46:36.810 --> 46:39.470 reingeschoben und immer noch und immer noch und dann irgendwie 46:39.470 --> 46:39.870 kleiner. 46:40.350 --> 46:44.270 Und das Schöne ist, dass dieser Stack extrem schnell wächst. 46:45.010 --> 46:48.630 Also schon für kleine Werte bekommt man irgendwann extrem große 46:48.630 --> 46:49.190 Stacks. 46:49.190 --> 46:51.950 Und da kann man zum Beispiel testen, wenn man einen neuen Compiler 46:51.950 --> 46:56.910 geschrieben hat für irgendeine Programmiersprache, wie gut performt 46:56.910 --> 47:01.730 der, wenn ich so viele rekursive Funktionsaufrufe habe und mein Stack 47:01.730 --> 47:03.630 relativ schnell relativ groß wird. 47:04.090 --> 47:08.430 Und fängt der auch relativ gut den Fall ab, dass ich irgendwann mal 47:08.430 --> 47:13.530 keinen Stack mehr habe, dass mir der Stackspeicher ausläuft, dass ich 47:13.530 --> 47:16.710 irgendwo dann keine Frames mehr für die Funktionen irgendwo 47:16.710 --> 47:17.510 hochschieben kann. 47:18.250 --> 47:23.270 Explodiert mir dann der Rechner oder fängt der Compiler, fängt das 47:23.270 --> 47:26.090 Programm das ab und sagt, hier Fehler und noch eine sinnvolle 47:26.090 --> 47:26.730 Fehlermeldung. 47:27.430 --> 47:31.990 Und 1972 mit irgendwelchen Programmiersprachen da, ist schon bei, ich 47:31.990 --> 47:34.430 glaube, Ackermann 1 oder 2 das Ding explodiert. 47:35.090 --> 47:37.770 Heutzutage, wenn man irgendwie sowas wie Java hat in einer relativ 47:37.770 --> 47:42.730 modernen Version, kommt man schon für, kann man halbwegs vernünftige 47:42.730 --> 47:47.070 Ackermann -Werte noch ausrechnen, bevor es dann irgendwann schief 47:47.070 --> 47:47.310 geht. 47:47.470 --> 47:50.750 Man muss halt gegebenenfalls nur sehr, sehr, sehr lange warten. 47:55.110 --> 47:57.370 Letzte Bemerkung zu dieser Ackermann-Funktion. 47:57.570 --> 48:03.410 So böse und unschön das ist, hat sie doch einen riesen Vorteil. 48:03.650 --> 48:06.170 Das Ding könnte man erstmal theoretisch berechnen. 48:06.330 --> 48:09.630 Wir haben eine Vorschrift, die diese Funktion berechnet. 48:09.630 --> 48:12.090 Und in Umständen brauche ich relativ viele Ressourcen, viel Speicher 48:12.090 --> 48:17.250 und viel Rechenkapazität, Rechenzeit, aber ich kann sie berechnen. 48:18.170 --> 48:21.470 Wir werden später in der Vorlesung auch noch eine Funktion 48:21.470 --> 48:22.230 kennenlernen. 48:23.110 --> 48:24.450 Die kann ich definieren. 48:25.150 --> 48:28.830 Die kann ich auf ein Blatt hinschreiben und sagen, das ist der Wert 48:28.830 --> 48:31.150 der Funktion an jeder beliebigen Stelle. 48:31.570 --> 48:33.810 Die hat auch nur einen Parameter, das ist eine natürliche Zahl. 48:33.810 --> 48:38.190 Ich kann diese Funktion für jede natürliche Zahl hinschreiben, was der 48:38.190 --> 48:39.650 Wert sein soll. 48:40.250 --> 48:43.070 Da kommt nicht der exakte Wert hin, aber es wird definiert, was der 48:43.070 --> 48:44.630 Wert sein soll. 48:45.450 --> 48:49.710 Und das Schöne ist, ich kann diese Funktion nicht berechnen und man 48:49.710 --> 48:52.050 kann beweisen, dass man diese Funktion nicht berechnen kann. 48:52.690 --> 48:56.130 Und was noch schöner ist an dieser Funktion, man kann dann auch noch 48:56.130 --> 48:59.430 zeigen, dass diese Funktion ganz schnell wächst. 49:00.150 --> 49:04.850 Und zwar schneller als jede andere beliebige Funktion, die es gibt. 49:05.430 --> 49:09.290 Das ist die Funktion, die wächst schneller als alle anderen 49:09.290 --> 49:12.590 Funktionen, die es gibt, plus sie können sie nicht berechnen. 49:13.490 --> 49:18.310 Man kann so für einige wenige Werte ganz am Anfang, konnte man es 49:18.310 --> 49:22.610 ausrechnen und beweisen, was der genaue Wert aus den natürlichen 49:22.610 --> 49:25.070 Zahlen an dieser Funktion, an dieser Stelle ist. 49:25.350 --> 49:28.190 Aber irgendwann so ab Wert 7 oder so, glaube ich, hört es auf. 49:28.350 --> 49:28.870 Kennt man noch nicht. 49:29.350 --> 49:32.270 Es gibt aber immer noch Leute, die so dran basteln und versuchen halt 49:32.270 --> 49:34.690 weitere Werte dieser Funktion zu entlocken. 49:35.270 --> 49:38.270 Das nennt sich die Busy Beaver, die fleißige Beaver-Funktion. 49:38.270 --> 49:41.630 Die werden Sie dann später kennenlernen, weil man, um die zu 49:41.630 --> 49:43.710 definieren, Boring-Maschinen braucht. 49:45.390 --> 49:50.610 Gut, also das noch als Bemerkung für vollständige Induktion. 49:51.390 --> 49:56.450 Sie werden in den Tutorien und in den Übungsblättern auch noch fleißig 49:56.450 --> 49:59.610 üben, solche induktiven Beweise durchzuführen. 49:59.730 --> 50:02.850 In der Mathematik wird das auch noch häufiger vorkommen. 50:02.850 --> 50:09.150 Wichtig ist, lernen Sie wirklich diese Induktionsvoraussetzung 50:09.150 --> 50:10.530 hinzuschreiben. 50:10.890 --> 50:18.990 Also entweder sowas wie für jedes N, wenn Aussage AN gilt, dann zeige 50:18.990 --> 50:20.610 ich, dass AN plus 1 gilt. 50:21.970 --> 50:26.670 Und die Voraussetzung muss dann immer sein, sei jetzt N aus N0 fest, 50:26.950 --> 50:27.510 aber beliebig. 50:27.510 --> 50:29.110 Schreiben Sie das am besten hin. 50:29.170 --> 50:32.270 Wenn Sie es nicht hinschreiben, ist es zwar auch in Ordnung, aber wenn 50:32.270 --> 50:34.410 Sie zeigen wollen, dass Sie es wirklich verstanden haben, schreiben 50:34.410 --> 50:38.390 Sie hin, sei N ein festes, aber beliebiges Element aus den natürlichen 50:38.390 --> 50:43.410 Zahlen und gelte für dieses N die Aussage AN, dann zeige ich Ihnen 50:43.410 --> 50:44.970 jetzt, dass AN plus 1 gilt. 50:46.030 --> 50:49.790 Erst dann ist so ein induktiver Beweis wirklich vollständig und 50:49.790 --> 50:50.130 richtig. 50:53.510 --> 50:56.970 Jetzt an dieser Stelle noch ein bisschen mehr zu formalen Sprachen. 50:57.090 --> 50:59.230 Ein bisschen was zu formalen Sprachen hatten wir schon gesehen, 50:59.370 --> 51:04.510 insbesondere die formale Sprache als Teilmenge über der Menge aller 51:04.510 --> 51:05.950 möglichen Wörter A-Stern. 51:06.410 --> 51:11.410 Also A-Stern war die Menge aller Wörter beliebiger Länge inklusive des 51:11.410 --> 51:16.110 leeren Wortes, die ich über einem Alphabet A bilden konnte. 51:18.090 --> 51:22.610 Was wir jetzt festlegen werden, ist eine neue Operation, das ist das 51:22.610 --> 51:27.630 Produkt formaler Sprachen und wir werden uns dieses A-Stern ein 51:27.630 --> 51:31.190 bisschen genauer anschauen, wie man dieses A-Stern definieren kann, 51:31.450 --> 51:36.050 wie man reinschreiben kann, was in diesem A-Stern alles drin ist. 51:38.370 --> 51:45.010 Also, das Produkt oder die Konkatenation formaler Sprachen ist einfach 51:45.010 --> 51:48.150 analog zu der Konkatenation von zwei Wörtern. 51:48.750 --> 51:53.890 Wenn ich also zwei formale Sprachen L1 und L2 habe, also Mengen, die 51:53.890 --> 51:59.630 Wörter enthalten, dann definiere ich das Produkt L1 mal L2 als die 51:59.630 --> 52:05.050 Menge aller möglichen Konkatenationen aus Wörtern aus L1 und L2. 52:05.050 --> 52:10.030 Das sind also alle Wörter, die durch Konkatenation von W1 und W2 52:10.030 --> 52:17.170 entstehen, wenn W1 aus der ersten formalen Sprache ist und W2 aus der 52:17.170 --> 52:18.330 zweiten formalen Sprache. 52:19.210 --> 52:23.490 Man kann jetzt beweisen, dass, weil die Konkatenation der Wörter 52:23.490 --> 52:28.870 assoziativ ist, ist auch das Produkt der formalen Sprachen assoziativ. 52:28.870 --> 52:35.110 Das heißt, L1, L2 mal L3 ist halt gleich W1, W2, W3 mit W1 Element L1 52:35.110 --> 52:38.430 und W2 Element L2 und W3 Element L3. 52:40.070 --> 52:41.370 Und so weiter und so fort. 52:41.490 --> 52:46.470 Das heißt also, die Klammern kann man sich wegen der Assoziativität 52:46.470 --> 52:47.410 sparen. 52:48.370 --> 52:51.350 Der Punkt wird gerne weggelassen, so wie das bei der mathematischen 52:51.350 --> 52:52.870 Multiplikation auch der Fall ist. 52:52.870 --> 52:56.490 Was es natürlich nicht ist, das Ganze ist natürlich nicht kommutativ. 52:57.250 --> 53:01.730 Das funktioniert an der Stelle nicht, weil bei der Konkatenation von 53:01.730 --> 53:03.690 Wörtern es eben auf die Reihenfolge ankommt. 53:06.050 --> 53:10.770 Also, einfaches Beispiel, wenn ich sowas habe wie L1 gleich A und AA, 53:11.330 --> 53:14.570 enthält die beiden Wörter A und AA, L2 enthält B und AB. 53:15.350 --> 53:19.710 Wenn ich dann L1 und L2 miteinander multipliziere, muss ich also alle 53:19.710 --> 53:22.370 möglichen Kombinationen bilden. 53:22.370 --> 53:31.110 Also einmal A mit B, einmal A mit AB, dann AA mit B und dann AA mit 53:31.110 --> 53:31.550 AB. 53:32.730 --> 53:36.290 Das heißt, es kann also maximal vier Wörter enthalten. 53:36.850 --> 53:39.530 Jetzt enthält es aber am Ende nur drei Wörter, weil ich nämlich 53:39.530 --> 53:42.510 zweimal das Wort AAB bilden kann. 53:42.630 --> 53:46.770 Indem ich es einmal mit AA aus L1 nehme und dann mit B aus L2 53:46.770 --> 53:53.050 konkateniere oder indem ich AA aus... indem ich A aus L1 nehme und das 53:53.050 --> 53:55.590 konkateniere mit AB aus L2. 53:59.450 --> 54:02.890 Man kann auch natürlich komplexere Sprachen betrachten, zum Beispiel 54:02.890 --> 54:07.630 das Alphabet aller Kommandowörter einer Programmiersprache und 54:07.630 --> 54:11.530 außerdem irgendwelche Alphabete, die es mir erlauben, zum Beispiel 54:11.530 --> 54:17.650 variablen Namen herzubauen oder auch Alphabete, die mir dann andere 54:17.650 --> 54:21.330 Ausdrücke machen können, zum Beispiel aussagenlogische Ausdrücke, 54:21.590 --> 54:24.370 arithmetische Ausdrücke innerhalb dieser Sprache. 54:25.030 --> 54:32.550 Und wenn ich das habe, dann kann ich anfangen, da aus solchen Dingern 54:32.550 --> 54:34.950 dann wirklich Programmiersprachen zu bauen. 54:35.590 --> 54:39.350 Ich habe also meine Sprache, die hat halt Kommandowörter, die hat 54:39.350 --> 54:42.890 irgendwelche Alphabete, mit denen ich Variablen bauen kann. 54:45.170 --> 54:48.830 Zum Beispiel könnte ich eine Programmiersprache haben, die lautet, 54:49.030 --> 54:52.810 okay, ein Variablenname darf aus den kleinen Buchstaben des 54:52.810 --> 55:00.170 lateinischen Alphabets A bis Z bestehen, gefolgt von zum Beispiel 55:00.170 --> 55:09.370 irgendeiner Integerzahl, einer ganzen Zahl oder beliebigen 55:09.370 --> 55:10.150 Kombinationen. 55:10.150 --> 55:13.530 Und der Variablenname ist gültig, hauptsächlich, solange er mit einem 55:13.530 --> 55:15.530 kleinen Buchstaben von A bis Z anfängt. 55:16.210 --> 55:18.770 Und dann kann ich so eine Sprache halt basteln, indem ich mir die 55:18.770 --> 55:19.950 Kommandowörter hernehme. 55:20.630 --> 55:24.270 Die Multipliz, das sind so Kommandowörter für die Deklaration und 55:24.270 --> 55:24.850 Variable. 55:25.750 --> 55:30.450 Die konkateniere ich mit einem Leerzeichen, das heißt, nach einer 55:30.450 --> 55:33.390 Deklarationsbezeichnung für eine Variable muss ein Leerzeichen kommen 55:33.390 --> 55:36.370 und dann muss irgendwie ein Variablenname kommen, der muss anfangen 55:36.370 --> 55:40.570 mit einem kleinen Buchstaben, also erstmal das B, die B-Menge, und 55:40.570 --> 55:44.450 danach kann Beliebiges kommen, das sich aus B und Z zusammensetzt. 55:44.810 --> 55:47.810 Das heißt, das konkateniere ich dann mit der formalen Sprache, die ich 55:47.810 --> 55:50.330 erhalte, indem ich B mit Z vereinige. 55:50.790 --> 55:53.450 Und wenn ich will, dass also ein Variablenname auch nur aus einem 55:53.450 --> 55:56.810 einzigen Buchstaben aus B kommt, dann muss ich das Wort Y zu der 55:56.810 --> 55:58.430 formalen Sprache auch noch hinzunehmen. 55:58.430 --> 56:03.550 Dann kann ich alle Variablennamen der Form machen, Kleinbuchstabe, 56:03.930 --> 56:07.630 beliebige Kombinationen aus Kleinbuchstabe und Zahl, wobei dieser 56:07.630 --> 56:09.590 zweite Teil halt optional ist. 56:09.930 --> 56:13.290 Und dann soll halt am Ende der Zeile eben noch ein Semikolon stehen. 56:14.810 --> 56:17.430 Da kann ich dann solche Variablen und Deklarationen machen, wie int 56:17.430 --> 56:25.190 Leerzeichen x2, double Leerzeichen w, int x3, y, z, w, 13, 0, 56:25.470 --> 56:26.650 Semikolon und so weiter. 56:27.430 --> 56:31.610 Was leider jetzt noch nicht gilt, ist zum Beispiel, dass man auch 56:31.610 --> 56:34.730 beliebig viele Leerzeichen anstatt eines einzelnen Leerzeichens nehmen 56:34.730 --> 56:34.910 kann. 56:35.270 --> 56:38.790 Dass also zwischen Variablen, Deklaration und Name auch zwei 56:38.790 --> 56:39.830 Leerzeichen stehen können. 56:40.270 --> 56:43.230 Und dass auch hinter der Variablen ein Leerzeichen stehen darf oder 56:43.230 --> 56:45.110 auch mehrere, bevor das Semikolon kommt. 56:45.690 --> 56:49.370 Und dass vielleicht auch vor dem Kommandowort ein oder mehrere 56:49.370 --> 56:52.750 Leerzeichen oder auch Tabulatoren oder beliebiger White Space stehen 56:52.750 --> 56:53.030 darf. 56:54.350 --> 56:58.150 Das muss man dann immer weiter komplizierter zusammenbauen. 56:58.530 --> 57:02.150 Aber man kommt eben gerade mit diesen Operationen, Vereinigung und 57:02.150 --> 57:03.950 Produkt formaler Sprachen aus. 57:04.230 --> 57:10.030 Und kann auf die Art und Weise komplett formal festlegen, wie 57:10.030 --> 57:13.430 syntaktisch korrekt so eine Variablen-Deklaration aussieht. 57:13.810 --> 57:17.090 Und dann immer komplizierter, wie sehen Befehle aus, wie sehen 57:17.090 --> 57:22.010 konditionale Befehle aus, wie sehen Befehlsblöcke aus und so weiter 57:22.010 --> 57:22.570 und so fort. 57:22.570 --> 57:27.130 Und wenn Sie sich mal hernehmen, diese Java Language Definition, da 57:27.130 --> 57:28.610 steht das eben genau so drin. 57:29.050 --> 57:33.570 Da steht genau so drin, wie ein Java Programm syntaktisch korrekt 57:33.570 --> 57:34.930 aufgebaut sein darf. 57:35.730 --> 57:38.950 Und wenn Sie das mal so formal hingeschrieben haben, dann haben Sie 57:38.950 --> 57:39.710 zwei Vorteile. 57:39.810 --> 57:41.210 Erstens, es ist eindeutig. 57:41.610 --> 57:45.910 Es gibt keine Unklarheit mehr, die durch irgendwelche Formulierungen 57:45.910 --> 57:48.890 in natürlicher Sprache herkommt, ob jetzt das eine oder das andere 57:48.890 --> 57:49.450 gemeint ist. 57:49.450 --> 57:53.010 Das heißt, es ist wirklich ganz klar und zweifelsfrei festgelegt, wie 57:53.010 --> 57:53.910 das aussehen darf. 57:54.410 --> 57:57.790 Plus, wenn Sie das so formal hingestellt haben, können Sie jetzt auch 57:57.790 --> 58:01.970 anfangen, Programme zu schreiben, die testen, ob ein Java Programm 58:01.970 --> 58:03.310 wirklich syntaktisch korrekt ist. 58:03.790 --> 58:06.510 Das ist so typischerweise eine der Sachen, wenn Sie ein Programm 58:06.510 --> 58:07.190 kompilieren. 58:07.710 --> 58:10.510 Bevor Sie anfangen zu kompilieren, ist manchmal ganz nützlich zu 58:10.510 --> 58:13.330 überprüfen, ob es syntaktisch korrekt ist. 58:13.330 --> 58:17.450 Und da kann man jetzt mit Hilfe dieser Festlegung, wenn man so eine 58:17.450 --> 58:20.570 Definition hat, mit Techniken, die wir hier in der Vorlesung 58:20.570 --> 58:25.370 kennenlernen, anfangen, Tester zu bauen, die überprüfen, ist das ein 58:25.370 --> 58:27.050 syntaktisch korrektes Wort oder nicht. 58:27.370 --> 58:32.090 Mit anderen Worten, ist dieses Programm, das ich kompilieren will, ein 58:32.090 --> 58:36.430 Wort aus der formalen Sprache der syntaktisch korrekten Programme? 58:37.590 --> 58:43.070 Oder ist es ein Wort aus der Sprache der syntaktisch korrekten 58:43.070 --> 58:44.970 Aussagen, logischen Ausdrücke? 58:45.770 --> 58:48.490 An der Stelle haben Sie noch gar nichts über Semantik. 58:48.830 --> 58:51.430 Also, was bedeutet das Programm, was muss gemacht werden, wenn das 58:51.430 --> 58:52.490 Programm ausgeführt wird? 58:52.790 --> 58:54.490 Das ist an der Stelle noch nicht festgelegt. 58:55.230 --> 58:56.640 Das ist dann der nächste Schritt beim Kompilieren. 58:56.640 --> 58:59.540 Aber der erste Schritt ist immer erstmal gucken, ist das überhaupt 58:59.540 --> 59:00.400 syntaktisch korrekt. 59:00.720 --> 59:03.660 Und wenn nein, dann brauche ich nicht zu kompilieren, dann mecker ich 59:03.660 --> 59:06.860 erstmal, dass der Programmierer das bitteschön beheben soll. 59:11.740 --> 59:15.360 Bei diesem Produkt gibt es auch ein neutrales Element. 59:16.380 --> 59:19.120 Das ist die Menge, die das leere Wort enthält. 59:19.120 --> 59:23.480 Wenn ich also irgendeine formale Sprache L multipliziere mit der 59:23.480 --> 59:27.040 Menge, die das leere Wort enthält, dann kommt vielleicht die 59:27.040 --> 59:28.960 ursprüngliche Sprache L raus. 59:29.720 --> 59:33.000 Das heißt also, die Menge mit dem leeren Wort Y ist sowas wie die 1 59:33.000 --> 59:34.620 bei der arithmetischen Multiplikation. 59:35.620 --> 59:38.040 Das kann man beweisen, indem man einfach nachrechnet. 59:38.040 --> 59:43.020 Also die eine Richtung L konkateniert mit der Menge des leeren Wortes. 59:43.120 --> 59:46.800 Das sind halt alle wie 1, wie 2, wo halt wie 1 aus L kommt und wie 2 59:46.800 --> 59:51.000 aus der Menge der Sprache mit dem leeren Wort. 59:51.420 --> 59:54.160 Das heißt, dass wie 2 ist also immer das leere Wort. 59:54.620 --> 59:57.660 Also wie 1 konkateniert mit dem leeren Wort ist immer wie 1. 59:57.780 --> 01:00:02.760 Also ist das die Sprache, die alle wie 1 enthält mit wie 1 aus der 01:00:02.760 --> 01:00:04.000 Sprache. 01:00:04.000 --> 01:00:06.340 Das ist einfach nochmal hingeschrieben mathematisch. 01:00:07.960 --> 01:00:11.200 Genauso kann man das umgekehrt halt entsprechend ausrechnen. 01:00:11.300 --> 01:00:15.200 Da tauschen halt wie 1 und wie 2 die Position und es kommt wieder 01:00:15.200 --> 01:00:19.300 genau derselbe Beweis raus und das ist relativ leicht nachzurechnen. 01:00:20.420 --> 01:00:23.740 Jetzt kann man genauso, wie wir Potenzen von Wörtern definiert haben, 01:00:23.960 --> 01:00:26.320 auch Potenzen von formalen Sprachen definieren. 01:00:27.680 --> 01:00:32.060 Und da kann man dann zum Beispiel anfangen, sowas zu definieren wie L 01:00:32.060 --> 01:00:32.460 hoch 0. 01:00:33.760 --> 01:00:37.940 Wenn ich das Ganze jetzt induktiv definieren möchte, muss ich mir also 01:00:37.940 --> 01:00:40.020 überlegen, L hoch 0, was soll das sein? 01:00:40.540 --> 01:00:44.840 Und wir legen einfach fest, L hoch 0 sei halt gerade die Menge mit dem 01:00:44.840 --> 01:00:45.540 leeren Wort Y. 01:00:46.280 --> 01:00:50.000 Und dann kann man für alle K aus der 0 halt festlegen, dass L hoch K 01:00:50.000 --> 01:00:53.580 plus 1 ist gerade gleich L mal L hoch K. 01:00:58.050 --> 01:00:59.990 Dementsprechend, das macht Sinn, das so zu machen. 01:01:00.090 --> 01:01:03.770 Durch Nachrichten sieht man halt, L hoch 3 ist gerade L mal L mal L, L 01:01:03.770 --> 01:01:06.750 hoch 2 ist L mal L und so weiter und so fort. 01:01:07.510 --> 01:01:10.270 Streng genommen müsste man da noch so Klammern reinschreiben, aber die 01:01:10.270 --> 01:01:14.070 Klammern können wir uns gerade wegen der Assoziativität sparen. 01:01:17.260 --> 01:01:19.660 So, jetzt kann man sich da halt wieder ein paar Beispiele anschauen. 01:01:19.660 --> 01:01:23.900 Also L hoch 0 gleich Y, dann sei L hoch 1 wieder unsere ursprüngliche 01:01:23.900 --> 01:01:25.580 Sprache AAB. 01:01:26.640 --> 01:01:30.580 Und dann L hoch 2 hat man dann eben entsprechend alle Kombinationen 01:01:30.580 --> 01:01:32.860 aus der Sprache L mit sich selber. 01:01:33.800 --> 01:01:40.440 Enthält diesmal tatsächlich 4 Wörter, kann also mehr als, diesmal 01:01:40.440 --> 01:01:42.720 tatsächlich 4 Wörter, hat aber nichts damit zu tun, dass es die 01:01:42.720 --> 01:01:43.420 Zweierpotenz ist. 01:01:44.000 --> 01:01:48.760 Theoretisch könnten es also durchaus mehr Wörter sein, also 1, 2, ah 01:01:48.760 --> 01:01:53.760 doch 4 Wörter, entsprechend 4 Wörter sind diesmal auch, fällt keines 01:01:53.760 --> 01:01:54.120 zusammen. 01:01:54.260 --> 01:01:58.320 Dann kommt L hoch 3 und so weiter und so fort, bis man dann irgendwann 01:01:58.320 --> 01:02:03.580 hinkommt, dass man im Prinzip bei L hoch 4 dann so Wörter hat, die 01:02:03.580 --> 01:02:04.820 fangen erstmal mit A an. 01:02:04.820 --> 01:02:08.340 Und dann kommt irgendwann ein B, dann können wieder A´s kommen oder 01:02:08.340 --> 01:02:12.780 dann können wieder B´s kommen oder wieder was anderes aus A, B, B, A. 01:02:15.560 --> 01:02:18.540 Man kann jetzt auch andere, interessantere Sprachen nehmen, zum 01:02:18.540 --> 01:02:21.300 Beispiel sich so eine Sprache her definieren, die soll alle Wörter 01:02:21.300 --> 01:02:26.180 enthalten, die haben die Form A hoch N, B hoch N mit einem N aus N+. 01:02:27.280 --> 01:02:32.640 Also fangen wir an mit N+, also mit 1, ist also A hoch 1, B hoch 1 01:02:32.640 --> 01:02:37.060 drin, dann ist halt A hoch 2, ist AA und B hoch 2 ist BB drin und dann 01:02:37.060 --> 01:02:41.300 geht es 3 mal A, 3B, 4A, 4B und so weiter und so fort. 01:02:42.560 --> 01:02:45.800 Was passiert jetzt, wenn ich zum Beispiel diese Sprache quadriere, 01:02:46.000 --> 01:02:48.860 wenn ich also L hoch 2 ausrechne? 01:02:50.180 --> 01:02:53.820 Dann kann man das aufteilen in die unterschiedlichen Fälle, dann hat 01:02:53.820 --> 01:02:59.960 man also erstmal sowas wie A, B mit A, B, dann A, B mit dem nächsten 01:02:59.960 --> 01:03:04.080 Wort, mit A, A, B, B, dann A, B mit wieder dem nächsten Wort, A, A, A, 01:03:04.200 --> 01:03:06.720 B, B, B und so weiter und so fort. 01:03:07.940 --> 01:03:11.720 Dann nimmt man das zweite Wort her, dieses A, A, B, B, das wird dann 01:03:11.720 --> 01:03:16.940 mit A, B konkateniert, dann mit sich selber, dann mit dem dritten Wort 01:03:16.940 --> 01:03:20.300 und so weiter und so fort und so weiter und so fort. 01:03:20.300 --> 01:03:23.780 Und wenn man jetzt die Augen zusammenkneift, dann sieht man, dass 01:03:23.780 --> 01:03:25.640 diese Wörter eine Struktur haben. 01:03:26.540 --> 01:03:31.120 Und diese Struktur dieser Wörter, die ist eben gerade sowas, dass wenn 01:03:31.120 --> 01:03:36.260 ich also erstmal einen A hoch N1, einen B hoch N1 habe, das heißt, ich 01:03:36.260 --> 01:03:40.560 habe erstmal ein Wort, das hat genauso viele A's wie B's und dann 01:03:40.560 --> 01:03:43.940 kommt dahinter ein Wort, das hat wieder genauso viele A's wie B's, nur 01:03:43.940 --> 01:03:49.300 dass diesmal die Anzahl der A's und die Anzahl der B's eine andere 01:03:49.300 --> 01:03:51.260 ist, als für den ersten Teil des Wortes. 01:03:51.960 --> 01:03:57.880 Also A hoch N hoch 1, B hoch N hoch 1, A hoch N2, B hoch N2 und N1 und 01:03:57.880 --> 01:04:02.260 N2 sind halt beide Zahlen aus den natürlichen Zahlen, können gleich 01:04:02.260 --> 01:04:04.140 sein oder können häufig auch unterschiedlich sein. 01:04:08.340 --> 01:04:16.500 Und jetzt kann man halt aufpassen, dass man diese Potenz nicht nur auf 01:04:16.500 --> 01:04:19.280 formale Sprachen, sondern zum Beispiel auch auf Alphabeten anwendet, 01:04:19.740 --> 01:04:24.820 weil ein Alphabet ist eine Teilmenge aller Wörter über dem Alphabet. 01:04:24.820 --> 01:04:29.340 Das heißt, ein Alphabet als sich selber ist auch eine formale Sprache. 01:04:30.320 --> 01:04:35.120 Das heißt, ich kann jetzt diese Definition der Potenzierung und der 01:04:35.120 --> 01:04:38.900 Konkatenation über formale Sprachen kann ich auch direkt anwenden auf 01:04:38.900 --> 01:04:44.200 Alphabete und bekomme dann andere formale Sprachen über diesem 01:04:44.200 --> 01:04:45.140 Alphabet aus. 01:04:46.120 --> 01:04:51.960 Wenn ich also das Alphabet selber auffasse als formale Sprache, dann 01:04:51.960 --> 01:04:55.320 ist das gerade die formale Sprache, die alle Wörter der Länge 1 über 01:04:55.320 --> 01:04:56.340 dem Alphabet enthält. 01:04:58.980 --> 01:05:02.260 Und jetzt kann man sich anschauen, wenn man sich anschaut A hoch I, 01:05:02.780 --> 01:05:07.540 dann ist das genau das gleiche wie die Sprache L A hoch I. 01:05:08.300 --> 01:05:15.480 Das heißt, so ein A hoch I enthält alle, ist die formale Sprache, die 01:05:15.480 --> 01:05:18.620 alle Wörter enthält der Länge I. 01:05:22.810 --> 01:05:27.230 Und wenn ich jetzt anfange, die Vereinigung zu bilden über alle diese 01:05:27.230 --> 01:05:33.150 Potenzen von A, also über alle formale Sprachen A hoch I, also Wörter 01:05:33.150 --> 01:05:37.070 der Länge 0, Wörter der Länge 1 und so weiter und so fort, dann kommt 01:05:37.070 --> 01:05:38.930 gerade dieses A-Sternchen heraus. 01:05:38.930 --> 01:05:41.070 Das heißt, das sind alle Wörter, die es gibt. 01:05:41.230 --> 01:05:44.370 Das sind alle möglichen Wörter, die ich über diesem A bilden kann. 01:05:44.870 --> 01:05:46.650 Und das Ganze nenne ich A-Sternchen. 01:05:46.650 --> 01:05:52.230 Und weil ich das eben gerade so bekommen kann, indem ich A immer mit 01:05:52.230 --> 01:05:56.050 sich selber konkateniere und darüber die Vereinigung bilde, nennt man 01:05:56.050 --> 01:06:00.750 das gerade eben den Konkatenationsabschluss über dem Alphabet A. 01:06:01.750 --> 01:06:05.830 Oder allgemein, wenn ich irgendeine beliebige formale Sprache L habe, 01:06:06.410 --> 01:06:10.450 dann kann ich den Konkatenationsabschluss von dieser formalen Sprache 01:06:10.450 --> 01:06:11.870 L hernehmen. 01:06:12.410 --> 01:06:15.150 Das nennt man manchmal auch die Klinische Hülle. 01:06:16.110 --> 01:06:20.870 Und zusätzlich zum einfachen Konkatenationsabschluss gibt es auch noch 01:06:20.870 --> 01:06:23.810 den Epsilon-freien Konkatenationsabschluss. 01:06:23.810 --> 01:06:28.850 Der unterscheidet sich dadurch, dass halt L hoch 0 nicht mehr Teil 01:06:28.850 --> 01:06:32.970 ist, sondern man bei L hoch 1 anfängt und dann immer weiter die 01:06:32.970 --> 01:06:34.690 Potenzen miteinander konkateniert. 01:06:35.790 --> 01:06:40.310 Dementsprechend ist der Konkatenationsabschluss halt entsprechend auch 01:06:40.310 --> 01:06:45.190 L hoch 0 vereinigt mit dem Epsilon-freien Konkatenationsabschluss. 01:06:46.930 --> 01:06:51.270 Das Ganze nennt sich Klinische Hülle, weil es entsprechend nach einem 01:06:51.270 --> 01:06:54.450 weiteren berühmten Forscher aus dem Bereich der theoretischen 01:06:54.450 --> 01:06:57.810 Informatik benannt ist, nach Stephen Cole Klin. 01:06:58.450 --> 01:07:04.670 Der 1909 ist er geboren in den USA, ist dann 1994 in Madison 01:07:04.670 --> 01:07:09.490 gestorben, hat auch lange an der University of Wisconsin-Madison 01:07:09.490 --> 01:07:10.330 gelernt. 01:07:10.330 --> 01:07:13.730 Und es gilt auch entsprechend als einer der Begründer der 01:07:13.730 --> 01:07:17.390 theoretischen Informatik, insbesondere verdanken wir ihm halt auch die 01:07:17.390 --> 01:07:20.970 Definition von formalen Sprachen, die Definition der Klinischen Hülle, 01:07:21.070 --> 01:07:24.690 des Konkatenationsabschlusses, aber auch solche Sachen wie das Lambda 01:07:24.690 --> 01:07:28.710 -Kalkül oder auch die regulären Ausdrücke sind Erfindungen, die auf 01:07:28.710 --> 01:07:29.330 ihn zurückgehen. 01:07:29.330 --> 01:07:33.750 Und wenn Sie schon mal programmiert haben und Strings oder 01:07:33.750 --> 01:07:39.070 Zeichenketten manipuliert haben oder da so ein Muster gesucht haben in 01:07:39.070 --> 01:07:42.290 Zeichenketten, in großen Texten, dann werden Sie hin und wieder schon 01:07:42.290 --> 01:07:44.870 mal mit regulären Ausdrücken in Berührung gekommen sein. 01:07:45.350 --> 01:07:48.390 Und diese regulären Ausdrücke sind eben genau das, was der Herr Cole 01:07:48.390 --> 01:07:51.770 Klin damals entsprechend definiert hat. 01:07:53.850 --> 01:07:57.790 Es gibt so Beispiele für einen Konkatenationsabschluss, also wenn man 01:07:57.790 --> 01:08:02.250 wieder A hoch N, B hoch N nimmt, dann hatten wir schon gesehen, L2 ist 01:08:02.250 --> 01:08:05.710 halt A hoch N1, B hoch N1 und dann A hoch N2, B hoch N2. 01:08:06.230 --> 01:08:10.050 Also zwei Teile und in jedem einzelnen Teil für sich selber müssen 01:08:10.050 --> 01:08:12.770 genauso viele A's gefolgt von genauso vielen B's vorkommen. 01:08:13.410 --> 01:08:17.030 Dann kann man halt zeigen, L hoch 3 ist entsprechend zusammengesetzt 01:08:17.030 --> 01:08:20.070 aus drei solchen Teilen, also gleich viele A's und gleich viele B's, 01:08:20.150 --> 01:08:22.630 dann wieder gleich viele A's und gleich viele B's, gleich viele A's 01:08:22.630 --> 01:08:25.810 und gleich viele B's, wobei die sich in den drei unterschiedlichen 01:08:25.810 --> 01:08:27.870 Teilen die absolute Anzahl unterscheiden kann. 01:08:28.290 --> 01:08:31.570 Und allgemein kann man das halt für dieses L hoch I machen. 01:08:32.670 --> 01:08:38.830 Und für L plus kann man halt entsprechend das Ganze auch definieren, 01:08:39.190 --> 01:08:46.430 nur dass halt da das I aus dem N plus sein darf und nicht mehr aus dem 01:08:46.430 --> 01:08:47.730 N null. 01:08:48.930 --> 01:08:55.190 Und das Ganze, die N1 und so weiter aus dem N plus sein dürfen, so wie 01:08:55.190 --> 01:08:56.890 sie es vorher halt auch schon waren. 01:08:56.890 --> 01:09:03.850 L plus und L Sternchen sind entsprechend präziser und kürzer als diese 01:09:03.850 --> 01:09:06.890 vielen Pünktchen, die ich machen will. 01:09:07.590 --> 01:09:10.990 Also wenn ich dieses I dann auch noch beliebig groß machen will und 01:09:10.990 --> 01:09:14.530 vereinigen will, dann kann ich das halt entsprechend mit L plus und L 01:09:14.530 --> 01:09:16.370 Sternchen definieren. 01:09:18.450 --> 01:09:21.090 Das Gleiche kann ich auch machen, wenn ich jetzt halt 01:09:21.090 --> 01:09:25.670 Konkatenationsabschluss bilde über kleinen Alphabeten. 01:09:25.770 --> 01:09:28.610 Also ein Alphabet enthält nur A, das Alphabet enthält nur B, ist 01:09:28.610 --> 01:09:30.050 gleichzeitig auch eine formale Sprache. 01:09:30.450 --> 01:09:34.250 Dann mache ich halt den Konkatenationsabschluss und dann bekomme ich 01:09:34.250 --> 01:09:37.630 zum einen erstmal Wörter, die bestehen nur aus A's beliebiger Länge, 01:09:37.770 --> 01:09:42.250 Wörter, die bestehen nur aus B's beliebiger Länge und auch noch das 01:09:42.250 --> 01:09:42.790 leere Wort. 01:09:42.790 --> 01:09:46.150 Dadurch, dass ich jetzt nicht den Epsilon-freien, sondern den echten 01:09:46.150 --> 01:09:49.390 Konkatenationsabschluss gebildet habe. 01:09:55.570 --> 01:09:58.330 Also das war die ursprüngliche Sprache, die ich da habe. 01:09:58.570 --> 01:10:01.610 Da ist noch der Konkatenationsabschluss erstmal über die Alphabete 01:10:01.610 --> 01:10:03.130 geschlossen. 01:10:03.610 --> 01:10:07.170 Und jetzt gehe ich hin und bilde auch noch den Konkatenationsabschluss 01:10:07.170 --> 01:10:08.250 über dieser Sprache L. 01:10:08.250 --> 01:10:11.750 Das heißt, ich überlege mir jetzt auch noch, was enthält L-Sternchen 01:10:11.750 --> 01:10:12.070 alles. 01:10:13.330 --> 01:10:14.510 Und das sind dann halt Wörter. 01:10:14.610 --> 01:10:19.630 Ich habe also eine beliebige Anzahl, endliches K, beliebige Anzahl 01:10:19.630 --> 01:10:25.490 endlicher Wörter, eine beliebige Anzahl K-Wörter, also K-Wörter und 01:10:25.490 --> 01:10:27.710 diese Wörter kommen halt aus der Sprache. 01:10:28.310 --> 01:10:33.210 L sind also entweder nur aus A's oder nur aus B's ausgebaut und werden 01:10:33.210 --> 01:10:36.170 dann konkateniert zu W1 bis WK. 01:10:37.210 --> 01:10:41.070 Also AA mit Y und dann nochmal ein paar A's und ein paar B's und dann 01:10:41.070 --> 01:10:44.170 nochmal wieder A's und so weiter und so fort. 01:10:45.050 --> 01:10:48.950 Und wenn man da jetzt hinschaut, dann kann man sich halt überlegen, 01:10:49.990 --> 01:10:57.470 dass ich beliebig viele Wörter zusammenbauen kann, endlich viele, und 01:10:57.470 --> 01:11:01.010 die können wieder aus der ursprünglichen Sprache sein, aus diesem L. 01:11:01.010 --> 01:11:04.910 Und dieses L enthält zum Beispiel das Wort, das nur A ist und das 01:11:04.910 --> 01:11:06.510 Wort, das nur B ist. 01:11:07.490 --> 01:11:12.810 Und wenn ich jetzt also K-Wörter zusammenbaue und diese K-Wörter 01:11:12.810 --> 01:11:17.930 dürfen halt aus dieser ursprünglichen Sprache sein, die halt A und B 01:11:17.930 --> 01:11:23.290 hat, dann kann ich insbesondere auch jede beliebige Kombination aus A 01:11:23.290 --> 01:11:27.050 und B zusammenbauen zu einem Wort der Länge K. 01:11:28.010 --> 01:11:34.350 Das heißt, dass diese Sprache, dieser Konkatenationsabschluss über 01:11:34.350 --> 01:11:37.030 diese Sprache, halt genau der gleiche ist wie der 01:11:37.030 --> 01:11:42.950 Konkatenationsabschluss über einem A-Sternchen, wobei A halt 01:11:42.950 --> 01:11:46.370 entsprechend die Vereinigung ist aus dem Zeichen A und dem Zeichen B, 01:11:46.490 --> 01:11:49.990 also das Alphabet ist, das aus den Buchstaben A und B besteht. 01:11:50.810 --> 01:11:54.970 Das heißt also, je nachdem kann es sein, dass wenn ich solche formalen 01:11:54.970 --> 01:11:58.570 Sprachen, den Konkatenationsabschluss erreiche, ich dann andere 01:11:58.570 --> 01:12:01.330 Sprachen bekomme, die dazu äquivalent sind. 01:12:06.970 --> 01:12:10.850 Jetzt kann man zum Beispiel hergehen und sich überlegen, wie werde ich 01:12:10.850 --> 01:12:15.010 dieses Problem los, dass ich zum Beispiel mehrere Leerzeichen zulassen 01:12:15.010 --> 01:12:15.350 möchte. 01:12:15.990 --> 01:12:19.690 Das kann man zum Beispiel machen, indem man jetzt sagt, okay, man hat 01:12:19.690 --> 01:12:24.230 ein S und Leerzeichen können beliebig viele Leerzeichen sein. 01:12:24.370 --> 01:12:28.330 Also wenn ich diese Menge, die das Leerzeichen hat, hoch plus, dann 01:12:28.330 --> 01:12:31.510 ist das ein Wort, das besteht aus mindestens einem, aber letztendlich 01:12:31.510 --> 01:12:32.910 beliebig vielen Leerzeichen. 01:12:33.730 --> 01:12:39.650 Dann diese Definition mit diesem B und B vereinigt Z-Sternchen und 01:12:39.650 --> 01:12:45.330 dahinter kann jetzt der nicht-y-freie Konkatenationsabschluss kommen, 01:12:45.810 --> 01:12:48.010 über die Menge mit dem nur dem Leerzeichen. 01:12:48.150 --> 01:12:50.850 Das heißt, das sind Wörter, die sind entweder null lang, also bestehen 01:12:50.850 --> 01:12:55.170 aus nichts, oder nur aus Hintereinanderreihung von Leerzeichen. 01:12:56.730 --> 01:13:00.550 Und dann entsprechend das Semikonon. 01:13:01.370 --> 01:13:04.230 Dann kann ich zumindest schon mal sowas schreiben, wie Integer, 01:13:04.770 --> 01:13:09.330 Leerzeichen, Leerzeichen, x42, ein Leerzeichen, Semikonon. 01:13:10.030 --> 01:13:14.090 Oder halt das ursprüngliche Double, ein Leerzeichen, Wurzel 2, kein 01:13:14.090 --> 01:13:15.150 Leerzeichen, Semikonon. 01:13:15.750 --> 01:13:17.430 Das ist schon eher das, was ich haben will. 01:13:18.530 --> 01:13:19.610 Ich habe aber immer noch ein Problem. 01:13:21.310 --> 01:13:25.990 Dahinten dieses B und so weiter konkateniert mit B vereinigt Z 01:13:25.990 --> 01:13:29.170 -Sternchen, das enthält zum Beispiel auch das Wort Double. 01:13:30.690 --> 01:13:33.810 Das heißt, ich kann dieses Wort Double, das ich oben reserviert hatte 01:13:33.810 --> 01:13:39.350 für die Deklarationsbefehle, für die Variablendeklaration, kann ich 01:13:39.350 --> 01:13:42.410 auch verwenden als variablen Namen. 01:13:43.470 --> 01:13:45.630 Natürlich blöd, das will ich irgendwie vermeiden. 01:13:46.390 --> 01:13:47.970 Wie kann ich das zum Beispiel vermeiden? 01:13:49.290 --> 01:13:51.790 Welche Verwendenoperation kann ich da zum Beispiel nehmen? 01:13:52.290 --> 01:13:56.090 Zum Beispiel, man nimmt diesen ganzen Kram da hinten, dieses B, 01:13:56.270 --> 01:13:58.550 konkateniert mit B vereinigt Z-Sternchen. 01:13:59.150 --> 01:14:02.310 Da mache ich eine Klammer drum und da mache ich dann weg S. 01:14:03.710 --> 01:14:09.230 Dann sind die Wörter alle draußen und könnte damit dann zumindest 01:14:09.230 --> 01:14:12.950 diesen hinteren Problemfall schon mal vermeiden. 01:14:19.250 --> 01:14:21.310 Zum Schluss der Vorlieb...ja? 01:14:28.000 --> 01:14:28.600 Nein, 01:14:32.160 --> 01:14:33.360 weil ich mache ja das weg. 01:14:33.500 --> 01:14:37.020 Also ich nehme eine Klammer komplett über B, konkateniert mit B 01:14:37.020 --> 01:14:37.980 vereinigt Z-Stern. 01:14:38.660 --> 01:14:39.820 Darum eine Klammer. 01:14:40.340 --> 01:14:44.620 Das enthält alle Wörter, die variablen Namen sein können. 01:14:44.920 --> 01:14:46.800 Und jetzt mache ich die Mengendifferenz. 01:14:47.400 --> 01:14:52.840 Und die Mengendifferenz weg S, das sind ganze Wörter aufgelistet. 01:14:53.240 --> 01:14:56.480 Das heißt, es werden nur Elemente rausgenommen, die wirklich genau 01:14:56.480 --> 01:14:59.840 diesem Wort eins zu eins entsetzen. 01:14:59.920 --> 01:15:00.760 Das ist die Mengenoperation. 01:15:01.200 --> 01:15:03.920 Ich habe also eine Menge, das enthält alle Wörter und die 01:15:03.920 --> 01:15:08.320 Mengenoperation nimmt nur die Elemente raus, die genau in der Menge S 01:15:08.320 --> 01:15:08.800 drin sind. 01:15:09.280 --> 01:15:11.560 Das ist also nicht, dass Wörter irgendwie zerlegt werden und 01:15:11.560 --> 01:15:13.600 abgestimmt werden, sondern das macht gerade die Mengendifferenz. 01:15:13.600 --> 01:15:16.940 Und das würde das entsprechend dann erlösen. 01:15:20.630 --> 01:15:25.870 Genau, jetzt noch zwei Warnungen, ganz zum Abschluss der Vorlesung, zu 01:15:25.870 --> 01:15:29.430 diesem Begriff epsilonfreier Konkatenationsabschluss. 01:15:30.050 --> 01:15:35.430 Man sagt ganz lapidar immer, naja, L plus unterscheidet sich von L 01:15:35.430 --> 01:15:38.270 Sternchen, weil in L plus ist das Epsilon nicht drin. 01:15:39.110 --> 01:15:41.070 Das stimmt so nicht. 01:15:41.070 --> 01:15:48.130 Das stimmt nur dann, wenn ich sage, A sei ein Alphabet, weil in einem 01:15:48.130 --> 01:15:51.970 Alphabet ist erstmal das Epsilon per se nicht drin, weil das Epsilon 01:15:51.970 --> 01:15:55.890 ist ja eigentlich ein leeres Wort, aber kein Zeichen oder Symbol als 01:15:55.890 --> 01:15:56.210 solches. 01:15:57.530 --> 01:16:01.370 Wenn ich also ein Alphabet A mir hernehme und da ist kein Epsilon drin 01:16:01.370 --> 01:16:04.310 und wenn ich davon den Konkatenationsabschluss bilde und davon den 01:16:04.310 --> 01:16:07.670 epsilonfreien Konkatenationsabschluss, dann unterscheiden sie sich 01:16:07.670 --> 01:16:11.110 tatsächlich nur darin, dass in dem einen das Epsilon drin ist, in dem 01:16:11.110 --> 01:16:11.670 anderen nicht. 01:16:14.940 --> 01:16:22.440 Es kann aber sein, dass das Epsilon zum Beispiel Teil der formalen 01:16:22.440 --> 01:16:23.080 Sprache ist. 01:16:23.600 --> 01:16:26.480 Also angenommen, ich nehme ein Alphabet und ich mache A Stern. 01:16:27.600 --> 01:16:29.600 Und das nenne ich meine formale Sprache L. 01:16:30.360 --> 01:16:32.460 Dann ist da das leere Wort Epsilon enthalten. 01:16:33.040 --> 01:16:36.260 Und wenn ich jetzt L plus bilde, also den epsilonfreien 01:16:36.260 --> 01:16:41.140 Konkatenationsabschluss von L, dann ist da am Ende trotzdem immer noch 01:16:41.140 --> 01:16:45.760 das Epsilon enthalten, weil das Epsilon in der ursprünglichen Sprache 01:16:45.760 --> 01:16:47.100 enthalten war. 01:16:54.090 --> 01:16:59.390 Dann noch, wenn ich den epsilonfreien Konkatenationsabschluss der 01:16:59.390 --> 01:17:07.150 leeren Menge bilde, dann ist da drin auch mindestens das leere Wort, 01:17:07.510 --> 01:17:10.730 also nicht den epsilonfreien Konkatenationsabschluss der leeren Menge 01:17:10.730 --> 01:17:14.730 bilde, dann ist da drin zumindest das leere Wort enthalten. 01:17:17.870 --> 01:17:20.090 Gut, also was nehmen sie mit? 01:17:20.270 --> 01:17:25.090 Sie nehmen mit, dass formale Sprachen konkateniert werden können, so 01:17:25.090 --> 01:17:28.690 wie wir Wörter konkatenieren, dass wir so Potenzen bilden können von 01:17:28.690 --> 01:17:33.090 Konkatenationen, dass man da dann über die Vereinigung aller Potenzen 01:17:33.090 --> 01:17:36.730 zum Konkatenationsabschluss kommt, beziehungsweise zum epsilonfreien 01:17:36.730 --> 01:17:40.490 Konkatenationsabschluss, wenn man L hoch 0 in der Vereinigung nicht 01:17:40.490 --> 01:17:44.810 mit drin hat, dass ein Alphabet auch eine Sprache sein kann und ich 01:17:44.810 --> 01:17:47.410 die Menge aller möglichen Wörter über der Sprache entsprechend als 01:17:47.410 --> 01:17:53.210 Konkatenationsabschluss definieren kann, dass sie mit diesen Sachen 01:17:53.210 --> 01:17:56.330 rechnen können, dass sie also die Mengenoperationen, die sie 01:17:56.330 --> 01:18:00.910 kennengelernt haben, dass sie diese Potenzen von Wörtern, Potenzen von 01:18:00.910 --> 01:18:05.950 formalen Sprachen, alle verwenden können, um selber neue formale 01:18:05.950 --> 01:18:12.670 Sprachen zu definieren und dass sie halt mit diesen Ausdrücken sicher 01:18:12.670 --> 01:18:13.970 und sauber umgehen können. 01:18:15.030 --> 01:18:20.190 Und das wird demnächst auf dem Übungsblatt passieren, das heute 01:18:20.190 --> 01:18:21.070 rauskommt. 01:18:22.430 --> 01:18:25.210 Irgendwann im Laufe des Tages, also heute Abend, kommt irgendwann das 01:18:25.210 --> 01:18:25.970 neue Übungsblatt. 01:18:25.970 --> 01:18:29.630 Vergessen Sie nicht, rechtzeitig das aktuelle Übungsblatt abzugeben. 01:18:29.870 --> 01:18:34.710 Wir haben bis morgen 16 Uhr noch Zeit und Freitag haben wir dann die 01:18:34.710 --> 01:18:35.490 erste Übung. 01:18:35.750 --> 01:18:39.170 Da werden wir hier das Übungsblatt besprechen. 01:18:39.750 --> 01:18:42.110 Und ich habe noch eine Bitte, noch keiner verlässt den Raum, wir haben 01:18:42.110 --> 01:18:43.130 noch eine wichtige Bitte. 01:18:43.870 --> 01:18:48.250 Sie alle haben das Übungsblatt gelesen und auf dem Übungsblatt war 01:18:48.250 --> 01:18:49.890 diese Bonusaufgabe drauf. 01:18:50.890 --> 01:18:54.730 Und diese Bonusaufgabe lautete, entweder per Hand 0 oder 1 01:18:54.730 --> 01:18:56.930 hinschreiben oder halt Münze werfen. 01:18:57.870 --> 01:18:58.850 Das Ganze hat einen Sinn. 01:18:58.930 --> 01:19:02.190 Ich will mit Ihnen hier ein kleines Experiment durchführen, das ein 01:19:02.190 --> 01:19:03.910 bisschen was mit Kryptografie zu tun hat. 01:19:03.990 --> 01:19:07.150 Das immer schon mal so ganz sanft, so an einfache Dinge zur 01:19:07.150 --> 01:19:09.350 Kryptografie hereingeführt werden. 01:19:09.850 --> 01:19:11.830 Und da ist insbesondere Zufall sehr wichtig. 01:19:12.750 --> 01:19:17.290 Und anhand dieser Sachen, die Sie Ihren Tutoren schicken, werden wir 01:19:17.290 --> 01:19:21.670 mal Ihnen zeigen, dass Zufall nicht so was einfach Herzustellendes 01:19:21.670 --> 01:19:21.950 ist. 01:19:22.970 --> 01:19:26.390 Deswegen, meine Bitte wäre, dass unter Ihnen nicht nur Leute sind, die 01:19:26.390 --> 01:19:29.910 einfach nur 0 und 1 aufs Papier geschrieben haben, sondern dass auch 01:19:29.910 --> 01:19:32.490 ein paar Leute sich mal die Mühe machen, Münze zu werfen. 01:19:33.250 --> 01:19:36.550 Dann wird nämlich das Experiment interessant und dann werden wir das 01:19:36.550 --> 01:19:39.570 in einem der nächsten, nicht morgen, aber in einem der nächsten 01:19:39.570 --> 01:19:42.850 Vorlesungen mal besprechen und uns da die Ergebnisse mal ein bisschen 01:19:42.850 --> 01:19:43.330 anschauen. 01:19:43.890 --> 01:19:45.850 Okay, dann bis Freitag zur Übung.