WEBVTT

00:09.760 --> 00:13.600
Kann ich ja schon mal beginnen mit dem inhaltlichen Teil der

00:13.600 --> 00:14.240
Vorlesung.

00:14.360 --> 00:18.340
Und zwar haben wir heute drei verschiedene Dinge vor uns.

00:18.940 --> 00:22.840
Und zwar hatten wir beim letzten Mal über Testen gesprochen und noch

00:22.840 --> 00:25.020
nicht über die Assertions, die hier im Titel stehen.

00:25.120 --> 00:25.960
Das werde ich heute machen.

00:26.680 --> 00:31.860
Dann gibt es eine Vorlesungseinheit zu parsen, suchen und sortieren.

00:32.760 --> 00:36.160
Und da müssen wir dann mal ein bisschen gucken, wie wir auch zeitlich

00:36.160 --> 00:38.000
durchkommen, weil ich sie da zwischendurch auch noch mal ein bisschen

00:38.000 --> 00:38.680
was fragen werde.

00:38.680 --> 00:41.980
Wenn wir noch Zeit haben, werden wir noch den nächsten Foliensatz zum

00:41.980 --> 00:44.500
Thema Finden und Beheben von Fehlern anfangen.

00:44.920 --> 00:47.640
Wenn nicht, ist das aber auch nicht so schlimm, weil wir den ohnehin

00:47.640 --> 00:50.340
nicht mehr ganz schaffen wegen der Verzögerung mit den Assertions.

00:50.620 --> 00:53.580
Aber das ist thematisch, denke ich mal, auch kein Problem.

00:54.640 --> 00:57.900
Genau, deswegen nehme ich mir jetzt auch noch mal die Zeit und fasse

00:57.900 --> 01:00.620
ein bisschen zusammen, was wir beim letzten Mal gemacht hatten in

01:00.620 --> 01:01.520
diesem Foliensatz.

01:02.000 --> 01:05.560
Hier also noch mal die Lernziele von dem Foliensatz zu testen sind

01:05.560 --> 01:08.160
Assertions, einfach nur, um kurz zu rekapitulieren.

01:08.800 --> 01:11.040
Was haben Sie beim letzten Mal zu dem Thema gehört?

01:12.320 --> 01:17.500
Sie hatten einerseits gehört, was die Definition eines Softwarefehlers

01:17.500 --> 01:18.060
ist.

01:19.940 --> 01:23.200
Wir hatten da diese verschiedenen Beispiele gesehen und dann also auch

01:23.200 --> 01:24.960
noch mal die Begrifflichkeiten unterschieden.

01:25.000 --> 01:28.580
Ist es einerseits ein Versagen des Systems, dass es nicht den

01:28.580 --> 01:31.420
Anforderungen oder dem erwarteten Verhalten entspricht?

01:31.540 --> 01:35.440
Bis hin zu Gibt es im Programmcode einen Fehler, sodass das Programm

01:35.440 --> 01:38.060
eben nicht das tut, was seine Spezifikation sagt?

01:38.160 --> 01:39.220
Ersteres war ein Failure.

01:39.960 --> 01:42.740
Letzteres war auf Englisch dann ein Fault und auf Deutsch redet man so

01:42.740 --> 01:45.660
ein bisschen ungenau, oftmals nur von Fehlern.

01:46.980 --> 01:51.380
Sie kennen ja außerdem die Kriterien für gute Testfälle und können

01:51.380 --> 01:54.640
anhand dieser Kriterien gute Testfälle erstellen.

01:54.760 --> 01:57.160
Und da hatten wir eben eine Folie mit diesen verschiedenen Kriterien,

01:57.240 --> 02:00.860
zum Beispiel, ich sage jetzt mal nicht alle, aber dass ein Testfall

02:00.860 --> 02:04.760
eine bestimmte Eigenschaft aus der Spezifikation abtestet, dass

02:04.760 --> 02:08.960
Testfälle möglichst kurz sind und dass für Testfälle auch der Bezug

02:08.960 --> 02:12.680
zur Spezifikation hergestellt ist, also auch klar ist, was testet

02:12.680 --> 02:14.060
dieser Testfall denn jetzt überhaupt?

02:14.280 --> 02:17.620
Denn das kann sich ja im Laufe der Zeit, in der Evolution meines

02:17.620 --> 02:19.840
Softwareprojekts auch ändern, die Spezifikation.

02:19.920 --> 02:21.680
Und dann würde ich natürlich auch herausfinden wollen, welche

02:21.680 --> 02:24.700
Testfälle dafür betroffen sind, beispielsweise.

02:25.820 --> 02:26.520
Genau der nächste Punkt.

02:26.620 --> 02:28.620
Sie können Zusicherungen, Assertions anwenden.

02:28.720 --> 02:30.120
Das kommt jetzt eben heute erst.

02:30.220 --> 02:32.000
Das können Sie von daher noch nicht.

02:33.160 --> 02:36.100
Sie können unterscheiden, welche Arten von Fehlern durch Testen

02:36.100 --> 02:38.160
entdeckt beziehungsweise nicht entdeckt werden können.

02:38.260 --> 02:42.280
Das war diese Unterscheidung, dass es ja verschiedene Arten oder

02:42.280 --> 02:45.340
verschiedene Gründe dafür gibt, dass Software versagt, also ein

02:45.340 --> 02:45.980
Failure hat.

02:46.640 --> 02:49.600
Unter anderem waren Fehler dabei, dass eben Programmcode nicht der

02:49.600 --> 02:50.880
Spezifikation entspricht.

02:51.000 --> 02:53.700
Und das ist eben, das sind die Arten von Fehlern, die wir durch Testen

02:53.700 --> 02:56.380
direkt auch feststellen können.

02:57.200 --> 02:59.920
Aber andere Gründe für Versagen können eben auch sein, dass

02:59.920 --> 03:02.320
Anforderungen falsch verstanden wurden, dass Anforderungen falsch

03:02.320 --> 03:05.740
interpretiert wurden oder dass auch Benutzer das System nicht so

03:05.740 --> 03:08.040
benutzen, wie es vorgesehen war.

03:09.180 --> 03:12.140
Das sind also andere Gründe, warum Software versagen kann, die man mit

03:12.140 --> 03:16.640
Testen teilweise auch ein bisschen begegnen kann, weil man oftmals

03:16.640 --> 03:20.100
auch durch Testen ein besseres Verständnis der Anforderungen bekommt,

03:21.240 --> 03:24.600
für die das Testen aber nicht dediziert da ist.

03:24.840 --> 03:28.960
Also insbesondere diese Fehler, die eben Fehler der Art sind, dass

03:28.960 --> 03:32.600
Programmcode nicht der Spezifikation entspricht, das sind diese Arten

03:32.600 --> 03:35.060
von Fehlern, die ich mit Testen entdecken kann.

03:35.860 --> 03:38.780
Gleichzeitig natürlich die Einschränkung, dass ich nie die Garantie

03:38.780 --> 03:42.300
habe, dass nur weil ich mir gut überlegt habe, welche Testfälle ich

03:42.300 --> 03:44.860
habe, dass ich damit garantieren kann, dass mein Code keine

03:44.860 --> 03:45.840
Programmfehler mehr hat.

03:45.960 --> 03:49.160
Also das dürfen Sie nie denken, dass Sie sagen, ich habe eine

03:49.160 --> 03:50.920
Testabdeckung von irgendwie jede Zeile.

03:51.320 --> 03:53.780
Also hat mein Programm keine Fehler mehr.

03:53.880 --> 03:56.720
Sie können eigentlich davon ausgehen, dass jedes einigermaßen komplexe

03:56.720 --> 03:57.860
Programm auch noch Fehler hat.

03:58.340 --> 04:00.600
Kann sein, dass die irgendwo so ganz versteckt sind und nie eigentlich

04:00.600 --> 04:03.100
zum Tragen kommen, weil der Teil des Codes nie in einer bestimmten

04:03.100 --> 04:04.420
Kombination ausgeführt wird.

04:04.820 --> 04:07.860
Aber Sie können eigentlich davon ausgehen, dass irgendwo noch Fehler

04:07.860 --> 04:08.400
drin stecken.

04:09.680 --> 04:10.940
Genau, das ist auch schon gleich der nächste Punkt.

04:11.000 --> 04:14.880
Sie können begründen, warum Testen notwendig und sinnvoll ist.

04:14.960 --> 04:18.720
Es ist einfach so, dass man beim Programmieren Fehler macht und dass

04:18.720 --> 04:21.060
Fehler, die passieren, können eben auch gemacht werden, dass dann doch

04:21.060 --> 04:26.480
mal irgendwo die bei Array Punkt Length das Minus eins vergessen wird

04:26.480 --> 04:27.400
in der Schleife oder so.

04:27.520 --> 04:28.960
Können Sie davon ausgehen, dass es passiert.

04:28.960 --> 04:33.080
Und um das eben abzufangen, bevor Software dann im Einsatz versagt,

04:33.580 --> 04:36.340
ist dieser Punkt der Qualitätssicherung wichtig und dabei eben auch

04:36.340 --> 04:38.560
der Aspekt des Testens.

04:39.560 --> 04:41.280
Genau, und weil das so wichtig ist, habe ich jetzt noch mal

04:41.280 --> 04:41.620
wiederholt.

04:42.780 --> 04:45.700
Was Sie jetzt, wie gesagt, noch nicht kennen, ist dieser Teil der

04:45.700 --> 04:46.640
Assertions.

04:47.300 --> 04:51.040
Und da würden wir dann jetzt mal hinspringen.

04:51.380 --> 04:54.320
Sie hatten sowieso schon gesehen, dass man dieses Schlüsselwort Assert

04:54.320 --> 04:58.100
beim Testen eben benutzen kann, um anzugeben, welche Ergebnisse man

04:58.100 --> 05:01.260
erwartet in einem Test, also dass der Test bei den Dreiecken zum

05:01.260 --> 05:05.260
Beispiel für eine bestimmte Kombination von Werten die Rückgabe

05:05.260 --> 05:10.060
invalid macht, würde man mit so einem Assert Schlüsselwort angeben.

05:12.380 --> 05:14.900
Man kann aber eben mit Assertions noch ein bisschen mehr machen.

05:15.120 --> 05:18.280
Allgemein Erwartungen, welche Werte an einer bestimmten Stelle im

05:18.280 --> 05:23.360
Programmcode zu erwarten sind, aufzuschreiben und zu dokumentieren.

05:24.480 --> 05:28.980
Das mag also überhaupt die Verwendung von diesem Schlüsselwort Assert

05:28.980 --> 05:31.300
mag manch einer so machen wie hier in diesem Comic.

05:31.380 --> 05:33.180
Das hatte ich, glaube ich, letztes Mal schon kurz gezeigt,

05:33.780 --> 05:34.380
dargestellt.

05:34.820 --> 05:38.720
Also zwei Entwickler, die sagen hier bei deinem Test, sagt er im

05:38.720 --> 05:40.700
blauen T-Shirt, steht Assert Falls.

05:41.320 --> 05:43.480
Wollte das nicht Assert True heißen hier an der Stelle?

05:47.680 --> 05:50.220
Aber wenn ich Assert True hingeschrieben habe, wurde der Test rot.

05:51.120 --> 05:52.500
Also habe ich Assert Falls hingeschrieben.

05:52.500 --> 05:55.400
Das ist natürlich genau falschrum, dass man sagt, ich schreibe halt

05:55.400 --> 05:57.260
das hin, was beim Test auch tatsächlich zurückkommt.

05:57.440 --> 06:01.140
Nein, man sollte beim Assert natürlich das hinschreiben, was erwartet

06:01.140 --> 06:02.740
ist und was das korrekte Ergebnis ist.

06:02.860 --> 06:05.380
Sonst ist es leicht, die Tests immer, also wenn man es so rummacht,

06:05.460 --> 06:08.440
ist es leicht, Tests immer so zu schreiben, dass sie auch positiv

06:08.440 --> 06:10.760
durchlaufen und sozusagen grün werden.

06:12.300 --> 06:13.660
Genau, was man, das macht man also nicht.

06:13.740 --> 06:17.100
Was man machen sollte mit Assertions ist anzugeben, was soll an einer

06:17.100 --> 06:21.300
bestimmten Stelle im Code gelten und welche Ergebnisse beim Testen

06:21.300 --> 06:22.300
erwarte ich.

06:23.060 --> 06:25.800
Hier ist diese Verwendung von dem Assert Schlüsselwort nochmal im Code

06:25.800 --> 06:26.200
gezeigt.

06:26.280 --> 06:29.360
Das kennen Sie schon von vorhin aus unserem oder von letzter Woche aus

06:29.360 --> 06:30.400
diesem Triangle Beispiel.

06:32.260 --> 06:35.420
Wir verwenden eben Assert, jetzt nehme ich mal eben den Stift dazu.

06:41.480 --> 06:46.080
An dieser Stelle, um zu sagen, für diesen Test erwarten wir jetzt,

06:46.660 --> 06:51.640
dass die Rückgabe unserer getesteten Methode Classify ist, dass dieses

06:51.640 --> 06:56.920
gegebene Dreieck gleichschenklig, gleichseitig war es glaube ich, ist

06:56.920 --> 06:57.940
an der Stelle.

07:00.460 --> 07:04.200
Genau, diese Assertions kann ich aber auch, wie gesagt, allgemeiner

07:04.200 --> 07:04.720
verwenden.

07:05.000 --> 07:09.640
Ich kann also an Stellen dokumentieren, ganz allgemein, welche

07:09.640 --> 07:13.840
Bedingungen zur Laufzeit gelten sollen, also welche Werte Variablen

07:13.840 --> 07:17.360
haben sollen oder auch welche Werte im Vergleich zueinander haben

07:17.360 --> 07:18.620
wollen, also nicht nur in Tests.

07:20.440 --> 07:23.740
Allgemein formuliert, ich erlaube es, oder Assertions erlauben ist,

07:24.060 --> 07:27.160
angenommene erforderliche Bedingungen zur Laufzeit zu prüfen.

07:27.440 --> 07:29.160
Und die Syntax hatten wir auch noch gar nicht gesehen.

07:30.260 --> 07:32.560
Man kann einfach nur schreiben Assert Bedingungen, wie wir das hier

07:32.560 --> 07:33.940
oben im Testfall gemacht haben.

07:34.480 --> 07:38.620
Also das Schlüsselwort Assert und dann etwas, was sich auswertet zu

07:38.620 --> 07:42.100
einem bool'schen Ausdruck oder man kann sogar mit Doppelpunkt und

07:42.100 --> 07:44.580
Anführungszeichen noch eine detaillierte Fehlermeldung dahinter

07:44.580 --> 07:48.060
schreiben, die eben dann vom Programm geworfen werden soll, sozusagen,

07:48.060 --> 07:51.100
falls die Bedingung mal nicht eingehalten wird.

07:52.720 --> 07:56.940
Genau, damit kann ich ausdrücken, was an einer Stelle im Code gelten

07:56.940 --> 07:57.300
soll.

07:58.840 --> 08:01.140
Wie gesagt, kann man das ja auch allgemeiner verwenden für

08:01.140 --> 08:04.060
Zusicherungen und da schauen wir uns jetzt mal typische Arten von

08:04.060 --> 08:08.060
solchen Zusicherungen an und an welchen Stellen im Programm Code die

08:08.060 --> 08:08.920
stehen können.

08:09.260 --> 08:13.380
Und zwar anhand eines Beispiels, dass ein Skalarprodukt von zwei

08:13.380 --> 08:17.420
Vektoren U und V berechnet.

08:17.420 --> 08:23.040
Diese Methode nimmt zwei Eingabewerten, ein Array namens U für den

08:23.040 --> 08:26.620
einen Vektor mit den verschiedenen Doppelwerten und ein Array namens V

08:26.620 --> 08:28.820
für den anderen Vektor mit den verschiedenen Doppelwerten.

08:29.360 --> 08:31.800
Ich überspringe jetzt erst mal noch die roten Stellen, beschreibe mal,

08:31.880 --> 08:33.000
was die Methode allgemein macht.

08:33.420 --> 08:38.900
Ich iteriere einfach von Index 0 bis Index N, also der Länge der

08:38.900 --> 08:43.100
Vektoren und multipliziere immer die beiden Werte, die ich da vorfinde

08:43.100 --> 08:46.560
und addiere diese ganzen multiplizierten Werte auf, bilde also das

08:46.560 --> 08:47.300
Skalarprodukt.

08:48.060 --> 08:51.840
Und wenn ich ja diesen Beispiel Code habe, dann kann ich eben

08:51.840 --> 08:55.880
formulieren, was ich oder was gültige Werte von diesen verschiedenen

08:55.880 --> 09:00.380
Variablen, die hier vorkommen, im Verlauf meines Programms sein

09:00.380 --> 09:00.640
können.

09:00.740 --> 09:03.960
Insbesondere würde ich am Anfang erst mal davon ausgehen, dass diese

09:03.960 --> 09:07.020
beiden Vektoren gleich lang sind, denn sonst kann ich ja zwei Vektoren

09:07.020 --> 09:10.600
nicht miteinander multiplizieren oder das Skalarprodukt bilden, wenn

09:10.600 --> 09:11.600
sie unterschiedlich lang sind.

09:11.980 --> 09:14.840
Das würde man dann eine Vorbedingung nennen, wenn man eine solche

09:14.840 --> 09:17.120
Assertion an den Anfang einer Methode schreibt.

09:17.880 --> 09:21.520
Dann kann ich auch innerhalb einer Schleife etwas formulieren, was

09:21.520 --> 09:22.340
immer gelten soll.

09:23.360 --> 09:26.200
Das nennt man dann eine Schleifeninvariante und wir gucken uns gleich

09:26.200 --> 09:28.080
mal an, was man da formulieren könnte.

09:28.440 --> 09:33.140
Und man kann eben am Ende der Methode formulieren, was am Ende der

09:33.140 --> 09:35.520
Methode immer gelten soll.

09:36.200 --> 09:39.300
Das nennt man dann eine Nachbedingung, was immer gelten soll, nachdem

09:39.300 --> 09:40.660
eine Methode abgearbeitet wurde.

09:41.180 --> 09:43.200
Vielleicht schauen wir uns erst mal...

09:44.240 --> 09:46.420
Ich klappe es mal einfach auf an der Stelle.

09:47.120 --> 09:51.820
Was man als erstes anschauen wollte, wäre, was nach der Methode immer

09:51.820 --> 09:52.040
gilt.

09:52.140 --> 09:55.580
Und da kann man einfach sozusagen nochmal in diesem Fall die

09:55.580 --> 10:01.000
Spezifikation wiederholen und sagen, am Ende soll gelten, dass das

10:01.000 --> 10:07.960
Ergebnis S eben die Summe ist über die einzelnen Produkte der jeweils

10:07.960 --> 10:09.420
Werte am gleichen Index.

10:11.400 --> 10:15.180
Also die Summe von 0 bis zur Länge meines Arrays minus 1, weil ich

10:15.180 --> 10:18.120
immer mit 0 indiziere, über entsprechend diese Werte.

10:18.240 --> 10:20.400
Das ist also sozusagen die Definition des Skalarprodukts.

10:20.800 --> 10:24.580
Und dieser Wert S soll eben in diesem Zusammenhang mit den Eingaben U

10:24.580 --> 10:26.840
und V stehen.

