Add to Watchlist

12.02.3 Komplexität, P und NP

80 views

Citation of segment
Embed Code
Purchasing a DVD Cite video

Formal Metadata

Title 12.02.3 Komplexität, P und NP
Title of Series Informatik 1, Winter 2010/2011
Author Loviscach, Jörn
License CC Attribution - NonCommercial - ShareAlike 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
DOI 10.5446/9559
Publisher Loviscach, Jörn
Release Date 2011
Language German
Producer Loviscach, Jörn

Content Metadata

Subject Area Computer Science

Related Material

The following resource is accompanying material for the video
Series
Annotations
Transcript
Loading...
Noch etwas philosophisches zu Komplexität insbesondere zum Zeitaufwand Rechenaufwand
Komplexität wie komplex ist ein Algorithmus das wovon Quadrat O von Lord das Zeitkomplexität wie schlimm ist ein Algorithmus wie schnell wächst er mit wachsender Daten stellt die war Rechenzeit mit wachsender Datenmengen des geht einen begann das Problem dass ich jüngst als gelöst von behauptet wurde es ist gelöst ist also anscheinend doch nicht ist P gleich das ist die Geschichte aus der theoretischen Informatik von der ich zumindest will dass sind die haben was das bedeutet dass wir nicht ganz mir bestimmen was das heißen soll dass es ein berüchtigtes Probleme aus der theoretischen Informatik es geht um Laufzeitverhalten von Algorithmen wie schnell lassen sich bestimmte Probleme lösen und sogar sagen Laufzeit vor auf das Verhalten von Problemen die komplexes als Probleme wie komplex ist der Algorithmus mit dem des nur so kommt man von Problemen
Auf die Algorithmen seien die Probleme seien Probleme seien nicht mehr so steht es Text Probleme die man es Probleme die genannt Hochform eine beliebige Potenzen lösen kann war schon nicht aus Potenz von Hochgart lösen kann Mit einem endlichen kann natürlich Suche würde da rein formale Sortieren würde da rein formale habe das Sortieren das ganz schlimm ist of vorsieht Quadrat die polynomialen Problem deshalb die von die Jahre lösbaren Problemen alles was sich in dem Tempo lösen kann dieser länger Problem ist der schon so was wie Probleme die so schlecht lösbar sind das Laufzeit von hoch Tausend haben dass die Algorithmen lösen kann auf der noch Tausend ab wenn sie verdoppeln 2 Tausend das Problem doppelt so groß machen als dass sie kriegen einen Faktor von 2 hoch Tausend dazu
2 hoch Tausend während nach 2 hoch Tausend ganz hoch ein 2. ungefähr ein Drittel
Ein 3. das also Zehenbruch fast 332 das was 10 333 als mit 333 nur die Laufzeit des Problem der Größe verdoppelt Doppelt so viele Daten eingeschmissen die Laufzeit plötzlich länger um nach 1 mit 133 großer mit allem was 0 6 das werde immer noch in dieser Menge geht also schon ziemlich finster die Probleme der Menge die Probleme der Länge diese ganz eigentümlich dass ist mit echte Konstruktion aus der theoretischen Informatik die nichtdeterministisch polynomial lösbaren Probleme wenig Algorithmen die alle Möglichkeiten ausreizen nicht immer nur eine Möglichkeit haben sondern alle Wege gehen können die für die 16. die Probleme von dem ich feststellen kann ob die Lösung Chef zu polynomialer Zeit so kann man das auch auf was dass die Probleme
Deren Lösung ich in Polynomialzeit dessen kann Probleme deren Lösung Man sich aber nicht von oben ja derzeit Tests kann
Die Lösung man 2 aus der Zeit
Test alle ist der Begriff anders Bauer Computer und alle Wege durch die
Nicht immer nur einen Weg zum verschiedene Wege zur selben Zeit kann ziemlich heftig und dann muss man aber schon nach wenigen stellt fest dass die Probleme deren Lösungen man von vom Jahr derzeit testen kann also umgekehrt der Primzahlen seines schwierig Zahlen dazu nicht schwierig umgekehrt festzustellen ob Anzahl das Produkt zweier Zahlen das ist einfach das Video von dieser Art und darum geht an der Stelle Sind diese beiden Problemen dieser wurde nicht gegen das oder nicht glauben wir damit die sich Kurorten an theoretischen Informatik und der vor dem Nachdenken darüber auch diese Hoffnung ist Dass man diese Problem griff hatte sich an andersrum die Hoffnung ist wenn das etliche Gleichheit sein sollte dass diese Probleme die lediglich finster sehr einfacher werden was man ziemlich komplizierte Problem einfach lösen Ist die Hoffnung ob so sein wird ob der Gleichheit herrscht ist bisher unklar ein schönes Problem aus der Problem von Problemen eine schöne Aufgabe aus der theoretischen Format des Propheten des haben was da steht die Frage wie ungleich oder gleich gar nicht ob 2 so viel ob diese beiden Mengen an Problemen dieselben sind oder nicht diese jetzt richtig kompliziert Die sich hier könne relativ kompliziert sein sind nur noch bis ins Haus Wenn die beiden kleinen hätte man eine sehr komplizierte Probleme
Run time (program lifecycle phase)
Algorithm
Computer animation
World Wide Web
Laufzeit
Computer file
Square
Best, worst and average case
Theoretical computer science
Algorithm
Computer animation
Exponentiation
Laufzeit
Lösung <Mathematik>
Square
Factorization
Algorithm
Computer animation
Laufzeit
Software testing
Set (mathematics)
Length
Theoretical computer science
Computer animation
Computer animation
Zahl
Computer animation
Lösung <Mathematik>
Prime number
Theoretical computer science
Loading...
Feedback

Timings

  272 ms - page object

Version

AV-Portal 3.8.0 (dec2fe8b0ce2e718d55d6f23ab68f0b2424a1f3f)