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. középszint

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

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, 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). Az alternáló utak módszere.

 

Többszörös összefüggőség, kétszeresen összefüggő gráf jellemzése körökkel. 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: a

karakterisztikus egyenlet szerepe.

 

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

 

A Ramsey-tételkör immár részletesebben: Az R(k,l ) és R(3,3,...,3) Ramsey számok becslése. Euklideszi Ramsey-tételek, a sík színezése 3 illetve 9 színnel.

 

Halmazrendszerek kombinatorikája: a Sperner tétel (kapcsolat párosításokkal: első bizonyítás) és a  LYM egyenlőtlenség (ebből második biz.). Az Erdős-Ko-Rado  tétel. A De Bruijn-Erdős tétel.  Extremális gráfok újra: négyszöget nem tartalmazó gráfok, felső becslés az élszámra.

 

Szabályos kombinatorikai struktúrák: véges síkok. Konstrukció a modulo p maradékosztály-test felett.  Véges síkok és négyszögmentes gráfok kapcsolata,

alsó becslés az élszámra. Véges síkok és a De  Bruijn-Erdős tétel.

 

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:

Katona Gyula, Recski András, Szabó Csaba: A számítástudomány alapjai, Typotex, 2004.

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