1 ALGORYTMY

2 ALGORYTM (w potocznym rozumieniu), to jednoznaczny formalny przepis (recepta) postępowania. Nie wymaga się przy tym rozumienia treści rozwiązywanego zagadnienia, wystarczy tylko ściśle wypełnić podane w opisie wskazówki.

3 Specyfikacja zadania Aby rozwiązać dowolny problem (zadanie), nie tylko z informatyki, trzeba go wcześniej poprawnie sformułować oraz ustalić dane i określić cel, czyli wyniki. Następnie zastanowić się nad sposobem jego rozwiązania, czyli algorytmem, a także wyborem odpowiedniego narzędzia, np. programu komputerowego, który to ułatwi.

4 Specyfikacja zadania SPECYFIKACJA ZADANIA, to opisanie zadania, czyli przedstawienie związku, jaki zachodzi między danymi a wynikami.

5 Przykłady algorytmów przepisy kulinarne instrukcje obsługi i montażuprocedury ewakuacyjne instrukcje przeprowadzenia doświadczeń, np. chemicznych instrukcje wykonywania obliczeń matematycznych, np. znajdowanie NWD lub NWW liczb naturalnych.

6 Definicja algorytmu ALGORYTMEM nazywamy opis obiektów łącznie z opisem czynności, które należy wykonać w ściśle określonej kolejności na tych obiektach, aby w skończonej liczbie kroków rozwiązywać zadanie.

7 Cechy algorytmu SKOŃCZONOŚĆ – musi on obrazować rozwiązanie zagadnienia za pomocą skończonej liczby kroków OKREŚLONOŚĆ – każdy krok powinien być określony jednoznacznie i we wszystkich możliwych przypadkach EFEKTYWNOŚĆ – wszystkie operacje powinny być dostatecznie proste WEJŚCIE – powinien on posiadać pewną liczbie danych wejściowych umożliwiających zapoczątkowanie go WYJŚCIE – powinien posiadać jedną lub więcej danych wyjściowych (wynik przeprowadzonych operacji)

8 Metody zapisywania algorytmówzapis w języku naturalnym (opis słowny) zapis w postaci listy kroków schematy blokowe lub sieci działań w językach formalnych (w postaci pseudokodu lub programów komputerowych)

9 Opis słowny algorytmu Opis słowny algorytmu składa się z opisu:obiektów, na których działa algorytm (co nazywamy DEKLARACJĄ) działania (czynności) algorytmu (co nazywamy OPISEM INSTRUKCJI)

10 Lista kroków Zapis algorytmu w postaci listy kroków polega na podaniu kolejno wykonanych operacji, składających się na rozwiązanie problemu.

11 Schematy blokowe Schemat blokowy algorytmu jest graficznym przedstawieniem słownego zapisu algorytmu. W schemacie blokowym poszczególne operacje przedstawione są za pomocą odpowiednio połączonych skrzynek (klocków, bloków). Połączenia określają kolejność i sposób wykonywania operacji realizujących dany algorytm.

12 Skrzynki schematów blokowychSkrzynki graniczne i łącznikowe start A A stop

13 Skrzynki schematów blokowychSkrzynki wprowadzania danych i wyprowadzania wyników czytaj a, b, c pisz x, y, z

14 Skrzynki schematów blokowychSkrzynki operacyjne (zwykle z operacją przypisania) delta := b*b-4*a*c

15 Skrzynki schematów blokowychSkrzynki warunkowe – selekcje (sprawdzenie wyników) warunek NIE TAK

16 Etapy rozwiązywania problemówSformułowanie zadania. Określenie danych wejściowych. Ustalenie celu, czyli wyniku. Określenie metody rozwiązania, czyli wybór algorytmu. Przedstawienie algorytmu w postaci: opisu słownego lub listy kroków, lub schematu blokowego, lub programu w wybranym języku oprogramowania. Analiza poprawności rozwiązania. Testowanie rozwiązania dla różnych danych – ocena efektywności przyjętej metody.

17 Przykład – przygotowanie kawyDEKLARACJA: kawa, woda, cukier, śmietanka OPIS SŁOWNY: przygotowanie składników zagotowanie wody wsypanie kawy do filiżanki (2 łyżeczki) zalanie kawy gorącą wodą dodanie cukru (2 łyżeczki) dodanie śmietanki pomieszanie

18 Przykład - przygotowanie kawyLISTA KROKÓW: start przygotuj składniki wsyp kawę do filiżanki zagotuj wodę (2 minuty) jeśli mam gorącą wodę przejdź do kroku 6, jeśli nie przejdź do 4 zalej kawę gorącą wodą dodaj cukier, jeśli nie słodzisz przejdź do kroku 8 dodaj śmietankę, jeśli bez śmietanki przejdź do kroku 9 pomieszaj stop

19 Przykład – przygotowanie kawySCHEMAT BLOKOWY start A zagotuj wodę (2 minuty) weź kawę, wodę, cukier, śmietankę Czy woda jest gorąca? NIE wsyp kawę do filiżanki A TAK B

20 B zalej kawę gorącą wodą Lubisz słodką kawę? TAK wsyp cukier NIE C

21 C Pijesz ze śmietanką? TAK dodaj śmietankę NIE pomieszaj stop

22 ĆWICZENIE DLA WAS Sporządź: słowny opis (obiektów i działań)listę kroków schemat blokowy gr. I smażenia jajecznicy gr. II gotowania budyniu gr. III przygotowania się do snu gr. IV wyjścia w deszczową pogodę

23 Algorytmy informatycznePrzykład specyfikacji zadania i listy kroków algorytmu Zadanie: Przedstaw w postaci listy kroków algorytm obliczania pola trójkąta. Dane: dowolne liczby rzeczywiste dodatnie: a, h (a – długość boku trójkąta, h – długość wysokości trójkąta opuszczonej na ten bok). Wynik: wartość pola trójkąta: P.

24 Algorytmy informatyczneZacznij algorytm. Wprowadź wartość boku a i wysokości h. Zmiennej P przypisz wartość wyrażenia: P := ½  a  h. Wyprowadź wynik: P. Zakończ algorytm.

25 ĆWICZENIE DLA WAS (zapisujemy algorytm w postaci listy kroków)Zapisz specyfikację zadania i listę kroków algorytmu obliczenia: gr. I - pola trapezu gr. II - pola równoległoboku gr. III - pola rombu

26 ĆWICZENIE DLA WAS (budujemy schemat blokowy)Narysuj i opisz schemat blokowy algorytmu rozwiązującego zadanie: Obliczanie rozwiązań równania kwadratowego ax2 + bx + c = 0, gdy dane są współczynniki a, b, c.

27 Dziękuję za uwagę 