Program programovacím jazyce 1 package uvod; 3 class Main { 4 public static void main(string[ ] s) {

Jednoduchý program ● Program je postup (algoritmus), jak vyřešit nějaké zadání, zapsaný v programovacím jazyce. ● Příklad - vytisknout na výstup pozdrav Ahoj. ● Řešení (ve formě programu v Javě) je uloženo v souboru Main.java (čísla řádek nejsou součástí textu): 1 package uvod; 2 3 class Main { 4 public static void main(String[ ] s) { 5 System.out.println("Ahoj"); // prikaz tisku 6 } 7}

● Jediný příkaz je na řádce 5, přikazuje vytisknou text Ahoj. ● Vykonáním programu se provede právě tento jediný příkaz a na výstupu se objeví text Ahoj.

Projekt ● Program v jazyce Java se obvykle vytváří pomocí kolekce podpůrných aplikací, které jsou souhrnně nazývány IDE (Integrated Development Environment). ● Příklady IDE: NetBeans, Eclipse, IntelliJ IDEA, ... ● Program je v rámci IDE vytvářen jako tzv. projekt. U projektu rozeznáváme strukturu: ○ fyzickou - tj. jeho umístění v adresářích a souborech, ○ logickou - tj. části ze kterých se projekt skládá. ● Pozn.: Pojem projektu není součástí jazyka Java, ale pouze používaného IDE. Projekty se v různých IDE liší, což brání automatické přenositelnosti projektů mezi různými IDE. Zde pod projektem rozumíme projekt IDE NetBeans.

Struktura projektu ● Logická: ○ projekt se skládá z balíků (package). Projekt obsahuje vždy alespoň jeden balík, jehož jméno je stejné se jménem projektu, ○ balík se skládá z tříd (class), ○ třída se skládá z metod (method), ○ metoda se skládá z příkazů (statement). ● Fyzická: ○ projekt je adresář, jehož jméno je stejné se jménem projektu. Příklad: /NetbeansProjects/uvod ○ balík je podadresář adresáře projektu: /NetbeansProjects/ahoj/src/uvod. Stejně jako u projektu je jméno balíku stejné se jménem jeho adresáře ( označuje domovský adresář).

Zdrojové soubory ● Program se zapisuje ve formě textových souborů - tzv. zdrojových souborů (source) s příponou .java ● Jeden zdrojový soubor obsahuje jednu třídu a jmenuje se stejně jako tato třída. ● Rozložení programu do řádků je nepodstatné a slouží pouze k lepší čitelnosti programu. ● Zdrojové soubory jsou uloženy v adresáři balíku, do kterého třída patří. Zdrojový souboru Main.java bude uložen v adresáři balíku ahoj t. j.: /NetbeansProjects/ahoj/src/uvod ● Pozn.:Textovým souborem se míní soubor, který se skládá pouze ze znaků. Např. soubory .doc nejsou textové, protože kromě textu obsahují další formátovací informace.

Struktura zdrojového souboru ● Zdrojový kód se skládá ze znaků kódu Unicode , který obsahuje znaky prakticky všech národních abeced. ● Znaky se v programu sdružují do větších celků nazývaných lexikální symboly (token). ● Lexikální symboly se dělí na: ○ klíčová slova - static, void, ... ○ speciální symboly - závorky, tečky, středníky, čárky, atd. a dvojznaky: ++, <<, +=, ... ○ jména - pozdrav, System, out, println ○ literály - "Ahoj", 99, 3.14., 'X' static void pozdrav() { System.out.println("Ahoj"); }

Komentáře ● Mezi lexikálními symboly může být uveden libovolný počet tzv. bílých mezer (white space), které nemají žádný vliv na funkci programu - slouží jen k lepší čitelnosti. Jsou to: ○ mezery a tabulátory, ○ konce řádek, ○ komentáře - tj. vysvětlivky ● Komentář je libovolný text ve formě: 1. jednořádkové: // cokoliv do konce řádky 2. víceřádkové: /* cokoliv až do dvojznaku: */

● Pozn.: Mezi klíčovými slovy a jmény musí být alespoň jedna bílá mezera.

Pojem "skládání" ● Projekt se skládá z jednotlivých částí, což se vyjadřuje rozdílnými způsoby: ○ Projekt se skládá z balíků, které se umístí do stejnojmenných podadresářů projektu. Adresář balíku uvod je: /NetbeansProjects/uvod/src/uvod ○ Balík se skládá z tříd, které jsou deklarovány ve zdrojovém souboru začínajícím klauzulí se jménem balíku: package uvod; Zdrojový soubor se jmenuje stejně jako třída s příponou . java a je umístěn v adresáři balíku. ○ Třída se skládá z metod, které jsou zapsány mezi složenými závorkami ohraničujícími tělo třídy. ○ Metoda se skládá z příkazů, které jsou zapsány mezi složenými závorkami ohraničujícími tělo metody.

Metoda ● Je část programu, která obsahuje řešení (algoritmus) nějaké dílčí úlohy. ● Metoda se skládá z: ○ hlavičky (header) - obsahuje (kromě jiného) jméno metody, ○ těla (body) - obsahuje posloupnost příkazů ohraničenou složenými závorkami, jejichž postupným vykonání se úloha řeší. ● Příklad metody, která vytiskne pozdrav česky a potom anglicky: static void tiskniAhojDvojjazycne() { // hlavička System.out.println("Ahoj"); // tělo System.out.println("Hello"); }

● Pozn.: Profesionální program mívá i tisíce metod.

Příkaz volání metody ● Aby se začaly vykonávat příkazy v těle metody musí být metoda tzv. zavolána (call). ● Metoda se volá příkazem volání metody, takto: jméno_metody ( ) ; ● Metodu ve které je uveden příkaz volání nazýváme volající (caller), zatímco metodu, jejíž jméno je uvedeno v příkazu nazýváme volanou (callee). ● Provedením příkazu se dočasně přeruší provádění volající metody a začne se provádět metoda volaná. ● Příklad - metoda main volá metodu tiskniAhojDvojjazycne: public static void main (String[ ] args) { tiskniAhojDvojjazycne(); }

Metoda main ● Metoda main má výsadní postavení. Vykonání projektu (v NetBeans akce "Run Main Project") znamená provedení právě metody main: ○ program bez metody main nelze provést, ○ hlavička metody main je závazná, tzn. musí být zapsána doslova uvedeným způsobem, ○ metoda main by sama neměla obsahovat žádný algoritmus. V těle metody main by měl být pouze příkaz volání jiné metody, která sama úlohu řeší. ● Běžná metoda má v programu smysl pouze tehdy, pokud ji jiná metoda volá. Metoda main je jediná metoda programu, kterou žádná jiná metoda nevolá.

Procedurální paradigma ● Procedurální paradigma je klasický (předobjektový), avšak stále platný styl programování. ● Při jeho použití se úlohu snažíme rozdělit na co nejvíce jednoduchých podúloh a pro řešení každé dílčí podúlohy napsat vhodnou metodu. ● Metody se potom vzájemně volají (i opakovaně) k vyřešení celé úlohy. ● Příklad.: Vytisknout dvakrát za sebou dvojjazyčný pozdrav: public static void main(String[ ] args) { tiskniAhojDvojjazycne(); tiskniAhojDvojjazycne(); }

● Pozn.: V klasických neobjektových jazycích (FORTRAN, C, Pascal) se metody nazývají procedury resp. funkce.

Příklad projektu prvocisla ● Úkol: vytiskni 3 nejmenší prvočísla. ● Řešení: projekt prvocisla, který bude obsahovat jediný balík prvocisla a v něm jediný zdrojový soubor Main.java s jedinou třídou Main. Ukol je vyřešen samostatnou metodou tiskni3Prvocisla volanou v metodě main: package prvocisla; class Main { public static void main(String [ ] args ) { tiskni3Prvocisla(); } static void tiskni3Prvocisla() { System.out.println(2); System.out.println(3); System.out.println(5); } }

Přepis příkladů z přednášek (1/2) ● Příklady z přednášek nejsou záměrně studentům k dispozici přímo ve formě hotových projektů, protože jejich ruční přepis do NetBeans je užitečné cvičení. ● Pro přepis je možno zvolit různé strategie: 1. Každý příklad si psát do samostatného projektu a tyto projekty si ukládat do vhodných adresářů. ■ výhoda: jednoduchost - NetBeans automaticky vytvoří pro každý projekt balík a třídu Main s metodou main, ■ nevýhoda: menší přehlednost (desítky projektů). 2. Vytvořit pouze jeden projekt pro celý předmět a pro jednotlivé příklady si v projektu vytvářet balíky a třídy (viz sbírka příkladů exalg). ■ nevýhoda - v projektu bude více metod main v různých třídách, takže nelze vykonat celý projekt najednou.

Přepis příkladů z přednášek (2/2) ● Kompromis: 1. Pro každé přednášku/téma vytvořte nový projekt s automaticky vytvořenou třídou Main a s automaticky vytvořenou metodou main. 2. Všechny příklady (tedy metody) k tématu si pište za sebou do třídy Main. 3. Každou metodu zavolejte samostatným příkazem z metody main. 4. Protože se metody v jedné třídě musí jmenovat různě, je potřeba odlišit různé varianty příkladu např. pořadovým číslem ve jménu metody: void tiskni3Prvocisla() { ... } void tiskni3Prvocisla2() { ... }

Hodnoty ● Hodnota (value) - základní element informace, se kterou program pracuje. ● Hodnoty se podle svého charakteru dělí do typů: ○ celočíselné - typ int, ○ "desetinné" - typ double, ○ znakové - typ char, ○ logické - typ boolean, ○ krátké texty neboli řetězy - String. ● Typy jsou označeny klíčovými slovy (int, double, ...) ● Výjimka: String není klíčové slovo ale jméno třídy.

Literály ● Hodnoty zapsané přímo v programu se nazývají literály. ● Každý typ má vlastní formát svých literálů: ○ int - posloupnost dekadických číslic, ○ double - dekadické číslice, desetinná tečka odděluje destinnou část, ○ char - jeden znak uzavřený v apostrofech, ○ boolean - klíčová slova true (pravda), false (nepravda), ○ String - posloupnost (i prázdná) znaků v uvozovkách. static void tiskniLiteraly() { System.out.println( 2010 ); System.out.println( 3.14 ); System.out.println( 'X' ); System.out.println( false ); System.out.println( "Algoritmizace" ); }

Výrazy ● Hodnoty v programu: 1. jsou zapsány přímo jako literály, 2. jsou čteny ze vstupních zařízení (klávesnice, soubory,..), 3. vznikají výpočtem výrazů (expression). ● Výraz je jednoduchý algoritmus pro výpočet nové hodnoty z hodnot známých. ● Příklad výrazu - výpočet kombinačního čísla 5 nad 3: (5 * 4 * 3) / (3 * 2 * 1) ● Výraz se skládá z: ○ operandů - např. literálů, ○ operátorů - tj. speciálních symbolů a klíčových slov, která označují operace (většinou, ale nejenom, matematické), ○ závorek - určujících pořadí výpočtu.

Aritmetické operátory ● Aritmetické operátory vyjádřují tyto symboly: ○ + sčítání anebo spojování řetězů, ○ - odečítání anebo změna znaménka, ○ * násobení, ○ / dělení. ● Operátory mají obvyklou prioritu známou z matematiky (výraz: 5 + 4 * 3 má hodnotu 17 a nikoliv 27). ● Pokud je alespoň jeden operand operátoru + řetěz, označuje operátor operaci spojování řetězů: System.out.println("Zitra" + "bude" + "hezky");

vypíše na výstup: Zitrabudehezky

● Operátor / se pro oba celočíselné operandy chápe jako celočíselné dělení: 5/2 je 2, 5/3 je 1, 5/6 je 0

Relační operátory ● Relační operátory předepisují relační (srovnávací) operace mezi dvěma operandy. Vyjádřují je tyto symboly: ○ == rovná se, ○ != nerovná se, ○ > větší než, ○ < menší než, ○ >= větší nebo rovno, ○ <= menší nebo rovno. ● Porovnávají se jimi celočíselné, znakové i desetinné operandy a jejich výsledkem je hodnota typu boolean tj. true nebo false. ● Příklad: System.out.println(5 > 3); // vytiskne se true

Proměnné ● Proměnná (variable) je úsek vnitřní paměti počítače (jeden nebo více bytů), který je dočasně rezervován pro program. ● Proměnná má schopnost uchovávat vloženou hodnotu a to tak dlouho, dokud program tuto hodnotu nezmění. ● Rezervace proměnné se provádí deklarací, která obsahuje následující informace: ○ typ hodnoty, kterou bude proměnná uchovávat, ○ jméno proměnné, pod kterým bude proměnná dále dostupná, ○ volitelně počáteční uloženou hodnotu: int x = 1; ● Proměnná může být operandem ve výrazu. Hodnotou proměnné je hodnota do ní uložená. ● Pozn.: Norma Javy rozeznává 7 druhů proměnných, které se liší svými vlastnostmi - viz dále.

Lokální proměnná (1/2) ● Lokální proměnná slouží k uchování hodnoty pouze po dobu provádění metody. ● Lokální proměnná se deklaruje deklaračním příkazem: int i; resp. int i = 10; ● Provedením uvedeného příkazu se v aktuální metodě zavede nová proměnná i, rezervují se pro ni čtyři byty v paměti a v druhém případě se do proměnné uloží počáteční hodnota 10. ● Příklad: static void vytiskniKvadratPi() { double pi = 3.14; System.out.println("Kvadrat pi: " + pi * pi); }

Lokální proměnná (2/2) ● Lokální proměnná je dostupná (tj. použitelná) pouze v té metodě, ve které byla deklarována (odtud její název). Lokální proměnnou tedy nelze použít pro předávání hodnot z jedné metody do druhé. ● Po ukončení metody lokální proměnná přestává existovat a její hodnota se ztrácí. ● Zánikem lokální proměnné se paměťové místo v paměti počítače, které bylo až dosud pro proměnnou rezervováno, uvolní a může být použito k jinému účelu.

Přiřazení ● Hodnotu proměnné je možno změnit přiřazením (assignment), které má obecný tvar proměnná = výraz ; ● Provedením příkazu se původní hodnota proměnné přepíše hodnotou novou a původní hodnota je nenávratně ztracena. ● Ve výrazu na pravé straně může být proměnná sama přítomna jako operand, takže přiřazovací příkaz často hodnotu v proměnné pouze pozmění: static void tiskniKvadraty() { int i = 2; System.out.println(i * i);// tiskne 4 i = i + 1; // zvětší hodnotu i o 1 System.out.println(i * i);// tiskne 9 }

Funkce ● Funkce je speciální metoda, která je zakončena příkazem return. ● Obecný tvar příkazu je: return výraz; ● V hlavičce funkce je místo klíčového slova void (tj. nic) uveden typ výrazu v příkazu return: static double dvakratPi() { // funkce typu double return 2 * 3.14; }

● Hodnota výrazu v příkazu return se nazývá návratová hodnota funkce. ● Volání funkce může být operandem výrazu. Hodnotou tohoto operandu je hodnota výrazu v příkazu return: double ctyrikratPi = 2 * dvakratPi();

Volající a volaná metoda ● Příkaz return umožňuje předávat hodnotu z volané funkce do volající metody: 1 package kruznice; 2 class Main { 3 // volající metoda 4 public static void main(String[] args) { 5 double obsah = obsahKruznice3(); // volání 6 System.out.println( 7 "Obsah kruzniceo polomeru 3 je " + obsah); 8 } 9 // volaná funkce 10 static double obsahKruznice3() { 11 double polomer = 3; 12 return 3.14 * polomer * polomer; 13 } 14 }

Krokování programu ● Skutečný průběh běhu předcházejícího programu po jednotlivých řádcích: 4 5 11 12 5 6 7 8

public static void main(String[] args) { ... = obsahKruznice3(); double polomer = 3; return 3.14 * polomer * polomer; double obsah = ...; System.out.println( "Obsah kruzniceo polomeru 3 je " + obsah); }

● Všiměte si, že řádek 5 se provádí nadvakrát: nejprve s v něm volá funkce obsahKruznice3 a po jejím dokončení se výsledek přiřazuje do proměnné. ● Uvedený postup výpočtu je možno sledovat v NetBeans, pokud se program spustí v tzv. krokovacím režimu (Debug Main Project).

Parametry ● Příkaz return umožňuje předat hodnotu z volané funkce do volající (připomínáme, že k tomuto účelu nelze použít lokální proměnnou). ● Pro předávání hodnot z volající funkce do volané slouží mechanismus parametrů. ● Parametr je druh proměnné, do které se hodnota přiřadí ve volající metodě a potom je dostupná v metodě volané. ● Deklarace parametru se provádí v kulatých závorkách v hlavičce volané metody: static void tiskniPozdrav(final String pozdrav) { System.out.println(pozdrav); }

● Přiřazení hodnoty do parametru se provádí ve volající metodě v příkazu volání metody: tiskniPozdrav("Ahoj"); // pozdrav = "Ahoj"

Parametr funkce ● Často se v jedné metodě (funkci) kombinuje předávání hodnot z volající metody pomocí parametrů s vracením výsledku příkazem return: class Main { public static void main(String[ ] args) { double polomer = 1.2; double obsah = obsahKruhu(polomer); System.out.println("Obsah kruhu o polomeru " + polomer + " je " + obsah); } double obsahKruhu(final double polomer) { return 3.14 * polomer * polomer; } }

Vlastnosti parametru ● Porovnání vlastností lokální proměnné a parametru: lokální proměnná

parametr

vzniká

deklaračním příkazem

příkazem volání metody

počáteční hodnota

inicializační část deklaračního příkazu

argument v příkazu volání

je metodicky změna hodnoty přiřazovacím příkazem nevhodná zaniká

ukončením volané metody

ukončením volané metody

Terminologie ● Ve výkladu je potřeba odlišit parametr, deklarovaný v hlavičce metody, od hodnoty, která je mu přiřazena při volání metody. Je možno použít dvě terminologie: výraz resp. jeho hodnota v deklarovaný parametr příkazu volání metody 1. terminologie

formální parametr

skutečný parametr

2. terminologie

parametr

argument

Java API ● API (Application Program Interface) - rozhraní aplikačních programů - rozsáhlá kolekce balíků, tříd a metod, které javovské aplikace mohou využívat. ● Dokumentace (tzv. javadoc) je dostupná on-line: Java SE API Documentation , (lze je stáhnout ve formátu HTML). ● Java API pokrývá všechny podstatné softwarové oblasti: ○ vstupy a výstupy, ○ síťování, ○ grafiku, ○ databáze, ○ paralelismy, ○ správu dat, ○ atd.

● Pozn.: Dříve používaný termín pro API je knihovny. ● Pozn.: Schopnost psát Java aplikace je do značné míry dána dobrou znalostí Java API.

Užitečné metody a konstanty ● Matematické - deklarované ve třídě java.lang.Math: ○ static double Math.random()- náhodné číslo z intervalu <0..1>, ○ static double Math.sin(double x) - funkce sinus (obdobně cos, tan, exp a další trigonometrické funkce), ○ static double Math.sqrt(double x)- druhá odmocnina, ○ static double Math.abs(double x) - absolutní hodnota, ○ double Math.PI - číslo pí, ○ double Math.E - základ přirozených logaritmů. ● Výstupní: ○ void System.out.println(String x) - tisk řetězu na výstup a odřádkování, ○ void System.out.print(String x) - pouze tisk.

Konvence zápisu jmen ● Každá proměnná, parametr, metoda, třída a balík je pojmenována jménem. ● Jména mohou být: ○ jednoslovná: ■ metody a proměnné jsou psána malými písmeny: sin, out, println, ... ■ třídy - počáteční velké, ostatní malé: System, Math, ... ■ konstanty - všechna písmena velká: PI, ○ víceslovná: ■ metody, proměnné, třídy - každé další slovo začíná velkým písmenem: fillOval, SecurityManager (tzv. velbloudí konvence), ■ konstanty - slova jsou oddělena podtržítkem: MAX_VALUE. ● Konvence je třeba striktně dodržovat, protože na nich závisí čitelnost programů!!!

Syntaktická pravidla (1/2) ● Správný program musí odpovídat specifikaci jazyka Java . Požadavky uvedené ve specifikaci lze rozdělit na ○ syntaktické - určují přijatelný "tvar" programu, ○ sémantické - určují správný význam programu. ● Syntaktické požadavky jsou uváděny ve formě syntaktických pravidel. Kolekce všech pravidel se nazývá gramatika. ● Každé syntaktické pravidlo říká, že nějaká jazyková konstrukce se skládá z jiných jazykových konstrukcí a z lexikálních symbolů. ● Příklad syntaktického pravidla ReturnStatement pro jazykovou konstrukci příkazu return: ReturnStatement: return Expression opt ;

Syntaktická pravidla (2/2) ● Uvedené pravidlo říká, že příkaz return se skládá z klíčového slova return následováného nepovinně (optionally) jakýmkoliv výrazem a povinně středníkem. ● Nepovinná část je označená indexem opt . ● Všechny následující příkazy jsou tedy syntakticky správné: return 0x10; return (10); return i * j; return "Ahoj"; return Math.random(); ● Syntaktická pravidla jsou doplněna mnoha sémantickými požadavky. Pro příkaz return např. platí požadavek, že výraz může být vynechán pouze v metodách, které nevracejí hodnotu (tzv. procedurách) a typ výrazu musí odpovídat typu uvedenému v hlavičce metody (funkce).

Složené příkazy ● Složené příkazy jsou skládají z jednoho nebo více jiných příkazů a používají se pro řízení programu. Jedná se o podmíněné příkazy, příkazy cyklu, příkazy pro ošetření výjimek atd. ● Nejjednodušší složený příkaz je blok, který sdružuje více příkazů tak, aby v programu tvořily jediný celek: Block: { Statements opt } ● Příklad: { i = i + 1; return i; } ● Pozn.: tělo metody je ve skutečnosti tvořeno příkazem blok.

Příkaz if ● Příkaz if provádí část programu podmíněně dle platnosti nějaké podmínky: IfThenStatement: if ( Condition ) Statement ● Condition (podmínka) je výraz, který podle sémantických pravidel musí být typu boolean, tj. jeho hodnotou musí být true nebo false. ● Vnořený příkaz (Statement) se provede právě tehdy, má-li podmínka hodnotu true. ● Příklad: if (x > y) { System.out.println(x+" je vetsi nez "+y); } ● Pozn.: vnořený příkaz se obvykle (nikoli povinně) zapisuje ve formě bloku tj. ve složených závorkách.

Detekce chyb při výpočtu ● V průběhu výpočtu programu může docházet k mnohým chybám, které znemožňují normální pokračování. ● Část chyb detekuje a ošetřuje Java sama, ale část musí být explicitně ošetřena programem. ● Při detekci chyby může metoda reagovat následujícími způsoby: 1. pokračovat ve výpočtu např. s chybnými hodnotami zcela nevhodné a nebezpečné řešení, 2. ukončit okamžitě výpočet - korektní, ale drastické řešení, 3. ukončit výpočet a vrátit domluvenou hodnotu (např. -1), která signalizuje chybu - není ideální, ale některé jazyky jiné neumožňují, 4. vyhodit vyjímku pomocí příkazu throw.

Příkaz throw ● Příkaz throw ukončuje výpočet metody, ve které byl vykonán a přenáší řízení (tj. pokračuje) do takového místa v programu, které je schopné nastalou chybovou situaci řešit. ● Pokud vhodné místo v programu není, je běh programu ukončen. ● Příkaz throw má syntaxi: ThrowStatement: throw Expression ; kde Expression je: ○ při detekci nevhodných argumentů předaných metodě: new IllegalArgumentException( "Zpráva o chybě") ○ při jiné chybě: new RuntimeException("Zpráva o chybě");

Detekce chybného argumentu ● Varianta v Javě: static double obsahKruhu(double polomer) { if (polomer < 0) throw new IllegalArgumentException( "Polomer musi byt nezaporny"); return Math.PI * polomer * polomer; } ● Pozn.: pro porovnání varianta v jazyku C: double obsahKruhu(double polomer) { if (polomer < 0) return -1; return PI * polomer * polomer; } V jazyku C je nutno po každém zavolání metody kontrolovat, zda vrácená hodnota neindikuje chybu.

Přikaz ifelse ● Příkaz ifelse je přirozené rozšíření příkazu if o tzv. else část, která se vykoná, pokud je podmínka v příkazu nepravdivá (má hodnotu false): IfThenElseStatement: if ( Condition ) Statement else Statement ● Příklad: static int max(final int x, final int y) { if (x > y) return x; else return y; } ● Pozn.: protože je v then části uveden příkaz return, který ukončuje metodu, je předcházející metoda ekvivalentní s: static int max2(final int x, final int y) { if (x > y) return x; return y; }

Příkazy cyklu ● Příkazem cyklu (for, while, do) se předepisuje opakované vykonávání vnořeného příkazu. ● Syntaxe příkazu for: ForStatement: for ( LocalVariableDeclaration opt ; Condition opt ; ForUpdate opt ) Statement ● Nepovinná část LocalVariableDeclaration umožňuje deklarovat tzv. řídící proměnnou cyklu. ● Nepovinná část ForUpdate má tvar přiřazení nové hodnoty do řídící proměnné. ● Část příkazu for v kulatých závorkách se nazývá hlavička cyklu a vnořený příkaz (Statement) se nazývá tělo cyklu. Tělo cyklu se obvykle zapisuje jako blok, byť je tvořeno jen jedním příkazem.

Chování příkazu for 1. je-li uvedena, deklaruje se a inicializuje řídící proměnná cyklu, 2. vyhodnotí se podmínka, a pokud má hodnotu false, cyklus se ukončí (není-li podmínka uvedená, chápe se jako by měla hodnotu true), 3. provede se tělo cyklu, 4. provede se ForUpdate, 5. pokračuje se krokem 2. ● Pozn.: Má-li tedy podmínka při prvním vyhodnocení hodnotu false, neprovede se tělo příkazu for ani jednou. ● Příklad: static void tiskniPrirozenaCislaDoN(final int n) { for (int i = 1; i <= n; i = i + 1) { System.out.println(i); } }

Iterace ● Iterace se nazývá postup, kdy požadovaný výsledek dostáváme postupným mnohonásobným opakováním stejného kroku. Příkaz cyklu nutno užít všude tam, kde je třeba naprogramovat iteraci a: 1. počet opakování není znám v době překladu, 2. počet opakování je sice znám, ale je příliš velký. ● Příklad - počet potřebných iterací je malý a konstantní: static double xNaTreti(final double x) { double mocnina = x; mocnina = mocnina * x; mocnina = mocnina * x; return mocnina; }

Použití příkazu for ● Počet iterací je velký: static double xNa100(final double x) { double mocnina = 1; for (int i = 0; i < 100; i = i + 1) { mocnina = mocnina * x; } return mocnina; }

● Počet iterací je proměnný: static double xNaN(final double x, final int n) { double mocnina = 1; for (int i = 0; i < n; i = i + 1) { mocnina = mocnina * x; } return mocnina; }

Řídící proměnná ● Řídící proměnnou cyklu lze užít k výpočtům v těle cyklu: static int faktorial(final int n) { if (n < 0) throw new IllegalArgumentException( "Faktorial neni definovan pro zaporna cisla"); int f = 1; for (int i = 2; i <= n; i = i + 1) { f = f * i; } return f; }

● Pozn.: řídící proměnnou cyklu lze v těle cyklu i modifikovat, avšak je to nevhodný styl programování.

Řídící proměnná jako počítadlo iterací ● Pokud příkaz cyklu počítá iterace jsou možná různá řešení: static void opakujNkrat(final int n) { // inkremetace řídící proměnné od 0 for (int i = 0; i < n; i = i + 1) { System.out.println(i); } // inkremetace řídící proměnné od 1 for (int i = 1; i <= n; i = i + 1) { System.out.println(i); } // dekremetace řídící proměnné for (int i = n; i >= 1; i = i - 1) { System.out.println(i); } }

Zacyklení ● Při nevhodném návrhu příkazu cyklu se program může "zacyklit " - tzn. příkaz cyklu provádí iterace nekonečně. Tato situace (obvykle chyba) se nazývá věčný cyklus (forever loop). ● Příklad metody, která se pro záporný argument n zacyklí, protože i nikdy nebude záporné: static opakujNkrat(final int n) { for (int i = 0; i != n; i = i + 1) { . . . // toto se má opakovat } }

● Pozn.: ve skutečnosti se v důsledku vlastností celočíselné aritmetiky zastaví po cca 4 miliardách iterací. ● Lepší řešení počítá se záporným n: static opakujNkrat(final int n) { for (int i = 0; i < n; i = i + 1) . . . }

Validace hodnot parametrů ● Je třeba kontrolovat, aby hodnoty, se kterými cyklus pracuje, byly korektní. Dříve uvedená metoda xNaN by dávala chybné výsledky pro záporná n. Oprava: static double xNaNezapN(final double x, final int n) { if (n < 0) throw new IllegalArgumentException("Zaporne n"); double mocnina = 1; for (int i = 0; i < n; i = i + 1) { mocnina = mocnina * x; } return mocnina; }

● Obecnou mocninu je lépe řešit samostatnou metodou: static double xNaN(final double x, final int n) { double mocnina = xNaNezapN(x, Math.abs(n)); if (n < 0) return 1/mocnina; return mocnina; }

Příkazy while a do ● Příkaz while je ekvivalentní příkazu for s prázdnou částí LocalVariableDeclaration a ForUpdate: WhileStatement: while ( Condition ) Statement ● Příkaz do je obdobou příkazu while, avšak podmínka je uvedena až na konci příkazu: DoStatement: do Statement while ( Condition ) ; ● Důsledek: na rozdíl od příkazů for a while se tělo příkazu do vykoná vždy alespoň jednou. ● Pozn.: příkaz do je jediný složený příkaz zakončený středníkem. ● Pozn.: Ježto příkazy while a do nemají část update hrozí u nich zvýšené riziko chyby zacyklení, které je nejčastěji způsobeno opominutím modifikovat řídící proměnnou cyklu.

Metoda versus cyklus ● Cyklus stejně jako metoda umožňuje při výpočtu opakovaně provádět část kódu. Porovnání obou prostředků:

metoda

cyklus má jméno bezejmenný provedení se vyvolá kdykoliv provedení se řídí hlavičkou příkazem volání metody cyklu pracuje vždy s novou sadou lokálních proměnných a parametrů

pracuje se stále stejnou sadou proměnných

Úvod do časové složitosti ● Velmi důležitým parametrem kvality programu je jeho rychlost. Ta je nepřímo úměrná počtu příkazů, které program vykoná během svého provádění a ten je úměrný počtu iterací v cyklech. Cykly jsou obvykle tím místem v programu, kde je jeho provádění možno urychlit: static double xNaNLepe(final double x, final int n) { if (n < 0) throw new IllegalArgumentException(); if (n == 0) return 1; double moc = 1; double moc2 = x; // řídící proměnná se po každé iteraci // nedekremetuje ale dělí dvěma for (int i = n; i >= 2; i = i / 2) { if (i % 2 == 1) // jestliže i je liché moc = moc * moc2; moc2 = moc2 * moc2; } return moc * moc2; }

Pole ● Velmi často je potřeba pracovat v programu s posloupností hodnot stejného typu jako je například posloupnost naměřených teplot, posloupnost jmen, posloupnost cen akcií, atd. ● Pro jednotlivé hodnoty nelze deklarovat samostatné proměnné, protože: 1. posloupnost je příliš velká, 2. v době návrhu programu není znám počet jejích prvků, 3. se všemi členy je potřeba provádět stejné operace, což by bylo obtížné, pokud by každý člen byl uložen v samostatné proměnné. ● Z uvedených důvodů má proto každý programovací jazyk konstrukci pole (array). ● Pozn.: termín pole je v češtině historický a neodpovídá anglickému termínu array (sada, šik, seskupení, atd.).

Typ pole ● Pole je konečná posloupnost proměnných stejného typu. Jednotlivé proměnné se nazývají prvky pole. Prvky pole jsou proměnné. ● Opakování druhů proměnných: 1. lokální proměnná, 2. parametr, 3. prvek pole. ● Vlastnosti pole se určují tzv. typem pole: ArrayType: Type [ ] ● Type v ArrayType může být jakýkoliv typ a určuje typ prvku pole. ● Příklad: int[], boolean[], double[], String[] ● Pozn.: na rozdíl od C, Pascal, atd. neurčuje v Javě typ pole počet prvků pole.

Vytvoření pole ● Pole se vytváří inicializátorem v deklaraci proměnné typu pole, který má tvar: new Typ [ Expression ] ● Expression musí být výraz typu int a jeho hodnota (nesmí být záporná) určuje počet prvků pole a nazývá se délka pole. ● Expression nemusí být konstantní a v tom případě se délka pole určuje až za běhu programu. ● Příklad: int[] pole10Cisel = new int[10]; int pocetChlapcu = . . .; int pocetDivek = . . .; String[] poleJmen = new String[pocetChlapcu + pocetDivek];

● Pokud je hodnota délky záporná hlásí se chyba NegativeArraySizeException.

Indexace ● Přístup k prvku pole se provádí tzv. indexací. Za pole se v hranatých závorkách uvede pořadové číslo (tzv. index) požadovaného prvku pole: ArrayExpression [ IndexExpresion ] ● IndexExpression musí být výraz typu int a jeho hodnota musí být v rozsahu 0 až délka_pole - 1 (indexy se vždy počítají od 0). ● Pokud je hodnota indexu mimo rozsah, hlásí program chybu: IndexOutOfBoundsException. ● Pozn.: Mechanismus indexace tvoří novou kvalitu programování. Protože index je výraz, jehož hodnota se počítá až při výpočtu, je indexací možno zapsat do programu přístup k proměnné, která se určí až v době výpočtu! Podobný mechanismu tvoří reference (viz dále).

Pole jako parametr ● Pole je možno předávat jako parametr. Deklarace parametru pole se provádí obdobně jako deklarace jednoduchých parametrů. ● Příklad: - metoda main (vstupní bod programu) má nadeklarován parametr pole řetězů, které obsahuje parametry programu zadané z příkazové řádky: public static void main(String[] args) { System.out.println("Prvni parametr programu je:" + args[0]); }

● Pozn.: Pokud uvedenému programu nezadáme argumenty, je zkončen s chybou IndexOutOfBoundsException, protože pole args bude mít délku 0. Parametry programu je možno v NetBeans nastavit takto: kursor na projekt, kliknutí pravého tlačítka, v menu vybrat Properties, v dialogu vybrat Run, nastavit položku Arguments.

Délka pole ● Na rozdíl od klasických programovacích jazyků není délka pole (tj. počet jeho prvků) součástí typu pole (tj. konstantní hodnota zadaná v programu), ale je to hodnota známá až za běhu programu. ● Délka pole se získá z pole zápisem: ArrayExpression . length ● Příklad výpis pole na jednu řádku: static void vypisPole(final int[] pole) { System.out.print('['); for (int i = 0; i < pole.length; i = i + 1) { System.out.print(pole[i]); if (i < pole.length - 1) // za posledním není čárka System.out.print(", "); System.out.println(']'); } }

Inicializace pole ● Po vytvoření číselného pole jsou jeho prvky automaticky inicializovány na hodnotu 0, boolovského pole na hodnoty false. ● Alternativní způsob vytvoření pole je inicializátorem (ArrayInitalizer) ve tvaru posloupnosti výrazů ve složených závorkách: public static void main(String[] args) { int[] polePrvocisel = {2,3,5,7,11,13,17,19}; vypisPole(polePrvocisel); }

● Pole je též možné inicializovat konstruktorem: new Typ [ ] ArrayInitalizer ● Na rozdíl od samotného inicializátoru, je konstruktor možno použít i jako skutečný parametr při volání metody: vypisPole(new int[] {2,3,5,7,11,13,17,19});

Cyklus foreach ● Cyklus foreach je zkrácený zápis cyklu for, který se dá použít pouze tehdy, jestliže: 1. chceme projít celé pole od 0-tého do posledního prvku, 2. prvky pole nepotřebujeme modifikovat. EnhancedForStatement: for (Type Identifier : Expression ) Statement ● Expression musí být pole a Type musí být stejného typu jako prvky pole. ● Příklad: static void double soucet(final double[] pole) { double sum = 0; for (double prvek : pole) { sum = sum + prvek; } return sum; }

Pole jako návratovová hodnota ● Pole je možno vracet jako výsledek funkce. Typ metody je potom typ pole. ● Příklad pole náhodných hodnot: static double[] nahodnePole(final int delka) { double[] nahodne = new double[delka]; for (int i = 0; i < nahodne.length; i = i + 1) { nahodne[i] = Math.random(); } return nahodne; }

● Příklad obrácení pole: static char[] vytvorObracenePole(final char[] pole){ char[] obracene = new char[pole.length]; for (int i = 0; i < pole.length; i = i + 1) { obracene[i] = pole[pole.length - 1 - i]; } return obracene; }

Metody pro pole v API (1/2) ● Třída java.util.Arrays obsahuje užitečné metody pro práci s poli. Dále uvádíme pouze metody pro pole s typem elementu int, avšak obdobné metody jsou definovány i pro ostatní typy: ○ static String toString(int[] a)- vrátí textovou reprezentaci hodnoty pole, ○ static void sort(int[] a) - uspořádá pole vzestupně podle velikosti, ○ static void fill(int[] a, int val) - vyplní pole hodnotou val, ○ static boolean equals(int[] a, int[] a2) - porovná dvě pole, ○ static int binarySearch(int[] a, int key) - nalezne index prvního prvku pole, který má hodnotu key, nebo vrátí zápornou hodnotu. Pole musí být napřed uspořádáno metodou sort.

Metody pro pole v API (2/2) ● Metoda pro kopírování prvků z jednoho pole do druhého je deklarována ve třídě java.lang.System: static void arraycopy(src, int srcPos, dest, int destPos, int length) ○ src - libovolné pole, ○ srcPos - index prvního kopírovaného prvku, ○ dest - pole do kterého se kopíruje, ○ destPos - index, na který se kopíruje, ○ length - počet kopírovaných prvků. ● Příklad sloučení dvou polí řetězů: static String[] sluc(String[] a, String[] b) { String[] res = new String[a.length + b.length]; System.arraycopy(a, 0, res, 0, a.length); System.arraycopy(b, 0, res, a.length, b.length); return res; }

Násobný parametr ● Poslední formální parametr metody může být deklarován jako násobný (variable arity): LastFormalParameter: Type ... opt Identifier ● Takový parametr se v těle metody chápe stejně jako by byl nadeklarován typu pole: Type[ ]. ● Při volání metody je možno za tento parametr uvést seznam hodnot, které se stanou prvky pole: public static void main(String[] args) { System.out.println(max(1,5,2,8)); // vytiskne 8 } static int max(int ... prvky) { int max = Integer.MIN_VALUE; for (int prvek : prvky) if (prvek > max) max = prvek; return max; }

Pole jako tabelovaná funkce ● Obsah pole může mít různou interpretaci, např. jako hodnoty tabelované funkce. ● Příklad - určitý integrál lichoběžníkovou metodou: static double urcityIntegral( final double[] hodnotyFunkce, final double krok) { if (hodnotyFunkce.length == 0) return 0; int poslIndex = hodnotyFunkce.length - 1; double suma = hodnotyFunkce[0] / 2; for (int i = 1; i < poslIndex; i = i + 1) { suma = suma + hodnotyFunkce[i]; } suma = suma + hodnotyFunkce[poslIndex] / 2; return suma * krok; }

Předávání pole referencí ● Pokud předáváme pole jako parametr, může volaná metoda změnit obsah pole a změna se projeví ve volající metodě. Je to proto, že parametr pole se předává referencí (odkazem) - viz dále. ● Příklad - obrať pořadí prvků pole (srovnej vytvorObracenePole): static void obratPole(final char[] poleZnaku) { for (int i = 0; i < poleZnaku.length/2; i = i+1) { // nejprve je potřeba uschovat hodnotu char pom = poleZnaku[i]; poleZnaku[i] = poleZnaku[poleZnaku.length-1-i]; poleZnaku[poleZnaku.length-1-i] = pom; } }

● Pozn.: algoritmus prohazuje první s posledním, druhý s předposledním atd. Algoritmus se musí zastavit v půlce pole, aby prvky nevrátil na jejich původní místo.

Vícerozměrné pole ● Vícerozměrné pole (tj. matice, kubice, atd) je přirozeným rozšířením jednorozměrného pole: int[][] matice = new [3][2]; // matice 3 krat 2

● Matice je organizována po řádcích, tj. předcházející deklarace vytvoří matici o 3 řádcích a 2 sloupcích ● Počet řádků matice: matice.length

● Přístup k prvku matice se provádí opakovanou indexací: matice[2][0] = 10;

● Inicializátor matice používá vnořené složené závorky: int [][] jednotkovaMatice = {{1,0,0}, {0,1,0}, {0,0,1}};

● Pokud se pro indexaci matice použije pouze jeden index, je výsledkem i-tý řádek matice. Počet sloupců (tj. počet prvků prvního řádku): matice[0].length

Výpis matice ● Algoritmy pro práci s maticemi obvykle používají vnější cyklus pro řádky, v jehož těle je vnitřní cyklus pro sloupce: static void vypisMatice(final char[][] maticeZnaku) { for (int radek = 0; radek < maticeZnaku.length; radek++) { for (int sloupec = 0; sloupec < maticeZnaku[0].length; sloupec++) { System.out.print(maticeZnaku[radek][sloupec]); if (sloupec < maticeZnaku[0].length -1) System.out.print(", "); } System.out.println(); // konec výpisu řádku } }

Dekompozice (1/2) ● Úlohy se snažíme rozkládat na co nejvíce jednoduchých metod. ● Při práci s maticí lze obvykle naprogramovat zvlášť pomocnou metodu pro jeden řádek a tu potom použít v hlavní metodě. ● Příklad - nalezení indexu řádku s maximálním součtem: Pomocná metoda pro součet řádku: static double sum(final double[] radek) { double sum = 0; for (double hod : radek) { sum += hod; } return sum; }

D (2 e /2) k ● Nalezení indexu řádku s maximálním součtem: o static int indexRadkuSMaximalnimSouctem( final double[][] matice) { m if (matice.length == 0) throw new IllegalArgumentException("Matice ma 0 p radku"); // index řádku s o maximálním součtem int indexMax = 0; z // maximální součet max = sum(matice[indexMax]); i double for (int ir = 1; ir < matice.length; ir++) { soucet ir-tého řádku c //double sumIr = sum(matice[ir]); if (sumIr > max) { // nalezen nový e maximální řádek indexMax = ir;

m a x = s u m I r ; } } retur n index Max; }

● Bit:

Zá

kladní

pojmy

1. dvojková číslice (binary digit) tj. 0 nebo 1, 2. paměťové místo, které může být ve dvou stavech (klopný obvod, magnetický dipól, vypálený otvor v atd.). Každému stavu je konvencí přiřazena jedna dvojková číslice. ● Byte - osmice bitů. Může se nacházet v 2 8 = 256 různých stavech. ● Slovo (word) - čtveřice, resp. osmice bytů, tj. 32 resp. 64 bitů. ● Vnitřní paměť počítače - posloupnost bytů (resp. slov). ● Adresa - pořadové číslo bytu paměti. V "rozumných" počítačových architekturách je slovo tak velké, aby do něj šla uložit maximální adresa. ● Adresa slova - adresa prvního bytu slova. Podobně také adresa proměnné.

Reprezentace hodnot ● Abstraktní hodnoty (matematické, logické atd.) musí být vždy nějak reprezentovány (vyjádřeny). Reprezentaci rozdělujeme na: ○ vnější - čitelná pro člověka (programátora resp. uživatele programu), ○ vnitřní - uložená do paměti počítače. ● Vnější reprezentace - obvykle krátkým textem tj. posloupností znaků: ○ literálem - tvar je definován normou jazyka a tedy přímo podporován. Hodnota je ovšem konstantní při překladu: 123, 123.0, 1.23e2, ○ obecným řetězem - manipulace musí být naprogramována "ručně": "123", "CXXIII", "sto dvacet tri"

Opakování číselných soustav ● Číslice - znak, který reprezentuje číslo. ● Poziční soustava - číslo je vyjádřeno posloupností číslic, z nichž každá má váhu danou pozicí v posloupnosti. Váha je mocnina základu soustavy Z. Poziční soustava vyžaduje číslice pro čísla z intervalu <0, Z - 1>. Při zápisu čísla v poziční soustavě musí být vždy zřejmý základ (při nejasnosti se uvádí jako index za číslem): ● Příklad: 25610 = 2 * 10 2 + 5 * 10 1 + 6 * 10 0 ● Dvojková (binární) soustava: Z = 2, číslice: '0', '1' ● Příklad: 10102 = 1 * 2 3 + 0 * 22 + 1 * 21 + 1 * 20 = 1010

Konstanty K, M, G ● Konstanty usnadňující práci s dvojkovou soustavou: ○ K = 210 = 1024 = cca tisíc ○ M = 220 = 210 * 210 = K * K = cca milion ○ G = 230 = K * M = cca miliarda ● Příklad - jaké maximální číslo lze zobrazit 16 binárními číslicemi: 216 - 1 = 26 * 210 - 1 = 64K - 1 = 65535 ● Příklad - jaké maximální číslo lze zobrazit 32 binárními číslicemi (tj. v jednom 4-bytovém slově): 232 - 1 = 22 * 230 - 1 = 4G - 1 tj. cca 4miliardy

Hexadecimální soustava ● Velká čísla v binární soustavě jsou velmi nepřehledná. Částečným řešením je hexadecimální soustava: ○ základ Z = 16, ○ číslice ■ dekadické s obvyklým významem, ■ speciální: 'A' ~ 10, 'B' ~ 11, 'C' ~ 12, 'D' ~ 13, 'E' ~ 14, 'F' ~ 15 ● Příklad: AB16 = 10 * 16 1 + 11 * 160 = 17110 ● Převod mezi hexadecimální a binární soustavou je velmi jednoduchý: každá hexadecimální číslice se nahradí 4bitovým binárním zápisem své hodnoty. ● Příklad: AB16 = 101010112 ● Hexadecimální literály v Javě: 0xAB, 0xFFFF, 0X3a

Kódy ● Kód je prosté zobrazení nějaké množiny hodnot (tzv. vzorů) na množinu nezáporných tzv. kódových čísel (resp. přímo na posloupnost bitů). ● Podle typu hodnot rozeznáváme kódy: ○ znakové - kódují znaky, což jsou prvky nějaké abecedy, které obvykle mají typický grafický symbol, ○ číselné - kódují čísla z nějaké konečné množiny. ● Bitová reprezentace vzoru je obvykle tvořena zápisem hodnoty kódového čísla v binární soustavě. ● Z bitové reprezentace vzoru nelze rozpoznat, jaký kód byl použit. Důsledek: z binárního resp. hexadecimálního výpisu vnitřní paměti počítače nelze rozpoznat, jaké hodnoty jsou v paměti uloženy.

Znakové kódy ● Znakové kódy přiřazují kódové číslo znakům zvolené abecedy: ○ ASCII (American Standard Code for Information Interchange) - přiřazuje množině znaků čísla z intervalu <0,127> (proto 7-bitový kód). Obsahuje písmena pouze anglické abecedy, ○ Národní kódy - přidávají kódová čísla pro národní znaky. Obvykle 8-bitové kódy specifické pro daný region (Windows1250, ISO-8859-2, atd...) - dnes na ústupu, ○ Unicode

Unicode ● Unicode - univerzální 16-bitový znakový kód, obsahující znaky všech národních abeced (65536 kódových čísel). ● Je nadmnožinou ASCII kódu, tj. pro znaky obsažené v ASCII definuje stejná kódová čísla. ● Kódování znaků v Javě: ○ všechny hodnoty znaků (tj. hodnoty typu char) jsou v paměti uloženy v kódu Unicode, ○ při čtení z vnějšího prostředí Java "umí" vždy i nativní kód systému a některé další kódy.

Číselné kódy ● Číselné kódy dělíme podle množiny vzorů na: ○ celočíselné, ○ kódy pro zobrazení hodnot v plovoucí řádové čárce. ● Celočíselné kódy přiřazují každému číslu z nějakému intervalu celých čísel <-m, n> nezáporné celé kódové číslo (kód doplňkový, BCD, přímý, inverzní, atd ...). ● Kódy pro zobrazení čísel v plovoucí řádové čárce zobrazují číslo jako trojici: znaménko, mantisa, exponent: z*m*2e ● Každá část má definován způsob reprezentace a umístění v celkovém obrazu desetinného čísla, např.:

Doplňkový kód ● Nejvíce používaný celočíselný kód s velmi dobrými vlastnostmi. ● Definice: ○ n (tj. vzor) - celé číslo, které kódujeme, ○ D(n) (tj. obraz) - nezáporné kódové číslo. ● Definice doplňkového kódu: D(n) : n >= 0 D(n) = n n<0 D(n) = Z - n kde Z je číslo 2 k, kde k je počet bitů, které jsou ke kódování k dispozici. ● Příklad pro k = 3, Z = 8: vzor

-4

-3

-2

-1

0

1

2

3

kód

4

5

6

7

0

1

2

3

binárně

100

101

110

111

000

001

010

011

Vlastnosti doplňkového kódu ● Kód umí zobrazit čísla v intervalu: <-2 k-1, 2 k-1 - 1>. ● Vzoru 0 odpovídá obraz 0. ● Nejvyšší bit binárního tvaru obrazu indikuje znaménko vzoru: 0 - nezáporné, 1 - záporné. ● Hodnota -1 je binárně zobrazena samými jedničkami. ● Inverze znaménka se provede jednoduchým postupem: ○ invertují se bity obrazu, ○ přičte se jednička. ● Příklad inverze hodnoty 2: D(2) = 010 inverze bitů: 101 +1 výsledek: 110 = D(-2)

"Magická" vlastnost doplňkového kódu ● Výsledek operace nad obrazy vzorů se rovná obrazu výsledku operace nad vzory. ● Příklad: D( 1) = 001 + D(-2) = 110 D(1-2) = 111 ● Vlastnost platí pouze pro aditivní operace (+ a -) a operaci násobení (jde vlastně o opakované sčítání). ● Důsledek: procesor počítače nemá zvláštní instrukce pro počítání s čísly v doplňkovém kódu (pro dělení však musí zvláštní operace existovat).

Přehled primitivních typů Javy kód

délka v bitech

minimální hodnota

maximální hodnota

zabalovací třída

byte

doplňkový

8

-128

127

Byte

short

doplňkový

16

-32768

32767

Short

char

dvojkový

16

0

65635

Character

int

doplňkový

32

-2147483648

2147483647

Integer

long

doplňkový

64

-9223372036854775808 9223372036854775807

Long

float

32

cca -3.4E38

cca 3.4E38

Float

double

64

cca -1.8E308

cca -1.8E308

Double

boolean

?

false

true

Boolean

Zabalovací třídy ● Zabalovací třídy (wrapper classes) jsou deklarovány v balíku java.lang a s výjimkou tříd Integer a Character se jmenují stejně jako odpovídající primitivní typ: Byte, Short, atd. Zabalovací třídy obsahují důležité konstanty a metody pro korespondující primitivní typ. ● Příklad - třída java.lang.Integer deklaruje pro typ int: ○ minimální a maximální zobrazitelnou hodnotu: MIN_VALUE MAX_VALUE

○ metody pro: ■ konverzi z vnější dekadické do vnitřní reprezentace: static int parseInt(String s) throws NumberFormatException

■ konverzi z vnitřní do vnější dekadické reprezentace: static String toString(int i)

Přetečení ● Přetečení (overflow) nazýváme situaci, kdy výsledek operace není zobrazitelný v typu, ve kterém se operace provádí. ● Příklad - následující výraz má hodnotu 4 miliardy, která není zobrazitelná v typu int: 2000000000 + 2000000000

● Přetečení není Javou detekováno jako chyba, takže jeho vznik může způsobit zcela chybný běh programu !!! ● Ošetření vzniku přetečení: ○ vhodnou volbou typu (použít místo typu int typ long nebo double): 2000000000L + 2000000000 // výpočet v long

○ využít vlastnosti doplňkového kódu, ve kterém se přetečení při aditivní operaci projeví neodpovídajícím znaménkem výsledku.

Kontrola přetečení ● Příklad - funkce kontrolující přetečení při aditivních operacích: static int neg(final int x) { if (x == Integer.MIN_VALUE) // hodnota -Integer.MIN_VALUE nemá obraz throw new IllegalArgumentException("Preteceni") return -x; } static int plus(final int x, final int y) { int vysl = x + y; if (x > 0 && y > 0 && vysl < 0) || (x < 0 && y < 0 && vysl > 0) throw new IllegalArgumentExceptiopn("Preteceni"); return vysl; } static int minus(final int x, final int y){ return plus(x, neg(y)); }

Bitové a logické operace ● Bitové a logické operace jsou realizací matematických operací negace (not), konjunkce (and), disjunkce (or) a nonekvivalence (xor) : a

b

not a

a and b

a or b

a xor b

0

0

1

0

0

0

0

1

1

0

1

1

1

0

0

0

1

1

1

1

0

1

1

0

● Pozn.: konjunkce se nazývá logický součin a její hodnota odpovídá aritmetickému součinu operandů. Obdobně disjunkce se nazývá logický součet. ● Pokud jsou uvedené operace prováděny nad typem boolean, pak 0 v tabulce reprezentuje false a 1 true.

Bitové a logické operátory operace/operátor

logický

bitový

not

!

~

and

&&

&

or

||

|

xor

^ , !=

^

● Logické operace se provádějí s hodnotami typu boolean. ● Bitové operace se provádějí s celočíselnými hodnotami tak, že se na každý bit vnitřní reprezentace aplikuje příslušná operace.

Logické operace ● Příklad - funkce testuje, zda je číslo v zadaném intervalu: static boolean xJeVIntervalu(final int x, final int min, final int max) { return x >= min && x <= max; } static boolean xJeMimoInterval1(final int x, final int min, final int max) { return x < min || x > max; } static boolean xJeMimoInterval2(final int x, final int min, final int max) { return !xJeVIntervalu(x, min, max); }

● Pozn.: logické operace se vyhodnocují tzv. zkráceným způsobem. T.zn., že pokud je např. v první funkci x menší než min, vrací funkce hodnotu false a již se dále netestuje, je-li x menší než max.

Bitové operace ● Bitové operace se obvykle používají tehdy, je-li potřeba manipulovat přímo s vnitřní reprezentací hodnoty. ● Příklad - jeden obrazový pixel je pro úsporu místa reprezentován hodnotou typu int, kde bity 0 až 7 jsou použity pro vyjádření jasnosti modré barvy v hodnotách 0 až 255 a obdobně jsou bity 8 až 15 použity pro barvu zelenou a 16 až 23 pro barvu červenou: static int modra(final int pixel), return pixel & 0xff; // 0xff = 00000000000000000000000011111111 } ● Pozn.: pravý operand bitové operace & se někdy nazývá maska, protože všechny bity, které jsou nulové v masce jsou nulové i ve výsledku operace.

Posouvací bitové operace ● Bitový posun vlevo (shift left) provede posun bitů vnitřní reprezentace celočíselné hodnoty o n pozic tak, že bit z pozice 0 se přesune na pozici n, bit z pozice 1 na pozici n+1 atd.. Nultý bit se nahrazuje 0, znaménkový bit se ztrácí: int i = 10; i = i << 3 // i má hodnotu 80 ● Posun vlevo (obdobně jako v desítkové soustavě) znamená násobení mocninou 2. Přetečení nastane, pokud je při posunu o 1 pozici nahrazen znaménkový bit bitem s jinou hodnotou t.zn., že výsledek má neodpovídající znaménko (srovnej přetečení aditivních operací). ● Příklad: int i = 0x80000000 // = Integer.MIN_VALUE i << 1 // = 0, došlo k přetečení

Bitový posun vpravo ● Bitový posun vpravo (shift right) odpovídá celočíselnému dělení mocninou 2. Spodní bity, které odpovídají zbytku, jsou ztraceny, přetečení nemůže nastat. ● Aby znaménko výsledku odpovídalo znaménku operandu, je znaménkový bit zachován. ● Důsledek: -1 / 2 == -1 ● Příklad: int i = 6; // D(6) = 000000000...0110 i = i >> 1; // D(3) = 000000000...0011 i = i >> 1; // D(1) = 000000000...0001 i = i >> 1; // D(0) = 000000000...0000 i = -6; // D(-6) = 111111111...1010 i = i >> 1; // D(-3) = 111111111...1101 i = i >> 1; // D(-2) = 111111111...1110 i = i >> 1; // D(-1) = 111111111...1111 i = i >> 1; // D(-1) = 111111111...1111

Využití bitových operací ● Pomocí bitových operací je možno složit vnitřní reprezentaci z jednotlivých částí: ● Příklad: v barevném modelu RGB je barva reprezentována celým číslem int, kde jednotlivé barevné složky (R-červená, G-zelená, B-modrá) jsou reprezentovány jednotlivými byty celého čísla a mají hodnotu 0 až 255: . . . int fialova = 0xff00ff; // červená + modrá int zluta = 0xffff00; // červená + zelená . . . static int vytvorBarvu(final int cervena, final int zelena, final int modra) { return (cervena & 0xff) << 16| (zelena & 0xff) << 8 | (modra & 0xff); }

Operace XOR ● Zvláštností operace xor je, že její opakovanou aplikací dostaneme původní hodnotu: a

b

a xor b

(a xor b) xor b == a

0

0

0

0

0

1

1

0

1

0

1

1

1

1

0

1

● To lze využít pro jednoduché šifrování: static void sifrujDesifruj(final char[] text, final int klic) { for (int i = 0; i < text.length; i++) { text[i] = (char)(text[i] ^ klic); } }

● Pozn: prolomení této šifry viz E.A.Poe: Zlatý skarabeus.

Operátory s vedlejším efektem ● Některé operátory, kromě výpočtu nové hodnoty, modifikují také hodnotu svého operandu (který proto musí být proměnná). Tento jev se nazývá vedlejší efekt (side effect). ● Operátory s vedlejším efektem jsou: ○ operátor přiřazení (=) ■ vedlejším efektem operace je právě přiřazení hodnoty pravého operandu do levého operandu proměnné, ■ hodnotou operace přiřazení je hodnota levého operandu (tj. proměnné) po provedeném přiřazení. ○ modifikační (update) operátory (+= ...), ○ inkrementační a dekrementační operátory (++ --),

Modifikační operátory ● Všem binárním operátorům (kromě logických) odpovídají tzv. modifikační (update) verze operátorů: +=, -=, *=, /=, %=, &=, |=,^=, <<=, >>=,

>>>=

● Výraz s modifikačním operátorem: Variable op = Expression (např.: x += 5) se chová (až na přetypování) jako výraz: Variable = Variable op Expression (odpovídá: x = x+5) ● Tyto operátory mají vedlejší efekt daný operátorem = int i = 12; i *=10; // i = i * 10; // v i je hodnota 120

● Pozn.: pro typy byte, short a char by se v ekvivalentním zápisu muselo použít přetypování: byte b = 10; b *=10; // b = (byte)(b * 10);

Inkrementace a dekremetace ● Operandem inkrementačních a dekrementačních operátorů (++, --) mohou být jen proměnné aritmetického typu (včetně char). Vedlejší efekt operátorů je zvětšení (inkrementace) resp. zmenšení (dekrementace) hodnoty proměnné o 1. ● Operátory lze užít dvojím způsobem jako: ○ prefixové - operátor před operandem, výsledkem je nová hodnota proměnné, ○ postfixové - operátor za operandem, výsledkem je původní hodnota proměnné. ● Příklad: int i = 2, j= 4; i++; // i == 3, hodnota výrazu == 2 --j; // j == 3; hodnota výrazu == 3

● Příklad využití hodnoty i vedlejšího efektu operátoru: while(--i > 0) { ... }

Priorita a asociativita operátorů ● Operátory mají tři vlastnosti: ○ násobnost (tzv. aritu) - unární, binární, ternární, která určuje, kolik má operátor operandů, ○ prioritu, ○ asociativitu - levou nebo pravou. ● Priorita a asociativita určuje pořadí provádění operací ve výrazu. To je v Javě (na rozdíl od C, Pascalu, atd.) striktně definované: ○ nejprve se vyhodnocují podvýrazy v závorkách, ○ potom se vyhodnocují operátory v pořadí podle priorit, ○ pokud mají operátory stejnou prioritu, tak se vyhodnocují ■ zleva doprava, pokud jsou zleva asociativní, ■ zprava doleva, pokud jsou zprava asociativní.

Přehled operátorů

Poznámky k prioritě operátorů ● Nejvyšší prioritu mají unární operátory. ● Multiplikativní operátory (*, /, %) mají vyšší (tj. obvyklou) prioritu než aditivní: ●x*6+y

● se chápe: ● (x * 6) + y

● Logické operátory mají nižší prioritu než relační, takže výrazy typu: ● a >= min && a <= max

● není třeba (na rozdíl od Pascalu) dávat do závorek. ● Bitové operátory mají nižší prioritu než aritmetické! ●x&y+7

● se proti očekávání chápe: ● x & (y + 7)

● Doporučení: v případě nejistoty použijte závorky.

Asociativita operátorů ● Většina operátorů je levě asociativní. Proto je výraz: x + y + 10

chápán jako: (x + y) + 10

● Pravě asociativní je přiřazovací operátor a modifikační operátory. To lze využít při vícenásobném přiřazení: int x; int y; x = y = 33;

které je chápáno jako: x = (y = 33);

● Pozn. pokud by operátor přiřazení byl levě asociativní, znamenal by předcházející výraz: (x = y) = 10. Takový výraz je ale chybný, protože na levé straně přiřazení musí být proměnná a výraz (x = y) proměnná není.

Další vlastnosti desetinných typů ● V zabalovacích třídách Float a Double jsou definovány následující konstanty: ○ NEGATIVE_INFINITY ○ POSITIVE_INFINITY ○ NaN ● Konstanty POSITIVE_INFINITY a NEGATIVE_INFINITY jsou výsledkem operací, které nelze zobrazit v příslušném typu. Např. pro double d > 0 platí: ○ d / 0 == Double.POSITIVE_INFINITY ● Konstanta NaN (Not a Number) je výsledek operace, která není jednoznačná: 0/0, POSITIVE_INFINITY POSITIVE_INFINITY, atd. ● Konstanty lze testovat funkcemi: ○ static boolean isInfinite(double v) ○ static boolean isNaN(double v)

Typová konverze ● Opakování: každý výraz a tedy každý operand má typ známý v době překladu. Typ určuje množinu hodnot, jejich reprezentaci a význam operátorů. ● Typová konverze je změna jednoho primitivního typu na jiný, která se vyskytuje v programu v určitých kontextech: ○ při přiřazení, ○ při předávání argumentu metodě, ○ při unárním a binárním povýšení (viz dále), ○ při přetypování, ○ při spojování řetězů. V těchto situacích jsou některé konverze povolené a jiné ne. ● Typ boolean nelze konvertovat vůbec. Ostatní primitivní typy lze navzájem konvertovat. ● Pozn.: za typovou konverzi nepovažujeme konverzi z vnější (tj. textové) do vnitřní reprezentace.

Relace nadtyp-podtyp ● Primitivní typy mají mezi sebou vztah nadtypu - podtypu, který znamená, že množina hodnot jednoho typu je nadmnožina druhého typu. Vztah je tranzitivní uzávěr relace přímého nadtypu (>1), která je definována: double >1 float, float >1 long long >1 int, int >1 char int >1 short, short >1 byte ● Důsledek: double je nadtypem všech primitivních typů s výjimkou boolean. ● Pozn.: pro relaci float >1 long neplatí uvedené tvrzení o podmnožině matematicky doslova, protože většinu hodnot typu long lze zobrazit v typu float pouze přibližně.

Hlavní druhy konverzí ● Rozšiřující konverze (widening) je konverze z podtypu na nadtyp. Je povolena vždy, neboť informace se neztrácí: double d = 1; // 1 je typu int ● Zužující konverze (narrowing) je konverze z nadtypu na podtyp. Je povolena pouze při explicitním přetypování a také při přiřazení celočíselné konstanty do aritmetického typu, ve kterém je zobrazitelná: int celaCastPI = (int)Math.PI; byte b = 10; // konverze z int na byte ● Konverze hodnoty na řetěz - každá hodnota má svou implicitní vnější (textovou) reprezentaci. Tato konverze se aplikuje v při spojování řetězů (nelze ji zapsat jako přetypování!). ● Pozn.: konverze obvykle znamená, že se při výpočtu změní vnitřní reprezentace hodnoty.

Aritmetické povýšení ● Povýšení (promotion) je postup, jakým se v aritmetickém výrazu provádějí automatické konverze (pouze rozšiřující): ○ Unární povýšení - před provedením jakékoliv operace se hodnota operandu typů byte, char a short automaticky konvertuje na typ int. Z toho plyne, že se žádný výpočet neprovádí na menším rozsahu než 32 bitů. ○ Binární povýšení: 1. Na celočíselné operandy binární operace se nejprve aplikuje unární povýšení. 2. Potom, pokud je typ jednoho operandu podtypem druhého, konvertuje se podtyp na nadtyp. 3. Nadtyp je typem celého výrazu.

Příklad povýšení ● Příklad: byte b = 33; long g = 0xAAAABBBBCCCC; -b * g + 1.2

● V uvedeném výrazu se: 1. b zkonvertuje na int, 2. provede se unární minus, 3. výsledek se zkonvertuje na long, 4. násobení se provede v long, 5. výsledek se zkonvertuje na double (1.2 je typu double), 6. sčítání se provede v double, 7. double je také typem celého výrazu.

Přetypování ● Přetypování (typecasting) umožňuje jakoukoliv konverzi mezi primitivními typy (kromě boolean): ( Type ) Expression ● Zužující konverze, která může znamenat ztrátu hodnoty, je dovolena pouze u přetypování: long g = 10000000000;// nejde zobrazit v int int i = (int)g; // došlo ke ztrátě hodnoty

● Přetypování je také možno použít, pokud chceme vynutit výpočet výrazu na jiném typu, než odpovídá aritmetickému povýšení: int m = 3; int n = 4; m / (double)n // = 0.75

Bez přetypování by se operace chápala jako celočíselné dělení v typu int a jeho výsledek by byl 0.

Příkaz - výraz ● Přidáním středníku za výraz vytvoříme příkaz, který se nazývá příkaz-výraz: ExpressionStatement: Expression ; ● Expression (na rozdíl od C) musí být buď volání funkce nebo výraz s vedlejším efektem. V obou případech je skutečná hodnota výrazu bezvýznamná a příkaz-výraz se používá pouze kvůli svému vedlejšímu efektu. ● Následující příkazy jsou ekvivalentní, přestože jsou použity různé operátory, které vrací různé hodnoty (jaké?). Všechny ● Pozn.: doposud jsme pro větší srozumitelnost mluvili o příkazu přiřazení a příkazu volání metody. Ve skutečnosti jde v obou případech o varianty příkaz výrazu.

m

Přímá rekurze ● Rekurzí nazýváme situaci, kdy se při vykonávání nějaké metody provede příkaz volání té samé metody. ● Metodu, která ve svém těle přímo obsahuje volání sebe sama nazýváme rekurzivní (tzv. přímá rekurze): ● Příklad: static long faktorial(final int n) { if (n < 0) throw new IllegalArgumentException("n<0"); if (n == 0) { return 1; } return n * faktorial(n - 1); // rekurzivní volání }

Ukončení rekurze ● Z hlediska řízení programu vytváří rekurze cyklus, protože v místě rekurzivního volání se de facto provádí skok zpět na začátek rekurzivní metody. ● Stejně jako běžný cyklus, musí být i rekurze ukončena a to podmíněným příkazem, který: ○ buď obsahuje příkaz return ve smyčce rekurze (viz metoda faktorial), ○ nebo obsahuje samotné rekurzivní volání: static int faktorial2(final int n) { if (n<0) throw new IllegalArgumentExcveption("n<0"); if (n > 0) return n * faktorial2(n - 1); return 1; }

Parametr rekurzivní metody ● Rekurzivní metoda má obvykle parametr, který se používá obdobně jako řídící proměnná cyklu. Rekurze se ukončí, jestliže hodnota parametru dosáhne nějaké hraniční hodnoty. Při rekurzivním volání se modifikovaná hodnota tohoto parametru předává volané metodě, což odpovídá modifikaci řídící proměnné v příkazu for. ● Často se rekurzivní metoda s parametrem doplňuje nerekurzivní metodou, která volá rekurzivní metodu s iniciální hodnotou řídícího parametru: static int maxPrvek(int... prvky) { return maxPrvek(prvky, 0); } static int maxPrvek(final int[] pole, final int zac) { if (zac >= pole.length) return Integer.MIN_VALUE; return Math.max(pole[zac], maxPrvek(pole, zac + 1)); }

Převod rekurze na iteraci ● Každý rekurzivní algoritmus je možno převést na iterativní (tj. takový, který místo rekurze používá cyklus. ● Příklad převodu rekurzivní metody na iteraci: static long faktorialIteraci(final int n) { if (n < 0) throw new IllegalArgumentException("n<0"); long f = 1; for (int i = 2; i <= n; i++) { f *=i; } return f; }

● Iterativní forma algoritmu bývá efektivnější, leč méně přehledná.

Rám ● Při volání metody se hodnota skutečného parametru (argumentu) přiřazuje do parametru formálního. Protože u rekurze je volající a volaná metoda stejná, dochází zdánlivě k přepsání hodnot parametrů volající metody argumenty pro metodu volanou. ● Ve skutečnosti však k přepsání hodnoty nedochází. Na začátku volání metody se pro volanou metodu vytvoří nový rám (aktivační záznam), což je blok vnitřní paměti, ve kterém deklarují: ○ formální parametry, ○ lokální proměnné, ○ servisní položky (návratová adresa, dynamický link, atd.). ● Parametry volané a volající metody se tedy nacházejí v různých rámech. ● Návratem z metody se rám ruší.

Exekuční zásobník (1/2) ● Doba existence rámů (life cycle) se řídí strategií LIFO (Last In First Out), tj. strategií datové struktury zásobník (stack). Naposled vytvořený (last in) rám je také první zrušen (first out), protože poslední rekurzivní volání je také nejdříve dokončeno. ● Rámy všech momentálně aktivních metod se nazývají exekuční zásobník. Aktuální počet rámů na zásobníku se nazývá hloubka exekučního zásobníku. ● Hloubka exekučního zásobníku je omezená, a pokud je v běhu překročena, dojde k chybě StackOverflow. Typicky když během chybně naprogramované rekurze dojde k věčnému cyklu. ● Pozn.:rekurzivní řešení bývá vhodné u takových algoritmů, jež zásobník z principu potřebují - viz dále Hanojské věže.

Exekuční zásobník

(2/2)

● Příklad - při výpočtu faktoriálu ze tří se postupně vytvoří 4 rámy protože během výpočtu se metoda faktorial volá postupně s argumenty 3, 2, 1 a 0:

Úloha se zásobníkem ● Při kontrole párovosti závorek v textu si algoritmus musí zapamatovat kolik a jakých otvíracích závorek se v textu dosud vyskytlo. To je nejsnazší v lokální proměnné rekurzivní metody. ● Algoritmus má dvě pomocné metody: static boolean jeOteviraciZavorka(final char c) { return c == '(' || c == '[' || c == '{'; } static boolean jsouParove(final char oteviraciZavorka, final char zaviraciZavorka) { switch (oteviraciZavorka) { case '(': return zaviraciZavorka == ')'; case '[': return zaviraciZavorka == ']'; case '{': return zaviraciZavorka == '}'; default: throw new RuntimeException("Neznama zavorka"); } }

Kontrola párovosti závorek ● Pokud je následující metodě předán text, který má na pozici pozZav otevírácí závorku, zkontroluje zda jí odpovídá závorka zavírací a vrátí následující pozici: static int kontrolaParovostiZavorek(final char[] text, int pozZav) { while (pozZav < text.length && jeOteviraciZavorka(text[pozZav])) { char oteviraciZavorka = text[pozZav]; pozZav = kontrolaParovostiZavorek(text, pozZav+1); if (!jsouParove(oteviraciZavorka, text[pozZav])) { throw new RuntimeException( "Neparova zavorka na pozici: " + pozZav); } pozZav++; } return pozZav; }

Metoda rozděl a panuj ● Obtížné úlohy je možno zjednodušit rozložením na více (obvykle 2) menší podúlohy stejného charakteru, tj. takové, které lze řešit stejnou funkcí jako původní úlohu. ● Celkové řešení se pak sestaví z výsledků rekurzivního volání metody nad podúlohy. ● Příklad - mocnina rekurzivně: static double mocnina(final double x, final int n) { if (n < 0) throw new IllegalArgumentException("n<0"); if (n == 0) return 1; double tmp = mocnina(x, n/2); tmp *= tmp; if (n % 2 == 1) // licha mocnina tmp *= x; return tmp; }

Mocnina iterativně ● Nerekurzivní verze algoritmu je mírně efektivnější, ale méně názorná: static double mocninaIteraci(final double x, int n) { if (n < 0) throw new IllegalArgumentException("n < 0"); if (n == 0) return 1; double tmp = x; double res = 1; while (n >= 2) { tmp *= tmp; if (n % 2 == 1) // je licha res *= tmp; n = n / 2; } return res * tmp; }

Nevhodná rekurze ● Rekurze není vhodná, pokud rozklad úlohy konverguje pomalu a počet rekurzivních volání (a tedy hloubka exekučního zásobníku) je úměrný rozsahu úlohy: ● Příklad: static void obratPole(final int[] a) { premistiPrvky(a, 0); } static void premistiPrvky(final int[] a, final int indexPrvniho) { if (indexPrvniho == a.length) return; int tmp = a[indexPrvniho]; premistiPrvky(a, indexPrvniho + 1); a[a.length - 1 - indexPrvniho] = tmp; }

● Algoritmus je velmi elegantní, avšak hloubka zásobníku je rovná délce obráceného pole.

Akceptovatelná hloubka ● Pokud vzniknou metodou rozděl a panuj dvě přibližně stejné podúlohy, je maximální hloubka exekučního zásobníku dvojkový logaritmus původní velikosti úlohy: static int maxPrvek2(int... prvky) { return maxPrvekSubpole(prvky, 0, prvky.length); } static int maxPrvekSubpole(final int[] pole, final int zacatek, final int zaKoncem) { if (zaKoncem == zacatek) throw new IllegalArgumentException("Prazdne subpole"); if (zaKoncem - zacatek == 1) { // jeden prvek return pole[zacatek]; } int stred = zacatek + (zaKoncem - zacatek) / 2; return Math.max( maxPrvekSubpole(pole, zacatek, stred), maxPrvekSubpole(pole, stred, zaKoncem)); }

Exponenciální nárůst ● Nevhodnou konstrukcí rekurzivního výpočtu může dojít k exponenciálnímu nárůstu počtu rekurzivních volání. ● Příklad - fibonaciho posloupnost: ○ f0 = 0, f1 = 1, fn=fn-1+fn-2, ○ začátek posloupnosti: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..... static int fib(final int n) { if (n < 0) throw new IllegalArgumentException("n < 0"); if (n == 0) return 0; if (n == 1) return 1; return fib(n-1) + fib(n-2); }

● Problémem algoritmu je, že počítá opakovaně již jednou nalezené prvky posloupnosti. Např. průběh rekurzivních volání pro n = 5 je f(5), f(4), f(3), f(2), f(1), f(0), f(1), f(2), f(1), f(0), f(3), f(2), f(1), f(0), f(1).

Fibonaci iterativně static long fibIteraci(final int n) { if (n < 0) throw new IllegalArgumentException("n<0"); if (n == 0) return 0; if (n == 1) return 1; long fm1 = 1; long fm2 = 0; long fn = 0; for (int i = 2; i <=n; i++) { fn = fm1 + fm2; fm2 = fm1; fm1 = fn; } return fn; }

Algoritmus ● Algoritmus je postup řešení úlohy, který má nějaké vlastnosti: ○ hromadný - je vhodný pro řešení třídy úloh, které se liší zadanými daty (avšak jsou algoritmy, které nemají vstupní data), ○ konečný - tzn. skončí po konečném počtu kroků (avšak jsou programy - např. řídící - napsané jako věčné smyčky), ○ deterministický - pro stejná vstupní data vrátí vždy stejný výsledek (avšak jsou algoritmy, které se opírají o náhodné hodnoty), ○ resultativní - tzn. dává nějaký výsledek (byť jsou programy, které jenom maří čas procesoru). ● Program - algoritmus zapsaný v programovacím jazyce.

Složitost ● Efektivita je důležitá vlastnost algoritmů, která určuje použitelnost algoritmů pro danou úlohu. Rozeznáváme efektivitu: ○ časovou - tzv. časovou složitost ○ paměťovou - tzv. paměťovou složitost ● Složitost je funkce, která udává spotřebu zdrojů (čas procesoru či paměť) v závislosti na velikosti řešené úlohy. ● Velikost úlohy měříme obvykle počtem prvků vstupních dat (u matic se však velikost měří počtem řádků a sloupců). ● Složitost se může zjišťovat: ○ empiricky tj.měřením - avšak naměřené hodnoty velmi závisí na konfiguraci měření tj. na typu procesoru, na operačního systému, atd, ○ analyticky tj. odvozením.

Krok algoritmu ● Aby se vyloučil vliv různě výkonných počítačů, neudává se složitost v časových jednotkách, ale v krocích: ○ není jednoznačně jasné, co považovat za jeden krok: operaci, příkaz, skok atd, ○ různé kroky mohou trvat různou dobu, ○ doba operace závisí na typu dat (int, double), ○ doba trvání kroku závisí na kontextu, ve kterém je proveden (např. obsah vyrovnávacích pamětí).

Odvození časové složitosti ● Příklad - časová složitost výpočtu aritmetického průměru: static double aritmetickyPrumer(final int... pole) { double p = 0; // inicializace for (int i = 0; // inicializace i < pole.length; i++) { // porovnání, inkrementace p = p + pole[i] / (double)pole.length; // přiřazení,indexace,součet,dělení } // vrácení hodnoty return p; }

● Časová složitost f(n) = 1 + 1 + n * (2 + 4) + 1 = 6n + 3. Asymptotická složitost je O(n) - tj. lineární.

Definice asymptotické složitosti ● Algoritmus může mít počáteční startovací režii, která je ovšem nevýznamná pro větší úlohy. ● Asymptotická složitost - funkce, která vyjadřuje charakter (průběh) složitosti pro velké argumenty. ● Definice: algoritmus, který má časovou složitost g(n) je asymptotické složitosti O(f(n), pokud existuje n0 a c, že pro všechna n > n0 platí g(n) < c . f(n) ● Příklad: jestliže má algoritmus časovou složitost: g(n) = 6n + 3 pak má asymptotickou složitost O(n), protože pro všechna n > 3 platí: 6 n + 3 < 7 n.

Srovnání tříd časových složitostí O(n) [sec]

10

20

30

40

50

60

70

80

90

100

5.3ritmy5,.6které 5.9mají6.h 1 orší6.3než 6.5 6.6 ● Z tabulky3.3je vi4d.3ět, ž4e.9 algo O(n.lnp(no))ly [sn eco ] mi3á 3 lní s8l6ožito 14s7t jso 21u3 pra2k 82ticky35n 4 epr4 o2v9 edit5e06lné. 5T84akov66é4 O(n2)a[hlg odo ] ritmy0se n0a .1zýva 0.j3í NP0.4(ned0e.7termi1nistic1k .4y po1ly .8nom2i.á 3 lní).2.8 O(● n3)N [ha odp ] ř: pro0blém2obch8odníh 18o ces 35tujícíh 60o tj. n 95alez1e 4n 2 í ne 2j0k 3 ratš2í78 O(n!)c [re oks y]ty, kte0rá p 8E 8Ez+í24pr3á Ev +4ě 0 je1d E+n 5o 7 u3d E+a 7n 4 ou 4E9 2 n2 13í0st,3Eje 150 ro+1c0há m oEž+i1n11ou5Em NP složité. ● Kryptografie užívá šifry, jejichž prolomení je NP složité. ● Pro NP problémy existují rychlé přibližné algoritmy tzv. heuristiky, které hledají suboptimální řešení. O(ln(n)) [sec]

Hledání půlením ● Hledání (searching) prvku v poli má obecně lineární složitost O(n). V seřazeném poli lze však hledat se složitostí O(log n): static int hledaniPulenim(final int prvek, final int[] serazenePole) { int i = 0; int j = pole.length - 1; while (i <= j) { int stred = (i + j) / 2; if (prvek < serazenePole[stred]) j = stred - 1;// prvek musí být v 1.polovině else if (prvek > serazenePole[stred]) i = stred + 1;// prvek musí být v 2.polovině else return stred; // prvek nalezen } return -1; // prvek nenalezen }

Řazení výběrem ● Řazení (sorting) znamená uspořádat posloupnost podle velikosti. Je to základní úloha, pro kterou existuje mnoho algoritmů různé složitosti. ● Řazení výběrem je jednoduchý a intuitivní postup: 1. pole myšleně rozdělíme na setříděný úsek a nesetříděný úsek, který je na začátku prázdný, 2. nalezneme v nesetříděném úseku minimální prvek, 3. vyměníme v nesetříděném úseku první prvek s minimálním, a tak se minimální stane novým prvkem setříděného úseku a nestetříděný úsek se zmenší. static void selectSort(final int...pole) { for (int i = 0; i < pole.length; i++) { int indexMinima = indexMinima(pole, i); prohodPrvky(pole, i, indexMinima); } }

Pomocné metody static int indexMinima(final int[] pole, final int zac) { int min = Integer.MAX_VALUE; int indexMinima = -1; for (int i = zac; i < pole.length; i++) { if (pole[i] < min) { min = pole[i]; indexMinima = i; } } return indexMinima; } static void prohodPrvky(final int[] pole, final int i, final int j) { if (i != j) { int tmp = pole[i]; pole[i] = pole[j]; pole[j] = tmp; } }

Bublinové řazení ● Idea tohoto algoritmu je prohazovat sousední prvky, které nejsou ve správném pořadí, dokud pole není seřazeno. Je velmi populární, přestože patří z hlediska složitosti k nejhorším: static void bubblesort(final int[] pole) { for (int i = pole.length - 1; i >= 0; i--) { boolean prohodiloSe = false; for (int j = 0; j < i; j++) if (pole[j] > pole[j + 1]) { prohodPrvky(pole, j, j + 1); prohodiloSe = true; } if (!prohodiloSe) break; } }

Optimální řadící algoritmy ● Dosud uvedené řadící algoritmy jsou třídy O(n2). Naštěstí existují i algorimty se složitostí O(n*log(n)). ● Pomocná metoda, která umí sloučit dvě seřazená pole tak, že výsledné pole je opět seřazené (tzv. merge): static int[] slucPole(final int[] a, final int[] b) { int[] vysl = new int[a.length + b.length]; int i = 0, ai = 0, bi = 0; while (ai < a.length && bi < b.length) { if (a[ai] < b[bi]) vysl[i++] = a[ai++]; else vysl[i++] = b[bi++]; } while (ai < a.length) vysl[i++] = a[ai++]; while (bi < b.length) vysl[i++] = b[bi++]; return vysl; }

Řazení s využitím slučování ● Metodou rozděl a panuj je možno řadit s využitím slučování. ○ pomocná metoda zkopíruje úsek pole do nového pole: static int[] kopieUseku(final int[] pole, final int zacatek, int zaKoncem) { int[] a = new int[zaKoncem - zacatek]; System.arraycopy(pole,zacatek,a,0,a.length); return a; }

○ hlavní metoda: static int[] seradPole(final int... pole) { if (pole.length == 1) return pole; int stred = pole.length / 2; int a[] = kopieUseku(pole, 0, stred); int b[] = kopieUseku(pole, stred, pole.length); return slucPole(seradPole(a), seradPole(b)); }

Slučování uvnitř pole ● V předcházejícím řešení se mnohokrát za sebou vytvářelo pomocné pole. Algoritmus však může slučovat úseky uvnitř jednoho pomocného pole: static void slucUseky(final int[] pole, final int zacatek, final int stred, final int zaKoncem, final int[] pomPole) { int i = 0, z = zacatek, s = stred; while (z < stred && s < zaKoncem) { if (pole[z] < pole[s]) pomPole[i++] = pole[z++]; else pomPole[i++] = pole[s++]; } while (z < stred) pomPole[i++] = pole[z++]; while (s < zaKoncem) pomPole[i++] = pole[s++]; System.arraycopy(pomPole, 0, pole, zacatek, zaKoncem - zacatek); }

Řazení slučováním (mergesort) ● Mergesort je efektivní řadící algoritmus složitosti O(n*log (n)), který používá metoda Arrays.sort v Java API: static void mergeSort(final int[] pole) { seradUsek(pole,0,pole.length,new int[pole.length]); } static void seradUsek(final int[] pole, final int zacatek, final int zaKoncem, final int[] pomPole) { if (zaKoncem - zacatek <= 1) // jednoprvkove pole return; int stred = zacatek + (zaKoncem - zacatek) / 2; seradUsek(pole, zacatek, stred, pomPole); seradUsek(pole, stred, zaKoncem, pomPole); slucUseky(pole, zacatek, stred, zaKoncem, pomPole); }

● Důležitou předností mergsortu je tzv. stabilita tj., že při řazení zachovává pořadí prvků stejné hodnoty. Nevýhoda je, že potřebuje pomocné pole stejné délky.

Objekty a třídy ● Objekt je sada proměnných (tzv. instančních) umístěných za sebou souvisle v paměti tvořící dohromady jeden celek. ● Objekt: ○ má stav, daný hodnotami těchto proměnými, ○ poskytuje služby realizované instančními metodami. ● Třída 1. je abstraktní množina objektů, které mají společné vlastnosti tj. obsahují stejnou sadu instančních proměnných a poskytují tytéž služby týmiž instančními metodami. 2. je programová konstrukce jež deklaruje : 1. statické metody, 2. vlastnosti objektů tj. instanční metody a instanční proměnné.

Příklad třídy z Java API ● V balíku java.awt je deklarována třída Point. Objekty třídy Point mají dvě instanční proměnné: x a y, určující polohu bodu. ● Objekty třídy Point poskytují služby realizované následujícími instančními metodami: ○ double getX() - vrátí x souřadnici bodu, ○ double getY() - vrátí y souřadnici bodu, ○ void move(int x, int y) - posune bod na souřadnice x, y, ○ void translate(int dx, int dy) - posune bod o hodnoty dx a dy. ● Pozn.: v dalším textu budeme místo přesného vyjádření "objekt třídy X" používat zkráceného "objekt X".

Význam tříd ● Třídy slouží v programu k těmto účelům: 1. jako místo pro deklaraci statických metod, které k sobě logicky patří (způsob, kterým jsme třídy používali dosud), 2. jako místo pro deklaraci vlastností objektů, 3. k oběma účelům současně ● V Java API je deklarováno v různých balících stovky hotových tříd a v nich jsou deklarovány tisíce metod. ● Příklad: ○ java.lang.Math - třída obsahuje pouze statické metody (sin, cos, ...) a nelze od ní objekty vytvářet. ○ java.awt.Point - slouží pouze k vytváření objektů bod. ● V programech obvykle uvádíme pouze krátké jméno třídy a jméno balíku je uvedeno zvlášť na začátku programu v klauzuli import.

Vytváření objektů ● Objekt se vytváří operátorem new, kterému se zadá: 1. jaké třídy má objekt být, 2. inicializační parametry pro inicializaci objektu, které obvykle určují počáteční hodnoty instančních proměnných objektu. ● Inicializační parametry při konstrukci objektu Point je počáteční hodnota souřadnic: // vytvoření objektu Point (bodu) // na souřadnicích 1,2 new Point(1,2);

● Grafické znázornění vytvořeného objektu:

Reference (1/2) ● Každý objekt je identifikován (tj. jednoznačně určen) speciální hodnotou, která se nazývá reference. Referenci si můžeme představit jako kladné celé 32 (resp. 64)-bitové číslo, se kterým se ale nedají provádět žádné aritmetické operace. ● Každý objekt má svou referenci a žádné dva objekty nemají referenci stejnou. ● Používání referencí je běžné i mimo oblast programování, takže existuje množství analogií. Například: objekt

reference

bankovní účet

číslo bankovního účtu

osoba

rodné číslo

webová stránka

url

Reference (2/2) ● Reference: 1. nemají vnější reprezentaci, takže je nelze vypisovat metodou println, 2. vnitřní reprezentace je implementačně závislá - tzn. může se lišit pro různé implementace Javy, 3. neexistují pro ně literály kromě literálu null, tudíž je nelze zapisovat do programu jako konstanty. 4. jediné povolené operace nad referencemi jsou porovnání na stejnost (==, !=). ● Pozn.1: srovnej vlastnosti referencí s vlastnostmi jiných hodnot - např. hodnot typu int. ● Pozn.2: pokud máte znalosti jiného programovacího jazyka, srovnejte vlastnosti javovských referencí např. s vlastnostmi ukazatelů v jazyce C, Pascal atp.

Referenční typy ● Protože s referencemi nejsou povolené aritmetické operace, nemohou být ukládány do proměnných aritmetických typů, ale jsou pro ně zavedeny speciální referenční typy. ● Pro každou třídu existuje samostatný referenční typ, který je tvořený množinou všech referencí objektů stejné třídy (např. množinou referencí všech objektů Point). Jméno referenčního typu je stejné jako jméno třídy. ● Příklad deklarace proměnné referenčního typu: Point p; ● Proměnná p je referenčního typu Point, což znamená, že do ní mohou být přiřazovány pouze hodnoty referencí objektů Point: Point p = new Point(5, 8); p = new Rectangle(5, 8); //nedovolené přiřazení

Použití reference ● Objekty se nedeklarují a tedy nemají jméno. Přístup k objektu je možný pouze tehdy, pokud je dispozici jeho reference. Speciálně je potřeba reference na objekt, pokud, chceme zavolat jeho instanční metodu: Point p = new Point(3, 4); System.out.println(p.getX()); // vypíše 3 p.move(30, 40); // presun na pozici [30,40] System.out.println(p.getX()); // vypíše 30

● Reference na jeden objekt může být uložena ve více proměnných, protože přiřazováním referencí se nevytváří nový objekt, pouze se kopíruje reference: Point p = new Point(5,6); Point q = p;

Zánik reference a objektu ● Pokud se ztratí všechny reference na objekt, přestane být objekt dostupný a z hlediska programu přestane existovat. Reference se ztrácí jestliže: 1. proměnná, kde je reference uložena přestane existovat, 2. do proměnné se přiřadí jiná reference: Point p = new Point(1,1); p = new Point(2,2) ; // objekt bodu [1,1] již dále // není dostupný. ● Paměť, kterou zabírají nedostupné objekty, může být znovu použita (recyklována) pro uložení nových objektů. Tento proces se děje automaticky a nazývá se garbage collecting (zkráceně GC).

Pole jako objekty ● Pole v Javě jsou speciálním případem objektů: ○ vytvářejí se též operátorem new, ○ jsou dostupné pouze pomocí referencí, ○ zanikají, pokud zaniknou jejich reference, ○ poskytují přístup k instanční proměnné length, ve které je uložena délka pole. ● Typ pole je speciální referenční typ. Proměnná tohoto typu může obsahovat pouze reference na pole. ● Opakování: na rozdíl od ostatních objektů, lze pole vytvořit kromě operátoru new, také inicializátorem pole: int [] pole = new int[3]; char[] samohlasky = {'A','E','I','O','U'};

Vícerozměrné pole ● Dvojrozměrné pole (matice) je realizováno jako jednorozměrné pole referencí na jednotlivé řádky pole: int[][] matice = new int[2][3];

Nepravidelná matice ● Protože u matice má každá řádka uloženou svoji délku, je možno v Javě vytvářet nepravidelné matice. ● Příklad - funkce, která vrací trojúhelníkovou matici obsazenou hodnotami Pascalova trojúhelníku: static int[][] pascaluvTrojuhelnik(int n) { int[][] pt = new int[n][]; for (int i = 0; i < n; i++) { pt[i] = new int[i + 1]; // vytvoření i-té řádky pt[i][0] = 1; pt[i][i] = 1; for (int j = 1; j < i; j++) { pt[i][j] = pt[i - 1][j - 1] + pt[i - 1][j]; } } return pt; }

● Obdobně lze vytvářet i pole vyšších dimenzí.

OOP ● Objektově orientované programování (resp. paradigma) je způsob tvorby programů, při kterém se hlavně vytvářejí objekty, které si vzájemně poskytují potřebné služby. Pro efektivní programování v OOP je nutná alespoň orientační znalost hotových tříd z Java API, aby vývojář nepsal algoritmy, které jsou již ve třídách z Java API vytvořené. ● Třídy jsou deklarovány v balících, které pokrývají základní oblasti programování. Např: ○ grafické rozhraní - balík javax.swing, ○ soubory - balík java.io, ○ sítě - balík java.net, ○ správa dat - balík java.util, ● Dále uvedeme několik příkladů tříd z Java API.

Třída String ● java.lang.String je třída neměnných posloupností znaků: String s = new String("xyz"); ● Pro řetězové literály platí výjimka: jejich uvedení v programu automaticky znamená vytvoření objektu String, takže předcházející příkaz je ekvivalentní s příkazem: String s = "xyz"; ● String poskytuje např. následující instanční metody: ○ int length() - délka řetězu, ○ char charAt(int i) - znak na i-té pozici, ○ String subString(int begin, int end) - podřetěz od indexu begin do end-1, ○ int indexOf(String str) - pozice str nebo -1, ○ String toUppercase() - řetěz přeložený na velká písmena, ○ String toLowerCase() - dtto na malá písmena.

Třída StringBuilder ● Třídu java.lang.StringBuilder tvoří proměnné řetězy. Objekty StringBuilder nabízejí podobné služby jako objekty String, ale navíc je možno obsah objektu modifikovat: ○ StringBuilder append(String s) - přidá na konec řetěz s, ○ StringBuilder insert(int offset, String s) - vloží řetěz s na pozici offset, ○ StringBuilder replace(int start, int end, String str) zamění část řetězu mezi pozicemi start a end řetězem s. ● Metody vrací jako výsledek referenci na objekt na který byly zavolány, takže lze volání řetězit: StringBuilder sb = new StringBuilde("dva"); sb.insert(0, "jedna ").append(" tři");

Třída BitSet ● Třídu java.util.BitSet tvoří neohraničené posloupnosti bitů: ○ BitSet(int nbits) - vytvoří posloupnost nbits false bitů, ○ void set(int fromIndex, int toIndex) ○ void clear(int fromIndex, int toIndex) - nastaví bity v zadaném rozsahu na true resp. false, ○ int cardinality() - vrátí počet true bitů, ○ void and(BitSet set) ○ void or(BitSet set) ○ void xor(BitSet set) - provede odpovídající logickou operaci mezi bity objektu a bity parametru set, ○ int size() - vrátí celkový počet bitů.

Eratosthenovo síto ● Algoritmus hledání prvočísel. Každý bit v objektu BitSet reprezetuje číslo. Vyškrtnutím násobků zbydou prvočísla: static BitSet eratosthenovoSito(int n) { BitSet prvocisla = new BitSet(); prvocisla.set(0, n); int z = (int) Math.sqrt(n); for (int prvocislo = 2; prvocislo <= z; prvocislo = prvocisla.nextSetBit(prvocislo + 1)) { for (int nasobekPrvocisla = prvocislo * 2; nasobekPrvocisla < n; nasobekPrvocisla += prvocislo) { prvocisla.clear(nasobekPrvocisla); // vyškrtnutí } } return prvocisla; }

Třída java.util.ArrayList ● Objekty java.util.ArrayList se chovají jako pole s proměnnou délkou, avšak elementy mohou být pouze reference. Místo indexace se pro přístup k prvkům používají metody: ○ boolean add(E e) - přidá element na konec, ○ void add(int index, E element) - uloží element na zadaný index. Ostatní elementy se odsunou o jednu pozici, ○ E get(int index) - vrátí element, který leží na daném indexu. ○ E set(int index, E element) - nahradí element na daném indexu, ○ int size() - vrátí počet elementů, ○ void clear() - zkrátí délku na 0 (následné volání metody size vrátí hodnotu 0).

Třída java.math.BigDecimal ● Objekty java.math.BigDecimal reprezentují neměnná dekadická čísla s libovolným rozsahem a přesností: ○ BigDecimal(String val) - konstruuje objekt dekadického čísla zadaný textově, např.: new BigDecimal("1.2345E+4000") ○ BigDecimal add(BigDecimal augend) BigDecimal subtract(BigDecimal subtrahend) BigDecimal multiply(BigDecimal multiplicand) BigDecimal divide(BigDecimal divisor) - vykonají aritmetickou operaci mezi objektem BigDecimal a zadaným parametrem. Vrátí referenci na objekt reprezetující výsledek operace.

Třída java.util.Random ● Objekty java.util.Random jsou náhodné generátory, které poskytují tyto hlavní služby: ○ Random(long seed) - konstruuje generátor se zadaným semenem, ○ int nextInt(int n) - vrací pseudonáhodná čísla typu int rovnoměrně rozložená v polouzavřeném intervalu <0 , n), ○ double nextDouble() - vrací pseudonáhodná čísla typu double rovnoměrně rozložená v intervalu <0, 1>, ○ double nextGaussian() - vrací pseudonáhodná čísla typu double s normálním (tj. gaussovským) rozložením v intervalu <0, standardní-odchylka>.

Třída Scanner ● Objekty java.util.Scanner reprezentují vstupní text (např. zadávaný z klávesnice). Scanner poskytuje služby pro analýzu vstupního textu, tj. pro rozklad textu na jednotlivé elementy (token). Element je číslo, řetěz, řádka textu atp. Elementy jsou oddělené bílými mezerami (white space) tj. mezerou, tabulátorem nebo novou řádkou. ○ boolean hasNext() - vrátí true, jestliže je k dispozici další element, ○ String next() - vrátí další element, ○ boolean hasNextInt() - vrátí true, když je následující element celé číslo zobrazitelné v typu int, ○ int nextInt() - vrátí hodnotu následujícího celého čísla nebo hodí výjimku InputMismatchException, pokud na vstupu číslo není. Obdobné metody existují pro typy double, long atd.

Použití ArrayList a Scanner ● Příklad - následující metoda vrátí v objektu ArrayList všechna celá čísla zadávaná z klávesnice oddělená mezerou, tabulátorem nebo novou řádkou. Cyklus while a tedy i celá metoda se ukončí, když je na vstup zapsán znak, který není dekadická číslice resp. znaménko. Na rozdíl od pole není nutno předem znát počet zadávaných čísel: static ArrayList ctiCisla() { // objekt Scanner pro čtení elementů // zadávaných z lávesnice: Scanner s = new Scanner(System.in); ArrayList list = new ArrayList(); while (s.hasNextInt()) { list.add(s.nextInt()); } return list; }

Neměnné objekty ● Objekty, jejichž stav (tj. hodnoty instančních proměnných) je nezměnitelný nazýváme neměnné (immutable) objekty. Jsou to objekty tříd String, objekty zabalovacích tříd: Byte, Short, Character, Integer, Long, Float, Double a Boolean, a řada dalších např.: BigDecimal, BigInteger, URL ● Reference na neměnné objekty se chovají přibližně jako hodnoty primitivních typů: Integer i3 = new Integer(3); m1(i3); // metoda m1 nemůže změnit objekt Integer System.out.println(i3) // vytiskne se 3 Point p = new Point(1,2); m2(p) // metoda m2 může změnit polohu bodu System.out.println(p.getX()) // vytiskne se cokoliv

Soubory ● Soubor dat uložený trvalým způsobem na vnějším mediu se nazývá prostě soubor (file). Typické vnější medium je: ○ magnetický či optický disk, ○ flash paměť, ○ magnetická páska. ● S daty v souborech lze pracovat dvěma způsoby: ○ sekvenčním - s daty se pracuje v pořadí, jak jsou v souboru uložena. Takový soubor se nazývá proud (stream). Jako proudy označujeme i sekvenční data, která nejsou uložena na vějším mediu, ale přicházejí např. z klávesnice, sítě nebo roury. ○ náhodným - s daty se pracuje libovolně "na přeskáčku" a jednotlivé hodnoty se podobně jako v poli identifikují indexem (to nelze na všech mediích, např. ne na magnetickém pásce).

Druhy streamů ● Podle charakteru dat rozeznáváme streamy: ○ textové - jsou tvořeny posloupností znaků Unicode v některém kódování (ASCII, Windows-1250, utf-8, atd). Znaky tvoří řádky, které jsou oddělené speciálními řídícími znaky CR (carriage return) resp. LF (line feed). ○ binární - všechny ostatní např.: .jpg, .exe atp. ● Pozn.: soubory formátu .doc, .ppt atp. nejsou textové, protože kromě textů obsahují další netextovou informaci. Soubory .html resp, .xml textové však jsou. ● Dále rozeznáváme streamy: ○ vstupní - ze streamu mohou být data pouze čtena, tzn., že před vytvořením reprezentujícího objektu musí již existovat, ○ výstupní - data mohou být pouze zapisována. A na závěr je nutno operaci close.

Balík java.io ● Práce se soubory je v Javě realizována jako služby objektů, které v aplikaci příslušný soubor reprezentují. ● K tomu nabízí balík java.io mnoho speciálních tříd: ○ File - obecný soubor nebo adresář, ○ FileOutputStream - obecný binární výstupní stream, ○ FileInputStream - obecný binární vstupní stream, ○ DataOutputStream - výstupní stream primitivních typů, ○ DataInputStream - vstupní stream primitivních typů, ○ ObjectOutputStream - výstupní stream objektů, ○ ObjectInputStream - vstupní stream objektů, ○ FileWriter - výstupní textový stream, ○ FileReader - vstupní textový stream, ○ PrintWriter - výstupní textový stream s výstupní konverzí, ○ Scanner - vstupní textový stream se vstupní konverzí.

Třída File ● Objekty třídy File reprezentují diskové soubory či adresáře (a to i neexistující), ale neumožňují přístup k datům souborů. ● Objekty nabízejí základní operace se soubory tj. vytvoření, zrušení apod : ○ File(String path)- vytvoří objekt reprezentující soubor zadaný absolutní nebo relativní cestou, ○ boolean delete() - zruší soubor, pokud existuje, ○ boolean exists() - zjistí, zda soubor existuje, ○ File[] listFiles() - je-li objekt File adresář, vrátí pole souborů (resp. podadresářů) v tomto adresáři, ○ long length() - délka souboru v bytech, ○ boolean isDirectory() - vrátí true, je-li to adresář.

Výpis adresáře ● Příklad - použití objektů File pro rekurzivní výpis adresářové struktury. Výpis podadresáře je vždy odsazen o tři mezery: static void vypisAdresare(final String cesta) { vypisAdresare(new File(cesta), 0); } static void vypisAdresare(final File file, final int odsazeni) { if (odsazeni == 0) System.out.printf("%s\n", file.getName()); else System.out.printf("%" + odsazeni + "s%s\n", "", file.getName()); if (file.isDirectory()) for (File f : file.listFiles()) vypisAdresare(f, odsazeni + 3); }

Klauzule throws ● Ve většině metod tříd z balíku java.io mohou nastat chyby. Metody reagují na vznik chyby vržením některé IO výjimky (IOException). Tyto výjimky jsou tzv. kontrolované (checked), což znamená, že metoda, ve které mohou vzniknout, musí být označena klauzulí throws s typem vrhané výjimky. ● Klauzulí throws musí být označeny i metody, ve kterých se původní metoda volá, včetně např. metody main: public static void main (String ... args) throws IOException { FileInputStream fis = new FileInputStream("vstup.txt"); ... }

Třída FileInputStream ● Objekty FileInputStream reprezentují binární i textové vstupní streamy. Bez ohledu na typy dat v souboru jsou data čtena jako posloupnost bytů v přímém kódu tj. o hodnotách 0 až 255. Hodnota -1 indikuje konec souboru. ○ FileInputStream(File file) throws FileNotFoundException konstruuje stream reprezentující soubor file, ○ int read() throws IOException - přečte a vrátí jeden byte, -1 znamená konec souboru. ○ int read(byte[] b) throws IOException - čte byty do pole b až do délky b.length. Vrací počet skutečně přečtených bytů resp. -1, jestliže byl soubor celý přečten. ○ void close() throws IOException - uzavírá soubor.

Hexadecimální výpis souboru se provádí obvykle hexadecimálně po bytech - typicky šestnáct na řádku: static void hexadecimalniVypisSouboru( final String cesta) throws IOException { FileInputStream fs = new FileInputStream(new File(cesta)); int count = 0; for (int c = fs.read(); c != -1; c = fs.read()) { System.out.printf("%2x ", c); if (++count % 16 == 0) // po každých 16 bytech System.out.println(); } }

Příklad výstupu: 46 2f 4d 41 4e 49 46 45 53 54 2e 4d 46 4d 61 6e 69 66 65 73 74 2d 56 65 72 73 69 6f

Třída FileOutputStream ● Objekty FileOutputStream reprezentují binární nebo textové výstupní soubory: ○ FileOutputStream(File file) throws FileNotFoundException konstruuje stream reprezentující soubor file, ○ void write(byte[] buffer) throws IOException - zapíše do souboru pole bytů buffer, ○ void write(int b) throws IOException - zapíše do souboru jeden byte b, ○ void close() throws IOException - uzavře soubor, což znamená, že se všechna data, která jsou dosud ve vyrovnávacích pamětech, zapíší fyzicky na disk.

Kopírování bytových souborů static void kopieSouboru(final String vstup, final String vystup) throws IOException { FileInputStream fis = new FileInputStream(new File(vstup)); FileOutputStream fos = new FileOutputStream(new File(vystup)); byte[] buffer = new byte[1024]; for (int len = fis.read(buffer); len != -1; len = fis.read(buffer)) { fos.write( buffer, 0, len ); } fos.close(); }

Datové streamy ● Výstupní datový stream DataOutputStream slouží k zápisu hodnot primitivních typů: ○ DataOutputStream(FileOutputStream in) - konstruuje z objektu FileOutputStream nový objekt DataOutputStream, ○ void writeXXX(XXX value) throws IOException - kde XXX jsou jednotlivé primitivní typy - zapíše do streamu binární hodnotu primitivního typu. ● Vstupní datový stream DataInputStream slouží ke čtení hodnot primitivních typů: ○ DataInputStream(FileInputStream in) - konstruuje z objektu FileInputStream nový objekt DataInputStream, ○ XXX readXXX() throws IOException - přečte ze streamu a vrátí hodnotu primitivního typu.

Serializace (1/2) ● Do binárního streamu lze zapsat jedinou operací celý objekt včetně všech všech objektů, které jsou z něj referencovány. Tato operace se nazývá serializace a týká se, kromě jiných, především objektů: ○ polí, ○ String, ○ objektů zabalovacích tříd, ○ ArrayList, ○ BigDecimal, ○ BitSet, ○ atd. ● Pro zápis resp. čtení celých objektů se používají objekty ObjectOutputStream a ObjectInputStream.

Serializace (2/2) ● ObjectOutputStream(FileOutputStream in) throws IOException - konstruuje objekt ObjectOutputStream

z objektu FileOutputStream, ● void writeObject(Object obj) throws IOException - zapíše do streamu objekt obj, ● ObjectInputStream(FileInputStream in) throws IOException - konstruuje objekt ObjectInputStream z

objektu FileInputStream, ● Object readObject() throws IOException, ClassNotFoundException - přečte objekt

ze streamu a vrátí jeho referenci. Vrácená reference se musí přetypovat na očekávaný refereční typ: String [] pole = (String [])ois.readObject();

Serializace pole static void testZapisuPole() throws Exception { double[] rnd = new double[1000]; double sum1 = 0; for (int i = 0; i < rnd.length; i++) // vytvoření sum1 += rnd[i] = Math.random(); // náhodného pole ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("r.tmp")); oos.writeObject(rnd); // zápis pole do souboru oos.close(); ObjectInputStream ois = new ObjectInputStream(new FileInputStream("r.tmp")); rnd = (double[]) ois.readObject(); // čtení pole double sum2 = 0; for (double d : rnd) sum2 += d; System.out.printf("Soucet zapsaneho pole= %f\n", sum1); System.out.printf("Soucet precteneho pole= %f\n", sum2); }

Textové streamy Základní třídy FileReader a FileWriter umožňují čtení resp. zápis textových streamů: ● FileReader(File file) throws FileNotFoundException -

- konstruuje objekt FileReader, ● int read() throws IOException - přečte z objektu FileReader jeden znak, -1 znamená konec streamu. ● FileWriter(File file) throws IOException - konstruuje objekt FileWriter, ● void write(int c) throws IOException - zapíše do streamu jeden znak.

Kopírování textových souborů public static void main( String[] args ) throws Exception { copy( "in.txt", "out.txt" ); } // Buffered ~ čte resp. zapisuje celé řádky resp. řetězy. static void copy(final String in, final String out) throws IOException { BufferedReader br=new BufferedReader(new FileReader(in)); BufferedWriter bw=new BufferedWriter(new FileWriter(out));

String s = null; while ( (s = br.readLine( ) ) != { bw.write( s ); bw.newLine( ); } br.close(); bw.close(); }

null )

Třída Scanner (1/2) ● Objekt Scanner reprezentuje vstupní textový stream a nabízí rozklad textu na jednotlivé řádky nebo elementy (token) což jsou části textu oddělené bílou mezerou ( tj. mezera, tabulátor nebo nová řádka): ○ Scanner(File source) throws FileNotFoundException konstruuje objekt Scanner, ○ boolean hasNext() - vrátí true, je-li k dispozici další element, ○ String next() - přečte a vrátí další element, ○ boolean hasNextLine() - vrátí true, je-li k dispozici další řádka, ○ String nextLine() - přečte a vrátí zbytek aktuální řádky.

Třída Scanner (2/2) ● Scanner rozeznává na vstupu i formát elementu, a je-li element číslo, zkonvertuje jej do vnitřní reprezentace: ○ boolean hasNextInt(), ○ int nextInt(), ○ boolean hasNextDouble(), ○ int nextDouble(), ○ taktéž i pro další primitivní typy.

● Příklad: static void vypisSouboruPoRadcich( final String vstup ) throws FileNotFoundException { Scanner s = new Scanner( new File(vstup) ); while (s.hasNextLine()) { System.out.println( s.nextLine() ); } }

Analýza textového souboru ● Následující metoda sečte hodnotu všech čísel v textovém souboru avšak nečíselné elementy ignoruje: static double soucetCiselVSouboru( String vstup ) throws FileNotFoundException { double sum = 0; Scanner sc = new Scanner( new File(vstup) ); while (sc.hasNext()) { if (sc.hasNextDouble()) { sum += sc.nextDouble(); } else { sc.next(); } } return sum; }

Statické proměnné (1/2) Druhy (kind) proměnných (nezaměňovat za typy proměnných !!): ○ proměnné existující od zavolání do ukončení metody: ■ parametry, ■ lokální proměnné, ○ proměnné existující po dobu života objektu: ■ elementy pole, ■ instanční proměnné, ○ proměnné existující po celou dobu běhu programu: ■ statické proměnné - slouží k uchování hodnot potřebných po celou dobu běhu programu. Deklarují se přímo ve třídě s modifikátorem static: class Main { static int dosavadniPocetPokusu = 0; ... }

Statické proměnné (2/2) ● Na rozdíl od lokálních proměnných se statické proměnné dle svého typu automaticky inicializují na implicitní hodnotu: ○ aritmetické typy (včetně char) na hodnotu 0, ○ typ boolean na hodnotu false, ○ referenční typy na hodnotu null. ● Předcházející deklarace je tedy ekvivalentní s deklarací: static int dosavadniPocetPokusu;

● Pozn.: Pokud se do statické proměnné přiřadí reference na objekt, bude také tento objekt a tedy jeho instanční proměnné (resp. elementy pole) existovat po celou dobu běhu programu: class Main { static int[] delkyMesicu = {31,28,31,30,31,30,31,31,30,31,30,31}; }

Použití statických proměnných ● Statické proměnné umožňují metodám přístup ke společným hodnotám, aniž by je bylo nutno předávat jako parametry. ● Příklad: class Main { static int dosavadniPocetPokusu = 0; static void pokus() { dosavadniPocetPokusu++; // vlastní kód pokusu ... } public static void main (String ...args) { // opakované volání metody pokus ... System.out.printf("Dosavadni pocet pokusu byl%d\n", dosavadniPocetPokusu); } }

Modifikátor private ● Chceme-li zabránit, aby proměnná či metoda byla přístupná z jiné třídy než ve které je deklarovaná, pak označíme deklaraci proměnné nebo metody klíčovým slovem private. ● Pokud chceme, aby hodnota privátní proměnné byla z jiné třídy čitelná, vytvoříme speciální metodu tzv. getter: class Main { private static int dosavadniPocetPokusu = 0; static void pokus() { dosavadniPocetPokusu++; // vlastní kód pokusu ... } static int getDosavadniPocetPokusu() { return dosavadniPocetPokusu; }

Datové struktury ● Datové struktury (kontejnery, kolekce) jsou sady hodnot, uspořádáné specifickým způsobem tak, aby měly požadované vlastnosti. Přístup k datům datové struktury je realizován metodami, které data ve struktuře modifikují nebo data ze struktury čtou. ● Datové struktury mohou být vytvořeny: ○ v souborech, ○ ve vnitřní paměti. ● Datové struktury v paměti lze realizovat dvojím způsobem: ○ polem, ○ spojovými strukturami. ● Pozn.: pole můžeme chápat také jako jednoduchou datovou strukturu, do níž je přístup realizován přímo konstrukcemi programovacího jazyka - tj. indexací.

Zásobník ● Datová struktura zásobník (stack) má následující vlastnosti: ○ udržuje stálé pořadí vložených elementů, ○ lze najednou vložit či vybrat jen jeden prvek, ○ vklad i výběr se děje na stejném konci zásobníku. ● Důsledek: prvky se ze zásobníku vyjímají v opačném pořadí, než do něj byly vloženy. Proto je jiné jméno pro zásobník LIFO (Last In First Out). ● Pozn. překlad angl. termínu stack (stoh, hranice) do češtiny pochází z podobnosti chování pistolového zásobníku a datové struktury stack:

Operace na zásobníku ● Zásobník má dva konce: 1. vrchol (top) - konec zásobníku, do kterého se prvky vkládají a ze kterého se vybírají, 2. dno (bottom) - opačný konec zásobníku. ● Základní operace nad zásobníkem: ○ push - vložení prvku na vrchol, ○ pop - přečtení a vyjmutí prvku z vrcholu, ○ peek - přečtení prvku z vrcholu, aniž by byl vyjmut. Operace mají konstantní složitost O(1). ● Při realizaci zásobníku je potřeba označovat aktuální polohu vrcholu zásobníku. K tomu obvykle slouží proměnná (resp. registr), která se standardně nazývá Stack Pointer (SP).

Implementace zásobníku (1/3) ● Zásobník budeme implementovat samostatnou třídou se dvěma privátními statickými proměnnými: pole data na uložená elementy a index sp, který ukazuje na vrchol zásobníku tj. na poslední vložený prvek: class Zasobnik { private static double[] data; private static int sp; static void init(int n) { data = new double[n]; sp = -1; } static int size() { return sp + 1; } static boolean isEmpty() { return size() == 0; }

Implementace zásobníku (2/3) static boolean isFull() { return size() == data.length; } static void push(final double element) { if (isFull()) throw new IllegalStateException("Plný zásobník"); data[++sp] = element; } static double peek() { if (isEmpty()) throw new IllegalStateException("Prázdný zásobník"); return data[sp]; } static double pop() { if (isEmpty()) throw new IllegalStateException("Prázdný zásobník"); return data[sp--]; }

Implementace zásobníku (3/3) ● Pro výpis obsahu zásobníku do řetězu využijeme objekt StringBuilder: static String toText() { StringBuilder sb = new StringBuilder("["); for (int i = 0; i < size(); i++) { sb.append(data[i]); if (i < size() - 1) { sb.append(", "); } } sb.append("]"); return sb.toString(); }

● Pozn.: Zásobník a další struktury v této přednášce by bylo lépe implementovat jako objekty (viz třída ArrayList). Tento způsob však vyžaduje podrobnou znalost OOP a přesahuje tak obsah předmětu alg.

Použití zásobníku (1/2) Příklad - obrátit pořadí zadané posloupnosti pomocí zásobníku: static void vypisObracene() { System.out.println("Napiš posloupnost čísel"); System.out.println("oddělených bílými mezerami"); System.out.println( "zakončenou libovolným písmenem"); Zasobnik.init(1000); Scanner scanner = new Scanner(System.in); while (scanner.hasNextDouble()) { Zasobnik.push(scanner.nextDouble()); } while (!Zasobnik.isEmpty()) { System.out.println(Zasobnik.pop()); } }

Použití zásobníku (2/2) ● V programech se zásobník používá: ○ při analýze textu, ○ při procházení jiných datových struktur, ● Pomocí zásobníku dokáže program vypočítat (vyhodnotit) výrazy, které nejsou v programu přímo zapsány, ale jsou programu předloženy jako data v textové formě. Výraz však musí být zadán v postfixové notaci, ve které je operátor uveden až za operandy: normální forma (infixová)

postfixová forma

a+b

ab+

+ ● Pozn. : V postfi(xao*vbé) +focrmě zá apisbu* cne jsou potřeba závorky, protože pořadí výpočtu je vždy dáno pořadím operátorů.

Výpočet výrazu na zásobníku (1/2) ● Příklad: výpočet výrazu 5 * ( 4 + 3) na zásobníku 1. výraz se zapíše v postfixové formě tj. 5 4 3 + * 2. výraz se postupně čte a pokud je ve výrazu: ■ operand - uloží se na zásobník, ■ binární operace - vyzvednou se ze zásobníku dva operandy, provede se s nimi požadovaná operace a výsledek se vrátí na zásobník, ■ konec - v zásobníku je výsledek výpočtu.

● V následujícím příkladu se předpokládá, že výraz je v postfixové formě a operandy jsou tvořeny jednotlivými dekadickými číslicemi bez oddělujících mezer.

Výpočet výrazu na zásobníku (2/2) static double vypocti(String vyraz) { // např.:"543+*" Zasobnik.init(100); for (int i = 0; i < vyraz.length(); i++) { char c = vyraz.charAt(i); switch (c) { case '+': { int op2 = Zasobnik.pop(); int op1 = Zasobnik.pop(); Zasobnik.push(op1 + op2); break; } // obdobně pro další operátory: -, *, / default: if (c < '0' || c > '9') throw new IllegalArgumentException("Chyba:" + c); Zasobnik.push(c - '0'); // hodnota číslice c } } double val = Zasobnik.pop(); if (!Zasobnik.isEmpty()) throw new IllegalArgumentException("Chybny vyraz"); return val; }

Seznam ● Datová struktura seznam (list) je velmi podobná poli, protože je tvořena posloupností elementů, z nichž každý má svůj index. Na rozdíl od pole je však počet prvků v seznamu proměnný. Seznam má následující operace: ○ get - čtení prvku ze zadaného indexu, ○ set - zápis na daný index, ○ add - přidání prvku na daný index - původní a všechny následující prvky se odsunou o jednu pozici, takže se žádný prvek neztratí, ○ remove - odstranění prvku ze zadaného indexu následující prvky se posunou o jeden index dopředu. ● Při implementaci seznamu polem mají operace get a set stejně jako u pole konstantní složitost O(1). Operace add a remove mají složitost lineární O(n), protože prvky je nutno v poli posouvat.

Implementace seznamu (1/3) class Seznam { private static double[] data; private static int size; private static void checkIndex() { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); } static void init(final int n) { data = new double[n]; size = 0; } static int size() { return size; }

Implementace seznamu (2/3) static boolean isFull() { return size = data.length; } static double get(final int index) { checkIndex(index); return data[index]; } static void set(final int index,final double element) { checkIndex(index); data[index] = element; }

Implementace seznamu (3/3) static void add(final int index,final double element) { if (isFull) throw new IllegalStateException("Plny seznam"); if (index != size) { checkIndex(index); System.arraycopy(data, index, data, index + 1, size - index); } data[index] = element; size++; } static double remove(final int index) { checkIndex(index); double val = data[index]; size--; System.arraycopy(data,index+1,data,index,size-index); return val; }

Realokace seznamu ● Aby se kapacita seznamu přizpůsobovala vloženým datům, můžeme datové pole realokovat: static void add(final int index,final double element){ if (index < 0 || index > size) throw new IndexOutOfBoundsException(); if (isFull()) { // zvětšení datoveho pole o 20% double[] tmp = new double[(int) ((data.length + 1) * 1.2)]; System.arraycopy(data, 0, tmp, 0, index); System.arraycopy(data, index, tmp, index + 1, size - index); data = tmp; } else { System.arraycopy(data, index, data, index + 1, size - index); } data[index] = element; size++; }

Fronta ● Datová struktura fronta je speciální druh seznamu, ve kterém lze vyjímat prvky pouze ze začátku a přidávat pouze na konec. Protože první přidaný prvek je z fronty také první vyjmut, nazývá se fronta také FIFO (First In First Out). ● Operace nad frontou: ○ addLast - přidání prvku na konec fronty, ○ removeFirst - přečtení a odebrání prvku ze začátku fronty. ● Fronta se užívá např. v paralelních programech k předávání dat mezi paralelně běžícími vlákny nebo procesy. ● Frontu lze implementovat jako seznam avšak výhodnější implementace je tzv. kruhová fronta.

Kruhová fronta ● V kruhové frontě při výběru prvku nedochází k přesunu ostatních prvků ale změní se jen index začátku fronty (head). Složitost operací addLast a removeFirst je tedy konstantní: O(1). Inkrementace indexů se však musí provádět modulo délka pole. ● Na obrázku znamená 1.p první prvek ve frontě, 2.p druhý prvek atd. Index tail ukazuje na první volné místo:

Implementace kruhové fronty (1/2) class KruhovaFronta { private static double[] data; private static int head = 0; private static int size = 0; static void init(final int capacity) { data = new double[capacity]; head = 0; size = 0; } static int size() { return size; } static boolean isEmpty() { return size == 0; } static boolean isFull() { return size == data.length; } }

Implementace kruhové fronty (2/2) static void addLast(final double element) { if (isFull()) throw new IllegalStateException("Plna fronta"); int tail = (head + size) % data.length; data[tail] = element; size++; } static double removeFirst() { if (isEmpty()) throw new IllegalStateException("Prazdna fronta"); double first = data[head]; head = (head + 1) % data.length; size--; return first; } }

Množina ● Množina (set) je datová struktura, která stejně jako matematická množina obsahuje každý prvek nejvýše jednou. Základní operace nad množinou: ○ add - přidání prvku do množiny, ○ contains - test, zda je prvek v množině přítomen, ○ remove - odebrání prvku z množiny. ● Další možné operace nad množinou jsou matematické operace: ○ sjednocení (union), ○ průnik (intersection).

Celočíselná množina ● Pokud je množina tvořena celými nezápornými čísly, je ji možno jednoduše implementovat charakteristickou funcí: class MnozinaInt { private static boolean[] data; static void init(int n) { data = new boolean[n]; } static boolean contains(int element) { return data[element]; } static void add(int element) { data[element] = true; } static void remove(int element) { data[element] = false; } }

Seřazená množina ● Seřazená množina (ordered set) je implementace množiny polem, která navíc udržuje prvky uspořádané podle velikosti. ● Uspořádání prvků umožňuje implementovat operaci contains algoritmem půlení s logaritmickou složitostí O(log n). Ostatní operace mají složitost lineární t.j. O(n). ● Pozn.: v metodě add se se hledaný prvek nejprve uloží na konec jako tzv. zarážka (sentinel), a pak se teprve pole prohledává. Jestliže se při hledání jako první nalezne zarážka, znamená to, že prvek v množině nebyl přítomen.

Seřazená množina (1/3) class SerazenaMnozina { // privátní část private static double data[]; private static int size; private static int find(final double element) { // hledání půlením int lowInd = 0; int highInd = size - 1; while (lowInd <= highInd) { int mInd = (lowInd + highInd) / 2; double datamInd = data[mInd]; if (datamInd == element) return mInd; if (datamInd < element) lowInd = mInd + 1; else highInd = mInd - 1; } return -1; // prvek nebyl nalezen }

Seřazená množina (2/3) // veřejná část static void init(final int n) { data = new double[n]; size = 0; } static boolean isEmpty() { return size == 0; } static boolean isFull() { return size == data.length; } static int size() { return size; } static boolean contains(final double element) { return find(element) >= 0; }

Seřazená množina (3/3) static void add(final double element) { if (isFull()) throw new IllegalStateException("Plna mnozina"); data[size] = element; // zarážka int i = 0; while (data[i] < element) i++; if (i == size) { // nalezena zarážka size++; return; } if (data[i] == element) // prvek už byl přítomen return; System.arraycopy(data, i, data, i + 1, size - i); data[i] = element; // vložení nového prvku size++; }

Opakování OOP ● V minulých přednáškách jsme postupně zaváděli a používali následující konstrukce OOP: ○ přednášky 1 až 3 - deklarace statických metod ve třídě ○ přednášky 4 až 8 - vytváření objektů - polí, ○ přednáška 9 - vytváření objektů ze tříd definovaných v Java API a používání referencí ○ přednáška 11 - deklarace statických proměnných ● Třídy se tedy používají dvojím způsobem a sice: 1. kontext pro deklaraci statických metod a proměnných, 2. vzory pro vytváření instancí tříd. ● Pozn.: V praxi se oba způsoby kombinují v rámci jedné třídy. V těchto přednáškách však pro větší přehlednost používáme konkrétní třídu pouze k jednou z těchto účelů.

Instanční proměnné ● Pokud se třída používá jako vzor pro vytváření instancí, je třeba ve třídě deklarovat proměnné, jež tvoří stav objektu. Tyto proměnné se nazývají instanční proměnné. ● Instanční proměnné se chovají podobně jako prvky pole. ○ vznikají v okamžiku vytvoření instance operátorem new, ○ zanikají v okamžiku zániku instance. ● Pozn.: podobně jako se statickými proměnnými korespondují statické metody s instančními proměnnými korespondují instanční metody. Jejich deklarace vyžaduje hlubší znalost OOP a přesahuje tak náplň předmětu ALG.

Deklarace instančních proměnných ● Příklad - deklarace třídy KomplexniCislo pouze s instančními proměnnými: class KomplexniCislo { double re; // instanční proměnné nemají double im; // modifikátor static ! }

● Operátor new se jménem třídy vytvoří nový objekt KomplexniCislo a vrátí referenci na tento objekt. Objekt bude obsahovat instanční proměnné re a im. ● Přístup k instančním proměnným je tvořen referencí na objekt, operátorem tečka a jménem instanční proměnné: KomplexniCislo kc = new KomplexniCislo(); kc.re = 1.0; kc.im = 2.5; ... kc = null; // objekt zanikl

Třída versus Instance ● Deklarace třídy a jednotlivé instance třídy (tj. objekty) k sobě mají stejný vztah jako např. technologický plán k výrobkům, které byly podle toho plánu vyrobeny. ● Instanční proměnné sídlí v instancích třídy, existuje jich v daném okamžiku právě tolik, kolik existuje instancí třídy. ● Statické proměnné existují vždy pouze v jediném exempláři. ● Příklad: čtyři instance třídy KomplexniCislo:

Spojové struktury ● Do referenční instanční proměnné, lze přiřadit referenci na jiný objekt a tak vytvářet v paměti tzv. spojové struktury. Objekty spojových struktur nazýváme uzly (node). Kromě referencí obsahuje uzel vždy také nějakou uloženou hodnotu: class SpojovyUzel { int hodnota; // inicializuje se na 0 SpojovyUzel dalsi; // inicializuje se na null } ... SpojovyUzel prvni = new SpojovyUzel(); prvni.dalsi = new SpojovyUzel(); prvni.dalsi.dalsi = new SpojovyUzel();

Spojové struktury ● Datové struktury lze implementovat i spojovými strukturami, kde každý prvek datové struktury je uložen v jednom uzlu a tento uzel je jednou či více referencemi napojen na další uzly. ● Takto realizovaná datová struktura bude obsahovat stejné metody jako struktura realizovaná polem, avšak s jinou implementací. Metody se však lišívají časovou složitostí. ● Spojová struktura musí mít vždy alespoň jednu (resp. více) statickou proměnnou, referující na první (resp. poslední) uzel struktury. ● Implementace spojovými strukturami mají větší paměťovou náročnost než implementace pomocí pole. Avšak spojové struktury nejsou prostorově omezeny a tedy mohou využít celý dostupný paměťový prostor.

Spojový zásobník (1/3) ● Při implementace zásobníku spojovou strukturou obsahuje privátní statická proměnná sp referenci na uzel, který tvoří vrchol zásobníku: class SpojovyZasobnik { // reference na vrchol zasobniku private static SpojovyUzel sp; // smazani zasobniku static void clear() { sp = null; // všechny uzly zaniknou } static boolean isEmpty() { return sp == null; }

Spojový zásobník (2/3) static void push(double value) { SpojovyUzel pom = new SpojovyUzel(); pom.value = value; pom.next = sp; // dosavadní vrchol se stane // druhým uzlem sp = pom; // nový uzel se stane vrcholem } static double pop() { if (isEmpty()) throw new IllegalStateException("Prazdny zasobnik"); double val = sp.value; sp = sp.next; // druhý uzel se stane vrcholem return val; } ... }

Spojový zásobník (3/3) ● Pro vytvoření textové formy obsahu zásobníku je potřeba cyklem projít celou strukturu. Řídící proměnnou cyklu je v tomto případě referenční proměnná p, která postupně během iterace ukazuje na jednotlivé uzly. ● Přechod na další uzel se provede přiřazením: p = p.next. static String toText() { StringBuilder sb = new StringBuilder("["); for (SpojovyUzel p = sp; p != null; p = p.next) { sb.append(p.value); if (p.next != null) { sb.append(", "); } } return sb.append(']').toString(); }

Spojová fronta (1/2) ● Fronta (queue) dovoluje přístup k oběma koncům, ježto má ukazatel na první i na poslední uzel. ● Těmito ukázané prvky se nazývají hlava (head) a ocas (tail). class SpojovaFronta { private static SpojovyUzel head; private static SpojovyUzel tail; static void clear() { head = null; tail = null; } static boolean isEmpty() { return head == null; }

Spojová fronta (2/2) static void addLast(double value) { SpojovyUzel tmp = new SpojovyUzel(); tmp.value = value; if (isEmpty()) // u jednoprvkové fronty je poslední zároveň první head = tmp; else tail.next = tmp; tail = tmp; } static double removeFirst() { if (isEmpty()) throw new IllegalStateException("Fronta je prazdna"); double first = head.value; head = head.next; return first; }

Spojový seznam ● Ve spojových strukturách, ve kterých má každý uzel pouze referenci na následníka se obtížně provádí modifikace uprostřed struktury. Proto se spojový seznam vytváří s uzlů, které mají referenci jak na následníka, tak na předchůdce. Takovým spojovým strukturám se říká obousměrně zřetězené (double linked). ● Uzel obousměrně zřetězené struktury: class ObousmernyUzel { // bidirectional node double value; ObousmernyUzel next; ObousmernyUzel previous; }

Obousměrná struktura Hle:

Spojový seznam (1/4) Základem implementace je privátní metoda findNode, která nalezne referenci uzlu na zadaném indexu: class SpojovySeznam { // privátní část private static ObousmernyUzel first; private static int size; private static ObousmernyUzel findNode(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); ObousmernyUzel node = first; if (index < size / 2) for (int i = 0; i < index; i++) node = node.next; // hledání dopředu else for (int i = 0; i < size - index; i++) node = node.previous; // hledání pozpátku return node; }

Spojový seznam (2/4) ● Vložení nového prvku do obousměrného seznamu vyžaduje změnit reference jak v jeho předchůdci, tak v následníku (původní reference jsou tečkované, nové červeně):

● Obdobně je třeba postupovat při vyjímání prvku.

Spojový seznam (3/4) ● Metoda findNode se využívá pro implementaci veřejných metod get, set, add a remove: static double get(final int index) { ObousmernyUzel p = findNode(index); return p.value; } static void set(final int index, final double element) { ObousmernyUzel p = findNode(index); p.value = element; } static void remove(final int index) { ObousmernyUzel node = findNode(index); node.next.previous = node.previous; node.previous.next = node.next; size--; if (node == first) // vyjímá se první prvek first = node.next; }

Spojový seznam (4/4) static void add(final int index, double element) { ObousmernyUzel newNode = new ObousmernyUzel(); newNode.value = element; if (isEmpty()) { if (index != 0) throw new IndexOutOfBoundsException(); newNode.next = newNode; newNode.prev = newNode; } else { ObousmernyUzel nextNode; if (index == size) nextNode = first; else nextNode = findNode(index); newNode.next = nextNode; newNode.prev = nextNode.previous; newNode.next.prev = newNode; newNode.prev.next = newNode; } if (index == 0) first = newNode; size++; }

Poznámky ● Termín "spojový seznam" se často omylem používá pro spojové struktury vůbec. Je potřeba důsledně rozlišovat mezi druhem datové struktury (tj. seznam, množina, fronta atd.) a její implementací tj. spojově nebo polem. ● Spojový seznam má omezenou použitelnost, protože hlavní operace get má lineární časovou složitost na rozdíl od konstantní složitosti v seznamu implementovaném polem. Obousměrná spojová struktura se hodí nejvíce pro implementaci oboustrané fronty (deque = double end queue), která však přesahuje rámec předmětu ALG.

Binární vyhledávací strom ● BVS - binární vyhledávací strom (BST - binary search tree) je spojová struktura, která má následující tvar:

Vlastnosti BVS (1/2) 1. Strom může být prázdný. Neprázdný strom má právě jeden uzel, zvaný kořen (root), na který žádný jiný uzel stromu neukazuje. 2. Na každý uzel stromu krom kořene ukazuje právě jeden uzel, který se nazývá rodič (parent). 3. Každý uzel stromu ukazuje na žádný, jeden nebo dva potomky (children). Potomci jsou levý (left) a pravý (right). 4. Uzel, který neukazuje na žádný jiný (tj. nemá potomky) se nazývá list (leaf). 5. Levý (resp. pravý) potomek a všichni jeho potomci se nazývají levý (resp. pravý) podstrom (může být i prázdný). 6. Hodnota uzlu je větší než všechny hodnoty v jeho levém podstromu a menší než všechny hodnoty v jeho pravém podstromu. Což platí pro všechny uzly ( i kořen ).

Vlastnosti BVS (2/2) ● Další vlastnosti BVS: ○ Hloubkou stromu h nazýváme délku nejdelší cestu od kořene k listům. Prázdný strom má hloubku 0. ○ Pravidelný strom je takový, kde každý uzel, který není list, má oba potomky. U pravidelného stromu je počet uzlů: n = 2h - 1 resp. h = log 2(n + 1). ○ Pokud se délka cesty od kořene k listům liší nejvíce o 1 (t.zn. že listy se nacházejí ve dvou sousedních patrech) nazýváme strom vyvážený (balanced tree). ● Příklad: na obrázku je nepravidelný, ale vyvážený strom. Kořen má hodnotu 10 a hodnoty v jeho levém podstromu jsou {2, 5, 7} < 10 a v pravém podstromu {13, 15} > 10.

Množina implementovaná BVS (1/5) ● BVS je velmi vhodný pro implementaci množiny, neboť dvě nejdůležitější operace nad množinou contains a add mají složitost O(h) a tedy pro vyvážený strom O(log n). ● Uzly BVS jsou objekty třídy: class UzelStromu { double value; UzelStromu left; UzelStromu right; }

● Třída StromovaMnozina obsahuje privátní statickou promennou root: class StromovaMnozina { private static UzelStromu root;

Množina implementovaná BVS (2/5) ● Základem implementace jsou dvě privátní rekurzivní metody contains a add.: private static boolean contains( final UzelStromu node, final double value) { if (node == null) // prázdná množina return false; if (node.value == value) // prvek nalezen return true; if (node.value > value) { // hledání v levém podstromu return contains(node.left, value); } else { // hledání v pravém podstromu return contains(node.right, value); } }

Množina implementovaná BVS (3/5) private static void add(final UzelStromu node, final double value) { if (value == node.value) // prvek již obsažen return; if (value < node.value) { // vkládání do levého podstromu if (node.left == null) { // není levý potomek node.left = new UzelStromu(); node.left.value = value; } else add(node.left, value); } else { // vkládání do pravého podstromu if (node.right == null) { // není pravý potomek node.right = new UzelStromu(); node.right.value = value; } else add(node.right, value); } }

Množina implementovaná BVS (4/5) ● Privátní metody jsou potom využity ve veřejných metodách contains a add: static boolean contains(final double value) { return contains(root, value); } static void add(final double value) { if (root == null) { root = new UzelStromu(); root.value = value; } else { add(root, value); } }

● Pozn.: Profesionální implementace vyžaduje i vyjmutí prvku ze stromu, které však vyžaduje jeho rekonstrukci, a dále by metoda add by prováděla vyvažování stromu. Tyto algoritmy však přesahují náplň předmětu ALG.

Množina implementovaná BVS (5/5) ● Také výpis BVS je tvořen kombinací privátní rekurzivní a veřejné metody: private static void appendText( final StringBuilder sb, final UzelStromu node) { if (node.left != null) { //výpis levého podstromu appendText(sb, node.left); sb.append(", "); } sb.append(node.value); if (node.right != null) {//výpis pravého podstrom sb.append(", "); appendText(sb, node.right); } } static String toText() { StringBuilder sb = new StringBuilder("["); appendText(sb, root); return sb.append(']').toString(); }