Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. Sada úloh pro PilsProg a softwarová aplikace pro

Za´padoˇceska´ univerzita v Plzni Fakulta aplikovanyćh vˇed Katedra informatiky a vy´poˇcetn´ı techniky

Bakal´ aˇ rsk´ a pr´ ace Sada u ´ loh pro PilsProg a softwarov´ a aplikace pro shromaˇ zd’ov´ an´ı vyˇ reˇ sen´ ych u ´ loh

Plzeˇ n, 2014

Martin Bláha

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem bakaláˇrskou práci vypracoval samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. V Plzni dne 7. kvˇetna 2014 Martin Bláha

Podˇ ekov´ an´ı Mé podˇekován´ı patˇr´ı Ing. Arnoˇstce Netrvalové, Ph.D. za odborné veden´ı, trpˇelivost a ochotu, kterou mi v pr˚ ubˇehu zpracován´ı bakaláˇrské práce vˇenovala.

Abstract The objectives and outcomes of this work are a set of problems for PilsProg programming contest and a software application for collecting of solved problems. The first part deals with the study of the PilsProg programming contest website and subsequently with the creation of the problem set using the available ACM validators. The purpose of the problem set is to provide a basis for a problem definition for the PilsProg programming contest. The second part of this work describes the application for storing and sharing of solved problems. In the future, the application should also provide an additional teaching material for students involved in programming.

Obsah ´ 1 Uvod

1

2 Vytvoˇ ren´ı sady u ´ loh pro PilsProg 2.1 Programovac´ı soutˇeˇz PilsProg . . . . . . . . . . 2.1.1 Základn´ı u ´daje . . . . . . . . . . . . . . 2.1.2 Registrace . . . . . . . . . . . . . . . . . 2.1.3 Pravidla soutˇeˇze . . . . . . . . . . . . . 2.1.4 Podporované programovac´ı jazyky . . . . 2.1.5 Softwarové vybaven´ı . . . . . . . . . . . 2.1.6 Odevzdán´ı u ´loh a odpovˇedi validátoru . 2.2 Validátor UVa Online Judge . . . . . . . . . . . 2.2.1 Základn´ı u ´daje . . . . . . . . . . . . . . 2.2.2 Registrace . . . . . . . . . . . . . . . . . ´ 2.2.3 Ulohy . . . . . . . . . . . . . . . . . . . 2.2.4 Zp˚ usob odevzdán´ı a odpovˇedi validátoru 2.3 Vybrané u ´lohy ze sady u ´loh . . . . . . . . . . . 2.3.1 Seˇrad’te jazyky . . . . . . . . . . . . . . 2.3.2 Dekódován´ı pásky . . . . . . . . . . . . . 2.3.3 Pˇreteˇcen´ı . . . . . . . . . . . . . . . . . 2.3.4 Zámek . . . . . . . . . . . . . . . . . . . 2.3.5 Nejdelˇs´ı spoleˇcná posloupnost . . . . . . 2.4 Problémy pˇri ˇreˇsen´ı u ´loh . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

2 2 2 2 3 4 5 5 5 5 6 6 6 9 10 13 15 17 20 22

3 Softwarov´ e aplikace 3.1 C´ıle aplikace . . . . . . . . 3.2 Pouˇzité technologie . . . . 3.2.1 Platforma Java . . 3.2.2 Programovac´ı jazyk 3.2.3 Apache Ant . . . . 3.2.4 Databáze MySQL . 3.3 Pouˇzité architektury . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

23 23 23 24 24 25 25 26

. . . . . . . . . Java . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

3.4

3.3.1 S´ıt’ová architektura klient-server . 3.3.2 V´ıcevrstvá architektura . . . . . . Programátorská dokumentace . . . . . . 3.4.1 Databáze . . . . . . . . . . . . . 3.4.2 Server . . . . . . . . . . . . . . . 3.4.3 Klient . . . . . . . . . . . . . . .

4 Z´ avˇ er

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

26 27 28 28 29 33 38

´ 1 Uvod V prvn´ı kapitole mé bakaláˇrské práce bych vás chtˇel seznámit s programovac´ı soutˇeˇz´ı PislProg. Pro kterou budu vytváˇret sadu u ´loh z jednoho z neobl´ıbenˇejˇs´ıho veˇrejného validaˇcn´ıho serveru pro trénován´ı programátorsk´ ych u ´loh UVa Online Judge, se kter´ ym vás také bl´ıˇze seznám´ım. Dále vám ukáˇzu vybrané u ´lohy z této vytvoˇrené sady, která bude slouˇzit jako podklad pro zadáván´ı u ´loh pro programátorskou soutˇeˇz PilsProg. V druhé kapitole mé bakaláˇrské práce vám ukáˇzu softwarovou aplikaci, která bude slouˇzit pro uchováván´ı a sd´ılen´ı vyˇreˇsen´ ych u ´loh s popisem, s jak´ ym algoritmem daná u ´loha byla vyˇreˇsena. Dále si pop´ıˇseme platformu Java s programovac´ım jazykem Java, která bude pouˇzita pro naprogramován´ı aplikace. Dále se seznám´ıme s relaˇcn´ı databáz´ı MySQL, která bude zvolena pro uchováván´ı dat a Apache Ant, kter´ y bude pouˇzit pro pˇreklad aplikace a také si ukáˇzeme architektury, které budou pouˇzity v aplikaci.

1

2 Vytvoˇren´ı sady u´loh pro PilsProg C´ılem této ˇca´sti bylo vybrat si jeden z veˇrejn´ ych validaˇcn´ıch server˚ u a z nˇeho vytvoˇrit sadu u ´loh, která by mˇela slouˇzit jako podklad pro vytvoˇren´ı zadán´ı pro programátorskou soutˇeˇz PilsProg. Pro vytvoˇren´ı sady budeme pouˇz´ıvat validaˇcn´ı server UVa Online Judge. Tento validaˇcn´ı server jsem si vybral proto, ˇze sn´ım pracuji jiˇz od prvn´ıho roˇcn´ıku na vysoké ˇskole a mám s n´ım nejv´ıce dobr´ ych zkuˇsenost´ı. Kaˇzdá u ´loha obsahuje zadán´ı pˇreloˇzené do ˇceˇstiny a zdrojov´ y kód, kter´ y danou u ´lohu ˇreˇs´ı. Ke kaˇzdé u ´loze je také pˇridán vstupn´ı a v´ ystupn´ı soubor, kter´ y slouˇz´ı pro reprezentaci testovan´ ych pˇr´ıpad˚ u.

2.1 2.1.1

Programovac´ı soutˇ eˇ z PilsProg Z´ akladn´ı u ´ daje

PilsProg [1] je programovac´ı soutˇeˇz pro studenty stˇredn´ıch ˇskol, jej´ımˇz garantem je Katedra informatiky a v´ ypoˇcetn´ı techniky Fakulty aplikovan´ ych vˇed Západoˇceské univerzity v Plzni. Tato soutˇeˇz slouˇz´ı pro porovnán´ı programátorsk´ ych schopnost´ı student˚ u r˚ uzn´ ych stˇredn´ıch ˇskol. Soutˇeˇz m˚ uˇze také pomoci u ´spˇeˇsn´ ym soutˇeˇz´ıc´ım k pˇrijet´ı na Fakultu aplikovan´ ych vˇed.

2.1.2

Registrace

Pro u ´ˇcast v soutˇeˇzi je nutná bezplatná registrace na webov´ ych stránkách PilsProgu [1] v dobˇe, která je urˇcená v harmonogramu soutˇeˇze, kter´ y se nacház´ı na stránkách. Soutˇeˇze se m˚ uˇzou z´ uˇcastnit jednotlivci, ale podm´ınkou pro registraci je, aby byl studentem stˇredn´ı ˇskoly v roce, ve kterém se soutˇeˇz poˇra´dá. Po registraci pˇrijde soutˇeˇz´ıc´ımu na e-mail registraˇcn´ı e-mail, kter´ y uvedl pˇri registraci. Soutˇeˇz´ıc´ı je následnˇe schopen se pˇrihlásit. Po pˇrihláˇsen´ı si soutˇeˇz´ıc´ı m˚ uˇze prohlédnout ilustraˇcn´ı u ´lohy a vyzkouˇset si jejich odevzdán´ı.

2

Vytvoˇren´ı sady u ´loh pro PilsProg

2.1.3

Programovac´ı soutˇeˇz PilsProg

Pravidla soutˇ eˇ ze

Kaˇzd´ y soutˇeˇz´ıc´ı pracuje samostatnˇe a má za u ´kol v urˇcité dobˇe vyˇreˇsit a naprogramovat správné ˇreˇsen´ı pro zadané problémy. Soutˇeˇz prob´ıhá ve dvou kolech - kvalifikaˇcn´ı a finálové. Kvalifikaˇcn´ıho kola se z´ uˇcastn´ı vˇsichni registrovan´ı soutˇeˇz´ıc´ı. Do finálového kola uˇz pak postupuj´ı pouze nejlepˇs´ı soutˇeˇz´ıc´ı. Kvalifikaˇcn´ı soutˇeˇz prob´ıhá z domova pomoc´ı webov´ ych stránek [1]. Pˇri spuˇstˇen´ı kvalifikaˇcn´ıho kola jsou na webov´ ych stránkách vyvˇeˇseny programovac´ı u ´lohy, které soutˇeˇz´ıc´ı ˇreˇs´ı. K poˇctu správnˇe odevzdan´ ych u ´loh se také udává doba od zaˇca´tku kvalifikaˇcn´ıho kola do doby, kdy soutˇeˇz´ıc´ı odevzdal ˇ správnˇe vyˇreˇsenou u ´lohu. Casy, za které soutˇeˇz´ıc´ı jednotlivé u ´lohy odevzdal, se sˇc´ıtaj´ı. Tento ˇcas poté slouˇz´ı pro vyhodnocen´ı poˇrad´ı, pakliˇze soutˇeˇz´ıc´ı maj´ı stejn´ y poˇcet správnˇe odevzdan´ ych u ´loh (viz Obrázek 2.1). Soutˇeˇz´ıc´ı proto mus´ı zvolit strategii takovou, ˇze zaˇcne vypracovávat u ´lohy od té, která mu zabere nejménˇe ˇcasu.

Obrázek 2.1: V´ ysledek kvalifikace Finálové kolo prob´ıhá v prostorách Katedry informatiky a v´ ypoˇcetn´ı techniky a je ˇcasovˇe omezen podle poˇctu ˇreˇsen´ ych u ´loh. Kaˇzd´ y soutˇeˇz´ıc´ı má pˇriˇrazen´ y poˇc´ıtaˇc, na kterém ˇreˇs´ı zadané u ´lohy. V pr˚ ubˇehu finálového kola soutˇeˇz´ıc´ı m˚ uˇze pouˇz´ıvat pouze knihy, které si sám donesl. Veˇskeré elektro3


Programovac´ı soutˇeˇz PilsProg

technické pom˚ ucky jsou zcela zakázány. Hodnocen´ı finálového kola se provád´ı stejnˇe jako v kvalifikaˇcn´ım kole s t´ım rozd´ılem, ˇze za kaˇzdou ˇspatnˇe odevzdanou u ´lohou se pˇriˇc´ıtá deset minut do celkového ˇcasu, která byla potˇreba pro vyˇreˇsené této u ´lohy.

2.1.4

