Algorytmy, Schematy blokowe

Algorytm w matematyce oraz informatyce to skończony uporządkowany zupełnie zbiór jasno zdefiniowanych czynności koniecznych do wykonania pewnego zadania w skończonej liczbie kroków. Ma on przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego. Algorytm może zostać zaimplementowany w postaci programu komputerowego lub układu elektronicznego. Kiedy podczas tego procesu programiści popełnią błąd (ang. bug), może to doprowadzić do poważnych skutków. Dla przykładu błędy w implementacji algorytmów bezpieczeństwa mogą ułatwić włamanie do systemu komputerowego.

Algorytm często porównuje się do przepisu kulinarnego. Dla przykładu, aby zrobić bigos należy w określonej kolejności oraz odstępach czasowych (imperatyw czasowy) dodawać właściwe rodzaje kapusty i innych składników. Może istnieć kilka różnych przepisów dających na końcu bardzo podobną potrawę.

Główna różnica między algorytmem kulinarnym i komputerowym tkwi w zdolności jego wykonawcy do zrozumienia języka przepisu. Kucharz jest dużo bardziej inteligentny od komputera. Wiele algorytmów jasnych dla człowieka, staje się niezrozumiałych dla maszyny.

W niektórych krajach, jak USA, algorytmy mogą zostać opatentowane, jeżeli dają się zaimplementować w jakimś praktycznym celu. Niektórzy twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki, bo jeden producent może uzyskać monopol, np. na pisanie oprogramowania tworzącego pewne typy plików (np. GIF). Wiele koncernów komputerowych prowadzi między sobą prawnicze spory dotyczące własności do niektórych patentów.

Historia algorytmów

Początki

Słowo algorytm pochodzi od nazwiska arabskiego matematyka z IX wieku Muhammeda ibn Musa Alchwarizmiego. Początkowo słowem algorism nazywano czynności konieczne do wykonywania obliczeń z użyciem dziesiętnego systemu liczbowego.

Obecne znaczenie słowa algorytm jako zestawu ścisłych reguł powstało wraz z rozwojem matematyki i techniki. Wynalezienie zbiorów zasad pozwalających na obliczanie parametrów konstruowanych maszyn, stało się podstawą rewolucji przemysłowej zapoczątkowanej w końcu XVIII stulecia. Jednak dopiero zbudowanie maszyn, które same mogły realizować pewne proste algorytmy, stało się przełomem. Początkowo miały one postać układów mechanicznych mogących dokonywać prostych obliczeń. Ogromnego postępu dokonał w tej dziedzinie w 1842 roku Charles Babbage, który na podstawie swoich doświadczeń sformułował ideę maszyny analitycznej zdolnej do realizacji złożonych algorytmów matematycznych.

Rozwój maszyn liczących

Wraz z wynalezieniem pod koniec XIX wieku kart perforowanych elektro-mechaniczne maszyny osiągnęły zdolność realizacji algorytmów przetwarzających ogromne zbiory danych. Karty perforowane stały się wejściem, z którego dane przetwarzały proste algorytmy sumujące. Jako wyjście służyły odpowiednie zegary. Ogromny postęp w tej dziedzinie zawdzięczamy firmie IBM, która zbudowała tego typu urządzenia, aby policzyć wszystkich mieszkańców USA.

W XX wieku postęp elektroniki pozwolił na budowę maszyn analogowych potrafiących w swoim wnętrzu odtwarzać pewne algorytmy matematyczne. Mogły one dokonywać operacji arytmetycznych oraz różniczkować i całkować.

Komputery

Kluczowym stał się moment, w którym badacze zdali sobie sprawę, że maszyny najlepiej radzą sobie z szybkim powtarzaniem bardzo prostych operacji. Algorytm wyrażony w najprostszym z możliwych języków okazał się dla urządzeń najlepszy. Prowadzone podczas II wojny światowej prace kryptologów doprowadziły do zbudowania maszyn łamiących szyfry. Największe zasługi miał tutaj Alan Turing. Badacz ten podczas prac nad algorytmami szyfrującymi, zdał sobie sprawę, że każdy z nich da się sprowadzić do zestawu instrukcji realizowanych przez pewną teoretyczną maszynę. Miała ona zdolność do czytania i pisania poleceń z nieskończonej taśmy. Jej rozkazy mogły zawierać polecenia przesunięcia się o ileś kroków głowicy, zapisu/odczytu w jakimś miejscu taśmy nowej instrukcji.

