maciej_syslo_algorytmy_2.pdf

W LABIRYNCIE ALGORYTMÓW 1

Maciej M. Sysło

Instytut Informatyki, Uniwersytet Wrocławski

syslo@ii.uni.wroc.pl

Ten artykuł jest poświęcone prezentacji książki

Piramidy, szyszki i inne konstrukcje algorytmiczne

która jest wyborem różnych sytuacji problemowych z otoczenia uczniów i nauczycieli – na ich

przykładzie ilustrowane są różne sposoby otrzymywania rozwiązań w postaci algorytmicznej. Pre-

zentacja jest okazją do przedstawienia, jak mogą wyglądać zajęcia z informatyki w gimnazjum,

poświęcone algorytmice, a ogólniej – jak należy rozumieć umiejętność rozwiązywania problemów

w postaci algorytmicznej, którą powinni zdobywać uczniowie na tych zajęciach 2 .

1. Co to jest problem?

Czy można go rozwiązać?

Czy potrzebny jest do tego komputer?

Zastanówmy się najpierw, co to jest problem i na czym polega czynność rozwiązywania problemu.

Interesują nas odpowiedzi na te pytania, odnoszące się przede wszystkim do nauczania i do szkoły.

Co mówi teoria?

Rozważania teoretyczne (pedagogiczne i metodyczne) na temat nauczania i uczenia się rozwiązy-

wania problemów można znaleźć na przykład w książce [7]. Jako jedną z możliwych definicji proble-

mu podano tam, że

problem istnieje wtedy, gdy uczeń w określonych warunkach ma coś

wykonać, ale nie jest poinstruowany, jak to zrobić.

A zatem, aby rozwiązać problem uczeń musi umieć, być może z pomocą nauczyciel, zrobić użytek

ze swojej wiedzy, a często również pogłębić ją w tym celu. Rozwiązanie danego problemu jest więc

nie tylko wynikiem uczenia się, ale proces rozwiązywania problemu jest sposobem uczenia i w me-

todyce nauczania wyróżnia się tzw. lekcje problemowe.

W konkretnym przypadku, interesuje nas znalezienie rozwiązania postawionego problemu (a ogól-

niej, stworzonej sytuacji problemowej), ale za tym stoi zasadniczy cel nauczania rozwiązywania pro-

blemów: nabycie przez uczniów ogólnych zasad rozwiązywania problemów oraz ukształtowanie

1 Ten artykuł ukazał się w materiałach konferencji „Informatyka w Szkole, XIV” (UMCS, Lublin 1998).

2 W równej mierze te rozważania odnoszą się do zajęć z informatyki w szkołach ponadgimnazjalnych, zob. [5].

M.M. Sysło, Algorytmika w gimnazjum

postawy poszukiwania problemów i dążenia do ich rozwiązywania . Najlepszym sprawdzianem

nabytych przez uczniów umiejętności, jest zdolność wykorzystania ich przy rozwiązywaniu nowych

sytuacji problemowych.

Tyle, w dużym skrócie, mówi teoria.

A jak jest w praktyce?

Nasze – nauczycieli, a zwłaszcza – uczniów odczucia na temat problemów i ich rozwiązywania są

często pod przemożnym wpływem popularnych znaczeń tych terminów. Na ogół, problem kojarzy się

uczniom z czymś nie do przebycia, nie do osiągnięcia, nie do rozwiązania. Podtrzymują ich w tym

przekonaniu problemy pochodzące z matematyki, z którymi stykają się na zajęciach – tym mianem

określa się bowiem w szkole najczęściej te zadania matematyczne, których rozwiązanie jest poza

możliwościami ucznia, znającego jedynie materiał przewidziany programem nauczania. Takie pro-

blemy w matematyce szkolnej są na ogół domeną zainteresowań olimpijczyków. Jakby zaprzeczeniem

takiego spojrzenia na matematykę, jest przepiękna książeczka Georgea Polya Jak to rozwiązać? [14] 3 ,

która uczy, jak radzić sobie z problemami w matematyce, z tymi, które znajdują się w zasięgu możli-

wości niemal każdego ucznia.

W uzupełnieniu „teoretycznej” definicji problemu możemy dodać, mając na uwadze powodzenie

zajęć problemowych, że sytuacje problemowe, które będziemy stwarzać uczniom w szkole, powinny:

