Bevezetés a számításelméletbe II.

Bevezetés a számításelméletbe 2.

Általános infók
Szak	info
Kredit	4
Ajánlott félév	2
Keresztfélév	van
Tanszék	SZIT
Követelmények
KisZH	nincs
NagyZH	2 db
Házi feladat	nincs
Vizsga	szóbeli
Elérhetőségek
Levlista	bsz2@NO-SPAM.sch.bme.hu
Tantárgyi adatlap
Tárgyhonlap

Követelmények

Előtanulmányi rend

Bevezetés a számításelméletbe 1. tárgyból aláírás megszerzése szükséges a tárgy felvételéhez.

A szorgalmi időszakban

• Az aláírás feltételei:
  • Két ZH sikeres (egyenként min. 40%) megírása.
• Megajánlott jegy: nincs.
• Pótlási lehetőségek:
  • A két ZH-ból csak az egyik pótolható, egyszer félév közben, egyszer a pótlási héten (különeljárási díj fejében). Ha egyik ZH sem sikerül elsőre, bukod a tárgyat.
• Elővizsga: nincs

A vizsgaidőszakban

• Vizsga: szóbeli. Kapsz egy témakört, azt 45 perced van kidolgozni, majd előadni azt az egyik vizsgáztatónak. A felelet után a vizsgáztató belekérdezhet a többi témakörbe, ezekre a kérdésekre is tudni kell válaszolni. A ketteshez minden tételt és definíciót ki kell tudni mondani és tudni kell értelmezni. A jobb jegyhez már a témakörödben lévő tételeket tudni kell bizonyítani is, a bizonyított tételek száma és nehézsége alakítja a vizsgajegyet kettes és ötös között.

Félévvégi jegy

• A jegybe (J) a ZH-k (ZH_x) és a vizsga (V) eredménye egyaránt beleszámít a következő módon:
  • $J=0,4*{\frac {ZH_{1}+ZH_{2}}{2}}+0,6*V$
• A tárgy teljesítéséhez a vizsgának is sikerülnie kell, nem elég a jó ZH-eredmény!

Jegyzetek

• Fleiner Tamás: Nagy, egyesített szuperjegyzet (NESZ)
  • Fleiner jegyzet
• Szöllősi Ferenc konzi - ZH-tippek
• Összefoglaló az 1-2. ZH-ra (Turi Barnabás, 2012. ősz)
• Tételek röviden

Kézzel írt előadásjegyzetek

• 2009-es, kézzel írott jegyzet
• 2008. tavasz (Wiener Gábor előadása) - by Elekes Csaba
• 2006-os, kézzel írott jegyzet
• 2003 tavasz (Szeszlér Dávid előadása)
• Jegyzet1 (kézzel írott)
• Jegyzet2 (kézzel írott)

Anyag 1. ZH-ig

• Definíciók (1 oldal)
• Tételek (1 oldal)
• 2006. Tételek az 1. ZH-ig
• 1999. tavasz - by Binzberger Viktor

Bizonyítások

