Download Algorithmen und Datenstrukturen im VLSI-Design: OBDD — by Prof. Dr. Christoph Meinel, Dr. Thorsten Theobald (auth.) PDF

By Prof. Dr. Christoph Meinel, Dr. Thorsten Theobald (auth.)

Eines der Hauptprobleme beim Chipentwurf besteht darin, daß die Anzahl der zu bewältigenden Kombinationen der einzelnen Chipbausteine ins Unermeßliche steigt. Hier hat sich eine sehr fruchtbare Verbindung zu einem Kerngebiet der Theoretischen Informatik, dem Gebiet des Entwurfs von Datenstrukturen und effizienten Algorithmen, herstellen lassen: das Konzept der geordneten binären Entscheidungsgraphen, das in zahlreichen CAD-Projekten zu einer beträchtlichen Leistungssteigerung geführt hat. Die Autoren stellen die Grundlagen dieses interdisziplinären Forschungsgebiets dar und behandeln wichtige Anwendungen aus dem rechnergestützten Schaltkreisentwurf.

Show description

Read Online or Download Algorithmen und Datenstrukturen im VLSI-Design: OBDD — Grundlagen und Anwendungen PDF

Similar german_4 books

Silizium-Planartechnologie: Grundprozesse, Physik und Bauelemente

Die Grundlagen der Mikroelektronik werden kompakt und in leicht verständlicher shape vorgestellt. Der Leser erfährt, wie integrierte Schalkreise hergestellt werden, wie sie funktionieren und wie ihre Grundelemente physikalisch beschrieben werden können. Aufgrund der großen Bedeutung von Simulationsprogrammen in der Silizium-Planartechnologie wird ergänzend auf CAD-Werkzeuge von der Prozesssimulation (z.

Additional info for Algorithmen und Datenstrukturen im VLSI-Design: OBDD — Grundlagen und Anwendungen

Example text

6. Seien A und B zwei Probleme. A heijJt Polynomialzeitreduzierbar auf B, wenn unter der Annahme, dajJ beliebige Instanzen von B in konstanter Zeit gelost werden konnen, ein Polynomiaizeit-Algorithmus fUr A existiert. Wir schreiben A ~p B. 7. Aus A ~p B und BE P folgt A E P. 8. 1. Ein Problem A heijJt NP-hart, wenn fur aile B E NP gilt: B ~p A. 2. Ein Problem A heijJt NP-vollstiindig, wenn A sowohl NP-hart ist als auch A E NP gilt. 9. Sei A ein NP-vollstiindiges Problem. Dann gilt: 1. Falls A E P, dann ist P = NP.

Zustand Eingabe qo qo ql ql q2 q2 q3 q3 0 1 0 1 0 1 0 1 Nachfolgezustand qo ql qo q2 qo q3 qo qo Ausgabe 1 0 1 0 1 0 1 1 Abb. 6. 8 Referenzen Die in diesem Kapitel behandelten Themen gehOren samtlich zu den Grund'agen der Informatik und der diskreten Mathematik. Nachfolgend solI deshalb nur eine kleine Auswahl von relevanten Lehrbiichern und Gesamtdarstellungen gegeben werden: Ausfiihrliche Informationen zu den Gebieten der diskreten Mathematik k6nnen in [Aig94] gefunden werden. Der Entwurf von Algorithmen und Datenstrukturen wird in [Mei91] und [OW96] behandelt.

1) Sei a = (al, ... , an) eine Belegung fUr die Variablen Xl, ... , Xn . an = folgt die Aussage aus der Beziehung I(al, ... , an) = , an_t}. 1m Fall an = 1 folgt sie von der Beziehung I(al, ... , an) = ,an-l)' 0 ° Eine Unterfunktion geht durch Konstantsetzung einer oder mehrerer Eingangsvariablen hervor. Aus diesem Grund kann jede Unterfunktion einer Funktion f E Bn durch einen Vektor c E {O, 1, id}n beschrieben werden. Wenn die i-te Komponente von c konstant oder 1 ist, wird die i-te Eingangsvariable Xi von I auf 0 bzw.

Download PDF sample

Rated 4.05 of 5 – based on 37 votes