Note de curs, clasele 9-10, 24 octombrie 2013

From Algopedia
Revision as of 09:51, 25 October 2013 by Cata (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Verificarea temei

Am discutat soluțiile pentru câteva din temele de analiză amortizată.

The Master Theorem

Am urmărit notele de săptămâna trecută de la clasele 11-12, predate la viteză mai mică.

Simulare

  • Conceptul general: Construim un model al sistemului. Modelul are o stare, care se tot modifică. Descriem starea prin variabile.
  • Există un tact, un increment, un ceas al sistemului. El nu trebuie stocat explicit.
  • Soluțiile naive pentru problemele de simulare avansează tact cu tact și recalculează starea sistemului.
  • Uneori, se pot face accelerări prin care să sărim multe tacturi deodată. La olimpiadă aceasta este cheia problemelor de simulare

Problemă introductivă: să se calculeze diferența, exprimată în zile, dintre două date calendaristice.

  • metoda naivă: avansez zi cu zi, incrementând luna și anul când este nevoie
  • acelerare: număr zilele din anii intermediari și avansez zi cu zi doar în anii de început și de sfârșit
  • soluția optimă: convertesc ambele date la numărul de zile trecute de la 1/1/0, apoi fac 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:

  • joc16 și tetris de la campion (naive, nu necesită accelerare)
  • clepsidru (OJI 2013), roata (OJI 2012), vase (OJI 2011), toate clasa a 9-a. Toate necesită accelerare.
  • vecini de la infoarena (covorul lui sierpinski) -- nu e chiar de simulare
  • swap de la infoarena (seamănă cu Handshakes de la Șumen 2009 juniori)
  • penal de la infoarena