INNE EBOOKI AUTORA
Koszyk
Algorytmika praktyczna
Nie tylko dla mistrzów
Autor:
Wydawca:
Format:
pdf, ibuk
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. |
POLECAMY
Ciekawe propozycje
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 |
KUP NA PREZENT
Algorytmika praktyczna
69,00 zł
Uzupełnij informacje na temat odbiorcy.
Produkt został pomyślnie dodany do koszyka.
Nieudana próba zakupu produktu. Spróbuj jeszcze raz.
Wypożyczaj w abonamencie!
Już od 2,66 zł za ebooka
