Algorytmika praktyczna

Algorytmika praktyczna

Nie tylko dla mistrzów

1 opinia

Format:

ibuk

WYBIERZ RODZAJ DOSTĘPU

 

Dostęp online przez myIBUK

WYBIERZ DŁUGOŚĆ DOSTĘPU

6,15

Wypożycz na 24h i opłać sms-em

22,45

cena zawiera podatek VAT

ZAPŁAĆ SMS-EM

TA KSIĄŻKA JEST W ABONAMENCIE

Już od 19,90 zł miesięcznie za 5 ebooków!

WYBIERZ SWÓJ ABONAMENT

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.


Liczba stron312
WydawcaWydawnictwo Naukowe PWN
ISBN-13978-83-01-15821-7
Numer wydania1
Język publikacjipolski
Informacja o sprzedawcyRavelo Sp. z o.o.

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
RozwińZwiń
W celu zapewnienia wysokiej jakości świadczonych przez nas usług, nasz portal internetowy wykorzystuje informacje przechowywane w przeglądarce internetowej w formie tzw. „cookies”. Poruszając się po naszej stronie internetowej wyrażasz zgodę na wykorzystywanie przez nas „cookies”. Informacje o przechowywaniu „cookies”, warunkach ich przechowywania i uzyskiwania dostępu do nich znajdują się w Regulaminie.

Nie pokazuj więcej tego powiadomienia