Wykształcenie jest tym, co pozostaje, gdy zapomni się to, czego nauczyliśmy się. [B.F. Skinner] Wszystko powinno być tak proste, |
Artykuł jest adresowany zarówno do tych, dla których ta książka jest pierwszym spotkaniem z algorytmami, jak i do tych, którzy skorzystają z niej, by na nowo odkrywać znane już algorytmy. W szczególności, może być bardzo przydatna w szkołach nauczycielom do prowadzenia zajęć o algorytmach – na lekcjach informatyki, matematyki, techniki i twórczości, i w uczelniach – jako wprowadzenie do algorytmiki. Podejście do nauczania o algorytmach zaproponowane w tej książce, jak i rozważania w tym artykule, mają na celu uczynienie z zajmowania się algorytmami takich działań, które pozostawią w uczących się jak największy i najtrwalszy ślad – stanowiący wkład w wykształcenie w rozumieniu Skinnera z powiedzenia zacytowanego powyżej.
Dla nikogo nie powinno być zaskoczeniem, że chociaż komputery powstawały, by wspomóc człowieka, to pomagają nam na tyle, na ile sami jesteśmy w stanie przygotować je do tego. Kiedyś człowiek usprawniał swoje bezpośrednie działanie, a teraz usprawnia działanie komputerów, by te jeszcze lepiej mu służyły – w tym celu buduje nowe i polepsza znane algorytmy, według których działają te maszyny. Czy umiejętność tworzenia i ulepszania algorytmów jest potrzebna każdemu człowiekowi? W tym artykule można znaleźć uzasadnienie, dlaczego w uczeniu się i w nauczaniu powinno znaleźć się miejsce na zajmowanie się tworzeniem również algorytmów. Umiejętność ta bowiem ma wpływ na rozwój twórczego myślenia uczniów, a także kładzie podwaliny pod przyszłe ich działania związane z rozwiązywaniem problemów, które dopiero mogą się pojawić.
Algorytmy to nie jest książka przeznaczona tylko dla dobrego ucznia i przygotowanego nauczyciela. Można powiedzieć przewrotnie – więcej z niej może skorzystać nowicjusz-uczeń i nowicjusz-nauczyciel, przebywając drogę od problemów do algorytmów “o własnych siłach”, niż wyręczając się w tym gotowymi przepisami. Dla nich rozkosz tworzenia i osiągania może być bardziej pociągająca niż smak gotowej potrawy.
1. Najstarsza historia
Od początków swojego istnienia człowiek zawsze upraszczał swoje czynności i działania, od: wzniecania ognia, budowania piramid, wysyłania wiadomości, wychodzenia z labiryntu i optymalnego poruszania się po drogach, aż po sterowanie maszynami, porządkowanie obiektów i informacji, sortowanie poczty i pakowanie plecaka. Zwykle, pierwszym zamierzeniem w nowym działaniu jest osiągnięcie wyznaczonego celu w jakikolwiek sposób. Korzysta się przy tym na ogół, często nieświadomie, z posiadanej już wiedzy i umiejętności zdobytych przy znajdowaniu rozwiązań innych problemów. Gdy już potrafimy coś zrobić, zastanawiamy się, jak to można zrobić prościej, lepiej, mniejszym wysiłkiem, szybciej, a czasem – stać nas na luksus zrobienia czegoś piękniej, z większą elegancją i przyjemnością.
Niemal jednocześnie z pojawieniem się pierwszych zadań do wykonania, człowiek zaczął sięgać po różne narzędzia, które miały mu w tym pomóc. Myśl plus pomoc (narzędzie) z czasem przeradzały się w technikę lub technologię.
1.1. Jak budowano piramidy
Jedną z zagadek, jaką pozostawiła nam po sobie starożytność, jest pytanie, w jaki sposób 4500 lat temu budowano piramidy, czyli według jakiego algorytmu postępowano. Przypuszcza się nawet, że w tym przypadku ewolucja ma jakby przeciwny kierunek, gdyż dzisiaj, z całą współczesną techniką, człowiek nie jest w stanie powtórzyć tamtych wyczynów. Weźmy pod uwagę suche liczby. Na przykład, piramida Cheopsa ma wysokość 146 m i jest oparta na kwadracie o boku 230 m. Jeśli przyjmiemy dla ułatwienia, że jest ona zbudowana z jednakowych bloków o wymiarach podstawy 3 m na 3 m i 2 m wysokości, to cała piramida składa się z około 123 tys. takich bloków! Przypuśmy, że budowano ją po 14 godzin dziennie, od świtu do zmroku, przez 20 lat – faraonowie na ogół żyli dość krótko. Z prostych obliczeń wynika, że co 50 min. musiał być ustawiany na swoim miejscu jeden taki blok. (W rzeczywistości, piramidę Cheopsa zbudowano z niejednorodnych kamiennych bloków – jest ich ponad dwa miliony, każdy waży ponad tonę, a średnio – około 2.5 tony, ale są również bloki ważące 20 ton. Oszacowano, że w trakcie jej budowania na swoje miejsce trafiało około 340 bloków dziennie – zob. [3] oraz [10].) Nie mówimy już tutaj o wycinaniu tych bloków – a zostały one spasowane z dokładnością do 1/50 cala tak, że dzisiaj nie można między nie wcisnąć nawet żyletki. Oszacowano, że przy budowie jednej piramidy uczestniczyło jednocześnie około 36 tys. robotników – więcej osób przeszkadzałoby sobie przy pracy.
Innym pytaniem jest, jak radzono sobie z utrzymaniem (wyżywieniem i zakwaterowaniem) takiej rzeszy robotników. Na ogół przyjmuje się, że pracowali oni bez sprzeciwu, a nawet bardzo chętnie, z poczuciem zaszczytu wykonywania przysługi swojemu władcy. Niewątpliwie, nie wszyscy byli z tego zadowoleni.
Nie znamy więc algorytmu, według którego organizowano budowę piramid. Budowle te jednak stoją do dzisiaj, jest ich ponad 400, a więc ich twórcom musiał być znany algorytm ich budowania, którego nie potrafimy dzisiaj odtworzyć. Posługiwano się zapewne zasadami, które nazwano i sformalizowano znacznie później: dziel i rządź (łac. divida et impera) – odpowiedni podział siły roboczej zapewniał posłuszeństwo – oraz dziel i zwyciężaj (ang. divide and conquere) – podział pracy z dobrze zaplanowaną komunikacją i współdziałaniem między grupami był niewątpliwie jedną z podstawowych zasad postępowania w przedsięwzięciu na taką skalę, które w ostateczności przyniosło zwycięstwo w postaci ukończonych budowli.
Przeważa pogląd, że piramidy budowali mieszkańcy tej Ziemi, chociaż istnieją teorie (np. Ericha von Daenikena), według których te budowle zostały postawione jeszcze przed narodzeniem się faraonów lub są dziełem przybyszów z innych planet lub układów słonecznych, podobnie jak posągi na Wyspie Wielkanocnej i mosty Majów. Nie udało się jednak dotychczas potwierdzić eksperymentalnie żadnej teorii budowania piramid, a podejmowane próby na mniejszą skalę skończyły się fiaskiem. Sytuacja jest więc taka, że wynik zastosowania algorytmu jest znany – bo piramidy stoją – natomiast nie znamy algorytmu.
Zainteresowanych szczegółowymi rozważaniami na ten temat odsyłamy do stron WWW [10].
1.2. Pierwsze algorytmy
W pracy koncepcyjnej, umysłowej, dość wcześnie zaczęto tworzyć opisy postępowań, mających na celu otrzymanie rozwiązania postawionego problemu lub wskazanie drogi do osiągnięcia wyznaczonego celu. Pierwsze takie opisy, które dzisiaj nazwalibyśmy algorytmami, dotyczyły wykonywania działań matematycznych. Za najwcześniejszy algorytm uważa się podany około 300 lat przed naszą erą algorytm Euklidesa, który jest przepisem na znajdowanie NWD(m,n) – największego wspólnego dzielnika dwóch liczb całkowitych m i n (zob. p. 7.4).
Wiele wieków wsześniej jednak, w Babilonie, Indiach, Chinach i w Egipcie, posługiwano się przepisami wykonywania działań matematycznych, które można również nazwać algorytmami. Jeden z takich algorytmów został podany przez egipskich matematyków 1800 lat p.n.e i dotyczył obliczania całkowitej wielokrotności liczby x, czyli nx, gdzie n jest liczbą naturalną. Ciekawostką jest, że posługiwano się w tym celu, niejawnie jednak, binarnym rozwinięciem liczby n. Na przykład, iloczyn 13x ma postać (1101)x, a wtedy y =13x można otrzymać w następującym ciągu operacji: y:=x, 2x:=x+x; 4x:=2x+2x, y:=y+4x, 8x:=4x+4x, i y:=y+8x. Zatem wielokrotność danej liczby można otrzymać posługując się operacjami: podwajania (sum częściowych), połowienia (współczynnika) i dodawania. Ta metoda jest znana również jako “metoda rosyjskich chłopów”, gdyż w XIX wieku była dość powszechnie stosowana na wsiach w Rosji. Dzisiaj raczej nie stosuje się jej, ale podobna idea jest wykorzystywana w binarnej metodzie podnoszenia do potęgi – zob. punkt 7.3.2.
Bardzo ważny algorytm opracowano w Chinach w XIII wieku (jego specjalny przypadek był znany również w Chinach, już w III wieku). Występuje on pod nazwą Chińskie Twierdzenie o Resztach i dotyczy reprezentacji liczb naturalnych w postaci ciągu reszt z dzielenia przez układ liczb pierwszych. Twierdzenie to ma dzisiaj bardzo duże znaczenie w obliczeniach na dużych liczbach i jest podstawą dla tzw. arytmetyki modularnej. Można o tym przeczytać w [1].
1.3. Urządzenia do wykonywania algorytmów
Równocześnie z tworzeniem algorytmów człowiek starał się pomagać sobie w różny sposób w ich wykonywaniu. W wykopaliskach między Mezopotamią a Indiami odnaleziono ślady stosowania już w X wieku p.n.e. systematycznych metod znajdowania wyniku prostych operacji za pomocą specjalnie przygotowanych i poukładanych kamieni. Początkowo kamienie układano w rzędach na piasku, tworząc w ten sposób plansze. Później zaczęto nawlekać kamienie na pręty, tworząc liczydła, które można było już przenosić w różne miejsca.
Pierwsze “urządzenia” pomagające w obliczeniach były konstrukcjami, które mocno zależały od przeznaczenia, czyli od rodzaju wykonywanych z ich pomocą działań. Porównując je z komputerami można powiedzieć, że dopiero elektroniczne maszyny cyfrowe stały się urządzeniami na tyle uniwersalnymi, że mogą być stosowane do wykonywania większości różnorodnych obliczeń, a wszystkie poprzednie konstrukcje były tworami “specjalnego przeznaczenia”. I tak, abakusy oraz później konstruowane liczydła są przeznaczone do wykonywania czterech podstawowych działań arytmetycznych, pierwsze arytmometry czy kalkulatory (np. zbudowane przez B. Pascala i G.W. Leibniza) można również stosować jedynie do podstawowych działań arytmetycznych – Pascal zbudował swoją Pascalinę, by pomagała jego ojcu, poborcy podatkowemu. Pierwsza konstrukcja Charlesa Babbage’a, maszyna różnicowa, była także zaprojektowana do wykonywania jedynie obliczeń według schematów różnicowych, a jej głównym przeznaczeniem było sporządzanie tablic matematycznych, wtedy, tj. na początku XIX wieku, tak bardzo potrzebnych w nawigacji i w obserwacjach astronomicznych.
Elementy historii komputerów i informatyki są zamieszczone w rodz. 1 podręcznika [4], zob. również [8]. Wiele faktów historycznych dotyczących algorytmów i komputerów znajduje się w ramkach na marginesach rozważań w książce.
1.4. Początki współczesnych komputerów
Na przełomie XIX i XX wieku zaczęto interesować się problemami obliczalności, a jednym z nich była kwestia określenia, co to jest algorytm i które problemy mogą być rozwiązywane za pomocą algorytmów. Badania w tym zakresie doprowadziły do powstania wielu matematycznych teorii obliczeń, które obecnie tworzą matematyczne podstawy informatyki. Zbiegło się to z początkami konstruowania elektronicznych maszyn cyfrowych, bezpośrednich poprzedników dzisiejszych komputerów. Wpływ teorii obliczeń na same konstrukcje był początkowo może niezauważalny, ale nie był to jedynie zbieg okoliczności, że najwięksi twórcy podstaw informatyki brali równocześnie udział przy konstruowaniu pierwszych komputerów. Zaliczyć do nich można Allana Turinga i Johna von Neumanna. Turing jest obecnie najbardziej znany jako twórca tzw. maszyny Turinga – teoretycznego modelu obliczeń, a także jako współtwórca maszyn Coloss, które były wykorzystywane przez Brytyjczyków w czasie II Wojny Światowej do rozpracowania niemickich maszyn szyfrujących Enigma. Von Neumann zaś wywarł olbrzymi wpływ na powstanie pierwszych amerykańskich komputerów ENIAC i EDVAC. Zajmował się również modelami mózgu, kładąc tym podwaliny pod dzisiejsze komputery neuronowe.
2. Początki algorytmiki
Dzisiejszy komputer działa według zadanego mu przepisu – nazwijmy go algorytmem … z braku w tej chwili innej, formalnej definicji algorytmu. Wynikają stąd pewne własności algorytmów, chociaż, jak już nadmieniliśmy, twory o tej nazwie powstawały na długo przed zbudowaniem pierwszego komputera i dzisiaj również tworzenie i stosowanie algorytmów nie jest jedynie domeną działalności osób, które zasiadają przy komputerach.
2.1. Nowe spojrzenie na stare algorytmy
Okazało się w wielu przypadkach, że twórcy algorytmów z czasów zanim powstały komputery kierowali się dobrą intuicją i ich twory spełniają większość warunków, które dzisiaj nakładamy na opisy działań, zwłaszcza komputerowych, zwane algorytmami. W wielu przypadkach te własności algorytmów zostały udowodnione dopiero niedawno. Na przykład okazało się, że algorytm Euklidesa (przedstawiony w p. 7.4) jest efektywny, a dokładniej – wielomianowy, czyli liczba wykonywanych w nim kroków nie jest większa od liczby bitów potrzebnych do zapamiętania większej z danych liczb. Z kolei, schemat Hornera (p. 7.2) jest wręcz algorytmem optymalnym, tzn. nie istnieje algorytm obliczania wartości wielomianu, w którym jest wykonywanych mniej dodawań i mnożeń niż w schemacie Hornera. Podobnie, optymalność najpopularniejszej, liniowej metody znajdowania najmniejszego lub największego elementu w zbiorze (p. 5.1.2), stosowanej zapewne od zarania ludzkości, wykazano ściśle dopiero w latach siedemdziesiątych (zob. p. 7.3 w [4])
2.2. Powstanie teorii obliczeń
Nie było i nie ma zgodności wśród autorów różnych książek o algorytmach i rozwiązywaniu problemów oraz badaczy algorytmów, co do definicji algorytmu. Przez wieki, od czasów Euklidesa, nie martwiono się jednak tym specjalnie, tylko tworzono opisy rozwiązywania różnych problemów i dzisiaj nazywamy je algorytmami. Nawet konstruktorzy pierwszych liczydeł, kalkulatorów i maszyn cyfrowych nie dociekali specjalnie, co to jest algorytm, lub raczej jak zdefiniować coś, co da się wykonać za pomocą ich maszyn. Można zrozumieć takie ich zachowanie, gdyż to, co chcieli rozwiązywać, obliczać lub wykonać, na ogół udawało się im.
Na przełomie XIX i XX wieku matematyków zainteresowało udzielenie odpowiedzi na dość ogólne pytanie: co można obliczyć, jakie funkcje są obliczalne, dla jakich problemów istnieją algorytmy, i ogólniej – czy wszystkie twierdzenia można udowodnić (lub obalić)? W 1901 roku David Hilbert, wśród wielu wyzwań dla matematyków zaczynającego się stulecia, jako dziesiąty problem sformułował pytanie: czy istnieje algorytm, który dla dowolnego równania wielomianowego wielu zmiennych o współczynnikach będących liczbami całkowitymi znajduje rozwiązanie w zbiorze liczb całkowitych? Dopiero po prawie siedemdziesięciu latach, J.V. Matijasiewicz odpowiedział, że taki algorytm nie może istnieć. Dziesiąty problem Hilberta wywołał olbrzymie zainteresowanie wśród matematyków obliczalnością – dziedziną, która zajmuje się poszukiwaniem odpowiedzi m.in. na pytanie, jakie problemy mają rozwiązanie w postaci algorytmu, a jakie nie mają.
Udzielenie odpowiedzi na pytanie dotyczące istnienia lub nieistnienia algorytmu wymaga sformalizowania pojęcia algorytmu. Można bowiem tworzyć opisy postępowań i uznawać je za algorytmy – wtedy, jeśli dla postawionego problemu umiemy podać algorytm jego rozwiązywania, to specjalnie nie interesuje nas, jaka powinna być formalna definicja algorytmu – przyjmujemy na ogół, że jest to opis postępowania, które zadawalająco (cokolwiek by to znaczyło) rozwiązuje nasz problem. Sytuacja zmienia się, gdy dla danego problemu nie udaje się stworzyć algorytmu. Wtedy algorytm może nie istnieć, ale aby to udowodnić, musimy posłużyć się precyzyjną definicją algorytmu i wykazać, że nie istnieje żaden twór o podanych własnościach algorytmu, który rozwiązuje dany problem. Jest dość intuicyjne, że na ogół znalezienie czegoś zabiera znacznie mniej czasu niż wykazanie, że coś poszukiwanego nie istnieje – aby się o tym przekonać, wystarczy sobie przypomnieć, ile czasu zabrało nam ostatnio nie znalezienie czegoś w domu.
Formalizacją dwóch pojęć: algorytm i obliczalność zajęło się w pierwszej połowie naszego stulecia wielu matematyków. Wprowadzono wiele różnych definicji obliczeń, przy czym większość z nich jest równoważna między sobą w tym sensie, że definiuje tę samą klasę funkcji obliczalnych. Do najpopularniejszych należy formalizm wprowadzony przez Allana Turinga, zwany dzisiaj maszyną Turinga. Ponieważ ta maszyna może wykonać obliczenia, które mogą być wykonane przez podobne “maszyny” lub “automaty” i ponieważ te maszyny mają cechy rzeczywistych komputerów, maszynę Turinga przyjmuje się za precyzyjną definicję intuicyjnego pojęcia algorytmu. Zatem, nie ma algorytmu problem, którego nie można rozwiązać za pomocą maszyny Turinga. Ta zasada, że maszyna Turinga jest sformalizowaną wersją algorytmu i że żadne postępowanie obliczeniowe, którego nie można przedstawić jako programu dla maszyny Turinga, nie może być nazwane algorytmem, nosi nazwę Tezy Churcha-Turinga.
Jaki stąd wypływa wniosek dla mniej sformalizowanych rozważań o algorytmach, nie korzystających z maszyny Turinga, na przykład prowadzonych w szkole lub w uczelni? Jest to bardzo ważne pytanie, gdyż zdecydowana większość książek poświęconych algorytmom, nie korzysta z formalnego pojęcia algorytmu. Na ogół, nie ma w nich również mowy o problemach, dla których nie istnieją algorytmy. Takiego podejścia nie można uznać za niepełne.
Jedna z najpopularniejszych książek dotyczących rozwiązywania problemów, zwłaszcza matematycznych, Jak to rozwiązać? George’a Polya [11], nie zawiera ani słowa o problemach matematycznych, które nie mają rozwiązań, chociaż w matematyce jest wiele takich problemów. Podobnie Hugo Steinhaus, w swojej przepięknej książce Kalejdoskop matematyczny [13] pisze jedynie o problemach, które mają rozwiązanie i można podać dla nich algorytmy.
W uczeniu o algorytmach, a ogólniej – w uczeniu rozwiązywania problemów, wcale nie jest niezbędne mówienie o problemach, które nie mają rozwiązań. Zwłaszcza, że wyniki dotyczące nierozwiązywalności problemów są w pewnym sensie mało intuicyjne i mało praktyczne. Na przykład, chociaż, zgodnie z dowodem Matijasiewicza, nie istnieje algorytm rozwiązywania jakiegokolwiek równania wielomianowego w zbiorze liczb całkowitych, to jednak wiele szczególnych, praktycznych równań potrafimy rozwiązywać za pomocą specjalnych algorytmów – zob. np. p. 7.5.1, gdzie jest omówiony algorytm rozwiązywania równania z dwoma niewiadomymi. Podobnie, problem stopu nie jest rozwiązywalny, tzn. nie istnieje algorytm stwierdzający, czy działanie jakiegokolwiek algorytmu zatrzyma się, czy nie (zob. bardzo prosty dowód tego faktu w pracy [9], zob. również [5]). Jednak w szczególnym przypadku konkretnego programu potrafimy zawsze określić, czy zapisany w nim algorytm ma skończone działanie, czy nie.
2.3. Definicja a opis algorytmu
Powyższe rozważania mogą służyć za uzasadnienie do wyjaśnienia, dlaczego w większości opracowań o algorytmach brak jest definicji pojęcia algorytm, a jeśli jest, to na ogół mało precyzyjna i rzadko dwie definicje pokrywają się. Wynika to stąd, że ścisła definicja algorytmu może być podana tylko na bazie bardzo formalnych rozważań na temat obliczalności. Dlatego na ogół definicję algorytmu zastępuje opis sposobu przedstawiania czy też reprezentowania algorytmów. Wtedy jakikolwiek opis sporządzony w przyjętej konwencji można uznać za poprawny opis algorytmu i – dzięki temu – opisywane postępowanie uznać za algorytm.
Tę dyskusję o definicji algorytmu możemy więc podsumować stwierdzeniem, że w rozważaniach o algorytmach, prowadzonych poza teorią obliczeń, postępuje się na ogół następująco:
Wtedy każde postępowanie, które potrafimy opisać (reprezentować) w przyjętej konwencji, można uznać za algorytm. Takie podejście przyjęto w książce, posługując się: listą kroków, drzewami, projektami w programie ELI oraz procedurami w języku Pascal, jako formami opisu algorytmów – zob. rozdz. 1 w książce oraz p. 4.1 dalej w tym artykule.
Czy algorytmy są niezbędnym elementem kształcenia? Postaramy się uzasadnić tutaj pogląd, że są to jedne z najważniejszych obiektów, jakie powinny pojawić się w trakcie uczenia się i nauczania. Przy czym, uprzedzając nasze uzasadnienie trzeba powiedzieć, że nie chodzi o nauczanie samych algorytmów, jako gotowych przepisów postępowania lub programów dla komputerów. Nauczaniem o algorytmach powinny rządzić ogólniejsze zasady, którym jest podporządkowana cała edukacja. Nie wszystkie zasady mają jednak decydujące znaczenie – wspomnimy jedynie o najważniejszych.
Obecna reforma szkolnictwa w Polsce ma na celu m.in. zbliżenie szkoły do indywidualnych oczekiwań oraz możliwości uczniów. W tym celu szkoła powinna umożliwiać i podsycać działania związane z nieskrępowaną twórczością uczniów. Znakomicie poddaje się temu cała dziedzina związana z rozwiązywaniem problemów, do której można zaliczyć również tę część algorytmiki, która jest rozumiana jako poszukiwanie rozwiązań problemów w postaci algorytmów.
Algorytm, rozumiany jako wynik rozwiązywania problemu, narzuca pewne reguły na sposoby pojawiania się ich w procesie uczenia się i nauczania. O algorytmach nie można uczyć w sposób statyczny, zamknięty, czy programowany, chociaż najczęściej docelowa postać algorytmu ma postać ścisłego opisu (np. jako program) kolejnych działań (kroków), które mają być wykonane. Algorytm nie powinien być podawany jako gotowa odpowiedź, będąca rozwiązaniem rozważanego problemu, gdyż jednym z głównych celów nauki rozwiązywania problemów jest poznanie i przyswojenie sobie przez uczącego się ogólnej wiedzy o rozwiązywaniu problemów i tworzeniu rozwiązań, użytecznej przede wszystkim w sytuacjach, gdy pojawiają się nowe problemy.
Na początku artykułu przytoczyliśmy słowa Skinnera określające, czym jest wykształcenie. Jest zapewne wiele słuszności w tym błyskotliwym określeniu zarówno wykształcenia, jak i, ogólniej, efektów uczenia się. Ile może wnieść do wykształcenia w tym sensie poświęcanie w szkole czasu na algorytmikę? Algorytmy, jako gotowe twory, na pewno nie są tymi obiektami, które, w swym precyzyjnym sformułowaniu, pozostawiają wiele w wykształceniu. Ale już w połączeniu z problemami, których są rozwiązaniem, stanowią pewien ślad, odnawialny w zbliżonych sytuacjach problemowych.
Jeszcze większe znaczenie mają wyryte w świadomości uczniów drogi postępowania, prowadzące do algorytmicznych rozwiązań problemów, “obsadzone na poboczach” przykładami z otoczenia uczniów, rzeczywistymi problemami z życia, skojarzeniami, ciekawostkami, w tym również przykładami z życia odkrywców algorytmów, których w książce jest wiele.
Zatem tym, co ma pozostawać po nauce o algorytmach, powinny być nie same przepisy postępowania i ba nawet nie opisy ogólnych technik rozwiązywania, ale pewne, trudne do określenia jednym słowem, połączenie: ogólnej strategii rozwiązywania problemów z przekonującym i rzeczywistym przykładem jej użycia, a to wszystko okraszone smakiem sukcesu z własnego osiągnięcia zwycięstwa nad problemem; i to wszystko ma stanowić przygotowanie do twórczego działania w obliczu pojawiających się problemów. Temu mogą służyć: odpowiednio dobierane przykłady problemów, ilustracje i schematy graficzne algorytmów, symulacje (najlepiej komputerowe) działania rozwiązań, własne obliczenia (mogą być “na piechotę”) opracowanymi metodami, rozwiązywanie podobnych zadań z otoczenia uczniów. Autor ma nadzieję, że potrafił zrealizować swoje zamierzenia napisania książki o algorytmach, umożliwiającej takie właśnie ich traktowanie.
Można mieć wątpliowści, czy umiejętność algorytmicznego myślenia jest potrzebna każdemu uczącemu się, każdemu człowiekowi? Zwłaszcza dzisiaj, w dobie komputerów, które go już wyręczają z wielu czynności i znakomicie nadają się do wykonywania algorytmów. Zapewne jest potrzebna, ale nie każdemu, nie zawsze i nie bezpośrednio. Znajomość sposobów postępowania (zwanych bardziej fachowo technikami algorytmicznymi) w różnych systuacjach umożliwia bowiem wpływanie na to, co się dzieje, często za sprawą komputerów. Nie mówiąc już o tym, że algorytmy, nawet te wykonywane przez komputery, bywają bardzo przydatne wtedy, gdy musimy coś wykonać “ręcznie”, bez pomocy tych maszyn.
3.1. Miejsce algorytmów w programach nauczania
Algorytmy, jako opisy postępowań prowadzących do wyznaczonego celu lub będących opisem rozwiązania postawionego problemu, pojawiają się w wielu dziedzinach nauczania. Występują również wokół nas, w wielu codziennych sytuacjach – jest o tym mowa w wielu miejscach książki, gdy opisujemy rozwiązywane zadania.
Niektóre algorytmy odnoszą się do zadań, które pojawiają się w nauczaniu matematyki, np. rozkład liczby na czynniki (p. 7.6.1), znajdowanie liczb pierwszych (p. 7.6.2), rozwiązywanie równania kwadratowego (p. 3.1) i in. Mogą być one przydatne do wzbogacenia zajęć z matematyki precyzyjnymi opisami postępowań, które ponadto mają dobre własności jako procedury postępowania, zgodnego z celem określonym w specyfikacji.
Wiele algorytmów w książce można zaliczyć do ogólnej dziedziny rozwiązywania problemów, dlatego trudno jest znaleźć dla nich miejsce w konkretnej dziedzinie nauczania. Takie problemy, jak: porządkowanie liczb, słów i dat (rozdz. 6), szukanie drogi wyjścia z labiryntu (p. 11.1), czy optymalne pakowanie plecaka (p. 11.2) można rozważać na wielu różnych lekcjach, np. matematyki, informatyki, fizyki i techniki. Celem zajmowania się tymi problemami jest wykształcenie u uczniów pewnych strategii postępowania w sytuacjach podobnych do tych omawianych lub odmiennych, ale wymagających podjęcia decyzji w konkretenej sytuacji praktycznej.
Szczególny pożytek można mieć z książki na zajęciach z elementów informatyki – niemal każdy program tego przedmiotu obejmuje bowiem zagadnienia związane z formułowaniem rozwiązań problemów w postaci algorytmów (zob. np. [12]). Na takich zajęciach uczący się mają na ogół możliwość posługiwania się komputerem, zatem mogą korzystać z komputerowych realizacji algorytmów. W szczególności mogą skorzystać z programu ELI, by reprezentować algorytmy w postaci projektów w tym programie – dla większości problemów omówionych w książce, ich projekty są załączone na dyskietce. Projekty te umożliwiają posłużenie się komputerem do wszechstronnego badania przebiegu algorytmów. Jeśli zajęcią dotyczą również metod programowania, to algorytmy z tej książki mogą służyć za przykłady zadań, na których są wprowadzane podstawowe konstrukcje programistyczne, takie jak: instrukcja przypisania, instrukcja warunkowa, instrukcje iteracyjne, rekurencja i in. Można w tym posłużyć się gotowymi realizacjami algorytmów w języku Pascal, załączonymi do książki na dyskietce.
Przykłady algorytmów, ich wykorzystania oraz występowania wyników ich działania zostaną wzbogacone w dalszej części książki, która nosi tytuł: Piramidy, szyszki i inne konstrukcje algorytmiczne [16]. Podejmujemy w niej wyzwania i próbujemy znaleźć odpowiedzi, m.in. na pytania: w jaki sposób budowano piramidy, dlaczego łuski na szyszkach są poukładane w spirale, których liczba jest liczbą … par królików po sześciu i siedmiu miesiącach od rozpoczęcia rozmnażania się stada itd.
4. Dla kogo jest ta książka i co w niej jest?
Książka jest przeznaczona przede wszystkim dla uczniów. Napisana jest więc tak, że można ją “czytać” bez niczyjej pomocy, nawet nie dysponując komputerem. Uczeń jest prowadzony niemal “za rękę”, co nie oznacza jednak, że może ją “przeczytać” bez wysiłku. W tekst są wplecione ćwiczenia, których celem jest zachęcenie go do większego zaangażowania się w tworzenie powstającego algorytmu. Rozwiązanie tych ćwiczeń pomaga również w lepszym zrozumieniu wykonywanych przez algorytm działań, a po utworzeniu algorytmu – celem ćwiczeń jest zastosowanie algorytmu, w jednej z użytych reprezentacji do rozwiązania jakiejś szczególnej wersji problemu. Nagrodą za trud poniesiony przy tworzeniu algorytmu jest nabycie pewnego zasobu podstawowych umiejętności, które mogą być przydatne w niezliczonej ilości innych sytuacji, czasem całkowicie nowych.
Z książki mogą korzystać również nauczyciele, przyjmujący na siebie rolę doradców w procesie poznawania i tworzenia, a czasem – odkrywania przez uczniów sposobów rozwiązywania problemów i budowania algorytmów. Różne fragmenty książki mogą być dobierane i wskazywane uczniom przez nauczyciela w zależności od tematu i celu zajęć.
4.1. Co można znaleźć w książce?
Zasadniczą część rozważań w książce stanowią wyprowadzenia sposobów rozwiązywania stawianych zadań – otrzymuje się je na końcu drogi przebywanej z pomocą: rozgrzewających do działania ćwiczeń, zachęcających uwag na marginesie, skojarzeń i przykładowych zadań z bliskiego otoczenia uczniów (np. z innych przedmiotów) motywujących zajmowanie się konkretnym problemem, oraz wspomnień z historii.
Dla osób o rozbudzonej twórczości, pod koniec każdego rozdziału i na końcu książki, znajdują się zadania i problemy, do rozwiązania których wystarczy znajomość materiału tej książki, chociaż czasem potrzebna jest ,,iskra boża”. Skala ich trudności waha się od elementarnych zadań po dość złożone problemy z klasycznej algorytmiki. Te trudniejsze problemy zostały opatrzone szczegółowymi uwagami i wskazówkami, jak się za nie zabrać.
Wiele algorytmów w książce odnosi się do zadań z zakresu szkolnej matematyki , z tak zwanej matematyki dyskretnej, określanej również mianem matematyki doby komputerów. Tak już bowiem było od samego początku – algorytmy pojawiały się zwykle najpierw w umysłach matematyków, jako sprawne sposoby wykonywania obliczeń, a komputery – kiedyś były nazywane nawet ,,maszynami cyfrowymi” lub ,,matematycznymi”.
4.2. Reprezentowanie algorytmów w książce
Na początku książki zadeklarowano, że algorytm jest opisem krok po kroku rozwiązania jakiegoś problemu lub osiągnięcia celu, a następnie (w rozdz. 1) wprowadzono reprezentacje algorytmów, którymi są najczęściej stosowane formy opisu: lista kroków, schemat blokowe, drzewo, projekt w programie ELI i procedura w języku Pascal.
Wszystkie omówione w książce algorytmy są przedstawione w postaci listy kroków, którą poprzedza dokładny opis rozwiązywanego zadania, czyli jego specyfikacja. Specyfikacja zadania składa się: z wykazu danych i warunków, jakie muszą spełniać oraz wykazu wyników i warunków, jakie muszą spełniać. Warunki określające własności wyników są jednocześnie opisem związku wyników z danymi. Specyfikacja jest ważnym elementem opisu algorytmu, gdyż sprawdzenie poprawności działania algorytmu odbywa się poprzez porównanie jego działania ze specyfikacją. W książce niewiele miejsca poświęcono formalnemu dowodzeniu poprawności algorytmów – podano tylko jeden przykład takiego dowodu (zob. p. 12.2). Dołożono jednak wszelkich starań, by przedstawione algorytmy były poprawne. Więcej natomiast jest mowy o sprawdzaniu poprawności programów, w tym również poprawności projektów algorytmów sporządzonych w programie ELI.
Tradycyjne schematy blokowe, poza kilkoma przykładami, nie są specjalnie wykorzystywane w książce. Ich miejsce zajęły graficzne ilustracje działania algorytmów, które obrazują efekty wykonania poszczególnych kroków algorytmu, zob. np.: rys. 5.5 – ilustrujący przebieg turnieju tenisowego, rys. 5.6 – działanie algorytmu jednoczesnego znajdowania najmniejszego i największego elementu w ciągu, czy rys. 8.6 – schemat rozrastania się stada królików.
Większy użytek uczyniono ze szczególnych postaci schematów blokowych, czyli z drzew, a dokładniej – z drzew algorytmów. Dla wielu zadań drzewo algorytmu może być wykorzystane do otrzymania dodatkowych własności algorytmów lub wykazania własności rozwiązywanego zadania. Na przykład, z drzew korzysta się w obrazowaniu przebiegu algorytów porządkowania (zob. rys. 4.1 i rys. 5.5) oraz w uzasadnianiu złożoności algorytmów umieszczania (rys. 9.4) i porządkowania (p. 10.4).
Program ELI umożliwia przedstawienie algorytmu w postaci schematu, który przypomina tradycyjny schemat blokowy. Schemat z programu ELI, nazywany projektem, ma jednak dużą przewagę nad schematem blokowym. Przede wszystkim można za jego pomocą reprezentować algorytmy zawierające podprogramy, w tym również podprogramy rekurencyjne. Ponadto, projekt może być wykorzystany do przeprowadzenia eksperymentów obliczeniowych z algorytmem. W trakcie wykonywania algorytmu przedstawionego w postaci projektu jest możliwe rejestrowanie wyników działania algorytmu w wielu oknach, zawierających: wartości zmiennych, ślad, stos wywołań podprogramów, komentarze, złożoność. Większość tych możliwości programu ELI została wykorzystana w projektach przedstawionych w książce.
Wszystkie algorytmy omówione w książce zostały również opisane w postaci procedur (podprogramów) w języku Pascal, a ich teksty znajdują się na dyskietce. Jest to jednak jedynie dodatek do tej książki, której celem nie jest nauka programowania, czyli zapisywania algorytmów w języku zrozumiałym przez komputer. Te opisy algorytmów należy traktować dosłownie jako opisy algorytmów w pewnym specyficznym języku. Dla osób nie uczących się programowania mogą być jeszcze jednym zapisem algorytmów w bardzo ścisły sposób. Dla tych natomiast, którzy uczą się również programowania, mogą być przykładowymi realizacjami algorytmów w języku programowania i służyć jako procedury-cegiełki w budowaniu programów rozwiązujących bardziej złożone problemy.
Algorytm może być pierwszym abstrakcyjnym tworem poznawanym i odkrywanym przez uczniów. Abstrakcja jest potrzebna w sytuacji, gdy mamy podać przepis nie tylko na konkretne postępowanie, ale na działania w sytuacji zmiennej, bo dla różnych danych tego samego problemu. W tym sensie algorytm ma być uniwersalnym przepisem i poziom złożoności jego opisu nie może być poniżej progu abstrakcji, wymaganej do jego poprawnego sporządzenia. Słuszne są więc słowa Einsteina z motta książki – pewnych opisów algorytmicznych nie można wykonać prościej, bo muszą być dobre dla danych z nieskończonego zbioru.
4.3. Rola problemu, przykładu i ilustracji
Niemal w każdej książce o algorytmach, tej adresowanej do szkół, jak i tej dla studentów, występują np. funkcja silnia i liczby Fibonacciego, jako standardowe przykłady zależności rekurencyjnych. Czym można uzasadnić, że te dwa rodzaje wielkości są ważne? Czym umotywować zajmowanie się nimi? Jak zainteresować uczących się wartościami np. 16! czy F_6?
W książce liczby te są wprowadzone na bazie odpowiednio dobranych problemów, dla których należy znaleźć algorytmy. I tak, 16! to liczba wszystkich możliwych zamkniętych tras premiera po miastach wojewódzkich w starym podziale administracyjnym, a F_6 pojawia się oczywiście jako liczba par królików. W następnej części książki [16] zostanie przedstawionych wiele różnych obiektów przyrody, żywej i nieożywionej, w których pojawiają się liczby Fibonacciego (zob. [6]).
Istotny jest również taki dobór danych dla problemu, aby miały one jakieś znaczenie dla uczącego się, a przez to bardziej go angażowały w tworzenie algorytmu. Porządkujemy więc w książce daty urodzenia uczniów, wyrazy pochodzące z gry w słowa i nieprzypadkowe (dla autora) daty. Dobór takich przykładów powinien być podyktowany konkretną sytuacją edukacyjną.
Więcej na temat powiązań algorytmów z rzeczywistymi sytuacjami piszemy w drugiej części [16], gdzie podajemy również bardzo wiele konkretnych przykładów użycia algorytmów i występowania wyników ich działania w otoczeniu uczniów. Często właśnie problem, przykład jego użycia czy ilustarcja zastosowania rozwiązania, jest tym, co pozostaje po nauce o algorytmach i czyni istotny wkład w wykształcenie uczącego się (w zrozumieniu Skinnera). Autor, w swojej długoletniej pracy nauczycielskiej, spotkał się z bardzo wieloma przykładami potwierdzającymi słuszność takiego podejścia.
5. Jak korzystać z książki – przykładowy scenariusz
Przedstawimy tutaj uwagi do przykładowej lekcji, poświęconej kilku wybranym pojęciom algorytmiki, takim jak: metoda dziel i zwyciężaj, przeszukiwanie binarne i funkcja logarytmiczna – pełna wersja scenariusza tej lekcji znajduje się w [16]. Nadrzędnym celem zajęć dotyczących tej grupy pojęć jest pomoc w wypracowaniu przez uczniów sposobów efektywnego poruszania się wśród zbiorów informacji. Obecnie, informacje i posługiwanie się nimi są nieodłącznym elementem każdej dziedziny. Stawiamy tezę, do której staramy się przekonać uczestników tej lekcji, odbywającej się być może poza tradycyjnymi przedmiotami, że:
Kilka słów o wymienionych pojęciach.
Metoda dziel i zwyciężaj (ang. divide and conquer) wyrosła zapewne z idei innego postępowania, w którym podstawowym krokiem jest również podział – dziel i rządź (łac. divide et impera). Nie należy jednak utożsamiać tych dwóch strategii, zwłaszcza na gruncie algorytmiki. W tej rzymskiej bowiem tkwi chęć panowania nad dzieloną materią, a więc podział jest w gruncie rzeczy rozdziałem części od siebie i ma uniemożliwić wspólne działanie całości (oczywiście przeciwko dzielącym). Natomiast stosując zasadę dziel i zwyciężaj w algorytmice, dzielimy, by zwyciężyć problem, a osiągamy to nie tylko przez podział, ale również przez staranne zaprojektowanie powiązań (komunikacji) między wydzielonymi częściami. Od siły i częstości tych powiązań zależy efektywność rozwiązywania problemu.
Trudno przesądzić, która z tych strategii miała większe zastosowanie w trakcie budowania piramid – oczywiście zwycięstwem miało być zbudowanie piramidy, ale by utrzymać wykonawców w reżimie morderczej pracy, posługiwano się zapewne również tą rzymską zasadą, sformułowaną znacznie później.
W rozwiązywaniu problemów, polegających na poruszaniu się po olbrzymich zasobach informacji, bez zasady dziel i zwyciężaj zdani bylibyśmy na wertowanie całych zbiorów, książek itd. A przyjmując ją, musimy jedynie zadecydować, jak dzielić, by z jednej strony – nie zgubić rozwiązania, a z drugiej – znaleźć je możliwie najszybciej. Często jest stosowana prostsza wersja tej metody, w której po podziale możemy zajmować się tylko jedną z części pochodzących z podziału.
Jedną z najpopularniejszych wersji metody dziel i zwyciężaj jest metoda połowienia, zwana binarną, w której przeszukiwany zbiór dzielimy zawsze na dwie, jednakowo liczne części.
Jak można przekonać uczniów do bliższego zapoznania się z tymi metodami i ich własnościami oraz zachęcić do ich stosowania? – to ostanie zapewne robią bezwiednie. Pierwszy lepszy przykład jest tutaj dobry: wertowanie tysiącstronicowej encykopedii, kartka po kartce – to 1000 kroków, a przez połowienie – nie więcej niż … 10, a w praktyce – o wiele mniej – gdyż stosujemy na ogół leksykograficzną wersję metody podziału.
Z tym ilościowym argumentem na korzyść metod binarnych wiąże się pojęcie logarytmu. By uniknąć matematycznej definicji (Baron John Napier (1550-1617), odkrywca logarytmu, wcale nie korzystał z tego, że funkcja logarytmiczna jest odwrotna do funkcji wykładniczej.), można podać, że logarytm z liczby n wynosi tyle, ile razy trzeba przepołowić n by zostało 1.
Znaczenie logarytmu w informatyce jest podstawowe i trzeba dołożyć starań, by uczniowie go ,,poczuli. Występuje bowiem jako: długość liczb zapisanych w komputerze (p. 7.1), wysokość drzewa wielu algorytmów (p. 9.2, 10.4) i złożoność wielu postępowań, np. przy wyłanianiu wicemistrza turnieju (p. 5.4). Nie chodzi przy tym o sprawność w posługiwaniu się logarytmem, jako funkcją matematyczną, to może być dodatkowym celem, ale o dostrzeżenie i docenienie znaczenia postępowania algorytmicznego, polegającego na ogół na wielokrotnym dzieleniu problemu na części, w którym dzięki temu liczba kroków jest logarytmiczna, a nie liniowa, w zależności od wielkości przeszukiwanego zbioru. Porównanie szybkości wzrastania obu funkcji, liniowej i logarytmicznej, powinno być tutaj przekonującym argumentem, by zapoznać się z pojęciem logarytmu i jego wykorzystaniem.
Scenariusz tej przykładowej lekcji zamieszczony w [16] zawiera propozycje materiałów do pracy własnej uczniów w szkole i w domu, np. wykonywanej w bibliotece, z książką telefoniczną lub encyklopedią. Rola nauczyciela polega na wybraniu odpowiednich tematów zadań (grupowych) i pokierowaniu dyskusją w trakcie prezentacji przed całą klasą wyników prac poszczególnych grup.
6. Cechy efektywnego uczenia się
W przedstawionym podejściu do nauczania o algorytmach można znaleźć wszystkie cechy efektywnego procesu akwizycji wiedzy, jakie wymienia np. De Corte [2]. Uczenie się jest więc:
Kumulacyjne – może być tak zaprojektowane i tak się odbywać, że uczniowie wykorzystują wiedzę i umiejętności nabyte wcześniej przy rozwiązywaniu prostszych problemów w trakcie rozwiązywania bardziej złożonych problemów.
Samoregulujące – uczniowie mogą sami budować swoją wiedzę o algorytmach, kierować jej zdobywaniem oraz samodzielnie nabywać umiejętności tworzenia algorytmów; im bardziej samodzielnie się uczą, tym większą przejmują kontrolę nad swoim uczeniem się.
Ukierunkowane na cel – uczenie się jest bardziej efektywne i większe ma znaczenie dla ucznia, gdyż odbywa się z pełną świadomością celu, jaki ma być osiągnięty – rozwiązanie problemu w postaci algorytmu – oraz z wolą jego osiągnięcia.
Sytuacyjne – przebiega w interakcji z otoczeniem – rozwiązywane problemy pochodzą z otoczenia uczniów, a ich rozwiązania mogą być wykorzystywane do własnych celów, i może odbywać się we współpracy między uczniami w formie pracy grupowej; co więcej, środowisko, w którym przebiega poznawanie i odkrywanie algorytmów, jest wzbogacone pomocami i otoczeniem, z którego pochodzą sytuacje, dla których jest poszukiwane rozwiązanie.
Indywidualnie zróżnicowane – rozwiązywane zadania i stosowane algorytmy mogą zależeć od indywidualnych zainteresowań uczniów, indywidualnego podejścia do uczenia się, możliwości, posiadanej wiedzy, motywacji, własnej skuteczności itd.
7. Czy wszystko jest tak piękne, jak algorytm Euklidesa?
Pytanie z tytułu tego rozdziału ma zwrócić uwagę na to, że algorytmika i rozważania o algorytmach nie są wypełnione jedynie sukcesami nauki i osiągnięciami człowieka. O tym również powinni dowiedzieć się uczniowie, zgłębiający sposoby rozwiązywania problemów.
Wspomnieliśmy już o dyskusyjnych kwestiach terminologicznych oraz o głębszym problemie z definicją pojęcia algorytm. Ten ostatni problem rozwiązaliśmy w książce podobnie, jak postąpiło wielu autorów przed nami – przez przyjęcie sposobów reprezentowania algorytmów i ich wykorzystanie do przedstawienia wielu dobrych przykładów algorytmów. Na tej podstawie uczący się ma możliwość wyrobienia sobie poglądu, czym jest algorytm i jakie ma cechy.
Książka dostarcza również materiału do dyskusji nad trudnością rozwiązywania wielu problemów. Jest to bardzo ważna kwestia, często bagatelizowana przez użytkowników komputerów, którzy uważają, że wyposażeni w komputer są w stanie rozwiązać każdy problem.
Książka może być przydatna do wyjaśnienia następujących kwestii związanych z trudnościami w tworzeniu algorytmów i w posługiwaniu się nimi do rozwiązywania konkretnych zadań – wspomoże ją w tym druga część [16]:
1. Nie każdy przepis osiągnięcia jakiegoś celu lub wykonania pewnego zadania można nazwać algorytmem. Przepisy kulinarne mogą służyć tutaj za dobry przykład. Osiągnięcie smaku – znanego Alicji – ciastka z wiśniami, zmieszanego ze śmietanką, ananasem, pieczonym indykiem, ciągutką i gorącą grzanką posmarowaną masłem może być bardzo trudne i niepowtarzalne (zob. problem 13.1).
2. Piramidy są przykładem istniejących obiektów, zbudowanych kiedyś zgodnie z jakimś algorytmem, którego do dzisiaj nie udało się odtworzyć. Zatem znamy wynik algorytmu, którego nie potrafimy odtworzyć.
3. Znane są problemy, dla których nie istnieje żaden algorytm, np. problem stopu. Oznacza to, że nie uda się nigdy napisać programu komputerowego, który będzie stwierdzał, czy jakikolwiek algorytm, w tym również on sam, zatrzyma się. Brak rozwiązania tego ogólnego problemu nie przesądza, że w konkretnym przypadku programu, czy nawet grupy programów, nie istnieje sposób sprawdzania, czy one się zatrzymują. W praktyce, na ogół postępujemy w zależności od przypadku i potrafimy sprawdzać zatrzymywanie się programów – zob. dyskusję w rozdz. 12.
4. Rozwiązywania równania kwadratowego (p. 3.1) i układu równań liniowych (p. 3.3) mogą być okazją do wyjaśnienia, na czym polegają obliczenia w arytmetyce komputerowej, czyli obliczenia niedokładne, i jakie mogą być konsekwencje nieprzewidzenia błędów, które mogą się pojawić przy tej okazji.
5. Istnieją bardzo proste algorytmy, których skończoności działania nie jesteśmy w stanie wykazać – jeden z najbardziej znanych przykładów jest podany w p. 12.3. W literaturze amerykańskiej ten problem nazywa się czasem ,,Sowieckim spiskiem (ang. Russian plot), gdyż pojawił się on w Stanach Zjednoczonych w okresie Zimnej Wojny (lata pięćdziesiąte), szybko zainteresowało się nim bardzo wielu matematyków, bezskutecznie poszukując dowodu skończoności. Uznano więc, że został on ,,podrzucony przez Rosjan, którzy w ten sposób chcieli odciągnąć matematyków amerykańskich od zajmowania się poważnymi problemami matematycznymi, związanymi z budową nowych broni.
6. Problem komiwojażera (p. 1.2) jest przykładem problemu, którego nie jesteśmy w stanie rozwiązać dla rzeczywistych (tj. praktycznych) danych żadnym z istniejących algorytmów. W takich przypadkach musimy posługiwać się metodami heurystycznymi, które dają wyniki przybliżone, bazują natomiast na intuicyjnie uzasadnionych kryteriach wyboru rozwiązań, mających szanse dość dobrze przybliżać najlepsze rozwiązanie (zob. problem 13.35).
7. Ogólnie, poznanie algorytmów rozwiązywania niektórych problemów praktycznych uczy pewnej pokory wobec skali trudności tych problemów i jest wyzwaniem, któremu można sprostać jedynie posługując się doskonalszymi algorytmami – usprawnianie komputerów daje tylko niewielki postęp w dziedzinie rozwiązywania trudnych problemów.
8. Wiele problemów i ich algorytmów może służyć przybliżeniu znaczenia bardzo ważnych pojęć, złożoność obliczeniowa oraz efektywność algorytmów, oraz wyjaśnieniu różnicy między nimi. Oba te pojęcia są związane z liczbą wykonywanych przez algorytm działań. Złożoność obliczeniowa odnosi się na ogół do teoretycznego oszacowania liczby działań i może dotyczyć zarówno algorytmu, jak i problemu, natomiast efektywność odnosi się najczęściej do konkretnego algorytmu i jego praktycznych walorów.
W obu przypadkach znajdują zastosowanie słowa Ralpha Gomory’ego, szefa naukowego ośrodka badawczego IBM: najlepszym sposobem przyspieszania pracy komputerów jest obarczanie ich mniejszą liczbą działań. Wiele przykładów problemów w książce jest ilustracją słuszności tych słów – zob. następny punkt w tym wyliczeniu – to nie postęp w szybkości działania procesorów, ale coraz bardziej efektywne algorytmy, czyli wykonujące coraz mniejszą liczbę działań powodują, że możemy rozwiązywać za pomocą komputerów problemy o coraz większych rozmiarach (w szczególności, z coraz większą liczbą danych).
Złożoność problemu i efektywność algorytmów jego rozwiązywania najlepiej można wyjaśnić na przykładach problemów: znajdowania najmniejszego elementu w ciągu (p. 5.3) lub porządkowania elementów (rozdz. 10). W pierwszym przypadku podaliśmy, a raczej sprecyzowaliśmy, dobrze znany algorytm i uzasadniliśmy jego optymalność (zob. p. 5.3), a w drugim – podaliśmy kilka algorytmów porządkowania, omówiliśmy i porównaliśmy ich własności oraz określiliśmy, ile porównań musi wykonać jakikolwiek algorytm porządkujący.
9. Potwierdzeniem słuszności słów Gomory’ego z poprzednniego punktu może być sytuacja w dziedzinie znajdowania największych liczb pierwszych i rozkładania liczb na czynniki – o tych problemach piszemy w p. 7.6. Podano tam na str. 131 największą znaną liczbe pierwszą – została ona znaleziona dnia 13 listopada 1996 roku. Już po wydrukowaniu książki (24 sierpnia 1997 roku) ogłoszono znalezienie liczby pierwszej, która ma dwa razy więcej cyfr: jest to liczba Mersenne’a dla p=2 976 221 i ma ona 895 932 cyfry.
Ciekawsze w tym jest to, że przez długie lata znajdowanie kolejnych największych liczb pierwszych było domeną osób posługujących się superkomputerami, czyli najszybszymi istniejącymi komputerami. Wśród nich największe sukcesy odnosiły maszyny z rodziny Cray. Ostatnie rekordy są już osiągane na komputerach osobistych IBM PC dzięki posłużeniu się specjalnym oprogramowaniem, które może działać równocześnie na wielu komputerach i to przez cały czas, gdy tylko są włączone. Więcej szczegółów na ten temat można znaleźć w serwisie internetowym [7].
O wiele trudniejszym problemem jest rozkład liczby na czynniki. Największa, rozłożona na czynniki liczba, ma 129 cyfr. W 1977 roku oszacowano, że znalezienie jej rozkładu przy użyciu znanych wtedy algorytmów i istniejących komputerów zabrałoby czas 2 miliony razy dłuższy niż wiek Wszechświata. W 1994 roku, dzięki przede wszystkim nowym algorytmom, liczbę tę rozłożono na czynniki w czasie ośmiu miesięcy, posługując się w tym celu 600 komputerami!
10. Podsumowanie
Przedstawiliśmy krótko tło dla rozważań o algorytmach, jako rozwiązaniach problemów, które obecnie stanowią często podstawę dla sporządzenia komputerowych rozwiązań (programów). W drugiej zaś części skupiliśmy uwagę na algorytmach jako obiektach twórczości własnej uczniów, formułowanych w trakcie zapoznawania się ze sposobami rozwiązywania problemów.
Rozważania w tej pracy są metodycznym komentarzem do książki Algorytmy [15], będącej propozycją podręcznika do zajęć z algorytmiki, których głównym celem jest ukształtowanie w Czytelniku pewnych ogólnych zasad rozwiązywania problemów i przygotowanie go do twórczego działania w obliczu pojawiających się, nowych problemów.
Podziękowania
Dziękuję Paniom Helenie Krupickiej i Annie Łaskiej-Gmaj za wiele uwag i dyskusje, które pomogły mi poprawić prezentację.
Literatura
1. Aho, A.V., Hopcroft, J.E., Ullman, J.D., Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.
2. De Corte, E., Spojrzenie wstecz i przed siebie na uczenie się wspomagane technologią z perspektywy badań nad uczeniem się i nauczaniem, Komputer w Edukacji, 1-2/1997.
3. Edwards, I.E.S., Piramidy Egiptu, PIW, Warszawa 1995.
4. Elementy informatyki. Vol. 1 – Podręcznik; Vol. 2 – Rozwiązania zadań; Vol. 3 – Poradnik metodyczny dla nauczyciela, pod redakcją M.M. Sysły, Wydawnictwo Naukowe PWN, 1993-1997.
5. Harel, D., Rzecz o istocie informatyki. Algorytmika, WNT, Warszawa 1992.
6. Liczby Fibonacciego: http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html
7. Liczby pierwsze: http://www.utm.edu/research/primes/
8. Ligonniere, R., Prehistoria i historia komputerów, Ossolineum, Wrocław 1992.
9. Nievergelt, J., Co to jest dydaktyka informatyki?, Komputer w Edukacji, 1/1994.
10. Piramidy: http://www.pbs.org/wgbh/nova/pyramid/
11. Polya, G., Jak to rozwiązać?, Wydawnictwo Naukowe PWN, Warszawa 1993.
12. Program nauczania elementów informatyki w liceum ogólnokształcącym oraz liceum zawodowym i technikum, DKO-4015-3/94/WS, Komputer w Edukacji, 2/1994.
13. Steinhaus, H., Kalejdoskop matematyczny, WSiP, Warszawa 1989.
14. Sysło, M.M., Deo, N., Kowalik, J.S., Algorytmy optymalizacjidyskretnej z programami w języku Pascal}, Wydawnictwo Naukowe PWN, Warszawa 1993, 1995.
15. Sysło, M.M., Algorytmy, WSiP, Warszawa 1997.
16. Sysło, M.M., Piramidy, szyszki i inne konstrukcje algorytmiczne, WSiP, Warszawa 1998 (w przygotowaniu).
