Az alábbi feladatokat beadandóként lehet teljesíteni (beprogramozni egy tetszőleges programozási nyelven).
Minden egyes feladatra maximálisan 20 pont szerezhető, ha az előírásoknak megfelel, hibátlanul működik, megfelelő dokumentációval van ellátva, és megfelelő statikus szerkezettel rendelkezik elkülönülő logikai és megjelenítő rétegekkel. A program nem szabályozott paraméterei tetszőlegesek lehetnek.
A kész programot személyesen kell bemutatni egy előre egyeztetett időpontban.
1) Hasítófüggvény generátor
Készíts programot, amely alkalmas szöveg hasító függvény előállítására.
A programban betölthetünk tetszőleges szöveget, amelyet a program szavakra bont. Ezt követően minden szónak vesszük az első három karakterét (amennyiben rövidebb a szó, szóközökkel töltjük fel), és ezek előfordulási gyakorisága alapján állapítjuk meg a nyílt címzésű, lineáris hasítótáblában (így a betöltött bemenet eloszlása optimális lesz). Ezt követően lehessen a programban tetszőleges további szöveget betölteni, amelyre a generált hasítófüggvényt alkalmazzuk. A program adja meg a betöltött szövegre a próbálkozások számát.
2) Rendező algoritmusok kombinálása.
Készíts programot, amely egy szekvenciális fájlból kulcs-érték párokat tud beolvasni (mindkettő egész szám, ahol a kulcsok 0-100, az értékek 0-1000 között lehetnek), és lerendezni őket a következő lehetőségekkel:
a) buborékrendezés az értékpárra;
b) kupacrendezés az értékpárra;
c) edényrendezés a kulcs szerint, majd kupacrendezés az érték szerint;
d) edényrendezés a kulcs szerint, majd leszámláló rendezés az érték szerint.
Mindegyik esetben adja meg a program a végeredményt, valamint a rendezéshez szükséges memória, illetve műveletigényt.
3) Útvonaltervezés I.
Adott egy város útvonalhálózata, benne egy, illetve kétirányú utcákkal. A város úgy van felépítve, hogy az utcák párhuzamosak, illetve merőlegesek egymásra. Nyilván tartjuk az aktuális időpillanatban a forgalom nagyságát az egyes utcákban, illetve a lezárt útszakaszokat és sávokat is. A forgalom mértéke 1-től 100-ig terjed, ami azt jelenti, hogy ekkora szorzóval kell megszoroznunk a haladási időnket az utcában, míg a lezárt útirányt 0 jelzi. A kereszteződéseket számozzuk vízszintes, illetve függőleges koordinátákkal, és adott egy kiinduló, illetve egy célkereszteződés. A feladatunk, hogy a kiinduló kereszteződésből minél gyorsabban eljussunk a célba.
Készíts programot, amely a fenti problémát megoldja úgy, hogy a város térképét, illetve a forgalom állapotát külön fájlból olvassa be, a kezdő- és célkoordinátákat a programban lehessen megadni. A program a haladást kereszteződésről kereszteződésre mutassa. Bármely kereszteződésnél meg lehessen adni új forgalomállapotot (illetve az azt tartalmazó fájlt), illetve célpontot, és ekkor a program számolja újra az útvonalat. A fájlok szerkezete tetszőleges lehet (pl. ábrázolhatjuk a térképet mátrixban, ahol egy pont lehet 0, ha nincs út, 1, ha egyirányú balra, 2, ha kétirányú, 3, ha egyirányú jobbra).
4) Útvonaltervezés II.
Készíts programot, amely tömegközlekedésen keresztüli útvonaltervezést valósít meg. A programban megadhatunk (illetve betölthetünk, menthetünk) különböző járatokat, ahol adott egy járatazonosító, induló város, célváros, indulási idő, érkezési idő, utazás költsége és a pontosság valószínűsége (pl. VB192, Debrecen, Nyíregyháza, 10:10, 11:30, 1600, 0.3). Járatokból tetszőlegesen sok lehet (és ebből kifolyólag városokból is), és két város között is tetszőlegesen sok járat közlekedhet. A feladat, hogy egy adott időpontban eljussunk egy adott városból egy másikba a következő módok valamelyikén (ez a programban kiválasztható):
- leggyorsabban,
- leggyorsabban úgy, hogy a pontosság összesített valószínűsége
egy adott határ felett van (amit a felhasználó szabályozhat),
- legkevesebb átszállással,
- legolcsóbban.
A program adja meg a megfelelő járatszámokat, illetve átszállásokat.
5) Minimális feszítőfa algoritmusok
Szeretnénk összehasonlítani a minimális feszítőfa előállító Kruskal, valamint a Prím algoritmust, utóbbinak két implementációját külön (azaz a rendezetlen tömböst és a kupacost is). Készíts programot, amely képes gráfokra alkalmazni a fenti algoritmusokat, és megadni a gráf minimális feszítőfáját, és annak előállításához szükséges műveletidőt (másodpercben).
A programban lehessen megadni egy inputfájlt, amely több gráf adatait is tárolja, akkor a program valamennyi gráfra lefuttatja a 3 algoritmust, és az eredményt egy kimeneti fájlba írja, megjelenítve algoritmusonként a szükséges műveleti időt. A gráf ábrázolása, és fájlban tárolása tetszőleges lehet.
6) Ütemezési diagram előállítása
Egy program rendszerint több modulból áll össze. Ezek a modulok függhetnek más moduloktól, tehát addig nem lehet elvégezni a fejlesztésüket, amíg a megelőző modulok (előfeltételek) nem készültek el. Adott egy bemeneti fájl, aminek sorai a következő formátumban vannak: programmodul azonosító, programodul név, fejlesztési időtartam, előfeltételek (ha vannak).
Készíts programot, amely grafikus felületen elkészíti egy program ütemezési diagramját, azaz egy olyan diagramot, ahol a programmodulok nevei szerepelnek, illetve a függőségek gráfszerűen ábrázolva. A program ezen felül adja meg a teljes program elkészülésének minimális idejét az előfeltételek hálózata alapján, továbbá legyen képes hibákat detektálni az ütemezésben, azaz ha például körkörös előfeltétel megadás van a bemenetben. |
