Katedra 
informatiky 
P·r¶3rodov·edeck¶a 
fakulta 
Univerzita 
Palack¶eho 
T·r¶3da 
17. 
listopadu 
12 
771 
46 
Olomouc 


POSUDEK 


¶´ 


BAKAL 
RSK´ 
ACE

A·EPR 


N¶azev 
bakal¶a·rsk¶e 
pr¶ace: 
Softwarov¶a 
podpora 
v¶yuky 
grafov¶ych 
algoritmou 
Diplomant: 
Martin 
Spurn¶y 
Autor 
posudku: 
RNDr. 
Miroslav 
Kola·r¶3k, 
Ph.D. 
(oponent 
pr¶ace) 


Posudek: 


C¶3lem 
bakal¶a·rsk¶e 
pr¶ace 
bylo 
vytvo·rit 
v¶yukovou 
gra—ckou 
aplikaci 
pro 
demonstraci 
z¶akladn¶3ch 
pojmou 
a 
algoritmou 
z 
teorie 
grafou. 
Textov¶a 
·ast 
je 
rozd·r¶c¶3: 
teoretick¶´


c¶elena 
do 
t·i 
·ast¶y 
uvod, 
popis 
charakteristiky 
aplikace 
a 
u·zivatelsk¶a 
p·r¶3ru·cka. 
Teoretick¶a 
·c¶ast 
byla 
v 
podstat·e 
cel¶a 
p·revzata 
odjinud, 
co·z 
diplomant 
·casto 
p·rizn¶av¶a 
ve 
v·et¶ach 
typu: 
N¶asleduj¶3c¶i 
kapitola, 
jej¶i 
texty 
a 
obr¶azky, 
byla 
p·revzata 
ze 


"

. 
. 
. 
\. 
L¶epe 
by 
na 
m·e 
pousobilo, 
kdyby 
si 
diplomant 
konkr¶etn¶i 
p·r¶3klady 
a 
obr¶azky 
vymyslel 
s¶am. 
V 
pr¶aci 
se 
vyskytuje 
velk¶e 
mno·zstv¶i 
chyb 
a 
p·reklepou. 
N¶asleduje 
seznam 
n·ekter¶ych 
z 
nich 
(do 
str. 
15): 


• 
str. 
3: 
je 
ps¶ano 
sesttra“ 
m¶3sto 
sestra\
""

• 
str. 
5: 
uspo·r¶adan¶a 
dvojice 
ps¶ana 
(U, 
H)i 
hU, 
Hi, 
tedy 
nejednotn·e 
(takt¶e·z 
na 
str. 
6) 
• 
str. 
6: 
v 
·c¶asti 
2.1.3 
je 
ps¶ano 
u, 
v 
. 
V 
m¶3sto 
u, 
v 
. 
U 
• 
str. 
6 
dole: 
·c¶ast 
textu 
V 
teorii 
grafou 
se 
pou·z¶3vaj¶i 
n¶asleduj¶3c¶i 
term¶3ny: 
Sou·cet 
stup·nou
"

v·sech 
uzlou 
v 
grafu 
je 
sud¶e 
·c¶3slo.“ 
je 
nesmysln¶a. 
V·ed·el 
by 
diplomant 
pro·c? 


• 
str. 
7: 
·c¶ast 
2.1.5. 
obsahuje 
logick¶e 
chyby. 
Zejm¶ena 
druh¶y 
odstavec 
ned¶av¶a 
voubec 
smysl! 
(Diplomant 
si 
zde 
nap·r. 
plete 
v·etu 
s 
de—nic¶3.) 
Jak 
je 
s 
touto 
·c¶ast¶i 
diplomant 
spokojen? 
• 
str. 
7 
dole: 
m¶3sto 
textu 
(na 
obr¶azku 
6.) 
jako 
Pograf“ 
. 
. 
. 
“ 
m¶a 
b¶yt 
(na 
obr¶azku 
5.) 
"” 
"

jako 
Podgraf“ 
. 
. 
. 
\; 
a 
je·st·e 
jednou 
n¶3·ze 
vypadlo 
ve 
slov·e 
pograf“ 
p¶3smeno 
d 


” 
"

• 
str. 
8: 
je 
pou·zit 
pojem 
cesta\, 
kter¶y 
je 
de—nov¶an 
a·z 
na 
str. 
9 
"

