Programovanie (2) v Jave
1-INF-166, LS 2017/18

Úvod · Pravidlá · Prednášky · Netbeans · Testovač · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· DÚ10 je zverejnená, odovzdávajte do stredy 16.5. 22:00.
· Bonusový projekt odovzdávajte do pondelka 21.5. 22:00 na testovači. Predvádzanie projektov bude po prvom termíne skúšky v stredu 23.5. (t.j. začneme medzi 11:45 a 12:00 v H6). Ak vtedy nemôžete prísť, kontaktujte vyučujúce, dohodneme iný termín.
· Opravný/náhradný test bude v pondelok 28.5. o 10:00 v F1-108. V prípade záujmu sa prihláste v AISe.
· Na termíny skúšok sa zapisujte v AIS. Termíny: streda 23.5. (riadny), štvrtok 7.6. (riadny alebo 1. opravný), streda 20.6. (1. alebo 2. opravný) plus v prípade potreby ešte jeden termín v poslednom týždni skúškového. Prípadné konflikty nám dajte vedieť čím skôr. Ďalšie informácie na stránke Test a skúška.


Prednáška 36

Z Programovanie
Prejsť na: navigácia, hľadanie

Oznamy

  • Dnešná prednáška: hľadanie maximálnej kliky, vaše otázky, ukážka OOP v C++
  • Poslednú DÚ odovzdávajte do stredy
  • Tento piatok 18.5. o 13:00 v posluchárni B záverečná písomka
  • Prvý termín skúšky v stredu 23.5.
  • Projekty odovzdávajte do pondelka 21.5. 22:00, predvádzanie bude možné v stredu po skúške alebo po dohode v inom čase

Zhrnutie

Čo by ste mali po dvoch semestroch vedieť

  • Základy jazykov C/C++, Java: cykly, podmienky, premenné, funkcie, primitívne typy, polia, alokovanie pamäte, reťazce, súbory
  • Základy OOP, triedy, dedenie, polymorfizmus, výnimky, generické programovanie
  • Základy tvorby GUI v JavaFX
  • Dátové štruktúry: spájaný zoznam, zásobník a rad, binárne stromy a ich využitie (vyhľadávacie, lexikografické, aritmetické, rozhodovacie,...), hešovacie tabuľky
  • Základné algoritmy: triedenia, binárne vyhľadávanie, prehľadávanie grafov a stromov, prehľadávanie s návratom
  • Vymyslieť jednoduchý algoritmus, vedieť ho napísať a odladiť, porozumieť hotovým programom

Nadväzujúce predmety

  • Algoritmy a dátové štruktúry (2/Z) a Tvorba efektívnych algoritmov (2/L): viac algoritmov a dátových štruktúr, časová zložitosť
  • Programovanie (3) (2/Z): viac programovania v Jave, návrhové vzory, vlákna
  • Ročníkový projekt (1) a (2): píšete väčší program na tému podľa vlastného výberu
    • Neskôr na túto tému môžete (ale nemusíte) nadviazať bakalárskou prácou
  • Rýchlostné programovanie: riešenie úloh z programátorských súťaží, precvičenie programovania, algoritmov, hľadania chýb
  • Medzi ďalšie školské aktivity súvisiace s programovaním patrí aj študentský vývojový tím

Prehľadávanie do hĺbky / do šírky / s návratom

  • Prehľadávanie grafu do hĺbky a do šírky sú rýchle algoritmy, ktoré navštívia každý vrchol iba raz
    • Prehľadávanie do hĺbky je rekurzívne, zistí, či sú dva vrcholy spojené cestou
    • Prehľadávanie do šírky používa rad (frontu), nájde najkratšiu cestu
  • Prehľadávanie s návratom (backtracking) je všeobecná technika na generovanie všetkých postupností určitého typu
    • Riešili sme ňou napr. problém 8 dám, sudoku a pod.
    • Dá sa použiť aj na grafoch, keď potrebujeme pozrieť všetky cesty, všetky podmnožiny vrcholov a pod.
    • Čas výpočtu je exponenciálny, použiť sa dá iba na veľmi malých vstupoch
    • Používame iba vtedy, ak nevieme nájsť rýchlejší algoritmus

