Maciej Syslo Algorytmy 3.pdf

ALGORYTMY, ALGORYTMIKA

I ALGORYTMICZNE MYŚLENIE W SZKOLE 1

Maciej M. Sysło

Instytut Informatyki, Uniwersytet Wrocławski

ul. Przesmyckiego 20, 51-151 Wrocław

syslo@ii.uni.wroc.pl

1. Kilka słów zamiast wstępu

Pojęcie algorytm robi w ostatnich latach zawrotną karierę. Podobnie, jak określenie „elektronicz-

ny”, w skrócie e- , bywa wytrychem do nowoczesności. Można by przejść nad tym do porządku dzien-

nego mówiąc e-tam , ale „atmosfera zaczyna się zagęszczać” i wymaga to od informatyków, zwłaszcza

szkolnych, jasnego stanowiska.

Do pewnego momentu, gdzieś w połowie zeszłego stulecia, słowo algorytm w potocznym znacze-

niu 2 nierozerwalnie pojawiało się w zestawieniu algorytm Euklidesa . Co najmniej dziwnym, bo prze-

cież przepis Euklidesa na znajdowanie największego dzielnika dwóch liczb ma grubo ponad 2000 lat,

a słowo algorytm zaczęło się wykluwać gdzieś pod koniec pierwszego tysiąclecia. Uzasadnienie jest

jednak proste – algorytm Euklidesa jest najprostszą, a jednocześnie najbardziej pojemną konstrukcją

umożliwiającą wyjaśnienie niemal wszystkich podstawowych cech konstrukcji algorytmicznych. Nie-

co później, w latach pięćdziesiątych, algorytmem był przede wszystkim przepis na obliczenia nume-

ryczne, gdyż pierwsze komputery służyły głównie do takich rachunków.

Obecnie, na dobrą sprawę, każdą czynność, w jakimś sensie celową i składającą się z uporządko-

wanych etapów, można by nazwać i często nazywa się algorytmem. Panie mają swoje algorytmy kuli-

narne i grozi nam, że wszyscy będziemy jadać taką samą zupę pomidorową. Szkoły i wyższe uczelnie

otrzymują dotacje z MEN na podstawie algorytmu – może to jest właśnie źródłem niedostatków

w szkołach?

W szkołach z kolei – algorytm pojawia się najwcześniej nie na zajęciach z informatyki, ale na ma-

tematyce, jako np. „algorytm pisemnego dodawania dwóch licz”, chociaż nie różni się on specjalnie

od tego, czego kiedyś uczono jako „dodawania dwóch dowolnych liczb”. Z kolei, na informatyce,

chcąc jak najbardziej uprościć to pojęcie i przybliżyć uczniom jego znaczenie na przykładach z ich

otoczenia, w wielu podręcznikach można spotkać takie przykłady, jak: algorytm ubierania się, wybie-

rania połączenia telefonicznego czy wyjścia klasy na wycieczkę.

Sytuacja w szkołach zaczyna być jednak dość poważna, głównie za sprawą matury z informatyki,

która ma sprawdzać m.in. umiejętność rozwiązywania problemów w postaci algorytmicznej. W tym

artykule nie w pełni wyjaśniamy wszystkie wątpliwości, ale staramy się odpowiedzieć na pytania sta-

wiane przez uczniów i nauczycieli i dość często, pośrednio lub bezpośrednio, adresowane do autora.

1 Artykuł ten ukazał się w materiałach Konferencji „Informatyka w Szkole, XVII”, Mielec 2001, str. 116-123.

Nie ma w nim więc jeszcze odniesienia do przygotowywanego pakietu edukacyjnego do nauczania informatyki

w liceum ogólnokształcącym.

2 Pomijamy w tych rozważaniach głębokie dociekania matematyków nad znaczeniem pojęcia algorytm, stymu-

lowane problemami, jakie na samym początku XX wieku sformułował David Hillbert.

M.M. Sysło, Algorytmy, algorytmika, algorytmiczne myślenie

2. Co to jest algorytm i jego miejsce w szkole

Nie należy zaczynać rozważań na tematy algorytmiczne od próby zdefiniowania tego pojęcia

w sensie informatycznym. To tak, jakbyśmy na początku zajęć z matematyki próbowali zdefiniować

liczbę. Nie zastanawiamy się jednak nad tym i rachujemy na okrągło. Podobnie, nie wiedząc o tym,

często nasze postępowanie przy rozwiązywaniu różnych problemów ma cechy algorytmów. Podczas

zajęć z informatyki, algorytmy mogą pojawiać się w rozważaniach od samego początku, a ich celem