• motywować ich do zajmowania się nimi, czyli problemy powinny stawać się jakby własnością

uczniów i przez to będzie im zależeć na ich rozwiązaniu,

• zawierać w sobie element zaciekawienia , czegoś, co jest zaprzeczeniem rutyny i stanowi wy-

zwanie „jak to rozwiązać?”.

Wiemy z życia, jak mało zajmującą rzeczą jest tylko coś posiadać, a więc obie te cechy środowiska

uczenia się, które staramy się stworzyć dla zajęć poświęconych rozwiązywaniu problemów: motywa-

cja – by „mieć problem” oraz „ciąg” do jego rozwiązania, są jednakowo ważne.

W programie zajęć poświęconych edukacji informatycznej, rozwiązywanie problemów jest dodat-

kowo opatrzone sugestią, że poszukujemy rozwiązań w postaci algorytmicznej . Chociaż już Eukli-

des ponad dwa tysiące lat temu podał przepis, który aż do połowy tego wieku był niemal synonimem

algorytmu, a matematycy od początku tego wieku starają się podać zadawalającą definicję algorytmu,

to dopiero era komputerów wywołała rzeczywiste zainteresowanie algorytmami. A więc informatyka,

chociaż nie jedyna, jest naturalną dziedziną rozważań o algorytmach. Ale czy niezbędne jest przy tym

posługiwanie się komputerami? I tak i nie. Jak trafnie ujął to 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 więc komputer i spodziewane jego użycie w rozwiązywaniu problemów powoduje, że dzisiaj do

rozwiązywania problemów podchodzimy z dużą ścisłością. I chociaż określenie algorytmu, jakie na

ogół stosujemy:

algorytm opisuje krok po kroku rozwiązanie postawionego problemu lub

sposób osiągnięcia jakiegoś celu.

3 George Polya był matematykiem i wiele osiągnął w badaniach matematycznych. Jego książeczka może być

potraktowana jako refleksja kogoś, kto zmagał się z trudnymi problemami. Jednym z jego błyskotliwych powie-

dzeń było: Jeśli nie potrafisz rozwiązać danego problemu, to istnieje łatwiejszy problem, którego nie potrafisz

rozwiązać: znajdź go. Jest to spojrzenie matematyka, dla którego „problem” oznacza „problem nierozwiązany”,

wskazuje jednak na bardzo istotną cechę zmagań z problemami – w odniesieniu do szkół oznacza to, że powin-

niśmy uczniom dobierać takie problemy, które stanowią wyzwanie dla niech, ale nie są jednak barierą nie do

przebycia.

M.M. Sysło, Algorytmika w gimnazjum

bardziej pochodzi z popularnej encyklopedii niż z podręcznika matematyki lub informatyki, to samo

rozwiązywanie problemów powinno nosić na sobie piętno precyzji, niemal matematycznej, by końco-

wy rezultat mógł posłużyć do znalezienia rozwiązania za pomocą komputera.

W rozwiązywaniu problemów w gimnazjum, komputer może być użyty do:

• przedstawiania działania algorytmów na różnych przykładach, dobieranych przez uczniów (np.

w systemach EI lub ELI),

• reprezentowania algorytmów w postaci schematów (np. w programie ELI),

• badania własności algorytmów (takich, jak poprawność, szybkość działania, skończoność, do-

kładność) na podstawie ich działania dla różnych danych (np. w programach EI i ELI),

• wreszcie, pisania własnych realizacji algorytmów w wybranym języku programowania (np.

w języku Logo lub Pascal).

Uczniowie gimnazjum, przystępujący na zajęciach informatyki do poszukiwania rozwiązań pro-

blemów w postaci algorytmicznej, są wystarczająco przygotowani do posługiwania się komputerem,

aby reprezentować, czyli precyzyjnie zapisywać algorytmy oraz badać ich własności, w szczególności

– wykonywać proste obliczenia na komputerze za pomocą opracowanych algorytmów. W tym ostat-

nim, mogą posłużyć się gotowymi, komputerowymi realizacjami podstawowych algorytmów, dołą-

czonymi do omawianych tutaj książek.

2. Algorytmy w Podstawie programowej

Algorytmy, w sposób jawny, najczęściej występują w zapisach Podstawy programowej dotyczą-