10:27.380 --> 10:28.980
Das nennt man dann, wie gesagt, die Nachbedingung.

10:29.340 --> 10:31.880
Und man kann sogar auch noch Bedingungen zwischendurch angeben, dass

10:31.880 --> 10:35.000
man nämlich hier sagt, naja, auch innerhalb der Schleife soll ja

10:35.000 --> 10:39.360
gelten, dass meine Summe, die ich bis dahin aufsummiert habe, schon

10:39.360 --> 10:43.360
eben dieser Summe entspricht bis zum Index, wo ich gerade bin.

10:43.860 --> 10:47.020
Also ich kann auch bei jeder Schleifeniteration schon aussagen oder

10:47.020 --> 10:50.260
prüfen, ob der Wert, den ich gerade als Zwischenergebnis, als Summe

10:50.260 --> 10:55.700
berechnet habe, eigentlich der erwartete Wert eben dieser sozusagen

10:55.700 --> 10:58.700
halb aufsummierten Summe ist.

11:00.140 --> 11:02.820
Genau, damit sehen Sie auch schon eben diese drei Arten von

11:02.820 --> 11:05.440
Zusicherungen, die in Programmen Sinn machen, nämlich hier unten

11:05.440 --> 11:07.300
nochmal aufgeführt Vorbedingung.

11:07.460 --> 11:10.020
Etwas muss vor dem Aufruf der Methode gelten.

11:10.520 --> 11:11.400
Eine Nachbedingung.

11:11.540 --> 11:14.020
Etwas soll nach dem Aufruf einer Methode gelten.

11:14.140 --> 11:17.040
Also was ist das Ergebnis dieser Methode nochmal ausgedrückt?

11:17.260 --> 11:18.880
Und eine Schleifeninvariante.

11:19.460 --> 11:23.100
Etwas soll in jeder Schleifeniteration gelten.

11:24.660 --> 11:26.980
Ja, schön, sagen Sie jetzt, dass man sowas ausdrücken kann.

11:27.120 --> 11:28.460
Aber wozu braucht man das?

11:29.420 --> 11:31.960
Fragt sich natürlich immer, wozu kann man sowas verwenden?

11:31.960 --> 11:36.740
Naja, und solche Zusicherungen sind eben ein weiteres Hilfsmittel, um

11:36.740 --> 11:43.060
bei der Entwicklung von Software Fehler zu vermeiden, weil man eben

11:43.060 --> 11:47.420
durch solche Assertions Annahmen darüber, welche Werte Variablen haben

11:47.420 --> 11:50.760
oder welche Bedingungen ein bisschen allgemeiner gesprochen gelten

11:50.760 --> 11:54.920
sollen, explizit machen kann im eigenen Programm Code, anstatt einfach

11:54.920 --> 11:58.120
nur als Programmierer implizit davon ausgegangen zu sein, dass in

11:58.120 --> 12:01.180
unserem Beispiel eben die beiden Vektoren immer gleich sind, kann man

12:01.180 --> 12:04.840
durch eine Assertion diese Annahme explizit machen.

12:06.100 --> 12:09.100
Typischerweise würde man bei Vorbedingungen eben sowas machen, dass

12:09.100 --> 12:12.920
man Restriktionen auf Parametern und auch auf globalen Variablen

12:13.960 --> 12:16.780
angibt, eben für eine Methode, die aufgerufen wird und diese

12:16.780 --> 12:18.820
Vorbedingungen dann an den Anfang der Methode schreibt.

12:19.560 --> 12:23.340
Eine Nachbedingung ist eben dafür da, die Effekte einer Methode formal

12:23.340 --> 12:26.900
zu beschreiben, also zu beschreiben, welcher funktionale Zusammenhang

12:26.900 --> 12:29.560
zum Beispiel soll denn jetzt gelten zwischen den Eingabe Parametern

12:29.560 --> 12:32.680
und zwischen meiner hier berechneten, meines berechneten Ausgabe

12:32.680 --> 12:33.220
Parameters.

12:33.800 --> 12:36.540
Das muss nicht unbedingt eine komplette Definition dessen sein, was

12:36.540 --> 12:37.260
die Methode tut.

12:37.340 --> 12:41.760
Es kann auch nur ein Teil der Rückgabewerte oder eine gewisse

12:41.760 --> 12:43.820
Partitionierung davon sein.

12:44.760 --> 12:48.260
Und wir können eben an zentralen Programmpunkten auch beliebige

12:48.260 --> 12:51.880
weitere Eigenschaften explizit festhalten, wie zum Beispiel in so

12:51.880 --> 12:55.760
einer Schleifenvariante immer wieder das formulieren.

12:57.400 --> 13:00.600
Und ich muss immer noch sagen, naja, wozu brauche ich das?

13:01.100 --> 13:04.720
Das Ultimative eigentlich, was man mit solchen Zusicherungen machen

13:04.720 --> 13:10.300
möchte, ist, die auch zu verwenden, um Korrektheitsaussagen bezüglich

13:10.300 --> 13:13.520
eines gegebenen Programms mathematisch beweisen zu können.

13:13.780 --> 13:16.420
Also das ist das Ziel der Software Verifikation.

13:17.060 --> 13:20.520
Und da werden solche Zusicherungen auch oft benutzt, um Beweise ein

13:20.520 --> 13:24.280
bisschen zu vereinfachen und abzukürzen, um es demjenigen, der was

13:24.280 --> 13:28.220
beweisen soll, zu ermöglichen, sich an gewissen Stellen auf gewisse

13:28.220 --> 13:32.100
Annahmen zu verlassen, verlassen zu können und andererseits dann noch

13:32.100 --> 13:34.340
beweisen zu müssen, dass diese Annahme wirklich immer gilt.

13:34.480 --> 13:37.440
Also so ein bisschen ein großes Problem, ein Softwareprogramm beweisen

13:37.440 --> 13:40.680
zu müssen, aufzuteilen an bestimmten Stellen anhand dieser Annahmen,

13:40.740 --> 13:43.660
um dann nur noch kleinere Teile beweisen zu können.

13:44.580 --> 13:46.220
Das ist, wie gesagt, das ultimative Ziel.

13:46.280 --> 13:50.500
Und das funktioniert jetzt für beliebigen Java-Code nicht einfach so.

13:51.740 --> 13:54.360
Trotzdem ist es aber immer noch sinnvoll, solche Zusicherungen zu

13:54.360 --> 13:57.420
machen, denn selbst wenn ich es nicht unbedingt für mein Programm, was

13:57.420 --> 14:01.040
ich verwende, mathematisch beweisen kann, ist es immer noch hilfreich,

14:01.100 --> 14:06.360
diese Annahmen eben explizit zu dokumentieren und dann auch im Laufe

14:06.360 --> 14:11.340
meines meiner Tests oder meines Qualitätssicherungsprozesses auch

14:11.340 --> 14:15.100
eigentlich ähnlich wie Testfälle, die immer mitlaufen, immer so eine

14:15.100 --> 14:18.380
Überprüfung zu haben, ob die Annahmen hier an der Stelle auch gelten,

14:18.460 --> 14:19.960
wenn ich mein System teste.

14:19.960 --> 14:22.420
Also es ist so eine Art zusätzlicher oder kann man auch als

14:22.420 --> 14:24.560
zusätzlichen Test sehen.

14:26.520 --> 14:29.460
Genau, wie sieht das in Java aus mit diesen Zusicherungen?

14:29.620 --> 14:31.640
Haben wir ja gerade schon motivierend eingeführt.

14:32.020 --> 14:35.360
In Java kann man eben allgemein solche Zusicherungen mit dem

14:35.360 --> 14:38.660
Schlüsselwort Assert, wie wir es aus den Tests schon kennen, in den

14:38.660 --> 14:40.480
Programmtext schreiben.

14:41.040 --> 14:44.540
Der Vorteil davon ist, dass ich diese Ausdrücke, die dann da stehen,

14:44.660 --> 14:48.280
auch direkt schon von der Java Virtual Machine überprüfen lassen kann.

14:49.460 --> 14:53.320
Also wenn ich mein Programm dann in einem Modus laufen lasse, wo die

14:53.320 --> 14:56.280
Assertions geprüft werden, das kann man nämlich auch ausschalten, dann

14:56.280 --> 15:01.540
würde bei jedem Programmlauf, wo so eine Assertion mal nicht wahr ist,

15:01.600 --> 15:03.240
dann sofort eine Fehlermeldung gegeben werden.

15:03.620 --> 15:05.920
Deswegen sage ich, das ist so eine Art zusätzlicher Test.

15:06.440 --> 15:11.080
In meiner Testumgebung kann ich das zum Beispiel sinnvoll machen.

15:12.100 --> 15:15.220
Nachteil davon ist, man kann nur Java Syntax verwenden, um die

15:15.220 --> 15:16.300
Bedingungen auszudrücken.

15:16.300 --> 15:19.540
Also man kann nicht natürlich sprachlich ein bisschen abstraktere

15:19.540 --> 15:22.020
Bedingungen beschreiben oder die sich vielleicht noch auf andere

15:22.020 --> 15:22.800
Methoden bezieht.

15:24.240 --> 15:27.960
Deswegen ist es häufig einfacher, Zusicherungen nur in Kommentaren zu

15:27.960 --> 15:30.780
schreiben, also natürlich sprachlich zu beschreiben, was denn jetzt

15:30.780 --> 15:33.420
hier die Annahmen sind über die verschiedenen Variablen und Werte.

15:34.320 --> 15:36.680
Das ist der Vorteil, dass man die volle sprachliche Freiheit hat.

15:36.780 --> 15:39.280
Vielleicht auch ein bisschen einfacher, denn in natürlicher Sprache

15:39.280 --> 15:40.420
können wir ja alle gut reden.

15:40.500 --> 15:43.640
Das können wir von nicht von Geburt an, aber von drei Jahren an oder

15:43.640 --> 15:43.860
so.

15:44.520 --> 15:47.740
Der Nachteil da ist aber, dass man das nicht oder nur sehr

15:47.740 --> 15:50.940
eingeschränkt automatisiert dann überprüfen kann, ob diese

15:50.940 --> 15:53.460
Zusicherungen, die da formuliert sind, auch wirklich zur Laufzeit so

15:53.460 --> 15:54.160
gelten oder nicht.

15:55.380 --> 15:58.760
Trotzdem ist es aber vielleicht noch besser als nichts, denn in jedem

15:58.760 --> 16:02.820
Fall sind solche Assertions eine gute Dokumentation der

16:02.820 --> 16:06.160
Verantwortlichkeiten zwischen Methoden Nutzer und Methoden

16:06.160 --> 16:06.760
Implementierer.

16:06.840 --> 16:07.380
Was heißt das?

16:08.740 --> 16:12.280
So eine Precondition gibt bei einer Methode dann ganz explizit an, was

16:12.280 --> 16:16.620
derjenige, der die Methode geschrieben hat, annimmt, welche Werte die

16:16.620 --> 16:18.740
Eingabedaten zum Beispiel haben dürfen.

16:18.860 --> 16:22.300
Und wenn Sie selber dann also eine Methode schreiben, die eine

16:22.300 --> 16:26.120
Methode, die von jemand anderem geschrieben ist, verwendet, dann ist

16:26.120 --> 16:29.620
es für Sie natürlich sehr hilfreich, genau sehen zu können, was hat

16:29.620 --> 16:30.960
derjenige denn jetzt hier beschrieben?

16:31.120 --> 16:33.980
Welche Parameterwerte überhaupt nur gültig für meine Methode sind oder

16:33.980 --> 16:38.380
welche weiteren Zusammenhänge zwischen diesen Parameterwerten geben

16:38.380 --> 16:38.640
müssen?

16:38.720 --> 16:41.960
Das macht dann Ihre Aufgabe, quasi eine Methode zu schreiben, die die

16:41.960 --> 16:45.860
andere Methode benutzt, dann deutlich einfacher.

16:45.980 --> 16:47.480
Und das Gleiche dann auch für die Nachbedingungen.

16:47.880 --> 16:51.760
Wenn eine Methode, die Sie aufrufen, genau angibt, was sie zurückgibt

16:51.760 --> 16:54.780
oder Bedingungen angibt, Zusicherungen darüber angibt, was sie

16:54.780 --> 16:57.420
zurückgibt, dann können Sie auch leichter damit arbeiten und müssen

16:57.420 --> 17:00.860
nicht per Trial and Error ausprobieren, was diese fremde Methode

17:00.860 --> 17:01.740
sozusagen macht.

17:03.240 --> 17:06.440
Diese Zusicherung von Verantwortlichkeiten zwischen Methoden Nutzer

17:06.440 --> 17:10.100
und Methoden Implementierer nennt man auch Design by Contract, dass

17:10.100 --> 17:12.640
man also sagt, ich entwerfe die verschiedenen Methoden in meinem

17:12.640 --> 17:16.120
Programm ja ohnehin immer, also ich muss ja aufteilen, wie ich meine

17:16.120 --> 17:17.760
Funktionalität in Methoden aufteile.

17:17.940 --> 17:21.420
Und dabei benutze ich aber solche Verträge, also Zusicherungen, um

17:21.420 --> 17:24.400
genau zu formulieren, was ist denn jetzt die Verantwortlichkeit

17:24.400 --> 17:26.840
dessen, der die Methode aufruft, nämlich die richtigen Parameter

17:26.840 --> 17:27.580
bereitzustellen?

17:27.880 --> 17:30.800
Und wenn diese Vorbedingung gegeben ist, was ist dann die

17:30.800 --> 17:33.700
Verantwortlichkeit desjenigen, der die Methode implementiert hat?

17:33.700 --> 17:38.420
Welche Werte sind noch dann gültig für die Rückgabe Parameter?

17:39.080 --> 17:41.680
Wie gesagt, das nennt man Design by Contract.

17:43.020 --> 17:45.420
Diese Assertions in Java, hatte ich eben schon kurz gesagt, werden

17:45.420 --> 17:49.380
standardmäßig nicht ausgewertet und überprüft, sondern man muss so ein

17:49.380 --> 17:54.460
bestimmtes Flag, also dieses E A für Enable Assertion Flag beim Aufruf

17:54.460 --> 17:59.060
dazu angeben, damit die Assertions dann zur Laufzeit auch überprüft

17:59.060 --> 17:59.280
werden.

17:59.340 --> 18:02.620
Das ist eben die Idee, dass man solche Assertions dann während der

18:02.620 --> 18:06.180
Qualitätssicherung und im Testbetrieb eingeschaltet lässt, sie dann

18:06.180 --> 18:09.500
aber, wenn man das System in einen Produktivbetrieb übernimmt, dann

18:09.500 --> 18:10.460
auch wieder ausschalten kann.

18:10.580 --> 18:13.360
Weil wenn das System produktiv gerade das Flugzeug steuert und dann

18:13.360 --> 18:15.680
die Assertions fehlschlägt und das Programm abbricht mit Fehler, dann

18:15.680 --> 18:18.000
ist es natürlich nicht so hilfreich, sondern dann kann man es lieber

18:18.000 --> 18:21.020
weiter versuchen, ob es nicht doch noch irgendwie funktioniert, sage

18:21.020 --> 18:21.300
ich mal.

18:22.560 --> 18:23.880
Man kann es ausschalten, man muss es auch nicht.

18:23.940 --> 18:26.900
Das kommt dann darauf an, wie man selber den Prozess sich überlegt.

18:28.400 --> 18:30.520
Genau, jetzt ist hier gesagt, Zusicherungen in Java kann ich über

18:30.520 --> 18:32.560
Asserts oder über natürliche Sprache machen.

18:33.380 --> 18:36.100
Es gibt auch noch andere Sprachen, die auch extra dafür zugeschnitten

18:36.100 --> 18:38.000
sind, solche Zusicherungen in Java zu machen.

18:38.100 --> 18:42.400
Da wäre ein Beispiel die sogenannte Java Modeling Language, die eben

18:43.480 --> 18:46.560
dazu da ist, noch ein bisschen detailliertere Aussagen, formale

18:46.560 --> 18:50.920
Spezifikationen über das Verhalten von Java Code zu machen.

18:51.160 --> 18:54.620
Zum Beispiel kann man da noch was darüber aussagen, was denn gelten

18:54.620 --> 18:56.300
soll, wenn eine Exception geworfen ist.

18:56.760 --> 19:00.580
Als Beispiel und damit ist das oder das ist auch ein aktiver Zweig in

19:00.580 --> 19:04.540
der Forschung mit solchen Spezifikationen oder Annotationen, was Vor-

19:04.540 --> 19:07.720
und Nachbedingungen und weitere Arten der Bedingungen sein soll, dann

19:07.720 --> 19:12.060
auch formale Aussagen über alle möglichen Pfade in meinem Programm

19:12.060 --> 19:15.360
treffen zu können, dass ich also wirklich für Programme einer

19:15.360 --> 19:17.780
bestimmten Größe, die auch bestimmte Einschränkungen haben, wirklich

19:17.780 --> 19:21.740
beweisen kann, dass irgendwelche Eigenschaften immer erfüllt sind.

19:22.280 --> 19:25.400
Wenn Sie das interessiert, dieses Thema, kann ich schon mal jetzt die

19:25.400 --> 19:29.840
Vorlesungen Formale Systeme und Formale Systeme 2 empfehlen, wo man da

19:29.840 --> 19:32.720
noch tiefer ins Detail reingeht in solche Themen.

19:35.540 --> 19:37.980
Genau, so viel allgemein zu den Zusicherungen in Java.

19:38.080 --> 19:40.340
Wir werden uns jetzt noch mal genauer die verschiedenen Arten der

19:40.340 --> 19:43.480
Zusicherungen anschauen und auch Beispiele dann, wie sowas in Java

19:43.480 --> 19:46.100
aussehen kann, noch mal anschauen.

19:49.180 --> 19:51.160
Genau, ein bisschen was haben wir davon, haben wir jetzt eigentlich

19:51.160 --> 19:51.600
auch schon gesagt.

19:51.600 --> 19:55.040
Also Zusicherung gibt eine Eigenschaft an, die bei der Ausführung des

19:55.040 --> 19:57.140
Programms an der entsprechenden Stelle erfüllt sein muss.

19:58.280 --> 20:01.600
Vorbedingung muss eben vor der Abarbeitung eines bestimmten Methoden

20:01.600 --> 20:02.460
Rumpfs erfüllt sein.

20:03.440 --> 20:05.820
So sind in Java dann die Vorbedingungen einfach definiert, dass sie

20:05.820 --> 20:07.200
eben am Anfang der Methode stehen.

20:07.300 --> 20:08.600
Das macht es zu einer Vorbedingung.

20:09.100 --> 20:11.900
Eine Nachbedingung muss erfüllt sein, nachdem die Methode abgearbeitet

20:11.900 --> 20:12.120
wurde.

20:12.420 --> 20:15.200
Es ist also auch eine Bedingung, die am Ende der Methode steht oder

20:15.200 --> 20:15.960
vorm Return.

20:16.780 --> 20:19.880
Und Klassen in Varianten gibt es in Java oder gibt es allgemein auch

20:19.880 --> 20:24.600
noch, die insgesamt den gültigen Zustand eines Objekts beschreiben.

20:24.700 --> 20:25.980
Das ist also noch wieder was Neues.

20:26.060 --> 20:29.000
Das sind in Varianten, die nicht unbedingt innerhalb einer Schleifen

