Dawno temu był sobie algorytm

Dawno temu był sobie algorytm

Autorzy: Martin Erwig

Wydawnictwo: DW PWN

Kategorie: Informatyka

Typ: e-book

Formaty: MOBI EPUB

Ilość stron: 342

cena od: 40.15 zł

Książka Dawno temu był sobie algorytm wyjaśnia koncepcje informatyki poprzez znane historie i codzienne sytuacje. Autor tłumaczy przetwarzanie informacji jako coś, co dzieje się poza komputerami, a informatykę jako studium systematycznego rozwiązywania problemów. Martin Erwig pokazuje, że wiele codziennych czynności dotyczy rozwiązywania problemów. Na przykład poranne wstawanie: wstajemy z łóżka, bierzemy prysznic, ubieramy się, jemy śniadanie. Ta prosta codzienna rutyna rozwiązuje powtarzający się problem za pomocą serii dobrze zdefiniowanych kroków. W informatyce takie rutynowe działanie nazywamy algorytmem. Książka wyjaśnia pojęcia z zakresu przetwarzania za pomocą przykładów z życia i popularnych opowieści. Na przykład Jaś i Małgosia wykonują algorytm powrotu z lasu do domu. Film Dzień świstaka ilustruje problem nierozwiązywalności; Sherlock Holmes manipuluje strukturami danych podczas rozwiązywania zagadek kryminalnych; magię w świecie Harryego Pottera można zrozumieć dzięki typom i abstrakcjom; natomiast Indiana Jones pokazuje złożoność wyszukiwania. Po drodze autor omawia reprezentacje i różne sposoby organizacji danych; trudne problemy; język, składnię i niejednoznaczność; struktury sterujące, pętle i problem stopu; różne rodzaje rekurencji; a także reguły znajdowania błędów w algorytmach. Książka zdobyła nagrodę American Book Fest za najlepszą książkę w kategorii Edukacja / Nauka.

Dane oryginału

Copyright © 2017 by Massachusetts Institute of Technology. Title of English-language original: Once upon an algorithm: how stories explain computing, ISBN 978-0-2620-3663-4, published by MIT Press. Polish-language edition copyright © 2019 by Polish Scientific Publishers PWN Wydawnictwo Naukowe PWN Spółka Akcyjna. All rights reserved.

Przekład Wojciech Fenrich i Witold Sikorski na zlecenie WITKOM Witold Sikorski

Projekt okładki polskiego wydania Joanna Andryjowicz, na podstawie oryginału

Ilustracja na okładce Molly Seamans © MIT Press

Wydawca Edyta Kawala

Redaktor prowadzący Jolanta Kowalczuk

Redaktor Irena Puchalska

Koordynator produkcji Anna Bączkowska

Skład wersji elektronicznej na zlecenie Wydawnictwa Naukowego PWN Marcin Kapusta / konwersja.virtualo.pl

Konsultacja dr Jakub Radoszewski

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

Copyright © for the Polish edition by Wydawnictwo Naukowe PWN SA

Warszawa 2019

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

Warszawa 2019

ISBN 978-83-01-20374-0

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

Spis treści

Przedmowa

Podziękowania

Wprowadzenie

Część I. Algorytmy

Przetwarzanie i algorytmy Jaś i Małgosia

1. Droga do zrozumienia przetwarzania

2. Przechodząc do rzeczy – gdy przetwarzanie odbywa się naprawdę

Reprezentacja i struktury danych Sherlock Holmes

3. Tajemnica znaków

4. Z notatnika detektywa – współudział po fakcie

Rozwiązywanie problemów i jego ograniczenia Indiana Jones

5. W poszukiwaniu doskonałej struktury danych

6. Porządkowanie sortowania

7. Misja niepodatna

Część II. Języki

Język i znaczenie Over the Rainbow

8. Podstawy języków

9. Znajdowanie odpowiedniego tonu – znaczenie dźwięku

Struktury sterujące i pętle Dzień świstaka

10. Przyjmij wyzwanie, zastosuj i powtórz

11. Bez gwarancji szczęśliwego zakończenia

Rekurencja Powrót do przyszłości

12. Dobre planowanie da wyniki

13. Kwestia interpretacji

Typy i abstrakcje Harry Potter

14. Magiczny typ

15. Z lotu ptaka – abstrahując od szczegółów

Słowniczek

Przypisy

Przedmowa

Gdy ludzie pytają mnie o moją pracę, rozmowa szybko schodzi na temat tego, czym jest informatyka. Stwierdzenie, że informatyka to nauka o komputerach, byłoby mylące (choć ściśle mówiąc, nie byłoby niepoprawne), ponieważ większość ludzi za komputer uznaje peceta lub laptopa i uważa, że informatyk większość czasu spędza na budowaniu sprzętu. Jednocześnie, zdefiniowanie informatyki jako nauki o przetwarzaniu stanowiłoby próbę ucieczki od tego pytania, ponieważ natychmiast pojawiłyby się wątpliwości, czym jest przetwarzanie.

Przez lata dochodziłem do wniosku, że nauczanie oparte jedynie na wprowadzaniu pojęć jednego za drugim nie działa dobrze, jest bowiem po prostu zbyt abstrakcyjne. Obecnie zaczynam zwykle od opisu informatyki jako dziedziny zajmującej się badaniami nad systematycznym rozwiązywaniem problemów. Każdy wie, czym jest problem, tak jak każdy widział rozwiązanie. Wyjaśniwszy tę perspektywę za pomocą przykładu, często mam możliwość wprowadzenia pojęcia algorytmu, które pozwala zwrócić uwagę na istotne różnice między informatyką a matematyką. Zwykle nie muszę mówić o językach programowania, komputerach i związanych z tym zagadnieniach technicznych, ale nawet jeśli do tego dochodzi, konkretny problem sprawia, że zilustrowanie tych pojęć jest łatwe. Niniejsza książka stanowi rozwinięcie tego podejścia.

Informatyka to relatywnie nowy członek naukowego klubu i niekiedy wydaje się, że nie zyskała sobie jeszcze takiego szacunku, jakim cieszą się poważne dyscypliny, takie jak fizyka, chemia czy biologia. Pomyślmy o filmowej scenie, w której występuje postać fizyka. Prawdopodobnie zobaczymy wtedy kogoś omawiającego skomplikowane wzory zapisane na tablicy lub odzianą w biały kitel osobę kierującą eksperymentem. Fizyk jest przedstawiany jako godny szacunku naukowiec dysponujący cenną wiedzą. A teraz wyobraźmy sobie podobną scenę z udziałem informatyka. Zobaczymy prawdopodobnie jakiegoś kujona, gościa siedzącego w ciemnym, zabałaganionym pokoju i gapiącego się w ekran komputerowego monitora, piszącego coś nerwowo na klawiaturze, by, prawdopodobnie, złamać jakiś kod lub hasło. Obie sceny przedstawiają sytuacje, w których następuje rozwiązanie ważnego problemu, ale o ile fizyk może dać jakieś przekonujące wyjaśnienie, w jaki sposób można go rozwiązać, rozwiązanie komputerowego problemu pozostaje tajemnicze, często magiczne i zdecydowanie zbyt skomplikowane, by wyjaśnić je komuś, kto nie jest specjalistą. Jeśli informatyki nie da się wyjaśnić zwykłym ludziom, dlaczego ktokolwiek miałby kiedykolwiek próbować czegoś się o niej dowiedzieć lub ją zrozumieć?

Informatyka zajmuje się przetwarzaniem – zjawiskiem, które dotyczy wszystkich. Nie mówię wyłącznie o telefonach komórkowych, laptopach czy internecie. Pomyślmy o składaniu papierowego samolotu, jeździe do pracy, gotowaniu posiłku, a nawet transkrypcji DNA – procesie zachodzącym w naszych komórkach miliony razy w czasie, gdy czytamy to zdanie. Wszystko to są przykłady przetwarzania – systematycznego sposobu rozwiązywania problemów – nawet jeśli większość ludzi nie postrzega tego w ten sposób.

Nauka daje nam podstawowe zrozumienie tego, jak działa świat natury. Daje nam też metodę naukową pozwalającą tę wiedzę ugruntować. To, co dotyczy nauki w ogólności, dotyczy również informatyki, szczególnie, że z przetwarzaniem możemy spotkać się w wielu różnych postaciach i sytuacjach. Zrozumienie przetwarzania w podstawowym zakresie daje więc korzyści podobne do podstawowej znajomości fizyki, chemii i biologii, pozwalając zrozumieć świat i efektywniej uporać się z wieloma rzeczywistymi problemami. Ten aspekt przetwarzania często jest nazywany myśleniem obliczeniowym (computational thinking).