• 
str. 
9: 
·c¶ast 
2.2.1. 
je 
kostrbat¶a 
a 
p·r¶3sn·e 
vzato 
i 
nep·resn¶a 
• 
str. 
9: 
v 
·c¶asti 
2.2.3 
je 
pou·zit 
pojem 
vnit·rn¶i 
uzel\, 
kter¶y 
nen¶i 
v 
textu 
de—nov¶an
"

• 
str. 
9: 
ve 
t·ret¶3m 
·r¶adku 
zdola 
je 
t·rikr¶at 
chybn·e 
uvedeno 
p¶3smeno 
E 
(m¶a 
b¶yt 
H) 
• 
str. 
10: 
·c¶ast 
2.2.5 
obsahuje 
(v 
souvisl¶em 
textu) 
z 
ni·ceho 
nic 
v·etu 
a 
doukaz. 
Diplomanta 
se 
pt¶am: 
Pro·c 
je 
v 
cel¶em 
textu 
(pr¶av·e 
v 
·c¶asti 
2.2.5) 
jedin¶y 
doukaz 
a 
jinde 
ne?“ 
"

• 
str. 
10: 
prvn¶i 
dva 
·r¶adky 
v 
·c¶asti 
2.2.6. 
vyu·z¶3vaj¶i 
nede—novan¶e 
pojmy 
pokr¶yt“ 
a 
Eu"
"

lerovsk¶y 
tah“ 


• 
str. 
10: 
v 
posledn¶3m 
·r¶adku 
je 
nav¶3c 
p¶3smeno 
a 
• 
str. 
13: 
na 
t·ret¶3m 
·r¶adku 
shora 
nen¶i 
vhodn¶e 
ps¶at 
ale\
"

!

• 
str. 
13: 
v 
·c¶asti 
3.2.2. 
je 
bez 
vysv·etlen¶i 
nov·e 
pou·zito 
zna·cen¶i 
!G 
• 
str. 
13: 
t·ret¶i 
·r¶adek 
zdola, 
ve 
slov·e 
neorintovan¶y“ 
vypadlo 
p¶3smeno 
e 
"


• 
str. 
14 
naho·re: 
je 
ps¶ano 
jej¶3“ 
m¶3sto 
jej¶3m\
""

• 
str. 
14: 
text 
na 
hlavn¶i 
diagon¶ale 
jsou 
nuly“ 
by 
bylo 
lep·s¶i 
napsat 
ve 
tvaru 
na 
hlavn¶3
” 
"

diagon¶ale 
jsou 
sam¶e 
nuly“ 


• 
str. 
14: 
v 
textu 
u 
posledn¶3ho 
punt¶3ku 
vypadlo 
slovo 
grafu\
"

• 
str. 
15: 
v 
obr¶azku 
jsou 
m¶3rn·e 
nekvalitn¶i 
ob·e 
matice; 
nav¶3c 
v 
matici 
S 
je 
chyba! 
V 
podobn¶em 
duchu 
bych 
(bohu·zel) 
mohl 
ve 
v¶y·ctu 
chyb 
pokra·covat. 
Zastav¶3m 
se 
ale 
u·z 
jen 
u 
dvou 
dal·s¶3ch: 


• 
str. 
21: 
v·eta 
Za 
efektivn¶i 
algoritmy 
se 
pova·zuj¶i 
takov¶e 
postupy, 
jejich·z 
slo·zitost 
je 
"

polynomi¶aln¶i 
(nap·r. 
n127, 
nikoliv 
exponenci¶aln¶i 
2n).“ 
se 
mi 
nel¶3b¶3. 
V·ed·el 
by 
diplomant 
pro·c? 


• 
str. 
36: 
text 
Tedy 
existuje 
zobrazen¶i 
w 
: 
H 
› 
R+, 
kde 
R+ 
ozna·cuje 
mno·zinu 
"

kladn¶ych 
koster 
grafu 
G“ 
je 
o·cividn·e 
nesmysln¶y. 