20:29.000 --> 20:32.500
Iterationen gelten, sondern in Varianten, die irgendwelche gültigen

20:32.500 --> 20:36.220
Zusammenhänge zwischen Attributen einer Klasse oder auch nur gültige

20:36.220 --> 20:40.340
Bedingungen für ein einzelnes Attribut einer Klasse angeben.

20:40.680 --> 20:43.480
Zum Beispiel gleich hier, wenn ich eine Klasse habe, ist egal, was für

20:43.480 --> 20:48.020
eine, die ein Attribut in Length hat, dann könnte eine solche

20:48.020 --> 20:51.760
Klasseninvariante sein, dass ich sage Naja, Länge muss immer größer

20:51.760 --> 20:52.460
gleich Null sein.

20:52.620 --> 20:54.360
Also Länge darf nicht negativ sein.

20:54.400 --> 20:56.820
Das macht gar keinen Sinn für meine Klasse, die ich gerade

20:56.820 --> 20:57.500
implementiere.

20:58.260 --> 20:59.520
Und das kann man in zwei Weisen machen.

20:59.600 --> 21:03.080
Man kann also einerseits für so eine Klasseninvariante schreiben, das

21:03.080 --> 21:05.540
natürlich sprachlich in einem Kommentar schreiben.

21:05.860 --> 21:07.780
Gut, das sieht jetzt auch nicht besonders natürlich sprachlich aus,

21:07.980 --> 21:11.400
aber es ist halt einfach irgendwie Text im Kommentar oder in Java, um

21:11.400 --> 21:16.460
Klasseninvarianten zu formulieren, kann man vor das Ende jeder Public

21:16.460 --> 21:19.300
Methode ein entsprechendes Assert-Statement hinschreiben.

21:19.380 --> 21:23.260
Das ist ein bisschen unpraktisch, vielleicht gelöst, aber das ist eben

21:23.260 --> 21:26.300
die Art und Weise, wie man in Java solche Klasseninvarianten dann

21:26.300 --> 21:27.800
formulieren kann.

21:28.560 --> 21:30.100
Vor dem Ende jeder Public Methode.

21:30.660 --> 21:32.460
Genau, Schleifeninvarianten hat man eben auch schon gesehen.

21:32.780 --> 21:35.540
Eine Zusicherung, die am Anfang und Ende eines jeden Durchlaufs der

21:35.540 --> 21:37.940
dazugehörigen Schleife erfüllt sein muss.

21:38.000 --> 21:40.260
Und die schreibt man typischerweise dann auch nur einmal hin, dass man

21:40.260 --> 21:43.140
sie nicht am Anfang und am Ende testen muss, was nicht ganz das

21:43.140 --> 21:45.520
Gleiche ist, aber Schreibarbeit ein bisschen spart.

21:46.300 --> 21:50.300
Okay, also das verschiedene Arten von Zusicherung, typische Arten von

21:50.300 --> 21:50.740
Zusicherung.

21:52.940 --> 21:55.680
Genau, wie gerade angekündigt, könnten wir uns jetzt auch mal ein

21:55.680 --> 21:59.300
Beispiel für diese Dinge in Java anschauen, was dann hoffentlich auch

21:59.300 --> 22:03.640
nochmal motiviert, wozu sowas hilfreich sein kann.

22:04.340 --> 22:07.260
Da würde ich Sie nämlich gleich erstmal bitten, zu versuchen, das

22:07.260 --> 22:11.660
Problem in diesem Programmcode hier noch ohne Assertions direkt durch

22:11.660 --> 22:12.440
Hinschauen zu finden.

22:12.560 --> 22:14.700
Und es kann jetzt auch bei diesem Beispiel sein, dass Sie es auch

22:14.700 --> 22:16.040
schon durch Hinschauen finden können.

22:16.580 --> 22:18.840
Und dann gucken wir uns aber mal, wie man es mit Assertions hätte

22:18.840 --> 22:19.480
vermeiden können.

22:19.880 --> 22:22.280
Also nehmen wir mal an, wir wollen eine Klasse schreiben zur

22:22.280 --> 22:25.760
Verwaltung der Uhrzeit, also Uhrzeit, wie auf einem Digital-Wecker

22:25.760 --> 22:28.320
dargestellt, mit Stunden und Minuten.

22:28.640 --> 22:29.300
Ganz einfach.

22:29.740 --> 22:34.100
Diese Klasse hat also zwei Attribute in Hour und in Minute, Stunden

22:34.100 --> 22:37.080
und Minuten, hat einen Konstruktor, der erstmal mit einer bestimmten

22:37.080 --> 22:41.660
Startzeit anfängt und hat zum Beispiel eine Methode, dass ich Zeit

22:41.660 --> 22:43.260
drauf addieren kann.

22:43.260 --> 22:46.600
Also dass ich vielleicht jetzt sagen möchte, ich möchte diese Uhrzeit

22:46.600 --> 22:48.940
um fünf Minuten weiter schalten.

22:49.180 --> 22:54.740
Und diese Methode addiert entsprechend dann die übergebene Zeit als

22:54.740 --> 22:56.860
Parameter auf die Stunden und die Minuten drauf.

22:59.040 --> 23:01.120
Die würde natürlich auch noch irgendwelche anderen Dinge tun, sonst

23:01.120 --> 23:02.540
wäre sie relativ witzlos, so eine Methode.

23:02.640 --> 23:03.960
Aber wir schauen uns oder so eine Klasse.

23:04.100 --> 23:07.540
Wir schauen uns jetzt mal nur diese drei Methoden an.

23:07.660 --> 23:10.620
Und wie gesagt, vielleicht sehen Sie schon durch scharfes Hinschauen,

23:10.740 --> 23:13.200
was da wahrscheinlich schräg ist, wobei wir jetzt ja keine

23:13.200 --> 23:16.380
Kompetenzspezifikation hier angegeben haben, aber nur so durch den

23:16.380 --> 23:17.300
gesunden Menschenverstand.

23:19.320 --> 23:21.420
Da sieht was nicht gut aus, ich lasse vielleicht noch mal ein bisschen

23:21.420 --> 23:23.000
nachdenken, aber ja, bitte.

23:23.680 --> 23:25.020
Genau, das ist genau der Punkt.

23:25.420 --> 23:28.660
Man hätte jetzt hier einen Fehler, dass die variable Minuten auch über

23:28.660 --> 23:30.060
60 Minuten lang werden würde.

23:30.100 --> 23:32.200
Und das macht bei einer Uhrzeit, wie wir jetzt alle mit gesunden

23:32.200 --> 23:34.220
Menschenverstand wissen, eben keinen Sinn.

23:34.360 --> 23:37.360
Also wenn ich jetzt schon die Minute auf 59 stehen habe und dann drei

23:37.360 --> 23:41.280
Minuten drauf addiere, dann würde hier Minute den Wert 62 haben.

23:41.280 --> 23:42.580
Und das macht wahrscheinlich keinen Sinn.

23:42.980 --> 23:45.260
Genau, also wie gesagt, bei diesem einfachen Beispiel kann man das

23:45.260 --> 23:47.820
auch noch durch scharfes Hinsehen erkennen.

23:48.560 --> 23:52.200
Wie kann man das aber auch mit Assertions explizit machen und dann ein

23:52.200 --> 23:54.860
bisschen systematischer zu der Einsicht kommen, dass hier ein Fehler

23:54.860 --> 23:55.300
passiert?

23:55.740 --> 23:59.100
Naja, man kann sich eben beim Entwurf dieser Klasse schon überlegen,

23:59.200 --> 24:02.940
was sind Annahmen über die möglichen Werte der Attribute, die immer

24:02.940 --> 24:03.520
gelten müssen?

24:03.620 --> 24:07.360
Und da könnte man dann also leicht zu der Einsicht kommen, dass wenn

24:07.360 --> 24:10.920
ich so eine klasse Time habe und in our Minute hier habe, dass ich

24:10.920 --> 24:14.780
eine gewisse Klasseninvariante eigentlich annehme, nämlich dass der

24:14.780 --> 24:17.600
Wert von our immer zwischen 0 und 24 ist.

24:18.320 --> 24:21.320
Oder zwischen 0 und 23, je nachdem, wie man es implementiert.

24:22.100 --> 24:23.820
Ach klar, echt kleiner 24 steht da ja auch genau.

24:24.240 --> 24:29.060
Und dass der Wert von Minute immer zwischen 0 und echt kleiner 60,

24:29.200 --> 24:31.620
also zwischen 0 und 59 ist.

24:32.700 --> 24:35.420
Und das wäre jetzt einfach nur eine Invariante als Kommentar

24:35.420 --> 24:37.080
modelliert oder aufgeschrieben.

24:37.080 --> 24:40.840
Wie gesagt, kann man eine Klasseninvariante in Java auch so umsetzen,

24:40.900 --> 24:43.800
dass man diese Invariante immer ans Ende jeder Public Methode schreibt

24:43.800 --> 24:45.060
und Public Constructor auch.

24:45.460 --> 24:48.460
Das heißt, man schreibt dann hier an diese Stelle die Invariante

24:48.460 --> 24:49.020
nochmal hin.

24:49.480 --> 24:51.340
Auch wirklich jetzt mit den Assert Keywords.

24:51.440 --> 24:53.840
Und an dieser Stelle schreibt man die Invariante auch nochmal hin.

24:54.680 --> 24:56.760
Wenn man dann im Testbetrieb das Ganze ein bisschen laufen lässt,

24:56.860 --> 25:00.720
kommt man dann vielleicht auch mal auf den Fall, dass hier die

25:00.720 --> 25:02.220
Assertion nicht gilt.

25:02.840 --> 25:05.720
Die kann eben verletzt sein und ist, wie gesagt, man kann es dadurch

25:05.720 --> 25:10.520
merken, dass man das Ganze mal ausführt und der Wert über 24 geht und

25:10.520 --> 25:13.380
dann eben die JVM zur Laufzeit einem auch einen Fehler geben würde.

25:13.700 --> 25:15.480
Oder vielleicht sieht man es hier auch schon ein bisschen direkter

25:15.480 --> 25:19.940
beim Hinsehen, dass das nicht immer gilt, wenn ich irgendwas drauf

25:19.940 --> 25:22.160
addiere und dann kann ich nicht sicherstellen, dass es immer noch

25:22.160 --> 25:24.120
unter 24 oder kleiner als 24 ist.

25:24.500 --> 25:28.040
Also diese Postcondition, diese Klasseninvariante hier kann verletzt

25:28.040 --> 25:28.300
sein.

25:28.760 --> 25:32.060
Dann, wenn ich erst mal weiß, was schiefgehen kann, ist es oftmals

25:32.060 --> 25:33.640
relativ leicht, sowas zu beheben.

25:33.640 --> 25:36.220
An der Stelle könnte ich jetzt zum Beispiel eine Methode

25:36.220 --> 25:40.140
normalisieren, der Zeit einfügen, also hier zu sagen, ich addiere erst

25:40.140 --> 25:44.040
mal wie gehabt und rufe dann aber nochmal Normalize Time auf, wo ich

25:44.040 --> 25:48.060
dann überprüfe, wenn die Minutenzahl, die ich jetzt gerade

25:48.060 --> 25:49.660
ausgerechnet habe, größer gleich 60 ist.

25:49.820 --> 25:53.220
Dann ziehe ich 60 von der Minutenzahl ab und addiere bei der Stunde

25:53.220 --> 25:53.880
eins drauf.

25:54.060 --> 25:58.060
Und wenn die Stundenzahl größer gleich 24 ist, dann ziehe ich auch

25:58.060 --> 25:59.060
nochmal 24 ab.

26:00.380 --> 26:02.800
Könnte man an diesem Beispiel noch weitermachen und überlegen, was

26:02.800 --> 26:06.380
sind da jetzt also implizite Preconditions, die ich eigentlich jetzt

26:06.380 --> 26:08.440
gerade für diese Methode hier mache.

26:10.260 --> 26:13.680
Das Beispiel habe ich jetzt gar nicht weiter vorbereitet, aber

26:13.680 --> 26:15.640
vielleicht noch zum kurzen Mitdenken.

26:18.440 --> 26:22.320
Also immer noch nicht ganz wohl dokumentiert, was hier eigentlich die

26:22.320 --> 26:23.040
Annahmen sind.

26:23.160 --> 26:26.680
Mit dieser Methode des Normalize Time wäre jetzt ja die Annahme, dass

26:26.680 --> 26:30.360
diese Zeit, die hier reinkommt, auch entsprechend wohl geformt ist,

26:30.360 --> 26:34.380
also dass da nicht in den Minuten größer 25 was drinsteht oder größer

26:34.380 --> 26:38.580
24 oder dass da keine 80 Minuten drinstehen, weil dann würde diese

26:38.580 --> 26:40.260
Normalisierung hier eben auch nicht funktionieren.

26:40.780 --> 26:43.000
Aber genau, einfach nur um das Prinzip klarzumachen.

26:43.120 --> 26:48.120
Ich habe ein Programmcode und ich kann eben mit Zusicherung explizit

26:48.120 --> 26:51.600
machen, was meine Annahmen über das Verhalten dieses Programmcodes

26:51.600 --> 26:56.360
sind und kann dann entweder dynamisch beim Testen Fehler finden oder

26:56.360 --> 27:00.840
auch einfach durch das dann explizit gemacht haben, besser sehen, dass

27:00.840 --> 27:04.000
irgendwo ein Fehler noch vorhanden ist und vorliegt.

27:07.080 --> 27:11.200
Okay, stellt sich vielleicht die Frage, wann benutze ich denn jetzt so

27:11.200 --> 27:15.720
ein Assert in meinem Programmcode und wann benutze ich eine If-Abfrage

27:15.720 --> 27:18.880
mit einer Exception hinterher, weil es ja irgendwie ähnliche Dinge

27:18.880 --> 27:19.080
sind.

27:19.160 --> 27:22.680
Ich möchte Fälle abfangen, die irgendwie nicht normal und vielleicht

27:22.680 --> 27:24.120
auch so ein bisschen nicht gewünscht sind.

27:26.120 --> 27:30.700
Asserts verwendet man dann, wenn man Annahmen macht, also man selber

27:30.700 --> 27:34.180
als Programmierer Annahmen macht zur Korrektheit des eigenen

27:34.180 --> 27:34.900
Programms.

27:35.000 --> 27:37.300
Und ich kann das eben auch verwenden zur Dokumentation.

27:37.720 --> 27:42.360
Ich sollte es aber nur verwenden für zur Laufzeit nicht behandelbare

27:42.360 --> 27:45.660
Fehler, weil das eben dazu führt, dass mein System dann den Fehler

27:45.660 --> 27:49.820
zurückliefert und sozusagen abbricht, also sich beendet.

27:51.780 --> 27:55.240
Das heißt, das ist eigentlich der wichtigste Punkt für nicht zur

27:55.240 --> 27:57.060
Laufzeit behandelbare Fehler.

27:57.500 --> 27:59.660
Dafür haben die Assertions aber auch noch den Vorteil, dass sie

27:59.660 --> 28:02.340
abschaltbar sind, dass ich eben sagen kann, in dem Testbetrieb habe

28:02.340 --> 28:05.160
ich diese Assertions an und im Produktivbetrieb vielleicht nicht,

28:05.480 --> 28:08.500
vielleicht auch, weil mir der Performance Overhead zu teuer ist.

28:08.920 --> 28:12.920
An diesem Beispiel, so einer Methode, dass ich bestimmte Balance, also

28:12.920 --> 28:15.700
einen bestimmten Geldwert setzen möchte für mein Konto oder so, könnte

28:15.700 --> 28:18.560
ich also hier sagen, Assert, der Betrag, der übergeben ist bei den

28:18.560 --> 28:21.560
Parametern, ist größer als null und wenn ja, dann setze ich ihn auch

28:21.560 --> 28:21.920
entsprechend.

28:22.920 --> 28:26.460
Auf der anderen Seite die If-Abfrage mit Exception verwende ich, wenn

28:26.460 --> 28:30.100
ich zum Beispiel Eingabedaten des Benutzers überprüfen möchte.

28:30.260 --> 28:32.960
Dann, wenn die falsch sind, würde ich ja eher eine Rückmeldung geben

28:32.960 --> 28:36.480
wollen an den Benutzer und nicht gleich mein ganzes Programm beenden.

28:37.900 --> 28:42.380
Kann das auch verwenden für Sonderfälle und insbesondere oder auch

28:42.380 --> 28:45.920
hier der wichtigste Punkt ist eigentlich, kann es verwenden für von

28:45.920 --> 28:49.060
aufrufenden Funktionen behandelbare Fehler.

28:50.440 --> 28:53.120
Das deckt auch noch nicht unbedingt alle Punkte ab, denn was bei den

28:53.120 --> 28:56.140
Exceptions eben noch anders ist als bei den Assertions ist, dass ich

28:56.140 --> 28:57.140
sie nicht abschalten kann.

28:57.320 --> 29:00.860
Also auch wenn ich solche Überprüfungen haben will, die noch zur

29:00.860 --> 29:04.400
Laufzeit oder im Produktivsystem, was ich später zum Einsatz bringe,

29:04.420 --> 29:07.800
zum Beispiel bei meinem Kunden noch aktiv sind, dann könnte ich

29:07.800 --> 29:10.700
vielleicht auch eher Exceptions verwenden, um dann auch in dem Fall,

29:10.900 --> 29:13.700
wo dann doch mal ein Fehler im Produktivsystem auftritt, dann auch

29:13.700 --> 29:17.060
eine detaillierte Rückmeldung zu bekommen, was schiefgegangen ist.

29:17.820 --> 29:19.940
Und das würde ich dann eben...

29:19.940 --> 29:22.440
könnte ich die gleiche Überprüfung im Prinzip hier auch so machen,

29:22.500 --> 29:27.420
dass ich sage, ich überprüfe mit dem If, ob dieser Wert B den

29:27.420 --> 29:29.660
gewünschten oder im gewünschten Bereich liegt.

29:29.800 --> 29:33.600
Und wenn nicht, werfe ich eben eine zum Beispiel Illegal Argument

29:33.600 --> 29:38.420
Exception und wenn doch, dann setze ich eben den Wert Balance auf den

29:38.420 --> 29:39.360
Zielwert.

29:41.020 --> 29:42.940
Okay, also das ist mal die Abwägung, die Sie da treffen müssen.

29:43.080 --> 29:46.340
Verwenden Sie Assert oder verwenden Sie eine If-Abfrage mit

29:46.340 --> 29:47.200
Exceptions.

29:48.560 --> 29:52.720
Bevor wir zum Ende von dieser Vorlesungseinheit kommen, noch ein paar

29:52.720 --> 29:54.520
Worte zur statischen Analyse.

29:55.180 --> 30:00.060
Wir haben ja auch letzte Woche dann schon gesehen, dass Testen eben so

30:00.060 --> 30:01.720
eine dynamische Überprüfung ist.

30:01.900 --> 30:06.620
Ich führe mein Programm aus und prüfe halt anhand konkreter Daten, ob

30:06.620 --> 30:08.320
für den Fall irgendwas funktioniert.

30:08.580 --> 30:11.220
Kann aber natürlich keine Aussage treffen, ob mein Programm

30:11.220 --> 30:13.960
funktioniert für eben Kombinationen von Daten.