• Chvátal tétele
• Lovász gyenge perfekt gráf tétele + másik Lovász-tétel: α(G') · ω(G')≥|V(G')|
• Pósa-tétel -> Ore-tétel
• Wilson-tétel

Gyakorlatok

Feladatok

• Mester (régi ZH-k és gyakok, Sebők Márton, 2013 ősz) - megoldással, hibákat jelezzétek nekem (2013 tavaszi változat, 2012 őszi változat)
• Hajdany
• Csima Judit - megoldással
• Kármán - megoldással

Gyakorlatfeladatok

• Gyakfeladatok (Sebők Márton, 2013 ősz) - megoldással, hibákat jelezzétek nekem (2013 tavaszi változat, 2012 őszi változat)
• Gyakfeladatok (Tóth Géza & Fogaras Dani, 2012 ősz) - megoldással
• Gyakfeladatok (kissg, 2009) - megoldással
• Gyakfeladatok (Tóth Ági, 2007 tavasz) - megoldással
• Gyakfeladatok (Marx Dániel, 2002 tavasz) - megoldással
• Gyakfeladatok (1999 ősz)
• 0-5. gyak - megoldással
• 1. gyak (Tóth Géza) - megoldással
• 8.gyak (Fogaras Dani) - megoldással
• 1. emelt gyak (2002 tavasz) - megoldással
• 2. emelt gyak (2002 tavasz) - megoldással
• 3. emelt gyak (2002 tavasz) - megoldással

1. ZH

ZH

• 2013 ősz - megoldással
• 2013 tavasz - megoldással
• 2012 ősz - megoldással
• 2012 tavasz - megoldással
• 2011 tavasz - megoldással
• 2011 ősz - megoldással
• 2010 tavasz - megoldással
• 2009 ősz
• 2008 ősz
• 2008
• 2007 ősz
• 2007 tavasz - megoldással
• 2006 tavasz - megoldással
• 2005
• 2004 tavasz
• 2003 tavasz
• 2002 ősz
• 2001 tavasz
• 1999 ősz

pótZH

• 2013 ősz - megoldással
• 2013 tavasz - megoldással
• 2012 tavasz - megoldással
• 2011 ősz - megoldással
• 2011 tavasz - megoldással
• 2010 tavasz - megoldással
• 2007 - megoldással
• 2007 tavasz - megoldással
• 2006 tavasz - megoldással
• 2003
• 1999

2. ZH

ZH

2013 osz - megoldással
2013 tavasz - megoldással
2012 ősz - megoldással
2012 tavasz - megoldással
2011 ősz - megoldással
2011 tavasz - megoldással
2010 ősz - megoldással
2010 tavasz
2007 ősz
2007 tavasz - megoldással
2006 ősz
2006 tavasz - megoldással
2005
2004 tavasz
2003 tavasz
2002 ősz
2001 ősz
2001 tavasz
1999 ősz
1999

pótZH

2013 ősz - megoldással
2013 tavasz - megoldással
2012 ősz - megoldással
2012 tavasz - megoldással
2011 ősz - megoldással
2011 tavasz - megoldással
2010 tavasz
2007 ősz
2006 tavasz - megoldással
2005 ősz
2004 tavasz
2003 tavasz
2001 ősz

zh1-2 & pzh1-2 2009 tavasz - megoldással
zh1-2 & pzh1-2 & ppzh1-2 2007-2008 tavasz
pzh1-2 2008
zh1-2 & pzh1-2 2007 tavasz
zh1-2 & pzh1-2 2006 tavasz
zh1-2 & pzh1-2 2005 tavasz
zh1-2 & pzh1-2 2004 tavasz

Vizsga

Tételsorok

• 2013 ősz
• 2010 ősz
• 2005 ősz
• 2004 tavasz
• 1999 tavasz

Kidolgozott tételek

• 2012 tavaszi félév tételei kidolgozva - bizonyítások nélkül
• 2011 tavaszi félév tételei kidolgozva (Haraszin Péter)
• 2010 őszi félév tételei kidolgozva (Haraszin Péter)
• 2009 tavaszi félév tételei kidolgozva (Vőneki Balázs)
• 2009 1-10.tétel - by vb
• 2008 tavasz - by sp
• 2008 tavasz
• 2006 tavasz - nagyon rövid
• 2006 ősz - bizonyítások nélkül
• 2005 tavasz
• 2004
• Kidolgozott tételek 1
• Kidolgozott tételek 2
• Kidolgozott tételek 3

Régi írásbeli vizsgák

(ilyen most már nincs, de gyakorló feladatnak tökéletesek)

• 2001_1
• 2001_2
• 2001_3
• 2000_1
• 2000_2
• 1998_1
• 1998_2
• 1998_3
• 1998_4
• 1997_1
• 1997_2

Tippek

ZH: Csak feladatok, de érdemes megtanulni a tételeket (bizonyítás nélkül): előfordul, hogy fogalmad sincs hogy kezdj neki egy példának, ilyenkor könnyebb végig gondolni az adott témánál tanult 5-10 tételt, és már biztos el tudsz indulni:) + végtelen feladatmegoldó rutin se árt.

Vizsga: szóbeli. Dobsz (kockával) egy tételt, 45 perced van kidolgozni, jelentkezel ha szimpatikus vizsgáztató jön be:D Bármit húzol, bele fognak kérdezni minimum a tételek felébe; ez tény, nem legenda. Minimum szint (értsd: 2es) az összes definíció és tétel pontos kimondása. Jobb jegyért bizonyítások, alkalmazás (esetleg könnyebb példákon) - ezek előadáson sokkal könnyebben megérthetők, mint jegyzetből. Tanulás közben, ha korábbi tételkidolgozásokat nézegetsz: figyelj arra, hogy nem biztos hogy ua., szoktak változtatni.

--Anna 2013.01.15.

Gyakvezérek

2012 ősz:

• Wiener Gábor
• Kiss Gergely
• Balázs Barbara
• Ács Bernadett
• Richlik György
• Mester Beáta
• Ács Bernadett
• Sebők Márton