Podług tej idei zbudowano pierwsze komputery. Posługiwały się algebrą Boole'a oraz binarnym systemem liczbowym. Kolejne rozkazy były odczytywane z kart perforowanych, a wyniki pojawiały się na świetlnych ekranach bądź w wydrukach. Okazało się, że tak proste maszyny były w stanie realizować bardzo złożone algorytmy matematyczne, jak np. obliczanie trajektorii pocisków czy rakiet.

Dzisiaj komputery są powszechne oraz tanie i przez to implementacja w nich właściwych algorytmów stała się bardzo ważną gałęzią gospodarki. Na całym świecie pracują miliony programistów zajmujących się doskonaleniem oprogramowania. Odpowiednie algorytmy noszące nazwę protokołów komunikacyjnych sterują ruchem informacji w globalnej sieci Internetowej. Wyszukiwanie w implementacjach błędów jest zajęciem niedającym się łatwo zautomatyzować i żmudnej pracy całych zespołów hackerów i programistów

Algorytmy komputerowe

Implementacja

Komputery przetwarzają przekazywane im informacje z wykorzystaniem pewnych algorytmów. Program jest algorytmem zapisanym w języku zrozumiałym dla maszyny (asemblerze). Każdy kod maszynowy da się przełożyć na zestaw instrukcji dla maszyny Turinga.

Zwykle algorytmy pracują na pewnych danych wejściowych i uzyskują z nich dane wyjściowe. Informacje zapisane w pamięci maszyny traktuje się jako jej stan wewnętrzny. Niektóre algorytmy mają za zadanie wyłącznie przeprowadzanie komputera z jednego stanu wewnętrznego do innego.

Każdy algorytm komputerowy musi być wyrażony w bardzo rygorystycznie zdefiniowanym języku. Ludzie często komunikując się przesyłają między sobą informację wieloznaczne. Komputery mogą reagować tylko na całkowicie jednoznaczne instrukcje. Jeżeli dany algorytm da się wykonać na maszynie o dostępnej mocy obliczeniowej i pamięci oraz akceptowalnym czasie, to mówi się, że jest obliczalny.

Poprawne działanie większości algorytmów implementowanych w komputerach opiera się na kolejnej realizacji pewnego zestawu warunków. Jeżeli, któryś z nich nie zostanie spełniony, to program kończy się komunikatem błędu. Czasami podczas implementacji algorytmu ważny warunek zostanie pominięty Dla przykładu, mamy program dzielący przez siebie dwie liczby. Użytkownik każe mu dzielić przez zero. Aplikacja bez sprawdzenia warunku “dzielnik nierówny zero” zawiesi się w takiej sytuacji.

Klasyfikacja

Badaniem algorytmów zajmuje się algorytmika

Istnieje wiele różnych sposobów podziału algorytmów na grupy. Problem ten wzbudza kontrowersje.

Podstawowe paradygmaty tworzenia algorytmów komputerowych:

• dziel i zdobywaj - dzielimy problem na kilka mniejszych i je znowu dzielimy, aż ich rozwiązania nie staną się oczywiste (rekurencja),

• programowanie dynamiczne - problem dzielony jest na kilka, ważność każdego z nich jest oceniana i po pewnym wnioskowaniu wyniki analizy niektórych prostszych zagadnień wykorzystuje się do rozwiązania głównego problemu,

• metoda zachłanna - nie analizujemy podproblemów dokładnie, tylko wybieramy najbardziej obiecującą w tym momencie drogę rozwiązania,

• programowanie liniowe - oceniamy rozwiązanie problemu przez pewną funkcję jakości i szukamy jej minimum,

• poszukiwanie i wyliczanie - kiedy przeszukujemy zbiór danych aż do odnalezienie rozwiązania,

• probabilistyczne rozwiązanie - algorytm działa poprawnie z bardzo wysokim prawdopodobieństwem, ale wynik nie jest pewny,

• heurystyka - człowiek na podstawie swojego doświadczenia tworzy algorytm, który działa w najbardziej prawdopodobnych warunkach, rozwiązanie zawsze jest przybliżone.

