Zu Beginn der Stunde wurden die Hausaufgabe(Nr 3 und Nr 4) vorgestellt. Dabei ist das Programm von Moritz zur verdopplung einer Kleeblattreihe noch nicht fertig, denn es lässt eine Lücke zwischen der orginalen und kopierten Reihe. Dies ist einfach zu beheben indem der Marienkäfer in die Lücke noch ein Kleeblatt setzt und dann das letzte… Weiterlesen Turing Maschinen
Monat: September 2019
Turing
In der heutigen Stunde haben wir uns überwiegend mit der Besprechung der Hausaufgaben beschäftigt. Am Ende der Stunde haben wir uns mit der Frage „Warum beschäftigen wir uns mit Turingmaschinen?“ auseinander gesetzt. Hausaufgabenbesprechung Kapitel 9.2.3.1 Nr.1 + 9.2.3.2 Nr 2 Was beinhaltet eine Turingmaschine? https://de.wikipedia.org/wiki/Turingmaschine#Formale_Definition Hausaufgabe Kapitel 9.2.3.2 Nr. 3 + 4
Das Halteproblem
Im ersten Teil der heutigen Doppelstunde haben wir die Lösbarkeit des Halteproblems besprochen, die wir uns als Hausaufgabe anschauen mussten. Da wir in der letzten Stunde gemerkt haben, das es sehr schwierig ist einen Algorithmus zu schreiben, der Endlosschleifen erkennt, kann man prüfen ob das Problem überhaubt lösbar ist. Dazu nimmt man an das man… Weiterlesen Das Halteproblem
Theoretische Berechenbarkeit
Begonnen wurde die Stunde damit, dass wir uns ein Programm anschauten, welches zeigen sollte, ob eine Zahl eine Primzahl ist. Dieses sah wie folgt aus: Dieses Programm war jedoch nur mäßig optimiert und brauchte schon bei sehr geringer Problemgröße sehr lange das Problem zu lösen.Da es teilweise extrem lang dauerte, kamen wir auf die Überlegung,… Weiterlesen Theoretische 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
Genetische Algorithmen
Heute haben wir besprochen wie man mit biologischen Vorgängen aus der Natur unser Rucksackproblem näherungsweise zu berechnen. Dazu nutzen wir die Mechanismen der Populationsgenetik. Ein Individuum ist in unserem Fall eine Kombination. Eine Population ist eine Liste mit x Kombinationen. Unser Fitnesswert ist das Gewicht der Kombination. Wenn das Gewicht das Maximalgewicht des Rucksack überschreitet… Weiterlesen Genetische Algorithmen
Rucksack Algorithmus
Wir haben diesmal die ganze Doppelstunde genutzt um den Algorithmus für das Rucksackproblem fertig zu programmieren. Hierbei haben wir mit einem Demoprogramm gearbeitet, bei dem wir nur noch die Funktionen gesamtGewicht, gesamtWert und optimalLösung implementieren mussten. Eine komplette Implementierung eines Programmes könnte z.b. so aussehen: Rucksackproblem gegenstaende = [(3.5, 375), (2.5, 300), (2.0, 100), (3.0,… Weiterlesen Rucksack Algorithmus
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