Jerzy Pejas: Algorytmy i struktury danych

- 1 -

ALGORYTMY

POJECIA I OPIS

Jerzy Pejas: Algorytmy i struktury danych

- 2 -

WPROWADZENIE (1)

Literatura podstawowa

[1] S.Algic, M.A.Arbib

Projektowanie

programów poprawnych i dobrze
zbudowanych, WNT, Warszawa 1982

[2] T.H.Cormen, Ch.E.Leiserson, R.I.Rivest

Wprowadzenia do algorytmów, WNT,
Warszawa 1997

[3] A. Drozdek, D.L. Simon Struktury

danych w jezyku C, WNT, Warszawa,
1996 r.

[4] David Harel Rzecz o istocie informatyki -

algorytmika, WNT, Warszawa 1992 r.

[5] D. van Tassel Praktyka programowania,

WNT, Warszawa 1982

[6] Piotr Wróblewski Algorytmy - struktury

danych i techniki programowania, Wyd.
Helion, 1996 r.

[7] Niklaus Wirth Algorytmy + dane =

program, WNT, Warszawa, 1980 r.

Literatura pomocnicza

1. L.Banachowski, A.Kreczmar, R.Rytter

Analiza algorytmów i struktur danych,
WNT, Warszawa 1987

2. J.M.Brady Informatyka teoretyczna w

ujeciu programistycznym, WNT,
Warszawa, 1983

3. W.C.Jones, Jr. Data structures using

Modula, John Wiley & Sons, New York
1988

Jerzy Pejas: Algorytmy i struktury danych

- 3 -

WPROWADZENIE

O czym bedzie mowa?

♦

Zastosowanie komputerów cechuje

obecnosc pewnych ogólnych metodologii

zawiazanych z formulowaniem problemu,

utworzeniem modelu matematycznego

zadania (

algorytmizacja zadania

),

programowaniem i rozwiazaniem zadania

przy pomocy komputera. W formulowaniu i

rozwiazywaniu zadan biora udzial zwykle

specjalisci z róznych dziedzin.

R o z w i a z a n i e

z a d a n i a

T r a n s f o r m a c j a

a l g o r y t m u n a

j e z y k

p r o g r a m o w a n i a

M e t o d a

r o z w i a z a n i a w

f o r m i e a l g o r y t m u

F o r m a l i z a c j a

s f o r m u l o w a n e g o

z a d a n i a

S f o r m u l o w a n i e

z a d a n i a

O p e r a t o r

k o m p u t e r a

P r o g r a m i s t a

S p e c j a l i s t a o d

a l g o r y t m ó w

( a l g o r y t m i k )

M a t e m a t y k a

S p e c j a l i s t a z

d a n e j d z i e d z i n y

Rys.1 Proces rozwiazywania zadan

algorytmicznych

Jerzy Pejas: Algorytmy i struktury danych

- 4 -

WPROWADZENIE

O czym bedzie mowa?

♦

Kazdy komputer moze wykonac

bezposrednio tylko niewielka

liczbe skrajnie prostych operacji,

takich jak przerzucanie,

wyzerowanie lub sprawdzenie

bitu. Dlaczego wiec przy pomocy

tak prostych rzeczy mozna

realizowac nawet bardzo zlozone

czynnosci? Jak bity to

robia? Odpowiedz

tkwi w dwóch glównych pojeciach:

proces i algorytm.

Rys.2 Operacje na bitach

Jerzy Pejas: Algorytmy i struktury danych

- 5 -

WPROWADZENIE (3)

Pojecie algorytmu i algorytmiki

♦

Pieczenie ciasta - to proces wykonywany ze
skladników, przez piekarza, za pomoca
pieca wedlug przepisu. Skladniki sa danymi
wejsciowymi tego procesu, ciasto jest
danymi wyjsciowymi, czyli wynikiem, a
przepis jest algorytmem. Innymi slowy,
algorytm definiuje czynnosci, które skladaja
sie na proces. Przepisy, a wiec algorytmy
zwiazane ze zbiorem procesów, nazywa sie
czesto oprogramowaniem, zas przybory,
piec, a takze piekarza nazywa sie zwykle
sprzetem.

Rys.3 Proces pieczenia ciasta

Jerzy Pejas: Algorytmy i struktury danych

- 6 -

WPROWADZENIE

