szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 maja 2017, o 21:25 
Użytkownik

Posty: 9
Lokalizacja: Kraków
Witam, uczęszczam do 1 klasy liceum profil mat-fiz-inf i chciałbym przygotowywać się do Olimpiady Informatycznej. Posiadam podstawy jeśli chodzi o język, przerobiłem całą książkę Stephena Praty J"ęzyk C++ Szkoła Programowania" oraz STL, wszelkie struktury danych pokroju vector, list, map itd. Zdaję sobie sprawę, że OI to konkurs ściśle związany z matematyką i gra ona tam główną rolę dlatego zwracam się na forum z prośbą o pomoc, czytałem już kilka postów jednak każdy problem jest indywidualny dlatego zdecydowałem się stworzyć własny temat. Podstawowe rzeczy jakie potrzebuje wiedzieć i jakie wprawiają mnie w zakłopotanie to algorytmy i książki potrzebne do olimpiady. Zaopatrzyłem się w "Wprowadzenie do algorytmów" Cormena i przerabiam ją powoli, jednak na forum spotkałem się z 2/3 opiniami, że przerobienie całej książki nie ma sensu zważając na jej rozmiary stąd moje pytanie do osób, które może spotkały się z tym samym problemem, które zagadnienia z tej książki przydadzą mi się w OI, druga sprawa to złożoności operacji, z tego co zasłyszałem na OI liczy się też wydajność rozwiązań i dobór odpowiednich algorytmów do konkretnych zadań, także na forum wyczytałem, że należy się zapoznać ze złożonościami i tu pojawia się problem, że kompletnie nie mam pojęcia gdzie tego szukać, próbowałem ale możliwe, że szukam w złych miejscach. Myślę, że to tyle i na sam koniec chciałbym dodać, że przygotowuje się do olimpiady sam, ponieważ w moje szkole nauczyciele uczący informatyki nie są informatykami z prawdziwego zdarzenia :P stąd moje zakłopotanie i pytania, które pewnie mogą wydawać się trochę bez sensu.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 02:05 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
Sama znajomość języka C++ ci nic nie da, jeśli nie będziesz miał podstaw z algorytmiki. To, co potrzebujesz opanować, to:
-algorytmy w teorii
-schematy blokowe
-złożoność obliczeniowa
Na pewno nie zaszkodzi też wiedza matematyczna rozszerzona, podstawowa wiedza o macierzach i takie tam.
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 12:26 
Użytkownik
Avatar użytkownika

Posty: 406
Lokalizacja: Warszawa
Schematy blokowe? Do czego na Olimpiadzie?
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 13:01 
Użytkownik

Posty: 1073
Lokalizacja: Lublin/Warszawa
Złożoność obliczeniowa?? Proste szacowanie złożoności wystarczy. Poza samą algorytmiką, podstawowa wiedza z matematyki dyskretnej może być potrzebna (grafy, kombinatoryka, teoria liczb).
Przygotowanie do OI nie polega na czytaniu książek, tylko na TRENINGU zadań przede wszystkim (MAIN, serwisy takie jak Codeforces, gdzie są systematycznie treningi, są tagi przy nazwach zadań które są wskazówką jakie typy zadań trzeba opanować, są tutoriale z rozwiązaniami, jest dostęp do kodów innych zawodników itp.). Powtarzam: TRENINGU! Tu się liczy, żeby szybko klepać bez błędów i jeszcze szybciej kminić.

Najbardziej doświadczeni zawodnicy, z pierwszych miejsc, znają większość zadań, która była na OIu, a na OIu przygotowanie się nie kończy - są konkursy międzynarodowe (BOI, CEOI, IOI, prawie każde mają swoje strony), a olimpiady informatyczne są na całym świecie. Trzeba zrobić kilkaset zadań na poziomie OI żeby być dobrze przygotowanym. Różnych zadań jest dużo i dużo jest też technik typowo olimpijskich, których w żadnych książkach nie znajdziesz.
Przygotuj sobie jakąś biblioteczkę podstawowych algorytmów (przy wykorzystaniu STLa).

Szukając informacji w internecie powinieneś zdawać sobie sprawę, że dużo więcej informacji znajdziesz po angielsku niż po polsku wpisując hasła w Google'u. To jest bardzo istotne. Hasło przewodnie: competitive programming.

