Algorithmen und Datenstrukturen im VLSI-Design

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.

Dr. sc. nat. Christoph Meinel (1954) is President and CEO of the Hasso-Plattner-Institut for IT-Systems Engineering (HPI) and full professor (C4) for computer science at the University of Potsdam. His research field is Internet and Web Technologies and Systems. Beside he is a teacher at the HPI School of Design Thinking, a visiting professor at the Computer Science School of the Technical University of Beijing (China) and a research fellow of the interdisciplinary center SnT at the University of Luxembourg. Since 2008 he is program director of the HPI-Stanford Design Thinking Research Program. He is author or co-author of 10 text books and monographs and has published more than 350 per-reviewed scientific papers in highly recognised international scientific journals and conferences. Harald Sack is Senior Researcher at the Hasso Plattner-Institute for IT-Systems Engineering (HPI) at the University of Potsdam. After graduating in computer science at the University of the Federal Forces Munich Campus in 1990, he worked as systems/network engineer and project manager in the signal intelligence corps of the German federal forces from 1990-1997. In 1997 he became an associated member of the graduate program 'mathematical optimization' at the University of Trier and graduated with a PhD thesis on formal verification in 2002. From 2002-2008 he did research and teaching as a postdoc at the Friedrich-Schiller-University in Jena and since 2007 he has a visiting position at the HPI, where he now is head of the research group 'semantic technologies'. His areas of research include multimedia retrieval, semantic web technologies, knowledge representations, machine learning and semantic enabled retrieval. Since 2008 he also serves as general secretary of the German IPv6 council.

1. Einleitung.- 2. Grundlagen.- 2.1 Aussagen und Prädikate.- 2.2 Mengen, Relationen und Funktionen.- 2.3 Graphen.- 2.4 Algorithmen und Datenstrukturen.- 2.5 Komplexität von Algorithmen.- 2.6 Hashverfahren.- 2.7 Endliche Automaten und Finite-State-Maschinen.- 2.8 Referenzen.- I. Datenstrukturen für Schaltfunktionen.- 3. Boolesche Funktionen.- 4. Klassische Darstellungen.- 5. Anforderungen an Datenstrukturen für die formale Schaltkreisverifikation.- II. OBDDs: Eine effiziente Datenstruktur.- 6. OBDDs - Geordnete binäre Entscheidungsgraphen.- 7. Effiziente Implementierung von OBDDs.- 8. Einfluß der Variablenordnung auf die Komplexität von OBDDs.- 9. Optimierung der Variablenordnung.- III. Anwendungen und Erweiterungen.- 10. Analyse sequentieller Systeme.- 11. Symbolisches Model Checking.- 12. Varianten und Erweiterungen von OBDDs.- 13. Transformationstechniken zur Optimierung.