Structuri de Date și Algoritmi (seria 1AB)

Această pagină poate fi doar citită. Poți vedea sursa, dar nu poți modifica pagina. Consultă administratorul dacă ești de părere că ceva este în neregulă.
======Tema 2: The Network======
==== Obiective ====
  * Înțelegerea conceptului de graf și a modurilor de parcurgere aferente
  * Aplicarea algoritmilor studiați pe topologie graf într-un exemplu practic
  * Înțelegerea unor anumite concepte din reţelistică.

==== Informaţii ====
  - Deadline hard, **06 mai ora 23:59** (termen limită - **nu se obţin puncte** pe soluţiile trimise mai târziu)
  - Trimiterea temelor se face pe platforma [[https://vmchecker.cs.pub.ro/|vmchecker]] (folosiți numele de utilizator şi parola de pe http://acs.curs.pub.ro).
  - Checker-ul offline poate fi descărcat de la această [[https://drive.google.com/open?id=1xOL5eymB_rQbzF_LpJVwG1e-2zYlMUjQ|adresă]] 
  - Puteţi cere ajutor oricând la această adresă [[sda-ab-tema2@googlegroups.com|email]]

==== Modificări temă====
  - 30/04/2018 19:40
     * corectură enunţ - cerinţe - comanda add primeşte şi distanţa pentru legătură, nu doar ip-urile;
  - 02/05/2018 00:20
     * menţiuni suplimentare - format date ieşire - ordinea în care sunt verificate ip-urile;



==== Descriere ====
Flavius e un student pasionat al Facultăţii de Automatică. Cea mai mare pasiune a sa a fost mereu reţelistica, astfel el a urmat modulele de la CISCO.
La CISCO, el a învăţat despre OSPF ( Open Shortest Path First ), un protocol care l-a captivat pe Flavius.
Aflând că la baza ideii de OSPF se află algoritmul lui Dijkstra, algoritm pe care îl va studia la cursul de SDA, i-a venit o idee.
El s-a gândit să simuleze o reţea ce are la bază protocolul OSPF, pentru a aprofuda algoritmul lui Dijkstra (pentru cursul de SDA şi, mai ales, pentru el).
{{ :teme2018:sdaimage.png?nolink |}}
Din păcate, săracul Flavius, student silitor, are o problemă.
Flavius nu s-a înţeles foarte bine cu programarea şi nici acum nu e foarte priceput, aşa că s-a gândit să vă ceară ajutor cu codul sursă.

==== Date de intrare ====

Fişierul cu date de intrare va conţine următoarele date:\\
  - numărul de routere;
  - pentru fiecare router, fiecare atribut pe câte un rând:
    * nume router;
    * IP router;
    * numărul de pc-uri care se conectează la router;
  - pentru fiecare pc care se conectează la router-ul curent, fiecare atribut pe câte un rând:
    * nume pc;
    * IP pc;
    * stare (0 pentru închis, 1 pentru deschis);
  - numărul de conexiuni între routere
  - fiecare conexiune este descrisă pe câte un rând de următoarele, separate print-un spaţiu:
    * numele router-ului de la un capăt;
    * numele router-ului de la celelalt capăt;
    * "distanţa" (număr întreg) dintre router-e;
  - numărul de operaţii cerute;
  - fiecare operaţie descrisă pe câte un rând.

==== Cerinţe ====

Ordinea în care sunt scrise operaţiile în fişierul de intrare este ordinea în care vor fi aplicate. Pentru toate operaţiile, pc-urile sau router-ele sunt identificate prin IP.

Operațiile posibile asupra datelor din fișier vor fi:
  * **ping x.x.x.x x.x.x.x :** spune dacă este conexiune între două staţii (ţine cont de conexiunile dintre toate router-ele şi de stările capetelor);
  * **sipn x.x.x.x :** afişează routerele cu care ai legatură directă;
  * **si x.x.x.x :** afişează ce PC-uri sunt conectate (au starea = 1) direct la router;
  * **trace x.x.x.x x.x.x.x :** afişează traseul de la echipament la echipament (ip-urile routerelor ce formează "drumul cel mai scurt")
  * **up x.x.x.x :** dechide un PC;
  * **lc x.x.x.x x.x.x.x :** distruge legătura dintre 2 routere;
  * **broke x.x.x.x :** închide un PC;
  * **add x.x.x.x x.x.x.x d:** adaugă o legătură între 2 routere, cu "distanţa" d;

==== Date de ieşire ====

Fişierul de ieşire va conţine rezultatele operaţiilor ce generează un răspuns. Rezultatele sunt scrise în ordinea în care sunt scrise operaţiile primite la intrare, fiecare rezultat este urmat de un final de linie.

  - **ping** scrie unul din răspunsurile "OK" sau "NO";
  - **trace**, **si** şi **sipn** scriu ca răspuns o listă de IP-uri, separate între ele printr-un spaţiu.

<note>În cazul în care există **mai multe soluţii teoretic corecte**, comenzile verifică IP-urile vecinilor sau PC-urilor în **ordinea în care apar în fişierul de intrare**, în zona în care sunt definite routerele şi pc-urile (spre exemplu, dacă routerul R1 are vecinii R2 şi R3, iar R2 este definit înaintea lui R3 în fişierul de intrare, atunci R2 va fi verificat primul când sunt exploraţi vecinii lui R1).
</note>

==== Exemplu ====
Flavius s-a simţit cam vinovat pentru sarcinile pe care vi le-a dat, aşa că s-a gândit să vă dea un exemplu:


<file date.in date.in>
6
Router1
192.0.1.1
1
pc1
192.0.1.2
1
Router2
192.0.2.1
1
pc1
192.0.2.2
1
Router3
192.0.3.1
1
pc1
192.0.3.2
1
Router4
192.0.4.1
1
pc1
192.0.4.2
0
Router5
192.0.5.1
1
pc1
192.0.5.2
1
Router6
192.0.6.1
1
pc1
192.0.6.2
1
8
Router1 Router2 10
Router1 Router3 1
Router3 Router4 5
Router3 Router5 1
Router4 Router2 3
Router4 Router6 1
Router5 Router4 1
Router6 Router2 1
14
ping 192.0.1.2 192.0.4.2
sipn 192.0.4.1
si 192.0.2.1
trace 192.0.1.2 192.0.2.2
up 192.0.4.2
ping 192.0.1.2 192.0.4.2
lc 192.0.3.1 192.0.5.1
trace 192.0.1.2 192.0.2.2
broke 192.0.2.2
add 192.0.3.1 192.0.5.1 10
trace 192.0.1.2 192.0.2.2
up 192.0.2.2
add 192.0.2.1 192.0.4.1 1
trace 192.0.1.2 192.0.2.2
</file>

<file date.out date.out>
NO
192.0.2.1 192.0.3.1 192.0.5.1 192.0.6.1
192.0.2.2
192.0.1.1 192.0.3.1 192.0.5.1 192.0.4.1 192.0.6.1 192.0.2.1 
OK
192.0.1.1 192.0.3.1 192.0.4.1 192.0.6.1 192.0.2.1 

192.0.1.1 192.0.3.1 192.0.4.1 192.0.2.1 

</file>

<note tip>Fişierul executabil va fi rulat cu o comandă de forma:\\
**./main date.in date.out**
</note>




====Reguli pentru trimitere====

*puteţi încărca mai multe soluţii, se va lua în considerare soluţia cu cel mai mare punctaj trimisă până la termenul limită (**6 mai, ora 23:59**)
*Arhiva temei va avea numele //GrupaSerie_Nume_Prenume_TemaNr.zip// și va fi încărcată pe [[https://vmchecker.cs.pub.ro/ui/|vmchecker]], folosind datele de autentificare de pe http://acs.curs.pub.ro/
*Arhiva trimisă conține (direct în rădăcină):
  - fișierele sursă
  - Makefile-ul (cu regulile **make build** și **make clean**). Executabilul generat trebuie să se numească **main**
  - fișierul README în care va fi descrisă soluția problemei



=== Restricții: ===
*Implementarea pentru comanda **trace** se va face pe baza algoritmului lui Dijkstra.
*Nu se acceptă implementări cu memorie alocată static pentru tipurile de date folosite (se acceptă numai variabile locale ce ocupă spaţiu O(1) sau de tip buffer pentru stocare temporară înainte de alocare).
*Menţineţi cel puţin un nivel minimal de aspect al codului şi evitaţi inconsistenţa (indentare haotică, numeroase combinaţii de caractere de tip "leading/trailing whitespace", numirea variabilelor şi a funcţiilor în ordinea literelor din alfabet).
*Se va depuncta lucrul nemodularizat (fără funcţii) până la **50 pct** (din 100) (pentru tot codul scris în main).
*Memoria trebuie eliberată. Dacă nu se respectă această cerință, depunctarea este de pana la **5 pct** (din 100) (pentru mai mult de O(1) memorie alocată fără eliberare).
*Dacă soluția voastră nu compilează, dar ideea este bună și trimiteți o încercare de implementare, puteți primi până la **20 pct** (din 100).
*Temele care vor fi copiate vor primi **0 pct**. Studenţii implicaţi vor figura pe blacklist-ul cursului de SDA.
Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Unelte pagină
