Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 20. 12. 2014 23:58 — Editoval check_drummer (22. 12. 2014 02:36)

check_drummer
Příspěvky: 2363
Reputace:   64 
 

Pokrývání obdélníka kopiemi shodného (menšího) obdélníka

Ahoj,
zkoumejme úlohu, kdy chceme nalézt takový obdélník P (nazvěme jej elementární obdélník) s jednotkovým obsahem (tj. bude mít rozměry x,1/x pro nějaké x), aby bylo pomocí P možno co nejlépe pokrýt libovolný obdélník Q (jeho rozměry označme u,v). (Pokrytím myslíme sestrojením kopií $P_i$ obdélníka P takových, že $Q \subseteq \cup_{i}{P_i}$.)

Takto je úloha formulována poněkud vágně (i když myšlenka je asi zřejmá), zpřesněme tedy formulaci (tedy to, co znamená "co nejlépe"): Pro jednoduchost uvažujme jen taková pokrytí, kdy strany kopií P (kterými Q pokrýváme) jsou rovnoběžné se stranami Q a jednotlivé kopie P se od sebe liší jen posunutím (takovým způsobem jsou pokryty např. podlahy, chodníky, apod.) Tedy při pokrývání máme na výběr umisťovat kopie P buď všechny "nadélku" nebo všechny "našířku" - a vybereme si to pokrytí, které má z těchto dvou menší chybu. (Např. elementárním obdélníkem P s rozměry 2x0.5 lze pokrýt obdélník Q s rozměry 3x4 beze zbytku, protože můžeme kopie P postavit "navýšku".)


Nyní definujme chybu $e$ pokrytí - půjde o rozdíl obsahu obdélníku R ($R:= \cup_{i}{P_i}$) a Q, tj. e(x,u,v):=obsah(R)-obsah(P). Definujeme-li nyní celokovou chybu jako určitý integrál přes všechny možné obdélníky Q, tj. přes všechny možné dvojice u,v, pak se dostaneme do problémů, protože tento integrál vyjde nekonečný. - A tedy je vhodnější zkoumat vztah dvou pokrytí daných elementárním obdélníkem se stranou x a dalším elementárním obdélníkem se stranou y - potom rozdíl chyb v daném pokrytí je f(x,y,u,v):=e(x,u,v)-e(y,u,v) a f(x,y,u,v)<0 právě když pokrytí odpovídající x je lepší než pokrytí odpovdíající y. Nyní již lze definovat, které pokrytí je lepší (přes všechna u,v) tak, že položíme $g:=\int_{[u,v] \in (0;+\infty)^2} {f(x,y,u,v).du.dv}$ - a řekneme, že pokrytí odpovídající x jsou lepší než pokrytí odpovídající y právě když g<0 (včetně případu, kdy $g=-\infty$).

Nyní tedy máme definovány potřebné pojmy a úkolem je nalézt "nejlepší" x. (Pokud bude mít někdo lepší nápad, jak definovat, které pokrytí (přes všechna u,v) je lepší, můžeme zkoumat i toto kriterium. Např. by bylo možné zkoumat nikoli integral, ale nejhorší případ (sup{e(x,u,v)} (přes u,v)), ale tento přístup je z hlediska "pravděpodobnostního" (Q je vybráno náhodně) méně vhodným kriteriem.)

Pozn.: Úlohu jsem se pokoušel řešit numericky, ale k žádnému konkrétnímu výsledku jsem se nedobral (vycházely mi hodnoty kolem x=0.85) - nejspíš by bylo nutné provést mnoho "simulací", aby bylo možné získat relevantní výsledky.


Cimrmanův botanický kvíz:
Co mají společného byliny kozlík a pivoňka?

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson