ALGORYTMY W PYTHONIE TECHNIKI PROGRAMOWANIA DLA PRAKTYKÓW

Przedmowa

• Przykładowe programy w Pythonie
• Co odróżnia tę książkę od innych podręczników?
• Jak należy czytać tę książkę?
• Co zostało opisane w tej książce?
• Konwencje typograficzne i oznaczenia

Rozdział 1. Zanim wystartujemy

• Czym powinien się charakteryzować algorytm?
• Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych
• Jak to się niedawno odbyło, czyli o tym, kto wymyślił metodologię programowania
• Proces koncepcji programów
• Poziomy abstrakcji opisu i wybór języka
• Maszyna Turinga
• Modelowanie i realizacja algorytmów
  • Schematy blokowe
  • Przetwarzanie danych – operatory
  • Grupowanie fragmentów kodu w funkcje
  • Pobieranie lub wyświetlanie wartości
  • Iteracyjne wykonywanie kodu
  • Operatory logiczne
• Poprawność algorytmów
• Zadania
• Rozwiązania i wskazówki do zadań

Rozdział 2. Systemy obliczeniowe i podstawy kodowania

• Systemy pozycyjne w pigułce
• System dwójkowy
• System szesnastkowy
• System ósemkowy
• Operacje arytmetyczne na liczbach dwójkowych
• Kod BCD
• Kodowanie liczb ze znakiem
  • Kod znak-moduł (ZM)
  • Kod U2 (system uzupełnienia dwójkowego)
• Zmienne w pamięci komputera
• Kodowanie znaków
• Kodowanie obrazów
  • Mapy bitowe na przykładzie formatu BMP

Rozdział 3. Rekurencja

• Definicja rekurencji
• Ilustracja pojęcia rekurencji
• Jak wykonują się programy rekurencyjne?
• Niebezpieczeństwa rekurencji
  • Ciąg Fibonacciego
  • Stack overflow!
• Pułapek ciąg dalszy
  • Stąd do wieczności
  • Definicja poprawna, ale.
• Typy programów rekurencyjnych
• Myślenie rekurencyjne
  • Przykład 1. Spirala
  • Przykład 2. Kwadraty „parzyste”
• Przeszukiwanie binarne
• Uwagi praktyczne na temat technik rekurencyjnych
• Zadania
• Rozwiązania i wskazówki do zadań

Rozdział 4. Analiza złożoności algorytmów

• Definicje i przykłady
  • Jeszcze raz funkcja silnia
  • Wyszukiwanie wspólnego elementu w kolekcjach
  • Zerowanie fragmentu tablicy
  • Wpadamy w pułapkę
  • Różne typy złożoności obliczeniowej
• Nowe zadanie: uprościć obliczenia!
• Analiza programów rekurencyjnych
  • Terminologia i definicje
  • Ilustracja metody na przykładzie
  • Rozkład logarytmiczny
  • Przeszukiwanie binarne. tym razem bez matematyki wyższej!
  • Zamiana dziedziny równania rekurencyjnego
  • Funkcja Ackermanna, czyli coś dla smakoszy
• Złożoność obliczeniowa to nie religia!
• Techniki optymalizacji programów
• Trochę praktyki: pomiary czasów wykonania
• Zadania
• Rozwiązania i wskazówki do zadań

Rozdział 5. Typy proste wbudowane

• Zmienne (nie zawsze) proste
  • Typy proste
  • Stałe symboliczne
  • Pojęcie referencji
  • Zasięg zmiennych
  • Napis niezmienny jest i basta!
  • Konwersje napisów na liczby (i odwrotnie)
• Formatowanie wyników z użyciem notacji f”
• Tablice (nie całkiem) klasyczne
  • Inicjalizacja tablic o stałym wymiarze
• Tuple (czasem zwane krotkami)
  • Modyfikacja tupli
  • Zastosowania programistyczne

Rozdział 6. Modelowanie abstrakcyjnych struktur danych

