WEBVTT

00:07.020 --> 00:10.540
Ja, dann willkommen zur letzten Vorlesung Algorithmen 1.

00:11.940 --> 00:16.200
Ich habe beim letzten Mal angefangen, eine Zusammenfassung der

00:16.200 --> 00:17.400
Vorlesung zu machen.

00:19.440 --> 00:23.580
Das fing an mit relativ offensichtlichen Auflistungen der

00:23.580 --> 00:27.360
Datenstrukturen und Algorithmen, die wir kennengelernt haben.

00:27.740 --> 00:30.920
Ich habe aber dann betont, dass fast noch wichtiger als diese

00:30.920 --> 00:36.580
konkreten Lösungsansätze Entwurfstechniken sind, die wir kennengelernt

00:36.580 --> 00:36.900
haben.

00:38.320 --> 00:41.460
Da war ich dann bei dieser Folie stehen geblieben letztes Mal.

00:45.500 --> 00:47.000
Da trage ich das nochmal vor.

00:47.220 --> 00:49.660
Also wir haben so Sachen wie, naja, wie baue ich Schleifen?

00:49.780 --> 00:51.520
Wir machen Teile- und Herrscheralgorithmen.

00:52.600 --> 00:54.080
Das ist offensichtlich.

00:56.320 --> 00:59.840
Die anderen Sachen hier sind gar nicht so offensichtlich, aber treten

00:59.840 --> 01:02.480
immer wieder auf und man sollte sich dessen bewusst sein als

01:02.480 --> 01:03.000
Möglichkeit.

01:04.240 --> 01:07.580
Erstmal, dass man mit Schleifen und Datenstruktur-Invarianten

01:07.580 --> 01:11.780
eigentlich den essentiellen Teil eines Entwurfs, eines Algorithmus

01:11.780 --> 01:15.980
oder einer Datenstruktur bereits im Kasten hat und der Rest eigentlich

01:15.980 --> 01:17.380
nur noch Detailarbeit ist.

01:18.520 --> 01:23.440
Dann randomisierte Algorithmen sind einfach, wir modellieren Probleme

01:23.440 --> 01:24.480
durch Graphen.

01:25.880 --> 01:29.280
Wir haben verschiedene Bedeutungsebenen, Mathematik, Funktionalität,

01:29.460 --> 01:33.320
Repräsentation, Algorithmus und konkrete Implementierung.

01:34.860 --> 01:38.160
Wir sollten bei der Implementierung Sonderfälle vermeiden, wenn das

01:38.160 --> 01:38.900
möglich ist.

01:39.420 --> 01:44.280
Ganz allgemein kann man fortgeschrittene Datenstrukturen durch Zeiger

01:44.280 --> 01:49.320
und Verweise zwischen Objekten aufbauen.

01:50.500 --> 01:54.520
Einmal verstandene Datenstruktur kann man sozusagen aufbohren, indem

01:54.520 --> 01:57.960
man zusätzliche Informationen speichert und damit zusätzliche

01:57.960 --> 02:00.280
Operationen effizient unterstützen kann.

02:03.080 --> 02:08.080
Wir haben mehrere Datenstrukturen kennengelernt, bei denen es Sinn

02:08.080 --> 02:11.200
macht, sie adaptiv wachsen zu lassen.

02:11.320 --> 02:14.960
Wir haben uns das im Detail angeschaut für Arrays.

02:16.500 --> 02:20.240
Aber das gleiche könnte man machen für zyklische Arrays, für

02:20.240 --> 02:24.840
Hashtabellen oder Binary Prioritätslisten.

02:24.840 --> 02:30.700
Da ist immer dieser Effekt, man kann Elemente einfügen und wenn die

02:30.700 --> 02:34.600
Datenstruktur zu voll wird, kann man das Array, in dem das Ganze

02:34.600 --> 02:35.900
gespeichert ist, vergrößern.

02:38.300 --> 02:40.820
Und das ist zum Beispiel auch eine schöne Klausuraufgabe.

02:41.360 --> 02:47.240
Bauen Sie unbeschränkte Hashtabellen oder unbeschränkte zyklische

02:47.240 --> 02:52.800
Arrays, definieren Sie, wie das geht, argumentieren Sie, dass das

02:52.800 --> 02:54.100
amortisiert effizient ist.

02:54.100 --> 02:56.720
Das wird genau das gleiche sein, wie bei den Arrays.

02:57.060 --> 02:59.840
Das haben wir in der Vorlesung weggelassen, ich glaube, in der Übung

02:59.840 --> 03:01.480
war das Auswahlmal dran.

03:03.580 --> 03:08.880
Dann gibt es implizite Datenstrukturen, die ein mathematisches Objekt

03:08.880 --> 03:12.880
repräsentieren, in einer sehr anwendungsspezifischen Art und Weise.

03:13.400 --> 03:19.020
Zum Beispiel hatten wir gesehen, wie man Intervallgrafen definieren

03:19.020 --> 03:19.400
kann.

03:19.400 --> 03:25.220
Die Knoten sind Intervalle auf der reellen Zahlenachse und Kanten sind

03:25.220 --> 03:29.460
implizit definiert, dadurch, dass eine Kante da ist, wenn zwei

03:29.460 --> 03:31.420
Intervalle sich schneiden.

03:32.320 --> 03:35.220
Und damit kann man dann eben sehr dichte Grafen mit sehr wenig

03:35.220 --> 03:37.400
Information repräsentieren.

03:37.500 --> 03:43.320
Andererseits haben diese Grafen dann auch eine spezielle Struktur, die

03:43.320 --> 03:46.520
es erlaubt, bestimmte Algorithmen effizienter zu machen.

03:46.520 --> 03:50.900
Auch das ist ein beliebtes Thema für Klausuraufgaben, weil man dann

03:50.900 --> 03:54.020
Grafentheorie und Sortieren zusammenzieht.

03:54.060 --> 03:58.160
Wir haben uns zum Beispiel in der Vorlesung Zusammenhangskomponenten

03:58.160 --> 03:58.900
angeschaut.

04:00.360 --> 04:05.060
Man kann aber viele andere algorithmische Fragestellungen auf

04:05.060 --> 04:08.720
Intervallgrafen sehr leicht lösen mit analogen Techniken.

04:11.680 --> 04:16.400
Andere Algorithmen und Entwurfsmuster sind Ausnutzung algebraischer

04:16.400 --> 04:16.860
Eigenschaften.

04:17.860 --> 04:20.940
Wir haben da ganz am Anfang zum Beispiel den Karatsuba-Algorithmus

04:20.940 --> 04:23.280
gesehen zur Multiplikation langer Zahlen.

04:24.340 --> 04:31.060
Wir haben bei universellen Hash-Funktionen die Eigenschaft von Körpern

04:31.060 --> 04:35.140
benutzt, dass sie ein eindeutig definiertes inverses Element haben.

04:36.060 --> 04:42.500
Wir haben Matrixmultiplikation ausgenutzt, um Pfade in Grafen zu

04:42.500 --> 04:44.220
zählen und so weiter.

04:44.620 --> 04:47.100
Also algebraische Techniken kommen immer wieder vor.

04:48.080 --> 04:53.200
Wir haben Algorithmen Schemata gesehen, wie Tiefensuche oder lokale

04:53.200 --> 04:58.880
Suche, die also ein Muster vorgeben für eine ganze Familie von

04:58.880 --> 05:03.640
Algorithmen, wo wir dann nur bestimmte Funktionen noch näher festlegen

05:03.640 --> 05:07.960
müssen, um eine konkrete Instanzierung dieses Schemas zu bekommen.

05:08.740 --> 05:11.200
Auch da könnte man schöne Klausuraufgaben machen.

05:12.240 --> 05:17.900
Lösen Sie dies und das mit Hilfe von DFS oder lokaler Suche und

05:17.900 --> 05:21.080
arbeiten Sie aus, wie dann die einzelnen Funktionen auszusehen haben.

05:25.300 --> 05:29.760
Dann haben wir einige Algorithmen gesehen, bei denen wir abstrakte

05:29.760 --> 05:31.500
Problemeigenschaften benutzen.

05:31.620 --> 05:35.760
Zum Beispiel waren alle Minimum-Spanning-Tree-Algorithmen, die wir

05:35.760 --> 05:38.100
gesehen haben, von der Art, dass sie die Schnitt- oder

05:38.100 --> 05:39.640
Kreiseigenschaft benutzen,

05:42.700 --> 05:48.120
um Kanten des minimalen Spannbaums zu identifizieren oder auch

05:48.120 --> 05:48.920
auszuschließen.

05:48.920 --> 05:52.520
Oder wir haben diese Blackbox-Löser gesehen.

05:54.060 --> 05:58.420
Ich baue nicht meinen eigenen Algorithmus, sondern wälze das ab auf

05:58.420 --> 06:02.580
irgendein bekanntes Verfahren und muss dann nur noch eine Modellierung

06:02.580 --> 06:05.840
meines Problems in der richtigen Sprache finden.

06:05.940 --> 06:08.900
Zum Beispiel etwas durch ein lineares Programm ausdrücken.

06:08.900 --> 06:15.200
Auch das beliebtes Thema für Klausuraufgaben oder Übungsaufgaben.

06:15.960 --> 06:18.980
Modellieren Sie dieses und jenes Optimierungsproblem als lineares

06:18.980 --> 06:21.440
Programm oder als ganzzeitiges lineares Programm?

06:22.220 --> 06:25.480
Wenn das in der Klausur drankommt, werden wir da aber durchaus

06:25.480 --> 06:29.780
einfache Sachen wählen, aber tendenziell das dann verbinden mit

06:29.780 --> 06:31.560
anderen Sachen, die Sie schon gesehen haben.

06:31.560 --> 06:34.040
Zum Beispiel ein grafentheoretisches Problem.

06:34.740 --> 06:37.540
Wir haben ja zum Beispiel in der Vorlesung gesehen, wie man kürzeste

06:37.540 --> 06:40.800
Wege grafentheoretisch modellieren kann.

06:43.060 --> 06:46.720
Oder Greedy-Algorithmen, dynamische Programmier-Algorithmen, auch

06:46.720 --> 06:50.060
beliebtes Thema für Klausuraufgaben.

06:50.440 --> 06:53.300
Entwerfen Sie einen Greedy-Algorithmus für folgendes Problem.

06:54.080 --> 06:57.020
Entwerfen Sie ein dynamisches Programmier-Algorithmus für folgendes

06:57.020 --> 06:57.380
Problem.

07:03.400 --> 07:06.760
Systematische Suche, das gleiche Spiel, Metaheuristiken wie lokale

07:06.760 --> 07:08.520
Suche oder evolutionäre Algorithmen.

07:09.200 --> 07:12.200
Tendenziell werden wir natürlich, je komplizierter die Metaheuristik

07:12.200 --> 07:15.800
ist, desto unwahrscheinlich ist es, dass das in der Klausur drankommt.

07:16.300 --> 07:19.340
Zum Beispiel zu sagen, entwerfen Sie einen evolutionären Algorithmus

07:19.340 --> 07:23.380
für folgendes Problem, macht wenig Sinn, weil wir da ja gar nicht im

07:23.380 --> 07:26.500
Detail darauf eingegangen sind, wie das geht, keine Beispiele gesehen.

07:29.660 --> 07:34.980
Ein weiteres abstraktes Thema, das wir kennengelernt haben, sind

07:34.980 --> 07:36.820
Techniken zur Analyse von Algorithmen.

07:36.920 --> 07:41.340
Auch das ist ein wichtiges Ziel dieser Vorlesung, das wir halt nur

07:41.340 --> 07:44.780
immer am Beispiel gemacht haben und nicht so aufoptimiert.

07:45.240 --> 07:50.880
Trotzdem ist das genauso wichtig wie die konkreten Algorithmen und

07:50.880 --> 07:53.100
wird eben in der Klausur sicherlich auch Rollen spielen.

07:53.100 --> 07:56.980
Also man muss immer mal wieder Summenformeln auswerten, zum Beispiel,

07:57.620 --> 07:59.320
weil da irgendwo eine Schleife ist.

07:59.440 --> 08:02.900
Die ite-Iteration braucht so und so viele Schritte, dann summiert man

08:02.900 --> 08:04.380
das auf und kriegt irgendwas hin.

08:05.060 --> 08:07.960
Oder wir haben einen Teile-und-Herrscher-Algorithmus, der zu einer

08:07.960 --> 08:14.980
Rekurrenz führt, die man dann löst, indem man vollständige Induktion

08:14.980 --> 08:17.700
anwendet oder indem man das Master-Theorem anwendet.

08:17.700 --> 08:21.740
Auch das ist eine beliebte Quelle von Klausuraufgaben.

08:23.600 --> 08:26.780
Manchmal will man es auch gar nicht so genau wissen, sondern man will

08:26.780 --> 08:28.720
nur nach oben oder nach unten abschätzen.

08:29.580 --> 08:35.500
Dann kann man auch recht komplizierte Summen durch asymptotisch

08:35.500 --> 08:37.520
hinreichend genaue Formeln abschätzen.

08:37.780 --> 08:38.940
Das muss man auch lernen.

08:40.300 --> 08:45.440
Und Asymptotik, also O-Kalkül oder auch andere Sachen wie Klein, Omega

08:45.440 --> 08:45.980
etc.

08:46.960 --> 08:52.120
liefern uns die geeigneten Notationen, um diese Abschätzungen zu

08:52.120 --> 08:52.360
machen.

08:56.060 --> 09:02.720
Oder mit einfachen Modellen meine ich hier, dass wir typischerweise

09:02.720 --> 09:07.160
bei der Algorithmanalyse nicht wirklich die Maschinenbefehle zählen,

09:07.240 --> 09:09.400
die in unserem RAM-Modell verwendet würden.

09:10.320 --> 09:11.260
Wäre auch sehr schwierig.

09:11.980 --> 09:16.560
Sondern dass diese Vernachlässigung von konstanten Faktoren uns oft

09:16.560 --> 09:21.080
erlaubt, nur bestimmte Operationentypen zu zählen, wie zum Beispiel

09:21.080 --> 09:22.940
Vergleiche bei einem Sortieralgorithmus.

09:22.940 --> 09:27.580
Auch eine wichtige Technik, die Sie vielleicht auch in der Klausur

09:27.580 --> 09:31.840
brauchen können, wenn wir Sie bitten, einen bestimmten Algorithmus zu

09:31.840 --> 09:32.420
analysieren.

09:33.160 --> 09:35.920
Wir haben so Sachen wie Analyse von Mitteln uns am Rande auch

09:35.920 --> 09:36.440
angeschaut.

09:36.880 --> 09:39.300
Amortisierung zum Beispiel bei unbeschränkten Feldern.

09:39.300 --> 09:46.080
Wir haben dann randomisierte Algorithmen analysiert, mit Hilfe von

09:46.080 --> 09:51.460
Linearität des Erwartungswertes und Definition geeigneter Indikator

09:51.460 --> 09:52.660
-Zufallsvariablen.

09:53.300 --> 09:57.440
Die konkreten Wahrscheinlichkeiten, die man dann irgendwann braucht,

09:58.600 --> 10:02.940
rechnet man dann mit Hilfe der Kombinatorik, also man zählt bestimmte

10:02.940 --> 10:03.580
Ereignisse.

10:03.580 --> 10:08.540
Das war zum Beispiel bei universellen Cache-Funktionen so, oder auch

10:08.540 --> 10:10.240
die untere Schranke fürs Sortieren.

10:10.960 --> 10:15.600
Da haben wir durch Zählen von Möglichkeiten herausgefunden, wie viele

10:15.600 --> 10:19.960
Bits man mindestens braucht an Informationen und dadurch auch wie

10:19.960 --> 10:20.760
viele Vergleiche.

10:22.680 --> 10:25.520
Bei diesen Summen haben wir dann gesehen, dass man die manchmal

10:25.520 --> 10:28.320
abschätzen kann mit Hilfe von Integralen.

10:28.320 --> 10:30.600
Zum Beispiel bei harmonischen Reihen.

10:35.540 --> 10:39.620
Und wieder war es so, dass Invarianten eine wichtige Rolle gespielt