Pojecie algorytmu i algorytmiki

♦

Przepisy okreslamy mianem algorytmów,

zas obszar dociekan, wiedzy i doswiadczen

dotyczacych algorytmów nazwiemy

algorytmika.

♦

Algorytmika to wiecej niz dzial informatyki.

Tkwi w centrum wszystkich dzialów

informatyki i jest wazna dla wiekszosci nauk

matematyczno-przyrodniczych, ekonomii i

techniki. Sama natura algorytmiki czyni ja

jednak szczególnie odpowiednia do

stosowania w tych dyscyplinach, które

czerpia korzysci z poslugiwania sie

komputerem.

♦

Slowo algorytm wywodzi sie od nazwiska

perskiego matematyka Muhammeda

Alchwarizmi, który zyl w IX wieku. To

nazwisko, pisane po lacinie, przyjelo postac

Algorismus, stad do algorytmu juz bardzo

blisko.

♦

Miedzy 400 a 300 rokiem przed Chrystusem

grecki matematyk Euklides wynalazl

algorytm znajdowania najwiekszego

wspólnego dzielnika (nwd) dwóch liczb

calkowitych. Algorytm Euklidesa, uwaza sie

za pierwszy kiedykolwiek wymyslony

niebanalny algorytm.

Jerzy Pejas: Algorytmy i struktury danych

- 7 -

WPROWADZENIE

Instrukcje podstawowe

•

Polecenie typu domieszaj cukier puder jest

ogólnym stwierdzeniem, mniej dokladnym
od wez nieco cukru pudru, wsyp go do
rozpuszczonej czekolady, wymieszaj, wez
jeszcze troche cukru, wsyp, wymieszaj ...,
itd. albo od precyzyjnego sformulowania
wez 150 gram cukru pudru, wsyp do
rozpuszczonej czekolady i wymieszaj przy
pomocy lyzki.

•

Przyjety poziom szczególowosci wynika z

tego, ze sprzet wie, jak wymieszac cukier
puder z czekolada.

•

Poziom szczególowosci jest bardzo wazny i

musi byc tak dobrany, aby odpowiadal
szczególnym mozliwosciom danego
sprzetu.

•

Poziom ten zalezy od uzgodnionego na

samym poczatku zestawu tzw. akcji
podstawowych (instrukcji podstawowych),
które z definicji wbudowane sa w sprzet.

•

Przy formulowaniu algorytmów bedziemy

przyjmowac, ze instrukcje podstawowe
musza byc okreslone jasno i precyzyjnie
oraz jasno odróznialne od nie instrukcji w
rodzaju wyjdzie z tego 6 do 8 porcji.

•

Jesli np. sprzet potrafi sam obliczyc

wyznacznik z macierzy, to nie ma sensu
mówic mu jak to ma zrobic. Podobnie, jesli
umie wykonac mnozenie dwóch liczb
calkowitych, to zadanie znalezienia np.
najwiekszego wspólnego mnoznika dwóch
liczb calkowitych formulujemy w oparciu o
zestaw instrukcji podstawowych wyzszego
poziomu.

Jerzy Pejas: Algorytmy i struktury danych

- 8 -

WPROWADZENIE

Przyklad algorytmu

W oparciu o ankiety personalne
pracowników przedsiebiorstwa, zawierajace
nazwisko, szczególy danych osobowych i
zarobki pracowników nalezy obliczyc
miesieczne wydatki firmy na place.

Algorytm postepowania:

(1) zanotuj na boku liczbe 0
(2) przewertuj kolejno ankiety,

dodajac zarobki kazdego z
pracowników do liczby na
boku,

(3) kiedy osiagniesz koniec

listy, przedstaw wartosc
liczby na boku jako wynik

Algorytm rzeczywiscie sumuje zarobki
pracowników. Tekst tego algorytmu jest i ma
ustalona dlugosc, ale proces który opisuje i
którym steruje zmienia sie wraz z liczba
ankiet i moze zabrac rózna ilosc czasu.
Algorytm ten jest jednak na tyle uniwersalny,
ze bez zadnych moze byc zastosowany w
róznych przedsiebiorstwach, o róznej liczbie
pracowników.

Rys.4 Sumowanie zarobków

Jerzy Pejas: Algorytmy i struktury danych

- 9 -

ZADANIE ALGORYTMICZNE

•

Algorytm opisuje wiele procesów o
róznych dlugosciach i czasach trwania.

Rys.5 Zadanie algorytmiczne i jego

rozwiazanie

•

Dowolny algorytm powinien zachowywac
sie zadawalajaco dla dowolnejliczby
zestawów danych wejsciowych, które
musza byc dopuszczalne (przygotowane
wg specyfikacji).

•

Algorytmy sa

rozwiazaniami

zadan

algorytmicznych

(problemów

obliczeniowych). Zadanie to

czarna

skrzynka, okreslona dokladna specyfikacja
danych wejsciowych i definicja zadanych
wyników.

•

Z instrukcji podstawowych buduje sie
algorytm. Kazdy instrukcja musi byc
wykonana w skonczonym czasie, w
przeciwnym bowiem razie algorytm nigdy
nie zakonczy sie (nie spelni warunku
stopu).

Jerzy Pejas: Algorytmy i struktury danych

- 10 -

DEFINICJA ALGORYTMU

Definicje nieformalne

•

Algorytm jest pewna scisle okreslona

procedura postepowania, która dla
wlasciwych danych wejsciowych produkuje
zadane dane wyjsciowe, zwane wynikiem
dzialania algorytmu.

•

Algorytm to takze sposób rozwiazania
konkretnego zadania algorytmicznego.
Problem: sprecyzowanie wymagan
dotyczacych relacji miedzy danymi
wejsciowymi i wyjsciowymi. Algorytm:
procedura obliczeniowa, zapewniajaca
osiagniecie tej relacji.

Okreslenia pomocnicze

•

Akcja podstawowa (instrukcja podstawo-
wa) - posiada skonczony czas trwania i

prowadzi do pozadanego i calkowicie
okreslonego wyniku.

•

Dane wejsciowe - cos, na czym wykonuje
sie akcje podstawowe i przez zmiane czego
mozna sadzic o wyniku akcji.

•

Dane wyjsciowe (wynik) - zmiana danych
wejsciowych na skutek poddaniu ich
pewnej akcji.

•

Jezyk - srodek opisu danych i akcji
podstawowych.

•

Instrukcja - opis akcji w pewnym jezyku.

•

Proces - akcja, która po rozlozeniu na
czesci, jest zbiorem innych akcji
podstawowych.

Algorytm jest to zbiór instrukcji,
okreslajacych w jakiej kolejnosci, na jakich
danych wejsciowych i jakie akcje
podstawowe nalezy wykonac, aby uzyskac
wymagany wynik.

Jerzy Pejas: Algorytmy i struktury danych

- 11 -

POSTACIE OPISU

ALGORYTMU

Kazdy z algorytmów mozna przedstawic w
trzech postaciach podstawowych:

postac

opisujaca

- jest opisem w jezyku naturalnym, w

szczególnosci matematycznym,

postac graficzna

- sa to specjalne znaki graficzne z zaznaczeniem
powiazan pomiedzy nimi,

postac programowa

-

algorytm zapisany jest w jezyku abstrakcyjnego
(pseudokodzie) lub konkretnego komputera.

Pseudokod: (patrz takze Cormen i in. -
Wprowadzenie do algorytmów):

1. Slowa begin i end definiuja blok algorytmu.

2. Instrukcje iteracji while, for, do-while oraz

warunkowe if - else maja taka sama
interpretacje jak w jezyku C.

3. Symbol -- oznacza, ze reszta wiersza jest

komentarzem.

4. Wielokrotne przypisywanie w formie i

←j←e.

5. Zmienne takie jak i, j, sa lokalne w danej

procedurze. Zmienne globalne musza byc
okreslone explicite.

6. Dostep do elementu tablicy oznaczamy

poprzez podanie jej nazwy i indeksu zadanego
elementu, np. a[i]. Notacja “..” sluzy do
oznaczenia podtablicy, np.

a[1..j] jest

podtablica.

7. Dane zlozone z kilku czesci sa organizowane w

klasy, skladajace sie z atrybutów lub pól.
Odwolanie sie do pola obiektu klasy: nazwa
obiektu i nazwa pola, wystepujacej po znaku
→. Np. dla wszystkich pól f obiektu x,
przypisanie y

←x oznacza y→f=x→f, a takze iz

