Dane oryginału

Original edition copyright © 2019 by Manning Publications Co. All rights reserved. Title of English-language original: Classic Computer Science Problems in Python by David Kopec, ISBN 978-1-61729-598-0. Polish-language edition © 2020 by Polish Scientific Publishers PWN Wydawnictwo Naukowe PWN Spółka Akcyjna.

All Rights reserved.

Przekład Natalia Chounlamany-Turalska na zlecenie WITKOM Witold Sikorski

Projekt okładki polskiego wydania INT-MEDIA Dawid Mazur

Wydawca Wioleta Szczygielska-Dybciak

Redaktor prowadzący Jolanta Kowalczuk

Redaktor Irena Puchalska

Koordynator produkcji Anna Bączkowska

Skład wersji elektronicznej na zlecenie Wydawnictwa Naukowego PWN: Marcin Kośka/Woblink

Zastrzeżonych nazw firm i produktów użyto w książce wyłącznie w celu identyfikacji.

Książka, którą nabyłeś, jest dziełem twórcy i wydawcy. Prosimy, abyś przestrzegał praw, jakie im przysługują. Jej zawartość możesz udostępnić nieodpłatnie osobom bliskim lub osobiście znanym. Ale nie publikuj jej w internecie. Jeśli cytujesz jej fragmenty nie zmieniaj ich treści i koniecznie zaznacz, czyje to dzieło. A kopiując jej część, rób to jedynie na użytek osobisty.

Szanujmy cudzą własność i prawo

Więcej na www.legalnakultura.pl

Polska Izba Książki

Copyright © for the Polish edition by Wydawnictwo Naukowe PWN SA

Warszawa 2020

ISBN 978-83-01-20993-3

eBook został przygotowany na podstawie wydania papierowego z 2020 r., (wyd. I)
Warszawa 2020

Wydawnictwo Naukowe PWN SA

02-460 Warszawa, ul. Gottlieba Daimlera 2

tel. 22 69 54 321, faks 22 69 54 288

infolinia 801 33 33 88

e-mail: pwn@pwn.com.pl, reklama@pwn.pl

www.pwn.pl

Dla mojej babci, Erminii Antos,
która cała życie się uczyła i nauczała

Spis treści

podziękowania

o autorze

o ilustracji na okładce

wprowadzenie

1. Małe problemy

1.1. Ciąg Fibonacciego

1.1.1. Pierwsza próba rekurencyjna

1.1.2. Wykorzystywanie przypadków podstawowych

1.1.3. Memoizacja na ratunek

1.1.4. Memoizacja automatyczna

1.1.5. Uproszczony Fibonacci

1.1.6. Generowanie liczb Fibonacciego za pomocą generatora

1.2. Trywialna kompresja

1.3. Szyfr nie do złamania

1.3.1. Przygotowywanie danych

1.3.2. Szyfrowanie i deszyfrowanie

1.4. Wyznaczanie liczby pi

1.5. Wieże Hanoi

1.5.1. Modelowanie wież

1.5.2. Rozwiązywanie problemu wież Hanoi

1.6. Praktyczne zastosowania

1.7. Ćwiczenia

2. Problemy wyszukiwania

2.1. Przeszukiwanie DNA

2.1.1. Przechowywanie DNA

2.1.2. Przeszukiwanie liniowe

2.1.3. Wyszukiwanie binarne

2.1.4. Uogólniony przykład

2.2. Rozwiązywanie labiryntów

2.2.1. Generowanie losowego labiryntu

2.2.2. Detale labiryntu

2.2.3. Przeszukiwanie w głąb

2.2.4. Przeszukiwanie wszerz

2.2.5. Algorytm A*

2.3. Misjonarze i kanibale

2.3.1. Modelowanie problemu

2.3.2. Rozwiązywanie problemu

2.4. Praktyczne zastosowania

2.5. Ćwiczenia

3. Problemy spełniania ograniczeń