10:39.620 --> 10:39.920
haben.

10:44.080 --> 10:47.400
Weitere Techniken, die wir kennengelernt haben, die in keine dieser

10:47.400 --> 10:55.880
vier Kategorien, Algorithmen, Datenstrukturen, Algorithmen, Muster

10:55.880 --> 11:00.100
oder Analysetechniken passen, ist Algorithm Engineering.

11:01.460 --> 11:07.320
Also wie gehe ich jetzt wirklich vor, wenn ich einen praktikablen

11:07.320 --> 11:08.420
Algorithmus haben will.

11:09.420 --> 11:12.080
Insbesondere wie gehe ich mit Implementierung, Experimenten,

11:12.180 --> 11:13.480
Algorithmen, Bibliotheken um.

11:14.000 --> 11:19.600
Haben wir hier in der Vorlesung nur am Rande gemacht und wird in der

11:19.600 --> 11:21.060
Klausur so keine Rolle spielen.

11:21.360 --> 11:23.840
Aber ich finde es wichtig, dass Sie da was von gehört haben.

11:23.840 --> 11:29.800
Achso Moment, wir könnten vielleicht so kleine Fragen stellen, was

11:29.800 --> 11:38.000
sind wichtige Eigenschaften von Algorithmen im Algorithm Engineering

11:38.000 --> 11:39.600
im Gegensatz zu Algorithm Theorie.

11:40.320 --> 11:43.620
Aber ich denke für dieses Jahr können wir das ausschließen.

11:45.240 --> 11:48.980
Parameter Tuning, das gehört eigentlich in das Algorithm Engineering

11:48.980 --> 11:49.600
mit rein.

11:52.000 --> 11:59.060
Oft kann man Algorithmen, da hat man Stellschrauben, zum Beispiel die

11:59.060 --> 12:02.420
Größe des Basisfalls beim Quicksort Algorithmus.

12:02.420 --> 12:05.580
Und da muss man sich halt überlegen, wie man diese Stellschrauben so

12:05.580 --> 12:08.340
bestimmt, dass man am Ende die beste Leistung kriegt.

12:08.940 --> 12:12.080
Das sollte Ihnen auch bewusst sein, dass Algorithmen nicht

12:12.080 --> 12:19.120
festgeformte Programme sind, wo alle Parameter genau so sein müssen,

12:19.280 --> 12:21.580
sondern man muss sich überlegen, wie diese Parameter überhaupt

12:21.580 --> 12:22.560
auszusehen haben.

12:23.900 --> 12:27.420
Dann habe ich hier in der Vorlesung High-Level Pseudocode verwendet.

12:28.600 --> 12:32.580
Ob Ihnen meine konkrete Form von Pseudocode jetzt so gut gefällt oder

12:32.580 --> 12:34.120
nicht, ist hier glaube ich zweitrangig.

12:34.860 --> 12:38.680
Aber ich halte es für wichtig, dass Sie gesehen haben, wie man durch

12:38.680 --> 12:42.340
Integration von Sachen, die eher sind wie einer Programmiersprache und

12:42.340 --> 12:46.500
mathematischer Notation, auch komplexe Algorithmen sehr kurz

12:46.500 --> 12:47.400
darstellen kann.

12:47.400 --> 12:50.580
Und ich glaube, das ist wichtig für den Algorithmenentwurf und

12:50.580 --> 12:54.560
vielleicht auch für die Dokumentation von Algorithmen, sodass ich

12:54.560 --> 12:57.840
denke, dass das auch in der Praxis eine wichtige Sache ist, dass man

12:57.840 --> 12:58.800
weiß, wie sowas geht.

13:00.700 --> 13:05.520
Die Lower Level sind so Sachen wie Dummy-Elemente in Listen oder

13:05.520 --> 13:10.260
Sentinels, also Wächter-Elemente, die es einem erlauben, Programme zu

13:10.260 --> 13:11.000
vereinfachen.

13:11.660 --> 13:16.940
Und wir haben ein bisschen geredet über Speicherverwaltung, dass man

13:16.940 --> 13:21.840
da halt aufpassen muss, ob das ein Leistungsengpass werden kann.

13:23.000 --> 13:26.980
Das waren jetzt die Zusammenfassungsfolien.

13:27.060 --> 13:27.940
Gibt es dazu Fragen?

13:33.210 --> 13:36.910
Sonst beginnt jetzt der Fast-Forwand.

13:42.190 --> 13:46.130
500 Folien in 45 Minuten.

13:46.890 --> 13:47.330
Los!

13:49.750 --> 13:56.010
Organisatorisches ist nur wichtig, dass die Abschlusskursur am 28.07.

13:56.210 --> 13:56.270
ist.

13:56.350 --> 13:57.190
Ich hoffe, das stimmt noch.

13:58.850 --> 14:02.150
Materialien, Bücher, was ein Algorithmus ist, wissen Sie auch.

14:03.090 --> 14:06.030
Ich werde Sie, glaube ich, nicht nach den Lebensdaten von Herrn Al

14:06.030 --> 14:07.290
-Khawarizmi fragen.

14:10.690 --> 14:13.650
Auch das hier ist alles nicht so wichtig für die Klausur.

14:13.950 --> 14:16.170
Da gehe ich von aus, dass Sie das sowieso jetzt wissen.

14:30.200 --> 14:32.320
Was ist eine Datenstruktur?

14:34.820 --> 14:35.300
Werkzeugkasten.

14:36.420 --> 14:39.200
Das ist alles noch Motivation, warum wir das machen.

14:39.320 --> 14:41.140
Ich hoffe, das ist Ihnen sowieso jetzt klar.

14:42.220 --> 14:45.340
Inhaltsübersicht mache ich jetzt nicht nochmal.

14:48.220 --> 14:53.560
Das erste, was wir dann gesehen haben, war dieser Appetithappen zur

14:53.560 --> 14:55.080
Langzahlmultiplikation.

14:56.040 --> 14:59.260
Da könnte man natürlich Aufgaben stellen, wie hier ist ein anderer

14:59.260 --> 15:02.920
Additionsalgorithmus, analysieren Sie den oder sowas.

15:02.920 --> 15:11.060
Was eigentlich ein noch beliebteres Thema ist, ist vielleicht andere

15:11.060 --> 15:16.160
Multiplikationsalgorithmen, also insbesondere dieser rekursive

15:16.160 --> 15:17.800
Multiplikationsalgorithmus.

15:17.900 --> 15:22.800
Da könnte man vielleicht andere Dividing-Conquer-Algorithmen für

15:22.800 --> 15:26.040
irgendwelche algebraischen Fragestellungen vorstellen und Sie bitten,

15:26.160 --> 15:27.060
die zu analysieren.

15:27.820 --> 15:35.060
Da gibt es also verschiedenste Verallgemeinerungen und dann natürlich

15:35.060 --> 15:36.860
Analyse mit den Master-Theorien.

15:37.100 --> 15:40.320
Auch andere Dinge können da immer wieder auftreten.

15:40.420 --> 15:44.660
Beliebtes Thema, und zwar sowohl für komplexere Aufgaben, wo Sie sich

15:44.660 --> 15:47.760
selber etwas überlegen müssen, als auch für Kurzaufgaben.

15:51.200 --> 15:53.860
Algorithmen und Entwurfsmuster, darüber habe ich gerade gesprochen.

15:55.400 --> 15:59.500
Harald Tuber-Offmann war dann ein Beispiel für den nicht-trivialen

15:59.500 --> 16:01.040
Teile -und-Herrscher-Algorithmus.

16:01.600 --> 16:05.180
Wie gesagt, Algorithm-Engineering wird jetzt keine so große Rolle

16:05.180 --> 16:07.480
spielen für die Klausur.

16:09.300 --> 16:13.080
Asymptotik sicherlich schon, also es gibt traditionell bei uns immer

16:13.080 --> 16:18.860
ein paar kleine OKK-Kühlaufgaben und als Teilproblem einer komplexeren

16:18.860 --> 16:20.860
Aufgabe kann das auch immer vorkommen.

16:23.580 --> 16:28.300
Meistens reden wir über O, aber denken Sie daran, dass es auch Omega

16:28.300 --> 16:34.480
für untere Schranken, Theta für bis auf konstanten Faktor genau und

16:34.480 --> 16:37.760
Klein -O und Klein-Omega für weniger und mehr gibt.

16:41.700 --> 16:43.440
Rechenregeln für O-Kalkül, ja.

16:45.020 --> 16:53.340
Wir sind da relativ wenig strikt darin, welche Rechenregeln Sie jetzt

16:53.340 --> 16:56.720
verwenden und wie genau Sie argumentieren, aber wenn Sie jetzt einen

16:56.720 --> 17:01.640
Beweis führen für O-Kalkül-Sachen, dann sollten da schon irgendwelche

17:01.640 --> 17:03.860
vernünftigen Schritte gemacht werden.

17:03.860 --> 17:06.900
Also die Sachen, wo man dann keine Punkte kriegt, sind halt

17:06.900 --> 17:10.840
normalerweise die, wo dann einfach irgendwo so ein Sprung gemacht wird

17:10.840 --> 17:13.100
oder ein falscher Schluss gezogen wird oder sowas.

17:14.640 --> 17:18.020
Gucken Sie sich am besten Musterlösungen an, um ein Gefühl dafür zu

17:18.020 --> 17:18.280
kriegen.

17:19.920 --> 17:23.260
Maschinenmodell, das ist auch eher so ein Wissensding, da gibt es so

17:23.260 --> 17:28.500
diese Details, warum ausgerechnet logarithmisch viele Bits, sowas

17:28.500 --> 17:29.680
sollte man vielleicht wissen.

17:29.680 --> 17:31.720
Was ist überhaupt das Konzept?

17:32.720 --> 17:35.920
Besondere von Neumann-Modell, uniformer Speicher.

17:37.880 --> 17:40.840
Wir werden jetzt nicht groß anfangen, Sie irgendwelche

17:40.840 --> 17:44.380
Maschinenprogramme schreiben zu lassen, aber man sollte grob wissen,

17:44.500 --> 17:51.580
was dieses Maschinenmodell ist und wie die Übersetzung funktioniert in

17:51.580 --> 17:53.400
unsere Pseudocodes.

17:53.840 --> 17:57.480
Aber eben alles sehr informell, wir werden da keine Detailarbeit

17:57.480 --> 17:58.360
verlangen.

18:01.320 --> 18:06.880
Also insbesondere sollte man halt irgendwie verstanden haben, dass wir

18:06.880 --> 18:11.340
hier einen relativ großen Schritt gehen von einem abstrakten

18:11.340 --> 18:14.380
Maschinenmodell, das vereinfachende Annahmen macht, wie zum Beispiel

18:14.380 --> 18:20.200
jeder Maschinenbefehl ist, einen Takt zu Pseudocodes und realistischen

18:20.200 --> 18:22.400
Maschinen, auf denen das ausgeführt werden soll.

18:22.780 --> 18:26.160
Dann gehen uns an verschiedensten Stellen konstante Faktoren verloren,

18:26.160 --> 18:29.940
die wir aber alle hinter dem U-Kalkül verstecken und die erlauben es

18:29.940 --> 18:34.140
uns, auf verschiedenen Abstraktionsebenen gleichzeitig zu agieren.

18:34.660 --> 18:39.160
Das ist ganz wichtig, allerdings für Klausuraufgaben weiß ich jetzt

18:39.160 --> 18:42.900
nicht so genau, wie man da jetzt konkrete Aufgaben rausmachen würde.

18:47.020 --> 18:50.220
Caching, Parallelverarbeitung ist auch Blick über den Tellerrand,

18:50.360 --> 18:53.580
brauchen Sie jetzt für die Klausur nicht im Detail.

18:54.540 --> 18:57.720
Allerdings wenn es so ist, wenn wir nach Vor- und Nachteilen

18:57.720 --> 19:01.920
bestimmter Algorithmen oder Datenstrukturen fragen, dann ist es

19:01.920 --> 19:05.380
durchaus ein zulässiges Argument zu sagen, das ist cache-effizienter

19:05.380 --> 19:08.460
oder so, wenn ich in der Vorlesung darüber geredet habe.

19:12.940 --> 19:15.400
Pseudocode, also Sie müssen jetzt nicht, wenn Sie Antworten machen,

19:15.540 --> 19:19.560
meinen Pseudocode verwenden oder sowas, aber vielleicht ein Wort dazu,

19:19.740 --> 19:26.000
wie man Programme oder Algorithmen in einer Klausur beschreibt.

19:29.460 --> 19:32.780
Was ich überhaupt nicht gern sehe ist, also Sie dürfen ja diese

19:32.780 --> 19:34.320
Schmierzettel verwenden.

19:35.600 --> 19:38.820
Und das hat sich auch bewährt und ich denke, das nimmt auch einiges an

19:38.820 --> 19:40.600
auswendig Lerndruck von Ihnen.

19:40.600 --> 19:47.240
Der Nachteil für uns ist, es gibt dann immer wieder Spezialisten, die

19:47.240 --> 19:51.740
merken, ah, hier ist eine Aufgabe, ich habe keine Ahnung, was die

19:51.740 --> 19:54.080
Lösung sein könnte, aber jetzt machen Sie Patternmatching.

19:54.300 --> 19:57.420
Okay, irgendein Begriff in der Aufgabenstellung, taucht da irgendwas

19:57.420 --> 20:00.940
in meiner Formelsammlung auf und das, was am besten passt, da fange

20:00.940 --> 20:02.760
ich an und schreibe die Formelsammlung ab.

20:04.280 --> 20:06.900
Oder paraphrasiere irgendwas, versuche dann Begriffe aus der

20:06.900 --> 20:10.560
Aufgabenstellung einzuflechten, aber es ist offensichtlicher Unsinn.

20:12.840 --> 20:17.400
Unsere Bewertungsschemata sind daraufhin getunt, dass sowas sowieso

20:17.400 --> 20:18.600
null Punkte gibt.

20:20.280 --> 20:23.620
Da müssten Sie großes Glück haben, wenn da tatsächlich nochmal ein

20:23.620 --> 20:24.960
Punkt kommt auf die Weise.

20:25.800 --> 20:28.640
Deshalb wäre meine Bitte, versuchen Sie das gar nicht erst, es macht

20:28.640 --> 20:30.720
nur allen Seiten Verdruss und Arbeit.

20:34.020 --> 20:40.060
Genau, jetzt etwas konstruktiver, wie schreibe ich das auf?

20:40.180 --> 20:44.080
Das kommt eben sehr darauf an, also seien Sie ruhig high-level, also

20:44.080 --> 20:45.920
mathematische Notation ist okay.

20:48.180 --> 20:52.760
Was man auch oft sieht, ist L-lange Programme, wo dann Sachen

20:52.760 --> 20:56.820
inkrementiert werden und Begins und Ends und dann verlieren Sie sich

20:56.820 --> 20:58.200
selber in Ihrer Schreiberei.

20:58.200 --> 21:02.940
Machen Sie das so kurz und prägnant wie möglich.

21:03.100 --> 21:06.740
Das Wichtige bei der Bewertung ist nicht, wie viele Zeilen Sie

21:06.740 --> 21:11.000
schreiben, sondern wie viele ergebnisrelevante Sachen da drin stehen.

21:11.780 --> 21:15.980
Und es kann durchaus auch mal sein, dass man ganz ohne Pseudokoden

21:15.980 --> 21:19.140
einen Algorithmus beschreiben kann, wenn Sie in klaren Worten sagen

21:19.140 --> 21:20.380
können, was gemacht wird.

21:21.000 --> 21:23.540
Also insbesondere gibt es immer mal wieder so Algorithmen

21:23.540 --> 21:28.960
-Entwurfsaufgaben, wo die Musterlösung dann im Wesentlichen so ist,

21:29.040 --> 21:34.840
sortiere nach dem und dem Schlüssel, dann laufe durch die Elemente und

21:34.840 --> 21:37.440
zähle folgende Ereignisse.

21:37.740 --> 21:39.620
Und das Ergebnis ist dann das und das.