cych edukacji informatycznej. Doszukać się ich można również, zwłaszcza po lekturze programów

nauczania i podręczników, w zapisach dotyczących edukacji matematycznej, fizycznej oraz technicz-

nej.

Na podstawie dwóch programów nauczania matematyki, Matematyka Błękitna oraz Matematyka

2001 , jak również towarzyszących im podręczników, zeszytów ćwiczeń i poradników metodycznych,

można się zorientować, że po raz pierwszy, uczniowie słyszą w szkole o algorytmach na lekcjach ma-

tematyki. Czy jest to właściwe użycie pojęcia algorytm oraz na ile na lekcjach matematyki uczniowie

są rzeczywiście wprowadzani do myślenia algorytmicznego oraz rozwiązywania problemów w postaci

algorytmicznej, będzie przedmiotem innych rozważań autora.

W tym artykule skupiamy uwagę przede wszystkim na algorytmice występującej na III etapie

kształcenia, czyli w gimnazjum, której zakres wynika z zapisów umieszczonych w podstawie progra-

mowej przedmiotu informatyka. Znaleźć tam można m.in. następujące sformułowania:

Treści:

• Rozwiązywanie problemów w postaci algorytmicznej.

Algorytmy wokół nas, przykłady algorytmów rozwiązywania problemów praktycz-

nych i szkolnych. Ścisłe sformułowanie sytuacji problemowych. Opisywanie algo-

rytmów w języku potocznym. Zapisywanie algorytmów w postaci procedur, które

może wykonać komputer. Podstawowe struktury języków opisu algorytmów. Przy-

kłady algorytmów rekurencyjnych. Definiowanie rozwiązań umiarkowanie złożonych

zadań metoda zstępującą. Przykłady testowania i oceny algorytmów.

Osiągnięcia:

• Rozwiązywanie umiarkowanie złożonych problemów przez stosowanie podsta-

wowych metod algorytmicznych.

Jako jeden z autorów tego zapisu, postaram się przedstawić swoje rozumienie tych sformułowań

oraz zaproponować sposoby realizacji zadań szkoły, z nich wynikające. Posługuję się przy tym mate-

riałem z obu moich książek poświęconych algorytmice, które zostały wydane przez WSiP: Algorytmy

[19] i Piramidy, szyszki i inne konstrukcje algortytmiczne [20]. Dalej odwołuje się do tych książek

skrótami: Algorytmy i Szyszki . Wykorzystuję również prace, przygotowane przez słuchaczy dwóch

M.M. Sysło, Algorytmika w gimnazjum

nitek studium podyplomowego, prowadzonych we Wrocławiu i w Nowym Sączu w 1998 roku. Prace

te zostały wykonane jako zadania egzaminacyjne z przedmiotu „Algorytmika i rozwiązywanie pro-

blemów”. W zajęciach wykorzystywałem m.in. obie swoje książki.

W tym miejscu chciałbym gorąco podziękować wszystkim słuchaczom obu studiów, SP13 (we

Wrocławiu) i SP14 (w Nowym Sączu), za aktywność w czasie zajęć oraz za duży wkład i zaangażo-

wanie w przygotowanie prac egzaminacyjnych. Myślę, że zwłaszcza te prace zyskały bardzo wiele na

wartości dzięki temu, że w doborze ich tematów dla poszczególnych osób kierowałem się: ich kierun-

kowym wykształceniem, szkołą, klasą i nauczanym przedmiotem, oraz innymi zainteresowaniami,

zwłaszcza pozaszkolnymi – wszystkie te informacje zebrałem na początku zajęć w formie ankiety.

Prace te okazały się znakomitą ilustracją do pierwszych trzech zdań z zacytowanych wyżej treści

z podstawy programowej, a zwłaszcza odnoszą się do hasła algorytmy wokół nas . Dopiero te zajęcia

uzmysłowiły mi, że nie można mówić o jakimś standardowym zestawie takich algorytmów, a zależeć

one powinny właśnie od otoczenia uczniów, od środowiska, w którym żyją i w którym przebiega na-

uczanie. Środowisko to jest kształtowane przez warunki społeczne i szkolne, w tym bardzo silnie

przez nauczyciela, prowadzącego zajęcia z informatyki. W tej potencjalnej różnorodności nie ma nic

