Podstawowe zagadnienia

(często algorytmy) do

oprogramowania dla

Siebie

Dr Zdzisław Szczepanik

Algorytmy na przestrzeni

wieków

Przyjmij że masz skromne środki ale

Jesteś zdecydowany wybudować

Swój własny dom. Zaproponuj

algorytm zbudowania tego domu.

Za prekursora algorytmów komputerowych
uznawana jest powszechnie Ada Augusta
(1815- 1852) , hrabina Lovelace, córka lorda
Byrona. Na pamiątkę jej wizji nazwano jeden
z nowoczesnych języków programowania
wysokiego poziomu ADA.

Zagadnienie

komiwojażera

Znajdź najkrótszą trasę premiera przebiegającą przez

wszystkie polskie województwa w danym podziale

administracyjnym

Założenie : mamy superkomputer wykonujący 10

11

(100miliardów

operacji / sec )

Liczba województw

Czas znalezienia

najkrótszej trasy

17

3,6 minuty

25

2*10

5

lat

49

4*10

42

lat

Metoda obliczeń ;

n!

Najlepszą koncepcją przyspieszenia

pracy komputerów lub farm

komputerowych jest obarczanie ich

możliwie najmniejszą liczbą działań.

Szybki wniosek ?

Kiedy zdefiniowano relację,

powiedzmy na zbiorach A i B

okazało się że tkwi tam pojęcie

funkcji, które to pojęcie miało

niesamowity wpływ na rozwój

cywilizacji ludzkiej.

Trzeba w takim razie oprogramować sposoby

obliczania wartości podstawowych i nie tylko

podstawowych funkcji















0

,

0

,

x

dla

x

x

dla

x

x

























0

,

1

0

,

0

0

,

1

)

(

x

dla

x

dla

x

dla

x

f







Dla realizacji takich zadań warto gromadzić
różne :

1.

Schematy blokowe

( graficzny sposób

przedstawiania algorytmu ).

2.

Drzewa algorytmów

( szczególny schemat

blokowy przyjmujący postać drzewa, z korzeniem
u góry ).

3.

Algorytmy liniowe

( lista kroków do wykonania

zgodnie

z kolejnością w jakiej występują –brak

warunków-

schemat Hornera).

4.

Algorytmy z rozgałęzieniami

( pojawiają się

warunki – równanie liniowe, kwadratowe, 3-go
stopnia, układy

równań liniowych, etc).

5.

Algorytmy z rozgałęzieniami ale dla

( porządkowania

trzech, czterech, pięciu,wielu

liczb-struktury danych! ).

6.

Algorytmy iteracyjne

( zbiory o dowolnej

liczbie

danych,

zbiory w algorytmach,

wartownik w

zbiorze (krańce w

zbiorze),

przeszukiwanie zbiorów w

poszukiwaniu

elementu, statystyki, szukanie lidera

(więcej

niż połowa

elementów – głosy w wyborach),

sprawiedliwy tenis ).

7.

Algorytmy porządkowania zbiorów o dowolnej

liczbie

elementów

( metody bąbelkowe,

porządkowanie przez

wybór, kubełkowe,

pozycyjne słów jednakowej i

różnej długości ).

8.

Algorytmy Hornera, Euklidesa, Erastotenesa

(pozycyjne systemy liczbowe – binarne,

dziesiętne ,

szesnastkowe, szybkie obliczanie

wartości wielomianu, szukanie największego
wspólnego

dzielnika,najmniejszej wspólnej

wielokrotnej,

rozkład na czynniki pierwsze

odsiew liczb złożonych

(zostaw dwójkę i wykreśl

inne podzielne przez 2,

zostaw 3 wykreśl

podzielne przez 3 etc. 2: 2, 3, 4, 5, 6,

7,…),

metoda Banacha – iteracja poszukiwania
pierwiastka kwadratowego z liczby a

x

i+1

=1/2 * (x

i

+ a / x

i

)

9.

Algorytmy rekurencyjne

9.1.

x

i+1

= 1 / 2 * (x

i

+ a / x

i

)

iteracja

9.2

w

n

(x) = w

n-1

(x) * x + a

n

9.3

w

n

(x) =

















1

,

)

(

0

,

1

0

n

dla

a

x

x

w

n

dla

a

n

n















rekurencja



















3

......

2

,

1

......

,.........

1

2

1

k

F

F

k

F

k

k

k

Ciąg Fibonacciego

10. Algorytm znajdowania zera funkcji

metoda

połowienia
przedziału.

11.

Szybkie algorytmy zagadnień już poznanych –

tzw. szybkie algorytmy porządkowania np..
Scalanie ciągów już wcześniej uporządkowanych

Ciąg 1 : 1, 3, 5, 7, 10, 12

Ciąg 2 :

1, 2, 6, 9, 11, 15, 17, 20

Scalony : 1, 1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 15, 17,
20

Wszystko w ramach strategii dziel i
zwyciężaj !!!!!!!!!!!!!!!

Własności algorytmów.

1.

Poprawność.

2. Skończoność.
3.

Efektywność

Tak naprawdę każda z tych własności
wymaga odrębnego dla danego zagadnienia
po

prostu

dowodu.

Nie

oznacza

to

wyeliminowania intuicji , niemniej bez
metod formalnych trudno będzie się pokusić
o postęp w algorytmice, a ten w coraz
większej liczbie odkrywanych przestrzeni
zastosowań jest niesłychanie pożądany, a
jeszcze należy wspomnieć o konkurencji w
Świecie.

Dziękuje za uwagę