WEBVTT 00:01.550 --> 00:02.690 Willkommen zur 13. 00:02.990 --> 00:03.350 Übung. 00:09.710 --> 00:14.270 Wir wollen anfangen mit dem Hinweis, es kamen schon relativ viele 00:14.270 --> 00:15.470 Anmeldezettel von Ihnen. 00:16.910 --> 00:20.470 Wir hoffen, dass noch mehr kommen und dass die möglichst bald kommen, 00:20.570 --> 00:23.270 damit wir bei den Planungen gut vorbereiten können. 00:23.490 --> 00:25.710 Also lassen Sie sich nicht zu lange Zeit mit dem Anmelden. 00:26.630 --> 00:28.610 Machen Sie das am besten dem Weltest. 00:29.690 --> 00:34.790 Ich möchte noch ein paar Worte verlieren zu dem, was Herr Goos Ihnen 00:34.790 --> 00:41.510 erzählt hat am Mittwoch bezüglich Fehler, die häufigsten Fehler bei 00:41.510 --> 00:42.710 der Softwarekonstruktion. 00:43.130 --> 00:46.870 Herr Goos hat behauptet, mehr als 50% der Fehler kämen aus der 00:46.870 --> 00:50.950 Anwendungsanalyse und das kann man auch unterfüttern. 00:51.990 --> 00:55.330 Ich habe da zwei Studien zugefunden und wollte Ihnen die eben kurz 00:55.330 --> 00:55.930 vorstellen. 00:55.930 --> 01:01.070 Wir sehen hier in dem Fall, wir haben tatsächlich einen Anteil von 46% 01:01.070 --> 01:05.750 Fehler, die sich auf Spezifikationsdinge zurückführen lassen. 01:05.970 --> 01:09.730 Also bezeichnet wurde das in der Studie mit Errors in Understanding 01:09.730 --> 01:14.350 the Problem and in the Choice of an Algorithm to Solve it. 01:18.750 --> 01:20.310 Sie kriegen ein bisschen Schatten. 01:21.890 --> 01:26.070 Das zweite wären die 38% hier, das sind dann die wirklichen 01:26.070 --> 01:30.570 Implementierungsfehler, die Sie so tun könnten je nach 01:30.570 --> 01:31.650 Programmiersprache. 01:32.070 --> 01:36.930 Und 16% hier, die sind halt einfach dabei, was schlicht und ergreifend 01:36.930 --> 01:41.330 so Dinge sind wie Rechtschreibfehler in Kommentaren oder in 01:41.330 --> 01:44.890 Nachrichten, die Sie dem Benutzer geben oder fehlende Kommentare oder 01:44.890 --> 01:45.150 solche. 01:45.350 --> 01:46.310 Das sind 16%. 01:47.430 --> 01:51.130 Und wenn Sie jetzt sagen, naja, wenn ich im Airbus sitze und die 01:51.130 --> 01:53.570 Software, die dort installiert ist, wenn die Rechtschreibfehler hat, 01:53.670 --> 01:56.570 finde ich das persönlich nicht so schlimm, wie wenn jetzt hier bei den 01:56.570 --> 02:04.030 46 % oder bei den 38% ein Fehler sitzt, dann können Sie natürlich sich 02:04.030 --> 02:08.430 trauen zu behaupten, es wären wirklich deutlich über 50% der Fehler 02:08.430 --> 02:12.670 allein auf die Spezifikation zurückzuführen. 02:13.510 --> 02:18.570 Was diese Zahl ebenfalls noch relativiert, diese 46%, ist, wenn man 02:18.570 --> 02:21.770 genauer in die Studie reinguckt, die ist von einem Herrn Endres, der 02:21.770 --> 02:25.910 hat damals bei IBM, bei dem IBM-Labor in Böblingen gearbeitet. 02:26.710 --> 02:31.250 Und diese Studie wurde verfasst über ein Betriebssystem, was IBM 02:31.250 --> 02:32.410 damals geschrieben hat. 02:33.050 --> 02:38.130 Und das heißt, dass die Spezifikation, die es an der Ende gab, 02:38.190 --> 02:40.850 natürlich von Fachleuten für Fachleute war. 02:40.850 --> 02:44.230 Das heißt, wenn Sie jetzt herkommen und zu irgendeinem kleinen 02:44.230 --> 02:47.070 Einzelhändler an der Ecke gehen und für diesen Einzelhändler 02:47.070 --> 02:50.750 irgendeine Software, Sie erinnern sich an die Oma mit ihrem Laden, was 02:50.750 --> 02:54.830 sie in Heskel gemacht haben, wenn Sie für die dann eine Software 02:54.830 --> 02:58.310 machen wollen und dann die Spezifikation aufschreiben wollen, kann es 02:58.310 --> 03:02.370 sein, dass dieser Anteil sogar noch ein bisschen größer wird, weil die 03:02.370 --> 03:04.170 Oma dann eben keine Fachfrau ist. 03:04.570 --> 03:07.470 Und dort müssen Sie ganz besonders Wert nochmal auf die Spezifikation 03:07.470 --> 03:07.830 legen. 03:09.110 --> 03:12.690 Eine zweite Studie, die ich zu dem Thema gefunden habe, Software 03:12.690 --> 03:17.470 Errors and Complexity in Empirical Investigation, die kommt, wenn Sie 03:17.470 --> 03:23.410 das zusammenzählen, der Anteil von Fehlern, die sich irgendwie auf 03:23.410 --> 03:26.630 Analyse und Spezifikation zurückführen lassen, ist in dem Fall sogar 03:26.630 --> 03:30.730 48 Prozent, ist also sogar noch größer. 03:31.550 --> 03:35.990 Und was bei dieser Studie auch noch beachtet wurde, ist der 03:35.990 --> 03:40.110 Unterschied zwischen Fehlern, die Sie praktisch in neuen Modulen 03:40.110 --> 03:44.690 gemacht haben, das ist immer mit New Modules hier bezeichnet, und 03:44.690 --> 03:48.510 Fehler, die in Modulen sind, die Sie von irgendwelchen anderen 03:48.510 --> 03:51.650 Projekten sich holen und einfach nochmal verwenden. 03:52.150 --> 03:56.010 Uns ist interessant, dass der Anteil der Fehler doch teilweise 03:56.010 --> 04:00.950 erheblich ist, bezüglich der Fehler, die Sie sich mit Modulen 04:00.950 --> 04:02.610 hereinholen wieder. 04:02.970 --> 04:08.030 Ein Ergebnis dieser Studie war auch noch, dass Sie, je besser die 04:08.030 --> 04:12.690 Spezifikation ist, umso eher können Sie den Fehler bei den Modulen, 04:12.770 --> 04:14.850 die Sie sich reinholen, natürlich senken. 04:15.070 --> 04:18.890 Wenn die Spezifikation, die Sie zu Modulen haben, genauer ist, und Sie 04:18.890 --> 04:21.670 die lesen können und verstehen können und genau wissen, was das Modul 04:21.670 --> 04:25.850 macht, ohne irgendwelche Seiteneffekte oder sonst irgendwas, dann 04:25.850 --> 04:28.170 können Sie es natürlich besser einsetzen als anders. 04:29.150 --> 04:34.350 Ein interessanter Hinweis nochmal hier, clerical errors, für alle, die 04:34.350 --> 04:36.550 den englischen Begriff nicht kennen, das sind auch wieder 04:36.550 --> 04:39.810 Rechtschreibfehler, das heißt zusammengenommen wieder 12% 04:39.810 --> 04:42.710 Rechtschreibfehler in Software, also diese beiden Studien passen mit 04:42.710 --> 04:46.230 ihren Ergebnissen, obwohl sie zehn Jahre auseinanderliegen, doch recht 04:46.230 --> 04:46.810 gut zusammen. 04:47.330 --> 04:51.210 Noch interessanter finde ich allerdings, dass ich in neuen Modulen 6% 04:51.210 --> 04:54.510 Rechtschreibfehler habe und in alten Modulen ebenfalls noch 6% 04:54.510 --> 04:55.470 Rechtschreibfehler finde. 05:02.230 --> 05:06.290 Ich möchte an dieser Stelle nochmal die abstrakten Datentypen 05:06.290 --> 05:11.070 aufgreifen und die mal jetzt in Verbindung setzen zu dem Konzept von 05:11.070 --> 05:13.990 Modulen, was wir in der letzten Übung behandelt haben. 05:14.470 --> 05:20.450 Die Idee hinter einem Modul war ja, dass wir gewisse Funktionen vor 05:20.450 --> 05:23.710 dem Benutzer unseres Moduls verbergen können. 05:23.710 --> 05:26.970 Also wir machen irgendeine Funktionssammlung, die irgendeinen Mehrwert 05:26.970 --> 05:30.450 für irgendeinen anderen Programmierer darstellen könnte, geben ihm die 05:30.450 --> 05:34.570 und sagen, da gibt es einen ganzen Stall voll Funktionen, die brauchst 05:34.570 --> 05:35.230 du gar nicht wissen. 05:35.770 --> 05:42.090 Das heißt, wir verstecken Entitäten und bieten andere Entitäten nach 05:42.090 --> 05:42.770 außen an. 05:44.090 --> 05:47.290 Und diese Entitäten, die wir verstecken, das tun wir nicht aus 05:47.290 --> 05:50.850 Bewussthaftigkeit oder weil wir irgendwelche nicht öffentlichen 05:50.850 --> 05:53.890 Schnittstellen haben wollen, um irgendeinen anderen Konkurrenten aus 05:53.890 --> 05:56.710 dem Markt zu drängen, sondern einfach nur aus dem Grund, dass wir 05:56.710 --> 06:01.890 sagen, diese Entitäten sind wirklich nur für uns selber nützlich. 06:02.050 --> 06:06.050 Also die Entitäten, die wir exportieren, brauchen die und sonst 06:06.050 --> 06:07.670 braucht die nun wirklich niemand. 06:09.170 --> 06:12.770 Und was das Ganze natürlich bewirkt, ist, dass ich, wenn ich eine 06:12.770 --> 06:16.190 Dokumentation zu einem Modul schreibe, dann müssen wir dann auch 06:16.190 --> 06:20.230 unterscheiden zwischen einer externen Dokumentation, also die, die Sie 06:20.230 --> 06:23.210 dem Programmierer geben, der Ihr Modul benutzen soll, und einer 06:23.210 --> 06:28.210 internen Dokumentation für denjenigen, der das Modul weiter warten 06:28.210 --> 06:28.510 soll. 06:28.930 --> 06:32.070 Und diese interne Dokumentation müssen Sie natürlich für alle Module 06:32.070 --> 06:32.390 machen. 06:32.790 --> 06:37.430 Die externe Dokumentation müssen Sie aber insbesondere nur für die 06:37.430 --> 06:40.190 Funktionen machen, die Sie auch nach außen weitergeben. 06:40.190 --> 06:43.970 Die müssen Sie ja dann auch mit Beispielen versehen und so machen, 06:44.110 --> 06:45.090 dass der Benutzer sie kennt. 06:45.870 --> 06:48.350 Dadurch, dass es deutlich weniger sind und der Benutzer auch gleich 06:48.350 --> 06:51.290 weiß, was für ihn überhaupt relevant ist, haben Sie natürlich auch 06:51.290 --> 06:54.510 einen Vorteil der Übersichtlichkeit, wenn Sie die nicht relevanten 06:54.510 --> 06:55.630 Entitäten verstecken. 06:57.010 --> 07:02.290 So, jetzt tun die abstrakten Datentypen was ziemlich ähnliches wie 07:02.290 --> 07:06.430 Module, nämlich, sie ermöglichen uns ebenfalls das Geheimnisprinzip 07:06.430 --> 07:08.890 auf Englisch Information Hiding. 07:09.590 --> 07:15.210 Und zwar verstecken wir den konkreten Datentyp hinter einer abstrakten 07:15.210 --> 07:15.810 Schnittstelle. 07:17.670 --> 07:21.970 Und das ist praktisch die Realisierung der abstrakten Algebren in der 07:21.970 --> 07:22.410 Praxis. 07:22.970 --> 07:26.750 Sie erinnern sich vielleicht, man könnte auch andersrum sagen, die 07:26.750 --> 07:30.250 abstrakten Algebren sind die Theorie für die abstrakten Datentypen. 07:31.770 --> 07:35.030 Falls Sie sich nicht so gut erinnern, möchte ich das Ganze nochmal 07:35.030 --> 07:38.130 aufgreifen und ein bisschen zusammenfassen. 07:38.130 --> 07:41.790 Das war ja doch etwas über die Kapitel 2 und 3 verstreut und hier 07:41.790 --> 07:43.150 nochmal in Zusammenhang setzen. 07:44.990 --> 07:46.490 Was war eine Algebra? 07:47.570 --> 07:51.050 Bei einer Algebra hatten wir zunächst mal eine sogenannte Signatur. 07:52.090 --> 07:55.570 Und das war eine Menge von Operationen, die wir formal dargestellt 07:55.570 --> 08:00.470 haben als Vereinigung von Sigma oben 0, Sigma oben 1, Sigma oben usw. 08:00.990 --> 08:04.750 Das waren die Funktionen, das waren die einstelligen Funktionen, die 08:04.750 --> 08:06.550 zweistelligen, dreistelligen usw. 08:06.710 --> 08:09.730 bis so viele Stellen, wie wir eben haben. 08:10.330 --> 08:14.030 Und das Sigma 0, das waren die Funktionen, die von keinem ihrer 08:14.030 --> 08:17.910 Parameter abhängen und somit immer einen konstanten Wert zurückgeben 08:17.910 --> 08:20.130 und die wir damit als Konstanten bezeichnen. 08:21.310 --> 08:26.310 Wir haben eine Menge von Elementaroperanten, die wir in unserer 08:26.310 --> 08:30.690 Algebra haben und unsere Konstanten, die wir haben, sind auch ein Teil 08:30.690 --> 08:32.330 der Elementaroperanten. 08:33.170 --> 08:39.130 Dann, als dritten Teil, den wir in einer Algebra dann haben, haben wir 08:39.130 --> 08:45.950 die Menge T der korrekten Terme zu Sigma und den Elementaroperanten, 08:46.450 --> 08:49.810 also alle Terme, die wir als gültig erachten. 08:50.530 --> 08:53.510 Das heißt, diese Menge, wir könnten natürlich anfangen zu versuchen, 08:53.590 --> 08:57.530 sie aufzuschreiben, sie stellen aber sicher schnell fest, dass das 08:57.530 --> 09:00.850 Ganze etwas unübersichtlich wird und wahrscheinlich ist das Mittel zum 09:00.850 --> 09:02.330 Zweck, um die aufzuschreiben. 09:04.270 --> 09:08.230 Was würden Sie dann nehmen, sinnvollerweise? 09:14.220 --> 09:16.500 Irgendjemand einen Vorschlag, wie wir diese Menge am besten 09:16.500 --> 09:17.120 aufschreiben? 09:29.420 --> 09:33.240 Also wir könnten zum Beispiel eine Grammatik aufschreiben, denen die 09:33.240 --> 09:38.120 Terme genügen müssen, oder wir könnten aufschreiben eine Bacchus-Nauer 09:38.120 --> 09:41.820 -Form oder eine eBNF oder sowas, um diese Menge anzugeben. 09:41.820 --> 09:48.940 Dann gehört dazu noch die Menge Q, eine Menge von Gesetzen oder auch 09:48.940 --> 09:54.600 Axiome, sagen wir dazu, und das sind Umformungen, die die Bedeutung, 09:55.020 --> 09:57.100 also die Semantik eines Terms erhalten. 09:57.580 --> 10:01.000 Das heißt, wir kommen von irgendeinem Term F zu irgendeinem anderen 10:01.000 --> 10:05.480 Term F' und die sagen dann das Gleiche aus. 10:06.280 --> 10:09.540 Beispiele für solche Axiome sind dann zum Beispiel die Halbgruppen- 10:09.540 --> 10:16.020 oder Monoid-Gesetze, HG1 und HG2, Kommutativgesetz und solche Sachen, 10:16.700 --> 10:20.700 oder zum Beispiel die Gesetze V1 bis V10 der Buhl'schen Algebra. 10:21.320 --> 10:26.040 Sie erinnern sich, was dem Morgen gab es da und Involution und all 10:26.040 --> 10:26.720 dergleichen mehr. 10:27.660 --> 10:34.640 Wenn wir jetzt das AAA bilden aus den Termen Sigma, also unserer 10:34.640 --> 10:39.300 Signatur und der Menge Q unserer Gesetze, dann nennt man das Ganze 10:39.300 --> 10:41.780 eine algebraische Struktur bzw. 10:41.960 --> 10:43.680 eine abstrakte Algebra. 10:44.160 --> 10:46.240 Das ist dann schon alles, was wir brauchen. 10:47.920 --> 10:50.580 An dieser Stelle nochmal zur Signatur. 10:50.980 --> 10:53.560 Das ist auch in den meisten Programmiersprachen tatsächlich so, dass 10:53.560 --> 10:56.700 sich das dann als Signatur bezeichnet, die Menge von den Funktionen, 10:56.760 --> 10:57.740 die mir da angeboten wird. 10:59.220 --> 11:03.240 Allerdings immer im Zusammenhang mit den Modifizierern, die angeboten 11:03.240 --> 11:06.840 werden, also in Java zum Beispiel Public, Private und so weiter, 11:07.300 --> 11:09.680 Static oder Final oder was uns einfällt. 11:10.980 --> 11:16.040 Es gilt dann in dieser abstrakten Algebra für zwei verschiedene Terme, 11:16.200 --> 11:25.900 also zum Beispiel 3 plus 3 ist gleich 9. 11:26.690 --> 11:32.380 Wenn wir sowas haben in unserer abstrakten Algebra, dann sagen wir, 11:32.600 --> 11:36.420 wenn wir die entsprechend unseren Gesetzen in Q umformen können, dann 11:36.420 --> 11:39.420 sind die beiden Terme identisch zu betrachten. 11:40.340 --> 11:42.940 Das heißt, wir könnten uns zu diesem Beispiel hier vielleicht 11:42.940 --> 11:46.360 irgendeine Algebra überlegen, wo das funktioniert. 11:47.100 --> 11:51.400 Wir müssten dann entsprechend also die Operanten dieses Kreuzchen hier 11:51.400 --> 11:54.320 so definieren, dass es vielleicht einer Multiplikation gleicht. 11:55.420 --> 11:58.860 Beispiele für solche abstrakten Algebren waren die Halbgruppen, 11:58.920 --> 12:02.160 Monoide, Verbände, Gruppen, Ringe, Körper, Vektorräume, Bool'sche 12:02.160 --> 12:03.900 Algebren und was noch alles. 12:04.360 --> 12:07.340 Das alles aus der theoretischen, mathematischen Sicht. 12:07.700 --> 12:11.240 Aber für eine abstrakte Algebra gibt es eigentlich nur drei Dinge, die 12:11.240 --> 12:13.720 Sie da brauchen und die sind eben hier angegeben. 12:14.580 --> 12:19.240 Zu den abstrakten Algebren haben wir konkrete Algebren angegeben. 12:19.920 --> 12:23.180 Und eine konkrete Algebra bekommen wir dann, wenn wir zusätzlich zur 12:23.180 --> 12:28.700 abstrakten Algebra noch eine Trägermenge haben, irgendeine Trägermenge 12:28.700 --> 12:33.400 T, und dabei muss natürlich gelten, dass unsere Elementaroperanten 12:33.400 --> 12:34.960 alle aus dieser Trägermenge sind. 12:34.960 --> 12:38.680 So eine Trägermenge könnte dann zum Beispiel die natürlichen Zahlen 12:38.680 --> 12:39.960 oder sonst irgendwas sein. 12:41.380 --> 12:48.120 Und dann haben wir eben dieses V, wo wir jeder der Funktionen, die wir 12:48.120 --> 12:52.880 haben in unserem Sigma, ein Funktionssymbol zuordnen, und zwar ein 12:52.880 --> 12:54.940 endstelliges Funktionssymbol jeweils. 12:55.580 --> 13:01.120 Wichtig an dieser Stelle nochmal der Hinweis, dass auf dieser Folie 13:01.120 --> 13:02.860 hier überhaupt keine Typen bzw. 13:03.040 --> 13:04.560 die Sorten berücksichtigt wurden. 13:05.000 --> 13:10.440 Das ist etwas, das müssen Sie auch beachten, durchaus, bei konkreten 13:10.440 --> 13:14.860 Algebren, die Sorten nur an dieser Stelle der Übersichtlichkeit halber 13:14.860 --> 13:15.380 weggelassen. 13:15.860 --> 13:18.300 Das ist, sagen wir mal, so ein Zusatzfeature, was Sie dann, wenn Sie 13:18.300 --> 13:19.940 das verstanden haben, noch dazu lernen. 13:20.900 --> 13:24.960 Und dann fordern wir natürlich, dass die Gesetze erfüllt sind durch 13:24.960 --> 13:29.300 diese Funktionen, die wir angeboten haben, und dann sagen wir, wir 13:29.300 --> 13:30.740 hätten eine Implementierung. 13:31.880 --> 13:37.300 So, als Beispiel hatten wir angegeben, dass N0 und Plus, das ist jetzt 13:37.300 --> 13:41.720 eine Implementierung einer abstrakten Algebra, die da heißt 13:41.720 --> 13:43.040 kommutatives Monoid. 13:43.040 --> 13:47.860 Das heißt, die Gesetze, wir haben die Funktion Plus, F hoch N ist Plus 13:47.860 --> 13:52.980 in dem Fall, und die Gesetze Q wären für kommutatives Monoid, also 13:52.980 --> 13:57.600 einmal kommutativ und dann assoziativ und was war es denn noch. 13:58.360 --> 14:01.060 Jedenfalls werden die alle durchs Plus erfüllt und erhalten. 14:01.460 --> 14:04.300 Also die Signatur entspricht der einen Monoid und die Gesetze sind 14:04.300 --> 14:05.000 auch erfüllt. 14:10.400 --> 14:14.780 So, dann haben wir von Grundtermalgebern gesprochen. 14:15.280 --> 14:16.800 Wie hängen die jetzt damit zusammen? 14:17.840 --> 14:22.280 Wenn wir uns das angucken, zum Beispiel hier oben mal dieses Beispiel, 14:22.440 --> 14:26.940 wir bilden ab Null einfach auf N und Suc geht von N auf N. 14:26.940 --> 14:31.480 Und die Terme, die wir zulassen wollen, sind Null, Suc Null, Suc Suc 14:31.480 --> 14:32.660 Null und so weiter. 14:33.420 --> 14:37.420 Also hier in dem Fall keine Grammatik, sondern mit Punkt Punkt Punkt 14:37.420 --> 14:43.280 die Menge T angegeben und gehofft, dass derjenige, der es liest, das 14:43.280 --> 14:44.140 schon so versteht. 14:44.320 --> 14:46.280 Aber wirklich sauber ist es natürlich nicht. 14:46.280 --> 14:50.240 So, was wir feststellen, ist, dass diese abstrakte Algebra, die wir 14:50.240 --> 14:52.980 haben, keinerlei Gesetze haben. 14:53.060 --> 14:57.400 Wir können die Terme nur aufblasen, bis ins Unendliche, beliebig lang 14:57.400 --> 15:00.640 machen, beliebig abstrakt, aber wir kriegen sie nie wieder klein. 15:00.900 --> 15:03.700 Es gibt nichts zum Umformen, um das Ding wieder kürzer zu machen. 15:04.720 --> 15:08.780 So, und wenn wir sowas haben, keine Gesetze, dann sprechen wir von 15:08.780 --> 15:10.960 einer freien Termalgebra. 15:10.960 --> 15:19.760 Und wenn dann zusätzlich noch gilt, dass, also wir haben ja gefordert, 15:19.860 --> 15:23.380 dass unsere konstanten Funktionen eine Teilmenge der 15:23.380 --> 15:26.720 Elementaroperanten sind, und wenn wir jetzt fordern, dass die 15:26.720 --> 15:30.780 konstanten Funktionen genau die Elementaroperanten sind, dann sprechen 15:30.780 --> 15:32.220 wir von einer Grundtermalgebra. 15:32.220 --> 15:35.300 Also eine Grundtermalgebra ist praktisch eine freie Termalgebra, wo 15:35.300 --> 15:44.280 zusätzlich noch gilt, dass die Elementaroperanten gleich den 15:44.280 --> 15:45.240 Konstanten sind. 15:45.960 --> 15:47.120 Was ist der Witz dabei? 15:47.520 --> 15:53.220 Ganz einfach, es gibt keine andere Möglichkeit, irgendwelche Terme 15:53.220 --> 15:53.920 aufzubauen. 15:54.220 --> 15:55.580 Das ist der ganze Witz dahinter. 15:55.580 --> 15:59.920 Und so kommen wir praktisch dann, kriegen wir den Bogen hin und wissen 15:59.920 --> 16:02.720 dann, was eine Grundtermalgebra ist. 16:05.510 --> 16:06.350 Gibt es Probleme? 16:10.690 --> 16:11.110 Fragen? 16:13.170 --> 16:13.370 Ja. 16:34.390 --> 16:36.950 Wir haben eine nullstellige Funktion und das ist die Null. 16:41.980 --> 16:42.960 In dem Beispiel hier. 16:44.660 --> 16:45.000 Bitte? 16:46.920 --> 16:48.100 Die wäre dann Sigma Null. 16:59.430 --> 17:05.570 Also die Frage ist, wie könnte man das hier überhaupt schaffen, nicht 17:05.570 --> 17:06.530 zu erfüllen? 17:07.810 --> 17:08.350 Keine Ahnung. 17:08.770 --> 17:12.090 Man kann immer nur so in praktischen Beispielen denken und da gilt 17:12.090 --> 17:13.270 halt immer nur irgendwie das. 17:13.790 --> 17:18.170 Aber nehmen Sie mal an, ich weiß es im Moment wirklich nicht, wo Sie 17:18.170 --> 17:19.870 noch irgendwelche anderen Terme herkriegen könnten. 17:20.310 --> 17:22.470 Da müssten Sie jetzt einen Theoretiker fragen, fürchte ich. 17:23.430 --> 17:27.050 Also in allen praktischen Beispielen gilt dann ja tatsächlich das 17:27.050 --> 17:27.250 hier. 17:27.490 --> 17:28.110 Da haben Sie recht. 17:30.930 --> 17:34.450 Jedenfalls haben wir so Grundtermalgebren. 17:34.890 --> 17:36.950 Das ist praktisch das Prinzip von Heskel. 17:37.610 --> 17:41.850 Denn unsere Konstruktoren in Heskel haben auch keinerlei Bedeutung. 17:41.930 --> 17:43.150 Die sind wie das Dings da oben. 17:43.250 --> 17:45.550 Ich kann damit beliebig große Terme aufblasen. 17:45.650 --> 17:47.150 Ich kann die beliebig komplex machen. 17:47.150 --> 17:53.450 Die sehen ja auch schon ein bisschen so aus wie EBNF oder wie BNF und 17:53.450 --> 17:55.350 ich kann da Riesendinge aufblasen. 17:55.470 --> 17:58.510 Aber ich kann sie eben nur aufblasen und bilden, aber ich kann damit 17:58.510 --> 17:58.950 nichts machen. 17:59.050 --> 18:01.290 Ich kann nicht rechnen, ich kann sie nicht vereinfachen, ich kann gar 18:01.290 --> 18:02.110 nichts damit machen. 18:02.670 --> 18:07.610 Das heißt, sie spannen mir tatsächlich nur eine freie Termalgebra auf. 18:07.610 --> 18:12.370 Und in Heskel gilt auch tatsächlich, es gibt ja außer diesen 18:12.370 --> 18:16.130 Konstruktoren dann keine anderen Elemente, die mir diese Terme 18:16.130 --> 18:17.010 aufbauen können. 18:17.830 --> 18:21.130 Also sind die Konstruktoren dann tatsächlich die initiale 18:21.130 --> 18:23.710 Grundtermalgebra von Heskel. 18:24.030 --> 18:35.230 Also der praktische Zusammenhang ist also für diese Theorie einfach 18:35.230 --> 18:39.910 der, dass das genau theoretisch beschreibt, was Heskel einfach tut. 18:40.910 --> 18:44.770 Also es wirkt jetzt erst mal im ersten Augenblick sehr abstrakt mit 18:44.770 --> 18:47.930 den Algebren, aber eigentlich ist es wirklich genau das, was wir mit 18:47.930 --> 18:48.950 Heskel tun. 18:49.370 --> 18:49.630 Frage? 19:11.440 --> 19:18.500 Der Kollege sagt, dass unser Zack hier ein Element von X ist. 19:18.500 --> 19:22.840 X sind unsere Elementaroperanten. 19:29.330 --> 19:30.450 So habe ich es noch nicht betrachtet. 19:31.050 --> 19:32.750 Kann sein, kann nicht sein, weiß ich jetzt nicht. 19:36.230 --> 19:37.390 Wer ist denn dafür? 19:40.010 --> 19:42.410 Einer, zwei, drei, vier, fünf. 19:42.830 --> 19:44.250 Fünf sind dafür, wer ist dagegen? 19:47.630 --> 19:50.730 Das heißt, wir denken alle zusammen noch mal ordentlich nach und 19:50.730 --> 19:52.390 stimmen nächste Woche noch mal ab. 19:53.390 --> 19:56.690 Also, ja, so habe ich es noch nicht betrachtet. 19:57.190 --> 19:59.750 Ich habe, wie gesagt, das gleiche Problem wie eure Kommilitone gehabt. 19:59.830 --> 20:02.130 Ich konnte mir beim besten Willen nicht vorstellen, was denn da noch 20:02.130 --> 20:02.910 das erfüllen könnte. 20:03.410 --> 20:04.790 Das müsste man mal durchdenken, ja. 20:06.830 --> 20:07.750 Na, guter Punkt. 20:13.440 --> 20:18.300 Okay, jetzt haben wir so schön angefangen bei den abstrakten Algebren, 20:18.700 --> 20:22.560 haben dann eine Trägermenge dazu getan, kamen zu den konkreten 20:22.560 --> 20:25.280 Algebren und haben dann festgestellt, wenn wir noch die Gesetze 20:25.280 --> 20:28.340 weglassen, dann kommen wir sogar zu Thermalgebren und Thermalgebren 20:28.340 --> 20:33.620 sind praktisch genau das, wenn ich noch mal Ihre Aufmerksamkeit haben 20:33.620 --> 20:35.300 dürfte, wäre nett. 20:44.210 --> 20:48.010 Und die Thermalgebren entsprechen praktisch genau unseren 20:48.010 --> 20:51.590 Konstruktoren und sind damit die theoretische Grundlage für das, was 20:51.590 --> 20:54.690 wir schon die ganze Zeit praktisch in Haskell tun und das ja auch sehr 20:54.690 --> 20:55.170 erfolgreich. 20:56.450 --> 21:01.190 Und jetzt wollen wir uns mal den ganzen Dings noch mal im Zusammenhang 21:01.190 --> 21:01.750 anschauen. 21:02.310 --> 21:07.470 Wir haben also das Konzept, die Theorie der abstrakten Algebra und in 21:07.470 --> 21:11.310 Haskell entspricht das eben gerade dem abstrakten Datentyp. 21:11.310 --> 21:14.270 Klammer auf, in anderen Programmiersprachen auch, Klammer zu. 21:14.810 --> 21:18.590 Und in unserem Beispiel hatten wir eben das kommutative Monoid als 21:18.590 --> 21:19.590 abstrakte Algebra. 21:20.610 --> 21:25.170 Dazu gibt es dann eine konkrete Algebra und in Haskell haben wir dann 21:25.170 --> 21:29.590 eben einen konkreten Datentyp, der den abstrakten Datentyp erfüllt. 21:30.150 --> 21:33.830 Also wie auf der Folie vorher dran praktisch, dieses Nat mit dem Plus. 21:35.150 --> 21:40.450 So, wir haben eine Grundtermalgebra als Theorie, die Repräsentation 21:40.450 --> 21:45.570 dessen in Haskell sind die Konstruktoren und aufgeblasen haben wir 21:45.570 --> 21:50.150 dieses Nat über das Null, Suc Null, Suc Suc Null und so weiter. 21:51.150 --> 21:55.150 Und dann haben wir in der Theorie die Axiomenmenge und die bilden wir 21:55.150 --> 22:00.070 eben ab in Haskell auf die Funktionen und auch auf die Signaturen. 22:00.070 --> 22:06.490 Also insbesondere zum Beispiel die Abgeschlossenheit stellen wir ja so 22:06.490 --> 22:07.310 dar in Haskell. 22:08.450 --> 22:14.050 So, unser Beispiel hier, das oben gegebene Beispiel, unser Sigma Null 22:14.050 --> 22:19.590 wäre Null, das ist unser einziger Nullstelliger Operand, ja also 22:19.590 --> 22:23.950 Elementaroperand, dann haben wir Sigma 1 und wir haben Sigma 2, unsere 22:23.950 --> 22:25.770 Operation, also hier dieses Plus. 22:27.290 --> 22:37.850 X-Frage kommt hier jetzt noch dazu, die Terme hier jetzt mal 22:37.850 --> 22:43.570 dargestellt als BNF, das heißt es ist entweder Null, es ist ein 22:43.570 --> 22:48.750 Nachfolgerterm oder es ist eben Obtermterm, so würde ich das 22:48.750 --> 22:49.270 darstellen. 22:49.270 --> 22:53.850 Und dann die Gesetzesmenge wäre die algebraische Abgeschlossenheit, 22:54.210 --> 22:57.690 das Plus, ja irgendwie habe ich die Operation irgendwann zwischendurch 22:57.690 --> 23:02.590 umbenannt in Plus von Ob, Plus A B soll Element Null sein, 23:02.990 --> 23:08.130 repräsentieren wir in Haskell durch diese Zeile, dann haben wir das 23:08.130 --> 23:13.030 Assoziativgesetz, Plus Plus A B C ist Plus A Plus B C, 23:13.410 --> 23:17.970 Kommutativgesetz Plus A B gleich Plus B A, und das Einzelement, was 23:17.970 --> 23:21.730 wir noch brauchen fürs kommutative Monoid wäre Plus Null A gleich A 23:21.730 --> 23:25.190 und Plus A Null ist ebenfalls gleich A. 23:26.150 --> 23:31.770 Und wenn wir das Ganze jetzt realisieren, es gab in der Vorlesung zwei 23:31.770 --> 23:37.770 Repräsentationen für die natürlichen Zahlen und das hier war dann die 23:37.770 --> 23:42.070 eine und wir können jetzt unser Plus halt tatsächlich so realisieren, 23:42.150 --> 23:45.150 wir können diese beiden Gesetze zum Beispiel einfach hinschreiben für 23:45.150 --> 23:50.570 das Einzelement, das hier steht jetzt als Kommentar hinten dran ist 23:50.570 --> 23:56.090 praktisch der Rest und ab da gilt schlicht und ergreifend das 23:56.090 --> 24:00.090 Kommutativgesetz, da kommen wir ja gar nicht mehr hin wegen dem 24:00.090 --> 24:03.930 Passen, weil was nicht hier und nicht hier passt, passt halt einfach 24:03.930 --> 24:09.990 dann hier, weil ja dann offenbar A ungleich Null war und damit Sub A 24:09.990 --> 24:12.950 gewesen sein muss, das heißt wir kommen hier schon gar nicht mehr hin 24:12.950 --> 24:17.650 und diese beiden, die kann man ja in Haskell schlicht und ergreifend 24:17.650 --> 24:19.430 nicht eingeben, weil sie unzulässig sind. 24:20.130 --> 24:24.210 Jetzt hatten wir in der Vorlesung noch die Realisierung des Typs NAT 24:24.210 --> 24:29.430 über Integer und dann sähe unsere Abgeschlossenheit immer noch genauso 24:29.430 --> 24:34.590 aus und der ganze andere Rest, der eben die Gesetze Q erfüllen muss, 24:34.830 --> 24:38.670 ist ja schon durch dieses Plus, das implementiert ist, erfüllt. 24:40.350 --> 24:43.310 Also Sie sehen ein, wir hatten einen abstrakten Datentyp, ein 24:43.310 --> 24:48.230 kommutatives Monoid und tatsächlich diese Gesetze werden durch mehrere 24:48.230 --> 24:50.070 Implementierungen auch erfüllt. 24:51.730 --> 24:55.950 Plus, wir haben keine besondere Anforderung dann gestellt, dass dann 24:55.950 --> 25:00.770 irgendwas hinterher größer sein muss oder kleiner sein muss oder sonst 25:00.770 --> 25:01.370 was in der Richtung. 25:01.690 --> 25:03.610 Wir haben nur das hier gefordert. 25:03.830 --> 25:08.450 Also es hätte hier auch eine ganz beliebige andere Funktion stehen 25:08.450 --> 25:11.730 können und auch eine ganz beliebige andere Grundmenge. 25:14.970 --> 25:19.370 Das Problem an diesen Beispielen, die wir bisher hatten, ist 25:19.370 --> 25:22.610 natürlich, dass sie immer so ein bisschen sehr theoretisch sind. 25:22.970 --> 25:25.690 Und auch in dem Kapitel 6 sehen Sie, dass es für die abstrakten 25:25.690 --> 25:31.850 Datentypen ja nun wirklich auch ganz, wirklich Beispiele gibt, die man 25:31.850 --> 25:32.490 so einsieht. 25:32.670 --> 25:35.550 Und da möchte ich eins mit Ihnen auch nochmal anschauen. 25:37.150 --> 25:41.010 Also wir haben jetzt einfach mal vorgegeben an dieser Stelle, dass wir 25:41.010 --> 25:43.850 einen Taschenrechner oder sowas in der Richtung programmieren wollen 25:43.850 --> 25:46.690 und wir wollen bei diesem Taschenrechner Variablen verarbeiten. 25:47.990 --> 25:50.730 Das ist so die Vorgabe, in Ihrem Taschenrechner können Sie 25:50.730 --> 25:52.930 irgendwelche Variablen ablegen und mit denen wollen Sie nachher 25:52.930 --> 25:56.210 rechnen und das wollen wir jetzt mal in Haskell modellieren. 25:56.210 --> 26:00.630 Das Problem dabei ist, dass wir uns irgendwie merken müssen, was die 26:00.630 --> 26:02.770 jeweilige Variable für einen Wert beinhaltet. 26:04.190 --> 26:08.010 Und diese Werte wollen wir natürlich in der Datenstruktur festhalten. 26:08.630 --> 26:12.150 Die wollen wir Speicher nennen, damit wir auch wissen, wo wir diese 26:12.150 --> 26:14.230 Variablen nachher wiederfinden können. 26:18.210 --> 26:21.990 Das heißt, wir müssen uns als erstes überlegen, wie wollen wir denn 26:21.990 --> 26:24.270 Variablen und Werte aufeinander abbilden. 26:26.430 --> 26:29.070 Dafür gibt es in Haskell einfach mehrere Möglichkeiten. 26:29.490 --> 26:32.870 Wir könnten eine Liste machen und machen da Tuppel rein und da ist 26:32.870 --> 26:35.010 dann einmal eine Variable und ein Integer drin. 26:35.130 --> 26:38.070 Also Integer sei jetzt einfach mal die Werte, die wir verwenden wollen 26:38.070 --> 26:38.950 für unsere Variable. 26:39.090 --> 26:41.330 Das ist ein dummer Taschenrechner, der kann nur mit ganzen Zahlen 26:41.330 --> 26:42.390 rechnen. 26:43.450 --> 26:45.850 Alternativ können wir natürlich auch sagen, wir machen einfach zwei 26:45.850 --> 26:49.410 Listen und die haben die gleiche Länge und insbesondere auch die 26:49.410 --> 26:53.470 gleiche Reihenfolge, sodass ich dann eine Liste von Variablen habe, 26:53.610 --> 26:58.370 also a, b, c, d und 5, 6, 7, 8 als Werte in einer anderen Liste drin. 26:58.910 --> 27:01.970 Wäre auch eine mögliche Repräsentation besser oder schlechter, man 27:01.970 --> 27:02.630 weiß es nicht. 27:02.630 --> 27:08.210 Oder man könnte jetzt eine Funktion bauen, die Variablen, die wir als 27:08.210 --> 27:11.830 Parameter bekommen, direkt abbildet auf das Ergebnis, was wir da 27:11.830 --> 27:12.790 reingeschrieben haben. 27:14.390 --> 27:17.150 Es ist einfach die Frage, welche davon ist denn die beste 27:17.150 --> 27:17.830 Realisierung? 27:20.670 --> 27:21.830 Welches ist denn am besten? 27:22.690 --> 27:25.130 Wer ist denn für die Liste? 27:29.350 --> 27:29.950 Wenige? 27:30.270 --> 27:31.710 Wer ist denn für die zwei Listen? 27:34.250 --> 27:35.290 Noch weniger? 27:35.810 --> 27:36.930 Wer ist für die Funktion? 27:39.610 --> 27:41.050 Hauchdünn mehr als fürs Erste? 27:41.150 --> 27:41.930 Wer ist noch wach? 27:44.690 --> 27:45.990 Ah, die gleichen. 27:49.280 --> 27:49.760 Okay. 27:52.420 --> 27:55.920 Was wir an dieser Stelle aber schon mal festhalten können, auch wenn 27:55.920 --> 27:58.820 wir uns noch nicht entscheiden wollen oder können, welches hier die 27:58.820 --> 28:01.980 beste Repräsentation ist und vielleicht fällt Ihnen ja auch noch eine 28:01.980 --> 28:04.580 vierte oder fünfte ein, die wir in Erwägung ziehen könnten. 28:04.580 --> 28:09.360 Unabhängig davon können wir aber einen gewissen Satz an Funktionen 28:09.360 --> 28:12.160 fordern von unserem Speicher, nämlich, dass wir ihn erst 28:12.160 --> 28:16.760 initialisieren wollen, dann, dass wir Variablen lesen wollen und dann, 28:16.920 --> 28:18.560 dass wir Variablen schreiben wollen. 28:19.280 --> 28:22.380 Da sind wir uns einig, dass das von allen, egal wie wir es 28:22.380 --> 28:25.120 realisieren, wohl erfüllt werden muss. 28:26.020 --> 28:34.340 Ja, und genau das, das da oben als Problem ist angegeben an dieser 28:34.340 --> 28:37.280 Stelle, dass wir natürlich bei unseren verschiedenen 28:37.280 --> 28:40.680 Realisierungsmöglichkeiten auch unterschiedlich viel Potenzial haben, 28:40.760 --> 28:41.480 Unsinn zu machen. 28:42.140 --> 28:46.540 Das heißt, wenn wir also insbesondere mit diesen zwei Listen, da haben 28:46.540 --> 28:50.680 wir ja relativ kritische Konsistenzbedingungen in der Form, dass da 28:50.680 --> 28:53.920 niemand uns irgendwelche Elemente vertauschen darf oder irgendwo 28:53.920 --> 28:57.260 Elemente zwischen reinfügen darf, sonst geht ja alles kaputt. 28:58.240 --> 29:01.580 Und das heißt, wir wollen unsere internen Datenstrukturen in 29:01.580 --> 29:03.440 irgendeiner Form auch schützen. 29:04.160 --> 29:08.500 Das heißt, wir wollen nach außen tatsächlich auch nur die hier 29:08.500 --> 29:11.380 aufgeführten Funktionen, die wir vorher definiert haben, die die 29:11.380 --> 29:13.920 Grundoperationen sind, die wir von einem Speicher erwarten. 29:13.920 --> 29:16.820 Wir wollen auch tatsächlich nur die anbieten. 29:17.220 --> 29:19.320 Und die Implementierung wollen wir komplett verstecken. 29:23.840 --> 29:27.460 Und diese limitierte Schnittstelle, die wir da auf der Folie vorher 29:27.460 --> 29:31.200 praktisch aufgeschrieben haben, das ist dann unser abstrakter 29:31.200 --> 29:34.040 Datentyp, den es jetzt gilt zu implementieren. 29:36.280 --> 29:45.870 Und damit auch gleich die Vorgehensweise als Tipp an Sie, fangen Sie 29:45.870 --> 29:49.550 nicht erst an, einen Datentyp zu implementieren und dann sich zu 29:49.550 --> 29:53.470 überlegen, wie könnten wir davon abstrahieren, sondern im Allgemeinen 29:53.470 --> 29:56.550 ist es besser, sich zuerst zu überlegen, was für Anforderungen habe 29:56.550 --> 30:00.330 ich an meinen Datentyp, dass dann die Anforderungen erst mal als 30:00.330 --> 30:05.650 abstrakten Datentyp zu implementieren, aufzuschreiben und dann sich zu 30:05.650 --> 30:08.990 überlegen, was wäre hierfür eine Implementierung. 30:10.390 --> 30:14.330 So, das hier oben nochmal angegeben, unser abstrakter Datentyp. 30:15.210 --> 30:19.430 Und diese Signatur definiert uns jetzt eine eindeutige Schnittstelle 30:19.430 --> 30:22.530 zu dem Benutzer unseres Moduls Speicher. 30:22.530 --> 30:25.910 Oder auch unseres Datentyps Speicher im Besonderen. 30:27.770 --> 30:31.970 Und das Problem ist, dass wir vorher unser Benutzer und wir uns 30:31.970 --> 30:34.570 zusammensetzen müssen und uns auf diese Schnittstelle einigen. 30:35.870 --> 30:39.190 Das kann auch im Nachhinein erfolgen, aber nur wenn Sie ein Produkt 30:39.190 --> 30:43.150 haben und sich dann der Benutzer mehr mit sich selber einigt, ihr 30:43.150 --> 30:44.030 Produkt zu kaufen. 30:44.030 --> 30:47.710 In einem normalen Softwareprojekt sieht es dann doch eher so aus, dass 30:47.710 --> 30:50.930 Sie sich am besten vorher hinsetzen, sich auf diese Schnittstelle hier 30:50.930 --> 30:56.490 oben einigen und danach können beide anfangen, wild drauf loszuhacken. 30:56.990 --> 31:00.970 Und das Schöne dabei ist, dass Sie dann unabhängig voneinander 31:00.970 --> 31:02.030 implementieren können. 31:02.210 --> 31:06.350 Also derjenige, der den Datentyp implementiert, kann all seine Liebe 31:06.350 --> 31:11.070 darauf verwenden, den so elegant und schön und schnell und performant 31:11.070 --> 31:13.530 und sicher und weiß der Kuckuck weiß, wie möglich zu machen. 31:13.950 --> 31:16.050 Und der andere, der verwendet ihn einfach. 31:16.470 --> 31:19.810 Für den ist das eine schwarze Kiste, da guckt er nicht rein, der weiß, 31:19.910 --> 31:23.790 diese Schnittstelle hat er, diese Schnittstelle benutzt er und diese 31:23.790 --> 31:26.490 Schnittstelle wird er hinterher verwenden. 31:28.710 --> 31:33.730 Es kann halt insbesondere der Implementierer sich dann überlegen, will 31:33.730 --> 31:37.610 er lieber eine schnellere Variante implementieren oder will er eine 31:37.610 --> 31:40.290 weniger speicherintensive Variante implementieren. 31:40.870 --> 31:44.790 Zu diesen beiden Fragen wollen wir später nochmal zurückkommen und uns 31:44.790 --> 31:45.830 das genauer anschauen. 31:46.710 --> 31:51.590 Er kann sich überlegen, will ich eine vielleicht langsamere Variante 31:51.590 --> 31:55.250 implementieren, die aber so einfach strukturiert ist, dass ich sie 31:55.250 --> 31:58.170 sehr leicht auf ihre Korrektheit hin beweisen kann. 31:58.630 --> 32:02.470 Sie haben ja bei unterschiedlichen Beispielen schon gesehen, dass es 32:02.470 --> 32:08.190 für das gleiche Problem mehrere Algorithmen gibt, die es lösen und 32:08.190 --> 32:11.490 dass es triviale Algorithmen gibt, die auch gleich der Mathematik 32:11.490 --> 32:15.750 entsprechen, wo wir im Notfall den Beweis aus dem Mathematikbuch 32:15.750 --> 32:18.490 abpinseln können, weil wir sie eins zu eins übersetzen. 32:18.910 --> 32:24.750 Oder es gibt dann andere ausgebuffte Algorithmen, wo wir dann halt 32:24.750 --> 32:27.450 selber nochmal richtig viel Gehirnschmalz in den Beweis reinstecken 32:27.450 --> 32:27.730 müssen. 32:28.270 --> 32:32.030 Und wenn jetzt die Firma Airbus, um die nochmal aufzugreifen, zu Ihnen 32:32.030 --> 32:35.590 kommt und sagt, bauen Sie uns ein Modul Speicher für unseren Airbus, 32:35.970 --> 32:40.030 dann nehmen Sie unter Umständen lieber eins, wo Sie sagen, das kann 32:40.030 --> 32:42.830 ich beweisen und da kann ich dann sogar eine Garantie für abgeben. 32:50.670 --> 32:51.070 Frage? 32:51.070 --> 32:53.850 Wie Sie über die Schnittstelle Fehlermeldungen zurückliefern? 33:05.650 --> 33:08.970 Also die Frage ist, wie geben wir an dieser Stelle Fehlermeldungen 33:08.970 --> 33:11.610 zurück, weil es könnte ja sein, dass wir zweimal den gleichen 33:11.610 --> 33:15.430 Variablen Namen reingeschrieben haben und dann nicht wissen, welchen 33:15.430 --> 33:16.190 wir zurückbekommen. 33:16.770 --> 33:19.670 Und Antwort auf diese Frage ist, wir haben es an der Stelle nicht 33:19.670 --> 33:25.130 definiert und deswegen ist das Verhalten auch egal. 33:25.130 --> 33:28.250 Sie können das implementieren, wie Sie wollen und ich male Ihnen 33:28.250 --> 33:31.970 diesbezüglich nochmal hier so ein Ding auf und schreibe Ihnen da 46% 33:31.970 --> 33:32.430 rein. 33:34.970 --> 33:36.090 Sie wissen, was ich meine. 33:37.750 --> 33:39.530 Also wir haben es an dieser Stelle nicht definiert. 33:39.850 --> 33:42.230 Wenn wir das vorsehen wollen, dann müssten wir hier oben tatsächlich 33:42.230 --> 33:43.770 unseren Typ weiter anpassen. 33:46.730 --> 33:47.650 So, gut. 33:49.890 --> 33:53.170 Wir haben uns in der letzten Übung die Module schon mal angeguckt und 33:53.170 --> 33:56.450 da gab es so einen Ausschnitt, so eine Folie, da stand drauf Modul B 33:56.450 --> 34:00.950 und wir haben ein B-Keypad und haben bei unser Ants exportiert und 34:00.950 --> 34:07.170 unseren Anteater und da hatten wir irgendeine Implementierung und wir 34:07.170 --> 34:11.210 hatten angegeben, alle Konstruktoren werden mitgeliefert, also mit 34:11.210 --> 34:15.210 exportiert, wenn wir dieses Punkt Punkt angeben und ohne Stand da, der 34:15.210 --> 34:17.590 Typ wird als abstrakter Datentyp exportiert. 34:17.970 --> 34:20.270 Und das ist praktisch jetzt genau das, was wir machen wollen. 34:22.130 --> 34:26.010 Es werden keine Konstruktoren exportiert, nochmal als Hinweis, wenn 34:26.010 --> 34:29.430 wir das weglassen und es als abstrakten Datentyp so mit exportieren. 34:29.430 --> 34:31.330 Was heißt das denn für uns? 34:32.210 --> 34:34.750 Na ja, nochmal zurück auf die Grumm-Thermen-Algebra zu kommen. 34:35.070 --> 34:36.650 Wir können überhaupt keine Therme bilden. 34:37.970 --> 34:42.050 Wir können eigentlich noch nicht mal etwas bilden, worauf wir mit 34:42.050 --> 34:45.490 unseren Gesetzen oder Funktionen drauf loskönnten, um überhaupt 34:45.490 --> 34:46.730 irgendwie damit zu arbeiten. 34:48.410 --> 34:51.750 Jetzt darauf dann die Antwort, wir sollen das ja aber auch gar nicht, 34:52.090 --> 34:56.430 sondern wir haben ja eine angebotene Funktion init, die uns Therme der 34:56.430 --> 34:58.430 richtigen Form aufbaut. 34:58.710 --> 35:02.490 Es könnte ja sein, dass wir auch nicht jeden beliebigen Therme im 35:02.490 --> 35:03.650 Aufbau zulassen wollen. 35:03.650 --> 35:07.790 Deswegen an dieser Stelle das init und die Konstruktoren werden nicht 35:07.790 --> 35:08.470 mitgeliefert. 35:09.250 --> 35:12.570 Weil die Konstruktoren geben ja dann den konkreten Datentyp 35:12.570 --> 35:13.310 tatsächlich an. 35:16.480 --> 35:18.560 So, und jetzt wollen wir uns mal anschauen, wie sieht so eine 35:18.560 --> 35:23.640 Implementierung aus, wenn wir es mal mit dieser Liste machen von 35:23.640 --> 35:25.480 Variable und Zahlpaaren. 35:25.480 --> 35:29.660 Das heißt, wir machen uns ein Modul und in diesem Modul wollen wir 35:29.660 --> 35:32.720 diesen abstrakten Datentyp jetzt implementieren. 35:33.680 --> 35:40.500 Wir sehen, wir exportieren tatsächlich nur den Typ selber, keine 35:40.500 --> 35:45.380 Konstruktoren und dazu aber noch die Funktion init lesen und 35:45.380 --> 35:45.780 schreiben. 35:46.820 --> 35:49.700 So, wir machen erstmal ein new type und definieren uns den. 35:50.100 --> 35:53.020 Wir nennen den Typ Speicher und das hier ist ein Konstruktor. 35:55.000 --> 35:57.620 Und zwar sieht das Ganze so aus, wir machen einen Speicher und dann 35:57.620 --> 36:00.820 eine Liste von Tuppeln mit var und int. 36:01.520 --> 36:06.100 Jetzt ist es so, dass Heskel an dieser Stelle je nach Version etwas 36:06.100 --> 36:09.840 tolerant ist und sagt, naja, wenn wir das da gleich mit rausgeben und 36:09.840 --> 36:12.060 auch noch gleich heißt, dann meint er wahrscheinlich, dass er gleich 36:12.060 --> 36:14.200 den Konstruktor mit exportieren will. 36:14.580 --> 36:17.380 Das ist aber so eigentlich nicht unbedingt Sinn der Sache. 36:17.920 --> 36:21.140 Ja, also wenn wir das tatsächlich auch anders nennen würden, dann 36:21.140 --> 36:23.760 hätten wir auch bestimmt keinen Konstruktor draußen. 36:24.760 --> 36:28.360 Nur fand ich, dass es sich auch im weiteren Verlauf dann so besser 36:28.360 --> 36:29.880 liest, deswegen habe ich es so genommen. 36:29.880 --> 36:35.580 Also wir haben unsere Funktion mit der Signatur init, die uns einen 36:35.580 --> 36:41.040 Speicher zurückliefert, einen hoffentlich leeren Speicher und ist auch 36:41.040 --> 36:42.140 ganz einfach implementiert. 36:42.240 --> 36:44.660 Wir haben init und liefern einen Speicher mit einer leeren Liste 36:44.660 --> 36:50.220 zurück und das ist also der Konstruktor für unseren leeren Speicher. 36:51.180 --> 36:53.380 Dann bieten wir an, eine Methode lesen. 36:53.600 --> 36:56.620 Wir bekommen als Parameter einen Speicher und eine Variable und geben 36:56.620 --> 36:59.000 zurück einen int-Wert. 37:00.660 --> 37:04.900 So, wir lesen aus diesem Speicher, wenn das ein leerer Speicher ist 37:04.900 --> 37:07.800 und wir irgendeine beliebige Variable bekommen. 37:08.320 --> 37:10.500 Das heißt, wir hätten hier gar nicht v gebraucht, sondern wir hätten 37:10.500 --> 37:12.020 auch ganz gut einen Unterstrich nehmen können. 37:12.320 --> 37:15.060 Dann geben wir in diesem Fall einfach 0 zurück. 37:15.200 --> 37:18.400 Und um Ihre Frage nochmal aufzugreifen, was machen wir, wenn die 37:18.400 --> 37:21.860 Variable schon drin ist, genauso hätten wir uns eigentlich vorher 37:21.860 --> 37:24.860 überlegen müssen, was machen wir, wenn die Variable nicht drin ist. 37:24.860 --> 37:27.840 Da wir aber einen abstrakten Datentyp haben und das alles nicht 37:27.840 --> 37:30.620 definiert haben, können wir uns hier an dieser Stelle gestatten, 37:30.720 --> 37:31.860 einfach mal 0 zurückzulehren. 37:33.140 --> 37:38.300 So, und wie Sie sehen können, wollen wir, wenn wir eine Liste bekommen 37:38.300 --> 37:44.020 und davon vorne einen Tuppel rausnehmen können, dann geben wir den 37:44.020 --> 37:44.680 Wert zurück. 37:45.200 --> 37:49.160 Und wenn die Variable eben nicht der erspricht, was wir aus dem Tuppel 37:49.160 --> 37:52.500 vorne rausgenommen haben, dann lesen wir den Speicher weiter und geben 37:52.500 --> 37:54.200 dann zurück, was da zurückkommt. 37:55.600 --> 37:58.580 Schreiben ist dann etwas einfacher zu implementieren, indem wir 37:58.580 --> 38:02.340 einfach unseren Speicher hernehmen und dann ein neues Tuppel aus 38:02.340 --> 38:05.420 unserer Variable und dem Wert vorne dran einhängen. 38:10.410 --> 38:15.950 So, alternativ jetzt hier noch die Angabe, wie wir diesen Speicher, 38:16.330 --> 38:19.330 und zwar genau den gleichen abstrakten Datentyp mit dem gleichen 38:19.330 --> 38:25.070 Export und genauso zu verwenden, insbesondere, das ist ja der wichtige 38:25.070 --> 38:27.610 Punkt dabei, wir können ihn genauso verwenden. 38:28.730 --> 38:31.510 Es sieht von außen genauso aus, ist aber jetzt nicht mit Listen 38:31.510 --> 38:33.190 implementiert, sondern mit Funktionen. 38:33.190 --> 38:36.470 Also insbesondere an dieser Stelle mit Lambda ausdrücken. 38:36.950 --> 38:39.610 Die ganze Darstellung ist auch ein bisschen kürzer. 38:41.430 --> 38:46.570 Wenn wir uns jetzt das Ding benutzen wollen, dann ist es von außen 38:46.570 --> 38:47.270 wirklich gleich. 38:47.930 --> 38:50.870 Also was an dieser Stelle noch fehlt in beiden Dingern wäre, wir 38:50.870 --> 38:53.190 müssten uns natürlich den Typ Variable noch definieren. 38:53.190 --> 38:56.970 Wir sagen an dieser Stelle einfach mal, dass wir ein String haben 38:56.970 --> 38:57.370 wollen. 38:58.210 --> 39:00.890 Und wenn wir es benutzen wollen, importieren wir erstmal den 39:00.890 --> 39:04.090 abstrakten Datentyp, indem wir das Modul, in dem der abstrakte 39:04.090 --> 39:05.430 Datentyp drin ist, importieren. 39:06.770 --> 39:10.290 Wir legen uns einen leeren Speicher an mit der Funktion init. 39:11.370 --> 39:16.310 Wir können einen komplexen Speicher anlegen, S, indem wir schreiben, 39:16.470 --> 39:22.390 auf init die Variable U mit dem Wert 4, dann die Variable V mit dem 39:22.390 --> 39:25.850 Wert 5 und die Variable W mit dem Wert 3. 39:26.370 --> 39:29.850 Und wir können den Speicher auslesen, indem wir einfach sagen, lesen S 39:29.850 --> 39:30.430 und V. 39:32.250 --> 39:35.050 Jetzt ist halt die Frage an der Stelle, welche Implementierung haben 39:35.050 --> 39:36.090 wir denn da verwendet? 39:42.260 --> 39:43.540 Antwort ist egal. 39:44.180 --> 39:46.940 Wir können die erste verwendet haben oder die zweite verwendet haben. 39:47.020 --> 39:51.360 Wir dürfen eben nur nicht zwei Module haben, die eben gleich heißen, 39:51.440 --> 39:52.540 weil sonst geht es in die Hose. 39:52.940 --> 39:57.220 Und wir dürfen ja auch diese Methoden nicht haben, die gleich heißen, 39:57.500 --> 39:58.540 sonst geht es auch in die Hose. 39:58.660 --> 40:02.920 Das heißt, wir müssten das dann zumindest in den Verzeichnissen des 40:02.920 --> 40:03.580 Jungs halten. 40:04.320 --> 40:04.760 Frage? 40:16.350 --> 40:19.730 Ja, der Hinweis von Ihrem Kollegen war, dass man init gar nicht nehmen 40:19.730 --> 40:21.750 kann, weil es in der Prelude schon definiert ist. 40:21.850 --> 40:22.730 Das ist natürlich richtig. 40:24.130 --> 40:26.650 Nehmen Sie hier einen beliebigen anderen Namen und schreiben Sie ihn 40:26.650 --> 40:26.890 dahin. 40:28.410 --> 40:32.390 Die Frage, die sich jetzt stellt, wir haben zwei Implementierungen für 40:32.390 --> 40:33.690 unseren abstrakten Datentyp. 40:34.910 --> 40:36.390 Welche ist denn da jetzt besser? 40:38.830 --> 40:41.450 Das müsste man sich dann nachher überlegen. 40:41.610 --> 40:42.970 Es gibt einen abstrakten Datentyp. 40:43.090 --> 40:45.470 Der, der ihn einsetzen will, hat vielleicht zwei Angebote. 40:46.370 --> 40:49.290 Und der will vielleicht... ja, was will der haben? 40:49.370 --> 40:50.230 Vielleicht das Schnellere. 40:51.750 --> 40:55.510 Und dafür habe ich es Ihnen jetzt mal aufgeschrieben, das Programm. 40:55.790 --> 40:59.470 Also ich habe es mir aufgeschrieben, dann in Hux laufen lassen und die 40:59.470 --> 41:02.130 Ergebnisse aufgeschrieben und Ihnen eine Tabelle draus gemacht. 41:02.830 --> 41:07.430 Und wie wir hier an dieser Tabelle sehen, ist, wenn wir die 41:07.430 --> 41:11.530 Implementierung mit Funktionen machen und die Reduktionen betrachten, 41:11.870 --> 41:17.310 diese rosane Linie, und die Implementierung mit der Liste angucken und 41:17.310 --> 41:21.050 die Anzahl der Reduktionen betrachten, die Haskell gebraucht hat, das 41:21.050 --> 41:24.910 ist die blaue Linie und Sie sehen, dass das wohl offenbar ein ziemlich 41:24.910 --> 41:27.110 relevanter Unterschied ist. 41:27.110 --> 41:31.290 Dass aber die Anzahl der Zellen, wenn wir es mit Funktionen 41:31.290 --> 41:36.870 implementieren, doch etwas drunter ist, als wenn wir das Ding mit 41:36.870 --> 41:38.030 einer Liste implementieren. 41:38.730 --> 41:43.150 Das könnte denn jetzt der Grund sein, dass es gleich schnell ist, aber 41:43.150 --> 41:48.530 mit Funktionen seltsamerweise weniger Speicher braucht als mit Listen. 41:51.720 --> 41:53.300 Hätte jemand einen Vorschlag? 42:15.660 --> 42:18.620 Also, Sie brauchen nur ganz unwesentlich mehr zu wissen, als das, was 42:18.620 --> 42:25.000 wir heute wiederholt haben, um die Frage zu beantworten. 42:29.750 --> 42:30.590 Jemand eine Idee? 42:50.840 --> 42:51.560 Na gut. 42:52.640 --> 42:55.460 Also, was Sie noch an dieser Stelle erinnern müssten, um die Frage 42:55.460 --> 42:58.660 beantworten zu können, war, na, wie ging denn das mit den Listen? 42:58.660 --> 43:00.160 Da war sowas mit dem Doppelpunkt. 43:00.640 --> 43:03.640 Das heißt, wir hatten irgendeinen Wert x und hintendran eine andere 43:03.640 --> 43:04.520 Liste xs. 43:06.220 --> 43:10.760 Wir erinnern uns, Haskell ist wirklich das mit unserer Grundterm 43:10.760 --> 43:14.500 -Algebra, wir bauen unsere Terme auf, also auch unsere Listen, indem 43:14.500 --> 43:16.800 wir unsere Elemente schreiben, dann schreiben wir einen Doppelpunkt 43:16.800 --> 43:21.080 davor und hintendran steht ein anderer Term, der ebenfalls eine Liste 43:21.080 --> 43:28.880 repräsentiert, also irgendein x1, Doppelpunkt, x2, Doppelpunkt, x3, 43:30.660 --> 43:34.520 Doppelpunkt und so weiter, bis wir dann irgendwann stehen haben, die 43:34.520 --> 43:35.120 leere Liste. 43:35.980 --> 43:40.620 Ja, so waren unsere Listen definiert, das heißt, das sind auch nur 43:40.620 --> 43:48.120 Terme, diese Term-Algebra, das Ganze aufgebaut zu einer Liste, das 43:48.120 --> 43:50.420 heißt, wir haben auch wieder nur Terme, auf die wir irgendwelche 43:50.420 --> 43:53.880 Axiome haben, mit der wir die Länge dieser Terme reduzieren können. 43:54.440 --> 43:57.500 Es gibt in Haskell nichts anderes, also können wir es nur so machen 43:57.500 --> 44:01.620 und deswegen ist es genauso aufwendig und weil wir bei der Liste 44:01.620 --> 44:04.080 natürlich noch ein bisschen zusätzlichen Aufwand mit irgendwelchen 44:04.080 --> 44:08.360 Termen haben, brauchen wir an der Stelle auch mehr Zellen. 44:08.980 --> 44:11.880 Also, ganz einfache Erklärung. 44:13.060 --> 44:17.440 So, jetzt war die Frage oder eine Frage, die an dieser Stelle 44:17.440 --> 44:21.160 auftaucht, naja, es sieht ja wohl so aus, als wäre das Wachstum oder 44:21.160 --> 44:25.300 der Zeitverbrauch in Abhängigkeit von der Problemgröße n, also das 44:25.300 --> 44:30.780 wäre dann die Länge oder die Größe unseres Speichers, wäre linear. 44:31.080 --> 44:33.440 Jetzt ist die Frage, wieso geht denn das hier auseinander? 44:35.000 --> 44:38.080 Ist da irgendwie mit dem o was kaputt oder wie sieht das denn 44:38.080 --> 44:38.820 überhaupt aus? 44:39.260 --> 44:43.880 Wenn wir es uns genauer anschauen beim Ausmessen, das ist übrigens die 44:43.880 --> 44:45.840 Methode, die da angewendet wurde. 44:47.300 --> 44:49.280 Natürlich, hier stimmt es mit dem Init auch wieder nicht. 44:49.280 --> 44:54.800 Ich habe das anders geschrieben als auf den Folien und deswegen hieß 44:54.800 --> 45:02.960 es da Initialize und dann hat es halt funktioniert. 45:05.040 --> 45:09.620 Und das habe ich ausgeführt und wir wollen es uns an der Stelle mal 45:09.620 --> 45:17.840 angucken, die Verhältnisse von den Reduktionen zueinander und von der 45:17.840 --> 45:19.380 Anzahl der Zellen zueinander. 45:19.380 --> 45:22.940 Und wir sehen, dass bei Funktionsimplementierung zu 45:22.940 --> 45:27.180 Listenimplementierung das Ganze bei der Reduktion doch offenbar 45:27.180 --> 45:28.960 konvergiert und zwar gegen eins. 45:29.620 --> 45:33.540 Also scheint es wohl wurscht zu sein bezüglich des Aufwands und wir 45:33.540 --> 45:37.340 gucken uns hier an, dass es auch sogar noch schneller konvergiert und 45:37.340 --> 45:39.260 das aber gegen deutlich geringeren Aufwand. 45:39.260 --> 45:43.680 Also wir werden wohl hier bei der Geschwindigkeit dann den gleichen 45:43.680 --> 45:46.860 Wert irgendwann erreichen, aber bei der Anzahl der Zellen werden wir 45:46.860 --> 45:52.020 wohl bei einem gewissen Prozentsatz unten drunter bleiben. 45:52.400 --> 45:56.680 Und zwar nur bei einem Verbrauch von, sagen wir mal, 93,5 Prozent der 45:56.680 --> 45:56.980 Zellen. 46:00.360 --> 46:04.540 Jetzt stellt sich natürlich die Frage, ob man sowas nur durch 46:04.540 --> 46:08.320 Implementieren und viele Testreihen und den Excel und gucken, wie die 46:08.320 --> 46:10.780 Kurve läuft, was macht es hintendran, muss man vielleicht noch mehr 46:10.780 --> 46:11.080 tun? 46:11.980 --> 46:16.000 Ne, wir hatten für das Ganze eine Theorie und diese Theorie wollen wir 46:16.000 --> 46:24.420 jetzt, da wir doch einigermaßen Heskel-Spezialisten, ob sie Hexel 46:24.420 --> 46:29.200 -Spezialisten sind, weiß ich nicht, aber da wir jetzt Excel 46:29.200 --> 46:35.700 -Spezialisten, nein Excel auch nicht, Heskel-Spezialisten sind, wollen 46:35.700 --> 46:36.500 wir uns mal angucken, 46:40.320 --> 46:45.580 ob wir das Ganze jetzt, die Theorie, die wir, ich glaube, kurz vor 46:45.580 --> 46:49.480 Weihnachten irgendwann mal gemacht haben, mit dem O-Kalkül an dieser 46:49.480 --> 46:51.020 Stelle nicht anwenden können. 46:52.380 --> 46:57.120 So, wir hatten da mit dem O-Kalkül, wir hatten O von 1, wir hatten O 46:57.120 --> 47:01.740 von n, O von log n gab es da, wir hatten auch noch Großos und Kleinos. 47:01.740 --> 47:05.700 An dieser Stelle wollen wir uns erstmal nur das Großo angucken, weil 47:05.700 --> 47:11.220 das auch, sag ich mal, mit am leichtesten zu rechnen ist und auch am 47:11.220 --> 47:15.800 meisten verwendet wird und das wollen wir jetzt mal hier üben drauf. 47:15.800 --> 47:21.160 Also angegeben an dieser Stelle für Sie, die Elementar-Operationen 47:21.160 --> 47:25.360 haben alle O von 1, also was Sie sich für int vorstellen, plus mal 47:25.360 --> 47:30.280 geteilt irgendwie, auf float, double, char und boolean alle O von 1. 47:31.800 --> 47:35.640 Hinweis an der Stelle, Integer als solches ist problematisch, da wir 47:35.640 --> 47:37.960 da ja eine unbegrenzte Länge von Zahlen haben. 47:38.880 --> 47:42.600 Das heißt, die Zahlen könnten 300 Byte groß sein, die könnten 1 47:42.600 --> 47:46.680 Kilobyte groß sein oder sowas in der Richtung und dann müssten wir 47:46.680 --> 47:49.360 natürlich eigentlich schon mit der Länge der Zahlen mitrechnen. 47:49.360 --> 47:53.640 Also dann dauert die Addition natürlich länger, wir können die 47:53.640 --> 47:57.220 Addition nicht mehr in einem Prozessortaktschritt machen und dann 47:57.220 --> 48:00.500 müssen wir das schon mit in Betracht ziehen. 48:01.780 --> 48:06.840 Was wir auch noch O von 1 ansetzen können, ist der Listenoperator, 48:07.040 --> 48:10.620 also die Konkatenation hier, also dass ich ein Element vorne dran 48:10.620 --> 48:15.820 hänge, der Doppelpunkt und die Tuppelbildung, auch den 48:15.820 --> 48:21.680 Tuppelkomponentenzugriff, also wenn ich irgendwas A, B, C habe, das da 48:21.680 --> 48:26.860 reinzuschreiben oder das da rauszuholen oder so, das ist alles O von 48:26.860 --> 48:27.320 1. 48:28.240 --> 48:33.120 Unsere Konstruktoren jeweils sind natürlich auch O von 1, um einen 48:33.120 --> 48:34.320 neuen Term zu bilden. 48:34.740 --> 48:39.100 Wenn wir eine Mustererkennung machen, also prüfen, ob irgendein Term 48:39.100 --> 48:42.000 auf etwas passt, betrachten wir das als O von 1. 48:43.440 --> 48:47.680 Arrayzugriff, einen Wert lesen oder schreiben, irgendwelche Wächter, 48:47.740 --> 48:50.480 die wir da haben in Java, also mit dem senkrechten Strich und 48:50.480 --> 48:53.580 irgendeiner Bedingung hinten dran, kommen wir auch zu O von 1. 48:53.780 --> 48:57.520 Let, where oder auch ein Funktionsaufwand, ist alles O von 1. 48:59.020 --> 49:02.320 Und dann müssen wir uns jeweils eben die Größe des Problems noch 49:02.320 --> 49:04.520 definieren, um dann rechnen zu können. 49:05.320 --> 49:09.500 Was an dieser Stelle aber ganz wichtig ist, was Sie eben nicht 49:09.500 --> 49:14.340 vergessen dürfen, der Konstruktoraufruf oder jetzt ein 49:14.340 --> 49:20.300 Funktionsaufruf, der Aufruf für sich alleine, und zwar nur der Aufruf, 49:20.800 --> 49:22.020 der ist O von 1. 49:22.020 --> 49:26.580 Aber das Ding innen drin kann natürlich kräftig nochmal dazu 49:26.580 --> 49:28.960 beitragen, dass Ihr Aufwand in die Höhe geht. 49:29.480 --> 49:33.640 Und deswegen ist eben nur der Aufruf O von 1. 49:33.780 --> 49:37.860 Die Funktion selber kann aber O von weiß der Kuckuck was sein. 49:38.560 --> 49:40.600 Also ganz wichtiger Hinweis an dieser Stelle. 49:41.940 --> 49:46.380 Wir wollen uns das mal angucken für einige Aufwände. 49:47.300 --> 49:52.280 Und ja, hier ist das X, XS, das Matching, haben wir gesagt, ist O von 49:52.280 --> 49:52.620 1. 49:53.080 --> 49:55.300 Diese Listenkonkordination ist O von 1. 49:55.660 --> 49:59.120 Also ergibt sich für das Ganze einfach nur ein Aufwand von O von 1. 49:59.120 --> 50:01.680 Für Tail sieht es gerade genauso aus. 50:02.100 --> 50:05.880 Wir haben X und XS passend da einmal. 50:06.060 --> 50:08.260 Da sehen wir natürlich, wir brauchen auch nicht beliebig tief 50:08.260 --> 50:12.820 reingehen in diese Liste, weil wir müssen ja nur gucken, ist es ein X 50:12.820 --> 50:16.300 und dann eine Liste und so, passt also O von 1. 50:17.740 --> 50:20.880 Genau der gleiche Fall ist es im Basisfall von Length. 50:21.760 --> 50:24.480 Wir müssen nur vergleichen, ist das auch die leere Liste oder ist das 50:24.480 --> 50:25.380 nicht die leere Liste. 50:25.940 --> 50:30.660 Das haben wir ganz schnell rausgefunden in O von 1 und geben dann den 50:30.660 --> 50:31.500 Wert 0 zurück. 50:31.880 --> 50:33.020 Das ist auch O von 1. 50:33.480 --> 50:36.260 Also ist das ganze Ding hier diese Zeile O von 1. 50:37.460 --> 50:40.760 So, jetzt haben wir aber noch eine andere Zeile für Length, nämlich 50:40.760 --> 50:43.460 noch den anderen Fall, nämlich dass die Liste hier oben nicht leer 50:43.460 --> 50:43.780 ist. 50:44.620 --> 50:47.780 Das heißt, wir müssen uns angucken, wie sieht das Ganze aus. 50:47.860 --> 50:48.900 Wir haben das Passen wieder. 50:49.320 --> 50:51.060 Okay, haben wir gesagt, ist O von 1. 50:54.370 --> 50:59.330 Dann haben wir 1 plus, das ist also ein Int, nehmen wir an dieser 50:59.330 --> 51:03.630 Stelle jetzt einfach mal an und die Operation plus ist somit also auch 51:03.630 --> 51:04.590 O von 1. 51:06.510 --> 51:08.050 Hier, Length xs. 51:09.610 --> 51:10.610 Ja, was ist jetzt das? 51:11.270 --> 51:15.750 Wir haben an dieser Stelle, müssen wir uns definieren erstmal, was ist 51:15.750 --> 51:16.010 n. 51:16.830 --> 51:20.010 n ist in dem Fall, wovon wollen wir sprechen, die Länge der Liste 51:20.010 --> 51:20.470 wahrscheinlich. 51:30.710 --> 51:33.770 Und dann müssen wir uns überlegen, was ist denn das hier für eine 51:33.770 --> 51:34.350 Funktion. 51:34.770 --> 51:39.570 Also bezeichnen wir das mal als f von n, ist gleich. 51:39.990 --> 51:48.110 Wir haben irgendein O von 1 plus f von, wir nehmen an, das sei unsere 51:48.110 --> 51:48.570 Funktion. 51:51.190 --> 51:54.630 Wir haben aber hier xs und das x nicht mehr dabei, also haben wir hier 51:54.630 --> 51:58.030 die Problemgröße, also die Länge der Liste, haben wir um 1 verringert. 51:58.170 --> 52:00.750 Also wäre das f von n minus 1. 52:02.770 --> 52:08.350 Also haben wir hier, O von 1 war irgendwie eine Konstante und wir 52:08.350 --> 52:12.550 kommen immer weiter zurück bis auf den Basisfall, der da oben ist auch 52:12.550 --> 52:16.310 für O von 1, also haben wir hier im Endeffekt eine Summe von i gleich 52:16.310 --> 52:21.170 0 bis n von irgendeiner Konstante. 52:21.170 --> 52:27.470 Das ist gleich, also n mal diese Konstante und damit sind wir in der 52:27.470 --> 52:28.590 Klasse O von n. 52:29.470 --> 52:31.390 Für die Bestimmung der Länge dieser Liste. 52:32.850 --> 52:37.350 Sagen Sie natürlich, ui, wie unpraktisch, bei einem Array in Java kann 52:37.350 --> 52:42.070 ich die Länge direkt gleich und so, aber in Haskell ist eben die Liste 52:42.070 --> 52:43.470 auch über Terme realisiert. 52:44.550 --> 52:47.350 Insbesondere auch, fällt mir gerade an, die Datenstruktur der Liste 52:47.350 --> 52:52.570 sowieso beinhaltet in aller Regel, dass Sie eben die Elemente 52:52.570 --> 52:54.410 schrittweise abschreiten müssen. 52:54.410 --> 52:58.610 Was denkbar gewesen wäre, ist, dass Sie sich einen eigenen Datentyp 52:58.610 --> 53:02.810 definieren, wo Sie einfach immer noch eine Zahl mitführen, in der Sie 53:02.810 --> 53:04.930 sich merken, wie lange die Liste gewesen ist. 53:06.270 --> 53:06.690 Aber gut. 53:07.890 --> 53:10.170 Wie sieht es aus jetzt bei der Funktion take? 53:11.410 --> 53:15.510 Wir passen die 0 in O von 1, wir passen den Unterstrich noch viel 53:15.510 --> 53:17.390 schneller und geben das zurück. 53:17.390 --> 53:19.430 Hier ist also O von 1. 53:20.850 --> 53:25.710 Hier ebenfalls wieder, wir passen den Unterstrich in O von 1, wir 53:25.710 --> 53:30.390 passen das in O von 1, wir geben das zurück in O von 1, alles O von 1. 53:32.410 --> 53:34.270 Wie sieht es bei take n aus? 53:35.050 --> 53:42.250 Wir gucken an, wir passen einmal, passen einmal, jeweils O von 1 und 53:42.250 --> 53:43.210 schauen uns das hier an. 53:43.530 --> 53:48.070 Wir haben das x, wollen wir zurückgeben, O von 1, die 53:48.070 --> 53:50.710 Listenkonkatenation haben wir auch gesagt O von 1. 53:52.970 --> 53:55.610 Und jetzt müssen wir uns den Ausdruck hier innen angucken. 53:56.830 --> 53:57.750 Wie sieht der aus? 53:58.350 --> 54:03.750 Also wir nehmen wieder an, das sei unser f von n und da haben wir eben 54:03.750 --> 54:15.010 ebenfalls O von 1 plus, da ist das gleiche nochmal, f von n, aber in 54:15.010 --> 54:18.670 dem Fall ist n, so steht es ja sogar gleich da, 1 kleiner. 54:20.910 --> 54:24.050 Das heißt, wir landen mit dem Ding wieder in O von n. 54:26.650 --> 54:30.730 Ist auch irgendwie plausibel, aus irgendeiner Liste n rauszunehmen, 54:30.850 --> 54:31.750 ist wieder O von n. 54:33.610 --> 54:35.770 Genauso verhält sich es hier auch für das Drop. 54:36.770 --> 54:40.150 Das Prinzip ist Ihnen jetzt, denke ich, doch einigermaßen klar 54:40.150 --> 54:41.910 geworden, gerade bei diesen Rekursionen. 54:42.730 --> 54:46.670 Sie teilen das Ganze auf in einen Basisfall, für den müssen Sie 54:46.670 --> 54:50.590 bestimmen, den Aufwand, den müssen Sie sich angucken, dann gucken Sie 54:50.590 --> 54:54.290 sich die Rekursionen an, den Rekursionsfall, gucken an, was kommt 54:54.290 --> 54:57.350 vorne dran, gucken an, was kommt hinten dran, noch ein Aufwand dazu 54:57.350 --> 55:00.670 und steigen dann ab in die Rekursion. 55:01.170 --> 55:06.350 Und da steigen Sie dann ebenso oft ab, wie dann hier steht. 55:06.670 --> 55:07.990 In dem Fall minus einmal. 55:07.990 --> 55:12.990 Wenn Sie jetzt zum Beispiel hier n halbe stehen hätten, also n durch 55:12.990 --> 55:15.790 2, dann würden Sie den hier halbieren. 55:16.570 --> 55:18.750 Okay, also wie gesagt, für Drop sieht es genauso aus. 55:19.490 --> 55:23.150 Und wir wollen mal angucken, wie das jetzt nicht mit Listenfunktionen, 55:23.150 --> 55:25.310 sondern mit höherwertigeren Funktionen aussieht. 55:25.310 --> 55:28.310 Und schauen uns dafür mal Mapf an. 55:28.750 --> 55:31.550 Hier vorne, das ist wieder alles O von 1, da hat sich nichts geändert. 55:34.210 --> 55:35.770 Und jetzt gucken wir uns das hier an. 55:36.270 --> 55:40.810 Wir haben gesagt, der Funktionsaufruf, nur der Funktionsaufruf ist O 55:40.810 --> 55:41.370 von 1. 55:41.370 --> 55:45.950 Die Konkatenation der Liste, also das vorne Dranschreiben, ist wieder 55:45.950 --> 55:46.810 O von 1. 55:47.810 --> 55:52.510 Und dann haben wir hier wieder unseren Aufruf mit unserem f von n. 55:52.910 --> 55:56.230 Und da kommt, genau wie bei den Fällen vorher, wieder n mal raus. 55:56.230 --> 56:01.370 Jetzt ist es aber wichtig, was dieses f für einen Aufwand hatte. 56:03.170 --> 56:07.090 Das heißt, wir können den Aufwand von Mapf nicht angeben ohne 56:07.090 --> 56:07.550 weiteres. 56:07.630 --> 56:11.810 Wir müssen hier arbeiten mit einer Variablen und sagen, naja, wir 56:11.810 --> 56:13.390 steigen wohl offenbar n mal ab. 56:13.390 --> 56:19.470 Und müssen deswegen sagen, der Aufwand des f von n mal phi als 56:19.470 --> 56:19.950 Aufwand. 56:21.910 --> 56:23.770 Genauso verhält sich es dann mit dem Filter. 56:24.850 --> 56:26.970 Ist auch irgendwie nichts Spannendes, Neues. 56:28.270 --> 56:31.010 Kommen wir lieber nochmal zu einem anderen Beispiel. 56:32.850 --> 56:35.490 Sie erinnern sich an Binary Search. 56:36.470 --> 56:42.150 Binary Search ging so, dass wir nicht eine große, lange Liste haben 56:42.150 --> 56:45.490 und die von Anfang an durchsuchen, bis wir irgendwann eventuell ein 56:45.490 --> 56:51.530 Element gefunden haben, sondern wir sagen, wir suchen uns einen 56:51.530 --> 56:55.830 Einstiegspunkt an der Liste und vergleichen, Voraussetzung, dass die 56:55.830 --> 56:56.830 Liste sortiert ist. 56:58.090 --> 56:59.490 Vergleichen mit dem Element hier. 57:01.330 --> 57:04.450 Und wenn es größer ist als das Element, suchen wir in der linken 57:04.450 --> 57:07.330 Seite, äh kleiner ist als das Element, suchen wir in der linken Seite, 57:07.490 --> 57:08.850 sonst suchen wir in der rechten Seite. 57:10.170 --> 57:12.390 Nehmen uns hier wieder ein Element in der Mitte raus. 57:14.350 --> 57:17.290 Gucken wieder größer, kleiner, ist größer, also suchen wir wieder in 57:17.290 --> 57:23.370 der rechten Seite, wieder in der Mitte und so weiter, bis wir dann 57:23.370 --> 57:24.870 unser Element gefunden haben. 57:25.870 --> 57:28.530 Wir haben damals angegeben, dass das deutlich schneller ist. 57:29.090 --> 57:30.170 Aus welchem Grund? 57:30.170 --> 57:33.890 Na, sie halbieren immer die Problemgröße immer weiter, jedes Mal mit 57:33.890 --> 57:37.110 jedem Schritt und deswegen hat es einen Aufwand von 57:40.200 --> 57:43.220 Log N, richtig. 57:45.360 --> 57:51.060 Das heißt, wenn wir jetzt anfangen zu messen, sollten wir es ja 57:51.060 --> 57:53.900 eigentlich schaffen, das Ding so hinzukriegen, wie wir das gerne 57:53.900 --> 57:54.160 hätten. 57:54.160 --> 57:57.840 Ich habe Ihnen dazu mal das Ding implementiert und einmal laufen 57:57.840 --> 58:03.000 lassen, suchen lassen und zwar hier unten ist wieder angegeben N, die 58:03.000 --> 58:03.720 Länge der Liste. 58:05.720 --> 58:09.280 Und sieh da, irgendwie haben wir aus unerfindlichen Gründen hier 58:09.280 --> 58:12.580 relativ gerade Striche. 58:13.920 --> 58:18.120 O von Log N, also Log zur Basis 2 N, wäre diese Linie hier unten. 58:22.490 --> 58:28.130 Zum Vergleich, N Log N, also das, was ein guter Sortieralgorithmus 58:28.130 --> 58:29.650 hat, wäre hier oben. 58:33.130 --> 58:38.410 Und die beiden, also Zellen und Reduktionen, sind dummerweise linearer 58:38.410 --> 58:38.910 Verbrauch. 58:39.310 --> 58:44.710 Und zwar sehen wir hier den Verbrauch an Zellen, der ist offenbar, 58:44.850 --> 58:47.590 jetzt müsste man die Farbe noch unterscheiden können, aber man kann es 58:47.590 --> 58:55.250 ja auch logisch machen, also hier offenbar 65 und hier haben wir O von 58:55.250 --> 58:56.370 88 N. 58:57.910 --> 58:58.890 Wie kann das passieren? 58:58.950 --> 59:01.310 Wir haben ja gerade gesagt, das wäre logarithmisch. 59:02.210 --> 59:05.430 Das heißt, wenn wir jetzt feststellen, das Ding ist zu langsam, müssen 59:05.430 --> 59:08.690 wir nochmal reingucken in den Algorithmus und nicht auf Heskel 59:08.690 --> 59:10.370 schimpfen, sondern gucken, ob wir vielleicht irgendeinen 59:10.370 --> 59:11.850 konzeptionellen Fehler haben. 59:12.850 --> 59:16.910 Also wir treten diesen Fall, schauen uns das genauer an, matchen 59:16.910 --> 59:20.990 wieder O von 1, Falls O von 1, alles O von 1, zufrieden. 59:21.490 --> 59:23.310 Das ist kleiner als O von Log N. 59:24.250 --> 59:25.770 Jetzt gehen wir in den Fall rein. 59:26.110 --> 59:28.750 Das Matchen, klar, kriegen wir wieder hin, O von 1. 59:31.030 --> 59:35.830 Das Ganze passen hier, das sind konstant viele Fälle, also jedes Mal 59:35.830 --> 59:40.690 drei Fälle, unabhängig von der Länge der Liste, in der wir suchen, ist 59:40.690 --> 59:41.690 also auch O von 1. 59:41.690 --> 59:45.810 Der Vergleich ist auch immer, wir vergleichen mit einem festen 59:45.810 --> 59:50.250 Element, mit einem Y, also der Vergleich zwischen zwei Integers, haben 59:50.250 --> 59:53.610 wir gesagt, auch O von 1, also ist das ganze Ding wieder O von 1. 59:55.230 --> 59:59.190 So, wir geben zurück, hier in dem Fall sind wir wieder O von 1 und 59:59.190 --> 01:00:02.410 fertig und sind glücklich, weil das kleiner von N log N ist. 01:00:02.830 --> 01:00:05.470 Wir gucken uns jetzt an, bsearch ls, rs. 01:00:06.110 --> 01:00:09.830 Da müssen wir jetzt mal reingucken, wo kommen denn ls und rs her? 01:00:11.310 --> 01:00:16.870 ls wären take m von xs und rs wären drop m von xs. 01:00:17.490 --> 01:00:19.910 Wobei wir uns hier irgendwo noch das Y mit rausnehmen. 01:00:20.310 --> 01:00:23.170 Der einfache Teil war wegen dem Aufbau, dass wir immer vorne dran 01:00:23.170 --> 01:00:26.630 hängen, halt bei der rechten Seite am Anfang raus, aber das ist auch 01:00:26.630 --> 01:00:27.190 nicht so wichtig. 01:00:28.670 --> 01:00:30.770 Okay, wir nehmen uns da raus, m, was ist m? 01:00:31.270 --> 01:00:36.930 m ist also l, div 2, l ist offensichtlich ja nur irgendeine Zahl. 01:00:37.690 --> 01:00:40.230 Okay, also das Ganze hier kriegen wir auch wieder in O von 1 hin. 01:00:43.060 --> 01:00:45.240 Naja, Moment, nicht ganz. 01:00:46.260 --> 01:00:52.660 Wir haben eben gezeigt, dass diese Funktion length von xs summerweise 01:00:52.660 --> 01:00:53.540 O von N hat. 01:00:57.140 --> 01:01:02.880 Und auch wenn wir noch so geschickt jetzt unseren Algorithmus gewählt 01:01:02.880 --> 01:01:09.160 haben, wenn wir irgendwo ein Element drin haben, was O von N ist, dann 01:01:09.160 --> 01:01:12.120 kommen wir mit dem Algorithmus nie wieder unter O von N. 01:01:12.800 --> 01:01:16.740 Wir kommen bestenfalls auf O von N, wenn nicht sogar darüber. 01:01:17.260 --> 01:01:18.200 Hinweis an dieser Stelle. 01:01:18.840 --> 01:01:22.580 Davon abgesehen wären take und drop sowieso O von N gewesen. 01:01:27.480 --> 01:01:29.480 So, zum Zusammenfassen. 01:01:31.500 --> 01:01:34.580 Für O von 1 haben wir die Listenfunktionen noch zusätzlich. 01:01:35.400 --> 01:01:38.420 Sie erinnern sich jetzt an die letzte Folie da mit dem O von 1, was da 01:01:38.420 --> 01:01:39.240 alles angegeben war. 01:01:39.300 --> 01:01:41.220 Da kommt also dann jetzt noch head und tail dazu. 01:01:42.540 --> 01:01:46.360 Und mit dem Aufwand O von N haben wir also gesehen length, take, drop 01:01:46.360 --> 01:01:47.060 und so weiter. 01:01:47.820 --> 01:01:52.060 Für Funktionen höherer Ordnung gilt, dass wir O von N haben plus N mal 01:01:52.060 --> 01:01:52.820 phi von f. 01:01:53.380 --> 01:01:57.200 Wobei phi f der Aufwand der inneren Funktion f ist, den wir von 01:01:57.200 --> 01:01:58.280 vornherein nicht kennen. 01:01:59.520 --> 01:02:00.240 Wie sieht das aus? 01:02:00.280 --> 01:02:01.160 Schauen wir es uns mal an. 01:02:01.480 --> 01:02:02.440 Was könnten wir denn hier haben? 01:02:02.480 --> 01:02:06.160 Wir könnten hier haben zum Beispiel O von 1. 01:02:07.360 --> 01:02:11.160 Dann hätten wir N mal O von 1 und dann wäre dieser Term auch O von N. 01:02:11.780 --> 01:02:14.180 Dann hätten wir O von N plus O von N. 01:02:14.280 --> 01:02:16.580 Das heißt, das Ganze ist dann wieder Element O von N. 01:02:18.040 --> 01:02:20.740 Also kommt es auf den da vorne nicht an, wenn es O von 1 ist. 01:02:21.100 --> 01:02:24.240 Und wenn wir hier hinten beispielsweise O von N haben, dann haben wir 01:02:24.240 --> 01:02:25.240 N mal O von N. 01:02:25.520 --> 01:02:26.880 Dann sind wir bei O von N². 01:02:28.340 --> 01:02:30.500 Dann ist der Term da vorne auch nicht mehr relevant. 01:02:30.660 --> 01:02:32.000 Sie erinnern sich an die Rechenregeln. 01:02:32.500 --> 01:02:36.340 Und wir sind im Element von O von N². 01:02:36.340 --> 01:02:39.600 Also können wir den Teil da vorne sogar vergessen. 01:02:41.060 --> 01:02:47.260 Bei der Binärsuche, wichtig, wir haben auch, obwohl wir uns so schön 01:02:47.260 --> 01:02:49.880 viel Mühe gegeben haben mit dem Algorithmus und so viel nachgedacht 01:02:49.880 --> 01:02:53.720 haben, wenn wir es auf Listen implementieren, zwangsläufig O von N. 01:02:53.980 --> 01:02:54.840 Das geht nicht anders. 01:02:55.380 --> 01:02:59.260 Wenn wir echte Arrays haben, dann kriegen wir durchaus den Algorithmus 01:02:59.260 --> 01:03:01.860 in Log N hin. 01:03:02.400 --> 01:03:05.180 Denn da können wir dann sagen, naja, das Array ist so und so lange 01:03:05.180 --> 01:03:05.680 unfertig. 01:03:05.800 --> 01:03:08.000 Da dauert das nur einen Moment lang. 01:03:08.340 --> 01:03:12.620 Wir müssen dann auch nicht die Funktion Take und Drop aufrufen, um die 01:03:12.620 --> 01:03:14.180 halbe Liste zu übergeben. 01:03:14.380 --> 01:03:18.040 Die halbe Liste zu übergeben kostet uns schon mal N Aufwand, um die 01:03:18.040 --> 01:03:19.080 Elemente zu kopieren. 01:03:19.540 --> 01:03:23.100 Sondern wir arbeiten dann nur mit Zeigern auf Indizes, wenn wir echte 01:03:23.100 --> 01:03:23.760 Arrays haben. 01:03:24.520 --> 01:03:27.400 Jetzt sagen Sie mir natürlich, warum hat der Herr Gelhausen denn dann 01:03:27.400 --> 01:03:29.680 nicht einfach die Arrays genommen, die es da gibt in Haskell? 01:03:30.240 --> 01:03:32.400 Na, die Antwort ist ganz einfach. 01:03:32.580 --> 01:03:36.880 Wenn Sie es aufmachen, Array.hs, die Bibliothek für Arrays in Haskell, 01:03:37.100 --> 01:03:41.400 dann sehen Sie, dass auch die mit Listen und also auch die, warum, 01:03:41.560 --> 01:03:45.360 weil es gar nicht anders geht, wieder über die Termalgebra aufgebaut 01:03:45.360 --> 01:03:49.680 sind, über diese induktive Definition der Terme. 01:03:49.940 --> 01:03:51.280 Es geht einfach nicht anders in Haskell. 01:03:51.380 --> 01:03:52.600 Es gibt keine andere Möglichkeit. 01:03:53.380 --> 01:03:56.980 Also kann ich Ihnen in Haskell hier niemals einen Algorithmus 01:03:56.980 --> 01:03:58.820 vorführen, der unter O von N hat. 01:03:58.820 --> 01:04:02.380 Weil alles einfach über Listen geht und die Problemgröße immer mit der 01:04:02.380 --> 01:04:02.900 Liste geht. 01:04:04.000 --> 01:04:07.420 Gut, dann kommt, 01:04:12.020 --> 01:04:17.800 ach ja genau, ein bisschen schwieriger das Beispiel zum Rechnen. 01:04:22.180 --> 01:04:24.140 Leicht ist wieder der Basisfall. 01:04:25.080 --> 01:04:29.600 Also das war Fib von 0 gleich 0, da kriegen wir O von 1 hin. 01:04:30.080 --> 01:04:32.620 Fib von 1 gleich 1 ist ebenfalls O von 1. 01:04:33.860 --> 01:04:35.520 Wie sieht es denn jetzt hier unten aus? 01:04:37.240 --> 01:04:40.600 Also Sie erinnern sich, da war in der Vorlesung der Satz dabei, Main 01:04:40.600 --> 01:04:49.500 von Fib 3 ist 2, Fib 12 ist dann 144, Fib 20 ist 6765 und Fib 100 01:04:49.500 --> 01:04:51.500 steht da nach langer Zeit noch keine Lösung. 01:04:52.100 --> 01:04:54.280 Das heißt, das ist ja eigentlich ein Kandidat, wo wir mal gucken 01:04:54.280 --> 01:04:55.600 wollen, wie ist denn da der Aufwand. 01:04:57.680 --> 01:05:01.180 Das heißt, wir gucken uns das an der Stelle an. 01:05:02.480 --> 01:05:05.380 Das Passen kriegen wir wieder hin in O von 1, ist kein Problem. 01:05:05.900 --> 01:05:07.120 Und jetzt haben wir das da hinten. 01:05:07.500 --> 01:05:16.160 Aha, wir haben also da hinten wieder O von N plus 1, also in dem Fall 01:05:16.160 --> 01:05:23.920 N minus 1, also O von N und dann nochmal plus O von N, wir gehen da 01:05:23.920 --> 01:05:28.640 rein, denn wir kommen Fib immer weiter runter, also wir haben F von F 01:05:28.640 --> 01:05:34.360 von F von F von und so weiter, bis wir dann irgendwann bei einem 01:05:34.360 --> 01:05:41.160 dieser beiden Basisfälle sind und der ist O von 1 und das Ganze machen 01:05:41.160 --> 01:05:44.200 wir N mal, also sind wir O von N in dem Fall. 01:05:44.200 --> 01:05:46.020 Also der Algorithmus ist dann O von N. 01:05:48.800 --> 01:05:51.760 Jetzt haben wir gesagt, der bessere Ansatz, der auch deutlich 01:05:51.760 --> 01:05:53.660 schneller läuft, wäre dieser hier. 01:05:55.080 --> 01:05:56.800 Schauen wir uns das mal genauer an. 01:05:57.500 --> 01:06:03.640 Wir haben Fib N, Passen geht wieder in O von 1, First Fib H, also FST 01:06:03.640 --> 01:06:04.160 Fib H. 01:06:04.500 --> 01:06:08.040 Fib H schauen wir mal eben nach, gibt uns offenbar ein Tuppel zurück 01:06:08.040 --> 01:06:11.740 und wir haben gesagt, der Tuppelzugriff ist O von 1, also sind wir in 01:06:11.740 --> 01:06:15.060 dem Fall hier O von 1 für den Tuppelzugriff. 01:06:16.500 --> 01:06:21.880 So, Fib H von 0 ist 0,1, da wären wir ebenfalls in der Klasse O von 1 01:06:21.880 --> 01:06:24.000 und jetzt gucken wir es uns mal hier hinten an. 01:06:24.540 --> 01:06:30.860 Passen geht wieder in O von 1, hier bauen wir ein Tuppel, wir haben 01:06:30.860 --> 01:06:34.980 gesagt, das Bauen von Tuppeln geht in O von 1, insbesondere da die 01:06:34.980 --> 01:06:38.080 Addition von zwei Zahlen auch in O von 1 geht. 01:06:40.440 --> 01:06:44.000 Und dann gucken wir hier nach, wie ist es denn da, wir kriegen unser 01:06:44.000 --> 01:06:48.680 Tuppel zurück von Fib hier die Problemgröße 1 kleiner. 01:06:49.140 --> 01:06:58.940 Also wir haben unser F von N ist wieder O von 1 plus F von N minus 1. 01:07:00.140 --> 01:07:02.180 Damit sind wir also wieder in O von N. 01:07:03.980 --> 01:07:07.700 Das ist jetzt natürlich etwas wunderlich, es ist in der gleichen 01:07:07.700 --> 01:07:12.420 Funktionsklasse und trotzdem dauert das mit 100 so lange und in dem 01:07:12.420 --> 01:07:13.500 Fall geht es so schnell. 01:07:15.220 --> 01:07:18.220 Da liegt jetzt natürlich nahe zu sagen, das muss an Heskel liegen. 01:07:19.100 --> 01:07:24.360 Also schauen wir es uns mal an, wenn wir es ausmessen, dann sehen wir, 01:07:24.780 --> 01:07:28.700 unsere beiden Funktionen sind also hier, die Anzahl der Reduktionen 01:07:28.700 --> 01:07:29.420 und der Zellen. 01:07:32.420 --> 01:07:38.660 Und wenn man genauer hinschaut, stellt man fest, dass ich hier drüben 01:07:38.660 --> 01:07:42.080 für die Reduktionen und die Zellen eine logarithmische Skala gewählt 01:07:42.080 --> 01:07:42.340 habe. 01:07:44.860 --> 01:07:48.000 Und das wäre unser Algorithmus gewesen. 01:07:48.460 --> 01:07:51.820 Auf der logarithmischen Skala eine Gerade heißt, er war dann wohl 01:07:51.820 --> 01:07:54.320 offenbar in irgendeiner Form exponentiell. 01:07:57.200 --> 01:07:58.920 Beziehungsweise quadratisch dann. 01:08:00.300 --> 01:08:01.420 Nee, exponentiell natürlich. 01:08:03.720 --> 01:08:08.240 Unser alternativer Algorithmus macht aber so eine umgeknickte 01:08:08.240 --> 01:08:15.700 Hyperbola, macht also das hier, hat dann demnach offenbar tatsächlich 01:08:15.700 --> 01:08:18.020 den Aufwand O von N. 01:08:19.940 --> 01:08:24.040 Und was ich Ihnen zeigen möchte, dass das also nicht an der Heskel 01:08:24.040 --> 01:08:26.480 -Implementierung jetzt irgendwie liegt, da habe ich Ihnen dann mal 01:08:26.480 --> 01:08:28.720 noch Java aufgeschrieben und C. 01:08:28.720 --> 01:08:32.900 Die sind ja recht ähnlich, das heißt, da konnte ich den gleichen 01:08:32.900 --> 01:08:36.360 Algorithmus nehmen, musste nur glaube ich einmal Main drumherum 01:08:36.360 --> 01:08:39.040 schreiben und einmal habe ich Class drumherum geschrieben. 01:08:39.580 --> 01:08:43.380 Habe es einmal in Java laufen lassen, einmal mit dem Visual C Compiler 01:08:43.380 --> 01:08:47.100 von Microsoft mit dem Optimierungs-Flagg groß O2. 01:08:48.460 --> 01:08:52.060 Und weil der im Vergleich zu Java so schlecht abgeschnitten ist, habe 01:08:52.060 --> 01:08:55.440 ich es dann nochmal durch den Intel C Compiler gejagt mit Pentium 4 01:08:55.440 --> 01:08:58.500 Optimierung und Hüdendü und Hasse nicht gesehen, was der alles 01:08:58.500 --> 01:08:59.060 geschafft hat. 01:09:01.540 --> 01:09:03.140 Jedenfalls marschieren wir auch hier lang. 01:09:04.160 --> 01:09:07.580 Und interessanterweise, also hier das ist MSC, 01:09:10.980 --> 01:09:15.200 diese dunkelblaue Linie ist der Intel Compiler und wenn Sie sich 01:09:15.200 --> 01:09:19.320 angucken, ganz knapp unten drunter ist der Java Compiler. 01:09:19.900 --> 01:09:22.780 Aus unerfindlichen Gründen ist in dem Fall Java tatsächlich schneller 01:09:22.780 --> 01:09:26.500 als der Intel C Compiler mit Pentium 4 Optimierung. 01:09:28.740 --> 01:09:31.340 Plädoyer für diese wunderschöne Sprache. 01:09:33.460 --> 01:09:39.200 Noch ein paar kleine Randbemerkungen zu der Folie, weil man da noch 01:09:39.200 --> 01:09:41.020 ein bisschen mehr sieht oder auch nicht sieht. 01:09:41.480 --> 01:09:42.600 Das möchte ich Ihnen erzählen. 01:09:43.720 --> 01:09:47.180 Hier, man sieht es einfach nicht so durch die Skala, liegt dann doch 01:09:47.180 --> 01:09:52.480 immerhin ein Zeitabschnitt von einer Sekunde für die Ausführung. 01:09:52.820 --> 01:09:56.140 Das heißt, der Intel Compiler und Java sind doch eine ganze Sekunde 01:09:56.140 --> 01:09:58.380 schneller bei einer Problemgröße von 25. 01:09:58.380 --> 01:10:03.020 Es sind nur 25 Einträge, also die 25. 01:10:03.320 --> 01:10:05.120 Fibonacci-Zahl gilt es da zu berichten. 01:10:06.180 --> 01:10:10.800 Der C Compiler brauchte drei Sekunden und Java und der Intel Compiler 01:10:10.800 --> 01:10:12.440 brauchten zwei Sekunden. 01:10:13.900 --> 01:10:16.900 Und das hier sieht jetzt natürlich nahe nebendran aus, also hier das 01:10:16.900 --> 01:10:19.400 ist in Millisekunden angegeben und das in Reduktionen. 01:10:20.200 --> 01:10:23.480 Nageln Sie mich nicht fest, aber gefühlsmäßig hat praktisch die eine 01:10:23.480 --> 01:10:27.020 Million oder doch ungefähr eine Million Durchläufe, die ich hier 01:10:27.020 --> 01:10:31.000 gemacht habe, damit die Zeiten einigermaßen akkurat sind, ungefähr 01:10:31.000 --> 01:10:33.280 genauso lange gedauert wie ein Durchlauf hier. 01:10:33.360 --> 01:10:36.480 Das heißt also hierzwischen ist dann praktisch ein Faktor von einer 01:10:36.480 --> 01:10:36.860 Million. 01:10:39.100 --> 01:10:41.420 Kann man dann mal so sagen, so effizient ist Haskell. 01:10:41.560 --> 01:10:43.380 Aber immerhin, man kann es ja sehr schön bedienen. 01:10:45.680 --> 01:10:50.160 Okay, O von N ist offenbar falsch, das heißt, wir müssen es uns dann 01:10:50.160 --> 01:10:51.420 wohl noch mal genauer angucken. 01:10:52.660 --> 01:10:56.180 Also hier oben haben wir dann doch sehr wahrscheinlich keinen Fehler 01:10:56.180 --> 01:10:59.680 gemacht, aber dann doch offenbar da unten. 01:11:00.360 --> 01:11:05.720 Und dazu gucken wir uns einfach mal an, die Zeit für ein Problem der 01:11:05.720 --> 01:11:07.120 Größe 1. 01:11:09.660 --> 01:11:11.920 Die Zeit ist in dem Fall konstant. 01:11:13.700 --> 01:11:19.440 Die Zeit für ein Problem der Größe N, schauen wir uns mal genauer an. 01:11:20.280 --> 01:11:34.540 Das ist ja dann die Zeit von T von N-1 plus den Aufruf von T von N-2. 01:11:38.120 --> 01:11:41.220 So, schauen wir uns mal an, was ist T von N-1? 01:11:42.700 --> 01:11:50.580 Gleiche Bauart, T von T von N-2 plus T von T von N-3. 01:11:50.580 --> 01:12:00.320 T von N-2 ist T von T von 01:12:08.600 --> 01:12:15.180 N -3 plus T von T von N-4. 01:12:16.180 --> 01:12:19.740 So, wenn wir das jetzt zusammennehmen und einmal zusammen 01:12:19.740 --> 01:12:27.140 aufschreiben, dann sehen wir, wir sind bei T von N gleich T von T von 01:12:27.140 --> 01:12:42.390 N -2 plus T von T von N-3 plus T von T von N-3 plus T von T von... 01:12:43.370 --> 01:12:43.770 Ach, 01:12:46.870 --> 01:12:47.810 Mist daneben. 01:12:51.840 --> 01:12:53.480 Und nun? 01:13:04.730 --> 01:13:05.530 Oh Mann! 01:13:10.660 --> 01:13:13.600 Aber schlau, wie ich war, habe ich es ja eben extra gespeichert. 01:13:23.940 --> 01:13:26.120 Also, dann ist es mir jetzt auch egal, in welcher Farbe wir 01:13:26.120 --> 01:13:26.620 weiterschreiben. 01:13:26.700 --> 01:13:30.400 Wir schreiben jetzt hier nur noch N-4 hin, machen die Klammer zu und 01:13:30.400 --> 01:13:35.000 erzählen Ihnen, dass Sie jetzt sehen, aha, wir haben hier offenbar die 01:13:35.000 --> 01:13:39.080 Zahl der Terme schon verdoppelt und nach dem Konstruktionsmuster sehen 01:13:39.080 --> 01:13:42.460 Sie auch ein, dass Sie offenbar jedes Mal die Zahl der Terme 01:13:42.460 --> 01:13:46.060 verdoppeln, wenn Sie so den Algorithmus haben wie hier und dass Sie 01:13:46.060 --> 01:13:52.660 deswegen eben nicht auf den Aufwand O von N kommen, sondern auf den 01:13:52.660 --> 01:13:55.500 Aufwand O von exponentiell. 01:13:58.100 --> 01:14:02.760 So, was ich Ihnen dazu noch zeigen möchte und mit Ihnen diskutieren 01:14:02.760 --> 01:14:06.860 möchte, es gibt für die Fibonacci-Zahlen einen beschlossenen 01:14:06.860 --> 01:14:12.580 Algorithmus, der so aussieht, Fib von N ist 1 plus Wurzel 5 durch 2 01:14:12.580 --> 01:14:17.440 hoch N minus 1 minus Wurzel 5 durch 2 hoch N durch Wurzel 5. 01:14:17.440 --> 01:14:20.800 Das ist nach dem Herrn Häuser, wenn Sie den Beweis sehen wollen, den 01:14:20.800 --> 01:14:23.660 tue ich Ihnen jetzt ungern an, deswegen lassen wir den, den schauen 01:14:23.660 --> 01:14:24.380 Sie dort nach. 01:14:26.860 --> 01:14:31.640 Aber die Frage ist, als geschlossene Formel sage ich ja immer ganz 01:14:31.640 --> 01:14:35.360 gerne oder ganz flott mal als Informatiker, naja, das ist dann O von 01:14:35.360 --> 01:14:35.700 1. 01:14:35.920 --> 01:14:37.960 Die Frage ist, ist es wirklich O von 1? 01:14:38.960 --> 01:14:42.020 Das müssen wir uns einfach überlegen, denn das N steht hier oben im 01:14:42.020 --> 01:14:49.040 Exponenten und dann sagen wir, okay, wir rechnen mit Wurzel 5, Wurzel 01:14:49.040 --> 01:14:54.460 5 ist eine Fließkommazahl und Fließkommazahlen, da haben wir ja direkt 01:14:54.460 --> 01:15:00.160 im Prozessor schon die Funktion exp, also um Potenzen auszurechnen, 01:15:00.560 --> 01:15:03.780 das heißt, das geht in vielleicht nicht einem, aber konstant vielen 01:15:03.780 --> 01:15:06.540 Taktzyklen und hängt nicht von diesem N hier ab. 01:15:06.540 --> 01:15:09.980 Das heißt, insofern könnten wir argumentieren, das hier geht 01:15:09.980 --> 01:15:13.820 tatsächlich alles in O von N und damit geht auch diese ganze Formel in 01:15:13.820 --> 01:15:14.340 O von N. 01:15:15.200 --> 01:15:18.460 Es kommt halt darauf an, wie genau Sie rechnen und wie groß Sie das N 01:15:18.460 --> 01:15:18.820 wählen. 01:15:18.900 --> 01:15:22.100 Wenn Sie damit Ihren Prozessor platzen lassen können, die Prozessoren 01:15:22.100 --> 01:15:25.940 arbeiten intern ja mit 80 Bit, aber auch die gehen irgendwann aus, 01:15:26.220 --> 01:15:28.900 wenn das irgendwann nicht mehr funktioniert, dann sind Sie natürlich 01:15:28.900 --> 01:15:33.340 ganz schnell außerhalb von O von N, weil Sie dann einfach das mit sich 01:15:33.340 --> 01:15:35.980 selber multiplizieren müssen, N mal und das mit sich selber 01:15:35.980 --> 01:15:39.680 multiplizieren, N mal, aber Sie fallen dann ja auch schlimmstenfalls 01:15:39.680 --> 01:15:41.900 in die Kategorie O von N. 01:15:42.920 --> 01:15:49.800 Was Sie aber nichtsdestotrotz bedenken müssen, immer wenn Sie mit O 01:15:49.800 --> 01:15:53.800 von N argumentieren oder damit rumrechnen sollen, theoretisch hat 01:15:53.800 --> 01:15:57.040 selbst der beste Algorithmus den Aufwand O von N. 01:15:58.320 --> 01:16:01.800 Egal wofür, weil Sie müssen ja immer die komplette Eingabe erstmal 01:16:01.800 --> 01:16:06.260 lesen und das braucht schlicht und ergreifend ja schon in Abhängigkeit 01:16:06.260 --> 01:16:08.340 von der Eingabelänge viel Zeit. 01:16:08.660 --> 01:16:12.080 Also können Sie jeden immer totschlagen, der sagt, er hätte einen 01:16:12.080 --> 01:16:14.620 guten Algorithmus gefunden, können Sie immer sagen, naja, die Eingabe 01:16:14.620 --> 01:16:17.300 liest du doch auch nur in O von N und damit ist dein Algorithmus auch 01:16:17.300 --> 01:16:17.920 nur O von N. 01:16:21.190 --> 01:16:25.430 Die Theoretiker klammern aus diesem Grund das natürlich aus. 01:16:28.510 --> 01:16:33.770 Und Sie werden sich damit ja dann auch noch genauer beschäftigen, aber 01:16:33.770 --> 01:16:37.550 an dieser Stelle sei gesagt, insbesondere bei Haskell kommt ja nochmal 01:16:37.550 --> 01:16:40.450 dazu, dass wir nicht mit Referenzsemantik arbeiten, sondern mit 01:16:40.450 --> 01:16:41.350 Wertesemantik. 01:16:41.350 --> 01:16:44.610 Das heißt, wenn wir irgendetwas übergeben an Haskell, übergeben wir 01:16:44.610 --> 01:16:48.130 nicht einen Zeiger darauf, auch die gleiche Datenstruktur, sondern 01:16:48.130 --> 01:16:51.890 kopieren zumindest semantisch jedes Mal die komplette Datenstruktur 01:16:51.890 --> 01:16:56.450 und haben deswegen auch immer den Aufwand O von N. 01:17:02.610 --> 01:17:03.010 Das was? 01:17:03.010 --> 01:17:03.770 Also, 01:17:09.450 --> 01:17:14.850 er meint jetzt, das Einlesen wäre an dieser Stelle konstant. 01:17:15.410 --> 01:17:19.330 Klar, wenn Sie 32 Bit auf einmal einlesen können oder 64 oder wie viel 01:17:19.330 --> 01:17:21.850 auch immer auf einmal einlesen können, ist es konstant, aber wenn Sie 01:17:21.850 --> 01:17:25.590 genau sind, ist es schon abhängig von der Anzahl der Bit, weil wenn 01:17:25.590 --> 01:17:30.670 Sie hier nicht mit Integers rechnen, so wie sie auch der Prozessor 01:17:30.670 --> 01:17:34.130 direkt unterstützt, sondern wegen mir mit irgendwelchen großen 01:17:34.130 --> 01:17:38.130 Dezimalzahlen, die einfach Schritt für Schritt, also Sie erinnern sich 01:17:38.130 --> 01:17:42.470 an BCD, Binary Coded Decimal, wo Sie dann halt tatsächlich Byte für 01:17:42.470 --> 01:17:47.930 Byte 0, 1, 2, 3, 4, 5 und so weiter stehen haben, dann ist es ja, wie 01:17:47.930 --> 01:17:50.650 Sie einsehen, sicher abhängig von der Länge der Stellen, wie lange Sie 01:17:50.650 --> 01:17:51.930 brauchen, um das einzulesen. 01:17:52.870 --> 01:17:57.230 Aber das ist, wie gesagt, so eine theoretische Argumentation auf der 01:17:57.230 --> 01:17:59.950 Grundlage und für uns gilt O von 1. 01:18:00.650 --> 01:18:03.590 Deswegen auch auf dieser Folie, damit, wenn Sie das dann heute auf dem 01:18:03.590 --> 01:18:06.510 Übungsblatt berechnen, dass das dann auch schön klappt. 01:18:08.530 --> 01:18:11.410 Ich bedanke mich recht herzlich und wünsche Ihnen ein schönes Wochenende.