Grenzen der Berechenbarkeit

Im Folgenden eine Struktur, die man benutzen kann um einen Text zu diesem Thema zu schreiben: Einleitung: Überblick -> was ist zu beweisen? Voraussetzungen: Arten der Turingmaschinen, die wir verwenden Abzählbarkeit/ Überabzählbarkeit partielle Funktionen Kurzform der Listen Abzählbarkeit der Turingmaschinen anhand der Tabelle klar machen Zwischenfazit: Menge der Turingmaschinen ist abzählbar. Folgerung der Abzählbarkeit für… Weiterlesen Grenzen der Berechenbarkeit

Genetische Algorithmen 10.9.19

Zu Beginn der Stunde hat Bjarne seine Hausaufgabe vorgestellt: Bei der Besprechung der Hausaufgabe haben wir festgestellt, dass die for-Schleife in der Funktion „loesungGenetischerAlgorithmus“, wie sie in der Musterlösung vorhanden ist, wichtig ist, da durch sie die Population weiterentwickelt wird. Anders als die for-Schleife in #Test, welche, in unserem Fall, 20 mal das beste Ergebnis… Weiterlesen Genetische Algorithmen 10.9.19

Implementierung Genetischer Algorithmus | 1

Heute besprachen wir die von uns über das Wochenende implementierten Funktionen. erzeugeIndividuum() erzeugePopulation() fitness() In der Funktion erzeugeIndividuum() wird ein neues Individuum mit der Länge 10 erzeugt und zurückgegeben. In erzeugePopulation() werden 50 Individuen erzeugt, in eine Liste eingefügt und zurückgegeben. In Fitness wird geschaut wie der Wert des jeweiligen Individuums ist. Diese Funktion hängt… Weiterlesen Implementierung Genetischer Algorithmus | 1

Das Rucksackproblem

Die Stunde hat damit begonnen, dass wir uns überlegt haben, wie man am effektivsten ein Juwelier ausrauben könnte. Wir wollten möglichst viel Geld erbeuten, aber maximal 20kg tragen, damit wir noch vor der Polizei wegrennen können. Das ganze haben wir dann anhand eines Beispiels auf inf-schule selbst ausprobiert. Der Rucksack konnte 15kg fassen und wir… Weiterlesen Das Rucksackproblem

Hausaufgaben P/NP

Zu Beginn haben wir das Protokoll der vorherigen Unterrichtstunde besprochen. Als Hausaufgabe für diese Stunde hatten wir auf, einen Text über bestimmte Begriffe des Themas Komplexität zu schreiben, in dem diese erklärt werden. Zwei von diesen Hausaufgaben haben wir draufhin gelesen und auf Fehler überprüft. Probleme in NP lassen sich bis jetzt nicht praktisch berrechnen[…]… Weiterlesen Hausaufgaben P/NP

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