Głównym celem tej książki jest analiza ogólnej natury przetwarzania, a tym samym zwrócenie uwagi na możliwość szerokiego zastosowania informatyki. Mam nadzieję, że wzbudzi to większe zainteresowanie informatyką i wywoła chęć dowiedzenia się o niej czegoś więcej.

Najpierw staram się odszukać przetwarzanie w codziennych sytuacjach, a następnie wyjaśniam związane z nim pojęcia informatyczne za pomocą przystępnych opowieści. Te codzienne sytuacje wzięte są ze zwykłego dnia pracy: poranne wstawanie, jedzenie śniadania, dojazd do pracy, zdarzenia mające miejsce w jej trakcie, wizyta u lekarza, popołudniowe uprawianie hobby, jedzenie kolacji i wieczorne rozmyślania o tym, co wydarzyło się w ciągu dnia. Łącznie wyodrębniam 15 takich sytuacji, z których każda stanowi punkt wyjścia do jednego rozdziału książki. Rozdziały te wyjaśniają następnie pojęcia informatyczne za pomocą 7 przystępnych opowieści. Każda z nich obejmuje dwa lub trzy rozdziały i dotyczy określonego zagadnienia z dziedziny informatyki.

Książka ma dwie części: algorytmy i języki. Są to dwa główne filary, na których jest oparte pojęcie przetwarzania. W tabeli 1 są zestawione opowieści i ilustrowane przez nie pojęcia informatyczne.

Tabela 1

Opowieść

Rozdziały

Tematy

Część I

Jaś i Małgosia

1, 2

Przetwarzanie i algorytmy

Sherlock Holmes

3, 4

Reprezentacja i struktury danych

Indiana Jones

5, 6, 7

Rozwiązywanie problemów i jego ograniczenia

Część II

Over the Rainbow

8, 9

Język i znaczenie

Dzień świstaka

10, 11

Struktury sterujące i pętle

Powrót do przyszłości

12, 13

Rekurencja

Harry Potter

14, 15

Typy i abstrakcje

Wszyscy doceniamy dobre opowieści. Są dla nas pocieszeniem, dają nadzieję i inspirują. Mówią nam o świecie, uświadamiają problemy, przed którymi stajemy, a niekiedy podsuwają rozwiązania. Opowieści mogą również dawać wskazówki dotyczące naszego życia. Gdy zastanawiamy się, czego mogą nas nauczyć, zwykle myślimy o miłości, konfliktach czy kondycji ludzkiej. Mnie na myśl przychodzi jednak również przetwarzanie. Gdy szekspirowska Julia pyta „Czymże jest nazwa?”, dotyka ważnego problemu reprezentacji. Mit Syzyfa autorstwa Alberta Camusa stawia pytanie, jak zmierzyć się z absurdalnością życia, ale i jak wykryć nigdy niekończące się przetwarzanie.

Opowieści mają wiele warstw znaczeniowych. Wśród nich często znajduje się warstwa związana z przetwarzaniem. Niniejsza książka stanowi próbę odsłonięcia tej warstwy i dania czytelnikom nowej perspektywy, z której będą mogli spojrzeć na opowieści i występujące w nich przetwarzanie. Mam nadzieję, że opowieści zostaną docenione za ich obliczeniową treść, a ten oryginalny punkt widzenia pobudzi zainteresowanie informatyką.

Podziękowania

Pomysł napisania tej książki wziął się z wielu rozmów, które odbyłem z przyjaciółmi, studentami, kolegami oraz osobami, z którymi jeżdżę autobusem do pracy. Wszystkim im dziękuję za cierpliwe wysłuchiwanie moich wyjaśnień dotyczących informatyki i za przyjazną niecierpliwość, gdy wyjaśnienia te stawały się zbyt długie i skomplikowane. Cel w postaci napisania dla szerokiej publiczności książki z zakresu informatyki w znacznym stopniu był podsycany przez te doświadczenia.

W ciągu ostatniej dekady miałem możliwość współpracy w ramach letnich praktyk z wieloma studentami studiów pierwszego stopnia, co stanowiło dla mnie dodatkową zachętę. Praktyki te uzyskały wsparcie w postaci grantów Narodowej Fundacji Nauki (National Science Foundation), której jestem wdzięczny za jej wsparcie dla badań naukowych oraz popularyzacji nauki w Stanach Zjednoczonych.

Szukając materiałów do tej książki, polegałem na internecie, w szczególności na Wikipedii (wikipedia.org) oraz stronie internetowej TV Tropes (tvtropes.org). Wszystkim osobom mającym wkład w ich istnienie dziękuję za poświęcenie i entuzjazm, z jakim dzielą się swą wiedzą ze światem.

Gdy pisałem tę książkę, Eric Walkingshaw, Paul Cull i Karl Smeltzer czytali niektóre rozdziały, dając mi eksperckie wsparcie odnośnie do treści i stylu pisania. Chciałbym im podziękować za ich cenne rady. Dziękuję również Jennifer Parham-Mocello za przeczytanie części rozdziałów i wypróbowanie kilku przykładów na studentach pierwszego roku studiów. Dziękuję także mojemu synowi Aleksandrowi za sprawdzenie pierwszej wersji pracy oraz cenne rady w kwestiach związanych z Harrym Potterem. Większa część tej książki została napisana w trakcie urlopu naukowego udzielonego mi przez Oregon State University. Dziękuję mojemu wydziałowi oraz uczelni za ich wsparcie dla tego projektu.

Urzeczywistnienie pomysłu na tę książkę było znacznie większym wyzwaniem, niż się spodziewałem. Moje szczere podziękowania płyną dla Marie Lufkin-Lee, Katherine Almeidy, Kathleen Hensley i Christine Savage z MIT Press za ich wsparcie dla tego projektu oraz pomoc udzieloną w trakcie jego realizacji.

Na koniec – mam to szczęście, że ożeniłem się z osobą, która jest moim najszczerszym i najbardziej cierpliwym czytelnikiem. Moja żona Anja nie szczędziła mi zachęt w trakcie przygody, jaką była praca nad tą książką. Zawsze cierpliwie wysłuchiwała moich pytań, które raczej częściej niż rzadziej miały erudycyjny i abstrakcyjny wydźwięk. Przeczytała wiele wstępnych wersji tekstu i cierpliwie próbowała mnie powstrzymać, gdy moje pisanie stawało się zbyt akademickie i zbyt zależne od technicznego żargonu. Ukończenie tej książki zawdzięcza jej więcej niż komukolwiek innemu, i to jej ją dedykuję.

Wprowadzenie

Obecnie przetwarzanie odgrywa w społeczeństwie znaczącą rolę. Dlaczego jednak miałoby to nas skłaniać do dowiedzenia się o nim czegoś więcej, skoro nie planujemy zostać informatykami? Moglibyśmy po prostu cieszyć się technologiami napędzanymi przez przetwarzanie i korzystać z ich dobrodziejstw. Nie zgłębiamy przecież tajników awioniki, chcąc skorzystać z możliwości, jakie dają powietrzne podróże, ani nie zabiegamy o dyplom na kierunku lekarskim, chcąc skorzystać z osiągnięć współczesnej służby zdrowia.

Świat, w którym żyjemy, nie składa się jednak wyłącznie z techniki opracowanej przez człowieka. Nadal musimy wchodzić w kontakt z pozbawionymi autonomii obiektami rządzonymi przez prawa fizyki. Zrozumienie podstaw mechaniki daje więc tę korzyść, że zwyczajnie pozwala przewidzieć zachowanie tych obiektów i bezpiecznie poruszać się w naszym środowisku. Podobne argumenty można przytoczyć na rzecz korzyści płynących ze zgłębiania kwestii przetwarzania i pokrewnych zagadnień. Przetwarzanie dokonuje się nie tylko we wnętrzu komputerów i elektronicznych gadżetów, lecz także na zewnątrz maszyn. Poniżej krótko omawiam niektóre z najważniejszych zasad informatyki i wyjaśniam, dlaczego są one istotne.

Przetwarzanie i algorytmy

Wykonajmy następujące proste ćwiczenie. Będą nam potrzebne linijka, ołówek i arkusz papieru w kratkę. Najpierw narysujmy poziomą linię długości 1 centymetra. Następnie narysujmy pionową linię tej samej długości, która będzie się zaczynać w jednym z końców pierwszej linii i będzie do niej prostopadła. Na koniec połączmy ukośną linią dwa wolne końce narysowanych przez nas linii, tworząc w ten sposób trójkąt. Zmierzmy teraz długość narysowanej linii ukośnej. Gratulacje, właśnie obliczyliśmy, ile wynosi pierwiastek z 2 (rys. 1).

