Partitionierungsproblem

Das Partitionierungsproblem ist ein mathematisches Problem, das durch seine NP-Schwere eine große Bedeutung in der Informatik erlangt hat. Es beschäftigt sich mit der Frage, einen Algorithmus zu finden, mit dem sich Zahlen in additive Bestandteile zerlegen lassen. Es ist möglicherweise "das einfachste schwere Problem"^[1].

Erläuterung

Wie viele Möglichkeiten gibt es, eine natürliche Zahl als Summe von natürlichen Zahlen zu schreiben?

Die Lösung für die Zahl 4 ist simpel.

• 4 = 1+1+1+1
• 4 = 2+1+1
• 4 = 2+2
• 4 = 3+1
• 4 = 4

Für die Zerlegung der Zahl 6, angefangen bei der Zerlegung in lauter Einsen 1+1+1+1+1+1=6 über 2+2+2=6 bis 6=6, gibt es bereits genau 11 Möglichkeiten. Der indische Mathematiker S. Ramanujan kam sehr schnell auf eine Vielzahl von Varianten, als er eine Liste der Zerlegungen aller Zahlen bis 200 berechnete. Die Zahl 200 lässt sich in genau 3972999029388 Additionsvarianten aufspalten.

Natürliche Zahl	Anzahl der Zerlegungen	Kongruenzen
1	1
2	2
3	3
4	5	5
5	7	7
6	11	11
7	15
8	22
9	30	5
10	42
11	56
12	77	7
13	101
14	135	5
15	176
16	231
17	297	11
18	385
19	490	5 und 7
20	627

Kongruenzen

Ramanujan entdeckte bei seinen Studien eine Gesetzmäßigkeit. Beginnt man mit der 4 und springt um 5, so erhält man immer Vielfache der Sprungzahl 5 als Zerlegungszahlen. Beginnt man bei der 6 und springt um 11, so erhält man Vielfache von 11. Ramanujan entdeckte weitere derartige Beziehungen, auch Kongruenzen genannt, als er die Potenzen der Primzahlen 5, 7 und 11 sowie deren Produkte als Sprungzahlen untersuchte. Der amerikanische Zahlentheoretiker Ken Ono konnte zeigen, dass es für alle Primzahlen größer 3 Kongruenzen gibt. Ob dies für die beiden kleinsten Primzahlen, die 2 und 3, und deren Vielfache ebenso gilt, konnte Ono nicht nachweisen.

Partitionierungsfunktion

Partitionierungsfunktionen sind Algorithmen der Informatik, mit denen sich für jede natürliche Zahl beliebige Zerlegungen in natürliche Zahlen berechnen lassen.

Man unterscheidet dabei zwischen Berechnungsfunktionen und Näherungsformeln.

Rekursive Generierungsfunktion

Eine einfache Generierungsfunktion gewinnt man aus der Umkehrung von Eulers Funktion

$\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \frac{1}{1-x^k}$

man erhält

$f(x)=\frac{1}{\prod_{k=1}^\infty (1-x^k)} = 1+1x+2x^2+3x^3+5x^4+...$

D.h. dass die Koeffizienten der Polynomdarstellung von f(x) den Werten von P(n) entsprechen.

Anwendungen

Die Bedeutung des Partitionierungsproblems liegt nur indirekt in der Partitionierung einer Zahl in kleinere Einheiten. Vielmehr lässt sich ein Problem durch die Umkehrung der Partitionierung beschreiben.

Einführendes Beispiel

Wenn eine Gruppe Kinder Mannschaften bilden will, um ein Spiel zu spielen, wird normalerweise gewählt. Dabei steht ein Pool von potentiellen Spielern am Spielfeldrand, und die Mannschaftsführer beider Mannschaften wählen abwechselnd so lange, bis jeder Teilnehmer einer Mannschaft zugeordnet wurde. Der Sinn dieses Rituals besteht darin, dass am Ende etwa gleich starke Mannschaften gegeneinander antreten.

Formal könnte man das Problem wie folgt spezifizieren:

• Es existiert eine Menge von Spielern.
• Die Spieler besitzen verschiedene Fähigkeiten. Diese könnte man verallgemeinernd als Spielstärke auf eine Skala von 1 bis 10 abbilden.
• Gesucht ist die Aufteilung in 2 Gruppen, bei der die Spielstärken der einzelnen Spieler addiert in beiden Gruppen gleich sind.

