Recski András (BME)
Lineáris idejű algoritmusok a VLSI huzalozásban
A nagybonyolultságú integrált (VLSI) áramkörök tervezésének egyik fontos feladata a ''részletes huzalozás'', amikor pontok adott részhalmazait kell összekötni bizonyos technológiai előirások figyelembevételével (vezetékek egymástól való távolsága, rétegek száma stb). A szokásos matematikai modellben a pontok (terminals) egy négyzetrács vagy kockarács pontjai és a részhalmazokat (nets) ebben a rács-gráfban pontdiszjunkt utakkal vagy Steiner-fákkal kell összekötnünk. Attól függően, hogy az összekötendő pontok hol helyezkednek el (egy téglalap oldalain (switchbox huzalozás) vagy csak kétátellenes oldalán (csatornahuzalozás) vagy csak egyetlen egyenesen), megfogalmazható a problémáknak egy geometriai hierarchiája. Egy másik hierarchia adódik a technológiai körülményekből (rétegek száma, rétegek közti átvezetések fajtája stb). A legtöbb probléma NP-nehéz, igy a témakör irodalmának nagy része heurisztikus algoritmusokat tartalmaz; ezek egy része a gyakorlatban igen jól működik. Vannak azonban olyan feladatok is, melyek polinom -- gyakran lineáris-- lépésszámban megoldhatóak. Ezek az algoritmusok gyakran a probléma mögött rejlő kombinatorikus struktúrákról is érdekes információkat adnak (perfekt gráfok, egyszerűbb ütemezési problémák stb).
Időpont: szept. 17. kedd 16:15 Helye: BME-ELTE, I. épület E. szárny, 213.