26.6.Feladatok
Előző 26. fejezet - Programozási tételek Következő

26.6.Feladatok

26.1. Feladat.

Lokális minimumok száma

Adottak az hosszúságú egészeket tartalmazó vektor. Adjuk meg, hogy hány lokális minimum van a vektorban. (Lokális minimum egy elem, ha kisebb a baloldali és nem nagyobb a jobboldali szomszédjánál.) Oldjuk meg a feladatot legfeljebb processzorral szinkron arhitekturán a lehető legkevesebb lépésben.

  • a) Specifikáljuk a feladatot!

  • b) Adjunk megoldó programot és mutassuk meg, hogy megfelel a specifikációnak !

26.2. Feladat.

Feltételes összegzés

Adott az vektor, és az függvény.

Számítsuk ki a

értéket!

Készítsük el a feladat specifikációját, írjunk fel megoldó programot és lássuk be a helyességét

26.3. Feladat.

Logikai mátrix sorainak egyezése egy mintával

Adottak az logikai mátrix és az -elemű logikai vektor. Adjuk meg, hogy a mátrix hány sora egyezik meg a vektorral. Oldjuk meg a feladatot processzorral szinkron arhitekturán a lehető legkevesebb lépésben.

  • a) Specifikáljuk a feladatot!

  • b) Adjunk megoldó programot és mutassuk meg, hogy megfelel a specifikációnak

26.4. Feladat.

Logikai mátrix szorzása

Adottak az logikai mátrix és az -elemű logikai vektor. Számítsuk ki a mátrix és a vektor szorzatát. Oldjuk meg a feladatot processzorral szinkron arhitekturán a lehető legkevesebb lépésben.

  • a) Specifikáljuk a feladatot!

  • b) Adjunk megoldó programot és mutassuk meg, hogy megfelel a specifikációnak

26.5. Feladat.

Első egyezés

Adottak az függvények. Számítsuk ki az és értékeket, ahol az első olyan index, melyre a három függvény értéke megegyezik, l az a tulajdonság, hogy létezik ilyen index.

  • a) Specifikáljuk a feladatot!

  • b) Adjunk megoldó programot és mutassuk meg, hogy megfelel a specifikációnak

26.6. Feladat.

Számoljuk ki két N bites bináris szám szorzatát. Specifikáljuk, adjunk rá programot, majd lássuk be, hogy a program megoldja a feladatot, megfelel a specifikációnak. A megengedett műveletek: léptetés, bitek egyenlőségvizsgálata és bitre vonatkozó értékadás.

26.7. Feladat.

Adott egy irányított, véges, körmentes gráf. Döntsük el, hogy van-e a gráfnak olyan irányított útja, amely minden csúcsot pontosan egyszer érint! (A gráfot egy -s mátrixban reprezentáljuk.) A gráf csúcsainak száma: , a csúcsok fokszáma legfeljebb . Rendelkezésre áll processzor. 

26.8. Feladat.

Adott egy irányított, véges, körmentes gráf. A csúcsokat 0-val, illetve 1-gyel címkézzük. Döntsük el, hogy van-e a gráfnak olyan irányított útja, amely mentén a csúcsok címkéinek sorozata pontosan egy előre megadott természetes szám kettes számrendszerben felírt alakját adja meg! A gráf csúcsainak száma: , a csúcsok fokszáma legfeljebb . (A gráfot egy -es mátrixban reprezentáljuk.) Rendelkezésre áll processzor. 

26.9. Feladat.

Visszavezetés

Adott egy fekete-fehér digitalizált kép egy sora az hosszúságú vektorban. A vektor egy eleme 0 vagy 1, a 0 a fekete, az 1 fehér képpontot jelöl. A sor minden képpontjára állapítsuk meg (azaz írjuk a vektor megfelelő elemébe), hogy milyen messze van tőle jobbra az első fekete képpont ! ( Fekete pontokra ez az érték 0)

26.10. Feladat.

Visszavezetés

