Algorytmika - pojęcia podstawowe

algorytmika (ang. algorithmics)
Dział informatyki zajmujący się poszukiwaniem, konstruowaniem i badaniem własności algorytmów, w kontekście ich przydatności do rozwiązywania problemów za pomocą komputerów. Nazwa ta została wprowadzona przez izraelskiego informatyka Davida Harela w tytule jego książki o algorytmach Algorithmics. The Spirit of Computing (Algorytmika. Rzecz o istocie informatyki, Warszawa 1992, WNT). Książka ta jest zapisem pogadanek autora o algorytmice i informatyce, wygłaszanych w radiu izraelskim.

algorytm (ang. algorithm)
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. 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. 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.

Drzewo algorytmu (ang. algorithm tree)
Graficzna reprezentacja algorytmu przyjmująca postać drzewa. W takiej reprezentacji, wierzchołki pośrednie drzewa zawierają wykonywane w algorytmie operacje, a w wierzchołkach końcowych znajdują się wszystkie możliwe wyniki wykonania algorytmu.

Drzewo binarne
Drzewo binarne (angielskie binary tree), struktura danych określona na skończonym zbiorze węzłów, którą można opisać rekurencyjnie w sposób następujący:
1) nie zawiera żadnych węzłów (drzewo puste);
2) składa się z trzech rozłącznych zbiorów węzłów: korzenia, lewego poddrzewa drzewa binarnego i prawego poddrzewa drzewa binarnego. Węzeł drzewa binarnego (każdy lub większość) zawiera wskaźnik do ojca (węzła nadrzędnego) oraz do prawego i lewego syna (węzłów podrzędnych), czyli co najwyżej dwa następniki. Pełne drzewo binarne ma w każdym wierzchołku 0 lub 2 następniki

Iteracja, pętla (ang. iteration)
Instrukcja powtarzania pewnego zbioru lub ciągu operacji. Liczba powtórzeń może być ustalona przed wykonaniem instrukcji lub może zależeć od spełnienia pewnego warunku, który jest sprawdzany w każdej iteracji.

Rekurencja
Sposób wykonywania obliczeń, w którym wydzielony podprogram wywołuje siebie samego. Rekurencję można również zastosować do opisu czynności, które nie są obliczeniami. Klasyczny jest już opis jedzenia kaszki podany przez informatyka rosyjskiego Andrieja P. Jerszowa: Jedz kaszkę znaczy weź łyżkę kaszki i jedz kaszkę (dalej). Podobnie można określić, co to znaczy tańczyć: Tańcz to zrób jeden krok i tańcz (dalej).
Rekurencyjny opis obliczeń jest na ogół bardziej zwarty niż opis tych samych obliczeń bez użycia rekurencji. Taki opis jest stosowany np. przy opisie fraktali, które są nawet definiowane jako twory podobne do swoich części.

Schemat blokowy
Graficzna reprezentacja algorytmu, stosowana początkowo w procesie (w trakcie) zamiany algorytmu na jego realizację w postaci programu komputerowego. Schemat blokowy składa się ze skrzynek i połączeń między nimi, które wyznaczają kolejność wykonywania działań umieszczonych w skrzynkach. W sformalizowanej postaci schematu, skrzynki mają kształt zależny od funkcji. Z czasem, w związku z rozwojem algorytmicznych języków programowania, popularność schematów blokowych spadła. Od czasu pojawienia się graficznego interfejsu użytkownika, który umożliwia posługiwanie się wieloma oknami na ekranie, schematy blokowe przeżywają renesans. Zrealizowane w specjalnym programie mogą być wykorzystane do komputerowego zapisywania algorytmów bez znajomości metod programowania oraz do wykonywania komputerowych eksperymentów z algorytmami zapisanymi w postaci schematów.

Program, program komputerowy (ang. computer program)
Zestaw poleceń przeznaczonych do wykonania przez komputer, powodujących jego działanie zgodnie z zamierzeniem użytkownika. Program może być zapisany w jednym z języków programowania, ale przed wykonaniem go przez komputer musi zostać przetłumaczony na kod maszynowy, czyli ciąg rozkazów dla procesora. Można wyróżnić programy: systemowe (niezbędne do poprawnego działania systemu komputerowego), narzędziowe (np. programy antywirusowe), użytkowe (służące użytkownikowi do wykonywania konkretnych zadań, np. rysowania, pisania), edukacyjne. Jest jeszcze wiele innych kategorii oprogramowania, np. gry komputerowe, języki programowania itd.

Wyszukiwanie binarne
wyszukiwanie binarne, przeszukiwanie binarne (ang. binary search), wyszukiwanie metodą połowienia, przeszukiwanie metodą połowienia, metoda połowienia (ang. binary search). Metoda (algorytm) przeszukiwania zbioru uporządkowanego w celu znalezienia wybranego elementu, np. hasła w słowniku. W każdym jej kroku, pozostały do przeszukania zbiór jest dzielony na dwie części, (na ogół na połowy), z których jedna zawiera poszukiwany element, a druga go nie zawiera. W tym celu środkowy element zbioru jest porównywany z poszukiwanym elementem i do dalszych poszukiwań jest pozostawiana ta część, w której może się on znajdować. Dzięki temu w jednym kroku tej metody przeszukiwany zbiór ulega zmniejszeniu o połowę i bardzo szybko trafiamy na poszukiwany element lub stwierdzamy, że nie ma go w tym zbiorze. Na przykład w taki sposób poszukujemy na ogół hasła w słowniku, numeru telefonu w książce telefonicznej, czy danych o książce w katalogu. Jeśli słownik ma 1000 stron, to stosując tę metodę każde zawarte w nim hasło można znaleźć po przejrzeniu co najwyżej 10 stronic. Ta metoda jest szczególnym przypadkiem metody dziel-i-zwyciężaj.