Auf das Partitionierungsproblem könnte man vorhergehende Beschreibung abbilden, indem die Spielstärken aller Spieler zum Wert X addiert werden. Damit steht fest, dass Gruppe A sowie Gruppe B jeweils eine Spielstärke von $\frac{X}2$ erreichen müssen, damit das Spiel ausgeglichen ist.

Damit wird schnell deutlich, das es einen einfachen Algorithmus gibt, sich einer Lösung des Problems anzunähern, indem abwechselnd der jeweils beste verbliebene Spieler gewählt wird. Ebenso ist ersichtlich, dass es unter Umständen keine perfekte Lösung des Problems gibt.

Inakzeptabel wird dies bei der Herausgabe von Wechselgeld an einem Fahrkartenautomaten. Oftmals ist jedoch auch eine näherungsweise Lösung des Problems hilfreich, um stark ungünstige Kombinationen auszuschließen. ^[2]

Parallelverarbeitung in Computern

Ein wichtiger Bereich, in dem das Partitionierungsproblem zum Tragen kommt, ist die Verteilung von Rechenaufgaben in Multiprozessorsystemen. Das Problem besteht darin, bei n zur Verfügung stehenden CPU oder Rechenkernen genau n Mengen von Rechenaufgaben mit gleicher Laufzeit zu bestimmen.

Allgemein: Graphpartitionierung

Hauptartikel: Graphpartitionierung

Um in einem rechenintensiven Computerprogramm die Vorteile eines parallelen Systems optimal ausnutzen zu können, muss dieses zwei Kriterien erfüllen:

• Die Rechenlast muss gleichmäßig auf die Recheneinheiten verteilt werden.
• Die zur Abarbeitung des Programms nötige Kommunikation zwischen den Recheneinheiten soll möglichst klein gehalten werden, da diese immense Ausführungszeit beansprucht.

Parallele Suchalgorithmen

Ein klassisches Problem für Künstliche Intelligenz ist die effiziente Abarbeitung von Suchbäumen. Zu den damit gegebenen Aufgabenstellungen gehören u.a. die Suche nach kürzesten Wegen, die Lösung des Constraint Satisfaction Problem oder die hier betrachtete Lösung der diskreten Optimierung. Für die Optimierung wird oft das aus dem Operations Research bekannte Baumsuchverfahren „Branch-and-Bound“ verwendet. In der Künstlichen Intelligenz ist es unter dem Namen A*-Algorithmus bekannt.

Typischerweise sind die diskreten Optimierungsprobleme, wie z.B. das Problem des Handlungsreisenden, das Rucksackproblem oder die Maschinenbelegungsplanung, von hoher Komplexität und somit durch lange Berechnungszeiten gekennzeichnet. Da die technische Entwicklung sequentieller Rechner zunehmend an physikalische Grenzen stößt, ist die Verwendung massiver Rechenparallelität eine vielversprechende Alternative. Bei Parallelrechnern muss aber eine ausgeglichene Beschäftigung der Prozessoren zur Aufrechterhaltung der Effizienz gewährleistet sein. Gerade für feinkörnige Parallelrechner mit mehreren 10.000 Prozessorelementen stellt die dazu erforderliche Lastverteilung der anstehenden Rechenarbeit auf die Prozessoren ein zentrales Problem dar.^[3]

Partitionierung in Datenbanken

Neben dem transparenten Betrieb einer logischen Datenbank auf mehrere Rechnerknoten findet vor allem in Bereich des Datawarehouse zusätzlich eine Partitionierung des Datenbestandes statt. Logisch zusammenhängende Daten einer Tabelle werden dabei in Gruppen sortiert und horizontal fragmentiert. Dies ist vorteilhaft zur Abarbeitung von Suchanfragen, da aus der Anfrage meist direkt ersichtlich ist welche Teilpartitionen zur Anfragebearbeitung herangezogen werden müssen. Andere Teile der logischen Tabelle werden dann nicht mehr durchsucht. Erweitert werden kann das Konzept durch vertikale Fragmentierung, bei der über die Spalten einer Tabelle gruppiert und fragmentiert wird, sowie Verteilung der einzelnen Fragmente auf verschiedene Rechnerknoten.

