Raqamli kutubxona Kibernetikadan matematik masalalar

§ 3. Miqdoriy baholashlar bilan bog'liq
chegara funktsiyalari bilan
1. Chegaraviy funksiyalar soni. Algebra funktsiyalarini amalga oshirishda
mantiqiy sxemalar chegara elementlaridan pol funktsiyalarining Nn soni
n o'zgaruvchida chegara xilma-xilligining tabiiy o'lchovi bo'lib xizmat qiladi
asos qilib beradi va bunday amalga oshirishning murakkabligini baholash imkonini beradi. Bu paydo bo'ldi
Nn ni oxiridan sanash muammosiga jiddiy e'tibor qaratish sababi
ellikinchi. Chunki Nn uchun aniq formulani olish mumkin emas
mumkin tuyuldi, tadqiqot maqsad qilingan
Nn uchun ē - + °° sifatida asimptotik baholarni olish, shuningdek, to'g'ridan-to'g'ri hisoblash
n ning kichik qiymatlari uchun kompyuter yordamida Nn qiymatlari.
§ 2, paragraflarda ta'kidlangan usullar. 1-3, logNn uchun 1965 yilga kelib mavjud edi
asimptotik baholar (6) olindi va asimptotiklar haqida savol tug'ildi
chegara funktsiyalari sonining logarifmi, lekin qandaydir tarzda ularni yaxshilaydi
1989 yilgacha baholash mumkin emas edi. Bunga parallel ravishda, darhol
oltmishinchi yillarning boshlarida bir qancha tadqiqotchilar edi
Nn ning aniq qiymatlari n = 6 gacha hisoblab chiqilgan. Keyingi taraqqiyot
allaqachon murakkab sanash usullari va kuchli kompyuterlarni talab qildi. 1965 yilda g.
Winder [117] N7 sanash natijalarini ma'lum qildi va 1970 yilda Murogoy bilan
hamkasblari [86] shunga o'xshash hisob-kitoblarning natijalarini nashr etishdi
ILLIAC-2 da amalga oshirilgan Nq uchun. Bu ishlarda Nn ni hisoblashdan tashqari
optimal amalga oshirishdagi og'irliklarning qiymatlari o'rganildi va ular ham bor edi
n = 8 gacha bo'lgan barcha to'liq taqqoslanadigan funktsiyalar aniqlandi
chegara hisoblanadi. Ushbu hisob-kitoblarning asosiy natijalari
munosabatlar xulq-atvori uchun chuqur tahlil qilingan
(logNn) / n2 uning asimptotikligini taxmin qilishga urinishda (2-jadvalga qarang).
jadval 2
NS
1
2
3
4
5
6
7
sakkiz
(log Nn) ln *
2
0,95183
0,74449
0,67987
0,66116
0,66225
0,67273
0,68740
Vinder, uning ostona mantiqining rivojlanishiga qo'shgan hissasi tan olinishi kerak
ajoyib, qayta-qayta ifoda etdi, bu natijalar asosida va
uning sezgi, ishonch (log Nn) / n2 -> ■ 1 [116, 117, 119],
ammo ehtiyotkorroq fikrlar ham bor edi [86]. Qattiq dalil
asimptotiklar (7), yangi geometrik natijalar bilan birga
makonni giperplanlar orqali bo'lish dan foydalanishni talab qildi
kuchli ehtimolli kombinatoryal tahlil usullari
faqat oltmishinchi yillarda paydo bo'lgan. Natija e'lon qilindi
muallif [15] va uning to'liqroq taqdimoti 4-teoremaning isboti bilan
[16] da paydo boʻlgan. 4-teoremadan tashqari, asimptotikaning isboti
Odlijkoning [89] tasodifiy (± 1) ishiga tayanadi.
matritsalar.
1967 yilda Komlosh [74] aniqlovchi ekanligini ko'rsatdi
tasodifiy (0, 1) matritsasi deyarli har doim nolga teng. Kelajakda bu
Littlewood - Offord lemmasiga asoslangan dalil,
tomonidan texnik jihatdan takomillashtirilgan (qarang [75]). Uning natijasi
tasodifiy (± 1) -matritsalar uchun amal qiladi. Bu shuni anglatadiki, n
tasodifiy ^ -komponentlari mustaqil bo'lgan o'lchovli vektorlar va
teng darajada 1 yoki -1 qiymatlarini olishi mumkin, deyarli har doim shakllanadi
w o'lchovli fazoda asos. Shuning uchun, har qanday n o'lchovli vektor u, in
Xususan, har qanday (± 1) -vektorni ularning chiziqli shaklida ifodalash mumkin
kombinatsiyalar.
Neyron tarmoqlar nazariyasida yuzaga keladigan muammoni hal qilish [70],
Odlyjko [89] ma'lum ma'noda re to'ldiradigan natijaga erishdi

