A számítástudomány matematikai alapjai

TARTALOM Előszó 9 Halmazok. Relációk és függvények. Kombinatorikai alapfogalmak. Gráfok Halmazok 13 n-esek 15 Relációk 17 Függvények 19 Variációk, permutációk, kombinációk 20 Logikai szitaformula 22 Generátorfüggvények 24 Gráfok. Alapfogalmak 26 Gráfok csúcsmátrixa. A legrövidebb út problémája 30 Gráfok összefüggősége. Kondenzáció 32 Független részhalmazok és teljes részgráfok. Fedések 35 Fák 37 Véges értékű függvények Alapfogalmak 40 Kifejezések és szuperpozíciók 44 Teljes függvényhalmazok 49 Zárt oszályok 54 Dualitás. Önduális függvények 56 Monotonitás 60 Lineáris függvények 63 Teljességi kritérium 65 Teljességi kritérium tetszőleges k esetén 72 A k-értékű függvények sajátosságai k > vagy = 3 esetén 74 Végtelen értékű függvények 78 Boole-függvények realizációi Boole-függvények előállításának minimalizációja. Diszjuktív normálformák 81 Diszjuktív normálformákat minimalizáló algoritmusok 85 Kapuhálózatok 91 A kaszkádmódszer 99 Automaták és formális nyelvek Ábécék, szavak, formális nyelvek, valamint a velük való műveletek 108 A generatív grammatikák fogalma és típusai. A Chomsky-féle hierarchia 116 A reguláris nyelvek tulajdonságai 126 Véges automaták mint felismerők. A determinisztikus véges automaták fogalma, megadásuk módjai. Bar-Hillel-lemma 131 A nemdeterminisztikus véges automaták. Ekvivalenciájuk a determinisztikus véges automatákkal, valamint a reguláris grammatikákkal 141 Reguláris kifejezések. Kleene tétele 150 Véges automaták minimalizációja 158 Véges automaták mint formális nyelvek átalakítói. A Mealy-és a Moore-automaták, a két típus ekvivalenciája. Alaptulajdonságok 170 Környezetfüggetlen nyelvek. A programozási nyelvek szintaktikája 182 Veremautomaták. Végállapottal, ill. üres veremmel történő felismerés, ezek ekvivalenciája. Szintaktikus elemzés és szintaktikus elemzők. A veremautomaták és a környezetfüggetlen nyelvek ekvivalenciája 201 Turing-gépek A Turing-gépek mint felismerők és átalakítók 217 Az univerzális Turing-gép 237 Algoritmikusan megoldhatatlan problémák 244 Turing-gépek bonyolultságának mértékei 249 Kódelmélet Információs csatorna. Betű szerinti kódolás 256 Felbonthatósági feltételek 259 Optimális kódok 261 Az optimális kód Huffmann-féle konstrukciója 266 Hibajavító kódolás 269 Lineáris kódok. Hamming-kódok 273 Standard dekódolási eljárások. A Hamming-korlát 277 Reed-Muller-kódok 282 Titkosírás 286 Relációs adatmodell Adatbázis-kezelő rendszerek kialakulása 289 Adatmodellezés 292 Adatmodellek 294 Kulcs, funkcionális függés, normálformák 300 Példa a relációk normalizálására 309 A relációs modell adatmanipulációs nyelve, relációs algebra 314 Rekorkalkuls, attributumkalkulus, az adatmanipulációs nyelvek ekvivalenciája 325 A funkcionális függőségek alaptulajdonságai 334 A relációs adatmodell extremális problémái 344 Attributumhalmazon levő adatbázisok struktúrája 355 Irodalom 365 Tárgymutató 366