History


Help on query formulation
Would you have known it? What are greedy algorithms? (Hättest Du es gewusst? Was sind gierige Algorithmen?) (German)
Monoid 32, No. 112, 7-10 (2012).
Aus dem Text: Für Optimierungsprobleme, deren Bewältigung einen unvertretbar hohen Rechenaufwand erfordert, hat die Mathematik Rechenverfahren (Algorithmen) entwickelt, deren Strategie darin besteht, dass sie nicht mehr nach optimalen, sondern nur noch nach annähernd optimalen Lösungen suchen. So lässt sich der Rechenaufwand im Allgemeinen beträchtlich verringern. Eine besonders wichtige Klasse von solchen effizienten Rechenverfahren sind die gierigen Algorithmen (greedy algorithms). Die Vorgehensweise des Häuptlings im Heiratsproblem beschreibt anschaulich den charakteristischen Ablauf eines solchen Algorithmus: Der Häuptling entschied sich in drei Schritten, wobei er bei jedem Schritt das dann jeweils noch vorhandene günstigste Angebot auswählte. Das strategische Muster eines beliebigen gierigen Algorithmus sieht ganz ähnlich aus: Ein gieriger Algorithmus ist ein in Schritten ablaufendes Rechenverfahren, das bei jedem Schritt nach einem vorgegebenen Kriterium die jeweils günstigste Teillösung bestimmt und aus diesen Teillösungen eine Gesamtlösung zusammensetzt.
Classification: P20 N60 K20 M40
Valid XHTML 1.0 Transitional Valid CSS!