Bevezetés a matematikába

Ez a tankönyv az ELTE programtervező informatikus hallgatói számára készült, a matematika ,,diszkrét” – azaz a folytonossághoz nem kapcsolódó – témaköreinek ismereteit tartalmazza. A halmazelmélet, relációk, függvények, természetes számok és egyéb számkörök tárgyalásánál rámutatunk az alkalmazásokra is: szó esik a lekérdező nyelvekről, a relációs adtabázis-kezelőkről, logikai függvényekről és elektronikai megvalósításukról, továbbá a számábrázolásokról. A véges halmazok, a kombinatorika és a végtelen halmazok ismertetését az elemi számelmélet tárgyalása követi, amely tartalmazza az RSA kódolást, a digitális aláírást és kulcs-csere módszerét is. A gráfelmélettel kapcsolatban néhány fontos adatstruktúra és számos gráfalgoritmus is szóba kerül. Az algebra megalapozza a kódoláselmélet és a komputeralgebra megértését, ezért röviden a véges testek elméletét is áttekintjük. A kódolás című fejezet rengeteg gyakorlati ismeretet is tartalmaz az adattömörítéssel és a hibajavító kódokkal kapcsolatosan. Az utolsó fejezet már átvezet az elméleti informatikába: részletesen tárgyaljuk a gépmodellek ekvivalenciáját, bemutatjuk a kiszámíthatóság és felsorolhatóság fogalmait, az algoritmussal megoldhatatlan problémák létezését. A kötet a tárigény és a futásidő vizsgálatával, a P és NP problémaosztályok megfogalmazásával zárul. Minden témakörhöz számos különböző szintű feladat tartozik.