Która książka do olimpiady informatycznej?

0

Mam do wyboru dwie książki:
http://ksiegarnia.pwn.pl/prod[...]rowadzenie-do-algorytmow.html
http://helion.pl/ksiazki/c-al[...]anych-adam-drozdek,calstr.htm
którą książkę wybrać?
W "Kompendium wiedzy" na forum znalazłem temat:
Książki do algorytmiki
Pierwsza z książek należy do kategorii "Średniozaawansowani", a druga do "Początkujący".
Natomiast tytuł pierwszej mówi o algorytmach, a drugiej o algorytmach i strukturach danych, ale w spisie treści pierwsza też ma rozdział o strukturach danych.
Którą wybrać? A może macie do polecenia inne książki? Którą wybrać?

I jeszcze jedno. Jak mogę przygotować się do olimpiady? Co powinienem robić, kupić, czytać, ..., żeby poszło mi dobrze? Nie mam osoby, która może mnie choć trochę poprowadzić przez to wszystko, więc zostaje mi to forum i Wy... nigdy nie startowałem w olimpiadzie.

0

Udział w olimpiadzie jest dobrowolny. Jeśli czujesz, że to nie jest dla Ciebie, to po prostu nie bierz udziału, nie ma nic na siłę.

Jeśli wciąż chcesz brać udział, to zapoznaj się z materiałami ze strony Olimpiady Informatycznej:

http://oi.edu.pl/l/40/ - zdania z rozwiązaniami w wersji elektronicznej
http://oi.edu.pl/l/niebieska_ksiazeczka/ - zadania z rozwiązaniami w wersji papierowej
http://oi.edu.pl/l/jak_zaczac/ - FAQ jak zacząć

Jak się przygotować... trzaskaj zadania z poprzednich edycji ;)

0

ah...zapomniałem dodać, chodzi o Olimpiadę Informatyczną Gimnazjalistów, OIG :)

i jedna uwaga, chcę wziąć udział, bo pisanie programów, skryptów, itp. jest bardzo ciekawe, a jeśli przy okazji nauczę się czegoś ciekawego, albo w najlepszym wypadku osiągnę jakiś dobry wynik, to nie marudzę :) ale jest właśnie kwestia przygotowania, bo nie mam osoby w otoczeniu, która dałaby mi cenne wskazówki, albo w razie pytań o pisanie programów, dała odpowiedź. Dlatego szukam książki i waszej pomocy :)

a z jakich książek lub stron wy się przygotowywaliście?

0

Pierwsza z książek należy do kategorii "Średniozaawansowani", a druga do "Początkujący".
Natomiast tytuł pierwszej mówi o algorytmach, a drugiej o algorytmach i strukturach danych, ale w spisie treści pierwsza też ma rozdział o strukturach danych.
Którą wybrać? A może macie do polecenia inne książki? Którą wybrać?

Zdecydowanie bierz Cormena. Nie jest to lektura łatwa (szczególnie dla gimnazjalisty), ale przydatna na wiele lat.
Zobacz sobie spis treści - obie są zarówno o algorytmach i strukturach danych! Po prostu Cormen nie ma w nazwie "struktura danych", ale jest tam więcej o takowych niż w innych książkach, które mają "struktury danych" w nazwie.
Zamów sobie niebieskie książeczki ze strony OI.

a z jakich książek lub stron wy się przygotowywaliście?

http://4programmers.net/Forum/Algorytmy/182500-naukaalgorytmiki-_poczatkujacy

Polecam również naukę do olimpiady matematycznej i olimpiady matematycznej gimnazjalistów dla treningu umysłu (do tego będziesz miał łatwiej na studiach - uwierz mi - osoby, które były finalistami OM o wiele szybciej zaczają nowe rzeczy z przedmiotów matematycznych).

I najważniejsza porada - następnym razem szukaj na forum! Zapewne wiele osób zadawało już podobne pytania.

0

wybór padł na książkę Cormena :) dzięki za pomoc, w wyszukiwaniu wyskoczyły mi tematy o olimpiadzie licealnej i nie tylko. Poza tym szukałem pomocy w wyborze pomiędzy konkretnymi książkami, a takiej na forum nie znalazłem
w OMG również wystartowałem ;)

i jeszcze jedno pytanie mi się nasunęło. Czy startując w olimpiadzie muszę bardzo dobrze nauczyć się języka C++ czy może ucząc się algorytmów i znając podstawy C++ poradzę sobie z zadaniami? W którym kierunku patrzeć?

2

Z C++ na olimpiadę wystarczy znajomość programowania strukturalnego + umiejętność tworzenia najprostszych struktur + zalecana jest biblioteka STL.
To wystarczy, ale może się też przydać czasami (w szczególności najważniejsze jest tutaj przeciążenie operatorów) coś z programowania obiektowego (tzn. najczęściej dzięki temu można pisać nieco szybciej), ale najważniejsza jest rozkmina i znajomość algorytmów.

0

Tylko tak naprawdę, to nie jest konkurs dla programistów, a matematyków.

Programowania wystarczy znać naprawdę niewiele, głównie pętle, ify, tablice, rekurencja, bo niektóre problemy iteracyjnie się dłużej wymyśla(a rozwiązania problemów w książkach są często). Ogólnie podstawy.

