Bonyolultságelmélet szeminárium

2015 Tavasz

Vezetők: Grolmusz Vince, Friedl Katalin, Pálvölgyi Dömötör, Király Zoltán

Minden második héten, Szerda 10:15-13:00
Pázmány Péter sétány 1/C. 3.607


Hirdetmények


Ajánlott irodalom


1. alkalom (II. 11.) Papp László

"Cikk-Cakk rendezés"
Goodrich cikke.

Cikk-Cakk rendezés: Determinisztikus "adat felejtő" (data-oblivius) rendező algoritmus O(n log(n)) időben.

Ismert tény, hogy egy n hosszú listát O(n log(n)) idő alatt tudunk determinisztikusan sorosan rendezni. Sokáig kérdéses volt, hogy létezik-e O(n log(n)) lépést használó hatékonyan párhuzamosítható rendezés. 1983-ban az Ajtai, Komlós és Szemerédi által készített AKS rendező hálózat adta meg erre a pozitív választ. Sajnos az AKS és eddigi javításai a gyakorlatban használhatatlanok mivel bár a mélységük O(log(n)), a tényleges műveletszám ~10.000.000 n log(n).

A rendező hálózatok rendelkeznek azon pozitív tulajdonsággal, hogy "adat felejtő"-ek: Az algoritmus memória hozzáférési sorozatai azonos hosszúságú bemenetek esetén azonosak. Így a memória hozzáférések - a bemenet hosszától eltekintve - függetlenek a bemeneti adattól. Így az AKS volt sokáig a legjobb ismert O(n log(n))-es "adat felejtő" rendező algoritmus is.

A Goodrich által készített Cikk-Cakk rendező hálózat a Shellsort és az AKS ötleteit használja. Az általa igényelt műveletszám ~10.000 n log(n), mely kevesebb az AKS műveletszámánál. Bár O(n log(n)) mélységű, így nem párhuzamosítható hatékonyan, ennek ellenére érdekes, mivel jelenleg ez az ismert legkevesebb műveletet igénylő "adat felejtő" rendező algoritmus.

Az előadás után cikkosztás volt.


2. alkalom (II. 25.) Kovács Erika

"Hálózatok kapacitásának közelíthetetlensége lineáris hálózati kóddal"
Lovett cikke.

A hálózati kódolás egy információküldési eljárás, mely lehetővé teszi, hogy egy hálózat belső pontjai a különböző csúcsokból beérkező üzeneteknek valamilyen függvényét továbbítsák. Aszerint, hogy ezen függvények milyen halmazból kerülhetnek ki, definiálhatunk általános- és lineáris hálózati kódokat. Ez utóbbiak a küldött üzeneteket egy vektortér elemeiként kezelik, és mindig valamilyen lineáris kombinációjukat továbbítják.

Ismert, hogy bizonyos üzenetküldési feladatoknál a lineáris kódok optimálisak (pl. aciklikus gráfok, egy forrás, több terminálpont esete [Jaggi et al.] ), de arra is akad példa, amikor bizonyítottan nem, mivel az általános hálózati kódokkal nagyobb kapacitás érhető el (pl. több forrás-terminál pár esetén [Dougherty et al.]).

Természetesen adódik a kérdés, hogy az általános hálózati kódolással elérhető kapacitás közelíthető-e a lineáris kódok kapacitásával? A cikk fő eredménye, hogy ilyen közelítés semmilyen konstanssal sem lehetséges.


TERV:

3. alkalom (III. 11.) Papp László

"Fekete-fehér játékok PSPACE-teljessége"
Fenner, Grier, Messner, Schaeffer és Thierauf cikke.


4. alkalom (III. 25.) Kisfaludi-Bak Sándor

"Gyors mátrixszorzás korlátai"
Ambainis, Filmus és LeGall cikke.


5. alkalom (IV. 15.) Herscskovics Dávid

"Alsó becslés a Klikk-Független diszjunktság nemdeterminisztikus kommunikációs bonyolultságára"
Göös cikke.


6. alkalom (IV. 29.) Tóthmérész Lilla

"A Turing- és a Karp-redukció szétválasztása"
Mandal, Pavan és Venugopalan cikke.


7. alkalom (V. 13.) Király Csaba

"TBA"
cikke.