Podporovan´ e programovac´ı jazyky

V PilsProgu soutˇeˇz´ıc´ı mohou pouˇz´ıvat ˇctyˇri programovac´ı jazyky. Podporované jazyky jsou C, C++, Java a Pascal. Kaˇzd´ y soutˇeˇz´ıc´ı m˚ uˇze vyuˇz´ıvat prostˇredk˚ u, které mu jazyk dovoluje mimo n´ıˇze uveden´ ych moˇznost´ı: • program nesm´ı otev´ırat soubory mimo standardn´ıho vstupu a v´ ystupu, • program nesm´ı vyuˇz´ıvat s´ıt’ovˇe prostˇredky, • program mus´ı vyuˇz´ıvat pouze jeden proces.

Jazyk C Je pouˇzit nejnovˇejˇs´ı standart C11 a u ´lohy jsou pˇrekládány pˇr´ıkazem gcc -std=c11 -lm -O2 vstup.c.

Jazyk C++ ´ Nejnovˇejˇs´ı standart je pouˇzit i u jazyka C++, kter´ ym je C++11. Ulohy se pˇrekládaj´ı pomoc´ı pˇr´ıkazu g++ -std=c++11 -lm -O2 vstup.cpp.

Jazyk Java U jazyka Java je pouˇzita verze 1.7.0. Z d˚ uvodu bezpeˇcnosti nesm´ı soutˇeˇz´ıc´ı vytváˇret vlastn´ı bal´ıˇcky.

Jazyk Pascal U jazyka Pascal je pouˇzita verze 2.6.0. 4


2.1.5

Validátor UVa Online Judge

Softwarov´ e vybaven´ı

Pˇri programován´ı v kvalifikaˇcn´ım kole je moˇzné pouˇz´ıt libovoln´ y editor, kter´ y soutˇeˇz´ıc´ımu vyhovuje. Ve finálovém kole budou na poˇc´ıtaˇci k dispozici n´ıˇze uvedené v´ yvojové prostˇred´ı, které uˇzivatel m˚ uˇze vyuˇz´ıt: • DevC++ (verze 5.4.2), • Eclipse (Kepler - verze 4.3.1), • FreePascal IDE (verze 1.0.12, verze pˇrekladaˇce 2.6.0).

2.1.6

Odevzd´ an´ı u ´ loh a odpovˇ edi valid´ atoru

Odevzdáván´ı vyˇreˇsen´ ych u ´loh se provád´ı pomoc´ı webov´ ych stránek [1]. Kaˇzd´ y soubor, kter´ y soutˇeˇz´ıc´ı odevzdává, mus´ı m´ıt pˇr´ıponu podle jazyka, kter´ y soutˇeˇz´ıc´ı pouˇzil. C mus´ı m´ıt pˇr´ıponu .c, C++ .cpp, Java .java a Pascal .pas. Pˇri odevzdán´ı programu soutˇeˇz´ıc´ı m˚ uˇze dostat jednu z n´ıˇze uveden´ ych odpovˇed´ı: • Chyba pˇ ri kompilaci - nelze pˇreloˇzit zdrojov´ y soubor, • Spr´ avn´ eˇ reˇ sen´ı - program byl uznán jako správné ˇreˇsen´ı zadané u ´lohy, • Chybn´ eˇ reˇ sen´ı - program vrátil ˇspatné v´ ysledky pro zadanou u ´lohu, • Pˇ rekroˇ cen´ı ˇ casov´ eho limitu - program neskonˇcil v ˇcasovém limitu, které poskytuj´ı informaci o tom, jestli dan´ y program splˇ nuje danou u ´lohu nebo ne.

2.2 2.2.1

Valid´ ator UVa Online Judge Z´ akladn´ı u ´ daje

UVa Online Judge [2] je veˇrejn´ y validátor pro nácvik u ´loh, které se vyuˇz´ıvaj´ı v ACM soutˇeˇz´ıch. Tento validátor patˇr´ı pod ˇspanˇelskou univerzitu Universidad 5



de Valladolid a je pˇr´ıstupn´ y pro vˇsechny uˇzivatele po bezplatné registraci. Validátor má pˇres 100 000 registrovan´ ych uˇzivatel˚ u, kteˇr´ı m˚ uˇzou vypracovávat pˇres 4 300 problém˚ u z r˚ uzn´ ych oblast´ı. Celé stránky jsou kompletnˇe napsané v anglickém jazyce vˇcetnˇe zadán´ı u ´loh. Mezi podporované programovac´ı jazyky patˇr´ı C/C++, Java a Pascal.

2.2.2

Registrace

Registrace je bezplatná a prob´ıhá na webov´ ych stránkách [2]. Pˇri registraci je nutné zadat jméno, e-mail, uˇzivatelské jméno a heslo. Také máme moˇznost pˇri registraci zaˇskrtnout, jestli chceme, aby se v´ ysledky u ´loh zas´ılaly na e-mail. Po zaregistrován´ı je ihned moˇzné se pˇrihlásit a zaˇc´ıt ˇreˇsit u ´lohy.

2.2.3

´ Ulohy

Vˇsechny u ´lohy, které m˚ uˇzeme ˇreˇsit, lze prohl´ıˇzet pomoc´ı webov´ ych stránek a jsou seˇrazeny do nˇekolika r˚ uzn´ ych sekc´ı, které mimo jiné obsahuj´ı také vˇsechny u ´lohy z ACM-ICPC svˇetového finále od roku 1990 do roku 2013. Kaˇzdou u ´lohu je také moˇzné stáhnou ve formátu PDF. U kaˇzdé u ´lohy je zadáno, v jaké ˇcasové dobˇe mus´ı program skonˇcit a kolik dan´ y algoritmus m˚ uˇze vyuˇz´ıt pamˇeti, pro vyˇreˇsen´ı dané u ´lohy.

2.2.4

Zp˚ usob odevzd´ an´ı a odpovˇ edi valid´ atoru

´ Ulohy se odevzdávaj´ı pomoc´ı webové stránky [2], kde je uˇzivatel pˇrihláˇsen pomoc´ı svého uˇzivatelského u ´ˇctu. Pˇri odevzdáván´ı je nutné vyplnit ˇc´ıslo ˇreˇsené u ´lohy, zaˇskrtnout jazyk, v kterém je u ´loha naprogramována a poté je moˇzné dvˇema zp˚ usoby vloˇzit zdrojov´ y kód ˇreˇsen´ı. Prvn´ı zp˚ usob je vybrán´ı souboru se zdrojov´ ym kódem. Druh´ y zp˚ usob je vloˇzen´ı zdrojového kódu do textového pole (viz Obrázek 2.2).

6



Obrázek 2.2: Zp˚ usob odevzdán´ı u ´lohy Po odeslán´ı u ´lohy si m˚ uˇzeme pomoc´ı webov´ ych stránek [2] zjistit, jakou odpovˇed’ jsme dostali od validátoru, jak m˚ uˇzeme vidˇet na obrázku (viz Obrázek 2.3). Na tomto obrázku vid´ıme, ˇze kaˇzdé odevzdán´ı má svoje identifikaˇcn´ı ˇc´ıslo, které je ve sloupci #. Následuje sloupec, ve kterém je spoleˇcnˇe identifikaˇcn´ı ˇc´ıslo u ´lohy s jej´ım názvem. Ve sloupci Verdict, nalezneme odpovˇed’ od validátoru. Sloupec Language obsahuje jazyk, ve kterém jsme ˇreˇsen´ı napsali a ve sloupc´ıch Run Time a Submission Date, jsou informace o ˇcasu bˇehu a datu, kdy u ´loha byla odevzdána.

7



Obrázek 2.3: Informace o odevzdan´ ych u ´lohách V´ ysledek se také zas´ılá na náˇs e-mail, pakliˇze jsme pˇri registraci zaˇskrtli odes´ılán´ı v´ ysledk˚ u na e-mail. Moˇzné odpovˇedi od validátoru jsou: • In Queue (QU) - Validátor je zaneprázdnˇen a nem˚ uˇze hned poskytnout informace o správnosti. V´ ysledky budou hned co bude moc. ˇ sen´ı bylo akceptované pro dané zadán´ı. • Accepted (AC) - Reˇ • Presentation Error (PE) - V´ ystup ˇreˇsen´ı je správn´ y, ale v´ ystup je ˇspatnˇe prezentován. • Wrong Answer (WA) - V´ ystup vaˇseho ˇreˇsen´ı je chybn´ y. • Compile Error (CE) - Pˇri kompilaci doˇslo k chybˇe. • Runtime Error (RE) - V pr˚ ubˇehu bˇehu programu se vyskytla chyba. • Time Limit Exceeded (TL) - Vaˇse ˇreˇsen´ı pˇrekroˇcilo ˇcasov´ y limit pro danou u ´lohu. • Memory Limit Exceeded (ML) - Program pˇrekroˇcil pamˇet’ové nároky, které bylo moˇzné vyuˇz´ıt pro danou u ´lohu. 8


Vybrané u ´lohy ze sady u ´loh

• Output Limit Exceeded (OL) - Program vypisuje pˇr´ıliˇs mnoho informac´ı. • Submission Error (SE) - Nepodaˇrilo se odevzdat u ´lohu. • Restricted Function (RF) - Program vyuˇz´ıvá funkce, které jsou zakázané. • Can’t Be Judged (CJ) - Program nem˚ uˇze b´ yt posouzen z d˚ uvodu, ˇze validátor nemá vstupn´ı a v´ ystupn´ı soubory.

2.3

Vybran´ eu ´ lohy ze sady u ´ loh

N´ıˇze si m˚ uˇzete prohlédnout ukázky u ´loh z vypracované sady. Vˇsechny u ´lohy byly naprogramovány pomoc´ı programovac´ıho jazyka Java a vˇsechny byly u ´spˇeˇsnˇe validovány na validaˇcn´ım serveru UVa Online Judge [2]. U kaˇzdé u ´lohy je origináln´ı zadán´ı, pˇreloˇzené origináln´ı zadán´ı a je popsána základn´ı myˇslenka u ´lohy s moˇzn´ ym zp˚ usobem ˇreˇsen´ı. U kaˇzdé u ´lohy je napsáno, jaké problémy se u dané u ´lohy pˇri ˇreˇsen´ı mohou vyskytnout. Na pˇriloˇzeném CD poté m˚ uˇzete naj´ıt vˇsech tˇriadvacet vyˇreˇsen´ ych u ´loh (viz Obrázek 2.4) s PDF souborem, ve kterém je origináln´ı zadán´ı u ´lohy. Naleznete tam také pˇreloˇzené zadán´ı do ˇceˇstiny s popisem moˇzného zp˚ usobu ˇreˇsen´ı pro danou u ´lohu. Ke kaˇzdé u ´loze jsou vytvoˇreny vstupy a v´ ystupy, které taktéˇz naleznete na pˇriloˇzeném CD. Vˇsechny u ´lohy jsou na pˇriloˇzeném CD rozdˇeleny do tˇr´ı sloˇzek Lehké, Stˇrednˇe obt´ıˇzné a Obt´ıˇzné, podle obt´ıˇznosti ˇreˇsen´ı.

9