30:14.400 --> 30:17.540
Bei unserem Dreieck das Beispiel Kombinationen von anderen Längen oder

30:17.540 --> 30:19.320
so, die ich nicht getestet habe.

30:20.540 --> 30:24.120
Das macht es eben gerade so schwierig, Testfälle auszuwählen.

30:24.220 --> 30:26.840
Ich muss entscheiden, was sind denn jetzt gute Werte, die ich

30:26.840 --> 30:31.940
auswähle, um eine gute Test Case Selection zu machen.

30:32.500 --> 30:34.840
Man könnte sich jetzt fragen, naja, wenn diese Auswahl der Testfälle

30:34.840 --> 30:37.880
so schwierig ist, warum kann ich da nicht einfach alle Eingaben, alle

30:37.880 --> 30:40.420
Eingabe, alle möglichen Eingaben testen?

30:40.860 --> 30:43.120
Die Antwort da ist vielleicht auch naheliegend bei wiederum

30:43.120 --> 30:44.080
komplexeren Programmen.

30:44.140 --> 30:45.440
Das sind viel zu viele.

30:46.020 --> 30:49.020
Also wenn Sie ein Programm haben, was nur einen Wert, einen Integer

30:49.020 --> 30:49.540
Wert nimmt.

30:50.000 --> 30:52.600
Selbst dann haben Sie schon ziemlich viel zu testen, weil Sie dann vom

30:52.600 --> 30:56.100
minimalen Integer Wert bis zum maximalen alle einzelnen Werte

30:56.100 --> 30:56.880
durchtesten müssen.

30:57.140 --> 31:00.800
Aber sobald es dann zwei Eingaben werden, kriegen Sie eben das Produkt

31:00.800 --> 31:01.080
davon.

31:01.220 --> 31:04.580
Also sehr viele mehr Möglichkeiten, was getestet werden muss.

31:04.740 --> 31:09.360
Also das explodiert Ihnen sofort, was die Anzahl der möglichen

31:09.360 --> 31:11.580
Eingaben für Ihr Programm sind.

31:12.000 --> 31:13.940
Also das Management der Testfälle wäre dann auch nicht mehr

31:13.940 --> 31:16.900
praktikabel und die Laufzeit vielleicht nicht eines einzelnen

31:16.900 --> 31:20.660
Testfalls, aber der Testfälle insgesamt wäre viel, viel, viel zu groß.

31:22.120 --> 31:24.780
Also ich kann nicht testen, indem ich einfach alle Eingaben

31:24.780 --> 31:25.920
ausprobiere.

31:26.120 --> 31:28.760
Ich muss immer diese Auswahl treffen beim Testen.

31:29.580 --> 31:32.580
Ein alternatives Vorgehen, um es in gewisser Weise doch zu

31:32.580 --> 31:37.000
ermöglichen, über alle Pfade, über alle Eingaben Aussagen zu treffen,

31:37.140 --> 31:42.300
ist eben das eben schon genannte formale Verifizieren von Code, also

31:42.300 --> 31:46.320
die Idee, ein Programm irgendwie in eine logische Formel zu übersetzen

31:46.320 --> 31:50.600
und dann zu versuchen, zu beweisen, formal zu beweisen, dass die

31:50.600 --> 31:53.400
Spezifikation oder vielleicht auch nur ausgewählte Eigenschaften

31:53.400 --> 31:55.160
daraus gelten.

31:55.860 --> 31:57.200
Da gibt es verschiedene...

31:57.200 --> 31:59.680
Also wie gesagt, es ist ein ganz riesengroßer Bereich in der

31:59.680 --> 32:01.440
Informatikforschung, der sich damit beschäftigt.

32:01.880 --> 32:03.680
Verschiedene Logiken, die man da verwenden kann.

32:04.320 --> 32:06.600
Man muss natürlich auch eine Spezifikation haben, die formal

32:06.600 --> 32:07.280
beschrieben ist.

32:07.360 --> 32:10.020
Das kann man schlecht gegen eine natürlichsprachige Spezifikation

32:10.020 --> 32:10.340
haben.

32:10.340 --> 32:16.120
Und wenn man das, also sowohl so eine Spezifikation hat und auch das

32:16.120 --> 32:19.180
Programm entsprechend transformieren kann, dann kann man eben entweder

32:19.180 --> 32:23.000
von Hand solche Beweise führen oder es gibt da auch schon Ansätze, um

32:23.000 --> 32:27.140
Rechner unterstützt oder sogar vollautomatisch Beweise zu führen.

32:27.560 --> 32:30.820
Das Ganze nennt man dann auch für die Begrifflichkeit statische

32:30.820 --> 32:34.900
Programm Analyse oder eben formale Verifikation, sowas machen zu

32:34.900 --> 32:35.120
können.

32:35.280 --> 32:40.420
Wie gesagt, Vorlesungen, formale Systeme geht da weiter ins Detail,

32:40.500 --> 32:41.040
wie das aussieht.

32:44.180 --> 32:47.040
Okay, dann kommen wir zu diesem Teil der Vorlesung auch schon zur

32:47.040 --> 32:47.720
Zusammenfassung.

32:48.180 --> 32:51.840
Wir hatten über Tests gesprochen und ich hatte motiviert auch anhand

32:51.840 --> 32:56.300
einiger prominenter Beispiele, dass ausgiebiges Testen eben

32:56.300 --> 32:57.220
unerlässlich ist.

32:57.660 --> 33:01.220
Software quasi immer Fehler enthält und Fehler eben dramatische

33:01.220 --> 33:02.500
Konsequenzen haben können.

33:03.000 --> 33:07.000
Testen eben eine Möglichkeit ist, Fehler schon im Entwicklungsprozess

33:07.000 --> 33:08.680
selber abfangen zu können.

33:08.680 --> 33:11.200
Es ist nicht die einzige Möglichkeit, das zu tun.

33:11.380 --> 33:13.660
Also gerade bei sicherheitskritischen Systemen verlässt man sich jetzt

33:13.660 --> 33:16.140
auch nicht nur darauf, das System zu testen.

33:16.380 --> 33:18.360
Wir haben ja eben gesehen, Ausfall der Testfälle ist schwierig,

33:18.800 --> 33:20.960
sondern da gibt es dann auch noch weitere Maßnahmen, dass man zum

33:20.960 --> 33:24.720
Beispiel sagt, man baut auch gewisse Fehler Toleranz ein, wenn Teile

33:24.720 --> 33:28.080
meines Systems Fehler dann doch haben und irgendwie Exceptions

33:28.080 --> 33:29.580
zurückliefern oder gar nichts mehr.

33:30.180 --> 33:33.020
Dann sind andere Teile des Systems so gebaut, dass sie mit so einem

33:33.020 --> 33:36.020
Versagen einer einzelnen Teilkomponente zum Beispiel trotzdem umgehen

33:36.020 --> 33:36.380
können.

33:36.380 --> 33:42.060
Durch Redundanz zum Beispiel, indem die verschiedene Komponenten

33:42.060 --> 33:45.820
mehrfach implementiert sind, also wirklich drei verschiedene Versionen

33:45.820 --> 33:48.480
einer Komponente implementiert werden, wo dann hoffentlich nur einen

33:48.480 --> 33:49.080
Fehler hat.

33:49.340 --> 33:51.440
Da gibt es also verschiedene weitere Techniken dann auch für.

33:51.560 --> 33:55.400
Aber Testen ist eben eine sehr wichtige Technik, die auch wirklich für

33:55.400 --> 33:58.480
alle Arten von Systemen relevant ist.

33:59.420 --> 34:02.940
Ziel des Testens ist es eben zum einen nachzuweisen, dass

34:02.940 --> 34:04.300
Funktionalität erfüllt ist.

34:04.300 --> 34:07.260
Das schafft man auch durch diese detaillierten Vergleiche mit der

34:07.260 --> 34:08.080
Spezifikation.

34:08.280 --> 34:11.000
Man kann dann anhand der Testfälle prüfen, sind denn jetzt wirklich

34:11.000 --> 34:14.840
alle Sätze sozusagen in meiner Spezifikation auch durch Testfälle

34:14.840 --> 34:15.680
abgedeckt?

34:15.740 --> 34:18.920
Und damit kann ich sagen Ja, die Funktionalität ist erfüllt.

34:19.600 --> 34:22.960
Und auf der anderen Seite ist Ziel des Testens dann auch Fehler zu

34:22.960 --> 34:23.320
finden.

34:23.640 --> 34:27.380
Was ja Sie erinnern sich, die Motivation war oder dieses ein bisschen

34:27.380 --> 34:28.280
doppelte Ziel.

34:28.800 --> 34:32.100
Die Motivation dazu war, dass Testen auch nicht nur vom Programmierer

34:32.100 --> 34:34.960
selber gemacht werden sollte, sondern das oftmals Sinn macht,

34:35.460 --> 34:39.340
dedizierte Tester und ein separates Qualitätssicherungsteam zusätzlich

34:39.340 --> 34:40.120
auch noch zu haben.

34:42.120 --> 34:44.860
Genau, Tests sollten so viele Situationen wie möglich abdecken.

34:44.980 --> 34:48.360
Und gleichzeitig ist die Auswahl von geeigneten Testfällen eben nicht

34:48.360 --> 34:49.680
so einfach.

34:50.220 --> 34:55.060
Und wenn Sie sich beim Formulieren von Testfällen an die vorgestellten

34:55.060 --> 34:58.640
Kriterien und Teststrategien halten, dann verbessert das die Qualität

34:58.640 --> 35:01.520
der Tests, weil es natürlich nicht unbedingt hilfreich ist, wenn Sie

35:01.520 --> 35:04.140
einfach für Ihr Programm 100 Tests schreiben und sagen Juhu, ich habe

35:04.140 --> 35:07.100
100 Tests geschrieben, wenn die 100 Tests eigentlich quasi alle das

35:07.100 --> 35:09.660
Gleiche oder alles was Uninteressantes testen, dann haben Sie

35:09.660 --> 35:10.700
eigentlich gar nichts gezeigt.

35:11.080 --> 35:14.000
Sondern wenn Sie schon den Aufwand treiben, 100 Tests zu schreiben,

35:14.100 --> 35:17.100
dann sollten diese 100 auch so ausgewählt sein, dass sie möglichst

35:17.100 --> 35:21.160
gute Testfälle sind und auch einer Teststrategie folgen.

35:22.440 --> 35:24.780
Genau, schließlich hatten wir uns die Zusicherungen Assertions

35:24.780 --> 35:29.840
angeschaut, mit denen ich angenommene erforderliche Bedingungen zur

35:29.840 --> 35:33.740
Laufzeit auch noch mal prüfen kann, das auch zur Qualitätssicherung

35:33.740 --> 35:34.940
verwenden kann.

35:36.460 --> 35:39.060
Bevor ich übergehe zum nächsten Foliensatz, habe ich hier noch eine

35:39.060 --> 35:45.520
Folie, eine Werbefolie zwischendurch mitgebracht und zwar veranstaltet

35:45.940 --> 35:49.260
die Fachschaft, Fachschaft Mathematik Informatik, eine

35:49.260 --> 35:53.600
Orientierungsveranstaltung nennt sich mit Schwung ins zweite Semester,

35:53.740 --> 35:58.380
wo Sie einfach hingehen können, um, wenn Sie irgendwelche Probleme bei

35:58.380 --> 36:01.600
sich jetzt im ersten Semester festgestellt haben oder es müssen auch

36:01.600 --> 36:03.700
keine Probleme sein, einfach so ein bisschen unsicher sind.

36:04.300 --> 36:05.440
Wie geht es jetzt alles weiter?

36:05.520 --> 36:07.440
Habe ich jetzt alles richtig und gut gemacht?

36:08.740 --> 36:10.880
Ich bin mit meinem Übungsschein nicht so gut klargekommen, wie ich das

36:10.880 --> 36:11.180
dachte.

36:11.400 --> 36:13.140
Oder was mache ich denn jetzt im zweiten Semester?

36:13.580 --> 36:16.940
Wenn Sie solche Arten von Fragen haben, können Sie am Dienstag, den 6

36:16.940 --> 36:17.320
.2.

36:18.020 --> 36:22.280
in den Keller, in die Räume, die da angegeben sind, gehen, kriegen da

36:22.280 --> 36:23.300
auch was zu essen und zu trinken.

36:23.300 --> 36:27.960
Und können sich da eben von den Fachschaftlern so ein bisschen beraten

36:27.960 --> 36:30.680
lassen, wie es dann jetzt auch weitergehen kann.

36:31.260 --> 36:33.860
Also wenn Sie Lust haben, können Sie da vorbeigehen.

36:35.400 --> 36:37.820
Genau, ein paar Literaturhinweise für diese Vorlesung habe ich immer

36:37.820 --> 36:38.020
noch.

36:38.340 --> 36:39.440
Ach, da ist vielleicht noch dazu gesagt.

36:39.720 --> 36:42.820
Ich habe diese Folie mit den Literaturhinweisen, die in jeder

36:42.820 --> 36:46.380
Vorlesung hinten immer dran steht, nicht immer gezeigt, aber Sie

36:46.380 --> 36:49.960
können die Vorlesungsfolien sicher herunterladen und beim Vor- oder

36:49.960 --> 36:53.520
Nachbereiten der Vorlesung haben Sie diese Folie dann hoffentlich auch

36:53.520 --> 36:53.960
schon gesehen.

36:54.360 --> 36:56.760
Und hatte ich ganz am Anfang ja auch schon gesagt, wenn mal Inhalte

36:56.760 --> 37:00.840
unklar sind, hilft es auch oft, das noch mal in anderen Worten, zum

37:00.840 --> 37:04.100
Beispiel hier im Buch, die Inhalte nachzulesen, um das dann besser zu

37:04.100 --> 37:04.420
verstehen.

37:05.220 --> 37:07.220
Und dazu gibt es eben auch direkt ein Kapitel.

37:09.740 --> 37:14.060
Okay, so viel zu Testen und Assertions.

37:18.890 --> 37:20.990
Bisschen über die Zeit, aber das geht auch noch.

37:21.770 --> 37:24.190
Muss ich hier mal erst mal zum Anfang wieder springen.

37:28.530 --> 37:31.290
Genau, das war eben mal Foliensatz 13.

37:31.910 --> 37:37.370
Jetzt geht es weiter mit dem Thema Zerteilen, Suchen und Sortieren.

37:37.490 --> 37:42.830
Das sind also drei Beispiel Herausforderungen oder drei typische

37:42.830 --> 37:46.270
Probleme, vor denen ich beim Schreiben eines Java-Programms oder

37:46.270 --> 37:49.290
allgemein eines Programms stehe und wo es dann eben auch schon

37:49.290 --> 37:53.190
typische Lösungsverfahren gibt, die ich dann im Folgenden vorstellen

37:53.190 --> 37:53.510
möchte.

37:53.510 --> 37:57.570
Also auch Beispiele für Algorithmen, wie wir sie ja ganz am Anfang der

37:57.570 --> 37:58.690
Vorlesung motiviert hatten.

37:59.730 --> 38:02.290
Dazu aber auch noch mal der Vorlesungsüberblick.

38:02.370 --> 38:05.070
Wie gesagt, sind wir jetzt bei den Grundlagen schon ziemlich weit

38:05.070 --> 38:07.230
durch und wir befinden uns jetzt in diesem Methodik-Block.

38:07.810 --> 38:10.370
Wir hatten gerade über das Testen gesprochen.

38:10.670 --> 38:13.190
Ich nehme mal wieder hier meinen Stift dazu, dass Sie auch wissen,

38:13.250 --> 38:13.830
wovon ich rede.

38:14.590 --> 38:18.090
Hier vorne geht es dann auch weiter mit Debugging.

38:18.230 --> 38:21.410
Aber jetzt gehen wir erst mal zu diesem Teil Parsen, Suchen und

38:21.410 --> 38:21.910
Sortieren.

38:22.330 --> 38:24.710
Sie vielleicht schon gemerkt, den habe ich jetzt erst eingebaut.

38:24.790 --> 38:27.250
Und die Folie, den hatte ich tatsächlich vergessen in der Übersicht.

38:27.470 --> 38:29.750
Also das ist jetzt eine neue Version von diesem Vorlesungsüberblick.

38:30.750 --> 38:32.570
Aber auch eine ganz grundlegende.

38:32.650 --> 38:35.230
Deswegen habe ich es mal da einsortiert.

38:36.850 --> 38:37.990
Parsen, fragen Sie sich jetzt.

38:38.070 --> 38:39.450
Gerade habe ich noch von Zerteilen geredet.

38:39.790 --> 38:42.130
Das ist jetzt eben hier wieder dieses Hin und Her zwischen deutschen

38:42.130 --> 38:43.370
und englischen Begriffen.

38:43.670 --> 38:49.010
In der Vorlesung geht es um Zerteilen und Zerteilen bezieht sich oder

38:49.010 --> 38:52.870
in der Informatik dieser Begriff auf das Zerteilen von Zeichenketten,

38:52.930 --> 38:55.690
was man auf Englisch auch Parsing nennt.

38:55.950 --> 38:58.150
Also den Begriff Parser haben Sie vielleicht auch schon mal gehört.

38:58.250 --> 39:00.270
Das ist eben genau dieses Zerteilen.

39:01.890 --> 39:05.250
Und ein Lernziel für heute wäre eben, dass Sie wissen, wie dieses

39:05.250 --> 39:08.450
Zerteilen funktioniert und dass Sie einen einfachen Zerteiler mit

39:08.450 --> 39:09.530
rekursivem Abstieg.

39:09.890 --> 39:12.670
Sehen wir später noch, was das ist, in Java implementieren können.

39:13.270 --> 39:15.430
Denken Sie vielleicht, oje, das klingt kompliziert.

39:15.430 --> 39:19.010
Aber Sie werden sehen, einen einfachen Zerteiler für die Beispiel

39:19.670 --> 39:22.430
Sprache oder Beispiel Zeichenketten, die wir hier betrachten werden,

39:22.490 --> 39:26.310
ist eigentlich, wenn man mal darüber nachdenkt, recht einfach.

39:27.570 --> 39:30.970
Dann werden wir uns das Suchen anschauen und insbesondere da zwei

39:30.970 --> 39:35.550
Beispiel Suchalgorithmen, nämlich die lineare und die binäre Suche.

39:35.750 --> 39:38.570
Und da wäre eben das Lernziel, dass Sie sowas auch in Java

39:38.570 --> 39:39.630
nachimplementieren könnten.

39:40.190 --> 39:44.990
Und beim Sortieren schauen wir uns auch die Funktionsweise einiger

39:44.990 --> 39:46.290
gängiger Sortierverfahren an.

39:46.870 --> 39:51.330
Und da wäre dann auch das Lernziel, dass Sie solche Sortierverfahren

39:51.330 --> 39:55.010
dann auch nachimplementieren können auf Arrays in Java.

39:56.570 --> 39:58.370
Entsprechend hat die Vorlesung drei Teile.

39:58.510 --> 40:02.190
Es geht erst um Zerteilen, Parsing und wir gucken uns einen Zerteiler

40:02.190 --> 40:03.370
mit rekursivem Abstieg an.

40:03.650 --> 40:05.610
Es geht um Suchverfahren, ist jetzt ein bisschen doppelt gemoppelt

