Samarali o'lchov - Effective dimension

Yilda matematika, samarali o'lchov ning modifikatsiyasi Hausdorff o'lchovi va boshqalar fraktal o'lchamlari uni a joylashtiradi hisoblash nazariyasi sozlash. Bir nechta farqlar mavjud (samarali o'lchamlarning turli xil tushunchalari), ulardan eng keng tarqalgani samarali Hausdorff o'lchovi. Hajmi, matematikada, ob'ekt hajmini tavsiflashning o'ziga xos usuli (o'lchov va boshqa har xil, o'lcham tushunchalariga qarama-qarshi). Hausdorff o'lchovi nuqtalar, chiziqlar, tekisliklar va boshqalarga berilgan taniqli butun o'lchovlarni ushbu butun o'lchovli ob'ektlar orasidagi oraliq kattalikdagi ob'ektlarni ajratib turishga imkon berish orqali umumlashtiradi. Masalan, fraktal tekislikning pastki to'plamlari oraliq o'lchamga ega bo'lishi mumkin 1 va 2, chunki ular chiziqlar yoki egri chiziqlardan "kattaroq", ammo to'ldirilgan doiralar yoki to'rtburchaklarnikidan "kichikroq". Effektiv o'lchov Hausdorff o'lchamini o'zgartiradi, chunki unchalik katta bo'lmagan o'lchovli ob'ektlar hisoblanadigan ma'noda nafaqat kichik, balki joylashishi mumkin (yoki qisman joylashishi mumkin). Shunday qilib, katta Hausdorff o'lchamiga ega bo'lgan ob'ektlar ham katta samarali o'lchovga ega va kichik o'lchamdagi narsalar kichik Hausdorff o'lchamiga ega, ammo ob'ekt kichik Hausdorffga ega, ammo katta samarali o'lchovga ega bo'lishi mumkin. Bunga misol algoritmik tasodifiy Hausdorff o'lchoviga ega bo'lgan (lekin bu nuqta bo'lgani uchun), ammo samarali o'lchov 1 bo'lgan chiziqda nuqta (chunki taxminan aytganda, uni Hausdorff o'lchamiga ega bo'lgan kichik intervaldan yaxshiroq lokalizatsiya qilib bo'lmaydi).

Qattiq ta'riflar

Ushbu maqola quyi to'plamlar uchun samarali o'lchovni belgilaydi Kantor maydoni 2^ω; ning quyi to'plamlari uchun chambarchas bog'liq ta'riflar mavjud Evklid fazosi Rⁿ. Biz to'plamni ko'rib chiqish o'rtasida erkin harakat qilamiz X tabiiy sonlarning cheksiz ketma-ketligi ${displaystyle chi _ {X}}$ ning xarakterli funktsiyasi bilan berilgan Xva ikkilik kengayish bilan haqiqiy raqam 0.X.

Martingalalar va boshqa galalar

A martingale Cantor makonida 2^ω funktsiya d: 2^ω → R^≥ 0 Cantor kosmosidan noaniq reallarga, bu adolatli shartni qondiradi:

{displaystyle d (sigma) = {frac {1} {2}} (d (sigma 0) + d (sigma 1))}

Martingale garov strategiyasi va funktsiyasi sifatida qaraladi ${displaystyle d (sigma)}$ 0s va 1s ketma-ketlikni seeing ko'rgandan keyin yaxshi kapitalni beradi. So'ngra adolat sharti shundan iboratki, ketma-ketlikdan keyin kapital -0 va -1 ko'rgandan keyin kapitalning o'rtacha qiymati; boshqacha qilib aytganda, martingale "teng ehtimolli" ikkita variantning ikkalasida ham 2: 1 koeffitsienti bilan bukmeyster uchun tikish sxemasini beradi, shuning uchun ham "adolatli" nom.

(E'tibor bering, bu ehtimollik nazariyasi tushunchasidan tubdan farq qiladi martingale.^[1] Martingale-ning ushbu ta'rifi shunga o'xshash adolatli holatga ega, shuningdek, ba'zi kuzatuvlardan keyingi kutilgan qiymat kuzatuvlarning oldingi tarixini hisobga olgan holda, kuzatishdan oldingi qiymat bilan bir xil ekanligini ta'kidlaydi. Farqi shundaki, ehtimollar nazariyasida kuzatuvlarning oldingi tarixi faqat kapital tarixiga ishora qiladi, ammo bu erda tarix satrdagi 0s va 1s ning aniq ketma-ketligini anglatadi.)

A supermartingale Cantor kosmosda funktsiya mavjud d o'zgartirilgan adolat shartini qondiradigan yuqoridagi kabi:

{displaystyle d (sigma) geq {frac {1} {2}} (d (sigma 0) + d (sigma 1))}

Supermartingale - bu garovga qo'yilganidan keyin kutilgan kapital, garov tikishdan oldin kapitaldan ko'p bo'lmagan garov tikish strategiyasi, bu ikkalasi doimo teng bo'lgan martingaladan farqli o'laroq. Bu ko'proq moslashuvchanlikni ta'minlaydi va samarasiz holatda juda o'xshash, chunki har doim ham superartingale d berilgan, o'zgartirilgan funktsiya mavjud d ' kamida kamida qancha pul yutadi d va bu aslida martingale. Garchi tikish strategiyasini aniqlash uchun algoritmlarni berish to'g'risida gaplasha boshlagach, qo'shimcha moslashuvchanlikni ta'minlash foydalidir, chunki ba'zi algoritmlar martingalalarga qaraganda supermartingallarni ishlab chiqarishga tabiiy ravishda qarz berishadi.

An s-gale funktsiya d shaklning yuqorisidagi kabi

{displaystyle d (sigma) = {frac {e (sigma)} {2 ^ {(1-s) | sigma |}}}}

uchun e ba'zi martingale.

An s-supergale funktsiya d shaklning yuqorisidagi kabi

{displaystyle d (sigma) = {frac {e (sigma)} {2 ^ {(1-s) | sigma |}}}}

uchun e ba'zi bir supermartingale.

An s- (super) gale - bu har bir qadamda inflyatsiya uchun kapitalning bir qismi yo'qoladigan tikish strategiyasi. Yozib oling s-gales va s-supergallar supermartingalalarning namunalari, va 1-gales va 1-supergaleslar aynan martingalalar va supermartingalalardir.

Umumiy holda, ushbu ob'ektlar "gales" deb nomlanadi.

Gale d muvaffaqiyatli bo'ladi kichik to'plamda X agar tabiiy sonlar ${displaystyle limsup _ {n} d (X | n) = yaroqsiz}$ qayerda ${displaystyle X | n}$ belgisini bildiradi n- birinchisidan iborat bo'lgan raqamli satr n ning raqamlari X.

Gale d kuchli muvaffaqiyatga erishadi kuni X agar ${displaystyle liminf _ {n} d (X | n) = yaroqsiz}$ .

Ushbu turli xil galeyalarning barcha tushunchalari samarali tarkibga ega emas, lekin ular o'zlarini faqat kichik bir gallar sinfiga cheklab qo'yishlari kerak, chunki har qanday to'plamda muvaffaqiyatga erishadigan ba'zi bir shamollarni topish mumkin. Axir, agar kimdir tanga aylanmalarining ketma-ketligini oldindan bilsa, shunchaki har bir varaqning ma'lum natijalariga pul tikib pul ishlash oson. Buning standart usuli - bu gallarning hisoblanadigan yoki hisoblanishga yaqin bo'lishini talab qilishdir:

Gale d deyiladi konstruktiv, c.e., yoki pastki yarim hisoblanadigan agar raqamlar bo'lsa ${displaystyle d (sigma)}$ bir xil chap-c.e. reallar (ya'ni bir xilda ortib borayotgan hisoblash mantiqiy ketma-ketligining chegarasi sifatida yozilishi mumkin).

The samarali Hausdorff o'lchovi natural sonlar to'plamining X bu ${displaystyle inf {s: mathrm {some c.e.} smathrm {-gale muvaffaqiyatli X}}$ .^[2]

The samarali qadoqlash hajmi ning X bu ${displaystyle inf {s: mathrm {some c.e.} smathrm {-gale muvaffaqiyatli ravishda X}}$ .^[3]

Kolmogorovning murakkabligini aniqlash

Kolmogorovning murakkabligi cheklangan ketma-ketlikni (belgilar yoki ikkilik raqamlar) algoritmik siqilishining pastki chegarasi deb hisoblash mumkin. U har bir shunday ketma-ketlikni belgilaydi w tabiiy son K (w) intuitiv ravishda, hech qanday kirish talab qilmaydigan va chiqadigan kompyuter dasturining (ba'zi bir sobit dasturlash tillarida yozilgan) minimal uzunligini o'lchaydi. w ishga tushirilganda.

The samarali Hausdorff o'lchovi natural sonlar to'plamining X bu ${displaystyle liminf _ {n} {frac {K (X | n)} {n}}}$ .^[4]^[5]^[6]^[7]

The samarali qadoqlash hajmi to'plamning X bu ${displaystyle limsup _ {n} {frac {K (X | n)} {n}}}$ .^[3]^[4]^[5]

Bundan ko'rinib turibdiki, samarali Hausdorff o'lchovi ham, to'plamning samarali qadoqlash hajmi ham 0 dan 1 gacha, samarali qadoqlash o'lchovi har doim kamida samarali Hausdorff o'lchoviga teng. Har bir tasodifiy ketma-ketlik samarali Hausdorff va qadoqlash o'lchamlari 1 ga teng bo'ladi, ammo samarali Hausdorff va qadoqlash o'lchamlari 1 bo'lgan tasodifiy bo'lmagan ketma-ketliklar ham mavjud.

Klassik o'lchov bilan taqqoslash

Agar Z ning pastki qismi 2^ω, uning Hausdorff o'lchovi ${displaystyle inf {s: mathrm {some} smathrm {-gale} Z ning barcha elementlarini muvaffaqiyatli bajaradi}}$ .^[2]

Qadoqlash hajmi Z bu ${displaystyle inf {s: mathrm {some} smathrm {-gale}} ning barcha elementlarida muvaffaqiyatli ishlaydi}}$ .^[3]

Shunday qilib, to'plamning samarali Hausdorff va qadoqlash o'lchamlari ${displaystyle X}$ oddiygina Hausdorff va qadoqlash o'lchamlari ${displaystyle {X}}$ (o'z navbatida) biz e'tiborimizni c.e. gales.

Quyidagilarni aniqlang:

{displaystyle H_ {eta}: = {Xin 2 ^ {omega}: X mathrm {samarali Hausdorff o'lchoviga ega} va eta}}

{displaystyle H_ {leq eta}: = {Xin 2 ^ {omega}: X mathrm {samarali Hausdorff o'lchoviga ega} leq eta}}

{displaystyle H _ {

{displaystyle P_ {eta}: = {Xin 2 ^ {omega}: X mathrm {samarali qadoqlash o'lchoviga ega} eta}}

{displaystyle P_ {leq eta}: = {Xin 2 ^ {omega}: X mathrm {samarali qadoqlash o'lchoviga ega} leq eta}}

{displaystyle P _ {

Yuqoridagilarning natijasi shundaki, ularning barchasi Hausdorff o'lchoviga ega ${displaystyle eta}$ .^[8]

${displaystyle H_ {eta}, H_ {leq eta}}$ va ${displaystyle H _ {$ barchasi 1 o'lchamdagi qadoqlarga ega.

${displaystyle P_ {eta}, P_ {leq eta}}$ va ${displaystyle P _ {$ barchasi qadoqlash hajmiga ega ${displaystyle eta}$ .

Adabiyotlar

^ John M. Hitchcock; Jek H. Lyuts (2006). "Nima uchun hisoblash murakkabligi yanada qat'iy martellarni talab qiladi". Hisoblash tizimlari nazariyasi.
^ ^a ^b Jek H. Lyuts (2003). "Murakkablik darslarida o'lchov". Hisoblash bo'yicha SIAM jurnali. 32 (5): 1236–1259. arXiv:cs / 0203016. doi:10.1137 / s0097539701417723.
^ ^a ^b ^v Krishna B. Atreya; John M. Hitchcock; Jek H. Lyuts; Elvira Mayordomo (2007). "Algoritmik ma'lumotdagi samarali kuchli o'lchov va hisoblash murakkabligi". Hisoblash bo'yicha SIAM jurnali. 37 (3): 671–705. arXiv:cs / 0211025. doi:10.1137 / s0097539703446912.
^ ^a ^b Jin-yi Cai; Yuris Xartmanis (1994). "Haqiqiy chiziqning Kolmogorov murakkabligining Hausdorff va topologik o'lchamlari to'g'risida". Kompyuter va tizim fanlari jurnali. 49 (3): 605–619. doi:10.1016 / S0022-0000 (05) 80073-X.
^ ^a ^b Lyudvig Stayger (1993). "Kolmogorov murakkabligi va Hausdorff o'lchovi". Axborot va hisoblash. 103 (2): 159–194. doi:10.1006 / inco.1993.1017.
^ Elvira Mayordomo (2002). "Konstruktiv Xausdorf o'lchovining Kolmogorov murakkabligini tavsiflash". Axborotni qayta ishlash xatlari. 84: 1–3. doi:10.1016 / S0020-0190 (02) 00343-5.
^ Lyudvig Stayger (2005). "Konstruktiv o'lchov Kolmogorovning murakkabligiga teng". Axborotni qayta ishlash xatlari. 93 (3): 149–153. doi:10.1016 / j.ipl.2004.09.023.
^ Boris Ryabko (1994). "Kombinatorial manbalarni kodlash va Hausdorff o'lchovi". Sovet matematikasi - Doklady.

J. H. Lutz (2005). "Effektiv fraktal o'lchamlari". Matematik mantiq chorakda. 51 (1): 62–72. CiteSeerX 10.1.1.143.7654. doi:10.1002 / malq.200310127. [1]
J. Reimann (2004). "Hisoblash va fraktal o'lchov, doktorlik dissertatsiyasi". Ruprext-Karls Universität Heidelberg. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering) [2]
L. Stayger (2007). "Cheksiz so'zlarning Kolmogorov murakkabligi". Nazariy kompyuter fanlari. 383 (2–3): 187–199. doi:10.1016 / j.tcs.2007.04.013. [3]

[wccrsm-1] John M. Hitchcock; Jek H. Lyuts (2006). "Nima uchun hisoblash murakkabligi yanada qat'iy martellarni talab qiladi". Hisoblash tizimlari nazariyasi.

[dicc-2] Jek H. Lyuts (2003). "Murakkablik darslarida o'lchov". Hisoblash bo'yicha SIAM jurnali. 32 (5): 1236–1259. arXiv:cs / 0203016. doi:10.1137 / s0097539701417723.

[efsdiaiacc-3] v Krishna B. Atreya; John M. Hitchcock; Jek H. Lyuts; Elvira Mayordomo (2007). "Algoritmik ma'lumotdagi samarali kuchli o'lchov va hisoblash murakkabligi". Hisoblash bo'yicha SIAM jurnali. 37 (3): 671–705. arXiv:cs / 0211025. doi:10.1137 / s0097539703446912.

[caha-4] Jin-yi Cai; Yuris Xartmanis (1994). "Haqiqiy chiziqning Kolmogorov murakkabligining Hausdorff va topologik o'lchamlari to'g'risida". Kompyuter va tizim fanlari jurnali. 49 (3): 605–619. doi:10.1016 / S0022-0000 (05) 80073-X.

[koha-5] Lyudvig Stayger (1993). "Kolmogorov murakkabligi va Hausdorff o'lchovi". Axborot va hisoblash. 103 (2): 159–194. doi:10.1006 / inco.1993.1017.

[akccochd-6] Elvira Mayordomo (2002). "Konstruktiv Xausdorf o'lchovining Kolmogorov murakkabligini tavsiflash". Axborotni qayta ishlash xatlari. 84: 1–3. doi:10.1016 / S0020-0190 (02) 00343-5.

[cdko-7] Lyudvig Stayger (2005). "Konstruktiv o'lchov Kolmogorovning murakkabligiga teng". Axborotni qayta ishlash xatlari. 93 (3): 149–153. doi:10.1016 / j.ipl.2004.09.023.

[rya-8] Boris Ryabko (1994). "Kombinatorial manbalarni kodlash va Hausdorff o'lchovi". Sovet matematikasi - Doklady.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]