• Szablon nowej struktury danych
• Dokładamy logikę biznesową
  • Błędne użycie obiektów klasy i wyjątki
• Przeciążanie operatorów arytmetycznych
• Poszerzanie definicji modelu danych
• Rekurencyjne struktury danych
• Pułapki OOP w Pythonie

Rozdział 7. Przykładowe realizacje wybranych struktur danych

• Listy jednokierunkowe
• „Tablicowa” implementacja list
• Listy innych typów
• Listy z iteratorem
• Zbiory
• Modelowanie kolekcji – podsumowanie

Rozdział 8. Typy złożone wbudowane

• Listy, czyli tablice dynamiczne
  • Metody dostępne dla list w Pythonie
  • Listy tworzone na podstawie wyrażeń
• Zbiory
  • Zbiory tworzone na podstawie wyrażeń
• Słowniki
• Szybkie tablice NumPy
  • Instalacja
  • N-wymiarowe tablice NumPy
  • Tablice i macierze NumPy
  • Deklarowanie tablic i macierzy NumPy
  • Funkcje tablicowe NumPy
  • Zmiany układu i rozmiaru tablic NumPy
• Wycinki w tablicach

Rozdział 9. Struktury danych o dostępie ograniczonym

• Stos
  • Zasada działania stosu
  • Realizacja programowa stosu
  • Sprawdzanie typu danych obiektu
• Kolejki FIFO
• Sterty i kolejki priorytetowe
  • Sortowanie za pomocą sterty

Rozdział 10. Drzewa i ich reprezentacje

• Binarne drzewa poszukiwań (BST)
• Drzewa binarne i wyrażenia arytmetyczne
• Uniwersalna struktura słownikowa
  • Zajętość pamięci słownika
  • Drzewa „egzotyczne”

Rozdział 11. Algorytmy przeszukiwania

• Przeszukiwanie liniowe
• Generyczne funkcje porównawcze
• Przeszukiwanie binarne
• Transformacja kluczowa (hashing)
  • W poszukiwaniu funkcji H()
  • Najbardziej znane funkcje H()
  • Obsługa konfliktów dostępu
  • Powrót do źródeł
  • Jeszcze raz tablice!
  • Próbkowanie liniowe
  • Podwójne kluczowanie
  • Zastosowania transformacji kluczowej
  • Klasyczne funkcje hashujące
  • Piszemy własną tablicę hashującą
• Podsumowanie metod transformacji kluczowej
• Przeszukiwanie danych w wybranych strukturach Pythona

Rozdział 12. Algorytmy sortowania

• Sortowanie przez wstawianie, algorytm klasy O(N2)
• Sortowanie bąbelkowe, algorytm klasy O(N2)
• Sortowanie szybkie (Quicksort) – algorytm klasy O(N log N)
• Scalanie zbiorów posortowanych
• Sortowanie przez scalanie, algorytm klasy O(N log N)
• Sortowanie zewnętrzne
• Sortowanie z użyciem bibliotek Pythona
• Uwagi praktyczne

Rozdział 13. Derekursywacja i optymalizacja algorytmów

• Jak pracuje kompilator?
• Odrobina formalizmu nie zaszkodzi!
• Kilka przykładów derekursywacji algorytmów
• Derekursywacja z wykorzystaniem stosu
  • Eliminacja zmiennych lokalnych
• Metoda funkcji przeciwnych
• Klasyczne schematy derekursywacji
  • Schemat typu while
  • Schemat typu if-else
  • Schemat z podwójnym wywołaniem rekurencyjnym
• Podsumowanie

Rozdział 14. Przeszukiwanie tekstów

• Algorytm typu brute force
• Nowe algorytmy poszukiwań
  • Algorytm KMP
  • Algorytm Boyera-Moore’a
  • Algorytm Rabina-Karpa
• Kilka prostych zadań
  • Rozwiązania

Rozdział 15. Zaawansowane techniki programowania

