Przykładowe algorytmy z życia codziennego

Większość urządzeń technicznych do prawidłowego działania potrzebuje specjalnego oprogramowania, które będzie nim sterowało. Tworzenie programu rozpoczynamy od stworzenia planu działań oraz opracowania procedur, które muszą wykonać poszczególne podzespoły urządzenia. W uproszczony sposób można to przedstawić za pomocą algorytmu.

 Algorytm – w matematyce oraz informatyce skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań.

PODSTAWOWE PARADYGMATY TWORZENIA ALGORYTMÓW KOMPUTEROWYCH:

DZIEL I ZWYCIĘŻAJ – dzielimy problem na kilka mniejszych, a te znowu dzielimy, aż ich rozwiązania staną się oczywiste,

PROGRAMOWANIE DYNAMICZNE – problem dzielony jest na kilka, ważność każdego z nich jest oceniana i po pewnym wnioskowaniu wyniki analizy niektórych prostszych zagadnień wykorzystuje się do rozwiązania głównego problemu,

METODA ZACHŁANNA – nie analizujemy podproblemów dokładnie, tylko wybieramy najbardziej obiecującą w tym momencie drogę rozwiązania,

PROGRAMOWANIE LINIOWE – oceniamy rozwiązanie problemu przez pewną funkcję jakości i szukamy jej minimum,

POSZUKIWANIE I WYLICZANIE – kiedy przeszukujemy zbiór danych aż do odnalezienia rozwiązania,

ALGORYTM PROBABILISTYCZNY – algorytm działa poprawnie z bardzo wysokim prawdopodobieństwem, ale wynik nie jest pewny,

HEURYSTYKA – człowiek na podstawie swojego doświadczenia tworzy algorytm, który działa w najbardziej prawdopodobnych warunkach, rozwiązanie zawsze jest przybliżone.

 

NAJWAŻNIEJSZE TECHNIKI IMPLEMENTACJI ALGORYTMÓW KOMPUTEROWYCH

PROCEDURALNOŚĆ – algorytm dzielimy na szereg podstawowych procedur, wiele algorytmów współdzieli wspólne biblioteki standardowych procedur, z których są one wywoływane w razie potrzeby,

PRACA SEKWENCYJNA – wykonywanie kolejnych procedur algorytmu, według kolejności ich wywołań, na raz pracuje tylko jedna procedura,

PRACA WIELOWĄTKOWA – procedury wykonywane są sekwencyjnie, lecz kolejność ich wykonania jest trudna do przewidzenia dla programisty

PRACA RÓWNOLEGŁA – wiele procedur wykonywanych jest w tym samym czasie, wymieniają się one danymi,

REKURENCJA – procedura lub funkcja wywołuje sama siebie, aż do uzyskania wyniku lub błędu,

OBIEKTOWOŚĆ – procedury i dane łączymy w pewne klasy reprezentujące najważniejsze elementy algorytmu oraz stan wewnętrzny wykonującego je urządzenia.

 

Schematy blokowe

Schematy blokowe są tzw. metajęzykiem. Oznacza to, że jest to język bardzo ogólny, służy do opisywania algorytmów w taki sposób, by na jego podstawie można było je zaimplementować w każdym języku.

Częściami składowymi schematów blokowych są proste figury geometryczne, np. prostokąt, romb, koło, równoległobok itd… W tych figurach umieszczamy warunki oraz proste instrukcje, przy czym mogą być one związane z jakimś konkretnym językiem (np. symbolem instrukcji przypisania może być “:=” tak, jak w Pascalu lub “=” tak, jak w C) Jeśli tworząc schemat nie jesteśmy jeszcze zdecydowani w jakim języku będziemy pisali nasz program lub tworzymy schemat dla kogoś, to lepiej jest stosować notację bardziej symboliczną, np. instrukcję przypisania zapisywać jako strzałkę skierowaną od wartości przypisywanej do zmiennej.

Za pomocą schematów blokowych łatwiej jest wizualizować działanie algorytmu. Od razu widać, co prowadzi do czego, nie ma więc problemu z np. źle ustawionymi lub brakiem wcięć kodu programu.

 

 Schematy algorytmów.

