Co to jest algorytm ?
Na lekcjach matematyki często
stajemy przed rozwiązaniem zdania. Większość
ich rozwiązujemy według pewnych schematów,
reguł Najpierw wypisujemy dane i szukane, zastanawiamy
się jak osiągnąć dany cel, a więc jaki
ma być wynik. Następnie wypisujemy wzory, które
Ĺ‚Ä…czÄ… dane z szukanymi bÄ…dĹş twierdzenia,
które można zastosować do rozwiązania danego
problemu. Nie tylko w szkole rozwiÄ…zujemy zadania,
wykonujemy je w kaĹĽdej innej dziedzinie naszego
życia, na przykład:
kupujÄ…c spodnie w sklepie, dzwoniÄ…c do kolegi,
znajdujÄ…c najwyĹĽszego ucznia w szkole,
Również przy takim typie zadań
musimy określić dane i warunki, które muszą
one spełniać, formułujemy także wynik,
który pragniemy uzyskać.
Algorytm
to przepis rozwiÄ…zania zadania, zawierajÄ…cy opis
danych wraz z opisem czynności, które należy
wykonać z tymi danymi, aby osiągnąć
zamierzony wynik.
Etapy rozwiÄ…zywania zadania:
W procesie rozwiÄ…zywania kaĹĽdego
zadania możemy wyróżnić pewne etapy, które
nas do niego prowadzÄ….
Etapy rozwiązywania zadań:
-
Sformułowanie zadania
-
Określenie danych
wejściowych
-
Określenie celu, czyli wyniku
-
Poszukiwanie metody rozwiÄ…zania,
czyli algorytmu
-
Przedstawienie algorytmu w postaci:
-
opisu słownego
-
listy krokĂłw
-
schematu blokowego
-
języka programowania
6. Analiza poprawności
rozwiÄ…zania
7. Testowanie rozwiÄ…zania dla
różnych danych. Ocena efektywności
przyjętej metody.
Algorytm musi być:
-
poprawny, tzn. dla kaĹĽdego
poprawnego zestawu danych, po wykonaniu
skończonej liczby czynności, prowadzi do
poprawnych wynikĂłw.
-
jednoznaczny- w kaĹĽdym wypadku
jego zastosowania, dla tych samych danych uzyskamy
ten sam wynik
-
szczegółowy, aby wykonawca
algorytmu rozumiał opisane czynności i
potrafił je wykonać
-
uniwersalny, aby służył
do rozwiązywania pewnej grupy zadań, a nie
tylko jednego konkretnego przypadku zadania.
Działania niealgorytmiczne
ZastanĂłw siÄ™: Czy wszystkie
działania są algorytmiczne ?
Czy dla każdego zadania można zbudować
algorytm? Czy rozwiÄ…zanie kaĹĽdego zadania polega
na wykonywaniu jednoznacznie opisanych, ściśle
określonych czynności? Odpowiedź jest
oczywista , ĹĽe nie. IstniejÄ… zadania, ktĂłrych
realizacji nie można ująć w ramy jakiegoś
planu działania. Taki charakter ma np. każda
twórczość artystyczna. Konieczna jest do tego
wyobraźnia i twórcze działanie, a na to nie ma
konkretnego przepisu. ZastanĂłw siÄ™ czy rzut
piłka do kosza jest działaniem algorytmicznym?
Budowa algorytmĂłw
Algorytmy powinny być tak
przedstawiane, aby było możliwe ich jednoznaczne
odczytanie i zastosowanie. NiektĂłre algorytmy
można opisać w języku potocznym,
zwłaszcza wtedy, gdy jego wykonawcą ma być
człowiek (w informatyce zajmujemy się
opracowywaniem algorytmĂłw, ktĂłrych wykonanie
powierzamy komputerom).
Z czego składa się algorytm?
Zawiera on opis danych, opis wynikĂłw oraz plan
działania, czyli przetworzenia danych. Plan ten
można przedstawić w postaci ciągu
czynności, które muszą być wykonane w
określonej kolejności. Opis czynności
występujących w algorytmie nazywamy
instrukcjami.
Algorytm liniowy
Ma on prostą postać. Składa
siÄ™ z ciÄ…gu instrukcji, ktĂłre sÄ… wykonywane
jedna po drugiej w kolejności, jaka wynika z ich
następstwa w zapisie algorytmu. Taki algorytm nosi
nazwÄ™
algorytmu liniowego ( sekwencyjnego).
Algorytmy liniowe majÄ… opisy
składające się z kroków, które nie
zaleĹĽÄ… od ĹĽadnych warunkĂłw i sÄ… wykonywane
w zapisanej kolejności. Istnieją jednak sytuacje, w
których dalsze postępowanie w algorytmie zależy od
spełnienia, bądź nie, określonych
warunków. Czasami musimy powtórzyć pewne kroki
algorytmu kilka razy. / przykład telefonowanie do
znajomego/
Opracuj algorytm gotowania ryĹĽu
Zastanów się jak ugotować
ryĹĽ. Na poczÄ…tku opracowywania algorytmu
przyjmijmy założenie, że używamy kuchenki
gazowej, posiadamy garnek i wodę. Zakładamy
rĂłwnieĹĽ, ĹĽe nic nie utrudni samej
czynności, to znaczy np. w trakcie gotowania nie
zostaniemy pozbawieni dopływu gazu, czy też osoba
nie wie co to garnek.
Algorytm ten ma postać:
-
Wlać do garnka zimną
wodÄ™.
-
Zapalić gaz.
-
Gotować wodę do wrzenia.
-
wrzucić 2 torebki ryżu.
-
Odczekać 5 minuty / podane
na opakowaniu/.
-
Zgasić gaz.
-
Wyjąć torebki z ryżem
-
sprawdzić czy ryż
został ugotowany
W
rzeczywistości, większość algorytmów ma
bardziej rozbudowaną strukturę. Często
występują w nich instrukcje, których wykonanie
uzależnione jest od spełnienia pewnego warunku lub
też spełnienie pewnego warunku powoduje wykonanie
jednej instrukcji, a niespełnienie innej. Taką
instrukcjÄ™ nazywamy
instrukcjÄ… warunkowÄ….
Działa ona według jednego z dwóch przedstawionych
schematĂłw:
Jeśli
spełniony jest warunek Z, wykonaj
instrukcjÄ™
A.
Jeśli
spełniony jest warunek Z, to wykonaj
instrukcjÄ™
A; w przeciwnym razie wykonaj instrukcjÄ™ B.
Instrukcja
A
i
B
opisuje jednÄ…
instrukcję lub instrukcję składającą
siÄ™ z ciÄ…gu instrukcji wykonywanych sekwencyjnie /
np telefonowanie do przyjaciela/. Instrukcja warunkowa
pozwala dokonać wyboru jednej z dwóch dalszych
drĂłg wykonania algorytmu.
Rozpatrzmy
przykład telefonowania:
-
Podnieś słuchawkę.
-
Wybierz cyfrÄ™ 9.
-
Wybierz cyfrÄ™ 9.
-
Wybierz cyfrÄ™ 9.
-
Czy połączyłeś z
pogotowiem ?
-
Jeśli TAK, to przejdź do
kroku 6.
-
Jeśli NIE, to przejdź do
kroku 7.
-
PrzekaĹĽ informacje lekarzowi.
-
Odłóż słuchawkę.
Instrukcja iteracyjna - ze znanÄ…
ilością powtórzeń
Przyjrzyj siÄ™ uwaĹĽnie algorytmowi.
Zauważyłeś, że istnieją tu
powtarzajÄ…ce siÄ™ instrukcje, aĹĽ trzykrotnie
występuje "Wybierz cyfrę 9".
Takie wielokrotne powtarzanie niektĂłrych instrukcji jest
cechÄ… charakterystycznÄ… wielu algorytmĂłw, jednak
nie zawsze (tak jak w tym algorytmie) moĹĽemy
określić dokładnie liczbę powtórzeń.
Może ona zależeć od spełnienia pewnych
warunkĂłw. Wielokrotne powtarzanie instrukcji
umoĹĽliwiajÄ…
instrukcje iteracyjne (pętle) .
Działa ona według schematu:
Wykonuj instrukcję A dokładnie n
razy.
Ćwiczenie
Popraw opracowany wcześniej algorytm tak, aby
sekwencję jednakowych czynności zastąpić
pętlą.
-
Podnieś słuchawkę.
-
Wykonaj czynność trzy
razy
-
Wybierz cyfrÄ™ 9.
-
Czy połączyłeś
siÄ™ z pogotowiem ?
-
Jeśli tak, to przejdź
do kroku 4.
-
Jeśli nie, to przejdź
do kroku 5.
-
przekaĹĽ informacje lekarzowi.
-
Odłóż
słuchawkę.
Działanie algorytmu może
zakończyć się na dwa różne sposoby,
albo uzyskamy połączenie z pogotowiem i i
przekaĹĽemy informacje lekarzowi, albo nie
połączymy się i wykonanie algorytmu
ograniczy się tylko do wykręcenia numeru 999
Jak widzisz zastosowanie pętli zmienia sposób
zapisu algorytmu, nie zmienia siÄ™ jednak jego
działanie.
Instrukcja iteracyjna - ze
spełnieniem warunku
Zmień wcześniejszy algorytm tak aby
uwzględnić przypadek braku połączenia
lub przypadek nieprawidłowego połączenia.
W poprzednim algorytmie w przypadku
uzyskania nieprawidłowego połączenia
bądź jego braku, przechodziliśmy do
ostatniego kroku , w którym odkładaliśmy
słuchawkę. Kończyło się
działanie algorytmu. W tej sytuacji powinniśmy
rozpocząć raz jeszcze jego wykonywanie, nie
zostało to jednak opisane w konstrukcji.
Rozbudujemy teraz algorytm, tak by powtarzano wybieranie
numeru aż do uzyskania połączenia. Dopiszemy
w tym celu polecenie będące drugim rodzajem
instrukcji iteracyjnej:
Powtarzaj
wykonywanie instrukcji A aĹĽ do
spełnienia warunku Z.
Czym jest instrukcja A, czym warunek Z ?
Instrukcja A - podniesienie słuchawki, wybranie
numeru
Warunek Z - uzyskanie połączenia z wybranym
numerem
Algorytm
-
Czy słuchawka jest
odłożona ?
-
Jeśli tak, to przejdź
do kroku 2.
-
Jeśli nie, to
odłóż słuchawkę przejdź
do kroku 1.
-
Podnieś słuchawkę.
-
Wykonaj czynność trzy
razy
-
Wybierz cyfrÄ™ 9.
-
Czy połączyłeś
siÄ™ z pogotowiem ?
-
Jeśli tak, to przejdź
do kroku 5.
-
Jeśli nie, to przejdź
do kroku 6.
-
PrzekaĹĽ informacje lekarzowi.
-
Odłóż
słuchawkę przejdź do kroku1
W algorytmie telefonicznego
powiadomienia lekarza pogotowia dodaliśmy
instrukcję, która uwzględniła, że po
nieudanej próbie uzyskanie połączenia
należy odłożyć słuchawkę, a
dopiero później ponownie ją podnieść i
spróbować raz jeszcze. W przypadku pierwszej
próby nawiązania połączenia również
sprawdzamy odłożenie słuchawki.
Czasami zdarza siÄ™ jednak, ĹĽe
już po podniesieniu słuchawki słychać,
że linia jest zajęta. Należałoby wtedy
odłożyć słuchawkę i ponownie ją
podnieść. Jeśli okazałoby się, że
nadal słychać w niej sygnał
zajętości linii czynność
należałoby powtórzyć. Musielibyśmy
wykonywać te czynności dopóki linia nie
byłaby wolna. W takim przypadku stosujemy
instrukcję, która działa według schematu:
DopĂłki warunek W jest
spełniony, wykonuj instrukcję A.
Algorytm
-
Czy słuchawka jest
odłożona ?
-
Jeśli tak, to przejdź
do kroku 2.
-
Jeśli nie, to
odłóż słuchawkę.
-
Podnieś słuchawkę.
-
Czy linia jest zajęta ?
-
Jeśli Tak, to:
-
Odłóż
słuchawkę.
-
PodnieĹ›
słuchawkę.
-
PrzejdĹş do kroku 3.
-
Jeśli Nie, to przejdź
do kroku 4.
-
Wykonaj czynność trzy
razy
-
Wybierz cyfrÄ™ 9.
-
Czy połączyłeś
siÄ™ z pogotowiem?
-
Jeśli tak, to przejdź
do kroku 6.
-
Jeśli nie, to przejdź
do kroku 1.
-
Przekaz informacje lekarzowi.
-
Odłóż
słuchawkę.
Jak widzimy w kroku 3 występuje
pętla, w której sprawdzamy najpierw warunek, a
dopiero potem wykonywana jest instrukcja opisana przez
kroki a, b, c. Jeśli warunek nie jest
spełniony, to instrukcja nie zostanie wykonana ani
razu.
W informatyce możemy realizować
szczególny rodzaj powtórzeń bez
konieczności stosowania pętli. Jest to technika
rekurencji.
|