3.1. Budowanie systemu do rozwiązywania problemów spełniania ograniczeń

3.2. Problem kolorowania mapy Australii

3.3. Problem ośmiu hetmanów

3.4. Wykreślanki

3.5. SEND + MORE = MONEY

3.6. Układ chipów na płytce

3.7. Praktyczne zastosowania

3.8. Ćwiczenia

4. Problemy grafowe

4.1. Mapa jako graf

4.2. Budowanie szkieletu grafu

4.2.1. Stosowanie klas Edge i Graph

4.3. Znajdowanie najkrótszej drogi

4.3.1. Powrót do przeszukiwania wszerz (BFS)

4.4. Minimalizowanie kosztu budowania sieci

4.4.1. Stosowanie wag

4.4.2. Znajdowanie minimalnego drzewa rozpinającego

4.5. Znajdowanie najkrótszych dróg w grafie z wagami

4.5.1. Algorytm Dijkstry

4.6. Praktyczne zastosowania

4.7. Ćwiczenia

5. Algorytmy genetyczne

5.1. Podstawy biologiczne

5.2. Generyczny algorytm genetyczny

5.3. Naiwny test

5.4. SEND + MORE = MONEY – ciąg dalszy

5.5. Optymalizowanie kompresji list

5.6. Wyzwania związane z algorytmami genetycznymi

5.7. Praktyczne zastosowania

5.8. Ćwiczenia

6. Algorytm klasteryzacji

6.1. Przygotowania

6.2. Algorytm klasteryzacji metodą k-średnich

6.3. Klasteryzacja gubernatorów według wieku i długości geograficznej

6.4. Klasteryzacja albumów Michaela Jacksona według długości

6.5. Problemy i rozszerzenia algorytmu klasteryzacji metodą k-średnich

6.6. Praktyczne zastosowania

6.7. Ćwiczenia

7. Dość proste sieci neuronowe

7.1. Podłoże biologiczne?

7.2. Sztuczne sieci neuronowe

7.2.1. Neurony

7.2.2. Warstwy

7.2.3. Propagacja wsteczna

7.2.4. Pełen obraz

7.3. Przygotowania

7.3.1. Iloczyn skalarny

7.3.2. Funkcja aktywacji

7.4. Budowanie sieci

7.4.1. Implementowanie neuronów

7.4.2. Implementowanie warstw

7.4.3. Implementowanie sieci

7.5. Problemy klasyfikacji

7.5.1. Normalizowanie danych

7.5.2. Klasyczny zbiór danych iris

7.5.3. Klasyfikowanie wina

7.6. Przyspieszanie sieci neuronowych

7.7. Problemy i rozszerzenia sieci neuronowych

7.8. Praktyczne zastosowania

7.9. Ćwiczenia

8. Przeszukiwanie z przeciwnikiem

8.1. Podstawowe elementy gry planszowej

8.2. Kółko i krzyżyk

8.2.1. Zarządzanie stanem gry kółko i krzyżyk

8.2.2. Minimax

8.2.3. Testowanie funkcji minimax na grze kółko i krzyżyk

8.2.4. Rozwijanie sztucznej inteligencji w grze kółko i krzyżyk

8.3. Connect 4

8.3.1. Mechanizm gry Connect 4

8.3.2. Sztuczna inteligencja w grze Connect 4

8.3.3. Poprawianie algorytmu minimax przez redukcję alfa-beta

8.4. Inne ulepszenia algorytmu minimax

8.5. Praktyczne zastosowania

8.6. Ćwiczenia

9. Inne problemy

9.1. Problem plecakowy

9.2. Problem komiwojażera

9.2.1. Naiwne podejście

9.2.2. Możliwości ulepszenia projektu

9.3. Mnemotechniki dla numerów telefonów

9.4. Praktyczne zastosowania

9.5. Ćwiczenia

dodatek A Glosariusz

dodatek B Dodatkowe materiały

