Az I. 649. feladat (2025. január)

I. 649. A lapunk októberi számában megjelent I. 637. feladatban a Token Ring hálózattal foglalkoztunk. A most következő feladatban a sín topológiájú, Ethernet típusú hálózatok modellezése lesz a cél.

Ebben a hálózatban a számítógépek egy vonal mentén sorban egymás után kapcsolódnak az adatokat átvivő közeghez. A számítógépek folyamatosan figyelik a közös vonalat, és érzékelik, ha azon adat érkezik, illetve érzékelik, hogy a vonalon nincs adat. Egy gép csak akkor kezd adatot küldeni a vonalon, ha azon más adat nem érkezik. Az adat tartalmazza a feladó és a célszámítógép címét. Az adat feldolgozását természetesen csak a címzett gép végzi el, a többiek eldobják a nem nekik szólót. Tekintsük úgy, hogy a vonalon az egyik gép által küldött adat 1 időegység alatt jut el minden másik géphez.

Az adatküldés meghiúsul, ha a közös vonalon ugyanabban az időpontban több számítógép is küld adatot. Ekkor mindegyik gép érzékeli, hogy az adat átvitele nem történhetett meg hibamentesen. Az adott időpontban éppen adatokat küldő gépek egy véletlen időegységig várakoznak, mielőtt újra megpróbálnák elküldeni az adatot. A várakozás véletlen idejét az $\displaystyle [1;N]$ intervallumból választják, ahol $\displaystyle N$ a hálózatban lévő gépek száma. Ha a várakozási idő letelt, akkor a következő olyan időpontban kezdik az adatküldést, amikor a vonal szabad, tehát más nem küld adatot.

A szimuláció során minden gép, amely éppen nem kíván adatot küldeni, egy véletlenszámtól függően eldönti, hogy a következő időegységtől kezdve küld-e adatot, vagy sem. Az adatküldésre való hajlandóságot egy $\displaystyle H$ véletlenszámmal adjuk meg. Ha egy gép egyszer úgy döntött, hogy küldeni szeretne, akkor egészen addig ebben az állapotában marad, amíg az adat elküldése sikeresen, ütközés érzékelése nélkül meg nem történik. A program standard bemenetének egyetlen sorában a gépek $\displaystyle N$ száma ($\displaystyle 2\leq N\leq 255$), a gépek adatküldését jellemző $\displaystyle H$ valószínűség ($\displaystyle 0\leq H<1$) valós szám, valamint a szimuláció teljes idejét időegységben megadó $\displaystyle T$ egész érték ($\displaystyle 1000\leq T<100\,000$) található egy-egy szóközzel elválasztva.

A program a standard kimenetre egy egész és egy valós számot írjon szóközzel elválasztva: mennyi adatot sikerült a szimuláció során átjuttatni a hálózaton, illetve átlagosan mennyi idő telt el egy-egy adat esetén a küldési hajlandóságtól a sikeres adatküldésig.

Példák:

Beküldendő egy tömörített i649.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2025. február 17-én LEJÁRT.

Mintamegoldásként Tóth Marcell Domonkos budapesti, 9. évfolyamos versenyző Python nyelven írt munkáját adjuk közre (i649.py).

Statisztika:

13 dolgozat érkezett.
10 pontot kapott:	Borsos Benedek, Fajszi Karsa, Nagy 292 Korina, Rajtik Sándor Barnabás, Szabó Imre Bence, Tóth Marcell Domonkos.
4 pontot kapott:	1 versenyző.
Nem versenyszerű:	3 dolgozat.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2025. januári informatika feladatai