Hirdetmények

• Kezdés pontosan 10 óra 15 perckor!!!
• Első alkalom: Március 8.

• Jegyet szerezni előadás megtartásával lehet. Aláírást csak az kaphat, aki legalább az alkalmak 66%-án ott van!
• Minden előadó köteles az előadás előtti vasárnap estig címet és absztraktot küldeni a kiraly@cs.elte.hu címre.
• A szemináriumi levelező-listára feliratkozni az Alkszem-request@cs.elte.hu címre küldött SUBSCRIBE tárgyú levéllel lehet. Érdemes feliratkozni, minden alkalom előtt szétküldjük az absztaktot!

1. alkalom (III. 22.) Király Zoltán

"Maximalizálás csak k-méretű halmazokon felvett értékek lekérdezésével"
Feige és Tennenholtz cikke.

Egy nemnegatív monoton szubmoduláris függvényt akarunk maximalizálni. Persze ez az egész alaphalmazon veszi fel a maximumát, ezért adott még egy k szám, és a k-elemű részhalmazokon keressük a maximumot. Erről a feladatról lehet tudni, hogy a mohó adja a legjobb közelítést, és ez kb. 0,632*OPT.

Mostani modellünkben azonban nem kérdezhetjük le bármely részhalmaz f értékét, csak a pontosan k eleműekét. A fő kérdés, amit most vizsgálunk, hogy ekkor polinom időben mi a legjobb elérhető approximációs hányados.

Megmutatjuk, hogy (1/2)+(1/4k) elérhető egy lokális mohó algoritmussal, de minden (1/2)+epsilon -közelítéshez már randomizáltan is kell exponenciális kérdés (ha k*epsilon tart a végtelenhez).

A második részben egy speciális esetet vizsgálunk. Van egy ismeretlen páros gráf, az f függvény az alsó osztályának részhalmazain van definiálva úgy, hogy egy részhalmaz értéke a szomszédok száma. Mi itt is csak k elemű alsó halmazokra kérdezhetjük le ezt az értéket. Erre a spec. esetre az előző alsó becslés nem működik, és a szerzők adnak is egy randomizált algoritmust, ami 0,50004-közelítő.

2. alkalom (IV. 5.) Fonyó Dávid

"Testreszabható úttervezés"
Delling, Goldberg, Pajor és Werneck cikke.

Habár Dijkstra algoritmusa közel lineáris időben oldja meg a legrövidebb út megtalálásának feladatát, kontinensméretű úthálózatok esetében futtatása így is több másodpercet vesz igénybe. A gyakorlatban inkább használnak olyan algoritmusokat, melyek egy - esetleg hosszabban futó - előfeldolgozó-fázis keretében kiegészítő adatokat gyártanak. Ezeket felhasználva a lekérdezések nagyon gyorsak lesznek. A legtöbb kutatás a természetes metrika, azaz az utazási idő minimalizálására irányul, holott a valóéletben sokszor másfajta metrikákat szeretnénk vizsgálni (pl: legrövidebb távolság, bicikliutak/autópályák előnyben részesítése/elkerülése, balkanyarok elkerülése).

Bemutatunk egy olyan algoritmust, amely hatékonyan alkalmazható tetszőleges metrikára, képes egyszerre több metrika szerinti lekérdezésekre is gyors választ adni, valamint kezelni menet közben generált új metrikákat. Ez lehetőséget biztosít például arra is, hogy az aktuális forgalmi helyzetnek megfelelően szabjuk testre a lekérdezések eredményét.

3. alkalom (IV. 26.) Fekete István

"Tételbizonyítás a kockavilágban I"

Célunk a (gépi v. automatikus) tételbizonyítás bemutatása a kockavilágban. A kockákból épített alakzatok világa egyszerűen áttekinthető: ismert számú (pl. n=5), névvel ellátott (pl. A, B, C, D, E) egybevágó kockából kialakított oszlopok (halmaza) egy asztal felett. A konfigurációk (pl. n=5 esetén 501 elemű) struktúra osztályának leíró nyelve és logikai axiomatizálása azonban elég összetett. Ezen az univerzumon megfogalmazott F1, F2, ..., Fm => G alakú tételek bizonyítását szeretnénk elvégezni. Két módszert vizsgálunk: (1) a logika alapú rezolúciót, valamint (2) a kombinatorikus leszámolás alapú eljárást. Utóbbi a konfigurációk generálását, valamint a feltételek és a következmény formuláinak teljesülésének ellenőrzi. A tétel fennáll, ha az állításoknak a konfigurációk állapotterén vett igazsághalmazaira teljesül, hogy az [F1], ..., [Fm] halmazok metszete benne van [G]-ben. Megnézünk egy olyan számítógépes programot (Dankovics Attia szakdolgozata), amely képes a kombinatorikus tételbizonyítás elvégzésére. (Ennek erőssége informatikai szempontból az, hogy implementálta az egyenlőségjeles elsőrendű logika nyelvének interpreterét).

4. alkalom (V. 10.) Tichler Krisztián, Sági Gábor és Fekete István

"Tételbizonyítás a kockavilágban II"

Az előző előadásban elhangzott legfontosabb fogalmak (a kockavilág axiómái, a logikai alapú, illetve kombinatorikus leszámolás alapú tételbizonyítás) átismétlése után kicsit elmélyedünk a részletekben.

A konfigurációk hierarchikus generálása: a természetes számok particionálásának, a kombinációk és permutációk generálásának algoritmusaival az összes konfiguráció három szinten állítható elő.
Ez lehetővé teszi a vágásokat a generálásban, ha valamelyik feltétel formula már magasabb szinten, egy egész konfiguráció halmazra nem teljesül. Az OEIS portál ismeri a konfigurációk számainak sorozatát és több értelmezést ad rá, köztük éppen azt is, amelyet mi használunk.

A véges kockavilág általános struktúraosztálya: a kockák n száma nem adott, csak azt tudjuk róla, hogy véges.
Ez a struktúraosztály nem axiomatizálható. Ezzel összefüggésben vizsgáljuk, hogy a kockavilág véges modelljeiből álló struktúraosztály eldönthető-e.

A végtelen kockavilág struktúraosztályai: megvizsgáljuk, hogy ha a kockák száma végtelen, akkor a megadott axiómarendszer, illetve csekély módosításai milyen modellekben válnak igazzá.
Konkrétabban: ha kappa és lambda két (akár végtelen) számosság, akkor legyen K_kappa, lambda azoknak a kockavilág-modelleknek az osztálya, melyekben kappa darab kocka van, és minden oszlop alacsonyabb, mint lambda. E modellosztályok strukturális, axiomatizálhatósági, és eldönthetőségi tulajdonságait vizsgáljuk.