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;