StichwortverzeichnisCopyright© 2007 by Doina Logofătu
-
3-Schritte-Modell 232Θ-Notation 12
Ω-Notation 13
114, 165
A
Abbruchbedingung 106
abs 174, 181, 190, 277
absteigende Teilfolge 240
Abstraktion 11
Abu Ja'far Muhammad ibn Musa al-Khwarizmi 1
Abwärtskompatibilität 36
Ackermann, Wilhelm 118
Ackermannfunktion 118
add 42, 54, 60, 91, 131, 134, 140, 147, 165
addFirst 91
addLast 90
adjazent 222
Adjazenzmatrix 8, 68, 222
ähnliche Summe 261
ALG doTransformBase10ToP()
ALG rekonstruiereTeilfolge() 29
ALG write_Triangulation() 288
ALG_Backtracking_Iterativ 176
ALG_Backtracking_Rekursiv 176
ALG_BINÄRE_SUCHE 5
ALG_COST_TRIANGULATIONS 287
ALG_DivideEtImpera 146
ALG_doTransformBase10ToP 121
ALG_EUKLID 2
ALG_EXAKT_DOPI 74
ALG_FFT 163
ALG_FibIt 233
ALG_FibRec 233
ALG_Greedy 39
ALG_GREEDY_COMPACT 212
ALG_HUFFMAN 59
ALG_KRUSKAL 51
ALG_LCS 246
ALG_N_DAMEN 173
ALG_NACHFOLGER_BS 80
ALG_NACHFOLGER_PERM 78
ALG_OPTIM_COMPACT_REC 208
ALG_POTENZSUMMEN 316
ALG_RAN_DOP 73
ALG_RAN_DOPI 73
ALG_REVERSE 79
ALG_REVERSE2 80
ALG_SCHNELLES_POTENZIEREN 108
ALG_SIEB_ERATOSTHENES 4
ALG_SWAP 79
ALG_TIRAMISU 6
ALG_VERSCH_SCHACHTELN 28
ALG_WARSHALL_ARBITRAGE 307
algebraische (kartesische) Form 164
Algorithmen mit unterer Schranke 75
Algorithmik 10
al-jabr 1
Allgemeinheit 10
allocate 242, 272
Analyse der Komplexität 16
Anzahl aller Kombinationen 181
Anzahl aller n-Permutationen 178
Anzahl aller Variationen 179
Anzahl der Gebiete für schneidende Geraden 304
Anzahl der schwarzen Pixel 158
Anzahl der surjektiven Abbildungen 186
Anzahl der Ziffern einer Zahl 107
Anzahl der Züge, Türme von Hanoi 150
Anzahl vollständiger Binärbäume 63
append 35, 110, 160
Arbitrage 305
ArithmeticException 320
arraycopy 80, 87
ArrayDeque 83, 89
ArrayList 41, 52, 54, 60, 91, 146, 154, 165
Arrays 30, 33
asList 33
assert 30, 36
AssertionError 36
Aufrundungsfunktion 238
aufsteigende Teilfolge 27, 240
Ausnahme 34
Ausnahmetyp 34
Aussage 100
Auswertung der Ergebnisse 94
B
Backtracking 169, 235
Bauer, Wolf, Ziege und Kohlkopf 226
Bauern auf dem Schachbrett 228
Baum 49, 105, 157, 233
bedingter Ausdruck ?: 43, 62, 126, 147, 161, 209, 255
Bedingung 25, 172
Bellman, Richard 231
Berliner Schachzeitung 169
Bernoullische Ungleichung 105
Beschreibung 10
Bestimmung des minimalen Pfades 231
Beweis 11, 100, 109, 111, 128, 240
Beweis durch vollständige Induktion 101, 103
Bezzel, Max 169
BigDecimal 114
BigInteger 111, 239
bijektive Funktion 18
Binärbaum 56
binäre Suche 4
Binärwort 56, 65
Binomialkoeffizienten 235, 239, 273, 318
Binomischer Lehrsatz (Newton’sche Binomialformel) 102, 312
Bit-Operatoren
BitSet 84, 201, 218
Blattknoten 56
Boolean 62, 89
Bottom-up-Ansatz 234
bus-invert-Methode 66
C
ℂ(ℤ) 164
carré latin 214
Cäsar, Julius 145
Catalan-Zahl 63, 224, 275, 286, 292
catch 31, 34
Cauchy-Schwarz-Ungleichung (Schwarzsche Ungleichung) 102
Character 217
charAt 60, 160, 209, 302
clear 87, 203, 210, 219
clone 203
close 31, 42, 45, 48, 54, 61, 94, 110
Co-NP 19
Code mit beliebiger Länge 56
Code mit fester Länge 56
Collatz-Funktion 106, 125
Collections 40, 42
compaction_factor 211
Comparable 29, 33, 42, 61
compare 43
compareTo 30, 33, 40, 43, 62
compound recursion 106, 118
Cook, Stephen Arthur,
currentTimeMillis 237
D
Darstellung 7, 32, 121
Data Ordering Problem 65
Datenabstraktion 32, 40, 163, 255, 319
Datenkanal 65
Decke aus Holz und Gold 167
default-Konstruktor 32
Dekodierung 56
delete 303
Deque 82, 89
Determinismus 10
Die Elemente 2
Die Zahl 4 108
digit 217
Dimension 131, 133, 138
direkte Rekursion 106, 130
direkter Beweis 100, 102, 109, 111, 128
Diskrete Fourier-Transformation (DFT) 162
Divide et Impera 145
Division mit Rest 111
Domino 253
Don Quijotes Windmühlen 168
DOP, DOPI 66, 71
Double 52
Double Ended Queue 82
drawLine 139
drawOval 133
drawRect 131, 134
Dreiecksungleichung 67
Drei-Gläser-Methode 78
Dynamische Programmierung 27, 231
E
Edit-Distanz 297
Einheitswurzeln 162
elementare Operation 11
Endlichkeit 10
Endlosschleife 106
enstrySet 55, 60, 92
Entscheidungsproblem 18, 72
Eratosthenes von Kyrene 3
Erfüllbarkeitsproblem 20
Ergebnisse DOP 95
Ergebnisse DOPI 96
Euklid 2
Euklidischer Abstand 288
Euklidischer Algorithmus 2, 320
Euler, Leonhard 164, 214
Exakt-Algorithmen (EX) 74
EXIT_ON_CLOSE 131, 134
Exklusiv-ODER 66
F
Fast Fourier Transformation (FFT)
fat recursion 106, 123
Fibonacci (Leonardo Pisano) 236
Fibonacci-Folge 105, 232
File 30, 35, 41, 44, 53, 60, 110
FileReader 35
fill 31, 259, 277
finally 31, 34, 45, …, 110, …
FloatBuffer 272
flush 238
foreach-Schleife 54, 62, 90, 166, 174, 187, 204, 210, 242, 260, 277
Formatter 123
Foto 158
Fotoproblem 191
Fraktal 135
Fraktal Space-Filling 141
G
gcd 111
Geheimnisprinzip 32
Genauigkeit 208, 317
Generator 135
Generierung aller n-BitStrings 80
Generierung aller n-Permutationen 78, 170
Generierung aller Variationen 179
geometrische Reihe 128
Gesamtanzahl der Transitionen 67
get 42, 52, 60, 91, 147, 165, …, 210, 242
getContentPane 131, 134, 140
getDefaultToolKit 131
getFirst 91
getKey 55
getLast 91
getScreenSize 131
getSize 131, 133, 138, 140
getValue 55, 61
Gewicht eines Graphen 49
Gewicht eines Huffman-Baumes 57
Gewichtsfunktion eines Graphen 49
Glaspyramide im Louvre, Paris 38
Gleichung 102, 123, 225, 281
Graffiti in Benalmadena 310
Graph 9, 18, 48, 75, 233
Graphenfärbungsproblem 20
Graphenisomorphismusproblem 20
Graphics 131, 133, 138
Greedy 39, 235
Greedy-Min-Algorithmen (GM) 74
Greedy-Min-Simplified-Algorithmen (GMS) 74
Gregory, James 114
Grenzwert 14
größter gemeinsamer Teiler 2, 146, 320
H
Hamiltonkreis 19
Hamming-Distanz 66, 298
Handlungsreisendenproblem 18, 39
HashSet 201
hasNext 55, 60, 219
hasNextDouble 152, 166
hasNextFloat 42
hasNextInt 30, 35, 110, 116, 124, 147, 154
hasNextLong 119, 121, 126, 284
hasPrevious 61, 249
Haus des Nikolaus 221
height 131, 133, 138
Hoare, C. A. R. 153
Holzskulptur an einem Stuhl 230
Huffman, Albert 56
Huffman-Baum 56
Huffman-Kodierung 56
I
imaginäre Einheit 1
Imaginärteil 162
indirekte Rekursion 106, 133
Induktionsanfang 100
Induktionsschluss 100
Induktionsvoraussetzung 100
Initiator 135
insert 31, 35, 303
IntBuffer 241
Integer 52, 60, 89, …, 154
Integer.MAX_VALUE 47, 258, 276
Integral 150
Interface 33
intersects 204
intValue 53, 90
Invertierung 66
IOException 41, 44, 47, 53, 60, 93, 111
isDigit 217
isEmpty 55, 60, 204
Isomorphismus 18
isProbablePrime 111
Iterator 54, 60, 91
iterator 55, 60, 91
J
JFrame 131, 134, 139
JPanel 131, 133, 138
K
Kapelle in Dorohoi 24
Kapselung 32
Kartenfärbungsproblem 7, 43, 224
kartesische (algebraische) Form 164
kartesisches Produkt 225
k-Bonacci-Folge 238
key 53, 93
Kirche auf Norderney 63
Klammerung von n Klammern-Paaren 224
Klassifizierung der Probleme 18
kleinstes gemeinsames Vielfaches 321
Kloster Suceviţa 322
Koch, Helge von 135
Koch’sche Schneeflockenkurve 135
Kodierung 56
Kombinationen 181
Kommandozeilen-Parameter 93
Kompaktierungsmenge 206
kompatible Tests 206
kompatible Zeichen 206
komplexe Zahlen 162
Komplexität 10, 12, 41, 59, 74, 153, 155, 208, 234, 317
konjunktive Normalform (KNF) 21
konstante Kategorie 12
Konstruktoren 29, 32
konvexe Hülle 15
Koordinate 127, 136
Korrektheit 10
Kreis, in Graph 19
Kruskal, Joseph Bernard 51
Kruskal-Algorithmus 48, 83
L
Labyrinth 228
längste absteigende Teilfolge 240
längste aufsteigende Teilfolge 27, 240
längste gemeinsame Teilfolge 245
Laufzeit 14
Leibnitz, Gottfried Wilhelm 114
length 85, 160, 209, 277
Levenshtein, Vladimir 298
Levenshtein-Distanz 298
lexikographisch 27, 78, 179, 221, 288
Liber Abaci 236
lineare Rekursion 106, 115
List 41, 52, 60, 91, 147, 154
ListIterator 54, 61, 91, 249
listIterator 55, 61, 92, 249
Locale 41, 53, 124
logischer Ausdruck 21, 82
Long 120
Long.MAX_VALUE 295
lower bound 76
Lucas, Edouard 148
Lucas-Zahlen 238
Ludwig XI., König 145
M
Machin, John 115
magische Quadrate 169, 177
Manna-Pnuelli-Funktion 120
Map Colouring Problem 7
Map.Entry 54, 60, 91
Math.abs 174, 181, 190, 277
Math.cos 165
Math.max 54, 93
Math.min 53, 93, 131, 133
Math.PI 165
Math.pow 289
Math.random 85
Math.round 238
Math.sin 165
Math.sqrt 138, 289
max 54, 93
maximal aufsteigende Teilfolge 26
Mehrfachvererbung 33
Memoization 232
Mengenüberdeckungsproblem 20
MergeSort 146, 155
Metrik 67, 297
Metrik-Bedingungen 298
min 53, 131, 133
minimale Triangulierung 286
minimaler Spannbaum 49, 76
Mittelpunkt eines Segments 136
Modell der flachen Erde 12
modPow 111
Multigraph 75
multimap-Konzept 52, 83
Multiplikation einer Matrizenfolge 291
Multiplikationsreihe 293
Nachfolger-Algorithmus 78
natürliche Ordnung 33, 41
Nauck, Franz, Dr. 169
n-Damen-Problem 169
n-dimensionale Schachtel 25
next 55, 60, 219
nextBoolean 85
nextClearBit 87
nextDouble 52, 124, 152, 166
nextFloat 42, 308
nextInt 30, 35, 44, 47, 60, 110, 116, 122, 139, 147, 154, 174, 186, 190, 192
nextLong 108, 113, 119, 122, 126, 284
nicht monotone (offene) Rekursion 106, 125
NP-hard 21
NP-vollständig 19, 71
n-Türme-Problem 178
NullPointerException 33
O
obere Schranke 13
offene (nicht monotone) Rekursion 106, 125
O-Notation 13
Optimalität 15, 231
Optimalitätsprinzip 231
Optimierungsproblem 18
Orangensport 196
Österreichkarte 8
overloading 32
overriding 32
P
pack 131, 134, 140
paint 131, 133, 138
parseInt 93
Partitionen einer natürlichen Zahl 182
passende Wörter 244
passt-Bedingung 25
Peano, Giuseppe 99
Peanosche Axiome 99
Permutationen 25, 67, 77
Pi () 114, 165
Pisano, Leonardo (Fibonacci) 236
Pivot-Element 153
point-region 157
Polygon 286
Polymorphismus 32
Polynom 163, 282, 310
position 242
Potenzieren, rekursives 107
Potenzieren, schnelles 108
Potenzsummen 311
pow 289
Präfixcode 56
pre-order Darstellung 158
previous 249
Primfaktorzerlegung 321
Primzahl 3, 101
print 31, 36, 41, 42, 45, 62
printf 48, 54, 94, 116
println 31, 36, 42, 48, 54, 110, 113
printStackTrace 31, 34
PrintStream 45, 47, 60, 93, 110, 113
PrintWriter 30, 35
Problem der Türme auf den ersten m Reihen 179
Problem der aufsteigenden Türme auf den ersten m Reihen 180
Produktmatrix 292
put 52, 54, 60, 91, 242, 272
Q
Quad-Bäume 157
Quadranacci-Folge 238
Quadrant 127, 158
Quersumme einer Zahl 106
QuickSort 146, 152
R
RAM (Random Access Machine) 11
Random 84
random 85
raumfüllende Fraktale 141
Realteil 162
Rechtecksregel 152
recurrere 105
Reduktion 15
Reelle Zeit 17
Rekursion 99
Rekursionsformel 268, 313
Rekursionsgleichung 268, 313
rekursive Datenstrukturen 105
rekursive Zahlenumwandlung 120
rekursives Potenzieren 107
remove 55, 61, 177, 210
replace 302
Rest großer Potenzen 111
Rezept 6
round 238
Rucksackproblem 20, 40
Rumänienkarte 22
S
SAT 20
Satz (Erdős, Szekeres) 240
Satz von Vieta (Vieta Relationen) 123, 282
Scanner 30, 35, 41, 44, 47, 53, 60, 108
Scheduling-Problem 10, 20
Schluss von n auf n+1 99
schnelles Potenzieren 108
Schnittpunkt einer Menge von n Strecken 15
Schotten auf dem Oktoberfest 266
Schwäne auf der Isar 143
Schwarzsche Ungleichung (Cauchy-Schwarz-Ungleichung) 102
Set 201
set 87, 203
setDefaultCloseOperation 131, 134
setLocation 134, 140
setPrefferedSize 131, 134, 140
setVisible 131, 134, 140
Sieb des Eratosthenes 3
Sierpinski-Dreieck 140
size 60, 90, 147, 255
Skulptur auf einem Brunnen in Bern 334
sort 30, 33, 40, 42
Sortieren 27
space-filling curves 141
Spannbaum 49
Spiegelung einer Zahl 106
Springer auf dem Schachbrett 45, 188, 275
sqrt 138, 289
statische lokale Klasse 33, 255, 289
Statue in Bremen 98
Strandkörbe auf Norderney 309
String 41, 44, 46, 53, 60, 110
StringBuffer 35
StringBuilder 31, 35, 110, 160, 301
substring 302
Sudoku 214
Summe zweier Wurzeln 123
Summen von Produkten 280
Summenformel 16, 100, 104, 177
surjektive Funktion 185
swap 78
symbolische Kodierung 7, 8
Symmetrie 67, 129
System.in 174, 183, 186, 190, 269
T
Teilbarkeit 101, 105, 199
Teilbarkeit durch eine Prinzahl 101
Teilbaum 159
Teilblock 214
Teile und Herrsche 145
Teiler 101, 105, 199
Teilfolge 245
Teilproblem 145, 231
Testmusterkompaktierung 205
Throwable 31, 34
Tiramisu 6
Toolkit 131, 134
Top-Down-Ansatz 234
toString 40, 43, 121, 166, 255
Transformation 7
Transition 66
Trapezregel 150
Travelling Salesman Problem (TSP) 18
TreeMap 52, 60, 91
Triangulierung eines konvexen Polygons 286
Tribonacci-Folge 238
try 30, 34, …, 110
Turm der Wallfahrtkapelle St. Bartholomä 64
Türme von Hanoi 105, 148
U
überladene Methoden 32
überlagerte Methoden 32
Überlappung der Probleme 232
ungünstigster Fall 14
untere Schranke 13
Untergraph 48
unzusammenhängend, Graph 49
useLocale 41, 53, 124, 152
V
value 53, 93
Vereinfachen 320
Verpackungsproblem 20
verschachtelte Rekursion 106, 118
verschachtelte Schachteln 25
Verschmelzungsoperation 57
versteckte Basen 229
Verteilung der Geschenke 258
verzweigte Rekursion 106, 123
Vielfache 321
Vielfache, das kleinste V. 321
Vieta Relationen (Satz von Vieta) 123, 282
vollständige Induktion 99
vollständiger Binärbaum 56
vollständiger Graph 75
W
Wachstum von O(g(n)) 17
Wahrscheinlichkeit 268
Wald 49
Walking Man an der Leopoldstraße 144
Warnsdorff-Regel 46
Widerspruch 26, 240
width 131, 133, 138
WindowConstants 131, 134
worst-case complexity 14
Wrapper-Klasse 120
Wurf einer Münze 266
Wurzelsatz von Vieta 123, 282
Z
Zahlen-Dreieck 249
Zahlensystem 120
Zahlenumwandlung, rekursiv 120
Zeichen 56
Zeichenmenge 57
Zeiteinheit 11
Zerlegung 198
Zufällige-Lösung-Algorithmen 73
zusammenhängend, Graph 49
Zutaten 6
Zuweisung 68