Eötvös Loránd Tudományegyetem

Természettudományi Kar

Matematika Alapszak

Kötelező tantárgy

Tantárgyi Adatlap

és tantárgyi követelmények

2006.

Tantárgycím: VÉGES MATEMATIKA 1. középszint

2.

Tantárgy kódja

Szemeszter

Követelmény

Kredit

Nyelv

Modul/szakirány

 

 

I.

kollokvium + gyakorlati jegy

2+3

magyar

 

 

3. A tantárgyfelelős személy és tanszék:

Elekes György, egyetemi tanár, Számítógéptudományi Tanszék

 

4. A tantárgy előadója:

Név:

Beosztás:

Tanszék, Int.:

Recski András

egy. tanár

Számítógéptudományi

 

 

 

 

5. A tantárgy az alábbi témakörök ismeretére épít:

középiskolai matematika anyag

 

6. Kötelező/ajánlott előtanulmányi rend:

A Bevezető Matematika kritériumtárgy követelményeinek teljesítése, illetve ha nem sikerül, akkor a tantárggyal párhuzamos hallgatása.

Kollokvium csak a gyakorlat sikeres teljesítése esetén tehető.

A Véges matematika 1. tárgyat párhuzamosan három szinten hirdetjük meg (alap- közép- és emelt szint), ezek közül egyet kell választani. A három szint egymás között szabadon átjárható.

 

 

7. A tantárgy célkitűzése:

a ma már középiskolában, sőt általános iskolában is egyre többször előforduló kombinatorikus gondolkodásmód kialakítása sok feladat-megoldással.

 

8.  A tantárgy részletes tematikája:

 

Stratégiás játékok.

 

Leszámlálási alapfeladatok: permutációk, variációk, kombinációk ismétlés nélkül és ismétléssel.  Logikai szitaformula és változatai, mint a  ``Dobjuk ki a rosszat''

elv általánosítása. Rekurziós okoskodások, Fibonacci-számok, ezekre vezető

kombinatorikai feladatok. A differencia-sorozatok módszere. A skatulyaelv és alkalmazásai kombinatorikai és geometriai  feladatokban. Átlagolás, kettős leszámlálás.

 

Binomiális együtthatók, azonosságok binomiális  együtthatókra. Kitalálós játékok: a Barkochba és  változatai, hamis pénz kitalálása. Módszerek lehetetlenség  igazolására: színezések, számozások.

 

Gráfok fogalma, hurokél, többszörös él, egyszerű  gráfok. Pontok fokszáma és élek száma közti  összefüggés, és alkalmazásai. Fokszámsorozatok  realizációja. Részgráfok, feszített részgráfok.  Séták, vonalak, utak, körök és kapcsolatuk. Összefüggő és nem összefüggő gráfok: komponensek.  Fák és erdők, élszámuk meghatározása. A leghosszabb utak módszere. Euler-vonal ill. körvonal létezésének szükséges és elégséges feltétele. Irányított gráfok,

turnamentek. Az Euler-tétel megfelelője irányított gráfokra (biz. nélkül). Hamilton-körök és Hamilton-utak, szükséges feltétel létezésükre. Elégséges feltétel(ek) Hamilton-körök és Hamilton-utak létezésére (biz. nélk.) összefüggőségi és útkereső algoritmusok: szélességi bejárás, labirintus-bejárás. Súlyozott élű gráfok: Kruskal és Dijkstra algoritmusai. Síkgráfok, Euler-formula (biz. nélk.), Kuratowski tétele (biz. nélk.). Síkgráfok élszáma. Gráfszínezések, kromatikus szám: kapcsolat a maximális fokszámmal és a legnagyobb teljes részgráf méretével. Síkgráfok színezése: a hatszíntétel. Élszínezések, Vizing tétele (biz. nélk.).

 

A Ramsey tétel néhány speciális esete, két és több szín esetére (csak gyakorlaton). Extremális gráfok: maximális élszám háromszögmentes gráfokra.

 

9. A tantárgy oktatásának módja: 2 óra előadás + 2 óra gyakorlat, kiscsoportos bontásban.

 

10. Követelmények

a.     A szorgalmi időszakban:  2 sikeres zárthelyi

b.     A vizsgaidőszakban:  kollokvium

 

11. Pótlási lehetőségek

        egy sikertelen zárthelyi pótolható

 

12. Konzultációs lehetőségek

Rendszeres konzultációs lehetőség a hallgatók igényei szerint, az előadóval és a gyakorlatvezetővel.

 

 

13. Jegyzet, tankönyv, felhasználható irodalom:

Elekes György: Kombinatorika feladatgyűjtemény, ELTE jegyzet

Hajnal Péter: Elemi kombinatorikai feladatok, JATE Polygon Kiadó

 

14. A tantárgy elvégzéséhez szükséges tanulmányi munka:

Az előadási anyag megértése és a vizsgára felkészülés, továbbá a házi feladatok elkészítése és a zárthelyik megírása.

 

15. A tantárgy tematikáját kidolgozta (Név, beosztás, tanszék/intézet):

Recski András  egyetemi tanár, Számítógéptudományi Tanszék