Matematyka , Fizyka pod OI

Question

Cześć,

Mam zamiar za rok wystartować w OI. Znam już podstawy algorytmiki, (OIJ) - wiem że głównie jest tam rozwiązywanie problemów strikte na pomysł / algorytm, ale wiem też że w niektórych zadaniach (sam się przekonałem robiąc zadania) przewija się bardziej skomplikowana matematyka/fizyka niż na OIJ.

Więc jakie tamaty z matematyki/fizyki polecalibyście przerobić? I jak znacie jakieś dobre źródła filmiki/książki/kursy itp.

Co umiem: (wiem że to są totalne podstawy. Ale pod OIJ wystarczają na wszystkie etapy, pomijam trywialne):

suma ciągu arytmetycznego, wzór na odległośc z tw Pitagorasa, tw Talesa, tw Pitagorasa, uciekanie przed sobą dwóch ciał - kiedy się dogonią(prędkośc,droga,czas itp), iloczyn wektorowy, iloczyn skalarny, układy równań liniowe, trójkąty podobne - ich własności, równania i nierówności kwadratowe. I pewnie jeszcze zapomniałem o czymś, ale w dużym skrócie tyle.

Ps. Chodzi mi głównie o materiały, żebym miał się z czego uczyć (Jestem świadomy, że nauka tego zajmie dużo czasu. I trzeba wszystko powoli od podstaw.)

Answer 1

Na OI to głównie potrzebna jest matematyka dyskretna, może też jakieś podstawy geometrii jak np. równania prostych przechodzących przez 2 punkty, kąt między prostymi.

Z matematyki dyskretnej na pewno ważne są takie tematy jak arytmetyka modularna, pierwszość i faktoryzacja liczb (w tym na pewno tw. Eulera i funkja Eulera), kombinatoryka i oczywiście cała teoria o grafach.

Ale nawet ważniejsza powiedziałbym jest znajomość algorytmów matematycznych. Czyli np. powinieneś wiedzieć jak zaimplementować roszerzony algorytm Euklidesa, szybkie potęgowanie, sprawdzanie pierwszości liczby, faktoryzacje liczby, liczenie funkcji Eulera, dwumianu newtona, liczenie pola figury, sprawdzanie czy odcinki się przecinają, sprawdzanie czy punkt jest wewnątrz figur i jeszcze wiele innych.

Ogólnie na cp-algorithms jest tak naprawde wszystko czego powinieneś umieć.

Comments

Na pewno znajomość matematyki licealnej też pomaga. Tu masz materiały do nauki matematyki dyskretnej, tylko to jest dla studentów, więc pewnie jeszcz trochę za trudne dla Ciebie.

---

Czasami zdarza się też, że przydaje się znajomość wartości oczekiwanej

---

@Whistleroosh, 

Dzięki, biorę się do nauki.