29-bet

32
uchun. A. ZUEV
Komlos natijasi. U aniqladiki, agar biz n emas, balki p chiziqli pastki fazoda deyarli har doim dan boshqa hech qanday (± 1) -vektor mavjud emas
olingan va ularga qarshi chiqqanlardan. Bundan tashqari, u bu erda bo'lsa-da, ko'rsatdi
bu ishlatilmaydi, bu P ehtimolligida (n, p) bu in
chiziqli pastki fazoda kamida bitta (± 1) -vektor mavjud,
asosiy hissa vektorlarning uchliklarining nolga teng chiziqli birikmalaridan kelib chiqadi. bu
ko'rib chiqilgan ehtimollik uchun aniq asimptotikani topishga imkon berdi
p (n, p) ~ 4 (h) j, p oo.
Komlos va Odlyjko natijalari o'rtasidagi sifat munosabatlari
diskret modeldan o'tish orqali ko'rsatish mumkin
davomiy. ^ -o'lchovli vektorning komponentlari mustaqil va uzluksiz bo'lsin
(-1, 1) oraliqda taqsimlanadi. Keyin, bunday taqsimotdan olib
ixtiyoriy chekli sonli K vektorlar, 1 ehtimollik bilan bizda bunga ega
ularning har qanday n tasi chiziqli mustaqil va har birining chiziqli korpusida
n - 1 qolgan K - n + 1 ni o'z ichiga olmaydi. Shunday qilib
Shunday qilib, Komlosh va Odlyjko natijalari haqiqatdan dalolat beradi
n ortishi bilan tasodifiy (± 1) -vektorlarning xossalari yaqinlashadi
uzluksiz taqsimotdan tanlangan vektorlarning xossalariga.
I.P.Chuxrov Odlijkoning natijasini ko'proq qilishga muvaffaq bo'ldi
shaffof, isbotni soddalashtiradigan, shuningdek, [89] dagi mavjudlarni yo'q qiladi.
noaniqliklar. Uning yaxshilanishlari eskizda qo'llaniladi
zaiflashtirilgan versiya bo'lgan quyidagi lemmaning isboti
Odlijko teoremasi.
Lemma 2. Chiziqli korpusdagi P (n, p) ehtimolligi p
tasodifiy n o'lchovli (± 1) -vektorlar kamida bittasini o'z ichiga oladi
(± 1) -vektor, generatorlardan farqli va ularga qarama-qarshi, ortib borishi bilan
n sifatida p C n (\ - 9,9 / ln n) nolga intiladi.
Isbot. Birinchi navbatda giperplanada e'tibor bering
2 arYy = b9: bu erda barcha PH 0 bo'lsa, kubning [[^ / 2]) dan ortiq cho'qqilari bo'lishi mumkin emas.
y ^ {- 1? 1} p. Littlewu lemmasi sifatida tanilgan bu bayonot
ha - Offord, Spernerning maksimal lemmasidan osongina kelib chiqadi
{- 1, 1} n da juftlik bilan taqqoslanmaydigan uchlari soni. Shuning uchun, o'zboshimchalik uchun
belgilangan qiymatlar a ^ FO va b va tasodifiy y / r - e {- 1, 1}
tenglikning 2 bajarilishi ehtimoli, aYy = & dan oshmaydi [^ nc])
P vektorlar orasida bo'lish ehtimolini P (n, p, mn) bilan belgilaymiz
chiziqli birikmasi nolga teng bo'lmagan mn vektor mavjud
koeffitsientlar (± 1) -vektorni beradi va undan kichikroq raqam yo'q
bu xususiyatga ega vektorlar. Bu mn vektorlar zarur
chiziqli mustaqil; shuning uchun asos mavjud
kichik buyurtma tp. Asosiy kichikning sobit pozitsiyasi bilan
(± 1) -vektorni aniqlovchi chiziqli birikmaning koeffitsientlari yagonadir
asosiy minor ustunlaridagi koordinatalari bilan belgilanadi,
chiziqli birikma qiymatining koordinata bilan mos kelishi ehtimoli
(± 1) -asosiy minorga kiritilmagan ustundagi vektorlar oshmaydi
(lm / 2]) 12 Vt. (p X m) -matritsadagi m tartibli minorni tanlash mumkin
(m) (m) yo'llar va 2n xil (± 1) -vektorlar mavjud, shuning uchun
P (n, p, m) ehtimolligi taxminni qondiradi

