Algorithmen und Problemlösungen mit C++ von der diskreten Mathematik zum fertigen Programm ; Lern- und Arbeitsbuch für Informatiker und Mathematiker ; [mit Online-Service

Cover......Page 1 Algorithmen und Problemlösungen mit C++: Von der Diskreten Mathematik zum fertigen Programm – Lern- und Arbeitsbuch für Informatiker und Mathematiker, 2 Auflage......Page 4 Copyright - ISBN: 383480763X......Page 5 Geleitwort......Page 8 Vorwort......Page 10 Danksagung......Page 12 Inhaltsverzeichnis......Page 14 Komplexe Zahlen – Kurze Einführung......Page 20 Kodierungsproblem komplexer Zahlen......Page 21 Problemanalyse und Entwurf der Lösung......Page 22 Programm Komplexe_Kodierung......Page 25 Programmanalyse......Page 28 Aufgaben......Page 32 Anmerkungen......Page 33 Problembeschreibung......Page 34 Problemanalyse und Entwurf der Lösung......Page 35 Der Algorithmus......Page 36 Das Programm......Page 38 Die Programmanalyse......Page 41 3. break-Anweisung in einer Mehrfachauswahl mit switch......Page 42 Anmerkungen......Page 43 1. Zeichen......Page 44 2. C-Strings......Page 45 3. C++-Strings......Page 46 Aufgaben......Page 51 Problemanalyse und Entwurf der Lösung......Page 52 Aufgabe......Page 53 Problem 2. Das Perlencollier......Page 54 Aufgabe......Page 55 Problem 3. Parkinson......Page 56 Programm......Page 57 Problem 4. Rapunzel im Internet......Page 59 Problemanalyse und Entwurf der Lösung......Page 60 Programm......Page 61 Problem 5. Bridge-Blatt......Page 63 Problemanalyse und Entwurf der Lösung......Page 64 Programm......Page 65 Aufgaben......Page 67 Problem 6. Wo sind die Königinnen?......Page 68 Problemanalyse und Entwurf der Lösung......Page 69 Programm......Page 71 Aufgaben......Page 73 Problem 7. Vogelsprache......Page 74 Programm......Page 75 Aufgabe......Page 77 1. Element und Menge......Page 78 3. Schreibweisen......Page 79 4. Mengenoperationen......Page 80 6. Relationen......Page 82 8. Funktionen......Page 83 Aufgaben......Page 84 Problemanalyse und Entwurf der Lösung......Page 86 Programm......Page 88 Aufgaben......Page 89 Problemanalyse und Entwurf der Lösung:......Page 91 Aufgaben......Page 92 Problem 3. Relation und ihre Eigenschaften......Page 93 Problemanalyse und Entwurf der Lösung......Page 94 Programm......Page 95 Aufgaben......Page 97 2. Primzahlen......Page 98 3. Fundamentalsatz der Arithmetik ......Page 99 4. Division mit Rest, ggT und kgV.......Page 100 5. Kongruenzen. Elementare Eigenschaften......Page 101 6. Chinesischer Restsatz......Page 102 7. Fermatsche Sätze......Page 103 8. Die Pell’sche Gleichung......Page 105 9. Satz von Vieta......Page 106 Aufgaben......Page 108 Aufgaben......Page 110 Problem 2. Sieb des Eratosthenes......Page 112 Problemanalyse und Entwurf der Lösung......Page 113 Programm in C......Page 114 Aufgaben......Page 115 Problem 3. Druck einer Broschüre......Page 116 Programm......Page 117 Problemanalyse und Entwurf der Lösung......Page 118 Aufgaben......Page 120 Problem 5. Der alte Gärtner......Page 121 Problemanalyse und Entwurf der Lösung......Page 122 Programm......Page 123 Aufgaben......Page 124 Problem 6. Kätzchen in Hüten......Page 125 Problemanalyse und Entwurf der Lösung......Page 126 Programm......Page 128 Aufgaben......Page 130 Problemanalyse und Entwurf der Lösung......Page 131 Aufgabe......Page 132 Problem 8. Korrekte Nachrichten......Page 133 Problemanalyse und Entwurf der Lösung......Page 134 Aufgaben......Page 135 Programm......Page 136 Aufgaben......Page 137 Problemanalyse und Entwurf der Lösung......Page 138 Programm......Page 139 Problem 11. Die schöne Marie und der schöne Hans......Page 140 Programm......Page 141 Problem 12. Kubische Gleichung......Page 142 Aufgabe......Page 143 Problemanalyse und Entwurf der Lösung......Page 144 Problem 14. Umwandlung einer römischen Zahl in eine Dezimalzahl......Page 145 Programm......Page 146 Aufgabe......Page 147 Programm......Page 148 Problem 16. Hässliche Zahlen......Page 149 Programm......Page 150 Problem 17. Vögel auf den Bäumen......Page 151 Programm......Page 152 Problem 18. Wieviele sind es mindestens? (Chinesischer Restsatz)......Page 153 Programm......Page 154 Aufgaben......Page 155 1. Dreiecksgeometrie......Page 156 2. Berechnung eines beliebigen Dreiecks......Page 157 Problemanalyse und Entwurf der Lösung......Page 159 Programm......Page 160 Aufgaben......Page 162 Problem 2. Der Kreisumfang......Page 163 Problemanalyse und Entwurf der Lösung......Page 164 Programm......Page 165 Aufgaben......Page 166 Problemanalyse und Entwurf der Lösung......Page 167 Programm......Page 168 Aufgaben......Page 169 1. Prinzip von Inklusion und Exklusion.......Page 170 2. Das Schubfachprinzip......Page 172 3. Permutationen (Anordnungen mit Berücksichtigung der Reihenfolge)......Page 175 4. Variationen (Auswahlen mit Beachtung der Reihenfolge)......Page 177 5. Kombinationen (Auswahlen ohne Beachtung der Reihenfolge)......Page 178 6. Binomialkoeffizienten und ihre Anwendungen......Page 179 Aufgaben......Page 181 Problem 1. Alle Teilmengen einer Menge in lexikographischer Reihenfolge......Page 183 Problemanalyse und Entwurf der Lösung......Page 184 Programm......Page 185 Aufgaben......Page 186 Problem 2. Der Gray-Code (minimale Änderungsreihenfolge)......Page 187 Programm......Page 188 Aufgaben......Page 189 Problemanalyse und Entwurf der Lösung......Page 190 Programm......Page 191 Problem 4. Ranking einer Permutation in lexikographischer Reihenfolge......Page 192 Problemanalyse und Entwurf der Lösung......Page 193 Aufgaben......Page 194 Problemanalyse und Entwurf der Lösung......Page 195 Programm......Page 196 Problemanalyse und Entwurf der Lösung......Page 197 Programm......Page 199 Aufgaben......Page 201 Problemanalyse und Entwurf der Lösung......Page 203 Aufgaben......Page 204 Einführung......Page 206 Sechs Probleme aus der Catalan-Familie......Page 207 Theorem. P1-P6 und die Catalan-Zahlen......Page 210 Die rekursive Formel......Page 213 Die erzeugende Funktion......Page 214 Noch 4 äquivalente Probleme......Page 216 Programm Catalan1......Page 217 Zweiter Algorithmus, eine weitere Rekursion......Page 218 Dritter Algorithmus, der ohne Rekursion auskommt......Page 219 Programm Catalan3......Page 220 Aufgaben......Page 222 Problemanalyse. Algebraische Modellierung.......Page 224 Von der Rekursionsgleichung zum Algorithmus......Page 226 Der Algorithmus......Page 229 Programm......Page 231 Aufgaben......Page 234 1. Darstellung der Punkte, Quadranten......Page 236 2. Abstand zwischen zwei Punkten......Page 237 3. Gerade in der Ebene......Page 238 4. Abstand eines Punktes zu einer Geraden, Fläche eines Dreiecks......Page 240 5. Die Ellipse......Page 241 7. Die Fläche eines Polygons, Punkt im Inneren eines Polygons......Page 242 8. Nächstes Paar......Page 245 9. Die konvexe Hülle......Page 247 Aufgaben......Page 249 Problem 1. Nächstes Paar......Page 250 Programm......Page 251 Problemanalyse und Entwurf der Lösung......Page 253 Programm......Page 254 Aufgaben......Page 255 Problem 3. Wie sicher sind die Bürger?......Page 257 Problemanalyse und Entwurf der Lösung......Page 259 Programm......Page 260 Aufgaben......Page 263 1. Einführende Begriffe......Page 268 2. Weg, Pfad, Zyklus und Kreis......Page 269 3. Vollständige und bipartite Graphen......Page 270 4. Darstellung der Graphen......Page 271 5. Traversieren von Graphen (BFS und DFS)......Page 273 6. Zusammenhang......Page 275 7. Hamiltonsche und eulersche Graphen......Page 276 8. Bäume und Wälder......Page 277 9. Minimaler Spannbaum......Page 278 Aufgaben......Page 280 Problemanalyse und Entwurf der Lösung......Page 281 Programm in C......Page 283 Programm DFS in C++......Page 284 Programm BFS in C++......Page 286 Problemanalyse und Entwurf der Lösung......Page 287 Programm......Page 288 Problem 3. Das Alphabet der fremden Sprache......Page 289 Problemanalyse und Entwurf der Lösung......Page 290 Programm in C......Page 293 Aufgaben......Page 294 Problem 4. Markus besucht seine Freunde......Page 295 Problemanalyse und Entwurf der Lösung......Page 296 Programm......Page 297 Aufgaben......Page 299 Programm......Page 300 Aufgaben......Page 301 Problemanalyse und Entwurf der Lösung......Page 302 Programm......Page 303 Augaben......Page 304 Grundlagen......Page 306 Problemanalyse und Entwurf der Lösung......Page 307 Programm in C......Page 308 Programm 1 in C++......Page 309 Programm 2 in C++......Page 311 Problem 2. Kartenfärbung......Page 312 Programm......Page 313 Problemanalyse und Entwurf der Lösung......Page 314 Programm......Page 315 Aufgabe......Page 316 Problem 4. Huffman-Kodierung......Page 317 Problemanalyse und Entwurf der Lösung......Page 318 Programm......Page 321 Aufgaben......Page 322 Vollständige Induktion......Page 324 Aufgaben......Page 329 Rekursion: Grundlagen......Page 330 Problem 1. Quersumme und Spiegelung einer natürlichen Zahl......Page 331 Aufgaben......Page 332 Problemanalyse und Entwurf der Lösung......Page 333 Programm......Page 334 Problemanalyse und Entwurf der Lösung......Page 335 Aufgaben......Page 336 Problemanalyse und Entwurf der Lösung......Page 337 Programm 4.2.......Page 338 Problem 5. Die Ackermannfunktion (Verschachtelte Rekursion, "compound recursion")......Page 339 Aufgabe......Page 340 Programm......Page 341 Aufgaben......Page 342 Programm......Page 343 Problem 8. Collatz-Funktion (nicht-monotone Rekursion)......Page 344 Programm......Page 345 Problem 9. Quadrate und Quadrätchen......Page 346 Problemanalyse und Entwurf der Lösung......Page 347 Programm......Page 348 Programm 1 (Borland C++-Variante)......Page 349 Der vorkompilierte Header stdafx.h......Page 352 Main WindowImpl.cpp - Implementierung der Klasse CMainWindow, diedie Quadrate zeichnet:......Page 353 main.cpp:......Page 355 Aufgaben......Page 357 Programm (Borland C++)......Page 358 MainWindowImpl.cpp......Page 360 Problem 12. Die Koch’sche Schneeflockenkurve......Page 362 MainWindowImpl.cpp......Page 365 Aufgaben......Page 367 Grundlagen......Page 370 Problemanalyse und Entwurf der Lösung......Page 371 Aufgaben......Page 372 Problemanalyse und Entwurf der Lösung......Page 373 Aufgaben......Page 374 Programm......Page 375 Problem 4. QuickSort......Page 376 Programm......Page 377 Aufgaben......Page 378 Programm......Page 379 Problem 6. Quad-Bäume......Page 380 Problemanalyse und Entwurf der Lösung......Page 382 Programm in C......Page 383 Aufgabe......Page 384 Problemanalyse und Entwurf der Lösung......Page 385 Programm......Page 387 Aufgaben......Page 388 Problem 1. Das Problem der n Damen......Page 390 Problemanalyse und Entwurf der Lösung......Page 391 Programm BP......Page 395 Allgemeine Bemerkungen zum Backtracking-Verfahren......Page 396 Aufgaben......Page 397 Problemanalyse und Entwurf der Lösung......Page 399 Aufgaben......Page 400 Problemanalyse und Entwurf der Lösung......Page 401 Problemanalyse und Entwurf der Lösung......Page 402 Problemanalyse und Entwurf der Lösung......Page 403 Programm......Page 404 Aufgaben......Page 405 Problemanalyse und Entwurf der Lösung......Page 406 Programm......Page 407 Problem 8. Alle Wege des Springers......Page 408 Programm......Page 409 Aufgaben......Page 410 Programm......Page 411 Problem 10. Der ausbrechende Ball......Page 412 Programm......Page 413 Problem 11. Olivensport......Page 415 Problemanalyse und Entwurf der Lösung......Page 417 Programm......Page 419 Problem 12. Testmusterkompaktierung......Page 421 Problemanalyse und Entwurf der Lösung......Page 423 Programm......Page 425 Aufgaben......Page 427 Problem 13. Sudoku......Page 430 Problemanalyse und Entwurf der Lösung......Page 432 Programm......Page 434 Aufgaben......Page 435 Noch 10 Probleme......Page 436 2. Optimalitätsprinzip......Page 444 4. Einführendes Beispiel – die Fibonacci-Folge......Page 445 6. Vergleich mit anderen Verfahren......Page 447 Aufgaben......Page 448 Problemanalyse und Entwurf der Lösung......Page 449 Aufgaben......Page 450 Problem 2. Längste aufsteigende Teilfolge......Page 452 Programm......Page 453 Aufgaben......Page 455 Problem 3. Zahlen-Dreieck......Page 456 Problemanalyse und Entwurf der Lösung......Page 457 Programm......Page 458 Problem 4. Domino......Page 459 Problemanalyse und Entwurf der Lösung......Page 460 Programm......Page 461 Problemanalyse und Entwurf der Lösung......Page 463 Programm......Page 464 Aufgabe......Page 465 Problem 6. Ähnliche Summe......Page 466 Problemanalyse und Entwurf der Lösung......Page 467 Programm......Page 468 Aufgaben......Page 469 Problem 7. Schotten auf dem Oktoberfest......Page 471 Problemanalyse und Entwurf der Lösung......Page 472 Programm 1 ......Page 473 Programm 2......Page 474 Programm 3......Page 475 Andere Lösungmöglichkeit......Page 476 Aufgaben......Page 477 Problemanalyse und Entwurf der Lösung......Page 478 Programm......Page 480 Aufgaben......Page 482 Problemanalyse und Entwurf der Lösung......Page 483 Programm......Page 485 Problem 10. Minimale Triangulierung eines konvexen Vielecks......Page 486 Problemanalyse und Entwurf der Lösung......Page 487 Programm......Page 489 Aufgaben......Page 491 Problem 11. Multiplikation einer Matrizenfolge......Page 492 Problemanalyse und Entwurf der Lösung......Page 493 Programm......Page 494 Aufgabe......Page 496 Problem 12. Edit-Distanz......Page 497 Problemanalyse und Entwurf der Lösung......Page 498 Programm......Page 500 Aufgaben......Page 502 Problem 13. Arbitrage......Page 503 Problemanalyse und Entwurf der Lösung......Page 504 Programm......Page 505 Problem 14. Längste gemeinsame Teilfolge (LCS)......Page 507 Problemanalyse und Entwurf der Lösung......Page 508 Programm......Page 510 Aufgaben......Page 511 Literaturverzeichnis......Page 512 A......Page 516 E......Page 517 K......Page 518 P......Page 519 T......Page 520 Z......Page 521