Dawno temu był sobie algorytm. Czyli jak książki, filmy i życie codzienne wyjaśniają nam dziedzinę algorytmów - ebook

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”.

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ć.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.