WEBVTT 00:05.190 --> 00:11.070 Gut, wir waren stehen geblieben beim Thema Kodierung und wir hatten 00:11.070 --> 00:14.710 uns zuletzt bedeutungserhaltende Abbildungen angesehen, das heißt also 00:14.710 --> 00:20.770 Abbildungen, die, wenn man geeignete Interpretationen anwendet, die 00:20.770 --> 00:24.030 Bedeutung entsprechend nicht verändern. 00:26.390 --> 00:30.510 Wir hatten uns angeschaut, was ein Homomorphismus ist, weil 00:30.510 --> 00:34.870 Homomorphismen geeignete Abbildungen sind, um Übersetzungen 00:34.870 --> 00:35.590 anzuschauen. 00:35.630 --> 00:39.290 Und wir hatten gesehen, dass ein Homomorphismus sozusagen das Ganze 00:39.290 --> 00:42.270 erhält unter der Konkatenation. 00:42.410 --> 00:45.930 Wenn ich also ein Homomorphismus auf ein konkateniertes Wort anwende, 00:46.670 --> 00:50.490 dann kann ich auch den Homomorphismus auf die Teilworte anwenden und 00:50.490 --> 00:52.230 danach das Ergebnis konkatenieren. 00:53.290 --> 00:58.610 Und ein Homomorphismus hatten wir gesagt, ist Epsilon-frei, wenn jedes 00:58.610 --> 01:02.170 Wort aus dem Grundalphabet, über den die Sprachen gebildet werden, 01:02.750 --> 01:05.190 nicht auf Epsilon abbildet. 01:07.090 --> 01:10.910 Wir hatten gesehen, wenn man doch das leere Wort hat, also das leere 01:10.910 --> 01:15.950 Wort darf ja durchaus hinterher vorkommen und ist allgemein drin in 01:15.950 --> 01:19.030 der Menge aller Wörter, die über einem Alphabet gebildet werden. 01:19.350 --> 01:23.430 Wenn ich das leere Wort in einen x-beliebigen Homomorphismus reintue, 01:23.550 --> 01:26.130 muss wieder das leere Wort rauskommen. 01:26.210 --> 01:27.990 Das hatten wir gezeigt über die Definition der Länge. 01:29.130 --> 01:32.870 Und wir waren stehen geblieben bei diesem Lemma und wollten uns das 01:32.870 --> 01:33.530 jetzt anschauen. 01:34.010 --> 01:35.150 Und was besagt das Lemma? 01:35.510 --> 01:41.010 Also wir haben zwei Alphabete A und B und wir haben zwei Abbildungen H 01:41.010 --> 01:45.050 und G, die von der Menge aller Wörter von dem einen Alphabet in die 01:45.050 --> 01:47.810 Menge aller Wörter über dem anderen Alphabet anwenden. 01:49.290 --> 01:54.390 Und jetzt seien diese Homomorphismen der Gestalt, dass sie für die 01:54.390 --> 01:58.290 einzelnen Worte im ursprünglichen Alphabet immer das selbe Ergebnis 01:58.290 --> 01:58.770 bilden. 01:59.610 --> 02:03.590 Das heißt, wenn ich ein Wort hernehme oder ein Zeichen aus dem 02:03.590 --> 02:07.210 ursprünglichen Alphabet, ist das ein Wort aus der Sprache über alle 02:07.210 --> 02:08.510 Wörter über diesem Alphabet. 02:09.050 --> 02:11.750 Wenn ich das in einen Homomorphismus reintue, bekomme ich dann halt 02:11.750 --> 02:14.350 entsprechend ein Wort, also es muss nicht ein einzelnes Zeichen sein, 02:14.450 --> 02:18.490 es können mehrere Zeichen sein, ein längeres Wort aus der Menge aller 02:18.490 --> 02:20.410 Wörter aus dem zweiten Alphabet. 02:21.310 --> 02:27.850 Und wenn das immer dasselbe Ergebnis gibt für H und G, für die 02:27.850 --> 02:35.610 einzelnen eine Länge langen Worte aus der Sprache, also die Zeichen 02:35.610 --> 02:40.030 aus dem Alphabet, dann gilt, dass die Homomorphisme komplett gleich 02:40.030 --> 02:40.190 ist. 02:40.270 --> 02:44.190 Dann ist es völlig egal, was für ein Wort welcher Länge ich reinstecke 02:44.190 --> 02:49.330 in den Homomorphismus, dann kommt auch immer dasselbe Ergebnis bei G 02:49.330 --> 02:49.650 raus. 02:50.230 --> 02:54.270 Mit anderen Worten, wie ich die einzelnen Zeichen aus dem 02:54.270 --> 02:59.050 Grundalphabet abbilde, legt vollständig fest, wie der Homomorphismus 02:59.050 --> 03:00.370 insgesamt abbildet. 03:01.530 --> 03:05.010 Das kann man jetzt wieder zeigen durch vollständige Induktion, indem 03:05.010 --> 03:09.410 man wieder anfängt mit einem Induktionsanfang und über die Länge der 03:09.410 --> 03:10.030 Worte geht. 03:10.870 --> 03:14.970 Und ich schaue mir dann immer Worte an, die immer ein Zeichen länger 03:14.970 --> 03:15.310 werden. 03:15.830 --> 03:19.630 Für das Wort mit der Länge 0, das Epsilon-Wort, ist das trivial. 03:19.890 --> 03:24.630 Wir hatten schon vorher gesehen, dass Homomorphismen Epsilon immer auf 03:24.630 --> 03:25.890 Epsilon abbilden. 03:26.630 --> 03:29.670 Dementsprechend gilt das für jeden Homomorphismus. 03:30.490 --> 03:37.570 Also sei das Ganze gegeben für ein Wort der Länge N aus der Menge 03:37.570 --> 03:38.250 aller Wörter. 03:38.690 --> 03:42.230 Und wir nehmen uns jetzt ein einzelnes Zeichen aus dem Alphabet A her 03:42.230 --> 03:47.710 und wir haben die Induktionsvoraussetzung, dass für die Wörter der 03:47.710 --> 03:50.270 Länge N H von W gleich G von W gilt. 03:51.150 --> 03:56.150 Jetzt machen wir aus diesem H von W der Länge N ein Wort der Länge N 03:56.150 --> 04:00.330 plus 1, indem wir hinten einfach ein beliebiges Zeichen aus dem 04:00.330 --> 04:04.910 Alphabet dran tun und müssen dann zeigen, dass H von W um dieses 04:04.910 --> 04:09.010 Zeichen X erweitert, verlängert auf Länge N plus 1, dass das das 04:09.010 --> 04:12.250 gleiche Abbild hat, als wenn ich das in G reinstecke. 04:12.930 --> 04:14.370 Und dann kann man einfach rechnen. 04:14.570 --> 04:19.830 H von W konkateniert mit X ist H von W konkateniert mit H von X. 04:19.910 --> 04:22.330 Das ist die Definition eines Homomorphismus und das ist die 04:22.330 --> 04:24.350 Voraussetzung für das Lemma. 04:25.730 --> 04:27.550 W war jetzt ein Wort der Länge N. 04:28.130 --> 04:30.010 Dementsprechend gilt die Induktionsvoraussetzung. 04:30.010 --> 04:32.150 Statt H von W können wir G von W schreiben. 04:34.490 --> 04:37.210 H von X muss sein gleich G von X. 04:37.410 --> 04:38.990 Das ist nämlich die Voraussetzung des Lemmas. 04:39.430 --> 04:43.870 Das heißt eben, dass immer auf das gleiche Wort abgebildet wird, wenn 04:43.870 --> 04:46.470 ich ein einzelnes Zeichen X aus dem Alphabet reintue. 04:47.070 --> 04:52.170 Und dann ist dementsprechend das Ganze das Ergebnis G von W X gemäß 04:52.170 --> 04:55.090 Definition Homomorphismus und dementsprechend gilt das Lemma. 04:56.270 --> 04:57.230 Soweit, so klar. 04:58.630 --> 05:03.810 Mit dieser Eigenschaft kann ich jetzt noch eine zweite Abbildung 05:03.810 --> 05:09.430 definieren und zwar oder eine besondere Art des Homomorphismus 05:09.430 --> 05:10.190 definieren. 05:10.730 --> 05:15.850 Angenommen, ich habe eine Abbildung, die einzelne Zeichen A abbildet 05:15.850 --> 05:20.850 in die Menge aller Wörter über dem Alphabet B. 05:21.070 --> 05:24.470 Also ich nehme ein X aus A her und bilde das ab, irgendein Wort, das 05:24.470 --> 05:25.550 über B gebildet wird. 05:26.370 --> 05:29.190 Und jetzt sei diese, das sei die Funktion F. 05:29.590 --> 05:33.370 Und da definiere ich mir jetzt eine davon abgeleitete Abbildung F 05:33.370 --> 05:37.550 Sternchen Sternchen, die jetzt nicht von A nach B Sternchen abbildet, 05:37.570 --> 05:39.410 sondern von A Sternchen nach B Sternchen. 05:39.510 --> 05:41.870 Also nicht einzelne Zeichen, sondern Wörter beliebiger Länge. 05:42.550 --> 05:44.070 Und es seien zwei Sachen definiert. 05:44.190 --> 05:48.130 Das eine sei, dass das leere Wort wieder auf das leere Wort abgebildet 05:48.130 --> 05:48.370 wird. 05:48.890 --> 05:51.130 Das ist wichtig, weil wir wollen am Ende einen Homomorphismus 05:51.130 --> 05:53.110 erreichen, erhalten. 05:53.550 --> 05:58.470 Und ansonsten für jedes beliebige Wort aus A Sternchen sei halt 05:58.470 --> 06:06.130 gegeben, dass F Sternchen Sternchen WX abbildet auf F Sternchen 06:06.130 --> 06:10.050 Sternchen von W konkateniert mit der Einzelabbildung, die durch F 06:10.050 --> 06:11.570 definiert wird. 06:11.930 --> 06:14.910 Das heißt, das Ganze ist wieder eine induktive Definition. 06:15.750 --> 06:19.790 Die Wörter werden in der Länge immer kleiner gemacht, indem hinten ein 06:19.790 --> 06:23.790 X abgespalten wird, also ein einzelnes Zeichen abgespalten wird. 06:24.730 --> 06:30.010 Das X muss es... und dann das wieder rekursiv angewandt wird auf das 06:30.010 --> 06:32.510 verbleibende Restwort W. 06:33.730 --> 06:37.490 Und dieses F Sternchen Sternchen ist wieder ein Homomorphismus. 06:38.010 --> 06:39.330 Man kann das schon sehr leicht ahnen. 06:39.410 --> 06:42.150 Man kann das durch vollständige Induktion beweisen. 06:42.690 --> 06:44.490 Ist auch ein relativ einfacher Beweis. 06:44.850 --> 06:47.870 Und dieses F Sternchen Sternchen, wenn wir es auf diese Art und Weise 06:47.870 --> 06:52.250 definieren, heißt ein durch F induzierter Homomorphismus. 06:52.910 --> 06:56.210 Das heißt, das ist der Homomorphismus, der dadurch festgelegt wird, 06:56.270 --> 06:59.810 dass ich einmal festlege, wie die einzelnen Zeichen aus dem Alphabet 06:59.810 --> 07:01.210 abgebildet werden. 07:01.510 --> 07:10.990 Und das ergibt dann automatisch einen Homomorphismus, der alle Wörter 07:10.990 --> 07:16.110 als Homomorphismus aus dem über A gebildeten Alphabet nach B Sternchen 07:16.110 --> 07:16.590 abbildet. 07:19.210 --> 07:22.730 Mit diesem Verfahren, dass man hinten was abschneidet und dann 07:22.730 --> 07:29.230 zusammentut, kann man jetzt sich anschauen, Kodierung, also eine 07:29.230 --> 07:34.050 Abbildung durch einen Homomorphismus, oder besser gesagt eine 07:34.050 --> 07:37.510 Übersetzung von Wörtern aus dem einen Alphabet über dem einen Alphabet 07:37.510 --> 07:40.870 A zu Wörtern über dem anderen Alphabet B. 07:42.230 --> 07:43.890 Und das sei ein Homomorphismus. 07:44.630 --> 07:47.410 Und dann möchte man natürlich noch ein paar andere Eigenschaften 07:47.410 --> 07:50.130 wissen, zum Beispiel, ob das Ganze injektiv ist. 07:52.670 --> 07:57.330 Das ist eine Eigenschaft, die ist nicht im Allgemeinen für beliebige 07:57.330 --> 07:59.170 Homomorphismen einfach zu sehen. 08:00.270 --> 08:04.590 Es gibt aber wiederum einen Spezialfall von Homomorphismen, sogenannte 08:05.590 --> 08:06.550 präfixfreie Homomorphismen. 08:07.610 --> 08:10.170 Und für die ist das einfach zu sehen. 08:11.070 --> 08:12.670 Was bedeutet präfixfrei? 08:12.770 --> 08:14.470 Das ist das, was man sich schon vorstellen kann. 08:15.070 --> 08:19.370 Das bedeutet, dass wenn ich mir anschaue, auf was wird denn 08:19.370 --> 08:21.490 abgebildet. 08:21.770 --> 08:25.310 Also ich bilde von irgendeinem Alphabet in ein anderes Alphabet ab, in 08:25.310 --> 08:26.190 das, was ich abbilde. 08:26.410 --> 08:27.570 Das sind meine Kodwörter. 08:27.810 --> 08:33.910 Das ist mein Kod, mit dem ich die Wörter aus A Sternchen kodiere. 08:34.370 --> 08:39.710 Wenn diese Kodwörter, auf die ich abbilde, derart sind, dass nie ein 08:39.710 --> 08:42.630 Kodwort Präfix eines anderen Kodes ist. 08:43.050 --> 08:47.370 Das heißt, es darf kein Kodwort geben, das irgendwie so anfängt, dass 08:47.370 --> 08:51.070 da der Anfang beliebiger Länge ein anderes Kodwort ist. 08:51.230 --> 08:53.150 Dann nennen wir das Ganze präfixfrei. 08:54.470 --> 08:59.010 Dann kann man relativ einfach zeigen, dass jeder präfixfreie Kod, also 08:59.010 --> 09:03.330 jeder Homomorphismus dieser Art, der präfixfreie Ergebnisse liefert, 09:03.490 --> 09:05.390 dass der injektiv ist. 09:07.950 --> 09:10.910 Vorher noch ein kleines Problem. 09:11.050 --> 09:13.570 Wenn wir uns die umgekehrte Richtung anschauen, also wenn wir wieder 09:13.570 --> 09:17.810 aus B Sternchen zurück abbilden wollen nach A Sternchen, wenn wir also 09:17.810 --> 09:22.190 den Kod, den wir durch den Homomorphismus erhalten haben, dekodieren 09:22.190 --> 09:22.510 wollen. 09:22.610 --> 09:25.870 Wieder auf das ursprüngliche Urbild zurückrechnen wollen. 09:27.090 --> 09:32.790 Da muss man beachten, dass ein Homomorphismus nicht notwendigerweise 09:32.790 --> 09:33.730 sujektiv ist. 09:34.450 --> 09:40.110 Das heißt, nicht jedes Wort aus B Sternchen muss notwendigerweise ein 09:40.110 --> 09:40.850 Kodwort sein. 09:41.510 --> 09:45.350 Und wenn ich jetzt dekodiere, ich also von B Sternchen zurück abbilde 09:45.350 --> 09:48.590 nach A Sternchen, dann muss ich irgendwie was überlegen für den Fall, 09:48.770 --> 09:52.290 dass irgendein Wort aus diesem B Sternchen gar kein gültiger Kod ist. 09:52.690 --> 09:56.130 Dass der gar nicht Abbild dieses Homomorphismus ist, des 09:56.130 --> 09:59.650 ursprünglichen war es und muss da irgendwie mir was einfallen lassen, 09:59.750 --> 10:01.030 dass ich das kennzeichne. 10:01.410 --> 10:04.810 Und das kann man relativ einfach damit machen, indem man so ein 10:04.810 --> 10:06.090 Spezialwort einführt. 10:06.310 --> 10:08.330 Hier so ein umgekehrtes T genommen. 10:08.790 --> 10:12.210 Das soll einfach stehen für undefiniert, nicht dekodierbar. 10:13.270 --> 10:16.510 Und wenn ich dann also die Dekodierung definiere, dann bildet die ab 10:16.510 --> 10:25.390 von B Sternchen nach A Sternchen vereinigt mit oder multipliziert mit 10:25.390 --> 10:28.730 diesem umgekehrten T Sternchen. 10:28.850 --> 10:32.730 Oder andersherum, ich vereinige das Alphabet mit diesem zusätzlichen 10:32.730 --> 10:36.790 Zeichen, das bei nicht dekodierbar mit reingeschleust wird und bilde 10:36.790 --> 10:38.970 darüber alle Wörter und daran wird abgebildet. 10:39.950 --> 10:46.990 Wenn also W kein Kodwort ist, dann muss ich meine Dekodierung halt so 10:46.990 --> 10:51.890 definieren, dass dann irgendwo dieses Spezialsymbol eingefügt werden 10:51.890 --> 10:52.110 soll. 10:52.970 --> 10:56.550 Einfaches Beispiel angenommen, wir haben so ein Homomorphismus, der 10:56.550 --> 10:59.690 bildet ab alle Wörter, die sich aus A, B und C irgendwie 10:59.690 --> 11:05.890 zusammensetzen in eine binäre Kodierung, in binäre Folgen, also nach 11:05.890 --> 11:06.930 0, 1 Sternchen. 11:07.810 --> 11:11.830 Das jetzt brauche ich nach dem, was ich vorher gelernt habe, nur noch 11:11.830 --> 11:18.350 festlegen, welches die Urabbilder sind und kann dann diesen durch 11:18.350 --> 11:26.090 diese Urabbildungsdefinition induzierten Homomorphismus hernehmen. 11:26.090 --> 11:31.050 Also nehmen wir her, wir haben diese Abbildung H von A, die sei 1, H 11:31.050 --> 11:34.330 von B gleich 0, 1 und H von C gleich 0, 0, 1. 11:35.270 --> 11:43.910 Man sieht, das ist präfixfrei, also es gibt keine Folge aus Nullen und 11:43.910 --> 11:46.470 Einsen, die jetzt mit einem anderen Kodwort anfängt. 11:46.850 --> 11:50.230 Das ist ganz simpel dadurch gelöst, dass ich erst mal mit Nullen vorne 11:50.230 --> 11:53.990 aufstocke, bis ich dann was richtiges rein tue und das immer länger 11:53.990 --> 11:55.710 werden lasse, bevor die erste 1 kommt. 11:57.050 --> 12:00.210 Und die Dekodierung bildet dann entsprechend jetzt ab von den binären 12:00.210 --> 12:04.410 Wörtern in die Wörter über dem Alphabet, die halt um dieses 12:04.410 --> 12:05.730 Sonderzeichen ergänzt wurden. 12:06.430 --> 12:09.030 Und wenn man dekodieren möchte, klar, man möchte erstmal wieder die 12:09.030 --> 12:12.550 Urbilder zurückhaben, also 0, 0, 0, 1, wenn ich das dekodiere, soll C 12:12.550 --> 12:17.410 rauskommen und wenn ich sowas dekodiere, wie 0, 1, 0, 1, kommt B, B 12:17.410 --> 12:17.730 raus. 12:19.070 --> 12:22.450 Jetzt sieht man auch schon, warum dieses mit dem Präfixfrei so schön 12:22.450 --> 12:24.810 und einfach zu handhaben ist bei der Dekodierung. 12:25.770 --> 12:31.410 Ich habe im Prinzip ja das Problem, wenn ich so einen Kod habe, dass 12:31.410 --> 12:37.010 da ja keine Wortgrenzen drin oder in diesem Fall Zeichengrenzen drin 12:37.010 --> 12:38.010 definiert sind. 12:38.150 --> 12:41.590 Ich habe also ursprünglich mal definiert, die einzelnen Zeichen, auf 12:41.590 --> 12:45.430 was werden die abgebildet und habe jetzt irgendwie ein Wort und will 12:45.430 --> 12:49.230 das abbilden auf ein Wort, das aus mehreren Zeichen besteht bei der 12:49.230 --> 12:49.790 Dekodierung. 12:50.410 --> 12:53.070 Und ich möchte aber nur auskommen mit dem Wissen darüber, wie ich die 12:53.070 --> 12:55.690 einzelnen Zeichen des Alphabets mal abgebildet habe. 12:56.270 --> 13:00.350 Jetzt kann man sich überlegen, wenn man jetzt so einen beliebig langen 13:00.350 --> 13:05.370 Kodwort bekommt, das aus mehreren Zeichen entstanden ist, aus dem 13:05.370 --> 13:08.930 Ursprungsalphabet zusammengesetzt, dann muss ich ja irgendwie wissen, 13:09.170 --> 13:13.770 wo sind da letztendlich Zeichengrenzen, wenn ich nur diese 13:13.770 --> 13:14.650 Informationen habe. 13:14.710 --> 13:17.710 Und das kann ich dadurch machen zum Beispiel, dass alle Kodwörter die 13:17.710 --> 13:18.550 gleiche Länge haben. 13:18.770 --> 13:23.530 Dann brauche ich immer nur zu zählen und weiß dann nach Länge, habe 13:23.530 --> 13:27.330 ich ein neues Urbild oder neues Abbild eines einzelnen Zeichen gehabt, 13:27.470 --> 13:31.630 gemäß der Homomorphismus-Definition kann zurück abbilden oder ich kann 13:31.630 --> 13:33.330 das halt über präfixfreie Kodes machen. 13:33.850 --> 13:37.270 Durch die präfixfreien Kodes weiß ich auch, brauche ich nur von links 13:37.270 --> 13:40.270 nach rechts so lange durchzugehen, meine Zeichen, bis ich ein 13:40.270 --> 13:41.970 vollständiges Kodwort zusammen habe. 13:42.650 --> 13:46.110 Ich weiß, das Kodwort kann dann nicht länger sein, weil sonst wäre das 13:46.110 --> 13:49.490 ja der Präfix eines Kodwortes und das darf es eben nicht sein. 13:50.270 --> 13:53.270 Das heißt also, wenn ich sowas habe wie 0101, gehe ich von links nach 13:53.270 --> 13:53.830 rechts durch. 13:54.030 --> 13:56.430 01, vollständiges Kodwort, weise ich jetzt in B. 13:56.590 --> 13:59.610 Die nächste Folge, 01, vollständiges Kodwort, weise ich jetzt in B, 14:00.010 --> 14:01.290 kann es dekodieren in BB. 14:02.130 --> 14:05.410 Und wenn ich dann zum Beispiel eine einzelne 0 nur bekomme und sonst 14:05.410 --> 14:09.130 nichts, dann weiß ich, das war kein Kodwort. 14:09.390 --> 14:11.950 Das ist nie durch den Homomorphismus festgelegt werden. 14:12.550 --> 14:16.790 Also muss ich das abbilden auf irgendwas, was das ungültige Zeichen 14:16.790 --> 14:20.670 enthält, zum Beispiel nur das ungültige Zeichen alleine. 14:23.730 --> 14:27.070 Dementsprechend, wenn man jetzt diese Dekodierung allgemein für dieses 14:27.070 --> 14:30.170 Beispiel hinschreibt, kann man das eben so hinschreiben, dass man 14:30.170 --> 14:34.810 sagt, man dekodiert ein Wort W und macht folgende Fallunterscheidung. 14:34.890 --> 14:36.850 Falls es Y ist, muss es Y sein. 14:38.310 --> 14:45.990 Falls es mit 1 anfängt und dann kommt noch irgendwas, dann wird die 1 14:45.990 --> 14:49.410 halt auf das A abgebildet und dann muss ich mich um den Rest kümmern. 14:49.870 --> 14:53.990 Falls es halt 01 ist, weise ich es in B und dann den Rest mich darum 14:53.990 --> 14:54.290 kümmern. 14:54.750 --> 14:59.930 Falls es 001 war, kommt das auch wieder auf C abgebildet und ich muss 14:59.930 --> 15:01.010 rekursiv den Rest machen. 15:01.330 --> 15:03.790 Und falls es irgendwas anderes ist, dann ist es etwas, was ich nicht 15:03.790 --> 15:06.310 kenne und dann wird einfach das ungültige Zeichen ausgegeben. 15:07.990 --> 15:11.450 Also so wie wir das für 01, 01 gerechnet haben, kann man das auch hier 15:11.450 --> 15:11.990 für rechnen. 15:12.110 --> 15:15.290 1 ist dann A, bleibt 001, 01 übrig. 15:15.930 --> 15:17.130 Dann muss man gucken. 15:18.930 --> 15:22.550 001 war das C, also AC bleibt 01 übrig. 15:22.690 --> 15:24.910 01 war das B, also kommt ACB raus. 15:25.410 --> 15:26.390 Bleibt nichts mehr übrig. 15:26.970 --> 15:32.850 U von Y war Y, also ACCB konkateniert mit Y, gleich ACB. 15:35.950 --> 15:38.150 Und ich habe Ihnen schon erklärt, warum das geklappt hat. 15:38.210 --> 15:42.010 Das hat eben deshalb geklappt, weil ich von links nach rechts 15:42.010 --> 15:46.290 durchgehen kann und sobald ich ein vollständiges Code worde habe, weiß 15:46.290 --> 15:49.550 ich, es kann kein anderes sein, eben wegen der Präfixeigenschaft. 15:49.770 --> 15:52.410 Also kann ich dann direkt die Abbildung machen. 15:54.330 --> 15:56.950 Oder andersherum, wenn man sich die Definition anschaut, es war in 15:56.950 --> 15:59.390 jeder Zeile klar, welche Definition man anwenden soll. 16:01.090 --> 16:04.270 Man nennt das Ganze auch dann wohldefiniert halt. 16:04.350 --> 16:09.570 Also der Code ist wohldefiniert, wenn ich immer weiß, welche Zeile, 16:09.710 --> 16:11.190 welche Abbildung ich machen kann. 16:11.250 --> 16:13.810 Es gibt keine Ambiguität, es gibt keine Doppeldeutigkeit. 16:14.030 --> 16:18.170 Es ist eindeutig, welche Regel ich bei der Rückabbildung anwenden 16:18.170 --> 16:18.490 soll. 16:20.330 --> 16:23.830 Problematisch wird es halt, wenn der Funktionswert auf mehreren Wegen 16:27.290 --> 16:28.330 gerechnet werden kann. 16:28.450 --> 16:31.530 Also wenn ich in dieser Fallunterscheidung jetzt einen von mehreren 16:31.530 --> 16:33.990 Fällen habe, den ich theoretisch anwenden könnte. 16:34.610 --> 16:37.230 Das muss nicht heißen, dass ich damit nicht dekodieren kann. 16:37.390 --> 16:41.730 Also ich kann eine Funktion machen, die dekodiert, die durchaus nicht 16:41.730 --> 16:44.950 eindeutig ist, welchen Fall ich in dieser Abbildung jetzt anwenden 16:44.950 --> 16:46.610 muss, die mehrere Fälle zulässt. 16:47.030 --> 16:51.310 Nur die muss dann so strukturiert sein, dass, wenn mehrere Fälle 16:51.310 --> 16:55.550 möglich sind, also wenn es mehrere mögliche Rückrechnregeln gibt, dass 16:55.550 --> 16:57.490 trotzdem immer noch dasselbe Ergebnis rauskommt. 16:58.290 --> 17:00.130 Das kann man durchaus definieren, das kann man machen. 17:00.610 --> 17:01.850 Das ist natürlich nicht so schön. 17:02.050 --> 17:05.290 Da ist es schwierig mit umzugehen, da ist es schwierig zu überprüfen, 17:05.350 --> 17:06.570 ob auch das Richtige rauskommt. 17:06.690 --> 17:08.730 Deswegen nennen wir das halt eben nicht wohl definiert. 17:09.490 --> 17:11.110 Oder auch lassen wir besser die Finger von. 17:12.410 --> 17:16.870 Also immer aufpassen, dass entweder wohl definiert ist, dann ist es 17:16.870 --> 17:19.230 schön einfach und funktioniert gut. 17:19.470 --> 17:23.030 Oder dass man halt wirklich aufpasst, dass man auch immer den gleichen 17:23.030 --> 17:23.930 Funktionswert erhält. 17:24.010 --> 17:26.750 Und das zu beweisen ist unter Umständen schwierig. 17:27.490 --> 17:30.710 Und deswegen für präfixfreie Codes kann man es ganz einfach machen, 17:30.830 --> 17:33.750 dass man das eben hinschreibt, also Y auf Y. 17:34.170 --> 17:39.850 Falls W irgendwie ein Codewort ist eines einzelnen Zeichens aus dem 17:39.850 --> 17:42.610 ursprünglichen Alphabet von A, dann wird es gleich direkt dekodiert 17:42.610 --> 17:43.850 und der Rest gemacht. 17:44.510 --> 17:49.130 Und falls es den nicht gibt, dann eben ungültig, nicht dekodierbar. 17:51.110 --> 17:57.130 Ein einfaches Beispiel für so einen präfixfreien Code ist UTF-8. 17:57.230 --> 18:02.570 UTF-8 ist ein Code, um Unicode-Zeichen zu definieren. 18:03.870 --> 18:08.810 Es dient dazu, um halt von der Menge der Zahlen, der Codepoints in 18:08.810 --> 18:15.070 Unicode abzubilden auf halt eine binäre Zahl, die für diesen Codepoint 18:15.070 --> 18:15.430 steht. 18:18.330 --> 18:20.850 Und da macht man das so. 18:21.770 --> 18:24.870 Man hat ja auf der linken Seite nicht nur ein einzelnes Unicode 18:24.870 --> 18:27.930 -Zeichen stehen, sondern eine ganze Folge von Unicode-Zeichen. 18:28.070 --> 18:32.230 Das heißt, ein Wort ist zusammengesetzt aus vielen Unicode-Zeichen und 18:32.230 --> 18:36.110 daraus muss jetzt wieder irgendwie eine ganz große, lange Zahl, eine 18:36.110 --> 18:38.870 Folge von Nullen und Einsen gemacht werden. 18:40.250 --> 18:46.850 Die einfachste Idee wäre nämlich Zeichen gleicher Länge her und 18:46.850 --> 18:50.510 schreibe einfach die Codepoints immer in Felder gleicher Länge 18:50.510 --> 18:51.230 hintereinander. 18:51.470 --> 18:52.690 Das ist ein einfacher Homomorphismus. 18:53.190 --> 18:53.830 Den gibt es auch. 18:53.890 --> 18:56.130 Der nennt sich UTF-16. 18:57.570 --> 19:00.970 Der hat den Nachteil, die Idee dahinter ist, dass man das vielleicht 19:00.970 --> 19:04.030 nicht so geschickterweise macht, weil man eventuell Speicher 19:04.030 --> 19:05.190 verschwindet. 19:05.450 --> 19:08.190 Wenn man sich nämlich anschaut, die Zeichen, die es so in Unicode 19:08.190 --> 19:11.430 gibt, da gibt es viele Zeichen, die werden sehr häufig verwendet. 19:11.650 --> 19:16.310 Zum Beispiel lateinischen Buchstaben oder auch korillische Buchstaben 19:16.310 --> 19:18.910 oder irgendwas, was verwendet wird, um viel Text zu schreiben. 19:19.250 --> 19:21.630 Das ist etwas, das in Unicode sehr häufig vorkommt. 19:21.690 --> 19:24.290 Aber es gibt auch sehr viele Zeichen, die kommen vielleicht nicht so 19:24.290 --> 19:24.850 häufig vor. 19:25.970 --> 19:29.670 Irgendwelche kleinen Emojis oder es gibt Länderflaggen in Unicode. 19:30.250 --> 19:33.810 Es gibt Zeichen, die die Schreibrichtung umdrehen und das ist zum 19:33.810 --> 19:36.250 Beispiel sehr unwahrscheinlich, dass wenn ich mal angefangen habe, von 19:36.250 --> 19:39.110 links nach rechts zu schreiben, dass ich alle zwei Zeichen meine 19:39.110 --> 19:40.790 Schreibrichtung wieder umkehre. 19:40.990 --> 19:43.650 Das mag es mal hin und wieder geben, aber wird meistens nicht 19:43.650 --> 19:44.030 vorkommen. 19:44.430 --> 19:48.030 Und wenn ich dafür immer gleich möglichst breites Feld habe, sodass 19:48.030 --> 19:52.090 ich alle Unicode-Points in die gleiche Feldlänge reinbekomme, dann 19:52.090 --> 19:53.310 verschwende ich halt viel Platz. 19:54.170 --> 19:57.750 Deswegen hat man mit UTF-8 einen präfixfreien Code gemacht. 19:59.090 --> 20:01.510 Und wenn man da reinschaut, da gibt es wieder einen Request for 20:01.510 --> 20:02.030 Comments für. 20:02.230 --> 20:06.510 Das heißt, das Ganze ist auch irgendwie verknüpft mit der Internet 20:06.510 --> 20:08.130 Engineering Taskforce am Ende. 20:08.590 --> 20:13.570 Also es gibt einen Request for Comments, den Nummer 3629, der legt das 20:13.570 --> 20:14.630 fest, wie das funktioniert. 20:14.850 --> 20:21.110 Und UTF-8 ist eben ein präfixfreier Code und die Präfixe hat man, die 20:21.110 --> 20:25.330 Präfixfreiheit hat man dadurch gemacht, dass man so eine Unterteilung 20:25.330 --> 20:28.290 macht der Code-Points, die es so gibt. 20:28.610 --> 20:32.510 Man unterteilt denen in Intervalle die Code-Points und das Ganze hier 20:32.510 --> 20:34.670 in Dexadezimalschreibweisen mal hingeschrieben. 20:35.230 --> 20:39.990 Also für alle Code-Points, die zwischen 0 und 7f liegen, die kriegen 20:39.990 --> 20:41.230 als Präfix erstmal eine 0. 20:42.010 --> 20:47.750 Dann die Code-Points, die zwischen 8 0 und 7ff liegen, die kriegen 20:47.750 --> 20:53.470 halt sozusagen ein zusammengesetztes Wort aus zwei Präfixen. 20:53.550 --> 20:58.630 Die kriegen 1 1 0 und dann wird hinten noch was drangehängt mit 1 0 20:58.630 --> 21:00.250 und so weiter und so fort. 21:00.350 --> 21:05.350 Und diese Anzahl der Bits, aus denen sich das zusammensetzt, die 21:05.350 --> 21:06.990 werden halt immer größer. 21:07.130 --> 21:13.550 Wir sehen halt oben für das erste Intervall brauchen sie nur 8 Bit, um 21:13.550 --> 21:17.210 die zu dekodieren und danach für das zweite Intervall brauchen sie 21:17.210 --> 21:22.750 schon 2 x 2 8 Bit, für das dritte Intervall 3 x 8 Bit und für das 21:22.750 --> 21:24.230 letzte Intervall 4 x 8 Bit. 21:24.730 --> 21:27.330 Das heißt, man kann sich jetzt schon vorstellen, die Zeichen von denen 21:27.330 --> 21:30.090 man erwartet, dass sie häufig vorkommen, die sollten halt in der 21:30.090 --> 21:33.510 ersten ersten Intervall liegen und die, die am wenigsten vorkommen, 21:33.550 --> 21:35.470 die sollten halt im letzten Intervall vorkommen. 21:37.010 --> 21:40.690 Und auch dadurch, dass das jetzt präfixfrei ist, kann man jederzeit 21:40.690 --> 21:43.230 von links nach rechts durchgehen. 21:43.610 --> 21:47.690 Wenn ich eine 0 sehe, dann weiß ich, die nächsten sieben Bits, die 21:47.690 --> 21:50.250 kommen, gehören zu einem Zeichen aus dem ersten Intervall. 21:50.850 --> 21:54.890 Wenn ich 1 1 0 sehe, dann weiß ich, okay, ich muss jetzt die nächsten 21:54.890 --> 21:59.310 5 Bit hernehmen und dann sollte eine 1 0 kommen und ich muss die 21:59.310 --> 22:02.690 nächsten 6 Bit hernehmen und so weiter und so fort. 22:03.830 --> 22:09.870 Das heißt, im Prinzip kann man das so interpretieren, wie viele Folge 22:09.870 --> 22:12.270 -Oktette man noch bekommt. 22:12.450 --> 22:15.630 Also wenn 0 vorne steht als erstes, gibt es kein Folge-Oktett. 22:15.930 --> 22:19.750 Wenn eine 1 1 0 steht, dann besteht das Ganze aus insgesamt zwei 22:19.750 --> 22:20.430 Oktetten. 22:20.510 --> 22:22.190 Das heißt, es kommt noch ein Folge-Oktett. 22:22.610 --> 22:25.690 Dann, wenn ich drei 1 stehen habe, dann besteht das Ganze halt aus 22:25.690 --> 22:26.970 drei Oktetten. 22:27.070 --> 22:30.290 Und wenn ich vier 1 stehen habe, besteht das Ganze aus vier Oktetten. 22:31.410 --> 22:37.010 Und man füllt dann diese Xer, die man hat, die man frei befüllen darf, 22:37.010 --> 22:43.110 dann entsprechend aus, durch die niedrigsten Bits, 22:46.530 --> 22:51.930 wie man sie hätte, als würde man diesen Unicode-Codepoint einfach 22:51.930 --> 22:57.330 binär als Zahl auf der Zweierbasis füllen. 22:58.850 --> 23:00.150 Also, ein einfaches Beispiel. 23:00.310 --> 23:05.270 Angenommen, wir hätten diesen Unicode-Codepoint 2 2 2 b in 23:05.270 --> 23:09.450 Hexadezimalschreibweise geschrieben, das heißt, das Ganze fällt rein 23:09.450 --> 23:13.690 in dieses Intervall von 8 0 0 0 bis 4 mal die F. 23:15.490 --> 23:19.010 Wir wissen also schon mal, dass wir dann durch Nachgucken in der 23:19.010 --> 23:20.370 Tabelle drei Oktette brauchen. 23:20.490 --> 23:24.730 Das erste Oktett fängt mit 1 1 0 an, das zweite Oktett mit 1 0 und das 23:24.730 --> 23:26.870 dritte Oktett auch mit 1 0. 23:29.390 --> 23:34.710 Schauen wir uns an, wenn ich jetzt 2 2 2 b in Dual-Binär-Darstellung 23:34.710 --> 23:42.430 hinschreibe, ist das eben diese Folge aus insgesamt zwei Oktetten oder 23:42.430 --> 23:47.850 vier Blöcken aus vier Bits, also insgesamt 16 Bits. 23:48.690 --> 23:52.850 Und jede Unicode-Zahl, jeden Unicode-Codepoint kann ich immer in 16 23:52.850 --> 23:56.170 Bit darstellen, deswegen funktioniert diese UTF-16-Darstellung, in die 23:56.170 --> 23:58.510 man einfach sagt, alle kriegen die gleiche Länge. 23:59.430 --> 24:02.770 Das würde entsprechend so aussehen, mit 16 Bit dargestellt. 24:03.410 --> 24:05.270 Und jetzt muss man das entsprechend zerlegen. 24:05.430 --> 24:10.330 Ich habe drei Oktette, das letzte Oktett enthält 6 Bits, das heißt die 24:10.330 --> 24:14.550 letzten 6 Bits aus dieser Zahl, die muss ich hochkopieren in das 24:14.550 --> 24:15.550 letzte Oktett. 24:16.370 --> 24:22.670 Die nächsten 6 Bits aus der Zahl muss ich auch wieder hochkopieren in 24:22.670 --> 24:23.690 das zweite Oktett. 24:23.870 --> 24:27.910 Bleiben noch vier Bits übrig, die ich noch nicht hochkopiert habe und 24:27.910 --> 24:29.630 die kommen dann halt in das erste Oktett rein. 24:30.190 --> 24:33.750 Und daraus ergibt sich dann halt die Unicode-Codierung von diesem 24:33.750 --> 24:38.310 Zeichen, das Sie hier entsprechend sehen, mit Präfixen für die Oktette 24:38.310 --> 24:41.810 halt dargestellt und farblich codiert, wo welche Bitfolge herkommt. 24:44.310 --> 24:48.990 Also summa summarum sollten Sie halt wissen, was sind Übersetzungen, 24:50.410 --> 24:54.850 dass man Übersetzungen als Homomorphismen darstellen kann, dass solche 24:54.850 --> 24:58.310 Homomorphismen Codes definieren, dass ich also von Wörtern aus dem 24:58.310 --> 25:01.450 einen über dem einen Alphabet in das andere Alphabet abbilden kann. 25:01.790 --> 25:06.610 Und das worin ich abbilde, das nenne ich halt die Codes, die Abbilder. 25:07.130 --> 25:11.090 Und dass es halt sowas wie präfixfreie Homomorphismen gibt, die man 25:11.090 --> 25:14.030 leicht wieder dekodieren kann, wo man eine einfache 25:14.030 --> 25:15.670 Dekodierungsvorschrift angeben kann. 25:16.290 --> 25:22.530 Und UTF-8 halt als Beispiel eines solchen präfixfreien Codes, der gut 25:22.530 --> 25:26.310 für die Dekodierung von so UTF-8 Zeichen gedacht ist. 25:29.470 --> 25:32.490 Jetzt ist ja bei UTF-8 schon diese Idee angekommen. 25:34.250 --> 25:39.710 Häufige Zeichen sollten möglichst wenig Bits haben, nicht so häufige 25:39.710 --> 25:44.650 Zeichen sollten möglichst lange Bits haben, damit am Ende die Anzahl 25:44.650 --> 25:47.330 der Bits, die ich zur Codierung so eines Zeichen brauche, möglichst 25:47.330 --> 25:47.930 gering wird. 25:48.730 --> 25:52.150 Wenn man sich das anschaut bei Unicode, also ich weiß, ich könnte es 25:52.150 --> 25:53.250 in 16 Bit kodieren. 25:53.390 --> 25:56.850 Ich könnte jedes Unicode Zeichen in 16 Bit kodieren. 25:57.750 --> 26:04.090 Manchmal reichen 8 Bit aus und manchmal brauche ich 4 mal 8 Bit, also 26:04.090 --> 26:05.570 32 Bit deutlich mehr. 26:06.530 --> 26:09.230 Das heißt, damit das funktioniert, wenn man das auf typischen Text 26:09.230 --> 26:12.210 anwendet, sollte natürlich im Mittel weniger als 16 Bit pro Zeichen 26:12.210 --> 26:12.830 rauskommen. 26:13.010 --> 26:16.010 Und das funktioniert halt nur dann, wenn es halt so eine Inbalance 26:16.010 --> 26:19.590 gibt, was die Häufigkeit der einzelnen Zeichen anschaut. 26:20.430 --> 26:24.510 Und wenn man jetzt mit präfixfreien Codes arbeitet, gibt es eine 26:24.510 --> 26:28.690 Codierung, die mir garantiert, dass ich die kürzeste mögliche 26:28.690 --> 26:33.750 präfixfreie Codierung für ein bestimmtes Alphabet finden kann. 26:34.210 --> 26:36.510 Und das ist die sogenannte Huffmann-Codierung. 26:37.530 --> 26:44.910 Mit der Huffmann-Codierung definiert mir ein Homomorphismus, der aus 26:44.910 --> 26:49.930 einem Alphabet abbildet in einen Code, der mir halt durch diesen die 26:49.930 --> 26:52.030 Huffmann -Codierung vorgegeben wird. 26:53.590 --> 26:59.990 Und der, wenn ich die Häufigkeiten kenne, mit der die Zeichen aus dem 26:59.990 --> 27:05.650 Alphabet vorkommen, entsprechend mir den kürzesten, möglichst 27:05.650 --> 27:08.930 präfixfreien Code gibt. 27:09.810 --> 27:14.970 Also formal ist es eine Abbildung von A Sternchen in Z2. 27:15.150 --> 27:18.390 Das heißt, es kommen also Bit Folgen aus Nullen und Einsen heraus, 27:18.550 --> 27:19.630 also nach Z2 Sternchen. 27:19.730 --> 27:20.810 Es ist Epsilon-frei. 27:21.730 --> 27:26.770 Und typischerweise wird so die Huffmann-Codierung auf beliebige Wörter 27:26.770 --> 27:29.390 über dem Alphabet A Sternchen angewandt. 27:30.090 --> 27:33.030 Und Huffmann-Codierung, Huffmann-Codierung kennen Sie alle. 27:33.350 --> 27:38.690 Das ist das, was in die ganzen SIP-Verfahren meistens darauf beruhen. 27:38.830 --> 27:41.450 Also GNU-SIP, B-SIP2 etc. 27:41.910 --> 27:45.750 basieren alle mit kleineren Variationen und Arten und Weisen, wie ich 27:45.750 --> 27:49.190 dann noch ein bisschen Verwaltungsinformationen vor und dahinter 27:49.190 --> 27:51.070 stecke, auf diese Huffmann-Codierung. 27:53.550 --> 27:57.650 Es gibt einen relativ einfachen Algorithmus, wie ich für ein 27:58.470 --> 28:03.390 beliebiges Alphabet, wenn ich die Häufigkeiten der Vorkommen der 28:03.390 --> 28:07.430 Zeichen aus dem Alphabet kenne hinterher, mir diesen Huffmann-Code 28:07.430 --> 28:07.870 berechnet. 28:08.970 --> 28:14.430 Also angenommen, wir hätten ein Wort aus A Sternchen und wir kennen 28:14.430 --> 28:20.470 die Vorkommen aller Zeichen in diesem Wort aus A Sternchen. 28:21.030 --> 28:24.550 Dann kann ich für dieses Wort aus A Sternchen einen Huffmann-Code 28:24.550 --> 28:25.870 berechnen. 28:27.150 --> 28:31.210 Und damit ich das kann, setze ich jetzt einfach voraus, dass in diesem 28:31.210 --> 28:34.910 Wort mindestens jedes Zeichen einmal vorkommt. 28:36.170 --> 28:39.690 Das kann ich machen ohne Beschränkung der Allgemeinheit, O, B, D, A. 28:40.010 --> 28:40.390 Warum? 28:40.910 --> 28:45.130 Angenommen, es gäbe in dem Wort Zeichen, die nicht vorkommen. 28:45.810 --> 28:48.290 Dann kann ich die einfach aus meinem Alphabet rausnehmen und brauche 28:48.290 --> 28:50.370 für die auch entsprechend keinen Code zu haben. 28:50.930 --> 28:53.010 Und wenn ich die aus dem Alphabet rausnehme, dann kann ich wieder 28:53.010 --> 28:56.730 einen Homomorphismus haben, der mir die Dinger nicht abbildet. 28:59.310 --> 29:03.450 Die Konstruktion dieses Huffmann-Codes kann man sich leicht als ein 29:03.450 --> 29:09.170 Baumverfahren vorstellen, indem man aus den Zeichen des Alphabetes 29:09.170 --> 29:13.570 einen Baum klustert und am Ende gibt mir der Baum, den ich da 29:13.570 --> 29:17.110 geklustert habe, entsprechend den Huffmann-Code vor. 29:17.210 --> 29:23.030 Ich kann dann für das Wort aus diesem Baum entsprechend dann den Code 29:23.030 --> 29:29.430 wieder ablesen, indem ich einfach Pfade aus diesem Baum verfolge, mir 29:29.430 --> 29:32.070 gucke, was steht in den Blättern und daraus den Code zusammenbaue. 29:33.830 --> 29:34.710 Einfaches Beispiel. 29:35.430 --> 29:43.730 Es sei dieses Wort gegeben, das besteht aus Zeichen A, B, C, D, E und 29:43.730 --> 29:48.090 ich habe irgendwie gewusst, welche oder ich kann zählen, wie häufig 29:48.090 --> 29:51.150 die Zeichen vorkommen und habe dann diesen Baum berechnet. 29:51.850 --> 29:56.350 Wenn ich den jetzt anwenden will, also angenommen, der Baum ist vom 29:56.350 --> 29:57.890 Himmel gefallen, den hat mir irgendeiner berechnet. 29:57.890 --> 30:01.450 Wenn ich damit jetzt kodieren möchte, das Wort, dann muss ich mir als 30:01.450 --> 30:05.830 erstes anschauen, okay, das A, in welches, in was wird das kodiert und 30:05.830 --> 30:10.670 um das rauszufinden, muss ich den kürzesten Weg von der Wurzel des 30:10.670 --> 30:14.990 Baumes bis zu dem Blatt hinnehmen, das mir das A vorgibt. 30:15.330 --> 30:19.210 Und das ist einfach hier immer runter gehen, immer 0, 0, 0, 30:19.750 --> 30:24.110 dementsprechend ist dreimal die 0 der Code für das A. 30:25.490 --> 30:28.710 Für die Konstruktion des Baumes scheint es wohl wichtig gewesen zu 30:28.710 --> 30:30.830 sein, wie häufig die einzelnen Zeichen vorkommen. 30:31.650 --> 30:34.710 Und da steht dann hier zusätzlich noch an dem Blatt dran, da steht zum 30:34.710 --> 30:38.390 Beispiel dabei für das A, dass das zweimal oben in dieser Wortfolge 30:38.390 --> 30:39.070 vorgekommen ist. 30:39.150 --> 30:43.690 Das B kam zweimal vor, das C kam dreimal vor und das D kam dreimal 30:43.690 --> 30:43.950 vor. 30:46.470 --> 30:49.090 Das F sogar siebenmal und das E fünfmal. 30:49.470 --> 30:53.390 Dementsprechend wird man erwarten, dass für A und B kürzere Codes 30:53.390 --> 30:57.010 gewählt werden als für F und E vielleicht ein kürzerer Code als F und 30:57.010 --> 30:59.930 C und D muss irgendwo zwischen E, F und B liegen. 31:00.370 --> 31:02.950 Und die Frage ist natürlich, kommen die jetzt so viel häufiger vor, 31:03.070 --> 31:05.910 dass ich da einen längeren Code zum Beispiel nehmen kann als für die, 31:05.950 --> 31:09.250 die zweimal vorkommen und ist das, wenn es siebenmal vorkommt, schon 31:09.250 --> 31:13.290 so viel länger, dass ich dafür dann einen kürzeren Code verwenden 31:13.290 --> 31:13.570 kann. 31:14.290 --> 31:18.330 Und wenn ich mir das anschaue, was hinterher rauskommt, die Tiefe, wo 31:18.330 --> 31:21.090 dieses Blatt aufbaut, wenn ich mir also den Baum in so Ebenen 31:21.730 --> 31:25.410 aufteile, die Tiefe, wo dann hinterher das Blatt vorkommt, bestimmt 31:25.410 --> 31:26.810 mir natürlich die Länge des Codes. 31:27.470 --> 31:33.190 Das heißt hier, das F ist auf Ebene 1, 2, kriegt also, muss ich zwei 31:33.190 --> 31:36.050 Kanten verfolgen, kriegt also dementsprechend einen Code der Länge 2, 31:36.210 --> 31:36.990 die 5 auch. 31:37.410 --> 31:40.270 Okay, auch wenn sie unterschiedlich häufig vorkommen, kriegen sie den 31:40.270 --> 31:40.890 gleichen Code. 31:41.270 --> 31:44.690 Und hier A, B, C und D liegen auch auf der gleichen Ebene, auf der 31:44.690 --> 31:47.330 Ebene 3, kriegen also einen drei Längen langen Code. 31:47.830 --> 31:50.590 Und das kann man entsprechend als Tabelle dann auch hinschreiben und 31:50.590 --> 31:52.970 sieht dann, dass man da einen präfixfreien Code hat. 31:54.670 --> 31:58.930 Und die Eigenschaft ist halt, dass das der kürzeste präfixfreie Code 31:58.930 --> 32:01.190 ist, um dieses Wort hinterher zu codieren. 32:03.550 --> 32:07.110 Wenn man das Ganze konstruieren will, geht man von unten nach oben 32:07.110 --> 32:07.390 vor. 32:07.690 --> 32:09.850 Man baut diesen Baum von unten nach oben auf. 32:10.510 --> 32:14.190 Man schreibt sich erstmal die Blätter hin, mit den einzelnen Zeichen 32:14.190 --> 32:18.170 und zusammen mit ihrer Häufigkeit, wie sie in diesem Wort vorkommen. 32:19.630 --> 32:22.430 Wenn man das jetzt formal hinschreibt, dann definiert man sich halt 32:22.430 --> 32:23.010 Mengen. 32:23.290 --> 32:29.770 Man kann sozusagen jede Ebene von Knoten auf diesem Baum kann man als 32:29.770 --> 32:30.790 Menge sich auffassen. 32:30.890 --> 32:36.150 Und diese Menge sind halt Tupel aus dem Zeichen, das codiert werden 32:36.150 --> 32:38.190 soll und der Häufigkeit, wie es vorkommt. 32:38.430 --> 32:41.890 Und ganz am Anfang M0 enthält halt die Menge aller Blätter. 32:42.090 --> 32:45.210 Das heißt, da unten gibt es nur einzelne Zeichen. 32:45.670 --> 32:49.410 Also haben wir dementsprechend eine Menge M0, die halt aus den Tupeln 32:49.410 --> 32:49.710 besteht. 32:49.850 --> 32:53.410 Das A kam zweimal vor, das B kam zweimal vor, das C dreimal, das D 32:53.410 --> 32:57.310 dreimal, das E fünfmal und das F siebenmal. 32:58.230 --> 33:02.510 Und jetzt fange ich an, neue Mengen zu konstruieren, eine Menge M1, 33:02.650 --> 33:07.810 eine Menge M2 etc., indem ich anfange, diese Tupel, die in dieser 33:07.810 --> 33:09.890 Menge M0 sind, zusammenzulegen. 33:11.570 --> 33:15.690 Also Anfang jetzt schon mal schön hingeschrieben, weil das ist 33:15.690 --> 33:17.390 natürlich ein bisschen gemogelt hier. 33:17.790 --> 33:19.470 Ich habe jetzt mal diese Elemente da hingeschrieben. 33:19.590 --> 33:22.450 Das sind die, wie sie vorher in dem Baum drin waren und die sind schon 33:22.450 --> 33:25.210 so angeordnet, dass sie hinterher auf der richtigen Ebene des Baumes 33:25.210 --> 33:25.530 liegen. 33:26.210 --> 33:28.610 Das weiß ich zu dem Zeitpunkt noch nicht, auf welcher Ebene die liegen 33:28.610 --> 33:28.870 werden. 33:28.990 --> 33:31.890 Eigentlich stehen die alle erstmal gleichberechtigt nebeneinander, 33:32.310 --> 33:34.870 aber da wir das Ergebnis schon kennen, haben wir halt gemogelt und die 33:34.870 --> 33:37.770 schon mal so schön hingeschrieben, dass man sie auch hinterher schön 33:37.770 --> 33:38.630 sich anschauen kann. 33:40.170 --> 33:43.210 Was ich jetzt mache ist, wenn ich so eine Menge M0 habe, dann fange 33:43.210 --> 33:47.870 ich an, Tupel zusammenzulegen und zwar die Tupel mit den kleinsten 33:47.870 --> 33:48.470 Häufigkeiten. 33:48.890 --> 33:53.610 Das heißt, ich nehme mir das Tupel her mit der kleinsten Häufigkeit 33:53.610 --> 33:57.770 und dann das Tupel mit der zweitkleinsten Häufigkeit und lege die 33:57.770 --> 33:58.450 beiden zusammen. 33:59.610 --> 34:02.350 Kann durchaus sein, dass diese Zusammenlegung nicht eindeutig ist. 34:02.770 --> 34:06.290 Kann ja sein, dass ich zum Beispiel fünf Tupel habe, die alle mit der 34:06.290 --> 34:07.650 gleichen Häufigkeit vorkommen. 34:08.410 --> 34:11.790 Wenn das der Fall ist, wähle ich mir halt eine beliebige 34:11.790 --> 34:14.670 Zusammenlegung von diesen beiden Tupeln zusammen. 34:15.210 --> 34:18.490 Ich lege halt immer zwei Tupel zusammen und zwar die mit den kleinsten 34:18.490 --> 34:22.050 Häufigkeiten und wenn das nicht eindeutig ist, kann ich rein zufällig 34:22.050 --> 34:23.570 wählen, welche ich da zusammenlege. 34:24.390 --> 34:27.170 Und was ich jetzt mache ist, wenn ich dieses Zusammenlegen als 34:27.170 --> 34:30.350 Mengenoperationen hinschreibe, dann ist das nichts anderes, als dass 34:30.350 --> 34:33.730 ich aus der Menge MI die beiden Tupel mit den kleinsten Häufigkeiten 34:33.730 --> 34:39.650 entferne und neues Tupel reinmache, das jetzt aus den Zeichen besteht, 34:40.150 --> 34:43.670 die da zusammengelegt wurden und zwar egal in welcher Reihenfolge. 34:44.030 --> 34:45.830 Die werden einfach als Menge hingeschrieben. 34:45.970 --> 34:49.450 Das heißt, interessiert mich keine Reihenfolgenoperationen und die 34:49.450 --> 34:54.790 Häufigkeit dieser neu gebildeten Zeichenmenge sei einfach die Addition 34:54.790 --> 34:57.790 der Häufigkeiten der jenen Tupel, die ich da zusammengelegt habe. 34:59.630 --> 35:04.210 Wenn ich das im Grafen mache, also meine ursprüngliche Menge, wenn ich 35:04.210 --> 35:08.810 das im Grafen mache, dann markiere ich mir einfach die beiden mit den 35:08.810 --> 35:13.090 kleinsten Häufigkeiten, also hier zwei A und zwei B und lege die 35:13.090 --> 35:19.490 zusammen zu einem neuen Knoten mit A, B und der Häufigkeit 4. 35:22.050 --> 35:25.350 Diese Information darüber, dass ich da A, B eigentlich zusammengelegt 35:25.350 --> 35:29.210 habe, die kann ich an der Stelle schon vergessen, weil ich jetzt keine 35:29.210 --> 35:29.870 Blätter mehr habe. 35:29.970 --> 35:32.950 Wenn ich hinter den Code bestimmen will, dann arbeite ich mich immer 35:32.950 --> 35:36.930 bis zu den Blättern vor und lese bei den Blättern dann erst ab, wie 35:36.930 --> 35:37.850 ich codieren muss. 35:39.050 --> 35:41.250 Das heißt, die Information darüber, dass ich jetzt A und B 35:41.250 --> 35:44.430 zusammengelegt habe und dass da 4 rauskommt, ist eigentlich völlig 35:44.430 --> 35:44.870 egal. 35:45.930 --> 35:49.350 Hat ja auch in der Zusammenlegung keinerlei Bedeutung. 35:49.450 --> 35:52.710 Also wenn ich die Zeichen zusammenlege, hinterher neue Zeichen 35:52.710 --> 35:57.910 zusammenlege, dann gucke ich mir ja gar nicht an, welche Zeichen da 35:57.910 --> 35:58.270 drin stehen. 35:58.330 --> 36:01.550 Das Einzige, worauf ich meine Entscheidung basiere, ist die 36:01.550 --> 36:02.650 Häufigkeiten der Tupel. 36:03.990 --> 36:08.690 Muss man aber eine Sache beachten, warum ich da trotzdem nur 4 36:08.690 --> 36:15.590 hinschreiben kann, weil ich lege ja zusammen und rein formal bilde ich 36:15.590 --> 36:20.010 hier die Vereinigung von den Zeichen, die ich da zusammengelegt habe. 36:21.150 --> 36:24.550 Und würde ich jetzt an irgendeiner Stelle, wenn ich diese neuen Mengen 36:24.550 --> 36:29.810 bilde, da eine Vereinigung kriegen, plötzlich zwei Tupel kriegen, die 36:29.810 --> 36:32.690 dasselbe sagen, also gleiche Häufigkeit haben und gleiche 36:32.690 --> 36:37.470 Zeichenmenge, dann würden die ja in dieser Menge zu einem Knoten am 36:37.470 --> 36:38.330 Ende zusammenfallen. 36:38.450 --> 36:39.390 Warum kann das nicht passieren? 36:41.890 --> 36:45.050 Warum kann das nicht passieren, dass ich da in dieses Problem 36:45.050 --> 36:48.470 reinlaufe, sondern warum kann ich da einfach, wenn ich das 36:48.470 --> 36:49.670 hinschreibe, mir das vergesse? 36:51.030 --> 36:54.750 Da könnte man sich jetzt einen kleinen Beweis überlegen, warum es nie 36:54.750 --> 36:58.110 sein kann, dass bei diesem Zusammenlegen zweimal dasselbe rauskommt. 36:58.810 --> 37:01.910 Und das hat einfach damit zu tun, ich habe ja unten in den Blättern 37:01.910 --> 37:03.850 unterschiedliche Zeichen stehen. 37:04.050 --> 37:05.830 Und jetzt lege ich immer zusammen und zusammen. 37:06.490 --> 37:08.630 Und wenn ich dann plötzlich auf irgendeiner Ebene zwei 37:08.630 --> 37:11.490 Zusammenlegungen hätte, die aus dem gleichen Zeichen besteht, dann 37:11.490 --> 37:13.450 müsste ich ja irgendwo bei der Ebene vorher schon mal was 37:13.450 --> 37:18.430 zusammengelegt haben, was aus Zeichen liegt, wo ich parallel selbe 37:18.430 --> 37:19.730 Zeichen zusammengelegt habe. 37:19.770 --> 37:22.950 Und das würde ja bedeuten, dass ich unten auf der Blattebene auch 37:22.950 --> 37:25.570 dasselbe Zeichen mehrmals haben müsste mit unterschiedlichen 37:25.570 --> 37:26.170 Häufigkeiten. 37:26.650 --> 37:29.730 Und das kann gemäß der Definition von M0 eben nicht der Fall sein. 37:29.830 --> 37:33.310 Könnte man also zum Beispiel durch vollständige Induktion beweisen, 37:33.490 --> 37:34.290 dass das nicht passiert. 37:35.670 --> 37:38.410 Gut, also die beiden werden zusammengelegt zu einer 4. 37:38.870 --> 37:42.390 Danach bleiben hier unten 3c und 3d übrig. 37:42.530 --> 37:45.530 Die werden zusammengelegt, haben Häufigkeit 6. 37:46.590 --> 37:52.870 Dann 4, muss ich mir das anschauen, sind jetzt noch übrig 4, 5e, 6, 37:52.970 --> 37:53.390 7e. 37:53.730 --> 37:55.470 Die hier unten wurden immer herausgenommen. 37:56.190 --> 37:59.890 Gut, 4 und 5 sind diejenigen, die werden zusammengelegt. 38:00.170 --> 38:01.670 Dann haben wir 9, 6 und 7. 38:01.790 --> 38:04.670 Also werden 6 und 7 zusammengelegt und dann werden noch 9 und 13 38:04.670 --> 38:05.390 zusammengelegt. 38:05.910 --> 38:15.130 Und ganz am Ende habe ich dementsprechend den einen einzelnen Knoten, 38:15.170 --> 38:16.790 der ist der Wurzelknoten meines Baumes. 38:17.610 --> 38:20.610 Und jetzt muss ich nur noch eines machen, damit ich auch hinterher mit 38:20.610 --> 38:21.850 diesem Baum kodieren kann. 38:22.290 --> 38:23.890 Ich muss den Kanten Namen geben. 38:25.330 --> 38:28.690 Und den Kanten gebe ich halt immer einen Namen, indem ich zum Beispiel 38:28.690 --> 38:31.930 sage, die Kante, die den linken Sohn oder den linken Nachfolger 38:31.930 --> 38:35.010 betrifft, kriegt halt die 0 und die rechte Kante kriegt halt eine 1. 38:36.090 --> 38:40.530 Wenn ich die so beschrifte, dann kann ich eben für jedes Zeichen, was 38:40.530 --> 38:45.930 ich habe, den Huffman-Code ablesen, indem ich jetzt halt in diesem 38:45.930 --> 38:47.650 Baum den kürzesten Pfad nehme. 38:48.150 --> 38:51.130 Und den kürzesten Pfad, das muss halt immer logischerweise ein Pfad 38:51.130 --> 38:58.590 sein, der nicht einen Schritt aus der Ebene zurück macht, sondern der 38:58.590 --> 39:00.470 direkt immer nur in den Baum tiefer geht. 39:01.030 --> 39:03.110 Den kann ich natürlich einfach dadurch finden, indem ich von unten 39:03.110 --> 39:06.990 nach oben hochgehe, indem ich halt unten vom Blatt sozusagen mir 39:06.990 --> 39:10.390 rückwärts den Code aufbaue und immer in Richtung Wurzel gehe und dabei 39:10.390 --> 39:13.650 mir merke, welche Kanten ich mit welcher Beschriftung durchlaufen 39:13.650 --> 39:13.970 habe. 39:15.850 --> 39:17.790 Genau, das sind halt je nach Rechtsführung. 39:20.430 --> 39:23.870 Und ja, das ist halt formal, es ist eine Konkatenation, kann ich dann 39:23.870 --> 39:24.630 entsprechend machen. 39:27.550 --> 39:30.450 Das ist halt der Baum, der am Ende dann rausgekommen ist, das ist der 39:30.450 --> 39:33.710 Baum von vorhin, den wir uns gesehen haben mit diesem prefixfreien 39:33.710 --> 39:34.450 Homomorphismus. 39:37.050 --> 39:39.670 Jetzt kann man sich schon leicht überlegen, dass so ein Huffman-Code 39:39.670 --> 39:41.410 im Allgemeinen nicht eindeutig ist. 39:42.070 --> 39:46.930 Zum einen kann es durchaus manchmal Mehrdeutigkeiten geben, welche 39:46.930 --> 39:48.370 Sachen ich zusammenlege. 39:49.870 --> 39:54.510 Also kann, wenn ich halt Tupel habe mit gleicher Häufigkeit und habe 39:54.510 --> 39:58.090 vier Stück davon, dann habe ich ganz viele verschiedene Möglichkeiten, 39:58.810 --> 40:01.090 zwölf Möglichkeiten, wie ich die zusammenlegen kann. 40:02.410 --> 40:05.570 Dementsprechend kommt natürlich auch ein unterschiedlicher Huffman 40:05.570 --> 40:10.070 -Code raus oder ganz einfach, ich kann einfach die Labels an den 40:10.070 --> 40:11.390 Kanten vertauschen. 40:11.470 --> 40:13.830 Ich kann also, statt links eine 0 zu schreiben, kann ich eine links 40:13.830 --> 40:15.070 eine 1 schreiben und rechts eine 0. 40:15.350 --> 40:19.890 Kommt formal ein anderer Huffman-Code raus, aber letztendlich von der 40:19.890 --> 40:21.430 Länge her kommt immer dasselbe bei raus. 40:23.470 --> 40:26.310 Jetzt kann man das Ganze noch ein bisschen vereinfachen. 40:26.910 --> 40:32.870 Zum Beispiel, wenn wir an geschriebenen Text denken, dann ist es 40:32.870 --> 40:39.190 vielleicht nicht sinnvoll, dass man immer einzelne Zeichen kodiert, 40:39.450 --> 40:43.170 sondern man wird sicherlich feststellen, bei längeren Texten werde ich 40:43.170 --> 40:46.490 vielleicht so Häufigkeiten nicht auf den Buchstaben eines Alphabets 40:46.490 --> 40:51.650 bekommen, sondern vielleicht bekomme ich Häufigkeiten bezüglich von 40:51.650 --> 40:56.010 Tupeln aus Buchstaben, also zweierfolgen aus Buchstaben oder 40:56.010 --> 40:57.710 vielleicht aus dreierfolgen aus Buchstaben. 40:57.890 --> 41:02.050 Sprich, ich gucke mir nicht einzelne Zeichen aus dem Alphabet an, 41:02.150 --> 41:05.190 sondern ich gucke mir immer ganze Blöcke einer fixen Länge aus dem 41:05.190 --> 41:08.990 Alphabet an, aus denen dann hinterher die Wörter aufgebaut werden und 41:08.990 --> 41:11.070 kann daraus eine Kodierung machen. 41:11.410 --> 41:14.610 Ich baue mir mit anderen Worten so eine Art neues Alphabet her, das so 41:14.610 --> 41:18.550 aus Blöcken fixer Länge besteht, gucke mir deren Häufigkeiten an und 41:18.550 --> 41:21.510 mache dann für diese Blöcke entsprechend eine Kodierung. 41:23.590 --> 41:26.890 Formal kann man das halt zu einem neuen induzierten Homomorphismus 41:26.890 --> 41:31.010 erweitern, indem ich mir halt Wörter der fixen Länge B aus dem 41:31.010 --> 41:34.390 Alphabet hernehme und dieser Homomorphismus, dieser induzierte 41:34.390 --> 41:42.750 Homomorphismus dann von Wörtern der Länge B abbildet nach Wörtern aus 41:42.750 --> 41:44.110 dem Alphabet Groß B. 41:46.670 --> 41:51.710 Also wichtig, Hoffman Codes, kürzester möglicher Präfix freier Code. 41:52.910 --> 41:56.030 Gibt einen Algorithmus, wie man diesen Baum bestimmen kann und was 41:56.030 --> 42:00.150 dann halt B-Zip und G-Zip noch machen ist, halt die Magie ist da drin, 42:00.210 --> 42:03.890 wie lang mache ich die Länge des Blockes, zum Beispiel habe ich noch 42:03.890 --> 42:05.830 irgendwelche Heuristiken und natürlich auch die ganzen 42:05.830 --> 42:07.030 Verwaltungsinformationen. 42:07.090 --> 42:10.970 Wenn ich eine beliebige Datei mit G-Zip kodiere, dann muss ich 42:10.970 --> 42:14.010 natürlich auch den Code, den ich jetzt verwendet habe, irgendwie mit 42:14.010 --> 42:17.010 übertragen, mit abspeichern in der Datei, damit ich, wenn ich 42:17.010 --> 42:21.050 hinterher dekodiere, entsprechend diese Tabelle des Codes vorliegen 42:21.050 --> 42:21.210 habe. 42:21.310 --> 42:23.030 Das muss also zum Beispiel rein in die Datei. 42:23.530 --> 42:27.090 Oder ich muss halt auch irgendwie kodieren, wann ist sozusagen das, 42:27.270 --> 42:30.670 was ich dekodieren soll in der Datei, diese Nutzlast, wann ist die zu 42:30.670 --> 42:30.930 Ende. 42:31.790 --> 42:35.890 Und da ist zum Beispiel bei G-Zip, wenn ich das richtig weiß, 0 42:35.890 --> 42:37.030 terminiert. 42:37.150 --> 42:42.510 Das heißt, wenn nur Nullen kommen, irgendwo am Ende, dann ist dieser 42:42.510 --> 42:43.150 Code vorbei. 42:43.410 --> 42:44.710 Und solche Sachen gibt es da halt. 42:46.550 --> 42:48.090 Da kann man lustige Sachen mitmachen. 42:49.530 --> 42:53.570 Insbesondere kann man dann Huffman-Codes finden, die dann halt 42:53.570 --> 42:55.130 Primzahlen entsprechen. 42:55.330 --> 42:59.930 Und dann kann man Dateien als Primzahl kodieren und lauter verrückte 42:59.930 --> 43:01.370 Sachen, die man damit auch noch machen kann. 43:02.370 --> 43:06.610 Nur damit es in so eine Größenordnung kam, wenn man sowas in G-Zip, so 43:06.610 --> 43:09.390 wie in G-Zip der Huffman-Code implementiert ist, mit der Blocklänge, 43:09.450 --> 43:11.450 die die verwenden und so weiter und so fort. 43:11.870 --> 43:15.470 Wenn man das so als auf durchschnittlich geschriebenen Text anwendet 43:15.470 --> 43:19.270 und man dann jetzt nicht die, zum Beispiel ASCII-Zeichen mit 8 oder 7 43:19.270 --> 43:23.010 Bit fixer Länge kodiert, sondern diesen Huffman-Code berechnet, ist 43:23.010 --> 43:26.550 Kompressionsverhältnis so Pi mal Daumen ungefähr 1 zu 10. 43:27.230 --> 43:30.490 Das heißt, Sie können mit der Präfix freier Code dieser Datei mit 43:30.490 --> 43:34.330 hinterher nur ungefähr die Größe 1 Zehntel haben, der ursprünglichen 43:34.330 --> 43:37.750 naiven Kodierung, wenn man immer Codes gleicher Länge verwendet. 43:38.730 --> 43:43.410 Wir verlassen jetzt mal zur Abwechslung so ein bisschen im Bereich der 43:43.410 --> 43:44.970 theoretischen Informatik. 43:45.570 --> 43:51.910 Und wir gehen jetzt in den 20-Prozent-Teil der technischen Informatik, 43:52.470 --> 43:54.650 den Sie hier in der Vorlesung auch bekommen werden. 43:58.010 --> 44:03.910 Sie werden noch hinterher in Rechnerorganisationen und in technischer 44:03.910 --> 44:08.430 Informatik 1 entsprechend das Ganze noch vertieft kennenlernen, aber 44:08.430 --> 44:11.470 hier lernen Sie so ein bisschen die Grundlagen kennen, also so die 44:11.470 --> 44:15.250 abstrakten Konzepte, die Sie dann mehr und mehr ausarbeiten werden. 44:16.310 --> 44:21.090 Und weil es halt Grundbegriff der Informatik ist, so ein bisschen 44:21.090 --> 44:24.170 werden wir natürlich immer noch den Verweis machen auf die 44:24.170 --> 44:26.110 theoretische Informatik. 44:26.470 --> 44:29.750 Aber Sie werden auch sehen, dass Sie auch hier das Ganze 44:29.750 --> 44:32.770 praxisrelevant anwenden wollen, wenn Sie nämlich hinterher echt 44:32.770 --> 44:35.750 anfangen wollen, echte Rechner zusammenzusetzen. 44:36.710 --> 44:38.810 Und wir machen Informationsverarbeitung. 44:39.370 --> 44:44.210 Das heißt, wir verarbeiten Daten und Sie hatten schon gesehen, eines 44:44.210 --> 44:49.270 am Anfang der Vorlesung, Sie haben Nachrichten, die Sie persistent 44:49.270 --> 44:57.030 machen, entweder persistent in der Zeit oder persistent über die 44:57.030 --> 44:59.590 Strecke hinweg, über die Distanz hinweg. 44:59.690 --> 45:02.350 Das eine war die Übertragung, das andere war die Speicherung. 45:02.930 --> 45:06.130 Und damit Sie Daten speichern können, brauchen Sie jetzt erstmal 45:06.130 --> 45:09.650 irgendwie einen Speicher, in dem Sie Daten ablegen können. 45:10.770 --> 45:14.250 Und wenn Sie Speicher, irgendwelche Sachen ablegen wollen und 45:14.250 --> 45:19.950 speichern wollen, dann müssen Sie als erstes wissen, wie groß ist das 45:19.950 --> 45:21.770 überhaupt, was ich im Speicher ablege. 45:23.370 --> 45:26.630 Da kommt dann der Begriff Bit und Byte zum Beispiel ins Spiel. 45:29.170 --> 45:31.770 Sie alle haben ja sicherlich wahrscheinlich schon mal einen Rechner 45:31.770 --> 45:34.210 gekauft und haben auch geguckt, wie viel Hauptspeicher der hat. 45:35.010 --> 45:43.270 Und allgemein, wenn Sie jetzt so Daten abspeichern im Binärsystem, so 45:43.270 --> 45:47.890 wie das im Rechner gemacht wird, einer bestimmten Länge, dann können 45:47.890 --> 45:50.950 Sie ja sicherlich angeben, was so da die Größenordnungen sind. 45:51.230 --> 45:54.950 Und wenn ich so 8 Bit zusammensetze, was für eine Größe hat das? 45:56.170 --> 45:57.870 Das ist ein Byte, das kennen wir noch. 45:58.870 --> 46:03.230 Wenn ich jetzt 1024 Bytes habe, wie nenne ich das Ganze? 46:04.510 --> 46:06.770 Noch mal laut, ein Kilobyte. 46:06.830 --> 46:09.570 Und wie nennen Sie sowas, wenn Sie 1024 Kilobyte haben? 46:10.990 --> 46:13.170 Und was nennen Sie 1024 Megabyte? 46:13.790 --> 46:15.890 Und 1024 Gigabyte? 46:16.650 --> 46:18.630 Und 1024 Terabyte? 46:19.550 --> 46:21.650 Und 1024 Petabyte? 46:22.650 --> 46:24.390 Und 1024 Exabyte? 46:29.230 --> 46:30.470 Und wissen Sie sowas? 46:31.950 --> 46:33.130 Sie haben alle keine Ahnung. 46:35.690 --> 46:41.010 Wären Sie in den USA und würden so Ihren Speicher angeben, Ihnen würde 46:41.010 --> 46:42.550 das letzte Hemd weggeklagt. 46:42.630 --> 46:45.670 Sie wären ein armer Mann, wenn Sie eine Firma hätten und so und so 46:45.670 --> 46:52.970 viel sagen, hier 1024 Gigabyte, 1024 Byte ist ein Kilobyte. 46:53.270 --> 46:55.430 Sie wären ein armer Mann, Ihnen würde man den Hintern wegklagen. 46:56.570 --> 46:57.010 Warum? 46:58.130 --> 46:59.250 Weil das nämlich nicht stimmt. 47:00.070 --> 47:03.950 Also, das Bit besteht aus den Zeichen 0 und 1. 47:04.390 --> 47:06.350 Da werden Sie noch ganz viel hören. 47:06.650 --> 47:10.350 Und wenn man heute 8 Bits zusammennimmt, dann nennt man das ein Byte. 47:11.270 --> 47:13.630 Früher hat man das nicht Byte genannt, früher hat man das ein Oktett 47:13.630 --> 47:14.030 genannt. 47:15.090 --> 47:17.230 Und es gibt halt Abkürzungen für einen Bit. 47:18.350 --> 47:19.870 Schreibt man direkt Bit hin. 47:20.070 --> 47:22.950 Manchmal sieht man B, aber B ist halt blöd, weil das eigentlich schon 47:22.950 --> 47:24.890 eine bestimmte Flächeneinheit benutzt. 47:25.210 --> 47:27.130 Für das Byte nimmt man das große B. 47:28.530 --> 47:30.470 Abfall hat eigentlich auch schon eine andere Bedeutung, ist eigentlich 47:30.470 --> 47:33.190 ein Bell, aber nun gut, die Informatik hat sich halt durchgesetzt und 47:33.190 --> 47:34.750 für das Oktett nehmen wir das kleine O. 47:36.810 --> 47:42.010 Und jetzt kommen die Größenpräfixe, wenn wir in größere Räume 47:42.010 --> 47:42.610 reingehen. 47:43.830 --> 47:50.510 Also, früher gab es Hauptspeicher, der war sehr klein, da wenn man ein 47:50.510 --> 47:51.850 paar hundert Bits hatte, war das gut. 47:52.670 --> 47:56.370 Heute hat man, da konnte man das ganze noch in Bytes angeben und zwar 47:56.370 --> 47:58.730 ohne irgendeinen Präfix zu verwenden, das war so klein. 47:59.330 --> 48:02.850 Heutzutage haben Sie Hauptspeicher, der ist sowas wie 2 auf 32 Bytes 48:02.850 --> 48:06.650 hoch und Festplatten, die haben sowas wie eine Milliarde, muss ich 48:06.650 --> 48:11.790 aufpassen, eine Trilliarde, Moment, eine Trilliarde Bytes. 48:12.990 --> 48:15.090 Wie groß ist das, eine Trilliarde Bytes? 48:18.430 --> 48:20.390 Und welches Präfix verwenden Sie? 48:20.850 --> 48:23.050 Verwendet für Ihr Festplattenhersteller. 48:24.750 --> 48:28.750 Der sagt, das ist ein Terabyte, wenn das eine Trilliarde, habe ich es 48:28.750 --> 48:30.330 richtig, das müsste eine Trilliarde sein, oder? 48:33.010 --> 48:34.890 Ist das nur eine Milliarde? 48:35.270 --> 48:35.670 Ne, Moment. 48:36.650 --> 48:39.770 Das sind tausend, das ist die Million, das wäre die Mehrheit, ist das 48:39.770 --> 48:40.410 keine Trilliarde? 48:43.450 --> 48:46.550 Das ist Trillionen, ja Entschuldigung, das ist eine Trillionen, mein 48:46.550 --> 48:46.830 Fehler. 48:48.270 --> 48:52.450 Genau und dann sehen Sie schon den Unterschied, bei den Festplatten, 48:52.670 --> 48:56.350 da nimmt man keine Zweierpotenzen und dann ist das wirklich sowas wie 48:56.350 --> 48:58.350 ein Terabyte und Gigabyte und Megabyte. 48:58.790 --> 49:01.970 Wenn man Zweierpotenzen hat, dann nimmt man was anderes. 49:03.270 --> 49:06.650 Warum hatte man da mit Kilobyte und so weiter angefangen? 49:06.810 --> 49:10.490 Naja, das kommt eigentlich aus dem Dezimalsystem, da hatte man zum 49:10.490 --> 49:14.290 Beispiel für Meter gibt es den Kilometer und dann für Sekunden gibt es 49:14.290 --> 49:18.330 die Mikrosekunde, bei Leistungseinheiten gab es dann halt Megawatt, 49:18.430 --> 49:21.350 Gigawatt, Terawatt und so weiter, aber das basiert alles auf dem 49:21.350 --> 49:27.890 Zehner -Logarithmus, also auf Größenordnungen, die mit Zehnerpotenzen 49:27.890 --> 49:28.450 ansteigen. 49:32.710 --> 49:37.530 Das sind also, das ist die Tabelle bei den Zehnerpotenzen und die 49:37.530 --> 49:40.510 nehmen wir halt fälschlicherweise immer auch für die Zweierpotenzen, 49:40.650 --> 49:41.730 aber eigentlich darf man es nicht. 49:41.830 --> 49:44.170 Es gibt eine Norm, die das festlegt und es ist eigentlich auch 49:44.170 --> 49:45.510 wichtig, dass man das unterscheidet. 49:46.330 --> 49:49.770 Das hier ist das Ganze nochmal für die Zehnerpotenzen aufgeschlagen, 49:50.230 --> 49:53.170 also vorne geht das halt immer, wird das immer kleiner, 49:53.430 --> 49:58.210 Millimikronanopikofemtoato und entsprechend wird es immer größer, bei 49:58.210 --> 50:02.570 1000 fängt es mit Kilo an, Mega, Giga, Tera, Peta, Hexa und mehr weiß 50:02.570 --> 50:03.170 ich leider auch nicht. 50:03.810 --> 50:06.550 Und dann kann man natürlich dann noch so Scherzsachen machen, dass man 50:06.550 --> 50:07.630 die Sachen zusammensetzt. 50:08.530 --> 50:11.610 Zum Beispiel gibt es dann so eine Längeneinheit, die heißt ein 50:11.610 --> 50:16.250 Atopasec, das ist die von dem Herrn Worsch, die Lieblingseinheit, gibt 50:16.250 --> 50:17.630 auch andere, die finden das ganz nett. 50:18.410 --> 50:21.090 Kann sich irgendeiner was unter einem Atopasec vorstellen? 50:22.070 --> 50:22.770 Wo sind die Physiker? 50:22.850 --> 50:24.530 Die sind natürlich jetzt rausgelaufen, das ist doof. 50:26.270 --> 50:27.810 Wer weiß, was ein Pasec ist? 50:30.430 --> 50:30.670 Genau, 50:33.890 --> 50:36.310 das ist also die Einheit, eine astronomische Einheit. 50:36.930 --> 50:38.970 Jetzt muss man wissen, was eine astronomische Einheit ist, das machen 50:38.970 --> 50:39.370 wir gleich. 50:39.750 --> 50:43.010 Die astronomische Einheit, wenn man jetzt guckt, dass die Erde 50:43.010 --> 50:48.790 sozusagen um eine astronomische Einheit sich verschoben hat, dann kann 50:48.790 --> 50:53.350 man sich den Winkel anschauen von dem entfernten Planeten und unter 50:53.350 --> 50:56.350 welchem Winkel sich sozusagen das Ganze dann verschoben hat. 50:57.750 --> 51:01.050 Und zwar auf dieser, naja, Kreisbahn ist es ja nicht, Ellipse ist es, 51:01.590 --> 51:06.450 also der Winkel, den man hat, der hat sich dann um eine Bogensekunde 51:06.450 --> 51:06.910 verschoben. 51:07.130 --> 51:10.610 Wenn man halt eine astronomische Einheit ist und dann muss man, damit 51:10.610 --> 51:13.730 man das so sieht, halt entsprechend ein Pasec weit sein. 51:13.970 --> 51:17.550 Astronomische Einheit ist der mittlere Abstand der Erde von der Sonne, 51:17.910 --> 51:18.190 richtig? 51:18.970 --> 51:21.490 Genau, das ist dann die astronomische Einheit. 51:21.890 --> 51:24.570 Kann man sich ungefähr vorstellen, wenn man das jetzt mal in Metern 51:24.570 --> 51:26.710 oder so ausdrückt, was so ein Pasec ist? 51:29.530 --> 51:36.510 Pasecs sind gerade ungefähr 3 x 10 und 18 Meter, ist also sehr lang. 51:37.070 --> 51:41.450 3 x 10 und 18 Zentimeter, Entschuldigung, 3 x 18 Zentimeter, das ist 51:41.450 --> 51:42.430 ungefähr ein Pasec. 51:43.410 --> 51:47.670 Wenn man dann ein Atopasec hat und das jetzt in Zentimeter umrechnen, 51:47.730 --> 51:52.290 dann muss man halt Ato, das ist 10 hoch minus 18 mal 10 hoch 18 Meter, 51:52.470 --> 51:58.570 dann sind also drei, das ist also ein Atopasec, wenn das Pasec 3 x 10 51:58.570 --> 52:03.310 hoch 18 Zentimeter sind, dann ist ein Atopasec so ungefähr 3 52:03.310 --> 52:04.010 Zentimeter. 52:07.130 --> 52:11.250 Oder, wenn man es halt amerikanisch ausrechnet, das sind so Pi mal 52:11.250 --> 52:12.510 Daumen ungefähr einen Inch. 52:13.590 --> 52:19.030 Und deswegen finden die Leute das halt lustig, statt Inches so etwas 52:19.030 --> 52:20.230 wie Atopasecs zu nehmen. 52:22.070 --> 52:24.430 Das ist wahrscheinlich so ein Schelden-Cooper-Humor. 52:26.550 --> 52:34.330 Bei den binären Größen haben wir, damit man das unterscheiden kann, 52:34.450 --> 52:37.310 haben wir halt eigentlich offiziell andere Präfixe. 52:37.910 --> 52:40.530 Das sind dann die Binary-Präfixe. 52:40.650 --> 52:44.230 Es gibt also ein Kilo-Binary, es gibt ein Mega-Binary, ein Terra 52:44.230 --> 52:46.070 -Binary und so weiter und so fort. 52:46.550 --> 52:49.390 Und die kürzt man dann halt ab und das ist natürlich lustig, Kibi, 52:50.110 --> 52:52.510 Mibi, Gibi und so weiter. 52:53.570 --> 52:57.070 Nur streng genommen sollte das eigentlich theoretisch die Einheit 52:57.070 --> 53:01.550 sein, mit der man gemäß des offiziellen Standards der International 53:01.550 --> 53:04.950 Electronical Commission die Größen angeben soll. 53:05.170 --> 53:07.810 Und wenn ich Ihnen sage, in den USA klagt man Ihnen dafür den Hintern 53:07.810 --> 53:09.910 weg, dann ist das kein Scherz, sondern das ist passiert. 53:10.970 --> 53:16.090 Da hat nämlich jemand sich beschwert, dass halt auf seiner Festplatte 53:16.090 --> 53:21.190 steht, was weiß ich, die kann 50 Gigabyte damals und die hat halt 53:21.190 --> 53:25.550 gesagt, Gigabyte, das ist doch das zur Basis 2 und hinterher war das 53:25.550 --> 53:31.050 aber zur Basis 10 und dann gibt es halt große Gerichtsverfahren und 53:31.050 --> 53:34.890 das hat man glaube ich sogar out of court sich dann geeinigt, also 53:34.890 --> 53:36.190 außergerichtlich sich geeinigt. 53:36.290 --> 53:41.590 Da sind dann irgendwelche unbekannten Geldzahlungen, Geldflüsse 53:41.590 --> 53:45.050 gewesen, wahrscheinlich sehr viel Geld, damit die Klugscheißer, die da 53:45.050 --> 53:48.890 den Prozess angezettelt haben, endlich die Klappe halten. 53:49.650 --> 53:52.650 Und damit das halt nicht mehr passiert, hat man halt jetzt 53:52.650 --> 53:55.750 sicherheitshalber diese Einheiten, mit der man eigentlich 53:55.750 --> 53:57.210 Speichergrößen angeben kann. 53:57.730 --> 54:00.510 Das heißt, als nächstes müssten Sie dann den RAM-Hersteller verklagen. 54:01.030 --> 54:03.350 Nur da wird es halt schwierig, weil wenn der RAM-Hersteller sagt, er 54:03.350 --> 54:09.530 hat so viel Gigabyte, aber er meint in Wirklichkeit binary Gigabyte, 54:09.650 --> 54:13.970 Gigi, Gibi, dann hat er Ihnen mehr gegeben, als Sie eigentlich gedacht 54:13.970 --> 54:15.670 hätten, was er Ihnen gegeben hat. 54:15.690 --> 54:17.830 Dann wird es schwierig, da auf Schadensersatz zu klagen. 54:19.870 --> 54:24.150 Also, Sie halten fest, Sie kennen das Bit, das Byte, Sie kennen die 54:24.150 --> 54:30.610 offiziellen Binary-Prefixes für Größen und Sie kennen auch den 54:30.610 --> 54:33.470 Unterschied zwischen dem Zehner- und dem Binary-System. 54:33.710 --> 54:37.170 Und wenn Ihnen einer was von RAM in Gigabyte erzählt, wissen Sie, dass 54:37.170 --> 54:40.190 das nicht notwendigerweise unbedingt die gleiche Größe sein muss, als 54:40.190 --> 54:42.830 wenn Sie eine Festplatte in einer bestimmten Gigabyte-Terabyte-Größe 54:42.830 --> 54:43.190 kaufen. 54:44.730 --> 54:48.350 Gut, was ist jetzt für uns formal gesehen ein Speicher? 54:49.010 --> 54:53.470 Ein Speicher ist für uns rein formal gesehen am Ende nichts anderes 54:53.470 --> 54:58.590 als eine Abbildung oder andersherum, also das Ergebnis einer 54:58.590 --> 54:59.090 Abbildung. 55:00.090 --> 55:04.430 Viele unterschiedliche Speicherzustände ergeben hinterher eine Menge. 55:05.330 --> 55:07.550 Was wir brauchen, wir brauchen also den, irgendwie müssen wir einen 55:07.550 --> 55:10.510 Formalismus haben für diesen Speicher selber, der Werte aufnimmt. 55:11.030 --> 55:13.590 Wir müssen irgendwie in der Lage sein, Werte aus dem Speicher 55:13.590 --> 55:16.670 rauszulesen und wir müssen irgendwie in der Lage sein, einzelne Werte 55:16.670 --> 55:18.530 in den Speicher reinzuschreiben. 55:18.630 --> 55:20.350 Und das müssen wir irgendwie formal hinschreiben. 55:20.690 --> 55:22.810 Jetzt könnte man sagen, warum, um Gottes Willen, müssen wir das denn 55:22.810 --> 55:24.090 jetzt bitte schön formal hinschreiben? 55:24.430 --> 55:26.710 Das soll einfach gebaut werden und Hauptsache, es funktioniert. 55:28.370 --> 55:32.690 So Spezifikationen haben halt immer den Vorteil, wenn ich testen 55:32.690 --> 55:36.170 möchte, ob das, was ich gebaut habe, auch so funktioniert, wie ich das 55:36.170 --> 55:39.850 gerne hätte, dann ist es gut, wenn ich mal sauber hingeschrieben habe, 55:40.190 --> 55:41.610 wie ist das denn bitteschön? 55:43.350 --> 55:47.450 Also, wir brauchen Formalismen, damit wir testen können. 55:48.010 --> 55:53.650 Wenn wir testen können, dann kann man so Testfälle sich erdenken. 55:53.990 --> 55:58.110 Dann kann man so Szenarien feststellen, von denen man weiß, was das 55:58.110 --> 55:59.050 Ergebnis sein muss. 55:59.550 --> 56:01.610 Und dann kann man diese Testfälle abdecken. 56:02.590 --> 56:06.710 Wenn jetzt die Testfälle alle positiv durchlaufen, dann weiß ich 56:06.710 --> 56:08.490 leider noch nicht, ob ich es richtig gemacht habe. 56:09.210 --> 56:12.090 Ich weiß nur, dass es für diese speziellen Testfälle funktioniert. 56:12.610 --> 56:19.610 Wenn ich die Testfälle aber geschickt wähle, dann kann ich zumindest 56:19.610 --> 56:21.630 grobe Fehler, so typische Fehler finden. 56:21.770 --> 56:24.810 Wenn nämlich dann ein Testfall fehlschlägt, dann weiß ich zumindest, 56:25.090 --> 56:26.650 dass es falsch ist. 56:27.290 --> 56:30.750 Das heißt, durch solche Testfälle kann ich, wenn ein Testfall 56:30.750 --> 56:34.630 fehlschlägt, zumindest feststellen, ob etwas falsch ist. 56:35.390 --> 56:38.770 Und wenn man etwas formal hinschreibt, dann denkt man manchmal auch 56:38.770 --> 56:44.210 ein bisschen nach und kann zum Beispiel Lücken in dem, wie man es sich 56:44.210 --> 56:46.930 überlegt hat, dass man das macht, finden. 56:48.410 --> 56:51.750 Und zum Beispiel für die Semantik von Programmiersprachen ist das sehr 56:51.750 --> 56:54.250 wichtig, dass man sowas formal hinschreibt, dass man hinterher auch 56:54.250 --> 56:59.390 einen Kompilierer finden kann, der das auch sauber und ordentlich 56:59.390 --> 57:02.890 macht und jedes beliebige Programm auch richtig entsprechend passt und 57:02.890 --> 57:05.570 das übersetzt in ein Programm, das das macht, was Sie auch wollen. 57:06.570 --> 57:09.870 Sie üben funktionales Denken, das ist als Informatiker nie schlecht. 57:11.110 --> 57:13.290 Wie stellen wir uns jetzt einen Speicher vor? 57:14.130 --> 57:18.950 Für einen Speicher können wir uns mental so eine Tabelle aufbauen. 57:19.750 --> 57:25.890 In der Tabelle gibt es Adressen und an einer Adresse steht ein 57:25.890 --> 57:26.610 bestimmter Wert. 57:27.650 --> 57:29.610 Jetzt kann man sich das so vorstellen als Tabelle. 57:29.770 --> 57:31.250 Jede Zeile ist eine Adresse. 57:31.650 --> 57:35.270 Ich könnte zum Beispiel die Zeilen durchnummerieren als Adresswert und 57:35.270 --> 57:37.650 in der Tabelle steht ein Wert drin, den ich nachschlage. 57:39.270 --> 57:40.370 Das sieht dann so aus. 57:40.610 --> 57:44.510 Also links alle Adressen, zum Beispiel die Zeilen von 1 bis Anzahl der 57:44.510 --> 57:48.330 Zeilen durchgezählt und rechts die Werte, die da drin stehen dürfen. 57:51.350 --> 57:54.530 Häufig sind das natürlich Bitfolgen, da wir binär rechnen. 57:55.530 --> 58:00.950 Also links Adressen als Bitfolgen, rechts die Werte, die wir eintragen 58:00.950 --> 58:04.010 und in der Regel sind das auch Bitfolgen spezieller Länge. 58:04.930 --> 58:08.830 Das heißt, ich habe links Bitfolgen endlicher spezieller Länge, ich 58:08.830 --> 58:10.430 habe rechts Bitfolgen endlicher Länge. 58:10.930 --> 58:14.290 Das bedeutet nichts anderes, als dass die Länge der Bitfolgen, die ich 58:14.290 --> 58:19.650 links bei den Adressen mir eintrage, bestimmt, wie viele Zeilen ich 58:19.650 --> 58:21.070 überhaupt in der Tabelle haben darf. 58:21.630 --> 58:23.430 Bestimmt mir letztendlich die Größe des Speichers. 58:24.490 --> 58:27.410 Im Sinne von, wie viele Werte kann ich abspeichern. 58:28.010 --> 58:32.230 Und rechts, das sagt mir, wie groß kann der Wert maximal sozusagen 58:32.230 --> 58:33.470 werden, den ich abspeichern kann. 58:33.550 --> 58:36.810 Wie viele unterschiedliche Werte kann ich an einer Adresse 58:36.810 --> 58:37.650 abspeichern. 58:38.910 --> 58:42.330 Und wenn man dann sozusagen nimmt, Menge der möglichen Adressen mal 58:42.330 --> 58:47.310 Menge der möglichen Werte, die ich pro Adresse abspeichern kann und 58:47.310 --> 58:50.810 das Ganze in Bit entsprechend rechnet, dann kann man daraus die Größe 58:50.810 --> 58:54.630 eines Speichers halt auf Binary in binärer Schreibweise 58:54.630 --> 58:55.750 niederschreiben. 58:57.750 --> 59:01.550 Wenn man jetzt einen Speicher formalisiert, dann ist ein Speicher 59:01.550 --> 59:04.510 selber ja so eine Tabelle und so eine Tabelle ist eine Abbildung. 59:05.530 --> 59:09.310 Ich bilde ab von der Menge der Adresse in die Menge der Werte. 59:11.030 --> 59:14.590 Also wenn ich zum Beispiel einen Speicher mit vier Binary Gigabytes 59:14.590 --> 59:21.190 habe, also Gigabinary Bytes, dann heißt, kann das zum Beispiel so 59:21.190 --> 59:28.170 sein, dass ich von den Adressen, die aus 0 und 1 bestehen und die 59:28.170 --> 59:36.210 Länge 32 haben, abbilde auf Werte, die zum Beispiel 8 binäre Zeichen 59:36.210 --> 59:37.290 lang sein können. 59:38.270 --> 59:44.970 Das sind dann also entsprechend 8 Bit oder auch 1 Byte abgebildet auf 59:44.970 --> 59:50.370 8 Bit lang. 59:51.710 --> 59:56.130 Das heißt genau Bytes und dann entsprechend mit den Adressen komme ich 59:56.130 --> 59:57.890 dann auf den Speicher. 59:59.930 --> 01:00:02.010 Ein Speicher ist in einem bestimmten Zustand. 01:00:02.230 --> 01:00:06.190 Diese Abbildung, die ich da definiert habe, ist ein bestimmter Zustand 01:00:06.190 --> 01:00:06.770 des Speichers. 01:00:06.830 --> 01:00:10.950 Ich habe bestimmte Werte in irgendwelchen Adressen abgelegt und ich 01:00:10.950 --> 01:00:14.130 kann jetzt zum Beispiel die Werte auslesen. 01:00:15.190 --> 01:00:17.990 Also ich kann zum Beispiel mir anschauen, was ist der Wert an einer 01:00:17.990 --> 01:00:18.850 bestimmten Adresse. 01:00:20.390 --> 01:00:24.610 Das heißt, die Menge Adressen ist jetzt in diesem Modell des Speichers 01:00:24.610 --> 01:00:29.270 prinzipiell fest und meistens, wenn man das in Silikon, in Silizium 01:00:29.270 --> 01:00:32.150 gießt, in Silikon wäre interessant, das mal zu gießen. 01:00:32.250 --> 01:00:33.410 Das wäre eine echte Herausforderung. 01:00:33.650 --> 01:00:37.290 Also wenn man das in Silizium gießt, dann hat meistens sogar dieser 01:00:37.290 --> 01:00:41.050 Tabelleneintrag einen physikalischen Ort. 01:00:41.150 --> 01:00:47.090 Der ist da irgendwo fest, irgendwo auf einer kleinen Fläche im 01:00:47.090 --> 01:00:47.970 Speicher vorhanden. 01:00:52.150 --> 01:00:56.490 Man kann das jetzt analog sehen zu sowas wie zum Beispiel 01:00:57.610 --> 01:01:00.490 Straßenadressen, wobei da die Analogie auch nur so und so weit geht. 01:01:02.090 --> 01:01:05.350 Wenn ich also jetzt lesen will, muss ich mir wieder eine Abbildung 01:01:05.350 --> 01:01:08.890 definieren und diese Abbildung nenne ich Memoried. 01:01:10.050 --> 01:01:15.230 Und was diese Abbildung macht, die bildet halt ab von diesem Tupel 01:01:15.230 --> 01:01:20.690 Memory und Adresse und bildet ab in die Menge aller Werte. 01:01:21.750 --> 01:01:24.190 Also Memory und Adresse in die Menge aller Werte. 01:01:24.330 --> 01:01:27.890 Und jetzt aufgepasst, hier passiert nämlich was Interessantes. 01:01:28.050 --> 01:01:32.790 Da steht, bildet ab aus dem kathesischen Produkt von Mem und Adresse. 01:01:33.870 --> 01:01:34.810 Mem sei der Speicher. 01:01:35.330 --> 01:01:36.570 Was war der Speicher nochmal? 01:01:39.010 --> 01:01:40.290 Der Speicher ist eine Abbildung. 01:01:40.870 --> 01:01:45.290 Das heißt, ich habe hier ein Tupel aus einer Abbildung und einer 01:01:45.290 --> 01:01:48.270 Adresse und bilde das ab auf einen Wert. 01:01:49.930 --> 01:01:54.250 Ist mir aber egal, ich darf auch Abbildungen als Mengenwerte nehmen, 01:01:54.450 --> 01:01:57.250 als etwas aus dem ich Tupel bilden kann. 01:01:57.990 --> 01:02:00.730 Das heißt also formal, dieser Memory ist ein bestimmter 01:02:00.730 --> 01:02:04.470 Speicherzustand und dieser Speicherzustand ist formal eine Abbildung. 01:02:05.190 --> 01:02:08.570 Und die wird halt entsprechend abgebildet. 01:02:09.930 --> 01:02:15.670 Und diese Abbildung selber, dieses MemRead, bildet ab von der Menge 01:02:15.670 --> 01:02:21.210 aller Abbildungen, von Adresse, Menge aller Abbildungen, Memory, die 01:02:21.210 --> 01:02:23.990 über so eine Adresse definiert sind, zu dem Wert. 01:02:28.750 --> 01:02:32.110 Also ist kein Problem, weil wir können uns so eine Abbildung jederzeit 01:02:32.110 --> 01:02:35.770 als Tabelle denken und deshalb ist das kein Problem, das als irgendwie 01:02:35.770 --> 01:02:36.970 in Mengenform zu gießen. 01:02:36.970 --> 01:02:40.190 Und jetzt kommt die Notation, die Ihnen mal gefehlt hatte, wo ich 01:02:40.190 --> 01:02:41.910 gesagt hatte, hier müssten Sie alle schreien. 01:02:41.990 --> 01:02:43.430 Diese Notation kennen wir noch nicht. 01:02:43.970 --> 01:02:47.870 Wenn wir uns die Menge aller Abbildungen von einer Menge A nach B 01:02:47.870 --> 01:02:50.950 anschauen, dann notieren wir uns das als B hoch A. 01:02:52.010 --> 01:02:58.230 Das ist das, was Sie damals schon hatten. 01:02:58.310 --> 01:03:00.410 Das haben wir auch an einer Stelle gebraucht, dass wir die Menge aller 01:03:00.410 --> 01:03:01.810 Abbildungen uns angeschaut haben. 01:03:03.310 --> 01:03:06.110 Da ein bisschen kontraintuitiv ist immer die Reihenfolge. 01:03:06.450 --> 01:03:09.410 B hoch A ist also nicht die Menge aller Abbildungen von B nach A, 01:03:09.730 --> 01:03:12.170 sondern die Menge aller Abbildungen von A nach B. 01:03:13.710 --> 01:03:17.790 Bei endlichen Mengen kann man jetzt für die Kardinalität der Menge 01:03:17.790 --> 01:03:21.810 aller Abbildungen sich entsprechend hernehmen, dass das Kardinalität 01:03:21.810 --> 01:03:23.790 von B hoch Kardinalität von A ist. 01:03:25.230 --> 01:03:29.710 Dementsprechend kann man auch ein Memory als allgemein beschreiben als 01:03:29.710 --> 01:03:33.610 die Menge aller möglichen Abbildungen von Adressen auf Werten. 01:03:34.270 --> 01:03:38.870 Das heißt also Memory bildet ab von Val hoch Adress, kathesisches 01:03:38.870 --> 01:03:41.470 Produkt mit Adressen, in die Menge Val. 01:03:42.150 --> 01:03:46.830 Also ein Speicher, eine Abbildung M zusammen mit einer Adresse wird 01:03:46.830 --> 01:03:51.490 abgebildet auf den Wert dieser Abbildung an der Adresse A. 01:03:53.130 --> 01:03:56.810 Umgekehrt will ich natürlich nicht nur aus dem Speicher lesen, ich 01:03:56.810 --> 01:03:59.050 will auch in den Speicher schreiben können. 01:04:00.710 --> 01:04:02.450 Und das ist ein wenig komplizierter. 01:04:07.270 --> 01:04:11.230 Ich brauche also eine Abbildung, wo ich erstmal einen Speicher habe, 01:04:11.310 --> 01:04:13.070 der irgendwie in einem bestimmten Zustand ist. 01:04:13.370 --> 01:04:16.670 Dann brauche ich eine Adresse und dann brauche ich den Wert, den ich 01:04:16.670 --> 01:04:18.230 an diese neue Adresse schreiben will. 01:04:18.890 --> 01:04:22.310 Deshalb ist also die Menge, aus der ich abbilde, dieses kathesische 01:04:22.310 --> 01:04:26.170 Produkt, aus Menge aller möglichen Speicher, aller möglichen Adressen 01:04:26.170 --> 01:04:28.030 und aller möglichen Werte. 01:04:28.470 --> 01:04:30.830 Und was herauskommt, ist wieder ein neuer Memory. 01:04:31.030 --> 01:04:35.570 Also wieder eine neue Funktion, die von den Adressen auf die Werte 01:04:35.570 --> 01:04:36.190 abbildet. 01:04:37.450 --> 01:04:42.090 Das ist halt ein neuer, also ein Memory, ein Zustand, eine Tabelle M, 01:04:42.570 --> 01:04:44.950 wird halt abgebildet auf eine neue Tabelle M'. 01:04:44.950 --> 01:04:50.890 Und zwar in der Form, dass der Wert, wenn ich, oder andersrum, und 01:04:50.890 --> 01:04:53.990 zwar in der Form, dass wenn ich eine beliebige Adresse auslese aus 01:04:53.990 --> 01:04:57.930 diesem neuen Speicher, ich an der Stelle, wo ich was Neues geschrieben 01:04:57.930 --> 01:05:02.430 habe, das Neue rausbekomme und an allen anderen Adressen das wieder 01:05:02.430 --> 01:05:05.010 rausbekomme, was vorher schon im Speicher drin stand. 01:05:05.670 --> 01:05:06.330 Das ist das hier. 01:05:06.410 --> 01:05:09.250 Nichts anderes ist das hier formal hingeschrieben. 01:05:12.420 --> 01:05:14.320 Kann man dann also auch wieder kürzer schreiben. 01:05:14.440 --> 01:05:16.020 Und jetzt wird es ein bisschen kompliziert. 01:05:16.220 --> 01:05:19.300 Also die Abbildung, Ziel- und Definitionsbereich bleibt gleich. 01:05:19.780 --> 01:05:24.900 Aber dieses Typel aus Speicher, Adresse, neuer Wert wird halt 01:05:24.900 --> 01:05:27.600 abgebildet wieder auf eine Abbildung. 01:05:28.320 --> 01:05:33.800 Nämlich auf die Abbildung, die halt sagt, dass jede beliebige Adresse 01:05:33.800 --> 01:05:37.900 A' in diesem neuen Speicher, in dieser neuen Abbildung, das ja das 01:05:37.900 --> 01:05:42.060 Ergebnis des Speicherns, des Schreibens ist, dass halt entweder der 01:05:42.060 --> 01:05:45.800 neue Wert ausgelesen wird an dieser neuen Adresse oder halt die alten 01:05:45.800 --> 01:05:48.120 Werte an allen anderen Adressen ausgelesen werden. 01:05:49.120 --> 01:05:51.940 Und wenn Sie sowas jetzt halt formal hinschreiben, dann können Sie das 01:05:51.940 --> 01:05:54.940 einem Hardwarebauer geben und er baut Ihnen halt einen Speicher, der 01:05:54.940 --> 01:05:55.700 das genau macht. 01:05:56.740 --> 01:05:59.260 Das Ganze ist die Frage, ist das plausibel? 01:05:59.380 --> 01:06:03.420 Macht das Sinn, so das Schreiben hinzudefinieren? 01:06:04.540 --> 01:06:05.940 Ja, kommt drauf an. 01:06:06.700 --> 01:06:10.440 Wenn Sie an einfachen Hauptspeicher denken, also konzeptionell 01:06:10.440 --> 01:06:12.940 Hauptspeicher, dann ist das durchaus plausibel und sinnvoll. 01:06:14.000 --> 01:06:14.520 Macht ja Sinn. 01:06:14.720 --> 01:06:19.380 Wenn ich meinen Hauptspeicher, welchen Wert reinschreibe, dann sollen 01:06:19.380 --> 01:06:21.580 ja die anderen Werte sich bitteschön nicht ändern, weil die will ich 01:06:21.580 --> 01:06:23.500 ja später vielleicht noch mal haben und ich muss die ja auch 01:06:23.500 --> 01:06:26.480 wiederfinden und die müssten entsprechend an ihren alten Adressen 01:06:26.480 --> 01:06:26.680 liegen. 01:06:27.300 --> 01:06:29.940 Es gibt aber halt noch andere Speicher, die anders sind. 01:06:30.500 --> 01:06:31.840 Einfaches Beispiel, ein Cache. 01:06:32.380 --> 01:06:36.280 Ein Cache soll halt dazu dienen, dass man schon mal in einem schnellen 01:06:36.280 --> 01:06:40.960 Speicher Werte drin stehen hat, die man vielleicht in nächster Zeit 01:06:40.960 --> 01:06:42.060 brauchen könnte. 01:06:43.080 --> 01:06:45.520 Also man geht davon aus, meistens hat man irgendwo einen großen 01:06:45.520 --> 01:06:48.840 langsamen Speicher, so einen Hauptspeicher und der Prozessor, der 01:06:48.840 --> 01:06:52.620 liest halt Werte aus und verarbeitet die und dieses übertragen aus dem 01:06:52.620 --> 01:06:55.980 Speicher zum Prozessor, also diese Funktion Memoid, die kostet halt 01:06:55.980 --> 01:06:56.320 Zeit. 01:06:57.240 --> 01:07:00.100 Das ist häufig eine Sache, die bremst den aus. 01:07:00.180 --> 01:07:03.160 Der Prozessor, der ist ratta ratta ratta fast, schnell und der 01:07:03.160 --> 01:07:04.100 Speicher, der ist langsam. 01:07:04.840 --> 01:07:05.920 Also was macht man? 01:07:06.100 --> 01:07:07.880 Man nimmt sich schnelleren Speicher her. 01:07:08.020 --> 01:07:11.480 Schnellerer Speicher ist teuer, also hat man nicht so viel schnelleren 01:07:11.480 --> 01:07:15.860 Speicher, wie man langsamen Hauptspeicher hat, aber man schaltet 01:07:15.860 --> 01:07:18.640 diesen schnelleren Speicher zwischen Hauptspeicher und Prozessor und 01:07:18.640 --> 01:07:19.400 das nennt man ein Cache. 01:07:20.040 --> 01:07:22.140 Und die Frage ist jetzt, was soll in dem Cache drinstehen? 01:07:22.240 --> 01:07:24.060 Es kann nicht alles drinstehen, was im Hauptspeicher ist. 01:07:24.140 --> 01:07:24.620 Es ist kleiner. 01:07:25.300 --> 01:07:28.980 Und das zum Beispiel, was in diesem Cache drinstehen soll, das soll 01:07:28.980 --> 01:07:32.600 vielleicht davon abhängen, was ich als Letztes geschrieben habe. 01:07:33.640 --> 01:07:36.380 Es kann auch davon abhängen, was ich als Letztes gelesen habe. 01:07:36.760 --> 01:07:39.120 Es kann aber auch davon abhängen, was ich als Letztes geschrieben 01:07:39.120 --> 01:07:39.500 habe. 01:07:40.040 --> 01:07:43.260 Das heißt, die Werte in diesem Cache, das was in dem Cache drin ist, 01:07:43.620 --> 01:07:46.560 die sollen sich halt ständig ändern, abhängig davon, was ich so in 01:07:46.560 --> 01:07:49.220 letzter Zeit geschrieben oder gelesen habe. 01:07:50.260 --> 01:07:54.080 Und dann gibt es auch noch eine andere Art von Speicher, die anders 01:07:54.080 --> 01:07:57.160 funktioniert, die nicht so funktioniert wie diese Tabellenform, 01:07:57.600 --> 01:08:02.000 sondern wo ich auf Dinge zugreifen will, nicht über Adressen, sondern 01:08:02.000 --> 01:08:04.300 über Werte, die im Speicher abgelegt sind. 01:08:04.900 --> 01:08:08.540 Das nennt man dann einen Assoziativspeicher, associative memory. 01:08:09.080 --> 01:08:13.000 Das heißt, ich habe irgendwie einen Wert, von dem ich weiß, dass er im 01:08:13.000 --> 01:08:18.180 Speicher liest und über diesen Wert adressiere ich andere Werte, die 01:08:18.180 --> 01:08:18.980 im Speicher liegen. 01:08:19.700 --> 01:08:22.080 Und zwar die Werte, die mit diesem Wert assoziiert sind. 01:08:22.920 --> 01:08:28.880 Das ist zum Beispiel so etwas, wie das menschliche Gehirn das häufig 01:08:28.880 --> 01:08:29.180 macht. 01:08:29.640 --> 01:08:33.020 Wir haben häufig einen assoziativen Speicher, dass wir für bedingte 01:08:33.020 --> 01:08:36.760 Dinge, für bestimmte Sachen, die wir im Speicher ablegen, uns 01:08:36.760 --> 01:08:39.580 irgendwie andere Sachen damit assoziiert haben, die damit 01:08:39.580 --> 01:08:43.980 zusammenhängen und die wir dann über, indem ich an das eine denke, das 01:08:43.980 --> 01:08:45.760 andere abrufen kann. 01:08:46.420 --> 01:08:49.400 Und sowas gibt es entsprechend auch vermehrt in neuen 01:08:49.400 --> 01:08:52.500 Rechnerarchitekturen, dass man mit assoziativen Speichern arbeitet. 01:08:53.100 --> 01:08:56.500 Insbesondere, wenn man hinterher mit neuronalen Rechnern arbeitet, ist 01:08:56.500 --> 01:08:58.220 der assoziative Speicher interessant. 01:08:59.900 --> 01:09:02.660 Also, was ist das Wesentliche an Speichern? 01:09:02.960 --> 01:09:07.800 Das Wesentliche an Speichern ist, dass das, was ich abspeichere, ich 01:09:07.800 --> 01:09:09.800 auch wieder rausholen kann. 01:09:15.260 --> 01:09:22.030 Das ist im Prinzip das Gleiche. 01:09:22.430 --> 01:09:26.850 Das heißt, wenn ich also reinschreibe in den Speicher und wieder 01:09:26.850 --> 01:09:29.330 auslese, dann soll das wieder rauskommen. 01:09:30.110 --> 01:09:32.490 Und für alles andere soll das andere rauskommen. 01:09:32.630 --> 01:09:37.270 Und das ist gerade so bei Caches und assoziativen Speichern eben nicht 01:09:37.270 --> 01:09:37.670 der Fall. 01:09:37.750 --> 01:09:38.590 Das will ich nicht. 01:09:40.030 --> 01:09:43.630 Mit dieser Spezifizierung kann man jetzt halt Testfälle organisieren. 01:09:43.750 --> 01:09:48.990 Mit dieser Spezifikation kann man jetzt Sachen wirklich in Hardware 01:09:48.990 --> 01:09:52.130 gießen, sodass sie sich so verhalten, wie die Spezifikation das ist. 01:09:53.330 --> 01:09:57.870 Und man kann auf die Art und Weise auch die Bedeutung von Programmen 01:09:57.870 --> 01:09:58.870 hinterher festlegen. 01:10:00.290 --> 01:10:01.270 Also, was ist wichtig? 01:10:01.410 --> 01:10:02.290 Das sollten Sie mitnehmen. 01:10:02.390 --> 01:10:03.550 Es gibt Hauptspeicher. 01:10:03.910 --> 01:10:06.870 Für das, was wir hier in der Vorlesung machen, stellen wir Ihnen uns 01:10:06.870 --> 01:10:07.890 vor als eine Tabelle. 01:10:08.390 --> 01:10:10.150 Das ist rein formal eine Abbildung. 01:10:12.070 --> 01:10:15.450 Adressen sind in dieser Abbildung immer so etwas wie physikalische 01:10:16.210 --> 01:10:16.610 Koordinaten. 01:10:16.610 --> 01:10:19.830 Außer Sie haben sowas wie ein Cache oder haben etwas anderes, dann ist 01:10:19.830 --> 01:10:20.150 es anders. 01:10:20.270 --> 01:10:23.310 Aber bei uns sind das immer physikalische Koordinaten. 01:10:23.970 --> 01:10:28.290 Und Sie wissen jetzt, dass man Abbildungen, also Speicher ist eine 01:10:28.290 --> 01:10:30.870 Abbildung und man schreibt rein, dann kriegt man eine neue Abbildung. 01:10:31.330 --> 01:10:36.190 Sie wissen jetzt, dass man Abbildungen auf Abbildungen auch abbilden 01:10:36.190 --> 01:10:36.430 kann. 01:10:37.190 --> 01:10:41.010 Dass also der Begriff von Definitions- und Zielbereich viel weiter 01:10:41.010 --> 01:10:43.670 gefasst ist, als einfach so aus Mengen, die mit irgendwelchen 01:10:43.670 --> 01:10:46.270 einzelnen Objekten da enthalten, die man irgendwie hinschreiben kann. 01:10:47.070 --> 01:10:48.610 Gut, und damit wäre es das für heute.