Najważniejsze techniki implementacji algorytmów komputerowych

• proceduralność - algorytm dzielimy na szereg podstawowych procedur, wiele algorytmów dzieli wspólne biblioteki standardowych procedur, z których są one wywoływane w razie potrzeby,

• praca po kolei - wykonywanie kolejnych procedur algorytmu, według kolejności ich wywołań, na raz pracuje tylko jedna procedura,

• praca równoległa - wiele procedur wykonywanych jest w tym samym czasie, wymieniają się one danymi,

• rekurencja - procedura wywołuje sama siebie, aż do uzyskania wyniku lub błędu,

• obiektowość - procedury i dane łączymy w pewne obiekty reprezentujące najważniejsze elementy algorytmu oraz stan wewnętrzny wykonującego je urządzenia.

Algorytmy poza komputerami

Implementacja algorytmu w ogólności oznacza występowanie pewnego podobieństwa pomiędzy algorytmem opisanym w ludzkim języku do fizycznego zjawiska lub procesu. Czasami algorytm może być podstawą budowy przez ludzi urządzenia, jak np. komputer. Jednak o implementacji możemy mówić również, kiedy pewien system zachowuje się podobnie do algorytmu. Dla przykładu mózg ptaka implementuje arytmetykę w postaci sieci neuronowej. Dzięki temu zwierzę jest w stanie porównywać pewne odstępy czasu. W przypadku maszyn algorytm może zostać zaimplementowany jako pewna sieć połączeń elektrycznych, pneumatycznych bądź mechanicznych. Przykładem może być tutaj analogowy regulator obrotów z pierwszych silników parowych, realizujący algorytm P (proporcjonalny). Przy takim podejściu sukces nie oznacza zatrzymanie algorytmu, lecz utrzymywanie pewnego stanu systemu. Możemy np. powiedzieć, że algorytm utrzymywania życia działa poprawnie, aż do śmierci organizmu. Poprawny algorytm ma utrzymywać pewne parametry żywej istoty (np. temperaturę) w optymalnym zakresie.

Przyszłość algorytmów

Ograniczenia algorytmów

Prawie każdy algorytm komputerowy musi kiedyś zakończyć swoją pracę. Oznacza to, że problem musi być rozwiązany z wykorzystaniem dostępnych zasobów obliczeniowych w skończonym czasie. Jeżeli algorytm dla coraz większego zbioru danych powoduje wzrost czasu obliczeń szybciej niż to wynikałoby z funkcji wielomianowej, to mówi się, że nie jest praktycznie obliczalny. Gdy kryterium braku obliczalności jest spełnione dla implementacji algorytmu na maszynę Turinga, to wtedy określa się go jako problem N-P zupełny.

Algorytmy sztucznej inteligencji

Większość problemów związanych z codziennym życiem to problemy N-P zupełne. Przykłady to odnajdywanie najkrótszej drogi, składanie układanki, czy odnajdywanie błędów w programach. Oznacza to, że algorytmy mogą radzić sobie w takimi problemami tylko w przybliżeniu lub bardzo szczególnej sytuacji. Sterowany algorytmem przybliżonym robot nie potrafi odnaleźć najkrótszej drogi w bardzo złożonym środowisku, mimo że dla człowieka może być ona oczywista.

Inżynierowie próbują rozwiązywać problemy N-P zupełne przez naśladowanie żywych organizmów. Jeżeli nie da się sformułować jasnego algorytmu rozwiązującego dany problem, można maszynę wyposażyć w zdolność do samodzielnego uczenia się. Zagadnieniem tym zajmuje się dział określany jako sztuczna inteligencja. Tego podejścia nie należy mylić z ludzką inteligencją. Maszyny naśladują tylko pewne cechy istot żywych, ale jak na razie nie są w stanie im dorównać na wielu polach.

Algorytmy kwantowe

Jednym z problemów N-P zupełnych jest łamanie kodów. Istnieją pewne algorytmy szyfrowania (RSA, DES), dla których szybkie znalezienie kluczy wymaga bardzo dużej mocy obliczeniowej. Tutaj rozwiązaniem mogą okazać się algorytmy zaimplementowane w komputerach kwantowych. W odróżnieniu od komputerów elektronicznych opartych na bitach, te kwantowe mają posługiwać się qubitami oraz zjawiskiem splątania. Pewne własności tych maszyn powodują, że niektóre problemy N-P zupełne dają się rozwiązać w jednym takcie obliczeń. Gdyby komuś udało się zbudować komputer kwantowy byłby w stanie złamać wszystkie dzisiaj używane algorytmy kryptograficzne. Dużym problemem komputerów kwantowych jest dekoherencja ich stanów. W ten sposób bardzo łatwo może dość do utraty danych. Rozwiązaniem ma być tutaj wykorzystanie splątania do teleportacji stanu kwantowego na kolejne cząstki elementarne. W związku z tym wielu naukowców pracuje już dziś nad implementacją algorytmów kryptografii kwantowej. Przykładem jest tutaj szyfrowanie danych z wykorzystaniem splątanych fotonów. Obecnie kierunki prac nad komputerami kwantowymi:

• fotonika - komputery oparte na fotonach,

• spinotronika - komputery operujące spinem elektronów zamiast napięcia.

Algorytmy równoległe

Jednym ze sposobów rozwiązywania złożonych problemów jest zastosowanie algorytmów równoległych. Oznacza to, że program nie jest wykonywany tylko jeden raz na jednym procesorze, ale równolegle na wielu różnych maszynach. Podejście to stosuje się od lat w superkomputerach. Jednak w takiej realizacji jest ono bardzo kosztowne. Nowym pomysłem jest tutaj zastosowanie sieci zwykłych komputerów tworzących klaster. Zadanie jest rozdzielane na wiele maszyn i obliczane równolegle w tysiącach komputerów. Czasami taką potężną sieć nazywa się z j. angielskiego grid. Przykłady to program SETI@Home, gdzie dane z nasłuchu kosmosu, analizowały dziesiątki tysięcy komputerów należących do zwykłych użytkowników. Maszyny były podłączone do Internetu przez, który przesyłały wyniki pracy uruchomionych na nich aplikacji. Nowym pomysłem na implementację algorytmów równoległych jest wykorzystanie do tego DNA. W jednej kropli wody znajdują się miliony cząstek tego kwasu. Jeżeli zsyntetyzujemy je tak, aby wykonywały pewien algorytm, to w ułamku sekundy potrzebnym na reakcje chemiczne komputer oparty na DNA znajdzie rozwiązanie bardzo złożonego problemu. Przykładem są tutaj bakterie, które zaprogramowano, aby mrugały rytmicznie światłem. Dziedzina nauki zajmująca się algorytmami w połączeniu z biologią to bioinformatyka.

SCHEMAT BLOKOWY

sieć działań, czyli graficzna reprezentacja procedury lub programu sporządzana w celach poglądowych lub jako przedstawienie algorytmu do zapisania w języku programowania.

Przykład prostego algorytmu w postaci schematu blokowego na sumę trzech liczb.


Istnieje kilka podstawowych klocków schematu blokowego:

KLOCKI GRANICZNE

Używany do zakończenia algorytmu (zwykle jeden, można używać kilku - algorytm ma wtedy mniej ścieżek i jest bardziej przejrzysty)



Używany do rozpoczęcia algorytmu(tylko jeden)

KLOCKI WEJŚCIA I WYJŚCIA

Służy do wprowadzania danych(wartości) z zewnątrz



Służy do wyprowadzania danych

KLOCEK WYKONAWCZY

W tym klocku można umieszczać jedną lub kilka instrukcji. Korzysta się z instrukcji przypisania(:=) i operatorów arytmetycznych(+; -; *; /; ^)

KLOCEK WARUNKOWY

Klocek ten ma jedno wejście i dwa wyjścia. Pytamy np. czy lewa strona jest równa prawej(a=b). Otrzymujemy odpowiedź TAK lub NIE i wychodzimy jednym z wyjść. Nie ma znaczenia, po której stronie jest znak Tak lub Nie. W klocku warunkowym umieszcza się tylko jedno wyrażenie logiczne. Wyrażenie logiczne budujemy za pomocą operatora logicznego, inaczej znaku relacji(=; <; >; <=; >=; <>)

Sposób rysowania schematów blokowych