21:40.580 --> 21:44.240
Dann können Sie einfach in Worten, in ein paar Zeilen beschreiben, was

21:44.240 --> 21:47.500
gemacht wird, weil das sind sowieso Standardtechniken, die wir

21:47.500 --> 21:50.800
tausendmal in Übungen gesehen haben oder sowas und dafür gibt es auch

21:50.800 --> 21:51.740
volle Punktzahlen.

21:51.740 --> 21:54.620
Solange Sie klar spezifizieren, was Sie tun.

21:55.080 --> 21:58.360
Wenn Sie dann zum Beispiel vergessen, zu spezifizieren, wonach wird

21:58.360 --> 22:02.360
sortiert oder wenn Sie vergessen, bestimmte Randfälle oder Vor- und

22:02.360 --> 22:06.660
Nachverarbeitungen zu besprechen, dann kann es halt schon Punktabzug

22:06.660 --> 22:06.900
geben.

22:08.760 --> 22:12.780
Oder wenn es dazu Fragen gibt, antworte ich auch gerne.

22:15.180 --> 22:19.800
Gut, dann hatten wir so Beispiele für Schleifeninvarianten gemacht.

22:19.800 --> 22:22.440
Da kann es auch durchaus sein, dass wir dann sowas machen.

22:22.500 --> 22:24.960
Hier ist ein Programm, geben Sie eine Schleifeninvariante an.

22:25.060 --> 22:28.160
Oder hier ist eine Schleifeninvariante für das Programm, argumentieren

22:28.160 --> 22:29.500
Sie, warum die erfüllt ist.

22:35.420 --> 22:39.080
Potenzberechnung war allgemein nett, weil man irgendwie was von linear

22:39.080 --> 22:42.060
auf logarithmisch runtergekriegt hat durch einen netten Trick, das

22:42.060 --> 22:44.640
kann vielleicht auch beim Algorithmenentwurf in anderen Fällen

22:44.640 --> 22:46.560
vorkommen.

22:46.560 --> 22:52.360
Dann hier dieses Programmanalyse, wie mache ich aus Pseudocode, lower

22:52.360 --> 22:55.960
-level -code, wie analysiere ich das, wenn wir in der Form nicht

22:55.960 --> 22:56.220
bringen.

22:56.300 --> 23:03.120
Das war eher Rechtfertigung dessen, wie man halt von Maschinenbefehlen

23:03.120 --> 23:04.300
zu Pseudocode kommt.

23:06.200 --> 23:09.780
Master-Theorem ist ganz wichtig, auch die Beweise von den einzelnen

23:09.780 --> 23:13.760
Fällen, weil es da durchaus sein kann, dass Sie das anwenden müssen

23:13.760 --> 23:16.740
oder auch Beweise erklären, nachvollziehen sollen.

23:17.820 --> 23:22.200
Es kann auch mal sein, dass wir Rekurrenzen analysieren, die nicht auf

23:22.200 --> 23:26.820
das Schema passen, die aber irgendwie so ähnlich funktionieren, wo

23:26.820 --> 23:29.400
einem das Master-Theorem vielleicht schon eine Idee gibt, was

23:29.400 --> 23:30.180
rauskommt.

23:30.900 --> 23:34.060
Und dann ist es vielleicht das sicherere, nicht zu sagen, hier Master

23:34.060 --> 23:38.480
-Theorem, wenn das nicht anwendbar ist, sondern dann raten Sie

23:38.480 --> 23:41.500
einfach, was es sein könnte und beweisen das durch vollständige

23:41.500 --> 23:42.060
Induktion.

23:42.400 --> 23:43.980
Das ist ja auch nicht wirklich schwierig.

23:44.930 --> 23:46.360
Wenn man richtig geraten hat.

23:49.620 --> 23:52.880
Also das sind jetzt die einzelnen Fälle des Master-Theorems, die

23:52.880 --> 23:54.080
sollte man drauf haben.

23:56.740 --> 24:02.200
Analyse mittelrandomisierter Algorithmen machen wir jetzt nicht so

24:02.200 --> 24:07.260
viel, also insbesondere wird es in der Klausur keine Aufgaben geben,

24:07.400 --> 24:10.960
wo Sie selber probabilistische Beweise machen müssen.

24:10.960 --> 24:15.260
Also es kann durchaus sein, dass Sie randomisierte Algorithmen

24:15.260 --> 24:19.060
entwerfen sollen, insbesondere vielleicht auch verwenden.

24:19.860 --> 24:23.820
Eine Standardentwurfsaufgabe benutzt zum Beispiel irgendwo

24:23.820 --> 24:24.600
Hashtabellen.

24:25.180 --> 24:28.800
Und dann haben Sie sozusagen als Unterprogramm eine randomisierte

24:28.800 --> 24:33.040
Datenstruktur und dann argumentiert man über erwartete Laufzeit und

24:33.040 --> 24:33.400
sowas.

24:33.860 --> 24:35.440
Lassen Sie sich davon nicht abschrecken.

24:35.440 --> 24:39.320
Sie brauchen jedenfalls keine probabilistischen Argumente selber

24:39.320 --> 24:40.980
führen in dieser Klausur.

24:41.780 --> 24:44.220
Ja, mit Graphen haben wir alles mögliche gemacht.

24:46.840 --> 24:50.280
Bäume treten halt auch immer wieder auf, auch in Aufgabenstellungen

24:50.280 --> 24:50.640
und so.

24:50.820 --> 24:54.040
Und dann sollte man sich klar sein, dass es da verschiedene Varianten

24:54.040 --> 24:58.560
von gibt und wenn man da was missversteht, kann das leicht dazu

24:58.560 --> 25:01.800
führen, dass man dann eine Aufgabe in den falschen Hals kriegt.

25:01.880 --> 25:02.980
Da sollten Sie auch aufpassen.

25:05.620 --> 25:08.220
Graphenalgorithmen haben wir eine ganze Reihe kennengelernt,

25:08.660 --> 25:12.960
insbesondere auch mehrere Möglichkeiten, um Decks zu erkennen oder

25:12.960 --> 25:14.860
topologische Sortierungen zu berechnen.

25:15.520 --> 25:19.280
Schöne Aufgabe wäre zum Beispiel, hier aus diesem IsDeck-Algorithmus

25:19.280 --> 25:22.220
einen topologischen Sortieralgorithmus zu bauen oder irgendeine

25:22.220 --> 25:23.240
Variante davon.

25:24.880 --> 25:27.300
p und np brauchen wir nicht in der Klausur.

25:29.340 --> 25:33.320
Gut, Folgen und Felder, ja, verkettete Listen.

25:33.320 --> 25:36.400
Da könnten zum Beispiel Aufgaben sein, machen Sie eine zusätzliche

25:36.400 --> 25:37.520
Operation da rein.

25:37.880 --> 25:40.280
Oder hier ist eine Variante von verketteten Listen.

25:41.320 --> 25:46.660
Oder hier kombinieren Sie mal eine Entwurfsaufgabe, wo man geschickt

25:46.660 --> 25:50.540
verkettete Listen mit Hashtabellen oder Sortieren verbinden muss.

25:51.580 --> 25:56.360
Das war zum Beispiel das Ziel von dieser LRU-Caching-Aufgabe, dass man

25:56.360 --> 25:59.280
mal sieht, wie verschiedene Aspekte, verkettete Listen und

25:59.280 --> 26:03.480
Hashtabellen in dem Fall, zusammenwirken, um insgesamt zu einem

26:03.480 --> 26:05.220
effizienten Algorithmus zu kommen.

26:06.100 --> 26:09.620
Und sowas könnte in einer etwas schwierigeren Entwurfsaufgabe auch mal

26:09.620 --> 26:10.780
eine Frage sein.

26:12.300 --> 26:15.620
Ja, dieser Dummy-Header war ein Beispiel für so ein Sentinel-Element.

26:18.460 --> 26:20.500
Sollte man auch verstehen, wie das geht.

26:21.100 --> 26:24.920
Die Splice-Operation war sozusagen unsere Basis-Operation, aus der wir

26:24.920 --> 26:26.720
dann alles andere aufgebaut haben.

26:27.280 --> 26:29.660
Entsprechend ist es da auch wichtig, die zu verstehen.

26:30.820 --> 26:34.400
Speicherverwaltung ist eher so etwas Qualitatives, wo mal so kurze

26:34.400 --> 26:36.020
Verständnisfragen kommen.

26:37.400 --> 26:39.580
Verschiedene Operationen auf Listen.

26:41.480 --> 26:44.540
Einfach verkettete Listen als Variante.

26:47.120 --> 26:48.660
Felder, unbeschränkte Felder.

26:48.800 --> 26:50.860
Amortisierung haben wir alles gemacht.

26:52.040 --> 26:53.900
Fragen zu stellen.

26:55.060 --> 26:58.620
Haben wir sogar mal eine konkrete amortisierte Analyse gemacht.

26:58.620 --> 27:01.880
Das könnte ich mir auch vorstellen, dass das eine Klausuraufgabe sein

27:01.880 --> 27:05.560
könnte, wo man dann irgendeine Variante einer Datenstruktur, die

27:05.560 --> 27:07.760
amortisierte Analyse zeigen soll.

27:10.900 --> 27:17.720
Oder Beständnisaufgaben zu, was ist überhaupt das Konzept, könnte

27:17.720 --> 27:18.760
natürlich vorkommen.

27:18.760 --> 27:27.500
Dann hatten wir folgende Datenstrukturen gesehen, die einen sehr

27:27.500 --> 27:32.800
beschränkten Funktionsumfang haben, wie Stapel, FIFOs und DAGs.

27:33.800 --> 27:37.940
Und die sind auch immer eine dankbare Quelle von Aufgaben, wo man dann

27:37.940 --> 27:41.680
sagen kann, implementieren Sie diese Datenstruktur mit dieser

27:41.680 --> 27:45.360
Repräsentation, diskutieren Sie, warum das gut oder schlecht ist,

27:45.360 --> 27:48.500
bohren Sie das in der und der Richtung auf oder sowas.

27:51.280 --> 27:55.440
Also Stapel gehen zum Beispiel, ist fast egal, wie Sie das

27:55.440 --> 27:58.340
implementieren, aber da muss man die Vor- und Nachteile verstehen.

27:59.440 --> 28:03.940
Bei FIFO-Warteschlangen bot sich dieses zyklische Array besonders an.

28:05.260 --> 28:07.500
Und da kann man auch gucken, ob man damit noch irgendwas anderes

28:07.500 --> 28:08.220
machen kann.

28:09.440 --> 28:12.280
DAGs waren nochmal eine Verallgemeinerung, wo man sich überlegen

28:12.280 --> 28:13.740
müsste, wie man das machen kann.

28:15.780 --> 28:20.480
Vergleich von Feldern und Listen sind dankbare Quellen für

28:20.480 --> 28:21.860
Kurzaufgaben.

28:22.900 --> 28:26.300
Oder gerade diese Tabelle, da kann man also hunderte von Fragen

28:26.300 --> 28:29.760
herausdestillieren, die man immer wieder variieren kann in jeder

28:29.760 --> 28:30.280
Klausur.

28:30.640 --> 28:34.260
Üben Sie am besten die alten Klausuren und dann ist Ihnen das, glaube

28:34.260 --> 28:36.520
ich, vertraut, wie diese Fragen aussehen.

28:38.780 --> 28:41.660
Laufzeitmessungen haben wir immer mal wieder eingestreut, aber da

28:41.660 --> 28:43.780
werde ich jetzt keine Fragen in der Klausur zustellen.

28:46.240 --> 28:46.640
Ja,

28:49.920 --> 28:52.680
Hashing, man sollte wissen, was eine Hashtabelle ist.

28:54.540 --> 28:57.460
Anwendungen, wie gesagt, da gibt es ganz viele Entwurfsaufgaben, wo

28:57.460 --> 28:58.460
man die dann braucht.

28:58.820 --> 29:01.620
Da sollte man vielleicht auch selber üben oder Aufgaben aus

29:01.620 --> 29:03.260
Lehrbüchern sich mal anschauen.

29:06.280 --> 29:09.900
Dieses Konzept von Kollisionen spielt immer wieder eine Rolle, da kann

29:09.900 --> 29:11.320
man auch Aufgaben zustellen.

29:11.680 --> 29:14.800
Und dann hatten wir uns zwei konkrete Implementierungen angeguckt.

29:14.800 --> 29:18.560
Hashing mit verketteten Listen und Hashing mit linearem Probing.

29:19.600 --> 29:23.140
Und da kann man dann auch Rechenaufgaben zustellen.

29:23.300 --> 29:27.240
Zum Beispiel, zeigen Sie, wie die Datenstruktur aufsieht nach

29:27.240 --> 29:30.180
folgender Operationenfolge, ist eine beliebte Aufgabe.

29:32.060 --> 29:36.860
Wie gesagt, die Analyse hatten wir hier nur gemacht für das Hashing

29:36.860 --> 29:40.500
mit Verketten, aber ich werde halt in der Klausur diese

29:40.500 --> 29:42.700
probabilistischen Sachen selber nicht machen.

29:44.100 --> 29:47.480
Aber möglicherweise könnten wir dann so Fragestellungen machen wie,

29:47.980 --> 29:51.700
hier ist eine universelle Klasse von Hash-Funktionen,

29:55.080 --> 29:58.880
wenden Sie die mal an, zeigen Sie, wie dann eine Hash-Tabelle

29:58.880 --> 29:59.340
aussieht.

29:59.900 --> 30:02.740
Oder zeigen Sie, dass die nicht universell ist, indem Sie einfach ein

30:02.740 --> 30:05.960
Gegenbeispiel angeben, wo dann ganz viele Kollisionen passieren.

30:06.540 --> 30:08.960
Das wäre ja kein probabilistischer Beweis.

30:15.020 --> 30:19.520
Was man auch wissen sollte, ist diese standarduniversellen Familien,

30:19.620 --> 30:24.000
die wir kennengelernt haben, insbesondere diese Skalarproduktfamilie,

30:24.120 --> 30:27.540
aber vielleicht auch die, die in den Übungen noch dran waren oder hier

30:27.540 --> 30:29.200
auf dieser Folie erwähnt wurden.

30:31.760 --> 30:36.180
Hashing mit linearer Suche, da war das dann so, das Einfügen und

30:36.180 --> 30:40.640
Suchen war eigentlich trivial, und das Entfernen, da war dann ein

30:40.640 --> 30:43.660
kleiner Trick mit drin, wo man auch wieder Invarianten braucht.

30:45.100 --> 30:47.920
Und deshalb tritt dieses Entfernen dann auch öfter mal in den

30:47.920 --> 30:49.060
Rechenaufgaben auf.

30:53.420 --> 30:57.140
Und dann, wie gesagt, Vergleich der Vor- und Nachteile dieser beiden

30:57.140 --> 30:57.980
Datenstrukturen.

30:58.000 --> 31:02.460
Sollte man wissen, wie der aussieht, weil man da einmal Kurzaufgaben

31:02.460 --> 31:03.340
zu stellen kann.

31:08.360 --> 31:10.060
Perfektes Hashing haben wir nicht gemacht.

31:13.500 --> 31:16.540
Und dieser Blick über den Tellerrand-Sachen sind jetzt auch nicht so

31:16.540 --> 31:16.780
wichtig.

31:16.900 --> 31:18.720
Sortieren haben wir ziemlich viel gemacht.

31:20.460 --> 31:24.880
Anwendungen auch immer wieder, es gibt Entwurfsaufgaben ganz oft, wo

31:24.880 --> 31:27.460
man sortieren muss, um etwas schnell hinzukriegen.

31:28.040 --> 31:32.120
Manchmal steht dann sogar so, sorgen Sie dafür, dass das in Linearzeit

31:32.120 --> 31:35.760
geht, und wenn Sie dann sortieren wollen, müssen Sie halt Radixort

31:35.760 --> 31:39.760
nehmen oder müssen Sie argumentieren, wie lang die Schlüssel werden

31:39.760 --> 31:40.520
oder so was.

31:45.380 --> 31:49.300
Einfache Suchalgorithmen sortieren durch Einfügen.

