O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Algorytmy. Almanach

Book Description

Książka Algorytmy. Almanach to cała wiedza o algorytmach, potrzebna ambitnemu programiście, zebrana w jeden kompletny podręcznik. Książka zawiera opisy algorytmów do rozwiązywania rozmaitych problemów, pomaga w wyborze i realizacji algorytmów odpowiednich do Twoich potrzeb, a także dostarcza wydajnych rozwiązań zakodowanych w kilku językach programowania, które łatwo można zaadaptować w konkretnych zadaniach.

Table of Contents

  1. Algorytmy. Almanach
  2. Przedmowa
    1. Zasada: używaj prawdziwego kodu, a nie pseudokodu
    2. Zasada: oddziel algorytm od rozwiązywanego problemu
    3. Zasada: wprowadzaj tylko tyle matematyki, ile trzeba
    4. Zasada: analizę matematyczną stosuj doświadczalnie
    5. Odbiorcy
    6. Treść książki
    7. Konwencje stosowane w tej książce
    8. Zastosowanie przykładów w kodzie
    9. Podziękowania
    10. Literatura
  3. I.
    1. 1. Algorytmy są ważne
      1. Postaraj się zrozumieć problem
      2. Jeśli to konieczne, eksperymentuj
        1. Algorytmy na ratunek
      3. Kwestia uboczna
      4. Nauka płynąca z opowiedzianej historii
      5. Literatura
    2. 2. Algorytmy w ujęciu matematycznym
      1. Rozmiar konkretnego problemu
      2. Tempo rośnięcia funkcji
      3. Analiza przypadku najlepszego, średniego i najgorszego
        1. Przypadek najgorszy
        2. Przypadek średni
        3. Przypadek najlepszy
      4. Rodziny efektywności
        1. Omówienie 0. Zachowanie stałe
        2. Omówienie 1. Zachowanie log n
        3. Omówienie 2. Zachowanie podliniowe O(nd) dla d<1
        4. Omówienie 3. Sprawność liniowa
        5. Omówienie 4. Sprawność n log n
        6. Omówienie 5a. Sprawność kwadratowa
        7. Omówienie 5b. Mniej oczywiste obliczenia sprawności
      5. Mieszanka działań
      6. Operacje do pomiarów wzorcowych
      7. Uwaga końcowa
      8. Literatura
    3. 3. Wzorce i dziedziny
      1. Wzorce — język komunikacji
        1. Postać wzorca algorytmu
        2. Forma wzorca algorytmu
      2. Forma wzorca pseudokodu
      3. Forma projektowa
      4. Forma oceny doświadczalnej
      5. Dziedziny a algorytmy
      6. Obliczenia zmiennopozycyjne
        1. Błąd zaokrąglenia
        2. Porównywanie wartości
        3. Wielkości specjalne
        4. Sprawność
      7. Ręczne przydzielanie pamięci
      8. Wybór języka programowania
        1. Literatura
  4. II.
    1. 4. Algorytmy sortowania
      1. Przegląd
        1. Terminologia
        2. Reprezentacja
        3. Elementy porównywalne
        4. Sortowanie stabilne
      2. Techniki analizy
        1. Typowe dane wejściowe
      3. Sortowanie przez wstawianie
        1. Kontekst
        2. Uwarunkowania
        3. Rozwiązanie
        4. Konsekwencje
        5. Analiza
      4. Sortowanie medianowe
        1. Kontekst
        2. Uwarunkowania
        3. Rozwiązanie
        4. Konsekwencje
        5. Analiza
      5. Sortowanie szybkie
        1. Kontekst
        2. Rozwiązanie
        3. Konsekwencje
        4. Analiza
        5. Odmiany
        6. Wybieranie wartości osiowej
        7. Wykonywanie podziału
        8. Przetwarzanie podtablic
        9. Zastosowanie prostszej techniki wstawiania dla małych podtablic
        10. IntroSort
      6. Sortowanie przez wybieranie
      7. Sortowanie przez kopcowanie
        1. Kontekst
        2. Uwarunkowania
        3. Rozwiązanie
        4. Analiza
        5. Odmiany
      8. Sortowanie przez zliczanie
        1. Kontekst
        2. Uwarunkowania
        3. Rozwiązanie
        4. Analiza
      9. Sortowanie kubełkowe
        1. Kontekst
        2. Uwarunkowania
        3. Rozwiązanie
        4. Analiza
        5. Odmiany
      10. Kryteria wyboru algorytmu sortowania
        1. Wyniki napisowych testów porównawczych
        2. Wyniki zmiennopozycyjnych testów porównawczych
      11. Literatura
    2. 5. Wyszukiwanie
      1. Przegląd
      2. Wyszukiwanie sekwencyjne
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
        2. Kontekst
        3. Uwarunkowania
        4. Rozwiązanie
        5. Konsekwencje
        6. Analiza
        7. Odmiany
        8. Wyszukiwanie binarne
        9. Wejście-wyjście
        10. Kontekst
        11. Uwarunkowania
        12. Rozwiązanie
        13. Konsekwencje
        14. Analiza
        15. Odmiany
      3. Wyszukiwanie z haszowaniem
        1. Wejście-wyjście
          1. Założenia
        2. Kontekst
        3. Uwarunkowania
        4. Rozwiązanie
        5. Konsekwencje
        6. Analiza
          1. Odmiany
      4. Przeszukiwanie drzewa binarnego
        1. Wejście-wyjście
        2. Kontekst
        3. Uwarunkowania
        4. Rozwiązanie
        5. Konsekwencje
        6. Analiza
        7. Odmiany
      5. Literatura
    3. 6. Algorytmy grafowe
      1. Przegląd
        1. Grafy
        2. Zagadnienia dotyczące pamięci
        3. Analiza grafu
        4. Projekt struktury danych
        5. Problemy
      2. Przeszukiwania w głąb
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenia
        2. Kontekst
        3. Rozwiązanie
        4. Analiza
      3. Przeszukiwanie wszerz
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenia
        2. Kontekst
        3. Rozwiązanie
        4. Analiza
      4. Najkrótsza ścieżka z jednym źródłem
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenia
        2. Rozwiązanie
        3. Konsekwencje
        4. Analiza
        5. Odmiany
        6. Porównanie
          1. Dane porównawcze
          2. Grafy gęste
          3. Grafy rzadkie
      5. Najkrótsza ścieżka między wszystkimi parami
        1. Wejście
        2. Wyjście
        3. Założenia
        4. Rozwiązanie
        5. Analiza
      6. Algorytmy minimalnego drzewa rozpinającego
        1. Rozwiązanie
        2. Konsekwencje
        3. Analiza
        4. Odmiany
      7. Literatura
    4. 7. Znajdowanie dróg w AI
      1. Przegląd
        1. Drzewo gry
        2. Drzewa poszukiwań
        3. Podstawowe zasady
          1. Reprezentowanie stanu
          2. Obliczanie dostępnych ruchów
          3. Korzystanie z informacji heurystycznych
          4. Maksymalna głębokość rozwinięcia
        4. Założenia
        5. Przeszukiwanie w głąb
        6. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenie
        7. Kontekst
        8. Rozwiązanie
        9. Konsekwencje
        10. Analiza
      2. Przeszukiwania wszerz
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
        2. Kontekst
        3. Rozwiązanie
        4. Konsekwencje
        5. Analiza
      3. A*SEARCH
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenia
        2. Kontekst
        3. Rozwiązanie
        4. Konsekwencje
        5. Uwarunkowania
        6. Analiza
        7. Odmiany
        8. Algorytmy pokrewne
      4. Porównanie
      5. Algorytm minimaks
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenia
        2. Kontekst
        3. Rozwiązanie
        4. Konsekwencje
        5. Analiza
        6. Odmiany
        7. Algorytm negmaks
        8. Wejście-wyjście
        9. Kontekst
        10. Rozwiązanie
        11. Konsekwencje
        12. Analiza
      6. Algorytm AlfaBeta
        1. Wejście-wyjście
        2. Rozwiązanie
        3. Konsekwencje
        4. Analiza
      7. Literatura
    5. 8. Algorytmy przepływu w sieciach
      1. Przegląd
        1. Przepływ w sieci
      2. Przepływ maksymalny
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
        2. Rozwiązanie
        3. Konsekwencje
          1. Analiza
          2. Optymalizacja
        4. Algorytmy pokrewne
      3. Dopasowanie obustronne
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
        2. Rozwiązanie
        3. Analiza
      4. Uwagi na temat ścieżek powiększających
      5. Przepływ o minimalnym koszcie
      6. Przeładunek
        1. Rozwiązanie
        2. Przewozy
        3. Rozwiązanie
      7. Przydział zadań
        1. Rozwiązanie
      8. Programowanie liniowe
      9. Literatura
    6. 9. Geometria obliczeniowa
      1. Przegląd
        1. Klasyfikacja problemów
          1. Dane wejściowe
          2. Obliczenia
          3. Specyfika zadania
        2. Założenia
        3. Klasyczne problemy geometrii obliczeniowej
          1. Otoczka wypukła
          2. Obliczenia punktów przecięcia odcinków w zbiorze
          3. Odpowiadanie na zapytania o najbliższego sąsiada
          4. Odpowiadanie na zapytania przedziałowe
          5. Podsumowanie
      2. Skanowanie otoczki wypukłej
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenia
        2. Kontekst
        3. Uwarunkowania
        4. Rozwiązanie
        5. Konsekwencje
        6. Analiza
        7. Odmiany
        8. Algorytmy pokrewne
      3. Zamiatanie prostą
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenia
        2. Kontekst
        3. Konieczności
        4. Rozwiązanie
        5. Konsekwencje
        6. Analiza
        7. Odmiany
      4. Pytanie o najbliższych sąsiadów
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenia
        2. Kontekst
        3. Uwarunkowania
        4. Rozwiązanie
        5. Konsekwencje
        6. Analiza
        7. Odmiany
      5. Zapytania przedziałowe
        1. Wejście-wyjście
          1. Wejście
          2. Wyjście
          3. Założenia
        2. Kontekst
        3. Uwarunkowania
        4. Rozwiązanie
        5. Analiza
      6. Literatura
  5. III.
    1. 10. Gdy wszystko inne zawodzi
      1. Wariacje na temat
      2. Algorytmy aproksymacyjne
      3. Algorytmy offline
      4. Algorytmy równoległe
      5. Algorytmy losowe
        1. Ocena rozmiaru zbioru
        2. Oszacowanie rozmiaru drzewa poszukiwań
      6. Algorytmy, które mogą być złe, lecz z malejącym prawdopodobieństwem
        1. Testowanie nierówności baz danych
        2. Dowody z wiedzą zerową
      7. Literatura
    2. 11. Epilog
      1. Przegląd
      2. Zasada: znaj swoje dane
      3. Zasada: podziel problem na mniejsze problemy
      4. Zasada: wybierz właściwą strukturę
      5. Zasada: dodaj pamięci, aby zwiększyć efektywność
      6. Zasada: jeśli nie widać rozwiązania, skonstruuj przeszukanie
      7. Zasada: jeśli nie widać rozwiązania, zredukuj problem do takiego, który ma rozwiązanie
      8. Zasada: pisanie algorytmów jest trudne, testowanie — trudniejsze
  6. IV.
    1. A. Testy wzorcowe
      1. Podstawy statystyczne
      2. Sprzęt
      3. Przykład
        1. Rozwiązania testów wzorcowych w Javie
        2. Linuksowe rozwiązania testów wzorcowych
        3. Rozwiązania testów porównawczych w języku Scheme
      4. Raportowanie
      5. Dokładność
    2. B. O autorach
  7. Indeks
  8. About the Authors
  9. Kolofon
  10. Copyright