<<str. główna ALGORYTMY I STRUKTURY DANYCH
| ITERACJA | REKURENCJA |
SORTOWANIE |
|
Algorytm to precyzyjny opis sposobu rozwiązania określonego zadania lub osiągnięcia jakiegoś celu. Pierwsze algorytmy w szkole pojawiają się na lekcjach matematyki jako opisy wykonania działań na dowolnych liczbach, np. algorytm pisemnego dodawania dwóch dowolnych liczb lub algorytm pisemnego mnożenia dwóch dowolnych liczb.
Wykonawcą algorytmu może być człowiek lub komputer. Algorytm jest podstawowym pojęciem informatyki. Każdy program komputerowy jest zapisem jakiegoś algorytmu.
Algorytm jest tworzony na podstawie specyfikacji problemu, który ma rozwiązywać. Dane i wyniki ze specyfikacji są jednocześnie danymi wejściowymi i danymi wyjściowymi (czyli wynikami działania) algorytmu. Od algorytmu wymaga się, aby wszystkie jego elementy (dane, polecenia, wyniki) były dobrze określone, a sam algorytm był uniwersalny, czyli działał poprawnie dla danych spełniających specyfikację.
Algorytm może być zapisany słownie w postaci listy kroków lub w jednym z języków programowania - wtedy jest zrozumiały dla komputera. Może być również przedstawiony w postaci graficznej, jako schemat blokowy lub drzewo algorytmu.
Oceną szybkości działania algorytmu jest jego złożoność, czyli liczba wykonywanych operacji. W praktyce często zadowalamy się oceną efektywności działania algorytmu, czyli jak szybko działa algorytm dla konkretnych danych. Mimo, że komputery są coraz szybsze, istnieją problemy, których nadal nie można rozwiązać ze względu na bardzo dużą złożoność opracowanych dla nich algorytmów.
Słowo "algorytm" pochodzi od brzmienia fragmentu nazwiska arabskiego matematyka, Muhammada ibn Musa al-Chorezmiego, żyjącego na przełomie VIII i IX wieku. Uważany jest on za prekursora obliczeniowych metod w matematyce. Za najwcześniejszy algorytm uznawany jest algorytm Euklidesa.
Algorytm to podstawa programu - trzeba pamiętać o:
- opisie problemu (celu do osiągnięcia, danych początkowych-wejściowych, oczekiwanm wyniku i jego postaci)
- metodzie rozwiązania (wejście-algorytm-wyjście),
- sprawdzeniu poprawności rozwiązania.
Sposoby zapisu algorytmów:
- słownie - lista kroków,
- graficznie - z użyciem symbolicznych elementów będących odpowiednikiem czynności
- w pseudojęzyku programowania lub konkretnym języku np C, VB lub TP
Dane a informacje
dane - szereg faktów i zjawisk (nie mają jednoznacznie określonego znaczenia),
informacje - przetworzone dane (mają konkretne znaczenie),
dane dla jednego, mogą być informacją dla drugiego,
dane -> przetwarzanie (algorytm) -> informacje
Cechy algorytmów:
- poprawność (algorytm daje dobre wyniki),
- jednoznaczność (daje takie same wyniki przy takich samych danych),
- skończoność (wykonuje się w skończonej ilości kroków),
- sprawność (czasowa - szybkość działania i pamięciowa - "zasobożerność")
Techniki algorytmiczne (budowanie algorytmów):
- wybór,
- powtarzanie - iteracja,
- rekurencja,
- przeszukiwanie (liniowe i binarne-połowienie),
- przeszukiwanie z nawrotami (wyczerpujące),
- "dziel i zwyciężaj" - funkcje i procedury rekurencyjne
- metoda zachłanna (otrzymanie jak najszybciej jak najlepszego wyniku).
Zmienna - reprezentowana przez nazwę i wartość
nazewnictwo (sposób zapisu, sposób pamiętania, sensowność nazwy, stosowane konwencje),
wartość i powiązanie jej z pamięcią - typ zmiennej czyli zbiór wartości jakie może przyjąć zmienna (tekst / całkowite - dokładność / rzeczywiste - przybliżone),
działanie instrukcji przypisania.
Kolejność działań w obliczeniach:
- znak minus przy liczbie,
- działania w nawiasach,
- potęgowanie,
- mnożenie/dzielenie, modulo,
- dodawanie i odejmowanie,
- relacje =, <, >, <=, >=.