INNE EBOOKI AUTORA
Autor:
Wydawca:
Format:
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.
Materiały dodatkowe dostępne na:
it.pwn.pl
Rok wydania | 2009 |
---|---|
Liczba stron | 312 |
Kategoria | Programowanie |
Wydawca | Wydawnictwo Naukowe PWN |
ISBN-13 | 978-83-01-15821-7 |
Numer wydania | 1 |
Język publikacji | polski |
Informacja o sprzedawcy | ePWN sp. z o.o. |
INNE EBOOKI AUTORA
POLECAMY
Ciekawe propozycje
Algorytmika dla studenta i technika...
do koszyka
Praktyczna analiza plików binarnych
do koszyka
Praktyczna analiza powłamaniowa
do koszyka
Praktyczna astrologia na co dzień
do koszyka
Praktyczna gramatyka języka polskiego
do koszyka
Praktyczna inżynieria wsteczna
do koszyka
Spis treści
Słowo wstępne | 9 |
Przedmowa | 11 |
1. Algorytmy grafowe | 15 |
1.1. Reprezentacja grafu | 16 |
1.2. Przeszukiwanie grafu wszerz | 20 |
1.3. Przeszukiwanie grafu w głąb | 25 |
1.4. Silnie spójne składowe | 31 |
1.5. Sortowanie topologiczne | 38 |
1.6. Acykliczność | 41 |
1.7. Mosty, punkty artykulacji i dwuspójnie składowe | 44 |
1.8. Ścieżka i cykl Eulera | 51 |
1.9. Minimalne drzewo rozpinające | 57 |
1.10. Algorytm Dijkstry | 60 |
1.11. Algorytm Bellmana-Forda | 65 |
1.12. Maksymalny przepływ | 67 |
1.12.1. Maksymalny przepły wyznaczany metodą Dinica | 68 |
1.12.2. maksymalny przepływ dla krawędzi jednostkowych | 72 |
1.12.3. Najtańszy maksymalny przepływ dla krawędzi jednostkowych | 74 |
1.13. Maksymalne skojarzenie w grafie dwudzielnym | 77 |
1.13.1. Dwudzielność grafu | 78 |
1.13.2. Maksymalne skojarzenie w grafie dwudzielnym w czasie O (n(n+m)) | 81 |
1.13.3. Maksymalne skojarzenie w grafie dwudzielnym w czasie O((n+m)n1/2) | 83 |
1.13.4. Najdroższe skojarzenie w grafie dwudzielnym | 86 |
2. Geometria obliczeniowa na płaszczyźnie | 91 |
2.1. Odległość punktu od prostej | 95 |
2.2. Pole wielokąta | 96 |
2.3. Przynależność punktu do figury | 98 |
2.4. Punkty przecięcia | 105 |
2.5. Trzy punkty - okrąg | 114 |
2.6. Sortowanie kątowe | 116 |
2.7. Otoczka wypukła | 120 |
2.8. Para najbliższych punktów | 123 |
3. Kombinatoryka | 128 |
3.1. Permutacje w kolejności antyleksykograficznej | 128 |
3.2. Permutacje - minimalna liczba transpozycji | 130 |
3.3. Permutacje - minimalna liczba transpozycji sąsiednich | 132 |
3.4. Wszystkie podzbiory zbioru | 135 |
3.5. Podzbiory k-elementowe w kolejności leksykograficznej | 137 |
3.6. Podziały zbioru z użyciem minimalnej liczby zmian | 138 |
3.7. Podziały liczby w kolejności antyleksykograficznej | 140 |
4. Teoria liczb | 142 |
4.1. Współczynnik dwumianowy | 142 |
4.2. Największy wspólny dzielnik | 144 |
4.3. Odwrotność modularna | 147 |
4.4. Kongruencje | 149 |
4.5. Szybkie potęgowanie modularne | 152 |
4.6. Sito Eratostenesa | 154 |
4.7. Lista liczb pierwszych | 155 |
4.8. Test pierwszości | 157 |
4.9. Arytmetyka wielkich liczb | 160 |
5. Struktury danych | 178 |
5.1. Struktura danych do reprezentacji zbiorów rozłącznych | 178 |
5.2. Drzewa wyszukiwań binarnych | 182 |
5.2.1. Drzewa maksimów | 185 |
5.2.2. Drzewa licznikowe | 187 |
5.2.3. Drzewa pozycyjne | 189 |
5.2.4. Drzewa pokryciowe | 192 |
5.3. Binarne drzewa statyczne dynamicznie alokowane | 195 |
5.4. Wzbogacane drzewa binarne | 200 |
6. Algorytmy tekstowe | 212 |
6.1. Algorytm KMP | 212 |
6.2. Minimalny okres słowa | 216 |
6.3. KMP dla wielu wzorców (algorytm Aho-Corasick) | 217 |
6.4. Promienie palindromów w słowie | 223 |
6.5. Drzewa sufiksowe | 226 |
6.5.1. Liczba wystąpień wzorca w tekście | 230 |
6.5.2. Liczba różnych podsłów słowa | 232 |
6.5.3. Najdłuższe podsłowo występujące n razy | 233 |
6.6. Maksymalny leksykograficznie sufiks | 234 |
6.7. Równoważność cykliczna | 235 |
6.8. Minimalna leksykograficznie cykliczność słowa | 237 |
7. Algebra liniowa | 240 |
7.1. Eliminacja Gaussa | 240 |
7.1.1. Eliminacja Gaussa w Z2 | 241 |
7.1.2. Eliminacja Gaussa w Zp | 244 |
7.2. Programowanie liniowe | 248 |
8. Elementy strategii podczas zawodów | 253 |
8.1. Szacowanie oczekiwanej złożoności czasowej | 253 |
8.2. Strategia pracy w drużynie | 255 |
8.3. Szablon | 258 |
8.4. Plik Makefile | 259 |
8.5. Parametry kompilacji programów | 259 |
8.5.1. Parametr - Weffc++ | 260 |
8.5.2. Parametr - Wformat | 262 |
8.5.3. Parametr - Wshadow | 263 |
8.5.4. Parametr - Wsequence-point | 264 |
8.5.5. Parametr - Wunused | 267 |
8.5.6. Parametr - Wuninitialized | 268 |
8.5.7. Parametr Wfloat-equal | 269 |
8.6. Nieustanny time-limit | 270 |
8.6.1. Eliminacja dzielenia | 271 |
8.6.2. Wczytywanie danych wejściowych | 271 |
8.6.3. Wstawki asemblerowe i kompilacja z optymalizacjami | 273 |
8.6.4. Lepsze wykorzystanie pamięci podręcznej | 274 |
8.6.5. Przetwarzanie wstępne | 275 |
Wskazówki do zadań | 278 |
Dodatki | 292 |
A. Nagłówki stosowane w programach | 292 |
B. Nagłównki Eryka Kopczyńskiego na konkurs TopCoder | 295 |
C. Sposoby na sukces w zawodach | 299 |
D. Wykaz zadań na programowanie dynamiczne | 304 |
E. Wykaz zadań na programowanie zachłanne | 305 |
F. Wykaz przykładowych zadań | 306 |
Literatura | 307 |
Indeks | 309 |