powinno być przybliżenie na przykładach, czym dokładnie jest algorytm. Zajęcia poświęcone więc

wprowadzeniu algorytmów powinny mieć charakter nauczania czynnościowego, podczas którego

uczniowie rozwiązują odpowiednie zadania oraz przedstawiają rozwiązania w postaci algorytmów.

Pojęcie „algorytm” swoją popularność i rozpowszechnienie zawdzięcza przede wszystkim informa-

tyce. A powodem są komputery. W bardzo uproszczony sposób, związek algorytmów z komputerami,

czyli pośrednio z informatyką, można ująć następująco – komputery głównie wykonują programy, a

każdy program jest zapisem jakiegoś algorytmu.

Algorytmy można zapisywać na papierze, na tablicy lub opisać słownie. Tak zresztą często postę-

pujemy również na lekcjach informatyki. Ale na tym nie koniec. Dopiero uzmysłowienie sobie, że ten

przepis ma być wykonany przez komputer czyni z niego twór informatyczny. Najlepiej ujmuje ten fakt

powiedzenie, którego autorem jest jeden z największych żyjących informatyków, Donald E. Knuth:

Mówi się często, że człowiek dotąd nie zrozumie czegoś,

zanim nie nauczy tego – kogoś innego.

W rzeczywistości,

człowiek nie zrozumie czegoś naprawdę,

zanim nie zdoła nauczyć tego – komputera.

A zatem algorytm 3 , to tak skonstruowany przepis, że może go zrozumieć i wykonać komputer .

Oczywiście do wszystkiego jest potrzebny człowiek, który ma przygotować i podać ten przepis kom-

puterowi. Stąd, ze względu na wykonawcę-komputer, o algorytmie mówi się m.in., że składa się

z uporządkowanych kroków, jednoznacznie opisanych, wykonalnych za pomocą prostych i znanych

operacji, ma skończone działanie itd. Dodatkowo, opis kroków algorytmu powinien być poprzedzony

specyfikacją , czyli precyzyjnym opisem wejścia i wyjścia, a więc danych i wyników. To wszystko po

to, by siadając do tłumaczenia komputerowi, co ma zrozumieć i wykonać, ani tłumaczący, ani później

komputer nie mieli żadnych wątpliwości, o co chodzi.

Z tych krótkich rozważań wynika kilka wniosków, jak powinno się uczyć algorytmiki na lekcjach

informatyki w gimnazjum i liceum:

•

algorytm powinien pojawiać się jako takie rozwiązanie problemu, które ma podstawowe ce-

chy „algorytmu informatycznego”, a więc jego docelowa postać może być przekazana kompu-

terowi do wykonania; przepis kulinarny niech nadal nazywa się przepisem, sposób uzyskania

połączenia telefonicznego za pomocą aparatu analogowego (czyli klasycznego telefonu) niech

będzie instrukcją, podobnie obsługa każdego urządzenia, a planowanie wycieczki i ubieranie

się to procesy decyzyjne;

przynajmniej kilka przykładów algorytmów powinno być wykonanych na lekcjach za pomocą

komputera (wśród treści podstawy programowej dla informatyki do gimnazjum występuje

sformułowanie: Zapisywanie algorytmów w postaci procedur, które może wykonać komputer )

– w gimnazjum mogą temu służyć realizacje (implementacje) algorytmów np. w języku Logo

lub w programie ELI, które przygotuje nauczyciel lub zdolniejsi uczniowie, a w liceum –

uczniowie sami programują algorytmy dla komputerów; oczywiście na zajęciach z technologii

informacyjnej w liceum nie ma miejsca na jawne mówienie o algorytmach, chociaż będą one

cały czas wykonywane przez uczniów w postaci programów, które stosują;

3 W dyskusji tutaj nie uwzględniamy takich konstrukcji, jak algorytm losowy, rozmyty, czy interakcyjne wyko-

nywanie obliczeń przez komputer, gdyż wykraczają one poza szkolny zakres informatyki.

M.M. Sysło, Algorytmy, algorytmika, algorytmiczne myślenie

powinno znaleźć się również miejsce na przedstawienie algorytmów w innej postaci kompute-

rowej, niż tylko zapisanych w języku programowania, np. jako realizacji w arkuszu kalkula-

cyjnym (zob. rozdz. 15 w [1]);

wynika stąd również, jaka powinna być rola nauki programowania w szkole – ma to być na-

uka języka komunikacji człowieka z komputerem, służącej przedstawianiu komputerowi algo-

rytmów do wykonania; podobnie więc jak w przypadku innych programów (np. użytkowych),

zakres zajęć z programowania powinien być dostosowany do omawianych algorytmów – nie

