Książka ta różni się od znanych na polskim rynku pozycji poświęconych algorytmice, dotyczy bowiem jej strony praktycznej. Taki sposób potraktowania tego działu informatyki wynika z coraz większego zainteresowania zarówno uczniów, jak i studentów udziałem w różnego rodzaju konkursach programistycznych.
Czytelnik znajdzie w niej przegląd implementacji podstawowych algorytmów i struktur danych, które można zastosować bezpośrednio bądź zaadaptować w prosty sposób przy rozwiązywaniu zadań konkursowych.
Fundamentem książki jest biblioteczka algorytmiczna, która była tworzona i rozbudowywana podczas przygotowań zespołu Warsaw Predators z Uniwersytetu Warszawskiego do reprezentowania tej uczelni na międzynarodowych zawodach.
Na niepowtarzalny charakter książki składają się następujące elementy: • prezentacja wszystkich ważniejszych z punktu widzenia konkursów działów algorytmiki; • intuicyjne podejście do przedstawianych zagadnień algorytmicznych; • zwięzła, efektywna implementacja omawianych algorytmów w języku C++; • liczne przykładowe zadania konkursowe wraz ze wskazówkami stopniowo nakierowującymi na właściwe rozwiązanie zadania, a także z adresem strony internetowej, na której można znaleźć programy stanowiące rozwiązania tych zadań; • tematyczne wykazy zadań z całego świata z możliwością testowania ich rozwiązań na stronach internetowych konkursów; • odsyłacze do literatury umożliwiającej szczegółowe poznanie opisywanych zagadnień od strony teoretycznej; • cenne rady dotyczące strategii uczestnictwa w konkursach.
Po pracę tę powinna sięgnąć każda osoba pragnąca doskonalić swoje umiejętności algorytmiczne i programistyczne.
Rozdziały:
1. Algorytmy grafowe 1.1. Reprezentacja grafu 1.2. Przeszukiwanie grafu wszerz 1.3. Przeszukiwanie grafu w głąb 1.4. Silnie spójne skłądowe 1.5. Sortowanie topologiczne 1.6. Acykliczność 1.7. Mosty, punkty artykulacji i dwuspójne składowe 1.8. Ścieżka i cykl Eulera 1.9. Minimalne drzewo rozpinające 1.10. Algorytm Dijkstry 1.11. Algorytm Bellmana-Forda 1.12. Maksymalny przepływ 1.13. Maksymalne skojarzenie w grafie dwudzielnym
2. Geometria obliczeniowa na płaszczyźnie 2.1. Odległość punktu od prostej 2.2. Pole wielokąta komputeks.pl 2.3. Przynależność punktu do figury 2.4. Punkty przecięcia 2.5. Trzy punkty - okrąg 2.6. Sortowanie kątowe 2.7. Otoczka wypukła 2.8. Para najbliższych punktów
3. Kombinatoryka 3.1. Permutacje w kolejności antyleksykograficznej 3.2. Permutacje - minimalna liczba transpozycji 3.3. Permutacje - minimalna liczba transpozycji sąsiednich 3.4. Wszytkie podzbiory zbioru styczna.pl 3.5. Podzbiory k-elementów w kolejności leksykograficzej 3.6. Podziały zbioru z użyciem minimalnej liczby zmian 3.7. Podziały liczby w kolejności antyleksykograficznej
4. Teoria liczb 4.1. Współczynnik dwumianowy 4.2. Największy wspólny dzielnik 4.3. Odwrotność modularna 4.4. Kongruencje 4.5. Szybkie potęgowanie modularne 4.6. Sito Eratostenesa 4.7. Lista liczb pierwszych 4.8. Test pierwszości 4.9. Arytmrtyka wielkich liczba
5. Struktury danych 5.1. Struktura danych do reprezentacji zbiorów rozłącznych 5.2. Drzewa wyszukiwań binarnych 5.3. Binarne drzewa statyczne dynamicznie alokowane 5.4. Wzbogacane drzewa binarne
6. Algorytmy tekstowe 6.1. Algorytm KMP 6.2. Minimalny okres słowa 6.3. KMP dla wielu wzorców (algorytm Aho-Corasick) 6.4. Promienie palindromów w słowie 6.5. Drzewa sufiksowe 6.6. Maksymalny leksykograficznie sufiks 6.7. Równoważność cykliczna 6.8. Minimalna leksykograficznie cykliczność słowa
7. Algebra liniowa 7.1. Eliminacja Gaussa 7.2. Programowanie liniowe
8. Elementy strategii podczas zawodów 8.1. Szacowanie oczekiwanej złożoności czasowej 8.2. Strategia pracy w drużynie 8.3. Szablon 8.4. Plik Makefile 8.5. Parametry kompilacji programó 8.6. Nieustanny time-limit
Wskazówki do zadań
Dodatki: A. Nagłówki stosowane w programach B. Nagłówki Eryka Kopczyńskiego na konkurs TopCoder C. Sposoby na sukces na zawodach D. Wykaz zadań na programowanie dynamiczne E. Wykaz zadań na programowanie zachłanne F. Wykaz przykładowych zadań
|