Co to geometryczne ćwiczenie ma wspólnego z przetwarzaniem? Jak wyjaśniam w rozdziałach 1 i 2, stanowi ono wykonanie algorytmu przez komputer dokonujący przetwarzania. W tym przykładzie zachowaliśmy się jak komputer, który wykonał algorytm, aby narysować i zmierzyć odcinki, co doprowadziło do obliczenia pierwiastka z 2. Posiadanie algorytmu jest kluczowe, ponieważ jedynie wtedy różne komputery mogą dokonywać przetwarzania wielokrotnie i w różnych momentach. Istotnym aspektem przetwarzania jest to, że wymaga ono zasobów (takich jak ołówek, papier i linijka) oraz czasu na jego przeprowadzenie. Posiadanie algorytmicznego opisu ponownie okazuje się ważne, ponieważ pomaga w analizie zasobów, jakich wymaga przetwarzanie.

Rysunek 1. Obliczanie pierwiastka kwadratowego z 2 przy użyciu ołówka i linijki

W rozdziałach 1 i 2 wyjaśniam:

• czym są algorytmy,

• że algorytmy są stosowane do systematycznego rozwiązywania problemów,

• że algorytm musi zostać wykonany przez komputer (człowieka, maszynę itp.), by doszło do przetwarzania,

• że wykonanie algorytmu zużywa zasoby.

Dlaczego to jest ważne?

Przepisy kulinarne stanowią przykłady algorytmów. Za każdym razem, gdy przygotowujemy kanapkę, pieczemy ciasto czekoladowe albo gotujemy swoje ulubione danie, postępując zgodnie z instrukcjami zawartymi w przepisie, w rzeczywistości wykonujemy algorytm w celu przekształcenia nieprzetworzonych składników w końcowy produkt. Do wymaganych zasobów zalicza się składniki posiłku, przybory kuchenne, energię i czas potrzebny do przygotowania potrawy.

Wiedza dotycząca algorytmów wyczula nas na kwestie związane z poprawnością metody oraz wymogi związane z zasobami. Pomaga nam zidentyfikować możliwości w zakresie ulepszenia procesów we wszystkich obszarach życia przez (re)organizację kroków i materiałów. W przypadku geometrycznego obliczania pierwiastka kwadratowego moglibyśmy na przykład pominąć rysowanie ukośnej linii i po prostu zmierzyć odległość między dwoma niepołączonymi końcami odcinków.

W przypadku gotowania ulepszenie może polegać na czymś tak prostym i oczywistym jak zmniejszenie liczby wycieczek do lodówki dzięki zaplanowaniu ich z góry lub zgromadzeniu wcześniej składników. Moglibyśmy zastanowić się, w jaki sposób efektywniej wykorzystać piekarnik lub piec i zaoszczędzić czas, wykonując kilka kroków jednocześnie, na przykład rozgrzewając piekarnik lub myjąc warzywa na sałatkę w czasie, gdy gotują się ziemniaki. Te techniki znajdują również zastosowanie w wielu innych dziedzinach – zaczynając od prostych instrukcji składania mebli, po procesy organizacyjne pozwalające na funkcjonowanie biura czy zarządzanie halą fabryczną.

W dziedzinie techniki algorytmy kontrolują w zasadzie każde przetwarzanie wykonywane przez komputer. Znaczącym przykładem jest kompresja danych, bez której transmisja muzyki lub filmów przez Internet byłaby niemal niemożliwa. Algorytmy kompresji danych identyfikują często powtarzające się wzory i zastępują je niewielkimi fragmentami kodu. Kompresja danych odpowiada bezpośrednio na problem ograniczonej ilości zasobów wymaganych do przetworzenia, redukując ilość pamięci konieczną do przechowywania piosenek czy filmów, a w ten sposób również na problem czasu, jaki zajmuje załadowanie ich z Internetu. Innym przykładem jest algorytm PageRank stosowany przez Google, który określa kolejność, w jakiej wyniki wyszukiwania są prezentowane użytkownikowi. Działa on, szacując istotność strony internetowej przez zliczenie, jak wiele wiedzie do niej linków, i określając wagę tych linków.

Reprezentacja i struktury danych

Można by sądzić, że przetwarzanie numeryczne zawsze jest prowadzone za pomocą liczb, ponieważ używamy hindusko-arabskiego systemu cyfr, a maszyny pracują, wykorzystując zera i jedynki. Geometryczna metoda obliczenia za pomocą odcinków może więc być zaskakująca. Przykład ten pokazuje jednak, że jedna i ta sama rzecz (np. ilość) może być reprezentowana na różne sposoby (przez symbole numeryczne lub odcinki).

Istotą przetwarzania jest przekształcanie reprezentacji. W rozdziale 3 wyjaśniam, czym są reprezentacje i w jaki sposób są wykorzystywane w przetwarzaniu. Wiele przypadków przetwarzania jest związanych z wielką ilością informacji, dlatego w rozdziale 4 wyjaśniam, w jaki sposób można efektywnie zorganizować zbiory danych. Kwestię tę komplikuje fakt, że każdy konkretny sposób organizacji może sprzyjać efektywności pewnych sposobów dostępu do danych, ale nie innych.

W rozdziałach 3 i 4 omawiam:

• różne formy reprezentacji,

• różne sposoby organizacji i dostępu do kolekcji danych,

• zalety i wady różnych sposobów organizacji danych.

Dlaczego to jest ważne?

Ilość każdego składnika w przepisie może zostać wyrażona za pomocą masy lub objętości. Są to różne formy reprezentacji, które do prawidłowego wykonania przepisu/algorytmu wymagają różnych przyborów do gotowania (wag lub miarek). Jeśli chodzi o organizację danych, sposób, w jaki jest zorganizowana nasza lodówka lub spiżarnia, ma wpływ na to, jak szybko możemy odnaleźć wszystkie składniki wymagane przez przepis. Możemy też się zastanowić, w jaki sposób kwestia reprezentacji odnosi się do samego przepisu. Może on mieć postać tekstowego opisu, serii obrazków lub filmu w serwisie YouTube. Wybór sposobu reprezentacji często robi dużą różnicę, jeśli chodzi o efektywność algorytmów.

W szczególności, w wielu miejscach pojawia się problem, jak zorganizować jakąś kolekcję przedmiotów lub ludzi, na przykład jak zorganizować przestrzeń na biurku lub w garażu, by ułatwić sobie szybkie wyszukiwanie przedmiotów, lub jak zorganizować biblioteczne półki z książkami. Zastanów się na ile różnych sposobów możesz czekać w kolejce: w sklepie spożywczym (stojąc w ogonku), w przychodni (siedząc w poczekalni z pobranym numerkiem) lub wchodząc na pokład samolotu (gdzie obowiązuje wiele kolejek).

W dziedzinie techniki arkusze kalkulacyjne są jednymi z tych narzędzi programistycznych, które odniosły największy sukces. W znacznym stopniu przyczyniła się do tego forma organizacji danych w postaci tabeli, ponieważ wspiera ona szybkie i proste budowanie formuł pozwalających na sumowanie po wierszach i kolumnach. Pozwala też na reprezentację danych i rezultatów ich przetwarzania w jednym miejscu. Jednocześnie Internet, będąc jednym z tych wynalazków końca XX wieku, które w największym stopniu zmieniły rzeczywistość, organizuje strony internetowe, komputery i połączenia między nimi w formie sieci. Ten sposób reprezentacji daje elastyczny dostęp do informacji i umożliwia efektywną transmisję danych.

Rozwiązywanie problemów i jego ograniczenia

Algorytm to pewna metoda rozwiązywania problemów – gdy chodzi o odnalezienie pierwiastka kwadratowego z jakiejś liczby czy o upieczenie ciasta. Informatyka zaś jest dyscypliną, która zajmuje się systematycznym rozwiązywaniem problemów.

Spośród wielu problemów, jakie można rozwiązać za pomocą algorytmów, dwa zasługują na szczegółowe rozważenie. W rozdziale 5 omawiam problem wyszukiwania, będący jednym z najczęściej wykorzystywanych sposobów przetwarzania danych. W rozdziale 6 wyjaśniam problem sortowania, który stanowi ilustrację pewnej bardzo skutecznej metody rozwiązywania problemów, a także pojęcie wewnętrznej złożoności problemu. W rozdziale 7 natomiast opisuję klasę tak zwanych problemów niepodatnych. Potrafiące je rozwiązać algorytmy istnieją, ale ich wykonanie trwa zbyt długo, a więc problemy te są nierozwiązywalne w praktyce.

W rozdziałach 5, 6 i 7 wyjaśniam:

• dlaczego wyszukiwanie może być trudne i czasochłonne,

• za pomocą jakich metod możemy usprawnić wyszukiwanie,

• czym charakteryzują się różne algorytmy sortujące,