40:05.610 --> 40:08.670
hier, aber naja, lineare Suche, binäre Suche und es geht um

40:08.670 --> 40:09.430
Sortierverfahren.

40:09.510 --> 40:10.790
Das hatte ich gerade noch nicht gesagt.

40:10.790 --> 40:15.190
Im speziellen Bubble Sort, Selection Sort und Insertion Sort und wie

40:15.190 --> 40:17.130
die funktionieren, sehen wir dann gleich.

40:17.990 --> 40:21.350
Wir starten mit dem Zerteilen.

40:22.510 --> 40:23.610
Also nochmal, wozu?

40:23.790 --> 40:24.630
Was ist das überhaupt?

40:24.730 --> 40:27.030
Ich habe es gerade schon mal kurz erklärt, aber jetzt nochmal im

40:27.030 --> 40:27.430
Detail.

40:27.850 --> 40:29.350
Zerteilen, Englisch Parsing.

40:29.890 --> 40:30.710
Was ist das?

40:31.430 --> 40:32.590
Wozu braucht man das?

40:33.030 --> 40:36.130
Es ist eben ein Problem, was in der Informatik recht häufig vorkommt.

40:37.090 --> 40:41.170
Und die Fragestellung ist, wie kann man eine Zeichenkette in seine

40:41.170 --> 40:46.070
semantisch bedeutsamen Teile zerteilen und auch die Struktur, die

40:46.070 --> 40:49.370
dahinter steckt, hinter dieser Zeichenkette feststellen?

40:49.570 --> 40:52.470
Also es geht nicht nur einfach darum, eine Zeichenkette String in die

40:52.470 --> 40:54.290
einzelnen Charakter zu teilen.

40:54.370 --> 40:57.850
Das geht natürlich irgendwie leicht, sondern die semantisch

40:57.850 --> 41:01.390
bedeutsamen Teile zu identifizieren und auch die Struktur.

41:02.690 --> 41:04.350
Schauen wir uns dafür Beispiele an.

41:04.430 --> 41:05.130
Was heißt das?

41:05.650 --> 41:10.290
Ein Beispiel wäre ein solcher String 13 plus 4 mal 52,5.

41:10.770 --> 41:13.510
Es könnte zum Beispiel ein String sein, der eine Eingabe ist für einen

41:13.510 --> 41:15.770
Taschenrechner, den ich implementiere.

41:15.930 --> 41:19.150
Also der Nutzer kann einen solchen String auf der Kommandozeile zum

41:19.150 --> 41:21.550
Beispiel eintippen und wir wollen jetzt einen Taschenrechner

41:21.550 --> 41:26.070
schreiben, der diesen Ausdruck, den das ja ergibt, für uns berechnet.

41:26.790 --> 41:28.750
Und die Frage ist eben hier, wie kann ich sowas verarbeiten?

41:28.850 --> 41:30.330
Was ist da eigentlich erstmal der erste Schritt?

41:31.310 --> 41:34.330
Und der erste Schritt ist eben, diesen String erst mal zu

41:34.330 --> 41:35.030
interpretieren.

41:35.390 --> 41:38.610
Davon ist der erste Schritt, ihn in die einzelnen semantisch

41:38.610 --> 41:41.970
bedeutsamen Teile zu zerteilen eben.

41:42.990 --> 41:44.770
Das sind, wie gesagt, nicht einfach die einzelnen Zeichen.

41:44.870 --> 41:48.930
Wenn ich jetzt einfach sage, ich zerteile ihn in 1, 3 Leerzeichen plus

41:48.930 --> 41:53.150
Leerzeichen 4, dann habe ich nichts semantisch Bedeutsames gewonnen,

41:53.490 --> 41:56.450
sondern die semantisch bedeutsamen Teile, an denen ich interessiert

41:56.450 --> 41:57.750
bin, sind im Prinzip diese hier.

41:57.750 --> 42:01.610
Es ist einmal eine Zahl 13, es ist ein Operator plus, wieder eine Zahl

42:01.610 --> 42:06.590
4, ein Operator, die Multiplikation und wieder eine Zahl 52,5.

42:06.730 --> 42:12.050
Das ist eigentlich das Ziel des Parsens, des Zerteilens, diese in

42:12.050 --> 42:14.890
diesem Fall semantisch bedeutsamen Teile herauszufinden.

42:16.310 --> 42:19.850
Und hier bei so einem mathematischen, arithmetischen Ausdruck geht es

42:19.850 --> 42:20.630
sogar noch ein bisschen weiter.

42:20.790 --> 42:23.470
Ich will nicht nur diese Teile herausfinden, sondern ich will, wie

42:23.470 --> 42:26.010
oben gesagt, auch die Struktur davon feststellen.

42:26.010 --> 42:30.110
Und in dem Fall eines solchen Ausdrucks hätte ich ja eine Struktur wie

42:30.110 --> 42:31.770
hier rechts angegeben in dem Baum.

42:32.310 --> 42:35.230
Und zwar wissen Sie ja aus der Schule auch noch, dass Punktrechnung

42:35.230 --> 42:36.550
vor Strichrechnung geht.

42:37.130 --> 42:40.370
Das heißt, ich würde bei der Berechnung eines solchen Ausdrucks wissen

42:40.370 --> 42:43.950
wollen, dass diese beiden Werte 4 und 52,5 irgendwie enger

42:43.950 --> 42:45.230
zusammenhängen.

42:45.370 --> 42:48.250
Also eine Einheit erst mal, also eine Untereinheit erst mal ergeben.

42:48.790 --> 42:50.510
Hat mein Stift den Geist aufgegeben?

42:50.650 --> 42:50.850
Na gut.

42:52.350 --> 42:53.890
Also quasi zuerst berechnet werden müssen.

42:54.430 --> 42:58.450
Dieses Element zu einem Ergebnis und das dann zusammen mit der 13

42:58.450 --> 42:59.470
nochmal addiert wird.

42:59.610 --> 43:02.470
Also man hat hier diese Struktur in diesem Fall, die die

43:02.470 --> 43:05.590
Berechnungsreihenfolge dieses Ausdrucks auch vorgibt.

43:06.730 --> 43:12.150
Ein anderes Beispiel für so eine Zerteilung wäre so ein Satz einfach.

43:12.730 --> 43:15.850
Und da könnte man sich jetzt verschiedene Zerteilungen durchlegen oder

43:15.850 --> 43:16.310
überlegen.

43:16.950 --> 43:19.790
Eine so grammatikalische wäre zum Beispiel zu sagen, was sind denn

43:19.790 --> 43:23.390
hier die grammatikalischen Satzteile, die man identifizieren wollen

43:23.390 --> 43:23.710
würde?

43:23.890 --> 43:27.250
Man könnte dann aufteilen Aha, hier die semantisch bedeutsamen Teile

43:27.250 --> 43:27.610
sind.

43:28.070 --> 43:36.070
Dies ist ein Beispiel, also Subjekt, Prädikat, Objekt als semantisch

43:36.070 --> 43:36.850
bedeutsame Teile.

43:37.190 --> 43:40.090
Also auch hier vielleicht nicht einfach nach Leerzeichen aufsplitten.

43:42.650 --> 43:46.970
Und schließlich ein weiteres Beispiel und vielleicht für diesen

43:46.970 --> 43:52.230
Kontext auch das wichtigste Beispiel auch ein Computerprogramm, was

43:52.230 --> 43:55.030
sie selber schreiben, ist ja erst mal nur ein ganz langer String.

43:55.650 --> 43:59.690
Also wenn sie ihre ihre Klasse schreiben in ihrem Editor, dann ja, es

43:59.690 --> 44:03.890
ist eine lange, lange Zeichenkette inklusive Zeilenumbrüchen, die ja

44:03.890 --> 44:06.370
auch ein Charakter nur sind.

44:06.930 --> 44:10.670
Und wenn jetzt die JVM zum Beispiel oder erst mal der Java Compiler

44:10.670 --> 44:14.730
sowas interpretieren soll und daraus ein laufiges Programm erstellen

44:14.730 --> 44:18.270
soll, ist eben auch dieses Zerteilen, das Parsen der erste Schritt

44:18.270 --> 44:21.530
oder der zweite, um genau zu sein, der durchgeführt werden muss.

44:21.530 --> 44:26.450
Also ein Compiler muss als ersten oder frühen Schritt dann erst mal

44:26.450 --> 44:30.530
diese Zeichenkette analysieren und diese semantisch bedeutsamen Teile

44:30.530 --> 44:32.250
feststellen.

44:32.730 --> 44:35.570
In dem Fall würde man sagen Aha, hier ist das Schlüsselwort Class.

44:36.010 --> 44:38.750
Dann ist ein semantisch bedeutsamer Teil, dass hier ein Datentyp

44:38.750 --> 44:39.070
steht.

44:39.770 --> 44:41.230
Die Klammer ist wieder ein Teil für sich.

44:41.570 --> 44:45.890
Der Datentyp, der Name einer Variablen, das Semikolon am Ende und

44:45.890 --> 44:48.370
irgendwas steht dann noch dazwischen und am Ende wieder die

44:48.370 --> 44:49.450
schließende Klammer.

44:49.450 --> 44:53.170
Also auch ein solchen String zu zerteilen in solche Elemente ist

44:53.170 --> 44:55.970
Zerteilen beziehungsweise Parsen.

44:58.390 --> 45:01.090
Genau und stellt sich jetzt die Frage, wie kann ich so eine Zerteilung

45:01.090 --> 45:02.370
machen in meinem Programm?

45:02.710 --> 45:08.370
Und die Lösungsidee dafür ist es, formale Sprachen und gerne

45:08.370 --> 45:11.750
kontextfreie Grammatiken zu verwenden, wie Sie das ja auch schon in

45:11.750 --> 45:14.730
Grundbegriffe der Informatik vor ein paar Wochen gelernt haben.

45:14.810 --> 45:18.410
Also die Begrifflichkeiten Grammatik, kontextfreie Grammatik kennen

45:18.410 --> 45:18.970
Sie da ja schon.

45:19.750 --> 45:22.690
In dieser Vorlesung werden wir uns anschauen, wie man also ein

45:22.690 --> 45:26.910
Programm schreiben kann, was anhand einer solchen Grammatik einen

45:26.910 --> 45:29.610
gegebenen String dann wiederum zerteilen kann, damit ich ihn dann in

45:29.610 --> 45:31.630
meinem Programm weiterverarbeiten kann, zum Beispiel in einem

45:31.630 --> 45:33.690
Taschenrechner, den ich implementieren möchte.

45:35.310 --> 45:37.110
Genau, den Taschenrechner werden wir uns jetzt auch mal genauer

45:37.110 --> 45:41.190
anschauen als Beispiel, wie man diese semantisch bedeutsamen Teile und

45:41.190 --> 45:44.450
die Struktur von solchen arithmetischen Ausdrücken, wie hier oben

45:45.730 --> 45:48.110
feststellen kann, anhand einer Grammatik.

45:48.630 --> 45:51.050
Anhand einer Grammatik, das heißt, wir müssen uns jetzt mal anschauen,

45:51.130 --> 45:55.130
was ist denn die Grammatik für solche Ausdrücke, wie wir sie da oben

45:55.130 --> 45:56.290
gesehen haben?

45:59.950 --> 46:02.990
Sie kennen es eben aus Grundbegriffen der Informatik, was man für eine

46:02.990 --> 46:03.870
Grammatik braucht.

46:04.670 --> 46:10.090
Wir brauchen zunächst Symbole und zwar einerseits Terminalsymbole,

46:10.310 --> 46:13.770
also die Symbole, die nachher auch in meinen sozusagen zu

46:13.770 --> 46:17.230
akzeptierenden Wörtern drinstehen sollen oder jetzt in unserem

46:17.230 --> 46:19.870
Zusammenhang, die in den Zeichenketten, die wir analysieren wollen,

46:19.970 --> 46:24.150
eben auch tatsächlich vorkommen und auch nicht Terminalsymbole oder

46:24.150 --> 46:29.010
Non -Terminalsymbole, die eben dazu da sind, meine Regeln oder die

46:29.010 --> 46:30.570
Regelproduktion machen zu können.

46:31.610 --> 46:33.710
In unserem Fall für die Taschenrechner würden wir jetzt sagen, na ja,

46:33.730 --> 46:37.130
die Terminalsymbole sind eben die Grundrechenarten, also Plus mal

46:38.390 --> 46:41.430
Minus geteilt, Klammerung vielleicht noch, wenn wir das unterstützen

46:41.430 --> 46:43.230
wollen und die Zahlen selber.

46:43.230 --> 46:46.890
Wir gehen jetzt mal in diesem Beispiel davon aus, dass eine Zahl immer

46:46.890 --> 46:49.570
ein Symbol ist, also nicht eine Ziffer ein Symbol ist, sondern dass

46:49.570 --> 46:53.550
die Zahl an sich schon so eine semantische Einheit für uns darstellt,

46:53.670 --> 46:56.470
weil das nämlich von Java schon leicht übernommen werden kann.

46:56.890 --> 47:00.370
Also eine Zahl nehmen wir, verstehen wir auch schon als ein Symbol,

47:00.570 --> 47:02.010
auch wenn sie aus mehreren Ziffern besteht.

47:03.670 --> 47:06.750
Genau diese Dinge brauchen wir, Terminalsymbole, Non-Terminalsymbole

47:06.750 --> 47:09.730
und man könnte sich jetzt für das, was wir gerade gesehen haben, eine

47:09.730 --> 47:11.990
Grammatik wie hier vorne überlegen.

47:11.990 --> 47:14.870
Also hier steht jetzt oder die Grammatik hätte erst mal diese Symbole

47:14.870 --> 47:18.330
und zusätzlich noch eine einzelne Produktionsregel, die eben sagt, na

47:18.330 --> 47:22.350
ja, so ein Nicht-Terminalsymbol E für Expression kann ich ersetzen,

47:22.470 --> 47:28.230
entweder durch E plus E oder durch E minus E oder durch E mal E oder

47:28.230 --> 47:31.030
durch E durch E oder durch Klammer oder durch eine Zahl.

47:32.090 --> 47:34.650
Und das kennen Sie dann ja, dann kann ich solche Regeln mehrfach

47:34.650 --> 47:38.170
anwenden und könnte den Ausdruck, den ich eben gesehen habe, mit sowas

47:38.170 --> 47:40.310
auch tatsächlich produzieren.

47:40.310 --> 47:42.610
Also hier haben wir ja das Plus, was ich irgendwie erzeugen kann und

47:42.610 --> 47:45.150
dann könnte ich das E auf der rechten Seite auch nochmal durch so

47:45.150 --> 47:48.410
einen Mal-Ausdruck ersetzen und dann sind wir auch schon fertig.

47:48.530 --> 47:51.530
Dann kann ich die drei Es, die dann sozusagen übrig sind, jeweils

47:51.530 --> 47:54.790
durch Zahlen ersetzen und habe dann den Ausdruck, den wir am Anfang

47:54.790 --> 47:55.630
hatten.

47:56.630 --> 48:01.870
Also eine Grammatik, die schon irgendwie passt, also die Zeichenkette

48:01.870 --> 48:03.230
irgendwie zerteilen kann.

48:03.470 --> 48:06.410
Aber weil hier steht erster Versuch, können Sie sich schon denken,

48:06.510 --> 48:08.370
dass das jetzt noch nicht der weisheitletzter Schluss ist.

48:09.530 --> 48:11.930
Es gibt hier nämlich noch ein Problem mit dieser Lösung.

48:12.190 --> 48:15.450
Vielleicht da auch erst mal die Frage an Sie.

48:15.730 --> 48:18.590
Was ist jetzt hier noch nicht so schön abgedeckt von dem

48:18.590 --> 48:24.070
Taschenrechner Zerteilbeispiel, wie ich es gerade eingeführt hatte?

48:27.640 --> 48:29.280
Vielleicht ein kleiner Hinweis, dieses Stichwort

48:29.280 --> 48:30.580
Berechnungsreihenfolge.

48:32.000 --> 48:34.580
Genau, die Punkt-Vor-Strich-Rechnung-Mehrregel meinten Sie jetzt also

48:34.580 --> 48:35.960
die Präzedenz der Operatoren.

48:36.180 --> 48:37.160
Genau, mit dieser.

48:37.840 --> 48:38.540
Genau das ist der Punkt.

48:38.640 --> 48:38.960
Sehr gut.

48:38.960 --> 48:42.140
Mit dieser Grammatik gibt es eben zwei verschiedene Möglichkeiten, wie

48:42.140 --> 48:43.520
ich so einen Baum aufbauen kann.

48:43.660 --> 48:47.440
Also ich könnte jetzt entweder sagen, ich habe das Plus ganz oben in

48:47.440 --> 48:50.900
unserem Baum stehen, wie wir Ihnen eben gesagt gesehen hatten, weil

48:50.900 --> 48:52.460
ich nämlich zuerst diese Regel anwende.

48:52.560 --> 48:55.460
Und das wäre jetzt zufällig der richtige Baum, den man auch haben

48:55.460 --> 48:55.740
wollte.

48:56.200 --> 48:59.400
Oder ich könnte ja hier auch als erstes diese Regel anwenden und quasi

48:59.400 --> 49:03.280
das Mal, die Multiplikation ganz nach oben schreiben.

49:03.520 --> 49:04.840
Ich gehe noch mal zurück auf den Baum eben.

49:05.740 --> 49:07.900
Und dann würde ich hier halt einen Baum erhalten, der genau andersrum

49:07.900 --> 49:11.060
ist, wo ich dann eigentlich die Addition in der berechnungsreichen

49:11.060 --> 49:13.240
Folge vor der Multiplikation hätte.

49:13.480 --> 49:16.880
Und das wäre eben in dem Fall eines Taschenrechners nicht das, was ich

49:16.880 --> 49:17.200
wollte.

49:17.420 --> 49:19.520
Außer ich habe es vielleicht so in meine Spezifikation geschrieben,

49:19.620 --> 49:20.100
dass ich das will.

49:20.180 --> 49:21.740
Aber normalerweise will man es nicht.

49:21.980 --> 49:24.780
Der Hintergrund ist hier also, dass es mehrdeutig ist.

49:24.860 --> 49:28.100
Ich kann hier verschiedene Varianten finden, wie ich diesen gegebenen

49:28.100 --> 49:30.120
Beispielstring zerteilen könnte.

49:31.120 --> 49:34.100
Und ich will eben bei so einem Taschenrechner typischerweise die

49:34.100 --> 49:37.680
berechnungsreichen Folgen hier auch schon mit berücksichtigt haben.

49:40.220 --> 49:42.300
Genau, was kann ich machen, um das zu lösen?

49:43.060 --> 49:45.860
Also das Problem ist Struktur wie Punkt vor Strich geht verloren.

49:46.380 --> 49:49.520
Ich kann das lösen, indem ich ein bisschen so eine, man kann sich das

49:49.520 --> 49:53.780
vorstellen, mehrschichtige Grammatik aufbaue und so vorgebe, wie die

49:53.780 --> 49:57.180
Reihenfolge immer jeweils zu interpretieren ist.

49:57.400 --> 50:00.500
Das mache ich, indem ich unterschiedliche Nicht-Terminal-Symbole oder

50:00.500 --> 50:02.760
Non -Terminal-Symbole einführe.

50:02.860 --> 50:05.420
Einerseits für die Punktrechnung, also Multiplikation und Division.