Obrázek 2.4: Seznam vyˇreˇsen´ ych u ´loh Pˇri ˇreˇsen´ı u ´loh, jsem vyuˇz´ıval kn´ıˇzku Uˇcebnice jazyka Java [3], která mi pomohla se syntax´ı Javy. Pro algoritmy, jsem vyuˇz´ıval kn´ıˇzku Programming Challenges [4], která je dostupná ke staˇzen´ı na Internetu a kn´ıˇzku Algorithms (4th Edition) od autor˚ u Roberta Sedgewicka a Kevina Wayna. Nejv´ıce mi, ale pomohla pˇri ˇreˇsen´ı webová stránka [5], kde se daj´ı naj´ıt diskuze o dané u ´loze.

2.3.1

Seˇ rad’te jazyky

Zad´ an´ı Pravdˇepodobnˇe jste si vˇsimli, ˇze angliˇctinou a ˇspanˇelˇstinou se mluv´ı v mnoha oblastech po celém svˇetˇe. Ted’ by bylo zaj´ımavé, seˇradit vˇsechny jazyky podle poˇct˚ u stát˚ u, kde se dan´ ym jazykem mluv´ı. Dostanete mapu, na které jsou zobrazeny státy s jazykem, se kter´ ym dan´ y stát mluv´ı. Pod´ıvejte se na následuj´ıc´ı mapu jako pˇr´ıklad. ttuuttdd 10



ttuuttdd uuttuudd uuttuudd Kaˇzdé p´ısmeno je zkratka pro jazyk a státy. Stát je definován jako spojená plocha se stejn´ ym p´ısmenem. Dvˇe p´ısmena jsou spojena, pokud druhé p´ısmeno je vlevo, vpravo, nad nebo pod. To znamená, ˇze na mapˇe jsou tˇri státy, kde se mluv´ı jazykem ,t‘ , tˇri státy, kde se mluv´ı jazykem ,u‘ a jeden stát, kde lidé mluv´ı jazykem ,d‘ . Vaˇs´ım u ´kolem je urˇcit poˇcet stát˚ u pro kaˇzd´ y jazyk a vytisknout v´ ysledky v zadaném poˇrad´ı.

Vstup Prvn´ı ˇrádek obsahuje poˇcet testovan´ ych pˇr´ıpad˚ u N. Kaˇzd´ y testovan´ y pˇr´ıpad se skládá z ˇrádku s dvˇema ˇc´ısly H a W, která udávaj´ı v´ yˇsku a ˇs´ıˇrku mapy. Poté následuje H ˇra´dk˚ u s ˇretˇezcem W p´ısmen. Tyto p´ısmena budou vˇzdy malá od ,a‘ do ,z‘ .

V´ ystup Pro kaˇzd´ y testovan´ y pˇr´ıpad vypiˇste World #n“, kde n je ˇc´ıslo testovaného ” pˇr´ıpadu. Poté vypiˇste ˇra´dek pro kaˇzd´ y jazyk, kter´ y se objev´ı v testovaném ˇ adek obsahuje jazyk, dvojteˇcku, mezeru a poˇcet stát˚ pˇr´ıpadˇe. R´ u, kde se t´ımto jazykem mluv´ı. Tyto ˇrádky jsou vypsány sestupnˇe podle poˇctu stát˚ u. Pokud dva jazyky maj´ı stejn´ y poˇcet stát˚ u, seˇrad´ı se podle abecedy, coˇz znamená, ˇze napˇr´ıklad jazyk ,i‘ bude pˇred jazykem ,q‘ .

Pˇ r´ıklad vstupu 2 48 ttuuttdd ttuuttdd uuttuudd uuttuudd 11



99 bbbbbbbbb aaaaaaaab bbbbbbbab baaaaacab bacccccab bacbbbcab bacccccab baaaaaaab bbbbbbbbb

Pˇ r´ıklad v´ ystupu World #1 t: 3 u: 3 d: 1 World #2 b: 2 a: 1 c: 1

Shrnut´ı zad´ an´ı C´ılem tohoto u ´kolu je zjistit z mapy poˇcet stát˚ u, ve kter´ ych se mluv´ı stejn´ ym jazykem. Vstupn´ı mapa je dána jako pole o velikosti m x n. Jazyk je definován jako p´ısmeno na mapˇe. Pokud se stejná p´ısmena dot´ ykaj´ı hranou, jde o stejn´ y stát.

Zp˚ usob ˇ reˇ sen´ı Tento u ´kol lze vyˇreˇsit pomoc´ı rekurzivn´ıho programován´ı, kde budeme postupovat od jednoho p´ısmena k dalˇs´ımu a od kaˇzdého p´ısmena p˚ ujdeme smˇerem doleva, nahoru, doprava a dol˚ u. Kaˇzd´ y znak, kter´ y objev´ıme si oznaˇc´ıme urˇcit´ ym znakem, kter´ y bude oznaˇcovat, ˇze dané p´ısmeno bylo zpracováno. Tento znak bude slouˇzit s hranicemi mapy jako ukonˇcen´ı rekurze. Pˇri zpracováván´ı p´ısmen si dˇeláme statistiky o poˇctu jazyk˚ u. 12



Moˇ zn´ e probl´ emy Z d˚ uvodu, ˇze jsme pouˇzili pro ˇreˇsen´ı u ´lohy rekurzivn´ı algoritmus se m˚ uˇze vyskytnout problém ohlednˇe nedostatku pamˇeti. Z tohoto d˚ uvodu je potˇreba zaˇr´ıdit, aby kaˇzdé p´ısmeno, které uˇz bylo zpracované rekurz´ı, zastavilo postup dalˇs´ı rekurze, které by dané p´ısmeno chtˇelo zpracovávat.

2.3.2

Dek´ odov´ an´ı p´ asky

Zad´ an´ı Váˇs ˇséf právˇe objevil v arch´ıvu staré poˇc´ıtaˇcové pásky. Na tˇechto páskách s otvory, m˚ uˇzou b´ yt uˇziteˇcné informace. Je na vás, abyste zjistili, co je na nich napsáno.

Vstup Vstup bude obsahovat jednu pásku.

V´ ystup V´ ystupn´ı zpráva, která je napsaná na pásce.

13



Pˇ r´ıklad vstupu

| | | | |

ooo . o | ooo . o o | oo o . o | oo . oo | oo o . oo |

Pˇ r´ıklad v´ ystupu quick

Shrnut´ı zad´ an´ı ˇef dal programátorovi starou dˇernou pásku a chce zjistit, jestli na n´ı nejsou S´ uloˇzeny nˇejaké d˚ uleˇzité informace.

Zp˚ usob ˇ reˇ sen´ı Tato u ´loha je velmi jednoduchá, pokud ˇreˇsitel v´ı, jak jsou data uloˇzena na pásce. Kaˇzdá páska má na kaˇzdé ˇrádce 6 otvor˚ u. Pokud tento otvor je prázdn´ y, znamená to, ˇze jeho hodnota je jedna, pokud pln´ y tak 0. Ze ˇsesti otvor˚ u dostaneme 6-ti m´ıstné dvojkové ˇc´ıslo, které po pˇrevodu do des´ıtkové soustavy udává pozici znaku v ASCII tabulce (viz Obrázek 2.5).

Obrázek 2.5: Zp˚ usob pˇrevodu

14



Moˇ zn´ e probl´ emy Jedin´ y problém, kter´ y m˚ uˇze nastat pˇri ˇreˇsen´ı této u ´lohy je, ˇze programátor nebude znát, jak jsou data uloˇzena na pásce. Pokud by to nastalo, u ´lohu by nebyl schopen vyˇreˇsit.

2.3.3

Pˇ reteˇ cen´ı

Zad´ an´ı Napiˇste program, kter´ y pˇreˇcte v´ yraz skládaj´ıc´ı se ze dvou kladn´ ych ˇc´ısel a operátoru. Zjistˇete, zda celá ˇc´ısla nebo v´ ysledek v´ yrazu je pˇr´ıliˇs velk´ y pro prezentaci jako normáln´ı“ neznaménkov´ y integer. Typ integer, pokud pracujete ” v Pascalu, typ int pokud pracujete v C.

Vstup Neznám´ y poˇcet ˇrádk˚ u. Kaˇzd´ y ˇrádek obsahuje celé ˇc´ıslo, jeden ze dvou operátor˚ u ,+‘ nebo ,*‘ a druhé celé ˇc´ıslo.

V´ ystup Pro kaˇzd´ y ˇrádek vstupu, vytisknete vstup nasledovan´ y 0 aˇz 3 ˇrádky obsahuj´ıc´ı jednu z tˇechto zpráv podle vhodnosti: first number too big“ (prvn´ı ˇc´ıslo je ” pˇr´ıliˇs velké), second number too big“ (druhé ˇc´ıslo je pˇr´ıliˇs velké), result too ” ” big“ (v´ ysledek je pˇr´ıliˇs velk´ y).

Pˇ r´ıklad vstupu 300 + 3 9999999999999999999999 + 11

15



Pˇ r´ıklad v´ ystupu 300 + 3 9999999999999999999999 + 11 first number too big result too big

Shrnut´ı zad´ an´ı C´ıl této u ´lohy je naˇc´ıst ze ˇra´dky dvˇe ˇc´ısla a jeden operátor a zjistit, jestli zadaná ˇc´ısla nebo spoˇc´ıtan´ y v´ ysledek nepˇretekl datov´ y typ integer.

Zp˚ usob ˇ reˇ sen´ı Naˇcteme ˇra´dek, z nˇehoˇz z´ıskáme dvˇe ˇc´ısla a operand. Mus´ıme poˇc´ıtat s t´ım, ˇze mezi ˇc´ısly a operandem m˚ uˇze b´ yt v´ıc jak jeden prázdn´ y znak. Pro uchován´ı vˇsech ˇc´ısel pouˇzijeme BigInteger. Následnˇe budeme testovat, jestli prvn´ı ˇc´ıslo nepˇreteklo. Pokud ˇc´ıslo má ménˇe neˇz 10 znak˚ u, nepˇreteˇce. Pokud bude m´ıt v´ıce jak 10 znak˚ u, pˇreteˇce. Pakliˇze ˇc´ıslo má právˇe 10 znak˚ u, mus´ıme nejdˇr´ıve otestovat, jestli dané ˇc´ıslo je menˇs´ı nebo vˇetˇs´ı neˇz nejvˇetˇs´ı hodnota typu integer a podle toho rozhodnou, jestli dané ˇc´ıslo pˇreteˇce nebo ne. Tento postup provedeme i pro druhé ˇc´ıslo. Poté obˇe ˇc´ısla seˇcteme ˇci vynásob´ıme podle vstupn´ıho operandu. V´ ysledek budeme vyhodnocovat jako pˇredeˇslá ˇc´ısla.

Moˇ zn´ e probl´ emy M˚ uˇze se stát, ˇze validátor bude stále dokola dávat odpovˇed’, ˇze dané ˇreˇsen´ı je nesprávné. Jedn´ım z d˚ uvod˚ u m˚ uˇze b´ yt, ˇze jsme si neuvˇedomili, ˇze mezi zadan´ ymi ˇc´ısly a operátorem se m˚ uˇze vyskytnout libovoln´ y poˇcet b´ıl´ ych znak˚ u, které jsme zapomnˇeli odstranit.

16


2.3.4


Z´ amek

