Mathematics for Informatics and Computer Science (eBook)

Pierre Audibert (Autor)

eBook Download: PDF | EPUB

2013 | 1. Auflage
914 Seiten
Wiley (Verlag)
978-1-118-58648-8 (ISBN)

Infos

How many ways do exist to mix different ingredients, how many chances to win a gambling game, how many possible paths going from one place to another in a network ? To this kind of questions Mathematics applied to computer gives a stimulating and exhaustive answer. This text, presented in three parts (Combinatorics, Probability, Graphs) addresses all those who wish to acquire basic or advanced knowledge in combinatorial theories. It is actually also used as a textbook. Basic and advanced theoretical elements are presented through simple applications like the Sudoku game, search engine algorithm and other easy to grasp applications. Through the progression from simple to complex, the teacher acquires knowledge of the state of the art of combinatorial theory. The non conventional simultaneous presentation of algorithms, programs and theory permits a powerful mixture of theory and practice. All in all, the originality of this approach gives a refreshing view on combinatorial theory.

Autor

Pierre Audibert is the author of Mathematics for Informatics and Computer Science, published by Wiley.

Inhalt

General Introduction xxiii

Chapter 1. Some Historical Elements 1

PART 1. COMBINATORICS 17

Part 1. Introduction 19

Chapter 2. Arrangements and Combinations 21

Chapter 3. Enumerations in Alphabetical Order 43

Chapter 4. Enumeration by Tree Structures 63

Chapter 5. Languages, Generating Functions and Recurrences
85

Chapter 6. Routes in a Square Grid 105

Chapter 7. Arrangements and Combinations with Repetitions
119

Chapter 8. Sieve Formula 137

Chapter 9. Mountain Ranges or Parenthesis Words: Catalan Numbers
165

Chapter 10. Other Mountain Ranges 197

Chapter 11. Some Applications of Catalan Numbers and Parenthesis
Words 215

Chapter 12. Burnside's Formula 227

Chapter 13. Matrices and Circulation on a Graph 253

Chapter 14. Parts and Partitions of a Set 275

Chapter 15. Partitions of a Number 289

Chapter 16. Flags 305

Chapter 17. Walls and Stacks 315

Chapter 18. Tiling of Rectangular Surfaces using Simple Shapes
331

Chapter 19. Permutations 345

PART 2. PROBABILITY 387

Part 2. Introduction 389

Chapter 20. Reminders about Discrete Probabilities 395

Chapter 21. Chance and the Computer 427

Chapter 22. Discrete and Continuous 447

Chapter 23. Generating Function Associated with a Discrete
Random Variable in a Game 469

Chapter 24. Graphs and Matrices for Dealing with Probability
Problems 497

Chapter 25. Repeated Games of Heads or Tails 509

Chapter 26. Random Routes on a Graph 535

Chapter 27. Repetitive Draws until the Outcome of a Certain
Pattern 565

Chapter 28. Probability Exercises 597

PART 3. GRAPHS 637

Part 3. Introduction 639

Chapter 29. Graphs and Routes 643

Chapter 30. Explorations in Graphs 661

Chapter 31. Trees with Numbered Nodes, Cayley's Theorem
and Prüfer Code 705

Chapter 32. Binary Trees 723

Chapter 33. Weighted Graphs: Shortest Paths and Minimum Spanning
Tree 737

Chapter 34. Eulerian Paths and Cycles, Spanning Trees of a Graph
759

Chapter 35. Enumeration of Spanning Trees of an Undirected Graph
779

Chapter 36. Enumeration of Eulerian Paths in Undirected Graphs
799

Chapter 37. Hamiltonian Paths and Circuits 835

APPENDICES 867

Appendix 1. Matrices 869

Appendix 2. Determinants and Route Combinatorics 885

Bibliography 907

Index 911

Rezensionen

"On the other hand if you are looking for an approach to combinatorics that is routed in applications and with lots of exercises then this is the book for you. Yes, dare I say it, it's fun." (I Programmer, 21 January 2011)

Produkt-Details

• Erscheint lt. Verlag: 1.3.2013
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Schlagworte: Computer Science • Electrical & Electronics Engineering • Elektrotechnik u. Elektronik • Informatik • Informationstechnologie • Information Technologies • Mathematik • Quantencomputer • Quantum Computing
• ISBN-10: 1-118-58648-4 / 1118586484
• ISBN-13: 978-1-118-58648-8 / 9781118586488