1

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

PRSUS

Projektowanie i symulacja

układów sterowania

2. Zasady budowania algorytmów

dr inż. Mirosław Nejman

Konsultacje:

pok. ST 142, śr. 13-14, czw. 14-15
e-mail: [e-mail]

tel.: [phone]

http://www.zaoios.pw.edu.pl

Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Co to jest algorytm?

Algorytm

-

„dokładny przepis wykonania

w

określonym porządku skończonej liczby operacji, pozwalający na

rozwiązanie każdego zadania danego typu”

Słownik języka polskiego PWN

Słowo „algorytm” wywodzi się od nazwiska arabskiego matematyka z IX
w. Mahmuta al-

Chorizmiego. Opisał on krok po kroku zasady

wykonywania czterech podstawowych operacji arytmetycznych
na liczbach dziesiętnych.

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Podstawowe cechy algorytmu

Uniwersalność

, czyli zapewnienie rozwiązania każdego zadania

należącego do określonego typu zadań.

Jednoznaczność

, czyli prezentacji metody postępowania w postaci

skończonej listy prostych i jednoznacznych rozkazów.

Zbieżność

, czyli dla każdego dopuszczalnego zbioru danych

początkowych liczba operacji prowadzących do poszukiwanego wyniku
jest skończona

Powtarzalność

, czyli każdy z użytkowników, stosując analogiczne dane i

algorytm, uzyska analogiczne wyniki.

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Po co tworzy się algorytmy ?

Algorytmy tworzy się po to, by rozwiązywać problemy.

Problemy:

– Nie każdy problem może być rozwiązany przy pomocy

algorytmu!

– Problemy, które mogą być rozwiązane przy pomocy algorytmu,

nazywamy algorytmicznymi, np.:

„ile mam zapłacić podatku, jeżeli

wygram milion w lotto?”

– Problemy, które nie mogą być rozwiązane przy pomocy algorytmu,

nazywamy niealgorytmicznymi, np.

„które liczby mam skreślić, żeby

wygrać milion w lotto?”

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Typy problemów

– Problemy, na które odpowiedzią jest Tak lub Nie nazywamy

decyzyjnymi, np.:

„czy mam płacić jakiś podatek, jeżeli wygram

milion w lotto?”

– Wszystkie pozostałe problemy nazywamy optymalizacyjnymi, np.:

„ile mam zapłacić podatku, jeżeli wygram milion w lotto?”

– Problemy mogą być przy tym obliczeniowo:

• Łatwe, czyli takie które można rozwiązać zadowalająco szybko,

np.:

rozpakować plik typu „zip” zabezpieczony hasłem, znając

hasło.

• Trudne, czyli takie które można rozwiązać, ale zajęłoby to zbyt

wiele czasu, np.:

rozpakować plik typu „zip” zabezpieczony

hasłem, nie znając hasła.

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Etapy rozwiązywania problemów:

1.

Sformułowanie zadania

2.

Określenie danych wejściowych

3.

Określenie celu, czyli wyniku

4.

Poszukiwanie metody rozwiązania, czyli algorytmu

5. Przedstawienie algorytmu w postaci:

– opisu słownego
– listy kroków
– schematu blokowego
– jednego z języków programowania

6. Analiza poprawności rozwiązania
7. Testowanie rozwiązania dla różnych danych - ocena efektywności
przyjętej metody

2

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Metody zapisu algorytmów

Do popularnych metod specyfikacji algorytmów zaliczamy:

– opis słowny w języku naturalnym
– notacja matematyczna
– metody graficzne, (np. schematy blokowe, strukturogramy, diagramy

UML)

– tablice decyzyjne
– zapis w niesformalizowanym języku syntetycznym (tzw. pseudokod)
– zapis w sformalizowanym języku syntetycznym (np. BASIC, Pascal,

C)

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Metody zapisu algorytmów

Opis słowny w języku naturalnym.

Najbardziej natural

ny dla człowieka, ale:

– Nieprecyzyjny
– Rozwlekły
– Wykorzystujący niezdefiniowane pojęcia

Stąd:

– Trudny do automatycznego przeniesienia na komputer

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Metody zapisu algorytmów

Notacja matematyczna

– Wykorzystuje symbole matematyczne
– Oszczędna i precyzyjna
– Bardzo użyteczna, jednak tylko dla algorytmów przeznaczonych do

obliczania czegoś (karmienie psa - odpada)

Przykład: algorytm obliczający sumę kwadratów liczb naturalnych od 1 do
100:





100

1

2

i

i

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Metody zapisu algorytmów

Zasady rysowania schematów blokowych

Schemat blokowy składa się:

– z elementów graficznych (zwanych blokami) oznaczających etapy

algorytmu

– ze strzałek łączących bloki, oznaczających kierunek wykonywania

programu

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Zasady rysowania schematów blokowych

Każdy schemat blokowy:

– Zaczyna się od bloku początkowego

– Kończy się blokiem końcowym

Przykład: Algorytm, który nic nie robi:

START

STOP

START

STOP

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Zasady rysowania schematów blokowych

Podstawowe rodzaje bloków:

– Operacyjny – oznacza działanie.

Ma jedno wejście, jedno wyjście.

– Wyboru – oznacza wybór jednej z możliwych dróg postępowania.

Ma jedno wejście, dwa lub więcej wyjść.

Zrób coś

Gotowe