B.1. Python

B.2. Algorytmy i struktury danych

B.3. Sztuczna inteligencja

B.4. Programowanie funkcyjne

B.5. Projekty open source pomocne w uczeniu maszynowym

dodatek C Krótkie wprowadzenie do adnotacji typów

C.1. Czym są adnotacje typów?

C.2. Jak wyglądają adnotacje typów?

C.3. Do czego przydają się adnotacje typów?

C.4. Jakie są wady adnotacji typów?

C.5. Zdobywanie dodatkowych informacji

przypisy

podziękowania

Dziękuję wszystkim pracownikom wydawnictwa Manning, którzy przyczynili się do powstania tej książki: Cheryl Weisman, Deirdre Hiam, Katie Tennant, Dottie Marsico, Janet Vail, Barbarze Mireckiej, Aleksandarowi Dragosavljević, Mary Piergies i Mariji Tudor.

Dziękuję redaktorowi zamawiającemu Brianowi Sawyerowi, który roztropnie zwrócił moją uwagę na Pythona, gdy skończyłem książkę o Swifcie. Dziękuję redaktor ds. rozwoju Jennifer Stout za niezmiennie pozytywne nastawienie i redaktor technicznej Frances Buontempo, która dokładnie przeanalizowała każdy rozdział i cały czas przekazywała szczegółowe, przydatne uwagi. Dziękuję korektorowi Andiemu Carrollowi, którego doskonała dbałość o szczegóły zarówno podczas pracy nad książką o Swifcie, jak i tą książką zaowocowała wyłapaniem wielu błędów, za co dziękuję również korektorowi technicznemu – Juanowi Rufesowi.

Książka została również zrecenzowana przez: Ala Krinkera, Ala Pezewskiego, Alana Bogusiewicza, Briana Canada, Craiga Hendersona, Daniela Kenney-Junga, Edmonda Sesaya, Ewę Baranowską, Garego Barnharta, Geoffa Clarka, Jamesa Watsona, Jeffreya Lima, Jensa Christiana, Bredahla Madsena, Juana Jimeneza, Juana Rufesa, Matta Lemke, Mayura Patila, Michaela Brighta, Roberto Casadei, Sama Zaydela, Thorstena Webera, Toma Jeffriesa oraz Willa Lopez. Dziękuję wszystkim osobom, które oferowały konstruktywną i szczegółową krytykę w trakcie powstawania książki. Wasze uwagi zostały uwzględnione.

Dziękuję mojej rodzinie, przyjaciołom i kolegom, którzy zachęcili mnie do rozpoczęcia pracy nad nową książką od razu po opublikowaniu Classic Computer Science Problems in Swift. Dziękuję moim internetowym przyjaciołom z Twittera, i nie tylko, za słowa zachęty i pomoc w wypromowaniu książki na małą i dużą skalę. Dziękuję również mojej żonie Rebecce Kopec i mojej mamie Sylvii Kopec, które zawsze wspierają mnie w realizacji projektów.

Prace nad książką trwały dość krótko. Większość manuskryptu została napisana latem 2018 roku, na podstawie wcześniejszej wersji Swifta. Doceniam to, że wydawnictwo Manning zgodziło się skompresować swój (zwykle dużo dłuższy) proces, dostosowując go do wygodniejszego dla mnie harmonogramu. Wiem, że to spowodowało zwiększenie presji na cały zespół, gdy w ciągu zaledwie kilku miesięcy przechodziliśmy przez trzy serie zbierania uwag od wielu osób na różnych poziomach. Większość czytelników byłaby zaskoczona, wiedząc, przez ile różnych procesów oceniania przechodzą książki techniczne w tradycyjnych wydawnictwach i ile osób jest zaangażowanych w ich krytykowanie i analizowanie. Dziękuję wszystkim, począwszy od redaktora i redaktora technicznego, przez redaktora działu recenzji, po wszystkich oficjalnych recenzentów.

