Over the past century, advancements in computer science have consistently resulted from extensive mathematical work. Even today, innovations in the digital domain continue to be grounded in a strong mathematical foundation. To succeed in this profession, both today's students and tomorrow's computer engineers need a solid mathematical background. The goal of this book series is to offer a solid foundation of the knowledge essential to working in the digital sector. Across three volumes, it explores fundamental principles, digital information, data analysis, and optimization. Whether the reader…mehr
Over the past century, advancements in computer science have consistently resulted from extensive mathematical work. Even today, innovations in the digital domain continue to be grounded in a strong mathematical foundation. To succeed in this profession, both today's students and tomorrow's computer engineers need a solid mathematical background. The goal of this book series is to offer a solid foundation of the knowledge essential to working in the digital sector. Across three volumes, it explores fundamental principles, digital information, data analysis, and optimization. Whether the reader is pursuing initial training or looking to deepen their expertise, the Mathematics for Digital Science series revisits familiar concepts, helping them refresh and expand their knowledge while also introducing equally essential, newer topics.
Gérard-Michel Cochard is Professor Emeritus at Université de Picardie Jules Verne, France, where he has held various senior positions. He has also served at the French Ministry of Education and the CNAM (Conservatoire National des Arts et Métiers). His research is conducted at the Eco-PRocédés, Optimisation et Aide à la Décision (EPROAD) laboratory, France. Mhand Hifi is Professor of Computer Science at Université de Picardie Jules Verne, France, where he heads the EPROAD UR 4669 laboratory and manages the ROD team. As an expert in operations research and NP-hard problem-solving, he actively contributes to numerous international conferences and journals in the field.
Inhaltsangabe
Preface ix Chapter 1. Linear Modeling for Two-Dimensional Data 1 1.1. Basic statistics 1 1.2. Linear adjustment 3 1.3. Linear correlation 7 Chapter 2. Multidimensional Data Analysis 13 2.1. Multidimensional tables 14 2.2. Analysis of a point cloud 24 2.2.1. Spatial analysis of individuals 24 2.2.2. Analysis in variable space 30 2.2.3. Link between the two spaces 32 2.3. Principal component factor analysis 35 2.3.1. Principles 35 2.3.2. Principal component factor analysis in practice 41 2.4. Appendix: useful software 48 2.5. Tanagra software 48 2.6. R software 56 Chapter 3. Introduction to Automatic Classification 65 3.1. Similarity and distance 66 3.1.1. Similarity, dissimilarity 66 3.1.2. Distance 67 3.2. Basics of information theory 69 3.3. Classification methods 78 3.4. Classification by partitioning 80 3.4.1. Partitioning principle 80 3.4.2. Inertia 81 3.4.3. Mobile center algorithm 82 3.5. Hierarchical classification 89 3.5.1. Principle 89 3.5.2. Aggregation strategies 90 3.5.3. Ward's aggregation strategy 98 3.6. Appendices 101 3.6.1. Huygens-König theorem 101 3.6.2. Classification software 103 Chapter 4. Linear Programming 109 4.1. An introductory example 110 4.2. General formulation 113 4.3. Geometry of a linear program 116 4.4. Simplex algorithm 118 4.5. Two-phase method. 129 4.6. Duality 135 4.7. Degeneracy 139 4.8. Introduction to integer linear programming 140 4.8.1. Gomory cuts 140 4.8.2. Branch and Bound algorithm 151 Chapter 5. Elements of Graph Theory 159 5.1. Definition and representations of a graph 160 5.1.1. Graphical representation 160 5.1.2. Tables associated with a graph 161 5.2. Main concepts and technology 162 5.2.1. Elements of a graph 163 5.2.2. Analysis of graph structure 168 5.3. Transitive closure of a graph's vertices 172 5.4. Decomposition of a directed graph into strongly connected components 173 5.5. Trees 175 5.5.1. Introduction 175 5.5.2. Trees in a graph 175 5.5.3. Spanning tree in a graph 177 5.6. Finding a fundamental system of independent cycles of a connected graph 179 5.7. Extremum spanning tree 180 5.7.1. General information 180 5.7.2. Extremum spanning tree search algorithms 180 Chapter 6. Path Optimization 187 6.1. Extremal-length paths 188 6.1.1. General information 188 6.1.2. Solving algorithms 189 6.1.3. Searching for ¿ -extremal paths 204 6.2. Hamiltonian path search 205 6.2.1. Decomposition into strongly connected components 205 6.2.2. Branch and Bound algorithm 207 Chapter 7. Transportation Problems 219 7.1. Maximum flow 220 7.1.1. General 220 7.1.2. Ford-Fulkerson theorem 223 7.1.3. Ford-Fulkerson algorithm 224 7.1.4. Practical solution method 230 7.2. Least cost transportation 236 7.2.1. Issues 236 7.2.2. Northwest Corner algorithm 238 7.2.3. Least cost method 240 7.2.4. Balas-Hammer or Vogel's algorithm 243 7.2.5. Stepping stone algorithm 246 7.2.6. Inequality of supply and demand 256 7.2.7. Unconnected graph and degeneration 257 7.2.8. Potentials and dual program 261 7.3. Assignment problems 263 7.3.1. Issues 263 7.3.2. Hungarian algorithm 269 Chapter 8. Scheduling Problems 279 8.1. Planning a project 280 8.1.1. Introduction 280 8.1.2. Earliest and latest date method 283 8.1.3. Gantt chart 289 8.2. Flow-shop problem 291 8.2.1. Johnson's algorithm for two machines 293 8.2.2. Case of three machines 297 8.3. The job-shop problem 306 References 311 List of Authors 313 Index 315
Preface ix Chapter 1. Linear Modeling for Two-Dimensional Data 1 1.1. Basic statistics 1 1.2. Linear adjustment 3 1.3. Linear correlation 7 Chapter 2. Multidimensional Data Analysis 13 2.1. Multidimensional tables 14 2.2. Analysis of a point cloud 24 2.2.1. Spatial analysis of individuals 24 2.2.2. Analysis in variable space 30 2.2.3. Link between the two spaces 32 2.3. Principal component factor analysis 35 2.3.1. Principles 35 2.3.2. Principal component factor analysis in practice 41 2.4. Appendix: useful software 48 2.5. Tanagra software 48 2.6. R software 56 Chapter 3. Introduction to Automatic Classification 65 3.1. Similarity and distance 66 3.1.1. Similarity, dissimilarity 66 3.1.2. Distance 67 3.2. Basics of information theory 69 3.3. Classification methods 78 3.4. Classification by partitioning 80 3.4.1. Partitioning principle 80 3.4.2. Inertia 81 3.4.3. Mobile center algorithm 82 3.5. Hierarchical classification 89 3.5.1. Principle 89 3.5.2. Aggregation strategies 90 3.5.3. Ward's aggregation strategy 98 3.6. Appendices 101 3.6.1. Huygens-König theorem 101 3.6.2. Classification software 103 Chapter 4. Linear Programming 109 4.1. An introductory example 110 4.2. General formulation 113 4.3. Geometry of a linear program 116 4.4. Simplex algorithm 118 4.5. Two-phase method. 129 4.6. Duality 135 4.7. Degeneracy 139 4.8. Introduction to integer linear programming 140 4.8.1. Gomory cuts 140 4.8.2. Branch and Bound algorithm 151 Chapter 5. Elements of Graph Theory 159 5.1. Definition and representations of a graph 160 5.1.1. Graphical representation 160 5.1.2. Tables associated with a graph 161 5.2. Main concepts and technology 162 5.2.1. Elements of a graph 163 5.2.2. Analysis of graph structure 168 5.3. Transitive closure of a graph's vertices 172 5.4. Decomposition of a directed graph into strongly connected components 173 5.5. Trees 175 5.5.1. Introduction 175 5.5.2. Trees in a graph 175 5.5.3. Spanning tree in a graph 177 5.6. Finding a fundamental system of independent cycles of a connected graph 179 5.7. Extremum spanning tree 180 5.7.1. General information 180 5.7.2. Extremum spanning tree search algorithms 180 Chapter 6. Path Optimization 187 6.1. Extremal-length paths 188 6.1.1. General information 188 6.1.2. Solving algorithms 189 6.1.3. Searching for ¿ -extremal paths 204 6.2. Hamiltonian path search 205 6.2.1. Decomposition into strongly connected components 205 6.2.2. Branch and Bound algorithm 207 Chapter 7. Transportation Problems 219 7.1. Maximum flow 220 7.1.1. General 220 7.1.2. Ford-Fulkerson theorem 223 7.1.3. Ford-Fulkerson algorithm 224 7.1.4. Practical solution method 230 7.2. Least cost transportation 236 7.2.1. Issues 236 7.2.2. Northwest Corner algorithm 238 7.2.3. Least cost method 240 7.2.4. Balas-Hammer or Vogel's algorithm 243 7.2.5. Stepping stone algorithm 246 7.2.6. Inequality of supply and demand 256 7.2.7. Unconnected graph and degeneration 257 7.2.8. Potentials and dual program 261 7.3. Assignment problems 263 7.3.1. Issues 263 7.3.2. Hungarian algorithm 269 Chapter 8. Scheduling Problems 279 8.1. Planning a project 280 8.1.1. Introduction 280 8.1.2. Earliest and latest date method 283 8.1.3. Gantt chart 289 8.2. Flow-shop problem 291 8.2.1. Johnson's algorithm for two machines 293 8.2.2. Case of three machines 297 8.3. The job-shop problem 306 References 311 List of Authors 313 Index 315
Es gelten unsere Allgemeinen Geschäftsbedingungen: www.buecher.de/agb
Impressum
www.buecher.de ist ein Internetauftritt der buecher.de internetstores GmbH
Geschäftsführung: Monica Sawhney | Roland Kölbl | Günter Hilger
Sitz der Gesellschaft: Batheyer Straße 115 - 117, 58099 Hagen
Postanschrift: Bürgermeister-Wegele-Str. 12, 86167 Augsburg
Amtsgericht Hagen HRB 13257
Steuernummer: 321/5800/1497
USt-IdNr: DE450055826
