Algorytmy w Pythonie. Techniki programowania dla praktyk - Helion

Autor: Piotr Wr
ISBN: 978-83-283-9368-4
okładka: mi
Księgarnia: Helion

Książka będzie dostępna od maja 2022

Zobacz także »

Zobacz także:

Windows Media Center. Domowe centrum rozrywki 66,67 zł, (8,00 zł -88%)
Ruby on Rails. Ćwiczenia 18,75 zł, (3,00 zł -84%)
Przywództwo w świecie VUCA. Jak być skutecznym liderem w niepewnym środowisku 58,64 zł, (12,90 zł -78%)
Scrum. O zwinnym zarządzaniu projektami. Wydanie II rozszerzone 58,64 zł, (12,90 zł -78%)
Od hierarchii do turkusu, czyli jak zarządzać w XXI wieku 58,64 zł, (12,90 zł -78%)

Spis treści

Algorytmy w Pythonie. Techniki programowania dla praktyków -- spis treści

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