• że niektóre sposoby przetwarzania mogę wspierać inne, na przykład sortowanie może wspierać wyszukiwanie,

• że algorytmy o wykładniczym czasie wykonania tak naprawdę nie mogą być uważane za rozwiązanie problemu.

Dlaczego to jest ważne?

Niezliczone godziny naszego życia spędzamy na poszukiwaniach – kluczyków do samochodu czy informacji w internecie. Zrozumienie wyszukiwania i zaznajomienie się z technikami, które mogą uczynić je bardziej efektywnym, może więc być pomocne. Problem wyszukiwania ilustruje dodatkowo, w jaki sposób wybór reprezentacji wpływa na efektywność algorytmów, odzwierciedlając uwagę Johna Deweya, że „problem dobrze postawiony to problem w połowie rozwiązany”[1].

Wiedza o tym, kiedy problem nie może zostać efektywnie rozwiązany, jest równie ważna jak znajomość algorytmów mających zastosowanie w przypadku problemów, które daje się rozwiązać, ponieważ pomaga nam to uniknąć poszukiwania efektywnych rozwiązań, gdy takie nie istnieją. Sugeruje to, że w niektórych przypadkach powinniśmy zadowolić się przybliżonymi odpowiedziami.

W dziedzinie techniki najbardziej oczywisty przypadek wyszukiwania stanowią wyszukiwarki internetowe, takie jak Google. Wyniki wyszukiwania dla jakiegoś zapytania nie są wyświetlane w przypadkowej kolejności, ale zwykle są posortowane zgodnie z ich przewidywaną istotnością czy odpowiedniością. Wiedza o tym, z jak trudnym problemem mamy do czynienia, jest potrzebna do opracowania algorytmów, które w wyniku przetwarzania dają przybliżone rozwiązania tam, gdzie uzyskanie dokładnych wyników zajęłoby zbyt dużo czasu. Znanym tego przykładem jest problem komiwojażera, który polega na znalezieniu zamkniętej trasy przebiegającej przez określoną liczbę miast w takiej kolejności, która pozwala na zminimalizowanie całkowitego przebytego dystansu.

Wiedzę o tym, że efektywny algorytm pozwalający rozwiązać jakiś problem nie istnieje, można również wykorzystać w pozytywny sposób. Przykładem jest szyfrowanie przy użyciu klucza publicznego, które pozwala na zachowanie prywatności transakcji internetowych, włączając w to zarządzanie kontami bankowymi i zakupy w sieci. Szyfrowanie działa tylko dzięki temu, że obecnie nie znamy żadnego efektywnego algorytmu pozwalającego na rozłożenie liczby na czynniki pierwsze (czyli na zapisanie jej w postaci iloczynu liczb pierwszych). Gdyby uległo to zmianie, szyfrowanie za pomocą klucza publicznego nie byłoby już bezpieczne.

Język i znaczenie

Każdy algorytm musi zostać wyrażony w jakimś języku. Współczesne komputery nie mogą zostać zaprogramowane za pomocą języka angielskiego, ponieważ języki naturalne zawierają zbyt dużo wieloznaczności, z czym ludzie łatwo sobie radzą, ale maszyny nie. Algorytmy, które mają być wykonane przez maszyny, muszą więc być napisane w językach, które mają dobrze zdefiniowaną strukturę i znaczenie.

W rozdziale 8 wyjaśniam, czym jest język i w jaki sposób można zdefiniować jego składnię. Definicja składni jakiegoś języka daje pewność, że każde z jego zdań będzie mieć dobrze zdefiniowaną strukturę, co stanowi podstawę zrozumienia i zdefiniowania znaczenia zdań i języków. W rozdziale 9 omawiam znaczenie języków i problem wieloznaczności.

W rozdziałach 8 i 9 opisuję:

• w jaki sposób gramatyka definiuje język,

• w jaki sposób można wykorzystać gramatykę do skonstruowania wszystkich zdań należących do tego języka,

• czym są drzewa syntaktyczne,

• w jaki sposób drzewa syntaktyczne reprezentują strukturę zdań i rozwiązują problem ich wieloznaczności.

Dlaczego to jest ważne?

Posługujemy się językami, by przekazać znaczenie. By komunikacja zadziałała, komunikujący się partnerzy muszą uzgodnić, co zalicza się do zbioru dobrze zbudowanych zdań i co każde z tych zdań znaczy. Polecenia zawarte w przepisach kulinarnych muszą na przykład precyzyjnie opisywać miary, temperaturę piekarnika, czas gotowania i tak dalej, by dać pożądany efekt.

W większości obszarów naszego życia wytworzyliśmy specjalną terminologię i języki, które ułatwiają bardziej efektywną komunikację. Jest to prawdą szczególnie w odniesieniu do informatyki, w której istotna część komunikacji dzieje się za pomocą maszyn. Skoro maszyny mają mniejsze umiejętności przetwarzania języka niż ludzie, dokładna definicja języków jest ważna, by zagwarantować, że zaprogramowane maszyny zachowają się w oczekiwany sposób.

W dziedzinie techniki szeroko wykorzystywanym językiem programowania jest język formuł arkuszy kalkulacyjnych. Każdy kto kiedykolwiek wprowadził do arkusza kalkulacyjnego jakąś formułę, napisał działający w nim program. Arkusze kalkulacyjne cieszą się złą sławą wynikającą z pojawiających się w nich niekiedy pomyłek i liczonych w milionach dolarów strat będących rezultatem niepoprawnych formuł. Innym wszechobecnym językiem jest HTML (hipertekstowy język znaczników). Za każdym razem, gdy na naszego laptopa, komputer stacjonarny czy telefon komórkowy ładujemy witrynę internetową, bardzo prawdopodobne jest, że jej treść jest wyświetlana w naszej przeglądarce w HTML-u, który jest językiem sprawiającym, że struktura strony internetowej staje się precyzyjna i prezentuje ją w jednoznaczny sposób. Choć HTML służy wyłącznie do reprezentowania informacji i sam nie opisuje przetwarzania, istnieje inny język zrozumiały dla dowolnej współczesnej przeglądarki. Jest to JavaScript, który określa dynamiczne zachowanie stron internetowych.

Struktury sterujące i pętle

Instrukcje będące elementem jakiegoś algorytmu mają dwie różne funkcje: służą one albo do bezpośredniego wykonywania działań na danych, albo decydowania, które instrukcje zostaną wykonane w następnej kolejności i ile razy. Instrukcje tego drugiego rodzaju są nazywane strukturami sterującymi. Tak jak fabuła filmu lub opowieści wiąże ze sobą pojedyncze czynności i sceny, tworząc spójną narrację, struktury sterujące z pojedynczych instrukcji budują algorytmy.

W rozdziale 10 wyjaśniam różnice między poszczególnymi strukturami sterującymi, szczególnie skupiając się na pętlach, które są wykorzystywane do wyrażenia powtarzalności działań. Ważne zagadnienie, które omawiam w rozdziale 11, dotyczy tego, czy pętla się kończy, czy biegnie w nieskończoność, oraz czy można to rozstrzygnąć za pomocą algorytmu.

W rozdziałach 10 i 11 omawiam:

• czym są struktury sterujące,

• dlaczego struktury sterujące stanowią kluczową część każdego języka służącego do wyrażania algorytmów,

• w jaki sposób powtarzalne zadania można wyrazić za pomocą pętli,

• czym jest problem stopu i dlaczego stanowi on przykład fundamentalnej własności przetwarzania.

Dlaczego to jest ważne?

Zanim usmażymy naleśniki, musimy wlać olej na patelnię. Kolejność kroków w przepisie ma znaczenie. Co więcej, przepis wymaga niekiedy podjęcia decyzji zależnie od właściwości składników lub przyborów i naczyń używanych do przygotowania potrawy. Jeśli korzystamy z piekarnika konwekcyjnego zamiast zwykłego, musimy skrócić czas pieczenia lub ustawić niższą temperaturę (albo zrobić jedno i drugie). Przepis zawiera pętlę, jeśli instruuje nas, byśmy wykonali jakieś działanie kilkukrotnie, na przykład dodali kilka jajek lub ubili ciasto.

Różnica między strukturami sterującymi i innymi działaniami sprowadza się do różnicy między robieniem czegoś a ustalaniem, co i ile razy należy zrobić, by to zrobić. W przypadku dowolnego procesu lub algorytmu możemy zechcieć ustalić, czy robi on to, co powinien, a nawet po prostu to, czy w ogóle jest w stanie się zakończyć. To raczej proste pytanie wyrażone przez problem stopu stanowi przykład jednej z wielu własności algorytmów, które chcielibyśmy poznać. Wiedza o tym, które własności algorytmów mogą zostać określone automatycznie przez inne algorytmy, mówi nam o ich bogactwie oraz ograniczeniach przetwarzania.

