Programovanie (2) v Jave
1-INF-166, LS 2016/17

Úvod · Pravidlá · Prednášky · Projekt · Netbeans · Odovzdávanie · 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).
· Predvádzanie projektov bude v pondelok 5.6. od 9:00 do 12:00 a v utorok 6.6 od 12:00 do 13:30 (po skúške), oboje v miestnosti M217. Na termín sa prihláste v AIS. Ak robíte vo dvojici, prihlási sa iba jeden člen dvojice.
· Body zo záverečného testu sú na testovači. Poradie príkladov: P1: do šírky, P2: topologické, P3: výnimky, P4: iterátor, P5: testy, P6: strom. Bolo potrebné získať aspoň 20 bodov zo 40.
· Opravný test bude 19.6.2017 od 9:00 v miestnosti M-I. Na termín sa prihláste v AISe.
· Zapisovanie známok a osobné stretnutia ku skúške budú v utorok 13.6. 13:30-14:30 v M163 a v stredu 14.6. 14:00-14:30 v M163.


Cvičenia 24

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

Úlohou tohto cvičenia je zoznámiť sa s knižnicou GraphGUI, ktorú budete používať na skúške a tiež si precvičiť prehľadávanie s návratom na grafoch.

Úloha A: Stiahnite si graphgui.zip a rozzipujte ho. Potom si ho otvorte v Netbeans pomocou New project, ako typ projektu zvoľte Java Project with Existing Sources, na ďalšej obrazovke vyplňte Project Name graphgui a na ďalšej pomocou Add Folder pridajte adresár s rozzipovanými súbormi. Je dobré si tento postup vyskúšať v učebni, aby ste na skúške nemali problémy. Projekt skúste skompilovať, spustiť a pozrite si, čo program robí.

Úloha B: Do súboru Editor.java doprogramujte, aby sa po stlačení tlačidla Run Editor otvorilo editovacie okienko, v ktorom je pre každý vrchol jeden ovládací prvok s číslom vrcholu a používateľ môže pre každý vrchol nastaviť, aby sa jeho farba zmenila na zelenú. Ovládacie prvky majú byť umiestnené pod sebou a na spodku bude ovládací prvok Button s nápisom OK, ktorý po stlačení označené vrcholy prefarbí. Ak bude okno zavreté bez stlačenia OK, zmeny sa nevykonajú. Pomôcky:

  • Na zmenu farby použite metódu setColorName("green") rozhrania Vertex.
  • Ako vhodný Layout aplikácie odporúčame GridPane
  • Odporúčané ovládacie prvky sú RadioButton (zaujímavé metódy setSelected, isSelected), pripadne ListView (vhodný SelectionModel je SelectionMode.MULTIPLE a jeho metódy getSelectedIndices() resp. getSelectedItems()).

Úloha C: Do súboru GraphAlgorithm.java doprogramujte, aby po stlačení tlačidla Action program spustil algoritmus hľadania najväčšej kliky a vrcholy v tejto klike aby boli vyfarbené žltou farbou (nastavte im meno farby "yellow") a ostatné vrcholy mimo kliky bielou farbou (nastavte im meno farby "white"). Algoritmus upravte z program na hľadanie maximálnej kliky (trieda MaximumClique). Metóda performAlgorithm vráti reťazec vo formáte "Pocet vrcholov kliky: 6".

Úloha D: Modifikujte program na hľadanie maximálnej kliky (trieda MaximumClique) z prednášky tak, aby vypísal všetky maximálne kliky. Môžete začať buď z jednoduchšej alebo z rýchlejšej verzie programu. Namiesto jedného ArrayListu maxClique si spravte ArrayList ArrayListov, do ktorého budete ukladať všetky doteraz nájdené riešenia maximálnej veľkosti. Ak nájdete väčšiu kliku, ArrayList vyprázdnite a uložte tam iba najnovšie nájdenú. Pozor, ak používate rýchlejšiu verziu programu, treba tiež upraviť alebo zmazať podmienku so stupňom vrchola.

Úloha E: Napíšte program, ktorý pomocou prehľadávania s návratom nájde najmenšiu dominujúcu množinu v grafe.

  • Dominujúca množina je taká množina vrcholov X, že každý vrchol grafu je buď v X, alebo susedí s nejakým vrcholom v X.
  • Napríklad hrany sú rovné chodby a vrcholy križovatky. Strážnik stojaci vo vrchole má pod kontrolou túto križovatku aj všetky s ňou susedné. Chceme s použitím čo najmešieho počtu strážnikov mať pod kontrolou všetky vrcholy grafu.

Algoritmus:

  • V každom rekurzívnom volaní vyskúšajte pre jeden vrchol dve možnosti: patrí do dominujúcej množiny alebo nepatrí. Potom rekurzívne zavolajte prehľadávanie pre všetky možnosti ďalších vrcholov.
  • Ak ste už spravili rozhodnutie pre každý vrchol, skontrolujte, či je výsledok naozaj dominujúca množina a porovnajte veľkosť s najlepšou zatiaľ nájdenou.

Viete kvôli zrýchleniu orezať nejaké neperspektívne vetvy výpočtu? Skúste napríklad niektorú z týchto stratégií:

  • ak ste už našli dominujúcu množinu určitej veľkosti, nemá zmysel skúmať a rozširovať množiny, ktoré majú zaručene viac prvkov
  • alebo nechceme pridať do X vrchol, ktorý nijako nepomôže, lebo aj on aj všetci jeho susedia už majú suseda v X
  • alebo nechceme vynechať vrchol, ak niektorý z jeho susedov nemá ešte suseda v X a ani nemá suseda s väčším číslom, ktorý ešte môže byť pridaný do X v ďalších rozhodnutiach