Olimpiada de la Kurchatov în Informatică 2018

Termeni de participare și date.

Notă importantă. Nu este necesar să faceți ambele programe. Dacă ați făcut doar una, sau chiar jumătate din program - trimiteți-ne-o, ne vom da seama.

Tur de-a lungul timpului și recompensarea câștigătorilor.

Câștigătorii și laureații vor primi premii valoroase și diplome frumoase.

Sarcina 1. Cadrul HDLC.

Pentru a transmite date prin canale de comunicații sincrone, este adesea folosită o structură de pachete transmise, numită HDLC. Fluxul de cadre este un bitstream, deoarece datele transmise sunt interpretate la nivelul fiecărui bit.

Suntem de acord cu următorii termeni: datele sunt informații destinate transmisiei între două puncte și împărțite în blocuri logice, a căror dimensiune este mai mare de opt biți; cadru - totalitatea blocului de date și suma de control a acestuia; pachet - cadrul peste care a fost efectuată operația de umplere.

• Datele sunt transmise în blocuri care sunt multiplii de opt biți, adică Dimensiunea în octeți a blocului de date este un număr întreg.
• Cea mai mică (cea mai dreaptă în notație binară) a unui octet individual este în flux primul, cel mai vechi (cel mai stâng) este ultimul.
• Pachetele sunt separate una de alta printr-o secvență de 8 biți 0111 1110 (0x7E). Aceeași secvență este transmisă în absența datelor utile pentru transmitere.
• Deoarece secvența 0111 1110 poate să apară în fluxul de date în sine, o operație numită umplutură este efectuată în timpul formării pachetului: după transmiterea a cinci biți unici într-un rând, un bit zero este adăugat la flux. Astfel, datorită procedurii de umplutură, mărimea pachetului transmis poate deveni un multiplu de opt biți.
• Receptorul efectuează o operație inversă - destuffing: bitul zero, care merge după cinci singure, este ignorat. Datorită acestor două operații, octetul 0x7E nu poate să apară în pachetul transmis.
• Pentru integritatea datelor, și anume detectarea de pachete transmise corect, se adaugă datele la control CRC16-CCITT, polinoamele de generator, dar cu unele modificări, care vor fi discutate mai jos.

Emițătorul mai întâi calculează suma de control a fluxului de date, apoi este atașat fluxului de date. Ca rezultat, se formează un cadru din blocul de date. Deasupra cadrului, are loc o operație de umplere: cadrul se transformă într-un pachet. În linie, pachetele sunt separate unul de celălalt cu unul sau mai mulți octeți de 0x7E.

Receptorul împarte fluxul de biți din linie în pachete, efectuează o operațiune de destaționare, primind cadre. Apoi divide cadrul într-un bloc de date și suma de control transmisă, calculează suma de control a blocului de date și compară cele două sume de control.

Fluxul de date este tratat ca un polinom: dacă un bit este zero, atunci coeficientul înainte de puterea corespunzătoare din polinom este 0, dacă bitul este unul, atunci coeficientul este unul. De exemplu, un flux de 17 biți de 10001000000100001 este echivalent cu un polinom generator. CRC, codul de redundanță ciclică se bazează pe găsirea restului de împărțire a polinomului de date într-un polinom generator. Restul este un polinom, care, văzută ca o secvență de biți, este o sumă de control. Divizarea polinomilor are loc modulo doi, adică operația de scădere obișnuită este înlocuită de o scădere binară (sau adăugare - este aceeași) fără transfer sau împrumut.

• Datele transmise sunt scrise în ordinea transmisiei lor pe linie: primul bit din stânga, ultimul din dreapta. La această secvență, adăugăm 16 zerouri în dreapta, ceea ce echivalează cu înmulțirea polinomului corespunzător prin și împărțirea polinomului rezultat în generatorul. Avem primul rest al diviziei.
• Scriem 16 unități și adăugăm la dreapta câte zerouri ca bitul ocupă datele transmise. Împărțim acest lucru într-un polinom generator, obținând al doilea rest.
• Se adaugă modulo 2 reziduuri și numărul 0xFFFF. Rezultatul este suma de control a pachetului, este nevoie de 16 biți și este atașat la sfârșitul pachetului transmis.

Să presupunem că vrem să transferăm un bloc de date constând dintr-un octet 0x30 (acesta este codul ASCII al simbolului 0). În bit ca un pachet se pare ca 0000 1100. Să se calculeze suma de control: Umple 16 zerouri - 0000 1100 0000 0000 0000 0000 și se împarte la polinomul generator de:

Restul de divizare este de 1100 0001 1000 1100. Acum, ia 16 unități și 8 zerouri (lungime de date) - 1111 1111 1111 1111 0000 0000. Al doilea rest este 1110 0001 1111 0000. Rezultatul modulo doi și numărul de resturi egale 0xFFFF 1101 1111 1000 0011 Aceasta este suma de control, care este egală cu 0xC1FB, dacă revenim la ordinul obișnuit de biți.

Având în vedere suma de control, cadrul se obține după cum urmează: 0x30, 0xFB, 0xC1. Sau în formă binară (primul bit transmis stânga): 0000 1100 11011111 1000 0,011 secvență Bold din cele cinci unul-biți, la care se adaugă după umplutura de zero biți. În consecință, pachetul este după cum urmează: 0000 1100 1101 1111 0100 0001 1. bitstream complet decorat va fi după cum urmează: 0111 1110 0000 1100 1101 1111 0100 0001 1011 1111 0. Acest exemplu, încă o dată arată că dimensiunea datelor transmise nu este un multiplu de un octet.

