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 zadaniaPrzykłady algorytmów to :• Algorytm Euklidesa • Algorytmy sortowania• Algorytmy kompresji• Algorytmy sztucznej inteligencji• Algorytmy przeszukiwania drzew: min-max i alpha-betaAlgorytmy 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ądkuMetody sortowania:1. przez zamianę (sortowanie bąbelkowe) 2. przez wybieranie 3. przez wstawianieAd.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ądkuAd.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ówOpis 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 ":="