maciej_syslo_algorytmy.pdf

(278 KB) Pobierz
A L G O R Y T M Y
ALGORYTMY 1
ODŚWIEŻONE SPOJRZENIE
Maciej M. Sysło
Instytut Informatyki, Uniwersytet Wrocławski
Przesmyckiego 20, 51-151 Wrocław
Education is what survives when what
has been learnt has been forgotten.
Wykształcenie jest tym, co pozostaje,
gdy zapomni się to, czego nauczyliśmy się.
[B.F. Skinner]
Thinks should be as simple as possible,
but no simpler.
Wszystko powinno być tak proste,
jak to tylko możliwe, ale nie prostsze.
[A. Einstein]
STRESZCZENIE
Książka Algorytmy [16] (Dalej w tym artykule, książka bez dodatkowego określenia odnosi się
właśnie do tej książki; podobnie, wszystkie odwołania bez podania źródła odnoszą się do fragmentów
tej książki.) różni się od wielu innych opracowań na ten temat tym, że nie jest tylko zbiorem gotowych
algorytmów, ale z jej pomocą można poznawać algorytmy uczestnicząc w ich powstawaniu i stając się
w ten sposób ich współtwórcą. Ten artykuł jest krótkim wprowadzeniem do algorytmiki. W pierwszej
części jest przedstawione tło dla rozważań o algorytmach – uwagi o historii komputerów i algorytmów
oraz opis rozwoju pojęcia algorytm. Druga zaś część zawiera zwięzłą charakterystykę zawartości
książki oraz uwagi metodyczne o sposobach korzystania z niej przez uczących się i przez nauczycieli.
Artykuł jest adresowany zarówno do tych, dla których ta książka jest pierwszym spotkaniem z al-
gorytmami, 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 algo-
rytmach – na lekcjach informatyki, matematyki, techniki i twórczości, i w uczelniach – jako wprowa-
dzenie do algorytmiki. Podejście do nauczania o algorytmach zaproponowane w tej książce, jak i roz-
waż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ło-
wieka, to pomagają nam na tyle, na ile sami jesteśmy w stanie przygotować je do tego. Kiedyś czło-
wiek 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
1 Ten artykuł ukazał się w materiałach konferencji „Informatyka w Szkole, XIII” (UMCS, Lublin 1997), a na-
stępnie w nieco zmienionej postaci został opublikowany w czasopismach Komputer w Edukacji i Komputer
w Szkole .
 
M.M. Sysło, ALGORYTMY – odświeżone spojrzenie
2
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 nauczycie-
la. 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 .
I. Algorytmy – rozważania ogólne
Przyjmijmy na początku encyklopedyczną definicję algorytmu, według której: Algorytm opisuje
krok po kroku rozwiązanie jakiegoś problemu lub osiągnięcie wyznaczonego celu.
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, sorto-
wanie 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świado-
mie, z posiadanej już wiedzy i umiejętności zdobytych przy znajdowaniu rozwiązań innych proble-
mó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 przy-
kład, piramida Cheopsa ma wysokość 146 m i jest oparta na kwadracie o boku 230 m. Jeśli przyjmie-
my 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 budowa-
no 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 [11].) 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.
M.M. Sysło, ALGORYTMY – odświeżone spojrzenie
3
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 sfor-
malizowano 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 podstawo-
wych 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 Dänikena), według których te budowle zostały postawione jeszcze przed narodzeniem się fara-
onó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 [11], zob.
również [17].
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 wyznaczo-
nego 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 wcześniej jednak, w Babilonie, Indiach, Chinach i w Egipcie, posługiwano się prze-
pisami 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łu-
giwano się w tym celu, niejawnie jednak, binarnym rozwinięciem liczby n . Na przykład, iloczyn 13 x
ma postać (1101) x , a wtedy y =13 x można otrzymać w następującym ciągu operacji: y := x , 2 x := x + x ;
4 x :=2 x +2 x , y := y +4 x , 8 x :=4 x +4 x , i y := y +8 x . Zatem wielokrotność danej liczby można otrzymać posłu-
gują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ść po-
wszechnie stosowana na wsiach w Rosji (zob. [17]). 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 pierw-
szych. Twierdzenie to ma dzisiaj bardzo duże znaczenie w obliczeniach na dużych liczbach i jest pod-
stawą dla tzw. arytmetyki modularnej. Można o tym przeczytać w [1] oraz w [17].
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, two-
rzą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 uniwer-
M.M. Sysło, ALGORYTMY – odświeżone spojrzenie
4
salnymi, ż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 kon-
struowane liczydła są przeznaczone do wykonywania czterech podstawowych działań arytmetycz-
nych, 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 rozdz. 1 podręcznika [4], zob.
również [9]. Wiele faktów historycznych dotyczących algorytmów i komputerów znajduje się w ram-
kach na marginesach rozważań w książkach [16] i [17].
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ą al-
gorytmów. Badania w tym zakresie doprowadziły do powstania wielu matematycznych teorii obli-
czeń, które obecnie tworzą matematyczne podstawy informatyki. Zbiegło się to z początkami konstru-
owania 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 jedy-
nie zbieg okoliczności, że najwięksi twórcy podstaw informatyki brali równocześnie udział przy kon-
struowaniu 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 ob-
liczeń, a także jako współtwórca maszyn Colossus, które były wykorzystywane przez Brytyjczyków
w czasie II Wojny Światowej do rozpracowania niemieckich 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, cho-
ciaż, 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 kie-
rowali 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 algoryt-
mów zostały udowodnione dopiero niedawno. Na przykład okazało się, że algorytm Euklidesa (przed-
stawiony 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 ko-
lei, 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 Horne-
ra. Podobnie, optymalność najpopularniejszej, liniowej metody znajdowania najmniejszego lub naj-
wię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 pro-
blemów oraz badaczy algorytmów, co do definicji algorytmu. Przez wieki, od czasów Euklidesa, nie
M.M. Sysło, ALGORYTMY – odświeżone spojrzenie
5
martwiono się jednak tym specjalnie, tylko tworzono opisy rozwiązywania różnych problemów i dzi-
siaj nazywamy je algorytmami. Nawet konstruktorzy pierwszych liczydeł, kalkulatorów i maszyn cy-
frowych nie dociekali specjalnie, co to jest algorytm, lub raczej jak zdefiniować coś, co da się wyko-
nać 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ól-
ne 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ło-
wał 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łkowi-
tych? 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 pro-
blemy mają rozwiązanie w postaci algorytmu, a jakie nie mają.
Udzielenie odpowiedzi na pytanie dotyczące istnienia lub nieistnienia algorytmu wymaga sformali-
zowania 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ś poszu-
kiwanego 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 XX wieku wielu
matematyków. Wprowadzono wiele różnych definicji obliczeń, przy czym większość z nich jest rów-
noważna między sobą w tym sensie, że definiuje tę samą klasę funkcji obliczalnych. Do najpopular-
niejszych 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 pro-
blem, 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 przed-
stawić 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ą algo-
rytmy. Takiego podejścia nie można jednak uznać za niepełne.
Jedna z najpopularniejszych książek dotyczących rozwiązywania problemów, zwłaszcza matema-
tycznych, Jak to rozwiązać? George'a Polya [12], nie zawiera ani słowa o problemach matematycz-
nych, 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 [14] 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 nie-
zbędne mówienie o problemach, które nie mają rozwiązań. Zwłaszcza, że wyniki dotyczące nieroz-
wiązywalności problemów są w pewnym sensie mało intuicyjne i mało praktyczne. Na przykład, cho-
ciaż, zgodnie z dowodem Matijasiewicza, nie istnieje algorytm rozwiązywania jakiegokolwiek równa-
nia wielomianowego w zbiorze liczb całkowitych, to jednak wiele szczególnych, praktycznych rów-

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin