Algorytmy - podstawy

Algorytm jest to sformalizowany ciąg logicznie powiązanych instrukcji (poleceń, rozkazów), których wykonanie pozwoli na przetworzenie informacji wejściowych (danych) w informacje wyjściowe (wyniki).
Przetwarzanie informacji to zadanie problemowe, które możemy nazwać "rozwiązywaniem zadań".
Szerzej algorytmem możemy nazwać sformalizowane rozwiązywanie krok po kroku dowolnego problemu.

Na całościowe rozwiązanie problemu składają się :
• wybór metody rozwiązania problemu
• plan zastosowania tej metody do rozwiązania problemu
• opis czynności wykonywanych podczas realizacji tego planu wraz z opisem ich skutków
• ostateczny wynik wykonywanych czynności
Czynności służące do rozwiązania zadania (kroki) to :
• analiza treści zadania
• wykaz danych wejściowych; wiadomych i niewiadomych oraz relacji między nimi
• sprawdzenie czy zadanie posiada jednoznaczne rozwiązanie
• wybór metody rozwiązania zadania
• opis czynności, które należy wykonać z danymi wejściowymi przy zastosowaniu
• wybranej metody rozwiązania
• sporządzenie i przedstawienie wyników rozwiązania zadania
• Urządzenie techniczne, które może realizować algorytm nosi nazwę automatu (żelazko z termoregulatorem, lodówka, pralka automatyczna). Uniwersalnym automatem do realizacji algorytmów z zakresu przetwarzania danych jest komputer.

Składowe algorytmu to :
• nazwa algorytmu,
• opis obiektów
• deklaracja stałych i zmiennych tekstowych i liczbowych
• deklaracja funkcji użytkownika
• opis czynności jakie należy wykonać z obiektami, co realizujemy za pomocą instrukcji, które opisują nie tylko sposób działania i kolejność ich wykonywania ale również ewentualne warunki jakie muszą być spełnione w celu uzyskania prawidłowego rozwiązania
• opis wyników - zawiera sposób udostępnienia wyników rozwiązanego zadania


Przykłady algorytmów to :
• Algorytm Euklidesa
• Algorytmy sortowania
• Algorytmy kompresji
• Algorytmy sztucznej inteligencji
• Algorytmy przeszukiwania drzew: min-max i alpha-beta

Algorytmy sortowania
W życiu codziennym często spotykamy się z faktem porządkowania np., aby łatwiej było znaleźć hasło w słowniku są one uporządkowane wg określonych zasad.

Sortowanie - proces ustawienia zbioru obiektów w określonym porządku

Metody sortowania:
1. przez zamianę (sortowanie bąbelkowe)
2. przez wybieranie
3. przez wstawianie


Ad.1 Jedną z popularnych metod sortowania jest sortowanie przez prostą zamianę (sortowanie bąbelkowe). W metodzie tej porównujemy sąsiednie elementy. W celu uporządkowania elementów od najmniejszego do największego, jeśli drugi element jest mniejszy od poprzedniego, to zamieniamy go miejscami. Następnie element, który stał się drugim, porównujemy z trzecim i przestawiamy, jeśli jest mniejszy itd.
Przykład:
7 6 1 9 5 - porównujemy 7 i 6 ( przestawiamy, bo 6 < 7)
6 7 1 9 5 - porównujemy 7 i 1 ( przestawiamy, bo 1 < 7)
6 1 7 9 5 - porównujemy 7 i 9 ( nie przestawiamy, bo 10 > 7)
6 1 7 9 5 - porównujemy 9 i 5 ( przestawiamy, bo 5 < 10)
6 1 7 5 9 - 9 na właściwym miejscu
….
Aż do uzyskania odpowiedniego porządku


Ad.2 Polega na wyszukaniu najmniejszej liczby, przestawieniu jej na początek ciągu elementów (czyli zamienieniu jej z pierwszą liczbą ciągu) i takim samym postępowaniu dalszym z pominięciem pierwszego elementu.
Przykład:
7 6 1 9 5 - 1 na pierwszą pozycję, 7 w miejsce 1
1 6 7 9 5 - 5 na drugą pozycję, 6 w miejsce 5
1 5 7 9 6 - 6 na trzecią pozycję, 7 w miejsce 6
1 5 6 9 7 - 7 na czwartą pozycję, 9 w miejsce 7
1 5 6 7 9 - 9 na właściwym miejscu (piątym)

Ad.3 Sortowanie przez wstawianie
Metoda porządkowania przez wybór polega na wstawianiu elementu we właściwe miejsce, jest ona powszechnie stosowana przez osoby grające w karty.

7| 6 1 9 5
6 7| 1 9 5
1 6 7| 9 5
1 6 7 9| 5
1 6 7 5 9|

