Problem des Handlungsreisenden

Angefangen wurde die Stunde wie üblich durch das Besprechen des vorherigen Protokolls. Hierbei wurden wir nochmal auf einen Fehler in der Ausdrucksweise aufmerksam gemacht: Es gibt keine „leichten“ oder „schweren“ Probleme in NP, es gibt lediglich Probleme in NP und NP-vollständige Probleme. Problemreduktion am Beispiel des Problems des Handlungsreisenden und dem Hamilton-Problem Zu Beginn muss… Weiterlesen Problem des Handlungsreisenden

Problemreduktion und Zusammenfassung

Das Hamiltonkreis-Problem ist NP-vollständig. Erläutern Sie ausführlich was das bedeutet. Dabei sollen mindestens folgende Aspekte und Begriffe thematisiert werden: Klasse P und Klasse NP Probleme in NP und NP-vollständige Probleme SAT Karp’s NP-vollständige Probleme Problemreduktion Praktisch lösbare Probleme Komplexität eines Algorithmus und Komplexität eines Problems Praktische Relevanz Tipps und hilfreiche Recherchepunkte: Was hat multiplizieren und… Weiterlesen Problemreduktion und Zusammenfassung

Zeitungsartikel über „P=NP?“ am 26.08.19

Heute haben wir im Unterricht den Zeitungsartikel aus der „Zeit Online“ gelesen, welchen wir als Hausaufgabe hätten lesen sollen. Zum download kommt ihr hier. Beim lesen haben wir uns darauf geeinigt, dass wir 10k/2 als „Wurzel aus 10 hoch k“ lesen.Was ich in dem Artikel als wichtig empfand sind folgende Punkte:– Es gibt schwierigere Probleme… Weiterlesen Zeitungsartikel über „P=NP?“ am 26.08.19

Die Klassen P und NP

Sollten Begriffe unklar sein siehe Beitrag Glossar. Nicht-deterministische Algorithmen mit polynomialer Komplexität Wenn wir bisher von Algorithmen gesprochen haben, haben wir vorausgesetzt, dass der Algorithmus deterministisch in dem Sinne ist, das der nächste Ausführungsschritt immer genau feststeht. Wenn man diese Voraussetzung weglässt, gelangt man zu den nichtdeterministischen Algorithmen. Etliche Probleme mit noch nicht geklärter Komplexität… Weiterlesen Die Klassen P und NP

Glossar

Komplexität von Algorithmen und Problemen deterministisch: ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten. Für die gleiche Eingabe folgt auch immer die gleiche Ausgabe und zusätzlich wird die gleiche Folge an Zuständen durchlaufen Kostenfunktion: Funktion zum Beschreiben des Wachstumsverhalten der Laufzeit des Algorithmus Kostenmaß: in welcher Art die Kosten gemessen werden nichtdeterministisch:… Weiterlesen Glossar

Rundreiseprobleme, Hamiltonkreislauf

Am Anfang der Stunde haben wir uns nochmal mit dem Eulerkreislauf auseinander gesetzt. Wiederholt sind wir Graph 1 und 2 von inf-schule nach der Systematik unseres Algorithmus durchgegangen und haben uns das Laufzeitverhalten angeschaut. Wir haben festgestellt, dass wenn man die Anzahl der Knoten verdoppelt, sich die Laufzeit vervierfacht, d.h. dass die Komplexität des Problems… Weiterlesen Rundreiseprobleme, Hamiltonkreislauf

Komplexitätsbetrachtungen

Am Anfang der Stunde haben wir uns noch einmal kurz mit den Faktorisierungen beschäftigt und uns Vergleiche dazu angeschaut. Eulerkreis Eulerkreis def.: Ein Eulerkreis oder (geschlossener) Eulerzug (auch Eulertour oder Eulersche Linie) ist in der Graphentheorie ein Zyklus, der alle Kanten eines Graphen genau einmal enthält. (https://de.wikipedia.org/wiki/Eulerkreisproblem ) Nach der Wiederholung zu den Faktorisierungen, sind wir zu Inf-Schule übergegangen und haben uns die Komplexitätsbetrachtungen genauer angeschaut (… Weiterlesen Komplexitätsbetrachtungen

Komplexität und Rundreiseprobleme

Am Anfang der Stunde haben wir die Hausaufgabe besprochen. Die Fragestellung war, wie lang es dauern würde eine Verschlüsselung zu lösen, die aus zwei 500 stelligen Zahlen besteht. Da wir in unserem Testprogramm für eine Zahl mit 18 Stellen 111,5369 Sekunden gebraucht haben und sich die benötigte Zeit nach jeder Stelle verdreifacht, muss man rechnen:… Weiterlesen Komplexität und Rundreiseprobleme

Faktorisierung

In der heutigen Stunde haben wir zu Beginn kurz über das neue Schulnetzwerk geredet. Im Anschluss haben wir mit der Faktorisierung von Primzahlen weitergemacht, mit der wir vor den Ferien begonnen hatten. Dabei geht es um die Darstellung einer Zahl n in möglichst kleine Primfaktoren. Beispiel 1: 16 = 2 * 2 * 2 *… Weiterlesen Faktorisierung