Godina izdanja: 2004
ISBN: 978-0-13-127767-7
Jezik: Engleski
Oblast: Matematika
Autor: Strani

TEHNIČKI PODACI O KNJIZI
• Naslov: Discrete Mathematics
• Autor: Richard Johnsonbaugh
• Izdanje: International Edition
• Izdavač: Pearson Education
• Godina izdanja: oko 2004–2005
• ISBN-10: 0131277677
• ISBN-13: 9780131277670
• Jezik: engleski
• Povez: meki (paperback)
• Oblast: diskretna matematika, računarstvo
________________________________________
OPIS KNJIGE
Discrete Mathematics Richarda Johnsonbaugha predstavlja jedan od standardnih univerzitetskih udžbenika namenjenih studentima matematike, informatike i tehničkih nauka. Knjiga je osmišljena tako da razvija matematičko mišljenje, logičko zaključivanje i sposobnost rešavanja problema, što su ključne veštine u savremenom računarstvu.
Autor sistematično obrađuje osnovne oblasti diskretne matematike: logiku i metode dokazivanja, skupove i funkcije, relacije, algoritme, teoriju brojeva, kombinatoriku, teoriju grafova, stabla, kao i uvod u automatske sisteme i formalne jezike. Poseban akcenat stavljen je na razumevanje dokaza i postupno usvajanje složenijih koncepata.
Knjiga se odlikuje jasnim, preglednim stilom i bogatim izborom primera. Svako poglavlje sadrži veliki broj zadataka za vežbu, kao i posebne segmente posvećene strategijama rešavanja problema, što omogućava studentima da aktivno usvajaju gradivo.
Zahvaljujući dobroj strukturi i ravnoteži između teorije i primene, ovaj udžbenik je pogodan i za nastavu i za samostalno učenje. Posebno je značajan za razumevanje matematičkih osnova algoritama, programiranja i računarstva uopšte.
________________________________________


CONTENTS
Preface XI
1 Logic and Proofs 1
1.1 Propositions 2
1.2 Conditional Propositions and Logical Equivalence 8
1.3 Quantifiers 17
1.4 Nested Quantifiers 29
1.5 Proofs 36
1.6 Resolution Proofs 50
1.7 Mathematical Induction 53
Problem-Solving Corner: Mathematical Induction 63
1.8 Strong Form of Induction and the Well-Ordering Property 65
Notes 70
Chapter Review 71
Chapter Self-Test 73
Computer Exercises 75
2 The Language of Mathematics 76
2.1 Sets 76
2.2 Functions 87
Problem-Solving Corner: Functions 102
2.3 Sequences and Strings 103
Notes 112
Chapter Review 112
Chapter Self-Test 114
Computer Exercises 115
3 Relations 116
3.1 Relations 116
3.2 Equivalence Relations 125
Problem-Solving Corner: Equivalence Relations 131
3.3 Matrices of Relations 132
3.4 Relational Databases 137
Notes 142
Chapter Review 142
Chapter Self-Test 142
Computer Exercises 144
4 Algorithms 145
4.1 Introduction 145
4.2 Examples of Algorithms 149
4.3 Analysis of Algorithms 156
Problem-Solving Corner: Design and Analysis of an Algorithm 171
4.4 Recursive Algorithms 173
Notes 180
Chapter Review 180
Chapter Self-Test 181
Computer Exercises 182
5 Introduction to Number Theory 183
5.1 Divisors 183
5.2 Representations of Integers and Integer Algorithms 192
5.3 The Euclidean Algorithm 205
Problem-Solving Corner: Making Postage 214
5.4 The RSA Public-Key Cryptosystem 215
Notes 217
Chapter Review 217
Chapter Self-Test 218
Computer Exercises 219
6 Counting Methods and the Pigeonhole Principle 220
6.1 Basic Principles 220
Problem-Solving Corner: Counting 228
6.2 Permutations and Combinations 229
Problem-Solving Corner: Combinations 240
6.3 Algorithms for Generating Permutations and Combinations 241
6.4 Introduction to Discrete Probability 247
6.5 Discrete Probability Theory 250
6.6 Generalized Permutations and Combinations 261
6.7 Binomial Coefficients and Combinatorial Identities 266
6.8 The Pigeonhole Principle 271
Notes 275
Chapter Review 275
Chapter Self-Test 276
Computer Exercises 278
7 Recurrence Relations 279
7.1 Introduction 279
7.2 Solving Recurrence Relations 290
Problem-Solving Corner: Recurrence Relations 302
7.3 Applications to the Analysis of Algorithms 305
Notes 315
Chapter Review 315
Chapter Self-Test 316
Computer Exercises 317
8 Graph Theory 318
8.1 Introduction 318
8.2 Paths and Cycles 329
Problem-Solving Corner: Graphs 339
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem 340
8.4 A Shortest-Path Algorithm 347
8.5 Representations of Graphs 352
8.6 Isomorphisms of Graphs 356
8.7 Planar Graphs 363
8.8 Instant Insanity 369
Notes 373
Chapter Review 373
Chapter Self-Test 375
Computer Exercises 377
9 Trees 379
9.1 Introduction 379
9.2 Terminology and Characterizations of Trees 386
Problem-Solving Corner: Trees 391
9.3 Spanning Trees 392
9.4 Minimal Spanning Trees 398
9.5 Binary Trees 403
9.6 Tree Traversals 409
9.7 Decision Trees and the Minimum Time for Sorting 414
9.8 Isomorphisms of Trees 420
9.9 Game Trees 429
Notes 437
Chapter Review 437
Chapter Self-Test 439
Computer Exercises 442
10 Network Models 444
10.1 Introduction 444
10.2 A Maximal Flow Algorithm 449
10.3 The Max Flow, Min Cut Theorem 457
10.4 Matching 461
Problem-Solving Corner: Matching 466
Notes 467
Chapter Review 467
Chapter Self-Test 468
Computer Exercises 469
11 Boolean Algebras and Combinatorial Circuits 470
11.1 Combinatorial Circuits 470
11.2 Properties of Combinatorial Circuits 477
11.3 Boolean Algebras 482
Problem-Solving Corner: Boolean Algebras 486
11.4 Boolean Functions and Synthesis of Circuits 488
11.5 Applications 493
Notes 501
Chapter Review 501
Chapter Self-Test 502
Computer Exercises 504
12 Automata, Grammars, and Languages 506
12.1 Sequential Circuits and Finite-State Machines 506
12.2 Finite-State Automata 511
12.3 Languages and Grammars 517
12.4 Nondeterministic Finite-State Automata 525
12.5 Relationships Between Languages and Automata 531
Notes 537
Chapter Review 538
Chapter Self-Test 539
Computer Exercises 540
13 Computational Geometry 542
13.1 The Closest-Pair Problem 542
13.2 An Algorithm to Compute the Convex Hull 547
Notes 554
Chapter Review 554
Chapter Self-Test 554
Computer Exercises 555
Appendix A: Matrices 556
Appendix B: Algebra Review 560
Appendix C: Pseudocode 571
References 577
Hints and Solutions to Selected Exercises 582
Index 662

TAGS: diskretna matematika, udžbenik, Richard Johnsonbaugh, logika, algoritmi, kombinatorika, teorija grafova, računarske nauke, matematičko razmišljanje, univerzitetska literatura
TAGS (EN): discrete mathematics, textbook, Richard Johnsonbaugh, logic, algorithms, combinatorics, graph theory, computer science, mathematical reasoning, university textbook

MG P38 (N)