Algorytmy
i
struktury danych
WYKA
AD 4
Dr inż. Krzysztof Pancerz
Krzysztof Pancerz
Algorytmy i struktury danych
Programowanie proceduralne

Funkcje (procedury) umożliwiają grupowanie
często wykorzystywanego kodu w postaci
zwartych modułów, które mogą być następnie
wielokrotnie stosowane.

Funkcje (procedury) najczęściej realizują
określony algorytm lub zbiór algorytmów, który
stosuje się dla specjalnego zbioru danych.
Krzysztof Pancerz
Algorytmy i struktury danych
Programowanie proceduralne (cd.)

Funkcje (procedury) są podprogramami
będącymi blokami instrukcji, posiadającymi
unikalną nazwę i jednoznacznie określony
sposób wymiany danych z otoczeniem.

Funkcje (procedury) mogą być wywoływane z
różnych miejsc programu.
Krzysztof Pancerz
Algorytmy i struktury danych
Procedury

Zadaniem procedury jest wykonanie sekwencji
instrukcji i ewentualne obliczenie jednej lub
kilku wartości, które przypisywane są
odpowiednim argumentom wejściowym
procedury.
Krzysztof Pancerz
Algorytmy i struktury danych
Funkcje

Zadaniem funkcji jest obliczenie jednej
wartości, która następnie jest zwracana przez
funkcję.
Krzysztof Pancerz
Algorytmy i struktury danych
Definicja procedury
void nazwa (lista_argum_wej)
{
// ... treść (ciało) procedury ...
}
Krzysztof Pancerz
Algorytmy i struktury danych
Definicja funkcji
typ_zwracany nazwa (lista_argum_wej)
{
// ... treść (ciało) funkcji ...
}

W treści (ciele) funkcji musi wystąpić co najmniej
jedna instrukcja:
return wyrażenie;
powodująca zakończenie wykonywania funkcji i
zwrócenie przez nią wyniku określonego przez
wyrażenie.
Krzysztof Pancerz
Algorytmy i struktury danych
Rekurencja

Rekurencja polega na rozwiązaniu danego
problemu (o rozmiarze danych wejściowych n)
poprzez rozwiązania tego samego problemu dla
danych o mniejszych rozmiarach.
Krzysztof Pancerz
Algorytmy i struktury danych
Nierekurencyjny algorytm obliczania silni
1 if n=0
n!=
{ }
1 �"2 �"...�"n if ną1
silnia=1;
for(i=1; i<=n; i++)
{
silnia=silnia*i;
}
Krzysztof Pancerz
Algorytmy i struktury danych
Rekurencyjny algorytm obliczania silni
1 if n=0
n!=
{ }
śąn-1źą!�"n if ną0
int silnia(int n)
{
if(n==0) { return 1; }
if(n>0) { return silnia(n-1)*n; }
}
Krzysztof Pancerz
Algorytmy i struktury danych
Zależności rekurencyjne

Zależność rekurencyjna dla danego ciągu a0,
a1, ..., an jest równaniem określającym w jaki
sposób wyraz an ciągu zależy od wyrazów
poprzednich a0, a1, ..., an-1.

Warunkami początkowymi nazywana jest
skończona liczba wartości a0, a1, ..., ak, gdzie
k
Zależność rekurencyjna oraz wartości
początkowe definiują ciąg.
Krzysztof Pancerz
Algorytmy i struktury danych
Ciąg Fibonacciego

Ciąg Fibonacciego definiowany jest przez
następującą zależność rekurencyjną oraz
warunki początkowe:
1 if n=0
f =
1 if n=1
n
{ }
f �ą f if ną1
n-1 n-2
Warunki początkowe
Zależność rekurencyjna
Krzysztof Pancerz
Algorytmy i struktury danych
Rekurencyjny algorytm wyznaczania elementów
ciągu Fibonacciego
int fibonacci(int n)
{
if(n==0) { return 1; }
if(n==1) { return 1; }
if(n>1)
{ return fibonacci(n-1)+fibonacci(n-2);
}
}
Krzysztof Pancerz
Algorytmy i struktury danych
Metody projektowania algorytmów

Metoda  dziel i zwyciężaj (divide and conquer)

Programowanie dynamiczne (dynamic
programming)

Algorytmy zachłanne (greedy algorithms)
Krzysztof Pancerz
Algorytmy i struktury danych
Metoda  dziel i zwyciężaj

Przy rozwiązywaniu danego problemu problem
dzielony jest na podproblemy o mniejszych
rozmiarach.

Najpierw znajdowane są rozwiązania
podproblemów, a następnie za pomocą tych
rozwiązań konstruowane jest rozwiązanie
całego problemu.

