Wstęp do programowania/Wstęp do algorytmów
Wprowadzenie do algorytmów
Najważniejszym pojęciem w informatyce jest algorytm. Nazwa ta ma swoje korzenie w średniowieczu i wzięła się ze zniekształconego nazwiska wielkiego uczonego arabskiego Al Chuwarizmiego, który żył na przełomie VIII i IX wieku i pochodzącego z Chorezmu. Al Chuwarizmi, działając w Domu Nauk kalifa Al Mamuna w Bagdadzie, opublikował ważne dzieła matematyczne, wśród nich Hisab al dżabr w'al muqabala – traktat o rozwiązywaniu równań, z którego wzięła nazwę algebra – jeden z głównych działów matematyki. W traktacie tym, poza wprowadzeniem systemu zapisu pozycyjnego, zaczerpniętego od Hindusów, a zwanego arabskim, podał między innymi metody rozwiązywania równań kwadratowych. Metody te odwoływały się do pojęć geometrycznych; utożsamiano wtedy liczby i działania z miarami obiektów geometrycznych. Liczby rzeczywiste to były długości odcinków, dodawanie to było sklejanie odcinków, mnożenie odpowiadało wyliczaniu pola prostokąta o danych bokach, a pierwiastkowanie wyznaczaniu boku kwadratu o zadanym polu. Arabowie, podobnie jak starożytni Grecy, nie znali pojęcia liczby ujemnej, stąd, gdy dziś patrzymy na metody Al Chuwarizmiego, poza oczywistym pięknem, wydają się nam one nieco dziwaczne. Ale cóż – wtedy inaczej po prostu się nie dało.
W pierwszym kroku rozwiązania Al Chuwarizmi polecał podzielić wszystkie współczynniki trójmianu kwadratowego przez współczynnik przy \( x^{2} \), aby uwolnić się od jednego z nich; w końcu pierwiastki przez takie podzielenie nie zmieniają się, a metoda staje się prostsza. Al Chuwarizmi rozważał zatem równania postaci \( x^{2}+bx+c \) dla różnych klas b i c: dodatnich, ujemnych i równych zero. Miał zatem do czynienia z 9 różnymi przypadkami i dla każdego z nich podał metodę wyznaczania pierwiastka takiego równania. Przyjrzyjmy się jednemu z nich: dane są zaczerpnięte bezpośrednio z omawianej księgi. Rozwiązujemy równanie
\( x^{2}+10x = 39 \)
Jest to zatem równanie z klasy równań, w których współczynnik przy x jest dodatni, a wyraz wolny ujemny (dla wygody przenieśliśmy go na prawą stronę, więc po tamtej stronie jawi się nam jako c dodatnie). Oto co proponował Al Chuwarizmi.
Rysujemy kwadrat o boku x. Po jednej jego stronie doklejamy prostokąt o bokach x oraz \( 10/2 = 5 \), po drugiej pod kątem prostym identyczny prostokąt. Uzupełniamy powstały kąt prosty wyznaczony przez 2 odcinki długości 5 do kwadratu i otrzymujemy duży kwadrat, którego pole wynosi
\( x^{2} + 5x + 5x + 25= 39 + 25 = 64 \)
Bok tego dużego kwadratu ma więc długość 8, a że powstał on przez sklejenie odcinka o długości x oraz odcinka o długości 5, więc \( x = 3 \). Drugi pierwiastek w tym przypadku nas nie interesuje: jest ujemny, a więc go "nie ma" – liczby ujemne nie istniały wówczas w świadomości współczesnych.
Zauważmy, że konstrukcję tę, a zatem i stosowne obliczenia, można powtórzyć dla każdej pary (b,c) w której b > 0, zaś c < 0. Wyrażając jednym wzorem efekt obliczeń uzyskalibyśmy wyrażenie
\( x=\sqrt{c+(\frac{b}{2})^2}-\frac{b}{2} \)
Obliczenie wartości x mogłoby się odbywać według następującego schematu:
- podziel \( b \) przez \( 2 \) i zapamiętaj wynik na zmiennej pomocniczej \( b' \)
- podnieś \( b' \) do kwadratu
- dodaj do otrzymanej liczby wartość \( c \)
- wyciągnij z otrzymanej sumy pierwiastek kwadratowy
- odejmij od tego, co uzyskałeś uprzednio zapamiętaną wartość \( b' \)
- otrzymana liczba jest szukanym (nieujemnym) pierwiastkiem równania \( x^{2}+bx=c \).
Zróbmy parę obserwacji.
Po pierwsze powyższa procedura jest wykonywalna dla każdych danych b,c>0. Zauważmy, że jedyna operacja, która mogłaby sprawić kłopoty z wykonaniem, to odejmowanie w punkcie 5 naszej procedury. Jednak można łatwo sprawdzić, że daje ono zawsze wynik dodatni:
w końcu dla \( c >0 \) mamy \( \sqrt{c+(\frac{b}{2})^2} > \sqrt{(\frac{b}{2})^2}=\frac{b}{2} \).
Po drugie, zastosowaliśmy tu pewne niewielkie, ale ważne uproszczenie algorytmu: użyliśmy w jego opisie pomocniczej zmiennej \( b' \), dzięki której nie musieliśmy dwukrotnie dzielić wartości \( b \) przez \( 2 \). Po trzecie, zapisując wzór na równanie kwadratowe skorzystaliśmy z tradycji notacyjnej, w myśl której w wyrażeniach arytmetycznych zawsze wiadomo, w jakiej kolejności wykonuje się działania. W szczególności w wyrażeniu podpierwiastkowym najpierw dzieliliśmy b przez 2, potem podnosiliśmy wynik do kwadratu, a na końcu dodawaliśmy do niego c. To, co w podanym przez Al Chuwarizmiego przepisie wymagało uściślenia kolejności, można wyrazić wzorem w zwartej formie, umówiwszy się zawczasu co do interpretacji podanej notacji. Niezwykle ważne jest, aby używana notacja była jednoznaczna i abyśmy nie popełniali błędu przy interpretacji wyrażeń, w szczególności żebyśmy byli zgodni co do kolejności wykonywanych działań. Wrócimy do tego zagadnienia w wykładzie o gramatykach.
Ćwiczenie
- Jak będzie działała podana metoda, dla c<realnowiki><realnowiki> = </realnowiki></realnowiki>0?
- Zaprojektuj geometryczną metodę w stylu Al Chuwarizmiego dla równania \( x^{2}= 5x + 6 \). Czy metoda ta da poprawne wyniki dla wszystkich równań postaci \( x^{2} = bx + c \) przy dodatnich b, c?
Co to są zatem algorytmy? Ogólnie określamy tym mianem wszelkie przepisy postępowania, które doprowadzają do uzyskania pożądanego efektu – rozwiązania zadania. W potocznej mowie mówimy czasem o algorytmach postępowania niewiele mających wspólnego z komputerami, jednak dla informatyków algorytmy wiążą się nierozerwalnie z programowaniem.
Prawdziwe problemy pojawiają się, gdy chcemy algorytm zakodować w taki sposób, żeby był dobrze wykonany przez maszynę. Nie możemy sobie pozwolić na odwoływanie się do doświadczenia, machanie rękami, domysły. Komputer niczego się nie domyśla, ba, nie rozumie języka naturalnego i potrzebna będzie nam precyzyjna notacja do komunikacji z nim. Istotą programowania jest bowiem wyrażanie algorytmów w sposób ścisły, podlegający rygorom skończonej liczby reguł, których znaczenie w jednoznaczny sposób jesteśmy określić.
Al Chuwarizmi nie był oczywiście pierwszym człowiekiem, który stosował podejście algorytmiczne do rozwiązywania problemów. W rzeczywistości każdy z nas stosuje algorytmy w rozmaitych sytuacjach życiowych. Człowiek pierwotny miał algorytm polowania na mamuty, czy rozpalania ognia. Dzisiaj często wykonujemy pewne algorytmy, nie zdając sobie sprawy. Warto przytoczyć parę przykładów algorytmów z życia codziennego:
Przepisy kucharskie Typowy przepis zawiera deklaracje obiektów (składników pichcenia) ich początkowe wartości (miary) oraz opis działań doprowadzający do przyrządzenia potrawy.
Zapis nutowy muzyki. Za pomocą szczególnego systemu notacyjnego określa się wysokości i względne czasy trwania nut i pauz między nimi. Można również i tu określić dane: są to zazwyczaj określenia instrumentów, które w partyturze występują, oraz dane początkowe, takie jak metrum czy dynamika poszczególnych części. Zauważmy, że poza standardowymi znakami na pięciolinii, kompozytorzy często stosują dodatkowe określenia takie jak crescendo, poco allegretto, piano, con fuoco itp, pozwalające wykonawcy lepiej wyczuć ich intencje. Szczególnie atrakcyjnie wyglądają niektóre nuty kompozytorów współczesnych, którzy odchodzą czasem od tradycyjnego zapisu nutowego i starają się niekiedy wymyślić i opisać własny system notacyjny, wyrażający ich intencje.
Instrukcje montażu Często do zestawów mebli, czy klocków lego, dołączona jest kartka z instrukcją montażu zapisaną za pomocą sekwencji rycin obrazujących kolejne fazy powstawania składanego obiektu. Użytkownik, porównując zmiany na poszczególnych obrazkach, ma się domyślić, jakie czynności, w jakiej kolejności i za pomocą jakich części ma wykonywać. Zauważmy, że i tu występuje charakterystyczny dla algorytmów opis danych: najczęściej zestaw części składowych jest wyrysowany obok historyjki obrazkowej z zaznaczeniem liczby poszczególnych elementów.
Opisy dojazdu Wyjaśniając jak dotrzeć do danego miejsca (mappy.com), wiele serwisów udostępnia opis drogi z zaznaczeniem kluczowych punktów i decyzji.
Opis układów choreograficznych, scenopisy przedstawień Tutaj też stosuje się specyficzną symbolikę i skróty notacyjne.
Takich przykładów można przytaczać tysiące. Właściwie niemal wszystko, co robimy, podlega jakiemuś algorytmowi działania – przy czym warto podkreślić, że ludzie nie muszą mieć algorytmów objaśnianych dokładnie: wiele mogą wywnioskować z kontekstu, doświadczenia, po prostu domyślając się, o co może chodzić. Kucharce nie trzeba wyjaśniać, co to znaczy "zeszklić cebulkę na ciemnozłoty kolor", a monterowi - co znaczy "zaizolować przewody".
Z komputerami jest jednak inaczej. Są to wyjątkowo głupie urządzenia i jeśli dokładnie nie wytłumaczymy, co mają zrobić, stają się bezradne. Między bajki należy włożyć rozmaite sytuacje znane z literatury fantastyczno-naukowej, w których komputery są równorzędnymi partnerami intelektualnymi dla ludzi. Sztuczna inteligencja, nawet jeśli istnieje, bazuje na ściśle określonych algorytmach działania i nie ma tam miejsca na intuicję, domyślenie się czegokolwiek czy nagłe olśnienie, które są doskonale znane istotom myślącym. Ludzie często nie zdają sobie sprawy, jak wiele w algorytmach, którymi się posługują, zależy od nieuświadamianego kontekstu, jak dużo muszą dopowiadać do rzekomo precyzyjnych procedur działania. Komputery bezlitośnie wyłapują luki w specyfikacji procedur i nie ma mowy, żeby domyśliły się, że wykonują jakąś bezsensowną akcję, typu wydrukowanie żądania zapłacenia 0 zł. Jeśli wyraźnie nie zapiszemy w algorytmie, że takich żądań nie należy generować, to komputer ślepo wykona nasze polecenie, choćby było ono w oczywisty sposób bezsensowne. W dalszych wykładach zobaczymy przykłady, w których algorytmy z pozoru wyglądające na poprawne i kompletne, będą miały luki powodujące błędne działanie.
Ćwiczenie
Znajdź w Internecie przykłady bezsensownego zachowania się komputerów. Spróbuj domyślić się, jakiego rodzaju błąd programisty był przyczyną kompromitacji.
Spróbujmy przymierzyć się do problemu znanego jeszcze ze starożytności. Przy dodawaniu sprowadza się mianowniki do najmniejszej wspólnej wielokrotności. Wyznaczenie jej najczęściej polega na tym, że oblicza się największy wspólny dzielnik, dzieli się jedną z liczb przez niego i wynik mnoży przez drugą. Jak jednak znaleźć największy wspólny dzielnik?