30-bet

BOSH FUNKSIYALARI VA BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 33
Endi P (n, p) m ehtimolini quyidagicha baholash mumkin:
P (n, p)
2 P (n, p, t) <2
t = s
t = s
n — t
va bu miqdor, ko'rsatilgandek, p ^ n da n ortishi bilan (l - 9,9 / ln n)
nolga intiladi. Bu dalilning eskizini yakunlaydi.
Endi asosiy natijani shakllantiramiz.
17-teorema [15, 16]. Eshikning Nn sonining logarifmi uchun
Yetarlicha katta n tengsizlik uchun n ta o'zgaruvchining funksiyalari
log Nn> n2 (1 - 10 / 1n n).
Isbot. § 2, 1-bandda ko'rsatilganidek, raqamni hisoblash
chegara funktsiyalarini konusning sonini hisoblash uchun kamaytirish mumkin
En + l gipertekisliklar bilan bo'linadi (8). Biz faqat ko'rib chiqamiz
ao = 0 bo'lgan pol funktsiyalari (4), ya'ni o'z-o'zidan dual. Eslab qoling,
to'g'ridan-to'g'ri (5) dan xulosa qilish oson bo'lgani uchun, ular Nn = Nn - 1 bilan o'chirildi.
O'z-o'zidan ikkilamchi funktsiyalar birma-bir
i?n = (ai, ..., an) bo'shliq joylashgan konuslarga ko'ra
shaklning 2n_1 giper tekisliklari bilan bo'linadi
= B a \ ± a% ± ... ± an = 0. (19)
Ushbu konuslarning soni uchun pastki chegarani olish usuli
chorrahada ekanligini Lemma 2 yordamida ko'rsatishdir
giperplanlarda (19) 2n dan ortiq (1 ~ 10 / 1nD1) chiziqli pastki bo'shliqlar mavjud,
va keyin 4-teoremadan foydalaning.
Biz p = * rc (1 - 9,9 / lnn) ni qo'yamiz va% n to'plamini tasodifiy deb hisoblaymiz
(± 1) -matrices A (pXn), kimning elementlar mustaqil va teng ehtimol bor
1 yoki -1 qiymatlarini oling. 91n to'plami shunday
2pn teng ehtimolli matritsalar. Matritsalar qatorlarini normal deb hisoblasak
giperplanlar vektorlari (19), biz har bir matritsa bilan bog'laymiz
uning qatorlari bilan qoplangan chiziqli pastki fazo chiziqli korpusdir
chiziqlar. Keyin p giper tekisliklarning kesishishi qatorlar bilan belgilanadi
A matritsa normal sifatida chiziqlining ortogonal to'ldiruvchisi bo'ladi
uning satrlarining qobig'i. Bu turli xil sonlarni hisoblash vazifasini kamaytiradi