W dziedzinie techniki struktury sterujące są wykorzystywane wszędzie tam, gdzie algorytmy, a więc rzeczywiście wszędzie. Dowolna informacja przesyłana przez Internet jest transmitowana w zapętlony sposób, aż zostanie poprawnie odebrana. Sygnalizacja świetlna kontrolowana jest przez powtarzającą się bez końca pętlę, a wiele procesów produkcyjnych zawiera zadania, które są powtarzane tak długo, aż zostanie spełnione pewne kryterium jakościowe. Przewidywanie zachowania algorytmów w przypadku nieznanych przyszłych danych wejściowych ma wiele zastosowań w dziedzinie bezpieczeństwa. Możemy na przykład chcieć się dowiedzieć, czy system jest wrażliwy na ataki hakerów. Odnosi się to również do robotów ratowniczych, które muszą zostać wykorzystane w sytuacjach różnych od tych, w których były poddawane treningowi. Dokładne przewidzenie zachowania robota w nieznanych sytuacjach może być kwestią życia lub śmierci.

Rekurencja

Zasada redukcji – proces wyjaśniania lub implementacji złożonego systemu za pomocą prostszych elementów – odgrywa istotną rolę w wielu obszarach nauki i techniki. Rekurencja to specjalny rodzaj redukcji, która odnosi się do siebie samej. Wiele algorytmów ma charakter rekurencyjny. Rozważmy na przykład instrukcje służące do wyszukiwania słowa w słowniku zawierającym jedną pozycję na stronie: „Otwórz słownik. Jeśli widzisz słowo, którego szukasz, przerwij. W przeciwnym razie poszukaj słowa w części słownika znajdującej się przed lub po bieżącej stronie”. Zauważmy, że w ostatnim zdaniu instrukcja wyszukiwania stanowi rekurencyjne odniesienie do całego procesu, które wiedzie nas na początek wszystkich instrukcji. Nie ma potrzeby dodawania do opisu czegoś w rodzaju „powtarzaj tę czynność, aż znajdziesz słowo”.

W rozdziale 12 omawiam rekurencję, która może być strukturą sterującą, ale wykorzystywana jest również do definiowania sposobów organizacji danych. W rozdziale 13 pokazuję, jak różnie można rozumieć rekurencję.

W rozdziałach 12 i 13 omawiam:

• ideę rekurencji,

• jak odróżnić poszczególne formy rekurencji,

• dwie różne metody rozszyfrowywania definicji rekurencyjnych i nadawania im sensu,

• w jaki sposób metody te pomagają w zrozumieniu rekurencji i związku między jej różnymi formami.

Dlaczego to jest ważne?

Rekurencyjna definicja „spróbuj i dopraw” jest następująca: „Spróbuj potrawy. Jeśli smakuje dobrze, przerwij. W przeciwnym razie dodaj szczyptę przyprawy, a następnie spróbuj i dopraw”. Każde powtarzalne działanie może zostać opisane rekurencyjnie za pomocą powtarzanego działania (tu „spróbuj i dopraw”) oraz jakiegoś warunku przerywającego.

Rekurencja jest kluczową zasadą pozwalającą uzyskać skończony opis potencjalnie nieskończonych danych i przetworzeń. Rekurencja w gramatyce języka ułatwia uzyskanie nieskończonego zbioru zdań, a algorytm rekurencyjny pozwala na przetworzenie danych wejściowych o dowolnym rozmiarze.

W związku z tym, że rekurencja jest ogólną instrukcją sterującą oraz mechanizmem służącym do organizacji danych, stanowi ona część wielu systemów oprogramowania. Istnieje również kilka bezpośrednich zastosowań rekurencji. Na przykład efekt Droste, w którym obrazek zawiera mniejszą wersję samego siebie, można uzyskać jako rezultat sprzężenia zwrotnego między sygnałem (obrazek) a odbiornikiem (kamerą). Sprzężenie zwrotne stanowi rekurencyjny opis powtarzalnego efektu. Fraktale to z kolei na poły podobne do siebie wzory geometryczne, które mogą zostać opisane przez równania rekurencyjne. Można je spotkać w naturze, na przykład w płatkach śniegu lub kryształach. Wykorzystuje się je również przy analizie białek i struktur DNA. Co więcej, fraktale są wykorzystywane w nanotechnologii do projektowania samoorganizujących się nanoobwodów. Samoreplikujące się maszyny stanowią koncepcję rekurencyjną, ponieważ gdy rozpoczną działanie, reprodukują swoje własne kopie, które reprodukują kolejne kopie i tak dalej. Samoreplikujące się maszyny rozważa się w kontekście badań przestrzeni kosmicznej.

Typy i abstrakcje

Przetwarzanie dokonuje się dzięki przekształcaniu reprezentacji. Jednak nie każde przekształcenie stosuje się do każdej reprezentacji. O ile możemy mnożyć liczby, to nie możemy mnożyć linii. Podobnie – choć możemy obliczyć długość odcinka lub pole prostokąta, nie ma to sensu w przypadku liczb.

Reprezentacje i przekształcenia mogą zostać zaklasyfikowane do różnych grup, by ułatwić odróżnienie tych przekształceń, które daje się wykonać, od tych, które nie mają sensu. Grupy te są nazywane typami, a reguły określające, które kombinacje przekształceń i reprezentacji są dozwolone, są nazywane regułami typów. Typy i reguły typów wspierają projektowanie algorytmów. Na przykład, jeśli chcemy obliczyć jakąś liczbę, powinniśmy użyć działania, które daje liczbę, a jeśli chcemy przekształcić listę liczb, powinniśmy użyć działania, które w charakterze danych wejściowych przyjmuje listy liczb.

W rozdziale 14 wyjaśniam, czym są typy i w jaki sposób można ich użyć, by sformułować reguły opisujące prawidłowości przetwarzania. Reguły takie mogą być wykorzystane do znalezienia błędów w algorytmach. Potęga typów leży w ich zdolności do pomijania szczegółów dotyczących pojedynczych obiektów, a stąd do formułowania reguł na ogólniejszym poziomie. Proces pomijania szczegółów jest nazywany abstrakcją, która jest przedmiotem rozdziału 15, gdzie wyjaśniam, dlaczego abstrakcje stanowią centralną kwestię w informatyce i w jaki sposób wiążą się one z typami, z algorytmami, a nawet z komputerami i językami.

W rozdziałach 14 i 15 mówię o tym:

• czym są typy i reguły typów,

• w jaki sposób można je zastosować do opisu praw dotyczących przetwarzania, które pomagają wykryć błędy w algorytmach i konstruować ich niezawodne wersje,

• że typy i reguły typów są jedynie specjalnym przypadkiem ogólniejszej idei abstrakcji,

• że algorytmy są abstrakcjami przetwarzania,

• że typy są abstrakcjami reprezentacji,

• że złożoność czasowa jest abstrakcją czasu wykonania.

Dlaczego to jest ważne?

Jeśli przepis wymaga otworzenia puszki fasoli, bylibyśmy zaskoczeni, gdyby ktoś zabrał się za to zadanie za pomocą łyżki, ponieważ łamałoby to regułę typu, która głosi, że łyżki nie są odpowiednie do wykonania tego zadania.

Wykorzystanie typów i innych abstrakcji do opisu reguł i procesów jest powszechne. Dowolna procedura, która musi zostać powtórzona, podsuwa algorytmiczną abstrakcję, to znaczy opis, który pomija zbędne detale i zastępuje zmienne fragmenty parametrami. Przepisy również zawierają algorytmiczne abstrakcje. Wiele książek kucharskich zawiera na przykład rozdział opisujący podstawowe techniki, takie jak obieranie lub usuwanie nasion pomidorów, do których można się następnie odnieść, gdy jakiś przepis będzie wymagać określonej ilości obranych i pozbawionych nasion pomidorów. Co więcej, podsumowanie funkcji różnych obiektów biorących udział w takiej abstrakcji jest zawarte w typach, które charakteryzują ich wymogi.

W dziedzinie techniki istnieje wiele przykładów typów i abstrakcji. Przykładami fizycznych typów są wszelkiego rodzaju różnokształtne wtyczki i gniazda, śruby i śrubokręty, a także wiertła, zamki i klucze. Różne kształty mają na celu zapobieżenie niewłaściwym kombinacjom. Przykłady typów z dziedziny oprogramowania można znaleźć w formularzach internetowych, które wymagają wprowadzenia numeru telefonu lub adresu e-mail w określonym formacie. Istnieje wiele przykładów kosztownych błędów spowodowanych przez zignorowanie typów. Na przykład w 1998 roku NASA straciła wartą 655 milionów dolarów sondę Mars Climate Orbiter z powodu niekompatybilnych reprezentacji liczb. Był to błąd typu, któremu można było zapobiec przy użyciu systemu typów. Samo pojęcie komputera stanowi wreszcie abstrakcyjne ujęcie ludzi, maszyn i innych podmiotów zdolnych do wykonywania algorytmów.