x i y wskazuja na te same obiekty. Zmienna
odpowiadajaca obiektowi jest traktowana
jako wskaznik do danych reprezentujacych
ten obiekt.

8. Parametry sa przekazywane do procedury

przez wartosc. Obiekty przekazywane sa przez
adres (wskazniki do nich).

Jerzy Pejas: Algorytmy i struktury danych

- 12 -

ALGORYTMY I DANE

•

Algorytm jest zbiorem starannie dobranych

instrukcji, bedace poleceniami wykonania
akcji podstawowych.

Rys.6 Program a algorytm

•

Kazdy komputer wyposazony jest w procesor,
który potrafi wykonywac wbudowane w niego
instrukcje elementarne.

•

Akcje podstawowe kazdego algorytmu musza
byc na taki wlasnie zestaw instrukcji

elementarnych i wykonywane przez
procesor w kolejnosci, wynikajacej z
logiki danego algorytmu.

•

Algorytm zawiera instrukcje sterujace,
mówiace procesorowi co ma zrobic i na
jakich danych, kiedy ma sie zatrzymac i
pozostac w stanie gotowosci do
kontynuowania pracy.

•

Stad juz jeden krok do programu, który
stanowi skonkretyzowane
sformulowanie algorytmów na podstawie
okreslonej reprezentacji i

struktur

danych. Mozna to dobitnie zapisac za
pomoca tytulu slynnej ksiazki

Algorytm

Akcje

podstawowe

obiekty - dane

Instrukcje

Porgram

Struktury

sterujace

Jerzy Pejas: Algorytmy i struktury danych

- 13 -

N.Wirth’a: algorytmy + struktury danych =
programy.

ALGORYTMY I DANE

Struktury sterujace

Kolejnoscia wykonania steruje sie przy
pomocy zbioru instrukcji zwanych
strukturami przeplywu sterowania lub krócej
strukturami sterujacymi. Do podstawowych
struktur sterujacych naleza:

•

bezposrednie nastepstwo w postaci
wykonaj A, a potem B (tzw. sekwencja
instrukcji podstawienia), np. do liczby 12
dodaj 3, a potem wynik podziel przez 5,

•

wybór warunkowy

(rozgalezienie

warunkowe) w postaci jesli Q, to wykonaj
A, w przeciwnym razie wykonaj B (ang. if
Q then A else B), lub jesli Q, to B (ang. if
Q then A); Q jest pewnym warunkiem,

•

selekcja, zwana takze wielokrotnym
wyborem warunkowym (krócej instrukcja
wyboru), w postaci przypadek C

1

z Q to

wykonaj A

1

, C

2

z Q to wykonaj A

2

, ..., C

n

z

Q to wykonaj A

n

(odpowiednik w jezyku

Pascal case Q of C

1

: A

1

; C

2

: A

2

; ..., C

n

: A

n

end), bedaca uogólnieniem wyboru
warunkowego z zagniezdzonymi innymi
warunkami wyboru.

•

iteracja ograniczona w postaci ogólnej
wykonaj A dokladnie N razy (np.
przykladem jest tu konstrukcja jezyka
Pascal for i:=1 to N do A;), gdzie N jest
pewna liczba,

•

iteracja warunkowa, zwana czasem
nieograniczona, w postaci wykonuj A az
do Q - iteracja z warunkiem koncowym
(odpowiednik w jezyku Pascal repeat A
until Q) lub dopóki Q, wykonuj A - iteracja

Jerzy Pejas: Algorytmy i struktury danych

- 14 -

z warunkiem poczatkowym (odpowiednik
w Pascalu while Q do A).

Jerzy Pejas: Algorytmy i struktury danych

- 15 -

ALGORYTMY I DANE

Przyklad: Algorytm sortowania
babelkowego

Rys.7 Glówne stadia sortowania babelkowego

Opis w jezyku naturalnym:

(1) wykonaj co nastepuje N-1 razy:

(2.1) wskaz na pierwszy element;
(2.2) wykonaj co nastepuje N-1 razy:

(2.2.1) porównaj wskazany element z

nastepnym

(2.2.2) jesli porównywane elementy sa w

niewlasciwej kolejnosci, zamien je
miejscami;

(2.2.3) wskaz na nastepny element

Pseudokod:

for i

← 1 to N-1

for j

← 1 to N-i

begin

key

← a[j]

if (a[j+1] < key)
begin
a[j]

