8063591562

najprostsza, a jednocześnie ich kod źródłowy jak najkrótszy.

Pozycja ta może służyć nie tylko zawodnikom — w połączeniu z książką dotyczącą podstaw algorytmiki, taką jak Wprowadzenie do algorytmów [WDA], może także stanowić doskonały sposób nauki „od podstaw”, łączący w sobie teoretyczną analizę algorytmów z podejściem bardziej praktycznym, opisanym w tej książce. Naukę taką w istotny sposób ułatwią liczne odwołania do literatury.

Pomysł na napisanie książki narodził się podczas treningów mojego zespołu — War-saw Predators, do zawodów ACM ICPC. W czasie wielu sesji treningowych tworzyliśmy i rozbudowywaliśmy naszą biblioteczkę algorytmiczną, w której umieszczaliśmy implementacje najczęściej wykorzystywanych w trakcie zawodów algorytmów i struktur danych. Książkę tę można określić mianem szczegółowej dokumentacji do biblioteczki algorytmicznej drużyny Warsaw Predators. Mam nadzieję, że materiały w niej zawarte pomogą wielu osobom w przygotowaniach do zawodów.

1.1. Struktura książki

Książka została podzielona na siedem rozdziałów, w których omówione są algorytmy z różnych dziedzin algorytmiki: teoria grafów, geometria obliczeniowa, kombinatoryka, teoria liczb, struktury danych, algorytmy tekstowe oraz algebra liniowa. W każdym z tych rozdziałów, przedstawione są różne algorytmy wraz z ich implementacjami, pochodzącymi z biblioteczki algorytmicznej. Ich omówienie ma na celu przybliżenie problematyki poruszanego zagadnienia oraz zaprezentowanie sposobu wykorzystania algorytmów w zadaniach. W celu zapoznania się z dowodami poprawności, czy dokładną analizą złożoności, należy sięgać do literatury, do której odwołania umieszczone są w różnych miejscach książki.

W dziale dodatków znajduje się rozdział dotyczący programowania dynamicznego oraz zachłannego. Z uwagi na fakt, iż z tymi dwoma technikami nie wiążą się specyficzne struktury danych ani algorytmy (rozwiązania zadań bazujących na programowaniu dynamicznym, czy zachłannym wykorzystują algorytmy z różnych dziedzin), zatem rozdział ten nie zawiera żadnych przydatnych implementacji, lecz odwołania do wielu zadań, na których można ćwiczyć umiejętność stosowania tych metod w praktyce.

W dodatkach umieszczone są również obserwacje oraz rady pochodzące od wielu światowej klasy zawodników. Lektura tego rozdziału może okazać się niezwykle cenna, gdyż zawarte w nim informacje pomagają uniknąć wielu problemów podczas przygotowań do zawodów.

W poszczególnych rozdziałach książki umieszczone są zadania związane z omawianą tematyką. Algorytmy potrzebne do ich rozwiązania są opisane, w miarę możliwości, w rozdziałach poprzedzających wystąpienie kolejnych zadań. W ten sposób, śledząc w kolejności poszczególne rozdziały książki, czytelnik będzie posiadał wiedzę potrzebną do rozwiązania wszystkich zadań. Większość z nich pochodzi z polskich konkursów informatycznych, takich jak Olimpiada Informatyczna, Potyczki Algorytmiczne czy Pogromcy Algorytmów. Programy stanowiące ich rozwiązania znajdują się na dołączonej płycie. Dodatkowo, na końcu książki umieszczony jest rozdział zawierający wskazówki do wszystkich tych zadań. Do każdego z nich znajduje się po kilka podpowiedzi, które mogą być pomocne podczas rozwiązywania — każda kolejna wskazówka uściśla pomysł naszkicowany w poprzedniej. Dzięki takiemu podejściu, jeśli początkowe wskazówki okażą się niewystarczające do rozwiązania zadania, można pokusić się o przeczytanie kolejnych.

Oprócz pełnych zadań, w książce znajdują się również odwołania do innych, pochodzących z internetowych serwisów, umożliwiających automatyczną weryfikację poprawności nadsyłanych rozwiązań. Czytelnik może najpierw rozwiązać samodzielnie zadanie, a następnie wysłać