Algorytm przetwarzania
TL;DR
Algorytmy to skończony ciąg czynności przekształcających dane wejściowe na dane wyjściowe. Są one używane w wielu dziedzinach, w tym w sztucznej inteligencji. Przykłady popularnych algorytmów to A*, min-max, przeszukiwanie wszerz, boidy, algorytmy grafowe, GoCap, sortowanie, rekurencja, szyfrowanie, algorytmy ewolucyjne, układy arytmetyczne i algorytmy aproksymacyjne. Algorytmy można opisać jako sekwencję czynności, które każdy człowiek wykonuje na co dzień. Algorytika jest odrębną nauką, która rozwija się razem z informatyką.
Charakterystyka
Uproszczona definicja pojęcia algorytmu mówi że:
Algorytmem nazywamy pewien skończony ciąg czynności, przekształcający wprowadzone dane (dane wejściowe) na dane wyjściowe (wynik).[1] (A. Jędryczkowski, 2005, s. 2)
Rysunek 1. Schemat poglądowy budowy algorytmu
Przy konstruowaniu dowolnego algorytmu wyróżnia się poszczególne etapy: zrozumienie problemu, założenia, projektowanie kolejnych kroków, konstruowanie schematu blokowego lub/i drzewa algorytmu, programowanie, testowanie. Algorytmy są składową większych struktur zwanych sztuczną inteligencją. Przetwarzanie, a w zasadzie przekształcanie danych, może odbywać się jednokrotnie lub wielokrotnie w zależności od ilości i sposobów wywoływania funkcji algorytmicznych.
Przykłady popularnych algorytmów
Najczęściej występujące algorytmy sztucznej inteligencji:
- algorytmy wyszukiwania drogi np. A* (A Star) - heurystyczna metoda wyszukiwania najkrótszej drogi w określonym środowisku [2] (C. Płotnicki-Chudyk, 2005, s. 6). Jednym z udanych następców został algorytm B* (B Star).
Rysunek 2. Przykład działania algorytmu A-Star
- algorytm min-max - podejmowanie decyzji (teoria decyzji) w skończonych diagramach decyzyjnych. Jedna z modyfikacji Min-Max została nazwana Alpha-Beta. Drugą, co do popularności modyfikacją stał się SSS* (ang. State Space Serach) użytkujący również pewne własności z A-Star [3]
- algorytm przeszukiwania wszerz - Przeszukiwanie wszerz (ang. Breadth-First Search, w skrócie BFS) oraz przeszukiwanie w głąb (ang. Depth-First Search, w skrócie DFS) są narzędziami wspomagającymi tworzenie algorytmów szukających optymalnych rozwiązań. Bardzo dobrze spisują się w przypadku przeszukiwania grafów. Z tego względu można użyć właśnie BFS do wyszukania najlepszej możliwej drogi w labiryncie
- boidy - Distributed Behavioral Model, w skrócie Boidy, to termin wymyślony przez Craig'a Reynolds'a - autora pomysłu na modelowanie zachowań stadnych. Jest to odzwierciedlenie algorytmu stadnego z tym, że jednostki dysponują parametrami z poszerzoną wiedzą co do poruszania się, oraz reagowania w sytuacjach niepewnych
- algorytmy grafowe - stosowane w postaci grafów dla reprezentacji bardziej złożonych mechanizmów, redukujące ilość szczegółów i powodujące ogólną przejrzystość rozpatrywanego modelu
- GoCap (Game Observation Capture) - technika algorytmiczna polegająca na obserwacji przez złożony zbiór algorytmów (program) osoby fizycznej, i zapisywaniu jej działania, celem późniejszego przeanalizowania i wykorzystania np. w grach elektronicznych nowej generacji[4] (T. Aleksander, 2003, s. 47)
- algorytmy sortujące - bardzo powszechnie stosowane w wszelkiego rodzajach bazach danych, a także hurtownie danych
- algorytmy rekurencyjne - stosowane do rozwiązywania problemów sposobem rekurencyjnym, gdzie rekursja jest najszybszym sposobem prawidłowego przetwarzania algorytmu[5] (N. Wirth, 2002, s. 148)
- algorytmy szyfrujące - stosowane we współczesnych technologiach internetowych, przekazie cyfrowym, danych dyskowych
- algorytmy ewolucyjne - zaliczane do klasy algorytmów heurystycznych, przeszukują przestrzeń alternatywnych rozwiązań najlepszych lub potencjalnie najlepszych. Przeszukiwanie takie odbywa się za pomocą opracowanych mechanizmów ewolucji oraz doboru naturalnego. W szczególności zaliczają się tu algorytmy genetyczne, których zasada działania polega na najczęściej losowej inicjacji pewnej początkowej populacji osobników i poddaniu każdego z nich ocenie. Kolejno wybierane są osobniki najlepiej przystosowane i za pomocą operacji genetycznych takich jak mutacja czy krzyżowanie, tworzone są nowe pokolenia, które po ocenie stają się bazą wyjściową do następnego kroku algorytmu. Często praktykuje się je w językach programowania C++ lub innymi językami wysokiego poziomu[6] (L. Rutkowski, 2005, s. 231)
- układy arytmetyczne - występujące w niemal każdej strukturze obliczeniowej (sumatory, układy mnożące, układy kombinacyjne)
- algorytmy aproksymacyjne - rozwiązujące problemy badawcze pokrycia wierzchołkowego, problem komiwojażera, pokrycia zbioru, sumy podziału i inne[7] (T. Cormen, 2001, s. 1073)
Zgodnie z definicją, algorytm można stworzyć opierając się o prawie każdą czynność, również z dnia codziennego człowieka. Każdy człowiek bowiem wykonuje pewien algorytm wstając rano z łóżka, myjąc zęby czy ubierając się. Przyrządzanie posiłku to także algorytm, tak jak prowadzenie samochodu, jazda rowerem, czy jakakolwiek inna czynność. Dzięki takiemu postrzeganiu, algorytmika stała się odrębną nauką prawie tak rozbudowaną jak sama informatyka.[8] (D. Harel, 2000, s. 23)
| Algorytm przetwarzania — artykuły polecane |
| Algorytm ewolucyjny — Programowanie obiektowe — Replikacja — Sztuczna inteligencja — Technika skojarzeń — Typizacja — Data science — Uczenie maszynowe — Algorytm genetyczny |
Przypisy
- ↑ [1] A. Jędryczkowski, Algorytmy, Prezentacja, 2005
- ↑ [2] C. Płotnicki - Chudyk, Wyszukiwanie drogi w grach komputerowych, Prezentacja, 2005
- ↑ [3] Algorytmy rozwiązywania gier - prezentacja, Koło naukowe informatyków Fraktal
- ↑ [4] T. Aleksander, "Optymalizacja uczenia za pomocą techniki GoCap", Perełki programowania gier. Vademecum profesjonalisty. Tom 3, rozdział 3.1, Helion, Gliwice, 2003
- ↑ [5] N. Wirth, Algorytmy + struktury danych = programy, Wydawnictwa Naukowo - Techniczne, 2002
- ↑ [6] L. Rutkowski, Metody i techniki sztucznej inteligencji, Wydawnictwo Naukowe PWN, 2005
- ↑ [7]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Wprowadzenie do algorytmów, Wydawnictwa Naukowo - Techniczne Warszawa, Wydanie 4, 2001
- ↑ [8] D. Harel, Rzecz o istocie informatyki: Algorytmika, Wydawnictwa Naukowo - Techniczne Warszawa, Wydanie drugie, 2000
Bibliografia
- A. Jędryczkowski, Algorytmy, Prezentacja, 2005
- C. Płotnicki - Chudyk, Wyszukiwanie drogi w grach komputerowych, Prezentacja, 2005
- D. Harel, Rzecz o istocie informatyki: Algorytmika, Wydawnictwa Naukowo - Techniczne Warszawa, Wydanie drugie, 2000
- Rutkowski L. (2005), Metody i techniki sztucznej inteligencji, Wydawnictwo Naukowe PWN, Warszawa
- T. Aleksander, "Optymalizacja uczenia za pomocą techniki GoCap", Perełki programowania gier. Vademecum profesjonalisty. Tom 3, rozdział 3.1, Helion, Gliwice, 2003
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Wprowadzenie do algorytmów, Wydawnictwa Naukowo - Techniczne Warszawa, Wydanie 4, 2001
- Wirth N. (2002), Algorytmy + struktury danych = programy, Wydawnictwa Naukowo-Techniczne, Warszawa
Autor: Arkadiusz Wiktor
