Th3D3str0y3r
Software-Overclocker(in)
Aufwand Berechnung von NP-vollständigen Problemen
Moin,
aus purer langeweile will ich ein Beispiel zum Aufwand eines NP Vollständigen Problems, genauer gesagt dem Partition Problem, nochmal nachrechnen (haben wir in der Uni schon gemacht).
Gegeben in eine Menge mit einer Mächtigkeit von 300. Dementsprechend gibt es 300! Variationen, das enstpricht mit ganz viel runden und mit Hilfe der Stirlingschen Annäherungsformel ungefäht 10^600.
Jetzt will ich berechnen wie lange der in 50 Jahren schnellste Supercomputer (ausgehend von einer Verdoppelung der Rechenleistung jedes Jahr) brauchen würde um das Problem zu lösen.
Der aktuell schnellste Supercomputer schafft 93.000TeraFLOPS (=93.000 * 10^12 FLOPS), das sind also 93PetaFLOPS, gerundet auf 100PFLOPS also ca 10^17 FLOPS.
Ein Jahr hat ungefähr 31536000 Sekunden (60*60*24*365), also ungefähr 3*10^7 Sekunden, für die weitere Berechnung 10^7.
50 Jahre lange Verdopplung, also 2^50 ist ungefähr 1,12*10^15, für die weitere Berechnung 10^15.
Also müsste der schnellste Supercomputer in 50 Jahren eine Rechenleistung von 10^17 * 10^7 * 10^15 = 10^39FLOPS haben.
Mit 100^600 / 10^39 bräuchte der Computer 10^561 Sekunden um das Problem zu lösen. Das sind 10^561 / 10^7 = 10^554 Jahre.
Aus der Vorlesung weiß ich, dass die Berechnung länger brauchen würde als die Erde existiert. Allerdings kommen mir 10^554 Jahre dann doch schon arg viel vor
Habe ich jetzt irgendwo einen kleinen Denkfehler, oder kommt das tatsächlich so hin?
Moin,
aus purer langeweile will ich ein Beispiel zum Aufwand eines NP Vollständigen Problems, genauer gesagt dem Partition Problem, nochmal nachrechnen (haben wir in der Uni schon gemacht).
Gegeben in eine Menge mit einer Mächtigkeit von 300. Dementsprechend gibt es 300! Variationen, das enstpricht mit ganz viel runden und mit Hilfe der Stirlingschen Annäherungsformel ungefäht 10^600.
Jetzt will ich berechnen wie lange der in 50 Jahren schnellste Supercomputer (ausgehend von einer Verdoppelung der Rechenleistung jedes Jahr) brauchen würde um das Problem zu lösen.
Der aktuell schnellste Supercomputer schafft 93.000TeraFLOPS (=93.000 * 10^12 FLOPS), das sind also 93PetaFLOPS, gerundet auf 100PFLOPS also ca 10^17 FLOPS.
Ein Jahr hat ungefähr 31536000 Sekunden (60*60*24*365), also ungefähr 3*10^7 Sekunden, für die weitere Berechnung 10^7.
50 Jahre lange Verdopplung, also 2^50 ist ungefähr 1,12*10^15, für die weitere Berechnung 10^15.
Also müsste der schnellste Supercomputer in 50 Jahren eine Rechenleistung von 10^17 * 10^7 * 10^15 = 10^39FLOPS haben.
Mit 100^600 / 10^39 bräuchte der Computer 10^561 Sekunden um das Problem zu lösen. Das sind 10^561 / 10^7 = 10^554 Jahre.
Aus der Vorlesung weiß ich, dass die Berechnung länger brauchen würde als die Erde existiert. Allerdings kommen mir 10^554 Jahre dann doch schon arg viel vor
Habe ich jetzt irgendwo einen kleinen Denkfehler, oder kommt das tatsächlich so hin?
