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. emelt szint

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.:

Elekes György

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, játékok a sakktáblán.

 

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.

 

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.  Séták, vonalak, utak, körök és kapcsolatuk. Végtelen gráfok, Kőnig-lemma végtelen utakról. Összefüggő  és nem összefüggő gráfok: komponensek.

Fák és erdők, élszámuk meghatározása.  Euler-vonal ill. körvonal létezésének  szükséges és elégséges feltétele. Irányított gráfok, turnamentek, pszeudogyőztesek. Az Euler-tétel megfelelője  irányított gráfokra. 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. Hamilton-út

létezése turnamentekben. Körmérkőzések, a teljes gráf  1-faktorokra bontásai.

 

Ö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, Kuratowski tétele. Gráfszínezések, kromatikus szám.

Háromszög nélküli nagy-kromatikus gráf. Kapcsolat végtelen gráf és véges részgráfjai kromatikus  száma között. Síkgráfok színezése: hat-, öt- és  négyszín  tétel. 

 

A Ramsey tétel gráfokra (két- és több színre.) Erdős alsó becslése. Ramsey tétele halmaz-rendszerekre.  A ``Happy end'' probléma. Extremális gráfok: Maximális és

maximálishoz közeli távolságok száma a síkban. Erdős-Stone-Simonovits (biz.  nélkül).

Becslés tiltott négyszög esetén. Véges geometriák. A Reimann-konstrukció. Felső becslés

az egységtávolságok számára a síkban.

 

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:

Brunczel András, Elekes György:  Véges matematika, ELTE jegyzet

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):

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