Motivace
Obecn´ y princip
Pˇr´ıklady
Princip v´yˇskovnice Jan Pavl´ık FSI VUT v Brnˇ e
14.5.2010
Geografick´ a v´ yˇskovnice
Motivace
Obecn´ y princip
Osnova pˇredn´aˇsky
1
Motivace
2
Obecn´y princip
3
Pˇr´ıklady Svˇetov´e rekordy Turnajov´e uspoˇr´ ad´ an´ı Skupinov´e hodnocen´ı Rozhledny
4
Geografick´ a v´yˇskovnice Inverzn´ı v´yˇskovnice
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Motivace
Obecn´ y princip
Osnova pˇredn´aˇsky
1
Motivace
2
Obecn´y princip
3
Pˇr´ıklady Svˇetov´e rekordy Turnajov´e uspoˇr´ ad´ an´ı Skupinov´e hodnocen´ı Rozhledny
4
Geografick´ a v´yˇskovnice Inverzn´ı v´yˇskovnice
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Motivace
Obecn´ y princip
Osnova pˇredn´aˇsky
1
Motivace
2
Obecn´y princip
3
Pˇr´ıklady Svˇetov´e rekordy Turnajov´e uspoˇr´ ad´ an´ı Skupinov´e hodnocen´ı Rozhledny
4
Geografick´ a v´yˇskovnice Inverzn´ı v´yˇskovnice
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Motivace
Obecn´ y princip
Osnova pˇredn´aˇsky
1
Motivace
2
Obecn´y princip
3
Pˇr´ıklady Svˇetov´e rekordy Turnajov´e uspoˇr´ ad´ an´ı Skupinov´e hodnocen´ı Rozhledny
4
Geografick´ a v´yˇskovnice Inverzn´ı v´yˇskovnice
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Motivace N´ akup chleba V obchodˇe maj´ı nˇekolik druh˚ u chleba. Chceme nˇejak´y vybrat pouze na z´ akladˇe hmotnosti (ˇc´ım vˇetˇs´ı, t´ım lepˇs´ı) a ceny (ˇc´ım niˇzˇs´ı, t´ım lepˇs´ı). chleba α β γ δ ǫ ζ Kter´e chleby m´ a smysl uvaˇzovat?
kg 1 0.6 0.8 1.2 0.6 0.5
Kˇc 34 22 25 33 24 20
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Motivace N´ akup chleba V obchodˇe maj´ı nˇekolik druh˚ u chleba. Chceme nˇejak´y vybrat pouze na z´ akladˇe hmotnosti (ˇc´ım vˇetˇs´ı, t´ım lepˇs´ı) a ceny (ˇc´ım niˇzˇs´ı, t´ım lepˇs´ı). chleba α β γ δ ǫ ζ Kter´e chleby m´ a smysl uvaˇzovat?
kg 1 0.6 0.8 1.2 0.6 0.5
Kˇc 34 22 25 33 24 20
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Motivace N´ akup chleba V obchodˇe maj´ı nˇekolik druh˚ u chleba. Chceme nˇejak´y vybrat pouze na z´ akladˇe hmotnosti (ˇc´ım vˇetˇs´ı, t´ım lepˇs´ı) a ceny (ˇc´ım niˇzˇs´ı, t´ım lepˇs´ı). chleba α β γ δ ǫ ζ Kter´e chleby m´ a smysl uvaˇzovat?
kg 1 0.6 0.8 1.2 0.6 0.5
Kˇc 34 22 25 33 24 20
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
ˇ sen´ı Reˇ Staˇc´ı vyˇskrtat ty, kter´e jsou nˇekter´ym jin´ym chlebem pˇrebity v obou krit´eri´ıch. ”Pˇrebit´ı” ch´ apeme reflexivnˇe. chleba α β γ δ ǫ ζ
kg 1 0.6 0.8 1.2 0.6 0.5
Kˇc 34 22 25 33 24 20
X (pˇrebito poloˇzkou δ) X X X X (pˇrebito poloˇzkou β) X
V´ysledek Chleba vybereme z mnoˇziny V = {β, γ, δ, ζ}.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
ˇ sen´ı Reˇ Staˇc´ı vyˇskrtat ty, kter´e jsou nˇekter´ym jin´ym chlebem pˇrebity v obou krit´eri´ıch. ”Pˇrebit´ı” ch´ apeme reflexivnˇe. chleba α β γ δ ǫ ζ
kg 1 0.6 0.8 1.2 0.6 0.5
Kˇc 34 22 25 33 24 20
X (pˇrebito poloˇzkou δ) X X X X (pˇrebito poloˇzkou β) X
V´ysledek Chleba vybereme z mnoˇziny V = {β, γ, δ, ζ}.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
ˇ sen´ı Reˇ Staˇc´ı vyˇskrtat ty, kter´e jsou nˇekter´ym jin´ym chlebem pˇrebity v obou krit´eri´ıch. ”Pˇrebit´ı” ch´ apeme reflexivnˇe. chleba α β γ δ ǫ ζ
kg 1 0.6 0.8 1.2 0.6 0.5
Kˇc 34 22 25 33 24 20
X (pˇrebito poloˇzkou δ) X X X X (pˇrebito poloˇzkou β) X
V´ysledek Chleba vybereme z mnoˇziny V = {β, γ, δ, ζ}.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Na mnoˇzinˇe A vˇsech chleb˚ u definujeme bin´ arn´ı relace G a P: (x, y ) ∈ G ⇔ y je tˇeˇzˇs´ı neˇz x (x, y ) ∈ P ⇔ y je draˇzˇs´ı neˇz x Situaci zobraz´ıme graficky. Na mnoˇzinˇe A vytvoˇr´ıme orientovan´y / y ⇔ (x, y ) ∈ G , graf se dvˇema typy hran: x _ _ _ / y x ⇔ (x, y ) ∈ P. Prvky oznaˇcujeme dohromady s cena hodnotami xhmotnost . / 22 ζ 20 1Q_QQ_Q n_/ β0.6 1 1n QnnQnQnQ B || 0.5 | | n 1 1nn Q Q
Q Q B |||||n nnnnnn1111
Q QQQQQQQB |~ vn~||nnnnn 1
Q QBQ o_o vnn_ _ _ _ _1 11 _
_ _ _ _ Q_(! ( 24 33 δ1.2 hPBhP P ǫ
1 11 m mm|m 0.6 `BBPPBPPP P 1 BB B PPP P
1 111 mmmmmmm|||| m1 m BB P
| BBB PP
PPPmPPmmmPm1m1m }| |||| vm mmPP | } o_vm _ _ 25 α34 γ0.8 1 o
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Na mnoˇzinˇe A vˇsech chleb˚ u definujeme bin´ arn´ı relace G a P: (x, y ) ∈ G ⇔ y je tˇeˇzˇs´ı neˇz x (x, y ) ∈ P ⇔ y je draˇzˇs´ı neˇz x Situaci zobraz´ıme graficky. Na mnoˇzinˇe A vytvoˇr´ıme orientovan´y / y ⇔ (x, y ) ∈ G , graf se dvˇema typy hran: x _ _ _ / y x ⇔ (x, y ) ∈ P. Prvky oznaˇcujeme dohromady s cena hodnotami xhmotnost . / 22 ζ 20 1Q_QQ_Q n_/ β0.6 1 1n QnnQnQnQ B || 0.5 | | n 1 1nn Q Q
Q Q B |||||n nnnnnn1111
Q QQQQQQQB |~ vn~||nnnnn 1
Q QBQ o_o vnn_ _ _ _ _1 11 _
_ _ _ _ Q_(! ( 24 33 δ1.2 hPBhP P ǫ
1 11 m mm|m 0.6 `BBPPBPPP P 1 BB B PPP P
1 111 mmmmmmm|||| m1 m BB P
| BBB PP
PPPmPPmmmPm1m1m }| |||| vm mmPP | } o_vm _ _ 25 α34 γ0.8 1 o
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Na mnoˇzinˇe A vˇsech chleb˚ u definujeme bin´ arn´ı relace G a P: (x, y ) ∈ G ⇔ y je tˇeˇzˇs´ı neˇz x (x, y ) ∈ P ⇔ y je draˇzˇs´ı neˇz x Situaci zobraz´ıme graficky. Na mnoˇzinˇe A vytvoˇr´ıme orientovan´y / y ⇔ (x, y ) ∈ G , graf se dvˇema typy hran: x _ _ _ / y x ⇔ (x, y ) ∈ P. Prvky oznaˇcujeme dohromady s cena hodnotami xhmotnost . / 22 ζ 20 1Q_QQ_Q n_/ β0.6 1 1n QnnQnQnQ B || 0.5 | | n 1 1nn Q Q
Q Q B |||||n nnnnnn1111
Q QQQQQQQB |~ vn~||nnnnn 1
Q QBQ o_o vnn_ _ _ _ _1 11 _
_ _ _ _ Q_(! ( 24 33 δ1.2 hPBhP P ǫ
1 11 m mm|m 0.6 `BBPPBPPP P 1 BB B PPP P
1 111 mmmmmmm|||| m1 m BB P
| BBB PP
PPPmPPmmmPm1m1m }| |||| vm mmPP | } o_vm _ _ 25 α34 γ0.8 1 o
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Hledan´e prvky splˇ nuj´ı vlastnost, ˇze nejsou pˇrebity libovoln´ym z ostatn´ıch chleb˚ u v obou krit´eri´ıch. To m˚ uˇzeme vyj´ adˇrit n´ asledovnˇe: (x, y ) ∈ G ⇒ (x, y ) ∈ P x ∈ V ⇔ (∀y ∈ A) (y , x) ∈ P ⇒ (y , x) ∈ G Protoˇze vˇsak G i P jsou relace jsou asymetrick´e, tj. nenastane souˇcasnˇe napˇr. (x, y ) ∈ G a (y , x) ∈ G , situaci m˚ uˇzeme pˇrepsat na (x, y ) ∈ G ⇒ (y , x) ∈ G ∨ (x, y ) ∈ P x ∈ V ⇔ (∀y ∈ A) (y , x) ∈ P ⇒ (y , x) ∈ G ∨ (x, y ) ∈ P Zavedeme-li R = G ∪ P −1 , pak x ∈ V ⇔ (∀y ∈ A)((x, y ) ∈ R ⇒ (y , x) ∈ R).
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Hledan´e prvky splˇ nuj´ı vlastnost, ˇze nejsou pˇrebity libovoln´ym z ostatn´ıch chleb˚ u v obou krit´eri´ıch. To m˚ uˇzeme vyj´ adˇrit n´ asledovnˇe: (x, y ) ∈ G ⇒ (x, y ) ∈ P x ∈ V ⇔ (∀y ∈ A) (y , x) ∈ P ⇒ (y , x) ∈ G Protoˇze vˇsak G i P jsou relace jsou asymetrick´e, tj. nenastane souˇcasnˇe napˇr. (x, y ) ∈ G a (y , x) ∈ G , situaci m˚ uˇzeme pˇrepsat na (x, y ) ∈ G ⇒ (y , x) ∈ G ∨ (x, y ) ∈ P x ∈ V ⇔ (∀y ∈ A) (y , x) ∈ P ⇒ (y , x) ∈ G ∨ (x, y ) ∈ P Zavedeme-li R = G ∪ P −1 , pak x ∈ V ⇔ (∀y ∈ A)((x, y ) ∈ R ⇒ (y , x) ∈ R).
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Hledan´e prvky splˇ nuj´ı vlastnost, ˇze nejsou pˇrebity libovoln´ym z ostatn´ıch chleb˚ u v obou krit´eri´ıch. To m˚ uˇzeme vyj´ adˇrit n´ asledovnˇe: (x, y ) ∈ G ⇒ (x, y ) ∈ P x ∈ V ⇔ (∀y ∈ A) (y , x) ∈ P ⇒ (y , x) ∈ G Protoˇze vˇsak G i P jsou relace jsou asymetrick´e, tj. nenastane souˇcasnˇe napˇr. (x, y ) ∈ G a (y , x) ∈ G , situaci m˚ uˇzeme pˇrepsat na (x, y ) ∈ G ⇒ (y , x) ∈ G ∨ (x, y ) ∈ P x ∈ V ⇔ (∀y ∈ A) (y , x) ∈ P ⇒ (y , x) ∈ G ∨ (x, y ) ∈ P Zavedeme-li R = G ∪ P −1 , pak x ∈ V ⇔ (∀y ∈ A)((x, y ) ∈ R ⇒ (y , x) ∈ R).
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Hledan´e prvky splˇ nuj´ı vlastnost, ˇze nejsou pˇrebity libovoln´ym z ostatn´ıch chleb˚ u v obou krit´eri´ıch. To m˚ uˇzeme vyj´ adˇrit n´ asledovnˇe: (x, y ) ∈ G ⇒ (x, y ) ∈ P x ∈ V ⇔ (∀y ∈ A) (y , x) ∈ P ⇒ (y , x) ∈ G Protoˇze vˇsak G i P jsou relace jsou asymetrick´e, tj. nenastane souˇcasnˇe napˇr. (x, y ) ∈ G a (y , x) ∈ G , situaci m˚ uˇzeme pˇrepsat na (x, y ) ∈ G ⇒ (y , x) ∈ G ∨ (x, y ) ∈ P x ∈ V ⇔ (∀y ∈ A) (y , x) ∈ P ⇒ (y , x) ∈ G ∨ (x, y ) ∈ P Zavedeme-li R = G ∪ P −1 , pak x ∈ V ⇔ (∀y ∈ A)((x, y ) ∈ R ⇒ (y , x) ∈ R).
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Staˇc´ı vz´ıt graf pro relaci R (pˇrid´ ame otoˇcen´e pˇreruˇsovan´ych ˇsipky k pln´ym): 7/ β ζ oN @ O fN/ NNNpNpppG O W/ p/ pNNppNN ^<< ppppp/p//p//p NNNNNNNN<<< p p / NNNNN<
gOo OwpOOOO oo@ 7 ǫ >>OOOOOO //// oooooooo >> OOOOO O /o/o/ oooo >> O O OoOoOoOo/o/ o/ > o oooOoOOO/ ' γ α o wo
Ovˇsem relaci R m˚ uˇzeme zjednoduˇsit odstranˇen´ım sv´e symetrick´e ˇc´ asti, tj. vytvoˇrit relaci R ∗ = R \ R −1 , neboˇt hledan´e prvky nyn´ı z´ avis´ı pouze na asymetrick´e ˇc´ asti relace.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Staˇc´ı vz´ıt graf pro relaci R (pˇrid´ ame otoˇcen´e pˇreruˇsovan´ych ˇsipky k pln´ym): 7/ β ζ oN @ O fN/ NNNpNpppG O W/ p/ pNNppNN ^<< ppppp/p//p//p NNNNNNNN<<< p p / NNNNN<gOo OwpOOOO oo@ 7 ǫ >>OOOOOO //// oooooooo >> OOOOO O /o/o/ oooo >> O O OoOoOoOo/o/ o/ > o oooOoOOO/ ' γ α o wo
Ovˇsem relaci R m˚ uˇzeme zjednoduˇsit odstranˇen´ım sv´e symetrick´e ˇc´ asti, tj. vytvoˇrit relaci R ∗ = R \ R −1 , neboˇt hledan´e prvky nyn´ı z´ avis´ı pouze na asymetrick´e ˇc´ asti relace.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Staˇc´ı vz´ıt graf pro relaci R (pˇrid´ ame otoˇcen´e pˇreruˇsovan´ych ˇsipky k pln´ym): 7/ β ζ oN @ O fN/ NNNpNpppG O W/ p/ pNNppNN ^<< ppppp/p//p//p NNNNNNNN<<< p p / NNNNN<gOo OwpOOOO oo@ 7 ǫ >>OOOOOO //// oooooooo >> OOOOO O /o/o/ oooo >> O O OoOoOoOo/o/ o/ > o oooOoOOO/ ' γ α o wo
Ovˇsem relaci R m˚ uˇzeme zjednoduˇsit odstranˇen´ım sv´e symetrick´e ˇc´ asti, tj. vytvoˇrit relaci R ∗ = R \ R −1 , neboˇt hledan´e prvky nyn´ı z´ avis´ı pouze na asymetrick´e ˇc´ asti relace.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Z grafu tedy m˚ uˇzeme odstranit dvojice protismˇern´ych ˇsipek. ζ
β
δ _>
>> >> >> >
α
^<< << << <<
ǫ
γ
V´ysledn´ a relace R ∗ zn´ azorˇ nuje moˇzn´ a vylepˇsen´ı (tj. pˇrebit´ı v dˇr´ıvˇejˇs´ım smyslu). Z mnoˇziny A tedy odstran´ıme prvky, odkud vych´ azej´ı ˇsipky a dost´av´ ame v´ysledek V = A \ {α, ǫ} = {β, γ, δ, ζ}.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Z grafu tedy m˚ uˇzeme odstranit dvojice protismˇern´ych ˇsipek. ζ
β
δ _>
>> >> >> >
α
^<< << << <<
ǫ
γ
V´ysledn´ a relace R ∗ zn´ azorˇ nuje moˇzn´ a vylepˇsen´ı (tj. pˇrebit´ı v dˇr´ıvˇejˇs´ım smyslu). Z mnoˇziny A tedy odstran´ıme prvky, odkud vych´ azej´ı ˇsipky a dost´av´ ame v´ysledek V = A \ {α, ǫ} = {β, γ, δ, ζ}.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Z grafu tedy m˚ uˇzeme odstranit dvojice protismˇern´ych ˇsipek. ζ
β
δ _>
>> >> >> >
α
^<< << << <<
ǫ
γ
V´ysledn´ a relace R ∗ zn´ azorˇ nuje moˇzn´ a vylepˇsen´ı (tj. pˇrebit´ı v dˇr´ıvˇejˇs´ım smyslu). Z mnoˇziny A tedy odstran´ıme prvky, odkud vych´ azej´ı ˇsipky a dost´av´ ame v´ysledek V = A \ {α, ǫ} = {β, γ, δ, ζ}.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Matematick´y rozbor Z grafu tedy m˚ uˇzeme odstranit dvojice protismˇern´ych ˇsipek. ζ
β
δ _>
>> >> >> >
α
^<< << << <<
ǫ
γ
V´ysledn´ a relace R ∗ zn´ azorˇ nuje moˇzn´ a vylepˇsen´ı (tj. pˇrebit´ı v dˇr´ıvˇejˇs´ım smyslu). Z mnoˇziny A tedy odstran´ıme prvky, odkud vych´ azej´ı ˇsipky a dost´av´ ame v´ysledek V = A \ {α, ǫ} = {β, γ, δ, ζ}.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Obecn´y princip
Prvky nalezen´e mnoˇziny splˇ nuj´ı princip BPNK (neboli NPNG): BPNK - ”Bez pr´ ace nejsou kol´ aˇce.” NPNG - ”No Pain - No Gain.” ˇ Cesky: ”Bez bolesti nen´ı zisku.” Ale ”No Pain ⇒ No Gain” znamen´ a: ”Gain ⇒ Pain”, tj. ”Zisk ⇒ bolest (cena).” V naˇsem pˇr´ıpadˇe bylo: Zisk (gain) - hmotnost, vyj´ adˇrena relac´ı G Bolest (pain) - cena, vyj´ adˇrena relac´ı P Relace R = G ∪ P −1 d´ av´ a celkov´y zisk, pˇriˇcemˇz jeho podstata tkv´ı ∗ relaci R .
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
V´yˇskovnice = mnoˇzina prvk˚ u splˇnuj´ıc´ıch princip NPNG
Definice M´ ame-li bin´ arn´ı relaci R na mnoˇzinˇe A, pak v´yˇskovnic´ı relace R nazveme mnoˇzinu V (R) vˇsech prvk˚ u a ∈ A takov´ych, ˇze pro kaˇzd´e x ∈ A plat´ı (a, x) ∈ R ⇒ (x, a) ∈ R. Pro dvˇe bin´ arn´ı relace G , P na A definujeme v´yˇskovnici relace G podle P: V (G /P) = V (G ∪ P −1 ). a pro v´ıce bin´ arn´ıch relac´ı zisku G1 , G2 , . . . a cen P1 , P2 , . . . : V (G1 , G2 , . . . /P1 , P2 , . . . ) = V (G1 ∪ G2 ∪ · · · ∪ P1−1 ∪ P2−1 . . . ).
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
V´yˇskovnice = mnoˇzina prvk˚ u splˇnuj´ıc´ıch princip NPNG
Definice M´ ame-li bin´ arn´ı relaci R na mnoˇzinˇe A, pak v´yˇskovnic´ı relace R nazveme mnoˇzinu V (R) vˇsech prvk˚ u a ∈ A takov´ych, ˇze pro kaˇzd´e x ∈ A plat´ı (a, x) ∈ R ⇒ (x, a) ∈ R. Pro dvˇe bin´ arn´ı relace G , P na A definujeme v´yˇskovnici relace G podle P: V (G /P) = V (G ∪ P −1 ). a pro v´ıce bin´ arn´ıch relac´ı zisku G1 , G2 , . . . a cen P1 , P2 , . . . : V (G1 , G2 , . . . /P1 , P2 , . . . ) = V (G1 ∪ G2 ∪ · · · ∪ P1−1 ∪ P2−1 . . . ).
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
V´yˇskovnice = mnoˇzina prvk˚ u splˇnuj´ıc´ıch princip NPNG
Definice M´ ame-li bin´ arn´ı relaci R na mnoˇzinˇe A, pak v´yˇskovnic´ı relace R nazveme mnoˇzinu V (R) vˇsech prvk˚ u a ∈ A takov´ych, ˇze pro kaˇzd´e x ∈ A plat´ı (a, x) ∈ R ⇒ (x, a) ∈ R. Pro dvˇe bin´ arn´ı relace G , P na A definujeme v´yˇskovnici relace G podle P: V (G /P) = V (G ∪ P −1 ). a pro v´ıce bin´ arn´ıch relac´ı zisku G1 , G2 , . . . a cen P1 , P2 , . . . : V (G1 , G2 , . . . /P1 , P2 , . . . ) = V (G1 ∪ G2 ∪ · · · ∪ P1−1 ∪ P2−1 . . . ).
Motivace
Obecn´ y princip
Pˇr´ıklady
1
Motivace
2
Obecn´y princip
3
Pˇr´ıklady Svˇetov´e rekordy Turnajov´e uspoˇr´ ad´ an´ı Skupinov´e hodnocen´ı Rozhledny
4
Geografick´ a v´yˇskovnice
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Svˇetov´e rekordy
Pˇr´ıklad Nechˇt prvky mnoˇziny A jsou ud´ alosti skoku do d´ alky v atletice. Kaˇzd´emu skoku pˇriˇrad´ıme jeho d´elku a ˇcas, kdy k nˇemu doˇslo. Zisk - d´ elka, vyj´ adˇrena relac´ı G Cena - ˇ cas (datum), kdy ke skoku doˇslo, vyj´ adˇren relac´ı P Pak v´yˇskovnice V (G /P) obsahuje pr´ avˇe vˇsechny svˇ etov´ e rekordy ve skoku do d´ alky.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Svˇetov´e rekordy
Pˇr´ıklad Nechˇt prvky mnoˇziny A jsou ud´ alosti skoku do d´ alky v atletice. Kaˇzd´emu skoku pˇriˇrad´ıme jeho d´elku a ˇcas, kdy k nˇemu doˇslo. Zisk - d´ elka, vyj´ adˇrena relac´ı G Cena - ˇ cas (datum), kdy ke skoku doˇslo, vyj´ adˇren relac´ı P Pak v´yˇskovnice V (G /P) obsahuje pr´ avˇe vˇsechny svˇ etov´ e rekordy ve skoku do d´ alky.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Svˇetov´e rekordy
Pˇr´ıklad Nechˇt prvky mnoˇziny A jsou ud´ alosti skoku do d´ alky v atletice. Kaˇzd´emu skoku pˇriˇrad´ıme jeho d´elku a ˇcas, kdy k nˇemu doˇslo. Zisk - d´ elka, vyj´ adˇrena relac´ı G Cena - ˇ cas (datum), kdy ke skoku doˇslo, vyj´ adˇren relac´ı P Pak v´yˇskovnice V (G /P) obsahuje pr´ avˇe vˇsechny svˇ etov´ e rekordy ve skoku do d´ alky.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Svˇetov´e rekordy
Pˇr´ıklad Nechˇt prvky mnoˇziny A jsou ud´ alosti skoku do d´ alky v atletice. Kaˇzd´emu skoku pˇriˇrad´ıme jeho d´elku a ˇcas, kdy k nˇemu doˇslo. Zisk - d´ elka, vyj´ adˇrena relac´ı G Cena - ˇ cas (datum), kdy ke skoku doˇslo, vyj´ adˇren relac´ı P Pak v´yˇskovnice V (G /P) obsahuje pr´ avˇe vˇsechny svˇ etov´ e rekordy ve skoku do d´ alky.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Svˇetov´e rekordy
Pˇr´ıklad Nechˇt prvky mnoˇziny A jsou ud´ alosti skoku do d´ alky v atletice. Kaˇzd´emu skoku pˇriˇrad´ıme jeho d´elku a ˇcas, kdy k nˇemu doˇslo. Zisk - d´ elka, vyj´ adˇrena relac´ı G Cena - ˇ cas (datum), kdy ke skoku doˇslo, vyj´ adˇren relac´ı P Pak v´yˇskovnice V (G /P) obsahuje pr´ avˇe vˇsechny svˇ etov´ e rekordy ve skoku do d´ alky.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Turnajov´e uspoˇr´ad´an´ı Z´ akladn´ı princip: (x, y ) ∈ R ⇔ hr´ aˇc x je poraˇzen hr´ aˇcem y
Pˇr´ıklad Davis˚ uv poh´ ar 2009.
CZ
HR
zz zz z z zz
CZ
|| || | | ||
E E@ @
@@ @@ @
E
IL
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Turnajov´e uspoˇr´ad´an´ı Z´ akladn´ı princip: (x, y ) ∈ R ⇔ hr´ aˇc x je poraˇzen hr´ aˇcem y
Pˇr´ıklad Davis˚ uv poh´ ar 2009.
CZ
HR
zz zz z z zz
CZ
|| || | | ||
E E@ @
@@ @@ @
E
IL
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Turnajov´e uspoˇr´ad´an´ı Pˇr´ısluˇsn´a relace R m´ a graf ( HR
/ CZ
/E o
IL )
a jej´ı v´yˇskovnice V1 obsahuje pouze v´ıtˇeze E . Jeho odstranˇen´ım z mnoˇziny hr´ aˇc˚ u dost´ av´ ame novou relaci. V jej´ı v´yˇskovnici V2 budou pr´ avˇe hr´ aˇci, kter´e vyˇradil pozdˇejˇs´ı v´ıtˇez a takto pokraˇcujeme do vyˇcerp´ an´ı mnoˇziny vˇsech hr´ aˇc˚ u. ( HR
/ CZ
IL )
(HR)
V´ysledkem je ohodnocen´ı hr´ aˇc˚ u podle u ´rovnˇe v´yˇskovnice, do kter´e se dostal. Toto ohodnocen´ı odpov´ıd´ a v´ysledk˚ um turnaje. V1 = {E }, V2 = {CZ , IL}, V3 = {HR}
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Turnajov´e uspoˇr´ad´an´ı Pˇr´ısluˇsn´a relace R m´ a graf ( HR
/ CZ
/E o
IL )
a jej´ı v´yˇskovnice V1 obsahuje pouze v´ıtˇeze E . Jeho odstranˇen´ım z mnoˇziny hr´ aˇc˚ u dost´ av´ ame novou relaci. V jej´ı v´yˇskovnici V2 budou pr´ avˇe hr´ aˇci, kter´e vyˇradil pozdˇejˇs´ı v´ıtˇez a takto pokraˇcujeme do vyˇcerp´ an´ı mnoˇziny vˇsech hr´ aˇc˚ u. ( HR
/ CZ
IL )
(HR)
V´ysledkem je ohodnocen´ı hr´ aˇc˚ u podle u ´rovnˇe v´yˇskovnice, do kter´e se dostal. Toto ohodnocen´ı odpov´ıd´ a v´ysledk˚ um turnaje. V1 = {E }, V2 = {CZ , IL}, V3 = {HR}
Motivace
Obecn´ y princip
Pˇr´ıklady
Turnajov´e uspoˇr´ad´an´ı
V nˇekter´ych pˇr´ıpadech vˇsak v´yˇskovnice m˚ uˇze b´yt pr´ azdn´ a. Pˇr´ıklad MS v hokeji 2010, skupina C: / CZ p7 N O gNNN NNN ppppp ppNN ppp NNNNN p p p /S F
Geografick´ a v´ yˇskovnice
Motivace
Obecn´ y princip
Pˇr´ıklady
Turnajov´e uspoˇr´ad´an´ı
V nˇekter´ych pˇr´ıpadech vˇsak v´yˇskovnice m˚ uˇze b´yt pr´ azdn´ a. Pˇr´ıklad MS v hokeji 2010, skupina C: / CZ p7 N O gNNN NNN ppppp ppNN ppp NNNNN p p p /S F
Geografick´ a v´ yˇskovnice
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Skupinov´e hodnocen´ı
Uvaˇzujme mnoˇzinu X se (ziskov´ym) ohodnocen´ım h : X → R. Na mnoˇzinˇe P(X ) vˇsech podmnoˇzin mnoˇziny X zavedeme relaci Rh : (M, N) ∈ Rh ⇔ (∃i ∈ R)(|Mi | < |Ni |), kde Mi = h−1 (i ↑) ∩ M je mnoˇzina vˇsech prvk˚ u mnoˇziny M, jejichˇz ohodnocen´ı je vˇetˇs´ı nebo rovno ˇc´ıslu i a | | znaˇc´ı poˇcet prvk˚ u.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Pˇr´ıklad Uvaˇzujme mnoˇzinu X = {a, b, c, d, e}, zobrazen´ı h : a 7→ 1, b 7→ 2, c 7→ 2, d 7→ 3, e 7→ 4 a mnoˇziny A = {a, b, c}, B = {b, c}, C = {b, d}, D = {c, d}, E = {a, d}, F = {d}. Pak na mnoˇzinˇe M = {A, B, C , D, E } m´ ame relaci Rh danou grafem: A1,2,2 o R D2,2 xx< O Y4444 iRlRRlRRlRRlRlR E O DDD x 4 l R R xx xxxxx lllll4l4444 R R RRRRRRRRRDDDD x RRR RRRD 4444 x|xxxlxllll RRR ) " 4 4 ul 4 4 4 4 C2,3 iRFRRR 5B 4 lll < 2,3 bFFRFFRRRRRR FFFFRRR RRR 444444 lllllllllzlzlzlzzz z FFFF RRRRR R R l FFFF R RRRlRlRlRll4l4l4l4l4ll zzzzzz F " lllRlRlRlR) z|zz ll R / E1,4 F4 ul Ohodnocen´ı prvk˚ u mnoˇzin uv´ ad´ıme v doln´ım indexu.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Pˇr´ıklad V´ysledky muˇzsk´e alpsk´e kombinace na ZOH v Tur´ınˇe 2006. http: // www. torino2006. it/ ENG/ IDF/ AS/ C73E_ ASM000000. html Tabulka um´ıstˇen´ı z´avodn´ık˚ u podle jednotliv´ych st´at˚ u: USA 1,16,29
HR 2,26,33
A 3,34
CH 4,7
I 5,9
CZ 6,12,20
F 8,13
N 10
S 11,18
Um´ıstˇen´ı je cenov´a funkce h, proto bude potˇreba poˇc´ıtat s relac´ı S = Rh−1 . Celkov´e hodnocen´ı je vidˇet na grafu relace S ∗ : / USA x< O x x x x xx xx A S
HR O
/ CH I bDD O DD DD DD D / CZ o F
V´yˇskovnice obsahuje pouze CZ, CH, USA (v ˇcesk´em abecedn´ım poˇrad´ı) - to jsou ´uspˇeˇsn´e st´aty v t´eto discipl´ınˇe.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Pˇr´ıklad V´ysledky muˇzsk´e alpsk´e kombinace na ZOH v Tur´ınˇe 2006. http: // www. torino2006. it/ ENG/ IDF/ AS/ C73E_ ASM000000. html Tabulka um´ıstˇen´ı z´avodn´ık˚ u podle jednotliv´ych st´at˚ u: USA 1,16,29
HR 2,26,33
A 3,34
CH 4,7
I 5,9
CZ 6,12,20
F 8,13
N 10
S 11,18
Um´ıstˇen´ı je cenov´a funkce h, proto bude potˇreba poˇc´ıtat s relac´ı S = Rh−1 . Celkov´e hodnocen´ı je vidˇet na grafu relace S ∗ : / USA x< O x x x x xx xx A S
HR O
/ CH I bDD O DD DD DD D / CZ o F
V´yˇskovnice obsahuje pouze CZ, CH, USA (v ˇcesk´em abecedn´ım poˇrad´ı) - to jsou ´uspˇeˇsn´e st´aty v t´eto discipl´ınˇe.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Pˇr´ıklad V´ysledky muˇzsk´e alpsk´e kombinace na ZOH v Tur´ınˇe 2006. http: // www. torino2006. it/ ENG/ IDF/ AS/ C73E_ ASM000000. html Tabulka um´ıstˇen´ı z´avodn´ık˚ u podle jednotliv´ych st´at˚ u: USA 1,16,29
HR 2,26,33
A 3,34
CH 4,7
I 5,9
CZ 6,12,20
F 8,13
N 10
S 11,18
Um´ıstˇen´ı je cenov´a funkce h, proto bude potˇreba poˇc´ıtat s relac´ı S = Rh−1 . Celkov´e hodnocen´ı je vidˇet na grafu relace S ∗ : / USA x< O x x x x xx xx A S
HR O
/ CH I bDD O DD DD DD D / CZ o F
V´yˇskovnice obsahuje pouze CZ, CH, USA (v ˇcesk´em abecedn´ım poˇrad´ı) - to jsou ´uspˇeˇsn´e st´aty v t´eto discipl´ınˇe.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Pˇr´ıklad V´ysledky muˇzsk´e alpsk´e kombinace na ZOH v Tur´ınˇe 2006. http: // www. torino2006. it/ ENG/ IDF/ AS/ C73E_ ASM000000. html Tabulka um´ıstˇen´ı z´avodn´ık˚ u podle jednotliv´ych st´at˚ u: USA 1,16,29
HR 2,26,33
A 3,34
CH 4,7
I 5,9
CZ 6,12,20
F 8,13
N 10
S 11,18
Um´ıstˇen´ı je cenov´a funkce h, proto bude potˇreba poˇc´ıtat s relac´ı S = Rh−1 . Celkov´e hodnocen´ı je vidˇet na grafu relace S ∗ : / USA x< O x x x x xx xx A S
HR O
/ CH I bDD O DD DD DD D / CZ o F
V´yˇskovnice obsahuje pouze CZ, CH, USA (v ˇcesk´em abecedn´ım poˇrad´ı) - to jsou ´uspˇeˇsn´e st´aty v t´eto discipl´ınˇe.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Rozhledny
Vˇeta Rozhlednov´y z´ akon: (T1 )Pokud je z bodu A vidˇet bod B, pak je z bodu B vidˇet bod A. (T2 )Pokud je bod A vidˇet z bodu B, pak je bod B vidˇet z bodu A. Ch´ apeme-li v´yˇse uveden´e ekvivalentn´ı v´yroky jako tvrzen´ı platn´ a pro vˇsechna A, B, pak je toto tvrzen´ı ˇr´ık´ a ”Relace viditelnosti je symetrick´ a.” Pokud vˇsak tvrzen´ı (T1) nebo (T2) bereme jako tvrzen´ı T (A) o konkr´etn´ım m´ıstˇe A, pak jejich platnost pˇresnˇe odpov´ıd´ a principu NPNG.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Rozhledny
Vˇeta Rozhlednov´y z´ akon: (T1 )Pokud je z bodu A vidˇet bod B, pak je z bodu B vidˇet bod A. (T2 )Pokud je bod A vidˇet z bodu B, pak je bod B vidˇet z bodu A. Ch´ apeme-li v´yˇse uveden´e ekvivalentn´ı v´yroky jako tvrzen´ı platn´ a pro vˇsechna A, B, pak je toto tvrzen´ı ˇr´ık´ a ”Relace viditelnosti je symetrick´ a.” Pokud vˇsak tvrzen´ı (T1) nebo (T2) bereme jako tvrzen´ı T (A) o konkr´etn´ım m´ıstˇe A, pak jejich platnost pˇresnˇe odpov´ıd´ a principu NPNG.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Rozhledny
Vˇeta Rozhlednov´y z´ akon: (T1 )Pokud je z bodu A vidˇet bod B, pak je z bodu B vidˇet bod A. (T2 )Pokud je bod A vidˇet z bodu B, pak je bod B vidˇet z bodu A. Ch´ apeme-li v´yˇse uveden´e ekvivalentn´ı v´yroky jako tvrzen´ı platn´ a pro vˇsechna A, B, pak je toto tvrzen´ı ˇr´ık´ a ”Relace viditelnosti je symetrick´ a.” Pokud vˇsak tvrzen´ı (T1) nebo (T2) bereme jako tvrzen´ı T (A) o konkr´etn´ım m´ıstˇe A, pak jejich platnost pˇresnˇe odpov´ıd´ a principu NPNG.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Rozhledny
Vˇeta Rozhlednov´y z´ akon: (T1 )Pokud je z bodu A vidˇet bod B, pak je z bodu B vidˇet bod A. (T2 )Pokud je bod A vidˇet z bodu B, pak je bod B vidˇet z bodu A. Ch´ apeme-li v´yˇse uveden´e ekvivalentn´ı v´yroky jako tvrzen´ı platn´ a pro vˇsechna A, B, pak je toto tvrzen´ı ˇr´ık´ a ”Relace viditelnosti je symetrick´ a.” Pokud vˇsak tvrzen´ı (T1) nebo (T2) bereme jako tvrzen´ı T (A) o konkr´etn´ım m´ıstˇe A, pak jejich platnost pˇresnˇe odpov´ıd´ a principu NPNG.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Rozhledny
Vˇeta Rozhlednov´y z´ akon: (T1 )Pokud je z bodu A vidˇet bod B, pak je z bodu B vidˇet bod A. (T2 )Pokud je bod A vidˇet z bodu B, pak je bod B vidˇet z bodu A. Ch´ apeme-li v´yˇse uveden´e ekvivalentn´ı v´yroky jako tvrzen´ı platn´ a pro vˇsechna A, B, pak je toto tvrzen´ı ˇr´ık´ a ”Relace viditelnosti je symetrick´ a.” Pokud vˇsak tvrzen´ı (T1) nebo (T2) bereme jako tvrzen´ı T (A) o konkr´etn´ım m´ıstˇe A, pak jejich platnost pˇresnˇe odpov´ıd´ a principu NPNG.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Rozhledny Uvaˇzme zobecnˇen´ı pojmu ”bod” na ”m´ısto” a zkusme uv´ aˇzit relaci viditelnosti. Ta pˇrest´ av´ a b´yt symetrick´ a, pokud bereme za ”m´ısto” napˇr´ıklad zalesnˇen´y kopec. Ten m˚ uˇze b´yt vidˇet z d´ alky, ovˇsem v˚ ubec nemus´ı poskytovat v´yhled. V tomto pˇr´ıpadˇe m´ a smysl hledat napˇr´ıklad m´ısto, ze kter´eho bude v´yhled ”dobr´y vzhledem k moˇznostem”. To n´ am urˇc´ı v´yˇskovnice pro relaci (x, y ) ∈ R ⇔ m´ısto x je vidˇet z m´ısta y . Najdeme tak kaˇzd´e m´ısto A takov´e, ˇze pro kaˇzd´e X plat´ı, ˇze pokud je A vidˇet z X , pak je X vidˇet z A. Vyuˇzit´ı: ve vojenstv´ı ...
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Rozhledny Uvaˇzme zobecnˇen´ı pojmu ”bod” na ”m´ısto” a zkusme uv´ aˇzit relaci viditelnosti. Ta pˇrest´ av´ a b´yt symetrick´ a, pokud bereme za ”m´ısto” napˇr´ıklad zalesnˇen´y kopec. Ten m˚ uˇze b´yt vidˇet z d´ alky, ovˇsem v˚ ubec nemus´ı poskytovat v´yhled. V tomto pˇr´ıpadˇe m´ a smysl hledat napˇr´ıklad m´ısto, ze kter´eho bude v´yhled ”dobr´y vzhledem k moˇznostem”. To n´ am urˇc´ı v´yˇskovnice pro relaci (x, y ) ∈ R ⇔ m´ısto x je vidˇet z m´ısta y . Najdeme tak kaˇzd´e m´ısto A takov´e, ˇze pro kaˇzd´e X plat´ı, ˇze pokud je A vidˇet z X , pak je X vidˇet z A. Vyuˇzit´ı: ve vojenstv´ı ...
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Rozhledny Uvaˇzme zobecnˇen´ı pojmu ”bod” na ”m´ısto” a zkusme uv´ aˇzit relaci viditelnosti. Ta pˇrest´ av´ a b´yt symetrick´ a, pokud bereme za ”m´ısto” napˇr´ıklad zalesnˇen´y kopec. Ten m˚ uˇze b´yt vidˇet z d´ alky, ovˇsem v˚ ubec nemus´ı poskytovat v´yhled. V tomto pˇr´ıpadˇe m´ a smysl hledat napˇr´ıklad m´ısto, ze kter´eho bude v´yhled ”dobr´y vzhledem k moˇznostem”. To n´ am urˇc´ı v´yˇskovnice pro relaci (x, y ) ∈ R ⇔ m´ısto x je vidˇet z m´ısta y . Najdeme tak kaˇzd´e m´ısto A takov´e, ˇze pro kaˇzd´e X plat´ı, ˇze pokud je A vidˇet z X , pak je X vidˇet z A. Vyuˇzit´ı: ve vojenstv´ı ...
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Geografick´a v´yˇskovnice Uvaˇzujme metrick´y prostor, tj. mnoˇzinu X , na n´ıˇz m´ ame definovnu vzd´ alenost (metriku) ρ(x, y ) mezi kaˇzd´ymi dvˇema body x, y ∈ X . Nechˇt A ⊆ X je mnoˇzina vrchol˚ u s definovanou funkc´ı v´yˇsky h : A → R. ame funkci d : A → R+ Nechˇt x0 ∈ X . Pak m´ 0 definovanou d(a) = ρ(x0 , a). Hled´ ame body z mnoˇziny A v´yznamn´e pro bod x0 svoj´ı polohou a v´yˇskou, tj. body bl´ızk´ e a vysok´ e. Uvaˇzujeme relace Zisk - v´yˇska h, vyj´ adˇrena relac´ı H Cena - vzd´ alenost d od bodu x0 , vyj´ adˇrena relac´ı Dx0 Hledan´e body jsou body v´yˇskovnice V (H/Dx0 ). Jak je najdeme? Body v´yˇskovnice najdeme pomoc´ı kruˇznicov´e konstrukce.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Geografick´a v´yˇskovnice Uvaˇzujme metrick´y prostor, tj. mnoˇzinu X , na n´ıˇz m´ ame definovnu vzd´ alenost (metriku) ρ(x, y ) mezi kaˇzd´ymi dvˇema body x, y ∈ X . Nechˇt A ⊆ X je mnoˇzina vrchol˚ u s definovanou funkc´ı v´yˇsky h : A → R. Nechˇt x0 ∈ X . Pak m´ ame funkci d : A → R+ 0 definovanou d(a) = ρ(x0 , a). Hled´ ame body z mnoˇziny A v´yznamn´e pro bod x0 svoj´ı polohou a v´yˇskou, tj. body bl´ızk´ e a vysok´ e. Uvaˇzujeme relace Zisk - v´yˇska h, vyj´ adˇrena relac´ı H Cena - vzd´ alenost d od bodu x0 , vyj´ adˇrena relac´ı Dx0 Hledan´e body jsou body v´yˇskovnice V (H/Dx0 ). Jak je najdeme? Body v´yˇskovnice najdeme pomoc´ı kruˇznicov´e konstrukce.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Geografick´a v´yˇskovnice Uvaˇzujme metrick´y prostor, tj. mnoˇzinu X , na n´ıˇz m´ ame definovnu vzd´ alenost (metriku) ρ(x, y ) mezi kaˇzd´ymi dvˇema body x, y ∈ X . Nechˇt A ⊆ X je mnoˇzina vrchol˚ u s definovanou funkc´ı v´yˇsky h : A → R. ame funkci d : A → R+ Nechˇt x0 ∈ X . Pak m´ 0 definovanou d(a) = ρ(x0 , a). Hled´ ame body z mnoˇziny A v´yznamn´e pro bod x0 svoj´ı polohou a v´yˇskou, tj. body bl´ızk´ e a vysok´ e. Uvaˇzujeme relace Zisk - v´yˇska h, vyj´ adˇrena relac´ı H Cena - vzd´ alenost d od bodu x0 , vyj´ adˇrena relac´ı Dx0 Hledan´e body jsou body v´yˇskovnice V (H/Dx0 ). Jak je najdeme? Body v´yˇskovnice najdeme pomoc´ı kruˇznicov´e konstrukce.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Geografick´a v´yˇskovnice Uvaˇzujme metrick´y prostor, tj. mnoˇzinu X , na n´ıˇz m´ ame definovnu vzd´ alenost (metriku) ρ(x, y ) mezi kaˇzd´ymi dvˇema body x, y ∈ X . Nechˇt A ⊆ X je mnoˇzina vrchol˚ u s definovanou funkc´ı v´yˇsky h : A → R. ame funkci d : A → R+ Nechˇt x0 ∈ X . Pak m´ 0 definovanou d(a) = ρ(x0 , a). Hled´ ame body z mnoˇziny A v´yznamn´e pro bod x0 svoj´ı polohou a v´yˇskou, tj. body bl´ızk´ e a vysok´ e. Uvaˇzujeme relace Zisk - v´yˇska h, vyj´ adˇrena relac´ı H Cena - vzd´ alenost d od bodu x0 , vyj´ adˇrena relac´ı Dx0 Hledan´e body jsou body v´yˇskovnice V (H/Dx0 ). Jak je najdeme? Body v´yˇskovnice najdeme pomoc´ı kruˇznicov´e konstrukce.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Geografick´a v´yˇskovnice Uvaˇzujme metrick´y prostor, tj. mnoˇzinu X , na n´ıˇz m´ ame definovnu vzd´ alenost (metriku) ρ(x, y ) mezi kaˇzd´ymi dvˇema body x, y ∈ X . Nechˇt A ⊆ X je mnoˇzina vrchol˚ u s definovanou funkc´ı v´yˇsky h : A → R. ame funkci d : A → R+ Nechˇt x0 ∈ X . Pak m´ 0 definovanou d(a) = ρ(x0 , a). Hled´ ame body z mnoˇziny A v´yznamn´e pro bod x0 svoj´ı polohou a v´yˇskou, tj. body bl´ızk´ e a vysok´ e. Uvaˇzujeme relace Zisk - v´yˇska h, vyj´ adˇrena relac´ı H Cena - vzd´ alenost d od bodu x0 , vyj´ adˇrena relac´ı Dx0 Hledan´e body jsou body v´yˇskovnice V (H/Dx0 ). Jak je najdeme? Body v´yˇskovnice najdeme pomoc´ı kruˇznicov´e konstrukce.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Geografick´a v´yˇskovnice Uvaˇzujme metrick´y prostor, tj. mnoˇzinu X , na n´ıˇz m´ ame definovnu vzd´ alenost (metriku) ρ(x, y ) mezi kaˇzd´ymi dvˇema body x, y ∈ X . Nechˇt A ⊆ X je mnoˇzina vrchol˚ u s definovanou funkc´ı v´yˇsky h : A → R. ame funkci d : A → R+ Nechˇt x0 ∈ X . Pak m´ 0 definovanou d(a) = ρ(x0 , a). Hled´ ame body z mnoˇziny A v´yznamn´e pro bod x0 svoj´ı polohou a v´yˇskou, tj. body bl´ızk´ e a vysok´ e. Uvaˇzujeme relace Zisk - v´yˇska h, vyj´ adˇrena relac´ı H Cena - vzd´ alenost d od bodu x0 , vyj´ adˇrena relac´ı Dx0 Hledan´e body jsou body v´yˇskovnice V (H/Dx0 ). Jak je najdeme? Body v´yˇskovnice najdeme pomoc´ı kruˇznicov´e konstrukce.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Geografick´a v´yˇskovnice Uvaˇzujme metrick´y prostor, tj. mnoˇzinu X , na n´ıˇz m´ ame definovnu vzd´ alenost (metriku) ρ(x, y ) mezi kaˇzd´ymi dvˇema body x, y ∈ X . Nechˇt A ⊆ X je mnoˇzina vrchol˚ u s definovanou funkc´ı v´yˇsky h : A → R. ame funkci d : A → R+ Nechˇt x0 ∈ X . Pak m´ 0 definovanou d(a) = ρ(x0 , a). Hled´ ame body z mnoˇziny A v´yznamn´e pro bod x0 svoj´ı polohou a v´yˇskou, tj. body bl´ızk´ e a vysok´ e. Uvaˇzujeme relace Zisk - v´yˇska h, vyj´ adˇrena relac´ı H Cena - vzd´ alenost d od bodu x0 , vyj´ adˇrena relac´ı Dx0 Hledan´e body jsou body v´yˇskovnice V (H/Dx0 ). Jak je najdeme? Body v´yˇskovnice najdeme pomoc´ı kruˇznicov´e konstrukce.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Geografick´a v´yˇskovnice Uvaˇzujme metrick´y prostor, tj. mnoˇzinu X , na n´ıˇz m´ ame definovnu vzd´ alenost (metriku) ρ(x, y ) mezi kaˇzd´ymi dvˇema body x, y ∈ X . Nechˇt A ⊆ X je mnoˇzina vrchol˚ u s definovanou funkc´ı v´yˇsky h : A → R. ame funkci d : A → R+ Nechˇt x0 ∈ X . Pak m´ 0 definovanou d(a) = ρ(x0 , a). Hled´ ame body z mnoˇziny A v´yznamn´e pro bod x0 svoj´ı polohou a v´yˇskou, tj. body bl´ızk´ e a vysok´ e. Uvaˇzujeme relace Zisk - v´yˇska h, vyj´ adˇrena relac´ı H Cena - vzd´ alenost d od bodu x0 , vyj´ adˇrena relac´ı Dx0 Hledan´e body jsou body v´yˇskovnice V (H/Dx0 ). Jak je najdeme? Body v´yˇskovnice najdeme pomoc´ı kruˇznicov´e konstrukce.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Geografick´a v´yˇskovnice Uvaˇzujme metrick´y prostor, tj. mnoˇzinu X , na n´ıˇz m´ ame definovnu vzd´ alenost (metriku) ρ(x, y ) mezi kaˇzd´ymi dvˇema body x, y ∈ X . Nechˇt A ⊆ X je mnoˇzina vrchol˚ u s definovanou funkc´ı v´yˇsky h : A → R. ame funkci d : A → R+ Nechˇt x0 ∈ X . Pak m´ 0 definovanou d(a) = ρ(x0 , a). Hled´ ame body z mnoˇziny A v´yznamn´e pro bod x0 svoj´ı polohou a v´yˇskou, tj. body bl´ızk´ e a vysok´ e. Uvaˇzujeme relace Zisk - v´yˇska h, vyj´ adˇrena relac´ı H Cena - vzd´ alenost d od bodu x0 , vyj´ adˇrena relac´ı Dx0 Hledan´e body jsou body v´yˇskovnice V (H/Dx0 ). Jak je najdeme? Body v´yˇskovnice najdeme pomoc´ı kruˇznicov´e konstrukce.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Inverzn´ı v´yˇskovnice
Opˇet uvaˇzujeme metrick´y prostor (X , ρ) a v´yˇskovou funkci h : A → R na A ⊆ X . Nechˇt v ∈ A je pevnˇe vybran´y vrchol. Pro kter´e body je vrchol v v´yznamn´y? Tj. pro kter´e x ∈ X plat´ı, ˇze v ∈ V (H/Dx )? Jak je najdeme? Hled´ an´ı inverzn´ı v´yˇskovnice provedeme pomoc´ı mnoho´ uheln´ıkov´eho algoritmu. V´yslednou mnoˇzinu m˚ uˇzeme ch´ apat jako sp´ adovou oblast vrcholu v , ˇci oblast jeho v´yznamu.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Inverzn´ı v´yˇskovnice
Opˇet uvaˇzujeme metrick´y prostor (X , ρ) a v´yˇskovou funkci h : A → R na A ⊆ X . Nechˇt v ∈ A je pevnˇe vybran´y vrchol. Pro kter´e body je vrchol v v´yznamn´y? Tj. pro kter´e x ∈ X plat´ı, ˇze v ∈ V (H/Dx )? Jak je najdeme? Hled´ an´ı inverzn´ı v´yˇskovnice provedeme pomoc´ı mnoho´ uheln´ıkov´eho algoritmu. V´yslednou mnoˇzinu m˚ uˇzeme ch´ apat jako sp´ adovou oblast vrcholu v , ˇci oblast jeho v´yznamu.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Inverzn´ı v´yˇskovnice
Opˇet uvaˇzujeme metrick´y prostor (X , ρ) a v´yˇskovou funkci h : A → R na A ⊆ X . Nechˇt v ∈ A je pevnˇe vybran´y vrchol. Pro kter´e body je vrchol v v´yznamn´y? Tj. pro kter´e x ∈ X plat´ı, ˇze v ∈ V (H/Dx )? Jak je najdeme? Hled´ an´ı inverzn´ı v´yˇskovnice provedeme pomoc´ı mnoho´ uheln´ıkov´eho algoritmu. V´yslednou mnoˇzinu m˚ uˇzeme ch´ apat jako sp´ adovou oblast vrcholu v , ˇci oblast jeho v´yznamu.
Motivace
Obecn´ y princip
Pˇr´ıklady
Geografick´ a v´ yˇskovnice
Inverzn´ı v´yˇskovnice
Opˇet uvaˇzujeme metrick´y prostor (X , ρ) a v´yˇskovou funkci h : A → R na A ⊆ X . Nechˇt v ∈ A je pevnˇe vybran´y vrchol. Pro kter´e body je vrchol v v´yznamn´y? Tj. pro kter´e x ∈ X plat´ı, ˇze v ∈ V (H/Dx )? Jak je najdeme? Hled´ an´ı inverzn´ı v´yˇskovnice provedeme pomoc´ı mnoho´ uheln´ıkov´eho algoritmu. V´yslednou mnoˇzinu m˚ uˇzeme ch´ apat jako sp´ adovou oblast vrcholu v , ˇci oblast jeho v´yznamu.