D¶ale 
je 
mnohokr¶at 
chybn·e 
ps¶an 
matematick¶y 
text 
jako 
b·e·zn¶y 
text, 
pom·ern·e 
·casto 
chyb¶i 
(nebo 
naopak 
p·reb¶yvaj¶3) 
·c¶arky 
v 
souv·et¶3ch 
a 
nezn·el¶e 
p·redlo·zky 
jsou 
ps¶any 
na 
konci 
·r¶adkou. 
Ob·cas 
nejsou 
spr¶avn·e 
pou·zity 
·cesk¶e 
uvozovky 
a 
vyskytuj¶i 
se 
chyby 
i 
p·ri 
psan¶i 
mal¶ych 
a 
velk¶ych 
p¶3smen. 
Aplikace 
mi 
·sla 
bez 
probl¶emou 
nainstalovat 
a 
spustit. 
Oce·nuji 
u 
n¶i 
zejm¶ena 
GUI 
a 
jednoduc
hou 
a 
promy·slenou 
ovladatelnost. 
Algoritmy 
funguj¶i 
spr¶avn·e 
a 
popis 
proub·ehu 
algoritmu 
je 
dobr¶y. 
Aplikace 
um¶i 
demonstrovat 
prouchod 
grafem 
do 
hloubky 
a 
do 
·s¶3·rky, 
hled¶an¶i 
minim¶aln¶i 
kostry 
(za·razovac¶3m 
a 
vy·razovac¶3m 
algoritmem), 
nalezen¶i 
nejkrat·s¶i 
cesty 
mezi 
dv·ema 
dan¶ymi 
uzly 
a 
nez¶avislost, 
dominanci 
a 
klikovost 
grafu. 
Bohu·zel 
dal·s¶i 
algoritmy 
z 
teorie 
grafou 
(kter¶e 
se 
u 
n¶as 
v 
bakal¶a·rsk¶ych 
oborech 
b·e·zn·e 
u·c¶3) 
v 
aplikaci 
nenajdeme, 
nap·r¶3klad: 
ur·cen¶i 
chromatick¶eho 
·c¶3sla, 
Dijkstrouv 
algoritmus, 
kreslen¶i 
grafu 
jedn¶3m 
tahem, 
nalezen¶i 
Hamiltonovsk¶e 
kru·znice, 
¶uloha 
obchodn¶3ho 
cestuj¶3c¶3ho, 
p¶arov¶an¶i 
a 
¶uloha 
·c¶3nsk¶eho 
po·st'¶aka. 
Jist·e 
by 
·sla 
demonstrovat 
i 
v·eta 
o 
sk¶ore 
grafu 
·ci 
nalezen¶i 
fundament¶aln¶3ho 
syst¶emu 
kru·znic. 
D¶ale 
n¶asleduje 
nesourod¶y 
v¶y·cet 
n·ekter¶ych 
nedostatkou, 
p·ripom¶3nek 
a 
ot¶azek: 


• 
Pokud 
n·ejak¶y 
algoritmus 
pracuje 
s 
heuristikou, 
m·elo 
by 
to 
b¶yt 
v 
aplikaci 
zm¶3n·eno. 
• 
P·ri 
zad¶av¶an¶i 
vlastnosti 
hrany 
se 
re¶aln¶e 
hodnoty 
p·revedou 
na 
celou 
·c¶ast 
(nap·r. 
8,7 
na 
8). 
Ohodnocen¶i 
hran 
je 
tak 
zbyte·cn·e 
omezeno 
pouze 
na 
p·rirozen¶a 
·c¶3sla. 
• 
K 
·cemu 
je 
dobr¶e 
de—novat 
hodnotu 
uzlou? 
• 
Pro·c 
je 
mo·zn¶e 
de—novat 
v¶3cen¶asobn¶e 
hrany? 
• 
Pro·c 
nen¶i 
mo·zn¶e 
tisknout 
(nap·r. 
graf 
a 
popis 
algoritmu)? 
• 
P·ri 
zm·en·e 
vlastnosti 
uzlu 
jsem 
po 
kliknut¶i 
na 
tla·c¶3tko 
OK“ 
obdr·zel 
zpr¶avu 
Jsem
” 
"

spr¶avn·e 
na 
vlastn¶3m.“ 
Co 
t¶3m 
cht·el 
autor 
·r¶3ci? 


• 
Po 
nastaven¶i 
zna·cen¶i 
uzlou 
na 
vlastn¶i 
popis 
mi 
ob·cas 
nebyla 
d¶ana 
mo·znost 
vlastn¶3ho 
popisu. 
• 
P·ri 
vy·cerp¶an¶i 
v·sech 
p¶3smen 
abecedy 
se 
vyp¶3·se 
upozorn·en¶i 
kon·c¶3c¶i 
nepravdivou 
v·etou 
Sou·casn¶y 
graf 
bude 
vymaz¶an\.
"

Pr¶aci 
doporu·cuji 
k 
obhajob·e 
a 
hodnot¶3m 
ji 
zn¶amkou 
dob·re. 


Ve 
Zl¶3n·e, 
27. 
srpna 
2010 


RNDr. 
Miroslav 
Kola·r¶3k, 
Ph.D.