StichwortverzeichnisCopyright© 2006 by Doina Logofătu
-
3-Schritte-Modell 404
A
Abstand eines Punktes zu einer Geraden 223
absteigende Teilfolge 411
abundante Zahl 120
Ackermannfunktion 306
Active Template Library (ATL) 317
adjazent 251
Adjazenzliste 256
Adjazenzmatrix 254
ähnliche Summe 425
ALG doTransformBase10ToP() 308
ALG recoverBoxesSubstring() 19
ALG write_Triangulation() 447
ALG_Backtracking_Iterativ 364
ALG_Backtracking_Recursiv 364
ALG_BFS 257, 265
ALG_CATALAN_1 200
ALG_CATALAN_2 201
ALG_CATALAN_3(n) 203
ALG_CHIN_RESTSATZ 85
ALG_COST_TRIANGULATIONS 447
ALG_DFS 257, 265
ALG_DivideEtImpera 338
ALG_EUKLID 84
ALG_FFT 354
ALG_FLOYD_WARSHALL 255, 268
ALG_Greedy 283
ALG_GREEDY_COMPACT 375
ALG_HILL_CONVEX_HULL 232
ALG_KOMPLEXE_KODIERUNG 6
ALG_KRUSKAL 262
ALG_N_DAMEN 361
ALG_NACHFOLGER_CVEKTOR 168
ALG_NAIVE_CLOSEST_PAIR 228
ALG_OPTIM_COMPACT_REC 391
ALG_POTENZSUMMEN 212
ALG_TEST_PRIM 82
ALG_UNRANK_PERMUTATION 178
ALG_VER_CLOSEST_PAIR 229
ALG_VERSCH_SCHACHTELN 18
Anzahl der Gebiete für schneidende Geraden 304
Anzahl der surjektiven Abbildungen 164, 373
Anzahl der Teiler 119
Anzahl der Ziffern von 102
Anzahl der Ziffern von n! 105
Anzahl vollständiger Binärbäume 191
ASCII-Wert 25, 40, 116, 310
Aufrundungsfunktion 69, 156
aufsteigende Teilfolge 17, 411
Außenprodukt 225
B
Backtracking 357
Bären aus Oxford 138
Bauer, Wolf, Ziege und Kohlkopf 401, 402
Baum 260, 348
Bäume – Herbst in Ottawa 282
Bayerischer Fan der Fußball-WM 2006 in München 218
bedingter Ausdruck ?: 187, 421
befreundete Zahlen 120
Bellman, Richard (1920-1984) 403
Berechnung eines Dreiecks 140, 142, 146
bergige Landschaften 200
Bernoullische Ungleichung 297
Berühmtheitsproblem 263
Bezzel, Max (1824-1871) 357
bijektive Funktion 65
binäres Prädikat 22, 46, 243, 284
Binomialkoeffizienten 162, 180, 215, 407, 411
Binomischer Lehrsatz (Newton’sche Binomialformel) 163, 166, 198, 208, 294
bipartiter Graph 254
Bit-Array 96
Bit-Operatoren 96, 116, 121, 310
Blick vom Turm des Ulmer Münsters 206
Breitensuche (BFS) 256, 264, 439
Brennpunkte, Ellipse 224
Bridge-Blatt 44
C
ℂ(ℤ) 3
C++-Strings 27
Cantor, Georg (1845-1918) 59
Cantor-Diagonalisierung 59, 67
Cäsar, Julius (100 v. Chr.-44 v. Chr.) 337
Catalan, Eugène Charles (1814-1894) 190
Catalan-Zahlen 189, 417, 425, 431
Cauchy-Diagonalisierung 72
Cauchy-Schwarz-Ungleichung (Schwarzsche Ungleichung) 294
charakteristischer Vektor einer Teilmenge 166
Chinesischer Restsatz 85, 136
Collatz-Funktion 311
compaction_factor 374
const-Member-Funktionen 12
cmath 6, 9, 102, 143, 148, 151, …
C-Programm 97, 266, 285, 350
Cramersche Regel 148
CRC-Wert 115
C-Strings 26, 52
ctype.h, cctype.h, Methoden 26, 52, 56, 273
CWindow (ATL) 317
Cyclic Redundancy Check (CRC-Verfahren) 115
D
Das Problem der Zufälligkeit 164
Das Problem der Türme auf den ersten m Reihen 367
Das Problem der aufsteigenden Türme auf den ersten m Reihen 368
Datenabstraktion 10, 22, 243, 317, 354
Datumsverpackung 121
defiziente Zahl 120
Destruktoren 10, 243, 355
Die Zahl 4 300
Differenz, symmetrische D. 62
diophantische Gleichung 88
direkte Rekursion 298, 316
direkter Beweis 128, 292, 294, 301
Dirichlet, Peter Gustav Lejeune (1805-1859) 155
Diskrete Fourier-Transformation (DFT) 352
Division mit Rest 83, 302
Domino 418
DOS-Programm 316, 325
Dreiecksgeometrie 139, 331
Druck einer Broschüre 99
Dynamische Programmierung 17, 214, 403
E
Edit-Distanz 456
Einheitswurzeln 352
Element der Menge 59
Ellipse 224, 233
Ellipsengleichung 225
Englische Erstausgabe von Euklids “Elemente” 250
Eratosthenes von Kyrene (ca. 275-194 v. Chr.) 95
erzeugende Funktion 197
Euklid (ca. 300 v. Chr.) 83
Euklidischer Algorithmus 83, 111, 214, 339
Euklids Beweis 82
Euklidischer Abstand 220, 234, 244, 427
Euler, Leonhard (1707-1783) 1, 190
Euler-Fermat Satz 87
Eulersche Gerade 149
Eulersche Phi-Funktion 88, 155
Eulertour (Eulerkreis) 259, 276, 280
F
Fast Fourier Transformation (FFT) 353
Fermat, Pierre de (1601-1665) 86
Fermatscher Zwei-Quadrate-Satz 86
Fibonacci (Leonardo Pisano, ca. 1180) 388
Fibonacci-Folge 157, 297, 384
Fläche eines Dreiecks 223
Fläche eines Polygons 225
Flächeninhalt 141
Fotoproblem 378
Fraktal 329
Fraktal Space-Filling 335
friend-Funktionen 10, 22, 355
Fundamentalsatz der Arithmetik 83
Funktionen, partielle F. 64
G
Genauigkeit 213, 391
Geometrische Reihe 110, 152, 314
Gerade in der Ebene 221
Gespiegelte Häuser in Lübeck 290
Gewichtsfunktion eines Graphen 261
Goldbach, Christian (1690-1764) 94
Goldbachsche Vermutung 94
Grad, Graph 252
Graham Scan 230
Graph 251
Gray-Code 170
Greedy 283
Großer Fermatscher Satz 87, 125
größter gemeinsamer Teiler 83, 111, 214, 338
Grüße über den runden Tisch 191
Gummibärchen 136
H
Hamburger Rathaus (gebaut 1886-1897) 217
Hamilton, Sir William Rowan (1805-1865) 259
Hamiltonkreis 259, 276
Hamming-Distanz 456
Haus des Nikolaus 280
Heronsche Formel (Satz des Heron) 141, 224
Hilbert-Waring-Theorem 87
Hill-Algorithmus 230, 231
Hoare, C.A.R. (geb. 1934) 344
Höhenformeln 141
Hilbert, David (1862-1943) 87
I
imaginäre Einheit 1
Imaginärteil 2
indirekte Rekursion 298, 325
injektive Funktion 65
Inkreisradius, Dreieck 141
inline-Funktionen 12, 355
Integral 342
Inverse von a modulo m 137
inzident 251
K
Kapselung 10
Kartenfärbung 286, 377
kartesisches Produkt 378
Kätzchen in Hüten 108
k-Bonacci-Folge 390
Klammerung von n Klammern-Paare 191, 377
Kleiner Fermatscher Satz (1640) 86
kleinstes gemeinsames Vielfaches 83
Koch, Helge von (1870-1924) 329
Koch’sche Schneeflockenkurve 329
Kodierungsproblem komplexer Zahlen 2
Kombinationen 161, 368
Kompaktierungsmenge 388
kompatible Tests 389
kompatible Zeichen 388
Komplement 62
Komplementärer Graph 263
komplexe Zahlen 1, 2, 353
Komplexität 213, 232, 284, 391
Komponente eines Graphen 258
Kongruenzen 84
König-Artus-Problem 263
Konstruktoren 10, 243, 355
konvexe Hülle 230, 243
Kosinussatz 140, 143
Kreis, in Graph 252
Kreis 147, 236
Kreisumfang 146, 150
Kubische Gleichung 125
L
längste absteigende Teilfolge 411, 414
längste aufsteigende Teilfolge 17, 411
längste gemeinsame Teilfolge 414
leere Menge 60
Levenshtein, Vladimir (geb. 1935) 456
Levenshtein-Distanz 456
lexikographisch 17, 21, 22, 35, 173, 280
Liber Abaci 63, 408
lineare Rekursion 298, 304
Logarithmus 102, 105, 113
Lucas-Zahlen 409
Ludwig XI., König (1461-1483) 337
M
magische Quadrate 358, 365
Manna-Pnuelli-Funktion 307
maximal aufsteigende Teilfolge 17
Maximiliansbrücke, München 80
Memoization 404
Mengenoperationen 61
Mengen 59, 435
MergeSort 346
Metrik 456
minimale Triangulierung 445
Minimaler Spannbaum 261
Multimengen 63
Multinomialkoeffizienten 159, 185
Multiplikation einer Matrizenfolge 451
Multiplikationsreihe 192
N
Nächstes Paar 228, 233
Nationaltheater „Vasile Alexandri”, Iaşi, Rumänien (gebaut 1894-1896) 58
n-Damen-Problem 357
n-Türme-Problem 365
O
offene (nicht monotone) Rekursion 298, 311
Operator-Überladung 10, 22, 243, 355
Optimalitätsprinzip 403
Ordnungen 64
P
Palindrom 40
Partitionen einer natürlichen Zahl 349
passende Wörter 394
passt-Bedingung 15, 19, 20
Peano, Giuseppe (1858-1932) 291
Peanosche Axiome 291
Pell’sche Gleichung 88, 114
Permutationen 15, 158, 173, 366
Pfad 252
Pfadmatrix 255, 267
Pi () 141, 143, 147, 354
Pick, Georg Alexander (1859-1942) 248
Pivot-Element 344
Polarkoordinaten 149
Polymorphie 12
Polynom 353, 443
Potenzieren, naives iteratives 183
Potenzieren, rekursives 299
Potenzieren, schnelles 111, 302
Potenzmenge (engl. power set) 62, 166
Potenzsummen 207
pre-order Darstellung 349
Primfaktorzerlegung 83, 101, 119, 155, 181
Primzahl 37, 82, 293
Primzahltest 93, 95
Prinzip von Inklusion und Exklusion 153
Produktmatrix 451
Projektionssatz 141, 143
Punkt im Inneren eines Polygons 225, 243
Q
qsort 215, 285
Quad-Bäume 348
Quadranacci-Folge 410
Quadranten 219, 237, 314
Quadrat einer speziellen Zahl 126
Quersumme einer Zahl 298, 445
QuickSort 344
R
Ranking einer Permutation 175
Rapunzel 40
Realteil 2
Rekursion 291, 297, …
Relationen 63
Rest großer Potenzen 302
Rucksackproblem 284
S
Satz (Erdős, Szekeres) 391
Satz von Legendre 181
Satz von Pick 248
Scheitel, Ellipse 224
Schiffe in Lübeck 249
Schlinge, Graph 251
schnelles Potenzieren 111, 302
Schnittmenge 61
Schreibweisen, Menge 60
Schubfachprinzip (Taubenschlagprinzip) 155, 186
Sieb des Eratosthenes 95, 164
Sierpinski-Dreieck 334
Sinussatz 140, 143
Sphinx in den Karpaten, Bucegi Gebirge 152
Spiegelung einer Zahl 298
Spiegelungsprinzip 199
Springer auf dem Schachbrett 287, 375, 437
St. Nikolai Kirche, Burg auf Fehrman 188
std, const_iterator 73, 76
std, iterator 13, 235
std, reverse_iterator 13
std::algorithm 19, 146, 174, 234, 243
std::auto_ptr - “smart pointer” 322
std::bitset 168
std::fstream 9, …
std::ifstream 9, 21, 34, …
std::iomanip 148
std::iter_swap 175
std::lexicographical_compare 20
std::map 180, 182, 203
std::multimap 75, 76
std::multiset 73
std::next_permutation 174
std::ofstream 9, 21, 34, …
std::pair 182, 235, 400, 419, 428
std::prev_permutation 174
std::reverse 175
std::set 73
std::sort 20, 22, 46, 234, 244,
std::string 28-, 34, 36, 42, 46, 56, 129, 372, 439, …
std::swap 175
std::vector 13, 19, …, 171, …, 351, …
std::vector<bool> 98, 171
Steigungswinkel 221
Steuerzeichen, oft benötigte 25
STL-Anwendung 9
Suan-Ching Handbuch 85
Summen von Produkten 422
Summenformel 68, 292
Sun-Tzu (ca. 300 n. Chr.) 85
surjektive Funktion 65, 164, 373
symmetrischen Zeichen 42
T
Teilbarkeit 81, 101, 118, 120, 155, 157, 293
Teilbarkeitsfunktion 81
Teilersummenfunktion 120
Teile und Herrsche 337
Teilfolge 17, 411
Teilgraph 258
Teilmenge 60, 166, 422, 425
Teilprobleme 337, 403
Testmusterkompaktierung 388
Tiefensuche (DFS) 257, 264
topologische Sortierung 270
Trapezregel 342
Traversieren von Graphen 256
Triangulierung eines konvexen Polygons 190, 445
Tribonacci-Folge 410
trigonometrische Formeln 141, 296
Turm von Pisa 472
Türme von Hanoi 340
U
Umfang, Dreieck 141, 429
Umkreisradius, Dreieck 141, 146
Umwandlung einer Dezimalzahl in eine römische Zahl 130
Umwandlung einer römischen Zahl in eine Dezimalzahl 128
Unranking einer Permutation 175
Untergraph 261
V
Variationen 160, 367
Vereinfachen 182, 204, 214
Vereinigungsmenge 61
verschachtelte Rekursion 298, 306
verschachtelte Schachteln 15
verzweigte Rekursion 298, 310
Vielfache 5, 81, 155, 157, 186
Vielfache, das kleinste V. 186
Vielfaches einer komplexen Zahl 5
Vier-Quadrate-Satz von Lagrange 87
Vieta Relationen (Satz von Vieta) 89, 310, 442
Vieta, François (1540-1603) 89
Vogelsprache 55
vollkommene (perfekte) Zahl 120
vollständige Induktion 127, 291
vollständiger Graph 254
W
Wahrscheinlichkeit 430
Wald 260
Waring, Edward (1736-1798) 87
Warnsdorff-Regel 288
Weg 252
Widerspruch 4, 16
wiederholende Zeichenketten 33
Wurzelsatz von Vieta 90
Z
Zahlen-Dreieck 415
Zahlensystem 3, 308, 399
Zahlenumwandlung, rekursiv 308
Zeichen 25
Zeiger auf Funktionen 56
Zerlegung 384
Zusammenhang 258
Zyklus 252