• Programowanie typu „dziel i zwyciężaj”
  • Znajdowanie minimum i maksimum w tablicy liczb
  • Mnożenie macierzy o rozmiarze NxN
  • Mnożenie liczb całkowitych
  • Inne znane algorytmy „dziel i zwyciężaj”
• Algorytmy „żarłoczne”, czyli przekąsić coś nadszedł już czas.
  • Problem plecakowy, czyli niełatwe jest życie turysty piechura
  • Wydawanie reszty, czyli „A nie ma pan drobnych?” w praktyce
• Programowanie dynamiczne
  • Ciąg Fibonacciego
  • Równania z wieloma zmiennymi
  • Najdłuższa wspólna podsekwencja
  • Najdłuższy wspólny podłańcuch
• Heurystyki i inne techniki programowania
• Uwagi bibliograficzne

Rozdział 16. Algorytmy grafowe

• Definicje i pojęcia podstawowe
  • Etykiety i wartości
• Cykle w grafach
• Sposoby reprezentacji grafów
  • Reprezentacja tablicowa
  • Słowniki węzłów
  • Listy kontra zbiory
• Podstawowe operacje na grafach
  • Suma grafów
  • Kompozycja grafów
  • Graf do potęgi
• Algorytm Warshalla
• Algorytm Floyda-Warshalla
• Algorytm Dijkstry
• Algorytm Bellmana-Forda
• Drzewo rozpinające minimalne
  • Algorytm Kruskala
  • Algorytm Prima
• Przeszukiwanie grafów
  • Strategia „w głąb” (przeszukiwanie zstępujące)
  • Strategia „wszerz”
  • Inne strategie przeszukiwania
• Problem właściwego doboru
• Podsumowanie

Rozdział 17. Matematyka i Python

• Biblioteki naukowe dla Pythona
• Klasyczne funkcje i metody matematyczne
• Funkcje matematyczne NumPy
• Poszukiwanie miejsc zerowych funkcji
• Iteracyjne obliczanie wartości funkcji
• Interpolacja funkcji metodą Lagrange’a
  • Różniczkowanie funkcji
• Całkowanie funkcji metodą Simpsona
• Rozwiązywanie układów równań liniowych metodą Gaussa
• Uwagi końcowe
• Wizualizacja danych z użyciem Matplotlib
  • Instalacja pakietu
  • Pierwszy wykres
  • Modyfikacje wyglądu wykresu
  • Wykresy statystyczne

Rozdział 18. Kodowanie i kompresja danych

• Kodowanie danych i arytmetyka dużych liczb
  • Metody prymitywne
  • Kodowanie symetryczne
  • Kodowanie asymetryczne
  • Kodowanie Base64
• Obliczenia na bardzo dużych liczbach całkowitych
  • Reprezentacja dużych liczb całkowitych
  • Wyliczanie wartości modulo
• Wybrane techniki łamania kodów
  • Jakość klucza szyfrującego
  • Metody łamania szyfrów
• Techniki kompresji danych
  • Kompresja za pomocą modelowania matematycznego
  • Kompresja metodą RLE
  • Kompresja danych metodą Huffmana
  • Kodowanie LZW

Rozdział 19. Czy komputery mogą myśleć.?

• Przegląd obszarów zainteresowań sztucznej inteligencji (SI)
  • Systemy eksperckie
  • Sieci neuronowe
• Reprezentacja problemów
• Gry dwuosobowe i drzewa gier
  • Algorytm min-max

Dodatek A. Python – lokalne środowisko pracy

• Testujemy poprawność instalacji Pythona
• Instalator pip i biblioteki Pythona
• Edytory do Pythona
• Środowiska IDE (i dlaczego PyCharm)
  • IDLE
  • PyCharm
  • Visual Studio Community
• Dokumentacja Pythona
• Używanie zasobów GitHuba

Literatura

Spis rysunków

Spis tabel

Skorowidz