Na schemacie kreska oddziela posortowaną lewą część liczb od nieposortowanej prawej części. Jeśli pragniemy ustawić liczby w kolejności od najmniejszego do największego, to bierzemy element drugi i jeśli jest on mniejszy od pierwszego to wstawiamy przed nim. Następnie bierzemy element trzeci i wstawiamy również w odpowiednie miejsce, a więc jeśli jest mniejszy od pierwszego to przed pierwszy, jeśli mniejszy od drugiego to przed drugi.

Kompresja - ogólnie działanie mające na celu zmniejszenie wielkości czegoś (czyli zwiększenia gęstości). Np. wody (fizyka). Działaniem przeciwnym do kompresji jest dekompresja.
W informatyce chodzi o działania mające na celu zmniejszenie objętości informacyjnej danych, czyli wyrażenie zestawu danych za pomocą mniejszej ilości bitów.

Sztuczna Inteligencja (ang. [Artificial Intelligence]) (AI) to technologia i kierunek badań informatycznych, którego zadaniem jest "Konstruowanie maszyn, o których działaniu dałoby się powiedzieć, że są podobne do ludzkich przejawów inteligencji",

Istnieją dwa różne podejścia do pracy nad AI. Pierwsze, to tworzenie całościowych modeli matematycznych analizowanych problemów i implementowanie ich w formie programów komputerowych mających realizować konkretne cele. Drugie to próby tworzenia struktur i programów "samouczących się", takich jak modele [sieci neuronowych]? oraz opracowywania procedur rozwiązywania problemów poprzez "uczenie" takich programów a następnie uzyskiwanie od nich odpowiedzi na "pytania".

Algorytm min-max to najprostszy algorytm przeszukiwania drzew mający zastosowanie w komputerowych nielosowych algorytmach gry w dwie osoby, np. szachów.
Wybieramy ten ruch który po ruchu przeciwnika ma "największą najmniejszą" wartość (stąd nazwa). Czyli dla każdego ruchu symulujemy wszystkie możliwe ruchy przeciwnika i za wartość danego naszego ruchu uznajemy wartość najlepszego z punktu przeciwnika ruchu który może on wykonać jeśli my wykonamy dany ruch (część min). Potem wybieramy ruch o najwyższej wartości (część max).

Wartość sytuacji można szacować rekurencyjnie algorytmem min-max, jednak po kilku poziomach konieczne jest użycie jakiejś innej funkcji, np. przyjmującej 1 dla wygranej, 0 dla przegranej i inną wartość dla pozostałych sytuacji.

Algorytm alpha-beta to zoptymalizowana postać algorytmu min-max. Podczas przeszukiwania zachowane są dwie wartości: α - najlepszy jak na razie nasz ruch i β - najlepszy jak na razie dla przeciwnika ruch w przypadku danego naszego ruchu. Przeszukiwanie ruchów przeciwnika możemy zakończyć kiedy β spadnie poniżej α, czyli w przypadku wykonania przez nas danego ruchu przeciwnik potrafi wykonać taki ruch, że nasz wynik będzie niższy niż dla jakiegoś innego naszego ruchu.

Rodzaje zapisu algorytmów
Opis słowny - polega na logicznym i zrozumiałym dla odbiorcy przedstawieniu kolejnych czynności (akcji), jakie należy wykonać, aby osiągnąć zamierzony efekt. Przykładami takiego opisu algorytmu mogą być: przepis kulinarny,
Schemat blokowy - jest jedną z najpopularniejszych form przedstawiania algorytmu.
Rodzaje sieci działań:
Proste (sekwencyjne) - nie używa się w nich bloków warunkowych. W takiej sieci działań kolejność realizacji poszczególnych operacji jest ściśle określona i żadna z nich nie może być pominięta ani powtórzona.
Z rozwidleniem - zawiera w sobie wybór jednej z kilku możliwych dróg realizacji danego zadania. Istnieje w nim przynajmniej jeden blok warunkowy.
Z pętlą, często w trakcie realizacji danego zadania konieczne jest powtórzenie niektórych operacji różniących się jedynie zestawem danych. Pętla obejmuje tą część bloków, która ma być powtarzana.
Złożone - będące kombinacją powyższych sieci.

ZASADY BUDOWY SCHEMATU BLOKOWEGO
1) Każda operacja jest umieszczona w skrzynce
2) Schemat ma tylko jedną skrzynkę "początek" i przynajmniej jedną skrzynkę "koniec"
3) Skrzynki są ze sobą połączone.
4) Ze skrzynki wychodzi jedno połączenie; wyjątek stanowią skrzynki: "koniec" (z której nie wychodzą już żądne połączenia) oraz "warunkowa"
(z której wychodzą dwa połączenia opisane TAK i NIE - w zależności od tego, czy warunek jest spełniony czy nie, można wyjść jedną z dwóch dróg)
5) W skrzynce "operacyjnej" zamiast znaku "=" pojawia się oznaczenie ":="