czy nie?

Tak

Nie

3

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Przykład schematu blokowego: Gotowanie wody

Nalej wodę do czajnika

START

Włącz czajnik

Zagotowana?

Nie

Tak

Wyłącz czajnik

STOP

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Przykład schematu blokowego: Wizyta u dentysty

Zarejestruj się

Boisz się?

START

Nie

1

Tak

STOP

Wyjdź z poczekalni

1

Wejdź do gabinetu

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Diagramy stanu UML

• Wypełnione kółko oznacza początek
• Kółko z kropką oznacza koniec
• Zaokrąglony prostokąt oznacza stan
• Strzałka oznacza przejście
• Grube poziome linie pozwalają
• na rozwidlenie lub złączenie procesu

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Strukturogramy

Operacja

Blok operacyjny

Blok wielokrotnego wyboru

Operacja

Operacja

Operacja

W

1

2

N

...

Blok warunkowy

Warunek

TAK

Operacja Operacja

Operacja

NIE

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Strukturogramy

Blok P

ętli

(2 rodzaje)

Powtórz N razy

Operacja

Warunek trwania

Operacja

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Strukturogram -

przykład

Wyłącz dzwonek

Czy masz
siłę wstać ?

Tak

Nie

Wstań

Śpij dalej

Koniec

Budzik nie dzwoni

Śpij dalej

4

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Tablice decyzyjne

Tablica decyzyjna

składa się z kolumn i wierszy podzielonych na 4 części

– Lewa górna ćwiartka zawiera warunki
– Lewa dolna ćwiartka zawiera procedury do wykonania
– Prawa górna ćwiartka zawiera rozpatrywane alternatywy
– Prawa dolna ćwiartka zawiera przyporządkowanie alternatyw do

procedur

Warunki

Alternatywy
warunków

Procedury

Rozpoczęcie
procedur

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Przykład tablicy decyzyjnej

Nieprzytomny klient

N N T N

Agresywny klient

T N - T

Klient coś ukradł

T T - N

Wezwij ochronę

X

Włącz alarm

X

Wezwij karetkę

X

Interweniuj

X

Warunki

Alternatywy
warunków

Procedury

Rozpoczęcie
procedur

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Przykład tablicy decyzyjnej

Nieprzytomny klient

N N T N

Agresywny klient

T N - T

Klient coś ukradł

T T - N

Wezwij ochronę

X

Włącz alarm

X

Wezwij karetkę

X

Interweniuj

X

Warunki

Alternatywy
warunków

Procedury

Rozpoczęcie
procedur

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Przykład tablicy decyzyjnej

Nieprzytomny klient

N N T N

Agresywny klient

T N - T

Klient coś ukradł

T T - N

Wezwij ochronę

X

Włącz alarm

X

Wezwij karetkę

X

Interweniuj

X

Warunki

Alternatywy
warunków

Procedury

Rozpoczęcie
procedur

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Pseudokod

Pseudokod

jest ogólnym sposobem opisu algorytmu opartym na

konwencji języków programowania, jednak nie ograniczonym do słownika
i zasad składni określonego języka programowania
Pseudokod

zwykle przypomina język programowania, na którym jest

oparty, ale:

– Detale nieistotne dla zrozumienia algorytmu są pomijane
– Elementy języka programowania są przemieszane z jezykiem

naturalnym

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Pseudokod -

przykład

Pseudokod 1:

Pseudokod 2:



while n<>0



print square

root(n)



input n

while (n):



print n**0.5



input(n)

Python:

• Dopóki liczba nie jest zerem:

• Wyświetl jej pierwiastek

• Wczytaj następną liczbę

5

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Zapis w sformalizowanym języku syntetycznym

Zapis algorytmu musi odpowiadać słownikowi i zasadom składni
określonego języka programowania.
Składnia może wprowadzać pewną rozwlekłość.
Język programowania wymaga (zwykle) jawnego podania wszystkich
szczegółowych danych.
Algor

ytm zapisany w sformalizowanym języku syntetycznym może być

automatycznie przetłumaczony na wykonywalny program.

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Języki programowania

JĘZYK WEWNĘTRZNY MASZYNY (kod maszynowy) składa się z
rozkazów mikroprocesora reprezentowanej w formie binarnej
JĘZYKI SYMBOLICZNE (asemblery) - notacja
w postaci skrótowych oznaczeń poszczególnych instrukcji
JĘZYKI WYSOKIEGO POZIOMU

– Ogólnego przeznaczenia: Basic, Pascal, C, Python
– Ekonomiczne: Cobol
– Komunikacji z bazami danych: SQL
– Sztucznej inteligencji: Prolog

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Języki niskiego poziomu

Kod maszynowy

3D00100000
730E
F7D8
03C4
83C004
8500
94
8B00
50
C3

Asembler

cmp eax, 1000
jae @dalej
neg eax
add eax, esp
add eax, 4
test dword[eax], eax
xchg eax, esp
mov eax, dword[eax]
push eax
ret

Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania

Rozwój języków programowania

I generacja: Kod maszynowy
II generacja: J

ęzyk symboliczny

III generacja: J

ęzyki wysokiego poziomu

– BASIC, Pascal, C

IV generacja: podej

ście obiektowe, interfejs bazodanowy, graficzny

interfejs u

żytkownika

– LabVIEW, Visual BASIC, Delphi, C#