Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

--- teme:tema2 [2017/02/15 00:16]
florina_elena.barbu
+++ teme:tema2 [2017/04/09 13:59]
mihai.iacov [Precizări]
@@ Linia 1: / Linia 1: @@
 ====== Tema 2: GPS tracker ======
-<html>
-<h2 id="obiective_laborator" class="sectioedit2">Obiective </h2>
+===== Obiective =====
-<div class="level2">
-  <ul>
-    <li class="level1"><div class="li">Înțelegerea conceptului de graf și a modurilor de parcurgere aferente </div></li>
-    <li class="level1"><div class="li">Aplicarea algoritmilor studiați pe topologie graf într-un exemplu practic </div></li>
-  </ul>
-</div>
-<h2>Descriere </h2>
+    * Înțelegerea conceptului de graf și a modurilor de parcurgere aferente
-<div class="level2">
+    * Aplicarea algoritmilor studiați pe topologie graf într-un exemplu practic
-  <p>
-     Sistemul Global de Poziționare (sau GPS) este o rețea de aproximativ 30 de sateliți care orbitează în jurul Pământului, la o altitudine de 20.000km. </br>
-     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.
+===== Descriere =====
-  </p>
-  <p>
+Sistemul Global de Poziționare (sau GPS) este o rețea de aproximativ 30 de sateliți care orbitează în jurul Pământului, la o altitudine de 20.000km.
-     Oriunde te afli pe planetă, cel puțin 3 sateliți sunt 'vizibili' la un moment dat. Fiecare transmite informații despre poziția sa și timpul curent la anumite intervale. Aceste semnale sunt interceptate de dispozitivul GPS care calculează cât de departe e satelitul, în funcție de cât de mult îi ia mesajului să ajungă.
+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.
-  </p>
-  <p>
+Oriunde te afli pe planetă, cel puțin 3 sateliți sunt 'vizibili' la un moment dat. Fiecare transmite informații despre poziția sa și timpul curent la anumite intervale. Aceste semnale sunt interceptate de dispozitivul GPS care calculează cât de departe e satelitul, în funcție de cât de mult îi ia mesajului să ajungă.
-     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 <b> trilaterație </b>.
-  </p>
+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** .
-  <p> <h3> Trilaterația (măsurarea distanțelor, nu a unghiurilor)</h3>
-  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. </br></br>
-  Asta este ceea ce receiver-ul GPS-ul tău face, deși acesta consideră sfere suprapuse (pentru simplificare, proiectăm sferele în plan, și vom obține cercurile de <b>centru C(x,y)</b> și <b>rază R</b>)</br>
+=== Trilaterația (măsurarea distanțelor, nu a unghiurilor) ===
+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.
+  <html>
   <img src="/sda-ab/wiki/_media/teme/gps-real-world.jpg" class="medialeft" alt="">
   <img src="/sda-ab/wiki/_media/teme/gps.jpg" class="mediacenter" alt="">