Poszczególne elementy schematu łączy się za pomocą strzałek. W większości przypadków blok ma jedną strzałkę wchodzącą i jedną wychodzącą.

Ta figura oznacza początek lub koniec algorytmu. W każdym algorytmie musi się znaleźć dokładnie jedna taka figura z napisem “Start” oznaczająca początek algorytmu oraz dokładnie jedna figura z napisem “Stop” oznaczająca koniec algorytmu. Najczęściej popełnianym błędem w schematach blokowych jest umieszczanie kilku stanów końcowych, zależnych od sposobu zakończenia programu. Jest to niedopuszczalne, w programie mamy przecież dokładnie jedną instrukcję “end.” Blok symbolizujący początek algorytmu ma dokładnie jedną strzałkę wychodzącą a blok symbolizujący koniec ma co najmniej jedną strzałkę wchodzącą.

Jest to figura oznaczająca proces. W jej obrębie umieszczamy wszelkie obliczenia lub podstawienia. Proces ma dokładnie jedną strzałkę wchodzącą i dokładnie jedną strzałkę wychodzącą.

 

Romb symbolizuje blok decyzyjny. Umieszcza się w nim jakiś warunek (np. “x>2”). Z dwóch wybranych wierzchołków rombu wyprowadzamy dwie możliwe drogi: gdy warunek jest spełniony (strzałkę wychodzącą z tego wierzchołka należy opatrzyć etykietą “Tak”) oraz gdy warunek nie jest spełniony. Każdy romb ma dokładnie jedną strzałkę wchodzącą oraz dokładnie dwie strzałki wychodzące.

Równoległobok jest stosowany do odczytu lub zapisu danych. W jego obrębie należy umieścić stosowną instrukcję np. Read(x) lub Write(x) (można też stosować opis słowny np. “Drukuj x na ekran”). Figura ta ma dokładnie jedną strzałkę wchodzącą i jedną wychodzącą.

 

Ta figura symbolizuje proces, który został już kiedyś zdefiniowany. Można ją porównać do procedury, którą definiuje się raz w programie, by następnie móc ją wielokrotnie wywoływać. Warunkiem użycia jest więc wcześniejsze zdefiniowanie procesu. Podobnie jak w przypadku zwykłego procesu i tu mamy jedno wejście i jedno wyjście.

Koło symbolizuje tzw. łącznik stronicowy. Może się zdarzyć, że chcemy “przeskoczyć” z jednego miejsca na kartce na inne (np. by nie krzyżować strzałek). Możemy w takim wypadku posłużyć się łącznikiem. Umieszczamy w jednym miejscu łącznik z określonym symbolem w środku (np. cyfrą, literą) i doprowadzamy do nie go strzałkę. Następnie w innym miejscu kartki umieszczamy drugi łącznik z takim samym symbolem w środku i wyprowadzamy z niego strzałkę. Łącznik jest często porównywany do teleportacji (z jednego miejsca na kartce do drugiego). Łączniki występują więc w parach, jeden ma tylko wejście a drugi wyjście.

Ten symbol to łącznik międzystronicowy. Działa analogicznie jak pierwszy, lecz nie w obrębie strony. Przydatne w złożonych algorytmach, które nie mieszczą się na jednej kartce. Uwaga: jeśli stosujemy oba typy łączników w schemacie, to najlepiej jest stosować liczby do identyfikowania jednych i litery do drugich. Dzięki temu nie dojdzie do pomyłki.

 

Najszybciej schematy pisze się na zwykłej kartce, pojawia się jednak problem, gdy schemat trzeba umieścić w jakimś dokumencie (np. dokumentacji projektu). Można wtedy skorzystać z popularnych edytorów tekstu (np. Word, Writer). Mają one wbudowane opcje do tworzenia figur schematu, ale nie są one zbyt wygodne w użyciu.

 

 

Przykładowe schematy blokowe

1. Gotowanie budyniu.
Schemat stworzony w programie Paint

2. Schemat algorytmu parzenia kawy z automatu stworzony w programie Word za pomocą Autokształtów.

3

Author: ZSE

Admnistrator serwisu. Nauczyciel przedmiotów informatycznych

Share This Post On

Submit a Comment

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *