Đang chuẩn bị liên kết để tải về tài liệu:
Handbook of algorithms for physical design automation part 10

Handbook of Algorithms for Physical Design Automation part 10 provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. It includes a personal perspective from Ralph Otten as he looks back on. | 5 Basic Algorithmic Techniques Vishal Khandelwal and Ankur Srivastava CONTENTS 5.1 Basic Complexity Analysis.73 5.2 Greedy Algorithms.75 5.3 Dynamic Programming.76 5.4 Introduction to Graph Theory.77 5.4.1 Graph Traversal Search.78 5.4.1.1 Breadth First Search.78 5.4.1.2 Depth First Search.78 5.4.1.3 Topological Ordering.79 5.4.2 Minimum Spanning Tree.79 5.4.2.1 Kruskal s Algorithm.80 5.4.2.2 Prim s Algorithm.80 5.4.3 Shortest Paths in Graphs .80 5.4.3.1 Dijkstra s Algorithm.81 5.4.3.2 Bellman Ford Algorithm.81 5.5 Network Flow Methods.82 5.6 Theory of NP-Completeness.84 5.7 Computational Geometry.85 5.7.1 Convex Hull .85 5.7.2 Voronoi Diagrams and Delaunay Triangulation.86 5.8 Simulated Annealing.86 References.87 This chapter provides a brief overview of some commonly used general concepts and algorithmic techniques. The chapter begins by discussing ways of analyzing the complexity of algorithms followed by general algorithmic concepts like greedy algorithms and dynamic programming. This is followed by a comprehensive discussion on graph algorithms including network flow techniques. This is followed by discussions on NP completeness and computational geometry. The chapter ends with the description of the technique of simulated annealing. 5.1 BASIC COMPLEXITY ANALYSIS An algorithm is essentially a sequence of simple steps used to solve a complex problem. An algorithm is considered good if its overall runtime is small and the rate at which this runtime increases with the problem size is small. Typically this runtime complexity is analytically measured modeled as a function of the total number of elements in the input problem. To make this analysis simpler several notations and conventions have been developed. 73 74 Handbook of Algorithms for Physical Design Automation -notation FIGURE 5.1 Complexity analysis. O -notation -Notation For a function h n h n represents the set of all functions that satisfy the following h n f n there exist positive constants c1 and c2 .