Wprowadzenie do algorytmów
Wprowadzenie do algorytmów
Zwiększanie posiadanej wiedzy może odbywać się poprzez przetwarzanie danych
według określonego algorytmu.
PROCES KOMUNIKACJI
KOMPUTER
ALGORYTM
CZA
OWIEK
Informacja  przyrost wiedzy, który może być uzyskany na podstawie danych.
Informacja - każdy czynnik zmniejszający stopień niewiedzy o badanym zjawisku,
umożliwiający człowiekowi, organizmowi żywemu lub urządzeniu
automatycznemu polepszenie znajomości otoczenia i w sprawniejszy sposób
przeprowadzenie celowego działania.
ASD LJ S
1
Wprowadzenie do algorytmów
Muhammed Al Chwarizmi (łac. Algorismus) - perski matematyk twórca reguł:
dodawania, odejmowania, mnożenia i dzielenia liczb dziesiętnych.
Euklides, grecki matematyk - twórca reguły wyznaczania największego wspólnego
dzielnika dwóch liczb naturalnych GCD (Greater Common Divider).
Alan Turing
Kurt Godel
Andriej Markov
Alonzo Church
Emil Post
Al Chwarizmi ( IX w.) Euklides (III p.n.e)
Stephen Kleene
ASD LJ S
Wprowadzenie do algorytmów
1805 Krosno Jacquard'a - pierwsza w dziejach programowana maszyna
maszyna tkacka sterowania za pomocÄ… kart perforowanych.
Joseph Marie Jacquard
Krosno Jacquarda
ASD LJ S
2
Wprowadzenie do algorytmów
1642 B. Pascal - mechaniczny kalkulator (dodawanie i odejmowanie
ośmiocyfrowych liczb.
Pascaline - pierwsza maszyna liczÄ…ca
1673 W. Leibniz - rozszerzenie kalkulatora Pascal a o operacje /, *.
ASD LJ S
Wprowadzenie do algorytmów
(1822 - 1833) Ch. Babbage  maszyna analityczna (difference engine).
Charles Babbage
Model analitycznej maszyny Babbage`a
ASD LJ S
3
Podstawowe pojęcia i definicje
Algorytm (algorithm)  dokładny przepis podający sposób rozwiązania określonego
zadania lub osiągnięcie jakiegoś celu w postaci skończonej liczby
uporządkowanych kroków.
(Elementy: definicja zadania, przepis w postaci ściśle określonego ciągu
kroków, możliwość realizacji przepisu, każdy z kroków algorytmu ma być
czynnością możliwą do wykonania, wykonanie zadania w każdym przypadku,
skończony czas działania).
Algorytm (inf.) - precyzyjna i jednoznaczna sekwencja operacji obliczeniowych,
które przekształcają dane wejściowe w oczekiwane wyniki (dane wyjściowe).
(Elementy: definicja problemu określa dane wejściowe i dane wyjściowe,
każda operacja obliczeniowa ma być operacją możliwą do wykonania przez
komputer).
ASD LJ S
Podstawowe pojęcia
Algorytm - ściśle określona procedura obliczeniowa, która dla poprawnych danych
wejściowych  produkuje właściwe wyniki.
Algorytm - skończona sekwencja reguł, która aplikuje się na skończonej liczbie
danych, pozwalająca rozwiązywać określony problem (klasę problemów).
Algorytm - zespół reguł w procesie obliczeniowym (przetwarzania danych).
ALGORYTM
Dane wyjściowe
Dane wejściowe
(PROGRAM)
KOMPUTER
ASD LJ S
4
Podstawowe pojęcia
program
Program ( ) - reprezentacja algorytmu w określonym języku np. binarnym
(wewnętrznym), symbolicznym, proceduralnym, obiektowym.
Program - ciąg zrozumiałych dla komputera instrukcji (rozkazów), przeznaczonych
do wykonywania. Obiekt pasywny.
Program  zapis algorytmu operujÄ…cego na pewnych strukturach danych.
Program = algorytm + struktury danych.
Język programowania (program language)  zestaw zasad do opisu algorytmu,
umożliwiających komunikatywność człowiek - komputer.
Kod z
ródłowy programu (source code) - Implementacja algorytmu, zapis
algorytmu w wybranym języku programowania.
Proces (process)  wykonywanie programu, zwiÄ…zane z wykorzystaniem: licznika
rozkazów (program counter), stosu procesu (process stack), sekcji danych
(data section). Obiekt aktywny.
ASD LJ S
Cechy algorytmu
1. Określoność (definiteness) - możliwość wykonywania wszystkich operacji.
2. Jednoznaczność (uniqually determined) - jednoznaczność wszystkich
wykonywanych operacji.
3. Skończoność (finiteness) - uzyskanie rozwiązania postawionego problemu w
skończonej liczbie kroków.
4. Ogólność (generality)  sformułowanie na założonym poziomie ogólności,
(wykorzystanie do rozwiązywania określonej klasy zadań).
5. Efektywność (effectiveness)  złożoność obliczeniowa.
6. Zupełność (complete)  uzwględnienie wszystkich możliwych przypadków
jakie mogą wystąpić.
ASD LJ S
5
Algorytmiczne rozwiÄ…zywanie problemu
Koncepcja  środki - realizacja
1. Postawienie problemu:
- definicja problemu,
- opis danych wejściowych (Input) i wyjściowych (Output),
- sprecyzowanie wymagań dotyczących rozwiązania,
2. Budowanie algorytmu:
- koncepcja rozwiÄ…zania,
- zapis algorytmu i stopniowe precyzowanie,
- analiza algorytmu.
3. Tworzenie programu:
- wybór języka i struktur danych,
- kompilacja, testowanie.
ASD LJ S
Algorytmiczne rozwiÄ…zywanie problemu
PROBLEMY
Określenie obszaru zastosowania algorytmu.
P1 P2 Pn
... .
Projektowanie algorytmów (wybór algorytmów).
Implementowanie algorytmów (wybór języka
ALGORYTMY
programowania).
A1 A2 A3
Uruchamianie i testowanie programów (wybór
systemu).
PROGRAMY
PR1 PR2 PR3
SYSTEMY
S1 S2
ASD LJ S
6
Algorytmiczne rozwiÄ…zywanie problemu
Stopniowe precyzowanie algorytmu (stepwise refinement).
Model Abstrakcyjne
Struktury danych języka
matematyczny typy danych
programowania
Algorytm
Postać Algorytm
w języku programowania
nieformalna w pseudojęzyku
Abstrakcyjny Typ Danych (ADT, Abstract Data Type) - zbior danych tworzony i
opisywany w formalny sposób przez własności danych i opearcje wykonywane na
nich (nie przez reprezentacjÄ™ danych i implementacjÄ™ operacji).
Struktura danych (Data Structure) - zbior zmiennych typów posiadający swoistą
strukturę wraz z mechanizmem dostępu do danych (np. tablice, rekordy, struktury i
unie).
ASD LJ S
Specyfikacja algorytmów
Formy specyfikacji algorytmów:
Werbalna, opisowa (descriptive form).
Schemat blokowy, sieć działań, (flow diagram, flow chart).
Pseudokod (pseudocode).
Języki programowania (programming languages).
ASD LJ S
7
Konstrukcje algorytmiczne
Elementarne konstrukcje algorytmiczne (primitive constructions).
Bezpośrednie następstwo.
Wybór warunkowy.
Iteracja warunkowa.
Iteracja ograniczona (pętla).
ASD LJ S
Konstrukcje algorytmiczne
Bezpośrednie następstwo.
instrukcja1
Pseudokod
{
instrukcja 1
instrukcja2
instrukcja 2
. . .
instrukcja N
}
instrukcjaN
ASD LJ S
8
Konstrukcje algorytmiczne
Wybór warunkowy (select with condition).
Pseudokod
N
T
warunek
IF(warunek){
instrukcja
instrukcja
}
Wybór warunkowy (dwuwariantowy).
Pseudokod
N
T
warunek
IF(warunek){
instrukcja1
instrukcja2 }ELSE{
instrukcja1
instrukcja2
}
ASD LJ S
Konstrukcje algorytmiczne
Wybór wielowariantowy: CASE
Pseudokod
T N
w= warunek1
SWITCH (w)
{
CASE warunek1:
T N
instrukcja1
w= warunek2
BREAK;
CASE warunek2:
N
w= warunek3
instrukcja2
BRRAK;
T
CASE warunek3:
instrukcja1 instrukcja2 instrukcja3
instrukcja3
BREAK;
DEFAULT:
BREAK;
}
ASD LJ S
9
Konstrukcje algorytmiczne
Iteracja warunkowa (niejawna liczba iteracji): WHILE
Pseudokod
T N
warunek
WHILE(warunek){
instrukcja instrukcja
}
Implementacja iteracji: WHILE
Pseudokod
N
T
x > a
WHILE(x>a){
x=x-1
x=x-1;
}
ASD LJ S
Konstrukcje algorytmiczne
Iteracja warunkowa (niejawna liczba iteracji): DO - WHILE
Pseudokod
instrukcja DO{
instrukcja
T N
}WHILE (warunek)
warunek
ASD LJ S
10
Konstrukcje algorytmiczne
Implementacja iteracji: DO  WHILE
Pseudokod
x=x+1
DO{
x=x+1;
N T
x > a
}WHILE(x > a)
Pseudokod
y=y-1
DO{
y=y-1;
T N
y > b
}WHILE(y d" b)
ASD LJ S
Konstrukcje algorytmiczne
Iteracja ograniczona (pętla, loop): FOR
instrukcja_ini
Pseudokod
FOR (instrukcja_ini; warunek; instrukcja_krok) {
warunek
T instrukcja1
N
instrukcja_krok
instrukcjaN
}
instrukcja1
instrukcjaN
ASD LJ S
11
Kanstrukcje algorytmiczne
Implementacja pętli: FOR
Pseudokod
i = 1
FOR (i=1; id" n; i=i+1){
T N x=x+A[i];
i d" n
i=i+1;
}
x=x+A[i]
i = i + 1 Pseudokod
FOR (i=1,2,& .,n){
x=x+A[i];
i=i+1;
}
ASD LJ S
Algorytm Euklidesa
Algorytm Euklidesa NWD (GCD, Greatest Common Divisor ) wyznaczania
największego wspołnego dzielnika.
Sformułowanie zadania.
Dane są dwie liczby całkowite nieujemne: a, b,dla których a+b>0.
Wyznaczyć największą liczbę naturalną d taką, że a mod d =0 i b mod d =0.
Wynik: Największy Wspólny Dzielnik NWD(a,b) liczb: a, b.
Własność NWD:
1. NWD(a,b) = NWD(b,a).
2. Jeżeli mniejsza z liczb jest równa zero, to NWD jest równy drugiej z nich.
3. Jeżeli obie liczby są dodatnie, to NWD jest równy największemu wspólnemu dzielnikowi
ich różnicy oraz mniejszej z nich.
a jeżeli b = 0
NWD(a,b) =
NWD(a-b,b) jeżeli b>0
ASD LJ S
12
Algorytm Euklidesa - konstrukcje iteracyjne
NWD, Algorytm (Euklidesa).
Dane: liczby naturalne a, b,
Wynik: NWD liczb a, b;
a b a b h
Algorytm - Pseudokod
Algorytm - Pseudokod
20 15 20 15
5 15 15 5 5
ALG3_NWD (a,b)//Dane a, b;
ALG4_NWD(a,b)//Dane a,b; ae"
e"b;
e"
e"
// a>0; a+b>0; // a+b>0 ;
5 10 5 0 0
{
5 5
{ DO {
WHILE(a `" b) { h=a mod b;
`"
`"
`"
IF( a > b ) a=b;
a=a-b; b=h;
ELSE } WHILE (h`"
`"0);
`"
`"
b=b-a;
} return (a);
return (a); } // Wynik: NWD=a;
} // Wynik: NWD=a;
ASD LJ S
Konstrukcje iteracyjne - implementacja
Obliczenie sumy wyrazów zbieżnego szeregu
"
1
"
k
k = 0
2
z dokÅ‚adnoÅ›ciÄ… µ.
Algorytm - Pseudokod
ALG8_Suma // Suma wyrazów szeregu;
{
s=0;
w=1;
m=0;
DO{
s=s+w;
m=m+1;
w=w/2;
}WHILE(µ < w);
return(s,m);
} //Wynik: suma:=s;
// Ilość sumowanych wyrazów: m;
ASD LJ S
13
Konstrukcje iteracyjne - implementacja
Obliczanie sumy wyrazów szeregu z dokÅ‚adnoÅ›ciÄ… µ.
µ
µ
µ
1
4
1 1 1Å"3 2 1Å"3Å"7 3 1Å"3Å"7 Å"11
4
H" 1+ - + - + .... ;
(1+x) x |x| d" 1;
x x x
4 4Å"8 4Å"8Å"12 4Å"8Å"12Å"16
w0=1
ALG9_Suma (x, µ)
4 (n-1)-1
// Suma wyrazów szeregu; dane: x,µ;
(- ); n=1,2,
w = w-1
x
n n
{
4n
read(x);
f=(1+x)1/4;
s=0; n=0; w=1;
DO{
s=s+w;
n=n+1;
w:= w((4(n-1)-1)/( 4n))(-x);
} WHILE (µ<ćłwćł);
r:=ćłf-sćł;
return(s,r,n);
} // Wynik: suma:=s; błąd:= r;
// Ilość sumowanych wyrazów:n;
ASD LJ S
Algorytmy przybliżone
Przybliżone algorytmy iteracyjne polegają na konstruowaniu ciągu
przybliżonych rozwiązań {xk}, k=1,2,3,..., który jest zbieżny przy pewnych
założeniach do rozwiązania dokładnego x*:
x1, x2, ...xk, xk+1....... x*
1. Czy proces iteracyjny jest zbieżny do rozwiązania dokładnego ?.
2. Jak ocenić szybkość zbieżności ?.
3. Jaki błąd popełniamy przyjmując w procesie przybliżania?.
ASD LJ S
14
Metoda stycznych (Newtona)
Poszukiwanie miejsca zerowego funkcji:
f(x) = 0
f(x)
Zakłożenia:
1. pierwiastek równania leży w przedziale [a, b]
2. f  (x) i f   (x) są ciągłe
3. f  (x) jest stałego znaku w [a, b]
f(xk)
dla k=0,1,2,
xk+1 = xk -
x*
x
f `(xk)
a
x2 x1 b
x0
gdzie: xk jest k-tym przybliżeniem pierwiastka.
Zbieżności metody:
lim xk = x*
k "
xk+1= xk - f(xk) / f  (xk) dla i " ¾ = ¾ - f(¾) / f (¾),
¾ - ¾ = - f(¾) / f (¾) Ò! f(¾) = 0, x* = ¾ jest pierwiastkiem równania.
ASD LJ S
Algorytm Newtona
Pseudokod
Pseudokod
ALG_Newton_v1(µ, x0, n)
ALG_Newton(µ, x0)
// Dane: µ,x0,n;
//Dane: µ, x0;
{
{
x=x0
x=x0;
FOR k=1,2, ...,n {
DO{
y=x;
y=x;
x=x-f(x)/f (x);
x=x-f(x)/f (x);
IF ćł((x-y)/y)ćł <µ
} WHILE ćł((x-y)/y)ćł> µ);
STOP;
return (x);
}
}
return(x);
}
ASD LJ S
15