←a[j+1]; a[j+1]←key

end

end

Jerzy Pejas: Algorytmy i struktury danych

- 16 -

PODPROGRAMY, CZYLI

PROCEDURY

W jakims dlugim tekscie zliczamy zdania
zawierajace slowo pieniadze.

•

W petli zewnetrznej realizowane sa dwa

poszukiwania: najpierw slowa pieniadze,
a nastepnie znaku konca zdania, czyli
kombinacji ‘. ‘.

Jerzy Pejas: Algorytmy i struktury danych

- 17 -

PODPROGRAMY, CZYLI

PROCEDURY

Ulepszenie algorytmu: napisanie
fragmentu algorytmu, zwanego
podprogramem lub

procedura z

parametrem.

•

Stosowanie podprogramów skraca
opis algorytmu.

•

Podprogram jest nowa akcja
podstawowa.

•

Procedury czynia algorytm czytelnym
o przejrzystej strukturze.

•

Zwykle obmysla sie wpierw algorytm
wysokiego poziomu z akcjami
podstawowymi, które moga byc
jeszcze nieznane. Takie podejscie
oznacza projektowanie od ogólu do
szczególu i nazywane jest

metoda

zstepujaca (inne podejscie, to metoda
wstepujaca).

Jerzy Pejas: Algorytmy i struktury danych

- 18 -

TYPY DANYCH I STRUKTURY

DANYCH

Jerzy Pejas: Algorytmy i struktury danych

- 19 -

TYPY DANYCH I STRUKTURY

DANYCH

Kolejki i stosy

Stos jest kolekcja danych, które sa
uporzadkowane wedlug
kolejnosci ich otrzymywania.
Kazdy nowy element danych jest
umieszczany na szczycie stosu.
Dane sa zdejmowane ze stosu,
poczawszy od elementu, który
znajduje sie na szczycie. Dynamike
umieszczania elementów na stosie oraz ich
zdejmowania okresla sie skrótem LIFO (ang.
Last-In First-Out, czyli ostatni na wejsciu -
pierwszy na wyjsciu). Na stosie mozna, obok
umieszczania oraz zdejmowania elementów,
wykonywac takze inne operacje, np. usuwac

wszystkie elementy oraz przesuwac elementy
w góre lub w dól.

Uporzadkowanie elementów w kolejce jest
takie samo jak na stosie, czyli zgodne z
kolejnoscia ich otrzymywania. Teraz jednak

kazda nowa dana jest umieszczana na koncu
kolejki, a pobierana z jej poczatku. Ten
sposób umieszczania oraz pobierania
elementów z kolejki okresla sie skrótem FIFO
(ang. First-In First-Out, czyli pierwszy na
wejsciu - pierwszy na wyjsciu).

Jerzy Pejas: Algorytmy i struktury danych

- 20 -

DIAGRAMY ALGORYTMÓW -

SCHEMATY BLOKOWE

Rysunek przedstawia trzy podstawowe
wzorce (konstrukcje strukturalne),
odpowiadajace wprowadzonym wczesniej
instrukcjom sterujacym:

•

Bezposrednie nastepstwo (sekwencja)

•

Wybór warunkowy (w skrócie warunek),

zwany takze if-then-else

•

Iteracja warunkowa z warunkiem

poczatkowym do-while (odpowiednik w
Pascalu while-do).

•

Konstrukcja z warunkiem koncowym

repeat-until.

•

Konstrukcja selekcji (lub wybór-

przypadku) jest rozszerzeniem instrukcji if-
then-else. Parametr decyzyjny,
wystepujacy w kazdym bloku decyzyjnym,
jest testowany kolejno, az do momentu
spelnienia warunku. Po spelnieniu

warunku wykonywana jest odpowiadajaca mu czesc
przypadku case.

Jerzy Pejas: Algorytmy i struktury danych

- 21 -

DIAGRAMY ALGORYTMÓW -

DIAGRAMY BLOKOWE

Diagramy te zostaly opracowane przez Nassi i
Shneidrman’a i rozbudowane przez Chapin’a
(zwane sa wykresami Nassi-
Shneiderman’a, wykresami N-S lub
wykresami Chapin’a).

Cechy:

•

zakres funkcjonalny (zasieg
powtórzen lub instrukcji if-then-
else) jest dobrze zdefiniowany oraz
dobrze widoczny,

