5. sada domácich zadaní - pre fajnšmekrov

Najneskorší termín odovzdania: 3.4.2016 (nedeľa) o 21:00
Odovzdávané súbory: AnalyzatorSkenu.java, Osoba.java

Doplňujúce požiadavky:

  • riešenia, ktoré nebude možné skompilovať (t.j. riešenia so syntaktickými chybami) nebudú hodnotené,
  • zdrojový kód správne naformátujte (CTRL+SHIFT+F),
  • komentovaný zdrojový kód

Bunka sem, bunka tam (8 bodov)

Daniela je študentkou medziodborového štúdia biológia-informatika na UPJŠ. A ako to už býva pri štúdiu biológie, práci v labákoch sa žiaden študent nevyhne. Daniela nie je žiadnou výnimkou. Pri jednej takej práci v laboratóriu im ich vyučujúci ukázal experiment, na ktorom práve robia. V rámci experimentu študujú pohyb a delenie akýchsi buniek (Daniela je ešte len prváčka, takže to, o aké bunky ide, veľmi "nerieši"). Samozrejme na UPJŠ nie je núdza ani o modernú laboratórnu techniku. A tak biológovia na tie bunky nepozerajú bežným mikroskopom ale rovno digitálnym mikroskopom. Taký digitálny mikroskop si môžete predstaviť ako digitálny fotoapárat s veľmi kvalitným "zoomom" - umožňuje vyfotografovať či nakamerovať mikroskopické zábery. Aby bolo bunky lepšie vidieť, biológia si dopomáhajú rôznymi fluorescenčnými látkami alebo ožarovaním (preto sú bunky tak "do zelena"). Ale k veci. Vyučujúci poprosil Danielu a jej spolužiakov o pomoc pri vyhodnocovaní experimentu. Biológovia majú kopu záberov z mikroskopu, no pre samotné vyhodnotenie by potrebovali vedieť, koľko buniek je jednotlivých záberoch (keďže čas vzniku záberov poznajú, môžu tak určiť rýchlosť delenia buniek a jej závislosť od okolitých podmienok). Daniela aj spolužiaci súhlasili (veď kto by sa nechcel podieľať na takomto experimente) - a začali bunky na záberoch rátať. S každým ďalším záberom a každou ďalšou bunkou ich nadšenie (exponenciálne?) klesalo... :-(

Ako také zábery vyzerajú, si môžete pozrieť na tomto obrázku:

Ďalšie mikroskopické zábery buniek nájdete v súbore: SkenyBuniek.zip (aj s počtom buniek, ktoré študenti na zábere napočítali)

A vtedy si Daniela uvedomila: veď ja viem predsa programovať! PAZ1a má za sebou, PAZ1b je ešte otvorené, no už všelijaké algoritmy a údajové štruktúry pozná. A nebolo by skvelé, ak by kolegom biológom ukázala, že informatike sa dnes už nevyhne asi žiaden vedecký odbor? Čo tak naprogramovať program, ktorý by zrátal počet buniek na zábere z digitálneho mikroskopu?

Obrázkov na spracovanie je veľa, niektoré sú oveľa väčšie ako tie na obrázku. Daniela je však znalá problematiky efektívnosti algoritmov. Rozhodla sa preto napísať program čo najefektívnejšie - v ideálnom prípade tak, aby pracoval v lineárnom čase (lepšie sa nedá, lebo na každý pixel obrázka sa musíme pozrieť aspoň raz).

Zadanie

Upravením triedy AnalyzatorSkenu vytvorte triedu na analýzu záberov buniek z digitálneho mikroskopu. Kód analyzujúci vstupný obrázok umiestnite do metódy analyzuj. Metódu pocetBuniek upravte tak, aby vrátila počet buniek na obrázku. Pri analýze použitie tieto skutočnosti:

  • metóda jePixelBunky vám povie, či pixel na zadaných súradniciach je pixelom bunky - využíva sa to, že obrázok je predspracovaný a pozadie má čiernu farbu,
  • rozmery načítaného obrázka sú v inštančných premenných sirka a vyska; platný rozsah indexov pre pixely v x-ovej súradnici je teda 0, ..., (sirka-1) a y-ovej súradnici je 0, ..., (vyska-1),
  • žiadne dve bunky sa nedotýkajú (ak niečo vyzerá ako 2 zlepené bunky, tak to je v skutočnosti jedna bunka, ktorá je práve v procese delenia)
  • pozor, bunka sa môže dotýkať aj niektorej zo strán obrázku a nemusí ju byť teda vidiet celú.

Trieda AnalyzatorSkenu:

import java.awt.*;
import java.awt.image.*;
import java.io.*;
import javax.imageio.*;

public class AnalyzatorSkenu {

        /**
         * Naskenovany obrazok
         */
        private BufferedImage obrazok;

        /**
         * Sirka nacitaneho obrazka
         */
        private int sirka;

        /**
         * Vyska nacitaneho obrazka
         */
        private int vyska;

        /**
         * Hustota buniek - podiel plochy pokrytej bunkami k ploche skenu
         */
        private double hustotaBuniek;

        /**
         * Vytvori novy analyzator skenu buniek a spusti zakladnu analyzu
         *
         * @param nazovSuboru
         *            nazov suboru so skenom buniek
         */
        public AnalyzatorSkenu(String nazovSuboru) {
                try {
                        obrazok = ImageIO.read(new File(nazovSuboru));
                        sirka = obrazok.getWidth();
                        vyska = obrazok.getHeight();
                } catch (IOException e) {
                        System.err.println("Subor " + nazovSuboru
                                        + " sa nepodarilo nacitat.");
                }

                analyzuj();
        }

        /**
         * Vrati, ci je pixel na suradniciach [x, y] pixelom bunky.
         */
        private boolean jePixelBunky(int x, int y) {
                Color pixel = new Color(obrazok.getRGB(x, y));
                return !pixel.equals(Color.black);
        }

        /**
         * Vypocita hustotu buniek
         */
        private void vypocitajHustotuBuniek() {
                int pocetBunkovychPixelov = 0;
                for (int y = 0; y < vyska; y++)
                        for (int x = 0; x < sirka; x++)
                                if (jePixelBunky(x, y))
                                        pocetBunkovychPixelov++;

                hustotaBuniek = pocetBunkovychPixelov / ((double) sirka * vyska);
        }

        /**
         * Realizuje zakladnu analyzu obrazka so skenom buniek
         */
        private void analyzuj() {
                vypocitajHustotuBuniek();
                // ???
                // ... dalsia analyza obrazku spustena po nacitani skenu
        }

        /**
         * Vrati pocet buniek na obrazku
         */
        public int getPocetBuniek() {
                // ???
                return 0;
        }

        /**
         * Vrati hustotu buniek (pomer bunkovych pixelov k vsetkym pixelom)
         */
        public double getHustotaBuniek() {
                return hustotaBuniek;
        }

        public static void main(String[] args) {
                AnalyzatorSkenu analyzator = new AnalyzatorSkenu("cellscan328371.png");
                System.out.println("Hustota buniek: "
                                + (analyzator.getHustotaBuniek() * 100) + " %");

                System.out.println("Pocet buniek: " + analyzator.getPocetBuniek());
        }
}
[$[Get Code]]

V triede AnalyzatorSkenu nájdete aj metódu vypocitajHustotuBuniek, ktorá demonštruje princíp práce s obrázkom ako aj použitie metódy jePixelBunky. Táto metóda do inštančnej premennej hustotaBuniek vypočíta pomer počtu pixelov, ktoré zachycujú nejakú bunku, k celkovému počtu pixelov obrázka. Inými slovami hustotaBuniek určuje, aké percento plochy obrázka je pokryté bunkami.

Matemágia (max. 4 body)

Viete kto je David Copperfield? Áno, je to ten slávny iluzionista. Ale počuli ste už o Arthurovi Benjaminovi? Arthur Benjamin (okrem toho, že je profesorom matematiky) je aj matemagik. Jeho vystúpenie na TEDe si môžete pozrieť na stránke: http://www.ted.com/talks/arthur_benjamin_does_mathemagic.html (len tak mimochodom, na TEDe nájdete kopu zaujímavých a inšpirujúcich prednášok a vystúpení). Pre nás bude najzaujímavejšia jeho demoštrácia, ktorá začína od 6 minúty. Arthur vyberie 4-ciferné číslo Y, ktoré je druhou mocninou nejakého dvojciferného čísla X, t.j. Y = X*X (Y je výsledok z úvodu jeho vystúpenia). Potom požiada náhodného diváka (teda až štyroch nezávisle), aby číslo Y vynásobil akýmkoľvek 3-ciferným číslom (toto číslo nikomu neprezradí) - označme ho M. Divákovi sa na kalkulačke zobrazí 6- alebo 7-ciferné číslo M*Y. Arthur diváka požiada, aby mu prezradil ľubovoľných 5 resp. 6 cifier z čísla M*Y v akomkoľvek poradí. Následne sa Arthur pokúsi uhádnuť chýbajúcu (divákom nepovedanú) šiestu, resp. siedmu cifru čísla M*Y. Ako inak, Arthur chýbajúcu cifru uhádne. Ide však o šťastie ale bo je za tým skrytá nejaká sofistikovaná matematika? Pre nás ako matematikov a informatikov, je to zaujímavá výzva, aby sme tento problém analyzovali.

Nech X je dvojciferné číslo také, že X*X je 4-ciferné číslo. Je pravdou, že pre každé 3-ciferné číslo M platí, že ľubovoľných (v akomkoľvek poradí) 5, resp. 6 cifier čísla X*X*M jednoznačne určuje zostávajúcu (šiestu resp. siedmu) cifru tohto čísla? Dokážte alebo nájdite kontrapríklad.

Ako odovzdávať riešenie:

  • Ak je tvrdenie pravdivé, dôkaz v písomnej forme odovzdajte svojmu cvičiacemu. Ak pri dôkaze využijete aj nejaký program, jeho zdrojový kód nech je súčasťou dôkazu.
  • Ak je tvrdenie nie je pravdivé, nájdite kontrapríklad (alebo kontrapríklady) ako trojicu (X, M1, M2) takú, že v číslach X*X*M1 a X*X*M2, ktoré majú rovnaký počet cifier, možno vybrať takých 5 resp. 6 cifier, podľa ktorých tieto čísla nemožno rozlíšiť, resp. nemožno jednoznačne doplniť šiestu, resp. siedmu cifru. Príklad: Ak si zoberiete číslá 3451 a 5324, tak tieto čísla nemožno rozlíšiť pomocou ľubovoľných 3 cifier. Totiž, ak nám niekto povie, že číslo obsahuje cifry 345, nevieme, či to je číslo 4351 alebo 5324 - a teda nevieme, či máme doplniť číslo 1 alebo 2. Za každý nájdený kontrapríklad je 0.1 boda. Ak pri hľadaní kontrapríkladov využijete nejaký program, jeho zdrojový kód musí byť súčasťou riešenia. Ak pri hľadaní kontrapríkladov sa budete opierať o nejaké matematické tvrdenia a kombinatoriku, popis postupu hľadania kontrapríkladov musí byť súčasťou riešenia (odovzdáva sa v písomnej forme).

Ako odovzdávať riešenie cez Moodle:

  • Moodle dovoľuje k tejto úlohe odovzdať 2 súbory. Prvý je akýkoľvek súbor, ktorý obsahuje popis vášho riešenia (podporný zdrojový kód, dôkazy, ...). Druhý je textový súbor kontrapriklady.txt. Evaluátor obsahuje test, či zadané trojice čísel predstavujú kontrapríklady (otestovať, či niečo spĺňa zadané vlastnosti je možné aj bez toho, aby ste vedeli, či vôbec existuje objekt s týmito vlastnosťami). Formát súboru kontrapriklady.txt: v každom riadku sa očakáva jeden kontrapríklad zadaný ako trojica medzerami oddelených čísel X, M1 a M2.

XPath pre stromy potomkov (6b)

Jedna z možných reprezentácii XML dokumentov je DOM (Document Object Model), v ktorom je obsah XML dokumentu reprezentovaný stromom:

Tak, ako v relačných databázach existuje (viac-menej) štandardizovaný dopytovací jazyk zvaný SQL, pri XML úlohu akéhosi dopytovacieho jazyka plní jazyk XPath:

Úlohou je implementovať akúsi zjednodušenú analógiu XPath-u pre stromy potomkov (4. prednáška, trieda Osoba): jazyk XCesta. Ak XCesta výraz vyhodnotíme vzhľadom na nejakú osobu v strome potomkov, výsledkom je nejaký zoznam osôb, ktoré sú v strome potomkov tejto osoby. XCesta výrazy budeme vyhodnocovať cez metódu xCesta objektov triedy Osoba:

import java.util.*;

public class Osoba {
        private String meno;
        private List<Osoba> deti = new ArrayList<Osoba>();

        public Osoba(String meno) {
                this.meno = meno;
        }

        public void pridajDieta(Osoba dieta) {
                deti.add(dieta);
        }

        public List<Osoba> xCesta(String vyraz) {
                // Riesenie
        }
}
[$[Get Code]]

Originálna skrátená syntax XPathu: http://www.w3schools.com/xsl/xpath_syntax.asp

Analogicky sa XCesta výrazy sa skladajú z lomítkom oddelených krokov. Kroky môžu byť nasledovných tvarov:

  • . (bodka) - vyberie aktuálnu osobu
  • Meno - vyberie všetky deti aktuálnej osoby zadaným menom
  • Prefix* - vyberie všetky deti aktuálnej osoby, ktorých meno začína zadaným prefixom (napr. Ja* vyberie všetky deti, ktorých meno začína písmenami Ja - napr. Janko, Janka, Jakub, atď.)
  • Prefix*[i] - vyberie i-te dieťa aktuálnej osoby spomedzi detí, ktorých meno začína zadaným prefixom (napr. Ja*[2] vyberie druhé dieťa začínajúce s prefixom Ja).
  • // - vyberie všetky osoby, ktoré sú v strome potomkov aktuálnej osoby vrátane tejto osoby. Pozor // sa vo výraze neoddeľuje lomítkami (aby ich tam nebolo priveľa).

Poznámka: Výraz "osoby v strom potomkov zadanej osoby" zahŕňa aj osobu v koreni (=zadanú osobu), nielen jej potomkov.

Osoby vrátené v zozname sú usporiadané v poradí, v akom by sa objavili pri preorder prechode stromom. Žiadna osoba sa vo vrátenom zozname nenachádza viac ako raz.

Príklady:

  • //Janko - vyberie všetky osoby s menom Janko, ktoré sú v strome potomkov zadanej osoby (vrátane zadanej osoby)
  • //Janko/Karol - vyberie všetky osoby s menom Karol, ktoré sú v strome potomkov zadanej osoby (vrátane tejto osoby) a zároveň ich rodič sa volá Janko. Tieto osoby s menom Janko musia byť taktiež v strome potomkov zadanej osoby.
  • Janko/K*[1]/Igor - vyberie všetky osoby s menom Igor, ktorých rodičom je osoba, ktorá je prvým dieťaťom s menom začínajúcim písmenom K, pričom táto osoba má rodičia s menom Janko. Táto osoba s menom Janko má rodiča, ktorý je tou osobou, nad ktorou sme XCesta výraz vyhodnocovali.
  • Janko/. - vyberie všetky deti tých detí aktuálnej osoby, ktoré sa volajú Janko.
  • Janko//. - vyberie všetky osoby v strome potomkov detí zadanej osoby s menom Janko (strom potomkov zahŕňa aj osobu v koreni tohto stromu).
  • //. vyberie všetky osoby v strome potomkov zadanej osoby (vrátane zadanej osoby).
  • . vyberie zadanú osobu

Upozornenie: Táto úloha nie je automaticky kontrolovaná evaluátorom.