Note de curs, clasele 9-10, 24 octombrie 2013
From Algopedia
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