Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az I. 710. feladat (2026. október)

I. 710. Ebben a feladatban egy számítógépes hálózat működésének modellezése lesz a cél. Az állomások (csomópontok) között adott számú összeköttetés (vonal) van a hálózatban. Az összeköttetések egy-egy kétirányú kapcsolatot biztosítanak a csomópontok között: ha \(\displaystyle A\) és \(\displaystyle C\) csomópont között \(\displaystyle 3\) vonal van, akkor \(\displaystyle A\) legföljebb \(\displaystyle 3\) adatcsomagot küldhet \(\displaystyle C\)-be, és \(\displaystyle C\) is legföljebb \(\displaystyle 3\) adatcsomagot küldhet \(\displaystyle A\)-ba egyszerre, egyidőben. Az adatcsomagok átvitele a két összekapcsolt csomópont között egy időegységig tart.

A hálózatban tetszőleges két csomópont között van összeköttetés vagy közvetlenül, vagy más csomópontokon keresztül. A hálózat csomópontjait az angol ábécé nagybetűi jelölik, így abban legföljebb 26 csomópont van. A hálózatban közlekedő adatcsomagok az adatokon túl tartalmazzák a feladó állomás (ahol a csomag keletkezett) és a célállomás (ahová el kell jutnia a csomagnak) betűjelét, valamint a csomag keletkezésének időpontját.

Vegyük példaként a következő hálózatot, ahol az élekre írt számok a két csomópont közötti kétirányú átviteli vonalak számát jelölik. A hálózatban két összekötött csomópont között legföljebb \(\displaystyle 10\) átviteli vonal lehet.

A szimuláció elvégzéséhez a csomópontoknak egységes eljárás szerint kell feldolgozniuk a csomagokat és döntést hozniuk, hogy melyik szomszédos csomópontokhoz irányítják őket. Egy állomás az éppen nála tárolt csomagokat időrendben próbálja meg továbbítani: először a legrégebben keletkezett és utoljára a legfiatalabb csomagot. Minden csomag esetében olyan útvonalat választ, amely a legkevesebb további csomóponton keresztül juttatja el a csomagot a cél felé.

Legyen adott példaként egy \(\displaystyle D\) csomópontban keletkező vagy oda továbbításra beérkező csomag, amelynek célállomása a \(\displaystyle B\) csomópont. Amennyiben a \(\displaystyle D\) és \(\displaystyle C\) állomások közötti \(\displaystyle 3\) vonalból legalább egy szabad, akkor ezt a csomagot \(\displaystyle D\) az egyik vonalon küldi majd tovább. Ezzel lefoglalja a \(\displaystyle 3\) vonal közül az egyiket. Ha azonban a \(\displaystyle D\) és \(\displaystyle C\) között már nem lenne szabad vonal, akkor a \(\displaystyle D\) állomás a \(\displaystyle B\)-be tartó csomagot a \(\displaystyle G\) csomópont felé küldené, amennyiben az ott meglévő \(\displaystyle 5\) vonal valamelyike szabad. Ha azok közül sem szabad egy sem – mert a \(\displaystyle D\) már azokon keresztül korábban keletkezett csomagokat küld –, akkor ezt a csomagot \(\displaystyle D\) most nem küldi tovább, a csomag vár egy időegységet. Természetesen nem küldi tovább az \(\displaystyle I\) állomás felé sem, hiszen onnan a \(\displaystyle B\) állomáshoz nem jutna közelebb a csomag.

A hálózat állomásai szinkronizálva vannak, minden állomás egyszerre, egy időegység alatt küld csomagokat a szomszédos állomások felé. A csomagok feldolgozása a csomópontokban elenyésző ideig tart, tehát a \(\displaystyle t\)-edik időegységben beérkezett vagy keletkezett csomagokról azonnal döntést hoznak, és a \(\displaystyle {(t+1)}\)-edik időegységben továbbítják azokat, amelyekhez van szabad vonal.

Készítsünk programot i710 néven, amely modellezi \(\displaystyle \tt T\) időegység alatt (\(\displaystyle \tt 10\leq T\leq 1000\)) a hálózat működését. A szimuláció során minden időegységben \(\displaystyle \tt C\) számú csomag keletkezik (\(\displaystyle \tt1\leq C\leq 10\)), amelynek kiinduló és célállomása a hálózat két véletlenszerűen választott, de eltérő csomópontja. Ha a csomag a \(\displaystyle t\)-edik időegységben keletkezik, akkor az ebben az időegységben beérkezett csomagokkal együtt a \(\displaystyle {(t+1)}\)-edik időegységben kezdődhet a továbbítása. Egy ilyen csomag keletkezési ideje egy \(\displaystyle t\)-nél nagyobb és \(\displaystyle (t+1)\)-nél kisebb valós véletlenszám.

A program standard bemenetének első sorában a hálózatban lévő összeköttetések \(\displaystyle \tt N\) száma, a modellezés teljes idejét megadó \(\displaystyle \tt T\) egész szám és az egy időegység alatt létrejövő új csomagok \(\displaystyle \tt C\) száma szerepel. A következő \(\displaystyle \tt N\) sorban az egyes összeköttetések leírása szerepel a példában látható módon.

A program működés közben jegyezzen fel adatokat annak érdekében, hogy a szimuláció közben statisztikát tudjon adni minden \(\displaystyle t\) időegységben a következőkről:

Bemenet Egy lehetséges kimenet
11 100 10 1 10 0 0 0
A 6 B 2 20 4 0 0
A 4 C 3 30 11 1 1
C 3 D 4 40 19 3 4
C 2 E 5 50 24 5 9
D 5 G 6 60 34 4 13
E 4 G 7 70 43 4 17
E 3 F 8 80 55 4 21
F 2 B \(\displaystyle \dots\)
H 1 C 95 950 901 25 1804
I 1 D 96 960 910 26 1830
J 1 A 97 970 917 31 1861
98 980 928 29 1890
99 990 941 28 1918

A program a standard kimenet \(\displaystyle t\)-edik sorába írja ki a fenti öt mennyiség aktuális értékét a \(\displaystyle t\)-edik időegységben egy-egy tabulátorral elválasztva, a fenti felsorolás sorrendjében.

Példa (a véletlen értékek miatt a kimenet csak tájékoztató jellegű):

Beküldendő egy tömörített i710.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ő 2026. november 16-án LEJÁRT.


Statisztika:

Az I. 710. feladat értékelése még nem fejeződött be.


A KöMaL 2026. októberi informatika feladatai