Zad´ an´ı V posledn´ı dobˇe je jeden závaˇzn´ y problém s Panda Land Safe Box. Nˇekolik trezor˚ u bylo vykradeno. Trezory pouˇz´ıvaj´ı 4 ˇc´ıselnou kombinaci válcového zámku (viz Obrázek 2.6). M˚ uˇzete pouze otáˇcet ˇc´ıslicemi smˇerem nahoru nebo dol˚ u, dokud vˇsechna ˇctyˇri ˇc´ısla neodpov´ıdaj´ı kl´ıˇci. Kaˇzdá ˇc´ıslice je navrˇzena tak, aby se otáˇcela od 0 do 9. Otoˇcen´ım nahoru z 9 se dostaneme na ˇc´ıslo 0 a otoˇcen´ı dol˚ u z 0 se dostaneme na ˇc´ıslici 9. Vzhledem k tomu existuje 10 000 kl´ıˇc˚ u, 0000 aˇz 9999. Kaˇzd´ y m˚ uˇze vyzkouˇset vˇsechny kombinace, dokud se sejf neodemkne.

Obrázek 2.6: Válcov´ y zámek Co se stalo, stalo se. Aby bylo moˇzné zpomalit u ´tok budouc´ıch lupiˇc˚ u, Panda Security Agency (PSA) vymyslela nov´ y bezpeˇcnostn´ı zámek s nˇekolika tlaˇc´ıtky. Nam´ısto pouˇzit´ı jedné kombinace kl´ıˇce, zámek nyn´ı m˚ uˇze m´ıt aˇz N kl´ıˇc˚ u, které mus´ı b´ yt vˇsechny odemknuty, aby ˇsel trezor odemknout. Tento zámek funguje takto: • Zpoˇcátku jsou ˇc´ısla na 0000. • Kl´ıˇce m˚ uˇzou b´ yt uvolnˇeny v libovolném poˇrad´ı. • Magické tlaˇc´ıtko JUMP m˚ uˇze nastavit ˇc´ıslice do nˇekterého z odemˇcen´ ych kl´ıˇc˚ u, aniˇz by bylo nˇejaké otoˇcen´ı. • Sejf se odemkne jenom tehdy, pokud jsou vˇsechny kl´ıˇce odemknuty s minimáln´ım poˇctem otoˇcen´ı s v´ yjimkou JUMP. • Pokud dojde k pˇrekroˇcen´ı poˇctu otáˇcen´ı, ˇc´ısla se vrát´ı do 0000 a vˇsechny kl´ıˇce budou opˇet zamˇceny. Tedy bude stav zámku vynulován a prolomen´ı bylo ne´ uspˇeˇsné. 17



PSA je zcela pˇresvˇedˇcené, ˇze tento nov´ y systém zpomal´ı prolamován´ı a dá jim dostatek ˇcasu na identifikaci a chycen´ı zlodˇeje. Aby bylo moˇzné urˇcit minimáln´ı potˇrebn´ y poˇcet otoˇcen´ı, chce PSA napsat program. Dostanete vˇsechny kl´ıˇce, spoˇc´ıtejte minimáln´ı poˇcet otoˇcen´ı, které je potˇreba k odemˇcen´ı sejfu.

Vstup Prvn´ı ˇrádek obsahuje celé ˇc´ıslo T, které udává poˇcet testovan´ ych pˇr´ıpad˚ u. Kaˇzd´ y pˇr´ıpad zaˇc´ıná cel´ ym ˇc´ıslem N (1<=N <=500) následuje poˇcet kl´ıˇc˚ u. Kaˇzdá z N dalˇs´ıch ˇra´dek obsahuje pˇresnˇe 4 ˇc´ıselná ˇc´ısla (pˇredn´ı nuly jsou povoleny) pˇredstavuj´ıc´ı kl´ıˇce pro odemknut´ı.

V´ ystup Pro kaˇzd´ y testovan´ y pˇr´ıpad, vytisknete na jednom ˇrádku minimáln´ı poˇcet otáˇcen´ı, potˇrebn´ y k odemknut´ı vˇsech kl´ıˇc˚ u. Vysvˇetlen´ı pro 2. pˇr´ıpad: • Dejte 0000 do 1111, otoˇcen´ı: 4 • Dejte 1111 do 1155, otoˇcen´ı: 8 • Skok z 1155 do 1111, m˚ uˇzeme to udˇelat, protoˇze 1111 bylo uˇz odemknuto. • Dejte 1111 do 5511, otoˇcen´ı 8 Celkem otoˇcen´ı = 4 + 8 + 8 = 20

Pˇ r´ıklad vstupu 4 2 3 3 4

1155 1111 1234 2145

2211 1155 5511 5678 9090 0213 9113 8113 18



Pˇ r´ıklad v´ ystupu 16 20 26 17

Shrnut´ı zad´ an´ı Dostaneme mnoˇzinu kl´ıˇc˚ u, které maj´ı odemknout ˇctyˇrcifern´ y rolovac´ı zámek. Zámek se odemkne, pokud odemkneme vˇsechny kl´ıˇce s nejménˇe otoˇcen´ım. Zámek má také funkci, která dokáˇze nastavit cifry na hodnotu z dˇr´ıve odemˇceného kl´ıˇce. Pˇri této funkci se nezapoˇc´ıtává ˇza´dné otoˇcen´ı.

Zp˚ usob ˇ reˇ sen´ı Naˇcteme vˇsechny kl´ıˇce, které budou slouˇzit jako vrcholy grafu. Poté vytvoˇr´ıme hrany, mezi vˇsemi vrcholy a vypoˇc´ıtáme hodnotu hrany tak, ˇze zjist´ıme, kolik je potˇreba otoˇcen´ı na zámku, abychom jsme se dostali z jednoho kl´ıˇce do druhého. Následnˇe budeme hledat minimáln´ı kostru grafu. Nejdˇr´ıve si seˇrad´ıme hrany od nejmenˇs´ı hodnoty, kterou jsme si vypoˇc´ıtali. Poté budeme procházet seˇrazené hrany a ukládat si v´ ysledné hrany, které budou spojovat vrcholy. Hranu dáme do v´ ysledn´ ych, pokud hrana, se kterou spoj´ıme dva vrcholy nevytvoˇr´ı v grafu cyklus. Pokud ho vytvoˇr´ı, hranu zahod´ıme. Po zjiˇstˇen´ı hran, která tvoˇr´ı kostru, projedeme vˇsechny tyto hrany a budeme sˇc´ıtat jejich hodnoty. Poté mus´ıme k v´ ysledku pˇriˇc´ıst nejmenˇs´ı hodnotu, z které se dostaneme od poˇca´teˇcn´ı hodnoty do nˇekterého z kl´ıˇc˚ u. V´ ysledná hodnota je ˇreˇsen´ı pro dan´ y pˇr´ıpad.

Moˇ zn´ e probl´ emy Tato u ´loha nejde ˇreˇsit pomoc´ı brutáln´ı s´ıly z d˚ uvodu, ˇze se nevejdeme do ˇcasového limitu. Z tohoto d˚ uvodu si mus´ıme uvˇedomit, ˇze dan´ y problém lze ˇreˇsit pomoc´ı minimáln´ı kostry grafu.

19


2.3.5


Nejdelˇ s´ı spoleˇ cn´ a posloupnost

Zad´ an´ı Máte dvˇe sekvence znak˚ u. Vypiˇste délku nejdelˇs´ı spoleˇcné posloupnosti obou sekvenc´ı. Napˇr´ıklad nejdelˇs´ı spoleˇcná posloupnost z tˇechto dvou sekvenc´ı abcdgh aedfhr je adh délky 3. Vstup se skládá ze dvou ˇra´dek. Prvn´ı ˇra´dek obsahuje prvn´ı ˇretˇezec, druh´ y ˇra´dek obsahuje druh´ y ˇretˇezec. Kaˇzd´ y ˇretˇezec je na samostatné ˇra´dce a obsahuje nejv´ yˇse 1000 znak˚ u. Pro kaˇzdé dva ˇra´dky vypiˇste ˇra´dek obsahuj´ıc´ı jedno celé ˇc´ıslo, které splˇ nuje v´ yˇse uvedená kritéria.

Pˇ r´ıklad vstupu a1b2c3d4e zz1yy2xx3ww4vv abcdgh aedfhr abcdefghijklmnopqrstuvwxyz a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0 abcdefghijklmnzyxwvutsrqpo opqrstuvwxyzabcdefghijklmn

Pˇ r´ıklad v´ ystupu 4 3 26 14

20



Shrnut´ı zad´ an´ı Na vstupu dostaneme dva ˇretˇezce a mus´ıme zjistit délku nejdelˇs´ı spoleˇcné posloupnosti.

Zp˚ usob ˇ reˇ sen´ı Tento problém lze vyˇreˇsit pomoc´ı dynamického programovan´ı. Vytvoˇr´ı se celoˇc´ıselné dvourozmˇerné pole o délce prvn´ıho slova a ˇs´ıˇrce druhého slova. K poli pˇridáme jeˇstˇe jeden ˇra´dek a sloupek. Prvn´ı sloupek a prvn´ı ˇra´dek se vypln´ı nulami. Index ˇra´dku ukazuje na znak v prvn´ım slovˇe a index sloupce ukazuje na znak ve druhém slovˇe. Následuj´ıc´ı buˇ nky se vyplˇ nuj´ı podle následuj´ıc´ıho postupu. Buˇ nky se budou vyplˇ novat po ˇra´dc´ıch. Pokud jsou si znaky rovny, vloˇz´ı se do buˇ nky ˇc´ıslo o jednu hodnotu vˇetˇs´ı, neˇz je na pozici ˇc´ıslo o jeden sloupek a jeden ˇra´dek zpˇet. Pokud si znaky nejsou rovny, vloˇz´ı se do buˇ nky ˇc´ıslo, které je o sloupek zpˇet nebo o ˇrádek n´ıˇz podle toho, které je vˇetˇs´ı. T´ımto postupem se vypln´ı celé pole (viz Tabulka 2.1). V´ yslednou hodnotu najdeme v posledn´ı buˇ nce.

0 a 0 1 0 b 0 2 0 c 0 3 0 d 0 4 0 e 0

z 0 0 0 0 0 0 0 0 0 0

z 1 y 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1

y 0 0 1 1 1 1 1 1 1 1

2 x x 3 w 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 3 3 2 2 2 3 3 2 2 2 3 3

w 0 0 1 1 2 2 3 3 3 3

4 v 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4

v 0 0 1 1 2 2 3 3 4 4

Tabulka 2.1: Vyplnˇené pole

Moˇ zn´ e probl´ emy Pokud programátor zná algoritmus, kter´ y nejdelˇs´ı spoleˇcnou posloupnost vypoˇc´ıtá, nen´ı problém u ´lohu vyˇreˇsit. 21


2.4

Problémy pˇri ˇreˇsen´ı u ´loh

Probl´ emy pˇ ri ˇ reˇ sen´ı u ´ loh

Nejvˇetˇs´ı problém pˇri ˇreˇsen´ı u ´loh se t´ yká anglického jazyka. V zadán´ı b´ yvá spousta detail˚ u, které je potˇreba splnit. Pokud ale programátor neovládá anglick´ y jazyk na v´ yborné u ´rovni, tyto detaily nemus´ı pochopit a pˇri odevzdáván´ı sloˇzitˇe hledat d˚ uvod, proˇc dané ˇreˇsen´ı validátor neakceptuje. Dalˇs´ım velk´ ym problémem pˇri ˇreˇsen´ı je ˇcasov´ y limit na vyˇreˇsen´ı daného problému. Tento limit je nastaven stejnˇe pro vˇsechny programovac´ı jazyky. Z tohoto d˚ uvodu je znev´ yhodnˇena Java oproti jazyku C/C++, které jsou ˇ v´ yraznˇe rychlejˇs´ı. Casto se proto stává, ˇze algoritmus, kter´ y ˇreˇs´ı dan´ y problém a je naprogramován v Javˇe, neprojde na ˇcasov´ y limit, ale pokud se naprogramuje v C/C++, tento algoritmus projde.

22

3 Softwarové aplikace 3.1

C´ıle aplikace

Mnoho student˚ u a zamˇestnanc˚ u Západoˇceské univerzity se u ´ˇcastn´ı programátorsk´ ych soutˇeˇz´ı. Tyto soutˇeˇze maj´ı spoleˇcn´ y základ v tom, ˇze je zadaná u ´loha a je potˇreba vymyslet optimáln´ı algoritmus, kter´ y ji ˇreˇs´ı a realizovat ho pomoc´ı zdrojového kódu. Pro ˇreˇsen´ı zadaného problému se ˇcasto vyuˇz´ıvaj´ı základn´ı algoritmy, jako je napˇr´ıklad prohledáván´ı grafu do hloubky, prohledáván´ı grafu do ˇs´ıˇrky, dynamické programován´ı atd.. Rozd´ıl je pouze v zadán´ı u ´lohy, z které mus´ı soutˇeˇz´ıc´ı poznat, jak´ y algoritmus pro dan´ y problém má pouˇz´ıt. Z tohoto d˚ uvodu vznikla tato softwarová aplikace, ve které by mˇeli uˇzivatelé shromaˇzd’ovat a sd´ılet vyˇreˇsené u ´lohy s popisem, s jak´ ym algoritmem danou u ´lohu vyˇreˇsili. Uˇzivatelé by d´ıky této aplikaci mˇeli m´ıt moˇznost z vyˇreˇsen´ ych u ´loh poznat, jak´ y algoritmus maj´ı pouˇz´ıt pro dan´ y problém. Hotové pˇr´ıklady s doprovodn´ ym textem by v budoucnu mˇely slouˇzit jako pomocn´ y uˇcebn´ı materiál pro uˇzivatele zab´ yvaj´ıc´ı se programován´ım. Aplikace by mˇela fungovat ve dvou reˇzimech. V prvn´ım reˇzimu, by aplikace mˇela b´ yt schopna prohl´ıˇzet a upravovat vˇsechny u ´lohy, které jsou v aplikaci uloˇzeny, pokud je aplikace pˇripojena na Internet. V druhém reˇzimu by uˇzivatel mˇel m´ıt moˇznost procházek u ´lohy, které si v prvn´ım reˇzimu uloˇzil bez toho, ˇze by aplikace musela b´ yt pˇripojena na Internet. K u ´lohám by mˇela b´ yt také diskuze, kde by uˇzivatelé mohli diskutovat o dané u ´loze.

3.2

Pouˇ zit´ e technologie

Aplikace byla naprogramována pomoc´ı platformy Java SE s programovac´ım jazykem Java. Pro sestaven´ı aplikace byla pouˇzita aplikace Apache Ant. K uloˇzen´ı dat aplikace vyuˇz´ıvá relaˇcn´ı databázi MySQL.

23

Softwarové aplikace

3.2.1

Pouˇzité technologie

Platforma Java

Java platforma je sada softwarového vybaven´ı, která slouˇz´ı pro v´ yvoj a spuˇstˇen´ı aplikac´ı, které byly napsány v programovac´ım jazyce Java. Platforma byla vyrobena a specifikována firmou Sun Microsystems, která byla v roce 2009 koupena spoleˇcnost´ı Oracle. Základem platformy Javy je Java Virutal Machine(JVM) slouˇz´ıc´ı pro spuˇstˇen´ı Java bytecodu a Java Application Programming Interface(API) obsahuj´ıc´ı základn´ı knihovny pro v´ yvoj aplikac´ı. Java bytecode dostaneme pˇreloˇzen´ım zdrojového kódu napsaného v programovac´ım jazyce Java. Existuj´ı i pˇrekladaˇce, které jsou schopny vytvoˇrit Java bytecode ze zdrojového kódu, kter´ y byl napsan´ y v jiném programovac´ım jazyce napˇr. Python. Protoˇze náˇs program se nejdˇr´ıve pˇrekládá do Java byte kódu a ten se spouˇst´ı v JVM, m˚ uˇze naˇse aplikace bˇeˇzet na r˚ uzn´ ych zaˇr´ızen´ı, na kter´ ych bˇeˇz´ı JVM. Platforma je vydávaná ve v´ıce verz´ı, které obsahuj´ı potˇrebné softwarové vybaven´ı pro v´ yvoj v daném prostˇred´ı. A to jsou: • JavaCard - v´ yvoj aplikac´ı pro platebn´ı a kreditn´ı karty, • Java SE - v´ yvoj aplikac´ı pro domác´ı poˇc´ıtaˇce, • Java EE - v´ yvoj rozsáhl´ ych podnikov´ ych aplikac´ı, • Java ME - v´ yvoj pro mobiln´ı aplikace.

3.2.2

Programovac´ı jazyk Java

Programovac´ı jazyk Java patˇr´ı mezi objektové orientované programovac´ı jazyky, kter´ y byl vyroben firmou Sun Microsystems v roce 1995. Je to hlavn´ı programovac´ı jazyk pro v´ yvoj aplikac´ı na platformˇe Java. Java patˇr´ı mezi nejpouˇz´ıvanˇejˇs´ı programovac´ı jazyky na svˇete. Nejvˇetˇs´ı jej´ı pˇrednost´ı je jej´ı multiplatformn´ı nezávislost. Pomoc´ı programovac´ıho jazyka Java m˚ uˇzeme vytváˇret aplikace pro r˚ uzná zaˇr´ızen´ı od poˇc´ıtaˇc˚ u aˇz po ˇcipové karty.

24


Pouˇzité technologie

V´ yhody jazyka Javy • Multiplatformn´ı nezávislost • Jednoduchá syntaxe • Objektovˇe orientovan´ y • Velké mnoˇzstv´ı knihoven

Nev´ yhody jazyka Javy • Pomal´ y start aplikace - Tento problém vzniká z d˚ uvodu, ˇze zdrojov´ y kód je nejdˇr´ıve pˇreloˇzen do Java bytecodu, kter´ y je následnˇe spuˇstˇen´ y v JVM. • Velk´ a pamˇ et’ov´ a n´ aroˇ cnost - Následkem pouˇzit´ı Garbage collectoru, kter´ y se stará v Javˇe o pˇridˇelen´ı a uvolˇ nován´ı pamˇeti.

3.2.3

Apache Ant

Apache Ant je open source softwarová aplikace slouˇz´ıc´ı pro sestavován´ı softwarov´ ych aplikac´ı napsan´ y pˇreváˇznˇe v jazyce Java. Protoˇze je Ant kompletnˇe napsán v jazyce Java, jde o aplikaci multiplatformnˇe nezávislou. Pro napsan´ı scriptu, kter´ y Ant zpracovává se pouˇz´ıvá jazyk XML.

3.2.4

Datab´ aze MySQL

MySQL je relaˇcn´ı databázov´ y systém vytvoˇren´ y firmou MySQL AB a nyn´ı vlastnˇeno firmou Oracle. Jde o multiplatformn´ı databázi, která slouˇz´ı pro uchováván´ı dat. Pro komunikaci s databáz´ı se vyuˇz´ıvá dotazovac´ı jazyk SQL.

Jazyk SQL Jazyk SQL je standardizovan´ y dotazovac´ı jazyk pro z´ıskáván´ı dat z relaˇcn´ıch databáz´ı. Pˇrestoˇze jde o dotazovac´ı jazyk, m˚ uˇzeme také pomoc´ı SQL pˇr´ıkazu

25


Pouˇzité architektury

vytváˇret, mazat a upravovat data v databázi. SQL pˇr´ıkazy lze rozdˇelit do tˇr´ı skupin. • Pˇ r´ıkazy pro manipulaci s daty - Tyto pˇr´ıkazy slouˇz´ı pro z´ıskán´ı a manipulaci dat z databáze. Oznaˇcuj´ı se zkratkou DML. Mezi tyto pˇr´ıkazy patˇr´ı SELECT, UPDATE, INSERT, DELETE atd. • Pˇ r´ıkazy pro definici dat - Pˇr´ıkazy slouˇz´ıc´ı pro vytvoˇren´ı struktury v databázi. Oznaˇcuj´ı se zktratkou DDL. Mezi tyto pˇr´ıkazy patˇr´ı CREATE, DROP a ALTER. • Pˇ r´ıkazy pro ˇ r´ızen´ı dat - Pˇr´ıkazy slouˇz´ı pro nastaven´ı pˇr´ıstupov´ ych práv a ˇr´ızen´ı transakc´ı. Oznaˇcuj´ı se zkratkou DCL. Mezi tyto pˇr´ıkazy patˇr´ı REVOKE, COMMIT, ROLLBACK atd.

3.3

Pouˇ zit´ e architektury

Pro vytvoˇren´ı aplikace byla pouˇzita s´ıt’ová architektura klient-server. Obˇe aplikace jsou napsány pomoc´ı v´ıcevrstvé architektury.

3.3.1

S´ıt’ov´ a architektura klient-server

Klient-server je s´ıt’ová architektura, která rozdˇeluje aplikaci na klienta a server. Tyto dvˇe aplikace mezi sebou komunikuj´ı pomoc´ı poˇc´ıtaˇcové s´ıtˇe.

Server Aplikace, která slouˇz´ı jako server, pracuje pasivnˇe, kdy ˇceká na dotazy od pˇripojeného klienta. Tento dotaz server zpracuje a odes´ılá klientovi odpovˇed’ (viz Obrázek 3.1).

Klient Tato aplikace se pˇripojuje k serveru a pracuje aktivnˇe. Po odeslán´ı dotazu serveru klient ˇceká, aˇz server zaˇsle odpovˇed’ (viz Obrázek 3.1). 26


Pouˇzité architektury

Obrázek 3.1: Klient-server

3.3.2

V´ıcevrstv´ a architektura

V´ıcevrstvá architektura je zp˚ usob v´ yvoje aplikace, která rozdˇel´ı aplikaci do nˇekolika vzájemnˇe nezávisl´ ych vrstev, které mezi sebou komunikuj´ı podle definovaného rozhran´ı. Kaˇzdá z vrstev se m˚ uˇze starat o r˚ uznou ˇca´st aplikace. Mezi nejznámˇejˇs´ı v´ıcevrstvou architekturu patˇr´ı tˇr´ıvrstvá (viz Obrázek 3.2), která rozdˇeluje vrstvy do tˇechto tˇr´ı vrstev: • Prezenˇ cn´ı vrstva - Prezenˇcn´ı vrstva se stará o komunikaci s uˇzivatelem. Pro komunikaci s uˇzivatelem se nejˇcastˇeji pouˇz´ıvá grafické uˇzivatelské rozhran´ı. • Aplikaˇ cn´ı vrstva - Aplikaˇcn´ı vrstva se stará o logickou ˇca´st aplikace. • Datov´ a vrstva - Datová vrstva se stará o naˇcten´ı a uloˇzen´ı dat. Tato vrstva m˚ uˇze vyuˇz´ıvat napˇr. databázi, soubory atd.

