AlgorytmyTeoria

[ Pobierz całość w formacie PDF ]
Algorytmy. Teoria.
Maciej Rzymski 17.01.2011r.
Pochodzenie słowa algorytm.
●
Słowo algorytm pochodzi od
łacińskiego brzmienia
łacińskiego brzmienia
nazwiska: Muhammad ibn
nazwiska: Muhammad ibn
Musa al-Chuwarizmi
Musa al-Chuwarizmi
(Algorismi)
(Algorismi)
.
.
●
Muhammad ibn Musa al-
Chuwarizmi to słynny perski
Chuwarizmi to słynny perski
matematyk, astronom i
matematyk, astronom i
geograf żyjący w
geograf żyjący w
IX
IX
w.
w.
●
Rozpowszechnił pochodzący
z Indii dziesiętny system
z Indii dziesiętny system
liczenia. Jego prace
liczenia. Jego prace
pozwoliły wyjaśnić pojęcie
pozwoliły wyjaśnić pojęcie
zera. Wprowadził elementy
zera. Wprowadził elementy
algebry.
algebry.
Słowo algorytm pochodzi od
Muhammad ibn Musa al-
Rozpowszechnił pochodzący
Definicja algorytmu.
●
algorytm
– pewna ściśle określona procedura obliczeniowa,
– pewna ściśle określona procedura obliczeniowa,
która dla
właściwych
właściwych
danych wejściowych
danych wejściowych
zwraca żądane
zwraca żądane
dane wyjściowe
zwane
zwane
wynikiem
wynikiem
działania algorytmu.
działania algorytmu.
●
Algorytm możemy traktować jako środek umożliwiający
rozwiązanie konkretnego
rozwiązanie konkretnego
problemu obliczeniowego.
problemu obliczeniowego.
●
Postawienie problemu polega na sprecyzowaniu wymagań
dotyczących relacji między danymi wejściowymi a wyjściowymi,
dotyczących relacji między danymi wejściowymi a wyjściowymi,
algorytm zaś opisuje właściwą procedurę obliczeniową, która
algorytm zaś opisuje właściwą procedurę obliczeniową, która
zapewnia że ta relacja zostanie osiągnięta.
zapewnia że ta relacja zostanie osiągnięta.
●
Każdy algorytm mozna przestawić w języku naturalnym, w
postaci programu komputerowego bądź listy kroków lub
postaci programu komputerowego bądź listy kroków lub
zrealizować sprzętowo. Jedynym wymaganiem jest precyzja
zrealizować sprzętowo. Jedynym wymaganiem jest precyzja
opisu wynikającej z procedury obliczeniowej algorytmu.
opisu wynikającej z procedury obliczeniowej algorytmu.
algorytm
która dla
dane wyjściowe
Algorytm możemy traktować jako środek umożliwiający
Postawienie problemu polega na sprecyzowaniu wymagań
Każdy algorytm mozna przestawić w języku naturalnym, w
Kilka przykładów problemów.
●
Znajdowanie Największego Wspólnego Dzielnika. Jest to
najstarszy znany algorytm opracowany ponad 2000 lat temu
najstarszy znany algorytm opracowany ponad 2000 lat temu
przez Euklidesa.
przez Euklidesa.
●
Poznanie ludzkiego genomu, czyli zidentyfikowanie wszystkich
100 000 genów ludzkiego DNA, określenie sekwencji 3
100 000 genów ludzkiego DNA, określenie sekwencji 3
miliardów par nukleotydów składających się na ludzkie DNA,
miliardów par nukleotydów składających się na ludzkie DNA,
zapisanie tej informacji w bazie danych.
zapisanie tej informacji w bazie danych.
●
Efektywne zarządzanie przepływem pakietów sieci Internet.
●
Wytyczanie najkrótszej trasy między określonymi punktami na
mapie - nawigacja samochodowa.
mapie - nawigacja samochodowa.
●
Znajdowanie największych liczb pierwszych.
●
Problem komiwojażera (TSP)
Znajdowanie Największego Wspólnego Dzielnika. Jest to
Poznanie ludzkiego genomu, czyli zidentyfikowanie wszystkich
Wytyczanie najkrótszej trasy między określonymi punktami na
Klasyfikacja algorytmów.
●
proste – rozgałęzione
- nie występują albo występują
rozgałęzienia,
●
cykliczne – mieszane
- z powrotami albo bez powrotów,
●
sekwencyjne - równoległe
- kroki algorytmu wykonywane
kolejno w sekwencji albo równolegle,
●
numeryczne
–
nienumeryczne -
wykonywanie obliczeń albo
przetwarzanie danych,
●
rekurencyjne - iteracyjne
- algorytm w kolejnych krokach
wywołuje sam siebie dla nowych wartości parametrów
wykonania lub wykonuje obliczenia w pętli dla zmieniającej się
wartości jej
niezmiennika
,
●
zachłanne
- wykonują działanie, które wydaje się najlepsze w
danej chwili, nie uwzględniając przyszłych kroków,
[ Pobierz całość w formacie PDF ]