Komplexität und Rundreiseprobleme

Am Anfang der Stunde haben wir die Hausaufgabe besprochen. Die Fragestellung war, wie lang es dauern würde eine Verschlüsselung zu lösen, die aus zwei 500 stelligen Zahlen besteht. Da wir in unserem Testprogramm für eine Zahl mit 18 Stellen 111,5369 Sekunden gebraucht haben und sich die benötigte Zeit nach jeder Stelle verdreifacht, muss man rechnen:

111,5369 * 3^482

Also die Zeit für 18 Stellen mal 3 für jede der noch fehlenden 482 Stellen. Das Ergebnis in Jahre umgerechnet ist dann 3,3*10^224. Natürlich bezieht sich das Ergebnis nur auf das Lösen der Verschlüsselung mit diesem spezifischen Algorithmus und Computer.

Dannach haben wir einen Mini-Exkurs in das Thema Quantencomputer gemacht und haben darüber gesprochen das es mithilfe dieser in der Zukunft Möglichkeiten geben könnte, solche Verschlüsselungen zu lösen.

Komplexität

Bei dem Thema Komplexität gibt es zwei verschiedene Begriffe.

Einmal die Komplexität eines Algorithmus :

Die Zeitkomplexität eines Algorithmus wird durch Kostenfunktionen beschrieben. Solche Funktionen liefern in der Regel Abschätzungen des Rechenaufwands für bestimmte Sonderfälle (best case, worst case).

http://inf-schule.de/grenzen/komplexitaet/primfaktorzerlegung/komplexitaetsbetrachtungen

Und die Komplexität eines Problems

Die Zeitkomplexität eines Problems wird […] durch eine untere Schranke für Kostenfunktionen von Algorithmen zur Lösung des Problems beschrieben

http://inf-schule.de/grenzen/komplexitaet/primfaktorzerlegung/komplexitaetsbetrachtungen

DIe Komplexität eines Algorithmus kann also nie weniger Komplex als das Problem an sich sein und der best case des Algorithmus ist genauso Komplex wie das Problem.

Rundreiseprobleme

Dannach haben wir ein neues Teilkapitel begonnen, bei dem wir uns zwei verschiedene Probleme angeschaut haben. Das Brückenproblem ist dabei von einem Computer relativ einfach zu lösen, da um sicherzustellen das jeder Stadtteil besucht wurde ohne das eine Brücke doppelt benutzt wurde nur auf die Anzahl der Brücken geachtet werden muss. Das Problem ist nur bei einer geraden Anzahl von Brücken lösbar. Das Brückenproblem kann vereinfacht auch als Graph dargestellt werden. Das nächste Problem, der Dodekaeder ist jedoch für einen Computer deutlich schwerer lösbar, da um alle Ecken des Dodekaeders genau einmal zu besuchen, ausprobiert werden muss und es keine klare Regel gibt.

(Nachtrag von Herrn Karp zur Faktorisierung:)

Schreibe einen Kommentar