A számítástudomány alapjai

Szerző

Szerkesztő

Budapest

'Katona Gyula Y.: A számítástudomány alapjai ' összes példány

Kiadó:	Typotex Elektronikus Kiadó Kft.
Kiadás helye:	Budapest
Kiadás éve:	2002
Kötés típusa:	Ragasztott papírkötés
Oldalszám:	190 oldal
Sorozatcím:
Kötetszám:
Nyelv:	Magyar
Méret:	24 cm x 16 cm
ISBN:	963-9326-24-0
Megjegyzés:	Fekete-fehér ábrákat tartalmaz.

Értesítőt kérek a kiadóról

A beállítást mentettük,
naponta értesítjük a beérkező friss
kiadványokról

Fülszöveg

A véges matematika különféle lehetőségek összeszámlálásával, különféle struktúrákkal (például gráfelmélet) és algoritmusokkal foglalkozik. A számítógépek elterjedése óta mind a matematikában, mind annak (műszaki, közgazdaságtani, biológiai stb.) alkalmazásaiban különösen fontos szerepet játszik.
A könyv elsősorban ezeket a témákat foglalja össze az ELTE és a BME matematikus, ill. alkalmazott matematikus hallgatói számára tartott Véges matematika vagy Kombinatorika és gráfelmélet című előadásokhoz. Emellett a számelmélet és az absztrakt algebra legfontosabb elemeibe is bevezetőt nyújt, hogy a BME villamosmérnök hallgatói számára tartott A számítástudomány elemei című tárgy anyagát és a BME műszaki informatikus hallgatói számára tartott Bevezetés a számelméletbe című tárgy anyagának nagy részét is lefedje.
A könyv szerzői évtizedek óta oktatják ezeket a tárgyakat a Budapesti Műszaki és Gazdaságtudományi Egyetemen, valamint az Eötvös Loránd Tudományegyetemen.

Tartalom

Előszó	9
Klasszikus leszámlálási problémák	11
Permutációk, variációk, kombinációk	11
Skatulya-elv	17
Szita módszer	18
Gráfelmélet	21
Alapfogalmak	21
Fák és tulajdonságaik	24
A mohó algoritmus	27
Euler- és Hamilton körök	28
Gráfok és mátrixok	31
Szomszédsági mátrix	31
Illeszkedési mátrix	32
Körmátrix	35
Egyéb gráfreprezentációk	37
Síkbarajzolható gráfok	38
Síkbarajzolható gráfok duálisa	41
Hogyan járjunk be egy gráfot?	47
Szemléletes előkészítés	47
A kétféle bejárás leírása	49
Legrövidebb utat kereső algoritmusok	52
Élsúlyozatlan eset	52
Dijkstra algoritmusa	52
Ford algoritmusa	54
Floyd algoritmusa	55
Párosítások és folyamok	56
Párosítás páros gráfban	56
König és Gallai tételei	59
Párosítás tetszőleges gráfban	61
Hálózati folyamok	64
A folyamprobléma általánosításai	68
Menger tételei	69
Többszörös összefüggőség	71
A mélységi keresés alkalmazásai	72
Alapkörrendszer keresése	72
Irányított körök felismerése, emeletekre bontás	73
A kritikus út módszere (PERT-módszer)	75
További alkalmazások	77
Gráfok színezése	77
Alsó és felső korlátok	77
Perfekt gráfok	82
Síkbarajzolható gráfok kromatikus száma	84
Élkromatikus szám	85
Részgráfokkal kapcsolatos kérdések	86
Ramsey-típusú tételek	86
Turán-típusú tételek	89
Adatok kezelése	91
Keresés	91
Beszúrás	92
Sorba rendezés	92
Hogyan tároljunk gráfokat?	94
Szomszédossági tömbök és listák	94
Láncolt szomszédossági listák	95
További megjegyzések	96
NP-beli problémák	96
A P, NP és NP-teljes problémaosztályok	96
A nem polinomrendű algoritmus is lehet jó	101
Számelmélet	105
Az alapműveletek	105
Kongruenciák, maradékosztályok	107
Műveletek maradékosztályokkal	108
Maradékrendszerek	109
Kongruenciák megoldása	112
Prímszámok, prímtesztelés	115
Nyilvános kulcsú titkosírások	119
Mi a jelszó?	119
Kódolás és dekódolás	119
További trükkök	120
Bizonyítás információközlés nélkül	121
Csoportok, gyűrűk, testek, hálók	125
Alapfogalmak	125
Részcsoportok, mellékosztályok, Lagrange tétele	129
Normálosztó, faktorcsoport, homomorfizmus	132
Permutációcsoportok, Cayley-tétel	135
Direkt sorozat, Abel-csoportok	138
Csoportok megadása, példák	140
További alapfogalmak	142
Az egész számok gyűrűje	145
Kongruenciák	147
Hálók	149
Testek	152
A Galois-elmélet alapjai	158
Rekurziók és generátorfüggvények	163
Homogén lineáris rekurzió	163
Stirling-számok	165
Bell-számok	168
Számelméleti partíciók	170
Catalan-számok	173
Extremális halmazrendszerek	177
Erdős-Ko-Radó tétele	177
Sperner-rendszerek	179
Tárgymutató	183
Ajánlott irodalom	189