![]() |
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:
- az időegység \(\displaystyle t\) értéke;
- hány adatcsomag van a hálózatban;
- összesen hány adatcsomag érkezett meg a célba eddig az időegységig;
- összesen hány várakozó adatcsomag van ebben az időegységben a hálózatban;
- összesen hány időegységet kellett várakozniuk a hálózatban eddig a csomagoknak.
| 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
