WEBVTT 00:10.950 --> 00:17.950 Und wir gehen über zum nächsten Kapitel, das da heißt Kodierungen. 00:19.830 --> 00:25.310 Und die Grundlagen dessen, was man braucht, um jetzt zum Beispiel 00:25.310 --> 00:31.150 Zahlen in einem Rechner darzustellen, die reichen sehr lange zurück. 00:31.850 --> 00:37.250 Die reichen zurück in die Zeit des ausgehenden 17. 00:38.030 --> 00:38.870 Jahrhunderts. 00:38.870 --> 00:44.490 Und hier ist ein Ausschnitt aus einem Brief an den Herzog von 00:44.490 --> 00:46.010 Braunschweig -Wolfenbüttel. 00:46.410 --> 00:50.330 Damals halt Deutschland noch nicht ein Land, sondern eine Ansammlung 00:50.330 --> 00:55.110 unterschiedlicher Herzogtümer, Fürstentümer, die zum Teil in 00:55.110 --> 00:57.370 Königreiche zusammengefasst sind. 00:57.830 --> 01:00.690 Und hier halt entsprechend an den Herzog von Braunschweig 01:00.690 --> 01:06.830 -Wolfenbüttel, der den Ruf hatte, ein Freund und Förderer der 01:06.830 --> 01:07.870 Wissenschaften zu sein. 01:07.870 --> 01:11.790 Also wenn man halt damals Geld wollte, dann hat man nicht an die DFG 01:11.790 --> 01:15.410 einen Projektantrag geschrieben oder an die Europäische Kommission, 01:15.910 --> 01:20.650 sondern musste sich an den jeweiligen Herrscher wenden, der viel Geld 01:20.650 --> 01:25.250 zur Verfügung hatte und musste da dann irgendwie mit dem verhandeln, 01:25.670 --> 01:28.010 ob man nicht Geld für seine Forschung bekommen kann. 01:28.090 --> 01:33.170 Und das gehört dann halt dazu, dass man Weihnachts- und Neujahrskarten 01:33.170 --> 01:33.450 schreibt. 01:33.450 --> 01:35.990 Und die Weihnachts- und Neujahrskarte hieß dann damals, und jetzt 01:35.990 --> 01:38.930 schauen wir mal, ob wir das irgendwie verständlich zusammenbekommen. 01:39.690 --> 01:43.350 Ich hoffe, es werden eure hochfürstliche Durchlaut in Gnaden 01:43.350 --> 01:47.070 vermerken, dass ich sowohl dem Gebrauche als meinem Gemütstriebe 01:47.070 --> 01:50.930 zufolge bei dem eingetretenen neuen Jahre auf dieses und viele 01:50.930 --> 01:55.210 folgende denselben in beständiger Gesundheit alle selbst verlangende 01:55.210 --> 02:00.990 hohe fürstliche Ersprießlichkeit zu gemeinem und derulande besonderen 02:00.990 --> 02:02.990 Besten aus treuem Herzen anwünsche. 02:03.770 --> 02:06.150 Das ist mal eine Neujahrskarte, die hat Stil. 02:09.230 --> 02:12.910 Wenn man das liest, das könnte auch so ein bisschen so klingen, als 02:12.910 --> 02:16.390 sei das Ganze schon ein bisschen schiffriert, ist aber tatsächlich 02:16.390 --> 02:17.170 Klartext. 02:17.610 --> 02:21.250 Mit anderen Worten, alles Gute zum neuen Jahr, viel Erfolg und gute 02:21.250 --> 02:21.750 Gesundheit. 02:22.930 --> 02:30.270 Geschrieben hat das Ganze Gottfried Wilhelm Leibniz, gelebt 1646 bis 02:30.270 --> 02:35.010 1716, Philosoph, Mathematiker, Physiker, Bibliotheker. 02:36.110 --> 02:39.650 Also noch ein fast universal Gelehrter. 02:39.750 --> 02:43.810 Zu der Zeit damals konnte man noch sehr viele Wissenschaften parallel 02:43.810 --> 02:47.730 haben, weil das Wissen in einer einzelnen Teildisziplin überschaubar 02:47.730 --> 02:47.970 war. 02:47.970 --> 02:53.810 Wenn man jetzt sieht auf die Jahresdaten, 1716 geboren, wenn man jetzt 02:53.810 --> 02:56.550 ratterratter schnell rechnet, dann weiß man, letztes Jahr ist der 02:56.550 --> 02:58.570 Todestag 300 Jahre her. 02:59.210 --> 03:02.350 Also letztes Jahr vor 300 Jahren ist Leibniz gestorben. 03:02.810 --> 03:05.750 Dementsprechend war letztes Jahr auch eine Art Leibnizjahr. 03:06.190 --> 03:09.250 Wenn man so ein bisschen schaut, ist letztes Jahr relativ viel zu 03:09.250 --> 03:12.750 Leibniz publiziert und geschrieben worden. 03:12.750 --> 03:15.090 Ich habe da auch was ins Ilias gestellt. 03:15.710 --> 03:19.470 Wenn man sich mal ein bisschen dafür interessiert, wie so diese Genies 03:19.470 --> 03:23.010 gelebt und getickt haben, kann man sich das da auch mal anschauen. 03:23.090 --> 03:26.550 Das ist manchmal ganz interessant, dass man weiß, wo die Sachen, mit 03:26.550 --> 03:31.130 denen wir heute ganz selbstverständlich umgehen, wo die ursprünglich 03:31.130 --> 03:34.570 entstanden sind und was für eine Geistesleistung eigentlich 03:34.570 --> 03:41.250 dahintersteckt, diese hervorzubringen, um zu formalisieren, überhaupt 03:41.250 --> 03:42.630 erstmal auf die Idee zu kommen. 03:43.470 --> 03:48.750 Und das, was Leibniz gemacht hat, hat unter anderem eine große 03:48.750 --> 03:51.750 Bedeutung für die sogenannte Codierung. 03:53.650 --> 03:58.510 Und wenn Sie in einem Rechner etwas addieren oder subtrahieren 03:58.510 --> 04:03.770 heutzutage, dann wird das mehr oder weniger auf dieselbe Art und Weise 04:03.770 --> 04:06.430 gemacht, wie Leibniz das damals herausgefunden hat. 04:08.190 --> 04:11.790 Und eine der Dinge, die Leibniz halt gemacht hat, war auch, dass er 04:11.790 --> 04:16.930 erste Addier- und Arithmetikmaschinen gebaut und erfunden hat. 04:17.010 --> 04:21.110 Das waren sozusagen mechanische Taschenrechner, mit denen man 04:21.110 --> 04:23.910 mechanisch bestimmte Grundrechenarten ausführen konnte. 04:26.130 --> 04:29.330 Womit wir uns jetzt in diesem Kapitel insbesondere beschäftigen, ist 04:29.330 --> 04:32.590 erstmal, wie kann ich Zahlen im Rechner darstellen? 04:33.230 --> 04:36.470 Und ich will das natürlich so machen, dass ich hinterher auch diese 04:36.470 --> 04:41.290 arithmetischen Operationen, wie Addition, Subtraktion usw., auch 04:41.290 --> 04:42.770 vernünftig darstellen kann. 04:43.670 --> 04:50.510 Und da steckt wieder eine gewisse Transfer- und Entdeckungsleistung 04:50.510 --> 04:53.230 dahinter, mit der wir heutzutage eigentlich selbstverständlich 04:53.230 --> 04:56.990 umgehen, weil wir es in der Grundschule schon so beigebracht bekommen 04:56.990 --> 05:00.090 haben, die aber noch nicht unbedingt jederzeit eine 05:00.090 --> 05:01.350 Selbstverständlichkeit waren. 05:01.350 --> 05:04.570 Zum Beispiel sowas wie das Konzept der negativen Zahlen. 05:05.250 --> 05:08.110 Es ist also nicht nur reicht, positive Zahlen darzustellen. 05:08.270 --> 05:11.810 Bisher haben wir in der Regel in der Vorlesung immer mit positiven 05:11.810 --> 05:13.990 Zahlen gearbeitet, mit den natürlichen Zahlen. 05:14.490 --> 05:18.410 Entweder natürliche Zahlen einschließlich Null, als Null beschrieben, 05:18.510 --> 05:20.430 oder die positiven natürlichen Zahlen. 05:20.950 --> 05:24.590 Allein die Entdeckung der Null, dass das sowas ist wie eine Zahl für 05:24.590 --> 05:26.770 nichts, war schon eine große Leistung. 05:27.090 --> 05:29.390 Und auch die Entdeckung des Negativen. 05:29.390 --> 05:33.670 Bis sich die Mathematik mal mit negativen Zahlen beschäftigt hat, war 05:33.670 --> 05:37.870 halt auch schon eine gewisse Leistung, weil am Anfang hat man sich 05:37.870 --> 05:40.830 erst einmal damit begnügt, Dinge, die da sind, zu zählen. 05:41.450 --> 05:43.350 Irgendetwas, was nichts da ist, interessiert nicht. 05:43.870 --> 05:46.910 Und sich damit zu überlegen, was ist denn mit sozusagen dem Gegenteil 05:46.910 --> 05:47.690 von was da sein. 05:47.750 --> 05:48.810 Das hat eine Weile gedauert. 05:50.250 --> 05:53.070 Und das ist auch etwas, was wir uns anschauen müssen. 05:54.150 --> 05:58.930 Was Sie heutzutage verwenden, wenn Sie mit Zahlen umgehen, ist in der 05:58.930 --> 06:00.710 Regel immer die Dezimaldarstellung. 06:01.390 --> 06:04.790 Da gibt es verschiedene, unterschiedliche Theorien, warum das ist, 06:04.870 --> 06:06.970 warum wir unbedingt Dezimaldarstellung verwenden. 06:08.850 --> 06:12.450 Zum einen macht es teilweise bestimmte Rechenoperationen einfach. 06:12.650 --> 06:15.390 Zum anderen sagt man, das liegt halt daran, dass wir meistens zehn 06:15.390 --> 06:21.710 Finger haben, dass das also etwas ist, was uns natürlich ist, mit 06:21.710 --> 06:26.530 Zahlenbereich bis zehn zu hantieren und dann Vielfachen von zehn. 06:26.530 --> 06:30.170 Das kann auch was ein bisschen mit der Psychologie zu tun haben, dass 06:30.170 --> 06:34.590 wir bestimmte Spannungen nur bedingt bedecken. 06:35.130 --> 06:38.050 Es ist zum Beispiel klar, nicht immer muss man unbedingt mit 06:38.050 --> 06:41.610 Zehnerbasis arbeiten, wenn Sie sich schon in der Schule mit römischen 06:41.610 --> 06:43.170 Zahlen zum Beispiel beschäftigt haben. 06:43.510 --> 06:46.730 Die haben ein ganz komisches System gehabt, das zum Teil 12er basiert 06:46.730 --> 06:52.290 ist, zum Teil ganz seltsame Regeln hatte, um Zahlen darzustellen. 06:54.270 --> 06:56.770 Wir arbeiten mit der Dezimaldarstellung. 06:57.330 --> 07:01.110 Und jetzt sind wir wieder an einem Punkt in der Vorlesung angelangt, 07:01.210 --> 07:03.950 wo Farbe auf den Folien wichtig ist. 07:04.590 --> 07:10.730 Und wenn immer Sie irgendwas lesen, was aussieht wie eine Ziffer oder 07:10.730 --> 07:16.050 eine Konkatenation von Ziffern, dann müssen Sie unterscheiden, schaue 07:16.050 --> 07:21.350 ich mir zurzeit ein Wort an, das besteht aus der Konkatenation von 07:21.350 --> 07:27.970 Zeichen und diese Zeichen können aussehen wie Ziffern oder spreche ich 07:27.970 --> 07:32.070 über eine Zahl und diese Zahl ist zufälligerweise in 07:32.070 --> 07:33.670 Dezimaldarstellung dargestellt. 07:35.930 --> 07:41.650 Wenn wir jetzt also Zahlen kodieren wollen als Nachrichten, wir 07:41.650 --> 07:45.070 erinnern uns, eine Nachricht ist irgendwie was abstrahiertes vom 07:45.070 --> 07:49.450 Signal, dass es sich dabei um eine Zahl handelt, das ist schon 07:49.450 --> 07:51.670 Information, davon weiß der Rechner nichts. 07:52.250 --> 07:56.170 Der Rechner weiß nur was von Nachrichten und dass das eine Zahl ist, 07:56.230 --> 08:00.010 das ist das, was wir rein interpretieren, wenn wir das Bezugssystem 08:00.010 --> 08:00.690 erkennen. 08:00.970 --> 08:05.990 Also in diesem Fall Bezugssystem, Darstellung einer Zahl als Nachricht 08:05.990 --> 08:07.050 im Dezimalsystem. 08:07.730 --> 08:11.230 Dann sieht das so aus, dass es eine Nachricht ist, dann kann man 08:11.230 --> 08:14.550 daraus Wörter machen und damit man Wörter machen kann, braucht man ein 08:14.550 --> 08:14.950 Alphabet. 08:15.290 --> 08:19.670 Und wir haben ein Alphabet, das nennen wir Z10, wichtig, das Z ist 08:19.670 --> 08:22.490 nicht so doppelt gestrichen, wie wir das schon mal hatten, das ist 08:22.490 --> 08:25.130 einfach gestrichen und das soll damit eben andeuten, dass wir es hier 08:25.130 --> 08:29.170 mit Zeichen oder Symbolen zu tun haben und nicht mit Zahlen per se. 08:29.950 --> 08:31.630 Und deswegen schreiben wir die auch blau. 08:32.130 --> 08:35.070 Wir sind erstmal, das sind Zeichen, da interpretieren wir erstmal noch 08:35.070 --> 08:35.810 nichts rein. 08:36.570 --> 08:40.690 Wenn wir wissen wollen, für welche Zahl das steht, dann müssen wir 08:40.690 --> 08:44.470 interpretieren, dann brauchen wir Bedeutung, Semantik und eine 08:44.470 --> 08:49.050 Möglichkeit, zum Beispiel diese Ziffern, die Zeichen sind, in diesem 08:49.050 --> 08:55.270 Alphabet, zu interpretieren ist, dass man sagt, okay, so eine blaue 0, 08:55.450 --> 09:01.530 das Zeichen 0, das soll stehen für die Zahl 0 und das Zeichen 1 soll 09:01.530 --> 09:05.250 stehen für die Zahl 1 und so weiter, das Zeichen 9 soll stehen für die 09:05.250 --> 09:05.830 Zahl 9. 09:06.710 --> 09:10.650 Und jetzt beißt sich die Katze in den Schwanz, weil damit ich Ihnen 09:10.650 --> 09:16.350 mitteilen kann, für welche Zahl so ein Zeichen aus diesem Alphabet 09:16.350 --> 09:20.630 stehen soll, da muss ich Ihnen das mitteilen und wenn ich Ihnen das 09:20.630 --> 09:23.090 mitteile, muss ich das als Nachricht kodieren und Ihnen übermitteln. 09:24.250 --> 09:28.330 Eine Möglichkeit, das zu kodieren und zu übermitteln ist zum Beispiel, 09:28.510 --> 09:33.610 indem ich die Zahl in natürlicher Sprache ausschreibe. 09:34.050 --> 09:37.970 Indem ich also das Wort 0, das ausgesprochen 0 ist, da halt im 09:37.970 --> 09:40.730 lateinischen Alphabet, im deutschen hinschreibe. 09:42.250 --> 09:43.710 Was ist das jetzt? 09:44.310 --> 09:46.950 Das ist offensichtlich eine Abbildung. 09:47.670 --> 09:50.570 Ich habe einen Definitionsbereich, der ist Z10. 09:51.330 --> 09:56.630 Ich habe einen Zielbereich, das ist die Menge der Worte 0, 1, 2, 8, 9, 09:57.330 --> 10:01.970 die aber in Wirklichkeit für die zugehörigen Zahlen stehen. 10:01.970 --> 10:05.530 Das heißt also, ich habe auf der einen Seite einen Definitionsbereich, 10:06.010 --> 10:08.970 der ist ein Alphabet von Zeichen und auf der anderen Seite habe ich 10:08.970 --> 10:11.750 einen Zielbereich, das sollen Zahlen sein. 10:12.310 --> 10:14.550 Zum Beispiel eine Teilmenge der natürlichen Zahlen. 10:15.130 --> 10:16.830 Und wenn ich sie hinschreibe, muss ich halt wieder Ziffern schreiben, 10:16.910 --> 10:17.870 dann habe ich wieder ein Kodierungsproblem. 10:18.310 --> 10:22.690 Jedenfalls, ich habe da also eine Abbildung, die nenne ich Numm10 von 10:22.690 --> 10:23.010 x. 10:23.290 --> 10:28.350 Und diese Abbildung bildet halt ab, die Zeichen aus dem Alphabet auf 10:28.350 --> 10:29.610 die zugehörigen Zahlen. 10:31.070 --> 10:35.610 Jetzt ist das natürlich recht mühsam, immer die Zahlen auszuschreiben. 10:35.730 --> 10:39.190 Wenn ich also sehr große Zahlen haben will und ich will deutlich 10:39.190 --> 10:41.630 machen, dass es mir jetzt nicht um die Zeichen geht, sondern um die 10:41.630 --> 10:47.250 Zahl selber und ich will 1.365.723 hinschreiben, dann ist das ein sehr 10:47.250 --> 10:47.870 langes Wort. 10:48.710 --> 10:52.510 Das macht es natürlich unhandlich, deswegen hat man ja auch zum 10:52.510 --> 10:55.490 Beispiel sowas wie die Dezimaldarstellung sich hergenommen. 10:56.310 --> 11:00.110 Das heißt, angenehmer ist es natürlich, das Ganze so zu schreiben. 11:01.290 --> 11:02.710 Und da ist jetzt halt Farbe wichtig. 11:02.870 --> 11:06.190 Wenn ich also darauf hinaus will, dass es sich im Augenblick um das 11:06.190 --> 11:09.130 Zeichen aus dem Alphabet handelt, dann schreibe ich das in Blau. 11:09.650 --> 11:13.810 Wenn ich darauf hinaus will, dass ich mich jetzt auf die tatsächliche 11:13.810 --> 11:18.250 Zahl beziehe und diese Zahl halt ihnen mitteile in der 11:18.250 --> 11:21.210 Dezimaldarstellung, dann schreibe ich das Ganze in Schwarz. 11:21.210 --> 11:26.710 Dann haben wir halt hier diese Abbildung, die erst mal kleinen Num 10 11:26.710 --> 11:32.690 von X abbildet, aus dem Z10 in eine Teilmenge der natürlichen Zahlen. 11:33.730 --> 11:36.810 Und wir machen das natürlich so, wir bilden jetzt Wörter über diesem 11:36.810 --> 11:42.270 Alphabet, indem wir diese Zeichen, diese Ziffern irgendwie miteinander 11:42.270 --> 11:45.430 konkatenieren, bekommen wir Wörter heraus. 11:46.150 --> 11:51.870 Und diese Wörter sollen eben gerade eine Zahl darstellen aus den 11:51.870 --> 11:57.970 natürlichen Zahlen und das Ganze in der Dezimaldarstellung, im 11:57.970 --> 11:59.030 Zehnerzahlensystem. 11:59.650 --> 12:03.610 Und auch das ist wieder eine Abbildung, die nenne ich Num 10, diesmal 12:03.610 --> 12:05.170 Num großgeschrieben. 12:06.050 --> 12:09.790 Und die bildet jetzt nicht mehr ab einzelne Zeichen aus dem Alphabet, 12:10.350 --> 12:13.910 sondern die bildet gesamte Wörter ab aus diesem Alphabet und die Menge 12:13.910 --> 12:17.250 aller möglichen Wörter hatten wir eben mit dem Konkatenationsabschluss 12:17.250 --> 12:18.130 hingeschrieben. 12:18.250 --> 12:20.510 Das ist eben gerade Z10 Stern. 12:21.110 --> 12:24.690 Das ist eben gerade der Konkatenationsabschluss und das wird jetzt 12:24.690 --> 12:27.710 abgebildet wieder in die natürlichen Zahlen hinein. 12:27.870 --> 12:32.350 Das heißt also, ich bilde jetzt mit der Dezimaldarstellung, will ich, 12:32.430 --> 12:36.490 wenn ich die interpretiere, die Dezimaldarstellung einer Zahl, bilde 12:36.490 --> 12:41.870 ich eben ein Wort über diesem Alphabet Z10 ab auf eine natürliche 12:41.870 --> 12:42.210 Zahl. 12:43.490 --> 12:44.910 Das ist das, was ich meinte. 12:45.010 --> 12:47.590 Deswegen ist das, dass Sie wissen, was eine Abbildung ist, was ein 12:47.590 --> 12:50.190 Alphabet ist, eine Sprache ist, so wichtig. 12:50.290 --> 12:53.250 Weil alles, was wir jetzt machen, um solche Dinge zu definieren, wir 12:53.250 --> 12:55.870 hantieren mit Mengen, wir hantieren mit Abbildungen, wir müssen in der 12:55.870 --> 12:58.410 Lage sein, eine Abbildung zu definieren. 12:58.530 --> 13:01.010 Das erste, wenn ich eine Abbildung definiere, ist Definitions- und 13:01.010 --> 13:02.650 Zielbereich, steht da schon. 13:02.650 --> 13:06.410 Da oben bei dieser kleinen Abbildung NUM10 von X, da habe ich die 13:06.410 --> 13:09.970 Abbildungsvorschrift hingeschrieben, in Form so einer Tabelle, aber 13:09.970 --> 13:12.910 zum Beispiel noch nicht den Definitions- und Zielbereich. 13:13.030 --> 13:15.210 Dann habe ich Ihnen nur gesagt, das können Sie sich aber denken, dass 13:15.210 --> 13:19.350 es von Z10 auf die natürlichen Zahlen abbildet, gemäß dieser 13:19.350 --> 13:20.350 Abbildungsvorschrift. 13:22.070 --> 13:26.770 Jetzt können Sie sich auch überlegen, als einfache Überlegung, diese 13:26.770 --> 13:32.450 kleine Abbildung, klein NUM10 von X, ist das eine sujektive Abbildung? 13:34.990 --> 13:36.130 Wer ist für sujektiv? 13:39.540 --> 13:41.540 Wer ist für nicht sujektiv? 13:43.560 --> 13:49.040 Diese kleine Abbildung NUM10 von X, was ist denn das Urbild der Zahl 13:49.040 --> 13:49.620 1000? 13:51.480 --> 13:53.360 Gibt es nicht, in der Tabelle gibt es nicht. 13:53.360 --> 13:59.020 Ich habe Urbilder 0 bis 9, aber zum Beispiel die Zahl 1000 ist kein 13:59.020 --> 14:01.700 Ziel, kein Abbild. 14:01.940 --> 14:05.740 Das heißt, sujektiv ist diese Abbildung nicht das kleine NUM10 von X. 14:06.280 --> 14:07.340 Ist sie injektiv? 14:10.820 --> 14:12.280 Ja, injektiv ist sie. 14:12.280 --> 14:20.600 Also es gibt keine Zeichen, keine Ziffer aus dem Alphabet, die auf... 14:20.600 --> 14:25.260 es gibt keine zwei Zeichen, zwei unterschiedlichen Zeichen aus dem 14:25.260 --> 14:28.080 Alphabet, die auf eine und dieselbe Zahl abgebildet werden. 14:28.640 --> 14:31.440 Also sujektiv ist es nicht, aber immerhin injektiv. 14:32.180 --> 14:41.640 Jetzt kann man sich überlegen, groß NUM10, das soll jetzt jeder Zahl 14:41.640 --> 14:50.900 als Wort über dem Alphabet Z10, soll jedes dieser Wörter abbilden auf 14:50.900 --> 14:53.420 eine Zahl aus der natürlichen Zahl. 14:54.000 --> 14:56.020 Ist das eine sujektive Abbildung? 14:57.320 --> 14:58.220 Wer ist für sujektiv? 14:59.920 --> 15:01.860 Okay, wer ist nicht für sujektiv? 15:03.100 --> 15:05.820 Okay, das ist offensichtlich sujektiv. 15:06.440 --> 15:11.720 Weil für jede natürliche Zahl kann ich ja ein Wort hinschreiben. 15:11.860 --> 15:14.580 Jede natürliche Zahl kann ich im Dezimalsystem darstellen. 15:14.720 --> 15:18.120 Haben Sie in der Schule gelernt, das hat man Ihnen nicht so explizit 15:18.120 --> 15:18.900 vielleicht beigebracht? 15:19.240 --> 15:23.600 Die andere Abfrage, ist diese Abbildung injektiv? 15:25.080 --> 15:26.160 Wer ist für injektiv? 15:29.880 --> 15:31.620 Wer ist für nicht injektiv? 15:33.400 --> 15:36.340 Einfaches Beispiel, das zeigt, dass die Abbildung nicht injektiv ist. 15:38.160 --> 15:39.800 Zahlen mit führenden Nullen. 15:40.060 --> 15:45.100 Wenn ich also hinschreibe 0,1 oder wenn ich hinschreibe 1, dann wird 15:45.100 --> 15:47.940 das auf 1 und dieselbe Zahl abgebildet. 15:48.280 --> 15:49.600 Zeils ist nicht injektiv. 15:49.780 --> 15:54.000 Also NUM10 mit groß geschrieben ist zwar sujektiv, aber im Gegensatz 15:54.000 --> 15:57.160 zu kleinen NUM10 nicht injektiv. 15:59.600 --> 16:02.460 Jetzt haben wir ja das Problem, wenn wir eine Abbildung definieren, 16:02.600 --> 16:05.840 Ziel - und Definitionsbereich brauchen wir und wir brauchen die 16:05.840 --> 16:07.200 Abbildungsvorschrift. 16:07.860 --> 16:11.000 Es ist die Frage, wie können wir jetzt diese Abbildungsvorschrift, der 16:11.000 --> 16:15.060 Dezimaldarstellung, groß NUM10, vernünftig hinschreiben. 16:16.180 --> 16:18.380 Und jetzt kommt wieder etwas, was wir hier machen. 16:18.500 --> 16:24.440 80% der Dinge sind Abbildungen, Relationen, Alphabete, formale 16:24.440 --> 16:28.380 Sprachen und ganz wichtig auch, haben wir extra ein eigenes Kapitel 16:28.380 --> 16:32.600 zu, was ist so eine typische Methode, um etwas zu definieren? 16:35.580 --> 16:38.560 Was ist so eine typische Methode, die Sie kennengelernt haben, um 16:38.560 --> 16:39.260 etwas zu definieren? 16:44.700 --> 16:47.540 Wir haben kennengelernt, wie können wir Sachen definieren. 16:47.880 --> 16:52.120 Und wir hatten uns eine Methode rausgesucht, um etwas zu definieren 16:52.120 --> 16:53.620 und die recht ausführlich besprochen. 16:55.680 --> 16:57.860 Genau, induktive Definition. 16:58.580 --> 17:02.460 Und wenn Sie irgendwie mit Sprachen und mit Wörtern hantieren und 17:02.460 --> 17:07.320 Abbildungen auf Wörtern definieren müssen, dann ist die induktive 17:07.320 --> 17:11.300 Definition immer ein guter Verdächtiger, der vielleicht hier ganz 17:11.300 --> 17:12.160 nützlich sein könnte. 17:12.820 --> 17:15.460 Und genauso kann man sich jetzt hier überlegen, dass für die 17:15.460 --> 17:20.380 Definition der Dezimaldarstellung eben eine induktive Definition recht 17:20.380 --> 17:21.640 geeignet sein könnte. 17:22.860 --> 17:26.320 Jetzt überlegen wir uns, was soll denn das der Zahlenwert sein? 17:26.400 --> 17:31.060 Wenn ich jetzt also ein Wort habe über dem Alphabet, das bestehe aus K 17:31.060 --> 17:37.380 -Zeichen, jetzt nummeriere ich die Zeichen nicht von links nach rechts 17:37.380 --> 17:40.660 durch, sondern ich nummeriere sie von rechts nach links durch und 17:40.660 --> 17:44.840 sage, das Zeichen ganz rechts habe den Index 0, das sei x0, das 17:44.840 --> 17:50.100 Zeichen ganz links, das habe den Index k-1, dann kann ich relativ 17:50.100 --> 17:56.040 leicht aus dem Wort und dieser Abbildung, klein num 10 von x, die ich 17:56.040 --> 18:01.100 da habe, die jeder Ziffer einen Zahlenwert zuordnet, kann ich relativ 18:01.100 --> 18:03.570 leicht jetzt die eigentliche Zahl errechnen. 18:04.080 --> 18:06.100 Das ist etwas, das machen sie ganz intuitiv. 18:06.620 --> 18:10.580 Das ist eben, ich nehme das ganz rechts, nehme davon den Zahlenwert 18:10.580 --> 18:14.840 von der Ziffer und multipliziere die mit 10 hoch 0 mit 1. 18:15.380 --> 18:19.860 Dann gehe ich einen Ziffer weiter nach links nehme davon wieder den 18:19.860 --> 18:23.580 Zahlenwert und multipliziere das mit 10 hoch 1. 18:24.420 --> 18:28.040 Gehe einen Ziffer weiter nach links, nehme davon den Zahlenwert gemäß 18:28.040 --> 18:32.920 klein num 10 von x, multipliziere das Ganze mit 10 hoch 2 und so 18:32.920 --> 18:35.620 weiter und so fort, bis ich bei der ganz linken Ziffer bin. 18:36.220 --> 18:42.280 Jeder hat den Index k-1 und multipliziere jetzt den Zahlenwert dieser 18:42.280 --> 18:46.540 Ziffer gemäß klein num 10 von x mit 10 hoch k-1. 18:47.840 --> 18:52.540 Das hat halt die unschöne Eigenschaft, dass ich die Länge des Wortes 18:52.540 --> 18:54.840 kennen muss, wenn ich das so definiere. 18:56.000 --> 18:57.440 Das geht eleganter. 18:58.600 --> 19:02.420 Jetzt kann man sich einmal damit ein bisschen rum-experimentieren und 19:02.420 --> 19:06.980 kann zum Beispiel einfach mal den Faktor 10 aus dieser Summe da oben 19:06.980 --> 19:08.940 raus multiplizieren. 19:09.260 --> 19:17.740 Dann erhalte ich sowas wie 10 mal alles bis auf die ganz rechte Ziffer 19:17.740 --> 19:23.280 plus den Zahlenwert der ganz rechten Ziffer, weil diese 10 hoch 0 habe 19:23.280 --> 19:26.380 ich entsprechend ausmultipliziert. 19:28.000 --> 19:34.300 Und was passiert ist, dass in diesem Inneren die ganzen Exponenten um 19:34.300 --> 19:35.280 1 niedriger werden. 19:35.520 --> 19:39.240 Das heißt, die gehen dann nur noch von 10 hoch 0 bis 10 hoch k-2. 19:39.900 --> 19:42.660 Das ist eigentlich ein ganz guter Hinweis darauf, wenn da immer 19:42.660 --> 19:46.220 irgendwas kleiner wird, dann kann man da der Sache vielleicht mit 19:46.220 --> 19:47.800 Induktion R werden. 19:49.020 --> 19:53.160 Und wenn ich mir das anschaue, die Definition von dem, was da in den 19:53.160 --> 19:56.320 runden Klammern steht, dann ist das eben gerade wieder diese 19:56.320 --> 20:01.520 Definition von groß num c, also Wert gemäß Dezimaldarstellung von dem 20:01.520 --> 20:04.860 Wort xk-1 bis x1. 20:05.540 --> 20:09.740 Das heißt, ich habe also x0 abgeschnitten, habe dem den Wert 20:09.740 --> 20:13.160 vorgegeben, gemäß meiner oben festgelegten, einfach festgelegten 20:13.160 --> 20:19.060 Abbildung und habe das, was übrig bleibt, zurückgeführt auf groß num 20:19.060 --> 20:25.200 10 von x1 bis xk-1 und das Ganze mit 10 multipliziert. 20:25.680 --> 20:29.300 Ich habe also die Größe des Problems dadurch reduziert, dass ich 20:29.300 --> 20:31.860 rechts was vom Wort abgeschnitten habe und mich jetzt wieder 20:31.860 --> 20:36.500 zurückbeziehe auf die Definition des Gleichens mit auf ein kürzeres 20:36.500 --> 20:36.720 Wort. 20:38.760 --> 20:42.420 Gut, wenn wir also eine Induktion induktiv definieren wollen, dann 20:42.420 --> 20:45.000 haben wir kennengelernt, das erste, was wir brauchen, ist ein 20:45.000 --> 20:46.140 Induktionsanfang. 20:46.740 --> 20:48.660 Und da müssen wir uns jetzt ein bisschen was überlegen. 20:49.600 --> 20:51.460 Worüber lassen wir überhaupt die Induktion laufen? 20:51.620 --> 20:55.620 Worüber lassen wir jetzt diesen Index n aller natürlichen Zahlen, für 20:55.620 --> 20:58.860 die wir zeigen, etwas definieren wollen, laufen? 20:59.300 --> 21:02.660 Und bei formalen Sprachen ist eine so der Standardtechniken, was 21:02.660 --> 21:05.500 häufig gut funktioniert, wir lassen den Index über die Länge des 21:05.500 --> 21:06.260 Wortes laufen. 21:06.920 --> 21:12.520 Wir fangen also mit ganz kurzen Wörtern an und das kürztmögliche Wort 21:12.520 --> 21:14.080 hat halt die Länge 0, ist Y. 21:14.980 --> 21:19.580 Wir müssen jetzt also Num groß Num 10 von Y festlegen. 21:20.120 --> 21:23.480 Und da lehnen wir per Definition fest, das sei gleich 0. 21:24.700 --> 21:26.020 Und das ist relativ wichtig. 21:26.400 --> 21:31.600 Das heißt also, mit anderen Worten, wenn Sie ein Wort über den Ziffern 21:31.600 --> 21:36.480 haben, der Dezimaldarstellung, das nichts hat, das kein Zeichen hat, 21:36.560 --> 21:40.620 das also Länge 0 hat, das nichts lang ist, dann hat das trotzdem einen 21:40.620 --> 21:44.460 Zahlenwert und dann hat das den Zahlenwert eben von 0. 21:47.540 --> 21:51.800 Und jetzt ist als nächstes, den Induktionsanfang haben wir, brauchen 21:51.800 --> 21:52.920 wir den Induktionsschritt. 21:53.460 --> 21:56.300 Jetzt nehmen wir uns also ein Wort her, aus dem 21:56.300 --> 22:00.640 Konkatenationsabschluss, über dem Alphabet der Ziffern der 22:00.640 --> 22:09.760 Dezimaldarstellung und wir nehmen uns ein Zeichen her, aus dem Z10. 22:10.340 --> 22:17.580 Und wir sagen jetzt, dieses Wort konkateniert mit dem Zeichen, dafür 22:17.580 --> 22:22.440 legen wir jetzt einen Zahlenwert fest. 22:23.180 --> 22:25.480 Und jetzt muss man sich was überlegen. 22:26.380 --> 22:30.860 Nämlich, kann ich denn jedes Wort so zerlegen? 22:30.860 --> 22:34.060 Kann ich also jedes beliebige Wort, das es gibt, auch wirklich 22:34.060 --> 22:40.300 darstellen, als ein Wort aus Z-Stern und aus einem einzelnen Zeichen? 22:42.300 --> 22:46.980 Das leere Wort kann ich so offensichtlich schon mal nicht darstellen, 22:47.100 --> 22:54.220 weil das leere Wort ist nicht die Konkatenation mit irgendeinem 22:54.220 --> 22:59.040 Zeichensymbol aus dem Alphabet Z10, sondern dann habe ich mindestens 22:59.040 --> 23:00.660 ein Wort, das mindestens einslang ist. 23:01.400 --> 23:05.380 Aber Wörter, die einslang sind, die kann ich so zum Beispiel 23:05.380 --> 23:05.940 darstellen. 23:06.620 --> 23:10.160 Also eben nehme ich gerade die Konkatenation von Y und das ist 23:10.160 --> 23:13.840 wiederum in Z10-Stern enthalten, weil es der Konkatenationsabschluss 23:13.840 --> 23:21.380 ist, der Y auch enthält, und einem Zeichen aus dem Alphabet Z10. 23:21.380 --> 23:24.360 Da kann ich immerhin Wörter, die mindestens einslang sind, darstellen 23:24.360 --> 23:28.700 und für jedes beliebige andere Wort kann ich natürlich hinten immer 23:28.700 --> 23:33.620 das letzte Zeichen abschneiden und kann es als das Restwort W und 23:33.620 --> 23:35.840 dieses letzte Zeichen X darstellen. 23:36.660 --> 23:39.780 Jetzt lautet einfach, so wie wir das vorhin ausgerechnet haben, dieser 23:39.780 --> 23:44.900 Induktionsschritt, Nummer von 10 von einem Wort, das diese Gestalt 23:44.900 --> 23:50.820 hat, wie X, wie aus Z-Stern, X aus dem Alphabet Z, dann ist das gerade 23:50.820 --> 23:58.080 10 mal Nummer 10 von W plus klein Nummer 10 von X. 23:58.840 --> 24:02.020 Klein Nummer 10 von X ist immer definiert, das ist das letzte Zeichen 24:02.020 --> 24:07.540 des Wortes und dann produziere ich die Länge des Wortes und muss das 24:07.540 --> 24:11.660 Ganze dann wieder rekursiv reintun und kann dann das Ganze aber mit 10 24:11.660 --> 24:12.900 multiplizieren. 24:14.600 --> 24:18.700 Das heißt, das ist also eine allgemeine Technik, die wir sehr häufig 24:18.700 --> 24:23.320 anwenden können, wenn wir Abbildungen definieren, die von einer 24:23.320 --> 24:28.940 Sprache irgendwie in eine andere oder die vom Konkatenationsabschluss 24:28.940 --> 24:31.320 in irgendeine andere Menge abbilden. 24:31.700 --> 24:34.160 Also nicht nur von einer Sprache, sondern von dem gesamten 24:34.160 --> 24:38.480 Konkatenationsabschluss über einem Alphabet abbildend in einer Menge. 24:40.200 --> 24:44.380 Wir wollen jetzt diese Funktion definieren für jedes Wort beliebiger 24:44.380 --> 24:44.600 Menge. 24:45.300 --> 24:48.660 Wir definieren den Wortanfang, Wortlänge ist gleich 0. 24:48.800 --> 24:53.120 Wir definieren also, was soll der Funktionswert von Y sein und 24:53.120 --> 24:58.740 definieren dann den Definitionsschritt von Wortlänge n nach Wortlänge 24:58.740 --> 25:00.040 n plus 1. 25:00.540 --> 25:03.460 Wir gehen also davon aus, dass die Funktion schon für ein Wort der 25:03.460 --> 25:09.220 Länge n definiert ist und definieren jetzt, was ist der Wert der 25:09.220 --> 25:11.640 Funktion für ein Wort der Länge n plus 1. 25:14.340 --> 25:18.260 Und wenn wir das gemacht haben, haben wir halt gemäß des Prinzips der 25:18.260 --> 25:24.460 vollständigen Induktion das für alle Wörter beliebiger Länge gezeigt. 25:25.080 --> 25:30.780 Und dabei ist es wichtig, es ist egal, ob ich das Wort nach rechts hin 25:30.780 --> 25:34.460 verlängere, also ob ich ein Wort nehme und rechts ein Zeichen dran 25:34.460 --> 25:38.460 nehme oder ob ich ein Wort nehme und links ein Zeichen dran lege. 25:38.840 --> 25:41.680 Ich kann das entweder auf die eine Art und Weise definieren oder ich 25:41.680 --> 25:44.680 kann es auf die andere Art und Weise definieren. 25:45.200 --> 25:50.620 Ich muss halt nur aufpassen, das Wort muss von der Länge n sein und X 25:50.620 --> 25:54.840 muss ein Zeichen sein und dann als Wort interpretiert hat es 25:54.840 --> 25:59.020 logischerweise die Länge 1, wenn es ein Zeichen aus dem Alphabet war. 26:04.400 --> 26:08.260 Die Dezimaldarstellung ist das, was Sie meistens in der Schule 26:08.260 --> 26:09.060 verwendet haben. 26:09.180 --> 26:12.180 Wenn Sie Informatikunterricht hatten oder ein bisschen ausgereifteren 26:12.180 --> 26:15.420 Mathematikunterricht, haben Sie auch schon mal ansatzweise andere 26:15.420 --> 26:20.960 Zahlendarstellungen kennengelernt, zum Beispiel das Binärsystem oder 26:20.960 --> 26:22.760 auch die römischen Zifferndarstellung. 26:23.560 --> 26:29.180 Wir hätten gerne, dass wir beliebige, möglichst beliebige 26:29.180 --> 26:30.160 Darstellungen haben. 26:30.160 --> 26:36.520 Und die Frage lautet da, und das ist vielleicht von Interesse, was ist 26:36.520 --> 26:40.720 das kleinstmögliche Alphabet, das ich verwenden kann, um alle 26:40.720 --> 26:43.240 natürlichen Zahlen darzustellen. 26:44.640 --> 26:49.240 Und das ist eben eine der großen Leistungen von Leibniz, dass er 26:49.240 --> 26:55.820 gezeigt hat, dass zwei Ziffern ausreichen, um jede andere beliebige 26:55.820 --> 27:04.540 natürliche Zahl, nicht negative, natürliche Zahl darzustellen und auch 27:04.540 --> 27:06.280 damit rechnen. 27:06.840 --> 27:11.940 Und das ist jetzt hier ein Beispiel aus der Art und Weise, wie Leibniz 27:11.940 --> 27:12.860 das gemacht hatte. 27:13.160 --> 27:17.160 Er hat beispielsweise gezeigt, wie man jetzt addieren kann mit einer 27:17.160 --> 27:21.980 Zahl, die im Binärsystem, also nur mit zwei Ziffern dargestellt wird. 27:21.980 --> 27:27.160 Rechts sieht man immer den Wert der Zahlen im Dezimalsystem, links im 27:27.160 --> 27:28.520 Binärsystem. 27:29.100 --> 27:31.800 Und dann hat er gezeigt, wie man die Sachen addieren kann. 27:33.960 --> 27:37.000 Wenn wir uns jetzt mal ganz oben links in der Matrix das Ding 27:37.000 --> 27:40.800 anschauen, dann ist das nichts anderes als eine Addition, so wie Sie 27:40.800 --> 27:44.000 mal mit Papier und Bleistift gelernt haben zu addieren. 27:44.420 --> 27:48.540 Wenn man also im Binärsystem die Zahlen 1,1,0 und 1,1,1 addieren will, 27:48.540 --> 27:52.420 dann geht man ganz rechts hin und addiert 1 und 0 ist 1. 27:53.360 --> 27:56.620 Dann addiert man 1 und 1, das ist halt 0. 27:57.220 --> 27:59.320 Übertrag 1, Übertrag hingeschrieben. 28:00.140 --> 28:06.880 Dann habe ich jetzt also da Übertrag plus 1 ist 0 und ein Übertrag 28:06.880 --> 28:08.240 plus 1 ist 1. 28:08.540 --> 28:10.340 Den Übertrag wieder hingeschrieben. 28:10.640 --> 28:15.080 Übertrag plus nichts, nichts ist immer 0, ist 1 und dann habe ich halt 28:15.080 --> 28:16.320 addiert. 28:17.280 --> 28:22.740 Und jetzt denken Sie mal an die Aussagenlogik und in der Aussagenlogik 28:22.740 --> 28:24.320 an die Bool'schen Funktionen. 28:25.480 --> 28:29.140 Bool'sche Funktionen hatten wir so definiert, dass man damit immer 28:29.140 --> 28:34.240 zwei Wahrheitswerte, wahr oder falsch, miteinander verknüpfen kann und 28:34.240 --> 28:36.600 man hat neun Wahrheitswerte herausbekommen. 28:37.240 --> 28:40.660 Und wir hatten damals schon gesagt, manchmal schreibt man WF und 28:40.660 --> 28:42.200 manchmal schreibt man 1 oder 0. 28:49.550 --> 28:51.690 Jetzt gucken wir mal durch, was wir alles hatten. 28:51.690 --> 28:56.130 Wir hatten und, 1 und 0 ist 0. 28:57.830 --> 28:57.830 Gut. 28:59.350 --> 29:04.230 1 oder 0 ist 1, ok, da kommt zumindest schon mal das Richtige raus, 29:04.810 --> 29:05.130 unten. 29:05.790 --> 29:09.790 Bei der nächsten haben wir dann stehen, 1 oder 1 ist 0. 29:11.030 --> 29:16.390 Also und oder oder, 1 oder 1 ist 1, sollte aber 0 sein. 29:16.390 --> 29:20.410 Also und oder oder funktionieren irgendwie nicht als 29:20.410 --> 29:24.130 Einzeloperationen, um da zum Beispiel sowas einfach zu addieren zu 29:24.130 --> 29:24.330 können. 29:24.970 --> 29:26.610 Es gibt aber noch andere Dinge. 29:27.270 --> 29:29.370 Es gibt zum Beispiel das exklusive oder. 29:29.810 --> 29:31.590 Ist jedem das exklusive oder bekannt? 29:31.770 --> 29:32.450 Wer kennt es nicht? 29:34.550 --> 29:39.990 Das exklusive oder ist auch sowas wie eine Bool'sche Funktion und sagt 29:39.990 --> 29:46.170 halt, nicht wie das oder eines von, eines von beiden oder beide müssen 29:46.170 --> 29:47.410 wahr sein, damit es weiß. 29:47.590 --> 29:53.590 Also 1 oder 0 ist wahr, 1 oder 1 ist wahr, 0 oder 1 ist wahr, sondern 29:53.590 --> 29:57.050 die sagt, genau eines von beiden muss wahr sein. 29:57.470 --> 30:02.270 Und da heißt es halt, 1 exklusiv oder 0 ist wahr. 30:03.910 --> 30:10.870 War falsch, exklusive war ist wahr und alles andere ist falsch. 30:11.330 --> 30:17.750 Also 0 exklusiv oder 0 ist falsch, 1 exklusiv oder 1 ist falsch. 30:18.170 --> 30:21.430 Und das ist genau gerade das, was wir brauchen hier zum addieren. 30:22.850 --> 30:26.390 1 exklusiv oder 0 ist 1, kommt das Richtige raus. 30:27.070 --> 30:30.670 1 exklusiv oder 1 ist 0, kommt auch das Richtige raus. 30:30.670 --> 30:33.250 Das Einzige, was wir machen müssen ist, wir brauchen diesen 30:33.250 --> 30:36.630 Sonderfall, dass wenn ich 1 exklusiv oder 1 mache, dann brauche ich 30:36.630 --> 30:37.290 noch einen Übertrag. 30:37.570 --> 30:39.410 Da muss ich den Übertrag setzen. 30:40.390 --> 30:42.590 Das passiert jetzt beim nächsten Mal, da habe ich drei Einsen. 30:42.690 --> 30:47.890 Da habe ich erstmal 1 exklusiv oder 1 ist 0 und einen Übertrag und 30:47.890 --> 30:50.730 dann 0 exklusiv oder 1 ist 1. 30:51.330 --> 30:54.370 Und dann habe ich da noch den Übertrag stehen und irgendwas, was 0 30:54.370 --> 30:57.450 ist, dann habe ich 0 exklusiv oder 1 ist 1. 30:57.450 --> 31:04.930 Das heißt, wenn ich also im Binärsystem addieren möchte, dann ist das 31:04.930 --> 31:10.350 nichts anderes als eine exklusive Oder-Operation mit Übertrag, den ich 31:10.350 --> 31:12.830 behalten muss, wenn ich 1 exklusiv oder 1 mache. 31:12.830 --> 31:17.650 Das heißt, wenn Sie also jetzt in Hardware etwas gießen wollen, das 31:17.650 --> 31:22.730 addiert, sogenanntes Addierwerk, dann beschreiben Sie das mit einer 31:22.730 --> 31:27.630 bool'schen Funktion, die da heißt exklusiv oder und müssen noch einen 31:27.630 --> 31:29.750 Mechanismus haben für den Übertrag. 31:31.610 --> 31:35.110 Bei der Subtraktion ist das leider nicht mehr so schön. 31:35.110 --> 31:37.370 Da muss man sich was einfallen lassen. 31:38.650 --> 31:43.610 Insbesondere will man ja eigentlich nicht dann noch sich verdrängen, 31:43.810 --> 31:46.950 dass man irgendwie anders addiert, als man subtrahiert. 31:47.370 --> 31:50.990 Im Idealfall hätte man gerne, dass man genauso subtrahiert, wie man 31:50.990 --> 31:51.490 addiert. 31:52.470 --> 31:55.990 Und damit man das hinbekommt, muss man hinterher sich ein bisschen 31:55.990 --> 31:59.690 Gedanken darüber machen, wie stelle ich denn negative Zahlen dar. 32:00.590 --> 32:04.190 Weil eine Subtraktion als Addition ist die Addition mit einer 32:04.190 --> 32:04.970 negativen Zahl. 32:05.390 --> 32:08.630 Und wenn ich mich dann geschickt anstelle bei der Repräsentation 32:08.630 --> 32:14.550 negativer Zahlen, dann funktioniert das mit diesem Exklusiv-Oder immer 32:14.550 --> 32:14.870 noch. 32:15.850 --> 32:16.290 Ja? 32:24.200 --> 32:25.060 Ah, nee. 32:25.360 --> 32:27.200 Ah doch, da fehlt ein Punkt für den Übertrag. 32:31.060 --> 32:32.760 Wahrscheinlich beim Scannen verloren gegangen. 32:33.920 --> 32:35.100 Ja, das Ding ist ein bisschen älter. 32:35.320 --> 32:37.700 Das ist von 1649. 32:39.740 --> 32:41.380 Da waren die Scanner noch nicht so gut. 32:44.520 --> 32:49.860 Oder der Herr Leibniz war übermüdet und dem Kurfürsten ist es eh nicht 32:49.860 --> 32:50.440 aufgefallen. 32:51.840 --> 32:52.700 Aber stimmt schon. 32:52.860 --> 32:56.420 Also hier an der Stelle, da fehlt ein Punkt für den Übertrag. 32:56.920 --> 32:58.180 Jetzt zoomen wir mal rein. 32:58.900 --> 32:59.960 Oh, nee, funktioniert nicht. 33:02.700 --> 33:06.720 Der muss irgendwo, also 1 und 1 exklusiv 0 und da müsste hier noch ein 33:06.720 --> 33:09.360 Übertrag stehen, weil sonst passt es nicht, dass hier die 0 rauskommt. 33:11.400 --> 33:13.600 Hat vielleicht einer gedacht, das ist ein Fliegenschiss und hat ihn 33:13.600 --> 33:14.060 wegradiert. 33:14.720 --> 33:15.660 Kann auch passieren. 33:21.350 --> 33:22.070 Gut. 33:23.210 --> 33:30.730 Diese Darstellung mit zwei Zeichen aus dem Alphabet, die nennt man 33:30.730 --> 33:32.090 Binärdarstellung. 33:32.830 --> 33:36.250 Da verwenden wir also dieses Alphabet Z2, bestehend aus den Zahlen 0 33:36.250 --> 33:36.810 und 1. 33:37.550 --> 33:41.850 Und wir definieren uns diese kleinen Nummern von 2 eben gerade so, 33:42.030 --> 33:49.630 dass der Binärwert von dem Zeichen 0 gerade der Zahl 0 sein soll und 33:49.630 --> 33:53.410 dass der Binärwert von dem Zeichen 1 gerade dem Zeichen 1 sein soll. 33:54.090 --> 33:58.690 Und dann definieren wir wieder diesen großen Num von 2 vom leeren Wort 33:58.690 --> 33:59.290 als 0. 34:00.290 --> 34:04.290 Und ansonsten für jedes andere Wort über dem Alphabet und für jedes 34:04.290 --> 34:08.010 einzelne Zeichen, wenn das Wort halt die Form hat WX, dann ist das 34:08.010 --> 34:11.890 eben gleich zweimal Num 2 von W plus Num 2 von X. 34:13.450 --> 34:16.410 Dann kann man das jetzt wieder so machen, wenn ich da jetzt eine 34:16.410 --> 34:20.910 beliebige Zeichenfolge reingebe, also die Zeichenfolge 1 1 0 1, also 34:20.910 --> 34:24.770 das Wort 1 1 0 1 und ich das nach dieser induktiven Definition 34:24.770 --> 34:29.750 ausrechne, dann komme ich am Ende wieder bei dieser Kettendarstellung 34:29.750 --> 34:33.010 dran, wie wir sie ursprünglich bei der Überlegung hatten, dass das 34:33.010 --> 34:36.450 eben gerade rechtes Zeichen mal 2 hoch 0 ist, plus nächstes Zeichen 34:36.450 --> 34:40.870 mal 2 hoch 1, plus nächstes Zeichen mal 2 hoch 2, plus letztes Zeichen 34:40.870 --> 34:42.290 mal 2 hoch 3. 34:42.910 --> 34:46.770 Das heißt, auch da die induktive Definition macht auch genau das, was 34:46.770 --> 34:47.690 wir bitteschön wollen. 34:49.970 --> 34:56.050 Wichtig ist halt, dass man sich hier immer überlegt, was bedeuten das? 34:56.150 --> 35:00.450 Wir haben diese Zeichen in schwarz geschrieben, jetzt mal hier in rot 35:00.450 --> 35:01.350 gehighlighted. 35:01.350 --> 35:08.330 Die sehen zwar aus wie die Zeichen aus dem Alphabet, das ist aber 35:08.330 --> 35:14.550 nicht das Zeichen aus dem Alphabet, sondern das ist bereits der Wert 35:14.550 --> 35:18.370 von kleinen Nummer 2 von einer blau geschriebenen 1. 35:19.930 --> 35:26.310 Und genauso ist das andere hier auch logischerweise schon die Zahlen 35:26.310 --> 35:30.730 und das Ganze alles in Dezimalschreibweise hingeschrieben. 35:31.350 --> 35:34.490 Ich könnte das in jeder anderen beliebigen Schreibweise hinschreiben, 35:34.590 --> 35:35.710 es wird immer noch das Richtige herauskommen. 35:35.770 --> 35:39.610 Das Rechnen ist halt anders, die Zahlen sehen halt anders aus, das 35:39.610 --> 35:42.050 sind dann irgendwie andere Wörter, die ich da habe. 35:42.510 --> 35:47.410 Aber hier ganz wichtig, dass man weiß, hier hat man bereits die 35:47.410 --> 35:52.530 Funktion kleinen Nummer 2 von x angewandt und das hier ist sowieso 35:52.530 --> 35:57.310 eine Zahl in einer Darstellung und hier per Konvention immer die 35:57.310 --> 35:59.490 Dezimaldarstellung, wenn wir das Ganze so schreiben. 36:01.130 --> 36:03.050 Es gibt auch andere Darstellungen. 36:03.150 --> 36:05.970 Ich kann das auch zu einer anderen Basis machen. 36:06.090 --> 36:08.190 Ich kann zum Beispiel mit 16 Zeichen arbeiten. 36:08.930 --> 36:12.390 Wenn ich also das Alphabet Z16 habe, dann nennt man das die 36:12.390 --> 36:16.270 Hexadezimaldarstellung und jetzt hat man das Problem, man hat also die 36:16.270 --> 36:20.330 Zeichen 0 bis 9, die man auch so in der Dezimaldarstellung verwendet, 36:20.330 --> 36:23.770 aber ich brauche ja 16, da fehlen mir noch 6 Stück. 36:25.050 --> 36:28.430 Damit man jetzt halt nicht mit der Konkatenation in Probleme kommt, 36:28.530 --> 36:31.110 weil dann kann ich die Konkatenation nicht mehr auseinanderhalten, 36:31.410 --> 36:34.930 nimmt man dann eben nicht Symbole, die sozusagen aus zwei Ziffern, wie 36:34.930 --> 36:37.770 aus dem Z10 bestehen, sondern man braucht neue Zeichen. 36:38.790 --> 36:41.950 Man muss seine 16 vollkriegen und das kann man zum Beispiel machen, 36:41.990 --> 36:44.390 indem man dann Buchstaben aus dem lateinischen Alphabet gibt. 36:44.850 --> 36:47.090 Dann hat man hinten halt noch A, B, C, D, E, F. 36:48.050 --> 36:51.710 Wenn man das Ganze wieder macht und sich überlegt, für welche Zahlen 36:51.710 --> 36:57.810 sollen denn diese Zeichen stehen, dann macht man das halt so von 0 bis 36:57.810 --> 36:58.690 9. 36:58.950 --> 37:03.250 Die 0 ist halt für die 0, die 2 für die 2, die 9 für die 9 und dann 37:03.250 --> 37:04.330 macht man da hinten weiter. 37:04.750 --> 37:09.950 Dann sagt man halt, dass A ist halt in 10, dass B ist 11, C ist 12 und 37:09.950 --> 37:12.830 so weiter bis F soll eben für die Zahl 15 stehen. 37:12.830 --> 37:16.950 Und dann kann ich das wieder genau nach dem gleichen Prinzip induktiv 37:16.950 --> 37:17.650 definieren. 37:17.870 --> 37:22.190 Num 16 von Epsilon ist eben gleich 0 und für jedes Wort, das ich habe, 37:22.550 --> 37:26.190 mit einem Zeichen hintendran, das ist eben gerade das letzte Zeichen 37:26.190 --> 37:31.890 davon, kleinen Num 16 von dem letzten Zeichen plus 16 mal Num 16 von 37:31.890 --> 37:32.750 dem restlichen Wort. 37:33.250 --> 37:38.450 Und dann kommt eben raus, wenn ich sowas habe wie 20A, das ist halt A, 37:38.730 --> 37:47.030 hat Wert 10, ist also 10 mal 16 hoch 0, dann 0 mal 16 hoch 1, 2 mal 16 37:47.030 --> 37:47.570 hoch 2. 37:51.910 --> 37:54.750 Wieder da muss ich klar machen, hier hat man schon eine kleine Nummer 37:54.750 --> 37:58.670 angewandt, das ist sowieso eine Zahl im Dezimalsystem und so weiter. 38:00.830 --> 38:04.310 Das hat jetzt halt das kleine Problem, das wir schon gesehen haben, 38:04.450 --> 38:06.990 als wir Nachrichten und Informationen besprochen haben. 38:07.570 --> 38:12.770 Wenn ich jetzt so eine Zeichenfolge sehe, ein Wort, das über einem 38:12.770 --> 38:20.070 Alphabet dieser Form Z2, Z16, Z10 gebildet wurde, dann kann ich nicht 38:20.070 --> 38:23.290 notwendigerweise dem Wort ansehen, aus welchem Alphabet es denn 38:23.290 --> 38:23.910 gebildet wurde. 38:24.550 --> 38:29.770 Wenn ich dreimal die 1 habe, das kann sowohl nach binär Darstellung 38:29.770 --> 38:32.610 sein, das kann nach Dezimal Darstellung sein, das kann nach 16, 38:33.590 --> 38:36.730 Hexadezimal Darstellung sein, das kann nach Basis 8 sein, da kann ich 38:36.730 --> 38:40.310 genau das gleiche Spiel machen, Alphabet mit 8 Zeichen, dann wäre es 38:40.310 --> 38:41.890 zur Basis 8. 38:43.670 --> 38:45.770 Das kann ich nicht unterscheiden. 38:46.230 --> 38:48.230 Das ist eben gerade das Bezugssystem. 38:48.230 --> 38:51.470 Wir hatten gesagt, wenn wir eine Information interpretieren wollen, 38:51.570 --> 38:53.710 brauchen wir dazu ein Bezugssystem. 38:54.330 --> 38:57.430 Und wenn wir halt Bezugssystem und ursprüngliche Nachricht irgendwie 38:57.430 --> 39:00.150 geeignet abspeichern wollen, dann nennen wir das Ganze ein Datum. 39:00.670 --> 39:05.350 Und das macht man dann zum Beispiel, wenn man es hinschreiben will, 39:05.430 --> 39:07.150 mit solchen Präfixen. 39:07.250 --> 39:10.810 Wenn man also explizit machen will, und das ist per Konvention in 39:10.810 --> 39:14.030 manchen Programmiersprachen, wenn ich also explizit machen will, dass 39:14.030 --> 39:18.190 das, was kommt, die Zeichenfolge, die ich jetzt hinschreibe, eine Zahl 39:18.190 --> 39:22.090 in Binärdarstellung sein soll, dann gebe ich dem den Präfix 0B. 39:22.950 --> 39:26.490 Wenn ich will, dass das zur Basis 8 ist, also in Oktardarstellung, 39:26.870 --> 39:29.250 dann gebe ich ihm das Präfix O0. 39:29.690 --> 39:32.670 Und wenn ich es halt haben will als Hexadezimal, dann gebe ich ihm den 39:32.670 --> 39:33.790 Präfix 0X. 39:34.270 --> 39:36.810 Und wenn es keinen Präfix hat, dann gehe ich halt davon aus, dass es 39:36.810 --> 39:38.630 zum Beispiel zur Dezimaldarstellung ist. 39:38.630 --> 39:42.730 Das muss halt in einer Programmiersprache festgelegt werden, damit man 39:42.730 --> 39:47.370 weiß, die Wörter, die hinter der Programmierer hinschreibt, welche 39:47.370 --> 39:49.590 Semantik haben sie, welche Bedeutung haben sie. 39:50.830 --> 39:57.630 Das heißt, sowas ist im Prinzip ein minimales Beispiel für ein Datum. 39:58.710 --> 40:03.210 Ich habe mein Bezugssystem durch eine Nachricht codiert, eben durch 40:03.210 --> 40:07.810 die Nachricht 0B, 0O, 0X, und ich habe die Nachricht selber. 40:07.810 --> 40:12.050 Und anstatt es als Tupel zu schreiben, könnte genauso gut den 40:12.050 --> 40:16.110 Programmierer zwingen, Klammer auf, erst das Bezugssystem, Komma, dann 40:16.110 --> 40:19.950 das Wort, das die Zahl wahrstellt, hinzuschreiben, habe ich es einfach 40:19.950 --> 40:20.650 konkretisiert. 40:21.550 --> 40:24.490 Wenn wir es ordentlich machen, für uns ist ein Datum eigentlich immer 40:24.490 --> 40:27.750 ein Tupel, müsste man das, wenn man es richtig notiert, mit den runden 40:27.750 --> 40:30.930 Klammern und mit dem Komma schreiben, anstatt einfach die Wörter zu 40:30.930 --> 40:31.690 konkretisieren. 40:36.460 --> 40:42.300 Wie wir gesehen haben, diese Form der Definition des Zahlenwertes 40:42.300 --> 40:47.060 eines Wortes über so einem Alphabet ZI, das kann ich für jedes I 40:47.060 --> 40:50.080 machen, solange das I größer gleich 2 ist. 40:50.200 --> 40:54.180 Also solange ich mindestens zwei Zeichen im Alphabet habe, kann ich so 40:54.180 --> 40:58.620 induktiv diese Definition dieser großen Numm zu irgendeiner beliebigen 40:58.620 --> 41:00.340 Basis I hinschreiben. 41:01.920 --> 41:05.440 Wir haben uns eben schon so informell überlegt, wie sieht das aus mit 41:05.440 --> 41:07.300 Injektivität und Subjektivität. 41:08.040 --> 41:09.380 Wir wären aber gerne sicher. 41:09.720 --> 41:13.920 Wir hätten nicht nur gerne ein intuitives Gefühl, wie das aussieht, 41:14.000 --> 41:15.120 sondern wir wären gerne sicher. 41:15.120 --> 41:19.440 Und deswegen gibt es zwei Fragen, die wir beantworten müssen. 41:20.900 --> 41:29.120 Kann ich aus jedem hingeschriebenen Wort eine Zahl interpretieren, ist 41:29.120 --> 41:33.160 also zu jedem Wort die dargestellte Zahl definiert? 41:33.160 --> 41:38.800 Und umgekehrt, kann ich zu jeder Zahl, die ich gerne hinschreiben 41:38.800 --> 41:44.040 möchte, kann ich da ein Wort definieren, sodass Numm von dieser Zahl 41:44.040 --> 41:47.060 eben gerade den gewünschten Zahlenwert ergibt? 41:50.540 --> 41:53.400 Das eine nennen wir halt die KR-Darstellung. 41:53.660 --> 41:56.840 Das ist halt die Verallgemeinerung von Dezimaldarstellung, 41:56.980 --> 41:59.100 Binärdarstellung, Hexadezimaldarstellung. 42:01.060 --> 42:04.720 Wir nehmen uns jetzt eine beliebige Basis, zu der wir darstellen 42:04.720 --> 42:05.020 wollen. 42:05.020 --> 42:07.480 K aus der Null und K größer gleich zwei. 42:07.880 --> 42:11.780 Wir definieren dann, wir haben ein Alphabet ZK mit K-Ziffern. 42:11.920 --> 42:18.000 Wir haben für diese ZK-Ziffern diese Zuordnung Klein-Numm. 42:18.120 --> 42:22.100 Das heißt, für jedes Zeichen aus dem Alphabet haben wir eine Zahl 42:22.100 --> 42:26.160 zugeordnet, die gerade eben aus dieser Menge Z, diesmal doppelt 42:26.160 --> 42:27.320 gestrichen K, kommt. 42:27.320 --> 42:32.340 Das heißt, also aus der Menge der Zahlen Null bis Klein-K, K so viele 42:32.340 --> 42:33.440 Zeichen wie im Alphabet. 42:38.040 --> 42:43.180 Das können wir umgekehrt festlegen, indem wir jetzt sagen, vorher 42:43.180 --> 42:45.620 hatten wir gesagt, für den Zeichen haben wir mit dieser Abbildung 42:45.620 --> 42:47.680 Klein -Numm den Zahlenwert zugeordnet. 42:47.680 --> 42:49.460 Jetzt kann ich es auch umgekehrt machen. 42:49.620 --> 42:54.920 Ich kann für jeden Zahlenwert aus diesem ZK das Alphabetzeichen 42:54.920 --> 42:55.460 zuordnen. 42:55.660 --> 42:57.680 Das wäre sozusagen die inverse Abbildung. 42:58.960 --> 43:04.660 Und diese inverse Abbildung nenne ich dann Rep, die Repräsentation von 43:04.660 --> 43:04.860 K. 43:06.040 --> 43:15.600 Und jetzt muss man aufpassen bei der Definition. 43:15.720 --> 43:18.360 Und hier ist nämlich was auf der Folie, das gefällt mir nicht. 43:19.360 --> 43:23.760 Also wir hatten gesehen, okay, also nicht hier auf der Folie, aber wir 43:23.760 --> 43:25.740 müssen uns jetzt was überlegen, weil wir es nicht hingeschrieben 43:25.740 --> 43:25.940 haben. 43:25.940 --> 43:29.300 Also wir haben Groß-Numm-K und gesehen für die Zuordnung des 43:29.300 --> 43:30.960 Zahlenwertes eines komplexen Wortes. 43:31.000 --> 43:32.940 Wir suchen etwas, das ist Groß-Reprä-K. 43:33.280 --> 43:37.420 Das weist einer Zahl seine Repräsentation zu und das soll definiert 43:37.420 --> 43:39.720 sein für alle N Null. 43:41.200 --> 43:47.480 Dieses Klein-Numm, hatten wir gesagt, bildet ab von dem Alphabet ZI 43:47.480 --> 43:49.220 hin in die natürliche Zahl. 43:49.840 --> 43:52.040 Und wenn wir das so gemacht haben, dann war das Ganze eben nicht 43:52.040 --> 43:52.680 subjektiv. 43:53.880 --> 43:55.720 Das kann ich jetzt nicht umdrehen. 43:56.100 --> 43:58.960 Ich kann jetzt nicht sagen, Klein-Reprä-K bildet ab von den 43:58.960 --> 44:02.480 natürlichen Zahlen hin nach dem Alphabet ZK. 44:03.040 --> 44:03.820 Das geht nicht. 44:04.540 --> 44:05.160 Warum nicht? 44:13.940 --> 44:16.080 Die ist nicht eindeutig. 44:16.220 --> 44:18.980 Oder was ist das eigentliche Problem, wenn ich abbilde von den 44:18.980 --> 44:20.320 natürlichen Zahlen? 44:20.500 --> 44:21.500 Also das ist nicht das Problem. 44:22.220 --> 44:24.220 Eine Funktion muss nicht eindeutig sein. 44:25.100 --> 44:27.920 Eine eindeutige Funktion ist injektiv. 44:29.680 --> 44:30.680 Was ist eine Funktion? 44:30.880 --> 44:31.580 Was ist eine Abbildung? 44:31.940 --> 44:34.560 Definition einer Funktion, auch genannte Abbildung. 44:35.420 --> 44:43.660 Eine Relation, die muss sein, links total und rechts eindeutig. 44:44.140 --> 44:51.340 Wenn ich jetzt von N Null abbilde nach ZK, das Alphabet, was bin ich 44:51.340 --> 44:51.620 nicht? 44:52.500 --> 44:53.640 Nein, links total. 44:55.660 --> 44:59.960 Was will ich denn für die Zahl 16 abbilden? 45:00.580 --> 45:02.200 Darf ich nichts abbilden? 45:03.780 --> 45:06.660 Weil ich habe nur, wenn ich, sagen wir mal, eine Dezimaldarstellung 45:06.660 --> 45:06.980 habe. 45:07.220 --> 45:12.200 Ich habe zehn Zeichen und will jetzt bei Klein-Reprä-K abbilden zu 45:12.200 --> 45:13.000 diesen zehn Zeichen. 45:13.100 --> 45:15.380 Und das kriege ich als Zahl aus den natürlichen Zahlen 16. 45:17.720 --> 45:20.240 Da darf ich nichts abbilden, sonst funktioniert das hinterher nicht. 45:20.420 --> 45:22.500 Sonst funktioniert die Invertierung nicht mehr. 45:22.500 --> 45:25.720 Das heißt, ich darf also nicht von den natürlichen Zahlen als 45:25.720 --> 45:30.280 Definitionsbereich abbilden bei dem kleinen Reprä-K, sondern ich darf 45:30.280 --> 45:33.940 eben nur von dem doppelt gestrichenen ZK abbilden. 45:34.480 --> 45:37.160 Das muss jetzt an dieser Stelle mein Definitionsbereich sein. 45:37.280 --> 45:40.920 Da muss ich den Definitionsbereich darauf einschränken, damit ich 45:40.920 --> 45:43.840 hinterher was bekomme, was eine Abbildung ist und auch so definiert 45:43.840 --> 45:44.780 ist, wie ich es gerne hätte. 45:46.320 --> 45:46.880 Klar. 45:47.860 --> 45:52.080 Irgendwem nicht klar, worüber wir hier gerade geschwafelt haben. 45:56.670 --> 45:58.490 Wie ist das mit dem leeren Wort? 45:59.910 --> 46:03.370 Leere Wort wird da ja gar nicht abgebildet. 46:03.910 --> 46:07.330 Also eine Abbildung, wir gehen ja von den Zahlen zu den Zeichen. 46:07.450 --> 46:10.310 Das leere Wort ist in der Menge der Zeichen nicht enthalten. 46:10.450 --> 46:15.770 Das Alphabet ZK enthält K-Zeichen, aber nicht das leere Wort. 46:16.750 --> 46:20.790 Ein Alphabet kann ein leeres Wort enthalten, in unserem Fall machen 46:20.790 --> 46:21.590 wir das aber nicht so. 46:21.650 --> 46:25.390 Wir hätten gerne ein Alphabet ZK mit K-Symbolen, die nennen wir 46:25.390 --> 46:25.950 Ziffern. 46:26.310 --> 46:28.010 Und das leere Wort ist eben keine Ziffer. 46:28.870 --> 46:31.950 Das leere Wort ist aber durchaus ein Wort, das über Ziffern gebildet 46:31.950 --> 46:32.190 wurde. 46:32.410 --> 46:32.970 Das ist halt leer. 46:32.970 --> 46:37.290 Und wird dann halt entsprechend in dieser induktiven Definition von 46:37.290 --> 46:40.930 der Groß-NUMKA-Abbildung abgedeckt. 46:41.670 --> 46:48.050 Genauso kann es sein im Zielbereich der Groß-Reprika, aber es hat eben 46:48.050 --> 46:51.610 keine Bedeutung bei den Klein-NUMKA oder bei den Klein-Reprika 46:51.610 --> 46:53.430 -Definitionen. 46:54.470 --> 47:00.050 Okay, also wir suchen jetzt dieses Groß-Reprika basierend auf diesem 47:00.050 --> 47:02.030 Klein -Reprika, das wir gesehen hatten. 47:02.130 --> 47:06.470 Und wir wollen jede beliebige natürliche Zahl, wollen wir ein Wort 47:06.470 --> 47:07.310 zuweisen. 47:11.190 --> 47:16.690 Und zwar möchten wir das so gerne haben, dass ja diese Repräsentation 47:16.690 --> 47:22.170 von K von der Zahl, wenn ich da mit Hilfe von Groß-NUMKA wieder 47:22.170 --> 47:25.890 zurückrechne die Bedeutung dieser Repräsentation, dann soll eben 47:25.890 --> 47:29.910 gerade wieder die Zahl, die ich vorher mit Reprika enkodiert habe, 47:29.970 --> 47:32.670 hingeschrieben habe, soll eben gerade wieder diese gleiche Bedeutung 47:32.670 --> 47:32.950 haben. 47:34.870 --> 47:38.170 Wie gesagt, man redet jetzt halt, wenn man solche Sachen hat, von 47:38.170 --> 47:42.530 Binärdarstellung, wenn K gleich 2 ist, von Ternärdarstellung, falls K 47:42.530 --> 47:43.350 gleich 3 ist. 47:43.750 --> 47:45.670 Wenn K gleich 8 ist, ist es die Oktal. 47:45.950 --> 47:48.350 Und wenn K gleich 16 ist, ist es die Hexadezimal. 47:49.990 --> 47:56.150 Und mehr griechische und lateinische Zahlen kann ich leider nicht 47:56.150 --> 47:58.870 mehr, als dass ich jetzt sagen könnte, wie es für K gleich 4 ist. 47:58.930 --> 48:02.510 Das ist wahrscheinlich Quartier, aber K gleich 5 hört man Latein schon 48:02.510 --> 48:02.850 auf. 48:07.010 --> 48:13.330 Damit wir jetzt diese Funktion Groß-Reprika vernünftig darstellen 48:13.330 --> 48:18.070 können, brauchen wir noch zwei Operationen, die nicht unbedingt ganz 48:18.070 --> 48:18.930 so geläufig sind. 48:19.090 --> 48:23.690 Für NUMKA hatten wir halt diese Exponenten, immer 10 hoch 0, 10 hoch 48:23.690 --> 48:24.530 1, 10 hoch 2. 48:24.530 --> 48:26.690 Das gehen wir auch davon aus, dass Sie wissen, was das ist. 48:27.270 --> 48:30.850 Das hier gehen wir jetzt mal nicht von aus, sondern definieren sie 48:30.850 --> 48:31.130 uns. 48:31.270 --> 48:35.370 Wir haben einmal die Operation LIV und einmal die Operation MOD oder 48:35.370 --> 48:37.790 ausgesprochen DIVISION und MODULO. 48:38.650 --> 48:43.050 Wenn ich eine Zahl aus den natürlichen Zahlen habe, x, und eine Zahl 48:43.050 --> 48:48.270 aus den positiven natürlichen Zahlen, also nicht 0, y, dann kann ich 48:48.270 --> 48:54.350 den Modulo von x mit y ausrechnen, x Modulo y und das soll eben gerade 48:54.350 --> 48:58.950 der Rest sein, der bei der ganzzahligen Division von x durch y 48:58.950 --> 48:59.590 rauskommt. 49:00.190 --> 49:06.950 Wenn ich also x durch y mit Rest teile, also den Rest übrig lasse, 49:07.050 --> 49:09.810 ganzzahlige Divisionen dürfen nur ganze Zahlen rauskommen und es 49:09.810 --> 49:12.590 bleibt halt ein Rest übrig, dann ist dieser Rest eben gerade der 49:12.590 --> 49:12.990 Modulo. 49:12.990 --> 49:16.290 Man kann sich dann überlegen, der Rest muss dann halt entsprechend 49:16.290 --> 49:20.470 größer gleich 0 sein, aber er muss echt kleiner sein, diesem y, weil 49:20.470 --> 49:23.710 sonst hätte ich ja das y nochmal da teilen können, sozusagen 49:23.710 --> 49:24.570 rausteilen können. 49:24.570 --> 49:34.010 Und umgekehrt, die ganzzahlige Division ohne Rest ist eben dieses x 49:34.010 --> 49:40.830 div y und dementsprechend gilt halt, dass wenn ich beliebiges x habe 49:40.830 --> 49:45.390 und beliebiges positives y aus den natürlichen Zahlen, dass ich x dann 49:45.390 --> 49:52.250 immer darstellen kann als y mal x div y plus x Modulo y. 49:54.010 --> 49:58.530 Einfaches Beispiel, 6 ganzzahlig geteilt durch 2 ist 3, der Rest bei 49:58.530 --> 50:06.030 der Division ist 0, dementsprechend ist eben 2 mal 3 plus 0 wieder 6. 50:06.690 --> 50:12.410 7 ganzzahlig geteilt durch 2 ist eben 3, Rest 1, dementsprechend ist 50:12.410 --> 50:17.830 dann wieder 2 mal 3 plus 1 7 und so weiter und so fort. 50:19.390 --> 50:24.990 Und mit diesen beiden Operatoren kann ich jetzt diese k-äre 50:24.990 --> 50:27.610 Darstellung definieren. 50:28.670 --> 50:32.750 Definieren wir jetzt also diese Abbildung, Reprekar, die bildet ab. 50:35.280 --> 50:35.960 Oh, da ist ein Fehler. 50:37.460 --> 50:40.980 Die müsste mich abbilden von N0 nach ZK Sternchen. 50:41.100 --> 50:42.340 Wer hat mir letztes Mal eine E-Mail geschrieben? 50:42.800 --> 50:43.640 Ein Empfehler. 50:43.800 --> 50:44.280 Wer war das? 50:45.220 --> 50:49.880 Schreibt mir bitte wieder eine E-Mail, Folie 16, dass ich das Ganze 50:49.880 --> 50:51.840 bitte schön korrigiere. 50:53.800 --> 50:55.860 Da kann man zehnmal drauf gucken, man sieht es nicht. 50:56.700 --> 51:01.040 Hier, da oben, da muss halt nach ZK Stern entsprechend abgebildet 51:01.040 --> 51:01.260 werden. 51:01.260 --> 51:05.540 Und dann brauchen wir, also Ziel- und Definitionsbereich haben wir, 51:05.600 --> 51:07.240 jetzt brauchen wir noch eine Abbildungsvorschrift. 51:07.660 --> 51:13.400 Jede natürliche Zahl N wird jetzt eben abgebildet, entweder auf kleine 51:13.400 --> 51:19.320 Reprekar von N, nämlich dann, wenn sie kleiner ist als diesem K, also 51:19.320 --> 51:24.200 wenn es ein einzelnes Zeichen gibt aus dem Alphabet, das für den 51:24.200 --> 51:25.600 Zahlenwert N steht. 51:27.500 --> 51:32.820 Oder ich muss es, wenn es größer ist, konkatenieren aus zwei Wörtern. 51:34.160 --> 51:40.680 Nämlich einmal ganz rechts schreibe ich in den Modulo, wenn ich die 51:40.680 --> 51:46.860 Zahl N durch K teile und links davon schreibe ich halt hin Reprekar 51:46.860 --> 51:48.900 von N Div K. 51:49.660 --> 51:55.100 Das heißt, ich habe hier wieder eine induktive Definition in einer 51:55.100 --> 51:56.060 gewissen Art und Weise. 51:57.340 --> 52:01.140 Alternativ kann man es halt auch so schreiben, dann ist es nämlich 52:01.140 --> 52:07.280 schöner, wenn ich das nach rechts hin rocke, dann sieht man schön, 52:07.440 --> 52:10.680 dass die Stellen, die ich hinterher in den Wörtern habe, wenn ich die 52:10.680 --> 52:13.560 durchnummeriere, die Position, wie das bei Wörtern so ist, dann 52:13.560 --> 52:16.300 stimmen die halt schön miteinander überein und das Wort wächst 52:16.300 --> 52:17.700 sozusagen nach links heraus. 52:18.900 --> 52:21.780 Das hatten wir schon gesagt, wenn Sie eine Definition sehen, eine 52:21.780 --> 52:25.760 Abbildung, müssen Sie als Übung und immer um sicher zu sein, dass der 52:25.760 --> 52:28.800 Kollege wie ich zum Beispiel keinen missbaut, das Ganze abklopfen. 52:29.300 --> 52:32.520 Und Sie hätten jetzt schon als erstes gesehen, oh, oh, oh, oh, 52:32.980 --> 52:35.280 Definitionen zum Zielbereich stimmen schon mal nicht. 52:35.460 --> 52:37.040 Das ist schon mal ganz böse. 52:37.800 --> 52:40.120 Abzug in der Klausur, Punktabzug in der Klausur. 52:42.640 --> 52:46.680 Was ist mit der Abbildungsvorschrift? 52:47.100 --> 52:47.820 Reicht die aus? 52:49.060 --> 52:52.080 Gut, die Frage ist, ist das Ganze sinnvoll? 52:52.540 --> 52:58.300 Und sinnvoll ist das Ganze dann, wenn für jedes N aus N0 dieses 52:58.300 --> 53:00.840 Großreplika auch definiert ist. 53:00.960 --> 53:03.520 Denn eine Abbildung muss linkstotal sein. 53:03.980 --> 53:07.680 Wenn das Ding nicht linkstotal ist, dann ist es keine Abbildung, dann 53:07.680 --> 53:09.160 ist die Definition Mist. 53:09.160 --> 53:13.480 Also müssen wir zeigen, dass für jede natürliche Zahl diese Abbildung 53:13.480 --> 53:15.100 bitteschön auch definiert ist. 53:18.860 --> 53:25.280 Behauptung, wenn wir ein positives M aus N plus haben, dann gilt für 53:25.280 --> 53:32.120 jedes N minus aus den natürlichen Zahlen mit N kleiner K hoch M ist 53:32.120 --> 53:34.500 Replika von N definiert. 53:36.020 --> 53:41.460 Das können wir mithilfe vollständiger Induktion beweisen. 53:45.600 --> 53:50.340 Denn ich habe hier dieses M, das kann ich laufen lassen, das kann ich 53:50.340 --> 53:56.120 loslaufen lassen von Null und wenn ich für jedes M aus den natürlichen 53:56.120 --> 54:02.600 Zahlen zeige, dass das gilt, dann ist offensichtlich auch für jedes N 54:02.600 --> 54:05.320 aus den natürlichen Zahlen Replika von N definiert. 54:06.340 --> 54:09.340 Das kann man so ansehen, das ist so ein bisschen so ein Spezialfall, 54:09.400 --> 54:12.180 den wir bei der induktiven Definition und dem induktiven Beweisen 54:12.180 --> 54:13.560 dargestellt haben. 54:13.760 --> 54:17.160 So ein bisschen der Spezialfall, wenn wir etwas in einem Schema 54:17.160 --> 54:17.820 treffen sollen. 54:18.820 --> 54:20.420 Also, wir wollen das behaupten. 54:20.500 --> 54:26.760 Wir behaupten, das ist, dass für jedes N kleiner K hoch M mit M 54:26.760 --> 54:31.940 natürliche Zahl und K halt das Ding da, zu dem wir Replika definiert 54:31.940 --> 54:36.000 haben, also K großer gleich zwei, dass dann Replika definiert ist. 54:37.120 --> 54:43.380 Induktionsanfang M gleich eins, also N kleiner K. 54:44.700 --> 54:45.900 Alles in Ordnung. 54:48.440 --> 54:49.160 Induktionsschritt. 54:51.120 --> 54:56.580 Wir haben so ein M und es gilt die Induktionsvoraussetzung für jedes N 54:56.580 --> 55:01.400 Null beliebiges, aber festes N Element Null mit N kleiner K hoch M ist 55:01.400 --> 55:03.040 Replika von N definiert. 55:04.340 --> 55:07.120 Also der Induktionsanfang ist jedem klar, oder? 55:07.480 --> 55:11.960 M gleich eins, dann ist N kleiner K und wenn ein kleiner K ist, dann 55:11.960 --> 55:16.600 bin ich in dem oberen Zweig der Abbildungsvorschrift und dann ist es 55:16.600 --> 55:19.240 definiert, weil Replika ist selber eine Abbildung. 55:20.980 --> 55:23.800 Also Replika hat man bewiesen, dass das eine Abbildung ist, oder man 55:23.800 --> 55:26.100 sieht, dass es eine Abbildung ist, also muss das auch für M gleich 55:26.100 --> 55:31.080 eins gelten, weil für M gleich eins nämlich mal kleine Replika und 55:31.080 --> 55:31.820 alles in Ordnung. 55:32.900 --> 55:33.300 Induktionsschritt. 55:33.540 --> 55:34.940 Jetzt ist das nicht mehr unbedingt so. 55:35.660 --> 55:38.320 Ich habe also ein N, M plus und es gelte diese 55:38.320 --> 55:39.740 Induktionsvoraussetzung. 55:40.440 --> 55:42.340 Wie sieht es jetzt aus mit M plus eins? 55:42.340 --> 55:46.120 Das heißt, wir zeigen jetzt für jedes N aus den natürlichen Zahlen mit 55:46.120 --> 55:50.900 N kleiner K, M plus eins, das Replika von N auch definiert ist und 55:50.900 --> 55:55.200 greifen dabei zurück auf die Tatsache, dass Replika von N für jedes N 55:55.200 --> 55:56.960 kleiner K hoch M definiert ist. 55:59.240 --> 56:04.200 Falls dieses N, das ich mir hernehme, kleiner K hoch M ist, alles in 56:04.200 --> 56:06.120 Ordnung, Induktionsvoraussetzung greift. 56:06.900 --> 56:11.820 Falls dieses K hoch M eben nicht, also das N nicht kleiner K hoch M 56:11.820 --> 56:15.840 ist, also wenn es echt größer gleich K hoch M ist oder echt kleiner K 56:15.840 --> 56:23.520 hoch M plus eins, dann ist aber immerhin N div K, also N ganzteilig 56:23.520 --> 56:26.840 geteilt durch K, kleiner K hoch M. 56:29.040 --> 56:32.280 Eigenschaften kann man sich gleich klar machen, wenn man also durch 56:32.280 --> 56:38.280 Definitionen der ganzteiligen Division, wenn ich da so eine Zahl habe, 56:38.560 --> 56:43.480 die größer gleich K hoch M ist und kleiner K hoch M plus eins, wenn 56:43.480 --> 56:48.580 ich die durch K zeile, dann wird das Ganze eben M plus eins durch K 56:48.580 --> 56:49.920 geteilt, ist halt K hoch M. 56:49.920 --> 56:54.620 Dann ist also diese Zahl auch echt kleiner, also N dividiert durch K 56:54.620 --> 56:55.800 echt kleiner K hoch M. 56:56.740 --> 57:04.820 Also nach Induktionsvoraussetzung ist Replika von N div K definiert. 57:07.660 --> 57:10.460 Das ist ja der zweite Fall, in dem ich mich befinde bei der 57:10.460 --> 57:11.180 Abbildungsvorschrift. 57:11.540 --> 57:15.900 Da verwende ich ja in Rekursiv Induktiv dieses Replika von N div K. 57:16.400 --> 57:20.200 Das ist definiert und wird dann konkretisiert mit kleinen Replika von 57:20.200 --> 57:22.460 K und kleinen Replika von K ist eine Abbildung, ist also auch 57:22.460 --> 57:22.900 definiert. 57:22.900 --> 57:27.400 Also ist auch der zweite, greift dann dieser zweite Ast in der 57:27.400 --> 57:30.920 Fallunterscheidung bei der Abbildungsvorschrift und das Ganze ist 57:30.920 --> 57:31.480 definiert. 57:32.620 --> 57:38.640 Somit ist also nach vollständiger Induktion definiert oder gezeigt, 57:38.820 --> 57:42.960 dass Replika, Großreplika überall definiert ist. 57:44.380 --> 57:47.600 Und jetzt wollen wir uns überlegen, macht das das, was es soll? 57:47.960 --> 57:52.840 Also die zweite Sache war beim Untersuchen, Abklopfen einer 57:52.840 --> 57:53.460 Definition. 57:53.840 --> 57:54.920 Ist es links total? 57:55.040 --> 57:56.000 Ist es überall definiert? 57:56.700 --> 57:59.060 Und macht es denn auch das, was es machen soll? 58:00.200 --> 58:03.360 Und das, was es machen soll, ist eben gerade das, was wir schon gesagt 58:03.360 --> 58:03.640 haben. 58:03.740 --> 58:07.260 Ich habe also eine Zahl, aus der mache ich ein Wort über diesem 58:07.260 --> 58:11.420 Alphabetzettuch K und das Wort soll eben gerade der Gestalt sein. 58:12.140 --> 58:15.760 Wenn ich auf dieses Wort wieder Großnum von K anwende, dann soll eben 58:15.760 --> 58:19.400 wieder die ursprüngliche Zahl herauskommen. 58:20.260 --> 58:23.900 Also das ist gerade dieses Lemma, das sagt, für jede natürliche Zahl 58:23.900 --> 58:30.180 M0 soll eben gerade sein Großnum von K von Großreplika von N und das 58:30.180 --> 58:31.260 gerade wieder N. 58:33.700 --> 58:36.840 Wichtig hier nochmal diese Überlegung zur Injektivität. 58:37.780 --> 58:41.820 Umgekehrt ist das nicht notwendigerweise so, wegen der führenden Null. 58:42.820 --> 58:44.900 Aber das haben wir auch nicht verlangt. 58:56.270 --> 58:59.170 Ja, müsste es? 59:09.400 --> 59:23.280 Nein, also das Repre produziert zwar nicht 59:26.380 --> 59:28.260 Zahlen mit führenden Nullen. 59:29.120 --> 59:34.660 Ich kann aber ein Wort hinschreiben über diesem Alphabet einfach ZK 59:34.660 --> 59:36.480 mit führenden Nullen. 59:37.660 --> 59:41.280 Das kann ich reinstecken in die Num-Funktion. 59:41.940 --> 59:44.040 Das habe ich nicht mit Repre erzeugt, das habe ich einfach 59:44.040 --> 59:45.100 hingeschrieben. 59:45.620 --> 59:51.780 Das stecke ich rein in die Num, kriege die Zahl raus und dann wird die 59:51.780 --> 59:55.980 wieder mit Repre erzeugt und das macht eben keine führenden Nullen. 59:55.980 --> 59:59.740 Und daraus ergibt sich dann eben das, dass einem gerade die 59:59.740 --> 01:00:03.940 Repräsentation des Zahlenwertes eines beliebigen Wortes über diesem 01:00:03.940 --> 01:00:08.920 Alphabet ZK eben nicht notwendigerweise der Repräsentation seines 01:00:08.920 --> 01:00:09.900 Zahlenwertes ist. 01:00:10.900 --> 01:00:15.760 Dementsprechend ist halt Repre auch nicht sujektiv. 01:00:16.440 --> 01:00:20.640 Repre ist nicht sujektiv, es erzeugt keine Zahlen mit führenden 01:00:20.640 --> 01:00:20.900 Nullen. 01:00:23.140 --> 01:00:24.480 Beantwortet das die Frage? 01:00:28.100 --> 01:00:29.580 Das muss man sich klar machen. 01:00:29.840 --> 01:00:31.940 Also Repre ist nicht sujektiv. 01:00:32.040 --> 01:00:34.760 Es erzeugt keine Zahlen mit führenden Nullen von der Art und Weise 01:00:34.760 --> 01:00:35.840 her, wie es aufgebaut ist. 01:00:36.160 --> 01:00:42.500 Das sind aber durchaus gültige Darstellungen zu einer Basis. 01:00:42.980 --> 01:00:45.680 Dem kann ich auch einen Zahlenwert zuordnen, nur wenn ich halt von 01:00:45.680 --> 01:00:48.040 diesem Zahlenwert, dem es zugeordnet ist, wieder die Repräsentation 01:00:48.040 --> 01:00:49.780 rechne, kriege ich ein anderes Wort raus. 01:00:52.100 --> 01:00:54.020 Das kann ich auch beweisen. 01:00:54.800 --> 01:00:57.960 Genauso mit vollständiger Induktion wie eben. 01:00:59.540 --> 01:01:03.000 Also für jedes N aus N Null ist NumKarRepreKar von N gleich N. 01:01:03.920 --> 01:01:08.140 Induktionsanfang für N Element N Null mit N kleiner K passt alles. 01:01:08.600 --> 01:01:12.800 Wegen eben der Definition von kleinen RepreKar und kleinen Num von K. 01:01:14.520 --> 01:01:14.960 Induktionsschritt. 01:01:15.040 --> 01:01:19.360 Wir haben jetzt wieder ein M Element positiven natürlichen Zahlen. 01:01:20.360 --> 01:01:25.040 Unter dem Induktionsschritt für jedes N aus den natürlichen Zahlen mit 01:01:25.040 --> 01:01:30.060 N kleiner K hoch M ist NumKar von RepreKar von N gleich N. 01:01:30.260 --> 01:01:32.280 Das ist unsere Induktionsvoraussetzung. 01:01:32.280 --> 01:01:35.700 Wir müssen jetzt zeigen, dass wenn diese Induktionsvoraussetzung gilt, 01:01:35.820 --> 01:01:42.740 dann auch für jedes beliebige N mit N kleiner K hoch M plus 1 auch 01:01:42.740 --> 01:01:46.900 diese Eigenschaften hat, dass der Zahlenwert, der Repräsentation der 01:01:46.900 --> 01:01:51.080 Zahl gerade wieder gleich dem Zahlenwert ist. 01:01:51.840 --> 01:01:57.280 Also für jedes beliebige N müssen wir zeigen, falls N kleiner K hoch M 01:01:57.280 --> 01:02:00.400 ist, bleibt die Induktionsvoraussetzung schon von vornherein. 01:02:00.500 --> 01:02:01.200 Alles in Ordnung. 01:02:01.800 --> 01:02:06.620 Falls dieses N wieder zwischen K hoch M und K hoch M plus 1 ist, dann 01:02:06.620 --> 01:02:08.680 ist N div K kleiner K hoch M. 01:02:09.880 --> 01:02:14.400 Also gilt die Induktionsvoraussetzung und wir müssen das Ganze jetzt 01:02:14.400 --> 01:02:14.860 zerlegen. 01:02:14.860 --> 01:02:16.280 Wir müssen jetzt gucken. 01:02:17.880 --> 01:02:20.340 NumKar von RepreKar von N dividiert durch K. 01:02:20.500 --> 01:02:25.520 Das ist nach der Induktionsvoraussetzung gleich N div K. 01:02:27.200 --> 01:02:34.420 Wenn ich da die Induktionsvoraussetzung da oben reinsetze, weil 01:02:34.420 --> 01:02:38.340 RepreKar von N div K ist eben N div K und der NumKar von N div K ist 01:02:38.340 --> 01:02:39.320 logischerweise N div. 01:02:42.160 --> 01:02:45.460 Also die Repräsentation von N div K hat eben gerade den Zahlenwert N 01:02:45.460 --> 01:02:49.120 div K und welche Zahlenwert davon ausrechnet, ist das eben gerade N 01:02:49.120 --> 01:02:49.480 div K. 01:02:50.460 --> 01:02:55.000 Das heißt also, dass NumKar von RepreKar von N und jetzt setze ich das 01:02:55.000 --> 01:02:58.640 ein, was ich vorhin weiß, dass ich so eine Zahl N halt darstellen kann 01:02:58.640 --> 01:03:00.980 als K mal N div K plus N mod K. 01:03:01.720 --> 01:03:06.200 Davon die Repräsentation ist gemäß der Definition der Repräsentation 01:03:06.200 --> 01:03:11.540 eben RepreKar von N div K konkateniert mit RepreKlein RepreKar von N 01:03:11.540 --> 01:03:16.180 mod K und das ist dann eben gerade nach der Definition von NumKar K 01:03:16.180 --> 01:03:22.340 mal NumKar von Repre von N div K plus Klein NumKar von Repre von N mod 01:03:22.340 --> 01:03:22.520 K. 01:03:22.520 --> 01:03:27.500 Das löse ich wieder von innen nach außen auf, ist also nach 01:03:27.500 --> 01:03:31.620 Induktionsvoraussetzung, weil dieses RepreKar von N div K und da von 01:03:31.620 --> 01:03:35.680 NumKar ist gerade N div K, dann steht da eben gerade wieder K N div K 01:03:35.680 --> 01:03:40.060 plus N mod K und das ist eben gerade wieder gleich der Eigenschaft bei 01:03:40.060 --> 01:03:43.800 diesen Modulo-Sachen, das ist eben gerade wieder gleich N. 01:03:44.520 --> 01:03:48.080 Also durch einfaches Rechnen und von innen nach außen wieder auflösen 01:03:48.080 --> 01:03:53.420 und durch dieses Induktionsschritt dadurch machen, dass ich diese 01:03:53.420 --> 01:03:59.460 Eigenschaft habe, dass ich jede Zahl darstellen kann als mit 01:03:59.460 --> 01:04:02.780 irgendeiner Beliebung, dass ich es durch eine positive Zahl K teile, 01:04:02.900 --> 01:04:07.040 mehr die Division plus den Rest nehme, dass das gerade wieder die Zahl 01:04:07.040 --> 01:04:07.400 ist. 01:04:09.200 --> 01:04:17.720 Hier muss man halt aufpassen, hier innen drin, hier mache ich 01:04:17.720 --> 01:04:22.240 arithmetische Operationen, hier außen, wenn ich mit RepreKar arbeite, 01:04:23.020 --> 01:04:26.120 mache ich hier innerhalb der Klammern Konkatenationen von Wörtern. 01:04:27.120 --> 01:04:33.560 Und dementsprechend hier innen drin numerisch, dann RepreKar, bin ich 01:04:33.560 --> 01:04:37.200 bei einem Wort, dann NumKar, bin ich wieder numerisch und kann das 01:04:37.200 --> 01:04:38.480 dann wieder entsprechend addieren. 01:04:38.620 --> 01:04:43.120 Genauso hier, N mod K RepreKar ist ein Wort, das kommt nach NumKar 01:04:43.120 --> 01:04:45.900 rein, ist wieder eine Zahl, kann ich wieder addieren. 01:04:46.820 --> 01:04:50.220 Man muss also aufpassen, dass man da nicht irgendwie einen Fehler 01:04:50.220 --> 01:04:53.580 macht, sich verschreibt oder nicht aufpasst, dass plötzlich der 01:04:53.580 --> 01:04:58.840 Definitionsbereich, was ich da in die Funktion reintue oder das Ding, 01:04:58.940 --> 01:05:02.020 was ich in die Funktion reintue, eben nicht im Definitionsbereich der 01:05:02.020 --> 01:05:02.640 Funktion ist. 01:05:02.640 --> 01:05:05.500 Dass ich also das eine wirklich nur auf Wörter und das andere wirklich 01:05:05.500 --> 01:05:08.680 nur auf Zahlen anwende und dass, wenn ich irgendwo was addiere, dass 01:05:08.680 --> 01:05:10.040 ich auch bitteschön Zahlen addiere. 01:05:12.460 --> 01:05:16.700 Alles, was wir bisher gemacht haben, gilt nur für positive Zahlen. 01:05:18.760 --> 01:05:22.020 Und dann ist man irgendwann auf die Idee gekommen, ja was ist denn, 01:05:22.200 --> 01:05:24.260 wenn ich negative Zahlen repräsentieren will. 01:05:24.260 --> 01:05:28.960 Das ist jetzt in dieser Leibnizschen Darstellung noch nicht der Fall. 01:05:29.680 --> 01:05:34.700 Wir haben das erstmal gezeigt für natürliche Zahlen, die sind per se 01:05:34.700 --> 01:05:37.840 null oder positiv, aber nicht für negative Zahlen. 01:05:38.720 --> 01:05:42.400 Und da gibt es durchaus unterschiedliche Wege, das zu machen. 01:05:43.860 --> 01:05:49.360 Und ein Weg ist der hier, der ist der unübliche Weg, aber er 01:05:49.360 --> 01:05:50.100 funktioniert. 01:05:50.820 --> 01:05:52.980 Man könnte das problemlos so machen. 01:05:53.820 --> 01:05:57.560 Das ist dieser Weg mithilfe dieses Meins. 01:05:58.440 --> 01:06:02.040 Und dafür definiere ich mir eine Ziffermenge, die hat drei Zeichen. 01:06:03.200 --> 01:06:08.420 Ich habe 0, 1 und das Zeichen, diese umgekehrte 1, die nennt man in 01:06:08.420 --> 01:06:09.260 der Regel Meins. 01:06:10.260 --> 01:06:16.680 Und jetzt definiere ich den Zahlenwert dieser Ziffern und das ist 01:06:16.680 --> 01:06:17.940 jetzt kein NumKa mehr. 01:06:18.200 --> 01:06:23.640 Das NumKa war für diese positiven Zahlen mit K-Zeichen, sondern das 01:06:23.640 --> 01:06:24.400 ist jetzt eine andere. 01:06:24.400 --> 01:06:28.020 Deswegen das Alphabet ist nur noch Z und ich definiere jetzt eine 01:06:28.020 --> 01:06:32.900 Abbildung Num, die von diesem Z auf die ganzen Zahlen abbildet, 01:06:32.960 --> 01:06:37.460 positive wie negative, und die sagt, dass Meins steht für minus 1, die 01:06:37.460 --> 01:06:39.880 0 für 0 und die 1 für 1. 01:06:40.540 --> 01:06:45.060 Und jetzt definiere ich mir die Großabbildung Num, die also beliebigen 01:06:45.060 --> 01:06:49.540 Wörter hat, den Zahlenwert, positive oder negative Zahlen usw., wie 01:06:49.540 --> 01:06:49.840 gehabt. 01:06:50.460 --> 01:06:55.560 Ich sage, der Zahlenwert des leeren Wortes ist gleich 0 und ansonsten 01:06:55.560 --> 01:07:00.580 habe ich ein Wort, WX, das letzte Zeichen wird abgespalten, kommt in 01:07:00.580 --> 01:07:04.600 NumX rein und der Rest ist halt dreimal Num von W. 01:07:05.460 --> 01:07:10.960 Das ist letztendlich die gleiche Definition wie bei dem Z3 für die 01:07:10.960 --> 01:07:14.500 positiven Zahlen, nur jetzt ist es so, dass plötzlich eines der 01:07:14.500 --> 01:07:20.320 Zeichen in dem Z negativen Wert hat und das Ganze funktioniert immer 01:07:20.320 --> 01:07:20.620 noch. 01:07:22.080 --> 01:07:25.880 Und das sieht man halt, wenn man das mal beispielsweise macht, Meins 0 01:07:25.880 --> 01:07:31.420 1, das ist halt gleich minus 3 hoch 2 plus 0 plus 3 hoch 0 gleich 01:07:31.420 --> 01:07:32.080 minus 8. 01:07:33.120 --> 01:07:38.360 Oder sowas wie Num von 1 Meins 0 1 ist halt 3 hoch 3 minus 3 hoch 2 01:07:38.360 --> 01:07:40.960 plus 0 plus 3 hoch 0 gleich 19. 01:07:42.440 --> 01:07:47.000 Und jetzt wird es mit der Intuition schon ein bisschen schwieriger. 01:07:47.800 --> 01:07:50.700 Bei diesen Binärdarstellungen, Dezimaldarstellungen, 01:07:50.800 --> 01:07:54.560 Hexadezimaldarstellungen, da konnte man schon intuitiv erahnen, 01:07:55.680 --> 01:08:01.460 offensichtlich kann ich jede Zahl, die ich darstellen will, irgendwie 01:08:01.460 --> 01:08:03.120 in so einer Darstellung darstellen. 01:08:03.120 --> 01:08:06.400 Und der Beweis war ja auch relativ einfach. 01:08:07.040 --> 01:08:09.660 Die Frage ist, ist das hier immer noch möglich? 01:08:09.900 --> 01:08:14.920 Kann ich jede beliebige Zahl mithilfe dieser Meinsdarstellung 01:08:14.920 --> 01:08:16.360 darstellen? 01:08:16.460 --> 01:08:18.780 Also jede beliebige negative oder positive Zahl. 01:08:19.200 --> 01:08:20.400 Funktioniert das immer noch? 01:08:23.740 --> 01:08:25.680 Erstmal schauen wir uns ein paar Eigenschaften an. 01:08:25.780 --> 01:08:29.840 Was ist denn, wenn ich jetzt addieren und subtrahieren möchte in 01:08:29.840 --> 01:08:31.560 dieser Darstellung? 01:08:32.920 --> 01:08:37.240 Was ich da machen kann, ist, dass ich mir eine Invertierungsfunktion 01:08:37.240 --> 01:08:41.820 definiere, dass ich mir das Inverse einer Zahl definiere. 01:08:41.820 --> 01:08:49.460 Und dieses Inverse einer Zahl in dieser Wortzahl, in dieser 01:08:49.460 --> 01:08:52.880 Meinsdarstellung, kann ich wieder induktiv definieren. 01:08:53.020 --> 01:08:56.860 Ich sage einfach, das Inverse von 1 ist Meins, das Inverse von Meins 01:08:56.860 --> 01:08:58.780 ist 1 und das Inverse von 0 ist 0. 01:08:58.780 --> 01:09:02.620 Das Inverse des leeren Wortes ist das leere Wort. 01:09:03.500 --> 01:09:07.120 Und für jedes andere Wort, das ich so zerlegen kann, W und ein Zeichen 01:09:07.120 --> 01:09:15.000 X, ist gerade die Konkatenation aus dem Inverse von W und dem Inverse 01:09:15.000 --> 01:09:16.580 von dem Zeichen X. 01:09:17.440 --> 01:09:25.480 Also sowas wie das Inverse von 1 Meins 0 1 ist eben gerade Meins 1 0 01:09:25.480 --> 01:09:26.220 Meins. 01:09:27.620 --> 01:09:32.180 Und wenn ich das Inverse so definiere, dann macht das eben gerade das, 01:09:32.320 --> 01:09:32.840 was ich möchte. 01:09:33.080 --> 01:09:35.120 Eine Multiplikation mit Minus 1. 01:09:35.580 --> 01:09:39.400 Dann gilt für jedes Wort, dass also der Zahlenwert des Inversen von W 01:09:39.400 --> 01:09:45.260 gerade das negative Zahlenwert von dem ursprünglichen Wert W ist. 01:09:45.260 --> 01:09:49.120 Also die Inversion macht sozusagen, das Invertieren macht genau das, 01:09:49.200 --> 01:09:51.500 was es numerisch auch bitteschön soll. 01:09:56.970 --> 01:10:02.870 Wenn ich mir jetzt sowas anschaue und ich will dahin kommen, dass 01:10:02.870 --> 01:10:06.150 Subtraktion und Addition dasselbe ist und dass ich eine 01:10:06.150 --> 01:10:13.230 Zahlendarstellung bekomme, in der ich subtrahiere, indem ich einfach 01:10:13.230 --> 01:10:17.930 die negative Darstellung der Zahl addiere, dann muss ich das ein 01:10:17.930 --> 01:10:18.850 bisschen anders machen. 01:10:19.650 --> 01:10:22.370 Und dafür kann man sich jetzt ein bisschen anschauen. 01:10:22.890 --> 01:10:25.690 Das Rechnen ist in diesem doppeltgeschriebenen ZK. 01:10:25.930 --> 01:10:26.930 Das hatten wir halt definiert. 01:10:27.030 --> 01:10:29.850 Das ist halt die Menge der Zahlen 0 bis K-1. 01:10:30.770 --> 01:10:33.570 Und was ist, wenn ich da jetzt drin addiere und subtrahiere? 01:10:33.570 --> 01:10:38.310 Dann wissen Sie jetzt aus Ihrer linearen Algebra-Vorlesung, wenn man 01:10:38.310 --> 01:10:43.210 solche Operatoren definiert, dann darf man natürlich nicht den 01:10:43.210 --> 01:10:44.910 Definitionsbereich verlassen. 01:10:45.090 --> 01:10:50.450 Also wenn ich zwei Zahlen aus dem ZK miteinander zum Beispiel addiere, 01:10:50.790 --> 01:10:54.890 dann soll auch bitteschön wieder eine Zahl aus dem ZK rauskommen. 01:10:55.390 --> 01:10:58.570 Das heißt, die normale Addition, wie man das auf den natürlichen 01:10:58.570 --> 01:11:00.050 Zahlen macht, das funktioniert nicht. 01:11:00.650 --> 01:11:03.090 Auf den natürlichen Zahlen kann ich zwei beliebige Zahlen nach der 01:11:03.090 --> 01:11:05.150 Addition, so wie Sie sie kennen, addieren, und es kommt wieder eine 01:11:05.150 --> 01:11:06.150 natürliche Zahl raus. 01:11:06.150 --> 01:11:14.850 Wenn ich aus dem Z6 die 5 hernehme und 5 mit 1 addiere, kommt 6 raus, 01:11:15.150 --> 01:11:16.590 aber das nicht im Z6. 01:11:17.010 --> 01:11:18.230 Das ist dann in den natürlichen Zahlen. 01:11:18.330 --> 01:11:19.650 Das heißt, die Addition tut nicht. 01:11:20.170 --> 01:11:22.870 Sondern wir brauchen eine andere Addition und diese Addition nennen 01:11:22.870 --> 01:11:29.230 wir halt plus subscript k und sagen halt x plus subscript ky. 01:11:29.770 --> 01:11:32.930 Das ist eben gerade x plus y Modulus k. 01:11:34.010 --> 01:11:39.770 Und genauso mache ich das mit x minus subscript ky und sage, das ist 01:11:39.770 --> 01:11:42.530 halt x minus y Modulus k. 01:11:43.950 --> 01:11:48.390 Und aus gutem Grund nennt man dann das, was man da hat, einen Ring. 01:11:50.070 --> 01:11:51.630 Den Ring ZK. 01:11:53.230 --> 01:11:53.750 Warum? 01:11:55.430 --> 01:12:00.390 Das können wir uns leicht darstellen, wenn wir halt das ZK uns nicht 01:12:00.390 --> 01:12:04.170 als Menge darstellen, sondern als Ring, als einen Kreis. 01:12:05.530 --> 01:12:07.490 Was heißt das, wenn ich das so definiere? 01:12:08.610 --> 01:12:12.410 Wenn ich Zahlen in diesem Ring, die kann ich als Pfeile darstellen. 01:12:13.130 --> 01:12:16.290 Ich kann zum Beispiel die Zahl 6 als so einen Pfeil darstellen, der 01:12:16.290 --> 01:12:19.050 geht bei der 0 los und geht bis zur 6. 01:12:19.650 --> 01:12:22.590 Und wenn ich die Zahl 3 darstellen würde, dann wäre das halt ein 01:12:22.590 --> 01:12:24.790 Pfeil, der geht bei der 0 los und endet bei der 3. 01:12:25.610 --> 01:12:29.230 Und wenn ich die jetzt miteinander addiere, dann kann ich mir das so 01:12:29.230 --> 01:12:33.530 vorstellen, dass ich mir erst die erste Zahl hernehme, die 6, und dann 01:12:33.530 --> 01:12:39.410 auf dessen Pfeilspitze setze ich die zweite Zahl, den Pfeil für die 3. 01:12:40.150 --> 01:12:42.690 Und wenn ich das mache, dann komme ich bei der 9 an. 01:12:44.390 --> 01:12:49.870 Oder, wenn ich jetzt halt das provozieren möchte, dass ich halt da im 01:12:49.870 --> 01:12:55.470 Kreis rumlaufe, ich kann die Zahl 14 nehmen, also von der 0 bis zur 14 01:12:55.470 --> 01:12:58.470 und da soll jetzt die 3 drauf, dann setze ich halt das auf die Spitze 01:12:58.470 --> 01:13:01.850 des roten Pfeiles und komme gerade bei der 1 raus. 01:13:02.630 --> 01:13:08.390 Das heißt, diese Definition von dem Plus als x plus y modulus k kann 01:13:08.390 --> 01:13:11.510 man schön darstellen in so einer Kreisdarstellung. 01:13:15.340 --> 01:13:18.380 Jetzt gibt es noch ein kleines Lemma, das man nachrechnen kann. 01:13:19.440 --> 01:13:24.540 Wenn ich diese Operationen Plus und Minus nehme und ich weiß vom 01:13:24.540 --> 01:13:27.660 Kontext her, dass ich nicht auf den natürlichen Zahlen landen will, 01:13:27.720 --> 01:13:31.920 sondern dass ich in diesem Ring zk rechnen will, dann lasse ich das 01:13:31.920 --> 01:13:35.720 Subscript k meistens weg, damit es halt nicht verwirrt. 01:13:35.720 --> 01:13:39.480 Und kann jetzt zum Beispiel sowas Nettes zeigen, dass für jede 01:13:39.480 --> 01:13:43.960 beliebige natürliche Zahl, wenn ich x plus y oder x minus y rechne, 01:13:44.660 --> 01:13:50.320 dann gilt halt x plus oder minus y modulus k ist das gleiche, als wenn 01:13:50.320 --> 01:13:58.400 ich erst x modulus k rechne und dann Plus Minus im Ring y modulus k. 01:13:59.000 --> 01:14:03.780 Das heißt also, diese Modulus-Operation sorgt dafür, dass ich in 01:14:03.780 --> 01:14:06.700 diesem Ring zk drin bleibe. 01:14:07.040 --> 01:14:10.440 Dass egal welche zwei Zahlen, die müssen nicht mal aus dem 01:14:10.440 --> 01:14:13.460 ursprünglichen zk kommen, die können aus den natürlichen Zahlen 01:14:13.460 --> 01:14:13.780 kommen. 01:14:13.780 --> 01:14:17.640 Wenn ich die auf diese Art und Weise addiere, x plus minus y und 01:14:17.640 --> 01:14:23.560 modulus k rechne, dann werde ich immer in dem Ring zk landen. 01:14:25.940 --> 01:14:31.660 Also Beweis, ich kann also x zerlegen als ein kqx plus rx und ein y 01:14:31.660 --> 01:14:33.180 ist ein ky plus ry. 01:14:33.720 --> 01:14:37.980 Das ist also Ergebnis der Division plus Rest. 01:14:39.580 --> 01:14:43.220 Und dann kann ich das halt entsprechend zerlegen in a. 01:14:44.200 --> 01:14:48.960 Und dieser Rest kommt eben gerade aus diesem zk, aus diesem Ring zk. 01:14:49.480 --> 01:14:53.300 Dann kann ich das halt entsprechend zerlegen als k gleich kqx plus 01:14:53.300 --> 01:14:57.040 minus ky plus rest x plus minus rest y. 01:14:57.040 --> 01:15:01.620 Das ganze modulus k nehmen und kann das dann wiederum der Rechenregel 01:15:01.620 --> 01:15:05.840 von diesem Modulus entsprechend zeigen, dass es Rest x plus minus Rest 01:15:05.840 --> 01:15:07.060 y modulus k ist. 01:15:07.280 --> 01:15:13.960 Also Rest x plus minus in dem k-Ring Rest y. 01:15:15.600 --> 01:15:20.700 Also addieren mache ich, indem ich Pfeile aufeinandersetze. 01:15:21.620 --> 01:15:26.240 Und zwar Basis des Pfeils an die Spitze des vorhergehenden Pfeils. 01:15:26.880 --> 01:15:32.680 Wenn ich jetzt subtrahiere, dann muss ich die Spitzen der Pfeile 01:15:32.680 --> 01:15:33.580 nebeneinander setzen. 01:15:34.040 --> 01:15:38.300 Also angenommen, ich möchte 4 minus 7 im Z16 rechnen. 01:15:39.900 --> 01:15:41.960 Dann nehme ich mir erstmal den Pfeil für die 4 her. 01:15:42.020 --> 01:15:44.400 Das ist dieser rote Pfeil, der geht von der 0 bis zur 4. 01:15:45.100 --> 01:15:49.320 Und dann setze ich jetzt den Pfeil für die 7 Spitze auf Spitze, also 01:15:49.320 --> 01:15:50.540 auf die Spitze der 4. 01:15:51.800 --> 01:15:55.600 Verfolge dann den Pfeil zurück bis zu seinem Anfang und komme da bei 01:15:55.600 --> 01:15:56.500 der 13 raus. 01:15:57.900 --> 01:16:02.920 Das heißt also, wenn ich 4 minus 7 rechne, dann komme ich bei der 13 01:16:02.920 --> 01:16:04.980 raus in diesem ZK. 01:16:07.780 --> 01:16:12.640 Diese ZKs sind deshalb so interessant und so nützlich, weil in den 01:16:12.640 --> 01:16:15.660 Rechnern, in denen wir arbeiten, haben wir ja auch nicht unendlich 01:16:15.660 --> 01:16:16.680 viel Speicher zur Verfügung. 01:16:16.680 --> 01:16:21.360 Sondern in den Rechnern, in denen wir arbeiten, können wir in der 01:16:21.360 --> 01:16:25.340 Regel nur Zahlen aus einem bestimmten Bereich hinschreiben. 01:16:25.880 --> 01:16:29.180 Wir verwenden in der Regel die Binärdarstellung und wir haben jetzt 01:16:29.180 --> 01:16:32.660 Speicherstellen, die haben eine bestimmte Länge. 01:16:33.940 --> 01:16:40.400 Können 8 Binärzeichen lang sein, 16 Binärzeichen, 32 Binärzeichen, 64 01:16:40.400 --> 01:16:41.160 Binärzeichen. 01:16:41.640 --> 01:16:44.440 Das ist sowas Übliches in den heutigen Rechnerarchitekturen. 01:16:45.480 --> 01:16:48.220 Hier in der Vorlesung und später in der Vorlesung Technische 01:16:48.220 --> 01:16:51.780 Informatik werden Sie eine sehr einfache Rechnerarchitektur 01:16:51.780 --> 01:16:52.400 kennenlernen. 01:16:52.400 --> 01:16:55.480 Da sind das eben gerade 24 Zeichen. 01:16:56.060 --> 01:16:58.240 Man spricht dann auch von 24 Bits. 01:16:59.580 --> 01:17:02.940 Das heißt, die Zahlen, die ich jetzt, wenn ich positive Zahlen 01:17:02.940 --> 01:17:10.220 darstellen will, die ich mit, wenn ich sie nur 16 Binärzeichen zur 01:17:10.220 --> 01:17:14.200 Verfügung habe, die Zahlen, die ich damit darstellen kann, die sind 01:17:14.200 --> 01:17:16.460 eben gerade dieser Ring Z16. 01:17:16.920 --> 01:17:21.140 Wenn ich also mich nur auf positive Zahlen beschränke und ich habe 16 01:17:21.140 --> 01:17:24.620 solcher Bits zur Verfügung und will mit denen Dingern rumrechnen, dann 01:17:24.620 --> 01:17:27.960 kann ich gerade eben diese Zahlen aus dem Z16 darstellen und alles, 01:17:28.080 --> 01:17:33.440 was ich irgendwie da hin und her addiere, wird immer in diesem Z16 01:17:33.440 --> 01:17:33.660 landen. 01:17:34.320 --> 01:17:36.580 Weil, wenn wir uns jetzt nochmal überlegen, was vorhin bei der 01:17:36.580 --> 01:17:41.140 Addition passiert ist, dieser Übertrag, den ich habe, wenn ich ganz 01:17:41.140 --> 01:17:43.860 links einen Übertrag habe, dann habe ich ja keine Speicherzelle mehr, 01:17:43.920 --> 01:17:44.820 wo ich den hinschreiben kann. 01:17:45.060 --> 01:17:48.160 Mein Wort kann nur 16 Zeichen lang sein. 01:17:48.640 --> 01:17:51.940 Und jetzt habe ich einen Übertrag, der muss nach links raus und da ist 01:17:51.940 --> 01:17:52.880 kein Platz mehr vorhanden. 01:17:53.320 --> 01:17:55.720 Dieser Übertrag, der geht halt flöten, der geht verloren. 01:17:55.720 --> 01:17:59.520 Und das Ergebnis ist, dass ich wieder bei einer anderen Zahl in diesem 01:17:59.520 --> 01:18:03.600 Z16 entsprechend dieser Rechenvorschrift lande. 01:18:04.920 --> 01:18:08.520 Jetzt würden wir ja gerne, wie gesagt, auch subtrahieren und wir 01:18:08.520 --> 01:18:13.020 würden gerne das so haben, dass eine Subtraktion auch gleich eine 01:18:13.020 --> 01:18:13.860 Addition ist. 01:18:13.860 --> 01:18:17.120 Jetzt habe ich hier das Problem, 4 minus 7 ist gleich 13. 01:18:18.920 --> 01:18:24.100 Das soll eigentlich das gleiche sein wie 4 plus minus 7. 01:18:24.420 --> 01:18:26.420 Eine minus 7 kann ich jetzt erstmal noch gar nicht darstellen. 01:18:27.000 --> 01:18:32.620 Aber ich hätte das gerne so, dass es 4 plus minus 7, das soll bitte 01:18:32.620 --> 01:18:38.120 schön der Darstellung der Zahl minus 3 entsprechen. 01:18:38.280 --> 01:18:40.940 Das, was da rauskommt, soll eine minus 3 sein. 01:18:41.780 --> 01:18:44.300 Wie kann man das machen? 01:18:46.780 --> 01:18:50.100 Also das hier ist erstmal noch das, was ich mündlich gesagt habe. 01:18:50.200 --> 01:18:54.100 Das ist diese Darstellung, die Binärdarstellung, wenn ich nur Speicher 01:18:54.100 --> 01:18:55.280 begrenzter Größe habe. 01:18:55.400 --> 01:18:59.180 Zum Beispiel die Mima benutzt 24 Bit und dann kann ich diese 01:18:59.180 --> 01:19:01.400 Binärdarstellung eben definieren. 01:19:01.520 --> 01:19:04.280 Die Binärdarstellung zu einer bestimmten Länge L. 01:19:05.800 --> 01:19:08.240 Ja, das ist lustig. 01:19:10.980 --> 01:19:14.280 Also die Binärdarstellung zu einer bestimmten Länge L, wenn ich halt L 01:19:14.280 --> 01:19:19.940 Zeichen zur Verfügung habe, die bildet eben gerade ab in diesem Z 2 01:19:19.940 --> 01:19:20.300 hoch L. 01:19:20.960 --> 01:19:23.460 Und wenn ich also 16 Zeichen zur Verfügung habe, dann habe ich ja 01:19:23.460 --> 01:19:26.160 diesen Z 2 hoch 16. 01:19:28.100 --> 01:19:31.520 Wenn ich den Z 16 habe, dann ist das eben 2 hoch 4. 01:19:31.740 --> 01:19:36.660 Dann habe ich halt 4 Zeichen aus dem Binärsystem zur Verfügung. 01:19:37.220 --> 01:19:44.200 Man kann halt sagen, die Binärdarstellung von N, das ist eben gerade 0 01:19:44.200 --> 01:19:49.640 hoch L, minus Länge der Repräsentation zu 2 von N. 01:19:50.160 --> 01:19:53.920 Das heißt also, ich gucke, wenn ich jetzt die Repräsentation 2 von N 01:19:53.920 --> 01:19:56.800 habe, die also keine Beschränkung hat in der Länge der Worte, die ich 01:19:56.800 --> 01:20:00.760 darstellen kann, wie viele führende 0 muss ich dann erstmal einfüllen, 01:20:00.940 --> 01:20:02.340 damit ich alle Positionen habe. 01:20:02.340 --> 01:20:07.020 Und dann kommt dahinter diese Repräsentation von 2 von N. 01:20:07.800 --> 01:20:11.780 Und da ich mich halt einschränke, dass die Zahlen eben gerade aus 01:20:11.780 --> 01:20:17.180 diesem Z 2 hoch L kommen, kann es nie passieren, dass Reprä 2 von N 01:20:17.180 --> 01:20:20.960 eine Darstellung benötigt, die länger ist als 2 hoch L Zeichen. 01:20:21.780 --> 01:20:25.660 Das heißt also, vorne mit führenden Nullen auffüllen und dann die 01:20:25.660 --> 01:20:29.940 Repräsentation, so wie wir sie bei beliebiger Wortlänge definiert 01:20:29.940 --> 01:20:31.680 haben, eben hinten dran schreiben. 01:20:32.520 --> 01:20:36.780 Und dementsprechend, wenn ich diese Binärdarstellung so definiere, 01:20:36.900 --> 01:20:41.260 dann ist eben die Länge der Binärdarstellung einer beliebigen Zahl aus 01:20:41.260 --> 01:20:47.920 dem Z 2 hoch L, hat eben gerade immer die Länge L, aber der Nummer 2 01:20:47.920 --> 01:20:51.840 Wert von L von N hat halt immer den richtigen Wert, nämlich wieder N. 01:20:52.560 --> 01:20:56.880 Das ist also das, jetzt eine Repräsentation, die eben diese führenden 01:20:56.880 --> 01:20:58.840 Nullen einfügt. 01:21:00.100 --> 01:21:04.700 Wo aber immer noch der Zahlenwert der Nummer 2 so erhalten wird, wie 01:21:04.700 --> 01:21:06.000 wir ihn bitte gerne schon hätten. 01:21:07.420 --> 01:21:09.920 Okay, was machen wir jetzt mit negativen Zahlen? 01:21:11.380 --> 01:21:15.700 Das hier ist jetzt mal der Z 16, also mit 4 Bit dargestellt. 01:21:17.820 --> 01:21:21.680 Der bildet halt die Zahlen 0 bis 15, so in einem Kreis dar. 01:21:23.500 --> 01:21:26.720 Wir definieren uns auch jetzt einen anderen. 01:21:27.700 --> 01:21:32.480 Das ist nicht mehr der Z 16, sondern das nennen wir K 4. 01:21:34.500 --> 01:21:38.200 Und dieses K, das steht für Komplementär. 01:21:38.900 --> 01:21:45.400 Und 4 ist die Anzahl der Bits, der Zeichen, die wir in unserem Wort, 01:21:45.640 --> 01:21:50.780 das wir zur Basis 2 in Binärdarstellung darstellen wollen, da haben, 01:21:50.860 --> 01:21:53.160 aber es sollen negative Zahlen auch darstellen können. 01:21:53.660 --> 01:21:56.700 Und das macht man jetzt halt so, dass das mit der Addition passt. 01:21:57.880 --> 01:22:00.380 Dass es mit der Addition und der Subtraktion passt. 01:22:00.800 --> 01:22:03.980 Wenn ich auf eine negative Zahl was Positives aufaddieren will, dann 01:22:03.980 --> 01:22:07.800 mache ich halt den Pfeil von 0 bis zu dieser negativen Zahl und dann 01:22:07.800 --> 01:22:11.940 setze ich den Pfeil, der die positive Zahl darstellt, eben an die 01:22:11.940 --> 01:22:12.360 Spitze. 01:22:12.360 --> 01:22:19.960 Wenn ich zu einer positiven Zahl eine negative Zahl addiere, dann geht 01:22:19.960 --> 01:22:24.200 der Pfeil der positiven Zahl bis zu irgendeiner Zahl und dann kommt 01:22:24.200 --> 01:22:29.680 der negative Pfeil und den setze ich gerade wieder auf die Spitze und 01:22:29.680 --> 01:22:33.120 da negative Zahlen sozusagen nach links gehen, geht der automatisch in 01:22:33.120 --> 01:22:33.860 die richtige Richtung. 01:22:38.100 --> 01:22:41.640 Also Addition, Spitze auf Spitze, da kann es halt passieren, dadurch, 01:22:41.800 --> 01:22:44.540 dass ich immer in diesem K4 lande, dass da Minus reinkommt. 01:22:47.920 --> 01:22:52.360 Aber, wenn ich zum Beispiel jetzt eine negative Zahl 2 plus eine 01:22:52.360 --> 01:22:55.840 positive Zahl 3 addiere, dann funktioniert das genau wieder so. 01:22:56.060 --> 01:22:59.680 Also Pfeil der positiven Zahl auf die Spitze der negativen Zahl 01:22:59.680 --> 01:23:04.620 stellen und ich komme bei 1 raus, genau da, wo ich bitteschön auch 01:23:04.620 --> 01:23:05.580 landen möchte. 01:23:07.820 --> 01:23:12.220 Genauso hier 3 plus Minus 2, also die Subtraktion als eine Addition 01:23:12.220 --> 01:23:15.800 der negativen Zahl, funktioniert genauso, wie ich will. 01:23:15.900 --> 01:23:19.320 Wieder den Beginn des Pfeils auf die Spitze der ersten Zahl stellen. 01:23:21.700 --> 01:23:26.660 Wenn man sich jetzt das anschaut, der K4 und der Z16, die haben genau 01:23:26.660 --> 01:23:27.840 gleich viele Positionen. 01:23:28.400 --> 01:23:31.400 Die stellen jeweils 16 verschiedene Zahlen dar. 01:23:32.120 --> 01:23:34.120 Einmal mit und einmal mit negativen Zahlen. 01:23:34.480 --> 01:23:38.100 Einmal mit negativen Zahlen und einmal ohne negative Zahlen. 01:23:38.100 --> 01:23:42.920 Wenn ich mir den Z16 anschaue, der hat halt auch 16 Positionen, dem 01:23:42.920 --> 01:23:49.680 kann ich jetzt die Darstellung, die Binärdarstellung zuordnen und kann 01:23:49.680 --> 01:23:54.500 jetzt einfach die Werte, die schwarzen Zahlenwerte austauschen durch 01:23:54.500 --> 01:23:57.540 das, was ich in dieser Zweierkomplementdarstellung machen will. 01:23:57.540 --> 01:24:02.160 Ich habe also die gleiche Kodierung wie vorher, die gleichen Folgen 01:24:02.160 --> 01:24:05.960 von Nullen und Einsen an den Positionen, wie ich sie vorher hatte im 01:24:05.960 --> 01:24:10.100 Z16, hier im K4, nur sie bedeuten jetzt etwas anderes. 01:24:11.380 --> 01:24:15.140 Die 4 mal die 1 bedeutet jetzt halt nicht 15, sondern die bedeutet 01:24:15.140 --> 01:24:16.900 jetzt halt Minus 1. 01:24:17.620 --> 01:24:21.720 Und das ist jetzt die Darstellung von negativen Zahlen nach diesem 01:24:21.720 --> 01:24:22.700 Zweierkomplement. 01:24:23.440 --> 01:24:27.560 Und das Schicke daran ist, wenn ich jetzt addiere, wenn ich jetzt eine 01:24:27.560 --> 01:24:32.680 positive Zahl mit einer negativen Zahl addiere und das genauso mache, 01:24:32.840 --> 01:24:36.980 wie ich das vorher bei Leibniz nur mit positiven Zahlen mache, dann 01:24:36.980 --> 01:24:38.420 kommt wieder das Richtige raus. 01:24:38.420 --> 01:24:45.440 Also angenommen, ich möchte von der Zahl 2, die dargestellt wird als 01:24:45.440 --> 01:24:48.140 0010, 1 abziehen. 01:24:48.840 --> 01:24:53.100 Dann ist das 0010 plus 1111. 01:24:53.780 --> 01:24:55.240 Schreibe ich das darunter? 01:24:56.580 --> 01:25:01.940 0 exklusiv oder 1 ist 1. 01:25:03.720 --> 01:25:07.820 1 exklusiv oder 1 ist 0, 1 Übertrag. 01:25:08.820 --> 01:25:11.980 1 exklusiv oder 1 ist 0, 1 Übertrag. 01:25:12.100 --> 01:25:14.800 1 exklusiv oder 1 ist 0, 1 Übertrag. 01:25:14.900 --> 01:25:17.140 Der 1 Übertrag fällt weg, weil wir haben nur 4 Stellen. 01:25:17.860 --> 01:25:21.360 Und heraus kommt die Zahl 0001. 01:25:21.360 --> 01:25:26.020 Das heißt, addieren und subtrahieren ist dasselbe. 01:25:26.200 --> 01:25:31.080 Diese Art der Darstellung negativer Zahlen ermöglicht es mir, so ein x 01:25:31.080 --> 01:25:36.020 -oder -basiertes Rechenwerk zu bauen und damit sowohl zu addieren als 01:25:36.020 --> 01:25:37.500 auch zu subtrahieren. 01:25:38.340 --> 01:25:41.460 Wie wir das dann jetzt mathematisch genau machen, schauen wir uns dann 01:25:41.460 --> 01:25:42.600 am Freitag an.