I wreszcie, co najważniejsze, dziękuję moim Czytelnikom za kupienie tej książki. Myślę, że to ważne, aby w świecie wypełnionym niedopracowanymi kursami internetowymi wspierać powstawanie książek, które pozwalają autorom na zaprezentowanie wiedzy w rozszerzonym formacie. Kursy internetowe mogą stanowić doskonałą pomoc, ale Twój zakup sprawia, że w edukacji informatycznej nadal pozostaje miejsce dla gruntownych, zweryfikowanych i starannie opracowanych książek.

o autorze

David Kopec jest adiunktem na Wydziale Informatyki i Innowacji w Champlain College w Burlington, Vermont. Jest doświadczonym programistą i autorem książek Classic Computer Science Problems in Swift (Manning, 2018) oraz Dart for Absolute Beginners (Apress, 2014). David uzyskał tytuł licencjata z ekonomii i magistra z informatyki, oba w Dartmouth College. Można się z nim skontaktować na Twitterze @davekopec.

o ilustracji na okładce

Rysunek na okładce książki Klasyczne problemy informatyki w Pythonie jest podpisany jako Habit buddyjskiego mnicha w Chinach. Ilustracja pochodzi z albumu Thomasa Jefferysa zatytułowanego A Collection of the Dresses of Different Nations, Ancient and Modern (cztery tomy) wydanego w Londynie w latach 1757–1772. Strona tytułowa informuje, że przedstawia on ręcznie kolorowane miedzioryty, uwypuklone przy użyciu gumy arabskiej.

Thomas Jefferys (1719–1771) był nazywany „Geografem króla George’a III”. Był angielskim kartografem, wiodącym dostawcą map. Tworzył ryciny map i drukował je na zlecenie rządu oraz innych organów urzędowych, a ponadto produkował szeroki zakres map i atlasów handlowych, w szczególności dla rejonu Ameryki Północnej. Tworzone przez niego mapy zapoczątkowały zainteresowanie strojami ludowymi z regionów, które badał i kartografował, co doskonale ilustruje ten album. Fascynacja dalekimi lądami i podróżowanie dla przyjemności były pod koniec XVIII wieku dość nowym zjawiskiem, a albumy przedstawiające mieszkańców innych krajów były bardzo popularne nie tylko wśród turystów, ale także osób, którzy wolą nie ruszać się z fotela.

Różnorodność rysunków w wydaniu Jefferysa demonstruje unikatowość i indywidualność różnych narodów około 200 lat temu. Od tego czasu zmienił się sposób ubierania i zmniejszyły się różnice między regionami oraz krajami. Obecnie często trudno jest rozróżnić mieszkańców różnych kontynentów. Być może, patrząc na to optymistycznie, zamieniliśmy różnorodność kulturową i wizualną na bogatsze życie osobiste, bardziej zróżnicowane i interesujące życie intelektualne oraz techniczne.

W czasach, gdy książki komputerowe wyglądają bardzo podobnie, wydawnictwo Manning celebruje nowatorskość i inicjatywę branży informatycznej za pomocą okładek przedstawiających olbrzymią różnorodność regionów sprzed dwustu lat, przywróconą do życia dzięki ilustracjom Jefferysa.

wprowadzenie

Dziękuję za zakup książki Klasyczne problemy informatyki w Pythonie. Python jest jednym z najpopularniejszych języków programowania na świecie, a programiści Pythona wywodzą się z różnych środowisk. Niektórzy mają formalne wykształcenie informatyczne. Inni traktują naukę Pythona tylko jako hobby. Jeszcze inni wykorzystują Pythona w pracy, mimo że nie są programistami. Jest to książka dla średniozaawansowanych i omawiane w niej problemy mają pomóc doświadczonym programistom w odświeżeniu wiedzy ze studiów informatycznych, wprowadzając jednocześnie pewne zaawansowane elementy języka. Osoby, które samodzielnie uczą się programowania, będą mogły przyspieszyć swoją edukację informatyczną, poznając klasyczne problemy w wybranym języku, czyli Pythonie. W książce przedstawiłem tak wiele różnych technik rozwiązywania problemów, że każdy znajdzie w niej coś dla siebie.

