Algorytmika praktyczna
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
- Kategorie:
- Język wydania: polski
- ISBN: 978-83-01-15821-7
- ISBN druku: 978-83-01-15817-0
- Liczba stron: 312
-
Sposób dostarczenia produktu elektronicznegoProdukty elektroniczne takie jak Ebooki czy Audiobooki są udostępniane online po opłaceniu zamówienia kartą lub przelewem na stronie Twoje konto > Biblioteka.Pliki można pobrać zazwyczaj w ciągu kilku-kilkunastu minut po uzyskaniu poprawnej autoryzacji płatności, choć w przypadku niektórych publikacji elektronicznych czas oczekiwania może być nieco dłuższy.Sprzedaż terytorialna towarów elektronicznych jest regulowana wyłącznie ograniczeniami terytorialnymi licencji konkretnych produktów.
-
Ważne informacje techniczneMinimalne wymagania sprzętowe:procesor: architektura x86 1GHz lub odpowiedniki w pozostałych architekturachPamięć operacyjna: 512MBMonitor i karta graficzna: zgodny ze standardem XGA, minimalna rozdzielczość 1024x768 16bitDysk twardy: dowolny obsługujący system operacyjny z minimalnie 100MB wolnego miejscaMysz lub inny manipulator + klawiaturaKarta sieciowa/modem: umożliwiająca dostęp do sieci Internet z prędkością 512kb/sMinimalne wymagania oprogramowania:System Operacyjny: System MS Windows 95 i wyżej, Linux z X.ORG, MacOS 9 lub wyżej, najnowsze systemy mobilne: Android, iPhone, SymbianOS, Windows MobilePrzeglądarka internetowa: Internet Explorer 7 lub wyżej, Opera 9 i wyżej, FireFox 2 i wyżej, Chrome 1.0 i wyżej, Safari 5Przeglądarka z obsługą ciasteczek i włączoną obsługą JavaScriptZalecany plugin Flash Player w wersji 10.0 lub wyżej.Informacja o formatach plików:
- PDF - format polecany do czytania na laptopach oraz komputerach stacjonarnych.
- EPUB - format pliku, który umożliwia czytanie książek elektronicznych na urządzeniach z mniejszymi ekranami (np. e-czytnik lub smartfon), dając możliwość dopasowania tekstu do wielkości urządzenia i preferencji użytkownika.
- MOBI - format zapisu firmy Mobipocket, który można pobrać na dowolne urządzenie elektroniczne (np.e-czytnik Kindle) z zainstalowanym programem (np. MobiPocket Reader) pozwalającym czytać pliki MOBI.
- Audiobooki w formacie MP3 - format pliku, przeznaczony do odsłuchu nagrań audio.
Rodzaje zabezpieczeń plików:- Watermark - (znak wodny) to zaszyfrowana informacja o użytkowniku, który zakupił produkt. Dzięki temu łatwo jest zidentyfikować użytkownika, który rozpowszechnił produkt w sposób niezgodny z prawem. Ten rodzaj zabezpieczenia jest zdecydowanie bardziej przyjazny dla użytkownika, ponieważ aby otworzyć książkę zabezpieczoną Watermarkiem nie jest potrzebne konto Adobe ID oraz autoryzacja urządzenia.
- Brak zabezpieczenia - część oferowanych w naszym sklepie plików nie posiada zabezpieczeń. Zazwyczaj tego typu pliki można pobierać ograniczoną ilość razy, określaną przez dostawcę publikacji elektronicznych. W przypadku zbyt dużej ilości pobrań plików na stronie WWW pojawia się stosowny komunikat.
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