27


Programátorská dokumentace

Obrázek 3.2: Tˇr´ıvrstvá architektura

3.4

Program´ atorsk´ a dokumentace

Celá softwarová aplikace je pojmenovaná ACM u ´loˇziˇstˇe. Je rozdˇelena na dvˇe aplikace a to ACM u ´loˇziˇstˇe - server a ACM u ´loˇziˇstˇe - klient.

3.4.1

Datab´ aze

Pro uloˇzen´ı dat jsou v databázi vytvoˇreny ˇctyˇri tabulky: • diskuze, • uzivatele, • slozky, • ulohy.

Tabulka diskuze V této tabulce se ukládaj´ı informace o diskuz´ıch v u ´lohách. Kaˇzd´ y záznam v tabulce mus´ı obsahovat id záznamu, id rodiˇce, kdo záznam vloˇzil, datum vloˇzen´ı a k jaké u ´loze záznam patˇr´ı. Kaˇzdá u ´loha, která byla vytvoˇrena, mus´ı

28



vytvoˇrit pro danou u ´lohu záznam v diskuzi s rodiˇcem null, kter´ y znamená, ˇze dan´ y záznam, nemá rodiˇce.

Tabulka uzivatele V tabulce uzivatele se ukládaj´ı informace o uˇzivateli. Tabulka obsahuje id uˇzivatele, nick, e-mail, heslo, které se pˇri vloˇzen´ı ˇsifruje, datum registrace, potvrzovac´ı ˇc´ıslo a u ´daj, jestli uˇzivatel potvrdil registraci.

Tabulka slozky Tabulka slozky obsahuje názvy sloˇzek, do kter´ ych m˚ uˇzeme pˇridávat u ´lohy. Kaˇzdá sloˇzka obsahuje id sloˇzky, ˇc´ıslo rodiˇce, název sloˇzky, ˇc´ıslo, které udává, jestli sloˇzka byla vymazána, datum vymazán´ı a ˇc´ıslo uˇzivatele, kter´ y sloˇzku vymazal. Tabulka mus´ı obsahovat jednu sloˇzku, která je hlavn´ı. Tato sloˇzka má hodnotu rodiˇce null, která znamená, ˇze ˇzádného rodiˇce nemá.

Tabulka ulohy Vˇsechny u ´lohy se ukládaj´ı do tabulky ulohy. Tato tabulka obsahuje vˇsechny informace a data o u ´loze. Kaˇzdá u ´loha má id, ˇc´ıslo rodiˇce, kter´ y ukazuje, do které sloˇzky daná u ´loha patˇr´ı a název u ´lohy, ˇc´ıslo, které udává, jestli u ´loha byla vymazána, datum vymazán´ı a ˇc´ıslo uˇzivatele, kter´ yu ´lohu vymazal. Dále jsou uloˇzeny tˇri soubory s jejich názvy. V tˇechto tˇrech souborech je uloˇzené zadán´ı, ˇreˇsen´ı a zdrojov´ y kód, které dané zadán´ı ˇreˇs´ı. Jako posledn´ı informace v tabulce je uvedena informace o tom, v jakém programovac´ım jazyce byl problém vyˇreˇsen.

3.4.2

Server

Server vyuˇz´ıvá tˇr´ıvrstvou architekturu. Prezenˇcn´ı vrstva je dˇelaná pomoc´ı textového uˇzivatelského rozhran´ı. Aplikaˇcn´ı vrstva se stará o pˇripojen´ı klienta a zpracován´ı poˇzadavk˚ u od klienta. Datová vrstva obsahuje tˇr´ıdy pro odeslán´ı e-mailu a tˇr´ıdy pro spolupráci s databáz´ı. Datová vrstva také obsahuje tˇr´ıdy, které se odes´ılaj´ı mezi serverem a klientem. 29



Pouˇ zit´ e extern´ı knihovny Aplikace vyuˇz´ıvá dvˇe extern´ı knihovny: • JavaMail - Slouˇz´ı pro pˇripojen´ı k smtp serveru a odeslán´ı e-mailu, • MySQL Connectors - Pouˇz´ıvá se pro pˇripojen´ı k MySQL databázi a práci sn´ı. Tyto knihovny se staraj´ı o pˇripojen´ı databáze a práci sn´ı a pro pˇripojeni k smtp serveru a odeslán´ı e-mailu.

Konfiguraˇ cn´ı soubor Konfiguraˇcn´ı soubor se mus´ı jmenovat config.properties. Tento soubor mus´ı obsahovat u ´daje o pˇripojen´ı k smtp serveru, které boudou pouˇzity pro odeslán´ı potvrzovac´ıho e-mailu, a pˇrihlaˇsovac´ı u ´daje do databáze, která bude slouˇzit pro ukládán´ı dat. Dále mus´ı byt uveden port, na kterém aplikace bude naslouchat. Konfiguraˇcn´ı soubor obsahuje na kaˇzdé ˇra´dce jednu informaci. Informace je uloˇzena ve formátu promˇenná = hodnota. Vˇsechny promˇenné aˇz na promˇennou domena jsou povinné. Pokud u promˇenné domena, je potˇreba nastavit v´ıce e-mail˚ u, jsou oddˇelené ˇca´rkou. Promˇenné, které se mus´ı nastavit aˇz na promˇennou domena jsou: • smtp server - adrese smtp serveru, • smtp ucet - u ´ˇcet na smtp serveru, • smtp heslo - heslo k u ´ˇctu na smtp serveru, • databaze url - url adresa databáze, • databaze uzivatel - jméno uˇzivatele v databázi, • databaze heslo - heslo uˇzivatele v databázi, • port - ˇc´ıslo portu na kterém aplikace bude naslouchat, • domena - doména, kterou mus´ı e-mail obsahovat (nepovinné). 30



Tˇ r´ıda Hlavni Hlavn´ı tˇr´ıda obsahuje statickou metodu main, která se volá pˇri spuˇstˇen´ı aplikace. Tato tˇr´ıda nepatˇr´ı do ˇzádné vrstvy. Tˇr´ıda se stará o naˇcten´ı konfiguraˇcn´ıho souboru, kde se nacházej´ı u ´daje o smtp serveru, databázi a portu, na kterém má aplikace naslouchat. Pokud jsou u ´daje z konfiguraˇcn´ıho souboru správnˇe naˇctené, vytváˇrej´ı se dvˇe instance PotvrzovaciMail a PripojeniMySQL. Následnˇe se vytváˇr´ı ServerSocet, kter´ y v nekoneˇcné smyˇcce bude ˇcekat na pˇripojen´ı klienta. Pokud je klient pˇripojen, vytvoˇr´ı se nové vlákno pomoc´ı instance VlaknoUzivatel.

Tˇ r´ıda VlaknoUzivatel (Aplikaˇ cn´ı vrstva) Je to jediná tˇr´ıda, která patˇr´ı do aplikaˇcn´ı vrstvy. Tˇr´ıda se stará o zpracován´ı dotaz˚ u od klienta a odeslán´ı odpovˇed´ı. Tˇr´ıda obsahuje metody pro zpracován´ı pˇr´ıkazu od nepˇrihláˇseného tak i pˇrihláˇseného uˇzivatele. Dále zde také najdeme metodu, která se stará o vygenerován´ı potvrzovac´ıho ˇc´ısla.

Tˇ r´ıda PrispevekDiskuze (Datov´ a vrstva) Tˇr´ıda obsahuje informace o jednom pˇr´ıspˇevku v diskuzi, kde jsou veˇrejné atributy o id pˇr´ıspˇevku, id rodiˇce, kdo pˇr´ıspˇevek napsal, text, datum vloˇzen´ı a id u ´lohy, kterému pˇr´ıspˇevek patˇr´ı.

Tˇ r´ıda Slozka (Datov´ a vrstva) Tato tˇr´ıda obsahuje informace o jedné sloˇzce, kde jsou veˇrejné atributy, které obsahuj´ı id sloˇzky, id rodiˇce a název sloˇzky.

Tˇ r´ıda UlohyObsah (Datov´ a vrstva) Tˇr´ıda slouˇz´ı pro uchováván´ı základn´ıch u ´daj˚ u o u ´loze v atributech, které ´ jsou veˇrejné. Udaje o u ´loze jsou id u ´lohy, id rodiˇce a název u ´lohy. Tato tˇr´ıda neobsahuje soubory k u ´loze.

31



Tˇ r´ıda Uloha (Datov´ a vrstva) Datová tˇr´ıda obsahuje vˇsechny u ´daje o jedné u ´loze. Uchovává svoje id a id rodiˇce. Dále tˇr´ıda uchovává název u ´lohy s názvy soubor˚ u. Tˇr´ıda obsahuje soubory se zadán´ım, ˇreˇsen´ım a se zdrojov´ ym kódem.

Tˇ r´ıda Obsah (Datov´ a vrstva) Tˇr´ıda slouˇz´ı pro uchován´ı vˇsech sloˇzek a u ´loh, které obsahuje aplikace. Tˇr´ıda obsahuje ArrayList instanc´ı tˇr´ıdy Slozek a ArrayList instanc´ı tˇr´ıdy Uloh.

Tˇ r´ıda Potvrzovac´ıMail (Datov´ a vrstva) Tˇr´ıda slouˇz´ı k odeslán´ı potvrzovac´ıho e-mailu uˇzivateli pˇri registraci. Pˇri vytvoˇren´ı instance je potˇreba zadat u ´daje pro vytvoˇren´ı spojen´ı se smtp serverem. Pro odeslán´ı potvrzovac´ıho e-mailu má tˇr´ıda metodu odesliPotvrzovaciMail, kde je nutné zadat jako parametr e-mail pˇr´ıjemce a potvrzovac´ı ˇc´ıslo.

Tˇ r´ıda Prikaz (Datov´ a vrstva) Tˇr´ıda Prikaz patˇr´ı do datové vrstvy a slouˇz´ı pro komunikaci mezi serverem a klientem, obsahuje statické ˇc´ıselné konstanty vˇsech pˇr´ıkaz˚ u, které se mohou v aplikaci pouˇz´ıt. Pˇri odes´ılán´ı tˇr´ıdy je potˇreba nastavit ˇc´ıslo pˇr´ıkazu. Pokud pˇr´ıkaz obsahuje data, jsou uloˇzena ve tˇr´ıdˇe jako atribut instance Object.

Tˇ r´ıda PripojeniMySQL (Datov´ a vrstva) Tˇr´ıda se stará o pˇripojen´ı a práci s databáz´ı MySQL. Pˇri vytvoˇren´ı instance je vytvoˇrené spojen´ı mezi aplikac´ı a databáz´ı MySQL. Tˇr´ıda obsahuje spoustu metod pro z´ıskávan´ı a u ´pravu dat v databázi. Posledn´ı metodou ve tˇr´ıdˇe je ukonˇcen´ı spojen´ı s databáz´ı.

32



Tˇ r´ıda PripojeniTCP (Datov´ a vrstva) Tˇr´ıda VlaknoSpojeniTCP vytváˇr´ı TCP spojen´ı mezi klientem a servem. Obsahuje metody pro pˇr´ıjem pˇr´ıkazu od klienta a odeslán´ı odpovˇedi.

