Babeş–Bolyai Tudományegyetem Kolozsvár
Matematikai és Informatikai Kar  
2006/2007  tanév,    1.  félév 

I.	A tantárgy adatai

A tantárgy neve: Gráfelméleti algoritmusok (Algoritmica grafurilor)
Kód: MIG0001
Kreditszám: 5
Hol tartják?  (előadás, szeminárium, laboratórium):
Mikor tarják? (előadás, szeminárium, laboratórium):

II.	Az oktatók adatai 
 
Előadás
Név, tudományos cím:    Dr. Kása Zoltán
Elérhetőség (e-mail, telefon): kasa@cs.ubbcluj.ro,  405827, 405327
Fogadóóra : szerda 13–14
Szeminárium
Név, tudományos cím: 
Elérhetőség (e-mail, telefon):
Fogadóóra :
Laboratórium
Név, tudományos cím: 
Elérhetőség (e-mail, telefon):
Fogadóóra :

III.	A tantárgy leírása: 
[Célja, tartalma, milyen kompetenciát biztosít, az órán (előadás, szeminárium laboratórium) használt módszerek – 10-20 sor].

A tantárgy célja, hogy megismertesse a hallgatókkal azokat a gráfelméleti foglamakat és algoritmusokat, amelyekre az informatikai tanulmányaik során feltétlenül szükségük van. A szemináriumokon a tanult foglamakat és algoritmusokat elmélyítik konkrét feladatok megoldásával. A gyakorlati órákon ezen algoritmusok egy részét programozzák és tesztelik. 

IV.	Kötelező könyvészet:
 [Teljes és pontos adatok, elérhetési mód  (akár internetcím is) – max. 10 cím].

1. Andrásfai Béla, Gráfelmélet, Polygon Kiadó Szeged , 1994. 
2. Bege Antal, Kása Zoltán: Algoritmikus kombinatorika és számelmélet, Ed. Presa Univ. Clujeana, 2006
3. Katona Gyula Y., Recski András, Szabó Csaba: Gráfelmélet, algoritmuselmélet és algebra, Budapest, Egyetemi jegyzet, 1997. 
4. Berge, C., Teoria grafurilor si aplicatiile ei, Ed. Tehnica, 1972
5. Tomescu, I., Introducere in combinatorica, Ed. Tehnica, 1972
6. Kása Zoltán: http://www.cs.ubbcluj.ro/~kasa

(A kari könyvtárban megtalálhatók):

V.	Az oktatásban használt eszközök:
[Esetenként: számítógép, laboratóriumi felszerelések, különleges eszközök stb. – annak megjelölésével, hogy a kar biztosítja-e vagy nem – nem kötelező].

A gyakorlati órákat a kar számítógép-laboratóriumaiban tartjuk.

VI.	A tevékenységek és ellenőrzések/részleges vizsgák órarendje:
[Minden tevékenység – előadás, szeminárium, laboratórium, részleges vizsga – tematikája, dátuma és a következő adatok (tevékenységekként): 
-	alapfogalmak vagy kulcsszavak, 
-	a megfelelő kötelező könyvészet adatai (fejezetek, oldalak)
-	a hallgatók kötelezettségei az illető tevékenységen (kötelező olvasmányok, házi feladatok, dolgozatok)].

1. előadás: Alapfogalmak. Milyen feladatok megoldásánál használhatunk gráfokat
2-3. előadás: Legrövidebb utak problémája (Dijkstra, Ford, Warhall-Floyd, Bellman-Kalaba algoritmusai)
4. előadás: A kritikus út módszere és alkalmazásai 
5. előadás: Euler-bejárás
6. előadás: Hamilton-bejárás 
7. előadás: Fák és ligetek. Alkalmazások 
8. előadás: Síkgráfok 
9-11.  előadás: Folyamfeladatok és alkalmazások (Ford–Fulkerson-algoritmus, általánosított folyamok, minimális költségű folyamok)
12. előadás: Párosítás páros gráfokban (magyar módszer, alkalmazások)
13. előadás: Extrémális feladatok a gráfelméletben (Ramsey- és Turán-típusú feladatok)
14. előadás: Függgetlen ponthalmazok, színezések

1. gyakorlat: Gráfok ábrázolása
2. gyakorlat: Távolsági mátrix kiszámítása, alkalmazás útkeresésre
3. gyakorlat: Dijsktra és Ford algoritmusa
4. gyakorlat: Bellman–Kalaba-algoritmus
5. gyakorlat: Kritikus út módszere
6-7. gyakorlat: Magyar módszer

A hallgatók tevékenységét a szemináriumokon és a gyakorlati órákon állandóan ellenőrizzük.  Ezen tevékenységek súlya a végleges jegyben 50 %.  Nincsenek félévközi vizsgák.

VII.	Az értékelés módja:
[A hallgatók milyen tevékenységét értékeljük (állandó ellenőrzés, zárthelyi dolgozatok, kutatási projektek, aktív részvétel stb.), ezek súlya a végleges jegyben, a vizsgáztatás módja, értékelési kritériumok]. 

A végleges jegyben 50% súllyal szerepel az írásbeli vizsga, 25% súllyal a szemináriumi és 25% súllyal a laboratóriumi tevékenység.

VIII.	Szervezési kérdések, a különleges esetek kezelése:
[Óralátogatás (esetleg), vizsgára való jelentkezés feltételei, bepótolás lehetőségei, plagizálás, másolás, csalás következményei, óvások megoldása].

A laboratóriumi dolgozatok elkészítése kötelező határidőre, esetleg pótolni lehet más csoporttal. Mindenki megnézheti az írásbeli dolgozatát, az óvást eredményét helyben megtudhatja.

IX.	Ajánlott, de nem kötelező könyvészet:
[Teljes és pontos adatok, elérhetési mód  (akár internetcím is) ].

1. Cataranciuc, S., Iacob,  M. E., Toadere, T., Probleme de teoria grafelor, Lito. Univ. Cluj-Napoca, 1994
2. Kása, Z., Tartia, C., Tâmbuilea, L., Culegere de probleme de teoria grafelor, Lito. Univ. Cluj-Napoca, 1979
3. Gondran M., Minoux, M., Graphes et algorithmes, Paris, 1979
4. Rosu, A., Teoria grafurilor, algoritmi, aplicatii. Ed. Militara, 1974
5. Lovász, L., Kombinatorikai problémék és feladatok, Typotex Kiadó, 1999
6. Toadere, T., Elemente de teoria grafelor, Lito. Univ. Cluj-Napoca, 1992
7. Tomescu, I., Probleme de combinatorica si teoria grafurilor, Ed. did. si ped., Bucurest

(A kari könyvtárban megtalálhatók).