•

dowolne przekazywanie sterowania
przeplywani w ramach diagramu jest
niemozliwe,

•

zasieg widocznosci zmiennych
(lokalnych i globalnych) jest latwy
do okreslenia,

•

w sposób prosty mozna przedstawiac
konstrukcje rekurencyjne.

First task

Next task

Next task

Condition

F

T

F

T

Case condition

Else

part

Then

part

Loop condition

Loop condition

Do - while

part

Repeat - until

part

Value

Value

Value

…..

Else

part

Case

part

Case

part

Case

part

….

Jerzy Pejas: Algorytmy i struktury danych

- 22 -

DIAGRAMY ALGORYTMÓW -
DIAGRAMY STRUKTURALNE

Jezyk projektowania programów
stosowany jest czesto w sprzezeniu z
narzedziami projektowania typu CASE

1

-

Komputerowo Wspomagana Inzynieria
Oprogramowania (ang. Computer-Aided
Software Engineering), które w
niektórych przypadkach tlumacza wrecz
komponenty graficzne algorytmu na
odpowiadajaca im reprezentacje
proceduralna. Stad np. diagramy struktur
sterowania moga byc tlumaczone na kod
zródlowy jezyka programowania.

1

CASE mozna uwazac za srodek automatyzacji programowania strukturalnego

Jerzy Pejas: Algorytmy i struktury danych

- 23 -

DIAGRAMY ALGORYTMÓW

- PORÓWNANIE

Schemat blokowy - przyklad

x2

x3

x4

x5

c

d

e

a

b

x1

x8

j

f

g

x6

i

h

x7

Jerzy Pejas: Algorytmy i struktury danych

- 24 -

DIAGRAMY ALGORYTMÓW

- PORÓWNANIE

Diagram blokowy - przyklad

a

b

x1

case xi, i=2,3,4

x2

x3

x4

f

x6

g

x5

c

d

e

h

i

x8

x7

j

Jerzy Pejas: Algorytmy i struktury danych

- 25 -

TRANSLATORY

Zlózmy ze dany jest programowania, tzn.
jego skladnia, semantyka i inne potrzebne
elementy, oraz oprogramowalismy
opracowany wlasnie algorytm A rozwiazujacy
pewne zadanie algorytmiczne i chcemy
przedstawic powstaly program o nazwie A

P

komputerowi. Jak to zrobic, aby komputer
zrozumial nasz program?

♦

Wyjscie pierwsze. Program A

P

mozemy

wprowadzic do pamieci komputera z
klawiatury lub wczytujac go z
zewnetrznego nosnika pamieciowego
(dyskietka, dysk, itp.). W trakcie
wczytywania program

A

P

ulega

przeksztalceniom, które stopniowo
sprowadzaja go do poziomu zrozumialego
przez komputer.

♦

Wyjscie drugie. Programu A

P

nie musimy

w calosci tlumaczyc na jezyk nizszego
poziomu. To raczej kazda z instrukcji
wysokiego poziomu zostaje
przetlumaczona na instrukcje jezyka
maszynowego natychmiast po jej
napotkaniu, a te z kolei od razu sa
wykonywane. Mechanizm odpowiedzialny
za tego rodzaju tlumaczenie i
natychmiastowe wykonanie jest
fragmentem oprogramowania
systemowego, nazywanym interpreterem.

Czesto kompilatory oraz interpretery
okreslane sa wspólnym mianem translatora
(doslownie - tlumacz). Translatory oprócz
zadania przelozenia programu na jezyk
maszynowy, musza wykrywac ewentualne
bledy w skladni programu i diagnozowac ich
przyczyny.

Jerzy Pejas: Algorytmy i struktury danych

- 26 -

TRANSLATORY

Jerzy Pejas: Algorytmy i struktury danych

- 27 -

JEZYKI PROGRAMOWANIA

Skladnia typowego jezyka zawiera:

•

warianty kilku struktur sterujacych

•

sposoby definiowania rozmaitych struktur

danych

•

wzorce podstawowych instrukcji

Algorytm sumowania liczb od 1 do N w
hipotetycznym jezyku JP:

definiuj N, X, Y liczby
calkowite
wczytaj N;

X := 0;
dla Y od 1 do N wykonaj

X := X + Y
koniec; wypisz X.

