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

Verificarea temei

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

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

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