Este necesar să scrieți trei programe: cadrul, deframerul și emulatorul liniei fizice. Cadrul transformă fluxul de date pe care îl transmite dintr-un fișier într-un flux HDLC stocat într-un alt fișier. Lungimea blocurilor de date la care este împărțită fluxul sursă este specificată din linia de comandă prin doi parametri: dimensiunea maximă și minimă a blocului. În acest caz, dimensiunea unui anumit bloc trebuie să fie o variabilă aleatoare care se află în intervalul specificat. Pachetele ar trebui separate de un număr arbitrar de octeți de delimitare.

Deframer primește un bitstream constând din pachete HDLC și îl convertește în pachete de date. Bit stream este citit dintr-un fișier; datele sunt scrise într-un alt fișier. Fluxul de biți nu începe neapărat cu secvența 0111 1110 - trebuie găsită încă (sincronizată cu firul); Este posibil să existe un număr arbitrar de pachete în flux; nu se fac ipoteze despre lungimea fiecărui pachet. Este necesar să se aloce din flux fiecare pachet, să se calculeze suma de control, să se compare cu pachetul transmis. Dacă suma este corectă și dimensiunea pachetului este mai mare de un octet, atunci conținutul pachetului este adăugat la fișierul de ieșire. dacă suma este incorectă sau dimensiunea pachetului nu este un multiplu de octet, atunci vom imprima mesajul de eroare și conținutul pachetului greșit. Apoi continuăm să procesăm următorul pachet.

Emulatorul linie fizică citirea dintr-un fișier HDLC flux cu o anumită probabilitate inversează biți flux arbitrar (simula interferența în liniile de transmisie), și scrie fluxul rezultat în fișierul de ieșire. Emulatorul distruge biți selectați aleatoriu; procentul de biți inversați este un număr real situat pe [0; 100] și este specificat de parametrul liniei de comandă a emulatorului.

Notă: în linii reale, procentul de biți inversați, la care sincronizarea este încă posibilă, este o valoare de ordinul unui procent. Prin urmare, nu vă așteptați ca, cu un procent mai mare de erori în linie, să vă puteți sincroniza cu fluxul și să restaurați datele. Totuși, acest lucru nu înseamnă că emulatorul va transmite întotdeauna numere mai mici decât unul.

Sarcina 2. Generatorul de puzzle-uri de cuvinte încrucișate japoneze.

Există multe tipuri diferite de cuvinte încrucișate: obișnuite, finlandeze, japoneze etc. Spre deosebire de puzzle-urile cu cuvinte încrucișate convenționale, unde doriți să ghiciți cuvinte, o imagine este criptată în puzzle-ul încrucișat japonez. Sunteți invitat să implementați un program care se bazează pe faimoasa imagine a puzzle-ului încrucișat japonez.

Cuvântul încrucișat este o zonă dreptunghiulară formată din pătrate (celule), care pot fi vopsite în culori diferite. În partea de sus a fiecărei coloane și în partea stângă a fiecărui rând există mai multe numere în ordine. Este posibil ca aceste numere să fie vopsite în culori diferite, atunci cuvântul încrucișat se numește colorat. Dacă culoarea numerelor este una, atunci cuvântul încrucișat este alb-negru. Numerele în sine sunt lungimile blocurilor orizontale (pentru numerele din stânga liniei) și verticale (pentru numerele din partea de sus a coloanei) blocuri de pătrate vopsite în culoarea corespunzătoare. Printre toate culorile prezente în cuvântul încrucișat, se numește culoarea de fundal; blocuri verticale sau orizontale de această culoare nu sunt luate în considerare la compilarea unei cuvinte încrucișate. Esența cuvintelor încrucișate este de a ghici unde sunt blocurile de culoarea de fundal și care este mărimea lor.

Pentru un cuvânt încrucișat alb-negru, există întotdeauna un bloc de culoare de fundal între blocurile negre. Pentru puzzle-uri de culoare încrucișată, nu există o astfel de restricție. Cu toate acestea, trebuie să existe întotdeauna un bloc de altă culoare între blocurile de aceeași culoare (probabil culoarea de fundal). Blocuri de culori diferite se pot alatura unul de celălalt îndeaproape.

Numerele din rânduri și coloane nu trebuie să se contrazică reciproc, adică imaginea trebuie restaurată din aceste numere într-un fel.

Trebuie să scrieți un program, care este alimentat la imaginea de intrare în format BMP. Imaginea poate fi alb-negru sau 16 culori. Programul dvs. ar trebui să se bazeze pe această imagine cu o cruce japoneză de rezolvare, dacă este posibilă construirea acesteia într-o manieră consecventă. Dacă imaginea are două culori, atunci culoarea de fundal este albă, iar numerele sunt vopsite în negru. Dacă imaginea are 16 culori, programul ar trebui să poată alege culoarea de fundal.

În cazul în care este imposibil să se construiască un cuvânt încrucișat coerent, solvabil, programul ar trebui să informeze utilizatorul despre el. Dacă este construită cuvântul încrucișat, atunci trebuie să fie vizualizată.

Încă o dată, atragem atenția: cuvântul încrucișat trebuie rezolvat.