Żeby przekazać posiadany algorytm drugiemu człowiekowi lub maszynie, musimy ten algorytm zapisać. I tu powstaje problem języka do zapisywania algorytmów. Języki naturalne, takie jak język polski, język angielski itp., nie bardzo się nadają do tego celu. Mimo to od wieków algorytmy zapisywano w językach naturalnych. Problem nie był palący, dopóki nie pojawiły się komputery. Ponieważ maszyna nie potrafi się niczego domyślić, to musi mieć jednoznacznie opisane czynności. Najlepszym obecnie “językiem” opisu algorytmów jest tzw. schemat blokowy.

Podstawową zasadą obowiązującą przy budowę schematów blokowych, jest łączenie strzałek “wychodzących” ze strzałkami “wchodzącymi”.

Schematy blokowe są zbudowane ze strzałek oraz niżej przedstawionych elementów.

Reguły rysowania schematów blokowych

I. Po zbudowaniu schematu blokowego nie powinno być takich strzałek, które z nikąd nie wychodzą, lub do nikąd nie dochodzą.

II. Każdy schemat blokowy musi mieć tylko jeden element startowy oraz co najmniej jeden element końca algorytmu.

Przykłady

• algorytm Euklidesa

• algorytmy sortowania

Algorytmy sortowania są jednymi z najbardziej znanych algorytmów. Ponieważ proces sortowania jest bardzo ważny w dzisiejszym oprogramowaniu tak więc powstało wiele algorytmów, które lepiej lub gorzej rozwiązują ten problem. Sortować można nie tylko tablice, ale także inne struktury danych, chociażby na przykład listy.

W podanych przeze mnie przykładach i algorytmach sortowane są zazwyczaj liczby. Jednakże w praktyce często należy posortować dane, które zawierają nie tylko liczby, np. posortować rekordy książki telefonicznej wg nazwisk abonentów. W tym przypadku sortowanie w takiej formie wymaga przemieszczania dużej ilości danych, a to z kolei wpływa na czas wykonania algorytmu. W takim przypadku sortuje się jedynie tablicę ze wskaźnikami do poszczególnych rekordów unikając w ten sposób sortowania całych rekordów. Mimo takich problemów problem sortowania dużych rekordów danych nie powinien sprawić większych trudności.

Cechą charakteryzującą niektórych algorytmów sortowania jest to, że działają one w miejscu. Znaczy to, że w czasie procesu sortowania tylko stała liczba elementów tablicy wejściowej jest przechowywana poza nią. Tak, więc algorytmy, które nie działają w miejscu wymagają dodatkowej pamięci.

Najważniejszym chyba parametrem, który określa algorytmy sortowania jest ich złożoność. Można udowodnić, że dolna granica złożoności algorytmów, które porównują elementy tablicy wejściowej wynosi n*lg n. Granica ta może być przekroczona przez algorytmy, które nie wykonują porównań. Takimi są na przykład: sortowanie poprzez zliczanie, pozycyjne, kubełkowe. Najbardziej uniwersalnym i w większości przypadków najszybszym jest algorytm QuickSort. Inną jego zaletą jest jego prostota i zwięzłość.

Wprowadzenie

Sortowanie bąbelkowe (bubble sort) to jeden z najprostszych sposobów sortowania elementów tablic i list. To właśnie od niego zwykle zaczyna się naukę sposobów sortowania, ponieważ algorytm ten jest łatwy do wytłumaczenia i implementacji. Doskonale nadaje się do sortowania małych ilości danych. Ponieważ jest to algorytm klasy O(n²), tak, więc stosowanie go do większej ilości danych mija się z celem. Jego nazwa wzięła się od tego, iż w tym sortowaniu liczby zachowują się jak bąbelki po kolei, jedna po drugiej idą do góry (lub w prawo, jak u mnie). Sortowanie bąbelkowe jest sortowaniem stabilnym.

Sortowanie bąbelkowe opiera się na bardzo prostej metodzie, a mianowicie po kolei porównywane są dwa sąsiednie elementy tablicy. Gdy element o mniejszym indeksie jest mniejszy od elementu o większym indeksie, (gdy sortujemy tablicę rosnąco) to zamieniane są one miejscami. Porównywane są w ten sposób wszystkie elementy tablicy. Algorytm kończy się, gdy cała tablica jest uporządkowana.

 

---