Slowa kluczowe: definiuj, wczytaj, dla itd.
Instrukcje:

przypisania

- X := 0

iteracji

- dla ...

wykonaj ... koniec

ALGORYTM

Jezyk programowania

PROGRAM

symbole

slowa kluczowe

skladnia

semantyka

Jerzy Pejas: Algorytmy i struktury danych

- 28 -

JEZYKI PROGRAMOWANIA

Definiowanie skladni jezyka w notacji
BNF (Backus-Naur Form) („|” oznacza
„lub”):

<instrukcja> : <instrukcja-dla> |

<instrukcja-
przypisania> | ...

<instrukcja-dla> : dla <naglówek-
dla> wykonaj <instrukcja> koniec
<naglówek-dla> : <zmienna> od

<wartosc> do
<wartosc>

<wartosc> : <zmienna> | <liczba> |
...

Diagramy skladniowe:

instrukcja-dla

instrukcja-przypisania

instrukcja

naglówek-dla

instrukcja

instrukcja-dla

dla

wykonaj

koniec

zmienna

wartosc

naglówek-dla

od

z krokiem

do

wartosc

wartosc

zmienna

cyfra

wartosc

cyfra

litera

zmienna

litera

Definiowanie struktur danych:

definiuj TA tablica
[1..50,8..107] w niej
liczby calkowite

i odwolanie do elementu tablicy:

TA[wartosc,wartosc]

Jerzy Pejas: Algorytmy i struktury danych

- 29 -

JEZYKI PROGRAMOWANIA

Skladnia jezyka programowania okresla:

•

jak opisywac struktury sterujace

•

jak opisywac struktury danych

•

jak tworzyc poprawne ciagi symboli dla

nazywania zmiennych i struktur danych

•

jak stosowac interpunkcje (np. spacje,

sredniki, kropki, nawiasy)

Semantyka okresla znaczenie poprawnych

skladniowo wyrazen

Przyklad problemów semantycznych - zmienne
procedurowe:

Jesli skladnia dopuszcza zmienne, których
wartosciami sa nazwy procedur, to procedura
Proc(V) moze byc wywolywana z róznymi
wartosciami parametru np. Proc(Rand) lub
Proc(Quick). Jaki wynik uzyskamy gdy
wywolamy Proc(Proc) dla:

procedura Proc(V):
1. wywolaj V(V), umieszczajac

wynik dzialania w zmiennej
X;

2. jesli X = 1, wróc i podaj

wynik 0; w przeciwnym razie
wróc i podaj wynik 1

Przyklad kompilacji na jezyk nizszego rzedu
(asembler):

Jezyk wysokiego

poziomu

Asembler

dla Y od 1 do N
wykonaj
(tresc iteracji)
koniec

LDS 0,Y

(zaladuj 0 pod adres
Y)

PETLA POR N,Y

(porównaj wart. pod
adr.)

SKR DALEJ (jesli równe, to

skocz)

DDS 1,Y

(dodaj 1 do wart. pod
adr. Y)

(tlumaczenie tresci iteracji)

SKO PETLA (skocz z powrotem)

DALEJ ...

Jerzy Pejas: Algorytmy i struktury danych

- 30 -

JEZYKI PROGRAMOWANIA

Definicja pojec:

q

Kompilacja - przekladanie calego
programu napisanego w jezyku
wysokiego poziomu na program w
jezyku nizszego poziomu

q

Interpretacja - przekladanie kolejno
instrukcji jezyka wysokiego poziomu na
instrukcje poziomu maszynowego

Elementy komputera:

PROCESOR

Pamiec operacyjna

Pamieci zewnetrzne

Urzadzenia

wejsciowe

Urzadzenia

wyjsciowe

Uruchomienie programu

PROCESOR

Pamiec operacyjna

Pamiec zewnetrzna

Program

1. krok

Jerzy Pejas: Algorytmy i struktury danych

- 31 -

JEZYKI PROGRAMOWANIA

Uruchomienie programu

PROCESOR

Pamiec operacyjna

Pamiec zewnetrzna

Program

2. krok

Dane

Urz. wejsciowe

PROCESOR

Pamiec operacyjna

Program

3. krok

Dane

Wyniki

PROCESOR

Pamiec operacyjna

Program

4. krok

Dane

Wyniki

Urz. wyjsciowe