ma potrzeby wprowadzania sztucznie konstrukcji języka, które nie będą potrzebne uczniom

w opisie algorytmów dla komputera.

3. Problemy algorytmiczne wokół nas

W podstawie programowej dla informatyki w gimnazjum występują m.in. takie hasła, jak algoryt-

my wokół nas , przykłady rozwiązywania problemów praktycznych i szkolnych 4 .

Jak już proponowaliśmy w poprzednim punkcie, pozostawmy jednak przepisy kulinarne, korzysta-

nie z telefonu, programowanie pilota czy kuchenki mikrofalowej innym przedmiotom szkolnym –

„algorytmy” w tych sytuacjach mają często niewielki związek z informatycznymi cechami opisów

czynności dla komputera, chociaż dobrze mogą ilustrować schematy wybranych konstrukcji algoryt-

micznych. Popularne jedzenie kaszki przez Jerszowa jest świetną ilustracją rekurencji, ale na tym ko-

niec, bo nikt nie będzie zaprzęgał do tego komputera.

W książce [5] zamieszczono opis wielu sytuacji, które mogą być bliskie uczniom, a które łatwo

można wykorzystać, w podanej lub w zmienionej postaci, jako uzasadnienie dla wprowadzenia kon-

kretnego algorytmu. Ponadto, praca [7] zawiera przykłady sytuacji problemowych, zasugerowanych

przez samych nauczycieli, którzy na zajęciach prowadzonych przez autora opracowali konspekty lek-

cji poświęconych rozwiązywaniu problemów w postaci algorytmicznej.

4. Rozwiązywanie problemów a algorytmika

Podejście problemowe do nauczania jest najbliższą algorytmice metodą dydaktyczną. Oddają to

zapisy w podstawie programowej dla informatyki do gimnazjum, gdzie pojawiają się takie określenia,

jak: rozwiązanie problemu , problemy praktyczne i szkolne , sytuacja problemowa . Oczywiście, rozwią-

zywanie problemów nie jest domeną informatyki czy algorytmiki, uczniowie zmagają się z proble-

mami niemal na każdym przedmiocie szkolnym – rozwiązanie problemu może mieć postać algorytmu,

ale nie musi, nie naginajmy więc sytuacji, jeśli przepis (rozwiązanie) nie gwarantuje własności, które

powinien mieć algorytm.

Więcej na temat problemów i nauczania problemowego piszemy w artykule [7]. Podejście to do-

starcza nam odpowiedzi na niektóre wątpliwości, związane z pytaniami, w jaki sposób uczyć w szkole

o algorytmach i jak przygotować uczniów do zdawania matury z informatyki. Krótko mówiąc, celem

zajęć poświęconych algorytmom nie jest jedynie omówienie wybranej ich grupy, ale nauka, w jaki

sposób je dobierać i stosować w rozwiązywaniu różnych sytuacji problemowych.

5. Algorytmy na maturze

Matura, zwłaszcza w wydaniu Nowej Matury jako egzamin zewnętrzny, będzie sprawdzianem nie

tylko osiągnięć abiturientów, ale także pewną ewaluacją pracy szkoły i nauczycieli. Odnosi się to nie

tylko do informatyki, ale akurat w przypadku nas interesującego przedmiotu jest wiele kwestii, które

wymagają od wszystkich zainteresowanych tym osób: właściwego zrozumienia charakteru tego egza-

minu, dokładnej znajomości dokumentów, znajomości przykładowych zadań, sposobu ich rozwiązy-

wania i oceniania, a od nauczycieli informatyki – również znajomości całego procesu tworzenia zadań

maturalnych. W szczególności należy:

4 W artykule [7] zamieszczono szczegółową dyskusję sformułować z podstawy programowej dla informatyki do

gimnazjum, odnoszących się do działu Rozwiązywanie problemów w postaci algorytmicznej .

M.M. Sysło, Algorytmy, algorytmika, algorytmiczne myślenie

1. Znać obowiązującą Podstawę programową . Wszystkie dokumenty programowe dla matury

w latach 2002 – 2004 są oparte na „starej” Podstawie programowej . Pierwszy egzamin maturalny

dla uczniów „idących z reformą” odbędzie się dopiero w 2005 roku. A zatem nie jest prawdą, co

czasem słychać w opiniach nauczycieli, „my uczymy według starego programu, a matura jest we-

dług nowego”.

2. Znać obowiązujący syllabus, czyli dokument, publikowany 2 lata przed egzaminem, który zawiera

wszystkie informacje programowe i organizacyjne dotyczące zakresu i przebiegu egzaminu. Dla