W metodzie  dziel i zwyciężaj najczęściej
wykorzystywana jest rekurencja.
Krzysztof Pancerz
Algorytmy i struktury danych
Standardowy algorytm mnożenia macierzy

A, B  macierze o rozmiarze n�n

C  iloczyn macierzy A i B o rozmiarze n�n
A=[aij]n�n
B=[bij]n�n
C=[cij]n�n
n-1
cij= aik�"bkj
"
k =0
i=0,1 ,... , n-1
j=0,1 ,... , n-1
Krzysztof Pancerz
Algorytmy i struktury danych
Standardowy algorytm mnożenia macierzy (cd.)
for(i=0; i{ for(j=0; j { for(k=0; k {
C[i][j]=C[i][j]+A[i][k]*B[k][j];
}
}
}
Krzysztof Pancerz
Algorytmy i struktury danych
Standardowy algorytm mnożenia macierzy (cd.)

Standardowy algorytm mnożenia macierzy
wykonuje n3 mnożeń. Stąd ma on złożoność
O(n3).
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytm mnożenia macierzy wykorzystujący metodę
 dziel i zwyciężaj (algorytm Strassen'a)

A, B  macierze o rozmiarze n�n, gdzie n jest
potęgą liczby 2.

C  iloczyn macierzy A i B o rozmiarze n�n

Krok 1: Jeśli n>2, to każda z macierzy (A oraz
B) dzielona jest na cztery macierze o
rozmiarach n/2�n/2:
A11 A12 B11 B12
A= B=
[ ] [ ]
A21 A22 B21 B22
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytm mnożenia macierzy wykorzystujący metodę
 dziel i zwyciężaj (algorytm Strassen'a) - cd.

Krok 2: Obliczany jest iloczyn macierzy wg
wzoru:
A11�"B11�ąA12�"B21 A11�"B12�ąA12�"B22
A�"B=
[ ]
A21�"B11�ąA22�"B21 A21�"B12�ąA22�"B22

Każdy element Aik�Bkj jest iloczynem macierzy i
jest obliczany rekurencyjnie aż do momentu
gdy macierze Aik oraz Bkj mają rozmiar 2�2.
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytm mnożenia macierzy wykorzystujący metodę
 dziel i zwyciężaj (algorytm Strassen'a) - cd.

Algorytm Strassen'a oblicza następujące
wielkości:
Q1=śą A11�ąA22źą�"śą B11�ąB22źą
Q2=śą A21�ąA22źą�"B11
Q3=A11�"śą B12-B22źą
Q4=A22�"śą B21-B11źą
Q5=śą A11�ąA12źą�"B22
Q6=śą A21-A11źą�"śą B11�ąB12źą
Q7=śą A12-A22źą�"śą B21�ąB22źą
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytm mnożenia macierzy wykorzystujący metodę
 dziel i zwyciężaj (algorytm Strassen'a) - cd.

a następnie wyznaczany jest iloczyn macierzy
wg wzoru:
Q1�ąQ4-Q5�ąQ7 Q3�ąQ5
C=
[ ]
Q2�ąQ4 Q1�ąQ3-Q2�ąQ6
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytm mnożenia macierzy wykorzystujący metodę
 dziel i zwyciężaj (algorytm Strassen'a) - cd.

Obliczenie wielkości Q1, Q2, ..., Q7 oraz
wyznaczenie iloczynu A�B wymagają tylko
siedmiu mnożeń macierzy oraz O(n2) dodawań
i odejmowań.

Algorytm Strassen'a jest algorytmem o
złożoności O(nlog7)=O(n2.807).

Praktycznie algorytm Strassen'a stosowany jest
dla dużych macierzy (np. jeśli ne"50).
Krzysztof Pancerz
Algorytmy i struktury danych
Sortowanie przez scalanie (mergesort)

Sortowana tablica dzielona jest w przybliżeniu
na dwie równe części, a następnie każda część
jest sortowana niezależnie.

Dwie posortowane części tablicy są scalane w
jedną część posortowaną.

W najgorszym przypadku sortowanie przez
scalanie jest algorytmem o złożoności O(n logn)
Krzysztof Pancerz
Algorytmy i struktury danych
Sortowanie przez scalanie (cd.)
Krzysztof Pancerz
Algorytmy i struktury danych
Inne algorytmy wykorzystujące metodę  dziel i
zwyciężaj

Wyszukiwanie binarne

Sortowanie szybkie (quicksort)
Krzysztof Pancerz
Algorytmy i struktury danych
Programowanie dynamiczne

Programowanie dynamiczne jest techniką
projektowania algorytmów polegającą na
podziale rozwiązywanego problemu na
mniejsze podproblemy.

Obliczenia rozpoczynane są od rozwiązania
najprostszych podproblemów, z których
następnie konstruowane są rozwiązania coraz
bardziej złożonych podproblemów aż do
uzyskania rozwiązania całego problemu.

Programowanie dynamiczne jest metodą
wstępującą.
Krzysztof Pancerz
Algorytmy i struktury danych
Programowanie dynamiczne (cd.)

Programowanie dynamiczne poprawia metodę
 dziel i zwyciężaj w sytuacji, kiedy wymaga ona
wielokrotnego obliczania rozwiązań tych
samych podproblemów.
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 1: Obliczanie elementów ciągu Fibonacciego

Rekurencyjna definicja ciągu Fibonacciego ma
postać:
1 if n=0
f =
1 if n=1
n
{ }
f �ą f if ną1
n-1 n-2
Warunki początkowe
Zależność rekurencyjna
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 1: Obliczanie elementów ciągu Fibonacciego
(cd.)

Obliczenia rozpoczynają się od znanych
wartości f0 oraz f1.

Następnie obliczane są kolejno wartości f2, f3,
..., fn.

Każda obliczona wartość fi umieszczana jest w
tablicy.
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 1: Obliczanie elementów ciągu
Fibonacciego (cd.)

Wersja 1:
int fib[100];
fib[0]=1;
fib[1]=1;
// ... wczytanie n ...
for(int i=2; i<=n; i++)
{
fib[i]=fib[i-1]+fib[i-2];
}
// ... wypisanie fib[n] ...
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 1: Obliczanie elementów ciągu
Fibonacciego (cd.)

Wersja 2:
fib1=1; fib2=1;
// ... wczytanie n ...
for(int i=2; i<=n; i++)
{
fib=fib1+fib2;
fib2=fib1;
fib1=fib;
}
// ... wypisanie fib ...
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 2: Obliczanie współczynnika
dwumianowego

Współczynnik dwumianowy może być
zdefiniowany rekurencyjnie:
1 if k=0 or k=n
n
=
n-1 n-1
śą źą
�ą if 0"ąk"ąn
k
{ }
śą źą śą źą
k k-1
Warunki początkowe
Zależność rekurencyjna
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 2: Obliczanie współczynnika
dwumianowego (cd.)
Otrzymujemy trójkąt Pascala.
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 2: Obliczanie współczynnika
dwumianowego (cd.)
int[][] bin=new int[100][100];
// ... wczytanie n oraz k ...
for(int i=0; i<=n; i++)
{
for(j=0; j<=minimum(i,k); j++)
{
if(j==0 || j==i) bin[i][j]=1;
else bin[i][j]=bin[i-1][j]+bin[i-1][j-1];
}
}
// ... wypisanie bin[n][k] ...
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytmy zachłanne

Algorytmy zachłanne służą do rozwiązywania
problemów optymalizacyjnych.

Algorytm zachłanny dokonuje w każdym kroku
działania zawsze wyboru, który lokalnie (tj. w danej
chwili) jest oceniany jako najkorzystniejszy.

Dokonywane lokalnie najkorzystniejsze wybory
prowadzą do znalezienia globalnego rozwiązania
problemu.

Algorytmy zachłanne nie zawsze prowadzą do
rozwiązań optymalnych (tj. mogą dawać
rozwiązania przybliżone).
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 1: Wydawanie reszty

Problem: Należy wydać resztę A używając
najmniejszej liczby monet.

Wejście:

A  reszta do wydania,

D  tablica nominałów monet:

D[0]=1,

D[0]
n  liczba nominałów monet.

Reguła zachłanna: w każdym kroku należy
użyć największego możliwego nominału.
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 1: Wydawanie reszty (cd.)
i=1;
while(A>0)
{
c=A/D[n-i];
cout<< użyj  <D[n-1];
A=A-c*D[n-1];
i=i+1;
}
Krzysztof Pancerz
Algorytmy i struktury danych
Przykład 2: Pokrycie zbioru

Problem: Należy pokryć dany zbiór X przez
najmniejszą liczbę jego podzbiorów (wszystkie
podzbiory X są również dane).

Wejście:

X  zbiór,

- podzbiory zboru X.
X X ... , X �" X
1, 2, n

Reguła zachłanna: w każdym kroku należy
wybrać taki podzbiór, który pokrywa największą
liczbę elementów zbioru X dotychczas nie
pokrytych.
Krzysztof Pancerz
Algorytmy i struktury danych