Tˇ r´ıda Konzole (Prezenˇ cn´ı vrstva) Tˇr´ıda vytváˇr´ı textové uˇzivatelské rozhran´ı, které slouˇz´ı pro komunikaci s uˇzivatelem pomoc´ı pˇr´ıkaz˚ u.

3.4.3

Klient

Klientská ˇcást má tˇr´ıvrstvou architekturu. Pro komunikaci s uˇzivatelem je vyuˇzito grafické uˇzivatelské rozhran´ı.

Konfiguraˇ cn´ı soubor Konfiguraˇcn´ı soubor se mus´ı jmenovat config.properties a mus´ı obsahovat u ´daje o adrese serveru, kde bˇeˇz´ı serverová ˇca´st aplikace, a portu na kterém tento server naslouchá. Konfiguraˇcn´ı soubor obsahuje na kaˇzdé ˇra´dce jednu informaci. Informace je uloˇzena ve formátu promˇenná = hodnota. Promˇenné, které mus´ıme nastavit jsou: • ip - adresa serveru, • port - ˇc´ıslo portu na kterém naslouchá server.

Pouˇ zit´ e extern´ı knihovny Aplikace vyuˇz´ıvá ˇctyˇri extern´ı knihovny: • Apache PDFBox - tisknut´ı PDF souboru, 33



• Java Syntax Highlighter - zobrazen´ı syntaxe u zdrojového kódu, • Pdf-renderer - zobrazen´ı a manipulaci s PDF souborem, • datove-tridy - knihovna obsahuj´ıc´ı datové tˇr´ıdy pro komunikaci se serverem. Tyto knihovny se staraj´ı o zobrazen´ı PDF souboru, zv´ yraznˇen´ı syntaxe ve zdrojovém kódu a tisk PDF souboru.

Tˇ r´ıda Hlavni Hlavn´ı tˇr´ıda aplikace obsahuje statickou metodu main volaj´ıc´ı pˇri spuˇstˇen´ı aplikace. Po spuˇstˇen´ı aplikace se naˇcte z konfiguraˇcn´ıho souboru adresa serveru a port, na kterém server naslouchá. Po u ´spˇeˇsném naˇcten´ı se vytváˇr´ı instance PripojeniTCP, která se poté dává jako parametr pˇri vytváˇren´ı instance Uzivatel.

Tˇ r´ıda Uzivatel (Aplikaˇ cn´ı vrstva) Tato tˇr´ıda se stará o zpracován´ı dotaz˚ u, které se odes´ılaj´ı na server a které pˇriˇsly ze serveru. Tˇr´ıda také obsahuje mnoho metod, které se volaj´ı pˇri události v GUI.

Tˇ r´ıda Filter (Aplikaˇ cn´ı vrstva) Tˇr´ıda Filter se stará o to, aby instance tˇr´ıdy JFileChooser, která tento filtr pouˇz´ıvá, mohla vybrat pouze z PDF soubor˚ u.

Tˇ r´ıda PripojeniTCP (Datov´ a vrstva) Tˇr´ıda z datové vrstvy vytváˇr´ı spojen´ı mezi klientem a servem. Tˇr´ıda funguje jako vydavatel. Pro pˇr´ıjem dat je pouˇzita tˇr´ıda ObjectInputStream, pokud data pˇrijdou, je na to upozornˇen pˇredplatitel, kterému se data pˇredaj´ı. Pro odeslán´ı dat je vytvoˇrena metoda odesliData, která vyuˇz´ıvá tˇr´ıdu ObjectOutputStream. 34



Tˇ r´ıda UlozeniDat (Datov´ a vrstva) Tˇr´ıda se stará o uloˇzen´ı dat do poˇc´ıtaˇce a jejich naˇcten´ı zpˇet. Tˇr´ıda obsahuje statické metody, které se proto vyuˇz´ıvaj´ı.

Tˇ r´ıda SouboryKUloham (Datov´ a vrstva) Tˇr´ıda obsahuje tˇri File promˇenné: • zadani, • zdrojak, • reseni. Ty odkazuj´ı na soubory, které slouˇz´ı pro zobrazen´ı jedné u ´lohy.

Tˇ r´ıda HlavniOkno (Prezenˇ cn´ı vrstva) Hlavn´ı tˇr´ıda prezenˇcn´ı vrstvy se stará o zobrazen´ı hlavn´ıho okna aplikace. Okno aplikace obsahuje strom s obsahem, panel se záloˇzkami, které zobrazuj´ı ´ vybranou u ´lohu a diskuzi k n´ı. Ulohu lze vybrat pomoc´ı stromu. Pro zobrazen´ı v syntaxe u zdrojového kódu tˇr´ıda vyuˇz´ıvá knihovnu Java Syntax Highlighter.

Tˇ r´ıda DiskuzePanel (Prezenˇ cn´ı vrstva) Tˇr´ıda vytváˇr´ı panel, kter´ y zobrazuje diskuzi k vybrané u ´loze. Tento panel vyuˇz´ıvá tˇr´ıda HlavniOkno.

Tˇ r´ıda MujRendererStrom (Prezenˇ cn´ı vrstva) Tˇr´ıda dˇed´ı od tˇr´ıdy DefaultTreeCellRenderer a upravuje zobrazen´ı ikon instance JTree, která danou tˇr´ıdu vyuˇz´ıvá.

35



Tˇ r´ıda ZobrazeniPdfPanel (Prezenˇ cn´ı vrstva) Prezenˇcn´ı tˇr´ıda staraj´ıc´ı se o zobrazen´ı PDF souboru v JPanelu. Tˇr´ıda vyuˇz´ıvá knihovnu Pdf-renderer. Tato tˇr´ıda také implementuje metody pro práci s PDF jako je napˇr´ıklad pˇresun na dalˇs´ı stránku nebo nastaven´ı PDF souboru.

Tˇ r´ıda PotvrzeniOkno (Prezenˇ cn´ı vrstva) Tˇr´ıda zobrazuje okno, které slouˇz´ı pro zadán´ı potvrzovac´ıho ˇc´ısla od uˇzivatele.

Tˇ r´ıda PresunouDialog (Prezenˇ cn´ı vrstva) Tˇr´ıda vytváˇr´ı dialog, kde uˇzivatel m˚ uˇze pˇresunout u ´lohu nebo sloˇzku ve stromˇe na jinou pozici.

Tˇ r´ıda PrihlaseniOkno (Prezenˇ cn´ı vrstva) Tato tˇr´ıda vytváˇr´ı okno, kde je moˇzné zadat u ´daje od uˇzivatele pro pˇrihláˇsen´ı do aplikace. Okno má také odkazy na registraci a spuˇstˇen´ı aplikace offline.

Tˇ r´ıda RegistraceOkno (Prezenˇ cn´ı vrstva) Tˇr´ıda vytváˇr´ı okna, které slouˇz´ı pro zadán´ı u ´daj˚ u od uˇzivatele pro registraci do aplikace.

Tˇ r´ıda StromPanel (Prezenˇ cn´ı vrstva) Tˇr´ıda Strom dˇed´ı od tˇr´ıdy JTree a slouˇz´ı pro vytvoˇren´ı stromu s obsahem aplikace. Tˇr´ıda obsahuje mnoho metod, které nastavuj´ı chován´ı stromu.

36



Tˇ r´ıda TiskDialog (Prezenˇ cn´ı vrstva) Tˇr´ıda zobrazuje dialog, kde si uˇzivatel m˚ uˇze vybrat, zda si chce vytisknout zadán´ı u ´lohy, popis ˇreˇsen´ı u ´lohy nebo zdrojov´ y kód, kter´ y ˇreˇs´ı danou u ´lohu.

Tˇ r´ıda VlozeniUlohyDialog (Prezenˇ cn´ı vrstva) Tˇr´ıda vytváˇr´ı dialog, kter´ y se stará o vloˇzen´ı u ´daj˚ u, které jsou potˇreba pro vytvoˇrené nové u ´lohy.

Tˇ r´ıda UpravaUlohyDialog (Prezenˇ cn´ı vrstva) Tˇr´ıda vytváˇr´ı dialog, kter´ y se stará o u ´pravu u ´daj˚ u, které jsou uloˇzeny u u ´lohy.

Tˇ r´ıda VlozitPrispevekDialog (Prezenˇ cn´ı vrstva) Tˇr´ıda vytváˇr´ı dialog pro vloˇzen´ı pˇr´ıspˇevku do diskuze k u ´lohám.

Tˇ r´ıda VlozitSlozkuDialog (Prezenˇ cn´ı vrstva) Tˇr´ıda vytváˇr´ı dialog, pro vytvoˇren´ı nové sloˇzky v aplikaci.

Tˇ r´ıda ZdrojovyKodPanel (Prezenˇ cn´ı vrstva) Tˇr´ıda se stará o zobrazen´ı zdrojového kódu a zobrazen´ı syntaxe. Tato tˇr´ıda také obsahuje metody pro v´ ymˇenu zdrojového kódu. Tˇr´ıdu vyuˇz´ıvá tˇr´ıda HlavniOkno.

37

4 Závˇer V prvn´ı kapitole mé bakaláˇrské práce jsem se zab´ yval programovac´ı soutˇeˇz´ı PilsProg a veˇrejn´ ym validaˇcn´ım serverem UVa Online Judge, kter´ y jsem následnˇe pouˇzil jako zdroj pro v´ ybˇer a vytvoˇren´ı sady u ´loh. Pˇri vytváˇren´ı sady u ´loh jsem si procviˇcil své programátorské schopnosti z hlediska vyˇreˇsen´ı problému v co nejlepˇs´ım ˇcase. Pˇri tˇechto u ´lohách jsem pouˇzil programátorské strategie, které jsem se nauˇcil ve ˇskole, jako je napˇr´ıklad rekurzivn´ı programovan´ı nebo dynamické programován´ı. Pˇri u ´lohách jsem si také vyzkouˇsel, ˇze u ´lohy jsou obvykle nastavené tak, aby se nedaly vyˇreˇsit pomoc´ı hrubé s´ıly. Vˇsech tˇriadvacet u ´loh, které jsem vyˇreˇsil, m˚ uˇzete naj´ıt na pˇriloˇzeném CD. Na tomto CD naleznete origináln´ı a pˇreloˇzené zadán´ı do ˇceˇstiny. U kaˇzdé u ´lohy je také popis moˇzného zp˚ usobu ˇreˇsen´ı se zdrojov´ ym kódem. Vˇsechny u ´lohy jsou na pˇriloˇzeném CD rozdˇeleny do tˇr´ı sloˇzek Lehké, Stˇrednˇe obt´ıˇzné a Obt´ıˇzné, podle obt´ıˇznosti ˇreˇsen´ı. Ke kaˇzdé u ´loze byly také vytvoˇreny vstupy a v´ ystupy, které taktéˇz naleznete na pˇriloˇzeném CD. V druhé kapitole jsem se zamˇeˇril na vytvoˇren´ı aplikace, kam by uˇzivatelé mohli shromaˇzd’ovat a sd´ılet vyˇreˇsené u ´lohy s popisem, s jak´ ym algoritmem danou u ´lohu vyˇreˇsili. Ke kaˇzdé u ´loze je také diskuze, kde by uˇzivatelé mohli diskutovat o dané u ´loze. Aplikace dokáˇze fungovat ve dvou reˇzimech. Online, kdy aplikace je pˇripojena na server a offline, kdy aplikace dokáˇze fungovat bez toho, ˇze by byla pˇripojena na server. Online reˇzimu aplikace m˚ uˇze provádˇet vˇsechny operace jako je napˇr´ıklad vloˇzen´ı nové u ´lohy, vloˇzen´ı pˇr´ıspˇevku, uloˇzen´ı u ´lohy atd.. Offline reˇzimu m˚ uˇzeme pouze procházet a prohl´ıˇzet si u ´lohy, které jsme si v online reˇzimu uloˇzili a tisknout jejich ˇcásti. Pro naprogramován´ı aplikace jsem pouˇzil platformu Java s programovac´ım jazykem Java. Pˇri vytváˇren´ı aplikace jsem z´ıskal zkuˇsenosti, jak naprogramovat aplikace, které mezi sebou komunikuj´ı pomoc´ı poˇc´ıtaˇcov´ı s´ıtˇe. Protoˇze vˇsechna data jsem si ukládal do databáze MySQL, procviˇcil jsem si také práci s n´ı a s t´ım, jak k dat˚ um pˇristupovat z Javy. Pro naprogramován´ı této aplikace jsem také vyuˇzil extern´ı knihovny, které jsem vyhledával na internetu a s jejichˇz funkc´ı a pouˇzit´ı jsem se poté seznamoval. Jako posledn´ı jsem pouˇzil aplikaci Apache Ant pro sestaven´ı aplikace. Pˇri vytváˇren´ı bakaláˇrské práce jsem se nauˇcil mnoho nov´ ych vˇec´ı, které, 38

