Clasele 9-10 lecția 19 - 18 feb 2015

From Algopedia
Jump to navigationJump to search

Probleme de simulare

Conceptul de simulare este definit un pic vag. Prin simulare încercăm să modelăm un sistem real. Modelul are o stare, descrisă prin variabile. Există un tact, un ceas al sistemului. Starea se schimbă cu fiecare tact.

Problemele de simulare cer, în general, starea sistemului la un timp final și, eventual, starea la alți timpi intermediari.

Problemele de simulare, în fapt, nu se rezolvă prin simulare (decât cel mult la gimnaziu). La liceu, soluțiile bazate pe simulare naivă, pas cu pas, iar puține puncte. Este necesar să căutăm metode de a accelera simularea, pentru a calcula starea sistemului sărind mulți pași deodată.

Diferența între două date calendaristice

Ca exemplu, să calculăm diferența între două date, exprimate prin tripleți (zi, lună, an).

  • metoda naivă: avansăm zi cu zi, incrementând luna și anul când este nevoie
  • acelerare: numărăm zilele din anii intermediari și avansăm zi cu zi doar în anii de început și de sfârșit
  • soluția optimă: convertim ambele date la numărul de zile trecute de la 1/1/0, apoi facem diferența între cele două numere
  • Este ok să ne referim la anul 0, care nu a existat? Este ok să ignor faptul că până la 1582 am folosit alt calendar, cu altă viteză?
    • da, câtă vreme ambele date ale problemei sunt din calendarul gregorian
    • două vorbe despre calendarul iulian (46 BC - 1582 AD); de ce se numesc lunile iulie și august astfel; cum calendarul iulian risca să ducă de râpă agricultura; cine mai ține astăzi calendarul iulian?

Probleme de simulare

Algoritmul lui Lee

Algoritmul lui Lee este folosit pentru a afla informații despre accesibilitate în matrice (atunci când matricele reprezintă o rețea dreptunghiulară de camere). El se înrudește cu algoritmul flood fill, dar calculează ceva în plus: distanțele minime de la punctul de pornire până la toate punctele vizitate.

Când vom discuta despre grafuri, vom vedea că matricea de camere este un tip particular de graf, în care fiecare nod are (cel mult) patru vecini, cei de la N, S, E și V. Algoritmul lui Lee decurge din parcurgerea în lățime a grafurilor (BFS). Aceasta înseamnă că elementele matricei sunt vizitate în ordinea crescătoare a distanței de la punctul de plecare. Spre deosebire de aceasta, algoritmul flood fill decurge din parcurgerea în adâncime a grafurilor (DFS), care explorează nodurile imediat ce le descoperă.

Dat fiind că graful nostru are o structură particulară, nu avem nevoie să-l reprezentăm ca pe un graf, iar algoritmul se simplifică considerabil.

Nu vom face aici demonstrația de corectitudine a distanțelor calculate de algoritmul lui Lee. Când vom vorbi despre grafuri, unul dintre primele subcapitole va fi parcurgerea în lățime, care va include și demonstrația de corectitudine.

Implementarea se face cu o coadă. Anexez o sursă pentru problema Muzeu.

Cât de lungă trebuie să fie coada ca să nu se umple? Discuție.

Aplicații

Algoritmul lui Lee este necesar când dorim să aflăm informații despre drumuri și distanțe:

  • Găsirea ieșirii dintr-un labirint / castel / hartă.
  • Găsirea celui mai scurt drum între două puncte dintr-o matrice.
  • În lumea reală, proiectarea de circuite electronice

Probleme

Observați o predilecție la o anumită clasă? :-)

Temă

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasele_9-10_lecția_19_-_18_feb_2015&oldid=11577"