Suboptimale Fragmentierung kann zu mäßigem Performancegewinn führen. Optimal zur effizienten Netzplanung ist die Aufteilung der Datensätze mit der höchsten Anfragefrequenz in kleinere Partitionen. Zu Zwecken der Archivierung kann auch die Partitionierung in aktive und passive Daten sinnvoll eingesetzt werden.

Beispiel: Tabelle Aufträge

• Partition 1: Jahre 2000-2005
• Partition 2: Jahre 2005-2007
• Partition 3: Jahr 2008

Anwendung in Netzwerken

Das Prinzip der Lastverteilung ist in vielen Bereichen essentiell, beispielsweise für den Betrieb großer Datenbanken, Serveranwendungen oder den Betrieb und die Planung von Netzwerkinfrastruktur.

DNS Namensauflösung

Hauptartikel: Lastverteilung per DNS

Bereits mittelgrosse Internetseiten verursachen oft zu viele Anfragen, als das sie von einem Computersystem beantwortet werden könnten. Es hat sich herausgestellt, das die dynamische Auflösung von Domainnamen zu wechselnden IP-Adressen ein wirkungsvolles Verfahren zur Umleitung der Nutzeranfragen an verschiedene, aber in ihrer Funktion gleichartige Computersysteme darstellt.

Das Konzept des Round Robin-DNS hat sich als günstige Lösung herausgestellt. Es verbindet einen geringen administrativen Aufwand mit ausreichend Nutzen. Dieser kann aufgrund des geschickten Einsatzes von IPs auch im Falle eines Ausfalls ohne Probleme weiterarbeiten, ohne am DNS-System an sich Eingriffe vornehmen zu müssen. Das Round Robin wird beispielsweise über den Namen www.bildungsmarkt-sachsen.de angesetzt und dieser wird auf die IPs abgebildet, die den Namen bms1.hrz.tu-chemnitz.de und bms2.hrz.tu-chemnitz.de zugeordnet sind. ^[4]

Planung von Funknetzen

Zum Betrieb eines Drahtlosnetzwerkes ist es wichtig, die erreichte Granularität der Netzabdeckung mit den entstehenden Kosten abzuwägen.

Das Problem besteht formal darin, eine Partitionierung für ein Gebiet A zu finden, so dass die entstehenden Regionen mit der Menge zur Verfügung stehender Sensoren die höchste bzw. mit so wenig Sensoren wie möglich die gewünschte Granularität aufweisen.

Für eine optimale Entscheidung sind verschiedene Parameter zu berücksichtigen. Diese werden durch eine lineare Gewichtungsfunktion zu einem (variablen) Wert addiert werden über den die Partitionierung erfolgt.

Es ist ebenso möglich, dass einige Regionen des Netzes wichtiger als andere sind und daher mit mehr Sensoren ausgestattet werden müssen (sog. hot spots). Werden mehr Sensoren aufgestellt als benötigt werden, kommt es seltener zu Engpässen und zu einer höheren Ausfalltoleranz bei Fehlfunktionen einzelner Sensoren. Zudem gewinnt Energieeffizienz zunehmend an Bedeutung. Netze können durch geschickte Optimierung in Zeiten geringer Auslastung einzelne Sensoren abschalten, wenn ihr Abdeckungsbereich derart überlappt, dass er durch benachbarte Sensoren mitversorgt wird.

Verwandte Probleme

Flaschenhals Graph-Partitionierungsproblem

Das Flaschenhals Graph-Partitionierungsproblem besteht in der Verteilung der Eckpunkte eines ungerichtet Kanten-gewichteten Graphen in zwei gleich große Mengen, so dass das größte Kantengewicht (maximum) in den Teilmengen minimal wird. Im Gegensatz zum Graph-Partitionierungsproblem (Graphpartitionierung), bei dem die Summe der Gewichte in den Teilmengen minimiert wird, ist die Flaschenhals-Version kein NP-Schweres Problem sondern lässt sich polynominaler Zeit lösen.

Einzelnachweise

1. ↑ Weisstein, Eric W. : Number Partitioning Problem. . From MathWorld--A Wolfram Web Resource. [1]
2. ↑ Brian Hayes: The easiest Hard Problem [2]. American Scientist . April 2002
3. ↑ Dominik Heinrich: [3].1995
4. ↑ Bildungsmarkt Sachsen: [4]