31:50.100 --> 31:55.440
Ein Gegenpol davon war sortieren durch Auswahl, wo man genauso schöne

31:55.440 --> 31:56.540
Sachen machen kann.

32:00.540 --> 32:04.120
Analyse, das wäre jetzt ein schönes Beispiel für sowas, wo man einfach

32:04.120 --> 32:07.880
mal so eine Schleifenstruktur aufdröselt und dann auch die konstanten

32:07.880 --> 32:12.160
Faktoren vielleicht mit abdeckt, um bestimmt auch Aufgaben zu stellen.

32:13.100 --> 32:16.020
Sortieren durch Mischen ist ein wichtiger Algorithmus, weil er

32:16.020 --> 32:19.060
deterministisch ist, zum DNO von N log N Zeit läuft.

32:20.700 --> 32:25.300
Und deshalb immer, wenn Sie nach einem asymptotisch effizienten

32:25.300 --> 32:29.060
Algorithmus irgendwo gefragt sind, am besten Mergesort nehmen, dann

32:29.060 --> 32:33.560
fallen Sie nicht in irgendwelche Fallen mit Quicksort oder sowas.

32:38.380 --> 32:41.580
Mit Mischen kann man wahrscheinlich auch andere Dinge machen als nur

32:41.580 --> 32:42.080
sortieren.

32:42.720 --> 32:46.360
Da kann man also auch wieder Aufgaben rausbauen.

32:46.880 --> 32:50.520
Untere Schranken haben wir kennengelernt, dass man, solange man nur

32:50.520 --> 32:56.520
vergleichsbasiert argumentiert, Omega N log N Vergleiche braucht.

32:57.360 --> 33:00.940
Da gab es auch schon Klausuraufgaben, die da verschiedene Aspekte

33:00.940 --> 33:02.580
davon abgefragt haben.

33:06.700 --> 33:09.640
Und das ist ein kombinatorischer Beweis, kein probabilistischer,

33:10.360 --> 33:12.280
deshalb kann sowas auch mal vorkommen.

33:13.040 --> 33:16.100
Hier war dann auch ein Beispiel, wo man mit diesen integralen

33:16.100 --> 33:17.500
Abschätzungen gemacht hat.

33:18.440 --> 33:19.700
Könnte auch mal vorkommen.

33:22.260 --> 33:25.940
Ja, dann Quicksort war vor allem wichtig, weil er in place oder fast

33:25.940 --> 33:27.220
in place arbeitet.

33:27.960 --> 33:30.340
Wir hatten dann eine Analyse gemacht für einen ganz einfachen

33:30.340 --> 33:35.060
Algorithmus und den dann schrittweise...

33:36.340 --> 33:40.540
Genau, also die Analyse war dann für einen einfachen Algorithmus mit

33:40.540 --> 33:43.220
probabilistischen Anteilen, wird also so nicht abgefragt.

33:44.740 --> 33:46.500
Und dann haben wir...

33:47.780 --> 33:50.660
Ja, das ist ein Algorithmen-Engineering-Aspekt, der dran kommen

33:50.660 --> 33:50.960
könnte.

33:51.040 --> 33:52.460
Wie mache ich das jetzt in place?

33:53.060 --> 33:54.620
Wie mache ich die Invarianten dafür?

33:54.780 --> 33:56.760
Da kann man bestimmt auch Aufgaben rausmachen.

33:56.760 --> 34:00.580
Oder eben Rechenaufgaben für Quicksort, könnte sicherlich passieren.

34:02.540 --> 34:06.260
Wichtig bei Quicksort ist, dass der Worst-Case ziemlich schlecht ist.

34:06.360 --> 34:09.100
Da sollte man wissen, warum, was man dagegen tut.

34:12.440 --> 34:14.120
Messungen sind jetzt nicht so wichtig.

34:14.860 --> 34:18.600
Und dann gab es halt eine Variante des Quicksort-Algorithmus, der ein

34:18.600 --> 34:23.180
ganz anderes Problem löst, nämlich Auswahl, also Selektion.

34:24.460 --> 34:27.340
Und der war dann halt erwartet lineare Zeit.

34:27.580 --> 34:31.060
Da könnte man halt auch Aufgaben zu stellen, irgendwie Variante.

34:31.900 --> 34:37.480
Jetzt haben wir nicht mehr einen Rang vorgegeben, sondern mehrere.

34:37.740 --> 34:38.500
Wie gehe ich damit um?

34:38.720 --> 34:40.180
Alles mögliche kann man da machen.

34:47.960 --> 34:49.820
Das hier war Blick über den Tellerrand.

34:49.960 --> 34:52.860
Das ist jetzt in dem Sinne nicht so wichtig.

34:55.800 --> 34:59.280
Ganzteiliges Sortieren, wie gesagt, als Möglichkeit, die untere

34:59.280 --> 35:00.140
Schranke zu durchbrechen.

35:03.520 --> 35:05.920
Und im einfachsten Fall den Bucket Sort.

35:06.520 --> 35:10.080
Da kann man vielleicht auch Aufgabenstellungen finden, wo es auf den

35:10.080 --> 35:13.560
ersten Blick gar nicht nach Sortieren aussieht, aber wo dieses

35:13.560 --> 35:15.620
Klassifizier -Pattern auftritt.

35:15.620 --> 35:19.100
Zum Beispiel war es bei uns so, dass dieser Bucket Sort-Algorithmus

35:19.100 --> 35:25.020
fast unverändert dann wieder als Algorithmus zur Umwandlung von

35:25.020 --> 35:29.620
Kantenlisten in ein Adjacenz-Array auftauchte.

35:30.060 --> 35:32.680
Und dass das eigentlich ein Sortierproblem ist, ist da gar nicht so

35:32.680 --> 35:33.320
offensichtlich.

35:34.260 --> 35:36.420
Sowas könnte auch irgendwie auftreten.

35:40.440 --> 35:43.460
Addict Sort habe ich schon gesagt, dass das eine Rolle spielt.

35:44.180 --> 35:48.020
Ich werde Sie nicht darum bitten, einen O-von-N-Wurzel-Log-Log-N

35:48.020 --> 35:50.000
-Algorithmus zu entwerfen.

35:52.740 --> 35:55.060
Und dann sollte man vielleicht ein paar Vor- und Nachteile

35:56.640 --> 35:58.920
vergleichsbasierter und ganzteiliger Algorithmen kennen.

36:02.500 --> 36:05.580
Externes Sortieren haben wir nur als Blick über den Tellerrand

36:05.580 --> 36:05.960
gemacht.

36:06.600 --> 36:11.040
Das spielt dann eher in Algorithmen 2 und der Algorithm-Engineering

36:11.040 --> 36:11.960
-Vorlesung eine Rolle.

36:17.900 --> 36:20.400
Prioritätslisten haben wir kennengelernt als Werkzeug.

36:20.500 --> 36:23.780
Das kann man auch wieder für viele Entwurfsaufgaben als Blackbox

36:23.780 --> 36:24.540
einsetzen.

36:26.100 --> 36:29.780
Aber eben auch konkret eine Implementierung durch binäre Heaps.

36:30.420 --> 36:36.780
Und außerdem liefert diese Repräsentation von binärer Heaps durch ein

36:36.780 --> 36:41.640
Array auch ein Entwurfsmuster, wie kann ich einen vollständigen Baum

36:41.640 --> 36:44.020
durch ein Array repräsentieren.

36:44.020 --> 36:46.920
Und da könnte man eben auch andere Anwendungen der Klausur sich

36:46.920 --> 36:49.060
angucken oder verallgemeinerung.

36:51.360 --> 36:55.800
Das war diese implizite Baumrepräsentation, wo dann statt Zeigern

36:55.800 --> 37:00.480
explizit abzuspeichern, man das Navigieren im Baum dann durch

37:00.480 --> 37:01.660
Arithmetik machen kann.

37:02.300 --> 37:06.800
Also der Vorgänger war durch Division durch 2, der linke Nachfolger

37:06.800 --> 37:11.220
durch Multiplikation mit 2 zu erreichen, der rechte Nachfolger

37:11.220 --> 37:13.920
Multiplikation mit 2 und 1 addieren.

37:17.580 --> 37:19.960
Und dann haben wir daraus binäre Heaps gebaut.

37:20.560 --> 37:23.260
Da kann man natürlich auch schöne Rechenaufgaben machen.

37:26.760 --> 37:31.600
Konstruktion ging in Linearzeit, obwohl naiv das O von n log n wäre,

37:32.320 --> 37:36.620
wenn man n Elemente mal logarithmische Zeit fürs Einfügen rechnen

37:36.620 --> 37:36.920
würde.

37:39.220 --> 37:41.940
Da gab es dann auch wieder so einen Summentrick.

37:42.740 --> 37:44.940
Könnte auch sein, dass der mal woanders nochmal auftaucht.

37:46.060 --> 37:48.040
Wäre auch nicht schlecht, wenn man den versteht.

37:49.420 --> 37:56.980
Und Heapsort ist halt theoretisch auch spannend, weil es ein echter In

37:56.980 --> 37:58.200
-Place -Algorithmus ist.

37:58.800 --> 38:01.520
Also Quicksort ist ja so, der braucht logarithmisch zusätzlichen

38:01.520 --> 38:01.960
Platz.

38:02.480 --> 38:07.040
Im strikten Algorithmen-Theorie-Sinn ist das noch nicht In-Place, aber

38:07.040 --> 38:11.740
O von 1 zusätzlicher Platz braucht Heapsort, wenn man das nicht

38:11.740 --> 38:13.100
rekursiv implementiert.

38:14.160 --> 38:15.980
Und das geht halt in dem Fall tatsächlich.

38:19.510 --> 38:23.330
Wieder so eine Tabelle mit schönen Vergleichen, aus denen man dann so

38:23.330 --> 38:25.370
Kurzaufgaben bauen kann.

38:27.610 --> 38:30.950
Adressierbare Prioritätslisten hatten wir kennengelernt.

38:32.030 --> 38:36.550
Die Verbindung haben wir hinterher gebraucht, bei dem Janik-Prim

38:36.550 --> 38:38.950
-Algorithmus und beim Dijkstra-Algorithmus.

38:40.310 --> 38:44.530
Und wir haben nur ganz kurz eine Implementierung kennengelernt, dass

38:44.530 --> 38:49.810
man nämlich die normalen Binary Heaps aufbohrt sozusagen, indem man

38:49.810 --> 38:54.850
die Elemente separat speichert von den Array-Einträgen.

38:55.490 --> 38:58.730
Und das war wichtig, weil man so etwas wie referenzielle Integrität

38:58.730 --> 38:59.130
braucht.

38:59.130 --> 39:04.850
Also man muss irgendwie Verweiser auf Elemente haben, die sich auch

39:04.850 --> 39:09.370
nicht ändern dürfen, wenn irgendwie eine Sift-Up- oder Sift-Down

39:09.370 --> 39:13.810
-Operation die Position der Elemente im Heap verschieben.

39:14.710 --> 39:17.650
Weil zum Beispiel das Decrease-Key, dann muss man sich auf ein

39:17.650 --> 39:23.150
bestimmtes Element per Verweis, das muss man referenzieren können.

39:23.150 --> 39:28.830
Das haben wir nicht im Detail gemacht, aber wie die Operationen dann

39:28.830 --> 39:32.770
umzusetzen wären, halte ich für naheliegend und könnte man dann auch

39:32.770 --> 39:34.870
mal abfragen in irgendeinem Kontext.

39:39.110 --> 39:42.990
Wir haben da einen Blick über den Tellerrand gemacht, Fibonacci-Heaps.

39:43.470 --> 39:47.430
Was Sie vielleicht wissen sollten, ist, dass Binary Heaps nicht in

39:47.430 --> 39:50.230
allen Operationen optimal sind, dass es dadurch, dass es auch

39:50.230 --> 39:54.110
schneller gehen kann, insbesondere Decrease-Key, geht in amortisiert

39:54.110 --> 39:58.050
konstanter Zeit und daraus folgen dann auch bessere Laufzeitschranken

39:58.050 --> 40:02.170
für Dijkstra's Algorithmus und den Janek-Priem-Algorithmus.

40:02.290 --> 40:05.750
Und sowas könnte in irgendeiner Frage mal indirekt auftauchen.

40:06.170 --> 40:08.870
Aber wir werden nicht fragen, wie geht denn das, weil das ist dann ein

40:08.870 --> 40:09.950
Algorithmen -Zweistoff.

40:14.410 --> 40:16.150
Was gibt es da noch zu sagen?

40:16.890 --> 40:23.290
Wie gesagt, Sum-Tricks, implizites Layout von Binärbäumen, Heapsort,

40:23.790 --> 40:26.770
kann man auch jenseits von Prioritätslisten benutzen.

40:27.710 --> 40:31.910
Dann war die nächst kompliziertere Datenstruktur, sortierte Folgen.

40:33.270 --> 40:37.350
Da haben wir erstmal das abstrakte Konzept kennengelernt, zum Beispiel

40:37.350 --> 40:41.010
doppeltverkettete Liste plus Navigationsdatenstruktur.

40:41.730 --> 40:46.290
Dann einen einfachen Warmwerdefall, sortiertes Array mit binärer

40:46.290 --> 40:46.770
Suche.

40:47.710 --> 40:54.270
Der nächste Schritt waren dann Anwendungen binärer Suchbäume, wo wir

40:54.270 --> 40:58.670
uns dann aber bedeckt gehalten haben, wie man da Worst-Case-Effizienz

40:58.670 --> 41:02.290
erreicht, wenn man beliebige Einfüge und Löschoperationen hat.

41:03.090 --> 41:04.770
Das Problem war,

41:09.310 --> 41:13.610
dass das beliebig unbalanciert werden kann.

41:15.790 --> 41:19.670
Da Rechenaufgaben zu binären Suchbäumen könnte man sicherlich auch

41:19.670 --> 41:20.010
machen.

41:20.910 --> 41:25.690
Oder hier diese Schleifeninvarianten, könnte man irgendwelche Beweise

41:25.690 --> 41:26.310
dazu machen.

41:27.270 --> 41:32.510
Was wir dann gemacht haben, ist, statt uns darum zu kümmern, wie man

41:32.510 --> 41:39.210
binäre Bäume balanciert, haben wir dann lieber die gerade flexibler

41:39.210 --> 41:40.990
gemacht und dann AB-Bäume eingeführt.

41:41.070 --> 41:43.710
Und da sollte man dann auch wissen, was sind die Schleifeninvarianten,

41:44.630 --> 41:49.350
was sind die Grundideen für die Operationen von Rechenaufgaben zu

41:49.350 --> 41:51.670
machen, Verständnisfragen stellen.

41:53.990 --> 41:57.830
Aber wir werden Sie jetzt nicht bitten, detaillierte Pseudocodes für

41:57.830 --> 41:59.750
Remove anzugeben oder sowas.

42:07.970 --> 42:11.370
Um Verständnis zu fragen, was ist die Komplexität, was sind die

42:11.370 --> 42:17.110
Bedingungen, warum braucht man diese Bedingungen, B größer gleich 2A

42:17.110 --> 42:19.770
minus 1, könnte man Aufgaben stellen.

42:19.770 --> 42:20.610
Ja,

42:23.770 --> 42:26.250
wir haben dann gesehen, dass man weitere Operationen da auch noch

42:26.250 --> 42:28.750
unterstützen kann, ohne da ins Detail zu gehen.

42:30.130 --> 42:34.730
Da könnte man einfache weitere Operationen durchaus auch Aufgaben zu

42:34.730 --> 42:35.010
bauen.

42:35.610 --> 42:40.210
Allerdings nichts Kompliziertes, wie Concaten Split zum Beispiel.

42:42.310 --> 42:45.870
Das haben wir nicht gemacht, da gibt es auch keine Aufgaben zu.

42:46.570 --> 42:50.510
7.4, 7.5 haben wir was gemacht.

42:50.650 --> 42:54.930
Augmentierte Suchbäume haben wir uns ein paar Beispiele angeguckt.

42:55.290 --> 42:58.830
Insbesondere mit diesem Abspeichern von Teilbäumengrößen kann man