złego, a wręcz przeciwnie – należy upatrywać szansę dla właściwego rozumienia i realizacji zapisów

z Podstawy programowej . Pokuszę się tutaj nawet o herezję: sytuacje problemowe i algorytmy z oto-

czenia nauczycieli przedmiotów niematematycznych są na ogół o wiele ciekawsze, niż sytuacje two-

rzone przez nauczycieli matematyki – odnosi się to przynajmniej do studiów SP13 i SP14. Stoi to

w sprzeczności z powszechną opinią, że problemami zajmują się tylko matematycy, a inne dziedziny

są wolne od problemów, którymi można zajmować się w szkole. Dalej, ilustruję to na wielu konkret-

nych przykładach.

3. Interpretacja zapisów z Podstawy programowej

Przedstawiam tutaj uwagi do przytoczonych w rozdz. 2 zapisów, dotyczących algorytmiki, które

znajdują się podstawie programowej informatyki dla gimnazjum. Największą uwagę skupię na wybo-

rze sytuacji problemowych, które są „napędem” lekcji problemowych.

Chcę pokazać, że zajęcia o algorytmach można tak poprowadzić, by były interesujące i przystępne

dla wszystkich uczniów , by wyzwalały „moce twórcze” nie tylko w tych, którzy interesują się kon-

kursami informatycznymi lub matematycznymi.

Algorytmy wokół nas

przykłady algorytmów rozwiązywania problemów praktycznych i szkolnych

Od wyboru sytuacji problemowej i algorytmu zależy powodzenie całych zajęć. Odpowiednim pro-

blemem możemy zainteresować i umotywować uczniów do działania, jak i zrealizować założony

przez nas cel – wprowadzenie wybranego sposobu rozwiązywania, a dokładniej – techniki algoryt-

micznej.

Zacznijmy od dwóch standardowych przykładów. Czy klasyczne algorytmy, takie jak rekurencyjne

obliczanie liczb Fibonacciego lub silnii są algorytmami z grupy „wokół nas”? – mam duże wątpliwo-

ści. Na pewno nie są nimi, jeśli są wprowadzane poprzez podanie odpowiedniego wzoru. Ale akurat

w tym przypadku można „podejść” do tych dwóch rodzajów liczb poprzez ich występowanie w rze-

czywistych sytuacjach. Występowaniu liczb Fibonacciego w przyrodzie żywej i martwej jest poświę-

cony cały rozdział w Szyszkach , właśnie szyszki są tutaj najlepszym przykładem, i nie tak trudno jest

znaleźć te właściwe – szyszki Fibonacciego [8]. Podobnie z silnią, która jest związana z liczbą

wszystkich możliwych ustawień w szeregu ustalonej liczby obiektów. Ten pierwszy przykład znako-

micie nadaje się na zajęcia nawet w szkole podstawowej, w bloku „Sztuka i technika”, gdyż właśnie

w sztuce można znaleźć te liczby oraz ich nieskończony ideał – złoty podział. Państwo Magdalena

i Mirosław Strzebońscy, słuchacze SP14, z wykształcenia plastycy, przedstawili scenariusze zajęć

poświęconych liczbom Fibonacciego i doskonałości w sztuce. Ich scenariusze zawierają również ele-

menty zajęć z bloku „Przyroda” oraz zajęć matematycznych. Posłużyli się przy tym zarówno obiekta-

mi naturalnymi (rośliny, słoneczniki), jak i dziełami architektury (Partenon, wazy greckie) i sztuki

(Apollo Belwederski, Wenus z Milo, Modulor Le Corbusiera).

M.M. Sysło, Algorytmika w gimnazjum

Inne przykłady sytuacji problemowych z otoczenia uczniów, które mogą służyć do wprowadzenia

algorytmów i algorytmicznych technik rozwiązywania problemów:

• wydawanie reszty w sklepie (i wiążące się z tym częstości występowania monet na rynku) w po-

staci najmniejszej liczby monet ( Szyszki , rozdz. 12), działanie automatów na monety ( Szyszki ,

rozdz. 13); część lekcji może mieć charakter praktyczny i odbyć się na przykład w ... sklepie;

• organizowanie rozgrywek szkolnych (o kompletowaniu podium w książce Algorytmy , p. 5.4) –

Pan Janusz Kruczek (SP14), z zawodu nauczyciel wychowania fizycznego, przedstawił scenariusz

zajęć z uczniami z grupy organizatorów życia sportowego (zajęcia te już się odbyły), poświęco-

nych zaplanowaniu rozgrywek szkolnych, które trwają najkrócej i należy wyłonić w nich trzy naj-

lepsze drużyny;

• dobór uczniów w pary według osobistych preferencji ; mogą to być klasyczne pary taneczne

( Szyszki , rozdz. 11 – takie zajęcia prowadziła Pani Grażyna Koba) albo dobór uczniów, by po

dwóch pracowali przy komputerze (Pan NN z SP13 zaproponował zajęcia pt. „Chcemy siebie”,

których celem jest dobranie się w pary, posługując się przy tym ... siecią komputerową);

• wybór trasy wycieczki – Pani Małgorzata Turowska (SP13) zorganizowała zajęcia w klasie

o profilu turystycznym, które polegały na zaplanowaniu wycieczki po Hiszpanii, która przebiega-

łaby po zadanych miejscach najkrótszą trasą;

• zachłanne pakowanie plecaka – Państwo Małgorzata i Jerzy Golemowie (SP13) zaproponowali

lekcję poświęconą ... racjonalności żywienia w sytuacji wybierania się na wycieczkę z plecakiem;

• „ algorytmy kulinarne ” – Pani Halina Galas (SP14) przeprowadziła lekcję na ten temat w pracow-

ni zajęć technicznych, a tematem była surówka z selerów i jabłek ze śmietaną – uczniowie najpierw

zastanawiali się m.in. nad tym, czy temperatura salaterki nie będzie miała wpływu na smak surów-

ki, a pod koniec lekcji testowali „wyniki” swoich algorytmów – otrzymano różne, smaczne „roz-

wiązania”;

• poszukiwanie z nawrotami – Państwo Małgorzata i Jacek Chowaniec (SP14) zaproponowali zaję-

cia dla swoich uczniów ze szkoły specjalnej, polegające na ustawianiu na szachownicy największej

liczby nieatakujących się królowych; uczniowie wykorzystują przy tym rzeczywiste plansze roz-

mieszczone na podłodze i program komputerowy; początkowo poszukiwania przebiegają metodą

prób-i-błędów, ale celem jest wyrobienie pewnej systematyczności w poszukiwaniach, jak i spraw-

ności ruchowej uczniów;

klasyczne problemy mogą być urozmaicone nowymi sytuacjami lub sposobami rozwiązywania, np.:

• jednoczesne znajdowanie najmniejszej i największej liczby – Pan Zbigniew Grzybacz (SP14)

opisał sytuację, która pojawia się w Wiejskiej Wspólnocie Leśnej, w której żyje: członkowie

Wspólnoty dzielą się sprawiedliwie wyciętymi drzewami, a polega to na tym, że kolejna osoba bie-

rze spośród pozostałych pni dwa, jeden najmniejszy, a drugi – największy;

• poszukiwania w zbiorach uporządkowanych i nieuporządkowanych – posłużenie się klasyczną

grą w odgadywanie liczb ( Algorytmy , p. 9.2); można posłużyć się kolorowymi kartami, np. karta

z wartownikiem może mieć inny kolor, a Pan Stanisław Brzęk (SP14) zaproponował użycie kart

w kolorach odpowiadających barwom rezystorów – wtedy nauczyciel (znający właściwą kolejność

tych barw) potrafi z daleka zorientować się, czy uczniowie znajdują właściwe rozwiązania; jedną

z najciekawszych prac przedstawił Pan Sławomir Bochniarz (SP14), polonista, nt. liniowego i bi-

narnego poszukiwanie informacji – zaproponował on trzy lekcje: jedną z języka polskiego (Czy

żyjemy w Nowym Średniowieczu?) oraz dwie z informatyki (Oko w oko z Golemem i Ile diabłów

mieści się na główce szpilki?);

• miary centralności danych – czy średnia z pensji wszystkich pracowników firmy, włączając dy-

rektorów i osoby sprzątające, jest rzeczywistą średnią zarobków? (Pan Mirosław Głód, SP13);

problemy rachunkowe, czysto matematyczne, mogą być również bardzo urozmaicone, a często –

„odmatematyzowane”, przez spojrzenie na nie okiem informatyka, np.:

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: