Ćwiczenie I

 

1. Pojęcia

Pojęcie algorytmu

 

2. Wiadomości

2.1 Historia informatyki

 

 

 

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

 

 

 

 

 

2.2 Algorytmika – algorytmy – definicje

 

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:

  1. określenia dopuszczalnego zbioru danych wejściowych,
  2. specyfikacji wyników jako funkcji danych wejściowych

 

 

2.3 Informatyczne rozwiązywanie zadań

 

            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

 

 

 

 

 

 

 

2.4 Rodzaje algorytmów

 

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)

 

 

3. Zadania i ćwiczenia

 

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