Jak czytać tę książkę?

Na rysunku 2 przedstawiono ogólny zarys pojęć omawianych w tej książce oraz sposób, w jaki są one ze sobą związane. Rozdziały 7, 11 i 13 (ciemniejsze pola na rys. 2) zawierają więcej treści technicznych. Rozdziały te można pominąć i ich znajomość nie jest konieczna, by zrozumieć resztę książki.

Choć treść tej książki jest uporządkowana w określony sposób, nie trzeba jej czytać właśnie w tej kolejności. Wiele rozdziałów można czytać niezależnie od siebie, nawet jeśli dalsze rozdziały tej książki odnoszą się do pojęć i przykładów, które zostały wcześniej wprowadzone.

Poniżej znajduje się przewodnik ułatwiający wybór rozdziałów, które chcemy przeczytać oraz ustalenie kolejności lektury. Wskazuje on również drogi wyjścia i skróty, które pozwolą przeskoczyć do przodu w trakcie lektury. Choć omawiam pojęcia informatyczne za pomocą wydarzeń, ludzi i przedmiotów pojawiających się w opowieściach, niekiedy wprowadzam również nowe sposoby notacji i omawiam przykłady, by bardziej szczegółowo pokazać pewne ważne kwestie. Jako czytelnik wielu książek popularnonaukowych jestem w pełni świadomy faktu, że głód takich szczegółów może być różny. Dlatego mam nadzieję, że ten przewodnik ułatwi czytelnikom poruszanie się po książce.

Rysunek 2. Pojęcia związane z przetwarzaniem i to, jak się ze sobą łączą

Sugeruję, by najpierw przeczytać rozdziały 1 i 2, ponieważ zawierają podstawowe pojęcia informatyczne, które pojawiają się w całej książce, takie jak algorytm, parametr, komputer czy złożoność czasowa. Lektura tych dwóch rozdziałów powinna być łatwa.

Pozostałych sześć obszarów tematycznych (jaśniejsze pola na rys. 2) jest w dużym stopniu niezależne od siebie, ale w obrębie każdego z nich rozdziały należy czytać po kolei. W rozdziale 4 wprowadziłem kilka struktur danych, a więc powinno się go czytać przed rozdziałem 5, 6, 8, 12 i 13 (tak jak ilustruje to diagram powyżej).

I wreszcie słowniczek na końcu książki – są w nim zawarte dodatkowe informacje na temat związków między rozdziałami, grupujące definicje w obszary tematyczne i łączące poszczególne hasła w sieć.

Część I

ALGORYTMY

Przetwarzanie i algorytmy

Jaś i Małgosia

PORANNE WSTAWANIE

Jest wczesny poranek. Dzwoni budzik. Ostatecznie udaje nam się wygramolić z łóżka. Ubieramy się. Ten prosty, codzienny schemat związany z porannym wstawaniem za pomocą szeregu dobrze określonych kroków rozwiązuje powtarzający się problem. W informatyce taki rutynowy sposób postępowania jest nazywany algorytmem. Branie prysznica, mycie zębów, jedzenie śniadania i tak dalej – wszystko to są kolejne przykłady algorytmów rozwiązujących określone problemy.

Ale chwileczkę! Pomijając to, że mogliśmy się nie wyspać, to co w zasadzie stanowi tu problem? Prozaicznych, codziennych czynności nie postrzegamy zwykle jako rozwiązań problemów. Być może dzieje się tak dlatego, że problemy te mają oczywiste rozwiązania albo że ich rozwiązanie jest łatwe. Słowo problem jest jednak powszechnie używane do określenia sytuacji czy też pytań, które mają dobrze znane rozwiązania. Pomyślmy o egzaminach, na których pojawiają się pytania mające dobrze określone odpowiedzi. Problemem jest więc dowolne pytanie lub sytuacja, która domaga się rozwiązania, nawet jeśli jasne jest, jak je osiągnąć. W tym znaczeniu konieczność porannego wstania z łóżka stanowi problem, któremu towarzyszy dobrze znana metoda dająca jego rozwiązanie.

Gdy już dowiemy się, jak rozwiązać problem, rzadko zastanawiamy się, w jaki sposób wymyślono odpowiadającą temu rozwiązaniu metodę. W szczególności, gdy metoda jest oczywista i prosta w użyciu, rozmyślanie o niej wydaje się bezcelowe. Namysł nad tym jak możemy rozwiązywać problemy może nam jednak pomóc rozwiązać nieznane problemy w przyszłości. Rozwiązania problemów nie zawsze są bezsporne. Z perspektywy czasu większość rozwiązań wydaje się bezdyskusyjna, co jednak, gdybyśmy nie wiedzieli, jak rozwiązać problem porannego wstawania? Jak byśmy do tego podeszli?

Kluczowa jest tu obserwacja, że nietrywialne problemy można rozłożyć na podproblemy i że rozwiązania tych podproblemów można połączyć w rozwiązanie problemu wyjściowego. Problem porannego wstawania składa się z dwóch podproblemów: wygramolenia się z łóżka i ubrania się. Mamy algorytmy pozwalające rozwiązać oba te problemy, to znaczy, odpowiednio, wydostać nasze ciało z łóżka i włożyć ubranie. Możemy połączyć te algorytmy w jeden algorytm rozwiązujący problem porannego wstawania, choć musimy uważać, by zrobić wszystko we właściwej kolejności. Skoro ubieranie się w łóżku jest raczej trudne, powinniśmy najpierw wykonać krok polegający na wstaniu z niego. Jeśli ten przykład nas nie przekonuje, pomyślmy o kolejności, w jakiej można brać prysznic i się ubierać. W tym prostym przykładzie istnieje tylko jedna kolejność wykonywania tych kroków, która wiedzie do sensownego rozwiązania, choć nie zawsze tak bywa.

Rozkładanie problemów nie ogranicza się do jednego poziomu. Problem ubierania się można na przykład rozłożyć dalej na kilka podproblemów, takich jak wkładanie spodni, koszuli, butów i tak dalej. Sympatyczną cechą rozkładania problemów jest to, że pomaga to uczynić proces znajdowania rozwiązań modułowym, co znaczy, że rozwiązania różnych podproblemów mogą być opracowywane niezależnie od siebie. Modułowość jest ważna, ponieważ pozwala zespołom na równoległe opracowywanie rozwiązań.

Zaprojektowanie algorytmu rozwiązującego problem nie kończy sprawy. By rzeczywiście rozwiązać problem, algorytmu trzeba użyć. Wiedza o tym, jak coś zrobić i faktyczne zrobienie tego to dwie różne rzeczy. Niektórzy z nas boleśnie przekonują się o tej różnicy każdego ranka, gdy budzik zaczyna dzwonić. Jest więc różnica między algorytmem a jego użyciem.

W informatyce każde użycie algorytmu jest nazywane przetworzeniem. Czy znaczy to, że gdy rzeczywiście wstajemy o poranku, przetwarzamy się z łóżka w ubranie? Brzmi to niedorzecznie, ale co powiedzielibyśmy o robocie robiącym to samo? Robot musi zostać zaprogramowany, by wykonać zadanie. Innymi słowy, algorytm zostaje opowiedziany robotowi w zrozumiałym dla niego języku. Gdy robot wykonuje swój program, by wstać z łóżka, czy nie powiedzielibyśmy, że dokonuje przetwarzania? Nie znaczy to, że ludzie to roboty, ale pokazuje, że wykonując algorytmy, ludzie faktycznie dokonują przetwarzania.

Potęga algorytmów wynika z faktu, że można je wykonywać wielokrotnie. Jak przysłowiowe koło, którego nie trzeba wymyślać na nowo, dobry algorytm, gdy już zostanie opracowany, zostanie z nami i będzie nam służyć przez wieki. Będzie ponownie wykorzystywany przez wiele osób w wielu sytuacjach, by dzięki rzetelnemu przetwarzaniu rozwiązywać powracające problemy. To dlatego algorytmy odgrywają kluczową rolę w informatyce, a projektowanie algorytmów jest jednym z najważniejszych i najbardziej ekscytujących zadań dla informatyka.