50:06.220 --> 50:07.620
Ist ja in Java gar kein Punkt, aber egal.

50:08.220 --> 50:12.160
Und einmal für die Strichrechnung, also Addition und Subtraktion.

50:12.840 --> 50:13.280
Subtraktion.

50:14.360 --> 50:17.000
Genau, das mache ich so, dass ich also sage, eine Expression ist erst

50:17.000 --> 50:20.840
mal etwas oder eine Expression, da habe ich eine Produktionsregel

50:20.840 --> 50:25.060
dafür, die mir das aufspaltet in ein Term plus eine andere Expression.

50:25.220 --> 50:26.180
Vielleicht mache ich es mal doch lieber so.

50:28.280 --> 50:28.980
Nehme den hier weg.

50:32.540 --> 50:36.580
Also in ein Term plus eine andere Expression oder ein Term minus eine

50:36.580 --> 50:38.880
andere Expression oder ich kann auch einfach nur sagen, das bleibt ein

50:38.880 --> 50:39.180
Term.

50:39.860 --> 50:42.520
Und erst wenn ich dann eine Verschachtelungsebene sozusagen

50:42.520 --> 50:46.560
runtergehe, kann ich sagen, einen solchen Term kann ich, da kann ich

50:46.560 --> 50:49.560
eine Produktionsregel anwenden und sagen, das ist ein Fakt, mal

50:49.560 --> 50:53.680
wiederum ein Term oder ein Fakt, Faktor, besser gesagt auf Deutsch

50:53.680 --> 50:56.280
geteilt durch einen Term oder einfach nur ein Faktor.

50:56.780 --> 51:00.420
Und ein Faktor kann dann nur aufgelöst werden, entweder als Zahl oder

51:00.420 --> 51:01.740
als Klammerausdruck.

51:02.820 --> 51:06.100
Das heißt, wenn ich jetzt so was habe, was unser Beispiel, was wir

51:06.100 --> 51:13.060
eben hatten, 13 plus 4 mal 52,5 ist klar, dass der Gesamtausdruck erst

51:13.060 --> 51:15.700
mal eine Expression ist und ich also hier erst mal nur auflösen kann

51:15.700 --> 51:21.220
hinsichtlich Plus oder Minus und den einen Teil dann wieder weiter

51:21.220 --> 51:21.880
auflösen kann.

51:21.980 --> 51:24.640
Jetzt wäre der hintere Teil ja eigentlich der mit der Multiplikation.

51:24.720 --> 51:25.460
Das ist eine Expression.

51:25.920 --> 51:28.820
Expression kann ich aber auch wieder produzieren oder umformen zu

51:28.820 --> 51:32.860
einem Term, ersetzen durch einen Term und kann dann da unten zu der

51:32.860 --> 51:34.320
Multiplikation kommen.

51:34.320 --> 51:37.060
Sie können sich überlegen, würde ich es jetzt hinkriegen, mit dieser

51:37.060 --> 51:39.540
Grammatik das sozusagen falschrum zu interpretieren?

51:40.180 --> 51:42.700
Das geht nicht, denn wenn sie hier in der Multiplikation erst mal

51:42.700 --> 51:47.140
drinstecken, sozusagen in der Auflösung ihrer Produktionsregeln, dann

51:47.140 --> 51:52.720
kann ich hier und hier nicht wieder ein Plus reinbekommen, ohne nicht

51:52.720 --> 51:54.540
vorher über eine Klammerung gegangen zu sein.

51:54.940 --> 51:57.560
Und genau das wollen wir ja haben, wenn wir diese Punktvorstreck

51:57.560 --> 51:59.120
Rechnung machen wollen.

51:59.580 --> 52:02.380
Also das wäre jetzt eine Grammatik, die auch diese Struktur, wie wir

52:02.380 --> 52:06.820
sie eben hatten, eindeutig immer bestimmen würde.

52:06.920 --> 52:10.080
Oder da gibt es nur eine Interpretationsmöglichkeit, eine Möglichkeit

52:10.080 --> 52:13.460
der Produktion solcher Ausdrücke, wie wir sie gerade gesehen haben.

52:18.940 --> 52:19.320
Genau.

52:21.160 --> 52:23.640
Gehen wir mal weiter, gehen weiter mit diesem Beispiel.

52:25.700 --> 52:28.000
Es geht ja bei uns darum, gar nicht zu sagen, wir wollen jetzt eine

52:28.000 --> 52:30.980
Sprache haben für unsere für unseren Ausdruck, sondern was wir ja

52:30.980 --> 52:34.180
eigentlich wollen, ist das Ganze zu verteilen, also im Endeffekt einen

52:34.180 --> 52:37.740
Parser zu bauen und uns jetzt als nächsten Schritt dann mal

52:37.740 --> 52:43.180
anzuschauen, wie würde denn jetzt so ein Parsebaum aussehen anhand der

52:43.180 --> 52:46.180
Grammatik, die wir hier haben und anhand unserer Beispielzeichenkette.

52:46.980 --> 52:50.220
Also Ziel ist es, einen sogenannten Parsebaum zu bestimmen, eine

52:50.220 --> 52:52.720
Zerteilung anhand der Grammatik.

52:52.780 --> 52:55.840
Und wir wollen unten in den Blättern eine Aufteilung haben, wo danach

52:55.840 --> 52:59.640
steht sozusagen Z plus Z mal Z.

52:59.640 --> 53:04.140
Wir fangen an mit einer Expression und dann ist eben die Frage, was

53:04.140 --> 53:06.060
ist denn jetzt von diesen Regeln?

53:06.160 --> 53:12.500
Die Regel, die ich als erstes anwenden muss, um am Ende zu einem

53:12.500 --> 53:18.380
Parsebaum zu kommen, wo eben 13 plus 4 mal 52,5 oder eigentlich Z plus

53:18.380 --> 53:21.260
Z mal Z in den Blättern steht.

53:22.400 --> 53:26.340
Wer weiß es, welche Regel müsste ich hier als erstes anwenden?

53:27.240 --> 53:28.840
Oder vielleicht gebe ich nochmal eins vor.

53:28.840 --> 53:30.700
Hier steht ja schon, das Ganze ist eine Expression.

53:30.900 --> 53:34.040
Also ich bin jetzt im Moment hier und kann eben eine dieser drei

53:34.040 --> 53:36.040
Regeln hier anwenden.

53:36.660 --> 53:40.260
Können gerne mal hochzeigen und sagen, ob ich das wohl erkenne,

53:40.320 --> 53:40.720
beeilen.

53:41.220 --> 53:45.180
Eins oder zwei oder drei, wenn Sie Idee haben.

53:45.940 --> 53:49.260
Also Regel 1 oder Regel 2 oder Regel 3.

53:49.420 --> 53:49.920
Was meinen Sie?

53:51.120 --> 53:54.520
Aber genau, ich sehe eigentlich nur Finger, die eine 1 in die Höhe

53:54.520 --> 53:54.800
strecken.

53:54.920 --> 53:57.600
Und genau das ist auch die Regel hier.

53:57.600 --> 54:01.360
Ich habe eben als erstes Element, wenn ich jetzt auf Expression Ebene

54:01.360 --> 54:03.880
bin, das Plus, was ich hier aufspalten wolle.

54:04.000 --> 54:06.260
Und Sie erinnern sich ja auch in unserem Baum, den wir vorhin hatten,

54:06.340 --> 54:08.280
stand das Plus ja auch zuoberst.

54:09.420 --> 54:12.540
Also würde man erst mal aufbauen wollen oder aufsplitten wollen.

54:12.620 --> 54:18.380
Expression wird ersetzt durch einen Term, das Terminalsymbol Plus und

54:18.380 --> 54:19.320
wieder eine Expression.

54:20.080 --> 54:22.920
Dann kann ich weitermachen, habe jetzt hier also den Term links stehen

54:22.920 --> 54:26.800
und kann mir überlegen, für was oder was, was ersetze ich denn hier?

54:26.800 --> 54:31.640
Welche von den möglichen Regeln für Term, nämlich diese, diese oder

54:31.640 --> 54:36.080
diese, würde ich jetzt hier verwenden, um weiterzukommen, um mein

54:36.080 --> 54:38.700
Ziel, meine Zielzerteilung zu finden?

54:39.740 --> 54:44.100
Die erste, die zweite oder die dritte, wenn ich mir diesen Term hier

54:44.100 --> 54:44.520
betrachte.

54:44.820 --> 54:46.840
Können Sie auch gerne wieder die Hand heben?

54:49.700 --> 54:50.200
Genau.

54:51.340 --> 54:53.400
Oder auch nicht nur genau, ich sehe genau und nicht genau.

54:53.780 --> 54:54.720
Die dritte ist es nämlich.

54:54.720 --> 54:57.760
Wir sind ja jetzt hier an der linken Stelle und vor dem Plus steht ja

54:57.760 --> 54:58.380
nur noch eine Zahl.

54:58.600 --> 55:01.600
Also müssen wir hier die dritte Regel anwenden und sagen ein Term zu

55:01.600 --> 55:05.160
einem Fakt und später, ich nehme es mal schon vorweg, ein Fakt zu

55:05.160 --> 55:05.700
einer Zahl.

55:05.880 --> 55:08.720
Und dann habe ich hier links meine Zahl in meinem Baum stehen und habe

55:08.720 --> 55:12.240
sozusagen schon die ersten beiden Blätter gefunden, nämlich Z und

55:12.240 --> 55:12.600
Plus.

55:13.360 --> 55:17.660
Muss jetzt noch den zweite, den zweiten Teil hier auflösen, ersetzen,

55:18.180 --> 55:21.560
wo ich wieder oben anfange bei einer Expression, um noch diesen Teil

55:21.560 --> 55:22.880
meiner Zeichenkette hier zu bekommen.

55:22.880 --> 55:25.620
Ich mache es jetzt vielleicht mal direkt selber weiter, ist vielleicht

55:25.620 --> 55:26.240
jetzt auch klar.

55:26.760 --> 55:30.520
Bei dieser Expression will ich eben jetzt 4 mal 52,5, also Z mal Z

55:30.520 --> 55:31.100
rausbekommen.

55:31.460 --> 55:36.080
Das heißt, hier oben eindeutig muss ich den Term erst mal auswählen,

55:36.160 --> 55:37.700
denn Plus oder Minus will ich ja nicht mehr haben.

55:38.220 --> 55:40.800
Mit dem Term komme ich dann eine Zahl runter und bekomme mein

55:40.800 --> 55:41.900
gewünschtes Malzeichen.

55:42.160 --> 55:45.920
Also erst mal sage ich, ich ersetze durch einen Term und dann nehme

55:45.920 --> 55:49.340
ich hier die erste Regel und dann diese beiden Faktenterme, die hier

55:49.340 --> 55:54.000
stehen, brauche ich jetzt nur noch zu ersetzen hin zu den Zahlen.

55:55.120 --> 55:59.800
So würde ein Passbaum also für diesen Beispielausdruck anhand unserer

55:59.800 --> 56:02.400
Grammatik aussehen.

56:04.720 --> 56:07.000
Genau und so können Sie jetzt auch, also was wir jetzt gerade gemacht

56:07.000 --> 56:10.640
haben, ist ja mal wieder selber Computer spielen und von Hand haben

56:10.640 --> 56:13.200
wir uns überlegt, was könnte denn hier so passen?

56:13.380 --> 56:15.660
Also ähnlich wie wir das am Anfang mit den bunten Scheiben in der

56:15.660 --> 56:17.880
allerersten Vorlesung hatten.

56:17.880 --> 56:20.800
Die Frage in der Programmierenden Vorlesung ist natürlich jetzt

56:20.800 --> 56:22.580
wieder, wie kann ich denn jetzt einen solchen Zerteiler

56:22.580 --> 56:26.700
implementieren, der mir das stupide, in stupider Weise oder wie wir

56:26.700 --> 56:31.320
das gesagt haben, für mich macht, also ein Programm, das mir aus so

56:31.320 --> 56:35.500
einer solchen Zeichenkette in meinem Taschenrechner einen solchen

56:35.500 --> 56:37.240
Passbaum erzeugt.

56:38.380 --> 56:41.380
Das Problem, was es hier für Menschen oder für Menschen nicht so

56:41.380 --> 56:43.060
schwierig macht, aber für den Computer vielleicht ein bisschen

56:43.060 --> 56:46.380
schwierig macht, ist, dass man jetzt irgendwie am Anfang entscheiden

56:46.380 --> 56:49.660
muss, welche Regeln man als erstes anwendet, damit es am Ende auch gut

56:49.660 --> 56:50.320
aufkommt.

56:52.840 --> 56:55.420
Das macht es jetzt ein bisschen schwierig, um vielleicht direkt zu

56:55.420 --> 56:57.280
sehen, wie man sowas implementiert.

56:57.860 --> 57:00.380
Was man jetzt machen könnte, wäre zu sagen, na ja, dann probiere ich

57:00.380 --> 57:01.520
einfach mal alle Regeln durch.

57:01.680 --> 57:03.400
Also ein Computerprogramm hat ja Zeit, sozusagen.

57:03.580 --> 57:06.280
Ich kann ja einfach mal alle Kombinationen ausprobieren und gucken, ob

57:06.280 --> 57:09.160
ich irgendwann mal diesen gewünschten Passbaum rausbekomme.

57:09.820 --> 57:10.880
Das würde auch funktionieren.

57:11.060 --> 57:13.060
Wäre natürlich keine besonders schlaue Vorgehensweise.

57:13.060 --> 57:18.180
Wir schauen uns eine etwas schlauere Vorgehensweise an und schauen uns

57:18.180 --> 57:24.820
nämlich Klassen von Parsern, also Klassen von Zerteilern genauer an.

57:25.520 --> 57:28.640
Im Folgenden schauen wir uns insbesondere eine Klasse an, nämlich das

57:28.640 --> 57:29.600
Top -Down-Parsing.

57:29.680 --> 57:31.160
Aber vielleicht erst mal zur Einordnung.

57:31.640 --> 57:37.060
Es gibt so zwei wichtige Klassen von Parsern, von Zerteilern, wie man

57:37.060 --> 57:39.780
vorgehen kann, nämlich einerseits Top-Down-Parser.

57:39.780 --> 57:43.520
Und da werden wir uns so rekursiven Abstieg Parser genauer anschauen

57:43.520 --> 57:45.960
und zum anderen Bottom-Up-Parser.

57:46.300 --> 57:49.260
Wenn man aber manuell unterwegs ist und also von Hand einen Parser

57:49.260 --> 57:52.060
schreiben will für ein Programm, dann verwendet man typischerweise

57:52.060 --> 57:53.300
einen solchen Top-Down-Parser.

57:53.380 --> 57:54.740
Das ist irgendwie für Menschen einfacher.

57:55.860 --> 57:57.300
Automatisch erzeugte Parser.

57:57.440 --> 58:01.400
Das gibt es auch, verwenden oftmals auch diese Bottom-Up-Strategie.

58:03.080 --> 58:05.720
Beim Top-Down-Parser ist eben die Idee ähnlich, wie wir es gerade

58:05.720 --> 58:06.440
gemacht haben.

58:06.440 --> 58:10.040
Man möchte ausgehend vom Start-Symbol, also bei uns die Expression,

58:11.380 --> 58:15.320
entscheiden können, welche Regel als nächstes angewendet werden kann.

58:16.260 --> 58:19.520
Und das Problem, das wir eben hatten, war ja, dass man für die

58:19.520 --> 58:22.000
Expression drei verschiedene Regeln anwenden konnte.

58:23.180 --> 58:28.660
Und die Idee beim Top-Down-Parsen oder beim rekursiven Abstieg Parsen

58:28.660 --> 58:33.100
dann auch ist, ist ein sogenanntes Vorschau-Symbol, also Look-Ahead

58:33.100 --> 58:39.020
-Symbol zu verwenden, um zu wissen, welche Regel als nächstes

58:41.580 --> 58:42.960
verwendet werden muss.

58:43.520 --> 58:44.700
Da gibt es unterschiedliche Look-Aheads.

58:44.820 --> 58:47.120
In unserem Fall reicht es jetzt nicht immer nur, ein nächstes Zeichen

58:47.120 --> 58:47.660
anzugucken.

58:48.020 --> 58:50.220
Es gibt dann aber auch kompliziertere Fälle, wo man auch ein Look

58:50.220 --> 58:53.580
-Ahead von mehreren Zeichen vielleicht benötigt.

58:55.440 --> 58:58.740
Okay, hier also erst mal unsere bisherige Grammatik nochmal.

58:59.860 --> 59:03.820
Diese erlaubt es jetzt erst mal, wie gesagt, nicht direkt zu

59:03.820 --> 59:06.640
entscheiden, welche Regel, also immer eindeutig zu entscheiden, welche

59:06.640 --> 59:08.400
Regel als nächstes angewendet werden muss.

59:08.440 --> 59:11.140
Wir hatten ja gerade eben die Frage, wenn ich Expression habe, muss

59:11.140 --> 59:15.120
ich denn jetzt diesen Ausdruck ersetzen oder diesen Teil hier oder

59:15.120 --> 59:17.400
dieses Wort oder das letzte?

59:17.500 --> 59:19.780
Das kann ich hier nicht direkt erkennen.

59:20.440 --> 59:24.580
Und die Idee oder ein Trick, wie man hier vorgehen kann, ist es, die

59:24.580 --> 59:29.400
Grammatik umzuformen mit einem Trick, einer Regel, die man sogenannte

59:29.400 --> 59:33.900
Linksfaktorisierung nennt, um es dann eben zu ermöglichen, immer

59:33.900 --> 59:37.420
anhand des ersten Zeichen oder des nächsten Zeichens eindeutig zu

59:37.420 --> 59:40.640
wissen, welche Regel angewendet werden muss.

59:42.720 --> 59:45.300
Diese Regel kann man jetzt nicht für alle Grammatiken immer anwenden,

59:45.480 --> 59:47.240
aber für diese hier passt es.

59:47.920 --> 59:51.220
Umformen würden wir es dann so, dass wir nämlich sagen, Faktorisierung

59:51.220 --> 59:52.060
steht hier ja auch schon.

59:52.540 --> 59:56.140
Wir faktorisieren die gemeinsamen Teile, die gemeinsamen Beginn, den

59:56.140 --> 01:00:01.420
gemeinsamen Start von diesen Regeln hier heraus in eine einzelne Regel

01:00:01.420 --> 01:00:05.500
und den hinteren Teil, der sich unterscheidet, bildet dann eine

01:00:05.500 --> 01:00:06.960
separate Regel.

01:00:07.520 --> 01:00:08.500
Wie sieht das also aus?

01:00:08.580 --> 01:00:12.540
Wir trennen oder wir stellen hier fest, na ja, diese drei Regeln haben

01:00:12.540 --> 01:00:14.160
ja jeweils immer Term vorne stehen.

01:00:14.260 --> 01:00:15.080
Das ist immer gleich.

01:00:15.540 --> 01:00:17.780
Und dann fangen sie sich aber an zu unterscheiden, dass hier ein Plus

01:00:17.780 --> 01:00:19.400
steht, hier ein Minus und da gar nichts mehr.

01:00:20.160 --> 01:00:22.560
Also kann ich sagen, ich habe zwei Regeln, nämlich eigentlich