+  </html>
+===== Precizări =====
+Vom considera ca fișier de intrare //coordonate.in//, în care pe prima linie vom avea un număr N care va reprezenta câte locații depistează sateliții noștri. \\
+Pe următoarele linii vom avea pentru fiecare locație:
+   *  nume locație
+  *   coordonate (x1, y1) satelit1
+  *   raza R satelit1
+  *   coordonate (x2, y2) satelit2
+  *   raza R satelit2
+  *   coordonate (x3, y3) satelit3
+  *   raza R satelit3
-  </p>
+ \\
-</div>
+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, obținându-le prin găsirea triadelor (x,y,z) care să satisfacă ecuațiile sferei.
-<h2>Precizări</h2>
-<p>
-  Vom considera ca fișier de intrare <i> coordonate.in </i>, în care pe prima linie vom avea un număr N care va reprezenta câte locații depistează sateliții noștri. </p>
-<p>
-  Pe următoarele linii vom avea:
-  <ul>
-  <li> nume locație </li>
-  <li> coordonate (x, y) satelit1</li>
-  <li> raza R satelit1</li>
-  <li> coordonate (x, y) satelit2</li>
-  <li> raza R satelit2</li>
-  <li> coordonate (x, y) satelit3</li>
-  <li> raza R satelit3</li>
-  </ul>
-  Coordonatele și raza se consideră date de fiecare satelit pentru fiecare dintre cele N locații. </br>
-  Având aceste 3 seturi de coordonate, trebuie să aflați coordonata (xi, yi) a locației respective. Se consideră prima coordonată calculată, locul din care plecăm.</p>
-<p>
-  Știind coordonatele tuturor locațiilor, vom considera costul de la o locație la cealaltă distanța dintre cele 2 puncte în plan. </p>
-<p>
-  Vom primi un update printr-un fișier <i>avarii.in</i> drumurile avariate dintre 2 locații, pe care nu se poate merge.
-</p>
-<h2>Cerințe</h2>
+<note important>
-<p>
+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ă) \\ \\
-   Executabilul obținum în urma compilării va avea numele <i> gps</i>, iar regula de execuție va fi: </br>
+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; fiecare locație va fi considerată ca fiind un nod al grafului prin care ne construim drumurile de la o locație la alta.
-</html>
+</note>
-   <file cpp>
-   ./gps coordonate.in avarii.in nume_destinatie
-   </file>
-<html>
-   unde numele destinației reprezintă locația unde vrem să ajungem. </br>
-   Având toate aceste date, vrem să calculăm care este cel mai scurt drum de la nodul de plecare, la cel destinație.
-</p>
-<h2>Reguli pentru trimitere </h2>
+<note tip>
-<div class="level2">
+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:
-  <ol>
-    <li class="level1"><div class="li"> Arhiva temei va avea numele <i> GrupaSerie_Nume_Prenume_TemaNr.zip </i> și va fi încărcată pe <a href = "https://vmchecker.cs.pub.ro/ui/"> vmchecker </a> unde vă puteți loga folosind credențialele de pe acs.curs </div></li>
-    <li class="level1"><div class="li"> Ea va conține fișierul main.c, Makefile-ul (cu regulile make și clean) și fișierul README în care va fi descrisă soluția problemei</div></li>
-    <li class="level1"><div class="li"> Dacă veți calcula coordonatele spațiale pentru toate locațiile, se poate obține punctaj parțial de <b>50p</b></div></li>
-    <li class="level1"><div class="li"> Dacă soluția voastră nu compilează, dar dacă ideea este bună și trimiteți o încercare de implementare, puteți primi până la <b>20p</b></div></li>
-    <li class="level1"><div class="li"> Temele care vor fi copiate vor primi <b>0p</b></div></li>
-  </ol>
-</div>
+**(x-x1)<sup>2</sup> + (y-y1)<sup>2</sup> = R1<sup>2</sup>**
-<h2>Referințe </h2>
+**(x-x2)<sup>2</sup> + (y-y2)<sup>2</sup> = R2<sup>2</sup>**
-<div class="level2">
-<ul>
+**(x-x3)<sup>2</sup> + (y-y2)<sup>2</sup> = R3<sup>2</sup>**
+</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)<sup>2</sup> + (y1-y2)<sup>2</sup> )**
+</note>
+Vom primi un update printr-un fișier //avarii.in// drumurile avariate dintre 2 locații, pe care **nu** se poate merge.
+===== Cerințe =====
+Executabilul obținut în urma compilării va avea numele **//gps//**, iar regula de execuție va fi:
+<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 coord_finale.out se vor scrie numele și perechea (x,y) de coordonate calculate pentru fiecare locație, în ordinea citirii lor din fișierul de intrare coordonate.in
+Având toate aceste date, vrem să calculăm care este cel mai scurt drum de la nodul de plecare, la cel destinație, pe care îl vom scrie în fișierul //rezultat.out// .
+===== Exemplu (date fictive momentan, nu e test real!!)=====
+^ coordonate.in ^ avarii.in   ^ coord_finale.out ^ rezultat.out ^
+|5               |dalas denver |12 7              |12            |
+|dalas           |             |2 3               |              |
+|12 13 2         |             |1 3               |              |
+|10  9 3         |             |1 3               |              |
+|12  8 2         |             |1 3               |              |
+|denver          |             |                  |              |
+|2 7 4           |             |                  |              |
+|2 8 5           |             |                  |              |
+|4 6 4           |             |                  |              |
+|texas           |             |                  |              |
+|2 3 4           |             |                  |              |
+|2 3 4           |             |                  |              |
+|2 3 4           |             |                  |              |
+|maryland        |             |                  |              |
+|2 3 4           |             |                  |              |
+|2 3 4           |             |                  |              |
+|2 3 4           |             |                  |              |
+|ilinois         |             |                  |              |
+|2 3 4           |             |                  |              |
+|2 3 4           |             |                  |              |
+|2 3 4           |             |                  |              |
+===== Reguli pentru trimitere =====
+  -    Arhiva temei va avea numele //GrupaSerie_Nume_Prenume_TemaNr.zip// și va fi încărcată pe vmchecker, unde vă puteți loga folosind credențialele de pe acs.curs
+  -   Ea va conține (direct în rădăcină):
+    * fișierul main.c </br>
+    * 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ă, dar dacă ideea este bună și trimiteți o încercare de implementare, puteți primi până la **20p**
+  -   Temele care vor fi copiate vor primi **0p**
+===== Referințe =====
+<html>
  <li class="level1"><div class="li"><a class="urlextern" href = "http://www.physics.org/article-questions.asp?id=55">How does GPS work? </a></div></li>
  <li class="level1"><div class="li"><a class="urlextern" href = "http://gisgeography.com/trilateration-triangulation-gps/">Trilateration vs Triangulation </a></div></li>
-</ul>
-</div>
 </html>

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină