Algoritmus

Algoritmus

Informatika 1

Pojmy zavedené v 2. prednáške(1)

• trieda ako

– inštancia metatriedy
– priamo definovaný objekt – Java

• delenie jazykov

– založené na objektoch
– založené na triedach - Java

• UML – grafické znázornenie triedy

– názov, atribúty, metódy
– rôzne pohľady podľa účelu

Informatika 1

1

Pojmy zavedené v 2. prednáške(2)

• definícia triedy – Java

– definícia atribútov
– definícia konštruktorov
– definícia metód

• parametre konštruktorov a metód

– formálne – v definícii metódy
– skutočné – v správe

• návratová hodnota metódy

– typ void

Informatika 1

2

Pojmy zavedené v 2. prednáške(3)

• primitívne dátové typy

– pre celé čísla
– pre reálne čísla
– znaky
– logické hodnoty

• literály

– primitívnych dátových typov
– String

Informatika 1

3

Pojmy zavedené v 2. prednáške(4)

• priraďovací príkaz

– výraz, operátor priradenia

• príkaz return
• príkazy pre tlač do okna terminálu

• komentáre

– jednoriadkové - // komentar
– viacriadkové /* komentar */

• dokumentačné /** komentar */

Informatika 1

4

Cieľ prednášky

• aritmetický výraz
• identifikátor
• algoritmus

– definícia a vlastnosti
– základné konštrukčné prvky
– Algoritmus – znázornenie v UML

• vetvenie

• príklad: Lepšia verzia automatu MHD

Informatika 1

5

Aritmetický výraz(1)

• príklady výrazov

Informatika 1

6

aTrzba + aCenaListka

aVlozenaCiastka – aCenaListka

paCenaListka

aPocetPredanychListkov + 1

0

Aritmetický výraz(2)

• predpis na výpočet číselnej hodnoty, obvykle má

tvar matematického výrazu

• aritmetický výraz môže mať formu:

– bez operátorov

• číselný literál
• číselný parameter
• číselný atribút

– s aritmetickým operátorom

• unárnyOperátor operand
• operand binárnyOperátor operand

Informatika 1

7

Aritmetický výraz(3)

• príklady výrazov

Informatika 1

8

aTrzba + aCenaListka

aVlozenaCiastka – aCenaListka

paCenaListka

aPocetPredanychListkov + 1

0

Unárne aritmetické operátory

• tvar:

• operand môže byť ľubovoľný aritmetický výraz
• unárne aritmetické operátory:

– - (mínus) – unárne mínus – zmena znamienka
– + (plus) – unárne plus

Informatika 1

9

operator operand

Binárne aritmetické operátory

• tvar

• operand môže byť ľubovoľný aritmetický výraz
• binárne aritmetické operátory:

– + (plus) – súčet
– - (mínus) – rozdiel
– * (hviezdička) – súčin
– / (lomka) – podiel
– % (percento) – zvyšok po delení

Informatika 1

10

prvýOperand operátor druhýOperand

Priorita operátorov(1)

• operátory sa vyhodnocujú v nasledujúcom

poradí:

– unárne +, -
– binárne *, /,%
– binárne +, -

• teda rovnako ako v matematike

Informatika 1

11

Priorita operátorov(2)

• poradie vyhodnocovania sa dá ovplyvňovať

zátvorkami – spôsobom obvyklým v matematike

• zátvorky treba používať vždy, keď to zlepší

čitateľnosť výrazu

Informatika 1

12

13

Informatika 1

Zátvorky

?. ?

?. ?

a * b / c * d

(a * b) / (c * d)

Typ hodnoty aritmetického výrazu

• operand v aritmetickom výraze môže

reprezentovať len číselnú hodnotu

Informatika 1

14

operandy

byte, short, int

long

float

double

byte, short, int

int

long

float

double

long

long

long

float

double

float

float

float

float

double

double

double

double

double

double

15

Informatika 1

Typová kompatibilita – príkaz návratu(1)

public int dajCenuListka()
{
return aCenaListka;
}

Typová kompatibilita – príkaz návratu(2)

• typ výrazu musí byť konvertovateľný na typ

návratovej hodnoty

Informatika 1

16

public typ nazovMetody(parametre)
{
return vyraz;
}

17

Informatika 1

Typová kompatibilita – priradenie(1)

aTrzba = aTrzba + aCenaListka;

Typová kompatibilita – priradenie(2)

• typ výrazu na pravej strane priraďovacieho

príkazu musí byť konvertovateľný na typ ľavej
strany priraďovacieho príkazu

Informatika 1

18

lavaStrana = výraz;

Typová kompatibilita – konverzie

• prvý stĺpec – cieľový typ konverzie
• prvý riadok – zdrojový typ konverzie

Informatika 1

19

operandy

byte

short

int

long

float

double

byte

A

N

N

N

N

N

short

A

A

N

N

N

N

int

A

A

A

N

N

N

long

A

A

A

A

N

N

float

A

A

A

A

A

N

double

A

A

A

A

A

A

20

Informatika 1

Typová kompatibilita príklad

private int aHodnotaInt;
private byte aHodnotaByte;
private double aHodnotaDouble;

aHodnotaInt = 5;

aHodnotaInt = aHodnotaByte;

aHodnotaInt = aHodnotaDouble;

Identifikátor

• názov, pomenovanie inštancie, triedy, správy,

metódy a atribútu sa nazýva identifikátor

• identifikátor je jedno alebo viacslovné

pomenovanie

Informatika 1

21

Návrh identifikátorov(1)

• identifikátory navrhujeme, volíme tak, aby

vyjadrovali význam, zmysel pojmu

• nepoužívame neznáme skratky
• programy sú síce určené na to, aby ich vykonávali

počítače, ale čítajú ich aj ľudia

• úspešný program sa stále nejako mení

Informatika 1

22

Návrh identifikátorov(2)

• pre tvorbu identifikátorov platia

– pravidlá – určuje programovací jazyk
– konvencie – určuje programátorská komunita

Informatika 1

23

Pravidlá tvorby identifikátorov

• programovací jazyk definuje pravidlá, ktoré musí

spĺňať každý identifikátor

• Java definuje tieto pravidlá

– môže sa skladať z písmen, číslic a znakov „_“

(podčiarkovník) a „$“ (dolár)

– nesmie začínať číslicou
– rozlišujú sa malé a VEĽKÉ písmená
– nesmie sa zhodovať so žiadnym kľúčovým slovom

• kľúčové slovo – slovo alebo identifikátor so špecifickým

významom v programovacom jazyku

Informatika 1

24

Konvencie pre tvorbu identifikátorov

• jednotlivé slová sa píšu bez medzier
• prvé slovo sa píše malým písmenom
• druhé a ďalšie slová začínajú veľkým písmenom
• výnimka: identifikátor triedy vždy začína veľkým

písmenom

• príklady

– trieda: AutomatMHD
– metóda: tlacListok

Informatika 1

25

Konvencie použité v príkladoch

• identifikátor sa píše bez diakritiky
• identifikátor atribútu začína predponou „a“

– príklad: aTrzba

• identifikátor parametra metódy a konštruktora

začína predponou „pa“

– príklad: paCenaListka

Informatika 1

26

Algoritmy a AutomatMHD

• telo konštruktora obsahuje tie príkazy, ktoré

predstavujú inicializáciu práve vytvoreného
automatu

• telá metód obsahujú tie príkazy, ktoré urobí

automat ako reakciu na prijatie rovnomennej
správy

• telá predstavujú algoritmy

Informatika 1

27

Algoritmus

• algoritmus

– popis pracovného postupu, ktorým sa rieši určitá

skupina úloh.

– presne definovaná konečná postupnosť príkazov

(krokov), vykonávaním ktorých pre každé prípustné
vstupné hodnoty získame po konečnom počte krokov
odpovedajúce výstupné hodnoty.

• algoritmizácia

– tvorivý proces hľadania a vytvárania algoritmu.

Informatika 1

28

Vlastnosti algoritmu

• determinovanosť – po vykonaní každého kroku

musí byť jednoznačne určený krok nasledujúci

• rezultatívnosť – pre rovnaké vstupné údaje musí

algoritmus dať rovnaké výstupné údaje

• konečnosť – vykonávanie algoritmu má vždy

konečný počet krokov

• hromadnosť – nie je riešením jedinej úlohy, ale

všetky úlohy danej kategórie, ktoré sa líšia len
hodnotami vstupných údajov

Informatika 1

29

Procesor

• algoritmus vykonáva objekt, ktorý sa nazýva

procesor.

• algoritmus musí byť vyjadrený v jazyku, ktorému

procesor rozumie a vie vykonávať príkazy
zapísané pomocou toho jazyka.

• predpokladom je, že procesor „neuvažuje“ –

príkazy algoritmu vykonáva mechanicky.

Informatika 1

30

Vyjadrenie algoritmu

• postup vyjadrený v prirodzenom jazyku –

procesorom je človek.

• znázornený graficky v podobe diagramu –

používa najčastejšie človek, keď sa chce vyjadriť
nezávisle od prirodzeného jazyka autora.

• zapísaný v programovacom jazyku – ak je

procesorom počítač.

Informatika 1

31

Štruktúrované programovanie

• doteraz – všeobecne o algoritmoch
• ich zápis môže mať rôzne formy v rôznych

programovacích jazykoch

• odteraz len štruktúrované programovanie
• podporuje ho aj Java

Informatika 1

32

Základné konštrukčné prvky

• prvkami sú príkazy
• jednoduché

– priraďovací príkaz
– príkaz návratu

• štruktúrované

– postupnosť (sekvencia)
– vetvenie (alternatíva )
– cyklus

Informatika 1

33

Štruktúrované príkazy

• postupnosť (sekvencia)

– určuje poradie vykonávania príkazov
– príkazy môžu byť jednoduché aj štruktúrované

• vetvenie – výber jednej alternatívy

– alternatívne vetvy algoritmu
– vetva sa uplatní, ak je splnená podmienka

• cyklus – opakovanie časti algoritmu

– opakovaná časť – telo cyklu
– opakovanie na základe podmienky cyklu

Informatika 1

34

Primitívny automat MHD

• telá konštruktora a všetkých metód sú

postupnosti (sekvencie) jednoduchých príkazov.

• grafické znázornenie v UML
• príklad – konštruktor
• telo konštruktora tvoria 3 príkazy – nastavenie

automatu do začiatočného stavu.

Informatika 1

35

Java – postupnosť príkazov

aCenaListka = paCenaListka;
aVlozenaCiastka = 0;
aTrzba = 0;

Informatika 1

36

Diagram aktivít UML – postupnosť(1)

Informatika 1

37

aktivita = jednoduchý príkaz

Diagram aktivít UML – postupnosť(2)

Informatika 1

38

aktivita = príkaz – sekvencia

Nedostatky prvej verzie automatu

1. chýba kontrola, či vložená čiastka pokrýva cenu

lístka

2. chýba kontrola, či je vložená minca s kladnou

hodnotou

3. chýba kontrola, či je zadaná cena lístka kladná
4. automat nevráti preplatok, ak sa vloží väčšia

čiastka, ako je cena lístka

Informatika 1

39

Riešenie nedostatkov – 1

chýba kontrola, či vložená čiastka pokrýva cenu
lístka
• treba sa rozhodnúť

– ak vložená čiastka dosahuje cenu lístka

• lístok sa vytlačí

– ak vložená čiastka nedosahuje cenu lístka

• lístok sa nevytlačí, vypíše sa dôvod

• riešenie: vetvenie

Informatika 1

40

Vetvenie v diagrame aktivít

Informatika 1

41

[podmienka]

vetvenie – decision

spojenie – merge

Telo metódy tlacListok

if (aCenaListka <= aVlozenaCiastka) {
// tlac listka – vynechane prikazy
aTrzba = aTrzba + aCenaListka;
aVlozenaCiastka = aVlozenaCiastka – aCenaListka;
} else {
System.out.println("Čiastka je menšia ako cena.");
}

Informatika 1

42

Vetvenie v jazyku Java – príkaz if

• úplný príkaz if

Informatika 1

43

if (podmienka) {
// príkazy vetvy, ak podmienka platí (true)
} else {
// príkazy vetvy, ak podmienka neplatí (false)
}

Vetvenie v jazyku Java – príkaz if

• neúplný príkaz if

Informatika 1

44

if (podmienka) {
// príkazy vetvy, ak podmienka platí (true)
}

Formulácia podmienky

• podobná matematickej forme
• logický výraz – jeho hodnota je typu boolean
• príklad:

• > (väčší ako) – relačný operátor
• ak je relácia splnená, výsledok má hodnotu true
• inak má hodnotu false

Informatika 1

45

aHodnotaMince > 0

Relačné operátory

• sú vždy binárne

• oba operandy sú aritmetické výrazy
• priorita relačných operátorov je nižšia ako

priorita aritmetických operátorov

• výsledok logického výrazu je vždy typu boolean

Informatika 1

46

prvýOperand operátor druhýOperand

Relačné operátory

matematika

Java

? > ?

x > y

? ≥ ?

x >= y

? < ?

x < y

? ≤ ?

x <= y

? = ?

x == y

? ≠ ?

x != y

Informatika 1

47

Blok

• časť kódu programu uzavretá do dvojice zátvoriek

{}

• bloky sa do seba vnárajú
• telo triedy obsahuje bloky – telá konštruktorov a

metód

• vetva v príkaze if tiež môže byť blok

Informatika 1

48

49

Informatika 1

Príkaz if bez bloku

if (podmienka)
// jeden príkaz – podmienka platí (true)
else
// jeden príkaz – podmienka neplatí (false)
// tu už začína nasledujúci príkaz

if (podmienka)
// jeden príkaz – podmienka platí (true)
// tu už začína nasledujúci príkaz

Riešenie nedostatkov – 2

chýba kontrola, či je vložená minca s kladnou
hodnotou
• použijeme vetvenie

– 1. vetva

• podmienka: hodnota vloženej mince > 0
• hodnota mince sa pripočíta

– 2. vetva

• podmienka: hodnota vloženej mince ≤ 0
• vypíše sa upozornenie

Informatika 1

50

Diagram aktivít – vlozMincu

Informatika 1

51

Telo metódy vlozMincu

if (paHodnotaMince > 0) {
aVlozenaCiastka = aVlozenaCiastka + paHodnotaMince;
} else {
System.out.println("Minca musi mat kladnu hodnotu.");
}

Informatika 1

52

Riešenie nedostatkov – 3

chýba kontrola, či je zadaná cena lístka kladná
• použijeme vetvenie

– 1. vetva

• podmienka: cena lístka > 0
• cena sa použije na inicializáciu atribútu

– 2. vetva

• podmienka: cena lístka ≤ 0
• atribút sa inicializuje preddefinovanou hodnotou

Informatika 1

53

Diagram aktivít – konštruktor

Informatika 1

54

Telo konštruktora AutomatMHD

if (paCenaListka > 0) {
aCenaListka = paCenaListka;
} else {
aCenaListka = 65;
}
aVlozenaCiastka = 0;
aTrzba = 0;

Informatika 1

55

Riešenie nedostatkov – 4

automat nevráti preplatok, ak sa vloží väčšia
čiastka, ako je cena lístka
• rozhranie automatu rozšírime o správu

vratZostatok

• triedu doplníme o novú metódu

Informatika 1

56

Automat vráti zostatok(1)

• ako automat pozná, koľko ma vrátiť?
• aVlozenaCiastka
• je metóda správna?

• treba nulovať aVlozenaCiastka.

Informatika 1

57

public int vratZostatok()
{
return aVlozenaCiastka;
}

Automat vráti zostatok(2)

• je teraz metóda správna?

• preklad je s chybou
• nulovanie sa nemôže vykonať

Informatika 1

58

public int vratZostatok()
{
return aVlozenaCiastka;
aVlozenaCiastka = 0;
}

Automat vráti zostatok(3)

• je teraz metóda správna?

• preklad je bez chýb
• automat nevráti nič

– metóda vráti nulu

Informatika 1

59

public int vratZostatok()
{
aVlozenaCiastka = 0;
return aVlozenaCiastka;
}

Automat vráti zostatok(4)

public int vratZostatok()
{
int zostatok;
zostatok = aVlozenaCiastka;
aVlozenaCiastka = 0;
return zostatok;
}

Informatika 1

60

Lokálna premenná

• definícia lokálnej premennej

• definícia a inicializácia lokálnej premennej

• rovnako ako

Informatika 1

61

int zostatok;

int zostatok = aVlozenaCiastka;

int zostatok;
zostatok = aVlozenaCiastka;

Premenná – spoločné vlastnosti

• atribúty, parametre a lokálne premenné sú

miesta v pamäti, v ktorých sú uložené hodnoty

• atribúty, parametre a lokálne premenné majú

vždy definovaný typ hodnoty, ktorú uchovávajú

• pokiaľ budeme o atribútoch, parametroch a

lokálnych premenných hovoriť všeobecne,
budeme hovoriť o premenných

Informatika 1

62

Atribúty, parametre a lokálne premenné(1)

• účel, poslanie

– atribút – uchováva stav objektu
– parameter – prenos spresňujúcej informácie
– lokálna premenná – dočasné uloženie určitej hodnoty

v rámci bloku

Informatika 1

63

Atribúty, parametre a lokálne premenné(2)

• definícia

– atribút – telo triedy, mimo konštruktorov a metód
– parameter – hlavička konštruktora alebo metódy
– lokálna premenná – v bloku (v tele konštruktora alebo

metódy)

Informatika 1

64

Atribúty, parametre a lokálne premenné(3)

• inicializácia

– atribút – v konštruktore v čase vytvárania inštancie
– parameter – v odosielanej správe ako skutočný

parameter

– lokálna premenná – v bloku (v tele konštruktora alebo

metódy)

Informatika 1

65

Atribúty, parametre a lokálne premenné(4)

• rozsah platnosti (viditeľnosť, použiteľnosť)

– atribút – v každom konštruktore alebo metóde
– parameter – v tele daného konštruktora alebo

metódy

– lokálna premenná – v bloku od miesta definície po

koniec bloku definície aj vo všetkých vnorených
blokoch.

Informatika 1

66

Atribúty, parametre a lokálne premenné(5)

• životný cyklus – existencia

– atribút – životný cyklus inštancie
– parameter – v čase vykonávania konštruktora alebo

metódy

– lokálna premenná – v čase vykonávania bloku od

miesta definície po koniec bloku, v ktorom bola
definovaná

Informatika 1

67

Vďaka za pozornosť