42:58.830 --> 43:02.770
schöne Dinge machen, wie Ränge bestimmen oder zählen, wie viele

43:02.770 --> 43:06.850
Objekte in einer Teilfolge drin sind.

43:07.250 --> 43:08.910
Aber auch Rechenaufgaben zu machen.

43:12.400 --> 43:15.560
Es gibt auch andere Datenstrukturen für sortierte Folgen.

43:15.560 --> 43:19.520
Da könnte man, wenn man sich einfacher anguckt, auch Aufgaben zu

43:19.520 --> 43:19.780
bauen.

43:19.960 --> 43:21.820
Aber das erklären wir dann im Detail.

43:23.440 --> 43:25.960
Die Messungen sind eher Blick über den Tellerrand.

43:28.500 --> 43:30.960
Ja, nebenbei haben Sie da eine ganze Menge gelernt.

43:31.500 --> 43:33.640
Dann ging es um Graph-Repräsentation.

43:34.360 --> 43:38.580
Da haben wir dann normalerweise gerichtete Graphen repräsentiert, weil

43:38.580 --> 43:43.420
ungerichtete man auch als B-Directed Graphs repräsentieren kann.

43:44.380 --> 43:47.680
Und dann geht es bei der Repräsentation, bei der Auswahl einer

43:47.680 --> 43:50.180
Repräsentation, darum, welche Operationen man braucht.

43:51.280 --> 43:54.700
Und was man ganz oft braucht, ist zumindest die Navigation.

43:54.860 --> 43:58.040
Gegeben ein Knoten findet die ausgehenden Kanten.

44:00.500 --> 44:05.820
Und das wird sehr gut durch Adjacenzfelder unterstützt.

44:06.440 --> 44:10.420
Noch einfachere Repräsentationen wären Kantenfolgen-Repräsentationen.

44:11.380 --> 44:14.860
Es gab aber eben nur wenige Verfahren, die damit umgehen können.

44:15.040 --> 44:16.620
Zum Beispiel Kruskalls Algorithmus.

44:17.640 --> 44:19.680
Und da könnte man natürlich auch Aufgaben machen.

44:20.820 --> 44:21.960
Hier ist ein Algorithmus.

44:22.540 --> 44:24.480
Welche Repräsentation brauchen Sie?

44:24.600 --> 44:26.860
Geht es auch mit der Kantenfolgen-Repräsentation?

44:27.440 --> 44:28.360
Wenn ja, wie?

44:28.940 --> 44:30.420
Das könnte man durchaus machen.

44:31.780 --> 44:36.500
Oder eben Adjacenzfelder bauen, Rechenaufgaben dazu machen, Varianten

44:36.500 --> 44:38.560
dieser Datenstrukturen uns angucken.

44:38.560 --> 44:40.380
Alle möglichen Sachen.

44:44.800 --> 44:47.140
Weitere Operationen habe ich vorgestellt.

44:47.520 --> 44:49.880
Da könnte man auch schöne kleine Aufgaben daraus machen.

44:49.940 --> 44:54.220
Was müssen Sie tun, um Knoteninformationen einzubauen?

44:54.460 --> 44:56.240
In ein Adjacenz-Array zum Beispiel.

44:59.860 --> 45:06.240
Aber ich werde sicherlich nicht fragen, wie wird der folgende 42

45:06.240 --> 45:08.920
-Knoten -Graf in Leder repräsentiert.

45:09.160 --> 45:11.300
Das war eher ein Blick über den Tellerrand.

45:20.100 --> 45:24.240
Adjacenzmatrizen waren wichtig wegen der Verbindung zur Algebra.

45:25.400 --> 45:27.340
Intervallgrafen habe ich schon von gesprochen.

45:32.380 --> 45:36.380
Graftraversierungen, da kann man viele Anwendungen von Breitensuche

45:36.380 --> 45:36.820
machen.

45:38.500 --> 45:42.580
Oder diese Kantenklassifikationen in Baum, rückwärts, quer und

45:42.580 --> 45:43.480
vorwärtskanten.

45:43.480 --> 45:47.920
Beweise dazu, dass bestimmte Kanten in bestimmten Graffamilien bei

45:47.920 --> 45:51.800
bestimmten Graftraversierungsalgorithmen nicht auftreten können.

45:52.020 --> 45:56.380
Zum Beispiel war es bei BFS ja so, dass es keine Vorwärtskanten geben

45:56.380 --> 45:56.820
kann.

46:14.060 --> 46:16.420
Die Frage war, wozu braucht man überhaupt diese

46:16.420 --> 46:17.660
Kantenklassifikationen.

46:18.720 --> 46:21.760
Ich könnte jetzt sagen, Wissenschaftler versuchen, alles zu

46:21.760 --> 46:22.540
kategorisieren.

46:22.540 --> 46:32.560
Aber der Trick ist wahrscheinlich, wenn sie Algorithmen entwerfen, die

46:32.560 --> 46:36.840
irgendwas mit Spannbäumen zu tun haben oder irgendwas mit Breitensuche

46:37.180 --> 46:40.960
oder irgendwas mit Tiefenzuche, dann müssen sie sich ja überlegen,

46:41.300 --> 46:45.580
während dieser Traversierung, wie behandeln sie diese verschiedenen

46:45.580 --> 46:46.600
Arten von Kanten.

46:46.600 --> 46:50.580
Und dann ist das sozusagen eine Checkliste.

46:50.660 --> 46:54.980
Okay, weiß ich, was ich zu tun habe, wenn ich so eine Kante finde.

46:56.740 --> 47:02.360
Und deshalb vielleicht auch die Aufgaben zur Berechnung dieser

47:02.360 --> 47:05.660
Kategorien, dass man dann vielleicht den Algorithmen benutzt, diese

47:05.660 --> 47:10.100
Eigenschaft, um irgendwelche Schlüsse zu ziehen, muss ich da

47:10.100 --> 47:11.600
weitersuchen oder sowas.

47:13.360 --> 47:14.540
Weitere Fragen?

47:17.720 --> 47:21.520
Repräsentation des Baumes durch diese Pärenzahlzeiger, das hatten wir

47:21.520 --> 47:24.820
dann auch beim Dijkstra-Algorithmus wiederverwendet.

47:25.260 --> 47:31.740
Breitensuche kann man mit zwei Stapeln nach FIFO implementieren oder

47:31.740 --> 47:33.580
wahrscheinlich auch viele andere Varianten.

47:33.740 --> 47:36.640
Wichtig ist halt nur, dass sie irgendwie hinkriegen, Schicht für

47:36.640 --> 47:37.860
Schicht da durchzulaufen.

47:38.440 --> 47:41.940
Und da kann man dann auch schöne Aufgaben zu stellen, Varianten davon,

47:43.980 --> 47:47.380
bestimmte Sachen ausrechnen mit Hilfe Breitensuche und so weiter.

47:49.020 --> 47:51.960
Genauso Tiefensuche, da hatten wir halt dieses Schema und damit kann

47:51.960 --> 47:53.420
man auch ganz viele Dinge tun.

47:54.620 --> 47:58.900
Rechenaufgaben kann man schöne machen, wo man dann sowas ähnliches wie

47:58.900 --> 48:05.280
hier angeben müsste oder nur Bilder dazu oder BFS-Nummerierungen

48:05.280 --> 48:07.420
ausrechnen oder Varianten davon.

48:08.420 --> 48:12.540
Ohnehin auf Bäumen kann man auch alle möglichen Nummerierungen machen

48:12.540 --> 48:15.640
und damit irgendwelche Sachen ableiten, da kann man immer Aufgaben

48:15.640 --> 48:16.460
rausstellen.

48:19.200 --> 48:25.960
Topologisches Sortieren hatten wir uns angeschaut mit Hilfe von DFS,

48:26.260 --> 48:28.520
kann ich aber auch auf anderem Wege machen, hatte ich schon darüber

48:28.520 --> 48:29.100
geredet.

48:30.680 --> 48:32.980
Starke Zusammenhangskomponenten ist ein Konzept, das man vielleicht

48:32.980 --> 48:36.180
mal verwendet, aber den detaillierten Algorithmus haben wir nicht

48:36.180 --> 48:39.660
gemacht und der wird auch so in der Klausur nicht kommen und diese

48:39.660 --> 48:43.820
weiteren DFS-basierten Linearzeitalgorithmen dann erst rechnen.

49:00.520 --> 49:02.960
Moment, haben Sie Breitensuche gesagt?

49:04.300 --> 49:07.460
Aber Traverse Tree-Edge und Traverse Non-Tree-Edge haben wir im

49:07.460 --> 49:10.140
Zusammenhang mit Tiefensuche gemacht, deshalb bin ich jetzt etwas

49:10.140 --> 49:11.240
verwirrt.

49:23.680 --> 49:26.740
Kann ich im Moment nichts zu sagen, also ich fürchte, diese Analogie

49:26.740 --> 49:29.280
kann auch mal in die Irre leiten, also ich weiß nicht genau, worauf

49:29.280 --> 49:33.040
Sie hinaus wollen und wenn ich jetzt Ja sage, dann beschweren Sie sich

49:33.040 --> 49:35.060
hinterher, dass irgendwas in der Klausur passiert.

49:36.140 --> 49:39.580
Aber ja, sicherlich, es gibt Analogien zwischen Breitensuche und

49:39.580 --> 49:43.480
Tiefensuche und die kann einem bestimmt helfen, bestimmte Aufgaben zu

49:43.480 --> 49:43.800
lösen.

49:44.440 --> 49:49.900
Aber wenn Sie in der Klausur so Verweise machen, analog wie in

49:49.900 --> 49:53.720
Vorlesungen oder so, lesen wir dann oft in Übungen, in Lösungen und

49:53.720 --> 49:57.900
wissen aber nicht genau, was Sie damit meinen und das kann dann zu

49:57.900 --> 49:59.300
Missverständnissen führen.

49:59.720 --> 50:02.460
Also lieber die Sachen so explizit wie möglich sagen.

50:03.440 --> 50:07.560
Sie haben normalerweise keinen Zeitdruck in dieser Klausur oder

50:07.560 --> 50:08.700
zumindest keinen großen.

50:13.180 --> 50:17.620
Okay, dann qualitative Vergleiche, Tiefensuche, Bestensuche.

50:19.720 --> 50:22.180
Muss jetzt langsam fertig werden.

50:22.420 --> 50:25.880
Kürzeste Wege, ja, wir haben den Dijkstra-Algorithmus kennengelernt,

50:25.920 --> 50:26.960
der ist natürlich wichtig.

50:29.860 --> 50:33.800
Wir haben gesehen, dass der nicht immer funktioniert.

50:34.360 --> 50:38.780
Man muss schon wissen, was passiert mit negativen Kosten, was passiert

50:38.780 --> 50:42.080
mit negativen Kreisen, wie gehe ich damit um, was bedeutet das für

50:42.080 --> 50:43.500
Entfernungen von Knoten.

50:44.060 --> 50:45.960
Bellman-Ford-Algorithmus ist wichtig.

50:47.380 --> 50:50.540
Azyklische Graphen sind besonders einfach zu handhaben, das ist auch

50:50.540 --> 50:51.100
nützlich.

50:51.780 --> 50:54.120
All -to-all ist klar, wie das geht, hoffe ich.

50:55.160 --> 50:58.600
Ja, dann Distanzen, Zielknoten, das war eher Blick über den

50:58.600 --> 50:59.760
Tellerrand, das machen wir nicht.

51:00.820 --> 51:03.860
Dann dieses ganze Transient Node Routing Zeug ist deshalb nicht so

51:03.860 --> 51:04.440
wichtig.

51:05.980 --> 51:10.320
MSTs sind dann wieder wichtig, insbesondere die Schnitteigenschaft und

51:10.320 --> 51:11.900
die Kreiseigenschaft sind wichtig.

51:11.900 --> 51:16.500
Der Janik-Priem-Algorithmus, der Kruskal-Algorithmus, Union-Find

51:16.500 --> 51:19.960
-Datenstruktur kann auch von unabhängigem Interesse sein, zum Beispiel

51:19.960 --> 51:22.260
für andere algorithmische Fragestellungen.

51:25.000 --> 51:30.140
Dann aber die Details von Analyse von Fahrtkompressionen machen wir

51:30.140 --> 51:30.800
natürlich nicht.

51:33.340 --> 51:33.900
Bitte?

51:34.760 --> 51:36.380
Wir haben Zeit, super.

51:37.920 --> 51:38.900
Laufzeitmessungen, okay.

51:41.100 --> 51:43.980
Generische Optimierungsansätze, Sie sollten sicherlich wissen, was das

51:43.980 --> 51:46.980
Rucksackproblem ist, was die verschiedenen Lösungsansätze waren.

51:47.440 --> 51:50.120
Vielleicht fragen wir Sie nach weiteren Lösungsansätzen dafür.

51:51.100 --> 51:54.280
Sie wollten allgemein diese Frameworks kennen, was ist Maximierung,

51:54.400 --> 51:56.900
Minimierung, lokale Suche und so weiter.

51:58.680 --> 52:02.460
Vielleicht fragen wir Sie, wie gesagt, wie wende ich lineare

52:02.460 --> 52:06.260
Programmierung, ganzzeitige lineare Programmierung an, um bestimmte

52:06.260 --> 52:08.060
Problemstellungen zu modellieren.

52:15.670 --> 52:20.970
Gridi-Algorithmen, Timo hat immer gesagt, die funktionieren nie.

52:21.470 --> 52:23.730
Trotzdem könnte es sein, dass wir Sie dann bitten, nicht

52:23.730 --> 52:27.570
funktionierende Gridi-Algorithmen zu entwerfen, die dann vielleicht

52:27.570 --> 52:28.450
doch funktionieren.

52:32.690 --> 52:37.310
Dynamische Programmierung, Sachen sind aber genauso nett, kommt auch

52:37.310 --> 52:38.390
immer wieder gerne vor.

52:39.750 --> 52:43.570
Sollte nicht vergessen, die Lösungsrekonstruktion mit anzugeben, außer

52:43.570 --> 52:45.010
wenn es ausgeschlossen ist.

52:47.010 --> 52:50.470
Gegenbeispiele sind auch nett, die Teilproblemeigenschaft,

52:50.730 --> 52:53.970
Austauschbarkeit, kann man schöne Fangfragen stellen.

52:54.950 --> 52:59.810
Systematische Suche könnte man auch irgendwas machen, wobei das schon

52:59.810 --> 53:03.290
etwas komplexere Algorithmen sind, die vielleicht eher am Rande

53:03.290 --> 53:03.890
drankommen.

53:04.770 --> 53:07.310
Aber man sollte zumindest wissen, was so ein Branch-and-Bound-Schema

53:07.310 --> 53:09.490
ist, was das lokale Sucheschema ist.

53:10.210 --> 53:14.450
Inwieweit Hill-Climbing eine spezielle Variante von lokaler Suche ist,

53:14.970 --> 53:17.170
warum man damit keine Optima immer findet.

53:19.170 --> 53:21.810
Evolutionäre Algorithmen wahrscheinlich eher allgemeine

53:21.810 --> 53:25.550
Verständnisfragen und keine detaillierten Aufgabenstellungen.

53:26.850 --> 53:29.870
Okay, und jetzt kommt der Überblick über so und so viele hundert

53:29.870 --> 53:31.210
Folien Übung.

53:33.210 --> 53:34.170
Willkommen zur Übung.

53:34.690 --> 53:39.230
Bevor wir anfangen mit der Zusammenfassung, habe ich noch ein Thema

53:39.230 --> 53:42.090
vorbereitet, ein letztes Thema für euch.

53:42.090 --> 53:44.730
Und zwar Ganzzeigelineare Programmierung.

53:45.650 --> 53:48.630
Das wurde in der Vorlesung ganz kurz angerissen, aber weil ich das

53:48.630 --> 53:51.310
ganz interessant finde, habe ich noch ein Beispiel mitgebracht.

53:52.970 --> 53:56.950
Bevor es dann nochmal den Klausuraufruf gibt und die Übersicht der