Omówienia zadań z OIa i kody rozwiązań są w niebieskich książeczkach: http://www.oi.edu.pl/l/40/
Przydatne linki: http://www.oi.edu.pl/l/21/

Tutoriale na TopCoder: https://www.topcoder.com/community/data ... tutorials/

Na ważniaku dużo rzeczy jest (kursy Wstęp do programowania, Algorytmy i struktury danych, Matematyka dyskretna 1).

Drogowskaz pasjonata, na dole masz OI:
http://warsztatywww.wikidot.com/drogowskaz-pasjonata:olimpiady

Szczegółowo wypisane podstawowe zagadnienia:
http://mokip.wdfiles.com/local--files/linki/plan_arka.pdf

Mogą się przydać rzeczy z ILOCAMPu:
https://ilocamp.pl/
tutaj można znaleźć książeczki z obozów.

Cormen jest książką raczej dla studentów, może być przydatny jeżeli chcesz dowodu poprawności jakiegoś podstawowego algorytmu. Istotne jest, abyś dobrze te algorytmy rozumiał, umiał je stosować i jeżeli to konieczne zmodyfikować jakieś podstawowe rzeczy. Implementacje znajdziesz w internecie.
Rozdziały, które na pewno powinieneś przeczytać z Cormena dot.:
- sortowania (ważne żeby umieć korzystać z sorta, zdefiniować własny porządek itd.)
- programowanie dynamiczne (rekurencje)
- algorytmy zachłanne
- cały rozdział związany z grafami, bo grafy są bardzo ważne (bfs, dfs, podział na spójne składowe, sortowanie topologiczne, podział na silnie spójne składowe, minimalne drzewo rozpinające, najkrótsze ścieżki - Dijkstra, Floyd-Warshall, może też trochę przepływy;)
- struktura zbiorów rozłącznych (Find&Union)
- trochę algorytmy teorioliczbowe (np. sito Eratostenesa, rozszerzone nwd, chińskie twierdzenie o resztach)
- stringi (KMP)
- może coś z geometrii obliczeniowej, choć to raczej na finał
- listy (na wskaźnikach)
- drzewa BST

Poza tym istotne są np.:
- drzewa przedziałowe, licznikowe - coś o tym jest tutaj: http://was.zaa.mimuw.edu.pl/?q=node/8
- cykle Eulera - algorytm Fleury'ego
- haszowanie: http://ki.staszic.waw.pl/materialy/Haszowanie.ppt
- 2 SAT.

Czytaj Deltę - jest tam dział informatyczny z omówieniami niektórych zadań.

Poza tym przydatne mogą być książki np.
Algorytmika praktyczna Stańczyka (ale tutaj kody mogą być zbyt skomplikowane dla początkującego)
Competitive programming,
Wstęp do teorii grafów, Wilson
Matematyka Dyskretna.

Aha, i nauczycielami się nie przejmuj. Oni z reguły nic nie umieją i to jest standard, poza paroma szkołami w kraju. Istotna jest samodzielna praca. Za to w Krakowie jest V LO i może oni prowadzą tam jakieś otwarte kółko ;) Więcej dowiesz się, jeżeli pogadasz z jakimś doświadczonym zawodnikiem.
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 13:52 
Użytkownik

Posty: 9
Lokalizacja: Kraków
Źródła były dla mnie kluczowe, napewno z tego z korzystam. Jednak jeśli ktoś miałby jeszcze jakieś rady to chętnie posłucham :D
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 13:53 
Użytkownik
Avatar użytkownika

Posty: 406
Lokalizacja: Warszawa
Całkiem fajna jest też książeczka https://cses.fi/book.pdf.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Przygotowanie do Olimpiady o Diamentowy Indeks AGH  listek242  4
 III Edycja Ogólnopolskiej Olimpiady "O Diamentowy Indeks AGH  Tomek_Z  292
 GMiL - przygotowanie  Konstanca  2
 Poszukiwania materiałów do Olimpiady Lingwisycznej  Sambard  0
 VI edycja Ogólnopolskiej Olimpiady "O Diamentowy Indeks AGH"  Mruczek  108
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl