Algorytmika - wstęp

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ń:

  1. Sformułowanie zadania

  2. Określenie danych wejściowych

  3. Określenie celu, czyli wyniku

  4. Poszukiwanie metody rozwiÄ…zania, czyli algorytmu

  5. 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ć:

  1. poprawny, tzn. dla każdego poprawnego zestawu danych, po wykonaniu skończonej liczby czynności, prowadzi do poprawnych wyników.

  2. jednoznaczny- w kaĹĽdym wypadku jego zastosowania, dla tych samych danych uzyskamy ten sam wynik

  3. szczegółowy, aby wykonawca algorytmu rozumiał opisane czynności i potrafił je wykonać

  4. 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ć:

  1. Wlać do garnka zimną wodę.

  2. Zapalić gaz.

  3. Gotować wodę do wrzenia.

  4. wrzucić 2 torebki ryżu.

  5. Odczekać 5 minuty / podane na opakowaniu/.

  6. Zgasić gaz.

  7. Wyjąć torebki z ryżem

  8. sprawdzić czy ryż został ugotowany


Instrukcja warunkowa

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:

  1. Podnieś słuchawkę.

  2. Wybierz cyfrÄ™ 9.

  3. Wybierz cyfrÄ™ 9.

  4. Wybierz cyfrÄ™ 9.

  5. Czy połączyłeś z pogotowiem ?

    1. Jeśli TAK, to przejdź do kroku 6.

    2. Jeśli NIE, to przejdź do kroku 7.

  6. PrzekaĹĽ informacje lekarzowi.

  7. Odłóż słuchawkę.


Instrukcja iteracyjna

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ą.

  1. Podnieś słuchawkę.

  2. Wykonaj czynność trzy razy

    1. Wybierz cyfrÄ™ 9.

  3. Czy połączyłeś się z pogotowiem ?

    1. Jeśli tak, to przejdź do kroku 4.

    2. Jeśli nie, to przejdź do kroku 5.

  4. przekaĹĽ informacje lekarzowi.

  5. 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

  1. Czy słuchawka jest odłożona ?

    1. Jeśli tak, to przejdź do kroku 2.

    2. Jeśli nie, to odłóż słuchawkę przejdź do kroku 1.

  2. Podnieś słuchawkę.

  3. Wykonaj czynność trzy razy

    1. Wybierz cyfrÄ™ 9.

  4. Czy połączyłeś się z pogotowiem ?

    1. Jeśli tak, to przejdź do kroku 5.

    2. Jeśli nie, to przejdź do kroku 6.

  5. PrzekaĹĽ informacje lekarzowi.

  6. 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

  1. Czy słuchawka jest odłożona ?

    1. Jeśli tak, to przejdź do kroku 2.

    2. Jeśli nie, to odłóż słuchawkę.

  2. Podnieś słuchawkę.

  3. Czy linia jest zajęta ?

    1. Jeśli Tak, to:

      1. Odłóż słuchawkę.

      2. Podnieś słuchawkę.

      3. PrzejdĹş do kroku 3.

    2. Jeśli Nie, to przejdź do kroku 4.

  4. Wykonaj czynność trzy razy

    1. Wybierz cyfrÄ™ 9.

  5. Czy połączyłeś się z pogotowiem?

    1. Jeśli tak, to przejdź do kroku 6.

    2. Jeśli nie, to przejdź do kroku 1.

  6. Przekaz informacje lekarzowi.

  7. 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.