Książka nie jest wprowadzeniem do Pythona. Wydawnictwo Manning i inne oferują wiele doskonałych książek z tego zakresu[1]. Natomiast ta książka bazuje na założeniu, że czytelnicy są średniozaawansowanymi lub zaawansowanymi programistami Pythona. Chociaż konieczne jest zainstalowanie wersji Python 3.7, nie jest wymagana biegła znajomość wszystkich funkcji tej najnowszej wersji. Co więcej, książka została opracowana jako materiał szkoleniowy, pomagający czytelnikom w osiągnięciu tej znajomości, aczkolwiek nie jest zalecana dla czytelników, którzy dopiero zaczynają naukę Pythona.

Dlaczego Python?

Python jest wykorzystywany do wielu różnych celów, takich jak m.in. data science, produkcja filmowa, edukacja informatyczna czy zarządzanie infrastrukturą IT. Tak naprawdę nie ma obszaru informatyki, który wykraczałby poza zasięg Pythona (no, może z wyjątkiem rozwijania jądra systemu). Python jest lubiany za elastyczność, piękną i zwięzłą składnię, czystą obiektowość i aktywną społeczność. Silna społeczność jest ważna, ponieważ to dzięki niej Python jest przyjazny dla nowych przybyszów i oferuje duży ekosystem dostępnych bibliotek, na których programiści mogą opierać swoje programy.

Z tych powodów Python jest uważany za język przyjazny dla początkujących i ta opinia jest prawdopodobnie prawdziwa. Większość osób zgodziłaby się, że Python jest łatwiejszy w nauce niż na przykład C++, i jego społeczność jest zdecydowanie przyjaźniej nastawiona do początkujących. Ponieważ Python jest tak przystępny, wiele osób się go uczy i dość szybko zaczyna pisać własne programy. Jednak nie wszyscy mają wykształcenie informatyczne, które pozwala poznać wiele wspaniałych i ogólnie dostępnych technik rozwiązywania problemów. Jeśli jesteś jednym z tych programistów, którzy znają Pythona, ale nie znają informatyki, ta książka jest dla Ciebie.

Programistom z wieloletnim doświadczeniem, którzy poznają Pythona jako kolejny już język programowania, zobaczenie problemów znanych z innego języka pomoże w szybszym nauczeniu się Pythona. Jeśli zaliczasz się do tej kategorii, ta książka może Ci posłużyć jako materiał do odświeżenia wiedzy przed rozmową kwalifikacyjną albo będzie okazją do poznania nowych technik rozwiązywania problemów, które mogą się przydać w codziennej pracy. Zachęcam do przejrzenia spisu treści w poszukiwaniu zagadnień, które mogą Cię zaciekawić.

Jakie są klasyczne problemy informatyki?

Niektórzy mówią, że komputery są dla informatyki tym, czym teleskopy dla astronomii. Jeśli to prawda, to język programowania jest jak soczewki teleskopu. Tak czy owak, termin „klasyczne problemy informatyki” został tu wykorzystany w znaczeniu „problemy programistyczne omawiane zazwyczaj w ramach programu studiów informatycznych”.

Istnieją pewne problemy programistyczne, które daje się do rozwiązania początkującym programistom i które są na tyle powszechnie stosowane, że przeszły do klasyki, zarówno na zajęciach akademickich (z informatyki, programowania itp.), jak i w średniozaawansowanych podręcznikach programistycznych (np. pierwszej książce poświęconej sztucznej inteligencji lub algorytmom). Niniejsza książka zawiera wiele problemów tego typu.

Poziom trudności problemów jest różny – od tych trywialnych, do których rozwiązania wystarczy kilka wierszy kodu, do złożonych, które wymagają rozbudowywania programu w kolejnych rozdziałach. Niektóre problemy zahaczają o sztuczną inteligencję, inne wymagają po prostu zdrowego rozsądku. Niektóre z nich są bardzo praktyczne, a inne nieco wymyślne.

Jakiego typu problemy są omawiane w tej książce?

W rozdziale 1 opisałem techniki rozwiązywania problemów, które są prawdopodobnie znane większości czytelników. Takie mechanizmy, jak rekurencja, memoizacja i pewne przekształcenia są kluczowymi komponentami innych technik prezentowanych w kolejnych rozdziałach.

To łagodne wprowadzenie jest kontynuowane w rozdziale 2, w którym skoncentrowałem się na problemach wyszukiwania. Wyszukiwanie to tak szeroki temat, że większość problemów omawianych w tej książce można zaliczyć do tej kategorii. W rozdziale 2 pojawiają się najważniejsze algorytmy wyszukiwania, takie jak wyszukiwanie binarne, przeszukiwanie wszerz, przeszukiwanie w głąb i A*. Te algorytmy są wykorzystywane w pozostałej części książki.

W rozdziale 3 będziemy budować platformę do rozwiązywania szerokiego zakresu problemów, które można zdefiniować abstrakcyjnie przy użyciu zmiennych o ograniczonych domenach, na które nałożone są ograniczenia. Przedstawione są w nim takie klasyki, jak problem ośmiu hetmanów, problem kolorowania mapy Australii oraz kryptoarytmetyka SEND + MORE = MONEY.

W rozdziale 4 zająłem się algorytmami grafowymi, których szeroki zakres zastosowań może zaskoczyć niewtajemniczonych. W tym rozdziale zbudujemy strukturę danych reprezentującą graf i użyjemy jej do rozwiązywania wielu klasycznych problemów optymalizacji.

W rozdziale 5 przedstawiłem algorytmy genetyczne – technikę, która jest mniej deterministyczna niż większość podanych w tej książce metod, ale czasami rozwiązują one zadania, których tradycyjne algorytmy nie są w stanie rozwiązać w rozsądnym czasie.

Rozdział 6 zawiera omówienie klasteryzacji metodą k-średnich i jest rozdziałem najbardziej koncentrującym się na konkretnych algorytmach. Ta technika klasteryzacji jest łatwa w implementacji i zrozumieniu oraz ma szeroki zakres zastosowań.

W rozdziale 7 podjąłem próbę wytłumaczenia, czym jest sieć neuronowa, i pokazania, jak może wyglądać jej bardzo prosta implementacja. Moim celem nie było szczegółowe omówienie tej ekscytującej i wciąż rozwijającej się dziedziny. W tym rozdziale zbudujemy sieć neuronową od podstaw, bez użycia jakiejś zewnętrznej biblioteki, aby naprawdę zademonstrować działanie sieci neuronowych.

Rozdział 8 jest poświęcony metodom przeszukiwania z przeciwnikiem w grach z dwoma uczestnikami i pełnymi informacjami. Omówiłem w nim algorytm przeszukiwania o nazwie minimax, którego można użyć do rozwijania fikcyjnego przeciwnika umiejącego dobrze grać w takie gry, jak szachy, warcaby czy Connect 4.

Na zakończenie, w rozdziale 9 przedstawiłem ciekawe problemy, które nie za bardzo pasowały do pozostałych rozdziałów książki.

Do kogo kierowana jest ta książka?

Ta książka powstała z myślą zarówno o średniozaawansowanych, jak i doświadczonych programistach. Doświadczeni programiści, którzy chcą pogłębić swoją znajomość Pythona, znajdą w niej zagadnienia dobrze im znane z zajęć informatyki. Średniozaawansowani programiści zaznajomią się z tymi problemami w wybranym przez siebie języku, czyli Pythonie. Programiści przygotowujący się do testów rekrutacyjnych mogą potraktować tę książkę jako cenny materiał pomocniczy.

Książka ta może się przydać nie tylko profesjonalnym programistom, ale także studentom kierunków informatycznych, którzy interesują się Pythonem. Nie jest ona rygorystycznym wprowadzeniem do struktur danych i algorytmów i nie zastąpi podręcznika do struktur danych i algorytmów. Nie zajmuje się dowodami i notacja dużego O rzadko się w niej pojawia. Natomiast zawiera ona przystępne i praktyczne omówienie technik rozwiązywania problemów, które powinno wchodzić w zakres zajęć ze struktur danych, algorytmów i sztucznej inteligencji.

Jak już wspominałem, przyjąłem założenie, że czytelnik zna składnię i semantykę języka Python. Książka nie przyniesie większych korzyści osobom, które nie mają żadnego doświadczenia w programowaniu i będzie trudna do opanowania dla osób, które w ogóle nie znają Pythona. Innymi słowy, Klasyczne problemy informatyki w Pythonie są książką dla zawodowych programistów Pythona i studentów informatyki.

Wersje Pythona, repozytorium kodów źródłowych i adnotacje typów

Kod źródłowy w tej książce został napisany zgodnie z wersją 3.7 języka Python. Wykorzystałem funkcje Pythona wprowadzone dopiero w wersji Python 3.7, dlatego część kodu nie będzie działała w wersjach wcześniejszych. Zalecam, aby zamiast pokonywać trudności związane z uruchamianiem przykładów w starszych wersjach, po prostu przed rozpoczęciem pracy z książką pobrać najnowszą wersję Pythona.

W tej książce korzystałem jedynie ze standardowej biblioteki Pythona (małym wyjątkiem jest rozdz. 2, w którym jest instalowany moduł typing_extensions), w związku z tym cały prezentowany kod powinien działać na dowolnej platformie wspierającej Pythona (macOS, Windows, GNU/Linux itd.). Kod książki był testowany jedynie w CPython (głównym interpreterze Pythona dostępnym na stronie python.org), choć większość będzie prawdopodobnie działała na dowolnym interpreterze Pythona zgodnym z wersją Python 3.7.

Ta książka nie wyjaśnia, jak korzystać z takich narzędzi Pythona, jak edytory, środowiska IDE, debuggery czy Python REPL. Kod źródłowy książki jest dostępny online w repozytorium GitHub: https://github.com/davecom/ClassicComputerScienceProblemsInPython. Kod źródłowy jest podzielony na foldery według rozdziałów. Czytając rozdział, można zobaczyć nazwę pliku źródłowego w nagłówku każdego z listingów kodu. Plik źródłowy można znaleźć w odpowiadającym mu folderze w repozytorium. Aby uruchomić przykład, zazwyczaj wystarczy wpisać python3 nazwapliku.py lub python nazwapliku.py w zależności od ustawień komputera związanych z nazwą interpretera Python 3.

We wszystkich prezentowanych listingach kodu są wykorzystywane adnotacje typów Pythona (ang. type hints lub type annotations). Te adnotacje stanowią stosunkowo nową funkcję języka Python i mogą deprymować programistów Pythona, którzy widzą je po raz pierwszy. Za ich wykorzystaniem przemawiają trzy argumenty:

1. Zapewniają czytelność w zakresie typów zmiennych oraz parametrów i wartości zwrotnych funkcji.

2. Ze względu na punkt 1. powodują, że kod w pewnym sensie sam się dokumentuje. Zamiast przeszukiwać komentarz lub napis dokumentujący w poszukiwaniu typu zwrotnego funkcji, wystarczy spojrzeć na jej sygnaturę.

3. Umożliwiają sprawdzanie poprawności typów w kodzie. Jednym z popularnych narzędzi do sprawdzania typów w Pythonie jest mypy.

