A kurzus idõpontja: Kedd 10-12, helye: Irinyi 106
A bonyolultságelmélet a matematika új ága, ami egy új dimenziót ad a matematikának. Eddig klasszikusnak számító területeket lehet ``bonyolultságelméleti szemüveggel'' újraértékelni. A ``klasszikus'' és algoritmikus matematiks között aktív, kétirányú kapcsolat létezik.
A bonyolultságelmélet matematikai jól leírt problémák között definiál osztályokat, amelyek valamilyen értelemben a probléma ``nehez'ségének'' matematikai definícióiként foghatók fel. Az osztályok között több hierarhia is kialakul. konkrét problémák a hierarhiában elfoglalt helyének meghatározása fontos problémákat rejt, lényeges összefüggésekre világít rá.
A téma matematikailag központi szerepet betöltõ kérdések bonyolultságával kapcsolatos kérdéseket vizsgál. Kiszámíthatóság, PSPACE-teljesség, polinomiális hierarchia, NP-teljesség, P-teljesség, NLOGSPACE-teljesség néhány olyan bonyolultságelméleti fogalom, amely ``nehézséget ír le '' matematikailag korrekt módon. A vizsgált problémák között lesznek algebrai (csoportokra vonatkozó szóprobléma, permanens kiszámítása), gráfelméleti (st-összefüggõség, kromatikus szám approximációja), halmazrendszerekkel kapcsolatos problémák (Vapnyik-Cservonyenszki-dimenzio). A fentiek csak ízelítõt adnbak a vizsgált témák sokszínûségébõl (amely témák bõvülhetnek és szûkülhetnek, ha úgy adódik).
Az elõadásról megpróbálok rövid jegyzeteket készíteni a honlapomon.
Jegyzetek: Az elõadás egyetlen egy könyvet vagy jegyzetet sem követ. Ennek ellenére felsorolok több, az elõadás anyagát részben fedõ, illetve az elmélyülni kívanó hallgató számára hasznos ismereteket nyújtó könyvet.
A témához több honlap kapcsolódik. Itt egy nagyon hiányos (remélhetõleg bõvülõ) listát adok közre:
Kurzusok leírása:
Elektronikus e's nyomtatott u'jságok:
Könyvek:
Társaságok:
A vizsga valószínûleg ``hagyományos'' vizsga lesz. Az ezekrõl való tudnivalókat a félév során tisztázzuk.