Engineering Informatics

Foreword to the First Edition xiii Preface to the First Edition xvii Preface to the Second Edition xxi 1 Fundamental Logic and the Definition of Engineering Tasks 1 1.1 Three Types of Inference 1 1.2 Engineering Tasks 3 1.3 A Model of Information and Tasks 5 1.4 Another Task Definition 8 1.5 The Five Orders of Ignorance 9 1.6 Summary 9 Exercises 10 References 10 2 Algorithms and Complexity 11 2.1 Algorithms and Execution Time of Programs 12 2.1.1 Program Execution Time versus Task Size 12 2.2 'Big Oh' Notation 14 2.2.1 Definition of the Big Oh Notation 15 2.2.2 Big Oh and Tightness of Bound 16 2.2.3 Classification of Functions 20 2.2.4 Examples 21 2.2.5 Tractability and Algorithm Optimality 30 2.3 Practical Methods for Determining the Complexity of Algorithms 30 2.4 P, NP and NP-Completeness 34 2.4.1 Zero-One Integer Programming (ZOIP) Problem 35 2.4.2 Classes of NP-Complete Problems 36 2.5 Summary 37 Exercises 37 Reference 40 Further Reading 40 3 Data Structures 41 3.1 Introduction 41 3.2 Definitions 42 3.3 Derived Data Types 42 3.3.1 Examples of Derived Data Types 43 3.3.2 User-Defined Data Types 45 3.4 Abstract Data Types 46 3.4.1 Linked Lists 47 3.4.2 Graphs 50 3.4.3 Trees 52 3.4.4 Stacks 56 3.4.5 Queues 60 3.5 An Example: Conceptual Structural Design of Buildings 63 3.6 Network Science 70 3.6.1 Types of Networks 71 3.7 Hashing 73 3.8 Summary 74 Exercises 74 Further Reading 79 4 Object Representation and Reasoning 81 4.1 Introduction 81 4.2 Grouping Data and Methods 82 4.3 Definitions and Basic Concepts 83 4.3.1 Classes and Objects 83 4.3.2 Object-Oriented Programming (OOP) 84 4.3.3 Messages 84 4.4 Important Characteristics of Objects 84 4.4.1 Encapsulation of Data and Methods 84 4.4.2 Message-Passing Mechanism 85 4.4.3 Abstraction Hierarchy 86 4.4.4 Secondary Features of Object Representation 88 4.4.5 Decomposition versus Abstraction 89 4.5 Applications Outside Programming 90 4.5.1 Knowledge Representation 91 4.5.2 User Interfaces 91 4.5.3 Off-the-Shelf Components 91 4.5.4 Product Models 91 4.6 An Object-Oriented Design Methodology 93 4.6.1 Single versus Multiple Inheritance 93 4.6.2 Message-Passing Architecture 94 4.7 Summary 95 Exercises 95 References 101 Further Reading 101 5 Database Concepts 103 5.1 Introduction 103 5.2 Basic Concepts 104 5.2.1 Initial Definitions 104 5.2.2 Evolution of Types of Databases 104 5.2.3 The Three-Level Architecture 106 5.3 Relational Database Systems 106 5.3.1 The Relational Model 107 5.3.2 Limitations of Relational Databases 111 5.3.3 Accessing Data in Relational Databases 112 5.4 Relational Database Design 114 5.4.1 First Normal Form 114 5.4.2 Second Normal Form 115 5.4.3 Third Normal Form 118 5.4.4 Boyce-Codd and Higher Normal Forms 119 5.4.5 Importance of Database Design 120 5.5 Transaction Processing 120 5.5.1 Definition of Transaction 121 5.5.2 Implementing Transactions 122 5.5.3 Properties of Transactions 124 5.6 Other Types of Database 124 5.6.1 Object-Oriented Databases 124 5.6.2 Geographical Databases 124 5.6.3 Multimedia Database Systems 125 5.6.4 Distributed Databases 125 5.7 Summary 126 Exercises 127 Transaction A 131 Transaction B 131 Reference 131 Further Reading 131 6 Computational Mechanics 133 6.1 Introduction 133 6.1.1 Challenges of Computational Mechanics 134 6.2 From Physical Principles to Practical Systems 135 6.3 Methods for Finding Solutions 137 6.3.1 Galerkin Method 137 6.3.2 Remarks 139 6.4 Issues in Computer-Aided Engineering 139 6.4.1 Accuracy 140 6.4.2 Speed 141 6.4.3 User Interaction 142 6.5 Summary 142 References 142 Further Reading 142 7 Constraint-Based Reasoning 143 7.1 Introduction 143 7.2 Terminology 145 7.3 Constraint-Solving Methods 146 7.3.1 Levels of Consistency for Label Propagation 147 7.3.2 Global Consistency in Label Propagation 148 7.3.3 Constraint Propagation 149 7.4 Reasoning with Constraints on Discrete Variables 149 7.4.1 CSP Complexity for Discrete Variables 151 7.5 Reasoning with Constraints on Continuous Variables 151 7.5.1 Constraint-Based Support for Collaborative Work 152 7.6 Summary 156 References 156 8 Optimization and Search 157 8.1 Introduction 157 8.2 Basic Concepts 158 8.2.1 Types of Optimization Problem 160 8.2.2 Formulating Optimization Tasks 161 8.2.3 Representing Search Spaces 163 8.2.4 Representing Constraints 164 8.2.5 Some Optimization Problems 165 8.3 Classification of Methods 167 8.4 Deterministic Optimization and Search 169 8.4.1 Special Cases 169 8.4.2 Deterministic Methods 174 8.5 Stochastic Methods 179 8.5.1 Pure Global Random Search 182 8.5.2 Local Search with Multiple Random Starts 182 8.5.3 Simulated Annealing 182 8.5.4 Genetic Algorithms 184 8.5.5 Controlled Random Search 184 8.5.6 PGSL 185 8.6 A Closer Look at Genetic Algorithms 188 8.6.1 Representation: Genetic Encoding 188 8.6.2 Evaluating an Individual 189 8.6.3 Creating the Initial Population 189 8.6.4 The Fitness Function 190 8.6.5 Reproduction 190 8.6.6 Mutation 192 8.7 Summary of Methods 192 Exercises 193 References 198 Further Reading 198 9 Knowledge Systems for Decision Support 199 9.1 Introduction 199 9.2 Important Characteristics of Knowledge Systems 200 9.3 Representation of Knowledge 202 9.3.1 Representation of Knowledge in Knowledge Systems 204 9.4 Reasoning with Knowledge 205 9.4.1 Rule Selection and Conflict Resolution 207 9.5 Importance of the User Interface 207 9.6 Maintenance of Knowledge 208 9.7 Model-based Reasoning 209 9.8 Case-Based Reasoning 209 9.8.1 Stages of Case-Based Reasoning 210 9.9 Summary 215 Reference 215 Further Reading 215 10 Machine Learning 217 10.1 Introduction 217 10.2 Improving Performance with Experience 218 10.3 Formalizing the Learning Task 220 10.3.1 Searching Hypothesis Spaces 224 10.4 Learning Algorithms 224 10.4.1 Rote Learning 225 10.4.2 Statistical Learning Techniques 226 10.4.3 Deductive Learning 230 10.4.4 Exploration and Discovery 231 10.5 A Closer Look at Artificial Neural Networks 231 10.5.1 Types of Neural Network 235 10.5.2 Learning in Neural Networks 236 10.5.3 Summary of Neural Networks 237 10.6 Support Vector Machines 237 10.6.1 Support Vector Classification 237 10.6.2 Support Vector Regression 240 10.7 Summary 240 Exercises 241 References 242 Further Reading 242 11 Geometric Modelling 243 11.1 Introduction 243 11.2 Engineering Applications 244 11.2.1 Criteria for Evaluating Representations 244 11.3 Mathematical Models for Representing Geometry 245 11.3.1 Two-Dimensional Representation of Simple Shapes 245 11.3.2 Curves Without Simple Mathematical Representations 247 11.3.3 B´ezier Curves 248 11.3.4 Mathematical Representation of Simple Surfaces 249 11.3.5 B´ezier Patches 250 11.3.6 Mathematical Representation of Regular-Shaped Solids 251 11.4 Representing Complex Solids 252 11.4.1 Primitive Instancing 252 11.4.2 Mesh Representations 253 11.4.3 Sweep Representations 255 11.4.4 Boundary Representations 257 11.4.5 Decomposition Models 258 11.4.6 Constructive Solid Geometry (CSG) 260 11.5 Applications 263 11.5.1 Estimation of Volume 263 11.5.2 Finite Element Mesh for a Spread Footing 264 11.5.3 3D Graphical View of a Structure 266 11.6 Summary 267 Further Reading 267 12 Computer Graphics 269 12.1 Introduction 269 12.2 Tasks of Computer Graphics 270 12.3 Display Devices 270 12.3.1 Types of Display Device 271 12.3.2 From Geometric Representations to Graphical Displays 272 12.4 Representing Graphics 272 12.4.1 Representing Colours 273 12.4.2 Coordinate System 273 12.4.3 Bitmap Representations 274 12.4.4 Higher-Level Representations 275 12.5 The Graphics Pipeline 276 12.5.1 Modelling Transformations 276 12.5.2 Viewing Transformations 280 12.5.3 Scan Conversion 285 12.6 Interactive Graphics 287 12.7 Graphical User Interfaces (GUI) and Human-Computer Interaction (HCI) 288 12.7.1 Engineer-Computer Interaction 288 12.8 Applications 289 12.8.1 4D Simulations 289 12.8.2 Navigating Multidimensional Solution Spaces 289 12.8.3 Computer Vision and Image Processing 290 12.8.4 Laser Scanning 290 12.9 Summary 292 References 292 Further Reading 292 13 Distributed Applications and the Web 293 13.1 Introduction 293 13.1.1 A Simple Example of a Client-Server System 294 13.1.2 Definitions 295 13.1.3 Trends Driving C/S Architecture 296 13.2 Examples of Client-Server Applications 297 13.2.1 File Servers 297 13.2.2 FTP Servers 298 13.2.3 Database Servers 298 13.2.4 Groupware Servers 298 13.2.5 Object Servers 298 13.2.6 Operating System Servers 299 13.2.7 Display Servers 299 13.2.8 Web Servers 300 13.2.9 Application Servers 300 13.3 Distinctive Features of C/S Systems 300 13.3.1 Asymmetrical Protocol 300 13.3.2 Message-Based Mechanism 301 13.3.3 Why are Protocols Important? 304 13.4 Client-server System Design 304 13.4.1 Three-Tier Architecture 305 13.4.2 Application Partitioning 306 13.5 Advantages of Client-Server Systems 307 13.6 Developing Client-Server Applications 307 13.6.1 TCP/IP Sockets 308 13.6.2 Other Middleware Options 309 13.7 The World Wide Web 309 13.7.1 Limitations of Exchanging Only Static Information 310 13.7.2 Common Gateway Interface 310 13.7.3 Engineering Applications on the Web 311 13.7.4 Other Models for Dynamic Information Exchange 311 13.8 Peer-to-Peer Networks 312 13.8.1 Information Interchange Through P2P Networks 314 13.8.2 P2P Networks for Engineering Applications 314 13.8.3 Advantages of Peer-to-Peer Networks 315 13.8.4 Issues and Challenges 315 13.9 Agent Technology 316 13.9.1 Issues in Multi-Agent Systems 317 13.10 Cloud Computing 318 13.11 Complexity 319 13.12 Summary 319 Reference 320 Further Reading 320 Index 321