Pojęcie algorytmu
AUTOMAT VON NEUMANNA (von Neumann, Turing, 1945)
Pomysł - automat sekwencyjny sterowany programem
Istota - program sterujący przechowywany w pamięci
Elementy:
- procesor
- pamięć
- moduł wejścia-wyjścia
- szyna adresowa
- szyna danych
- szyna sterująca
Rozwiązując jakikolwiek problem (zadanie) stosujemy zazwyczaj określoną metodę – przepis - która ma pozwolić na uzyskanie wyniku (rozwiązania). Warunkiem przystąpienia do rozwiązywania jakiegokolwiek problemu jest posiadanie niezbędnych wiadomości i doświadczenia.
ALGORYTM – sposób postępowania, aby otrzymać poprawny wynik
ALGORYTM – skończony ciąg operacji wraz ze ściśle sprecyzowanym porządkiem ich wykonywania, które po realizacji dają poprawny wynik charakteryzujący się:
- skończoność
- określoność
- ogólność
- efektywność
Właściwości:
- poprawny
- określony
- wykonywalny
- testowany
- efektywność
Opis szczegółowy właściwości:
ogólność
algorytm formułuje się dla całej klasy podobnych zadań, różniących się parametrami ustalanymi za pośrednictwem danych wejściowych określonego typu. Sformułowanie algorytmu nie powinno korzystać ze specyficznych cech wykonawcy;
jednoznaczność
w algorytmie nie ma miejsca na dowolność interpretacji. Zamiast powiedzieć: weź dowolną wartość, trzeba określić sposób jej wyliczenia lub pobrania;
skończoność
niezależnie od tego, czy liczba przewidzianych do wykonania czynności jest z góry znana, czy też zależy od danych, sam zapis poleceń musi być ujęty w skończonej formie;
skuteczność
dla każdego prawidłowego zestawu danych algorytm powinien zatrzymać się w skończonym czasie (po wykonaniu lub mimo niewykonania zadania). Znaczenie pojęcia „prawidłowy zestaw danych” winno być wyjaśnione w specyfikacji danych.
W ten sposób, 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.
Zadanie algorytmiczne składa się z:
W procesie rozwiązywania każdego zadania możemy wyróżnić pewne etapy, które nas do niego prowadzą:
Rozwiązanie algorytmiczne polega, więc na podaniu algorytmu tzn. takiego opisu działań przy pomocy operacji elementarnych, który zastosowany do poprawnych danych wejściowych daje oczekiwane wyniki. Rozróżniamy wykonywanie algorytmów od działania twórczego.
Problemy dotyczące algorytmów:
1. Język: zbiór instrukcji elementarnych;
2. Rozstrzygalność: czy istnieje algorytm rozwiązujący dany problem?
3. Analiza poprawności: czy algorytm działa poprawnie, tzn. robi to co
ma robić?
4. Analiza złożoności: czy algorytm działa szybko?
5. Analiza numeryczna: czy algorytm działa dokładnie?
W informatycznym rozwiązywaniu zadań wyróżniamy następujące etapy:
· - sformułowanie zadania;
· - konstruowanie algorytmu jako przepisu na rozwiązanie zadania;
· - konstruowanie schematu blokowego reprezentacji algorytmu;
· - konstruowanie programu komputerowego jako zapisu algorytmu w języku programowania;
· - weryfikacja, analiza i eksploatacja programu
Algorytmy możemy podzielić na:
1) Algorytmy imperatywne
2) Algorytmy funkcjonalne
1) Przykład algorytmu imperatywnego
Zamiana pliku:
utwórz plik tymczasowy
zapisz nowe dane do pliku tymczasowego
wykonaj rename(nazwa pliku tymczasowego, nazwa wymienianego pliku)
2) Przykład algorytmu funkcjonalnego
Przykład algorytmu funkcjonalnego: wyliczanie reszty modulo:
x reszta_modulo y ::= x - y * (x podzielone_całkowitoliczbowo_przez y)
Ćwiczenie 1
Zapisać w formie kolejnych poleceń sposób określania liczby rozwiązań równania kwadratowego.
Ćwiczenie 2
Zapisać w formie kolejnych poleceń sposób obliczania wartości rozwiązań (pierwiastków) równania kwadratowego
Ćwiczenie 3
Opracuj algorytm telefonicznego zawiadamiania - numer telefonu : 616-22-22.
Ćwiczenie 4
Czy przepisy kulinarne są algorytmami?
Jakie formy działalności nie stanowią działania algorytmicznego?
Ćwiczenie 5
Zapisać w formie algorytmu program, pobierający aktualny czas i wyświetlający komunikat:
- „Dzień dobry” – przed 12.00
- „Dobry wieczór” – po 12.00
Ćwiczenie 6
Zapisać w formie algorytmu program, pobierający aktualny czas i wyświetlający komunikat:
- „Dzień dobry” – przed 12.00
- „Dobry wieczór” – po 12.00
jedynie trzy razy, następne wywołanie nie powoduje wyświetlenia żadnego komunikatu
Ćwiczenie 7
Zapisać w formie algorytmu program pobierający od użytkownika liczbę całkowitą i następnie wyświetlający komunikat określający, czy wprowadzona liczba jest parzysta czy nieparzysta.
Ćwiczenie 8
Zapisać w formie algorytmu program pobierający od użytkownika liczbę całkowitą i następnie wyświetlający komunikat określający, czy wprowadzona liczba jest parzysta czy nieparzysta – dodatkowo sprawdzenie poprawności, czyli czy rzeczywiście wprowadzono liczbę całkowitą.