Pozor, na DÚ10 máte použiť prehľadávanie do šírky, na skúške prehľadávanie s návratom

Opakovanie backtracky na grafe

  • Na predminulej prednáške boli príklady na prehľadávanie grafu s návratom
    • Hľadanie ciest dĺžky k
    • Hľadanie najdlhšej cesty v neohodnotenom grafe
    • Hľadanie najdlhšej cesty v ohodnotenom grafe
  • Pri riešení sme postupne vytvárali cestu pridávaním potenciálnych vrcholov do nej a následným kontrolovaním situácie (hotové riešenie, slepá vetva)

Hľadanie maximálnej kliky

  • Pozrime sa teraz na iný typ problému, nehľadáme cestu, ale množinu vrcholov
  • Klika je taká množina vrcholov, v ktorej sú každé dva vrcholy spojené hranou
  • Maximálna klika je klika s najväčším počtom vrcholov v danom grafe

Graf G=(V,E), kde V={0,...,4} a E={{0,1},{0,2},{0,3},{1,2},{2,3},{2,4},{3,4}} obsahuje niekoľko klík veľkosti 3, ale žiadnu kliku veľkosti 4

Maximalna klika: [0, 1, 2]

Po pridaní hrany {0,4} dostávame kliku veľkosti 4:

Maximalna klika: [0, 2, 3, 4]

Jednoduchšia verzia

Hľadanie maximálnej kliky:

  • Prehľadávame všetky podmnožiny vrcholov
  • Rekurzívne skúšame každý vrchol najprv pridať do podmnožiny, potom vynechať
  • Keď prejdeme cez všetky vrcholy, skontrolujeme, že aktuálna podmnožina je klika
  • Aktuálnu podmnožinu aj najväčšiu nájdenú kliku ukladáme do LinkedList-u.
/** Trieda, ktora umoznuje najst maximalnu kliku v danom grafe. */
class MaximumClique {

    /** samotny graf */
    private Graph g;
    /** zoznam vrcholov v najvacsej doteraz najdenej klike */
    private LinkedList<Integer> maxClique;
    /** zoznam vrcholov v aktualnej podmnozine */
    private LinkedList<Integer> vertexSet;

    /** Konstruktor, ktory dostane graf a spusti rekurzivne vyhladavanie */
    public MaximumClique(Graph g) {
        this.g = g;  // uloz vstupny graf
        // vytvor dve prazdne mnoziny vrcholov
        vertexSet = new LinkedList<Integer>();
        maxClique = new LinkedList<Integer>();
        search(0); // zavolaj rekurziu
    }

    /** Hlavna rekurzivna metoda volana z konstruktora.
     * Metoda skusi pouzit aj vynechat vrchol vertex
     * potom skusa vsetky moznosti pre vrcholy vertex+1...n-1. */
    private void search(int vertex) {
        // ak uz sme vycerpali vsetky vrcholy, nie je co skusat dalej
        if (vertex == g.getNumberOfVertices()) {
	    // skontroluj, ci mame kliku a ak ano, porovnaj s najlepsou doteraz
	    if(isClique(g, vertexSet) && vertexSet.size() > maxClique.size()) {
		// konstruktor LinkedListu moze vytvorit kopiu inej Collection
		maxClique = new LinkedList<Integer>(vertexSet);
	    }
            return;
        }
	// pridaj vrchol vertex do mnoziny a zavolaj rekurziu
	vertexSet.addLast(vertex);
	search(vertex + 1);
	// odober vertex z mnoziny a zavolaj rekurziu na ostatne vrcholy
	vertexSet.removeLast();
        search(vertex + 1);
    }

   /** pomocna metoda, ktora overi, ci je vertexSet klika. */
    private static boolean isClique(Graph g, 
            Collection<Integer> vertexSet) {
        // iterujeme cez vsetky dvojice v mnozine
	for(int u : vertexSet) {
	    for(int v : vertexSet) {		
		if (u!=v && !g.existsEdge(u, v)) { // over hranu
		    return false;  // hrana nie je
		}
            }
        }
        return true; // vsetky hrany najdene
    }

    /** vrati maximalnu kliku najdenu v grafe g */
    public List<Integer> maxClique() {
        // vrat nemenitelnu kopiu nasej najlepsej kliky
        return Collections.unmodifiableList(maxClique);
    }
}


Príklad použitia

        MaximumClique c = new MaximumClique(g);
        System.out.println("Maximalna klika: "
                + c.maxClique().toString());

Rýchlejšia verzia

  • Rekurzívne skúšame každý vrchol najprv pridať do kliky, potom vynechať
  • Vrchol pridávame do kliky iba ak je spojený so všetkými vrcholmi, ktoré už sú v klike
  • Vrchol v klike veľkosti k má stupeň (počet susedov) aspoň k-1
  • Preto do kliky skúšame dať iba vrcholy, ktoré majú dosť veľký stupeň na to, aby mohli patriť do kliky väčšej ako zatiaľ najväčšia nájdená (to neznamená, že do takej kliky aj patria)
/** Trieda, ktora umoznuje najst maximalnu kliku v danom grafe. */
class MaximumClique {

    /** samotny graf */
    private Graph g;
    /** zoznam vrcholov v najvacsej doteraz najdenej klike */
    private LinkedList<Integer> maxClique;
    /** zoznam vrcholov v aktualnej klike */
    private LinkedList<Integer> clique;

    /** Konstruktor, ktory dostane graf a spusti rekurzivne vyhladavanie */
    public MaximumClique(Graph g) {
        this.g = g;  // uloz vstupny graf
        // vytvor dve prazdne kliky
        clique = new LinkedList<Integer>();
        maxClique = new LinkedList<Integer>();
        search(0); // zavolaj rekurziu
    }

    /** Hlavna rekurzivna metoda volana z konstruktora.
     * Metoda skusi pouzit aj vynechat vrchol vertex
     * potom skusa vsetky moznosti pre vrcholy vertex+1...n-1. */
    private void search(int vertex) {
        // ak aktualna klika je vacsia ako doterajsie maximum, uloz ju
        if (clique.size() > maxClique.size()) {
            // konstruktor LinkedListu moze vytvorit kopiu inej Collection
            maxClique = new LinkedList<Integer>(clique);
        }
        // ak uz sme vycerpali vsetky vrcholy, nie je co skusat dalej
        if (vertex == g.getNumberOfVertices()) {
            return;
        }
        // otestuj, ci sa vrchol vertex da pridat do kliky
        // a ci ma sancu byt vo vacsej klike ako doteraz najdena
        if (isConnected(g, vertex, clique)
                && degree(g, vertex) + 1 > maxClique.size()) {
            // ak ano, pridaj ho do kliky a zavolaj rekurziu
            clique.addLast(vertex);
            search(vertex + 1);
            // odober vertex x kliky
            clique.removeLast();
        }
        // preskoc vertex a zavolaj rekurziu na ostatne vrcholy
        search(vertex + 1);
    }

   /** pomocna metoda, ktora overi, ci vrchol vertex je v grafe g
     * spojeny s kazdym z vrcholov v mnozine vertexSet. */
    private static boolean isConnected(Graph g, int vertex,
            Collection<Integer> vertexSet) {
        // iterujeme cez mnozinu vertexSet
	for(int v : vertexSet) {
            if (!g.existsEdge(vertex, v)) { // over hranu
                return false;  // hrana nie je
            }
        }
        return true; // vsetky hrany najdene
    }

    /** pomocna metoda, ktora zisti stupen vrchola vertex v grafe g */
    private static int degree(Graph g, int vertex) {
        // iterujeme cez susedov vrchola, zvysujeme pocitadlo result
        int result = 0;
	for(int x : g.adjVertices(vertex)) {
            result++;
        }
        return result;
    }

    /** vrati maximalnu kliku najdenu v grafe g */
    public List<Integer> maxClique() {
        // vrat nemenitelnu kopiu nasej najlepsej kliky
        return Collections.unmodifiableList(maxClique);
    }
}

Cvičenia:

  • Čo by program robil, ak by sme vynechali test na stupeň vrchola z rekurzívnej funkcie?
  • Čo by program robil, ak by sme vynechali aj test isConnected?
  • Čo program robí, ak ho spustíme na grafe bez hrán?
  • Ktorá reprezentácia grafu je vhodnejšia pre tento algoritmus?

Základy OOP v C++

Viac informácií nájdete napríklad v týchto dvoch tutoriáloch:

Ilustračný príklad: trieda Interval

/** Trieda reprezentujuca uzavrety interval s celociselnymi
 * suradnicami oboch koncov. */
class Interval {
public:
    /** Konstruktor so zadanymi suradnicami zaciatku a konca */
    Interval(int newStart, int newEnd);

    /** Vrati lavy koniec intervalu */
    int getStart() const;

    /** Vrati pravy koniec intervalu */
    int getEnd() const;

    /** Vrati dlzku intervalu */
    int length() const;

    /** Porovna intervaly najprv podla laveho konca,
     * pri rovnosti podla praveho. */
    bool operator <(const Interval &other) const;

private:
    int start;
    int end;
};

Interval::Interval(int newStart, int newEnd)
: start(newStart), end(newEnd) {
}

int Interval::getStart() const {
    return start;
}

int Interval::getEnd() const {
    return end;
}

int Interval::length() const {
    return end - start;
}

bool Interval::operator<(const Interval& other) const {
    return start < other.start || (start == other.start && end < other.end);
}

Niektoré rozdiely medzi triedami v Jave a C++:

  • V C++ oddeľujeme deklaráciu triedy (premenné a hlavičky metód) od implementácie metód
    • Implementáciu niektorých veľmi krátkych metód môžeme dať priamo do deklarácie
  • V dlhšom programe dáme deklaráciu napr. do súboru Interval.h a implementácie metód do súboru Interval.cpp
    • Ak chceme používať intervaly, dáme do hlavičky #include "Interval.h"
    • Na rozdiel od Javy pomenovanie súborov nemusí sedieť s menani tried
  • Deklarácia triedy rozdelená na časti public, private, protected, za deklaráciou bodkočiarka
  • Pri implementácii musíme pred názov dať meno triedy napr. Interval::length
  • Štruktúra struct je skoro to isté ako trieda, iba default prístup je public

Konštruktor

  • premenné objektu môžeme inicializovať pred začiatkom tela konštruktora
Interval::Interval(int newStart, int newEnd)
: start(newStart), end(newEnd) {
}
  • môžeme to však spraviť aj obyčajnými priradeniami
Interval::Interval(int newStart, int newEnd) {
  start = newStart;
  end = newEnd;
}
  • prvý spôsob vhodný ak premenná je objekt - do zátvorky dáme parametre konštruktora
class SomeClass {
  Interval myInterval;
  SomeClass(int start, int end);
  ...
}; 

SomeClass::SomeClass(int start, int end) 
  : myInterval(start, end) {
}
  • použitie konštruktora:
    • inicializácia lokálnej premennej i1: Interval i1(2, 4)
    • vytvorenie nového objektu pomocou new: Interval *pi = new Interval(2, 4);
    • vytvorenie anonymnej dočasnej premennej, ktorá sa inicializuje a nakopíruje do vektora: a.push_back(Interval(5, 8));

Preťaženie operátorov

  • Väčšinu operátorov, ktoré majú aspoň jeden operand objekt, môžeme preťažiť, teda vymyslieť im vlastný význam
  • V našom príklade preťažujeme < (využije sa pri triedení)
  • Viac Prednáška 24

Const

  • Niektoré metódy sú označené ako const, čo znamená, že nemenia objekt
  • Naopak parametre metód môžu byť const referencie
    • Nemusia sa kopírovať, ale máme zaručené, že nebudú zmenené
bool Interval::operator<(const Interval& other) const {
    return start < other.start || (start == other.start && end < other.end);
}

Aritmetický strom v C++

class Node {
public: 
    virtual int evaluate() const = 0; // abstraktna metoda
    virtual void print() const = 0;  // abstraktna metoda
    virtual ~Node() { }  // destruktor s prazdnym telom
};

class BinaryNode : public Node {
public :
    BinaryNode(Node *newLeft, Node *newRight);
    virtual ~BinaryNode();
protected:
    Node *left, *right;
};

BinaryNode::BinaryNode(Node *newLeft, Node *newRight)
 : left(newLeft), right(newRight) {
}

BinaryNode::~BinaryNode() {
    delete left;
    delete right;
}

class ConstantNode : public Node {
public :
    ConstantNode(int newValue);
    virtual int evaluate() const;
    virtual void print() const;
private:
    int value;
};

ConstantNode::ConstantNode(int newValue)
    : Node(), value(newValue) {
}

int ConstantNode::evaluate() const {
    return value;
}

void ConstantNode::print() const {
    cout << value;
}

class PlusNode : public BinaryNode {
public:
    PlusNode(Node *newLeft, Node *newRight);
    virtual int evaluate() const;
    virtual void print() const;
};

PlusNode::PlusNode(Node* newLeft, Node* newRight)
: BinaryNode(newLeft, newRight) {
}

int PlusNode::evaluate() const {
    return left->evaluate()+right->evaluate();
}

void PlusNode::print() const {
    cout << "(";
    left->print();
    cout << "+";
    right->print();
    cout << ")";
}

void treeTest() {
    Node * tree = new PlusNode(new PlusNode(new ConstantNode(2), new ConstantNode(1)),
            new ConstantNode(5));
    tree->print();
    cout << endl << tree->evaluate() << endl;
    delete tree;
}

Dedenie

  • BinaryNode je podtriedou Node:
class BinaryNode : public Node {
public :
    BinaryNode(Node *newLeft, Node *newRight);
    virtual ~BinaryNode();
protected:
    Node *left, *right;
};
  • V hornej časti konštruktora môžeme zavolať konštruktor nadtriedy:
PlusNode::PlusNode(Node* newLeft, Node* newRight)
: BinaryNode(newLeft, newRight) {
}
  • Pozor, ak chceme, aby sa metódy správali polymorfne, musia byť deklarované ako virtual
  • Abstraktné metódy sa píšu takto: virtual int evaluate() const = 0;

Deštruktor

  • Špeciálna metóda, opak konštruktora
    • spúšťa sa automaticky pri zániku objektu (keď na objekt spustíme delete alebo ak objekt v lokálnej premennej a funkcia končí)
    • zvyčajne sa používa na odalokovanie pamäte, prípadne ďalšie upratovanie
    • deštruktory sú často virtuálne
    • po skončení deštruktora sa zavolá deštruktor nadtriedy
BinaryNode::~BinaryNode() {
    delete left;  // rekurzivne zavolá deštruktor na ľavý podstrom
    delete right;
}

Uloženie v pamäti

V Jave:

  • každá premenná buď primitívny typ alebo referencia na objekt/pole
  • všetky objekty alokované cez new
  • odalokované automaticky
  • do premennej typu nejaká trieda môžeme priradiť aj referenciu na objekt z podtriedy

V C++:

  • premenná môže priamo obsahovať objekt, alebo referenciu na objekt alebo smerník
  • naopak smerník môže ukazovať aj na primitívny typ
  • objekty alokované cez new treba zmazať
  • do premennej typu nejaká trieda sa objekty kopírujú
    • môžeme predefinovať operátor priradenia a copy konštruktor, aby fungovali ako treba
    • nemôžeme priradiť objekt podtriedy, lebo by sa nemusel zmestiť
  • smerníky fungujú podobne ako referencie v Jave, použijeme ak chceme využiť polymorfizmus