Podstawowe zagadnienia
(często algorytmy) do
oprogramowania dla
Siebie
Dr Zdzisław Szczepanik
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ę