MYŚLENIE ALGORYTMICZNE JAK ROZWIĄZYWAĆ PROBLEMY ZA POMOCĄ ALGORYTMÓW

Spis treści
Przedmowa

Podziękowania

Wprowadzenie

1. Tablice mieszające

Problem 1.: Płatki śniegu
Problem
Uproszczenie problemu
Rozwiązywanie podstawowego problemu
Rozwiązanie 1.: Porównywanie parami
Rozwiązanie 2.: Zmniejszenie liczby wykonywanych operacji
Tablice mieszające
Projekt tablicy mieszającej
Dlaczego warto używać tablic mieszających?
Problem 2.: Chaos w hasłach
Problem
Rozwiązanie 1.: Sprawdzanie wszystkich haseł
Rozwiązanie 2.: Użycie tablicy mieszającej
Problem 3.: Sprawdzanie pisowni – usuwanie litery
Problem
Rozważania o zastosowaniu tablic mieszających
Rozwiązanie doraźne
Podsumowanie
Uwagi

2. Drzewa i rekurencja

Problem 1.: Halloweenowy łup
Problem
Drzewa binarne
Rozwiązywanie problemu dla przykładowego drzewa
Reprezentacja drzew binarnych
Zbieranie wszystkich cukierków
Zupełnie inne rozwiązanie
Przechodzenie minimalnej liczby ulic
Odczyt danych wejściowych
Dlaczego korzystać z rekurencji?
Problem 2.: Odległość pomiędzy potomkami
Problem
Odczyt danych wejściowych
Liczba potomków w odległości d od wierzchołka
Liczba potomków dla wszystkich wierzchołków
Sortowanie wierzchołków
Wyświetlanie wyników
Funkcja main
Podsumowanie
Uwagi

3. Memoizacja i programowanie dynamiczne

Problem 1.: Burgerowa gorączka
Problem
Określenie planu rozwiązania problemu
Określanie optymalnego rozwiązania
Rozwiązanie 1.: Zastosowanie rekurencji
Rozwiązanie 2.: Memoizacja
Rozwiązanie 3.: Programowanie dynamiczne
Memoizacja i programowanie dynamiczne
Krok 1.: Struktura optymalnego rozwiązania
Krok 2.: Rozwiązanie rekurencyjne
Krok 3.: Memoizacja
Krok 4.: Programowanie dynamiczne
Problem 2.: Skąpcy
Problem
Określanie optymalnego rozwiązania
Rozwiązanie 1.: Rekurencja
Funkcja main
Rozwiązanie 2.: Memoizacja
Problem 3.: Rywalizacja hokejowa
Problem
Rozważania dotyczące rywalizacji
Określenie optymalnego rozwiązania
Rozwiązanie 1.: Rekurencja
Rozwiązanie 2.: Memoizacja
Rozwiązanie 3.: Programowanie dynamiczne
Optymalizacja zużycia pamięci
Podsumowanie
Uwagi

4. Zaawansowana memoizacja i programowanie dynamiczne

Problem 1.: Skoczek
Problem
Analiza przykładu
Rozwiązanie 1.: Analiza wstecz
Rozwiązanie 2.: Analiza w przód
Problem 2.: Sposoby budowy
Problem
Analiza przykładu
Rozwiązanie 1.: Stosowanie „dokładnych” podproblemów
Rozwiązanie 2.: Dodawanie kolejnych podproblemów
Podsumowanie
Uwagi

5. Grafy i przeszukiwanie wszerz

Problem 1.: Pogoń skoczka
Problem
Optymalne ruchy skoczka
Najlepszy wynik skoczka
Przesunięcie i powrót skoczka
Optymalizacja czasu działania
Grafy i przeszukiwanie wszerz
Czym są grafy?
Grafy a drzewa
Algorytm BFS na grafach
Grafy a programowanie dynamiczne
Problem 2.: Wspinaczka po linie
Problem
Rozwiązanie 1.: Poszukiwanie ruchów
Rozwiązanie 2.: Nowy model
Problem 3.: Tłumaczenie książek
Problem
Wczytywanie nazw języków
Budowanie grafu
Implementacja algorytmu BFS
Koszt całkowity
Podsumowanie
Uwagi

6. Najkrótsze ścieżki na grafach ważonych

Problem 1.: Myszy w labiryncie
Problem
Zostawiamy algorytm BFS
Znajdowanie najkrótszej ścieżki na grafach ważonych
Tworzenie grafu
Implementacja algorytmu Dijkstry
Dwie optymalizacje
Algorytm Dijkstry
Efektywność działania algorytmu Dijkstry
Krawędzie o wagach ujemnych
Problem 2.: Planowanie odwiedzin u babci
Problem
Macierz sąsiedztwa
Konstruowanie grafu
Analiza przypadku testowego dziwacznych ścieżek
Zadanie 1.: Najkrótsze ścieżki
Zadanie 2.: Liczba najkrótszych ścieżek
Podsumowanie
Uwagi

