A kurzus a matematikus MSC hallgatók számára meghírdetett "Algoritmusok és bonyolultságelmélet" heti két órás kurzus. Az elõadáshoz gyakorlat is tartozik. A kurzus kreditelése egyben történik. A gyakorlati teljesítmény és az elõadás megértése külön-külön lesz elbírálva. Mindkettõért 50-50 pont kapható.

A gyakorlatra vonatkozó szabályokat a gyakorlat vezetõje tisztázza.

Az elõadás mégértését írásbeli vizsgán tesztelem. Az írásbeli vizsga pontozásáról csak annyit, hogy alapfogalmak ismeretének hiánya 0 pontos vizsgát eredményez. A vizsgához közeledve pontos tematikák, mintavizsgák segítik az elvek teljes tisztázását.

Az 50 pontos vizsgát ki lehet váltani egy 20+30-os skálára, ahol a bentülõs vizsga súlya csak 30 pont. A maradék 20 pontot egy elõadás lejegyzetelésével lehet megszerezni. A jegyzetelésre az elõadás elõtt kell jelentkezni. Minden alkalommal EGY diák kaphat jogot erre. Két héten belül kell a jegyzet elsõ változatát bemutatni. A jegyzetnek érthetõnek kell lenni olyan számára is, aki az elõadáson nem vett részt. Megjegyzéseim alapján még két hét áll a végsõ változat kialakítására, ami publikus lesz. A 20 pont a befektetett munka, önállóság függvénye. Aki kapkodva, összevissza jegyzetet állít össze az kevesebb pontot szerez. Egy diák legfeljebb egyszer lesz kijelölve jegyzetelésre. Elõre láthatólag a max 100 elérése mellett az jegyek a következõképpen alakulnak ki:

• 1: elégetlen teljesítés gyakorlaton, illetve < ₌50 összpont
• 2: teljesített gyakorlat és 50 < összpont < ₌ 60
• 3: teljesített gyakorlat és 60 < összpont < ₌ 70
• 4: teljesített gyakorlat és 70 < összpont < ₌ 85
• 5: teljesített gyakorlat és 85 < összpont

A biztos ismeret, illetve az anyag folyamatos követésének hiánya komoly problémákat okozhat a vizsgára készülésnél és a vizsgánál. Így az elõadás hallgatása nem csupán heti 2 óra elõadáson való megjelenést jelent, de otthoni munkát is követel. A hallgató felkészültségétõl függõen ez heti több óra munkát is jelenthet.

Elõadás: Csütörtök 8:00-9:30, Grünwald-terem

Szobám: A Bolyai-épület 102-es szobája

Fogadóóra: Késõbb meghatározandó idõpont vagy megbeszélés szerint (Telefon: X 4088 (kívülrõl 544 088)).

    Akinek ez az idõpont nem megfelelõ vagy más problémával akar hozzám fordulni az emailen hajnal@math.u-szeged.hu tud velem legkönnyebben kapcsolatot teremteni

• C. Papadimitriou: Számítási bonyolultság, Novadat Kiadó, 1999.
• M. Sipser: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
• Lovász László: Algoritmusok bonyolultsága, Tankönyvkiadó, 1989.

• Arora-Barak egy új könyvének elérhetõ változata
• Jin-Yi Cai egy készulõ könyvének elõzetes változata
• Egy `Computational Complexity Theory' nyári kurzus (David Mix Barrington és Alexis Maciel) anyaga BSc-seknek
• Oded Goldreich `Computational Complexity: A Conceptual Perspective ' könyvének elõzetes változata