Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

Fleiner Tamás, egyetemi tanár, SzIT

Katona Gyula, egyetemi docens, SzIT

Kaszanitzky Viktória, egyetemi adjunktus, SzIT

Recski András, egyetemi tanár, SzIT

Sali Attila, egyetemi docens, SzIT

A tantárgy célkitűzése a villamosmérnöki tanulmányokhoz szükséges és a mérnöki alapműveltséghez tartozó egyes alapvető matematikai ismeretek elsajátítása, azok szemléletmódjának kialakítása. Ezen belül a tantárgy a lineáris algebra és a gráfelmélet egyes területeire nyújt bevezetést.

A tantárgyat sikeresen teljesítő hallgató képes lesz:

·      érteni és alkalmazni a tárgyban előkerülő fogalmakat és ismereteket;

·      önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat;

·      alkalmazni a tárgyban szereplő algoritmusokat;

a későbbi tanulmányok során felismerni azokat a helyzeteket, ahol a tárgyban tanult ismeretek szerephez jutnak és sikerrel alkalmazni a tanultakat.

1. Gráfelméleti alapfogalmak. Gráfok fokszámösszege, komponensek, utak, séták, élsorozatok, izomorfia. Fák és erdők, azok egyszerűbb tulajdonságai.
2. Feszítőfa, alapkörrendszer (fundamentális körrendszer), fundamentális vágásrendszer. Minimális költségű feszítőfa, Kruskal algoritmusa.
3. Gráfbejárás fogalma, élek osztályozása, BFS. Legrövidebb utak és a BFS tulajdonságai, legrövidebb utak fája. Élmenti javítás, Dijkstra algoritmusa.
4. Ford és Floyd algoritmusai. Mélységi keresés, irányított körök keresése, aciklikus gráfok jellemzése. PERT feladat, megoldásnak algoritmusa.
5. Euler-séta és körséta, létezésének szükséges és elégséges feltétele (összefüggő gráf esetén). Hamilton-kör és út fogalma. Szükséges, illetve elégséges feltételek Hamilton-kör létezésére: Dirac és Ore tételei ill. komponensszám pontelhagyások esetén.
6. Gráf síkba, illetve gömbre rajzolhatósága. Az Euler-féle poliédertétel és következményei egyszerű, síkbarajzolható gráfokra. Kuratowski gráfok, soros bővítés, Kuratowski tétele. Síkbarajzolt gráf duálisa. Elvágó él, soros élek, vágás. A duális gráf tulajdonságai (élszám, csúcsszám, összefüggőség, kör-vágás dualitás, annak speciális esetei). Síkgráfok kromatikus száma, négyszíntétel.
7. Lineáris egyenletrendszerek megoldása Gauss-eliminációval. Elemi sorekvivalens lépés, lépcsős alak és redukált lépcsős alak fogalma. Kapcsolat az
   egyenletek és ismeretlenek száma, illetve a megoldás egyértelműsége között.
8. Rn és Rn alterének fogalma. Lineáris kombináció, generált altér (és ennek altér volta), generátorrendszer. Lineáris függetlenség (ennek kétféle definíciója és ezek ekvivalenciája). Az újonnan érkező vektor lemmája. F-G egyenlőtlenség.
9. Bázis és dimenzió fogalma, a dimenzió egyértelműsége. Standard bázis, Rn dimenziója. Koordinátavektor fogalma és annak egyértelműsége. Bázis létezése Rn tetszőleges alterében.
10. Determináns definíciója. Permutációk inverziószáma. A determináns alaptulajdonságai. Determináns kiszámítása Gauss-eliminációval. A kifejtési tétel.
11. Műveletek mátrixokkal (összeadás, skalárral szorzás, szorzás, transzponálás), ezek tulajdonságai. A transzponált determinánsa. Determinánsok szorzástétele (biz. nélkül). Lineáris leképezések.
12. Mátrix inverze, létezésének szükséges és elégséges feltétele, az inverz kiszámítása. Mátrix rangja, a rangfogalmak egyenlősége, a rang meghatározása. Az n × n-es lineáris egyenletrendszerek egyértelmű megoldhatóságának jellemzése a determináns segítségével. Kapcsolat a lineáris egyenletrendszerek, az Rn-beli generált altérhez tartozás kérdése, illetve a mátrixszorzáson alapuló mátrixegyenletek között. Kapcsolat négyzetes mátrix determinánsa, illetve a sorok és az oszlopok lineáris függetlensége között.

Szorgalmi időszakban: A félév folyamán két zárthelyit íratunk. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) feltétele a zárthelyiken külön-külön legalább 40% -os teljesítmény.

Azok a hallgatók, akik egy korábbi félévből érvényes aláírással rendelkeznek, megkísérelhetik újból megírni a zárthelyiket, hogy a korábbi zárthelyik eredményein javítsanak. Erre az esetre az alábbi feltételek vonatkoznak:

l Ha sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor a vizsgajegybe (lásd lentebb) az így kapott eredmény számít bele (akkor is, ha ez rosszabb).

l Ha nem sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámot számítjuk be.

Ha egy érvényes aláírással rendelkező hallgató az aktuális félévben legalább egy zárthelyin megjelenik, azt úgy tekintjük, hogy az illető kísérletet tett az aláírás feltételeinek újbóli teljesítésére (és rá a fenti feltételek vonatkoznak). Ellenkező esetben a legutolsó olyan félévbeli teljesítményt vesszük figyelembe, amikor a hallgató megkísérelte az aláírás feltételeinek teljesítését.

 Vizsgaidőszakban: Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik. A vizsga ebből a tárgyból szóbeli.

A vizsgajegyet a két zárthelyi eredményéből és a vizsgán nyújtott szóbeli teljesítmény súlyozott átlaga, amiben a zárthelyik súlya 2, a szóbeli vizsgáé pedig 3. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyik eredményétől). Ismétlő vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

A vizsgán kapott végső jegyet meghatározó pontszámot az alábbi képlettel számítjuk ki. (zh1 és zh2 az első, illetve második zárthelyin, v pedig a szóbeli vizsgán szerzett pontszám.)

végső_pont = 0,4*(min(50,zh1) + min(50,zh2)) + 1,2*min(50,v).

A végső jegy a végső pontszám alapján: 0-39: elégtelen, 40-54: elégséges, 55-69: közepes, 70-84: jó, 85-100: jeles.

A tárgyhoz tartozó vizsgatételsor félévről félévre változik, az aktuális félévre érvényes vizsgatételsor a tárgy tanszéki weboldaláról tölthető le a szorgalmi időszak utolsó hetétől.

Katona Y. Gyula - Recski András - Szabó Csaba: A számítástudomány alapjai, TypoTEX Kiadó, 2003.

Friedl Katalin – Recski András – Simonyi Gábor: Gráfelméleti feladatok, TypoTEX Kiadó 2006.

Szeszlér Dávid: Bevezetés a számításelméletbe: http://cs.bme.hu/bsz1/jegyzet/bsz1_jegyzet.pdf

Fleiner Tamás: A számítástudomány alapjai: http://www.cs.bme.hu/~fleiner/jegyzet/NESZ.pdf