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

2.

Tantárgy kódja

Szemeszter

Követelmény

Kredit

Nyelv

Modul/szakirány

 

 

II.

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, Véges matematika 1. tantárgy

 

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

Véges matematika 1. előzetes elvégzése kötelező.

A Véges matematika 2 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:

 

Első félévi anyag fontos részeinek ismétlése:  szitaformula és változatai, különféle rekurziók.

 

Minimax tételek: intervallum-rendszerekre vonatkozó feladatok. Páros gráfok és párosítások,

Kőnig-Hall tétel és változatai. Kapcsolat páros gráf különféle paraméterei között (Gallai tételei). Tutte tétele párosítások létezéséről nem páros gráfban.

 

Többszörös összefüggőség, (algoritmusok is).  Hálózati folyamok. A Ford-Fulkerson tétel.

A folyamprobléma általánosításai és  alkalmazásai.

 

A mélységi keresés és alkalmazásai.

 

Lineáris rekurzióra vezető feladatok, állandó együtthatós lineáris rekurziók megoldása.

 

Séták a rácspontokon, tükrözési elv, Catalan-számok  (sor a pénztárnál), bolyongás.

 

A Ramsey-tételkör: Becslések  Ramsey számokra: harmadfokú konstrukció klasszikus halmazrendszer-tételekkel;  tetszőleges polinomiális konstrukció az általános (moduláris)  tételekből.

 

Euklideszi Ramsey tételek; a d dimenziós euklideszi  egység-távolság gráfjának kromatikus száma exponenciális.

 

Halmazrendszerek kombinatorikája: Klasszikus és lineáris algebrai módszerek. A Sperner tétel és a LYM egyenlőtlenség.  Erdős-Ko-Rado tétel. A De Bruijn-Erdős tétel és a  Fisher-egyenlőtlenség. Páratlanfalva tétele.

 

A polinom-módszer: kettő-távolságú ponthalmazok, halmazrendszerek lefogása, l-metsző halmaz-rendszerek.

 

Szabályos kombinatorikai struktúrák: véges projektív és affin síkok, Latin négyzetek.

 

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