7. Wyszukiwanie binarne

Problem 1.: Karmienie mrówek
Problem
Nowy rodzaj problemów z drzewami
Wczytywanie danych wejściowych
Sprawdzanie wykonalności
Poszukiwanie rozwiązania
Wyszukiwanie binarne
Wydajność działania algorytmu wyszukiwania binarnego
Określanie wykonalności
Przeszukiwanie tablicy posortowanej
Problem 2.: Skok przez rzekę
Problem
Koncepcja zachłanności
Testowanie wykonalności
Poszukiwanie rozwiązania
Wczytywanie danych wejściowych
Problem 3.: Jakość życia
Problem
Sortowanie wszystkich prostokątów
Wyszukiwanie binarne
Sprawdzanie wykonalności
Szybsze sprawdzanie wykonalności
Problem 4.: Drzwi w jaskini
Problem
Rozwiązywanie podzadań
Zastosowanie wyszukiwania liniowego
Stosowanie wyszukiwania binarnego
Podsumowanie
Uwagi

8. Kopce i drzewa segmentów

Problem 1.: Promocja w supermarkecie
Problem
Rozwiązanie 1.: Wartość maksymalna i minimalna w tablicy
Kopce maksymalne
Kopce minimalne
Rozwiązanie 2.: Kopce
Kopce
Inne zastosowania
Wybór struktury danych
Problem 2.: Budowanie drzewców
Problem
Rekurencyjne wyświetlanie drzewców
Sortowanie na podstawie etykiet
Rozwiązanie 1.: Rekurencja
Pytania o sumę zakresu
Drzewa segmentów
Rozwiązanie 2.: Drzewa segmentów
Drzewa segmentów
Problem 3.: Suma dwóch
Problem
Wypełnianie drzewa segmentów
Znajdowanie odpowiedzi z użyciem drzewa segmentów
Aktualizacja drzewa segmentów
Funkcja main
Podsumowanie
Uwagi

9. Struktura zbiorów rozłącznych

Problem 1.: Sieć społecznościowa
Problem
Modelowanie danych w formie grafu
Rozwiązanie 1.: BFS
Struktura zbiorów rozłącznych
Rozwiązanie 2.: Struktura zbiorów rozłącznych
Optymalizacja 1.: Łączenie na podstawie wielkości
Optymalizacja 2.: Skracanie ścieżek
Struktura zbiorów rozłącznych
Relacje: Trzy wymagania
Wybieranie struktury zbiorów rozłącznych
Optymalizacje
Problem 2.: Przyjaciele i wrogowie
Problem
Rozszerzenie: Struktura zbiorów rozłącznych
Funkcja main
Operacje find i union
Operacje UstawJakoPrzyjaciół i UstawJakoWrogów
Operacje CzySąPrzyjaciółmi i CzySąWrogami
Problem 3.: Kłopot z szufladami
Problem
Równoważne szuflady
Funkcja main
Implementacja operacji find i union
Podsumowanie
Uwagi

10. Randomizacja

Problem 1.: Yokan
Problem
Losowy wybór kawałka
Generowanie liczb losowych
Określanie liczby kawałków
Odgadywanie smaków
Ilu prób potrzebujemy?
Wypełnianie tablic smaków
Funkcja main
Randomizacja
Algorytmy typu Monte Carlo
Algorytmy typu Las Vegas
Algorytmy deterministyczne a probabilistyczne
Problem 2.: Kapsle i butelki
Problem
Rozwiązywanie podzadania
Rozwiązanie 1.: Rekurencja
Rozwiązanie 2.: Dodanie randomizacji
Sortowanie szybkie
Implementacja algorytmu sortowania szybkiego
Efektywność najgorszego przypadku i oczekiwana
Podsumowanie
Uwagi

Podsumowanie

A. Efektywność algorytmów

Kwestia czasu. i nie tylko
Notacja dużego O
Czas liniowy
Czas stały
Inny przykład
Czas kwadratowy
Notacja dużego O w tej książce

B. Ponieważ nie mogłem się powstrzymać

Płatki śniegu: niejawne listy połączone
Burgerowa gorączka: rekonstrukcja rozwiązania
Pogoń skoczka: kodowanie ruchów
Algorytm Dijkstry: stosowanie kopca
Myszy w labiryncie: śledzenie z użyciem kopców
Myszy w labiryncie: implementacja z użyciem kopca
Skracanie skracania ścieżek
Krok 1.: Żadnych więcej operatorów trójargumentowych
Krok 2.: Bardziej czytelne operatory przypisania
Krok 3.: Wyjaśnienie rekurencji
Kapsle i butelki: sortowanie w miejscu

C. Z podziękowaniem za problemy