WEBVTT 00:00.440 --> 00:01.540 So, schönen guten Morgen. 00:01.620 --> 00:02.880 Jetzt kann ich Sie endlich begrüßen. 00:03.380 --> 00:06.580 Etwas verzögert, weil mein Rechner irgendwie gestockt hat, er wollte 00:06.580 --> 00:07.080 nicht so recht. 00:07.760 --> 00:09.300 Jetzt scheint aber alles zu funktionieren. 00:09.540 --> 00:11.960 Allerdings bin ich über WLAN drin und nicht über das Festnetz. 00:12.880 --> 00:15.260 Es gibt schon eine erste Frage, ganz kurz. 00:18.640 --> 00:19.520 Naja, also... 00:20.480 --> 00:21.700 Gibt es noch eine Frage? 00:25.420 --> 00:25.860 Das... 00:26.400 --> 00:27.760 Die Frage stellen Sie nochmal. 00:27.760 --> 00:30.580 Ich weiß nicht, ob die von vorher noch da ist. 00:32.180 --> 00:33.940 Die habe ich wohl mal übersehen. 00:34.520 --> 00:37.760 Okay, ich denke, wir können dann hier einsteigen. 00:38.660 --> 00:41.160 Wir hatten uns letztes Mal beschäftigt mit Berechenbarkeit, 00:42.360 --> 00:42.840 Entscheidbarkeit. 00:44.020 --> 00:46.220 Wir hatten ja Algorithmen angeschaut. 00:46.300 --> 00:49.420 Ich habe Ihnen dann etwas erzählt über abzählbare Mengen. 00:50.400 --> 00:52.440 Da hatten wir uns ein bisschen Gedanken drüber gemacht. 00:52.540 --> 00:54.600 Ich hatte Ihnen etwas erzählt darüber, dass die Menge der 00:54.600 --> 00:58.820 berechenbaren Funktionen abzählbar ist, aber die Menge aller 00:58.820 --> 00:59.810 Funktionen eben überabzählbar. 01:00.400 --> 01:02.100 Das war das Degranalisierungsverfahren. 01:02.220 --> 01:03.720 Wir haben uns Entscheidbarkeit angeschaut. 01:04.300 --> 01:06.420 Ich habe Ihnen Aufzählbarkeit dargestellt. 01:06.540 --> 01:10.960 Da geht es dann darum, dass eben die Funktion, die die Abzählbarkeit 01:10.960 --> 01:13.220 darstellt, im Prinzip dann auch noch berechenbar sein muss. 01:13.860 --> 01:20.180 Und wir hatten dann uns auf die Fructuring-Berechenbarkeit gestürzt 01:20.180 --> 01:22.480 und gesagt, das ist ein formales Modell für Berechenbarkeit. 01:22.880 --> 01:25.440 Jetzt können wir also sagen, mit diesem formalen Modell können wir 01:25.440 --> 01:26.020 berechnen. 01:26.460 --> 01:27.380 Ich hatte das definiert. 01:27.460 --> 01:28.840 Wir hatten dann ein paar Beispiele gesehen. 01:28.960 --> 01:32.800 Ich hatte dann entsprechend aus allem, was vorher über Berechenbarkeit 01:32.800 --> 01:35.500 definiert worden war, dann Turing-Berechenbarkeit gemacht, 01:35.620 --> 01:37.780 beziehungsweise Turing-Aufzählbarkeit, Entscheidbarkeit. 01:38.420 --> 01:41.680 Und wir hatten gesehen, dass man universelle Turing-Maschinen angeben 01:41.680 --> 01:44.660 kann, mit der man jede andere Maschine dann simulieren kann. 01:46.080 --> 01:48.900 Und das war die Kodierung, die wir dort genommen hatten. 01:49.440 --> 01:52.320 Das war also diese Simulation dieser Turing-Maschine. 01:53.220 --> 01:57.460 Und ich hatte Ihnen dann eine Sprache vorgestellt, die Sprache LNA, 01:57.980 --> 02:00.880 die gerade von mir zeigen könnte, dass sie nicht akzeptiert werden 02:00.880 --> 02:03.180 kann durch eine Turing-Maschine, ging auch wieder über einen 02:03.180 --> 02:07.100 Diagonalisierungsansatz, dass eben gerade diese Diagonal-Elemente 02:07.100 --> 02:09.340 hier, oder dass es eine Sprache ist, die sich an den Diagonal 02:09.340 --> 02:12.140 -Elementen einer Tabelle gerade von allen anderen unterscheidet. 02:14.480 --> 02:17.300 Und das war also das, was wir hier gesehen haben, dass es eben 02:17.300 --> 02:19.980 Sprachen gibt, die nicht in L0 sind im Prinzip, weil ja Turing 02:19.980 --> 02:22.520 -Maschinen zu L0-Grammatiken äquivalent sind. 02:23.360 --> 02:26.520 Und wir hatten uns dann beschäftigt mit der Sturgeon-These. 02:26.720 --> 02:29.920 Ich hatte Ihnen gesagt, das ist eben eine wesentliche Grundlage für 02:29.920 --> 02:32.880 die Behandlung von Berechenbarkeit, dass wir sagen, wir können im 02:32.880 --> 02:37.060 Prinzip alle Modelle oder eine ganze Reihe von Modellen, die in der 02:37.060 --> 02:39.500 Literatur vorhanden sind, um Berechenbarkeit zu charakterisieren. 02:40.620 --> 02:43.220 Von vielen von denen kann man zeigen, dass sie äquivalent sind, 02:43.420 --> 02:45.020 äquivalent zur Turing-Berechenbarkeit. 02:45.540 --> 02:48.720 Und damit ist das eigentlich im Prinzip die Turing-Berechenbarkeit 02:48.720 --> 02:52.000 oder auch eine andere, wir können jedes andere äquivalente Modell 02:52.000 --> 02:52.560 dafür nehmen. 02:53.620 --> 02:56.420 Und es ist halt nur eine These, weil ich über intuitive 02:56.420 --> 02:58.460 Berechenbarkeit natürlich nichts beweisen kann. 02:58.840 --> 03:00.120 Das ist halt ein intuitiver Begriff. 03:01.000 --> 03:03.860 Und danach kamen wir zum Halteproblem, das habe ich Ihnen vorgestellt. 03:03.960 --> 03:08.340 Das Halteproblem, bei dem es darum geht, ob es möglich ist, für ein 03:08.340 --> 03:12.460 beliebiges Programm und beliebige Eingaben zu entscheiden, ob dieses 03:12.460 --> 03:14.660 Programm mit dieser Eingabe hält oder nicht. 03:14.980 --> 03:16.200 Das ist ein unerscheinbares Problem. 03:16.380 --> 03:18.400 Wir haben gesehen, wie man das machen kann. 03:18.400 --> 03:22.620 Wenn wir annehmen, das wäre entscheidbar, konnten wir zeigen, dann 03:22.620 --> 03:25.240 können wir eine Turing-Maschine konstruieren, die gerade diese Sprache 03:25.240 --> 03:27.800 akzeptiert, LNA, von der wir gezeigt haben, dass sie nicht 03:27.800 --> 03:31.240 akzeptierbar ist, oder dass es für sie keine Turing-Maschine geben 03:31.240 --> 03:31.540 kann. 03:31.880 --> 03:36.060 Deswegen ist das ein Widerspruch dazu, dass man annimmt, das 03:36.060 --> 03:37.300 Halteproblem wäre lösbar. 03:37.780 --> 03:40.320 Und das Interessante ist eben, es gibt eine ganze Reihe 03:40.320 --> 03:45.240 praxisrelevante und nicht durchaus praxisrelevante Fragen, wie zum 03:45.240 --> 03:47.500 Beispiel Äquivalenz von kontextfreien Grammatiken. 03:47.500 --> 03:50.620 Das ist nicht so irgendwo mit Turing-Maschinen, die Ihnen nicht 03:50.620 --> 03:52.940 interessieren, sondern kontextfreie Sprachen sind interessante 03:52.940 --> 03:53.420 Sprachen. 03:53.980 --> 03:56.700 Und wenn man dafür beliebige kontextfreie Grammatiken nicht überprüfen 03:56.700 --> 04:00.960 kann, ob sie äquivalent sind, dann zeigt das schon, es gibt viele 04:00.960 --> 04:04.300 Probleme, von denen man nachweisen kann, man braucht sich gar nicht 04:04.300 --> 04:07.740 anzustrengen, einen Algorithmus für dieses allgemeine Problem zu 04:07.740 --> 04:11.220 formulieren, weil es einfach nicht entscheidbar ist. 04:11.860 --> 04:15.460 Dann muss man sich auf ein Teilproblem konzentrieren, von dem man 04:15.460 --> 04:16.840 weiß, dass es entscheidbar ist. 04:16.960 --> 04:22.000 Und dann geht es natürlich darum, dass man sich mit dem Aufwand 04:22.000 --> 04:22.500 beschäftigt. 04:22.560 --> 04:23.700 Und das machen wir heute vor allem. 04:24.320 --> 04:28.760 Damit kommen wir zu einem ganz wichtigen weiteren Thema der Vorlesung, 04:30.380 --> 04:31.260 nämlich Komplexitätsbetrachtungen. 04:31.640 --> 04:36.560 Eigentlich eine meiner Kernkompetenzen, aber wir machen das nur 04:36.560 --> 04:39.440 relativ kurz, heute und vielleicht noch ein bisschen am Mittwoch. 04:39.900 --> 04:42.560 Da geht es also darum, wie viel kostet eine Berechnung? 04:42.560 --> 04:45.940 Für Sie, für die Wirtschaftsingenieure, eigentlich die zentrale Frage. 04:46.040 --> 04:49.440 Sie wollen immer Dinge effizienter machen, kostengünstiger. 04:49.800 --> 04:52.420 Wenn Sie im Informatikbereich etwas kostengünstiger machen wollen, 04:52.580 --> 04:56.040 müssen Sie sich mit Komplexität beschäftigen, müssen sehen, wie Sie 04:56.040 --> 04:57.840 Aufwand eigentlich abschätzen können. 04:58.280 --> 04:59.780 Und hier machen wir das jetzt etwas grundsätzlich. 05:00.500 --> 05:03.600 Also einmal, was kostet die Berechnung einer Funktion oder was kostet 05:03.600 --> 05:05.000 die Lösung eines Problems? 05:05.620 --> 05:08.500 Und natürlich hängt das Ganze davon ab, was für ein Berechnungsmodell 05:08.500 --> 05:10.540 wir haben und welchen Algorithmus wir nehmen. 05:11.880 --> 05:17.020 Also, ich will wissen, was kostet das Sortieren zum Beispiel? 05:17.740 --> 05:22.520 Also, ich will nicht wissen, wie teuer ist ein Algorithmus, sondern 05:22.520 --> 05:24.840 wie teuer ist es zu sortieren, allgemein. 05:25.280 --> 05:28.580 Und das heißt, ich muss damit Aussagen machen über beliebige 05:28.580 --> 05:31.360 Berechnungsmodelle oder ich kann sagen, für ein Berechnungsmodell, 05:31.900 --> 05:34.620 egal wie ich es mache, kostet das so und so viel. 05:36.500 --> 05:39.300 Und es gibt auch unterschiedlichste Berechnungsmodelle. 05:39.300 --> 05:42.160 Zum Beispiel kann ich sagen, ich habe sequentielle Berechnungen mit 05:42.160 --> 05:44.920 elementaren Operationen oder parallele Berechnungen. 05:45.400 --> 05:47.060 Ändert das was an den Kosten? 05:47.660 --> 05:49.760 Wie ändern sich die Kosten dadurch? 05:49.900 --> 05:51.560 Alle diese Fragen sind hochinteressant. 05:52.260 --> 05:54.900 Und das, was wir normalerweise machen, ist, dass wir uns Turing 05:54.900 --> 05:55.800 -Maschinen anschauen. 05:56.340 --> 05:57.480 Die haben wir schon gesehen. 05:57.860 --> 05:59.060 Die sind ja sehr einfach. 05:59.380 --> 06:01.340 Können Sie sagen, Sie rechnen ja nicht mit einer Turing-Maschine, 06:01.520 --> 06:04.280 sondern Sie haben ein Smartphone oder Ihr Laptop oder einen 06:04.280 --> 06:04.820 Superrechner. 06:05.460 --> 06:06.920 Das sind alles Register-Maschinen. 06:06.920 --> 06:10.380 Die Register-Maschinen lernen wir etwas später noch kennen, im Bereich 06:10.380 --> 06:13.340 Technische Informatik, wo wir uns dann die von Neumann-Maschinen 06:13.340 --> 06:13.980 anschauen. 06:14.060 --> 06:16.800 Das ist im Prinzip die Struktur aller unserer Rechner, die wir haben. 06:17.720 --> 06:19.480 Und das sind Register-Maschinen. 06:19.600 --> 06:21.220 Random Access Machine im Englischen. 06:22.020 --> 06:23.700 Und deswegen RAM abgekürzt. 06:24.600 --> 06:27.820 Also nicht für Random Access Memory, sondern Random Access Machines 06:27.820 --> 06:29.220 oder auf Deutsch Register-Maschinen. 06:30.240 --> 06:32.960 Und eine Turing-Maschine ist keine Register-Maschine, weil ich da 06:32.960 --> 06:36.040 einen sequentiellen Zugriff habe auf die Elemente auf dem Band. 06:36.040 --> 06:39.100 Bei einer Random Access Machine habe ich wahlfreien Zugriff. 06:40.120 --> 06:41.300 Und das kann ja durchaus Unterschiede machen. 06:41.340 --> 06:44.840 Ob ich jetzt also ein Band habe, auf das ich nur so irgendwo mal 06:44.840 --> 06:47.680 zugreifen kann und wenn ich jetzt irgendwo da hin will, muss ich da 06:47.680 --> 06:48.520 ganz rüber laufen. 06:48.840 --> 06:52.060 Oder ich habe irgendeinen Speicher und ich kann an eine beliebige 06:52.060 --> 06:55.560 Stelle einfach mit, egal wo ich hin will, mit gleichen Kosten darauf 06:55.560 --> 06:56.120 zugreifen. 06:56.780 --> 06:57.660 Wesentliche Unterschiede. 06:58.220 --> 07:00.200 Zugriffskosten auf Speicher sind relevant. 07:00.860 --> 07:03.860 Ob ich das sequentiell oder wahlfrei machen kann, kann durchaus 07:03.860 --> 07:04.540 Unterschiede machen. 07:04.540 --> 07:08.060 Wir werden sehen, grundsätzlich reicht es, tatsächlich Turing 07:08.060 --> 07:08.940 -Maschinen anzuschauen. 07:09.260 --> 07:12.540 Grundsätzlich in Bezug auf gewisse Komplexitätsklassen. 07:13.340 --> 07:16.360 Und dann kann ich mir anschauen, Parallel RAMs, also parallele 07:16.360 --> 07:20.780 Rechenanlagen, wie viele, wenn ich also jetzt so eine Register 07:20.780 --> 07:24.200 -Maschine habe, was passiert, wenn ich davon viele nebeneinander 07:24.200 --> 07:27.640 setzen kann und die gemeinsam einsetzen kann, um ein Problem zu lösen. 07:27.900 --> 07:29.480 Da gibt es viele interessante Fragestellungen. 07:29.620 --> 07:31.280 Sie haben alle Parallel-Rechen an der Tasche. 07:31.280 --> 07:36.940 Die heutigen Smartphones haben in der Regel mehrfache Cores drin. 07:37.320 --> 07:39.160 Das heißt, sie rechnen alle parallel. 07:39.780 --> 07:44.520 Wobei ihre Software in der Regel häufig nicht wirklich parallelisiert, 07:44.720 --> 07:49.580 sondern es werden nur auf mehreren Rechnern unterschiedliche Programme 07:49.580 --> 07:50.140 ausgeführt. 07:50.460 --> 07:53.060 Aber man kann eben auch einzelne Programme parallelisieren und damit 07:53.060 --> 07:53.740 einiges erreichen. 07:54.780 --> 07:57.660 Ich würde Ihnen gerne viel mehr darüber erzählen, weil das meine 07:57.660 --> 08:01.140 Kernkompetenz ist, gerade diese Sachen zu machen, aber wir haben dafür 08:01.140 --> 08:01.880 leider keine Zeit. 08:01.980 --> 08:05.220 Ich kann Ihnen nur etwas erzählen über grundsätzlich Komplexität von 08:05.220 --> 08:05.640 Problemen. 08:06.280 --> 08:10.580 Wenn ich also von Problemen rede, wie Sortieren zum Beispiel, dann 08:10.580 --> 08:12.940 kann ich sagen, okay, ich kenne einen Algorithmus, der hat einen 08:12.940 --> 08:14.040 bestimmten Berechnungsaufwand. 08:14.220 --> 08:17.020 Also, obere Schranke für einen Berechnungsaufwand. 08:17.100 --> 08:20.180 Ich gebe Ihnen einen Algorithmus, analysieren den und dann weiß ich, 08:20.260 --> 08:23.240 wie viel ich maximal ausgeben muss, um dieses Problem zu lösen, weil 08:23.240 --> 08:24.380 ich kann ja den Algorithmus nehmen. 08:25.060 --> 08:28.380 Das Interessante ist, wie sieht das mit unteren Schranken aus? 08:28.860 --> 08:32.940 Das heißt, wie viel Aufwand muss ich mindestens treiben, um ein 08:32.940 --> 08:33.720 Problem zu lösen? 08:33.820 --> 08:37.180 Also beim Sortierproblem, wie viele Vergleiche brauche ich mindestens, 08:38.200 --> 08:42.220 um eine Folge zu sortieren oder beliebige Folgen sortieren zu können? 08:43.040 --> 08:46.060 Und das ist dann eine Frage, da kann ich mich nicht auf einen 08:46.060 --> 08:49.220 Algorithmus beschränken, da muss ich etwas über alle sagen, über 08:49.220 --> 08:51.800 beliebige Algorithmen, offensichtlich eine viel schwieriger Aussage. 08:51.800 --> 08:54.480 Trotzdem können wir für viele Probleme solche Aussagen machen. 08:54.800 --> 08:57.260 Beim Sortieren kann man das, für das allgemeine Sortierproblem, wissen 08:57.260 --> 08:59.820 Sie, man braucht NlogN-Vergleiche mindestens. 09:00.200 --> 09:03.760 Und wir kennen Algorithmen, die tatsächlich mit NlogN vergleichen, mal 09:03.760 --> 09:05.100 irgendeine Konstante auskommen. 09:05.240 --> 09:08.040 Also da können wir wirklich optimale Verfahren angeben, bei denen 09:08.040 --> 09:11.640 tatsächlich die obere und die untere Schranke identisch sind. 09:12.720 --> 09:15.420 Beziehungsweise, wir können die obere Schranke tatsächlich bis runter 09:15.420 --> 09:18.500 drücken auf die untere Schranke, können also genau die Komplexität 09:18.500 --> 09:20.600 festlegen für gewisse Probleme. 09:20.600 --> 09:22.620 Es gibt eine ganze Reihe von Problemen, wo das exakt können. 09:22.980 --> 09:24.320 Es gibt viele andere, wo das nicht geht. 09:26.860 --> 09:30.120 Also, wenn wir etwas jetzt über Turing-Maschinen allgemein aussagen 09:30.120 --> 09:32.960 möchten, gehen wir wieder auf Turing-Maschinen und weg von dem 09:32.960 --> 09:34.320 einfachen Problem des Sortierens. 09:35.560 --> 09:39.560 Also, da haben wir ein Alphabet und zwei Teilmengen von E-Stern. 09:40.020 --> 09:43.500 Wir haben eine Funktion, die wir berechnen sollen mit einer Turing 09:43.500 --> 09:43.880 -Maschine. 09:44.340 --> 09:47.700 Und jetzt wollen wir sagen, was kostet es, eine Funktion zu berechnen 09:47.700 --> 09:48.560 mit einer Turing-Maschine. 09:49.330 --> 09:53.660 Und da haben wir, und zwar die Zeit- und die Platzkomplexität. 09:53.780 --> 09:57.360 Das sind die klassischen zwei Komplexitätsmaße, die man sich anschaut. 09:57.700 --> 10:03.440 Sie können dazu noch nehmen, sowas wie Parallelitätsgrad. 10:08.600 --> 10:10.840 Parallelitätsgrad könnte man noch machen. 10:11.100 --> 10:15.640 Oder Sie könnten, jetzt heutzutage viel wichtiger, Energieaufwand, 10:15.660 --> 10:16.460 könnten Sie auch nehmen. 10:16.460 --> 10:19.300 Wie viel Energie braucht eine Berechnung? 10:20.280 --> 10:23.540 Energieaufwand für Berechnungen ist heutzutage ein sehr relevantes 10:23.540 --> 10:27.000 Thema, weil wir sehen müssen, dass wir eben nicht zu viel Energie 10:27.000 --> 10:27.420 brauchen. 10:27.900 --> 10:32.360 Und also mit möglichst wenig Energie etwas zu berechnen, ist eine der 10:32.360 --> 10:33.640 großen Herausforderungen im Augenblick. 10:34.400 --> 10:37.800 Wir gehen aber erstmal auf, also das sind doch interessante andere 10:37.800 --> 10:40.580 Sachen, wir gucken erstmal nur auf die Zeitkomplexität. 10:41.380 --> 10:44.460 Und die Zeitkomplexität definieren wir einfach so, dass wir uns 10:44.460 --> 10:47.320 anschauen bei einer Turing-Maschine, was wäre da die Zeit? 10:47.600 --> 10:49.680 Wir können uns vielleicht mit einer Stoppuhr neben die Turing-Maschine 10:49.680 --> 10:51.160 setzen und warten, bis sie fertig ist. 10:51.560 --> 10:55.480 Wir können nur gucken, was für Konfigurationen führt die Turing 10:55.480 --> 10:56.140 -Maschine aus. 10:56.580 --> 11:00.740 Wir schauen uns die Länge der kürzesten Konfigurationenfolge von der 11:00.740 --> 11:02.760 Anfangs - zur Endkonfiguration an. 11:03.540 --> 11:05.740 Es kann sein, dass es eine nicht deterministische Turing-Maschine ist, 11:05.800 --> 11:08.000 dann haben wir einen Baum von Konfigurationsfolgen. 11:08.460 --> 11:12.820 Wir wissen, dass die Funktion berechnet wird oder dass sie berechenbar 11:12.820 --> 11:17.320 ist durch eine Turing-Maschine, wenn es eben eine Folge gibt, die zu 11:17.320 --> 11:19.760 einer Endkonfiguration kommt, eine Konfigurationsfolge. 11:20.180 --> 11:23.360 Und jetzt nehmen wir uns die kürzeste derartige Folge her, die könnte 11:23.360 --> 11:24.160 man ja auch wählen. 11:24.620 --> 11:28.960 Und dann ist das die Zeit, um diese Funktion mit dieser Turing 11:28.960 --> 11:29.800 -Maschine zu berechnen. 11:30.260 --> 11:33.620 Die Länge der kürzesten Folge, also das ist unser schöner Baum hier 11:33.620 --> 11:36.880 mit allen möglichen Verzweigungen. 11:37.300 --> 11:41.080 Und da schauen wir uns eben den kürzesten Weg an, denn das wäre ja 11:41.080 --> 11:41.780 eine Möglichkeit. 11:42.480 --> 11:44.700 Die anderen interessieren uns gar nicht, das ist die Länge der 11:44.700 --> 11:47.280 kürzesten Konfigurationsfolge, von der Anfangs- bis zur 11:47.280 --> 11:53.180 Endkonfiguration ausgehend von einem Eingabewort W aus M1, wollen wir 11:53.180 --> 11:57.820 das F von W berechnen, das muss dann am Ende auf dem Band stehen. 11:58.420 --> 12:01.680 Und das ist also jetzt unser Maß für die Zeit, die Anzahl der 12:01.680 --> 12:02.780 Schritte, die Anzahl der Konfigurationen. 12:03.620 --> 12:07.160 Und dann können wir sagen, wir schauen uns jetzt alle möglichen Wörter 12:07.160 --> 12:10.620 an, die auf dem Band stehen können, die die gleiche Länge haben. 12:13.160 --> 12:16.020 Und jetzt schauen wir uns an, wie lange die Turing-Maschine braucht, 12:16.080 --> 12:18.540 bei irgendwelchen Wörtern gleicher Länge. 12:19.380 --> 12:20.680 Und das ist dann die Länge N. 12:21.960 --> 12:25.960 Schauen wir uns also an, alle Zeiten der Turing-Maschine auf Wörtern 12:25.960 --> 12:26.440 dieser Länge. 12:29.240 --> 12:32.120 Und entsprechend definieren wir jetzt die Platzkomplexität. 12:34.620 --> 12:36.700 Platzkomplexität, was ist der Platz einer Turing-Maschine? 12:36.700 --> 12:38.340 Wie viel Platz braucht die denn? 12:38.700 --> 12:42.980 Naja, wir haben ja ein Eingabeband und auf unserem Eingabeband, da 12:42.980 --> 12:45.040 steht zu Anfang irgendein Wort drauf. 12:45.900 --> 12:48.240 Und dann kann es ja sein, dass wir im Laufe der Berechnung noch 12:48.240 --> 12:50.200 weitere Felder brauchen, auf die wir rechnen müssen. 12:50.780 --> 12:55.440 Wir schauen uns einfach an, die Anzahl der durch Schreiben veränderten 12:55.440 --> 12:59.840 Zellen des Bandes in der kürzesten Konfigurationenfolge von der 12:59.840 --> 13:01.360 Initial - zur Endkonfiguration. 13:01.900 --> 13:06.720 Also auf wie vielen Feldern mussten wir etwas anderes schreiben, als 13:06.720 --> 13:07.480 dort vorher stand? 13:08.760 --> 13:11.140 Wenn wir das nur lesen, das zählt ja gar nicht dabei, wenn wir nur 13:11.140 --> 13:13.600 einmal durchlaufen, das ist eigentlich gar nicht so relevant. 13:13.740 --> 13:17.520 Das Wesentliche ist, wie viel brauchen wir an Arbeitsband? 13:18.400 --> 13:21.880 Stellen Sie sich vor, Sie hätten eben bei Ihrer Turing-Maschine extra 13:21.880 --> 13:23.980 ein Arbeitsband und nur auf dem könnten Sie schreiben. 13:24.060 --> 13:27.300 Dann wäre das die Anzahl der Zellen auf diesem Arbeitsband, das Sie 13:27.300 --> 13:28.140 tatsächlich brauchen. 13:30.200 --> 13:32.320 Und das wäre jetzt der Platz. 13:32.700 --> 13:34.440 Auf wie viele Zellen müssen Sie schreiben? 13:34.660 --> 13:37.100 Beim normalen Rechner wäre das eben die Anzahl der Speicherzellen, die 13:37.100 --> 13:38.680 Sie brauchen in Ihrem Speicher. 13:39.240 --> 13:40.440 Das ist die Platzkomplexität. 13:40.840 --> 13:47.260 Entsprechend wieder PTM von W und dann die Platzkomplexität bezogen 13:47.260 --> 13:48.840 auf alle Wörter gleicher Länge. 13:49.260 --> 13:54.860 Und Sie sehen schon, das Ganze ist die Berechnungskomplexität im 13:54.860 --> 13:56.020 schlechtesten Fall. 13:56.570 --> 14:01.680 Man sagt hier für oben bei der Zeitkomplexität auch die Worst-Case 14:01.680 --> 14:09.060 -Execution -Time, WZ ist die Abkürzung, häufig die Zeitkomplexität im 14:09.060 --> 14:10.020 schlechtesten Fall. 14:10.420 --> 14:15.700 Im schlechtesten Fall, weil wir hier gerade das Maximum jeweils dieser 14:15.700 --> 14:17.220 Zeiten betrachten. 14:18.180 --> 14:23.440 Das ist unsere Abschätzung der Zeitkomplexität, im schlechtesten Fall. 14:23.440 --> 14:26.400 Sie könnten auch den mittleren Fall sich anschauen, Sie können sich 14:26.400 --> 14:30.880 den besten Fall anschauen, Sie können sich irgendwelche Aufwände für 14:30.880 --> 14:35.000 eine Teilmenge von Problemen betrachten, kann man alles machen. 14:35.400 --> 14:37.260 Wir beschränken uns jetzt auf den schlechtesten Fall. 14:38.100 --> 14:41.360 Und Sie kennen das so ein bisschen aus Grundlageninformatik 1, da 14:41.360 --> 14:44.200 haben Sie den Aufwand von einzelnen Algorithmen abgeschätzt, haben 14:44.200 --> 14:46.300 auch mal den mittleren Fall angeschaut, natürlich auch den besten 14:46.300 --> 14:46.940 Fall. 14:46.940 --> 14:52.200 Und jetzt wollen wir Komplexitätsklassen definieren. 14:52.340 --> 14:53.020 Was heißt das? 14:53.420 --> 14:59.120 Wir wollen gerne Funktionen klassifizieren, entsprechend ihrem 14:59.120 --> 14:59.800 Aufwand. 15:01.760 --> 15:03.060 Wie machen wir das? 15:03.380 --> 15:06.300 Fangen wir an, D-Time von G. 15:07.020 --> 15:08.400 D-Time von G. 15:08.700 --> 15:12.340 D steht für deterministisch und G ist eine Funktion. 15:14.340 --> 15:20.620 Und zwar ist D-Time von G die Menge aller Funktionen, die mit der 15:20.620 --> 15:25.260 Zeitkomplexität Groß-O von G von einer deterministischen Turing 15:25.260 --> 15:26.580 -Maschine berechenbar sind. 15:28.020 --> 15:29.600 Wofür steht O von G? 15:30.160 --> 15:44.000 Groß-O von G ist die Menge aller F, kurz hier ein bisschen ab, es gibt 15:44.000 --> 16:04.700 ein N0, es gibt ein C, sodass für alle N größer gleich N0, F von N 16:04.700 --> 16:08.740 kleiner gleich C mal G von N ist. 16:08.740 --> 16:12.680 Das heißt, das ist eine Abschätzung nach oben, G von N ist eine obere 16:12.680 --> 16:20.300 Schranke für den Berechnungsaufwand, also für die Schwierigkeit dieser 16:20.300 --> 16:26.200 Funktion und eine obere Schranke bis auf konstante Faktoren, das ist 16:26.200 --> 16:29.660 dieses C, und zwar asymptotisch ab einer gewissen Schranke. 16:29.920 --> 16:30.700 Da gibt es eine Frage. 16:32.660 --> 16:34.320 Naja, sehr nett. 16:36.860 --> 16:41.980 Das ist übrigens eine Anwendung, wie man das nutzen könnte, wenn ich 16:41.980 --> 16:45.360 diese Vorlesungen gleichzeitig irgendwo hin streamen würde, dann 16:45.360 --> 16:49.520 könnten natürlich externe Hörer auch gleichzeitig hier Fragen stellen 16:49.520 --> 16:52.100 in der Vorlesung, was man durchaus auch machen kann, das ist noch ein 16:52.100 --> 16:56.540 sinnvollerer Einsatz dieses Interaktionswerkzeugs, weil man dann von 16:56.540 --> 16:59.500 außerhalb tatsächlich auch interagieren kann. 16:59.500 --> 17:02.820 Also bei Televorlesungen haben wir früher auch gemacht, gleichzeitig 17:02.820 --> 17:08.240 Vorlesungen, die ich hier gehalten habe, die gleichzeitig in Mannheim 17:08.240 --> 17:10.920 und in Freiburg zu hören waren. 17:11.340 --> 17:13.220 Da haben wir bei solchen Werkzeugen auch gearbeitet. 17:13.960 --> 17:18.440 Okay, also Dietheim nochmal, die Menge der Funktionen, die maximal den 17:18.440 --> 17:22.940 Aufwand G brauchen, um berechnet zu werden, bis auf konstanten 17:22.940 --> 17:23.740 Faktoren im G. 17:23.740 --> 17:26.080 Das ist das, was ich hier oben noch kurz angedeutet habe. 17:26.180 --> 17:32.660 Ich nehme an, Sie kennen diese Notation für asymptotische Notationen, 17:32.660 --> 17:34.680 also für asymptotischen Aufwand. 17:35.440 --> 17:40.060 N-Time von G entsprechend N für nicht deterministisch, das heißt, Sie 17:40.060 --> 17:47.800 können Funktionen mit nicht deterministischen Turing-Maschinen in der 17:47.800 --> 17:50.480 Zeit maximal 10 mal G berechnen. 17:51.620 --> 17:56.860 Und dann kommt das Ganze nochmal für den Platz, D-Space und N-Space, 17:57.140 --> 17:59.260 jeweils mit deterministischen Turing-Maschinen oder nicht 17:59.260 --> 18:01.840 deterministischen Turing-Maschinen, Funktionen zu berechnen. 18:02.240 --> 18:04.460 Das sind jetzt allgemeine Angaben. 18:04.860 --> 18:05.440 Und was ist das G? 18:05.540 --> 18:07.680 Für das G können Sie beliebige Funktionen nehmen. 18:08.060 --> 18:11.480 Sie können dann nehmen eine lineare Funktion oder irgendein Polynom, 18:11.620 --> 18:15.280 also G von N gleich N hoch K oder G von N gleich N log N. 18:15.280 --> 18:19.480 Da wäre das Sortierproblem zum Beispiel drin, weil Sie das genau dort, 18:20.100 --> 18:25.140 also Sie können das Sortierproblem inside N log N tatsächlich lösen. 18:25.920 --> 18:28.560 Sie können auch exponentielle Funktionen hier angeben oder 18:28.560 --> 18:30.920 logarithmische, log hoch K von N. 18:31.760 --> 18:35.460 Das sind so typische Komplexitätsklassen, die man betrachtet. 18:35.600 --> 18:41.260 Und wir werden das jetzt etwas eingrenzen oder eine Klasse besonders 18:41.260 --> 18:45.800 hervorheben, dass zunächst mal die Klasse der in polynomialer Zeit 18:45.800 --> 18:47.340 berechenbaren Funktionen. 18:47.720 --> 18:49.080 Warum betrachten wir die? 18:49.200 --> 18:53.000 Wir sagen, wir wollen eigentlich die Funktion charakterisieren, die 18:53.000 --> 18:56.180 man in einigermaßen vernünftiger Zeit berechnen kann. 18:57.080 --> 18:59.960 Wir hatten schon öfter darüber gesprochen bei dem Wortproblem. 19:00.060 --> 19:02.800 Da sagten wir, eigentlich ist linear nur einigermaßen vernünftig. 19:03.140 --> 19:04.660 N hoch 3 waren schon zu viel. 19:05.260 --> 19:08.340 Aber exponentiell, wie bei den Kontextsensitiven, das ist schon 19:08.340 --> 19:11.980 außerhalb dessen, was wir als vernünftig machbar ansehen. 19:12.720 --> 19:16.540 Also alles, was noch polynomiell ist, also hier irgend so ein N hoch K 19:16.540 --> 19:20.740 da drin, das sehen wir noch als einigermaßen machbar an. 19:22.260 --> 19:25.180 Ja, polynomiell, das ist schon mal ganz gut. 19:26.300 --> 19:31.000 Alles, was darüber hinausgeht, wäre nicht so gut. 19:32.220 --> 19:34.940 Es gibt aber eine gewisse Variante. 19:34.940 --> 19:36.700 Hier steht ja D-Time. 19:36.840 --> 19:40.880 Was ist denn, wenn ich statt D-Time N-Time hier hinschreibe? 19:41.740 --> 19:47.440 Das heißt, alle Funktionen, die von nicht deterministischen Turing 19:47.440 --> 19:50.820 -Maschinen in polynomieller Zeit berechnet werden können, also bei 19:50.820 --> 19:54.520 denen die kürzeste Berechnungsfolge, die es gibt, polynomielle Länge 19:54.520 --> 19:54.860 hat. 19:56.780 --> 19:58.940 Ist das das Gleiche oder nicht? 19:58.940 --> 20:03.540 Also, was heißt das erst mal? 20:03.640 --> 20:07.040 N-P heißt ja, ich habe einen Berechnungspfad, der polynomielle Länge 20:07.040 --> 20:07.840 haben darf. 20:08.500 --> 20:12.200 Und man kann N-P sich so erklären, was machen wir da? 20:13.000 --> 20:18.120 Man kann nicht deterministisch eine potenzielle Lösung raten und dann 20:18.120 --> 20:22.040 in polynomieller Zeit die Korrektheit der Lösung überprüfen. 20:22.460 --> 20:23.440 Kleines Beispiel. 20:24.240 --> 20:26.940 Wenn Sie ein Problem haben wie das Travelling Salesperson Problem. 20:26.940 --> 20:32.780 Sie wollen eine Rundreise durch viele Städte machen und die wollen Sie 20:32.780 --> 20:37.560 alle besuchen und Sie wollen dafür irgendwie den kürzestmöglichen Weg 20:37.560 --> 20:38.060 finden. 20:39.340 --> 20:42.380 Vielleicht ist das einer, weiß ich nicht, was ein kürzestmöglicher Weg 20:42.380 --> 20:42.680 ist. 20:43.880 --> 20:46.940 Travelling Salesperson Problem, Problem des Handelsreisenden. 20:48.440 --> 20:52.320 Nicht deterministisch kann ich das so lösen, dass ich eine Lösung 20:52.320 --> 20:52.880 rate. 20:52.880 --> 20:58.500 Ich rate einen Weg durch meine Städte, die ich besuchen soll und 20:58.500 --> 21:04.520 überprüfe, die Frage ist also, gibt es einen Weg mit den Kosten dieses 21:04.520 --> 21:09.820 Weges, mit den Kosten dieses Weg P für Path kleiner gleich irgendein 21:09.820 --> 21:10.040 K. 21:11.580 --> 21:15.620 So, dann kann ich eine Lösung raten und kann überprüfen, gibt es einen 21:15.620 --> 21:20.800 Pfad, der maximal die Länge K hat und ich rate einen Weg, überprüfe, 21:20.980 --> 21:25.040 welche Länge hat der Weg, ist der kleiner gleich K oder größer K und 21:25.040 --> 21:30.400 da ich ja jede mögliche Lösung raten kann, kann ich ja auch, wenn eine 21:30.400 --> 21:31.980 existiert, die richtige raten. 21:32.700 --> 21:39.920 Also diese Frage kann ich auf jeden Fall dann mit diesem Ansatz, nicht 21:39.920 --> 21:44.280 deterministisch eine potenzielle Lösung raten und dann überprüfen, das 21:44.280 --> 21:47.320 ist in polymeterzeit möglich, also um die Länge eines Weges zu 21:47.320 --> 21:49.220 berechnen, dann habe ich linearen Aufwand, gar kein Problem. 21:50.060 --> 21:52.640 Und ich nehme halt einfach, ich rate zufällig die beste Lösung. 21:53.360 --> 21:56.920 Und dann habe ich sofort die Antwort auf die Frage, ob ich kleiner 21:56.920 --> 21:58.060 gleich irgendeiner Schranke bin. 22:00.560 --> 22:03.360 Das Problem ist natürlich, wenn wir das jetzt versuchen 22:03.360 --> 22:07.300 deterministisch zu machen, erinnern Sie sich daran, wie wir nicht 22:07.300 --> 22:09.860 deterministische Turing-Maschinen durch deterministisch simuliert 22:09.860 --> 22:10.160 haben. 22:10.620 --> 22:14.100 Der naive Ansatz, das zu tun, war ja so, dass wir hier unseren Baum 22:14.100 --> 22:17.360 haben und dann sukzessive die verschiedenen Verzweigungen. 22:17.940 --> 22:21.880 Und wir waren ja so vorgegangen, dass wir dann schrittweise das 22:21.880 --> 22:22.800 abgearbeitet haben. 22:22.880 --> 22:25.420 Und schrittweise abarbeiten führt halt zu exponentiellem Aufwand. 22:25.920 --> 22:29.460 Das heißt, die naive deterministische Simulation so eines nicht 22:29.460 --> 22:33.660 deterministischen Algorithmus führt leider zu einem exponentiellen 22:33.660 --> 22:34.140 Aufwand. 22:35.640 --> 22:38.820 Und das heißt, das NP hat zwar immer noch das P drin für polynomiell, 22:39.300 --> 22:44.500 aber das N für Nicht-Determinismus kann uns hier eventuell etwas 22:44.500 --> 22:47.720 bringen, was mehr Aufwand verursacht. 22:48.800 --> 22:53.020 Und natürlich ist es so, dass P enthalten ist in NP, das ist klar. 22:53.560 --> 22:56.360 Jedes Problem, das ich deterministisch lösen kann im Problem der Zeit, 22:56.460 --> 22:58.460 kann ich auch nicht deterministisch lösen in der Zeit, das ist gar 22:58.460 --> 22:59.000 keine Frage. 22:59.800 --> 23:02.680 Das Interessante ist, dass man bis heute nicht weiß, ob diese beiden 23:02.680 --> 23:04.140 Klassen identisch sind oder nicht. 23:04.140 --> 23:08.460 Die Intuition sagt uns, also Intuition ist das, was ich hier oben 23:08.460 --> 23:11.360 angedeutet habe, die naive deterministische Simulation. 23:12.380 --> 23:17.060 Die Intuition sagt uns, das spricht vieles dafür, dass die beiden 23:17.060 --> 23:18.160 Klassen verschieden sind. 23:19.140 --> 23:25.240 Bis heute ist es niemandem gelungen, wirklich zu zeigen, dass der 23:25.240 --> 23:31.180 konkrete Aufwand deterministisch tatsächlich unterschiedlich ist. 23:31.660 --> 23:34.960 Ja, das klingt erstaunlich. 23:35.880 --> 23:39.120 Aber wenn einem von Ihnen etwas einfällt, das ist eine typische oder 23:39.120 --> 23:42.920 eine sehr gut funktionierende Strategie, die ist schon bei vielen 23:42.920 --> 23:46.240 Problemen erfolgreich gewesen, dass man einfach so ein offenes Problem 23:46.240 --> 23:49.240 einem Studenten gibt oder den Studenten in der großen Vorlesung und 23:49.240 --> 23:54.260 wer dann mit so wenig Vorwissen oder wenig Vorprägung in seinen 23:54.260 --> 23:57.220 Gedanken daran geht, kann vielleicht eine ganz tolle Idee haben und 23:57.220 --> 23:58.160 die richtige Lösung finden. 23:58.160 --> 24:01.640 Also wenn jemandem von Ihnen dann etwas Schönes einfällt, ich gebe 24:01.640 --> 24:05.840 Ihnen jetzt ein paar weiteren Hinweise, wie man daran gehen könnte, 24:06.120 --> 24:08.560 aber vielleicht prägt Sie das dann schon zu sehr vor und Sie finden 24:08.560 --> 24:09.320 die Lösung nicht mehr. 24:09.860 --> 24:12.040 Ich habe sie bisher nicht gefunden, hat keiner gefunden in der Welt 24:12.040 --> 24:12.340 bisher. 24:12.440 --> 24:13.880 Das ist eines der großen Probleme. 24:15.900 --> 24:20.260 Und es ist so, sagen wir auch Operations Research, wenn Sie sich 24:20.260 --> 24:23.400 anschauen, die interessanten Probleme Operations Research liegen fast 24:23.400 --> 24:24.200 alle in NP. 24:25.240 --> 24:29.280 Das heißt, da brauchen wir effiziente Verfahren. 24:30.420 --> 24:34.680 Und leider sind die meisten dieser Probleme tatsächlich ziemlich 24:34.680 --> 24:35.620 schwer in NP. 24:37.320 --> 24:43.240 Und das heißt, wenn wir zeigen könnten, P ist gleich NP, hätten wir 24:43.240 --> 24:47.240 eine ganze große Menge von Problemen auf einmal, oder für eine große 24:47.240 --> 24:50.760 Menge von Problemen auf einmal Möglichkeiten, sie effizient zu lösen 24:50.760 --> 24:53.180 beziehungsweise mit polynomialem Aufwand deterministisch. 24:53.180 --> 24:54.760 Das ist bis heute offen. 24:55.300 --> 24:57.500 Und um darüber argumentieren zu können, müssen wir so ein paar 24:57.500 --> 24:59.180 Begriffe jetzt noch kennenlernen. 25:00.100 --> 25:01.640 Also das habe ich jetzt gerade eben genannt. 25:02.400 --> 25:05.660 Wir wissen von vielen praktischen Problemen, dass sie in NP liegen, 25:07.100 --> 25:10.940 aber wir wissen eben nicht, ob man sie deterministisch in polynomialer 25:10.940 --> 25:12.680 Zeit lösen kann. 25:12.760 --> 25:16.340 Wir können sie nur nicht deterministisch polynomial lösen. 25:16.580 --> 25:17.980 Wie das Turfling-Face-Person-Problem. 25:17.980 --> 25:23.300 Also das hier oben, da sollte das TSP halt angedeutet sein. 25:24.600 --> 25:29.480 Und um darüber argumentieren zu können, wie das aussieht mit der 25:29.480 --> 25:33.180 Schwierigkeit von Problemen, müssen wir uns einen Begriff erstmal 25:33.180 --> 25:34.980 anschauen, das ist der Begriff der Reduzierbarkeit. 25:36.220 --> 25:40.120 Also, wir schauen uns zwei Probleme an und wollen uns anschauen, ob 25:40.120 --> 25:43.800 die Komplexität und die Schwierigkeit, sich zu lösen, also der 25:43.800 --> 25:47.720 Aufwand, um sie zu lösen, irgendwie in eine Beziehung gesetzt werden 25:47.720 --> 25:48.020 kann. 25:49.020 --> 25:52.620 Und das, was uns besonders interessiert, ist, ob sich der 25:52.620 --> 25:56.820 Lösungsaufwand für zwei Probleme vielleicht nur polynomial 25:56.820 --> 25:57.420 unterscheidet. 25:57.580 --> 25:59.160 Polynomial ist ja alles, was gut ist. 25:59.680 --> 26:02.320 Oder wenn es polynomial ist, sagen wir, das ist etwas, was 26:02.320 --> 26:03.180 akzeptierbar ist. 26:03.560 --> 26:06.540 Also es wird höchstens quadratisch, wenn es vorher linear war, aber 26:06.540 --> 26:09.420 ich kann es mit einem Polynom immer noch in Beziehung setzen. 26:10.420 --> 26:13.760 Und die Definition, die wir brauchen, ist jetzt so, dass wir sagen, 26:13.840 --> 26:22.860 ein Problem Q kann ich auf ein Problem P polynomialzeit reduzieren, 26:24.320 --> 26:32.820 wenn es eine Funktion F gibt, die jede Instanz dieses Problems Q auf 26:32.820 --> 26:39.260 eine Instanz des Problems P abbildet, in polynomieller Zeit, also 26:39.260 --> 26:43.300 linear oder quadratisch oder so etwas oder auch kubisch, aber eben 26:43.300 --> 26:45.900 nicht exponentielle Zeit, polynomielle Zeit. 26:47.000 --> 26:53.220 Und wenn ich außerdem in der Lage bin, die Lösung dieser so erzeugten 26:53.220 --> 26:59.820 Instanz von P, wenn ich diese Lösung auch wieder mit einer in 26:59.820 --> 27:05.880 polynomieller Zeit berechenbaren Funktion G in eine Lösung des 27:05.880 --> 27:08.660 Problems Q transformieren kann. 27:09.660 --> 27:15.120 Und das heißt doch, ich weiß natürlich nicht, wie der Aufwand ist für 27:15.120 --> 27:21.200 die Lösung des Problems P, aber wenn ich das Problem P mit irgendeiner 27:21.200 --> 27:30.240 Komplexität, ich sag mal jetzt, das ist also T P von N, lösen kann, 27:31.820 --> 27:36.640 dann ist der Aufwand, um das T Q zu berechnen, also der Aufwand von 27:36.640 --> 27:42.560 dem Q, dann sind die höchstens um den Faktor polynomiell auseinander. 27:43.180 --> 27:47.380 Das heißt, ich muss das hier vielleicht noch irgendwie hoch irgendein 27:47.380 --> 27:47.960 K nehmen. 27:52.000 --> 27:55.840 Das ist der Aufwand einfach nur mit einem polynomiellen Unterschied, 27:56.000 --> 28:00.420 beziehungsweise ich habe eben hier einen polynomiellen Aufwand, ich 28:00.420 --> 28:04.000 könnte auch sagen, das T P von N hoch K, ich könnte auch sagen, plus 28:04.000 --> 28:05.800 K, auf jeden Fall ist der Unterschied polynomiell. 28:06.780 --> 28:10.700 Also so wie ich es hier formuliert habe, hier nochmal zurück, müsste 28:10.700 --> 28:15.720 ich sagen, ich habe den Aufwand hier, das wäre irgendwas O von N hoch 28:15.720 --> 28:23.300 K, dann habe ich hier Aufwand O von N hoch L, dann hätte ich also 28:23.300 --> 28:27.900 Aufwand N hoch K, T P von N plus N hoch L, das wäre der richtige 28:27.900 --> 28:28.300 Aufwand. 28:28.680 --> 28:30.540 Das wäre dann der Aufwand für das T Q von N. 28:31.480 --> 28:35.060 Also ich kann mein Problem lösen, indem ich einfach hier rumlaufe. 28:36.560 --> 28:44.760 Und deswegen ist also der Aufwand von dem Q in Beziehung gesetzt zu 28:44.760 --> 28:48.560 dem Aufwand für das P. Und insbesondere, wenn ich also das Q auf das 28:48.560 --> 28:55.120 Problem P reduzieren kann, und wenn das P polynomiell lösbar ist, dann 28:55.120 --> 28:57.960 hätte ich hier dreimal polynomiell, das heißt, dann wäre auch das 28:57.960 --> 29:00.660 Problem Q polynomiell lösbar. 29:03.100 --> 29:07.180 Und andersherum, wenn ich zeigen könnte, Q ist nicht polynomiell 29:07.180 --> 29:10.680 lösbar, dann ist auch das Problem P nicht polynomiell lösbar. 29:12.860 --> 29:16.540 Also wenn es da einen polynomiellen Aufwand gibt zwischen P und LP, 29:17.220 --> 29:20.780 dann habe ich das Ganze polynomiell gemacht. 29:21.700 --> 29:24.720 Okay, das ist also jetzt ein wesentlicher Begriff. 29:25.200 --> 29:27.640 Und jetzt kommt ein kleines Beispiel. 29:28.100 --> 29:30.500 Man muss ja auch sehen, das ist sehr praxis- oder sehr relevant. 29:31.460 --> 29:34.440 Ganz einfaches Beispiel, Modifikation von n-Kreuz-N-Matrizen. 29:35.740 --> 29:39.940 Sie kennen vermutlich den Aufwand für n-Kreuz-N-Matrizen. 29:40.180 --> 29:43.300 Der liegt so, ich sage mal, Tmm. 29:44.140 --> 29:49.380 Matrixmultiplikation von n ist in O von n hoch 3. 29:50.780 --> 29:52.180 Schulmethode kennen Sie wahrscheinlich. 29:52.520 --> 29:54.440 Untere Schranke übrigens ist nur n². 29:54.740 --> 29:56.820 Großer Unterschied zwischen unterer und oberer Schranke. 29:57.440 --> 30:02.640 Obere Schranke kann man reduzieren hier auf n hoch 2.35. 30:03.660 --> 30:06.060 Wenn Sie mehr wissen wollen darüber, müssten Sie meine Vorlesung 30:06.060 --> 30:08.300 Effiziente Algorithmen gehen, die ich leider nicht noch mal halte, 30:08.400 --> 30:09.940 weil ich im Sommersemester keine Vorlesung mehr halte. 30:12.000 --> 30:13.520 Aber das ist ein anderes Problem. 30:13.940 --> 30:16.140 So, n hoch 3, Matrixmultiplikation. 30:16.860 --> 30:20.240 Jetzt sage ich, ich weiß gar nicht, wie man Matrizen multipliziert. 30:21.180 --> 30:25.100 Ich weiß aber, wie man Matrizen invertiert. 30:26.740 --> 30:31.480 Und das nutze ich, meine Kenntnis, um Matrizen zu invertieren, um 30:31.480 --> 30:33.220 Matrizen zu multiplizieren. 30:33.680 --> 30:37.200 Ich habe mein Problem der Multiplikation von n-Korz-n-Matrizen. 30:37.320 --> 30:40.520 Ich möchte gerne Matrizen A und B multiplizieren. 30:41.740 --> 30:46.580 Jetzt transformiere ich, indem ich eine Matrix C bilde, die so 30:46.580 --> 30:52.080 aussieht, dass ich hier so eine große 3n-Korz-3n-Matrix baue, wo A und 30:52.080 --> 30:55.480 B einfach vorkommen als Teilmatrizen. 30:55.480 --> 31:00.760 Und der Rest sind eben Nullmatrizen, Einheitsmatrizen und so weiter. 31:01.820 --> 31:06.480 Wenn ich diese Matrix mir anschaue, dann weiß ich, die Inverse dieser 31:06.480 --> 31:09.880 Matrix hat gerade folgende Gestalt. 31:09.960 --> 31:11.980 Da stehen hier auch wieder die Einheitsmatrizen. 31:12.440 --> 31:15.680 Da steht Minus A, Minus B und hier steht das Produkt von A und B. 31:16.940 --> 31:21.680 Das heißt, ich brauche nur für diese Matrix hier die Inverse zu 31:21.680 --> 31:28.060 berechnen und kann dann aus der Lösung oben rechts diese Teilmatrix 31:28.060 --> 31:28.860 herausziehen. 31:28.980 --> 31:29.780 Das ist mein Produkt. 31:31.040 --> 31:32.860 Das heißt, ich brauche gar nichts zu multiplizieren. 31:33.280 --> 31:35.340 Die Algorithmen können sich vergessen, sie brauchen nur zu 31:35.340 --> 31:35.880 invertieren. 31:36.780 --> 31:39.120 Ob das jetzt effizient ist, will ich damit nicht sagen. 31:39.720 --> 31:44.260 Aber auf jeden Fall kann man die Matrixmultiplikation auf diesem Wege 31:44.260 --> 31:44.740 erledigen. 31:45.880 --> 31:48.960 Und Sie sehen, der Aufwand in dem Fall ist kaum voneinander 31:48.960 --> 31:49.660 unterschiedlich. 31:49.660 --> 31:52.820 Also um das da einzubetten in so eine große Matrix, das ist ja kein 31:52.820 --> 31:53.500 großer Aufwand. 31:55.300 --> 31:59.740 Wenn Sie sagen, Sie zählen alle Einzelelemente, haben Sie hier halt n 31:59.740 --> 32:01.640 Quadratelemente, die Sie da reinschreiben müssen. 32:01.960 --> 32:03.260 Das ist keine große Schwierigkeit. 32:07.030 --> 32:12.130 Mit n hoch 2.35, damit meine ich, dass Sie tatsächlich in der Lage 32:12.130 --> 32:18.190 sind, den Aufwand für die Matrixmultiplikation auf Groß O von n hoch 2 32:18.190 --> 32:20.270 .35 zu reduzieren. 32:20.890 --> 32:25.550 Das heißt, Sie können mit weniger als n hoch 3 arithmetischen 32:25.550 --> 32:29.670 Operationen, Multiplikationen, Additionen und so weiter, zwei Matrizen 32:29.670 --> 32:30.410 multiplizieren. 32:31.370 --> 32:34.430 Das ist ein interessantes Verfahren, das ist nicht sehr 32:34.430 --> 32:35.210 praxisrelevant. 32:35.630 --> 32:41.330 Praxisrelevant ist ein Verfahren, bei dem Sie auf die Zeit n hoch 2.81 32:41.330 --> 32:41.750 gehen. 32:42.070 --> 32:43.610 Das ist das Verfahren von Strassen. 32:44.550 --> 32:47.030 Ein Divide-and-Conquer-Verfahren, mit dem Sie die Zeit runterdrücken 32:47.030 --> 32:47.310 können. 32:47.310 --> 32:50.770 Also das wissen wir mittlerweile alles, dass man Matrixmultiplikation 32:50.770 --> 32:55.050 normalerweise macht, nicht mit n hoch 3, sondern mit n hoch 2.81. 32:55.570 --> 32:59.290 Und wenn Sie asymptotisch das schnellste Verfahren haben wollen, 32:59.430 --> 33:02.790 nehmen Sie eins, das auf n hoch 2.35 kommt. 33:03.190 --> 33:05.110 Also Groß O von jeweils. 33:05.710 --> 33:07.690 Das muss ich natürlich eigentlich immer dazuschreiben. 33:08.030 --> 33:10.970 Groß O von, das ist der Aufwand für die Matrixmultiplikation. 33:11.410 --> 33:14.350 Führt leider jetzt viel zu weit weg von dem, was ich Ihnen hier 33:14.350 --> 33:14.830 erzählen kann. 33:14.830 --> 33:17.110 Ich muss mich beschränken auf diese formalen Hintergründe. 33:18.330 --> 33:21.370 Und das ist ein praktisches Beispiel, wo Sie sehen, was sind das für 33:21.370 --> 33:22.330 Transformationen. 33:23.110 --> 33:25.650 Das sind jetzt zwei Probleme, von denen wir wissen, die sind beide 33:25.650 --> 33:26.270 polynomiell. 33:26.670 --> 33:28.970 Sie können natürlich irgendwelche beliebigen Probleme hernehmen, 33:29.050 --> 33:30.070 können die so transformieren. 33:31.810 --> 33:35.490 Und wenn das geht, haben Sie dann einen polynomiellen Aufwand, um hin 33:35.490 --> 33:36.110 und her zu laufen. 33:37.210 --> 33:42.070 Und jetzt kommt ein ganz wesentlicher Begriff, der dazu dient, 33:42.230 --> 33:46.570 festzustellen, wann ist ein Problem eigentlich schwer. 33:47.050 --> 33:49.970 Und zwar ist schwer im Sinne von NP. 33:51.810 --> 33:54.650 So, im Sinne von Problem, die ich mit nicht deterministischen 33:54.650 --> 33:56.490 Turingmaschinen problematischer Zeit berechnen kann. 33:57.930 --> 34:00.450 Und jetzt gibt es davor noch ganz kurz eine Frage. 34:01.250 --> 34:03.830 Das habe ich ja gerade beantwortet. 34:04.270 --> 34:04.970 NP schwer. 34:06.050 --> 34:07.990 Nennen wir jetzt ein Problem X. 34:09.330 --> 34:16.570 Wenn wir in der Lage sind, jedes beliebige Problem aus NP, A, B, C, 34:16.690 --> 34:23.090 was immer wir an Problemen dort haben, jedes Problem, Polymialzeit zu 34:23.090 --> 34:24.530 reduzieren auf X. 34:26.850 --> 34:28.210 Was heißt das? 34:28.930 --> 34:34.710 Wenn wir jedes Problem, Polymialzeit reduzieren können auf X, dann 34:34.710 --> 34:37.550 heißt das doch nach dem, was wir gerade auf der vorigen Folie gesehen 34:37.550 --> 34:44.550 haben, wenn wir das Problem X, dieses eine Problem, in Polymialzeit 34:44.550 --> 34:50.730 lösen könnten deterministisch, könnten wir alle Probleme aus NP in 34:50.730 --> 34:52.110 Polymialzeit reduzieren. 34:52.870 --> 34:57.750 Ein gewaltiger Fortschritt gegenüber dem Problem, was ich Ihnen 34:57.750 --> 34:59.130 zunächst genannt habe. 34:59.490 --> 35:02.770 Ich sagte, wir wollen wissen, sind P und NP unterschiedlich? 35:02.770 --> 35:06.290 Da müssten wir etwas sagen über beliebige Probleme in NP. 35:08.950 --> 35:13.590 Kann ich jedes Problem aus NP irgendwie in deterministischer Zeit 35:13.590 --> 35:15.730 polynomial lösen? 35:16.230 --> 35:19.670 Jetzt können wir das Ganze reduzieren auf ein Problem X. 35:20.810 --> 35:23.290 Wir brauchen nur dieses eine Problem anzugucken, X. 35:23.910 --> 35:27.950 Wenn wir das in Polymialzeit deterministisch lösen können, können wir 35:27.950 --> 35:31.350 alle Probleme aus NP auch in Polymialzeit lösen. 35:31.930 --> 35:32.370 Fantastisch. 35:32.810 --> 35:36.690 Wir haben das große Problem reduziert darauf, ein einziges Problem 35:36.690 --> 35:37.710 genauer zu betrachten. 35:40.750 --> 35:44.170 Nun könnte es noch andere Probleme geben, bei denen man sich überlegt, 35:44.270 --> 35:46.370 na ja, vielleicht ist das auch in der drin. 35:47.170 --> 35:49.730 Dann brauche ich nur zu sagen, also nehmen wir mal an, wir haben 35:49.730 --> 35:53.230 gezeigt, dass ein Problem X NP schwer ist. 35:53.890 --> 35:56.050 Dann kann ich mir irgendein anderes hernehmen, Problem Y. 35:57.250 --> 36:01.730 Und wenn ich zeigen kann, das hier ist kleiner gleich P, also 36:01.730 --> 36:07.950 polynomial reduzierbar, oder X ist reduzierbar auf Y, dann ist das 36:07.950 --> 36:09.010 hier auch schon NP schwer. 36:10.130 --> 36:14.150 Jetzt brauche ich nur noch ein Problem herzunehmen und zu zeigen, ich 36:14.150 --> 36:19.210 kann dieses Problem, von dem ich weiß, es ist NP schwer, auf ein 36:19.210 --> 36:23.970 anderes Problem reduzieren, dann ist das auch NP schwer. 36:25.450 --> 36:30.110 Das heißt, ich kann auf einmal für eine Reihe von Problemen, die kann 36:30.110 --> 36:33.570 ich mir angucken und feststellen, na ja, die sind irgendwie alle NP 36:33.570 --> 36:33.930 schwer. 36:34.250 --> 36:36.670 Das heißt, ich brauche mich auf die nur zu konzentrieren. 36:37.650 --> 36:40.550 Vielleicht finde ich ja irgendeines dieser Probleme, dass ich dann 36:40.550 --> 36:44.470 einen Polynomial-Zeitalgorithmus finden kann. 36:46.030 --> 36:49.970 Das ist eine gewaltige Einschränkung des Aufwandes, aber natürlich 36:49.970 --> 36:56.450 habe ich zunächst mal die gewaltige Aufgabe zu lösen, dass ich jedes 36:56.450 --> 37:00.170 Problem aus NP auf dieses X hier erst mal reduzieren muss. 37:02.130 --> 37:05.090 Zunächst mal sieht man also, wie gesagt, ein NP-schweres Problem ist 37:05.090 --> 37:08.690 mindestens so schwer wie jedes beliebige Problem aus NP. 37:10.130 --> 37:13.750 Und das Schöne ist, dass wir dafür Beispiele haben, das kommt gleich. 37:14.850 --> 37:18.010 Zunächst mal sagen wir, wir hatten ja gerade eben dieses Bild gehabt, 37:18.110 --> 37:24.530 NP, und hier dieses Problem X, die mussten alle darauf reduziert 37:24.530 --> 37:25.150 werden können. 37:26.150 --> 37:31.930 Und wenn jetzt dieses Problem X selber in NP ist, dann ist es ein 37:31.930 --> 37:36.770 Problem in NP, das mindestens so schwer ist wie jedes andere in NP. 37:37.270 --> 37:40.350 Das heißt, das ist eines der schwersten Probleme in NP. 37:41.470 --> 37:44.310 Das Dumme ist, wir wissen mittlerweile von vielen praktischen 37:44.310 --> 37:48.820 Problemen, gerade den Problemen, die Sie im OR-Bereich betrachten, das 37:48.820 --> 37:53.260 sind überwiegend NP-schwere Probleme, beziehungsweise in dem Fall NP 37:53.260 --> 37:54.420 -vollständige Probleme. 37:54.700 --> 37:57.740 Die liegen in NP und gehören zu den schwersten Problemen in NP. 37:57.920 --> 37:59.680 Das TSP zum Beispiel ist so ein Problem. 38:02.630 --> 38:11.650 Das wurde 1971, also vor 45 Jahren, von Stephen Cook definiert und 38:11.650 --> 38:18.130 seitdem hat man sehr viele Probleme nachweisen können, dass sie NP 38:18.130 --> 38:18.730 -schwer sind. 38:18.910 --> 38:24.350 Das Erste war dieses Erfüllbarkeitsproblem der Aussagenlogik. 38:24.390 --> 38:26.350 Was ist das Erfüllbarkeitsproblem der Aussagenlogik? 38:26.910 --> 38:36.510 Sie haben irgendeine Formel, X1 oder X2 und irgendwas anderes und so 38:36.510 --> 38:36.810 weiter. 38:36.810 --> 38:38.730 Irgendeine Formel der Aussagenlogik. 38:39.430 --> 38:45.790 Und Sie suchen nach einer Belegung der Variablen X1 bis Xn, sodass 38:45.790 --> 38:47.690 diese Formel wahr ist. 38:48.070 --> 38:49.210 Kann sie erfüllt werden? 38:50.310 --> 38:51.570 Das ist das Erfüllbarkeitsproblem. 38:52.450 --> 38:57.010 Und zwar möchte man für eine beliebige Formel der Aussagenlogik, in 38:57.010 --> 39:00.010 der Regel guckt man sich nur die an in konjunktiver Normalform. 39:00.770 --> 39:02.790 Sie wissen, was konjunktive Normalform ist, habe ich hier gerade 39:02.790 --> 39:03.310 angedeutet. 39:03.310 --> 39:07.210 Sie haben disjunktive Klauseln, die durch Konjunktionen verbunden 39:07.210 --> 39:07.390 sind. 39:07.430 --> 39:09.310 Das haben Sie alles im Grundlagen der Informatik 1 gelernt. 39:10.450 --> 39:12.010 Ob sie erfüllbar ist oder nicht? 39:14.470 --> 39:17.350 Das ist nachgewiesen worden als NP-vollständig. 39:17.430 --> 39:23.530 Im Prinzip heißt das, Sie können jedes NP-Problem durch eine 39:23.530 --> 39:26.250 aussagenlogische Formel charakterisieren. 39:26.670 --> 39:29.950 Das ist gar nicht so weit hergeholt, dass Sie das, was in dem Problem 39:29.950 --> 39:31.950 formuliert ist, in Aussagenlogik formulieren. 39:35.810 --> 39:38.150 Sie formulieren das als Entscheidungsproblem. 39:39.330 --> 39:42.790 Dann müssen Sie eine Belegung von Variablen finden, die 39:42.790 --> 39:47.370 problemspezifisch sind, sodass Sie die Entscheidung Ja oder Nein 39:47.370 --> 39:48.050 treffen können. 39:49.750 --> 39:52.850 Das ist naheliegend, dass das so geht. 39:53.670 --> 39:56.270 Genaueres dazu finden Sie in dem schönen Buch, was Sie geschrieben 39:56.270 --> 39:56.550 haben. 39:56.750 --> 39:59.630 Und natürlich auch in viel anderer Literatur, insbesondere in der 39:59.630 --> 40:00.850 Originalliteratur von Cook. 40:02.090 --> 40:04.770 Beweis dazu haben wir in das Buch auch mit aufgenommen. 40:06.110 --> 40:08.030 Das ist das Erfüllbarkeitsproblem der Aussagenlogik. 40:08.110 --> 40:13.450 Dann gibt es noch viele andere Probleme, wie das TSP-Problem, zum 40:13.450 --> 40:14.530 Beispiel, das ich schon genannt hatte. 40:14.990 --> 40:19.170 Ich möchte eine Rundreise kürzester Länge oder kleinstem Gewicht 40:19.170 --> 40:19.670 bestimmen. 40:20.250 --> 40:26.930 Beziehungsweise ich frage, gibt es einen Weg, einen Path P mit Kosten 40:26.930 --> 40:29.650 von P, 40:33.650 --> 40:35.050 kleiner gleich K. 40:35.930 --> 40:38.230 Das ist das Entscheidungsproblem für das Travelling Salesperson 40:38.230 --> 40:38.550 Problem. 40:39.550 --> 40:41.130 Kommen wir gleich nochmal auf diese Art Fragen. 40:42.910 --> 40:45.550 Für das kann man das auch zeigen oder für Projektplanung. 40:45.550 --> 40:48.750 Projektplanung kennen Sie alle als typische Aufgaben von 40:48.750 --> 40:49.610 Wirtschaftsingenieuren. 40:50.610 --> 40:54.250 Projektplanung mit beschränkten Ressourcen, auch ein nettes, typisches 40:54.250 --> 40:54.750 Problem. 40:56.010 --> 41:00.490 Ist NP vollständig, wenn Sie noch zeitliche Mindest- und 41:00.490 --> 41:04.230 Maximalabstände, insbesondere wenn Sie noch zeitliche Maximalabstände 41:04.230 --> 41:08.310 da mit drin haben, zwischen einzelnen Vorgängen in so einem Ablauf. 41:09.350 --> 41:12.150 Verschiedene Vorgänge, die ablaufen und Sie haben noch zeitliche 41:12.150 --> 41:13.470 Mindest - und Maximalabstände. 41:13.470 --> 41:18.930 Dann ist allein das Finden einer gültigen Lösung schon ein NP 41:18.930 --> 41:20.150 -vollständiges Problem. 41:22.150 --> 41:26.910 Also nicht nur die beste Lösung zu finden, sondern auch noch überhaupt 41:26.910 --> 41:30.390 eine gültige Lösung zu finden, ist dann schon NP-schwer. 41:33.750 --> 41:37.230 Bei so vielen schweren Problemen macht es Sinn, eine kleine Pause zu 41:37.230 --> 41:37.410 machen. 41:37.410 --> 41:42.070 Wirklich eine kleine Pause heute, damit Sie sich kurz erholen können 41:42.070 --> 41:46.630 von diesen faszinierenden, gewaltigen Erkenntnissen, die Sie jetzt 41:46.630 --> 41:48.090 gerade präsentiert bekommen haben. 45:00.510 --> 45:06.130 So, es kam gerade die Frage, ich sollte nochmal diese Transformation 45:06.130 --> 45:08.950 für die Matrixmultiplikation wiederholen. 45:09.510 --> 45:11.990 Lassen Sie uns das zu der Pause nochmal kurz nutzen. 45:12.670 --> 45:19.130 Genau, da hatten wir das Beispiel mit der Matrixmultiplikation. 45:19.910 --> 45:25.330 Also Sie haben Matrizen gegeben, A und B. 45:26.210 --> 45:28.150 Das sind Ihre beiden Matrizen A und B. 45:28.870 --> 45:37.770 Und Sie bauen aus A und B eine Matrix C, in der Sie A und B an diesen 45:37.770 --> 45:39.230 Stellen reinschreiben. 45:39.230 --> 45:41.730 Eine 3n x 3n Matrix. 45:42.110 --> 45:44.070 A und B sind n x n Matrizen. 45:44.950 --> 45:46.690 Und dann invertieren Sie die Matrix. 45:48.050 --> 45:53.330 Und wenn Sie sich eine Matrix dieser Gestalt anschauen, dann hat die 45:53.330 --> 45:54.890 Invertierte nun mal diese Gestalt. 45:54.990 --> 45:59.650 Sie können die beiden Matrizen C und C hoch minus 1 multiplizieren und 45:59.650 --> 46:04.090 stellen fest, das Produkt dieser beiden Matrizen hier ist gerade die 46:04.090 --> 46:04.970 Einheitsmatrix. 46:07.330 --> 46:15.030 Das heißt, dieses rechts ist die Inverse und hier oben, wenn Sie also 46:15.030 --> 46:19.890 invertieren können, entsteht bei der Inversion dieser Matrix da oben 46:19.890 --> 46:21.930 rechts das Produkt von A und B. 46:24.110 --> 46:26.890 Das heißt, Sie kümmern sich gar nicht um die Multiplikation von 46:26.890 --> 46:30.190 Matrizen, Sie kümmern sich nur darum, wie Sie eine Matrix invertieren 46:30.190 --> 46:32.510 können, mit welchem Verfahren auch immer. 46:33.010 --> 46:36.670 Und Sie wissen, am Ende muss eine Matrix rauskommen, bei der ich 46:36.670 --> 46:40.630 einfach hier diese obere rechte n x n Matrix rausnehme. 46:40.730 --> 46:43.650 Das ist mein Produkt der beiden Matrizen A und B. 46:44.930 --> 46:48.610 Insofern nutze ich hier die Inversion von Matrizen, um am Ende ein 46:48.610 --> 46:50.990 Produkt von Matrizen tatsächlich zu bekommen. 46:52.430 --> 46:55.870 Aber ich brauche hier kein direktes Verfahren, um die beiden Matrizen 46:55.870 --> 46:56.470 zu multiplizieren. 46:56.530 --> 47:00.310 Das mache ich allein über die Inversion und eben die Einbettung in 47:00.310 --> 47:01.290 eine größere Matrix. 47:01.930 --> 47:05.290 Okay, dann gehen wir auf... 47:07.130 --> 47:12.290 Das war diese Folie, wir waren da schon ein bisschen weiter... 47:13.030 --> 47:16.290 Genau, die Folie hatten wir uns gerade als letztes angeschaut. 47:16.670 --> 47:19.050 Jetzt wollen wir das ein bisschen konkreter machen. 47:19.190 --> 47:23.930 Also man kennt jetzt viele NPE-vollständige Probleme, unzählig viele, 47:24.230 --> 47:26.170 sehr viele Probleme sind NPE-vollständig. 47:26.170 --> 47:32.270 Und die Vermutung ist, dass es keinen Algorithmus gibt, der NPE 47:32.270 --> 47:35.210 -vollständige Probleme in der Zeit löst. 47:35.850 --> 47:37.070 Man weiß es aber nicht. 47:37.390 --> 47:38.930 Das konnte von niemandem bewiesen werden. 47:39.410 --> 47:44.950 Es gibt durchaus andere Komplexitätsklassen, von denen man meinte, sie 47:44.950 --> 47:48.890 würden eine vollständige Hierarchie bilden, richtig eine Folge von 47:48.890 --> 47:51.310 immer schwierigeren Komplexitätsklassen. 47:51.310 --> 47:53.690 Dann hat man festgestellt, die fallen alle zusammen. 47:54.030 --> 47:56.730 Damit war also eine ganze Reihe von Überlegungen auf einmal hinfällig, 47:57.050 --> 47:58.290 weil die zusammengefallen sind. 47:58.370 --> 48:00.750 Es gibt also Beispiele, wo man zunächst mal meinte, die sind 48:00.750 --> 48:02.690 unterschiedlich, sie waren aber identisch. 48:03.290 --> 48:04.650 Hier wissen wir es bis heute nicht. 48:04.750 --> 48:05.950 Wie gesagt, das ist immer noch ein Problem. 48:07.630 --> 48:11.730 Wenn man zeigen will, dass ein Problem vermutlich nicht polymerlösbar 48:11.730 --> 48:16.850 ist, dann verwendet man eben diese Folgerung, die ich schon nannte. 48:16.850 --> 48:22.310 Ich nehme ein beliebiges NP-vollständiges Problem her und reduziere es 48:22.310 --> 48:27.130 auf dieses Problem P, von dem ich zeige, dass ein Problem P vermutlich 48:27.130 --> 48:29.090 nicht polymerlösbar ist. 48:30.910 --> 48:34.370 Und dann muss ich also zeigen, dass ich ein beliebiges vollständiges 48:34.370 --> 48:37.070 Problem auf dieses Problem, für das es mich interessiert, reduzieren 48:37.070 --> 48:37.270 kann. 48:37.470 --> 48:38.590 Wir machen das gleich an einem Beispiel. 48:40.050 --> 48:44.230 Und hier zur Beziehung dieser verschiedenen Klassen auf der Folie, die 48:44.230 --> 48:47.170 Sie vorliegen haben, steht das NP-schwer gar nicht mehr dabei, ich 48:47.170 --> 48:48.770 habe das lieber noch dazugefügt. 48:49.490 --> 48:53.390 Also wir haben die Klasse NP, wir haben die Klasse P. P ist natürlich 48:53.390 --> 48:56.750 hier, das wissen wir, vollständig enthalten in NP. 48:57.970 --> 49:03.010 Wir wissen jetzt, es gibt Probleme, die sind NP-schwer. 49:03.530 --> 49:06.210 Das ist dieser ganze Bereich, die sind alle NP-schwer. 49:06.850 --> 49:11.370 Und dann gibt es Probleme, die sind gleichzeitig in NP. 49:12.410 --> 49:14.190 Das sind die NP-Vollständigen. 49:15.450 --> 49:18.170 Die habe ich hier disjunkt von P gezeichnet. 49:18.830 --> 49:20.770 Das ist halt etwas, was wir nicht wissen. 49:21.650 --> 49:22.990 Sind die wirklich unterschiedlich? 49:24.370 --> 49:29.050 Es mag viele Probleme geben, die außerhalb von NP liegen, die NP 49:29.050 --> 49:34.150 -schwer sind, aber vielleicht deutlich schwerer als NP. 49:35.250 --> 49:39.550 Das geht ja noch viel weiter mit den Komplexitätsklassen. 49:40.190 --> 49:43.250 Also das ist so der Zusammenhang zwischen diesen Klassen, die ich 49:43.250 --> 49:44.910 Ihnen gerade dargestellt habe. 49:47.190 --> 49:49.990 Und ist auch im Buch sehr ausführlich alles beschrieben. 49:50.670 --> 49:53.650 Jetzt gibt es noch ein paar weitere Komplexitätsklassen. 49:53.750 --> 49:55.250 Wir kommen gleich noch auf ein konkretes Beispiel. 49:55.750 --> 50:01.250 Aber nochmal eine weitere Klasse, die mit polynomiellem Platz 50:01.250 --> 50:02.170 berechenbar funktioniert. 50:02.190 --> 50:04.010 Wir haben ja Zeit- und Platzkomplexität. 50:04.730 --> 50:06.870 Das wäre die Klasse PSPACE. 50:08.750 --> 50:13.870 Interessanterweise in NP, da liegen alle die Probleme, die Sie mit 50:13.870 --> 50:17.790 logarithmischem Platz berechnen können. 50:20.410 --> 50:22.230 Also nicht deterministisch. 50:22.870 --> 50:26.770 Wenn Sie polynomiellen Platz zulassen, haben Sie PSPACE. 50:28.390 --> 50:31.250 Sie erinnern sich an die linearbeschränkten Automaten. 50:32.150 --> 50:34.250 Da hatten wir einen linearbeschränkten Platz. 50:35.150 --> 50:37.350 Das liegt also in dieser Klasse mit drin. 50:38.130 --> 50:40.530 Kann aber auch, wenn wir sagen, nicht nur linear, sondern auch 50:40.530 --> 50:42.230 quadratisch oder kubisch oder sowas. 50:42.570 --> 50:43.630 Alles noch in PSPACE. 50:45.690 --> 50:46.670 Weitere Klassen. 50:47.330 --> 50:49.270 EXPTIME, exponentielle Zeit. 50:50.850 --> 50:51.970 Deterministische Turingmaschine. 50:53.510 --> 50:56.110 Und Zeit 2 hoch N hoch K. 50:58.010 --> 51:00.610 Das heißt, richtig schwer. 51:01.470 --> 51:02.610 Richtig aufwendig. 51:04.270 --> 51:06.390 Und das Ganze könnten Sie auch noch nicht deterministisch machen. 51:07.670 --> 51:08.950 Noch aufwendiger. 51:12.560 --> 51:16.120 Und dann können Sie auch noch sagen, ich kann ja auch EXPSPACE 51:16.120 --> 51:16.700 betrachten. 51:17.320 --> 51:18.360 Exponentiellen Platz. 51:20.160 --> 51:21.620 Dann haben Sie noch eine weitere Klasse. 51:22.380 --> 51:29.380 Und das Ganze ist dann insgesamt eine Hierarchie von einer ganzen 51:29.380 --> 51:33.880 Reihe von Komplexitätsgraden. 51:34.280 --> 51:38.080 P, NP, PSPACE, EXPTIME, EXPSPACE und so weiter. 51:38.640 --> 51:46.420 Es ist klar, dass zwischen EXPTIME und P natürlich eine echte 51:46.420 --> 51:48.340 Teilmenge von EXPTIME ist. 51:49.700 --> 51:53.200 Also deterministisch exponentielle Zeit ist natürlich eine deutlich 51:53.200 --> 51:56.800 größere Menge, als die, die ich mit Polymerzeit berechnen kann. 51:57.580 --> 52:01.480 Aber wo genau die Grenze ist hier, das ist offen. 52:02.760 --> 52:05.680 Also wo es echt enthalten ist und wo nicht. 52:06.220 --> 52:06.780 Da ist vieles offen. 52:06.820 --> 52:07.760 Ein paar Sachen sind bekannt. 52:08.160 --> 52:09.800 Da fehlt mir leider die Zeit, darauf einzugehen. 52:10.180 --> 52:12.520 Ganz wichtig ist, das geht natürlich beliebig weiter. 52:13.700 --> 52:16.940 Sie können nach EXPTIME Super Exponential Zeit machen. 52:16.940 --> 52:19.120 Sie können ja die Potenzen beliebig hoch machen. 52:20.960 --> 52:25.280 Und das heißt, da gibt es noch einiges oben drüber. 52:26.300 --> 52:29.680 Wir wollen gerne möglichst alles in diesem kleinen Bereich machen, 52:29.800 --> 52:34.220 hier im Bereich P. Leider ist uns das bei vielen praktischen Problemen 52:34.220 --> 52:35.420 nicht vergönnt. 52:35.760 --> 52:40.740 Und wenn wir alleine noch für NP einigermaßen vernünftige 52:40.740 --> 52:43.300 Vorgehensweisen hätten, wäre das gut. 52:43.300 --> 52:46.600 Und das werde ich Ihnen gleich noch ein bisschen darauf eingehen. 52:46.900 --> 52:51.140 Aber das zu dieser Hierarchie der Komplexitätsklassen, da kann man 52:51.140 --> 52:52.500 eine ganze Vorlesung drüber halten. 52:52.960 --> 52:55.960 Nur über die Beziehungen zwischen diesen verschiedenen 52:55.960 --> 52:56.300 Komplexitätsklassen. 52:57.260 --> 53:00.860 Es gibt darunter, unterhalb von P, gibt es auch noch wieder kleinere 53:00.860 --> 53:03.420 Klassen, wo man das noch weiter einschränken kann. 53:03.880 --> 53:05.200 Auch darauf kann ich hier nicht eingehen. 53:05.860 --> 53:10.220 Und ich möchte jetzt ein Beispiel Ihnen zeigen, wie man ein Problem 53:10.220 --> 53:11.800 auf ein anderes reduzieren kann. 53:11.800 --> 53:14.920 Für die Matrixmultiplikation und die Inversion haben wir das schon 53:14.920 --> 53:15.300 gesehen. 53:15.700 --> 53:18.320 Aber jetzt mal für ein NP-schweres Problem. 53:19.300 --> 53:24.700 Und jetzt will ich Ihnen zeigen, wie man das Dreisatzproblem auf das 53:24.700 --> 53:26.040 Klickenproblem reduzieren kann. 53:26.100 --> 53:29.040 Das Dreisatzproblem hat mit Fernsehen nichts zu tun. 53:29.520 --> 53:30.560 Das ist kein Fernsehsender. 53:31.300 --> 53:35.420 Das Dreisatzproblem besteht darin, es geht um das 53:35.420 --> 53:37.600 Erfüllbarkeitsproblem der Aussagenlogik. 53:38.520 --> 53:40.860 Ich habe also beliebig viele Variablen. 53:41.700 --> 53:44.860 X1 bis Xn oder hier in dem Beispiel X1 bis X4. 53:46.000 --> 53:52.100 Und meine Formel liegt in konjunktiver Normalform vor. 53:57.330 --> 54:04.150 Aber in jeder disjunktiven Klausel finden Sie nur drei Literale. 54:04.990 --> 54:12.030 Ein Literal ist eine Variable, entweder direkt so oder negiert. 54:12.510 --> 54:16.770 Ich kann ja eine Variable X angeben oder X-Strich, X-Quer, also X 54:16.770 --> 54:17.210 negiert. 54:18.250 --> 54:19.110 Also nicht X. 54:22.170 --> 54:26.230 Ein Beispiel wäre hier, wenn ich meine Klauseln... 54:26.230 --> 54:27.230 Also sieht man ja hier. 54:27.470 --> 54:29.730 Da kommt X1 vor, da kommt X1-Strich vor. 54:29.730 --> 54:33.750 Da kommt X2 vor, X2-Strich kommt gar nicht vor. 54:34.710 --> 54:38.050 X3-Strich kommt da vor, hier haben wir doch ein X4, das kommt auch X4 54:38.050 --> 54:38.550 -Strich vor. 54:38.750 --> 54:41.250 Also die kommen sowohl negiert als auch nicht negiert vor. 54:42.550 --> 54:45.430 Aber in jeder disjunktiven Klausel nur drei Literale. 54:47.430 --> 54:51.530 Das Interessante ist, selbst in dieser Form ist das ganze NP 54:51.530 --> 54:52.450 vollständig. 54:52.450 --> 54:58.230 Wenn Sie aber auf zwei Satz gehen, das heißt nur zwei Literale pro 54:58.230 --> 55:02.250 disjunktiver Klausel, liegt das ganze NP. 55:03.670 --> 55:05.750 Ist in quadratischer Zeit dann lösbar. 55:07.810 --> 55:11.810 Das heißt, von zwei auf drei in den Klauseln bringt uns schon eine 55:11.810 --> 55:15.410 deutliche Erhöhung des Aufwandes. 55:15.970 --> 55:19.290 Und jetzt wollen wir sehen, wie wir das Drei-Satz-Problem, von dem wir 55:19.290 --> 55:21.410 annehmen, das ist... 55:23.470 --> 55:26.130 Wir nehmen das jetzt an, man kann es zeigen. 55:26.930 --> 55:30.230 Ich kann das Satzproblem, das Erfüllbarkeitsproblem der Aussagenlogik, 55:30.290 --> 55:34.550 von dem wir jetzt wissen, habe ich Ihnen gesagt, dass es NP 55:34.550 --> 55:38.470 -vollständig ist oder NP-schwer ist, das kann ich reduzieren aufs Drei 55:38.470 --> 55:39.070 -Satz -Problem. 55:39.070 --> 55:43.090 Ich kann also jede Aussagenlogische Formel in diese Form bringen, 55:43.210 --> 55:46.330 sodass ich nur drei Literale pro disjunktiver Klausel habe. 55:47.430 --> 55:50.010 Und jetzt will ich das reduzieren auf das Klicken-Problem. 55:50.090 --> 55:51.170 Was ist das Klicken-Problem? 55:53.570 --> 55:58.410 Ein Klicken-Problem ist das Problem, für einen beliebigen 55:58.410 --> 56:06.330 ungerichteten Graphen festzustellen, häufig wollen wir die maximale 56:06.330 --> 56:10.650 Klicke haben, jetzt frage ich nur, ich habe ein K aus N, und ich 56:10.650 --> 56:14.250 frage, gibt es eine Klicke, also einen vollständig verbundenen 56:14.250 --> 56:19.510 Teilgraf, der Größe K in diesem Graphen, für K gleich 3 wäre das 56:19.510 --> 56:21.270 dieser rot markierte Teilgraf. 56:21.810 --> 56:24.690 Der ist vollständig verbunden, jeder Knoten mit jedem anderen 56:24.690 --> 56:29.210 verbunden, hat die Größe 3, hat in dem Fall für K gleich 3 also eine 56:29.210 --> 56:33.330 sehr einfache Struktur, und Sie sehen, das ist die einzige derartige 56:33.330 --> 56:36.910 Klicke in diesem Graphen, der Größe 3. 56:37.350 --> 56:41.130 Klicken der Größe 2 haben Sie hier ganz viele, jede Kante zwischen 56:41.130 --> 56:43.410 zwei Knoten ist eine Klicke der Größe 2. 56:44.010 --> 56:46.630 Klicke der Größe 3 haben Sie hier nur eine, Klicken der Größe 4 finden 56:46.630 --> 56:47.170 Sie hier nicht. 56:48.810 --> 56:49.910 Das ist das Klicken-Problem. 56:50.750 --> 56:53.250 Jetzt will ich zeigen, dieses Problem ist ein p-schwer. 56:54.470 --> 56:58.610 Dadurch, dass ich Ihnen das Dreisatzproblem reduziere auf das Klicken 56:58.610 --> 57:02.170 -Problem, Also, wie machen wir das? 57:02.570 --> 57:08.310 Wir haben eine Instanz des Dreisatzproblems, das heißt wir haben hier 57:08.310 --> 57:09.350 eine Formel, 57:13.080 --> 57:17.540 in dem Fall C, gleich C1 bis CM, meine C1 bis CM sind meine Klauseln, 57:18.500 --> 57:20.280 da sind jeweils n Variablen drin, 57:23.520 --> 57:29.480 und diese C, I, J in diesen einzelnen Klauseln sind also eine Eingabe 57:29.480 --> 57:33.580 für Dreisatz, sind also eine Instanz meines Problems hier. 57:34.040 --> 57:37.580 Ich gebe Ihnen ein konkretes Beispiel, hier habe ich also genau das, 57:37.640 --> 57:39.980 was ich vorher schon hatte, oder was ähnliches, nicht genau das, ein 57:39.980 --> 57:46.760 anderes Problem hier, hier habe ich nur drei literale X1, X2, X3, und 57:46.760 --> 57:50.060 die treten in drei Klauseln auf, disjunktive Klauseln, die hier 57:50.060 --> 57:55.860 angegeben sind, und jetzt will ich zu dieser Problemstellung, zu 57:55.860 --> 58:03.040 dieser Formel, einen Graphen konstruieren, bei dem ich darüber, dass 58:03.040 --> 58:06.740 ich frage, gibt es eine Clique irgendeiner bestimmten Größe, eine 58:06.740 --> 58:10.720 Antwort finde auf die Frage, gibt es eine Belegung bei einer Variablen 58:10.720 --> 58:15.200 X1 bis X3, so dass diese Formel erfüllt werden kann. 58:16.240 --> 58:19.340 Wann kann eine solche Formel überhaupt erfüllt werden? 58:19.620 --> 58:26.260 Doch immer dann, wenn ich jede einzelne Klausel, C1, C2, C3, also 58:26.260 --> 58:28.900 jeden dieser disjunktiven Terme, erfüllen kann. 58:29.840 --> 58:33.720 Ich muss also in jeder dieser Klauseln eine Variable finden, oder ein 58:33.720 --> 58:37.940 Literal finden, das ich auf 1 setzen, das auf 1 gesetzt werden kann, 58:38.360 --> 58:42.140 und wenn das in jeder Klausel möglich ist, dann habe ich eine Belegung 58:42.140 --> 58:47.460 meiner Variablen gefunden, so dass jede dieser drei Klauseln erfüllt 58:47.460 --> 58:50.180 werden kann, damit auch die Konjunktion der drei Klauseln. 58:51.240 --> 58:57.680 Also suche ich jetzt nach variablen Belegungen der X1, X2, X3, so dass 58:57.680 --> 59:00.720 möglichst jede der drei Klauseln erfüllt wird. 59:01.780 --> 59:02.640 Wie mache ich das? 59:03.560 --> 59:07.320 Ich erzeuge einen Graphen, das steht hier oben, es ist definiert, wie 59:07.320 --> 59:07.840 ich das mache. 59:08.790 --> 59:13.700 Ich definiere Knoten, für jedes Literal, das auftaucht, einen Knoten, 59:14.360 --> 59:21.200 und jetzt verbinde ich die Knoten, die gleichzeitig den Wert 1 haben 59:21.200 --> 59:22.740 können, durch eine Kante. 59:23.840 --> 59:25.680 Nehmen wir uns mal das X1 hierher. 59:27.020 --> 59:33.200 Das X1 kann sicherlich nicht gleichzeitig mit dem Literal C2 1 1 59:33.200 --> 59:39.200 werden, das ist X1' Aber es könnte gleichzeitig mit dem Literal C2 2, 59:39.980 --> 59:45.180 das ist nämlich das X2, gleichzeitig wahr werden. 59:46.240 --> 59:52.740 Und das X2 kann zum Beispiel gleichzeitig wie das X3 wahr werden. 59:53.420 --> 59:55.920 Dieser schreckliche senkrechte Strich, der stört mich wirklich. 59:56.680 --> 59:58.320 An dieser Stelle muss ich ihn wirklich wegmachen. 59:59.200 --> 01:00:10.040 Und auf diese Art und Weise können wir die Knoten verbinden, und zwar 01:00:10.040 --> 01:00:14.120 immer Knoten in verschiedenen Ebenen dieses Graphen. 01:00:14.860 --> 01:00:17.580 Das sind hier alle die Kanten, die sich ergeben. 01:00:18.920 --> 01:00:24.140 Das heißt, jede Kante in diesem Fall sagt aus, diese zwei Literale 01:00:24.140 --> 01:00:26.180 können gleichzeitig 1 sein. 01:00:28.140 --> 01:00:33.820 So, jetzt möchte ich gerne, dass M-Klauseln gleichzeitig wahr werden. 01:00:37.240 --> 01:00:42.260 Das heißt, ich kann natürlich erst mal diesen Graphen in polynomialer 01:00:42.260 --> 01:00:45.460 Zeit erzeugen, das ist kein Problem, ich brauche ja nur meine Formel 01:00:45.460 --> 01:00:46.040 durchzugucken. 01:00:46.800 --> 01:00:51.520 Jetzt wähle ich K, also dieses bei der Clique, die Frage, gibt es eine 01:00:51.520 --> 01:00:53.880 Clique der Größe K? 01:00:56.040 --> 01:00:57.640 Das wähle ich gleich M. 01:01:00.080 --> 01:01:03.480 Jetzt nehme ich mal an, ich kann für diesen Graphen eine Clique der 01:01:03.480 --> 01:01:04.580 Größe M finden. 01:01:05.980 --> 01:01:11.880 Eine Clique der Größe M heißt, ich habe hier eine Teilmenge des 01:01:11.880 --> 01:01:17.060 Graphen gefunden, und alle die Knoten da drin sind miteinander 01:01:17.060 --> 01:01:17.680 verbunden. 01:01:19.480 --> 01:01:25.520 Das heißt, ich kann das ja, da das ja alles Literale bezeichnet hier, 01:01:25.580 --> 01:01:27.700 die einzelnen Knoten sind durch die Literale der Formel 01:01:27.700 --> 01:01:35.980 gekennzeichnet, wenn ich jetzt genau die Knoten auf 1 setze, die in 01:01:35.980 --> 01:01:39.800 dieser Clique drin liegen, der Größe M, dann habe ich ja gerade meine 01:01:39.800 --> 01:01:44.960 M -Klauseln verbunden durch Kanten, sodass dort Literale drin 01:01:44.960 --> 01:01:47.840 vorkommen, die gleichzeitig auf 1 gesetzt werden können. 01:01:49.140 --> 01:01:53.200 Und das heißt, es gibt dann M-Literalen, M-verschiedenen Klauseln, die 01:01:53.200 --> 01:01:56.540 können nie in der gleichen Klausel sein, sodass alle gleichzeitig 01:01:56.540 --> 01:01:57.560 erfüllt werden können. 01:01:58.180 --> 01:02:01.280 Das heißt, wenn ich eine Klausel habe, oder Quatsch, wenn ich eine 01:02:01.280 --> 01:02:05.160 Clique habe, der Größe M, in dem Graphen, den ich hier erzeugt habe, 01:02:05.980 --> 01:02:11.980 aus meiner aussagenlogischen Formel, dann habe ich damit eine Belegung 01:02:11.980 --> 01:02:15.360 der Variablen, sodass die aussagenlogische Formel erfüllt werden kann. 01:02:16.400 --> 01:02:20.160 Und wenn es keine Clique der Größe M gibt, dann kann diese Formel 01:02:20.160 --> 01:02:21.040 nicht erfüllt werden. 01:02:22.980 --> 01:02:26.140 Und damit habe ich gezeigt, Clique ist ein p-schwer. 01:02:27.600 --> 01:02:32.020 Ja, weil ich ja das Transformieren war in Polymerleiterzeit machbar, 01:02:32.340 --> 01:02:35.800 das Rücktransformieren ist auch in Polymerleiterzeit machbar, also das 01:02:35.800 --> 01:02:37.200 ist alles zu erledigen. 01:02:38.120 --> 01:02:39.460 Ist also kein Problem. 01:02:40.320 --> 01:02:43.660 Wir haben damit gezeigt, Clique ist auch ein p-schweres Problem. 01:02:44.400 --> 01:02:46.360 Beziehungsweise Clique mit dem K drin. 01:02:46.980 --> 01:02:50.380 Okay, und jetzt habe ich gerade gesagt, die Clique mit dem K drin. 01:02:50.760 --> 01:02:53.720 Warum stehe ich immer so hin und her zwischen Optimierungsproblemen 01:02:53.720 --> 01:02:54.740 und Entscheidungsproblemen? 01:02:54.960 --> 01:02:56.260 Man kann das systematisch machen. 01:02:58.180 --> 01:03:03.120 Ich habe jetzt hier für das Clique-Problem die Frage, die wir gerade 01:03:03.120 --> 01:03:06.900 betrachtet haben, gibt es eine Clique der Größe K in G? 01:03:07.780 --> 01:03:10.200 Darauf will ich die Antwort Ja oder Nein haben. 01:03:10.880 --> 01:03:14.140 Dann weiß ich nur, es gibt eine Clique, sagt mir der Algorithmus. 01:03:15.360 --> 01:03:20.580 Jetzt möchte ich aber gerne wissen, was ist denn das größte K, sodass 01:03:20.580 --> 01:03:22.160 G eine K-Clique enthält? 01:03:23.280 --> 01:03:25.460 Ich möchte gerne die maximale Clique haben. 01:03:27.300 --> 01:03:28.520 Das ist ja viel schwerer. 01:03:28.520 --> 01:03:32.160 Nicht nur für ein K feststellen, gibt es eine Clique der Größe, 01:03:32.220 --> 01:03:33.900 sondern auch noch das Maximale. 01:03:34.360 --> 01:03:35.520 Das ist Optimierungsproblem. 01:03:36.680 --> 01:03:39.400 Das Entscheidungsproblem, das Optimierungsproblem ist offensichtlich 01:03:39.400 --> 01:03:40.160 viel schwieriger. 01:03:41.560 --> 01:03:44.860 Da muss ich ja das Größte rausfinden. 01:03:46.120 --> 01:03:51.000 Und dann weiß ich als Antwort auf die Frage nur, was ist das größte K? 01:03:52.600 --> 01:03:55.780 Jetzt will ich aber auch wissen, welche Clique ist das denn nun? 01:03:56.920 --> 01:03:58.780 Jetzt bau mir bitte mal diese Clique. 01:04:00.140 --> 01:04:01.700 Das ist wiederum schwieriger. 01:04:01.780 --> 01:04:04.020 Da muss ich ja tatsächlich so eine Clique konstruieren. 01:04:04.460 --> 01:04:06.480 Vorher habe ich nur einen Existenzbeweis gemacht. 01:04:07.160 --> 01:04:10.000 Es gibt eine Clique, die diese maximale Größe hat. 01:04:10.680 --> 01:04:11.800 Jetzt muss ich die auch angeben. 01:04:13.260 --> 01:04:18.380 Und offensichtlich ist es doch so, wenn ich mir die Probleme 01:04:18.380 --> 01:04:25.980 betrachte, also wenn ich eine maximale Clique konstruieren kann, kann 01:04:25.980 --> 01:04:32.040 ich doch sofort die Antwort geben hier, das größte K, sodass G eine K 01:04:32.040 --> 01:04:33.940 -Clique enthält, na ja, das ist die Größe dieser Clique. 01:04:34.740 --> 01:04:38.080 Und die Frage, ob es eine Clique der Größe K in G gibt, kann ich für 01:04:38.080 --> 01:04:42.560 jedes K beantworten, weil wenn das K größer ist als die Größe meiner 01:04:42.560 --> 01:04:44.640 maximalen Clique, gibt es keine derartige. 01:04:44.840 --> 01:04:48.280 Wenn das K kleiner ist, kleiner gleich ist, dann gibt es natürlich 01:04:48.280 --> 01:04:52.320 eine, weil jede Clique, natürlich Klicken jeder kleineren Größe 01:04:52.320 --> 01:04:54.420 automatisch mit enthält. 01:04:56.260 --> 01:04:59.820 Also, die Richtung hier ist trivial, ganz einfach. 01:05:00.920 --> 01:05:03.160 Tatsächlich kann man auch in dieser Richtung vorgehen. 01:05:05.140 --> 01:05:08.500 Ich habe jetzt nur das Entscheidungsproblem zunächst mal bearbeitet. 01:05:09.640 --> 01:05:17.420 Jetzt kann ich also für eine solche Frage, für solche Grafen und einen 01:05:17.420 --> 01:05:21.680 K angeben, ob es eine Clique der Größe K gibt. 01:05:22.100 --> 01:05:24.140 Wie kann ich daraus ein Optimierungsproblem lösen? 01:05:25.700 --> 01:05:29.000 Na ja, ich weiß ja, wie groß mein Graf ist. 01:05:29.880 --> 01:05:37.540 Der Graf, der hat Anfall V sei gleich N, N Knoten. 01:05:38.600 --> 01:05:42.220 Ich frage einfach, gibt es eine Clique der Größe N? 01:05:43.360 --> 01:05:44.940 Der Algorithmus sagt Nein. 01:05:46.400 --> 01:05:48.980 Dann gehe ich als nächstes auf N halbe. 01:05:50.260 --> 01:05:51.900 Jetzt sagt er, gibt es. 01:05:52.460 --> 01:05:53.240 Da gibt es eine Clique. 01:05:53.980 --> 01:05:57.880 Dann gehe ich entsprechend auf 3 Viertel N und so weiter. 01:05:57.960 --> 01:06:06.900 Ich mache eine binäre Suche nach dem maximalen K, sodass mein 01:06:06.900 --> 01:06:10.860 Algorithmus, der Entscheidungsalgorithmus noch sagt, ich kann das 01:06:10.860 --> 01:06:11.200 lösen. 01:06:11.360 --> 01:06:17.120 Das heißt, von da nach da mache ich einfach eine binäre Suche. 01:06:18.180 --> 01:06:23.860 Ich muss jedes Mal, maximal log N Mal, muss ich ein solches 01:06:23.860 --> 01:06:25.140 Entscheidungsproblem lösen. 01:06:25.980 --> 01:06:29.400 Aber das verändert meinen Aufwand nicht wesentlich. 01:06:30.000 --> 01:06:32.960 Das bleibt polynomiell voneinander abhängig. 01:06:33.540 --> 01:06:34.320 Kein Problem. 01:06:35.900 --> 01:06:43.860 Jetzt kann ich sagen, naja, ich möchte gerne das Konstruktionsproblem 01:06:43.860 --> 01:06:44.140 lösen. 01:06:44.220 --> 01:06:45.980 Ich habe aber nur das Optimierungsproblem gelöst. 01:06:47.200 --> 01:06:48.760 Dann gehe ich einfach wie folgt vor. 01:06:49.480 --> 01:06:52.720 Ich habe hier irgendwie meinen Graphen. 01:06:55.780 --> 01:06:58.360 Und er hat alle möglichen Knoten und Kanten. 01:06:59.640 --> 01:07:04.680 Und jetzt entferne ich eine Kante aus meinem Graphen. 01:07:04.680 --> 01:07:07.140 Ich lösche einfach hier eine Kante raus. 01:07:08.940 --> 01:07:15.020 Und schaue nach, was ist jetzt das maximale K für eine K-Klicke. 01:07:15.860 --> 01:07:19.380 Wenn das das gleiche ist wie vorher, dann ist diese Kante nicht in der 01:07:19.380 --> 01:07:20.400 maximalen Klicke drin. 01:07:21.360 --> 01:07:24.760 Und so lösche ich sukzessive die einzelnen Kanten aus meinem Graphen 01:07:24.760 --> 01:07:25.160 raus. 01:07:25.820 --> 01:07:28.920 Und in dem Fall, wo sich dadurch das K als Antwort auf das 01:07:28.920 --> 01:07:32.340 Optimierungsproblem ändert, weiß ich, diese Kante war relevant, die 01:07:32.340 --> 01:07:32.800 lasse ich drin. 01:07:32.800 --> 01:07:36.120 Und wenn sich das nicht geändert hat, kann ich die Kante löschen. 01:07:36.780 --> 01:07:40.800 Das heißt, ich kann aus dem Optimierungsproblem N-mal angewandt, 01:07:42.260 --> 01:07:46.460 maximal N-mal angewandt oder N-3-mal angewandt, alles andere ist nicht 01:07:46.460 --> 01:07:51.940 mehr relevant, kann ich das Konstruktionsproblem lösen. 01:07:53.080 --> 01:07:54.700 Ich kann die tatsächlich konstruieren. 01:07:55.860 --> 01:07:59.060 Und damit kann ich also auch in dieser Richtung hier vorgehen. 01:07:59.800 --> 01:08:05.000 Okay, das heißt aber auch, dass ich mich darauf beschränken kann, 01:08:05.380 --> 01:08:07.500 zunächst mal Entscheidungsprobleme zu betrachten. 01:08:09.120 --> 01:08:12.740 Und wenn ich die Entscheidungsprobleme beantwortet habe, habe ich im 01:08:12.740 --> 01:08:15.300 Prinzip auch die Antworten für das Optimierungsproblem und für das 01:08:15.300 --> 01:08:16.080 Konstruktionsproblem. 01:08:17.580 --> 01:08:20.140 Das ist also auch wieder eine wichtige Erkenntnis. 01:08:20.880 --> 01:08:28.700 So, jetzt kommt das Problem, dass Sie natürlich später irgendeinen 01:08:28.700 --> 01:08:30.800 Vorgesetzten haben, der Ihnen Aufgaben gibt. 01:08:32.880 --> 01:08:35.760 Und er sagt Ihnen, Sie sollen jetzt irgendeinen tollen Algorithmus 01:08:35.760 --> 01:08:37.620 entwickeln, Sie sollen irgendein Problem lösen. 01:08:38.380 --> 01:08:41.980 Und Sie sagen Ihrem Boss, ich finde keinen Algorithmus, ich schaffe 01:08:41.980 --> 01:08:42.820 das einfach nicht. 01:08:43.540 --> 01:08:47.200 Dann wird der Chef Ihnen sagen, schlecht, ich nehme lieber einen 01:08:47.200 --> 01:08:48.940 anderen, der intelligenter ist als Sie. 01:08:49.880 --> 01:08:54.500 Dann können Sie sagen, Sie vermuten, dass es gar keinen effizienten 01:08:54.500 --> 01:08:55.280 Algorithmus gibt. 01:08:55.380 --> 01:08:58.660 Er sagt dann, naja, vermuten können Sie vieles, es hilft mir aber noch 01:08:58.660 --> 01:08:58.960 nicht. 01:09:00.300 --> 01:09:06.220 Und dann können Sie sagen, wenn Sie ein bisschen mehr wissen, ich kann 01:09:06.220 --> 01:09:10.380 keinen effizienten Algorithmus finden, aber ich kann beweisen, das 01:09:10.380 --> 01:09:12.200 Problem ist NP-vollständig. 01:09:13.520 --> 01:09:17.700 Und das bedeutet, dass es ganz viele Leute gibt, die sich ganz lange 01:09:17.700 --> 01:09:21.320 damit beschäftigt haben, und keiner von denen hat bisher einen 01:09:21.320 --> 01:09:23.000 polynomiellen Algorithmus finden können. 01:09:24.980 --> 01:09:26.980 Also keinen effizienten Algorithmus. 01:09:28.100 --> 01:09:34.040 Und dann können Sie sagen, okay, wenn das so ist, dann müssen wir 01:09:34.040 --> 01:09:37.460 vielleicht die Hoffnung aufgeben, dass es einen effizienten gibt, oder 01:09:37.460 --> 01:09:41.520 wir müssen einfach das Problem ein bisschen verändern und vielleicht 01:09:41.520 --> 01:09:45.740 sagen, wir geben uns auch mit einem nicht optimalen Ergebnis zufrieden 01:09:45.740 --> 01:09:49.040 und machen das approximativ. 01:09:50.600 --> 01:09:53.720 Und das ist das, was man in der Praxis tatsächlich tut. 01:09:55.240 --> 01:09:59.860 Man überprüft, ob das Problem vielleicht in eingeschränkter Form 01:09:59.860 --> 01:10:00.460 vorliegt. 01:10:01.300 --> 01:10:05.180 Sie haben weitere Randbedingungen, die das Problem einfach machen. 01:10:07.780 --> 01:10:11.480 Also es gibt viele Beispiele dafür. 01:10:11.480 --> 01:10:15.940 Also ich habe neulich ein interessantes Problem kennengelernt, da ging 01:10:15.940 --> 01:10:20.460 es, will ich Ihnen kurz erzählen, ein Stromnetz, ich spreche ja 01:10:20.460 --> 01:10:24.100 Energieinformatik, eine nette Anwendung. 01:10:24.960 --> 01:10:28.560 Sie haben ein Stromnetz und Sie sind alle schön miteinander verbunden 01:10:28.560 --> 01:10:36.440 und Sie haben für jedes eine Angabe V1, V2 oder V3 und so weiter. 01:10:36.580 --> 01:10:39.360 An den Knoten stehen jeweils Zahlen dran. 01:10:39.360 --> 01:10:43.420 Und diese Zahlen geben an, wie viel Strom Sie dort produzieren können. 01:10:44.300 --> 01:10:45.840 Das heißt, Sie können dort Strom liefern. 01:10:46.900 --> 01:10:52.840 Und dann haben Sie irgendeine Nachfrage, irgendeinen D, das ist die 01:10:52.840 --> 01:10:56.320 Nachfrage in dem Netz und müssen Sie dafür sorgen, dass Sie genau die 01:10:56.320 --> 01:10:57.280 Nachfrage decken können. 01:10:57.380 --> 01:11:04.040 Das heißt, Sie brauchen eine Summe der VI gleich D, beziehungsweise 01:11:04.040 --> 01:11:06.360 der richtigen VIs. 01:11:06.360 --> 01:11:08.880 Nicht alle, sondern Sie müssen einige auswählen. 01:11:10.000 --> 01:11:12.640 Und man kann leicht zeigen, dass das ein LP-schweres Problem ist. 01:11:14.300 --> 01:11:17.720 Wenn Sie nur entscheiden müssen, ob Sie einen solchen Knoten 01:11:17.720 --> 01:11:19.160 anschalten oder abschalten. 01:11:21.200 --> 01:11:29.500 Wenn Sie aber in der Lage sind, die Erzeugungsleistung eines 01:11:29.500 --> 01:11:34.240 Kraftwerks dynamisch zu regeln, wenn das irgend sowas ist und Sie 01:11:34.240 --> 01:11:40.620 können praktisch dynamisch zwischen 0 und V1 die Erzeugung Ihres 01:11:40.620 --> 01:11:47.260 Knotens verändern, und das gilt hier für alle diese Kraftwerke, dann 01:11:47.260 --> 01:11:51.060 ist das ein Problem, das in linearer Zeit beantwortet werden kann. 01:11:52.800 --> 01:11:56.520 Wenn Sie nur entscheiden können zwischen einschalten oder abschalten, 01:11:56.920 --> 01:12:01.080 ist es ein diskretes kombinatorisches Optimierungsproblem und ist LP 01:12:01.080 --> 01:12:01.480 -schwer. 01:12:01.480 --> 01:12:06.480 In dem Augenblick, wo Sie kontinuierlich regelbare Kraftwerke haben, 01:12:06.580 --> 01:12:08.220 ist das ein linear lösbares Problem. 01:12:10.180 --> 01:12:14.720 Also da muss man genau aufpassen, wenn man als Informatiker da rangeht 01:12:14.720 --> 01:12:18.700 und solche Probleme modelliert, mache ich das eigentlich richtig. 01:12:20.100 --> 01:12:25.560 Also in dem Fall ist sogar die eingeschränkte Form hier die diskrete 01:12:25.560 --> 01:12:28.700 Kombination der einzelnen Kraftwerke. 01:12:29.780 --> 01:12:31.940 Allgemeiner ist es ja, wenn ich das beliebig einstellen kann. 01:12:32.020 --> 01:12:35.700 Aber das sind einfach andere Eigenschaften, die man ausnutzen kann. 01:12:36.760 --> 01:12:39.540 Oder, das muss ich mal wieder weglöschen, damit Sie was sehen können, 01:12:41.340 --> 01:12:46.360 kann es sein, dass ich mich mit einer suboptimalen Lösung zufrieden 01:12:46.360 --> 01:12:49.840 geben kann, sofern die nah genug dran ist. 01:12:50.940 --> 01:12:55.100 Zum Beispiel beim Travelling Salesperson Problem können Sie in 01:12:55.100 --> 01:12:58.760 quadratischer Zeit eine Lösung erzeugen. 01:12:59.600 --> 01:13:04.480 Euklidisch heißt, ich habe euklidische Abstände zwischen den einzelnen 01:13:04.480 --> 01:13:09.220 Elementen, also einfache Abstandsfunktionen. 01:13:09.280 --> 01:13:14.000 Da kann ich bis auf einen Faktor 1,5 die optimale Lösung 01:13:14.000 --> 01:13:14.540 approximieren. 01:13:14.620 --> 01:13:17.900 Ich bin also maximal 50% schlechter als die optimale Lösung. 01:13:18.520 --> 01:13:20.160 Das geht in quadratischer Zeit. 01:13:21.560 --> 01:13:25.720 Es gibt andere Probleme, bei denen Sie zeigen können, ich kann in 01:13:25.720 --> 01:13:32.820 polynomieller Zeit bis auf einen Faktor 1 plus Epsilon mal optimale 01:13:32.820 --> 01:13:33.560 Lösung kommen. 01:13:34.580 --> 01:13:38.420 Das sind die polynomiell approximierbaren Probleme. 01:13:41.420 --> 01:13:44.920 Irgendein kleines Epsilon, für jedes beliebige kleine Epsilon können 01:13:44.920 --> 01:13:49.880 Sie einen polynomiellen Algorithmus angeben, sodass Sie approximieren 01:13:49.880 --> 01:13:50.040 können. 01:13:50.100 --> 01:13:54.260 In diesem Fall war dieses Epsilon 0,5 bei dem TSP. 01:13:55.560 --> 01:13:58.820 Aber es gibt Probleme, bei denen man noch deutlich näher rankommen 01:13:58.820 --> 01:13:59.120 kann. 01:13:59.920 --> 01:14:02.100 Und dann macht man natürlich so etwas, dass man ein solches 01:14:02.100 --> 01:14:03.720 Approximationsschema verwendet. 01:14:04.540 --> 01:14:07.560 Oder Sie machen das zunächst mal mit einer systematischen 01:14:07.560 --> 01:14:09.460 Entwurfsmethode, dynamisches Programmieren. 01:14:11.100 --> 01:14:15.140 Reduktion von Automaten war ein dynamisches Programmieren-Ansatz. 01:14:16.120 --> 01:14:18.980 Das ist allerdings kein NP-vollständiges Problem. 01:14:19.680 --> 01:14:23.860 Branch-and-Bound, Branch-and-Cut-Verfahren, die Sie kennen aus 01:14:23.860 --> 01:14:24.840 Operations Research. 01:14:25.600 --> 01:14:27.200 Das sind also auch Standardverfahren. 01:14:27.780 --> 01:14:30.740 Insbesondere kann man die einschränken, kann sie abschneiden, ab einer 01:14:30.740 --> 01:14:33.760 gewissen Stelle, wenn Sie Branch-and-Bound oder Branch-and-Cut 01:14:33.760 --> 01:14:36.880 vollständig ausführen, sind Sie natürlich im Gesamtaufwand dann 01:14:36.880 --> 01:14:37.580 exponentiell. 01:14:38.720 --> 01:14:42.060 Divide -and-Conquer, ebenso systematische Entwurfsmethoden, die Ihnen 01:14:42.060 --> 01:14:44.960 einigermaßen vernünftige Lösungen bringen. 01:14:46.080 --> 01:14:49.320 Und für kleine Probleminstanzen kann das also schon ganz gut sein. 01:14:50.960 --> 01:14:55.800 Wie gesagt, Sie verzichten auf die Lösungsgüte, nehmen die schnelle 01:14:55.800 --> 01:14:59.500 Heuristik oder Sie setzen randomisierte Verfahren ein. 01:15:00.400 --> 01:15:03.600 Randomisierte Verfahren gibt es in Hülle und Fülle. 01:15:04.860 --> 01:15:08.780 Zum Beispiel also Meta-Heuristiken wie Tabu-Search, Simulated 01:15:08.780 --> 01:15:11.620 Kneeling, Evolutionäre Algorithmen, Ameisen-Algorithmen und so weiter. 01:15:12.200 --> 01:15:13.980 Sehr viele Varianten dieser Algorithmen. 01:15:14.860 --> 01:15:18.040 Und mit denen können Sie gute Lösungen erzeugen. 01:15:18.760 --> 01:15:22.580 Sie können nicht beweisen, dass Ihre Lösung optimal ist, aber Sie 01:15:22.580 --> 01:15:26.000 können relativ schnell gute Lösungen erzeugen. 01:15:26.000 --> 01:15:31.220 Und wenn die gut genug sind, dann reicht Ihnen das vielleicht. 01:15:31.340 --> 01:15:33.420 Also gut genug ist häufig schon ausreichend. 01:15:34.800 --> 01:15:37.380 Wenn Sie noch ein bisschen dran drehen können, ist es gut, aber wenn 01:15:37.380 --> 01:15:40.720 Sie so viel Aufwand reinstecken müssen, dann sagen Sie, das mache ich 01:15:40.720 --> 01:15:41.220 dann lieber nicht. 01:15:41.460 --> 01:15:45.580 Man hat sogar zeigen können, für viele Probleme, für NP-schwere 01:15:45.580 --> 01:15:48.740 Probleme, konnte man tatsächlich mit den Meta-Heuristiken, 01:15:49.160 --> 01:15:52.040 insbesondere hier mit evolutionären Algorithmen und mit Ameisen 01:15:52.040 --> 01:15:56.320 -Algorithmen, insbesondere bei dieser Projektplanung mit beschränkten 01:15:56.320 --> 01:15:59.800 Ressourcen, da sind wir mit Ameisen-Algorithmen sehr weit gekommen, 01:15:59.880 --> 01:16:01.360 wirklich die optimalen Lösungen zu finden. 01:16:02.320 --> 01:16:03.000 Das geht durchaus. 01:16:03.500 --> 01:16:05.580 Also das ist dann der Ansatz, den man dann wählt. 01:16:06.420 --> 01:16:09.860 Und damit sind wir durch diesen Teil durch. 01:16:10.400 --> 01:16:13.200 Tatsächlich nur eine Doppelstunde für Komplexität. 01:16:14.080 --> 01:16:16.220 Ich müsste Ihnen viel mehr erzählen darüber. 01:16:16.940 --> 01:16:20.660 Es ist auch ein ganz wichtiger Teil, und den werden Sie auch in den 01:16:20.660 --> 01:16:22.280 Übungen intensiver sich anschauen. 01:16:22.280 --> 01:16:25.340 Sie können sicher sein, dass Sie sich zu solchen Fragen, die mit 01:16:25.340 --> 01:16:29.240 Komplexität zu tun haben, immer wieder konfrontiert werden, auch in 01:16:29.240 --> 01:16:32.300 Situationen, wo es darauf ankommt, dass Sie Wissen zeigen. 01:16:32.460 --> 01:16:35.880 Also das sind typische Fragen, die was mit Klausuren und Ähnlichem zu 01:16:35.880 --> 01:16:36.400 tun haben. 01:16:36.980 --> 01:16:40.440 War nur eine Doppelstunde, aber ist sehr klausurrelevant, das, was ich 01:16:40.440 --> 01:16:41.460 Ihnen heute erzählt habe. 01:16:42.060 --> 01:16:45.620 Das sind ganz elementare Erkenntnisse, die ich Ihnen nur so schnell 01:16:45.620 --> 01:16:48.520 präsentieren konnte, weil ich viel Vorarbeiten gemacht habe dafür. 01:16:49.000 --> 01:16:52.040 Jetzt kannten Sie die ganzen Notationen, die wir brauchten, und damit 01:16:52.040 --> 01:16:53.060 konnte ich Ihnen das erzählen. 01:16:53.400 --> 01:16:56.040 Was haben wir gemacht in diesem ersten Teil der Vorlesung? 01:16:56.880 --> 01:17:01.420 Formale Beschreibung von informationsverarbeitenden Systemen. 01:17:01.500 --> 01:17:03.880 Wir haben Automaten angeschaut, wir haben reguläre Ausdrücke 01:17:03.880 --> 01:17:06.600 angeschaut, Grammatiken, um Sprachen zu beschreiben. 01:17:10.070 --> 01:17:11.550 Und von Sprachen natürlich. 01:17:12.890 --> 01:17:16.950 Wir haben uns angeschaut, die Ausdrucksfähigkeit und Effizienz der 01:17:16.950 --> 01:17:18.590 verschiedenen Beschreibungsmethoden. 01:17:19.350 --> 01:17:21.470 Ausdrucksfähigkeit, wir brauchten Klammerschachtelung. 01:17:21.470 --> 01:17:25.730 Deswegen kamen wir zu den kontextfreien Sprachen oder den 01:17:25.730 --> 01:17:26.510 Kellerautomaten. 01:17:27.490 --> 01:17:31.990 Wir wollten effizient sein beim Wortproblem, deswegen sind wir auf die 01:17:31.990 --> 01:17:33.970 deterministischen Kellerautomaten runtergegangen. 01:17:34.930 --> 01:17:39.150 Wir haben erkennen können, dass es Äquivalenz gibt zwischen 01:17:39.150 --> 01:17:43.530 verschiedenen Beschreibungsmethoden und haben das sehr, sehr sinnvoll 01:17:43.530 --> 01:17:44.910 und häufig ausgenutzt. 01:17:44.990 --> 01:17:48.470 Bei allen unseren Konstruktionen der Äquivalenz zwischen Grammatiken 01:17:48.470 --> 01:17:53.030 und Automaten und regulären Ausdrücken und so weiter, da haben wir ja 01:17:53.030 --> 01:17:58.670 zum Beispiel bei Grammatiken auf Automaten, haben wir meistens bei der 01:17:58.670 --> 01:18:02.390 Grammatik zum Automat einen nicht deterministischen Automaten erzeugt. 01:18:02.610 --> 01:18:03.430 War viel einfacher. 01:18:04.150 --> 01:18:06.850 Oder auch bei den Kellerautomaten zu einer Grammatik zunächst mal den 01:18:06.850 --> 01:18:07.670 nicht deterministischen. 01:18:08.090 --> 01:18:10.070 Wenn man Glück hat, geht das auch noch deterministisch. 01:18:10.750 --> 01:18:13.490 Und dann haben wir uns mit den prinzipiellen Grenzen der Informatik 01:18:13.490 --> 01:18:14.170 beschäftigt. 01:18:15.050 --> 01:18:17.190 Was ist eigentlich eine berechenbare Funktion? 01:18:18.190 --> 01:18:20.190 Keineswegs jede Funktion ist berechenbar. 01:18:20.290 --> 01:18:24.130 Die nicht berechenbaren Funktionen sind keineswegs nur irgendwelche 01:18:24.130 --> 01:18:27.770 exotischen Probleme, über die man niemals stolpern wird. 01:18:27.830 --> 01:18:32.050 Ich habe Ihnen konkrete Probleme genannt, die man sich durchaus 01:18:32.050 --> 01:18:34.470 vorstellen könnte, dass jemand auf die Idee kommt, dafür einen 01:18:34.470 --> 01:18:35.530 Algorithmus zu entwickeln. 01:18:36.890 --> 01:18:39.210 Entscheidbarkeit und das Letzte ist noch Komplexität. 01:18:39.370 --> 01:18:41.910 Der Aufwand ist ein ganz wichtiger Teil. 01:18:42.550 --> 01:18:45.230 Wie groß ist der Aufwand, um bestimmte Probleme zu lösen? 01:18:45.230 --> 01:18:51.190 Wenn Sie zeigen können, Sie haben einen Algorithmus gefunden für ein 01:18:51.190 --> 01:18:56.730 Problem und dabei den Aufwand genau entsprechend der unteren Schranke 01:18:56.730 --> 01:19:01.190 hinbekommen, dann wissen Sie, das ist ein optimaler Algorithmus. 01:19:02.070 --> 01:19:04.430 Dann nützt es nicht, zu versuchen, den noch zu verbessern, das ist 01:19:04.430 --> 01:19:05.010 dann optimal. 01:19:05.690 --> 01:19:08.550 Allerdings habe ich jetzt nur über Worst-Case-Execution-Time 01:19:08.550 --> 01:19:08.910 gesprochen. 01:19:09.470 --> 01:19:13.510 Wenn es dann noch um weitere Dinge geht, wie mittleres Verhalten usw., 01:19:13.510 --> 01:19:15.310 dann wird das noch ein bisschen aufwendiger. 01:19:16.470 --> 01:19:17.530 Also da kann man noch sehr viel tun. 01:19:18.390 --> 01:19:22.530 Und das sind alles drei wesentliche, grundlegende Aspekte, die man 01:19:22.530 --> 01:19:25.290 sich anschauen muss, wenn man sich mit Informationsverarbeitung 01:19:25.290 --> 01:19:25.950 beschäftigt. 01:19:26.370 --> 01:19:29.790 Deswegen haben wir das ja auch in unserem Buch zusammengefasst alles 01:19:29.790 --> 01:19:34.330 und nur versucht dabei, das noch möglichst im Sinne von praktischer 01:19:34.330 --> 01:19:37.250 Anwendung zu formulieren, sodass man wirklich einen Zugang findet. 01:19:37.890 --> 01:19:42.390 Ich hoffe, dass Sie das auch so feststellen, dass Sie das damit 01:19:42.390 --> 01:19:43.110 verstehen können. 01:19:43.110 --> 01:19:51.370 Und damit sind wir durch dieses Kapitel durchgekommen und haben damit 01:19:51.370 --> 01:19:56.670 alles bearbeitet, was mit theoretischer Informatik bzw. 01:19:57.230 --> 01:20:00.430 in dieser Vorlesung an formalen Modellen aus der theoretischen 01:20:00.430 --> 01:20:01.710 Informatik relevant ist. 01:20:02.170 --> 01:20:06.570 Und wir werden uns nächstes Mal dann mit dem nächsten Teil der 01:20:06.570 --> 01:20:09.430 technischen Informatik beschäftigen, mit Schaltnetzen und Schaltwerken 01:20:09.430 --> 01:20:09.810 bzw. 01:20:09.970 --> 01:20:10.650 dem Weg dahin. 01:20:10.650 --> 01:20:12.430 Ich danke Ihnen für die Aufmerksamkeit.