Nie wszyscy są fanami adnotacji typu i decyzja o zastosowaniu ich w książce była, szczerze mówiąc, ryzykowna. Mam nadzieje, że będą one pomocą, a nie utrudnieniem. Pisanie kodu Pythona z adnotacjami typów zajmuje nieco więcej czasu, ale zwiększa jego czytelność. Co ciekawe, adnotacje typu nie mają żadnego wpływu na samo działanie kodu w interpreterze Pythona. Dowolny kod z tej książki powinien nadal działać po usunięciu z niego adnotacji typu. Jeśli po raz pierwszy się z nimi spotykasz i czujesz, że przed rozpoczęciem lektury potrzebujesz bardziej szczegółowego wprowadzenia do tego zagadnienia, zajrzyj do dodatku C, który zawiera przyspieszony kurs z adnotacji typu.

Sama standardowa biblioteka – bez grafiki czy kodu interfejsu użytkownika

Żaden z prezentowanych w tej książce przykładów nie generuje obiektów graficznych i nie korzysta z graficznego interfejsu użytkownika (GUI). Dlaczego? Moim celem było rozwiązanie przedstawionych problemów w jak najbardziej zwięzły i czytelny sposób. Często generowanie efektów graficznych stanowi dodatkową komplikację lub sprawia, że rozwiązanie jest dużo bardziej złożone niż to konieczne do zilustrowania wybranej techniki lub algorytmu.

Co więcej, dzięki rezygnacji z użycia jakichkolwiek bibliotek GUI przedstawiony w tej książce kod jest wyjątkowo przenośny. Może być łatwo uruchamiany zarówno na wbudowanej dystrybucji Pythona uruchomionej na Linuksie, jak i na komputerze z systemem Windows. Dodatkowo podjąłem świadomą decyzję, żeby używać tylko pakietów ze standardowej biblioteki Pythona, bez bibliotek zewnętrznych jak w bardziej zaawansowanych książkach o Pythonie. Dlaczego? Moim celem jest nauczenie podstawowych technik rozwiązywania problemów, a nie podejścia typu „pip install a solution”. Mam nadzieję, że konieczność opracowania każdego rozwiązania od podstaw pozwoli lepiej zrozumieć działanie popularnych bibliotek. Ograniczenie się do standardowej biblioteki ułatwi przynajmniej przenoszenie i uruchamianie kodu tej książki.

Nie znaczy to, że rozwiązania graficzne nigdy nie ilustrują algorytmu lepiej niż tekstowe. Po prostu ta książka się nimi nie zajmuje. Dodałyby one kolejną, niepotrzebną warstwę złożoności.

Część serii

To druga książka z serii zatytułowanej Classic Computer Science Problems, opublikowana przez Manning – pierwsza, zatytułowana Classic Computer Science Problems in Swift, została wydana w 2018 r. W każdej książce z tej serii starano się przekazać wiedzę o danym języku, przedstawiając go z perspektywy (prawie) tych samych problemów informatyki.

Jeśli spodoba Ci się ta książka i planujesz nauczyć się innego języka omówionego w ramach tej serii, przejście z jednej książki do drugiej może się okazać prostym sposobem poprawienia umiejętności programowania w wybranym języku. Na razie seria ta obejmuje jedynie języki Swift i Python. Dwie pierwsze książki napisałem sam, ponieważ mam duże doświadczenie w obu językach, ale trwają już rozmowy na temat opublikowania kolejnych książek z tej serii współtworzonych przez ekspertów w zakresie innych języków. Zachęcam do ich poszukania, jeśli spodoba Ci się niniejsza książka. Więcej informacji o tej serii można znaleźć na stronie https://classicproblems.com/.

1 Osobom zaczynającym przygodę z Pythonem zalecam wcześniejsze zapoznanie się z książką Naomi Ceder zatytułowaną Python. Szybko i prosto, Wyd. 3. Helion, 2019.