Informatykę można nazwać nauką o rozwiązywaniu problemów. Nawet jeśli nie znajdziemy tej definicji w zbyt wielu podręcznikach, perspektywa ta stanowi użyteczne przypomnienie, dlaczego dyscyplina ta wpływa na coraz więcej i więcej obszarów naszego życia. W wielu przypadkach przetwarzanie odbywa się w pożyteczny sposób poza maszyną i jest dokonywane przez ludzi (niemających informatycznego wykształcenia) w celu rozwiązania problemów. W rozdziale 1 wprowadzam pojęcie przetwarzania i – dzięki opowieści o Jasiu i Małgosi – uwydatniam te jego aspekty, które dotyczą ludzi oraz rozwiązywania problemów.

1. Droga do zrozumienia przetwarzania

Czym jest przetwarzanie? Pytanie to znajduje się w samym centrum informatyki. Rozdział ten daje na nie – przynajmniej wstępną – odpowiedź i łączy pojęcie przetwarzania z innymi, blisko związanymi z nim pojęciami. W szczególności, wyjaśniam w nim związek między przetwarzaniem a pojęciem rozwiązywania problemu oraz pojęciem algorytmu. W tym celu opisuję dwa dopełniające się aspekty przetwarzania: to, co ono robi, oraz to, czym jest.

Pierwsza perspektywa, zgodnie z którą przetwarzanie rozwiązuje problemy, kładzie nacisk na to, że problem może zostać rozwiązany dzięki przetwarzaniu, o ile zyska odpowiednią reprezentację i zostanie podzielony na podproblemy. Nie tylko odzwierciedla to ogromny wpływ, jaki informatyka wywarła na tak wiele różnych obszarów życia, ale wyjaśnia również, dlaczego przetwarzanie jest kluczowym elementem wszelkiego rodzaju ludzkich działań, niezależnie od wykorzystania maszyn przetwarzających.

Perspektywa ta nie obejmuje jednak pewnego istotnego aspektu przetwarzania. Bliższe spojrzenie na różnice między przetwarzaniem a rozwiązywaniem problemów prowadzi w kierunku drugiego punktu widzenia, zgodnie z którym przetwarzanie to wykonywanie algorytmu. Algorytm to precyzyjny opis przetwarzania, który sprawia, że możliwe staje się jego zautomatyzowanie i analizowanie. Perspektywa ta przedstawia przetwarzanie jako proces składający się z kilku kroków, co pomaga wyjaśnić jak i dlaczego jest ono tak efektywne w rozwiązywaniu problemów.

Klucz do ujarzmienia przetwarzania leży w zgrupowaniu podobnych problemów w jedną klasę i zaprojektowaniu algorytmu, który rozwiązuje każdy z należących do niej problemów. Czyni to algorytm czymś podobnym do jakiejś umiejętności. Do umiejętności – na przykład umiejętności upieczenia ciasta lub naprawienia samochodu – można odwołać się w różnych momentach i stąd można z niej korzystać wielokrotnie w celu rozwiązania różnych przypadków należących do danej klasy problemów. Umiejętności można również nabywać i dzielić je z innymi, co pozwala im oddziaływać jeszcze szerzej. W podobny sposób możemy wielokrotnie wykonać jakiś algorytm w celu rozwiązania różnych przypadków problemów i z każdym wykonaniem dokonywać przetwarzania rozwiązującego aktualny problem.

Rozmienianie problemów na drobne

Na początku skorzystajmy z tej pierwszej perspektywy i rozważmy przetwarzanie jako proces rozwiązujący określony problem. Jako przykładu użyję dobrze znanej opowieści o Jasiu i Małgosi – rodzeństwie, które zostało pozostawione w lesie przez rodziców na pastwę losu. Przyjrzyjmy się błyskotliwemu pomysłowi Jasia, dzięki któremu udało im się wrócić do domu z leśnej głuszy. Historia ta dzieje się w kontekście panującego głodu: macocha Jasia i Małgosi namawia ich ojca, by zaprowadzić dzieci do lasu i tam je zostawić, aby rodzice mogli przetrwać. Usłyszawszy przypadkiem rozmowę rodziców, Jaś jeszcze tej samej nocy wychodzi na zewnątrz i zbiera kilka garści małych kamyków, które wpycha do swoich kieszeni. Następnego dnia, idąc przez las, rzuca wzdłuż trasy kamyki, znacząc za ich pomocą drogę wiodącą z powrotem do domu. Gdy rodzice je zostawili, dzieci poczekały, aż się ściemni, a kamyki zaczęły błyszczeć w świetle księżyca. Następnie podążyły ich śladem, aż trafiły do domu.

Opowieść nie kończy się w tym miejscu, ale ta jej część daje nam osobliwy przykład tego, jak problem zostaje rozwiązany dzięki przetwarzaniu. Problem, który wymaga tu rozwiązania, to problem przetrwania – kwestia znacznie poważniejsza od porannego wstawania. Problem przetrwania przedstawia się tu jako zadanie polegające na przemieszczeniu się z pewnego miejsca w lesie do miejsca, w którym znajduje się dom Jasia i Małgosi. Jest to problem nietrywialny, szczególnie, że nie da się go rozwiązać w jednym kroku. Problem, który jest zbyt złożony, by rozwiązać go w jednym kroku, musi zostać podzielony na podproblemy, które są łatwe do rozwiązania i których rozwiązania mogą zostać połączone w jedno rozwiązanie odnoszące się do całościowego problemu.

Problem znalezienia drogi pozwalającej wydostać się z lasu można rozłożyć na podproblemy identyfikując ciąg położeń pośrednich, które są wystarczająco blisko siebie, by można było między nimi łatwo się przemieszczać. Położenia te tworzą drogę wiodącą z lasu z powrotem do domu Jasia i Małgosi, a pojedyncze przemieszczenia z jednego miejsca na drugie dają się łatwo wykonać. Wzięte razem, skutkują przemieszczeniem się z położonego w lesie miejsca początkowego do domu. Przemieszczanie to w metodyczny sposób rozwiązuje problem Jasia i Małgosi, jakim jest przetrwanie. Metodyczność rozwiązywania problemów to jedna z kluczowych cech przetwarzania.

Jak pokazuje ten przykład, przetwarzanie składa się zwykle nie z jednego, ale z wielu kroków. Każdy z tych kroków stanowi rozwiązanie podproblemu i odrobinę zmienia problemową sytuację. Na przykład każde przemieszczenie się Jasia i Małgosi do kolejnego kamyka stanowi krok przetwarzania, który zmienia ich położenie w lesie, co odpowiada rozwiązaniu podproblemu polegającego na osiągnięciu kolejnego celu na drodze wiodącej do domu. Choć w większości przypadków każdy pojedynczy krok będzie sprawiać, że dzięki przetwarzaniu znajdziemy się bliżej rozwiązania, nie musi tak być w przypadku każdego kroku. Jedynie wszystkie kroki razem muszą dawać rozwiązanie. W naszej opowieści, choć każde miejsce, przez które Jaś i Małgosia przechodzą, ogólnie rzecz biorąc będzie się znajdować bliżej domu, prawdopodobne jest, że ich trasa nie będzie linią prostą. Niektóre kamyki mogą prowadzić trasą okrężną, pozwalając na przykład na ominięcie przeszkód czy przejście przez most. Nie zmienia to jednak łącznego wyniku przemieszczeń.

Waga tej nauki polega na tym, że rozwiązanie uzyskiwane jest dzięki systematycznemu rozkładaniu problemu na mniejsze części. Choć rozkładanie takie jest kluczową strategią pozwalającą na uzyskanie rozwiązania problemu, to nie zawsze wystarcza – rozwiązania mogą zależeć od dodatkowych obiektów, którymi w przypadku Jasia i Małgosi są kamyki.

Nie ma przetwarzania bez reprezentacji

Jeśli przetwarzanie składa się z określonej liczby kroków, to co się dzieje za sprawą każdego z tych kroków i jak to możliwe, że wszystkie razem dają rozwiązanie danego problemu? Aby mógł powstać efekt końcowy, każdy krok musi dawać efekt, na którym może się oprzeć kolejny krok – tak, aby łączny efekt wszystkich kroków dawał rozwiązanie problemu. W naszej opowieści rezultatem każdego kroku jest zmiana położenia Jasia i Małgosi, a problem zostaje rozwiązany, gdy położenie to ostatecznie staje się zgodne z położeniem ich domu. Mówiąc ogólnie, krok przetwarzania może wpływać niemal na wszystko – na konkretne, fizyczne przedmioty czy na matematyczne byty abstrakcyjne.

Do rozwiązania problemu konieczne jest, aby przetwarzanie przekształcało reprezentację czegoś, co ma znaczenie w świecie rzeczywistym. Położenia Jasia i Małgosi reprezentują dwa możliwe stany: wszystkie położenia w lesie reprezentują problemowy stan zagrożenia i możliwej śmierci, a ich dom reprezentuje stan będący rozwiązaniem – bezpieczeństwo i przetrwanie. To dlatego przetwarzanie, które prowadzi Jasia i Małgosię do domu, rozwiązuje problem – sprawia ono, że dzieci przemieszczają się z miejsca pełnego niebezpieczeństw do takiego, gdzie jest bezpiecznie. Inaczej byłoby w przypadku przetwarzania prowadzącego z jednego miejsca w lesie do innego miejsca w lesie, które nie dawałoby takiego skutku.

