Kurchatov Olimpia Informatika 2018
A részvételi feltételek és a dátumok.
Fontos megjegyzés. Nem szükséges mindkét programot elvégezni. Ha csak egy, vagy akár a program fele készítettél - küldje el nekünk, akkor kitaláljuk.
Teljes körű turné és a nyertesek jutalmazása.
A győzteseket és a nyerteseket értékes nyereményekkel és gyönyörű oklevelekkel nyerik el.
1. feladat: HDLC-keret.
A szinkron kommunikációs csatornákon keresztüli adat továbbítására gyakran használnak továbbított csomagok HDLC-szerű struktúráját, amelyet kereteknek neveznek. A keretfolyam egy bitfolyam, mert a továbbított adatokat az egyes bitszinteken értelmezzük.
Egyetértünk a következő kifejezésekkel: az adatok két pont közötti átvitelre szánt információk, amelyek logikai blokkokba vannak osztva, amelyek mérete nyolc bit többszöröse; keret - az adatblokk teljes mérete és ellenőrző összege; csomag - az a keret, amely fölött a töltöttség végrehajtása történt.
A HDLC adatfolyam a következőképpen szerveződik:- Az adatokat olyan blokkokba továbbítjuk, amelyek nyolc bit többszörösek, azaz. Az adatblokk byte-ban megadott méret egy egész szám.
- Az egyéni bájt legalacsonyabb (a bináris jelölés leginkább megfelelő) bitje a patakban van, a legrégebbi (a leghátrányosabb) az utolsó.
- A csomagokat egymástól elválasztják egy 0111 1110 (0x7E) 8 bites szekvenciával. Ugyanaz a szekvencia továbbításra kerül, ha nincsenek hasznos adatok az átvitelhez.
- Mivel az adatfolyam megfeleljen szekvencia 0111 1110, a folyamat alkotó a csomag készül nevezett művelet töltelék (töltelék) kisugárzását követően az öt egymást követő egy bit a bitfolyamban hozzáadjuk nulla. Így, mivel a töltési eljárást transzfer mérete válhat maradék nélkül nem osztható nyolc bit.
- A vevő egy fordított műveletet hajt végre - a zsírosodás: a nulla bitet, ami öt egyszeri után történik, figyelmen kívül hagyják. E két művelet miatt a 0x7E bájt nem tud megjelenni a továbbított csomagban.
- Az adatok integritását, azaz a kimutatására továbbított csomagok helyesen, az adatokat hozzáadjuk az ellenőrző összeg CRC16-CCITT, generátor polinomot, de néhány módosítással, amelyet az alábbiakban tárgyaljuk.
A távadó először kiszámolja az adatfolyam ellenőrző összegét, majd az adatfolyamhoz csatolja. Ennek eredményeként létrejön egy keret az adatblokkból. A keret fölött egy töltési művelet zajlik le: a keret csomagká válik. A sorban a csomagok egy vagy több 0x7E bájtból vannak elválasztva egymástól.
A vevő elválasztja a vonalról a bitfolyamot csomagokká, végrehajt egy desta- tion műveletet, fogadja a kereteket. Ezután elosztja a kockát egy adatblokkba és a továbbított ellenőrzőösszegbe, kiszámítja az adatblokk ellenőrző összegét, és összehasonlítja a két ellenőrzőösszeget.
Az adatfolyamot polinomiaként kezeljük: ha egy bit nulla, akkor a polinomban a megfelelő teljesítmény előtt a koefficiens 0, ha a bit egy, akkor az együttható egy. Például egy 10001000000100001 17 bites áram egy generáló polinomnak felel meg. A CRC, a ciklikus redundancia kódexe azon alapul, hogy megtalálja az adatok polinomának egy generáló polinomiaként való megosztását. A fennmaradó rész egy polinom, mely egy bitszekvenciának tekintve ellenőrző összeg. A polinomok felosztása modulo 2, vagyis a megszokott kivonási műveletet bináris kivonással (vagy kiegészítéssel - mindegyik) helyettesítjük átadás vagy kölcsönvétel nélkül.
Az adatok ellenőrző összege a következőképpen alakul:- Az átvitt adatok a sorban a továbbítás sorrendjében vannak írva: az első bit a bal oldalon, az utolsó a jobb oldalon. Ehhez a sorozathoz hozzáadunk 16 nullát jobbra, ami egyenértékű a megfelelő polinom megszorzásával, és az eredményül kapott polinomot a generátorba osztja. Megszerzük az első részleget.
- 16 egységet írunk, és jobbra add meg a nullákat, amint a bit a továbbított adatokat elfoglalja. Ezt egy generáló polinómává választjuk, és megkapjuk a második maradékot.
- A modulo 2-t mind a szermaradványokat, mind a 0xFFFF számot adjuk hozzá. Az eredmény a csomag ellenőrzőösszege, 16 bitre van szükség, és hozzá van adva a továbbított csomag végéhez.
Tegyük fel, hogy szeretnénk továbbítani adatblokk álló bájt 0x30 (ez az ASCII karakteres kódot 0). A bit csomagként úgy néz ki, 0000 1100. Nézzük kiszámítja az ellenőrző összeget: Fill 16 nullát - 0000 1100 0000 0000 0000 0000 és osszuk el a generátor polinom:
A maradék a szétválás 1100 0001 1000 1100. Most hogy 16 egység és a 8 nullák (adat hossza) - 1111 1111 1111 1111 0000 0000. Második fennmaradó 1110 0001 1111 0000. Az eredmény a modulo két és a maradékok száma egyenlő 0xFFFF 1101 1111 1000 0011 . Ez egy ellenőrző azaz 0xC1FB, ha megy vissza a szokásos bitek sorrendje.
Beleértve az ellenőrző keret a következőképpen állítjuk elő: 0x30, 0xFB, 0xC1. Vagy bináris formában (az első átvitt bit bal): 0000 1100 11.011.111 1000 0011 Bold szekvenciáját az öt egy-bitek, amelyek után adjuk hozzá a töltelék nulla bitet. Következésképpen, a csomag a következő: 0000 1100 1101 1111 0100 0001 1. Teljesen berendezett bitfolyam az alábbiak lesznek: 0111 1110 0000 1100 1101 1111 0100 0001 1011 1111 0. Ez a példa ismét azt mutatja, hogy a méret a továbbított adatok nem többszöröse egy bájt.
Három programot kell írni: a keret, a deframer és a fizikai vonal emulátora. A keret átalakítja az adatfolyamot, amelyet bizonyos fájlokból egy másik fájlba tárolt HDLC adatfolyammá továbbít. Az adatblokkok hossza, amelyekre a forrásfolyamot megosztották, a parancssorból két paraméter határozza meg: a maximális és minimális blokkméretet. Ebben az esetben egy adott blokk méretének egy megadott tartományban lévő véletlenszerű változónak kell lennie. A csomagokat tetszőleges számú elhatároló bájtból kell elválasztani.
A deframer HDLC csomagokat tartalmazó bitfolyamot fogad, és adatcsomagokká alakítja. A bitfolyam egy fájlból olvasható; az adatok egy másik fájlba vannak írva. A bitfolyam nem feltétlenül kezdődik a 0111 1110 szekvenciával - még meg kell találni (a szálat szinkronizálva); Vannak tetszőleges számú csomag a patakban; nincs feltételezés az egyes csomagok hossza tekintetében. Minden egyes csomagból ki kell osztani a streamet, kiszámolnia kell az ellenőrző összeget, és összehasonlítani a továbbított csomaggal. Ha az összeg helyes, és a csomagméret egy byte többszöröse, akkor a csomag tartalma hozzáadódik a kimeneti fájlhoz. ha az összeg hibás vagy a csomag mérete nem egy byte többszöröse, akkor kinyomtatjuk a hibaüzenetet és a rossz csomag tartalmát. Ezután folytatjuk a következő csomag feldolgozását.
A fizikai vonalas emulátor egy fájlból HDLC-adatfolyamot olvasható ki, és némi valószínűséggel invertálja az arbitrális stream biteket (szimulálja az interferenciát az átviteli vonalakban), és a kimenő fájlt a kimeneti fájlba írja. Az emulátor véletlenszerűen kiválasztja a kiválasztott biteket; az inverz bitek százaléka valós szám [0; 100] -on, és az emulátor parancssori paramétere határozza meg.
Megjegyzés: valós sorokban az inverz bitek százalékos aránya, amelynél a szinkronizálás még lehetséges, egy százalékos érték. Ezért ne számíts rá, hogy a sorban szereplő hibák nagyobb hányadát szinkronizálhatja az adatfolyammal és visszaállíthatja az adatokat. Ez azonban nem jelenti azt, hogy az emulátor mindig kevesebb mint egy számot továbbít.
2. feladat: A japán keresztrejtvények generátorai.
A keresztrejtvények sokféle típusa létezik: hétköznapi, finn, japán, stb. A hagyományos keresztrejtvényekkel ellentétben, ahol szavakat akar találni, egy képet titkosítanak a japán keresztrejtvényben. Ön felkérést kap egy olyan program megvalósítására, amely a japán keresztrejtvény híres képére épül.
A keresztrejtvény maga négyszögletes terület, négyzetekből (cellákból), amelyek különböző színekkel festhetők. Az egyes oszlopok tetején és az egyes sorok bal oldalán több sorrend van. Lehetséges, hogy ezeket a számokat különböző színekben festették, majd a keresztrejtvény színűnek hívják. Ha a számok színe egy, akkor a keresztrejtvény fekete-fehér. Maguk a számok a vízszintes tömbök (a vonal bal oldalán lévő számok) és a függőleges (az oszlop tetején lévő számokhoz) négyzetek blokkjai, amelyek a megfelelő színűek. A keresztrejtvényben szereplő összes szín közül az egyik a háttérszín; e színű függőleges vagy vízszintes blokkokat nem veszi figyelembe keresztrejtvény összeállításakor. A keresztrejtvény lényege, hogy kitaláljuk, hol vannak a háttérszín blokkjai és milyen méretűek.
Fekete-fehér keresztrejtvény esetén mindig fekete háttérblokkok találhatók. A színes keresztrejtvényekhez nincs ilyen korlátozás. Azonban mindig egy másik színblokknak kell lennie az azonos színű blokkok (talán a háttérszín) között. A különböző színű blokkok szorosan összefonódhatnak egymással.
A sorokban és oszlopokban lévő számok nem mondhatnak ellent egymásnak, vagyis a képeket valamilyen módon vissza kell állítani ezekből a számokból.
Be kell írni egy programot, amelyet a bemeneti képhez BMP formátumban táplálunk. A kép fekete-fehér vagy 16 színű lehet. A programnak erre a képre ki kell építeni egy megoldható japán keresztrejtvényt, ha lehetséges, hogy következetes módon építsék fel. Ha a kép kétszínű, akkor a háttérszín fehér, a számok pedig fekete színnel vannak festve. Ha a kép 16 színnel rendelkezik, akkor a programnak képesnek kell lennie a háttérszín kiválasztására.
Abban az esetben, ha lehetetlen egy következetes megoldható keresztrejtvény létrehozása, a programnak tájékoztatnia kell a felhasználót. Ha a keresztrejtvény épül, akkor meg kell jeleníteni.
Ismét felhívjuk a figyelmet: a keresztrejtvényt meg kell oldani.