A chiptervezés során a fő szempont többnyire az energiahatékonyság és a teljesítmény maximalizálása. Nem mindegy, hogy a kulcsfontosságú komponensek között mekkora a távolság, ez lényegesen befolyásolja a végső teljesítményt, de a chip mérete sem utolsó szempont. A tervezés folyamata, a chip alaprajzának megtervezése az ún. floorplanning, amit chiptervező mérnökök végeznek, és akár hónapokig is eltarthat, mire megtalálják a legjobb elrendezést, ha egyáltalán sikerül. A mesterséges tanuló algoritmusok azonban ebben is egyre többet segítenek, és lehet, hogy hamarosan elveszik a chiptervező mérnökök munkáját. Mielőtt tehát kihal ez a szakma, pillantsunk bele egy kis feladványon keresztül, hogy milyen nehézségekkel is kell megküzdeniük a chiptervező mérnököknek!

151. feladvány: Chiptervezés

Tegyük fel, hogy egy chiptervező mérnöknek az alábbi korlátos négyzetrácson belül kellene megoldania azt a feladatot, hogy az azonos betűvel jelzett vezetékeket összekösse.

A korlátozások a következők:

• Vezetékek nem ágazhatnak el.
• Minden vezeték töröttvonal mentén kell fusson, és csak vízszíntes, függőleges és 45 fokban átlósan futó szakaszokból állhat.
• A vízszintes és függőleges részeknek a berajzolt rácsvonalakra kell illeszkedniük.
• Töréspont csak rácspontban lehet, és a vezetékek sehol nem törhetnek 90 fokban, vagy annál nagyobb mértékben, legfeljebb csak 45 fokban (ennek a korlátozásnak már a chip szélén lévő bevezető szakaszban is érvényesnek kell lennie, ezért rajzoltuk be a bejövő vezetékek utolsó szakaszát, és nem csak az érintkező pontokat).
• Kereszteződések lehetnek, de egy pontban csak két vezeték kereszteződhet, és azok is csak egymásra merőlegesen haladhatnak át egymáson, egyik sem törhet meg a kereszteződésben.

Van megoldása a feladatnak?

Bónusz kérdések haladóknak: Hány különböző megoldás van? Mely betűkiosztásokra lenne még megoldás, és melyekre nem létezik? Ez utóbbi kérdést kisebb chipek esetére is feltehetjük, lásd az alábbi ábrákat.

Nehézségi szint:

A megfejtéseket részletes magyarázattal és a szükséges ábrákkal együtt az eszventura@qubit.hu címre várjuk. A leggyorsabb és legkreatívabb megoldást küldő versenyzőink felkerülnek az Ész Ventura dicsőségfalára, közöttük és minden jó megoldást beküldő versenyző között év végén nyereményeket sorsolunk ki. Fiatal megoldóinktól kérjük, hogy tüntessék fel életkorukat és évfolyamukat, mert körükben különdíjakat is ki fogunk sorsolni. Az e-mail subject mezőjében kérjük továbbá sorszámmal jelezni, hogy melyik feladvány megoldásáról van szó. Beküldési határidő: június 15. éjfél.

Az Ész Ventura feladványügyi rovat gazdája: Gáspár Merse Előd fizikus, kognitív kutató, társasjáték-fejlesztő és bűvész.