Diszkrét matematika és algoritmuselmélet alapjai

Tartalom

Bevezetés
0.1 Általános jelölések
I. Kombinatorika 1
1. Halmazok 3
1.1 Halmazok definíciója 3
1.2 Boole - algebrák 6
1.3 Minőségi függetlenség és véges Boole-algebrák 12
1.4 Feladatok 19
1.5 Hivatkozások 19
2. Elemi leszámlálások 21
2.1 Általános módszerek 21
2.2 Teljes indukció 24
2.3 Permutációk, variációk, kombinációk 27
2.3.1 Permutációk 28
2.3.2 Variációk, kombinációk 31
2.4 A Stirling formula 40
2.5 Feladatok 41
2.6 Megoldások 44
2.7 Hivatkozások 44
3. Binomiális és polinomiális együtthatók 47
3.1 Binomiális és polinomiális tételek 47
3.2 A binomiális együtthatók tulajdonságai 51
3.3 Összegezési módszerek 56
3.3.1 Binomiális együtthatók összegei 57
3.3.2 Hatványok összege 59
3.4 Rugalmas pénzérmék 62
3.5 Feladatok 63
3.6 Megoldások 67
3.7 Hivatkozások 68
4. A logikai szitaformula 69
4.1 A formula 69
4.2 Elcserélt levelek 71
4.3 Additív halmazfüggvények 76
4.4 Feladatok 81
4.5 Megoldások 82
4.6 Hivatkozások 86
5. Rekurzív sorozatok 87
5.1 Az iterációs módszer 91
5.2 Lineáris rekurziók 93
5.2.1 Algebrai összefüggések 94
5.2.2 Állandó együtthatójú egyenletek 97
5.3 A Fibonacci-sorozat 102
5.4 Szimultán (többdimenziós) rekurziók 103
5.5 Néhány nevezetes rekurzió 107
5.5.1 Ackermann - függvény 107
5.5.2 Lucas-Lehmer teszt 108
5.5.3 Newton gyökvonási algoritmusa 108
5.6 Magasabbrendü számtani sorozatok 109
5.7 Feladatok 112
5.8 Megoldások 116
5.9 Függelék: Mersenne számok 118
5.10 Hivatkozások 119
6. Generátorfüggvények 121
6.1 Lineáris rekurziók 123
6.2 Nemlineáris rekurziók 133
6.2.1 Catalan számok 134
6.2.2 A pénzváltási probléma 137
6.3 Más típusú generátorfüggvények 141
6.4 Feladatok 143
6.5 Megoldások 143
6.6 Hivatkozások 145
7. Extremális halmazrendszerek 147
7.1 Sperner tétele 147
7.2 Erdős-DeBruijn, Ryser és Fischer tételei 150
7.3 Erdős-Ko-Rado tétele 155
7.4 Egyéb eredmények 155
7.5 Szimplexek 158
7.6 Feladatok 164
7.7 Megoldások 164
7.8 Hivatkozások 165
8. Partíciós problémák 167
8.1 Számok felbontása 167
8.2 Halmazpartíciók 170
8.3 Összefoglalás 174
8.4 Hivatkozások 176
II. Gráfelmélet 177
1. Gráfelméleti alapfogalmak 179
1.1 Bevezetés 179
1.2 Nevezetes gráfok 186
1.3 Elemi definíciók és összefüggések 189
1.4 Utak, összefüggőség 192
1.5 Összefoglaló vizsgakérdések 198
1.6 Feladatok 200
1.7 Hivatkozások 201
2 Euler körök és utak 203
2.1 A königsbergi hidak 203
2.2 Euler tételei 206
2.3 Feladatok 209
2.4 Hivatkozás 210
3. Hamilton körök és utak 211
3.1 Hamilton körök 212
3.2 Kockagráfok és Gray-kódok 218
3.3 Feladatok 221
3.4 Megoldás 222
3.5 Hivatkozások 223
4. Gráfok mátrixai 225
4.1 Csúcsmátrixok 226
4.2 Élmátrixok 236
4.3 Egyéb mátrixok és ábrázolási módok 239
4.4 Feladatok 240
4.5 Hivatkozások 240
5. Útkereső algoritmusok 241
5.1 Dijkstra algoritmusa 242
5.2 Hivatkozás 246
6. Fák 247
6.1 Alapvető összefüggések 247
6.2 Fák összeszámlálása 252
6.2.1 Számozott csúcs fák 252
6.2.2 Bináris fák 253
6.2.3 Paraffin molekulák 254
6.3 Fák alkalmazásai 256
6.3.1 Rendezésekről általában 256
6.3.2 Rendezés bináris fán 257
6.4 Feladatok 260
6.5 Hivatkozások 260
7. Feszítőfák 261
7.1 Kruskal algoritmusa 262
7.2 Utazó ügynök metrikus gráfokban 268
7.3 Hivatkozás 270
8. Gráfok izomorfiája 271
8.1 Izomorfizmusok 271
8.2 Invariáns tulajdonságok 275
8.3 Fák izomorfiája 276
8.4 Feladat 282
8.5 Megoldás 282
8.6 Hivatkozás 283
9. Síkgráfok 285
9.1 Definíciók és Kuratowsky tétele 285
9.1.1 Egyéb felületek 292
9.2 Euler poliédertétele 296
9.3 Fullerének 301
9.4 Térképek 303
9.5 Feladatok 303
9.6 Megoldások 303
9.7 Hivatkozások 304
10. Gráfok színezései 305
10.1 Csúcsszínezések 306
10.1.1 Alapfogalmak 306
10.1.2 Síkgráfok 308
10.1.3 Egyéb kérdések 314
10.2 Élszínezések 317
10.2.1 Ramsey-elmélet 317
10.2.2 Ramsey - számok 322
10.2.3 Egyéb kérdések 328
10.3 Feladatok 330
10.4 Megoldások 331
10.5 Hivatkozások 331
11. Kétpólusú gráfok 333
11.1 Páros gráfok 333
11.2 Párosítások 335
11.3 Következmények 340
11.4 Egy statikai alkalmazás 341
11.5 Hivatkozás 342
12. Extremális gráfok 343
12.1 Túrán Pál Tétele 343
12.2 Egyéb eredmények 347
12.3 Hivatkozás 349
13. Gráfok spektruma 351
13.1 Alapfogalmak 351
13.2 További eredmények 356
13.3 Feladat és megoldása 357
13.4 Hivatkozás 357
14. Hálózati folyamok 359
14.1 Alkalmazások 371
14.2 Hivatkozások 372
15. Matroidok 373
15.1 Alapvető definíciók és tulajdonságok 373
15.2 Alkalmazások 378
15.3 Feladatok 380
15.4 Hivatkozások 380
III. Algoritmuselmélet alapjai 383
0 Bevezetés 385
1 Az algoritmus definíciói 389
1.1 Turing - gépek 389
1.2 A rekurzióelmélet alapjai 391
1.2.1 Rekurzív függvények 392
1.2.2 Rekurzív és rekurzíve felsorolható halmazok 395
1.3 Formális nyelvek 398
1.4 Egyéb definíciók 401
2 Bonyolultság 403
3 NP - teljesség 409
3.1 Bevezetés 409
3.2 Nemdeterminisztikus TM -k 412
3.3 Boole-függvények kielégíthetősége 415
4 Hivatkozások 421
IV. Függelék 423
Algoritmusok gyorsasága 425
Az (xn) polinomok 427
Az xn polinomok koordinátái 429
A Pk(n) polinomok 431
Parciális törtekre bontás 433
Általános irodalom 437
Név- és tárgymutató 439-473

Témakörök