E-Book Content
A sz´ am´ıt´ astudom´ any alapjai A BME I. ´eves villamosm´ern¨ok, m´ern¨ok-informatikus ´es matematikus-hallgat´oi sz´am´ara ¨ Ossze´ all´ıtotta: Fleiner Tam´as G1 G x0 v0 v x Utols´o friss´ıt´es: 2013. december 23. Tartalomjegyz´ ek Bevezet˝ o 4 Vizsgatematika 7 1. Alapismeretek 1.1. Komplex sz´amok . . . . . . . . . . . . . 1.2. Kombinatorika . . . . . . . . . . . . . . 1.2.1. Elemi lesz´aml´al´asok . . . . . . . . 1.2.2. A szita-formula ´es a skatulya-elv . 1.3. Koordin´atageometria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 10 15 15 20 23 2. Line´ aris algebra 2.1. Vektorterek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Line´aris egyenletrendszerek . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1. Egy koordin´atageometriai alkalmaz´as . . . . . . . . . . . . . . . . 2.3. Permut´aci´ok, determin´ansok . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Permut´aci´ok, inverzi´osz´am . . . . . . . . . . . . . . . . . . . . . . 2.3.2. Determin´ansok . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4. M´atrixok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1. M´atrixm˝ uveletek, t´erbeli vektorok szorz´asa . . . . . . . . . . . . . 2.4.2. M´atrix inverze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.3. M´atrix rangja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.4. Line´aris egyenletrendszerek t´argyal´asa m´atrixokkal . . . . . . . . 2.5. Line´aris lek´epez´esek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1. Line´aris lek´epez´esek m´atrixai . . . . . . . . . . . . . . . . . . . . 2.5.2. Line´aris transzform´aci´ok ´es m´atrixok saj´at´ert´ekei, saj´atvektorai ´es saj´atalterei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 26 33 38 39 39 40 45 45 48 50 52 52 56 3. Gr´ afok 3.1. A gr´afelm´elet alapjai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. F´ak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 62 66 1 58 3.3. 3.4. 3.5. 3.6. 3.7. 3.8. 3.2.1. F´ak alaptulajdons´agai . . . . . . . . . . . . . . . . 3.2.2. Cayley t´etele . . . . . . . . . . . . . . . . . . . . . 3.2.3. Kruskal algoritmusa . . . . . . . . . . . . . . . . . Euler ´es Hamilton bej´ar´asok . . . . . . . . . . . . . . . . . 3.3.1. Gr´afok ´eleinek bej´ar´asa . . . . . . . . . . . . . . . . 3.3.2. Gr´afok cs´ ucsainak bej´ar´asa . . . . . . . . . . . . . . Gr´afbej´ar´asok . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1. Legr¨ovidebb utak . . . . . . . . . . . . . . . . . . . 3.4.2. Legsz´elesebb utak . . . . . . . . . . . . . . . . . . . 3.4.3. M´elys´egi bej´ar´as, aciklikus gr´afok, leghosszabb utak H´al´ozati folyamok ´es alkalmaz´asaik . . . . . . . . . . . . . 3.5.1. Menger t´etelei ´es gr´afok t¨obbsz¨or¨os ¨osszef¨ ugg˝os´ege . 3.5.2. P´aros gr´afok, p´aros´ıt´asok ´es gr´afparam´eterek . . . . S´ıkgr´afok . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.1. S´ıkgr´afok dualit´asa . . . . . . . . . . . . . . . . . . Gr´afok sz´ınez´esei . . . . . . . . . . . . . . . . . . . . . . . 3.7.1. Gr´afok ´elsz´ınez´ese . . . . . . . . . . . . . . . . . . . 3.7.2. S´ıkgr´afok sz´ınez´ese . . . . . . . . . . . . . . . . . . Perfekt gr´afok . . . . . . . . . . . . . . . . . . . . . . . . . 4. Sz´ amelm´ elet 4.1. Oszthat´os´ag, pr´ımek, k¨oz¨os oszt´ok