Please choose your delivery country and your customer group
Eine Reihe von Beitraegen auf der 12. Arbeitstagung 'Entwurf von Schaltsystemen und Systementwurf' (1983) machte deutlich, in welchem Masse mit der Entwicklung von Software zur Unterstuetzung des Schaltkreisentwurfs Algorithmen zur Loesung komplizierter kombinatorischer Probleme benoetigt werden. Darunter befindet sich eine Vielzahl von Aufgaben, fuer die alle bisher gefundenen Loesungsverfahren die Eigenschaft haben, dass ihre Zeitkompliziertheit mit der Aufgabengroesse exponentiell waechst. Dazu gehoeren z.B. Faerbbarkeits-, Ueberdeckungs- und Zerlegungsprobleme fuer Graphen genauso wie Probleme der linearen und der quadratischen Optimierung. In der Praxis koennen daher solche Aufgaben bereits bei relativ kleiner Problemgroesse nicht mehr exakt geloest werden. Die prinzipiellen Moeglichkeiten der algorithmischen Bewaeltigung solcher Problemklassen koennen folgendermassen klassifiziert werden: Einschraenkung der Aufgabe bzgl. der zu bearbeitenden Eingaben; approximative Algorithmen; stochastische Algorithmen; determinierte Algorithmen, heuristische Algorithmen.