Warunkiem poprawnego dzia

Zobacz także:

• Python na maturze. Kurs video. Algorytmy i podstawy j 139,00 zł, (62,55 zł -55%)
• Algorytmy kryptograficzne. Przewodnik po algorytmach w blockchain, kryptografii kwantowej, protoko 79,00 zł, (39,50 zł -50%)
• Algorytmy 78,11 zł, (41,40 zł -47%)
• 20 algorytm 126,70 zł, (70,95 zł -44%)
• Algorytmy 78,68 zł, (44,85 zł -43%)

Spis treści

Myślenie algorytmiczne. Jak rozwiązywać problemy za pomocą algorytmów. Wydanie II eBook -- 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