Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare | ||
teme:tema2 [2017/02/15 20:56] florina_elena.barbu |
teme:tema2 [2017/04/26 18:04] (curent) iulian.matesica |
||
---|---|---|---|
Linia 2: | Linia 2: | ||
- | ==== Obiective ==== | + | ===== Obiective |
* Înțelegerea conceptului de graf și a modurilor de parcurgere aferente | * Înțelegerea conceptului de graf și a modurilor de parcurgere aferente | ||
* Aplicarea algoritmilor studiați pe topologie graf într-un exemplu practic | * Aplicarea algoritmilor studiați pe topologie graf într-un exemplu practic | ||
+ | ===== Informații ===== | ||
+ | * Deadline soft, **26 aprilie ora 23:59** | ||
+ | * Termen final de trimitere **4 mai ora 23:59** (depunctare de 0.5pt/zi, maxim 4p depunctare). | ||
+ | * Trimiterea temelor se face pe platforma [[https:// | ||
- | ==== Descriere ==== | ||
- | Sistemul Global de Poziționare (sau GPS) este o rețea de aproximativ 30 de sateliți care orbitează în jurul Pământului, | + | |
- | | + | ===== Descriere ===== |
- | \\ | + | |
- | | + | Sistemul Global de Poziționare (sau GPS) este o rețea de aproximativ 30 de sateliți care orbitează în jurul Pământului, |
+ | Acesta a fost dezvoltat de guvernul Statelor Unite în scop militar, dar oricine folosește acum un dispozitiv GPS poate recepționa semnalele radio pe care sateliții le fac broadcast. | ||
| | ||
- | Odată ce acesta are informații despre cât de departe cei trei sateliți sunt, receiver-ul GPS poate indica locația folosind | + | Oriunde te afli pe planetă, cel puțin 3 sateliți sunt ' |
- | \\ | + | |
- | === Trilaterația (măsurarea distanțelor, | + | |
- | Imaginează-ți că stai undeva pe Pământ cu 3 sateliți deasupra ta. Dacă știi cât de departe ești de satelitul | + | |
- | Asta este ceea ce receiver-ul GPS-ul tău face, deși acesta consideră sfere suprapuse. | + | |
| | ||
+ | Odată ce acesta are informații despre cât de departe cei trei sateliți sunt, receiver-ul GPS poate indica locația folosind un proces numit **trilaterație** . | ||
+ | | ||
+ | === Trilaterația (măsurarea distanțelor, | ||
+ | Imaginează-ți că stai undeva pe Pământ cu 3 sateliți deasupra ta. Dacă știi cât de departe ești de satelitul A, atunci trebuie să te afli undeva în cercul roșu. Dacă consideri la fel pentru sateliții B și C, poți afla locația ta precisă calculând intersecția celor 3 cercuri. | ||
+ | Asta este ceea ce receiver-ul GPS-ul tău face, deși acesta consideră sfere suprapuse. | ||
+ | |||
+ | < | ||
<img src="/ | <img src="/ | ||
<img src="/ | <img src="/ | ||
- | + | </ | |
- | ==== Precizări ==== | + | ===== Precizări |
- | <p> | + | |
- | Vom considera ca fișier de intrare | + | Vom considera ca fișier de intrare |
- | < | + | |
- | Pe următoarele linii vom avea pentru fiecare locație: | + | Pe următoarele linii vom avea pentru fiecare locație: |
- | | + | * nume locație |
- | < | + | |
- | | + | |
- | | + | |
- | | + | |
- | | + | |
- | | + | |
- | | + | |
- | </ | + | \\ |
- | + | Coordonatele și raza se consideră date de fiecare satelit pentru fiecare dintre cele N locații.\\ | |
- | Coordonatele și raza se consideră date de fiecare satelit pentru fiecare dintre cele N locații. | + | |
- | Datorită distanței mult mai mari de la Pământ la sateliți, față de diferența de înălțime între sateliți, ei se pot considera în același plan (z1 = z2 = z3 = z). Între cele 3 sfere există așadar cel mult 2 puncte de intersecție, | + | Datorită distanței mult mai mari de la Pământ la sateliți, față de diferența de înălțime între sateliți, ei se pot considera în același plan (z1 = z2 = z3 = z). Între cele 3 sfere există așadar cel mult 2 puncte de intersecție, |
- | </p> | + | |
<note important> | <note important> | ||
- | | + | Pentru simplificarea modelului problemei, considerăm doar proiecțiile sferelor, și presupunem că acestea se vor intersecta doar într-un singur punct (cara va reprenzenta locația propriu-zisă) |
- | < | + | Atenție: pentru a nu greși la calcule, se recomandă scrierea ecuațiilor celor 3 cercuri și aflarea coordonatelor unei locații prin calcularea punctului de intersecție; |
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | Dacă cei 3 sateliţi sunt reprezentaţi cu cercurile C1(x1, y1, R1), C2(x2, y2, R2) şi C3(x3, y3, R3), atunci punctul de intersecţie al celor 3 cercuri, P(x, y) va respecta ecuaţiile: | ||
+ | |||
+ | **(x-x1)< | ||
+ | |||
+ | **(x-x2)< | ||
+ | |||
+ | **(x-x3)< | ||
+ | </note> | ||
| | ||
- | < | + | Se consideră prima coordonată calculată, locul din care plecăm. |
- | < | + | |
- | < | + | |
- | < | + | Știind coordonatele tuturor locațiilor, vom considera costul de la o locație la cealaltă distanța dintre cele 2 puncte în plan. |
- | | + | <note tip> |
+ | Pentru punctele P1(x1, y1) şi P2(x2, y2) putem scrie ecuaţia distanţei: P1P2 = dist(P1,P2) = **sqrt( (x1-x2)< | ||
+ | </note> | ||
- | < | + | Vom primi un update printr-un fișier //avarii.in// drumurile avariate dintre 2 locații, pe care **nu** se poate merge. |
- | ./gps coordonate.in | + | |
- | </file> | + | |
- | + | ||
- | unde numele destinației reprezintă | + | |
- | | + | |
+ | ===== Cerințe ===== | ||
- | <h2>Reguli pentru trimitere | + | Executabilul obținut în urma compilării va avea numele **// |
+ | |||
+ | <note tip> | ||
+ | **./gps coordonate.in avarii.in nume_destinatie coord_finale.out rezultat.out ** | ||
+ | </note> | ||
+ | unde numele destinației reprezintă locația unde vrem să ajungem pornind din nodul pe care am zis că-l vom considera nod de plecare. | ||
- | < | + | În fișierul |
- | <li class=" | + | |
- | <li class=" | + | |
- | - fișierul | + | |
- | - Makefile-ul (cu regulile make pentru executabilul < | + | |
- | - fișierul README în care va fi descrisă soluția problemei</ | + | |
- | <li class=" | + | |
- | <li class=" | + | |
- | <li class=" | + | |
+ | Având toate aceste date, vrem să calculăm **costul** celui mai scurt drum de la nodul de plecare, la cel destinație, | ||
+ | ===== Exemplu (date fictive momentan, nu e test real!!)===== | ||
+ | ^ coordonate.in ^ | ||
+ | |8 |Loctie8 Locatie5 |19 17 | ||
+ | |Locatie1 | ||
+ | |Satelit0 51 41 40 |Loctie3 Locatie1 |0 6 | ||
+ | |Satelit1 54 5 37 | ||
+ | |Satelit2 376 93 365 | |13 10 | ||
+ | | | ||
+ | |Locatie2 | ||
+ | |Satelit0 158 65 148 | |18 15 | ||
+ | |Satelit1 51 561 545 | | ||
+ | |Satelit1 51 561 545 | | ||
+ | | | ||
+ | |Locatie3 | ||
+ | |Satelit0 289 6 289 | ||
+ | |Satelit1 264 176 314 | | ||
+ | |Satelit2 217 462 505 | | ||
+ | | | | ||
+ | |Locatie4 | ||
+ | |Satelit0 9 31 25 | ||
+ | |Satelit1 16 39 32 | | ||
+ | |Satelit2 208 263 320 | | ||
+ | | | ||
+ | |Locatie5 | ||
+ | |Satelit0 205 66 200 | | ||
+ | |Satelit1 76 26 65 | | ||
+ | |Satelit2 266 214 325 | | ||
+ | | | ||
+ | |Locatie6 | | ||
+ | |Satelit0 322 285 410| | ||
+ | |Satelit1 82 173 170| | ||
+ | |Satelit2 175 551 557| | ||
+ | | | ||
+ | |Locatie7| | ||
+ | |Satelit0 53 3 36| | ||
+ | |Satelit1 137 25 122| | ||
+ | |Satelit2 52 615 613| | ||
+ | | | ||
+ | |Locatie8| | ||
+ | |Satelit0 70 351 340| | ||
+ | |Satelit1 379 15 361| | ||
+ | |Satelit2 87 275 269| | ||
- | <h2> | + | ===== Reguli pentru trimitere ===== |
+ | |||
+ | - Arhiva temei va avea numele // | ||
+ | - Ea va conține (direct în rădăcină): | ||
+ | * fișierul main.c | ||
+ | * Makefile-ul (cu regulile make pentru executabilul **gps** și clean) | ||
+ | * fișierul README în care va fi descrisă soluția problemei | ||
+ | - Dacă veți calcula coordonatele spațiale pentru toate locațiile (adică fișierul de ieșire coord_finale.out e integral corect pentru un test), se poate obține punctaj parțial de **50p** | ||
+ | - Dacă soluția voastră nu compilează, | ||
+ | - | ||
+ | |||
+ | ===== Referințe | ||
+ | <html> | ||
< | < | ||
< | < | ||
+ | </ | ||