NAUKA ALGORYTMÓW PORADNIK PISANIA LEPSZEGO KODU

Przedmowa

Wprowadzenie

• Dla kogo przeznaczona jest ta książka?
• O kodzie
• Konwencje używane w tej książce
• Podziękowania

1. Rozwiązywanie problemów

• Czym jest algorytm?
• Znajdowanie największej wartości w dowolnej liście
• Zliczanie kluczowych operacji
• Modele pozwalają prognozować wydajność algorytmu
• Znajdowanie dwóch największych wartości na dowolnej liście
• Algorytm pucharowy
• Złożoność czasowa i pamięciowa
• Podsumowanie
• Ćwiczenia

2. Analiza algorytmów

• Używanie modeli empirycznych do prognozowania wydajności
• Mnożenie można wykonywać szybciej
• Klasy złożoności
• Analiza asymptotyczna
• Zliczanie wszystkich operacji
• Zliczanie wszystkich bajtów
• Gdy zamykają się jedne drzwi, otwierają się inne
• Wyszukiwanie binarne w tablicy
• Prawie tak łatwe jak ?
• Dwie pieczenie na jednym ogniu
• Łączenie wszystkich elementów
• Dopasowywanie do krzywej a dolna i górna granica
• Podsumowanie
• Ćwiczenia

3. Lepsze życie dzięki lepszemu haszowaniu

• Łączenie wartości z kluczami
• Funkcje haszujące i skróty
• Tablica z haszowaniem dla par (klucz, wartość)
• Wykrywanie i rozwiązywanie kolizji za pomocą próbkowania liniowego
• Tworzenie odrębnych łańcuchów dzięki listom powiązanym
• Usuwanie elementu z listy powiązanej
• Ocena wydajności
• Zwiększanie rozmiaru tablic z haszowaniem
• Analiza wydajności dynamicznych tablic z haszowaniem
• Haszowanie doskonałe
• Iteracyjne pobieranie par (klucz, wartość)
• Podsumowanie
• Ćwiczenia

4. Wędrówka po kopcu

• Kopce binarne typu max
• Wstawianie elementu (wartość, priorytet)
• Usuwanie wartości o najwyższym priorytecie
• Reprezentowanie kopca binarnego za pomocą tablicy
• Implementacja „wypływania” i „zatapiania”
• Podsumowanie
• Ćwiczenia

5. Sortowanie bez tajemnic

• Sortowanie przez przestawianie
• Sortowanie przez wybieranie
• Budowa algorytmu sortowania o złożoności kwadratowej
• Analizowanie wydajności sortowania przez wstawianie i sortowania przez wybieranie
• Rekurencja oraz podejście dziel i rządź
• Sortowanie przez scalanie
• Sortowanie szybkie
• Sortowanie przez kopcowanie
• Porównanie wydajności algorytmów o złożoności O(N log N)
• Algorytm timsort
• Podsumowanie
• Ćwiczenie

6. Drzewa binarne – nieskończoność na wyciągnięcie ręki

• Wprowadzenie
• Binarne drzewa poszukiwań
• Szukanie wartości w binarnym drzewie poszukiwań
• Usuwanie wartości z binarnego drzewa poszukiwań
• Przechodzenie drzewa binarnego
• Analiza wydajności binarnych drzew poszukiwań
• Samoorganizujące się drzewa binarne
• Analiza wydajności drzew samoorganizujących się
• Używanie drzewa binarnego jako tablicy symboli (klucz, wartość)
• Używanie drzewa binarnego jako kolejki priorytetowej
• Podsumowanie
• Ćwiczenia

7. Grafy – połącz punkty

• Grafy służą do wydajnego zapisywania przydatnych informacji
• Znajdowanie drogi w labiryncie za pomocą przeszukiwania w głąb
• Inna strategia – przeszukiwanie wszerz
• Grafy skierowane
• Grafy z wagami krawędzi
• Algorytm Dijkstry
• Najkrótsze ścieżki dla wszystkich par
• Algorytm Floyda-Warshalla
• Podsumowanie
• Ćwiczenia

8. Podsumowanie

• Wbudowane typy Pythona
• Implementowanie stosu w Pythonie
• Implementowanie kolejek w Pythonie
• Implementacje kopca i kolejki priorytetowej
• Dalsza nauka

O autorach