matury w 2002 roku obowiązuje Syllabus. Matura z informatyki 2002 [3], a na rok 2003 opubli-

kowano już jedynie poprawki do tego dokumentu.

3. Zapoznać się z dodatkowymi dokumentami, które w przypadku matury z informatyki dotyczą

technicznej strony przebiegu egzaminu. Dokumenty te można otrzymać w OKE.

Nie będziemy tutaj więcej poruszać ogólnych tematów dotyczących matury z informatyki – pod-

czas tej konferencji są temu poświęcone specjalne warsztaty – zajmiemy się natomiast kwestią miejsca

algorytmów i algorytmiki na maturze oraz wyjaśnieniem „niedomówień” występujących w syllabusie

maturalnym.

5.1. Ile algorytmów na maturze

Niektórzy nauczyciele, po lekturze Syllabusa 2000 [3] odnoszą wrażenie, że gros przykładowych

zadań maturalnych dotyczy algorytmiki. Na dobrą sprawę, tylko jedno zadanie zostało zaprojektowane

z tej „działki” (Arkusz I, zad. 2). W przypadku pozostałych zadań, jeśli kojarzy się je z algorytmiką, to

zapewne za sprawą precyzji występującej w ich sformułowaniu. Jeśli bowiem chcemy oczekiwać od

ucznia podania rozwiązania postawionego problemu, to dla ścisłości i jasności odpowiedzi sugeruje-

my, by odpowiedź miała cechy specyfikacji, często kojarzonej tylko z algorytmami. Otóż każde roz-

wiązanie zadania, przygotowane do przekazania go komputerowi – a taki przecież charakter mają

informatyczne rozwiązania zadań – powinno mieć postać specyfikacji, czyli zawierać opis: danych,

wyników i procesu postępowania. Inaczej byłoby trudno, uczniowi – zaproponować rozwiązanie,

a nauczycielowi – sprawdzić jego poprawność. Odsyłam do dyskusji powyżej na temat informatycz-

nego rozwiązywania zadań.

5.2. Co to są algorytmy klasyczne

Jest kilka możliwych odpowiedzi na pytanie, „co to są algorytmy klasyczne?”. Na przykład, „są to

algorytmy zawarte u Sysły”, czyli opisane w książce [4], lub w jakimś innym opracowaniu. Wielu

nauczycieli dopomina się listy takich algorytmów i kiedyś nawet taka lista została opracowana przez

grupę informatyków (brałem w tym udział). Ostatnio jednak bardzo niechętnie tworzę taką listę, gdyż

uważam, że najpierw należy przekonać nauczycieli, o co rzeczywiście chodzi w nauczaniu algorytmiki

(a raczej algorytmicznego myślenia) i w jaki sposób znajomość tego zakresu wiedzy i umiejętności

informatycznych powinna być sprawdzana. Zadania maturalne są tutaj dobrym przykładem tego wła-

śnie zrozumienia, ale oczywiście powinno to być kształtowane przez cały okres nauczania. Nie odpy-

tujmy uczniów ze znajomości algorytmów z jakiejkolwiek listy, gdyż na maturze nie pytamy o kon-

kretny (z nazwy) algorytm, ale stawiamy problemy, do rozwiązania których należy dobrać i posłużyć

się odpowiednimi algorytmami.

Posłużę się więc teraz przykładem jednego z zadań maturalnych. Będzie to wspomniane już zad. 2.

z Arkusza I, zaczerpnięte z Syllabusa 2002 [3]. W skrócie, opuszczając tutaj opis sytuacji problemo-

wej, zadanie to dotyczy poszukiwania wyróżnionego elementu w zbiorze. Można więc zapytać: jakie

algorytmy do rozwiązania tego zadania powinny „być obowiązkowe” dla ucznia. Ze schematu ocenia-

nia tego zadania wynika, że uwzględniono, iż uczeń może znać: algorytm liniowy dla ciągu nieupo-

rządkowanego, algorytm liniowy dla ciągu uporządkowanego i algorytm dziel-i-zwyciężaj dla ciągu

uporządkowanego. Maksymalną liczbę punktów uczeń może otrzymać za poprawne użycie pierwsze-

go i trzeciego algorytmu.

Z tego zadania wynika, że oczekujemy od ucznia znajomości sposobów informatycznego rozwią-

zywania problemów poszukiwania elementów w zbiorach nieuporządkowanych i uporządkowanych.

Znanych jest wiele algorytmów do rozwiązania tego typu zadań i ostatecznie można ważniejsze z nich

M.M. Sysło, Algorytmy, algorytmika, algorytmiczne myślenie

