Algorytmika - wprowadzenie
ALGORYTM to przedstawienie rozwiązania zadania w sposób uporządkowany, tj. z wyszczególnieniem kolejnych czynności.
Opisanie zadania, czyli szukanie związku, jaki zachodzi między danymi a wynikami, nazywamy SPECYFIKACJĄ ZADANIA
ETAPY ROZWIĄZYWANIA PROBLEMÓW
1) Sformułowanie zadania.
2) Określenie danych wejściowych.
3) Określenie celu, czyli wyniku.
4) Poszukiwanie metody rozwiązania, czyli algorytmu.
5) Przedstawienie algorytmu w postaci:
opisu słownego
listy kroków
schematu blokowego
jednego z języków programowania
6) Analiza poprawności rozwiązania.
7) Testowanie rozwiązania dla różnych danych - ocena efektywności przyjętej metody.
SPOSOBY ZAPISYWANIA ALGORYTMU.
ZAPIS ALGORYTMU W POSTACI CIĄGU KROKÓW polega na podaniu kolejnych wykonywanych operacji, składających się na całe rozwiązanie
ZAPIS ALGORYTMU W POSTACI GRAFICZNEJ - SCHEMATY BLOKOWE.
Schemat blokowy to graficzne przedstawienie ciągu kroków algorytmu, często stosowane jako ideowy rysunek poprzedzający tworzenie programu.
W schemacie blokowym poszczególne operacje przedstawiane są za pomocą odpowiednio połączonych skrzynek (klocków, bloków).
Sposób i kolejność działań programu określane są przez wzajemny układ
i sposób łączenia bloków ze sobą. Każde działanie (krok) ma w schemacie blokowym swoje standardowe oznaczenie.
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 ":="
Z SYTUACJĄ WARUNKOWĄ mamy do czynienia wówczas, gdy wynik lub dalsze działanie należy od spełnienia warunku. NA schemacie blokowym sytuacje warunkowe realizujemy przez SKRZYNKĘ WARUNKOWĄ.
ITERACJA (działanie w pętli) to technika algorytmiczna polegająca na wykonaniu tej samej instrukcji dla n zmiennych (np. liczb, wartości logicznych etc.) Iteracja oszczędza czas programisty, który ten musiałby spędzić wpisując instrukcję n razy, zależnie od liczby zmiennych. Liczba powtórzeń w iteracji jest z góry określona lub zależy od spełnienia określonego warunku.
W realizacji algorytmów iteracyjnych ważne jest prawidłowe określenie sposobu zakończenia działań. Można to zrobić za pomocą licznika, który odlicza kolejne kroki iteracji (liczbę powtórzeń).
Zapętlenie algorytmu to błąd w projektowaniu kroków algorytmu polegający na pominięciu warunku (np. licznika), który kończy działanie w pętli (iterację). Wtedy iteracja ciągnie się w nieskończoność, gdyż program wykonujący działanie nie wie kiedy ma ją przerwać.
Własne programy piszemy posługując się językami programowania, takimi jak Pascal, język C, Basic. Do programowania służą programy - specjalne edytory wchodzące w skład środowiska programowania, zawierającego zwykle oprócz edytora kompilator i inne narzędzia wspomagające programowanie, np. Turbo Pascal, C++, Visual Basic, Delphi.
PROGRAM to ciąg instrukcji wykonujący określony algorytm. Aby zatem napisać własny program, należy poznać nie tylko instrukcje programowania, ale przede wszystkim metody programowania.
Aby przedstawić algorytm w postaci programu, trzeba go napisać jako ciąg instrukcji języka programowania. Każda instrukcja, podobnie jak skrzynka w schemacie blokowym, odpowiada określonej operacji, dlatego też kolejność występowania instrukcji w programie określa kolejność wykonywania operacji.
TRANSLACJA to tłumaczenie programu na język wewnętrzny komputera, wykonywane za pomocą wyspecjalizowanego programu, tzw. translatora. Wyróżniamy dwa typy translacji: kompilację i interpretację.
Po napisaniu ciągu instrukcji w wybranym języku programowania należy zapisać program w pliku na nośniku pamięci zewnętrznej, np. dysku twardym, oraz wykonać jego kompilację, czyli uruchomić proces tłumaczący instrukcje na język zrozumiały dla procesora. Po poprawnym przeprowadzeniu kompilacji można program uruchomić.
W zależności od języka programowania i wersji programu służącego do pisania programów plik utworzony w takim programie może mieć różne rozszerzenia, np. programy pisane w Turbo Pascalu mają rozszerzenie pas.
Pisanie programów w języku programowania RAM umożliwia program edukacyjny EI - moduł COMPUTER systemu DISC-MATH. Korzystając z niego można nie tylko napisać program, ale także przeprowadzić jego kompilację, a następnie uruchomić. W dokumentacji do programu opisano zasady korzystania z całego modułu komputer.
KOMPILACJA - przetłumaczenie napisanego przez nas programu w całości, tak by mógł on być wykonany przez komputer przy każdorazowym uruchomieniu. Raz skompilowany program nie wymaga już powtórnej operacji tłumaczenia. Do wykonania kompilacji służą programy narzędziowe - kompilatory.
INTERPRETACJA - tłumaczenie programu tworzonego w jednym z języków programowania instrukcja po instrukcji, tak by każda wywołana instrukcja była wykonana przez komputer. Tłumaczenie następuje każdorazowo przy uruchomieniu programu.
KOMÓRKA PAMIĘCI: komputer, aby móc bez przeszkód poruszać się po swoim skomplikowanym wnętrzu, potrzebuje wielu danych o własnej "anatomii". Wszystkie miejsca ważne dla jego działania (procesor, dysk, sloty kart rozszerzenia etc.) mają przypisany sobie fragment pamięci RAM. Pamięć ta podzielona jest na logiczne komórki, z których każda posiada swój adres. Dzięki temu pisząc programy, możemy nakazać im przebywanie i korzystanie z określonych obszarów pamięci RAM.
WARUNEK to wyrażenie logiczne, którego wartość (TAK lub NIE, PRAWDA lub FAŁSZ) decyduje o wykonaniu lub nie uwarunkowanej nim instrukcji.
PROGRAMOWANIE STRUKTURALNE to rozbicie działania programu na procedury (podprogramy), z których każda odpowiada za rozwiązanie określonego problemu. Procedury stanowią wtedy odrębne, samodzielnie działające całości, które możemy wykorzystać także i w innych pisanych programach.
PROCEDURA to wyodrębniona część programu, mająca jednoznaczną nazwę i ustalony sposób wymiany danych z innymi częściami programu.
PARAMETRY to zmienne, poprzez które procedura komunikuje się z innymi fragmentami programu. Parametry formalne to zmienne wpisane w procedurę, które zastępowane są przez konkretne dane (parametry aktualne) w momencie wywołania programu.
Wśród technik algorytmicznych ważne miejsce zajmują techniki sortowania, czyli porządkowania ciągów elementów, np. liczb:
SORTOWANIE BĄBELKOWE polega na porównywaniu parami kolejnych liczb i przestawianiu, jeśli są ustawione w niewłaściwej kolejności.
SORTOWANIE PRZEZ WYBÓR, metoda porządkowania liczb (np. od największej do najmniejszej) polegająca na wyszukaniu największej liczby, przestawieniu jej na początek ciągu liczb (czyli zmienieniu jej z pierwszą liczbą ciągu) i takim samym postępowaniu w ciągu z pominięciem pierwszego elementu.
SORTOWANIE KUBEŁKOWE, w przypadku ciągu słów według porządku alfabetycznego polega na porównywaniu liter umieszczonych na tych samych pozycjach, począwszy od ostatniej litery najdłuższych słów. Litera na danej pozycji decyduje o umieszczeniu słowa w ciągu w odpowiednim miejscu.
PODSUMOWANIE I UZUPEŁNIENIE
ALGORYTMIKA to jeden z obszarów tematycznych informatyki; zajmuje się budowaniem teoretycznych modeli informatycznych, czyli algorytmami.
ALGORYTM podaje krok po kroku sposób rozwiązania problemu.
Rozwiązując dowolny problem, postępujemy według podobnego schematu; określamy: dane wejściowe, sposób ich przetwarzania i wyniki, czyli cel i sposób rozwiązania.
W schemacie blokowym, czyli graficznej prezentacji algorytmu, układ skrzynek i połączeń między nimi wyznacza kolejność i sposób wykonywania działań.
W każdej skrzynce należy umieszczać jeden rodzaj operacji; skrzynki muszą być połączone.
Dla czynności wielokrotnie powtarzanych stosuje się działania w pętli, czyli iterację, jedną z najczęściej spotykanych technik algorytmicznych.
Stosując iterację należy określić sposób jej zakończenia, gdyż w przeciwnym razie program się zapętli. Zakończenie pętli może być uzależnione od zadanej liczby powtórzeń lub od spełnienia warunku logicznego.
Program to logicznie uporządkowany ciąg instrukcji realizujący określone zadanie czyli algorytm.
Programowanie polega na przedstawieniu algorytmu w postaci instrukcji języka programowania, zapisanych w kolejności wyznaczonej przez ten algorytm.
Instrukcja języka to zapis danej operacji w składni odpowiedniej dla danego języka programowania.
Programy napisane w języku wysokiego poziomu, np. Turbo Pascal, C, Visual Basic, nie są zrozumiałe dla komputera - są tłumaczone na język wewnętrzny komputera.
Tłumaczenie programu z języka wysokiego poziomu na język wewnętrzny komputera nazywamy translacją.
Pamięć komputera podzielona jest na mniejsze części (komórki). Każda z nich ma swój adres.
Zmienna w programie ma określoną bieżącą wartość, która może ulegać zmianie w trakcie wykonywania zadania (po podstawieniu do niej innej wartości). Ze zmienną związane jest jej miejsce w pamięci komputera.
Podprogramy (procedury) rozwiązują wyodrębnione części zadania i mogą być wielokrotnie wywoływane przez dany program (lub inny).
Główne metody sortowania to: przez wybór, bąbelkowe i kubełkowe.
Z rekurencją spotykamy się w definicjach, w których definiowane pojęcie odwołuje się do samego siebie.
Algorytmy iteracyjne mogą być zapisane w postaci rekurencji.