Adott egy fekete-fehér, sorból és oszlopból álló, digitalizált kép. A kép minden képpontjára az mátrix tartalmazza, hogy milyen messze van tőle jobbra az első fekete képpont ( Fekete pontokra ez az érték 0). A kép egy bekezdésekre tagolt szöveget tartalmaz, minden bekezdés első sora beljebb kezdődik. Meg szeretnénk keresni a bekezdések kezdetét a k’epen. Feladat : Jelöljük meg a kép első oszlopának azon pontjait (azaz az logikai vektor megfelelő elemeit állítsuk igazra) , melyek felett van legalább olyan sor, melynek első képpontja feh’er.

Párhuzamos és elosztott rendszereket gyakran írunk le folyamathálózatok formájában [[???Hoa 78, ???Hoa 85]]. A folyamatokat dobozokkal jelöljük, a folyamatok közötti kommunikáció formája üzenetküldés. Az üzeneteket egyirányú kommunikációra alkalmas csatornákon keresztül juttatja el a feladó a címzettnek, címzetteknek. Feltételezzük, hogy az üzenettovábbítás megbízható, üzenetek nem veszenek el, nem sérülnek meg, csak a valóban elküldött üzenetek érkeznek meg. Az üzenetküldés aszinkron, a feladó általában rögtön folytatja tevékenységét miután a csatornára elhelyezte az üzenetet, nem kell megvárnia az üzenet átvételét. A csatornák sor típusú változóként viselkednek, átmenetileg képesek tárolni a már elküldött, de még nem fogadott üzeneteket. A csatorna kapacitása határozza meg a tárolható üzenetek számát. Ha a csatorna kapcitása korlátos, akkor előfordulhat, hogy a küldő fél nem tudja rögtön elhelyezni üzenetét és várakozni kell, amíg a csatorna képes nem lesz újabb üzenet fogadására. Minden csatornához két sor típusú változó tartozik, az egyik a csatornán várakozó üzeneteket tartalmazza (a csatorna aktuális állapota), a másik a csatorna története. A csatorna története minden olyan üzenetet tartalmaz helyes sorrendben, amelyik valaha rákerült a csatornára, a történetváltozóról a fogadó fél nem távolítja el az üzeneteket. A történetváltozót egy felülvonással jelöljük. A történetváltozó tárolása a valóságban nehezen vagy egyáltalán nem megoldható, mert egy hosszú ideig futó programban az üzenetek száma idővel minden korlátot meghaladhat. Történetváltozókat ezért csak úgy használunk értékadásokban, hogy értéküket csak saját új érték meghatározásához használjuk fel. Ezek az egyszerű értékadások elhagyhatóak anélkül, hogy a program többi részének működése megváltozna.

26.11. ábra -

A ábrán két folyamatot és az őket összekötő csatornát láthatjuk. A csatornára a folyamat helyezhet el üzenetet, egész számok formájában. A folyamat olvas a csatornáról. Az alábbi műveletek tartoznak a csatorna típusú változókhoz:

Az alábbiakban megadjuk az egyes műveletek pontos jelentését is. Elemi műveletek jelentését megadhatjuk hatásrelációjukkal, vagy azzal ekvivalens módon a leggyangébb előfeltételük kiszámításának meghatározásával is.

Figyeljük meg, hogy üzenetküldés leggyengébb előfeltételének kiszámításakor a csatorna történetét is helyettesíteni kell az utófeltételben, míg az üzenet eltávolítása nem érinti a történetváltozót.

Ha a folyamatok közötti kommunikációra nem használunk osztott változókat, hanem kizárólag csatronaváltozók segítségével oldjuk meg az információ cseréjét, akkor az egyes folyamatok közötti kapcsolat jól ellenőrizhetővé válik. A lokalitás tétel állítását fogalmazhatjuk újra speciális formában:

26.11. Lemma (Lokalitás folyamthálózatokban).

  • Ha egy állítás változói között csak folyamat lokális változói, ill. kimenő csatornaváltozói szerepelnek, akkor a állítás stabil a többi folyamatban.

  • Ha és , akkor stabil a teljes folyamathálózatban.

Előző Fel Következő
26.5.Elemenként feldolgozható függvények Tartalom 26.7.Természetes számok generátora