wypisać. Ale nie chcę przez to powiedzieć, że wszystkie te algorytmy są w jakimś sensie „obowiąz-

kowe” dla ucznia. Uczeń znający metodę dziel-i-zwyciężaj może otrzymać maksymalną liczbę punk-

tów, ale uczeń, który nie wykaże się jej znajomością na maturze, otrzyma mniej punktów. Uzasadnie-

nie takiego oceniania jest proste – z informatycznego punktu widzenia metoda dziel-i-zwyciężaj jest

najlepsza, a celem nauczania informatyki nie jest tylko podanie rozwiązania problemu i posłużenie się

komputerem, ale również zwracanie uwagi na to, że są sposoby lepsze i gorsze, że informatyczne roz-

wiązywanie zadań ma swój charakter, a komputer w końcu nie z wszystkim umie i może sobie pora-

dzić.

Jak się można przekonać wczytując się w treść omawianego tutaj zadania, jego sformułowanie na-

prowadza ucznia na tor rozumowania autora zadania i wiedzie go do najlepszego rozwiązania.

Wracając do zawieszonego na chwilę pytania o algorytmy klasyczne, wszystkie trzy wymienione

wyżej algorytmy do nich należą, ale już przeszukiwanie liniowe z wartownikiem (zob. [4]) można

sobie podarować i uznać, że jest to głównie propozycja realizacji (implementacji) algorytmu liniowe-

go. Ma ona duże znaczenie dla informatyków, gdyż znacznie ułatwia uzasadnienie poprawności algo-

rytmu linowego, co jednak wykracza poza zakres szkolnej informatyki.

Dyskusja powyżej sugeruje, że jest możliwa częściowa odpowiedź na postawione pytanie o algo-

rytmy klasyczne, ale w nieco zmienionej postaci. W miejsce listy takich algorytmów można się poku-

sić o wykaz typowych sytuacji problemowych (byłoby to jednocześnie odpowiedzią na inne pytanie –

zob. następny podpunkt) wraz z metodami ich rozwiązywania. I te właśnie metody mogłyby być

uznane za algorytmy klasyczne, z wcześniejszym zastrzeżeniem, że to wcale nie oznacza, że znajo-

mość ich wszystkich obowiązuje uczniów przystępujących do matury.

Ograniczenie miejsca w tym artykule nie pozwala na kontynuację tej dyskusji. Wspomniany wykaz

sytuacji problemowych wraz z metodami ich rozwiązywania jest w trakcie opracowywania i zostanie

wkrótce udostępniony.

5.3. Co to są typowe sytuacje problemowe

Sytuacja problemowa , to nic innego jak „historyjka”, w realiach której jest umieszczony problem

do rozwiązania. Podobnie, jak w przypadku „algorytmów klasycznych”, trudno, a nawet – jeszcze

trudniej – jest podać określenie typowej sytuacji problemowej. Można jedynie mówić o pewnych ty-

powych grupach zagadnień i dla dalszego wyjaśnienia odwoływać się do przykładów. Nauczyciele

i osoby układające zadania maturalne z informatyki powinni mieć na uwadze, by sformułowanie zada-

nia nie zawierało treści, związanych ze stworzoną sytuacją i potrzebnych do jej rozwiązania, które

mogą być obce uczniom 5 .

Oczywiście nauczyciele i osoby układające zadania maturalne z informatyki z zamysłem powinni

tworzyć takie sytuacje problemowe, w których w naturalny sposób da się pomieścić sposób rozwiąza-

nia (algorytm), zbadanie znajomości którego ma być celem zadania. Zatem pewne sugestie dotyczące

możliwych sytuacji problemowych wynikają z przewidzianego zakresu algorytmów, które powinny

być znane uczniom przystępującym do egzaminu maturalnego z informatyki, patrz poprzedni pod-

punkt.

6. Algorytmika w szkoleniach nauczycieli

W programach wielu studiów podyplomowych z informatyki znajdują się przedmioty występujące

pod różnymi nazwami, które odnoszą się do rozwiązywania problemów i przedstawiania rozwiązań

w postaci algorytmicznej. Inną kwestią jest, jak wygląda przebieg takich zajęć – to trudno jest wy-

wnioskować z samego programu nauczania. Mogę jedynie mówić za siebie.

Po pierwsze, w naszym przypadku przedmiot „Rozwiązywanie problemów w postaci algorytmicz-

nej” występuje jedynie w programach tych studiów, które przygotowują przyszłych nauczycieli infor-

5 W jednej z prób maturalnych okazało się, że NIESTETY podczas egzaminu z informatyki, nie można wyma-

gać od uczniów, by wiedzieli, kto był „dwukrotną polską noblistką”!

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: