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

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

Szőnyi Tamás

egyetemi tanár

Számítógéptudományi Tanszék

 

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.  Alapötletek leszámlálási feladatok megoldására: egymás utáni döntések, ``Dobjuk ki a rosszat'' elv alkalmazásai. A többszöri megszámlálás korrekciója

 (``tehén-szabály''). 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 skatulyaelv és alkalmazásai kombinatorikai és geometriai feladatokban. Átlagolá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. Egy speciális eset:páros gráfok, a fokszám-összefüggés páros gráfokra. 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 (a ``komponenstétel''). Fák és erdők, élszámuk meghatározása. A ``königsbergi hidak problémája'': 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: részletesen csak a szélességi  bejárás. 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.

 

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

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