Złożoność algorytmu (ang. algorithm complexity)
Liczba elementarnych operacji, np. porównań, dodawań, mnożeń, przestawień elementów, wykonywanych przez algorytm, podawana na ogół w zależności od długości (ilości) danych. Na przykład liczba porównań potrzebnych do znalezienia najmniejszego (lub największego) elementu w nieuporządkowanym zbiorze jest o jeden mniejsza od liczby elementów w zbiorze. A w algorytmie porządkowania przez wybór jest wykonywanych n(n-1)/2 porównań i n-1 przestawień elementów, gdy porządkowany jest zbiór złożony z n elementów. Rzeczywisty czas działania algorytmu może być podany dopiero dla jego konkretnej realizacji, przeznaczonej dla konkretnego komputera. Inną miarą jakości algorytmu jest jego efektywność określana na podstawie testowania szybkości jego działania na przykładowych danych. Złożoność i efektywność można również zdefiniować do programów.

Algorytm Newtona-Raphsona (ang. Newton-Raphson algorithm)
Algorytm służący do obliczania wartości pierwiastka kwadratowego metodą iteracyjną. Dla danej liczby podpierwiastkowej a, obliczenia wartości sqrt(a) rozpoczynają się od wartości początkowej x0, która jest przybliżeniem rozwiązania, za którą można przyjąć na przykład (1+a)/2. Następne przybliżenia są wyznaczane ze wzoru: xi+1 = (xi+a/xi)/2. Obliczenia kończą się, gdy dwa kolejne przybliżenia niewiele różnią się między sobą, czyli gdy różnica |xi - xi+1| jest małą liczbą, na przykład 0.000001.

Algorytm aproksymacyjny (ang. approximation algorithm), algorytm przybliżony
Algorytm umożliwiający otrzymanie przybliżonego rozwiązania, czyli takiego rozwiązania, które nie jest najlepsze (tj. optymalne), ale różni się od niego niewiele w sensie przyjętej miary dokładności. Algorytmy przybliżone są stosowane wtedy, gdy nie potrafimy znaleźć rozwiązania optymalnego i musimy się zadowolić rozwiązaniem przybliżonym. Ponadto algorytmy komputerowe działające na liczbach reprezentowanych w komputerze w sposób przybliżony dają również rozwiązania tylko przybliżone z pewną dokładnością. Algorytm Newtona-Raphsona, służący do obliczania wartości pierwiastka kwadratowego, jest przykładem algorytmu przybliżonego.

Aproksymacja
Aproksymacja, przybliżenie wielkości dokładnej przez inną, bliską jej w pewnym określonym sensie. Mówi się o aproksymacji krzywej przez łamaną, liczby niewymiernej przez wymierną, dowolnej funkcji ciągłej przez wielomian.

Agorytm z nawrotami (ang. backtracking algorithm), przeszukiwanie z nawrotami
Algorytm polegający na poszukiwaniu rozwiązania wśród wszystkich możliwych rozwiązań w sposób, który gwarantuje, że nie zostanie ono przeoczone, jeśli tylko istnieje. Przykładem takiego algorytmu może być sposób poszukiwania wyjścia z labiryntu. Przyjmuje się w tym przypadku, że przejście z danego punktu do następnego punktu wykonujemy w ustalonym porządku możliwych punktów do przejścia (np. od lewej do prawej) i gdy nie ma już żadnej możliwości pójścia dalej, wówczas cofamy się (tj. robimy nawrót) do punktu, z którego przyszliśmy. Tak poruszał się po labiryncie mityczny Tezeusz w poszukiwaniu potwora Minotaura, a w nawrotach pomagała mu nić ofiarowana mu przed wejściem do labiryntu przez Ariadnę.

Agorytm zachłanny (ang. greedy algorithm)
Algorytm, w którym na każdym kroku podejmowana jest możliwie najlepsza decyzja. Jeśli chcemy osiągnąć jak najwięcej, to w myśl strategii zachłannej na każdym kroku bierzemy najwięcej, jak to tylko możliwe. Z kolei, by wziąć możliwie najmniej czegoś, na każdym kroku powinniśmy brać jak najmniej. Przykładem strategii zachłannej jest metoda wydawania reszty w postaci najmniejszej liczby banknotów i monet. W myśl tej strategii sprzedawca powinien wydawać resztę od największych banknotów, próbując wydać możliwie najwięcej banknotów jeszcze mieszczących się w reszcie. Na przykład resztę w wysokości 9 złotych i 93 groszy powinniśmy otrzymać w postaci sumy monet: 5+2+2 złotych oraz 50+20+20+2+1 groszy.

Ta strategia jest zachłanna dla obu stron: klient otrzymuje resztę w postaci najmniejszej liczby banknotów, a sprzedawca ma mniej kłopotu z wydawaniem (dzięki czemu również ma mniej okazji, by pomylić się w wydawaniu).

Etapy rozwiązywania problemów:
Sformułowanie zadania.
Określenie danych wejściowych.
Określenie celu, czyli wyniku.
Poszukiwanie metody rozwiązania, czyli algorytmu w postaci:
Przedstawienie algorytmu w postaci:
- opisu słownego
- listy kroków
- schemat blokowego
- jednego z języków programowania
Analiza poprawności rozwiązania.
Testowanie rozwiązania dla różnych danych - ocena efektywności przyjętej metody.