01:00:22.560 --> 01:00:27.940
Expression wird ersetzt durch Term und die rechte Seite einer

01:00:27.940 --> 01:00:28.440
Expression.

01:00:28.780 --> 01:00:31.540
Und die rechte Seite einer Expression kann ich dann nochmal ersetzen,

01:00:31.640 --> 01:00:36.040
entweder durch Plus Expression oder durch Minus Expression oder durch

01:00:36.040 --> 01:00:36.740
gar nichts mehr.

01:00:36.820 --> 01:00:38.960
Also Epsilon hier für das leere Wort geschrieben.

01:00:40.160 --> 01:00:41.980
Genau so kann ich es bei der nächsten Regel auch machen.

01:00:42.400 --> 01:00:45.400
Auch hier habe ich das Gemeinsame, dass am Anfang immer Fakt steht.

01:00:45.900 --> 01:00:48.560
Also kann ich auch sagen, ist es eigentlich ein Term überhaupt erst

01:00:48.560 --> 01:00:51.840
mal ein Fakt und eine rechte Seite vom Term und die rechte Seite vom

01:00:51.840 --> 01:00:54.220
Term ist dann nochmal geteilt oder ein leeres Wort.

01:00:55.120 --> 01:00:57.800
Und wenn Sie sich das hier jetzt anschauen, haben also die Regeln oder

01:00:57.800 --> 01:01:01.580
die Produktionsregeln entweder nur eine Möglichkeit oder sie sind eine

01:01:01.580 --> 01:01:04.980
Produktionsregel, wo als erstes, also wo mehrere Möglichkeiten sind,

01:01:05.280 --> 01:01:09.920
aber wo als erstes ein Terminalsymbol steht, wo ich also anhand der

01:01:09.920 --> 01:01:12.240
Zeichenkette, die ich gerade einlese, dann direkt entscheiden kann,

01:01:12.660 --> 01:01:15.560
welche Regel ich denn als nächstes nehmen muss.

01:01:18.790 --> 01:01:20.950
Genau und diese Grammatik, wie gesagt, hat jetzt also diese schöne

01:01:20.950 --> 01:01:24.290
Eigenschaft, dass ich anhand eines, also wenn ich ein Parser bin,

01:01:24.630 --> 01:01:27.170
anhand des nächsten Symbols entscheiden kann, was die nächste Regel

01:01:27.170 --> 01:01:29.690
ist, die ich anwenden muss und ich muss gar nicht mehr nachdenken

01:01:29.690 --> 01:01:33.270
sozusagen und kann also leicht auch einen solchen Parser schreiben.

01:01:33.710 --> 01:01:38.570
Vielleicht noch am Rande bemerkt, die Klasse von Sprachen, für die

01:01:38.570 --> 01:01:41.950
sowas möglich ist, also für die es so leicht möglich ist, nennt man

01:01:41.950 --> 01:01:46.650
LL1 Sprachen und hier steht die 1 für diesen Lookahead von 1, dass ich

01:01:46.650 --> 01:01:50.390
also nur ein Zeichen einlesen brauche, um zu wissen, also ein nächstes

01:01:50.390 --> 01:01:52.950
Zeichen immer einlesen brauche, um zu wissen, was die nächste Regel

01:01:52.950 --> 01:01:53.270
ist.

01:01:53.970 --> 01:02:00.070
Bei dem LL steht das erste L für von links und das zweite L steht für

01:02:00.070 --> 01:02:03.690
leftmost, also links zuerst, dass man, wenn man mehrere Nicht

01:02:03.690 --> 01:02:08.150
-Terminalsymbole hat, das linke dann zuerst auflöst in dem

01:02:08.150 --> 01:02:09.250
dazugehörigen Parser.

01:02:11.010 --> 01:02:14.030
Okay, schauen wir uns jetzt also mal an, wie man diesen Parser

01:02:14.030 --> 01:02:15.950
tatsächlich in Java schreiben könnte.

01:02:20.310 --> 01:02:24.330
Genau, was ich gerade schon gesagt hatte, das Schöne ist, man kann für

01:02:24.330 --> 01:02:27.070
so eine LL1 Sprache, wie wir sie jetzt gerade gesehen haben, einen Top

01:02:27.070 --> 01:02:29.850
- oder Down-Parser bauen, der eben am nächsten Zeichen orientiert

01:02:29.850 --> 01:02:32.390
entscheiden kann, welche Regel anzuwenden ist.

01:02:32.450 --> 01:02:36.170
Und diese Klasse von Parsern nennt man dann wieder Recursive Descent

01:02:36.170 --> 01:02:40.670
oder auch auf Deutsch Recursiva Abstiegszerteiler, wenn man das ganz

01:02:40.670 --> 01:02:41.730
auf Deutsch sagen möchte.

01:02:42.450 --> 01:02:44.690
Wenn wir das jetzt in Java implementieren wollen, können wir eine

01:02:44.690 --> 01:02:48.630
Hilfsklasse verwenden, müssen nicht alles ganz von Hand machen, die

01:02:48.630 --> 01:02:53.410
uns die ganz grundlegende Zerteilung in einfach Textbausteine schon

01:02:53.410 --> 01:02:55.110
mal vornimmt.

01:02:55.830 --> 01:02:59.210
In Java gibt es dafür die sogenannte Stream Tokenizer Klasse.

01:02:59.590 --> 01:03:03.010
Was die macht, ist die sogenannte lexikalische Analyse, dass man eben

01:03:03.010 --> 01:03:08.510
die einzelnen Textbausteine, hatte ich jetzt gerade gesagt, auf

01:03:08.510 --> 01:03:12.570
englischen Tokens, einer solchen Zeichenkette schon mal für mich

01:03:12.570 --> 01:03:14.730
identifiziert, zum Beispiel anhand von Leerzeichen.

01:03:15.130 --> 01:03:19.450
Aber das können auch noch andere Regeln sein, was da diese Tokens dann

01:03:19.450 --> 01:03:20.630
tatsächlich sind.

01:03:21.610 --> 01:03:24.990
Die Klasse kann man einfach verwenden und die würde uns so einen

01:03:24.990 --> 01:03:30.070
String eben schon in verschiedene Elemente in einem Array sozusagen

01:03:30.070 --> 01:03:34.650
zerteilen oder lexikalisch analysieren erstmal.

01:03:35.050 --> 01:03:38.110
Und was denn jetzt noch die Aufgabe unseres Parsers ist, ist für diese

01:03:38.110 --> 01:03:42.330
Zerteilung jetzt noch diesen Baum der Struktur zu finden.

01:03:43.510 --> 01:03:45.950
Wie gesagt, diese einzelnen Pfeile, das wird glaube ich auch noch mal

01:03:45.950 --> 01:03:48.710
eingezweigt, genau nennt man hier Tokens und deswegen heißt diese

01:03:48.710 --> 01:03:52.990
Klasse auch Tokenizer, weil sie eben aus einem String, aus einer

01:03:52.990 --> 01:03:55.910
Zeichenkette diese verschiedenen Tokens heraus extrahiert.

01:03:56.190 --> 01:03:58.910
Und in Java ist es eben schon so gemacht, dass die einzelnen Zahlen an

01:03:58.910 --> 01:04:02.050
sich auch schon ein ganzes Token ergeben und man jetzt nicht noch mit

01:04:02.050 --> 01:04:03.930
den einzelnen Ziffern herumschlagen muss sozusagen.

01:04:05.490 --> 01:04:09.150
Um diesen Parser zu implementieren, brauchen wir außerdem noch zwei

01:04:09.150 --> 01:04:10.730
Hilfsfunktionen.

01:04:11.810 --> 01:04:13.670
Die blende ich mal hier ein.

01:04:14.910 --> 01:04:16.510
Überhaupt erstmal natürlich eine Klasse.

01:04:16.910 --> 01:04:20.450
Unsere Klasse hat, geht's jetzt wieder mit meinem Stift?

01:04:20.750 --> 01:04:20.830
Ja.

01:04:21.670 --> 01:04:25.710
Hat zwei Attribute, nämlich den Lookahead, das ist das nächste

01:04:25.710 --> 01:04:28.750
Zeichen, was ich gelesen habe, hier als Integer abgespeichert, weil

01:04:28.750 --> 01:04:32.670
das die StreamTokenizer Klasse so macht und eben eine Referenz auf

01:04:32.670 --> 01:04:36.470
diese Klasse StreamTokenizer, gibt dann zwei Hilfsmethoden, nämlich

01:04:36.470 --> 01:04:42.190
einmal Next, einmal Match, die Hilfsmethode Next nimmt einfach das

01:04:42.190 --> 01:04:46.350
nächste Zeichen, also fragt diesen StringTokenizer, was das nächste

01:04:46.350 --> 01:04:50.050
Zeichen beziehungsweise das nächste Token ist und speichert das in der

01:04:50.050 --> 01:04:58.110
Variable Lookahead und die Methode Match überprüft, ob ein Zeichen,

01:04:58.110 --> 01:05:01.370
was tatsächlich gelesen wurde, das ist ja in unserer Variable

01:05:01.370 --> 01:05:05.250
Lookahead drin, übereinstimmt mit einem erwarteten Zeichen, was also

01:05:05.250 --> 01:05:07.970
an einer bestimmten Stelle einfach vorkommen muss, was wir wissen.

01:05:08.510 --> 01:05:11.330
Also es prüft, ist das, was ich gerade gelesen habe, auch das, was ich

01:05:11.330 --> 01:05:12.090
erwarte?

01:05:12.490 --> 01:05:16.870
Wenn nicht, dann werfe ich eine neue Exception, PassException, das

01:05:16.870 --> 01:05:20.970
passt irgendwie alles nicht oder ich konsumiere dann dieses eine

01:05:20.970 --> 01:05:23.390
Zeichen und gehe zum nächsten Zeichen, rufe also Next auf.

01:05:24.490 --> 01:05:28.410
Das sind unsere beiden Hilfsfunktionen.

01:05:28.430 --> 01:05:31.610
Ach ja, genau, noch dazu gesagt, Sie wundern sich vielleicht, warum da

01:05:31.610 --> 01:05:34.270
Integer steht für die Zeichen, die gelesen werden.

01:05:34.670 --> 01:05:38.230
Das ist jetzt bei diesem StringTokenizer so, dass der nicht einfach

01:05:38.230 --> 01:05:41.110
das Zeichen oder irgendwie eine Zahl oder so zurückgibt, sondern das

01:05:41.110 --> 01:05:42.470
so ein bisschen codiert sozusagen.

01:05:44.270 --> 01:05:47.950
Und zwar sind in diesem Integerwert dann die, wenn es einzelne Zeichen

01:05:47.950 --> 01:05:50.190
sind, die als nächstes gelesen wurden, die Characters drin.

01:05:50.630 --> 01:05:53.430
Wenn eine Zahl als nächstes gelesen wurde, dann ist einfach eine

01:05:53.430 --> 01:05:55.950
Konstante für eine Zahl drin.

01:05:56.070 --> 01:05:58.130
Ich glaube, das ist, ich weiß nicht mehr, ist das minus 4 oder minus

01:05:58.130 --> 01:05:59.790
20 oder so, ist aber ja auch egal.

01:05:59.890 --> 01:06:02.470
Es ist in der Klasse eben eine Konstante definiert mit einem

01:06:02.470 --> 01:06:05.550
Integerwert, der eine Zahl repräsentiert.

01:06:06.350 --> 01:06:09.430
Es gibt dann auch noch ein Token für EndOfFile, wenn man fertig ist

01:06:09.430 --> 01:06:15.010
oder für Wörter, wenn mal zusammenhängende Mehrzeichen Dinge vorkommen

01:06:15.010 --> 01:06:16.790
in meinem String, das haben wir ja beim Taschenrechner nicht.

01:06:18.170 --> 01:06:20.630
Genau, das sind also die verschiedenen Werte, die dieser

01:06:20.630 --> 01:06:24.190
StringTokenizer als Integers zurückgibt, fürs Verständnis auf der

01:06:24.190 --> 01:06:25.950
nächsten Seite dann noch relevant.

01:06:27.470 --> 01:06:29.990
Und damit mit diesen Hilfsunktionen in dieser Klasse können wir jetzt

01:06:29.990 --> 01:06:33.290
unseren Parser wirklich einfach Regel für Regel nach unserer Grammatik

01:06:33.290 --> 01:06:33.750
schreiben.

01:06:35.330 --> 01:06:39.370
Und wenn wir das so von Hand schreiben, dann brauchen wir auch gar

01:06:39.370 --> 01:06:42.190
nicht mehr diese Linksfaktorisierung, die wir eben gesehen hatten, die

01:06:42.190 --> 01:06:44.150
braucht man eben, um zu überprüfen, ob es geht.

01:06:44.670 --> 01:06:47.690
Aber wenn wir das jetzt schon festgestellt haben, dann können wir es

01:06:47.690 --> 01:06:48.990
auch direkt hinschreiben.

01:06:49.070 --> 01:06:50.830
Wir können also sagen, wir hatten diese Regel hier.

01:06:51.470 --> 01:06:52.950
Es geht mein Stift schon wieder nicht, na gut.

01:06:53.730 --> 01:06:57.390
Diese Regel Expression wird ersetzt, entweder durch TermPlusExpression

01:06:57.390 --> 01:07:00.670
oder durch TermMinusExpression oder einfach nur durch Term.

01:07:01.210 --> 01:07:04.470
Und das realisiere ich dann in einer Methode, die PassExpression

01:07:04.470 --> 01:07:08.130
heißt, also die diese Regel umsetzen soll, indem ich sage, naja, ich

01:07:08.130 --> 01:07:11.530
weiß, am Anfang kommt sowieso erst mal ein Term, also kann ich die

01:07:11.530 --> 01:07:15.030
Methode PassTerm, die wir unten definieren werden, aufrufen und dann

01:07:15.030 --> 01:07:17.330
mache ich eben diese Lookahead, um zu entscheiden, mache ich denn

01:07:17.330 --> 01:07:20.090
jetzt bei dieser Regel weiter oder bei dieser hier oder hier hinten?

01:07:20.870 --> 01:07:25.390
Und zwar überprüfe ich, wenn der Lookahead Plus oder Minus ist,

01:07:26.430 --> 01:07:29.290
konsumiere ich das nächste Token, was ja das Plus oder das Minus ist

01:07:29.290 --> 01:07:33.170
und sage dann, ich rufe die Methode PassExpression auf wieder, um

01:07:33.170 --> 01:07:35.070
diesen Teil hier auszuwerten oder diesen.

01:07:36.270 --> 01:07:38.950
Oder wenn ich schon fertig bin, dann bin ich fertig, dann kann meine

01:07:38.950 --> 01:07:40.470
Methode direkt terminieren.

01:07:41.870 --> 01:07:45.770
Die nächste Regel, Term, kann ich, wie hier unten gezeigt, umsetzen.

01:07:45.890 --> 01:07:48.970
Ich kann sagen, ein Term, oder vielleicht erstmal noch zur

01:07:48.970 --> 01:07:51.950
Wiederholung, kann ich ersetzen durch FaktMalTerm, FaktDurchTerm oder

01:07:51.950 --> 01:07:52.770
einfach nur Fraktor.

01:07:54.030 --> 01:07:57.470
Das kann ich wieder genauso machen, den gemeinsamen Teil schreibe ich

01:07:57.470 --> 01:08:01.210
vorne weg, schreibe PassFact und dann kommt dieses Lookahead von nur

01:08:01.210 --> 01:08:04.530
einem Zeichen, dann entscheide ich quasi, in welche dieser Regeln ich

01:08:04.530 --> 01:08:09.170
wirklich reingehen will und sage, wenn es mal oder geteilt hier als

01:08:09.170 --> 01:08:13.010
nächstes Zeichen gelesen wird, dann konsumiere ich dieses Zeichen und

01:08:13.010 --> 01:08:17.330
rufe PassTerm auf, weil dann kommt ja ein Term dahinter oder wenn das

01:08:17.330 --> 01:08:18.990
nicht der Fall ist, dann bin ich anscheinend fertig.

01:08:19.970 --> 01:08:22.790
Hinten kann ich es dann nur noch in einen Fakt umsetzen, den ich hier

01:08:22.790 --> 01:08:23.710
oben schon gepasst habe.

01:08:25.870 --> 01:08:29.910
Und letzte Regel, wir hatten ja nur drei, ein Fakt ist ein bisschen

01:08:29.910 --> 01:08:31.950
interessanter und wir brauchen jetzt auch mal die Match-Funktion

01:08:31.950 --> 01:08:35.590
dafür, denn hier kann ich ja entweder ersetzen durch Klammern und da

01:08:35.590 --> 01:08:37.510
drin eine Expression oder durch eine Zahl.

01:08:38.170 --> 01:08:40.610
Hier kann ich jetzt also direkt gucken, was ist das nächste Zeichen,

01:08:40.690 --> 01:08:44.670
was ich einlese, wenn es eine geöffnete Klammer ist, würde ich sagen

01:08:44.670 --> 01:08:47.870
Match, die geöffnete Klammer, da hätte ich auch direkt Next schreiben

01:08:47.870 --> 01:08:49.230
können, das kommt eigentlich aufs Gleiche raus.

01:08:49.710 --> 01:08:53.550
Dann rufe ich wieder PassExpression auf, um hier weiterzumachen mit

01:08:53.550 --> 01:08:59.530
der Ersetzung anhand der ersten Regel und dann muss ich, nachdem ich

01:08:59.530 --> 01:09:02.570
mit dieser Expression hier in der Mitte fertig bin, muss das nächste

01:09:02.570 --> 01:09:04.350
Zeichen eine schließende Klammer sein.

01:09:04.350 --> 01:09:08.630
Sonst gibt es eben eine Exception, wenn hier plötzlich eine Zahl

01:09:08.630 --> 01:09:11.710
kommt, die da nicht hingehört, ohne Operator zum Beispiel verbunden.

01:09:13.130 --> 01:09:17.650
Das ist also der erste Fall, wenn ich eine Klammer finde und wenn ich

01:09:17.650 --> 01:09:20.670
keine Klammer finde, prüfe ich, ist das nächste Zeichen eine Zahl,

01:09:21.330 --> 01:09:24.230
wenn ja, dann konsumiere ich diese Zahl, weil dann habe ich ja nicht,

01:09:24.390 --> 01:09:28.870
jetzt bin ich direkt drauf gehüpft, ein Terminalsymbol und wenn es das

01:09:28.870 --> 01:09:31.890
auch nicht ist, dann ist irgendwas Unerwartetes, dann habe ich also

01:09:31.890 --> 01:09:33.550
hier einen Fehler beim Parsen.

01:09:35.550 --> 01:09:40.470
Genau und so, jetzt ist es auch schon später, so sehen Sie halt, wenn

01:09:40.470 --> 01:09:44.410
man erst mal diese Vorarbeit gemacht hat, so eine Grammatik zu

01:09:44.410 --> 01:09:48.230
definieren, kann man in Java anhand dieser StreamVocalizer-Klasse im

01:09:48.230 --> 01:09:51.950
Prinzip die einzelnen Regeln der Grammatik auch tatsächlich einfach so

01:09:51.950 --> 01:09:57.230
hinschreiben und sich so einen Parser für solche Ausdrücke schreiben.

01:10:00.370 --> 01:10:03.910
Genau, kommen wir zur Zusammenfassung zu diesem Teil, der, ich gucke

