Autor: T.Karp

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

Siehe inf-schule.de. Ergebnis lautet: Die Laufzeit wächst bei unserem einfachen Algorithmus exponentiell mit der Stellenzahl.

Bei einer Kantenlänge von n Karten gibt es (n*n)! Möglichkeiten die Karten anzuordnen. Für jede Karte gibt es 4 Möglichkeiten diese zu drehen. Damit ergibt sich eine gesamte Zahl an (n*n)! * 4(n*n) verschiedenen Möglichkeiten. Im schlechtesten Fall müssen diese alle untersucht werden (beim naiven Algorithmus). (siehe auch inf-schule) Man könnte das Verfahren auf verschiedene… Weiterlesen Affenpuzzle und praktische Berechenbarkeit / Faktorisierung

Implementierung von Quicksort (Quellcode siehe Datei zur letzten Stunde) Erste Laufzeittests

(Ab jetzt sollten Protokolle der Kategorie „Komplexität“ zugeordnet werden, da wir uns die nächste Zeit mit der Komplexität von Algorithmen und Problemen beschäftigen werden) Besprechung der Idee von Selectionsort und Bubblesort Implementierung beider Verfahren Idee von Quicksort Die Verfahren sind auf inf-schule.de (Kapitel 9.1.1) ausführlich beschrieben. Implementierung der Sortierverfahren Ich hatte gerade keinen Zugriff auf… Weiterlesen Selectionsort und Bubblesort