Algorytmika
TECHNOLOGIA INFORMACYJNA
PODSTAWOWE POJ
CIA
�� ALGORYTMIKA to jeden z obszarów
tematycznych informatyki; zajmuje się
budowaniem i badaniem teoretycznych modeli
informatycznych, czyli algorytmami
�� ALGORYTM to skończony, uporządkowany zbiór
jasno zdefiniowanych czynności, koniecznych
do wykonania pewnego zadania w ograniczonej
liczbie kroków; ma przeprowadzić system z
pewnego stanu początkowego do pożądanego
stanu końcowego
ALGORYTMY KOMPUTEROWE
�� Komputery przetwarzają przekazywane im
informacje z wykorzystaniem pewnych algorytmów.
Program jest algorytmem zapisanym w języku
zrozumiałym dla maszyny (asemblerze).
�� Każdy algorytm komputerowy musi być wyrażony w
bardzo rygorystycznie zdefiniowanym języku.
�� Jeżeli dany algorytm da się wykonać na maszynie o
dostępnej mocy obliczeniowej i pamięci oraz
akceptowalnym czasie, to mówi się że jest
obliczalny.
ETAPY ROZWI
ZYWANIA PROBLEMÓW
1. Sformułowanie zadania
2. Określenie danych wejściowych
3. Określenie celu działania, czyli wyniku
4. Poszukiwanie metody rozwiązania, czyli algorytmu
5. Przedstawienie algorytmu w postaci
sformalizowanej
6. Analiza poprawności rozwiązania
7. Ocena efektywności przyjętej metody
SPOSOBY ZAPISYWANIA ALGORYTMÓW
�� Zapis w postaci ciągu kroków polega na
podaniu kolejnych wykonywanych operacji,
składających się na całe rozwiązanie; zapis
może być zrealizowany z wykorzystaniem języka
potocznego, metajęzyka, języka programowania
�� Zapis w postaci graficznej - schematy blokowe;
Schemat blokowy to graficzne przedstawienie
ciągu kroków algorytmu, często stosowane jako
ideowy rysunek poprzedzający tworzenie
programu.
LISTA KROKÓW  PIERWIASTKI RÓWNANIA
KWADRATOWEG0
�� Krok 1: Wczytaj współczynniki a, b, c równania.
�� Krok 2: Jeśli a = 0, wypisz komentarz:  To nie
jest równanie kwadratowe i przejdz
do kroku 7.
�� Krok 3: Oblicz wyróżnik (delta) według wzoru:
" = b*b - 4*a*c
�� Krok 4: Jeśli " > O, oblicz x1 oraz x2 i wyświetl
ich wartości (-bąsqrt(")/(2a))
LISTA KROKÓW  PIERWIASTKI RÓWNANIA
KWADRATOWEG0
�� Krok 5: Jeśli " = O, oblicz x0 i wyświetl jego
wartość (x0 = -b/(2a))
�� Krok 6: Jeśli " < O, wyświetl komunikat:  Brak
rozwiązań w zbiorze liczb rzeczywistych
�� Krok 7: Zakończ działanie algorytmu
J
ZYKI PROGRAMOWANIA  PIERWIASTKI
RÓWNANIA KWADRATOWEGO
�� Writeln( Poszukiwanie pierwiastków równania
kwadratowego );
�� writeln( Podaj współczynniki a, b, c: );
�� write( a=  ); readln(a);
�� write( b=  ); readln(b);
�� write( c=  ); readln(c);
�� d=delta(a,b,c);
�� if d<0 then writeln( Równanie nie ma rozwiązania )
�� else if d=0 then jeden_pierwiastek(a,b)
�� else dwa_pierwiastki(a,b,d);
SCHEMATY BLOKOWE
SCHEMATY BLOKOWE
�� Schemat blokowy (ang. block diagram,
flowchart) to diagram, na którym procedura,
system albo program komputerowy są
reprezentowane przez opisane figury
geometryczne, połączone liniami zgodnie z
kolejnością wykonywania czynności
wynikających z przyjętego algorytmu
rozwiązania zadania.
�� Schemat blokowy pozwala opisać istotne etapy
algorytmu i wskazać logiczne zależności między
nimi.
SCHEMATY BLOKOWE  RODZAJE BLOKÓW
�� Blok graniczny - oznacza on początek, koniec,
przerwanie lub wstrzymanie wykonywania
działania, np. blok startu programu.
SCHEMATY BLOKOWE  RODZAJE BLOKÓW
�� Blok wejścia-wyjścia  przedstawia
czynność wprowadzania danych do
programu i przyporządkowania ich
zmiennym dla póz
niejszego
wykorzystania, jak i
wyprowadzania stanu zmiennych
SCHEMATY BLOKOWE  RODZAJE BLOKÓW
�� Blok obliczeniowy - oznacza
wykonanie operacji, w efekcie
której zmienią się wartości
zmiennych, postać lub miejsce
zapisu danych, np. z = z + 1.
SCHEMATY BLOKOWE  RODZAJE BLOKÓW
�� Blok decyzyjny - przedstawia wybór
jednego z dwóch wariantów
wykonywania programu na
podstawie sprawdzenia
zdefiniowanego w nim warunku
np. a = b.
SCHEMATY BLOKOWE  RODZAJE BLOKÓW
�� Blok wywołania
podprogramu - oznacza
zmianę wykonywanej
czynności na skutek
wywołania podprogramu,
np. MAX(x,y,z).
SCHEMATY BLOKOWE  RODZAJE BLOKÓW
�� Blok fragmentu - przedstawia
część programu zdefiniowanego
odrębnie, np. sortowanie.
SCHEMATY BLOKOWE  RODZAJE BLOKÓW
�� Blok komentarza - pozwala wprowadzać
komentarze wyjaśniające poszczególne części
schematu, co ułatwia zrozumienie go
czytającemu, stosowany w szczególnie
skomplikowanych schematach
SCHEMATY BLOKOWE  RODZAJE BLOKÓW
�� A
ącznik wewnętrzny - służy do łączenia
odrębnych części schematu znajdujących się
na tej samej stronie, powiązane ze sobą
łączniki oznaczone są tą samą etykietą
SCHEMATY BLOKOWE  RODZAJE BLOKÓW
�� A
ącznik zewnętrzny - służy do łączenia
odrębnych części schematu znajdujących się
na odrębnych stronach, powinien być opisany
jak łącznik wewnętrzny, poza tym powinien
zawierać numer strony, do które się odwołuje
TYPOWE KONSTRUKCJE W ALGORYTMACH
�� Konstrukcja warunkowa - mamy z nią do czynienia
wówczas, gdy wynik lub dalsze działanie należy od
spełnienia pewnego warunku. Na schemacie
blokowym sytuacje warunkowe realizujemy przez
blok decyzyjny
�� Iteracja (działanie w pętli) to technika
algorytmiczna polegająca na wielokrotnym
wykonaniu pewnej sekwencji instrukcji. Liczba
powtórzeń w iteracji jest z góry określona lub
zależy od spełnienia określonego warunku. Iteracja
w schemacie blokowym to zamknięta pętla
zawierająca przynajmniej jeden blok decyzyjny
PARADYGMATY TWORZENIA ALGORYTMÓW
�� Dziel i zdobywaj - dzielimy problem na kilka
mniejszych i je znowu dzielimy, aż ich rozwiązania
nie staną się oczywiste (rekurencja)
�� Metoda zachłanna - nie analizujemy
podproblemów dokładnie, tylko wybieramy
najbardziej obiecującą w tym momencie drogę
rozwiązania
�� Programowanie dynamiczne - jest techniką
projektowania algorytmów stosowaną przeważnie
do rozwiązywania zagadnień optymalizacyjnych,
dla których nie istnieją algorytmy zachłanne.
PARADYGMATY TWORZENIA ALGORYTMÓW
�� Programowanie liniowe - oceniamy rozwiązanie
problemu przez pewną funkcję jakości i szukamy
jej minimum
�� Poszukiwanie i wyliczanie - przeszukujemy zbiór
danych aż do odnalezienia rozwiązania
�� Probabilistyczne rozwiązanie - algorytm działa
poprawnie z pewnym prawdopodobieństwem, ale
wynik nie jest pewny
�� Heurystyka - metoda znajdowania rozwiązań dla
której nie ma gwarancji znalezienia rozwiązania
optymalnego, a często nawet prawidłowego
PRZYKA
AD ALGORYTMU EUKLIDESA
�� Algorytm Euklidesa (metoda kolejnych dzieleń]
to algorytm znajdowania największego
wspólnego dzielnika (NWD) dwóch różnych liczb
naturalnych (autorstwa Eudoksosa z Knidos)
�� Dane są dwie liczby naturalne dodatnie a i b
�� Oblicz c jako resztę z dzielenia a przez b
�� Zastąp a przez b, zaś b przez c
�� Jeżeli b = O, to szukany NWD = a, w przeciwnym
przypadku przejdz
do kroku 2
PRZYKA
AD ALGORYTMU EUKLIDESA
�� Obliczyć NWD(1001,42):
�� NWD(1001,42)=7
ALGORYTM EUKLIDESA - REKURENCJA
�� Algorytm Euklidesa można zapisać w postaci
rekurencyjnej
�� Rekurencja definiuje funkcję odwołując się w
definicji do niej samej
�� Definicja rekurencyjna potrzebuje przynajmniej
jednego przypadku bazowego (nie
rekurencyjnego) - w tym przypadku jest to
wartość dla b=0
ALGORYTM EUKLIDESA - REKURENCJA ZAPIS W
J
ZYKACH C I PASCAL
�� int nwd(int a, int b)
{ int tmp;
while (b) // czyli while(b! = 0)
{ tmp = a%b;
a = b;
b = tmp;
}
return a;
}
ALGORYTM EUKLIDESA - REKURENCJA ZAPIS W
J
ZYKACH C I PASCAL
�� function nwd(a,b: Integer): Integer;
var tmp: Integer;
begin
repeat
tmp := a mod b;
a := b;
b := tmp;
until b = 0;
nwd := a;
end;
ALGORYTM EUKLIDESA - REKURENCJA ZAPIS W
J
ZYKACH C I PASCAL
�� int nwd(int a, int b)
{ int tmp;
while (b) // czyli while(b! = 0)
{ tmp = a%b;
a = b;
b = tmp;
}
return a;
}
�� function nwd(a,b: Integer): Integer;
var tmp: Integer;
begin
repeat
tmp := a mod b;
a := b;
b := tmp;
until b = 0;
nwd := a;
end;