01:10:03.910 --> 01:10:06.230
gerade beschreckend auf die Uhr, ein bisschen länger geworden ist, als

01:10:06.230 --> 01:10:06.970
das gedacht war.

01:10:07.210 --> 01:10:11.570
Naja, beim Parsen geht es also darum, die Struktur eines Textes zu

01:10:11.570 --> 01:10:11.930
erkennen.

01:10:12.390 --> 01:10:14.950
Es gibt diese zwei großen Klassen von Parsern, die ich erwähnt hatte,

01:10:15.130 --> 01:10:17.370
Top -Down oder Bottom-Up und wir haben uns eben so einen Top-Down

01:10:17.370 --> 01:10:18.270
-Parser angeschaut.

01:10:19.270 --> 01:10:24.390
Um einen solchen Top-Down-Parser oder Top-Down-Zerteiler zu bauen,

01:10:24.530 --> 01:10:27.650
muss man sich erst mal überlegen, was die Grammatik ist, die man vor

01:10:27.650 --> 01:10:28.110
sich hat.

01:10:28.630 --> 01:10:31.590
Eventuell muss man die Grammatik transformieren, um eben in den Regeln

01:10:31.590 --> 01:10:34.350
eindeutig entscheiden zu können, welche Regel als nächstes angewendet

01:10:34.350 --> 01:10:34.790
werden kann.

01:10:34.910 --> 01:10:38.670
Da hatten Sie diese Faktorisierung gesehen und dann kann ich jede

01:10:38.670 --> 01:10:40.570
Regel in einer Methode implementieren.

01:10:40.750 --> 01:10:43.290
Wie gesagt, klappt das nicht für alle Sprachen, aber für diese, wie

01:10:43.290 --> 01:10:44.810
wir gerade hatten, klappte das gut.

01:10:45.850 --> 01:10:48.750
Wenn man komplexere Grammatiken vor sich hat, macht es auch Sinn,

01:10:49.110 --> 01:10:51.910
solche Parser nicht von Hand zu schreiben, sondern sogenannte Parser

01:10:51.910 --> 01:10:53.170
-Generatoren zu verwenden.

01:10:53.590 --> 01:10:58.030
Das sind wiederum Programme, die als Eingabe eine Grammatik bekommen

01:10:58.030 --> 01:11:01.990
und dann für diese Grammatik einen Parser als Ausgabe produzieren,

01:11:02.110 --> 01:11:04.230
also die ein Programm als Ausgabe produzieren.

01:11:04.370 --> 01:11:05.710
Deswegen Generator.

01:11:06.470 --> 01:11:08.990
Bei noch einfacheren Sprachen als das, was wir hier gesehen haben,

01:11:09.270 --> 01:11:12.410
reguläre Sprachen, kann man auch Automaten oder sogar nur reguläre

01:11:12.410 --> 01:11:13.950
Ausdrücke verwenden.

01:11:14.810 --> 01:11:14.990
Genau.

01:11:15.070 --> 01:11:17.910
Und auch hier ein Pointer auf zukünftige Vorlesungen.

01:11:18.070 --> 01:11:21.630
Wenn Sie das interessiert, dieses Thema zerteilen, lernen Sie da in

01:11:21.630 --> 01:11:25.170
der Vorlesung Übersetzerbau bei Gregor Snelting mehr dazu.

01:11:28.740 --> 01:11:31.720
Okay, das war jetzt wie gesagt ein bisschen lange zum Thema Parsen,

01:11:31.900 --> 01:11:32.580
aber na gut.

01:11:33.400 --> 01:11:34.900
Schauen wir uns aber das Suchen noch an.

01:11:34.980 --> 01:11:37.100
Das ist jetzt nicht so ein langer Teil der Vorlesung.

01:11:37.160 --> 01:11:38.820
Das passt, glaube ich, noch ganz gut.

01:11:39.920 --> 01:11:42.580
Suchen also eine andere Klasse von Problemen.

01:11:42.660 --> 01:11:45.980
Ich habe irgendwie Daten und ich möchte wissen, ob ein bestimmtes

01:11:45.980 --> 01:11:49.820
Datum, was ich suche, in diesen vielen Daten enthalten ist.

01:11:49.900 --> 01:11:52.200
Und da gibt es zwei Strategien, oder es gibt auch noch mehr, aber zwei

01:11:52.200 --> 01:11:55.080
Strategien, die wir uns anschauen werden, nämlich die lineare Suche

01:11:55.080 --> 01:11:56.600
und die binäre Suche.

01:11:57.060 --> 01:12:01.140
Lineare Suche ist so ein bisschen das einfache Idee, wie man vorgehen

01:12:01.140 --> 01:12:01.520
könnte.

01:12:04.100 --> 01:12:06.200
Genau, was ist das oder was ist gegeben?

01:12:06.260 --> 01:12:08.200
Was ist die Eingabe bei so einer linearen Suche?

01:12:08.600 --> 01:12:12.280
Gegeben ist ein Array A mit beliebigen Elementen.

01:12:12.460 --> 01:12:14.740
Wir nehmen unseren Beispiel mal an, die sind vom Typ Long, aber es

01:12:14.740 --> 01:12:15.580
könnte irgendwas sein.

01:12:16.020 --> 01:12:20.580
Und auf der einen Seite und ein Element X auf der anderen Seite, was

01:12:20.580 --> 01:12:23.240
ich eben suchen möchte in diesem Array.

01:12:23.540 --> 01:12:26.720
Und dann gibt es zwei Varianten von so einer Such-Fragestellung.

01:12:27.000 --> 01:12:31.320
Man kann einerseits fragen, kommt X überhaupt in A vor, wo das

01:12:31.320 --> 01:12:33.820
Ergebnis dann wohl verwertet ist, also ja oder nein.

01:12:34.540 --> 01:12:38.520
Oder man ist manchmal daran interessiert, wo steht X in diesem A?

01:12:38.680 --> 01:12:41.380
Also welche, an welcher Position finde ich X?

01:12:41.900 --> 01:12:43.360
Vielleicht gibt es auch mehrere X da drin.

01:12:43.540 --> 01:12:44.620
Das wäre dann noch eine Variante.

01:12:44.780 --> 01:12:46.300
An welchen Positionen stehen sie?

01:12:46.660 --> 01:12:48.440
Oftmals sucht man auch nur nach der ersten Position.

01:12:50.020 --> 01:12:52.320
Das ist eben der Input für diese lineare Suche.

01:12:52.460 --> 01:12:54.720
Voraussetzungen hier sind keine weiteren, wie bei der anderen

01:12:54.720 --> 01:12:55.920
Suchstrategie.

01:12:56.320 --> 01:12:59.220
Und die Lösungsmethode, so eine Suche oder eine lineare Suche zu

01:12:59.220 --> 01:13:03.860
machen, ist einfach, ich durchlaufe alle Elemente des Arrays, bis ich

01:13:03.860 --> 01:13:07.640
entweder X gefunden habe oder bis ich das Ende des Arrays erreicht

01:13:07.640 --> 01:13:07.920
habe.

01:13:08.120 --> 01:13:10.720
Also das, jetzt werden Sie wahrscheinlich auch von alleine

01:13:10.720 --> 01:13:14.460
draufgekommen, aber so funktioniert lineare Suche.

01:13:14.620 --> 01:13:16.740
Das könnte man so implementieren, wie hier dargestellt.

01:13:16.800 --> 01:13:18.440
Brauchen wir, glaube ich, auch nicht so tief einsteigen.

01:13:19.000 --> 01:13:21.400
Entweder diese Variante, ich will einfach nur wissen, ob es drin ist

01:13:21.400 --> 01:13:24.860
oder die Variante, ich möchte auch den Index wissen.

01:13:25.120 --> 01:13:26.560
Und ich gehe mal kurz rein.

01:13:26.980 --> 01:13:32.480
Man kann eben hier zum Beispiel, ja das in der Wildschleife

01:13:32.480 --> 01:13:37.180
implementieren und sagen, solange mein Index noch kleiner ist als die

01:13:37.180 --> 01:13:41.020
Länge und ich das Element noch nicht gefunden habe, überprüfe ich

01:13:41.020 --> 01:13:45.200
immer, ob das aktuelle Element an meinem Index den gesuchten Wert hat.

01:13:45.200 --> 01:13:48.540
Wenn ja, oder sowieso, setze ich das Ergebnis dieses Vergleichs in die

01:13:48.540 --> 01:13:53.180
Variable found und inkrementiere i und wenn ich dann eben ein Element

01:13:53.180 --> 01:13:55.800
gefunden habe, breche ich diese Wildschleife ab oder wenn ich am Ende

01:13:55.800 --> 01:13:56.480
des Arrays bin.

01:13:57.080 --> 01:13:59.500
Ähnlich auch, wenn ich das Ganze mit dem Index mache.

01:14:02.040 --> 01:14:04.120
Wie sieht das visualisiert aus?

01:14:04.540 --> 01:14:08.360
Wenn ich jetzt mal die Variante, wo ich den Index haben möchte, mir

01:14:08.360 --> 01:14:12.440
anschaue, würde ich das Ganze erstmal initialisieren oder ich würde

01:14:12.440 --> 01:14:18.420
mal annehmen, wir berufen das mit den Variablen, ich suche eine 5 und

01:14:18.420 --> 01:14:22.340
meine Arraylänge ist auch 5 auf, würde dann durchiterieren.

01:14:22.720 --> 01:14:24.140
Ich habe es am Anfang noch nicht gefunden.

01:14:24.360 --> 01:14:25.340
Es wird hier jetzt gerade grün.

01:14:26.240 --> 01:14:28.360
Den Index setze ich am Anfang auf minus 1.

01:14:29.760 --> 01:14:32.060
Das i initialisiere ich auf 0.

01:14:32.700 --> 01:14:34.320
Dann werte ich diesen Ausdruck aus.

01:14:34.580 --> 01:14:36.780
Habe ich es schon gefunden und ist i noch kleiner als die Länge?

01:14:36.940 --> 01:14:37.600
Das ist der Fall.

01:14:38.500 --> 01:14:39.340
Dann mache ich einen Vergleich.

01:14:39.620 --> 01:14:44.300
Ist am ersten Element meines Arrays hier unten, das gesuchte Wert

01:14:44.300 --> 01:14:45.120
schon drin.

01:14:45.700 --> 01:14:48.600
Vergleiche also diese 4, die hier drin steht, mit meiner 5.

01:14:49.180 --> 01:14:49.900
Ist nicht der Fall.

01:14:50.420 --> 01:14:52.160
Also gehe ich weiter, inkrementiere i.

01:14:54.320 --> 01:14:55.500
Schleifenabbruchbedingung ist auch noch nicht erfüllt.

01:14:55.640 --> 01:14:57.620
Dann mache ich den Vergleich wieder mit dem nächsten Array-Element.

01:14:58.440 --> 01:14:59.200
Wieder nicht erfüllt.

01:14:59.820 --> 01:15:00.500
Inkrementiere i.

01:15:01.780 --> 01:15:02.980
Prüfe wieder die Bedingung.

01:15:04.560 --> 01:15:06.740
Diesmal ist der Vergleich erfüllt, denn hier an dritter Stelle steht

01:15:06.740 --> 01:15:07.640
tatsächlich eine 5.

01:15:08.080 --> 01:15:10.580
Das heißt, ich gehe hier rein, setze den Index entsprechend und setze

01:15:10.580 --> 01:15:13.740
found of true, sodass dann meine Bedingung in der nächsten Iteration

01:15:13.740 --> 01:15:17.100
nicht mehr erfüllt ist und ich dann diesen Index zurückgeben kann.

01:15:17.340 --> 01:15:18.860
Also recht straightforward.

01:15:20.260 --> 01:15:22.020
Das wäre die lineare Suche.

01:15:22.080 --> 01:15:25.400
Die dauert halt, also da muss man eben durch gegebenenfalls ganze

01:15:25.400 --> 01:15:27.800
Array durchschreiten, um festzustellen, dass irgendetwas nicht

01:15:27.800 --> 01:15:28.900
enthalten sind.

01:15:29.300 --> 01:15:31.960
Gibt noch eine andere Suchstrategie, die jetzt eine gewisse

01:15:31.960 --> 01:15:32.920
Voraussetzung hat.

01:15:33.580 --> 01:15:36.540
Das gleiche gegebenen Array A und einen Wert, den ich suche.

01:15:36.840 --> 01:15:40.840
Und ich frage mich eben, kommt X in A vor oder wo steht X?

01:15:41.380 --> 01:15:45.660
Die Voraussetzung für so eine binäre Suche ist dann, dass das Array A

01:15:45.660 --> 01:15:47.940
schon aufsteigend sortiert sein muss.

01:15:48.520 --> 01:15:52.580
Und wenn ich eben die sozusagen luxuriöse Situation habe, dass mein

01:15:52.580 --> 01:15:56.300
Array schon aufsteigend sortiert sein muss, dann kann ich effizienter

01:15:56.300 --> 01:15:56.540
suchen.

01:15:56.640 --> 01:15:59.040
Dann muss ich nicht einfach unten anfangen, sondern dann kann ich

01:15:59.040 --> 01:16:02.680
einen effizienteren Suchalgorithmus implementieren.

01:16:03.380 --> 01:16:04.540
Und zwar den folgenden.

01:16:07.120 --> 01:16:11.900
Ich wähle das mittlere Element meines Arrays und vergleiche.

01:16:11.940 --> 01:16:13.680
Also erstmal gucke ich, ist das schon das gesuchte?

01:16:13.760 --> 01:16:15.440
Das wäre natürlich Glück, dann bin ich schon fertig.

01:16:15.960 --> 01:16:21.420
Wenn es nicht das gesuchte ist, dann schaue ich, ist das Element P,

01:16:21.520 --> 01:16:24.760
was ich gerade vor mir habe, größer oder kleiner meinem gesuchten Wert

01:16:24.760 --> 01:16:28.320
und weiß anhand dessen, weil ich ja weiß, dass es sortiert ist, ob ich

01:16:28.320 --> 01:16:30.960
rechts davon oder links davon weitersuchen muss.

01:16:31.040 --> 01:16:33.840
Ich teile also das Array auf in zwei Hälften und suche in der

01:16:33.840 --> 01:16:36.880
richtigen Hälfte des Arrays weiter nach meinem gesuchten Wert.

01:16:37.320 --> 01:16:41.180
Und so muss ich eben nie alle Elemente meines Arrays anschauen.

01:16:42.460 --> 01:16:44.920
Das kann ich dann, wie hier gezeigt, implementieren.

01:16:45.440 --> 01:16:48.660
Aber ich mache es vielleicht mal direkt anhand des Beispiels.

01:16:49.160 --> 01:16:49.980
Methode find.

01:16:50.120 --> 01:16:52.180
Ich habe gewisse Initialisierung und dann auch wieder eine

01:16:52.180 --> 01:16:55.500
Wildschleife, die sagt, habe ich es schon gefunden, dann kann ich

01:16:55.500 --> 01:17:00.820
natürlich beenden oder sind meine beiden Hilfsvariablen low und high

01:17:00.820 --> 01:17:04.280
sozusagen falsch rum, weil dann bin ich irgendwo in den Bereich

01:17:04.280 --> 01:17:06.760
reingelaufen, ohne das Element gefunden zu haben.

01:17:06.840 --> 01:17:07.560
Werden Sie gleich sehen.

01:17:08.840 --> 01:17:12.340
Wenn ich hier starten würde, zum Beispiel mit den Werten 9 und 7, also

01:17:12.340 --> 01:17:16.500
ein Array mit Länge 7 und dem Wert 9, den ich suche, initialisiere ich

01:17:16.500 --> 01:17:21.860
erst mal meine Werte, laufe die Schleife rein und würde dann die

01:17:21.860 --> 01:17:26.640
Variable Medium setzen auf die Mitte von low und high.

01:17:26.700 --> 01:17:33.080
Low und high sind erst mal als Länge des Arrays und 0 initialisiert.

01:17:33.180 --> 01:17:36.300
Das wäre in unserem Fall jetzt der Wert 3.

01:17:37.040 --> 01:17:39.780
Ich schaue jetzt also, steht mein gesuchter Wert vielleicht schon

01:17:39.780 --> 01:17:41.120
zufällig an der Stelle 3.

01:17:42.380 --> 01:17:43.760
Das ist natürlich jetzt hier nicht der Fall.

01:17:43.960 --> 01:17:46.220
Wenn nicht, ist mein gesuchter Wert kleiner als 3.

01:17:46.320 --> 01:17:47.140
Das ist er auch nicht.

01:17:47.540 --> 01:17:51.020
Dann ist mein gesuchter Wert wohl größer als 3 und ich muss nur noch

01:17:51.020 --> 01:17:52.680
an dieser Seite des Arrays weitersuchen.

01:17:53.040 --> 01:17:54.320
Ich brauche mir das hier gar nicht mehr anschauen.

01:17:54.440 --> 01:17:55.700
Also wenn ich hier sehe, es ist eine 6.

01:17:56.040 --> 01:17:58.700
Wenn ich weiß, ich suche eine 9 und ich weiß, das Array ist sortiert,

01:17:58.800 --> 01:18:00.300
dann muss ich nur noch auf die rechte Seite gucken.

01:18:00.680 --> 01:18:02.320
Das ist dann jetzt hier gerade passiert.

01:18:02.420 --> 01:18:06.780
Ich kann ein low auf 3 setzen, auf den neuen Wert oder 4.

01:18:07.000 --> 01:18:10.060
3 kenne ich ja schon und kann dann entsprechend weitermachen.

01:18:10.280 --> 01:18:13.240
Genau, dann vergleiche ich, schaue ich mir wieder hier die Mitte an.

01:18:13.280 --> 01:18:13.880
Das wäre 10.

01:18:14.360 --> 01:18:17.220
9 ist kleiner und dann bleibt nur noch das Array hier in der Mitte mit

01:18:17.220 --> 01:18:18.640
einem Element übrig.

01:18:20.280 --> 01:18:25.320
Genau, so kann man dann weiter durchgehen und das wären auch schon die

01:18:25.320 --> 01:18:27.140
Einsichten zur Suche.

01:18:27.200 --> 01:18:28.440
Wie gesagt, recht einfach.

01:18:29.080 --> 01:18:31.360
Die lineare Suche konnten Sie sich wahrscheinlich jetzt auch schon

01:18:31.360 --> 01:18:32.480
selber vorstellen, wie das geht.

01:18:32.580 --> 01:18:34.980
Aber interessant jetzt auch mitzunehmen, wenn ich schon ein bisschen

01:18:34.980 --> 01:18:37.900
mehr weiß über meine Daten, wie zum Beispiel, dass sie sortiert sind,

01:18:38.200 --> 01:18:41.480
kann ich schlauere Suchverfahren wie zum Beispiel die binäre Suche

01:18:41.480 --> 01:18:42.660
hier auch verwenden.

01:18:42.920 --> 01:18:44.380
Oder Sie verwenden Methoden aus der API.

01:18:44.500 --> 01:18:45.300
Das geht natürlich auch.

01:18:45.960 --> 01:18:49.720
Gut, dann bis nächste Woche.

01:18:50.200 --> 01:18:51.340
Schöne Woche wünsche ich Ihnen.

01:18:51.740 --> 01:18:52.480
Genau, bis dann.