Wozu dient die Landausche O-Notation?
Die O-Notation, die von dem deutschen Mathematiker Edmund Landau eingeführt wurde, dient dazu
das Wachstum verschiedener Funktionen zu vergleichen.
Welche offensichtliche Eigenschaft hat die Landausche O-Notation?
Eine offensichtliche Eigenschaft ist, dass jede Funktion in der gleichen Größenordnung wie sie selbst wächst, aber nicht langsamer
Was betrachtet man in der Komplexitätstheorie?
In der Komplexitätstheorie betrachtet man die für eine Berechnung erforderliche Ressourcennutzung,
Ressourcen sind die Anzahl der Rechenschritte sowie der benötigte Speicherplatz.
Was versteht man unter der Komplexität eines Algorithmus?
Unter der Komplexität eines Algorithmus versteht man das Wachstum des Ressourcenverbrauchs des Algorithmus
in Abhängigkeit von der Größe der Eingabewerte, vor allem in Bezug auf die Ressourcen Zeit und Speicherplatz.
Was beschreibt die Zeitkomplexität eines Algorithmus?
Die Zeitkomplexität eines Algorithmus beschreibt, wie der Rechenaufwand wächst, wenn die Eingabedaten größer werden.
Welcher ist der schnelleste sortier Algorithmus?
QuickSort ist der schnellste.
Benne 5 Sortieralgorithmen und deren Zeit- und Speicherkomplexität.
Algorithmus
Durchschnittliche Zeit
Schlechtester Fall
Speicherbedarf
BubbleSort
Θ(n2)
Θ(n)
HeapSort
Θ(n⋅logn)
MergeSort
QuickSort
SelectionSort
Die Frage lautet: Ist P gleich NP?
Welche Fragestellung verbirgt sich dahinter?
Anders gesagt: Kann man Aufgaben, deren Lösungen sich schnell überprüfen lassen (NP), auch genauso schnell lösen (P)?
P ist eine Teilmenge von NP:
Was bedeutet das?
Alles, was schnell lösbar ist (P), lässt sich natürlich auch schnell überprüfen (NP).
NP-Vollständigkeit beschreibt die schwierigsten Probleme in der Klasse NP (nicht-deterministische Polynomialzeit). Solche Probleme haben zwei besondere Eigenschaften. Benenne diese.
Sie lassen sich schnell überprüfen (liegen also in NP).
Jedes andere Problem in NP kann auf sie zurückgeführt werden, und zwar in polynomialer Zeit.
Was bedeutet Reduzierbarkeit?
Man sagt, ein Problem L1 kann auf ein anderes Problem L2reduziert werden (schreibweise L1≤p2L), wenn:
Es eine Funktion f gibt, die L1auf L2 überträgt.
Diese Funktion f in polynomialer Zeit berechenbar ist.
Das bedeutet: Wenn wir L2 lösen können, können wir L1 auch lösen, und zwar in polynomialer Zeit.
Was sind NP-schwere und NP-vollständige Probleme?
NP-schwer: Probleme, auf die sich jedes Problem in NP reduzieren lässt. Sie müssen aber selbst nicht in NP liegen (können also schwerer sein).
NP-vollständig: Probleme, die sowohl NP-schwer sind als auch selbst in NP liegen.
Warum ist NP-Vollständigkeit wichtig?
Zentrale Bedeutung von NP-vollständigen Problemen:
NP-vollständige Probleme sind die „schwierigsten“ Probleme in NP. Wenn ein Algorithmus eines dieser Probleme effizient löst, lassen sich alle anderen NP-Probleme effizient lösen.
Was besagt der Satz von Cook? (Erfüllbarkeitsproblem)
Der Satz von Cook besagt, dass das Erfüllbarkeitsproblem (SAT) – die Frage, ob eine aussagenlogische Formel erfüllbar ist – NP-vollständig ist. Das heißt:
SAT liegt in NP.
Jedes andere Problem in NP lässt sich auf SAT reduzieren.
Gibt es einen Algorithmus, der das Erfüllbarkeitsproblem der Aussagenlogik in Polynomialzeit löst?
Es ist kein solcher Algorithmus bekannt, aber es konnte bisher auch nicht nachgewiesen werden, dass ein solcher Algorithmus nicht existiert. Es gibt einen solchen Algorithmus genau dann, wenn P = NP.
Gibt es eine Sprache, für die die Zeitkomplexität kleiner ist als die Platzkomplexität?
Nein, eine solche Sprache kann es nicht geben, denn eine Turing-Maschine kann maximal eine Zelle pro Rechenschritt verwenden. Also kann sie insgesamt nicht mehr Platz benötigen als Rechenschritte.
Was kannst du mir über die Komplexität bei Quantencomputern erzählen?
Quantencomputer können die gleichen Aufgaben lösen wie klassische Computer,
aber oft viel schneller, da sie anders funktionieren. Statt Bits verwenden sie QBits
Was unterscheidet QBits von Bits?
Quantencomputer verwenden QBits, die mehrere Zustände gleichzeitig annehmen können.
Dadurch können sie viele Möglichkeiten parallel berechnen und nur die richtigen Ergebnisse weiterverwenden
Für Quantencomputer gibt es Komplexitätsklassen und die wichtigste dieser Klassen ist BQP. Was bedeutet diese und was sind die wichtigsten Algorithmen?
BQP, steht für „Bounded-error, Quantum, Polynomial time.
Shor-Algorithmus:
Zerlegt Zahlen in ihre Primfaktoren in Polynomialzeit.
Diskreter Logarithmus (Shor-Algorithmus):
Berechnet diskrete Logarithmen effizient in Polynomialzeit.
Ebenfalls schwer für klassische Computer.
Grover-Algorithmus:
Findet Einträge in unsortierten Listen viel schneller:
Klassisch: Laufzeit O(n) (lineare Zeit, muss jeden Eintrag prüfen).
Mit Quantencomputern: Laufzeit O(wurzel von n)(wesentlich schneller).
Was sind NP-vollständige Probleme?
NP-vollständige Probleme sind die schwierigsten Aufgaben innerhalb der Komplexitätsklasse NP.
Sie haben gemeinsam, dass ihre Lösung schwer zu finden, aber leicht zu überprüfen ist.
Nenne 5 Beispiele von NP-vollständigen Problemen.
NP-vollständige Probleme sind die schwierigsten Aufgaben innerhalb der Komplexitätsklasse NP. Sie haben gemeinsam, dass ihre Lösung schwer zu finden, aber leicht zu überprüfen ist.
Um was für ein NP-vollständiges Problem handelt es sich hier?
Beschreibung: Das SAT-Problem fragt, ob eine aussagenlogische Formel erfüllbar ist. Beim 3SAT-Problem ist die Formel in einer speziellen Form: konjunktive Normalform mit maximal drei Variablen (Literalen) pro Klausel.
Schwierigkeit: Selbst diese eingeschränkte Version bleibt NP-vollständig.
Beschreibung:
Ein Rucksack hat eine maximale Kapazität.
Gibt es eine Kombination von Paketen mit unterschiedlichen Größen, die den Rucksack exakt füllt?
Mathematisch: Gibt es eine Teilmenge von Paketen, deren Größen genau die Kapazität des Rucksacks ergeben?
Variationen:
Pakete dürfen mehrfach verwendet werden.
Pakete haben zusätzlich Werte, und das Ziel ist es, den Gesamtwert zu maximieren oder einen Mindestwert zu erreichen.
Gegeben ein Graph mit Knoten (Punkten) und Kanten (Verbindungen).
Gibt es eine Gruppe von Knoten, die alle direkt miteinander verbunden sind?
Beispiel: Eine Clique der Größe 4 bedeutet, dass vier Knoten untereinander verbunden sind.
Schwierigkeit: Das Finden einer Clique einer bestimmten Größe ist schwer, aber das Überprüfen einer Lösung ist einfach.
Hamilton-Kreis:
Ein Pfad in einem Graphen, der jeden Knoten genau einmal besucht und zum Startpunkt zurückkehrt.
Handlungsreisendenproblem (TSP):
Ein Reisender will eine Rundreise durch Städte machen.
Ziel: Eine Route finden, die alle Städte genau einmal besucht und die kürzeste oder effizienteste Strecke nutzt.
Anwendungen: Logistik, Tourenplanung, Genomsequenzierung.
Eine Menge von Zahlen soll in zwei Teilmengen aufgeteilt werden, sodass die Summe der Zahlen in beiden Teilmengen gleich ist.
Beispiel: Kann man die Zahlen {3, 1, 5, 9, 12} so aufteilen, dass die Summen gleich sind?
Schwierigkeit: Wenn die Gesamtsumme der Zahlen ungerade ist, ist die Antwort direkt „Nein“. Ansonsten gibt es viele Möglichkeiten (2ⁿ Kombinationen), und das Problem ähnelt dem Rucksackproblem.
Last changed20 days ago