Algorytmy, języki programowania, programy

Wykład 6

Technologia Informacyjna

mgr Anna Bombińska-Sołtys

e-mail:[e-mail]

http://annasoltys.vot.pl/wyklady/

Historia algorytmu

Pierwsze opisy, które później nazwano algorytmami, dotyczyły

rozwiązań zadań matematycznych.

Pomiędzy 400 a 300 rokiem p.n.e. grecki matematyk i filozof

Euklides, wymyślił pierwszy znany nam nietrywialny algorytm,
czyli przepis na realizację zadania. Był to algorytm znajdowania
największego wspólnego dzielnika dwóch dodatnich liczb
całkowitych.

Algorytm Euklidesa

Algorytm Euklidesa - algorytm znajdowania największego

wspólnego dzielnika (NWD) dwóch liczb naturalnych. Nie wymaga
rozkładania liczb na czynniki pierwsze. Algorytm wymyślił
Eudoksos z Knidos (IV wiek p.n.e.), a Euklides jedynie zawarł go
w swoim dziele Elementy.

W algorytmie wykorzystywana jest zależność

Największy wspólny dzielnik

Stąd

Cechy algorytmu

1. Musi posiadać określony stan początkowy, czyli operację od

której zaczyna się jego realizacja.

2. Ilość operacji potrzebnych do zakończenia pracy musi być

skończona - warunek skończoności.

3. Musi dać się zastosować do rozwiązywania całej klasy zagadnień,

a nie jednego konkretnego zadania – warunek uniwersalności.

4. Interpretacja poszczególnych etapów wykonania musi być

jednoznaczna - warunek jednoznaczności.

5. Cel musi być osiągnięty w akceptowalnym czasie – warunek

efektywności.

6. Musi posiadać wyróżniony koniec.

Sposoby zapisu i typy algorytmów

Występują następujące sposoby przedstawiania algorytmów:

- ciąg kroków (opis słowny),

- drzewo decyzyjne

- schemat blokowy (sieć działań)

- zapis w strukturalnym języku programowania

Wyróżniamy następujące typy algorytmów:

- liniowy

- rozgałęziony

- z powtórzeniami (iteracyjny)

Ciąg kroków (opis słowny)

Jest to na ogół mało precyzyjny sposób zapisu. 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, recepta wykonania leku, metoda rozwiązania
zadania.

Przykład - Algorytm gotowania jajka na miękko.

Krok 1.

Włóż jajko do gotującej się wody.

Krok 2.

Zanotuj czas początkowy t

0

.

Krok 3.

Oczytaj czas aktualny t.

Krok 4.

Oblicz D

t

= t - t

0

.

Krok 5.

Jeśli D

t

< 3 min., to przejdź do kroku 3.

Krok 6.

Wyjmij jajko z gotującej się wody. Zakończ algorytm.

Drzewo decyzyjne

Drzewo decyzyjne – graficzna metoda wspomagania procesu

decyzyjnego, stosowana w teorii decyzji.

Schemat blokowy

Schemat blokowy

algorytmu jest najbardziej popularnym

graficznym sposobem przedstawiania algorytmu. Składa się on ze
skrzynek oraz połączeń między nimi. Są tu zapisane operacje,
które mają być wykonane, a połączenia wyznaczają kolejność
wykonania.

Schematy blokowe

NAJWIĘKSZY WSPÓLNY DZIELNIK

Algorytm liniowy

Algorytmem

liniowym (sekwencyjny)

nazywamy taki

algorytm, który ma postać listy kroków wykonywanych zgodnie z
ich kolejnością.

Algorytm rozgałęziony

Algorytm rozgałęziony zawiera rozgałęzienia będące efektem

sprawdzania warunków. Wyrażenia warunkowe umożliwiają
wykonanie zadania dla wielu wariantów danych i rozważenie
różnych przypadków.

Algorytm z powtórzeniami (iteracyjny)

W

algorytmach z powtórzeniami

powtarzanie różnych działań ma dwojaką
postać:

- liczba

powtórzeń

jest z góry

określona (przed rozpoczęciem cyklu)

- liczba powtórzeń

jest nieznana

(zależy

od

spełnienia

pewnego

warunku).

Z tego wynika, że możemy spotkać się z
dwoma

sytuacjami:

gdy

musimy

wykonać czynność bądź zadaną ilość razy,
bądź do momentu spełnienia warunku.

Język algorytmiczny (programowania)

Język algorytmiczny jest najbardziej ścisłym i zrozumiałym dla

komputera opisem algorytmu.

Algorytm

zapisany w języku programowania nazywamy

programem. Tekst programu może również służyć do
komunikowania rozwiązania człowiekowi.

Języki programowania są językami formalnymi (sztucznymi), a

ich wyrażenia, czyli programy muszą mieć formę możliwą do
zaakceptowania przez maszynę.

Języki programowania

1. Języki kompilowane (samodzielne programy):

-

Pascal

-

Delphi

-

C, C++.

2. Języki częściowo kompilowane (powstaje kod bajtowy -

postać pośrednia wymagający platformy uruchomieniowej):

-

Java -JVM (Java VirtualMachine),

-

JRE (Java Runtime Environment),

-

C# -.NET Framework.

Wymienione platformy są bezpłatne.

Języki programowania

3. Języki interpretowane (wymagany jest interpreter):

-

JavaScript (interpreterem jest przeglądarka),

-

Perl (Practical Extraction and Report Language, praktyczny
język ekstrakcji i raportowania),

-

PHP (obecnie PHP Hypertext Preprocessor, pierwotnie
Personal Home Page) stosowany głównie do dynamicznego
tworzenia stron internetowych,

-

VBA (Visual Basic for Aplications), interpretatorem jest
pakiet Microsoft Office, najbardziej przydatny w arkuszu
kalkulacyjnym.

Przegląd języków programowania

Program dla komputera IBM 650

Kolumna LOC zawiera numer adresu pod którym znajduje się

instrukcja, OP zawiera kod operacji, DATA dane, INST adres
instrukcji, która ma być wykonana jako następna.

Program w języku FORTRAN I

W listopadzie 1954 roku została ogłoszona pierwsza specyfikacja

języka FORTRAN, nazwa jest akronimem słów the IBM
Mathematical FORmula TRANslating system.

Można zauważyć, że program ten jest dużo czytelniejszy od

poprzedniego.

Program w języku Algol-60

W latach 60-tych antidotum na brak czytelności stał się język

Algol-60. Wprowadzono w nim pętlę for oraz możliwość dzielenia
programu na podprocedury.

Źródło

Literatura

Wstęp do informatyki.

Piotr Fulmański, Ścibór Sobieski.

Podręcznik, Wydawnictwo Uniwersytetu Łódzkiego 2005.

Algorytmy. Maciej M. Sysło. WSiP Warszawa 2002.

Strony www:

http://pl.wikipedia.org