Suche Programm für optimale DVD Speicherplatznutzung

Ich habe noch nie von so einem Programm gehört, aber so eine DVD kann man auch selbst zusammenstellen. Einfach bei Nero nach Dateigröße sortieren lassen, dann so viele große Dateien wie möglich und dann wie es passt kleiner werden.
Was ich dir noch verraten kann: Das Problem ist NP-vollständig

Ich kenne jemanden, der hat dieses Problem bearbeitet, als er es noch für Disketten brauchte!

Im Moment wohl ein geeignetes Tool: Burn To The Brim

ACHTUNG: Braucht einen installierten ASPI-Layer. Wer noch keinen hat, kann FrogASPI verwenden (als WNASPI32.DLL in das SYSTEM32-Verzeichnis von Windows kopieren).
__

P.S.: Empfohlene Einstellungen für "DVD+R Single Layer" im Anhang.

Die "Dateisystemgröße" kann es nicht erkennen, weil die DVD erst mal noch leer ist, und nicht bekannt ist, wie viele Dateien drauf sollen; man reserviert eben so viel Platz, wie vermutlich für das Verwalten der Dateien notwendig sein wird. 2 MB für das "Inhaltsverzeichnis" sind also ziemlich großzügig ... aber ich habe dabei auch bedacht, dass Glitzerscheiben meist zuerst außen kaputtgehen. Ein wenig Reserve ist immer gut.

Noch wichtiger die untere Zeile: Wie viel Platz darf höchstens übrigbleiben, damit die DVD noch erzeugt wird? -- Wenn hier ein ziemlich kleiner Wert eingetragen wird, dann bleiben einige Dateien unbeachtet zurück, wenn die letzte DVD einfach nicht voll genug wird. Könnte nützlich sein, wenn man "inkrementell" immer mal wieder was wegbrennen will.

Der in der Hilfedatei vorgeschlagene Wert war "Kapazität - Dateisystemgröße". Hier würde auch eine gerade mal ansatzweise gefüllte DVD noch erstellt werden.

Zitat von Spawnhl

PS:Was hat JoeCool damit gemeint:

Zitat: "Was ich dir noch verraten kann: Das Problem ist NP-vollständig "

Das ist eine Herausforderung für meinen Spitznamen...

Wenn Informatiker Probleme lösen müssen, dann müssen sie versuchen, das sowohl korrekt als auch schnell zu schaffen. Oft ist nämlich der "triviale" Ansatz einer, der bei einem Anstieg der Datenmenge die benötigte Rechenzeit extrem erhöhen würde. Zur Abschätzung des Aufwandes wird ein Term angegeben, der eine Schreibweise wie eine Funktion hat, und die Größenordnung bzw. die Entwicklung der Rechenzeit abhängig von der Elementanzahl als Formel beschreibt.

Gern genommene Beispiele sind Sortier-Algorithmen. Menschen können eine überschaubare Anzahl von Elementen einer Menge schnell sortieren, weil sie in der Lage sind, ein Element unterbewußt mit mehreren zu vergleichen, und eine günstige Zielposition abzuschätzen. PCs dagegen können immer nur exakt zwei Elemente miteinander vergleichen.

Im trivialen Ansatz müsste ein PC jedes Element mit allen anderen Elementen vergleichen. In diesem Fall wäre die "Komplexität" quadratisch, der Informatiker schreibt das: O(n^2). Das ist leider eine höchst unvorteilhafte Komplexität: Bei der doppelten Anzahl zu sortierender Elemente würde dieser Ansatz vier Mal so lange dauern, bei der zehnfachen Anzahl hundert Mal so lange.

Zum Glück wurden für das Sortieren bereits effizientere Ansätze gefunden. Im Allgemeinen arbeiten diese über die Regel "Teile und herrsche": Anstatt die Gesamtmenge aller Elemente gleichzeitig zu sortieren, versucht man, jedes Element mit möglichst wenigen anderen Elementen vergleichen zu müssen, indem man es (meist rekursiv - also wiederholt, bis man nur noch je zwei Elemente hat) in Teilmengen unterteilt, und dann nur noch die äußeren Elemente der Teilmenge betrachtet und wenn nötig tauscht. Diese Verfahren haben eine logarithmische Komplexität: Das Sortieren der hundertfachen Anzahl würde hier deutlich weniger als hundert Mal so lange dauern, z.B. nur zehn Mal so lange (exakte Werte sind nicht interessant, nur Verhältnisse von Größenordnungen).

Polynome sind Summen aus Potenzen der gleichen Basis. Die Quadratfunktion ist ein sehr einfaches Polynom. Die Kombination "jedes Element mit allen anderen Elementen" hat quadratische Komplexität, und damit polynomiale. Es gibt allerdings auch "bösartigere" Probleme, die "nicht polynomiale (NP) Komplexität" haben. Dazu zählen Probleme der Kombinatorik, bei denen optimale Teilmengen aus Gesamtmengen gesucht werden. In deinem Fall handelt es sich um das Rucksackproblem (nach Richard Karp). Hier ist die Komplexität exponentiell. Das bedeutet: Mit jedem zusätzlichen Element wächst die nötige Zeit um eine Größenordnung.

n    1   2   3   4   5   6   7   8   9
2^n   2   4   8  16  32  64 128 256 512
3^n   3   9  27  81 243 729 ...

Ich weise noch einmal darauf hin: Bei der Betrachtung der Komplexität zählen nicht die exakten Werte, nur die Beschreibung des Verhaltens ihrer Entwicklung in Abhängigkeit von der Anzahl.

Der Vorteil an der Gruppierung von Problemen in Komplexitätsklassen ist: Wenn für ein Problem einer Klasse ein Ansatz gefunden wird, der eine geringere Komplexität hat, gilt dieser für alle Probleme der gleichen Klasse. Der Ansatz "Teile und herrsche" hat die Komplexität vieler polynomial komplexer Probleme reduzieren können auf lineare oder logarithmische Komplexität (optimal wäre "konstante Komplexität", aber die hat kaum ein Problem). Sollte irgend wann einmal ein Ansatz gefunden werden, der auch die Komplexität typischer NP-Probleme reduziert, wäre das eine Revolution in der Mathematik und Informatik...

Die Erklärung der NP-Vollständigkeit war mir nun leider zu schwammig. Um die zu verstehen, muss man wohl wenigstens ein paar Wochen Kombinatorik vor nicht allzu langer Zeit studiert haben.