algorytmika

Report
algorytmika
1
Od problemu do programu
problem
wy
bó
r
algorytm
za
pis
program
2
Zależność między programem a
algorytmem
komputer
wy
ko
nuj
e
Program
komputerowy
rea
lizu
je
algorytm
3
Definicje
• Algorytm to uporządkowany i uściślony sposób
rozwiązywania problemu, zawierający
szczegółowy opis wykonywanych czynności
• Program komputerowy to logicznie
uporządkowany ciąg instrukcji języka
programowania, realizujący algorytm
• Specyfikacja zadania – szczegółowy opis
zadania, w którym wymieniane są dane
wejściowe i wyniki oraz warunki jakie muszą
spełniać, określa się więc związek między
danymi a wynikami
4
Definicje
• Algorytmy, które wykonują działania
matematyczne na danych liczbowych,
nazywamy algorytmami numerycznymi.
• Algorytmika, to dział informatyki zajmujący
się różnymi aspektami tworzenia i
analizowania algorytmów
5
Etapy konstruowania algorytmu:
• sformułowanie zadania – ustalamy jaki problem
ma rozwiązać algorytm;
• określenie danych wejściowych, ich typu;
• określenie wyniku i sposobu jego prezentacji;
• ustalenie metody wykonania zadania;
• zapisanie algorytmu za pomocą wybranej
metody;
• analiza poprawności rozwiązania;
• testowanie rozwiązania dla różnych danych;
• ocena skuteczności algorytmu;
6
Cechy dobrego algorytmu
• Poprawność- algorytm powinien zwracać
prawidłowe wyniki dla każdego zestawu
poprawnych danych.
• Skończoność- rozwiązanie zadania musi być
możliwe dla dowolnego zestawu danych w
skończonej liczbie kroków.
• Jednoznaczność- algorytm powinien zwracać te
same wyniki dla zestawu takich samych danych
wejściowych.
• Sprawność- szybkość działania i optymalne
wykorzystanie zasobów komputera
7
Sposoby zapisu, prezentacji
algorytmów
•
•
•
•
•
•
•
wypowiedź ustna
lista kroków
pseudojęzyk (pseudokod)
schemat blokowy
drzewo algorytmu
prezentacja w programach użytkowych
zapis w języku programowania
8
Specyfikacja zadania
• Problem: oblicz średnia arytmetyczna trzech
dowolnych liczb rzeczywistych.
• Dane: trzy dowolne liczby rzeczywiste A, B, C
• Wynik: wartość średniej arytmetycznej liczb
A, B, C, równa SR
9
Algorytm w postaci listy kroków - oblicza średnią
arytmetyczną trzech dowolnych liczb rzeczywistych
•
•
1.
2.
3.
4.
5.
6.
Dane: dowolne liczby rzeczywiste A, B, C
Wynik: wartość średniej arytmetycznej liczb A, B, C równa SR
Zacznij algorytm
Wprowadź wartość trzech liczb A, B, C
Zmiennej S przypisz wartość wyrażenia a+b+c -> S:=A+B+C
Zmiennej SR przypisz wartość wyrażenia s/3 -> SR:=S/3
Wyprowadź wynik: SR
Zakończ algorytm
10
Graficzna prezentacja algorytmu schemat blokowy
11
Graficzna prezentacja algorytmu schemat blokowy
12
Zasady przedstawiania algorytmów w
postaci schematu blokowego
Ogólne zasady budowania schematów blokowych nie zależą od kształtu
tworzących je bloków ani od narzędzi stosowanych do ich konstrukcji.
1. Operacje algorytmu należy umieszczać w odpowiednich blokach.
2. Każdy schemat blokowy ma jeden blok startowy, natomiast bloków
zakończenia algorytmu może być kilka.
3. Wszystkie bloki muszą być ze sobą połączone (nie może być „przerw" w
schemacie). Każde połączenie jest zaczepione do danego bloku i
dochodzi do następnego bloku lub innego połączenia.
4. Kolejność wykonywania operacji wyznaczają połączenia między blokami.
5. Do każdego bloku wchodzi jedno połączenie (oprócz bloku początku) i
jedno wychodzi (oprócz bloku warunku, z którego wychodzą dwa
połączenia, oraz bloku zakończenia algorytmu, z którego nie wychodzi już
żadne połączenie).
13
Algorytm obliczania średniej arytmetycznej
trzech dowolnych liczb rzeczywistych.
14
Przykład algorytmu liniowego
15
Algorytm liniowy, algorytm z
warunkami
• Algorytm liniowy realizuje jeden ciąg działań,
czynności wykonywane są po kolei
• W algorytmie z warunkami może wystąpić
kilka alternatywnych ciągów działań. Wybór
jednego z nich zależy od spełnienia (lub
niespełnienia) warunku
16

similar documents