53:56.950 --> 53:57.210
Übungen.

53:57.890 --> 54:01.690
Wir haben letzte Übung, hat Timo lineare Programmierung eingeführt,

54:01.810 --> 54:02.650
ein Beispiel dazu gehabt.

54:03.370 --> 54:08.350
Da ging es darum, dass man meistens versucht, das Problem in so einer

54:08.350 --> 54:09.290
Form hier darzustellen.

54:09.650 --> 54:12.130
Man maximiert eben eine Zielfunktion unter Nebenbedingungen.

54:12.370 --> 54:14.130
Nebenbedingungen kann man in so einer Markenschreibweise darstellen.

54:16.170 --> 54:19.070
Und was wir jetzt machen wollen, ist Ganzzeigelineare Programmierung.

54:20.130 --> 54:24.630
Das ist eigentlich das Gleiche, nur dass eben unser Lösungsraum jetzt

54:24.630 --> 54:26.150
eben ganze Zahlen sind.

54:28.610 --> 54:32.390
Das hilft einem häufig in der Praxis, weil viele Forderungen sind,

54:32.510 --> 54:34.170
dass die Lösungsmenge in Ganzzeig ist.

54:35.270 --> 54:39.270
Oft hat man noch eine weitere Einschränkung, dass eben nur 0 und 1

54:39.270 --> 54:39.690
erlaubt sind.

54:40.070 --> 54:43.190
Dann werden halt die Lösungsvektoren so eine Indikatorvariable.

54:43.350 --> 54:46.450
0, wenn es irgendwie nicht dabei ist oder 1, wenn es dabei ist.

54:47.470 --> 54:51.550
Egal, ob es jetzt 0, 1 ist oder ein Z ist, es ist immer NP schwer.

54:51.550 --> 54:55.710
Das Problem daran ist, es ist halt nicht einfach lösbar.

54:56.610 --> 55:00.330
Jetzt ein Beispiel, wie man sowas einsetzt.

55:01.370 --> 55:04.230
Habe ich geklaut aus dem Skript für OR.

55:04.510 --> 55:08.770
Also wenn irgendwer von euch OR hört noch, dann werdet ihr das gleich

55:08.770 --> 55:09.270
auch nochmal sehen.

55:09.830 --> 55:12.270
Das ist jetzt auch wieder ein Beispiel aus der Wirtschaft.

55:13.070 --> 55:14.990
Wie letzte Woche eben auch in der Süßwarenfabrik.

55:15.490 --> 55:18.190
Bei der Süßwarenfabrik war es dann so, da hat man Süßigkeiten gehabt

55:18.190 --> 55:22.210
und man konnte sich dann überlegen, will 0,8 der Produktion in

55:22.210 --> 55:24.410
Süßigkeiten stecken oder 0,7 soll Schokolade sein.

55:25.150 --> 55:26.890
Jetzt haben wir aber was anderes, das sind Projekte.

55:27.910 --> 55:31.950
Projekte P1 bis P5 und die Frage ist halt, die können realisiert

55:31.950 --> 55:32.230
werden.

55:32.870 --> 55:34.690
Da sieht man schon sofort das Problem, ein Projekt kann entweder

55:34.690 --> 55:35.930
realisiert werden oder es wird nicht realisiert.

55:36.570 --> 55:39.210
Und es wird nicht zu 0,8 oder zu 70% realisiert, es wird entweder

55:39.210 --> 55:40.310
realisiert oder nicht realisiert.

55:40.910 --> 55:45.430
Und dann Projekte und die kosten was und die kosten halt in

55:45.430 --> 55:46.490
verschiedenen Jahren verschieden viel.

55:47.210 --> 55:49.950
Und man hat halt pro Jahr ein bestimmtes Kapital, da sieht man schon

55:49.950 --> 55:54.350
sofort die ersten Nebenbedingungen, dass die Kosten im Jahr halt

55:54.350 --> 55:55.710
kleinkeitig und bezahlend sein sollen.

55:56.230 --> 55:58.310
Und man hat auch einen Gewinn für die verschiedenen Projekte.

55:59.910 --> 56:04.370
Und eben den Gewinn wollen wir halt maximieren, also die Summe über

56:04.370 --> 56:05.790
die realisierten Projekte.

56:06.630 --> 56:08.710
Und um es noch ein bisschen spannender zu machen, hat man noch andere

56:08.710 --> 56:09.210
Nebenbedingungen.

56:10.310 --> 56:13.070
Nämlich, dass hier bestimmte Zusammenhänge bestehen zwischen den

56:13.070 --> 56:13.870
Projekten.

56:14.010 --> 56:17.850
Also P3 und P4 kann man entweder beide machen oder keins von beiden.

56:20.210 --> 56:23.370
Zum Beispiel, weil es irgendwelche Engpässe gibt oder sowas.

56:25.850 --> 56:28.950
Ebenso bei P4 und P5 gibt es vielleicht auch eine Fabrik, die nur eins

56:28.950 --> 56:30.930
von beiden produzieren kann, also höchstens eins von den beiden.

56:32.670 --> 56:36.150
P3 baut auf P5 auf, das heißt, wenn man P5 nicht hat, kann man P3 auch

56:36.150 --> 56:36.490
nicht haben.

56:38.650 --> 56:43.430
Und hier meinetwegen ist es so, dass diese beiden Projekte total

56:43.430 --> 56:44.690
wichtig sind für das Unternehmen.

56:45.090 --> 56:46.650
Das heißt, mindestens eins von den beiden muss man machen.

56:47.870 --> 56:50.610
Genau, und das wollen wir jetzt eigentlich nicht lösen, aber zumindest

56:50.610 --> 56:51.630
mal als ILP formulieren.

56:51.730 --> 56:53.350
Das heißt, dass man diesen Schritt mal gesehen hat, wie man von einem

56:53.350 --> 56:55.370
Problem, von einem ILP kommt.

56:55.370 --> 56:57.290
Und das mache ich jetzt auf dem Papier.

57:16.900 --> 57:22.480
Und zwar, was wir jetzt als erstes machen, die Überlegung ist halt,

57:22.840 --> 57:26.540
wir haben fünf Projekte und ich habe gesagt, man kann entweder

57:26.540 --> 57:27.440
einführen oder nicht einführen.

57:27.440 --> 57:29.580
Das heißt, realisieren oder nicht realisieren.

57:29.660 --> 57:33.640
Das heißt, was wir jetzt einführen, sind Indikator-Variablen.

57:34.100 --> 57:37.080
Also für jedes Projekt führe ich jetzt ein XI ein.

57:42.420 --> 57:51.360
XI ist gleich 1, wenn eben das Projekt PI realisiert wird

57:55.420 --> 57:58.820
und 0 sonst.

58:03.730 --> 58:08.550
Also I natürlich dann 1 bis 5.

58:13.010 --> 58:14.610
Wir wollen ja irgendwie auf die Form kommen.

58:16.210 --> 58:19.270
Wie war das?

58:19.550 --> 58:20.410
Ich gucke nochmal kurz nach.

58:20.510 --> 58:22.510
Das war glaube ich CTX.

58:23.710 --> 58:27.010
Also maximiere C transponiert X.

58:27.890 --> 58:30.370
Unter Nebenbedingungen, da schreibt man meistens ST hin, das heißt

58:30.370 --> 58:31.170
Subject To.

58:33.730 --> 58:36.690
AX gleich B.

58:41.590 --> 58:43.730
Unser X ist eben gerade diese XI.

58:44.050 --> 58:48.750
Also X ist gleich X1, X5.

58:53.690 --> 58:55.170
Transponiert, wir brauchen einen Spaltenvektor.

58:57.550 --> 58:58.330
Fangen wir an.

58:58.830 --> 59:02.290
Also wir wollen maximieren unsere Zielfunktion.

59:02.910 --> 59:07.030
Und das ist eben die Summe über die Gewinne der Projekte, die

59:07.030 --> 59:07.710
realisiert werden.

59:08.730 --> 59:11.210
Und man kann sich jetzt gerade überlegen, man hat diese Indikator

59:11.210 --> 59:12.210
-Variablen 1 und 0.

59:12.630 --> 59:16.510
Das heißt, wir können das ganz einfach so hinschreiben.

59:18.070 --> 59:22.290
Ich schreibe jetzt hier mal die Variablen hin als Spaltenüberschrift.

59:24.830 --> 59:29.490
Und was wir maximieren wollen, ist eben diese Zielfunktion hier.

59:30.510 --> 59:36.550
20X1 plus 40X2 plus 20X3 plus 15X4 plus 30X5.

59:39.710 --> 59:40.630
Unter den Nebenbedingungen.

59:42.010 --> 59:45.230
Die ersten Nebenbedingungen haben wir eben schon gesagt, das sind eben

59:45.230 --> 59:47.790
die Kapitale, die wir pro Jahr zur Verfügung haben.

59:48.470 --> 59:55.890
Das heißt, im ersten Jahr haben wir halt nur 25 Kapital, irgendeine

59:55.890 --> 59:57.330
Einheit könnt ihr euch jetzt überlegen, zur Verfügung.

59:58.810 --> 01:00:00.210
Und wie viel geben wir aus?

01:00:00.410 --> 01:00:03.330
Na ja, wenn wir X1 realisieren, geben wir 5 aus.

01:00:03.890 --> 01:00:06.330
Wenn wir X2 realisieren, geben wir 4 aus.

01:00:06.790 --> 01:00:09.690
Und 3, 7, 8.

01:00:09.850 --> 01:00:14.950
Ja, gelesen wieder, 5X1 plus 4X2 plus 3X3 plus 7X4 plus 8X5, das kann

01:00:14.950 --> 01:00:15.830
ja gleich 25 sein.

01:00:16.310 --> 01:00:19.150
Eben, wenn es 0 ist, zählt es nicht dazu und wenn es 1 ist, zählt es

01:00:19.150 --> 01:00:20.310
dazu und insgesamt haben wir nur 25.

01:00:21.290 --> 01:00:23.350
Das kann man jetzt für die anderen, das schreibe ich mal hin, das ist

01:00:23.350 --> 01:00:25.370
das erste Jahr, das Kapital.

01:00:26.030 --> 01:00:28.050
Das kann man jetzt für das zweite Jahr und das dritte Jahr auch

01:00:28.050 --> 01:00:28.370
machen.

01:00:32.450 --> 01:00:34.850
Das schreibe ich jetzt, glaube ich, nicht hin, nicht komplett hin.

01:00:36.530 --> 01:00:39.310
Aber was hier hinkommt, ist klar, das sind eben die Spalten über die

01:00:39.310 --> 01:00:39.550
Jahre.

01:00:41.390 --> 01:00:43.370
Jetzt aber zu den wirklich interessanten Nebenbedingungen, das sind

01:00:43.370 --> 01:00:44.050
nämlich die hier unten.

01:00:46.170 --> 01:00:50.650
Das Spannende ist halt, dass man, hier steht irgendwie so etwas wie

01:00:50.650 --> 01:00:53.870
auslagenlogische Formeln und man kann eben auslagenlogische Formeln

01:00:53.870 --> 01:00:58.930
interpretieren oder übersetzen als Ungleichung mit 0,1

01:00:58.930 --> 01:00:59.150
Indikatorvariablen.

01:00:59.910 --> 01:01:00.590
Und das wollen wir jetzt machen.

01:01:01.370 --> 01:01:06.530
Hier steht dann quasi P3 und P4 nur zusammen oder gar nicht.

01:01:06.530 --> 01:01:11.570
Das heißt im Prinzip, P3, jetzt interpretiere ich mal dieses P3 als

01:01:11.570 --> 01:01:14.370
auslagenlogische Variable.

01:01:15.630 --> 01:01:21.090
P3 genau dann, wenn P4, also entweder sind beide 0 oder beide 1.

01:01:23.930 --> 01:01:28.510
So, das gilt, das schreibe ich mir hier genau dann hin, um das zu

01:01:28.510 --> 01:01:32.670
unterscheiden, eben x3 gleich x4 ist.

01:01:34.410 --> 01:01:37.810
Und dann haben wir hier das als Gleich- und Ungleich-Nahgestellte.

01:01:37.830 --> 01:01:39.370
Das bringt uns aber noch nicht viel, wir wollen es ja irgendwie auf

01:01:39.370 --> 01:01:41.050
diese Form a x kleiner gleich b bringen.

01:01:42.150 --> 01:01:47.250
Also fangen wir um, dann steht hier x3 minus x4 ist gleich 0.

01:01:49.030 --> 01:01:51.670
Aber auch das bringt uns nichts, wir wollen ja auf kleiner gleich b

01:01:51.670 --> 01:01:51.950
kommen.

01:01:52.550 --> 01:01:53.530
Das ist ja die Form, die wir haben wollen.

01:01:54.370 --> 01:01:58.990
Das geht aber, indem wir sagen, das ist genau dann, wenn der Fall x3

01:01:58.990 --> 01:02:03.550
minus x4 kleiner gleich 0 und x4

01:02:06.740 --> 01:02:14.560
minus x3 kleiner gleich 0.

01:02:16.600 --> 01:02:21.820
Das führen wir einfach hier rum, wir haben hier 0 und 0, einmal 1 und

01:02:21.820 --> 01:02:27.120
minus 1 bei x3 und 4 und einmal minus 1 und 1.

01:02:28.440 --> 01:02:29.240
So, das ist die erste Bedingung.

01:02:30.480 --> 01:02:35.040
Zweite Bedingung ist, p4 und p5 von beiden höchstens 1.

01:02:37.200 --> 01:02:40.620
Wie man da dran geht, also entweder, da gibt es bestimmte Tabellen,

01:02:41.160 --> 01:02:45.720
wahrscheinlich ein OR macht das mit Tabellen und irgendwelchen, wie

01:02:45.720 --> 01:02:46.380
wir das gerne machen.

01:02:46.780 --> 01:02:51.400
Aber wir überlegen einfach, wie das gehen könnte, p4 und p5 höchstens

01:02:51.400 --> 01:02:51.840
1.

01:02:52.300 --> 01:02:56.080
Das heißt, wenn ich beide zusammenzähle, beide Indikativariablen,

01:02:56.420 --> 01:02:57.580
dürfen die eben nicht 2 sein.

01:02:58.260 --> 01:03:00.220
Und das sagt auch schon, was wir haben wollen.

01:03:02.980 --> 01:03:09.560
x4 plus x5 kleiner gleich 1.

01:03:10.220 --> 01:03:14.660
Also x4 plus x5 2 ist nicht erlaubt, aber 1 ist erlaubt.

01:03:15.300 --> 01:03:19.040
Das heißt, was hier stehen muss, ist eben das hier.

01:03:19.620 --> 01:03:21.420
Also x4 plus x5 kleiner gleich 1.

01:03:22.320 --> 01:03:24.520
Dann hier p3 baut auf p5 auf.

01:03:25.120 --> 01:03:28.600
Aussagenlogisch bedeutet das, p3 impliziert p5.

01:03:29.020 --> 01:03:31.460
Das heißt, wenn wir p3 haben, müssen wir p5 auch haben.

01:03:31.800 --> 01:03:33.420
Wenn wir p3 nicht haben, ist p5 egal.

01:03:34.700 --> 01:03:40.800
Als Ungleichung heißt es, dass x5 größer gleich sein muss als x3.

01:03:41.240 --> 01:03:45.320
Das gleiche wieder, also wenn x3 0 ist, ist x5 egal.

01:03:45.460 --> 01:03:47.600
Aber wenn x3 1 ist, muss x5 auch 1 sein.

01:03:51.420 --> 01:03:55.760
Und das formen wir wieder um, auf diese Form hier.

01:03:56.440 --> 01:04:03.660
Also 0 größer gleich 2 minus x5.

01:04:12.410 --> 01:04:15.410
Und das letzte ist von p1 und p4 mindestens 1.

01:04:16.250 --> 01:04:18.650
Also p1 oder p4 muss gelten.

01:04:19.930 --> 01:04:24.170
Das ist 1 plus x4 größer gleich 1.

01:04:26.590 --> 01:04:29.290
Beide zusammengezählt dürfen nicht 0 sein, aber 1 geht und 2 geht

01:04:29.290 --> 01:04:29.590
auch.

01:04:30.690 --> 01:04:31.810
Und das formen wir wieder um.

01:04:32.090 --> 01:04:35.030
Da steht hier um die Zählform minus 1, da steht hier minus x1.

01:04:35.570 --> 01:04:39.070
Minus x4 kleiner gleich 1, äh minus 1.

01:04:41.850 --> 01:04:45.970
Minus 1, der Spalte hier und der Spalte.

01:04:46.590 --> 01:04:47.470
So und damit sind wir fertig.

01:04:47.610 --> 01:04:52.390
Denn das hier, was wir hier gerade hingeschrieben haben, ist unsere

01:04:52.390 --> 01:04:52.890
Matrix A.

01:04:53.590 --> 01:04:56.950
Und das hier ist eben unser B.

01:04:57.950 --> 01:04:59.030
Also wenn wir diese Form hier annehmen.

01:04:59.950 --> 01:05:03.810
Und das hier ist gerade unser C.

01:05:06.710 --> 01:05:11.890
Also das ist C auf jeden Fall, aber hier steht C transponiert.

01:05:12.490 --> 01:05:13.750
Also muss hier auch genau C transponiert werden.

01:05:14.530 --> 01:05:15.850
Genau, so sind wir fertig jetzt.

01:05:16.330 --> 01:05:17.710
Das war jetzt ein Beispiel aus der Wirklichkeit.

01:05:17.710 --> 01:05:24.550
Aber es gibt auch die Möglichkeit ILPs darzustellen für andere

01:05:24.550 --> 01:05:25.950
Probleme, sondern auch für Graphenprobleme.

01:05:26.550 --> 01:05:29.250
Ganz bekannt ist da Challenging Salesman, aber da möchte ich jetzt

01:05:29.250 --> 01:05:30.130
nicht mehr drauf eingehen.

01:05:31.850 --> 01:05:32.780
Aber das kann man sich auch mal anschauen.

01:05:34.070 --> 01:05:34.710
Das war es von mir.

01:05:34.950 --> 01:05:35.710
Gut, Übung.

01:05:37.130 --> 01:05:40.750
Die Saalübung, das was wir gemacht haben, ist klausurrelevant.

01:05:41.730 --> 01:05:42.470
Ganz klar.

01:05:43.130 --> 01:05:47.630
Und in der folgenden Übersicht werde ich verschiedene Sachen

01:05:47.630 --> 01:05:48.210
ausschließen.

01:05:48.690 --> 01:05:52.450
Und nur weil etwas jetzt nicht auftaucht, heißt das nicht, dass es

01:05:52.450 --> 01:05:53.230
ausgeschlossen ist.

01:05:54.370 --> 01:05:54.550
Gut.

01:05:56.310 --> 01:05:58.550
Erste Übung, ganz lange her.

01:05:59.250 --> 01:06:00.970
Haben wir mit O-Kalkül angefangen.

01:06:01.090 --> 01:06:04.490
Habe ich euch Definitionen aufgezeigt, habe ich euch Äquivalenzen

01:06:04.490 --> 01:06:04.870
gezeigt.

01:06:05.370 --> 01:06:08.210
Und diesen kleinen Logarithmierungstrick von O-Kalkül, das ist

01:06:08.210 --> 01:06:11.070
natürlich Basisstoff, das sollte man als Informatiker drauf haben.

01:06:11.910 --> 01:06:12.630
Klar.

01:06:14.010 --> 01:06:19.990
Invarianten zur Korrektheit ist beliebtes Mittel, um bei Algorithmen

01:06:19.990 --> 01:06:21.010
die Korrektheit zu zeigen.

01:06:21.630 --> 01:06:25.130
Locker, kann auch in irgendeiner Form in der Klausur auftauchen.

01:06:25.610 --> 01:06:27.930
Rekkurrenzen lösen ist auch ein beliebtes Klausurthema.

01:06:28.670 --> 01:06:31.410
O-Kalkül, Mastertheorien, andere Lösungsmethoden.

01:06:32.290 --> 01:06:33.630
Induktion, klar.

01:06:34.410 --> 01:06:35.690
Haben wir auf dem Übungsblatt geübt.

01:06:37.910 --> 01:06:41.210
Nicht dran kommt, also Substitution ist ein ganz wichtiges

01:06:41.210 --> 01:06:41.670
Hilfsmittel.

01:06:41.870 --> 01:06:42.850
Habe ich euch vorgerechnet.

01:06:44.150 --> 01:06:47.110
Vorwärts, rückwärts kam irgendwo Log, Log N am Ende raus.

01:06:48.510 --> 01:06:50.610
Erzeugende Funktionen habe ich euch auch vorgerechnet.

01:06:50.950 --> 01:06:51.910
Das kommt nicht dran.

01:06:52.610 --> 01:06:54.090
Klar, habe ich damals schon auch gesagt.

01:06:55.270 --> 01:06:58.610
Danach kam Binärzähler, amortisierte Analyse, Kontomethode.

01:06:59.230 --> 01:07:00.750
Ja, das ist natürlich auch ein wichtiges Thema.

01:07:01.890 --> 01:07:04.690
Dann als Beispiel hatten wir die Hotlist-Datenstruktur.

01:07:04.690 --> 01:07:08.190
Das ist, finde ich, ein sehr intuitives Beispiel für Amortisierung.

01:07:08.870 --> 01:07:11.330
Natürlich werden wir nicht dieses konkrete Thema abfragen.

01:07:11.470 --> 01:07:14.070
Aber es heißt nicht, dass wir nicht eine Amortisierung irgendwo zeigen

01:07:14.070 --> 01:07:14.330
können.

01:07:15.550 --> 01:07:18.550
Also amortisierte Analyse anhand dieser Beispiele lernen.

01:07:19.010 --> 01:07:19.890
Nicht die Beispiele selbst.

01:07:21.310 --> 01:07:24.250
Wobei Binärzähler ein ganz prototypisches Beispiel ist, was auch immer

01:07:24.250 --> 01:07:24.990
wieder auftaucht.

01:07:27.930 --> 01:07:29.670
Unbounded Arrays ist unglaublich wichtig.

01:07:29.830 --> 01:07:32.450
Da gab es auch die Erweiterung mit Alpha- und Beta-Parametern.

01:07:32.690 --> 01:07:33.250
Ist auch wichtig.

01:07:35.950 --> 01:07:37.510
Dann ging es mit Hashing los.

01:07:38.450 --> 01:07:41.450
Eine ganz typische Anwendung von Hashing ist Duplikaterkennung.

01:07:43.670 --> 01:07:47.170
Kommt immer wieder gerne versteckt in Anwendungsaufgaben vor.

01:07:48.190 --> 01:07:49.190
Muss man draufhaben.

01:07:50.130 --> 01:07:51.690
Muss man auch für die Realität draufhaben.

01:07:52.790 --> 01:07:57.290
Wenn dann irgendwie der Chef herkommt und irgendeine Duplikaterkennung

01:07:57.290 --> 01:07:59.790
machen möchte oder ein Join in der Datenbank macht das mit Hashing.

01:08:00.170 --> 01:08:00.790
Genau das Gleiche.

01:08:01.630 --> 01:08:05.090
Dann haben wir verschiedene Fortsetzungen von Hashing gehabt.

01:08:05.230 --> 01:08:07.910
Nämlich die verteilte Duplikaterkennung von Sebastian.

01:08:08.310 --> 01:08:09.830
Oder der Blumenfelder auch von Sebastian.

01:08:10.110 --> 01:08:13.510
Das kommt in der Form natürlich nicht dran, weil das weit über die

01:08:13.510 --> 01:08:14.390
Vorlesung hinausging.

01:08:16.510 --> 01:08:17.910
LRU-Pager habt ihr programmiert.

01:08:17.970 --> 01:08:21.590
Das ist eine Kombination, um sehr schön die beiden Strukturen

01:08:21.590 --> 01:08:22.850
ineinander zu vernetzen.

01:08:24.210 --> 01:08:26.790
Dann hatten wir einen großen Teil über Hash-Funktionen.

01:08:28.150 --> 01:08:32.510
Da kam die Frage, können wir eine universelle Hash-Funktion annehmen?

01:08:32.790 --> 01:08:35.150
Ja, die kannst du sogar angeben, wenn du in der Übung hier warst.

01:08:38.330 --> 01:08:42.610
Ihr müsst jetzt nicht die explizite Bitmatrix-Multiplikationsmethode

01:08:42.610 --> 01:08:43.130
da kennen.

01:08:44.050 --> 01:08:45.790
Aber ja, immerhin hast du da eine.

01:08:47.710 --> 01:08:51.950
So, Hashing von Zeichenketten habe ich euch auch gezeigt.

01:08:52.070 --> 01:08:53.810
Da waren unglaublich komplizierte Formeln drin.

01:08:53.990 --> 01:08:55.850
Lernt bitte diese Formeln nicht auswendig.

01:08:55.850 --> 01:08:57.030
Aber wie es geht.

01:08:59.050 --> 01:09:01.190
Dann kam das große Sortierkapitel.

01:09:01.650 --> 01:09:04.190
Da habe ich wieder von vorn angefangen mit Selection Sort, Insertion

01:09:04.190 --> 01:09:04.450
Sort.

01:09:04.610 --> 01:09:08.430
Dann habe ich die Average Case Analyse von Insertion Sort gemacht.

01:09:08.790 --> 01:09:09.610
Die kommt nicht dran.

01:09:10.650 --> 01:09:13.450
Aber die beiden oberen Sortieren in irgendeiner Form ist ein

01:09:13.450 --> 01:09:14.930
unglaublich beliebtes Klauselthema.

01:09:18.290 --> 01:09:19.750
Dann gingen wir mit Sortieren weiter.

01:09:19.950 --> 01:09:20.970
Fünfte Übung, Merge Sort.

01:09:21.570 --> 01:09:22.670
Asymptotisch, toll.

01:09:22.670 --> 01:09:24.130
Quick Sort.

01:09:24.390 --> 01:09:27.550
Und der Sebastian hat Dual Pivot Quick Sort gezeigt.

01:09:28.070 --> 01:09:30.470
Halten wir für eine sehr interessante Erweiterung.

01:09:30.710 --> 01:09:34.090
Insgesamt diese ganzen Erweiterungen von Quick Sort sind lernenswert.

01:09:35.430 --> 01:09:39.290
Und vielleicht jetzt nicht die explizite Ausführung von Quick Sort,

01:09:39.410 --> 01:09:40.830
aber wie die Idee dahinter ist.

01:09:41.790 --> 01:09:45.090
Was man denn mit Dual Pivot oder noch mehr als zwei Pivot machen kann.

01:09:47.390 --> 01:09:51.130
Gut, nicht dran kommt, adaptives Sortieren insbesondere.

01:09:51.130 --> 01:09:53.690
Lernt bitte nicht diese eine Folie mit den unglaublich vielen

01:09:53.690 --> 01:09:55.970
Kennzahlen von adaptiver Sortierung auswendig.

01:09:56.210 --> 01:09:57.070
Die brauchen wir nicht.

01:09:58.230 --> 01:10:00.710
Ganz nett ist ein natürliches Merge Sort.

01:10:00.790 --> 01:10:02.270
Ob das wirklich dran kommt, eher nicht.

01:10:06.010 --> 01:10:10.290
Dann kam eine Rechenstunde mit perfekten Binärbäumen, wo ich euch

01:10:10.290 --> 01:10:14.630
einen perfekten Binärbaum hingemalt habe und angefangen habe da Knoten

01:10:14.630 --> 01:10:17.630
und Kanten und alles mögliche und Höhen auszurechnen insbesondere.

01:10:18.330 --> 01:10:19.830
Und eine implizite Darstellung dafür.

01:10:19.830 --> 01:10:23.130
Das ist unglaublich wichtig, diese perfekten Binärbäume, wo Andauer-

01:10:23.130 --> 01:10:24.570
und Zweierpotenzen drin vorkommen.

01:10:26.090 --> 01:10:29.730
Für die Informatik ganz Basiswissen, braucht ihr.

01:10:31.390 --> 01:10:34.590
Dann gab es verschiedene Ausprägungen von Binärbäumen, nämlich

01:10:34.590 --> 01:10:34.850
Heapsort.

01:10:38.330 --> 01:10:41.290
Die Durchrechnung von so einem Heapsort solltet ihr auch drauf haben.

01:10:43.370 --> 01:10:46.990
Dann die Erweiterung um die Adressierbarkeit, damit man auf jedes

01:10:46.990 --> 01:10:48.650
Element auch wieder drauf zugreifen kann.

01:10:48.650 --> 01:10:52.490
Könnte schöne Klausuraufgaben geben dazu.

01:10:55.350 --> 01:10:58.210
Insbesondere möchte man dann diese Invariante von diesen

01:10:58.210 --> 01:11:01.430
adressierbaren Heaps dann doch parat haben.

01:11:07.210 --> 01:11:11.030
In der Vorlesung waren die AB-Bäume dran.

01:11:11.230 --> 01:11:14.150
Wenn in der Klausur irgendwas auftaucht, dann kommen AB-Bäume dran und

01:11:14.150 --> 01:11:16.950
nicht Rot-Schwarz-Bäume, so wie versprochen auch damals schon.

01:11:16.950 --> 01:11:20.510
Aber zu wissen, dass die balanciert sind, das ist auf jeden Fall nicht

01:11:20.510 --> 01:11:20.830
falsch.

01:11:22.030 --> 01:11:24.490
Und was denn jetzt eigentlich Balance bei so einem Baum bedeutet und

01:11:24.490 --> 01:11:25.490
was alles schief gehen kann.

01:11:27.550 --> 01:11:30.910
Was ihr auch nicht wissen müsst, ist, wie viele binäre Suchbäume es

01:11:30.910 --> 01:11:35.950
gibt, aber binäre Suchbäume sind Basiswissen.

01:11:38.210 --> 01:11:41.590
Dann gab es eine interessante Stunde, wo ich angefangen habe, über die

01:11:41.590 --> 01:11:43.130
Wirklichkeit und die Vorlesung zu diskutieren.

01:11:43.690 --> 01:11:46.850
Was jetzt eigentlich die Vorlesung mit den Datenstrukturen in Java und

01:11:46.850 --> 01:11:48.010
C++ zu tun hat.

01:11:48.810 --> 01:11:51.010
Die war unglaublich wichtig, glaube ich.

01:11:52.370 --> 01:11:54.590
Vielleicht weniger für die Klausur als für den Rest des Lebens.

01:11:59.210 --> 01:12:01.590
Dann ging es los mit Graphen.

01:12:02.530 --> 01:12:05.810
Da habe ich angefangen, euch absichtlich zu verwirren mit unglaublich

01:12:05.810 --> 01:12:06.630
vielen Graftypen.

01:12:06.750 --> 01:12:09.550
Das liegt daran, dass man immer den Graftypen nimmt, den man am

01:12:09.550 --> 01:12:10.850
liebsten hat für die Anwendung.

01:12:10.850 --> 01:12:14.030
Das heißt, die verschiedenen Typen vielleicht gegeneinander wissen,

01:12:14.270 --> 01:12:15.310
dass es da viele gibt.

01:12:16.990 --> 01:12:20.870
Und nicht unbedingt müsst ihr wissen, wer was wann erfunden hat.

01:12:21.090 --> 01:12:26.490
Es ist zwar schön zu wissen, dass Euler das erfunden hat, aber wir

01:12:26.490 --> 01:12:29.250
fragen das jetzt nicht in der Klausur, wer hat da jetzt den

01:12:29.250 --> 01:12:30.570
Vierfarbensatz bewiesen zuerst.

01:12:32.870 --> 01:12:36.190
Dann verschiedene Beispiele für Graphen, dann die verschiedenen

01:12:36.190 --> 01:12:39.330
kleinen Anfangsbeweise, die ich da gemacht habe.

01:12:39.330 --> 01:12:41.450
Die brauchen Basiswissen.

01:12:45.970 --> 01:12:48.450
Dann ging es weiter mit der Breitensuche in DEX.