Jeśli ktoś ma problem z zadaniem to polecam złapać kilka książek do matematyki dyskretnej, znaleźć odpowiednie zagadnienie i program sam się pisze. Oczywiście można samemu kombinować na logikę, ale wierzcie mi że szkoda czasu i to są podstawowe problemy, ze szczegółami opisane najczęściej właśnie w dziedzinie matematyki, która zbiera różne nieokreślone kategorią zagadnienia (Matematyka Dyskretna).

Pamiętam jak kiedyś się męczyłem z zadaniem tylko w Technikum na OI z takimi właśnie zdaniami. Poszedłem do nauczycielki od matmy niczego nie oczekując, rzuciła słowo: grafy planarne, kolorowanie grafów. Chwila w sieci i już zadanie gotowe. Następnym razem szukałem już po prostu zagadnień matematycznych i znalazłem o problemie oficerów (kwadrat łaciński). Te zadania są łatwymi zadaniami w oparciu o problemy matematyczne rozwiązane już dawno temu. Można znaleźć problem, twierdzenie, dowód i na tej podstawie już wystarczy tylko to zaimplementować.

Dlatego twierdzę, że to olimpiada matematyczna dla osób znających podstawy programowania i wiedzących gdzie szukać zagadnień matematycznych. Są też tacy co dużo kombinują i oddają programy, które zazwyczaj nie wszystkie dane dobrze przemielą.

0

zgadzam się... wiele zadań, po przeanalizowaniu zbiegały się do zwykłego podstawienia do wzoru, np. było zadanie tak ciekawie rozbudowane, że wyglądało na trudne, ale po rozpisaniu wyszedł wzór 100x + 10y + za liczby x, y, z były jedno cyfrowe... wystarczyło wypisać je na ekran ;)

Wracając do tematu. Problemy z jakimi się spotykam często są błahe, ale nie potrafię się ich pozbyć. Nie wiem na przykład, jak można wczytać bardzo długie liczby. Przykładowo w zadaniu "Cukierki":
zadania.oig.edu.pl/OIG/stored_files/download/2094683
wystarczyło dwukrotnie wypisać liczbę podaną na wejściu; ale liczba b jest w zakresie od 1 do 10100.
Mam nadzieję, że można rozmawiać o tych zadaniach, ponieważ 1 runda już minęła, a w regulaminie OIG nie znalazłem zakazu ;)

Oczywiście matematyka się przydaje, ale chciałbym sięgnąć trochę głębiej i, mimo że matematyka w dużym stopniu wystarczy, poczytać o czymś stricte algorytmicznym i "C++ -owym".

0

Jeśli ktoś miał Matematykę Dyskretną wie o jakie zagadnienia i problemy chodzi, jeśli nie miał styczności z tym to rozumiem, że nie do końca wie o co mi chodzi. Jednak napisałem to dla waszego pożytku. Sam przez te olimpiady przechodziłem i to było odkrycie, które pozwoliło mi znaleźć rozwiązania w książkach, a najczęściej ebookach i prezentacjach wykładowców w necie.

Najłatwiej znaleźć rozwiązania jeśli zadania są oparte o grafy, a takich zawsze sporo. Bierzemy wtedy do ręki książkę o teorii grafów, a raczej od Matematyki Dyskretnej gdzie mamy taki rozdział i czytamy co to graf spójny, płaski, dwoisty co to cykle itd.. Jakie są metody sprawdzania, że to graf płaski. Dochodzimy do kolorowania grafów itd. i nagle zauważamy, że mamy podane na tacy rozwiązania, no ew. warto zajrzeć co to kwantyfikatory, żeby rozszyfrować oznaczenia. Algorytm tam już mamy podany, prawie zawsze rekurencyjnie i łatwo to podczepić pod zadanie. Bo otoczka zadania i jego opis to mydlenie oczu dziwnymi historyjkami. Gdyby nazwali po imieniu o co chodzi, to każdy w googlu znalazłby rozwiązanie od razu. Dlatego to śmieszne, ale wcale nie trzeba przy tych zadaniach nie wiadomo jak główkować i algorytmy wymyślać. Wystarczy zaimplementować dowód tezy podanej w książce.

Co do Cormena, nikt nie odważy się zanegować, że to świetny kawał wiedzy. Część się może przydać jak np. drzewa, grafy ich wyważanie, różne algorytmy na nich. Sam korzystając z Cormena to robiłem, ale nie na olimpiady. Duża część jednak jak np. omawianie konkretnie drzewa czerwono-czarnego (gdzie na OI wystarczy najprostsze jeśli jest mus), listy, kolejki od podszewki, które sam implementowałem na studiach nie będą zbyt potrzebne na OI.

0

@JumpSmerf Kiedy trzeba coś szybko napisać to ok, ale to dopiero na wyższych szczeblach. Z matematyki też wiedzy mieć nie trzeba. Trzeba być kumatym, znać podstawy programowania i najlepiej troszkę się pobawić w programowaniu oraz umieć dobrze szukać, by znaleźć odpowiednie zagadnienie w literaturze. Można też wyłamywać drzwi i wymyślać, ale po co skoro jakiś matematyk to pięknie na pewno rozwiązął i udowodnił, najczęsciej pozostawiając gotowe algorytmy tylko zapisane matematycznie (bardzo często zapisane rekurencyjnie), czego nie trzeba się bać, wystarczy tylko ogarnąć zapis, ja np. się dziwiłem widząc kwantyfikatory, ale okazało się że to bardzo proste do ogarnięcia, tylko zapis enigmatyczny na początku odstraszał.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0