Závˇer

vˇeˇr´ım, vyuˇziji v navazuj´ıc´ım studiu a následnˇe ve své budouc´ı programátorské práci.

39

Seznam zkratek UVa - University of Valladolid ACM - Association for Computing Machinery ACM-ICPC - ACM International Collegiate Programming Contest PDF - Portable Document Format JDK - Java Development Kit JVM - Java virtual machine API - Application Programming Interface Java SE - Java Platform, Standard Edition Java ME - Java Platform, Enterprise Edition Java EE - Java Platform, Micro Edition DML - Data Manipulation Language DDL - Data Definition Language DCL - Data Control Language SMTP - Simple Mail Transfer Protocol GUI - Graphical User Interface

40

Literatura [1] Programátorská soutˇeˇz PilsProg URL: [citováno: 4.5.2014] [2] Validátor UVa Online Judge URL: [citováno: 4.5.2014] [3] Steven S. Skiena, Miguel A. Revilla. Programming Challenges. URL: [citováno: 4.5.2014] [4] Doc. Ing. Pavel Herout, Ph.D. Uˇcebnice jazyka Java. 2007. ISBN 978-80-7232-323-4 [5] Diskuze k UVa Online Judge validátoru URL: [citováno: 4.5.2014] [6] Robert Sedgewick a Kevin Wayne Algorithms (4th Edition). 2011. ISBN 978-0-321-57351-3

41

Pˇ r´ılohy Seznam pˇ r´ıloh Schéma 1 ERA model databáze Uˇzivatelská pˇr´ıruˇcka

42

Schéma 1 ERA model databáze

43

Uˇ zivatelsk´ a pˇ r´ıruˇ cka

44

Pro pˇreloˇzen´ı a bˇeh obou aplikac´ı je nutné m´ıt nainstalovan´ y JDK 1.7 nebo vyˇsˇs´ı.

Server Pˇ reloˇ zen´ı Aplikace se pˇreloˇz´ı pomoc´ı pˇr´ıkazu ant, ve sloˇzce server. T´ımto pˇr´ıkazem vznikne spustiteln´ y soubor ACM u ´loˇziˇstˇe - server.jar.

Pˇ red spuˇ stˇ en´ım Pˇred spuˇstˇen´ım aplikace je nutné nastavit konfiguraˇcn´ı soubor, kter´ y se mus´ı jmenovat config.properties a mus´ı b´ yt ve stejné sloˇzce jako ACM u ´loˇziˇstˇe server.jar. Konfiguraˇcn´ı soubor obsahuje na kaˇzdé ˇra´dce jednu informaci. Informace je uloˇzena ve formátu promˇenná = hodnota (viz Obrázek 1). Vˇsechny promˇenné aˇz na promˇennou domena je nutné nastavit. Pokud se promˇenná domena nenastav´ı, jsou povoleny pro registraci vˇsechny e-maily. Pokud je potˇreba u promˇenné domena nastavit v´ıce e-mail˚ u, jsou oddˇelené ˇca´rkou. • smtp server - adrese smtp serveru, • smtp ucet - u ´ˇcet na smtp serveru, • smtp heslo - heslo k u ´ˇctu na smtp serveru, • databaze url - url adresa databáze, • databaze uzivatel - jméno uˇzivatele v databázi, • databaze heslo - heslo uˇzivatele v databázi, • port - ˇc´ıslo portu, na kterém aplikace bude naslouchat, • domena - doména, kterou mus´ı e-mail obsahovat pˇri registraci.

45

Obrázek 1: Konfiguraˇcn´ı soubor Spuˇ stˇ en´ı Spuˇstˇen´ı prob´ıhá pomoc´ı pˇr´ıkazu java -jar ’ACM u ´loˇziˇstˇe - server.jar’. Poté je moˇzno zadat dva pˇr´ıkazy. Pˇr´ıkaz vytvor databazi, vytvoˇr´ı novou databázi a pˇr´ıkaz konec, slouˇz´ı pro ukonˇcen´ı aplikace.

Klient Aplikace se pˇreloˇz´ı pomoc´ı pˇr´ıkazu ant, ve sloˇzce klient. T´ımto pˇr´ıkazem vznikne spustiteln´ y soubor ACM u ´loˇziˇstˇe - klient.jar.

Pˇ red spuˇ stˇ en´ım Pˇred spuˇstˇen´ım aplikace je nutné nastavit konfiguraˇcn´ı soubor, kter´ y se mus´ı jmenovat config.properties a mus´ı b´ yt ve stejné sloˇzce jako ACM u ´loˇziˇstˇe klient.jar. Konfiguraˇcn´ı soubor obsahuje na kaˇzdé ˇra´dce jednu informaci. Informace je uloˇzena ve formátu promˇenná = hodnota. Promˇenné, které mus´ıme nastavit jsou: • ip - adresa serveru,

46

• port - ˇc´ıslo portu na kterém naslouchá server.

Spuˇ stˇ en´ı Spuˇstˇen´ı aplikace prob´ıhá pomoc´ı pˇr´ıkazu java -jar ’ACM u ´loˇziˇstˇe - klient.jar’ nebo spuˇstˇen´ı souboru ACM u ´loˇziˇstˇe - klient.jar.

Pˇ rihlaˇ sovac´ı okno a registrace Po spuˇstˇen´ı aplikace se nám spust´ı okno pro pˇrihláˇsen´ı (viz Obrázek 2). V oknˇe m˚ uˇzeme vyplnit e-mail s heslem a t´ım se pˇrihlásit do aplikace, která funguje online. To znamená, ˇze je pˇripojena na server. Pokud uˇzivatel nemá pˇrihlaˇsovac´ı u ´daje, je nejdˇr´ıve potˇreba se zaregistrovat. Do registrace se dostaneme kliknut´ım na odkaz registrovat. Po kliknut´ı na odkaz registrovat se nám spust´ı okno (viz Obrázek 3), kde je nutné vyplnit e-mail, kter´ y mus´ı m´ıt doménu, která je urˇcena serverem, a heslo, které mus´ı b´ yt delˇs´ı jak 5 znak˚ u. Tyto informace m˚ uˇzeme také zjistit, kdyˇz najedeme myˇs´ı na otazn´ık. Po registraci pˇrijde uˇzivateli e-mail s ˇc´ıslem, které je potˇreba zadat pˇri vyˇzádán´ı. Zadán´ı ˇc´ısla se mus´ı provést do 24 hodin, nebo se bude muset znova provést registrace. Poté je moˇzné se do aplikace pˇrihlásit. Na oknˇe pro pˇrihláˇsen´ı m˚ uˇzeme také kliknout na odkaz Bez pˇrihláˇsen´ı, která spust´ı aplikaci v offline reˇzimu. To znamená, bez pˇripojen´ı na server.

Obrázek 2: Okno pro pˇrihláˇsen´ı

47

Obrázek 3: Okno pro registraci Hlavn´ı okno s pˇ rihl´ aˇ sen´ım Hlavn´ı okno aplikace je rozdˇeleno na tˇri ˇca´sti (viz Obrázek 4). V pravé ˇcásti aplikace je strom, kter´ y obsahuje sloˇzky a názvy u ´loh. Pravá strana je rozdˇeˇ sen´ı a lena vodorovnˇe na dvˇe ˇca´sti. Horn´ı ˇca´st má tˇri záloˇzky a to Zadán´ı, Reˇ Zdrojový kód, kde se zobrazuj´ı ˇca´sti u ´lohy. V doln´ı ˇca´sti se zobrazuje diskuze k této u ´loze. Ve stromˇe lze vybrat u ´lohu pomoc´ı toho, ˇze na n´ı klikneme lev´ ym tlaˇc´ıtkem myˇsi. Po kliknut´ı prav´ ym tlaˇc´ıtkem myˇsi na sloˇzku nebo u ´lohu se zobraz´ı menu. U sloˇzky lze vybrat, jestli danou sloˇzku chceme pˇrejmenovat, odstranit nebo do n´ı vloˇzit novou sloˇzku ˇci novou u ´lohu. U u ´lohy m˚ uˇzeme vybrat, jestli chceme danou u ´lohu pˇrejmenovat, upravit nebo odstranit. U u ´lohy m˚ uˇzeme také vybrat, ˇze danou u ´lohu chceme vytisknou. Po kliknut´ı na tisk je poté potˇreba vybrat, jakou ˇcást u ´lohy se má vytisknout. U kaˇzdé u ´lohy, m˚ uˇzeme pˇridávat nov´ y pˇr´ıspˇevek pomoc´ı tlaˇc´ıtka Vloˇz pˇr´ıspˇevek nebo reagovat na pˇr´ıspˇevek jiného uˇzivatele tak, ˇze klikneme u jeho e-mailu na odkaz reagovat. Pˇri vloˇzen´ı nového pˇr´ıspˇevku nebo reakci na pˇr´ıspˇevek se zobraz´ı dialog, kam dan´ y pˇr´ıspˇevek nap´ıˇseme. Hlavn´ı okno má také v doln´ım pravém rohu napsáno, jestli daná u ´loha je uloˇzena nebo ne. Pˇred t´ımto popisem je znak + nebo -, pˇri jehoˇz kliknut´ı uloˇz´ıme nebo odstran´ıme danou u ´lohu.

48

Obrázek 4: Hlavn´ı okno aplikace s vybranou u ´lohou Hlavn´ı okno bez pˇ rihl´ aˇ sen´ı Hlavn´ı okno v reˇzimu offline vypadá stejnˇe jako v reˇzimu online. Je omezena pouze jeho funkˇcnost, kdy lze pouze prohl´ıˇzet u ´lohy, které jsme si v online reˇzimu uloˇzili. V tomto reˇzimu nelze upravovat ˇzádná data, pouze prohl´ıˇzet a tisknout ˇcásti u ´loh.

49

Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. Sada úloh pro PilsProg a softwarová aplikace pro

Recommend Documents