01:12:49.930 --> 01:12:53.190
Eine Breitensuche von DEX ist so ein Basisalgorithmus, der sich auf

01:12:53.190 --> 01:12:56.910
viele verschiedene Anwendungen anpassen lässt.

01:12:58.110 --> 01:13:00.890
Und sowas kommt dann gerne in der Klausur dran, die Anwendung.

01:13:00.990 --> 01:13:04.130
Und man muss erkennen können, dass man diesen Basisalgorithmus umbauen

01:13:04.130 --> 01:13:04.730
kann dazu.

01:13:06.410 --> 01:13:08.830
Das ist vielleicht auch ein ganz interessanter Tipp.

01:13:09.750 --> 01:13:13.410
Wenn ihr die alten Klausuren anguckt, da kommt selten die Frage,

01:13:14.850 --> 01:13:16.410
führen Sie Breitensuche durch.

01:13:16.610 --> 01:13:20.510
Sondern es kommt eher die Frage, Sie haben dieses und dieses Problem,

01:13:20.690 --> 01:13:21.210
lösen Sie das.

01:13:21.930 --> 01:13:23.870
Und dann stellt sich heraus, ja, Sie brauchen Breitensuche.

01:13:25.290 --> 01:13:27.730
So in der Art sollten die Klausuraufgaben sein.

01:13:29.390 --> 01:13:34.450
Okay, dann kam, genau, und gerade von so einem Typ war auch diese

01:13:34.450 --> 01:13:35.770
Aufgabe mit den Vampiren.

01:13:36.390 --> 01:13:39.070
Sie haben ein Problem, jetzt finden Sie einen Algorithmus zum Lösen.

01:13:39.170 --> 01:13:43.150
Und darin war dann dieser starke Zusammenhangskomponenten-Algorithmus

01:13:43.150 --> 01:13:44.390
von Sebastian nützlich.

01:13:46.010 --> 01:13:48.990
Aber diesen Algorithmus selbst werden wir natürlich nicht verlangen.

01:13:49.610 --> 01:13:51.970
Also der war viel zu kompliziert, der war explizit für diese

01:13:51.970 --> 01:13:52.950
Vampirsache gedacht.

01:13:53.870 --> 01:13:58.790
Aber das Tiefensuchschema und sowas wie Tiefensuchnummerierung in

01:13:58.790 --> 01:14:01.510
einem anderen Anwendungsbeispiel durchaus denkbar.

01:14:06.570 --> 01:14:13.010
Dann hat der Julian den Durchmesser, der mit Exzentrizität von Knoten

01:14:13.010 --> 01:14:14.190
zusammenhängt, vorgestellt.

01:14:15.430 --> 01:14:18.250
Durchmesser von Graphen ist auch ein wichtiges Thema.

01:14:18.250 --> 01:14:22.410
Wie viele Schritte brauche ich im Facebook-Graph zu jedem anderen

01:14:22.410 --> 01:14:23.190
Person?

01:14:27.850 --> 01:14:31.830
Die zehnte Übung war eine volle Stunde, also eine volle Doppelstunde.

01:14:32.610 --> 01:14:33.850
Und da haben wir ziemlich viel gemacht.

01:14:34.490 --> 01:14:35.670
Es fing an mit Dijkstra.

01:14:36.590 --> 01:14:39.110
Natürlich war Dijkstra in der Vorlesung dran, aber Dijkstra ist

01:14:39.110 --> 01:14:39.670
sowieso wichtig.

01:14:41.050 --> 01:14:41.610
Also Dijkstra.

01:14:42.130 --> 01:14:45.270
Dann kamen verschiedene Beschleunigungstechniken für die Routenplanung

01:14:45.270 --> 01:14:46.270
und kürzeste Wegesuche.

01:14:46.270 --> 01:14:50.070
TNR-Routing, also Transit Node Routing, kommt in der Form natürlich

01:14:50.070 --> 01:14:50.430
nicht dran.

01:14:50.910 --> 01:14:54.090
Viel zu weit, viel zu weitgreifend, jenseits der Vorlesung.

01:14:55.630 --> 01:14:56.550
Aber Dijkstra oder sowas.

01:14:57.510 --> 01:14:59.710
Bellman-Ford, die Grundalgorithmen.

01:15:00.870 --> 01:15:03.070
Dann habe ich wieder was über Graphen erzählt.

01:15:04.470 --> 01:15:09.010
Insbesondere verschiedene Darstellungen, Adjacenz, Adjacenz-Sternchen,

01:15:09.290 --> 01:15:12.070
Felder, Matrizen, Listen.

01:15:12.970 --> 01:15:13.670
Was gibt es da noch?

01:15:14.490 --> 01:15:15.050
Ich glaube, das war es.

01:15:16.270 --> 01:15:18.830
Alle müsst ihr kennen, müsst ihr auch wissen.

01:15:19.050 --> 01:15:20.530
Habt ihr ja auch eine implementiert vielleicht.

01:15:21.410 --> 01:15:23.610
Die Inzidenzmatrix ist eine besondere, die ist ein bisschen anders,

01:15:23.730 --> 01:15:24.350
aber müsst ihr auch wissen.

01:15:25.470 --> 01:15:29.210
Dann gibt es verschiedene Arten, aus anderen Graphen zu machen und

01:15:29.210 --> 01:15:30.670
Kreise in Graphen zu finden.

01:15:31.030 --> 01:15:34.490
Besondere Kreise, Hamiltonische Kreise, Euler'sche Kreise, Satz von

01:15:34.490 --> 01:15:34.750
Euler.

01:15:35.270 --> 01:15:36.210
Ja, muss man kennen.

01:15:36.890 --> 01:15:39.610
Vielleicht nicht den Beweis, aber die Aussage.

01:15:43.830 --> 01:15:48.050
Dann vorbereitend auf das ganze MST-Kapitel waren diese

01:15:48.050 --> 01:15:48.610
Baumequivalenzen.

01:15:50.110 --> 01:15:55.750
Baum ist maximal kreislos, minimal zusammenhängend, sowas.

01:15:56.990 --> 01:15:59.190
Ich habe euch zwei von denen gezeigt.

01:15:59.430 --> 01:16:02.350
Ich hoffe, dass in dem Tutorium noch ein paar andere Richtungen

01:16:02.350 --> 01:16:03.030
gezeigt wurden.

01:16:04.990 --> 01:16:08.510
Diese ganzen Baumbeweise haben eine ganz ähnliche Struktur.

01:16:08.510 --> 01:16:11.910
Und wenn ihr in die letzten Klausuren reinguckt, die minimale

01:16:11.910 --> 01:16:14.650
Spannbauaufgaben enthielten genau diese Strukturen.

01:16:20.360 --> 01:16:24.020
Deswegen steht hier auch fett, die Beweismethodik kennen und nicht

01:16:24.020 --> 01:16:26.200
notwendigerweise tatsächlich den einzelnen Beweis.

01:16:28.200 --> 01:16:31.000
Der Satz von Cayley war der Schmankerl am Ende, der ist

01:16:31.000 --> 01:16:31.260
ausgeschlossen.

01:16:32.780 --> 01:16:35.140
Aufspannende Bäume, dann gab es die eine Stunde, wo ich euch

01:16:35.140 --> 01:16:37.100
aufspannende Bäume und Schnitte erklärt habe.

01:16:37.920 --> 01:16:42.360
Auch wichtig, insbesondere weil Schnitte und aufspannende Bäume und

01:16:42.360 --> 01:16:44.860
Kreise dann im MST-Kapitel-Zusammenhang kommen.

01:16:46.600 --> 01:16:50.340
Dann gab es noch eine Erweiterung, dann gab es das Problem der Graph

01:16:50.340 --> 01:16:53.480
-Partitionierung, das kommt nicht dran, das ist weit jenseits

01:16:53.480 --> 01:16:54.220
Vorlesungsstoff.

01:16:55.680 --> 01:16:59.000
Und auch jenseits Vorlesungsstoff ist dann der Filterkurs Cayley,

01:16:59.460 --> 01:17:03.820
Minimum -Spanning-Tree-Algorithmus, den Vitali vorgezeigt hat und

01:17:03.820 --> 01:17:04.960
erfunden hat.

01:17:08.020 --> 01:17:11.820
Wir haben danach sehr viel dynamische Programmierung gemacht,

01:17:13.580 --> 01:17:17.080
hoffentlich ausführlich, hoffentlich habt ihr da viel verstanden

01:17:17.080 --> 01:17:17.420
dabei.

01:17:18.320 --> 01:17:22.080
Wir haben verschiedene Beispiele aufgezeigt, ich habe an dem optimalen

01:17:22.080 --> 01:17:24.480
binären Suchbeispiel viel erklärt.

01:17:25.460 --> 01:17:28.940
Wichtig, wir werden nicht dieses einzelne Problem fragen, sondern

01:17:28.940 --> 01:17:31.300
wenn, dann natürlich ein neues dynamisches Programmierproblem

01:17:31.300 --> 01:17:33.180
vorstellen und euch lösen lassen.

01:17:37.100 --> 01:17:39.500
Aber die sind dann Beispiele oder prototypisch dafür.

01:17:42.460 --> 01:17:46.020
Dann diese Anwendung von dynamischer Programmierung in Form von

01:17:46.020 --> 01:17:49.380
Viterbi kommt natürlich nicht dran, das war jetzt auch wieder ein

01:17:49.380 --> 01:17:54.360
Anwendungsproblem, nicht aus OR, sondern aus Signalverarbeitung.

01:17:56.840 --> 01:18:02.180
Lineare Programmierung war letztes Mal meine geliebte Süßwarenfabrik,

01:18:02.620 --> 01:18:06.360
die ist wichtig, klar, das ist ein ganz typisches LP-Beispiel.

01:18:07.120 --> 01:18:11.320
Insbesondere solltet ihr auch diese verschiedenen Formen, die ich aus

01:18:11.320 --> 01:18:16.300
diesem LP produziert habe, die Matrixform mal angucken, dass ihr das

01:18:16.300 --> 01:18:16.860
so wisst.

01:18:17.140 --> 01:18:20.020
Es gibt eine Zielfunktion, es gibt Nebenbedingungen, man sollte die

01:18:20.020 --> 01:18:22.380
möglichst zusammen und kompakt hinschreiben können.

01:18:27.330 --> 01:18:29.910
Oder, was hier nicht drin steht, ein ILP.

01:18:30.990 --> 01:18:35.030
Unterscheidet sich nur darin, dass man Z irgendwo an die richtige

01:18:35.030 --> 01:18:35.810
Stelle hinschreibt.

01:18:36.990 --> 01:18:40.490
Aber mit diesem Z schreibt man eben hin, dass die Variablen

01:18:40.490 --> 01:18:41.770
normalerweise 0,1 sind.

01:18:43.030 --> 01:18:46.490
Es ist zwar Z, das sind zwar theoretisch alle ganzen Zahlen, aber in

01:18:46.490 --> 01:18:50.150
der Regel bricht man das dann noch kleiner runter auf 0,1, also drin

01:18:50.150 --> 01:18:50.730
oder nicht drin.

01:18:51.890 --> 01:18:55.710
Nicht dran kommt solche Advanced-Sachen wie Dualitätssatz und in dem

01:18:55.710 --> 01:18:59.170
Foliensatz, den ich ins Netz gestellt habe, gibt es noch ein Beispiel

01:18:59.170 --> 01:19:03.330
zum Simplex-Algorithmus, das ist nur zum schöne Dinge angucken.

01:19:05.470 --> 01:19:07.270
So, ich glaube, das war's.

01:19:11.040 --> 01:19:14.400
Ich wollte noch ein Ding zum Gridi-Algorithmus sagen.

01:19:15.860 --> 01:19:20.140
Gridi, richtig, funktioniert nicht, es sei denn, man beweist, dass er

01:19:20.140 --> 01:19:20.560
funktioniert.

01:19:22.960 --> 01:19:25.800
Gridi -Algorithmen haben wir nicht besonders viele kennengelernt.

01:19:26.460 --> 01:19:29.540
Der minimale Spannbaum-Algorithmus ist der prototypische Gridi

01:19:29.540 --> 01:19:30.040
-Algorithmus.

01:19:30.220 --> 01:19:32.080
Es ist ganz besonders, dass der funktioniert.

01:19:33.740 --> 01:19:34.260
Was gibt es noch?

01:19:36.160 --> 01:19:36.720
Rucksackproblem?

01:19:37.900 --> 01:19:41.000
Ja, aber der ist nicht optimal.

01:19:41.240 --> 01:19:44.980
Also wenn man Gridi beim Rucksack ankommt, dann wird das Ergebnis eben

01:19:44.980 --> 01:19:45.740
nicht immer optimal.

01:19:46.680 --> 01:19:51.280
Also dieser Tipp bezüglich Gridi ist nicht optimal, ist so gemeint,

01:19:51.640 --> 01:19:54.620
wenn ihr in der Klausur irgendein Problem bekommt und damit Gridi

01:19:54.620 --> 01:19:57.200
drangeht, dann ist das wahrscheinlich nicht richtig.

01:19:57.520 --> 01:19:58.840
Es sei denn, das ist ein minimaler Spannbaum.

01:20:01.080 --> 01:20:05.360
Dann müsst ihr zeigen, dass es tatsächlich ein Gridi-lösbares Problem

01:20:05.360 --> 01:20:05.680
ist.

01:20:09.010 --> 01:20:09.470
Okay.

01:20:12.690 --> 01:20:15.850
Also wenn Sie in der Klausur eine Aufgabe bekommen, wo Sie nach einer

01:20:15.850 --> 01:20:20.870
optimalen Lösung gefragt werden, ist es tatsächlich so wahrscheinlich,

01:20:21.050 --> 01:20:22.450
dass Sie dann ein Gridi-Algorithmus haben.

01:20:23.430 --> 01:20:26.910
Aber wenn das nicht der Fall ist, dann könnte es auch sein, dass Gridi

01:20:26.910 --> 01:20:27.430
-Algorithmus...

01:20:27.430 --> 01:20:29.740
Da muss man...

01:20:30.590 --> 01:20:31.150
Okay.

01:20:34.650 --> 01:20:37.470
Soviel zu Gridi und nicht Gridi.

01:20:39.010 --> 01:20:39.430
Fragen?

01:20:40.170 --> 01:20:41.010
Natürlich, Fragen.

01:20:50.850 --> 01:20:55.070
Wenn eine optimale Lösung verlangt ist, dann finden Sie eine optimale

01:20:55.070 --> 01:20:55.370
Lösung.

01:20:55.370 --> 01:20:55.570
Ja.

01:21:02.760 --> 01:21:04.700
Das ist eine interessante Frage.

01:21:05.720 --> 01:21:12.020
Also die Frage war, ob das Wort Lösung so gemeint ist, dass irgendeine

01:21:12.020 --> 01:21:13.940
Lösung oder eine optimale Lösung gemeint ist.

01:21:14.260 --> 01:21:15.340
Das ist eine interessante Frage.

01:21:15.720 --> 01:21:20.180
Das hängt damit zusammen, insbesondere hängt das bei der linearen

01:21:20.180 --> 01:21:22.280
Programmierung mit den ganzen Nebenbedingungen zusammen.

01:21:22.280 --> 01:21:25.820
Man nennt nämlich die Lösungen, die die Nebenbedingungen erfüllen,

01:21:25.960 --> 01:21:27.480
Feasible Solutions oder Lösungen.

01:21:27.940 --> 01:21:30.840
Also man lässt da das Vorderwort weg, das heißt einfach Lösung.

01:21:31.180 --> 01:21:34.060
Und die optimale Lösung ist die, die dann diese Zielfunktion

01:21:34.060 --> 01:21:34.300
maximiert.

01:21:36.040 --> 01:21:40.120
Bei all den anderen Problemen ist es meistens einfach nur eine Lösung,

01:21:40.320 --> 01:21:41.320
eine Lösung des Problems.

01:21:43.260 --> 01:21:46.140
Daher kommen diese Ambiguities.

01:21:47.820 --> 01:21:48.360
Mehr Deutlichkeiten.