Rysunek 1.1. Przetwarzanie jest procesem służącym do rozwiązania konkretnego problemu. Przetwarzanie składa się zwykle z kilku kroków. Wychodząc od reprezentacji problemu, każdy krok przekształca tę reprezentację, aż uda się osiągnąć rozwiązanie. Jaś i Małgosia rozwiązują problem przetrwania w procesie zmiany swojego położenia, krok po kroku, kamyczek po kamyczku przemieszczając się z głębi lasu do swojego domu

Przykład ten zawiera jeszcze jeden poziom reprezentacji. Skoro przetwarzanie zdefiniowane przez przemieszczenia między położeniami jest dokonywane przez Jasia i Małgosię, położenia te muszą być dla nich rozpoznawalne. To dlatego Jaś przez całą drogę rzuca kamyki. Kamyki reprezentują położenia w postaci umożliwiającej komputerowi, czyli Jasiowi i Małgosi, faktyczne wykonanie kolejnych kroków przetwarzania. Często spotyka się kilka warstw reprezentacji. W tym przypadku mamy do czynienia z jedną warstwą, która definiuje problem (położenia) i jedną, która umożliwia, by przetwarzanie dało rozwiązanie (kamyki). Dodatkowo, wszystkie kamyki razem tworzą kolejny poziom reprezentacji, reprezentują one bowiem drogę wiodącą z głębi lasu z powrotem do domu. Reprezentacje te zbiorczo są ujęte w tabeli 1.1.

Rysunek 1.1 stanowi podsumowanie tego, czym jest przetwarzanie widziane z perspektywy rozwiązywania problemów. Przedstawia on próbę odnalezienia drogi przez Jasia i Małgosię jako przykład spojrzenia na przetwarzanie jak na przekształcanie reprezentacji w pewnej sekwencji kroków. W przypadku problemu porannego wstawania również odnajdujemy reprezentacje, na przykład w postaci położenia (w łóżku, poza łóżkiem) oraz budzika reprezentującego czas. Reprezentacje mogą przybierać różne formy. Bardziej szczegółowo są one omówione w rozdziale 3.

Tabela 1.1

Reprezentacja przetwarzania

Reprezentacja problemu

Obiekt

Reprezentuje

Pojęcie

Reprezentuje

Jeden kamyk

Położenie w lesie

Położenie w lesie

Zagrożenie

Dom

Dom

Bezpieczeństwo

Wszystkie kamyki

Droga z lasu

Droga z lasu

Rozwiązanie problemu

Coś więcej niż rozwiązywanie problemów

Spojrzenie na przetwarzanie jako na proces prowadzący do rozwiązania problemu uwzględnia jego cel, ale nie wyjaśnia, czym przetwarzanie tak naprawdę jest. Co więcej, perspektywa ta ma pewne ograniczenia, ponieważ nie zawsze rozwiązanie problemu polega na przetwarzaniu.

Jak ilustruje rysunek 1.2, jest przetwarzanie i jest rozwiązywanie problemów. Choć jedno i drugie często na siebie zachodzi, przetwarzanie nie zawsze rozwiązuje problemy, a niektóre problemy mają rozwiązania niewymagające przetwarzania. W tej książce akcent jest położony na obszar, w którym przetwarzanie i rozwiązywanie problemów się przecinają, ale aby uczynić tę kwestię bardziej wyraźną, rozważę pewne przykłady ilustrujące dwie pozostałe możliwości.

Aby zrozumieć pierwszą z nich, wyobraźmy sobie przetwarzanie, w ramach którego przemieszczamy się od kamyka do kamyka, z jednego miejsca w lesie do innego miejsca w lesie. Kroki tego procesu są co do zasady takie same jak w pierwotnej opowieści, ale odpowiadająca im zmiana położenia nie rozwiązałaby problemu przetrwania, przed jakim stoją Jaś i Małgosia. Jeszcze drastyczniejszy przykład byłby taki: wyobraźmy sobie sytuację, w której kamyki układają się w pętlę, co znaczy, że związane z nimi przetwarzanie wydaje się prowadzić donikąd, gdyż początkowe i końcowe położenie jest identyczne. Innymi słowy, przetwarzanie nie daje żadnego łącznego rezultatu. Różnica między tymi dwoma przypadkami, a tym opisanym w opowieści wynika ze znaczenia, jakie jest nadawane temu procesowi.

Procesy pozbawione takiego wyraźnego znaczenia nadal można zakwalifikować jako przetwarzanie, ale nie można ich postrzegać jako rozwiązania problemu. Ten przypadek nie jest znowu taki ważny, ponieważ zawsze możemy przypisać jakieś arbitralne znaczenie reprezentacji wykorzystywanej w danym przetwarzaniu. Tak więc dowolne przetwarzanie można by pewnie uznać za rozwiązanie problemu. Zawsze zależy to od znaczenia, jakie wiążemy z reprezentacją. Na przykład poruszanie się w lesie po trasie w kształcie pętli mogłoby nie pomóc Jasiowi i Małgosi, mogłoby jednak rozwiązać jakiemuś biegaczowi problem treningowy. Tak więc to, czy przetwarzanie rozwiązuje jakiś problem jest względne, co znaczy, że zależy od użyteczności przetwarzania. W tym przypadku to, czy ktoś uzna, że jakieś konkretne zastosowanie przetwarzania ma status rozwiązania problemu, czy nie, nie wpływa na istotę tego przetwarzania.

Sytuacja jest znacząco inna w przypadku rozwiązywania problemu niezwiązanego z przetwarzaniem, jako że podsuwa nam ono kolejne kryteria tego, czym jest przetwarzanie. Na rysunku 1.2 są zilustrowane dwa takie kryteria, które w rzeczywistości są ze sobą ściśle związane. Po pierwsze, jeśli problem zostaje rozwiązany ad hoc, w sposób nieoparty na jakiejś konkretnej metodzie, nie mamy do czynienia z przetwarzaniem. Innymi słowy, przetwarzanie musi mieć charakter metodyczny. W naszej opowieści możemy znaleźć kilka przypadków problemów, które udało się rozwiązać w sposób niezwiązany z przetwarzaniem. Jeden z nich pojawia się, gdy Jaś i Małgosia są przetrzymywani przez Babę Jagę, która próbuje utuczyć Jasia, by następnie go zjeść. W związku z tym, że ma ona słaby wzrok, masę Jasia szacuje, macając jego palec. Jasiowi udaje się ją zwieść co do swej masy, podsuwając jej małą kostkę zamiast palca. Pomysł ten nie stanowi rezultatu metodycznego przetwarzania, ale rozwiązuje problem – dzięki temu udaje się opóźnić zjedzenie Jasia przez Babę Jagę.

Inny przykład rozwiązania problemu niebędącego przetwarzaniem pojawia się tuż po tym, jak Jaś i Małgosia wracają do domu. Rodzice planują, że następnego dnia ponownie wywiodą rodzeństwo do lasu, ale tym razem macocha wieczorem zamyka drzwi, aby uniemożliwić Jasiowi zebranie kamyków. Problemem jest tutaj to, że Jaś nie może uzyskać dostępu do kamyków, które tak bardzo przydały mu się za pierwszym razem i na których mógł polegać, szukając drogi powrotnej do domu. Jego rozwiązanie polega na znalezieniu zamiennika w postaci okruszków chleba. Istotne jest to, w jaki sposób Jaś dochodzi do tego rozwiązania – ma pomysł, przychodzi mu do głowy twórcza myśl. Ogólnie rzecz biorąc, rozwiązanie pojawiające się w chwili olśnienia jest bardzo trudne – jeśli nie niemożliwe – do uzyskania w metodyczny sposób za pomocą przetwarzania, ponieważ wymaga rozumowania dokonującego się na bardzo subtelnym poziomie, a dotyczącego przedmiotów i ich własności.

Rysunek 1.2. Rozróżnienie między rozwiązywaniem problemów a przetwarzaniem. Przetwarzanie, którego rezultat nie ma znaczenia w świecie rzeczywistym, nie rozwiązuje żadnego problemu. Rozwiązanie problemu ad hoc, które nie jest powtarzalne, nie jest przetwarzaniem

Przypisy

Wprowadzenie

[1] John Dewey, „The Pattern of Inquiry”, w: Logic: Theory of Inquiry (1938).

KSIĄŻKI TEGO AUTORA

Dawno temu był sobie algorytm