logo
  1. Главная страница
  2. Дипломные работы
  3. Общий
  4. Panjaraning eng kichik vektorini va berilgan vektorga eng yaqin vektorini topish masalasining algoritmik jihatlari

Panjaraning eng kichik vektorini va berilgan vektorga eng yaqin vektorini topish masalasining algoritmik jihatlari

Загружено в:

12.08.2023

Скачано:

0

Размер:

20578 KB
Скачать
Panjaraning eng kichik vektorini va berilgan vektorga eng yaqin vektorini topish masalasining algoritmik jihatlari MUNDARIJA KIRISH 4 I BOB. PANJARALAR TO’G’RISIDA ASOSIY MALUMOTLAR 6 1-§.Panjaralar. 6 2-§. Ikkita matrisalarni bitta panjarani ifoda etishlari sharti 7 3-§. m-ta chiziqli bog’lanmagan nuqtalar panjara bazisini tashkil etishi ʌ uchun zarur va yetarli shar t 12 4-§. O’zaro panjaralar 13 II BOB. To’plamlar. Panjaralarning fundamental sohalari. 1-§. To’plamlar 18 2-§. Panjaralarning fundamental sohalari 19 3-§. Blixfeladt va Minkovskiy teoremalari 25 4-§. Panjaraning matritsaviy bazisi normasini baholash 26 III BOB. Panjaraning eng kichik vektorini topish algoritmi 1-§. Panjaralar. Gram Shmidt ortogonalizatsiyasi 33 2 -§. Panjaraning eng kichik vektori 34 3 -§. Korkin Zolatarev bazislari 36 4- c –ortogonal bazislar 38 5. Lovasning panjara bazisini keltirish algoritmi 42 6. Algoritmlar 43 XULOSA 58 Foydalanilgan adabiyotlar ro’yxati 1 KIRISH Mavzuning dolzarbligi: O‘zbekiston Respublikasi Prezidentining 2018 yil 5 iyundagi “Oliy ta’lim muassasalarida ta’lim sifatini oshirish va ularning mamlakatda amalga oshirilayotgan keng qamrovli islohatlarda qamrovini faol ishtirokini ta’minlash bo‘yicha qo‘shimcha chora-tadbirlari to‘g‘risida” gi PQ- 3775 Qarorida “Ta’lim sifati professor o‘qituvchilarning bilimi va pedogogik mahorati, talabalarga yaratilgan sharoitlar ustidan tizimli ravishda monitoring o‘rnatish” bo‘yicha asosiy vazifa sifatida belgilandi. 2020 yil 7 maydagi “Matematika sohasida ta’lim sifatini oshirish va ilmiy tadqiqotlarni rivojlantirish chora tadbirlari to‘g‘risida”gi PQ-4708-son qarorida qo‘yilgan vazifalarni hal qilishda “Matematika” fani muta¬xassislar tayyorlashning o‘quv jarayonida yuqori daraja¬dagi matematik tayyorgarligi va ko‘pgina maxsus fanlar bo‘yicha chuqur bilimlar egasi bo‘lishida asosiy o‘rin tutadi. Ushbu magistrlik dissertatsiyasida sonlar geometriyasining dolzarb muammolaridan bo'lgan panjaraning eng kichik vektorini topish algoritmi, shu vektor uzunligini baholash masalalari qarab chiqiladi. Tadqiqotning ob’yekti va predmeti: Tadqiqot obyekti bo‘lib algebraik panjaralar, qism panjaralar, panjaraning eng kichik vektorini qurish masalasi hisoblanadi. Tadqiqot predmeti esa panjaraning eng kichik vektorini topish algoritmlari va uni baholashdan iborat. Tadqiqotning maqsadi va vazifalari: Ushbu ishning maqsadi va vazifalari quyidagicha: algebraik panjaralar va ularning qism panjaralarining xossalarini o'rganish, panjara bazisini qurish, bazis vektorlarini panjaraning bir jinsli minimumi orqali baholash , panjaraning eng kichikvektorini topish lagoritmlari , shu vektorni baholari olishdan iborat. Ilmiy yangiligi: Ishning asosiy yangiliklari quyidagilardan iborat: • Algebraik panjara bazis vektorlari normasining panjara bir jinsli minimumi orqali baholari olingan. • Panjara eng kichik vektorini topish algoritmi ishlab chiqilgan. • Ishlab chiqilgan algoritm kompyuter algebrasi tizimlarida realizatsiya qilingan. Tadqiqotning asosiy masalalari va farazlari: Oxirgi yillarda algoritmlar bilan bog’liq bo‘lgan, algebrik geometriyaning bazaviy abstrakt-nazariy tushunchalarini konkret hisoblanadigan matematik sohalar keng rivojlanmoqda. Magistrlik 2 dissertatsiyasida algebraik panjaralarning bazis vektorlari normasini baholash, panjara eng kichik vektorini hisoblash va baholash algoritmlariga oid masalalar qarab chiqiladi. Tadqiqot mavzusi bo‘yicha adabiyotlar sharhi(tahlili): Ushbu dissertatsiya ishida algebarik panjaralarning xossalari J.W. Cassels. An Introduction to the Geometry of Numbers (Second Printing. Springer-Verlag Berlin, Heidelberg, New York, 1971) m onografiyada berilgan. Sonlar geometriyasining panjaralarga oid tasdiqlar, jumladan, panjaraning bazisi to'g'risidagi ma'lumotlar A.V. Malyshev. The main notions and theorems of the geometry of numbers ( Chebyshevskii sbornik, 2019, vol. 20, no. 3, pp. 43–73 ) s harhiy maqolada ham keltirilgan. Panjaralarning zamonaviy xossalari va panjara bazisiga oid malumotlar P.M. Gruber, C.G. Lekkerkerker, Geometry of numbers ( North-Holland , 1987) kitorbida yetarlicha tahlil qilingan. Panjara bazisi vektorlarining baholariga oid ilmiy natijalar Ruzimuradov Kh.Kh. Fundamental rectangles of admissible lattices ( Journal of Mathematical Sciences. May 1996, Volume 79, Issue 5. pp 1320-1324 ) va Ruzimuradov Kh.Kh. On the problem of counting the number of points of algebraic lattices in rectangles ( Uzbek Mathematical Journal, 2008, No. 4, pp. 116-124 ) maqolalarda olingan. Yuqorida keltirilgan adabiyotlardan foydalanib ushbu magistrlik dissertatsiyasida panjaraning bazis vektorlarinormasi bahosi uning bir jinsli minimumi orqali olingan. Panjaraning eng kichik vektorini hisoblash algoritmlari keltirilgan. Tadqiqotda qo‘llanilgan metodikaning tavsifi: Ishda chiziqli va nochiziqli algebraning usullaridan, to'plamlar nazariyasi metodlaridan , kompyuter algebrasi tizimlaridan foydalanilgan. Tadqiqot natijalarining nazariy va amaliy ahamiyati: Ishda algebraik panjaralarning xossalari qarab chiqilgan bo'lib, barcha olingan natijalar nazariy xarakterga ega. Ishning amaliy ahamiyati shundaki, unda olingan panjar a bazisi vektorlari normasining baholarini panjaraning boshqa xossalarini tadqiq qilishda ishlatish mumkin. Disertatsiya ishining natijalaridan panjaraning eng kichik vetoriga oid masalalarni yechishda foydalanish mumkin. Ish tuzilmasining tavsifi: Dissertatsiya ishi kirish qismi, uchta bob va adabiyotlar ro‘yxatidan iborat. Dissertatsiyaning umumiy hajmi 61 betdan iborat. Kirish qismida masala tarixi, adabiyotlar tahlili kichikcha berilgan, dissertatsiya ishida qilingan ishlar to‘g’risida kichikcha ma’lumotlar berib o‘tilgan va asosiy olingan natijalar bayoni keltirilgan. Birinchi bob sonlar geometriyasining asosiy tushunchalaridan bo'lgan panjaralaraga bag'ishlangan, bu yerda panjaraga oid qiism panjara tushunchasi, 3 panjaraning bazisi tushunchasi, matritsaviy bazis, o'zaro panjara, panjara qatlamlari kabi tushunchalarning bayoni va xossalari keltirilgan. Ushbu tushunchalardan kelgusi boblarda foydalanilgan. Ikkinchi bob panjaraning fundamental sohalari, Blixfeldt va Minkovskiy teoremalariga bag'ishlangan. Ushbu bobda panjara bazisi vektorlari normasining yangi bahosi olingan. Uchinchi bobda panjaraning eng kichik vektoriga oid tushunchalar, panjara bazisining bir qancha formalari, eng kichik vektorni hisoblashga oid algoritmlar keltirilgan Magistrlik dissertatsiyasining asosiy natijalari asosida quyidagi maqola va tezislarda chop qilingan: 1. On an Estimate Related to the Homogeneous Minimum of the Admissible Lattice. ( Ruzimuradov, Poyanova). International Conference on Mathematics and its Scientific Applications. on 3rd March 2022. Sathyabama icmsa. AIP Conference Proceedings. 2. Otsenka normы matrichnogo bazisa dopustimoy reshyotki. Umumta'lim fanlarini asinxron va asinxron bog'lab o'quvchi kreativ faoliyatini rivojlantirishda inegrativ yondashuv. (Respublika ilmiy-amaliy konfrensiyasi materiallari to’plami).- Denov-2022. 4 1-BOB PANJARALAR TO’G’RISIDA ASOSIY MA’LUMOTLAR 1.1. PANJARALAR 1.1-Ta’rif to’plamga panjara deyiladi, bunda -xosmas matritsa, -esa n o’lchovli butun sonli vektorlar to’plamidan iborat. -matritsaga -panjara ba’zisi deyiladi. Agarda (I-birlik matritsa) bo’lsa, panjara ko’rinishga ega bo’ladi, bunga bosh panjara deyiladi. miqdorga panjara hajmi deyiladi. 1.1-Lemma. to’plamning avtomorfizmlari guruxi butun sonli unimodulyar matritsalar to’plami bilan ustma-ust keladi, ya’ni agarda - butun sonli unimodulyar matritsa bo’lsa, bo’ladi. Isbot. Agarda bo’lsa, E- butun sonli unimodulyar matritsa va aksincha, agarda - butun sonli unimodulyar matritsa bo’lsa, bo’lishini ko’rsatamiz. bo’lsin. - butun sonli unimodulyar matritsa bo’lishligini ko’rsatamiz. Teskarisidan faraz qilaylik, ya’ni -matritsaning elementi butun son bo’lmasin. 5 Bu vaqtda to’plamdan shunday vektorni olamizki, uning i - nchi koordinatasi 1 bo’lib, qolgan koordinatalari esa nollardan iborat bo’lsin. matritsa bilan vektorga ta’sir qilamiz. Bu holda vektor hosil bo’ladi. Bu vektorning j- nchi koordinatasi elementdan iborat, shuning uchun . Bu esa degan shartga ziddir. Demak, - butun sonli matritsa ekan. Endi matritsa xosmas ekanligini ko’rsatamiz. Agarda xosmas matritsa bo’lsa, to’plamda n ta chiziqli bo’lmagan nuqtalar bo’lmaydi va to’plamning hamma nuqtalari o’lchovi n- dan kichik bo’lgan fazoda yotadi, bunday bo’lishi mumkin emas. Shuning uchun E xosmasdir. tenglikdan ekanligi kelib chiqadi, bundan hozirgina isbot etilganiga asosan ham butun sonli ekanligi kelib chiqadi. va matritsalar butun sonligidan - matritsa unimodulyar ekanligi kelib chiqadi. Ikkinchi tomondan, agarda butun sonli unimodulyar matritsa bo’lsa, tenglik o’rinli bo’lishini ko’rsataylik. Agarda butun sonli unimodulyar matritsa bo’lsa, u holda bajariladi, bundan ekanligi kelib chiqadi. hamma butun sonli unimodulyar matritsalarni qabul qilsa, ham, hamma butun sonli unimodulyar matritsalarni qabul qiladi. Shuning uchun Lemma isbot bo’ldi. 6 Bu lemmadan foydalanib, ba’zislar haqidagi teoremani isbotlaymiz. 1.2. Ikkita matritsalarni bitta panjarani ifoda etishlari sharti 1.1-teorema. Tartiblari n n bo’lgan ikkita va matritsalar bitta panjarani ifodalaydi, faqat va faqat shu vaqtdaki, agarda shunday sonli unimodulyar matritsa mavjud bo’lsaki, bo’lsa. Isbot va to’plamlar bitta panjarani aniqlasin, bu holda va to’plamlar ustma-ust tushadi. Shuning uchun, lemma 1.1ga asosan matritsa butun sonli unimodulyar matritsadir, ya’ni Aksincha, bo’lsin, 1.1 lemmaga asosan bo’ladi. Shuning uchun Teorema isbot bo’ldi. Natija. panjara hajmi, d(Λ)=|detA| , bazisni tanlab olishga bog’liq emas. Haqiqatdan ham, agarda matritsa panjaraning ikkinchi bazisi bo’lsa , bo’ladi. Bundan, 1.2-Lemma. τ (det matritsa panjaraning avtomorfizmi bo’ladi, faqat va faqat shu holdakim, agarda ko’rinishga ega bo’lsa. 7 Isbot. τ-matritsa panjaraning avtomorfizmi bo’lsin, ya’ni , bu vaqtda bo’ladi. Bundan Lemma 1.1 ga asosan , ya’ni Aksincha, . Panjarani yana quyidagi ko’rinishda yozish mumkin: Bu yerda – lar matritsaning ustunlari, ya’ni . Ta’rif. 1.2 Agar panjaraning har bir nuqtasi, panjaraning ham nuqtasidan iborat bo’lsa, ya’ni bo’lsa, ga panjaraning qismpanjarasi deyiladi. Endi panjarani uning qismpanjarasi bilan bog’laydigan teoremani isbotlaymiz. Teorema.1.2 to’plam panjaraning qism panjarasi bo’lishi uchun, shunday mavjud bo’lishi lozimki, bo’lsin. Isbot : Yetarliligi. M to’plamdan ixtiyoriy elementni olamiz, yani bo’lsin. 8 Bu yerda butun sonli matritsa . Demak, Zaruriyligi . bo’lsin . U holda , esa panjaraning bazisi. matritsaning har bir ustunini n-o’lchovli vektor deb qaraymiz, ya’ni ning ta’rifidan kelib chiqadiki, . U holda ning ta’rifiga asosan shunday vektorlar mavjud bo’ladiki , yoki . ya’ni, bo’ladi, bunda -butun sonli matritsa. Shuning uchun Ta’rif.1.3 Bu songa qismpanjaraning panjaradagi indeksi deyiladi. Teorema. 1.2 dan bir nechta oddiy va foydali natijalar kelib chiqadi. 1- Natija. panjaraning qismpanjarasi bo’lsin. U holda panjaraning shunday bazisi mavjud bo’ladiki, tenglik bajariladi, bu panjara bazisi, yuqori uchburchakli butun sonli matritsa, yani 9 Isbot. M panjara bu panjaraning qismpanjarasi. Shu sababli 1.2 teoremaga asosan shunday butun sonli B matritsa mavjudki, bo’ladi. 1.1 lemmaga asosan B matritsani yuqori uchburchakli matritsa ko’rinishiga keltirish mumkin, ya’ni Bunda E- butun sonli unimodulyar matrisa, hamda . Binobarin, 1.1. ga asosan va matritsalar Λ panjaraning bazislari bo’lganligidan 1 natijaning isboti kelib chiqadi. 2 -natija . -lar panjaraning chiziqli bog’lanmagan nuqtalari bo’lsin. U holda panjaraning shunday ba’zisi topiladiki, 10 bo’ladi, bunda aij -butun sonlar. ( Isbot. panjaraning nuqtalarini shunday tanlab olamizki, vektorlar chiziqli bog’lanmagan bo’lsin. Λ panjaraning bazisi bo’lgan qism panjarasini tekshiramiz , 1- natijaga asosan, bunda yuqori uchburchakli matritsa. 2-natija isbot etildi. Endi bazisi bo’lgan panjara berilgan bo’lsin, uni ko’rinishida yozamiz. n o’lchovli fazoning k -chiziqli bog’lanmagan vektorlari larga tortilgan panjaraning qismfazosini + ni ko’rib chiqamiz. Ta’rif. 1. 4 panjara bilan uning qismfazosining kesilganini panjara k -o’lchovli qatlami deb aytiladi, uni bilan belgilaymiz, ya’ni, miqdorga k-o’lchovli qatlam hajmi deyiladi. 11 Ta’rif. 1.5 z va z bo’lsin. U xolda to’plamni qatlamga parallel bo’lgan panjara qatlami deb ataladi. 1.3 m-ta chiziqli bog’lanmagan nuqtalar panjara bazisini tashkil etishi uchun zarur va yetarli shart Natija 3. lar panjaraning chiziqli bog’lanmagan nuqtalari bo’lsin. nuqtalar panjaraning bazisini tashkil etishlari uchun nuqtalar panjaraning m- o’lchovli qatlamining bazisi bo’lishligi zarur va yetarlidir. Isbot. Agar lar panjara bazisining bir qismi bo’lsa, ravshanki ular panjaraning m-o’lchovli qatlami ning bazisini tashkil etadilar. Aksincha, m-o’lchovli qatlam bazisi bo’lsin va panjarani 2 natijada aniqlangan va sonlarga muvofiq bo’lgan bazisi bo’lsin. 2-natijani qo’llasak , ( bo’ladi. Bundan 12 (1.2.1) deb hisoblash mumkin. Shuning uchun (1.2.1) dan ekanligi kelib chiqadi va demak ( va deb olish mumkin. 3- natija isbot etildi. panjaraning qism panjarasi bo’lgan ni indeksini harakterlaydigan quyidagi lemma o’rinlidir. Lemma. 1.3 . panjara qism panjarasi bo’lgan ni indeksi panjaraning M qismpanjaraga nisbatan qo’shni sinflari soniga tengdir. Isbot . bu - panjaraning qism panjarasi, butun sonli matritsa 1.2 lemmaga asosan panjara bazisi ni va matritsani shunday tanlab olish mumkinki, qismpanjara ushbu ko’rinishga ega bo’ladi: 13 Additiv gruppa ni qism yarimgruppa bo’yicha qo’shni sinflarga ajratamiz. Birinchi sinfga qismpanjara ning hamma elementlari kiradi. Ushbu vektorlar to’plamini qaraymiz. Bu panjarani M qism panjara bo’yicha taqqoslanmaydigan (taqqoslama bo’lmagan) vektorlar to’plamidir. Bunday vektorlar soni ga teng. Ravshanki, panjaraning M qism panjarasiga nisbatan olingan, taqqoslanib bo’lmaydigan vektorlar soni, gruppaning qism gruppasi nisbatan olingan qo’shni sinflar soniga tengdir. U holda, ravshanki, panjaradagi M qismpanjara indeksi formula bilan aniqlanadi, ya’ni indeks panjarani qism panjaraga nisbatan qo’shni sinflar soniga teng ekan. 1.4 O’zaro panjaralar Ta’rif.1.6 panjara uchun matritsaviy bazisi bo’lsin. ga panjaraning o’zaro panjarasi deyiladi O’z navbatida , panjara panjaraga o’zaro panjara bo’ladi. Har qanday va uchun va skalyar ko’paytma butun son ekanligini qayd qilamiz. Eslatma 1. Panjaralarning o’zaroligi bazisni tanlashga bog’liq emas. 14 Haqiqatdan ham, 1.3.1 teoremaga asosan berilgan panjaraning bazislari bir - birlaridan o’ng tomondagi ko’paytma bilan farq qiladilar. Bu ko’paytma esa butun sonli unimodulyar matritsadir. Shuning uchun, agarda matritsa panjaraning biron bazisi bo’lsa, bo’ladi, E esa butun sonli unimodulyar matritsadir. U holda bo’ladi. Bundan eslatmaning to’g’riligi kelib chiqadi. Endi unimodulyar panjara panjaraga o’zaro bo’lsin. Ravshanki panjara ham unimodulyardir. Quyidagi lemmani isbotlaymiz. Lemma 1.4 Har bir primitiv vektor uchun, hajmi bo’lgan panjaraning tartibli qatlami mavjud va bu qatlam vektorga ortogonal bo’lgan qism fazoda joylashgan bo’ladi. Isbot. unimodulyar panjara ning primitiv vektori bo’lsin. U holda 1.2 teoremaning 3- natijasiga asosan, bu vektorni bazisga to’ldirish mumkin. U holda bo’lsin va 15 - panjaraning bazisi bo’lsin. determinantni birinchi ustun elementlari bo’yicha yoyamiz, ya’ni Bunda bo’lganligidan bo’ladi, demak Shuning uchun Shunday qilib biz ko’rsatdikki, o’lchovli qatlamda panjaraning -ta chiziqli bog’lanmagan vektorlari mavjud ekan va bu vektorlar vektorga ortogonal ekan. Bu qatlam hajmini bilan belgilab, uni vektorning uzunligiga teng ekanini ko’rsatamiz. Ma’lumki, ikkinchi tomondan , Shuning uchun 16 panjaraning hajmi esa Bunda yoki kelib chiqadi. Lemma isbot bo’ldi. Ta’rif 1.7 h= miqdorga panjaraning o’lchovli parallel qatlamlari orasidagi masofa deyiladi, bunda esa vektor bilan uchidan tushirilgan perpendikular orasidagi burchak. 1-bob bo’yicha xulosalar Ushbu bobda panjaraning ta’rifi keltirilgan. Panjarani analitik ifodalash, matritsalar yordamida tasvirlash masalalari qarab chiqilgan. Panjaraning turli bazislardagi matritsaviy bazislari orasidagi bog‘lanishlar, chiziqli bog‘lanmagan vektorlar sistemasining panjara bazisini tashkil etishi shartlari, panjara bazis vektorlarining xossalari, o‘zaro panjaralar va ularning xossalari o‘rganilgan. Ushbu materiallar dissertatsiyaishining keyingi boblarida ishlatiladi. 17 2-BOB TO’PLAMLAR. PANJARANING FUNDAMENTAL SOHALARI 2.1 To’plamlar Ta’rif 2.1 fazo ikkita nuqtalari lar ayirmasi panjara ga taaluqli bo’lsa, bularga panjara bo’yicha taqqoslama deyiladi, ya’ni deyiladi, agarda uchun bo’lsa . Ravshanki, agarda bo’lsa, bo’ladi . So’ngra, agarda va bo’lsa, bo’ladi. Ta’rif. 2.2 Agar ya’ni bo’lganda bo’lsa, to’plamga koordinata boshiga nisbatan simmetrik deyiladi. Ta’rif. 2.3 To’plam : da va bir- birlariga bog’liq bo’lmagan holda mos ravishda va to’plamlar elementlarini qabul qilsalar to’plamga va to’plamlar yig’indisi deyiladi va ko’rinishda yoziladi . Lemma 2.1 Agarda va simmetrik to’plamlar bo’lsa ham simmetrik to’plam bo’ladi. Isbot. to’plamni ko’ramiz, bunda , . , bunda bo’lsin. 18 va to’plamlar semmetrik bo’lganligi sababli, va bo’ladi. Bu holda, yig’indi ta’rifiga asosan, bo’ladi.Lemma isbot bo’ldi. Ta’rif. 2.4 Agarda ixtiyoriy nuqtalar va ixtiyoriy 1) son uchun kesma bo’lsa to’plamga qavariq deyiladi. Lemma 2.2 . Agarda va to’plamlar qavariq bo’lsalar to’plam ham qavariq bo’ladi. Isbot. Teskarisidan faraz qilaylik, ya’ni to’plam qavariq bo’lmasin. Ya’ni to’plamning shunday nuqtalari mavjud bo’lsinki, biror 1) son uchun bo’lsin. va to’plamlar yig’indisi ta’rifidan , , va to’plamlar qavariq bo’lganliklari sababli, va bo’ladi. Bundan 2.3 ta’rifga asosan ekanligi kelib chiqadi. Bu esa bizning farazimizga ziddir. Demak, to’plam qavariqdir. 19 2.2. Panjaralarning fundamental sohalari Ta’rif. 2.5 Agar shunday haqiqiy son va z nuqta mavjud bo’lsaki, bo’lsa, tuplam to’plamga o’xshash deb ataladi. Teorema 2.1 Agar o’xshash qavariq va to’plamlar va hajmlarga ega bo’lsalar, munosabat o’rinli bo’ladi . Isbot. Teorema shartiga asosan, va to’plamlar o’xshashdirlar. Shuning uchun haqiqiy son va mavjud bo’ladiki, bo’ladi. Teoremani isbotlash uchun , ( 2.3.1) va (2.2) tengliklarni isbot etish kifoyadir. Birinchi munosabatni isbot etamiz. Ikkinchisi esa birinchisining isbotiga o’xshash bo’ladi.(2.1) tenglik quyidagi munosabatga ekvivalentdir: . 20 Eng avval ekanligini ko’rsatamiz. -ning ixtiyoriy elementi bo’lsin. Bu element to’plamga ham taaluqli ekanligini ko’rsatamiz. Haqiqatdan ham, ∈ S, bo’lganligidan Endi ekanligini ko’rsatamiz. Bu munosabatni isbot etish uchun biz, ning ixtiyoriy elementi ko’rinishda bo’lishini ko’rsatishimiz kerak, bunda . bo’lganligidan, bo’ladi. Demak, . Teorema shartiga asosan S to’plam qavariqdir. Shuning uchun, agarda deb olsak, bo’ladi, yoki , ya’ni bo’ladi. Shunday qilib biz, ekanligini ko’rsatdik. Demak, Teorema isbot bo’ldi. 21 2.1 ta’rifda biz nuqtalarning panjaraga nisbatan taqqoslamaligini bergan edik. fazo nuqtalarini sinflarga shunday bo’lish mumkin: Ikki y va nuqtalar taqqoslanuvchi bo’ladilar shu vaqtdaki, agarda ular bir sinfga taaluqli bo’lsalar. Sinf ko’rinishi bo’lgan nuqtalardan iborat, bunda shu sinfning biror fiksirlangan nuqtasidan iborat. Z esa panjaraning hamma qiymatlarini qabul qiladi. Agarda , bo’lsa ravshanki, bo’ladi. Agarda va bo’lsa bo’ladi. Shunday qilib biz sinflar yig’indisi va sinfni ixtiyoriy songa ko’paytirishni aniqladik. simvollar bilan har biridan bittadan olingan qo’shni sinflar komplektini belgilaymiz va uni Λ panjaraning fundamental sohasi deb ataymiz. Ta’rif. 2.5 to’plamga panjara Λ ning fundamental sohasi deyiladi, agarda u ikki xossani qanoatlantirsa: 1. Har qanday nuqta uchun, shunday topilsaki, bo’lsa. 2. Agar va bo’lganda bo’lsa. Ta’rif. 2.6 matritsa panjaraning biror ba’zisi bo’lsin, va lar shart bilan bir-birlariga bog’liq bo’lmagan holda haqiqiy qiymatlarni qabul qilsinlar. U holda to’plamga fundamental parallelepepid deydiki, ya’ni bu dir. 22 Lemma. 2.3 to’plamni ichiga kirmog’i uchun , to’plam ning bo’sh bo’lmasligi zarur va yetarlidir, bunda . Isbot. Teskarisidan faraz qilamiz, ya’ni ixtiyoriy uchun bo’sh bo’lmasin, ammo bo’lsin. U holda fazoda shunday mavjud bo’ladiki, y S to’plamning hech bir nuqtasi bilan taqqoslanmaydi. Endi to’plamni qaraymiz. Bu to’plam panjara nuqtalarini o’z ichiga olmaydi, bu esa lemma shartiga ziddir. Lemma isbot bo’ldi. Eslatma. 2 to’plam ni o’z ichiga olishligi uchun to’plam ni qoplashi zarur va yetarlidir. Zaruriyligi. bo’lsin. qo’shni sinflar ta’rifidan kelib chiqadiki, to’plam fazoni qoplaydi, bunda esa panjaraning hamma nuqtalarini qabul qiladi. U holda munosabatdan kelib chiqadiki, to’plam fazoni qoplovchi ekan. Yetarliligi . to’plam -ni qoplasin, ammo bo’lsin, ya’ni teskarisidan isbot qilamiz. munosabat, fazoda shunday nuqta mavjudki, u to’plamni hech bir nuqtasi bilan taqqoslanmaydi degan so’z bilan teng ko’chlidir, ya’ni (ixtiyoriy uchun ), yoki 23 Bu esa to’plam ni qoplashiga ziddir. Eslatma.3 S to’plamni bilan ustma -ust tushishi uchun, to’plam ni bo’sh joy qoldirmasdan qoplamog’i zarur va yetarlidir. Isbot. Zaruriyligi. bo’lsin. Bu vaqtda ko’rsatish kerakki, to’plam fazoni bo’sh joy qoldirmasdan qoplaydi. Buning uchun to’plam fazoni bo’sh joy qoldirmasdan qoplashini ko’rsatsak kifoyadir, bunda nuqta panjara hamma nuqtalarini qabul qiladi. Ya’ni, har qanday nuqta, berilgan bo’yicha faqat yagona to’plamga taaluqli bo’ladi. Agarda ikkita va to’plamlarga taaluqli bo’lsa ( ), bundan kelib chiqadiki, yagona nuqta ikkita qo’shni sinflarga taaluqli bo’ladi. Bu - ning ta’rifiga ziddir. Yetarliligi . to’plam ni bo’sh qoldirmay qoplasin. Bu vaqtda 3- eslatmaga asosan bo’ladi. Ikkinchi tomondan to’plam bo’sh qoldirmasdan qoplaydi. Shuning uchun 3-eslatmaga asosan bo’ladi. Demak, . Eslatma isbot bo’ldi. panjara va haqiqiy matritsa bo’lsin, bu vaqtda bilan matritsaviy bazisi bo’lgan panjarani tushunamiz. 24 Agarda haqiqiy son bo’lsa, bilan panjarani tushunamiz. Buning determinanti ga tengdir. bilan ∈ nuqta koordinatalari ko’paytmasining modulini belgilaymiz, ya’ni . bilan panjara bir jinsli minumumini belgilaymiz, ya’ni Istalgan uchun , N(Λ+Z) bilan vektorga siljigan Λ panjarani belgilaymiz, ya’ni N(Λ+Z)=inf N(Y) M(Λ) simvoli bilan birjinslimas minumumni belgilaymiz, ya’ni M sup N((Λ)+Z) Eslatma 4. Λ panjara da n-o’lchovli bo’lsin. Har qandayn-o’lchovli xosmas diagnal matritsa uchun tenglik o’rinli bo’ladi. Isbot. D= detD= 25 bo’lsin. U holda ta’rifi bo’yicha Eslatma 5. Λ panjara da n-o’lchovli va D esa n-o’lchovli xosmas diagnal matritsa bo’lsin. Bu vaqtda , Tenglik o’rinli bo’ladi. Isbot. Ta’rifga asosan, Shuni qayd qilamizki, agarda bo’lsa, shunday mavjud bo’ladiki, va bo’ladi. Shuning uchun 4-eslatmaga asosan Bundan, ta’rifini hisobga olib, 26 2.3. Blixfeldt va Minkovskiy teoremalari Teorema 2.1. Λ panjara hajmga ega bo’lsin, -nuqtali to’plam bo’lib, hajmi bo’lishi mumkinligi, agarda bo’lsa, to’plam panjaraning ikkita har xil va nuqtalarni o’z ichiga oladiki, bu nuqtalar ayirmasi panjara ga taaluqli bo’ladi. Isbot. panjaraning istalgan bazisi bo’lsin, P -Fundamental parallelopiped ya’ni , bunda nuqtalar to’plami va shartni qanoatlantirsin. Ravshanki, to’plam ni to’liq qoplaydi. bilan (Zpanjaraning hamma nuqtalarini qabul qiladi), P+Z yotgan T to’plam qismini belgilaymiz, bu vaqtda T Shuning uchun hajm uchun tenglik . Teorema shartiga ko’ra . Shuning uchun . Demak, hech bo’lmaganda bitta nuqta topiladiki, 27 Bunda . Demak, bo’ladi. Teorema isbot etildi. Teorema 2. 2 (Minkovskiyning umumlashgan teoremasi.) T markaziy simmetrik nuqtalar to’plami, uning hajmi bo’ishi mumkin), esa hajmi bo’lgan panjara bo’lsin. Agarda bo’lsa to’plam hech bo’lmaganda Λ panjarani bitta noldan farqli nuqtasini o’z ichiga oladi . Isbot. bo’lganligi sababli Blixfeladt teoremasiga asosan T to’plam ikkita har xil nuqtalarni o’z ichiga oladi . bo’ladi. Shartga asosan T markaziy simmetrik to’plam bo’lganligi uchun, T to’plam nuqta bilan - nuqtani ham o’z ichiga oladi. To’plamlar yig’indisi ta’rifiga asosan nuqta to’plamga taaluqli bo’ladi . Teorema isbot etildi. Teorema 2.3 (Minkovskiy teoremasi.) T- qavariq markaziy simmetrik , hajmi bo’lgan nuqtali to’plam bo’lsin . bo’ishi mumkin), esa hajmi bo’lgan panjara bo’lsin. Agarda bo’lsa to’plam Λ panjaraning noldan farqli , hech bo’lmaganda bitta nuqtasini o’z ichiga oladi. 28 Isbot. T to’plamni olamiz. T qavariq to’plam bo’lganligidan bo’ladi. T to’plam T)=detΛ hajmga ega . 3.2 teoremaga asosan , to’plam panjarani hech bo’lmaganda bitta noldan farqli nuqtasini o’z ichiga oladi. Teorema isbot etildi. Ta’rif. 2.1 Shunday son mavjud bo’lib, T to’plamning hamma nuqtalari shartda yotgan bo’lsalar, T to’plamga chegaralangan deyiladi . Ta’rif. 2.2. Agarda ) ketma -ket nuqtalar - to’plamga taaluqli bo’lib, bo’lsa, ya’ni nuqtaning har bir koordinatasi nuqtaning mos koordinatasiga intilganda bo’lsa, T to’plamga yopiq deyiladi. Teorema 2.4 (Minkovskiy teoremasi.) T markaziy simmetrik , qavariq ,yopiq, chegaralangan, va hajmi bo’lgan nuqtali to’plam bo’lsin . esa hajmi bo’lgan panjara bo’lsin. Agarda bo’lsa , T hech bo’lmaganda Λ panjaraning noldan farqli bitta nuqtasini o’z ichiga oladi . Isbot. to’plami bo’lganda hajmga ega. 3.3.3.teoremaga asosan to’plam, va demak to’plam bo’lgan panjara nuqtasini o’z ichiga oladi. 29 T to’plam chegaralangan bo’lganligidan panjaraning faqat chekli nuqtalari nuqta rolida uchrashishi mumkin. Demak, bulardan biri, masalan nuqta da uchun uchrashuvi mumkin. Demak, bo’ladi, har qanday kichik uchun. bo’ladi, chunki T yopiq to’plam . Teorema 3.5 fazoda unimodulyar panjara va qavariq markaziy simmetrik va hajmi bo’lgan S to’plam berilgan bo’lsin. Bu holda hech bo’lmaganda ikkita da’vo o’rinli bo’ladi: S noldan farqli panjaraning nuqtasini o’z ichiga oladi; S to’plam ni o’z ichiga oladi. Isbot. -yetarli darajada kichik va musbat son bo’lsin. fazoni Z nuqtasi shunday olingan bo’lsinkim, bo’lsin. to’plamni qaraymiz. Ravshanki, G geometrik to’plami va 30 Lemma(3.3 ) ga asosan, boshlang’ich nuqtadan farq qiladigan Λ panjaraning nuqtasini o’z ichiga oladi. S qavariq bo’lganligi sababli , bo’ladi.(lemma 2.1 ga asosan).Shuning uchun . Shuning uchun, yoki S o’z ichiga ning bosh’lang'ich nuqtadan farqli nuqtasini o’z ichiga oladi, yoki aks holda ( Z nuqta istalgan bo’lganligidan) 4-eslatmaga asosan, S ⊃ Z bo’ladi. Teorema isbot etildi. Teorema 3.6 fazoda unimodulyar panjara va markaziy simmetrik qavariq S to’plam berilgan bo’lib, uning hajmi bo’lsin, hamda S to’plamning faqat chegarasi Λ panjara nuqtalarini o’z ichiga olsin. U holda to’plam ni o’z ichiga oladi.(bunda S esa S ning yoyilmasidan iborat). Isbot. fazoning ixtiyoriy nuqtasi Z bo’lsin va Z shunday tanlab olingan bo’lsinki, bo’lsin. to’plamni qaraymiz. Ravshanki, G simmetrik to’plam va . 31 lemmaga asosan , boshlang’ich nuqtadan boshqa nuqtani o’z ichiga oladi. S-qavariq bo’lganligi sababli, , bo’ladi . Shuning uchun . -istalgan kichik son bo’lganligidan, S to’plam Λ panjaraning nuqtalarini o’z ichiga olmaydi, hamda Z ixtiyoriy nuqta. Shuning uchun, . Bu teorema Mordell teoremasi bo’lib, ko’p masalalarda qo’llaniladi, masalan, o’zgaruvchiga bog’liq bo’lgan uchta chiziqli formalar ko’paytmasi masalasiga tadbiq qilinadi. 2.4. Panjaraning matritsaviy bazisi normasini baholash panjara matritsaviy bazisga ega bo‘lsin, uning hajmi dan iborat bo‘ladi. 32 bo‘lsin, bu yerda ; bilan miqdorni belgilaymiz. 1 ta’rif. ([1]) ni panjaraning bir jinsli minimumi deb ataymiz. panjarani shartda mumkin bo‘lgan panjara deb ataymiz. Bu yerda Chebishevning maksimal yoki cheksiz normasini (norma Chebishyova [2]): , to shaklda kiritamiz. Ushbu paragrafda panjaraning matritsaviy bazisi normasininng panjara bir jinsli minimumi orqali bahosi olinadi. Quyidagi teoremani qaraymiz. Teorema. panjara uchun va bo‘lsin. U holda faqat bir jinsli minimudan bog‘liq bo‘lgan shunday o‘zgarmas mavjudki, bo‘lganda tengsizlik o‘rinli bo‘ladi. Teoremani isbot qilish uchun quyidagi eslatma va lemmadan foydalanamiz Eslatma 1. [5] Shunday o‘zgarmas mavjudki, qirralari koordlinata o‘qlariga parallel bo‘lgan va hajmga ega bo‘lgan parallelepiped panjaraning nuqtalarini o‘zida saqlamaydi. Lemma -1. [5] Elementlari haqiqiy sonlardan iborat bo‘lgan . matritsa berilgan bo‘lsin. Agar bu matritsa elementlari uchun quyidagi shartlar o‘rinli bo‘lsa, 33 u holda bo’ladi. T e oremani isbot qilish uchun quyidagi parallelepipedlar ketma-ketligini quramiz : bu parallelepipedning hajmi dan iborat bo‘lib, uning birinchi qirrasi shartni qanoatlantirsin. matritsani shunday tanlaymizki, . , tengliklar o‘rinli bo‘lsin va hosil bo‘lgan parallelepipedning hajmi bo‘ladi, bu yerda deb olamiz. O‘xshashlik almashtirish yordamida parallelepipedning birinchi koordinata o‘qiga parallel bo‘lgan tomonini hajmi panjara asosiy parallelepiped hajmidan katta bo‘lgunga qadar cho‘zamiz, natijada shunday soni topiladiki, panjaraning nuqtasini o‘z ichida saqlaydigan eng kichik parallelepiped quyidagicha bo‘ladi: Bu parallelepipedning hajmi shartni qanoatlantiradi va bu yerda deb olamiz. nuqta quyidagi koordinatalarga ega bo‘lsin . U holda bo‘ladi. So‘ngra, ning ikkinchi koordinata o‘qiga parallel bo‘lgan tomonini o‘xshashlik almashtirish yordamida cho‘zib, panjaraning yana bir vektorini hosil qilamiz: 34 , bu yerda Xuddi shunday parallelepipedning qolgan koordinata o‘qlariga mos keluvchi tomonlarini mos ravishda o‘xshashlik almashtirishlari yordamida cho‘zib, shu jumladan, –nchi koordinata o‘qiga mos keluvchi oxirgi : s vektorni hosil qilamiz, bu yerda shart o‘rinli bo‘ladi. Faraz qilaylik, yuqoridagidek qurilgan parallelepipedlardan eng katta tomonga tega bo‘lgan parallelepiped bo‘lsin. U holda yuqorida hosil qilingan vektorlarning hammasi tomoni ga teng bo‘lgan kubga tegishli bo‘ladi. 1-lemmaga asosan bu vektorlar panjaraning ta chiziqli bog‘lanmagan vektorlari sistemasini tashkil qiladi. Endi panjara ko‘rinishdda bo‘lsin. U holda vektorlar sistemasini panjaraning qism panjarasi ning bazisi sifatida qarash mumkin.. Birinchi bobning 1.7.-lemmasiga asosan [1] bu qism panjarani quyidagi shaklda tasvirlashimiz mumkin bo‘ladi , bu yerda – butun sonli matritsadlan iborat. bo‘lsin. S matritsaning normasini baholaymiz. Barcha vektorlar tomonining uzunligi ga teng bo‘lgan kubda yotganligi uchun, har bir vektorning uzunligi kub qirrasining uzunligidan katta emas, ya’ni . (1) Qaralayotgan parallelepipedning hajmi bo‘lganligi uchun . (2) 35 tengsizlikni hosil qilamiz. shartdan shunday ning mavjudligi kelib chiqadiki, tenglik o‘rinli bo‘ladi. Bu yerdan . tengliklarni hosil qilamiz. ning qiymatini (2) ga qo‘yib , . Bu yerdan . (3) ni hosil qilamiz. (2) va (3) tengsizliklardan , (4) ni hosil qilamiz, bo‘lganligi uchun (4) dan quyidlagini hosil qilamiz . (5) Endi matritsaning normasini baholaymiz. unimodulyar matritsa mavjudki, bo‘ladi. Birinchi bobning 1.1-lemmasiga asosan matritsani shunday tanlaymizki, (6) tenglik va munosabatlar o‘rinli bo‘lsin. teskari matritsani topamiz. (6) tengikdan quyidagini hosil qilamiz: 36 (7) bu yerda munosabatlar o‘rinli bo‘ladi. U holda tengsizlikni hisobga olsak, (8) bahoni hosil qilamiz. bo‘lganligi uchun (9) dan . munosabatni hosil qilamiz. Bu yerdan va (5) tengsizlikdan munosabatni hosil qilamiz. Bu esa teorema shartidagi tengsizlikdan iborat. 2-bob bo‘yicha xulosalar Ushbu bobda tshplamalar va panjaraldar orasidagi munosabatlar, ba’zi qavariq to‘plamalarning xossalari, panjaraning fundamental sohalari, panjara bir jinsli minimumi va ba’zi baholari qarab chiqilgan. Panjara va to‘plamlarga oid Blixfeldt va Minkovskiy teoremalari keltirilgan. Bu bobning asosiy natijasi quyidagi teoremadan iborat. Teorema. panjara uchun va bo‘lsin. U holda faqat bir jinsli minimudan bog‘liq bo‘lgan shunday o‘zgarmas mavjudki, bo‘lganda tengsizlik o‘rinli bo‘ladi. 37 3-BOB. PANJARANING ENG KICHIK VEKTORINI TOPISH ALGORITMI 3.1 Panjaralar. Gram Shmidt ortogonalizatsiyasi vektorlar m o’lchovli Evklid fazosida ba’zi bir chiziqli mustaqil vektorlar bo’lsin. panjarani qaraymiz. -matritsaning bazisi, n-esa matritsaning o’lchami yoki rangi. Bu matritsa Gram-Shmidt matritsasi deb ataladi. 38 . songa panjara determinanti deyiladi. Panjara determinanti vektorlarga tortilgan parallelepiped hajmiga teng. Agar bo’lsa, u holda det ko’rish mumkin bo’lib, bunda vektorlar biror ortonormal bazisdagi koordinatalardan tuzilgan matritsa. Panjaraning bazisi yagona emas, lekin panjaraning bir bazisdan ixtiyoriy boshqasiga o’tish matritsasi unimodulyar ekanligini ko’rish mumkin, ya’ni bu unimodulyar matritsa determinanti ga teng. Shuning uchun panjara determinanti bazisni tanlashga bog’liq emas. vektorlarga Gram Shmidt ortogonalizasiya jarayonidagi vektorlar bo’lsin: (k=1,2,...,n) (1) bunda bunda (2) vektorning pastki fazoga ortogonal proyeksiyasi. 39 . vektorning qism fazoning ortogonal to’ldiruvchisiga proyeksiyasidan iborat ekanligini ko’rish mumkin. Bundan qism fazoning ortogonal bazis ekanligi xususiy holda kelib chiqadi. ( panjaraning bazisi emas, chunki panjaraga tegishli emas.) Lemma 1. ( Adamar tengsizligi) panjaraning biror bazisi , Ʌ bu vektorlar yordamida Gram- Shmidt ortogonallashtirish natijasida hosil bo’lgan vektorlar bo’lsin(1),(2). U holda tengsizlik o’rinli. 3.3 Panjaraning eng kichik vektori Lemma 2. - panjaraning biror bazisi, Ʌ - Gram - Shmidt ortogonallashtirish natijasida olingan vektorlar bo’lsin.(1), (2.) U holda , Bu yerda Ʌ -panjaraning eng kichik vektori uzunligi. Isbot.x eng kichik vektorni (3) bu yerda (3) . 40 j- shart bajariladigan eng katta indeks bo’lsin. (3) tenglikning barcha qismlarini bj* ga skalyar ko’paytirib, ni olamiz. bo’lgani uchun kelib chiqadi. Shuning uchun, | | Gaus qisqartirish algoritmi(n=2) Ikki o’lchovli panjara eng kichik vektorini qurishning Gaus algoritmini qaraymiz. procedure Gauss-Reduction (var b 1 ,b 2 ) repeat if | | end q shunday topiladiki, minimal uzunlikka ega bo’lsin; if q=0 return end ; 41 end end. Ravshanki, algoritm chiqishida vektorlar panjara bazisini tashkil etadi. Oddiy geometrik mulohazalar shuni ko’rsatadiki, bunda b 1 panjaraning eng kichik vektori va b 2 –b 1 shunday burchak hosil qiladi. Eng kichik vektorning xossalari. Eslatma. 3 Panjaraning eng kichik vektorning izlash masalasi -qiyin hisoblanadi. Teorema 3.4 .(SH.Ermit,sm 2) -L panjaraning eng kichik vektorining uzunligi bo’lsin. U holda (4) Bu yerda faqat n ga bog’liq biror kattalik. 5.Eslatma. (4) bahoga erishiladigan ning qiymati Ermit konstantasi deb ataladi. Ma’lumki, uning uchun n asimptotik baho va (5) 42 aniq tengsizlik o’rinli, shuning uchun (6) ?????? ning aniq qiymati faqat unchalik katta bo’lmagan n lar uchun ma’lum. , , , quyidagi xossani qanoatlantiruvchi ning vektorlari bo’lsin. ga tegishli bo’lgan, lekin L(b 1 ,...b k-1 ) ga tegishli bo’lmagan vektorlar orasida b k vektor minimal uzunlikka ega. (k=1,2,...,n) , (L( deb hisoblaymiz. Ravshanki, u holda vektorlar panjaraning bazisini tashkil etadi. Bu bazis Minkovskiy bo’yicha keltirilgan deb ataladi, bunda b k -panjaraning k-chi ketma -ket bazisi deyiladi. Teorema. 3.5 [2] Minkovskiy bo’yicha keltirilgan bazis uchun (7) o’rinli, bu yerda Ermit konstantasi. Xususan, (5) dan (8) kelib chiqadi. 7-Eslatma. (7) tengsizlik Minkovskiy bo’yicha keltirilgan bazis, ortogonal bazisga yaqin ekanligini ko’rsatadi. 43 3.3 Korkin-Zolotarev bazislari. - vektorlar(1), (2) ortogonallashtirish natijasida panjaraning bazisidan olingan vektorlar bo’lsin. panjaraning bazisi Korkin-Zolotarev bo’yicha keltirilgan deyiladi, agar -panjaraning eng kichik vektoriki: -panjaraning shunday nol bo’lmagan vektoriki, L( ) ga ortogonal to’ldiruvchiga ning proyeksiyasi minimal bo’lsa (k=1,2,...n) ( ) 3.4 c-ortogonal bazislar. (8) tengsizlik yangi tushuncha kiritilishini asoslaydi. bazis c- ortogonal yoki Lenstra bo’yicha c-keltirilgan deyiladi. [5], agar o’rinli bo’lsa. Adamar tengsizligidan da c-ortogonal bazis mavjud emas. da esa bu tushuncha ortogonallikka aylanadi. 6-teoremadan ixtiyoriy panjara uchun da c ortogonal bazis mavjudligi kelib chiqadi. Tayinlangan n da uchun c- ortogonal bazisni topishni birinchi polinomial algoritmi X.Lenstra [9] , c-ortogonal bazisni qurishni birinchi polinomial algoritmini L.Lovas taklif etgan. 44 Endi c- keltirilgan bazis tushunchasini kiritamiz. vektorlar (1), (2) ortogonallashtirish natijasida panjaraning bazisidan olingan bo’lsin. bazis c-keltirilgan (Zegel bo’yicha) [5] deyiladi, agar (9) (k=2,3,...,n) (10) o’rinli bo’lsa. Keyinchalik c-keltirilgan bazis c-ortogonal bo’lishini ko’ramiz. Teskarisi o’rinli emas. Masalan: bazis c=2 da ortogonal, lekin c-keltirilgan emas. Haqiqatdan uning uchun , , , tenglik bajariladi. tengsizlik bajarilmaydi. Ma’lumki [2] , da ixtiyoriy panjara uchun c-keltirilgan bazis mavjud. Uning da mavjudligi quyida keltiriladigan maxsusroq bazisni qurish algoritmidan ham kelib chiqadi. Dastlab c-keltirilgan bazis deyarli bir-biriga ortogonal kichik vektorlardan iborat ekanligini ko’rsatuvchi ba’zi formal bo’lmagan mulohazalarni keltiramiz. 45 (9) shart vektorning vektorga proeksiyasi uzunligi vektorga nisbatan unchalik katta bo’lmasligi lozimligini anglatadi. Bu shart agar, vektor ga deyarli ortogonal yoki vektor uzunligi vektor uzunligiga nisbatan kichik bo’lsa bajariladi. Shunday qilib, (9) shart bazis deyarli ortogonal vektorlardan iboratligini anglatmasligi mumkin. Masalan, - juda uzun vektor, a ga nisbatan kichik, a ga nisbatan kichik va hokazo bo’lganda vaziyat bo’lishi mumkin. Lekin bu vaziyatning amalga oshirilishiga c-keltirilgan bazisda vektorlar uzunligi “deyarli kichraymasligini” ( vektor uzunligi vektor uzunligiga nisbatan unchalik kichik emas) anglatuvchi (10) shart to’sqinlik qiladi. ......... Teorema. 2.7 -panjaraning c-keltirilgan bazisi, bo’lsin, u holda (11) (12) Isbot . (11) dagi birinchi tengsizlik bu Adamar tengsizligidir. Ikkinchi tengsizlikni isbotlaymiz. (1),(2) Gram -Shmidt ortogonallashtirish natijasida dan olingan vektorlar bo’lsin. (10) dan ...... (13) kelib chiqadi. 46 Shuning uchun va ga ko’ra | ga ega bo’lamiz. Demak, Endi (12) ni isbotlaymiz. (13) va (14) dan kelib chiqadi. Xususan, , bu tengsizliklarni ko’paytirib, ni olamiz. Bundan (12) kelib chiqadi. 9-Eslatma. (11) dan c-keltirilgan bazis ortogonal bo’lishi kelib chiqadi. Teskarisi umuman olganda noto’g’ri. 47 10-Eslatma .(11) va (12) formulalarni (4), (6) va (7) ,(8) formulalar bilan mos ravishda taqqoslash, c-keltirilgan bazis Menkovskiy bo’yicha keltirilgan bazisni qanoatlantiradigan ba’zi muhim xossalarga ega bo’lishini ko’rsatadi. Teorema. 3.9 panjaraning keltirilgan bazisi, - eng kichik vektor uzunligi bo’lsin. U holda (15) Isbot. 2-Lemmaga ko’ra. , , Lekin Shuning uchun bundan talab qilinganga ega bo’lamiz. 12- Eslatma. (15) tengsizlik, - panjaraning eng kichik vektoridan biri ekanligini ko’rsatadi. Bu teoremani isbotlashda biz (9) xossadan foydalandik. 13-mashq. Agar da chiziqli bog’lanmagan vektorlar bo’lsin. da U holda da c-keltirilgan bazisni qurishni polinomial algoritmi [4] da keltirilgan. 48 3.5 Lovasning panjara bazisini keltirish algoritmi panjaraning bazisidan (1),(2) ortogonallashtirish natijasida olingan bo’lsin. bazis Lovas bo’yicha c-keltirilgan deyiladi, c da agar, (16) (k=2,3,...,n) (17) munosabat o’rinli bo’lsa. Shunday qilib, Lovas bo’yicha c-keltirilgan bazis ta’rifi, c-keltirilgan bazis tarifidan (10) shartni (17) shart bilan almashtirish bilan hosil qilinadi. Keyinchalik ko’ramizki, (17) shart (10) ga qaraganda ko’chliroq. Adabiyotlarda bunday bazislar ko’pincha (ayniqsa, ) y=bo’yicha LLL-keltirilgan deb ataladi. Agar, bo’lsa, u holda bo’ladi. vektorning ortogonal to’ldiruvchiga proyeksiyasi bo’lgani uchun (17) shart bu proyeksiya ning bu ortogonal to’ldiruvchiga proyeksiyasiga qaraganda unchalik kichik emasligini bildiradi. (17) shart (k=2,3,...,n) (18) tengsizliklar teng kuchli. (16) va (18) dan, (10) tengsizlikni oson hosil qilish mumkin. 49 Shunday qilib, Lovas bo’yicha c-keltirilgan bazis c-keltirilgan bo’ladi. Teskarisi o’rinli emas.Masalan: bazis (u ortogonal) , uchun c- keltirilgan, lekin Lovas bo’yicha c-keltirilgan emas, chunki bu holda tengsizlik bajariladi. tengsizlik esa yo’q. c-ortogonal bazis Lovas bo’yicha c-keltirilgan bazis 3-BOB. PANJARANING ENG KICHIK VEKTORINI TOPISH ALGORITMI 3.1 Panjaralar. Gram Shmidt ortogonalizatsiyasi vektorlar m o’lchovli Evklid fazosida ba’zi bir chiziqli mustaqil vektorlar. panjarani qaraymiz. 50 -matritsaning bazisi, n-esa matritsaning o’lchami yoki rangi . Bu matritsa Gram-Shmidt matritsasi deb ataladi. . ga panjara determinanti deyiladi. Panjara determinanti vektorlarga tortilgan parallelepiped hajmiga teng. Agar bo’lsa, u holda det ko’rish mumkin bo’lib, bunda vektorlar biror ortonormal bazisdagi koordinatalardan tuzilgan matritsa. Panjaraning bazisi yagona emas, lekin panjaraning bir bazisdan ixtiyoriy boshqasiga o’tish matritsasi unimodulyar ekanligini ko’rish mumkin, ya’ni bu unimodulyar matritsa determinanti ga teng. Shuning uchun panjara determinanti bazisni tanlashga bog’liq emas. vektorlarga Gram Shmidt ortogonalizasiya jarayonidagi vektorlar bo’lsin: (k=1,2,...,n) (1) bunda bunda (2) 51 vektorning pastki fazoga ortogonal proyeksiyasi. . vektorning qism fazoning ortogonal to’ldiruvchisiga proyeksiyasidan iborat ekanligini ko’rish mumkin. Bundan qism fazoning ortogonal bazis ekanligi xususiy holda kelib chiqadi. ( panjaraning bazisi emas, chunki panjaraga tegishli emas.) Lemma 1. ( Adamar tengsizligi) panjaraning biror bazisi , Ʌ bu vektorlar yordamida Gram- Shmidt ortogonallashtirish natijasida hosil bo’lgan vektorlar bo’lsin(1),(2). U holda tengsizlik o’rinli. 3.3 Panjaraning eng kichik vektori Lemma 2. - Ʌ panjaraning biror bazisi, - Gram - Shmidt ortogonallashtirish natijasida olingan vektorlar bo’lsin.(1), (2.) U holda , Bu yerda Ʌ -panjaraning eng kichik vektori uzunligi. Isbot.x eng kichik vektorni (3) 52 bu yerda (3) . j- shart bajariladigan eng katta indeks bo’lsin. (3) tenglikning barcha qismlarini bj* ga skalyar ko’paytirib, ni olamiz. bo’lgani uchun kelib chiqadi. Shuning uchun, | | Gaus qisqartirish algoritmi(n=2) Ikki o’lchovli panjara eng kichik vektorini qurishning Gaus algoritmini qaraymiz. procedure Gauss-Reduction (var b1,b2) repeat if | | end q shunday topiladiki, minimal uzunlikka ega bo’lsin; if q=0 return 53 end ; end end. Ravshanki, algoritm chiqishida vektorlar panjara bazisini tashkil etadi. Oddiy geometrik mulohazalar shuni ko’rsatadiki, bunda b 1 panjaraning eng kichik vektori va b 2 –b 1 shunday burchak hosil qiladi. Eng kichik vektorning xossalari. Eslatma. 3 Panjaraning eng kichik vektorning izlash masalasi -qiyin hisoblanadi. Teorema 3.4 .(SH.Ermit,sm 2) -L panjaraning eng kichik vektorining uzunligi bo’lsin. U holda (4) Bu yerda faqat n ga bog’liq biror kattalik. 5.Eslatma. (4) bahoga erishiladigan ning qiymati Ermit konstantasi deb ataladi. Ma’lumki, uning uchun n 54 asimptotik baho va (5) aniq tengsizlik o’rinli, shuning uchun (6) ?????? ning aniq qiymati faqat unchalik katta bo’lmagan n lar uchun ma’lum. , , , quyidagi xossani qanoatlantiruvchi ning vektorlari bo’lsin. ga tegishli bo’lgan, lekin L(b 1 ,...b k-1 ) ga tegishli bo’lmagan vektorlar orasida b k vektor minimal uzunlikka ega. (k=1,2,...,n) , (L( deb hisoblaymiz. Ravshanki, u holda vektorlar panjaraning bazisini tashkil etadi. Bu bazis Minkovskiy bo’yicha keltirilgan deb ataladi, bunda b k -panjaraning k-chi ketma -ket bazisi deyiladi. Teorema. 3.5 [7] Minkovskiy bo’yicha keltirilgan bazis uchun (7) o’rinli, bu yerda Ermit konstantasi. Xususan, (5) dan (8) 55 kelib chiqadi. 7-Eslatma. (7) tengsizlik Minkovskiy bo’yicha keltirilgan bazis, ortogonal bazisga yaqin ekanligini ko’rsatadi. 3.3 Korkin-Zolotarev bazislari. - vektorlar(1), (2) ortogonallashtirish natijasida panjaraning bazisidan olingan vektorlar bo’lsin. panjaraning bazisi Korkin-Zolotarev bo’yicha keltirilgan deyiladi, agar -panjaraning eng kichik vektoriki: -panjaraning shunday nol bo’lmagan vektoriki, L( ) ga ortogonal to’ldiruvchiga ning proyeksiyasi minimal bo’lsa (k=1,2,...n) ( ) 3.4 c-ortogonal bazislar. (8) tengsizlik yangi tushuncha kiritilishini asoslaydi. bazis c- ortogonal yoki Lenstra bo’yicha c-keltirilgan deyiladi. [5], agar o’rinli bo’lsa. Adamar tengsizligidan da c-ortogonal bazis mavjud emas. da esa bu tushuncha ortogonallikka aylanadi. 6-teoremadan ixtiyoriy panjara uchun 56 da c ortogonal bazis mavjudligi kelib chiqadi. Tayinlangan n da uchun c- ortogonal bazisni topishni birinchi polinomial algoritmi X.Lenstra [14] , c-ortogonal bazisni qurishni birinchi polinomial algoritmini L.Lovas taklif etgan. Endi c- keltirilgan bazis tushunchasini kiritamiz. vektorlar (1), (2) ortogonallashtirish natijasida panjaraning bazisidan olingan bo’lsin. bazis c-keltirilgan (Zegel bo’yicha) [10] deyiladi, agar (9) (k=2,3,...,n) (10) o’rinli bo’lsa. Keyinchalik c-keltirilgan bazis c-ortogonal bo’lishini ko’ramiz. Teskarisi o’rinli emas. Masalan: bazis c=2 da ortogonal, lekin c-keltirilgan emas. Haqiqatdan uning uchun , , , tenglik bajariladi. tengsizlik bajarilmaydi. Ma’lumki [2] , da ixtiyoriy panjara uchun c-keltirilgan bazis mavjud. Uning da mavjudligi quyida keltiriladigan maxsusroq bazisni qurish algoritmidan ham kelib chiqadi. 57 Dastlab c-keltirilgan bazis deyarli bir-biriga ortogonal kichik vektorlardan iborat ekanligini ko’rsatuvchi ba’zi formal bo’lmagan mulohazalarni keltiramiz. (9) shart vektorning vektorga proeksiyasi uzunligi vektorga nisbatan unchalik katta bo’lmasligi lozimligini anglatadi. Bu shart agar, vektor ga deyarli ortogonal yoki vektor uzunligi vektor uzunligiga nisbatan kichik bo’lsa bajariladi. Shunday qilib, (9) shart bazis deyarli ortogonal vektorlardan iboratligini anglatmasligi mumkin. Masalan, - juda uzun vektor, a ga nisbatan kichik, a ga nisbatan kichik va hokazo bo’lganda vaziyat bo’lishi mumkin. Lekin bu vaziyatning amalga oshirilishiga c-keltirilgan bazisda vektorlar uzunligi “deyarli kichraymasligini” ( vektor uzunligi vektor uzunligiga nisbatan unchalik kichik emas) anglatuvchi (10) shart to’sqinlik qiladi. ......... Teorema. 2.7 -panjaraning c-keltirilgan bazisi, bo’lsin, u holda (11) (12) Isbot . (11) dagi birinchi tengsizlik bu Adamar tengsizligidir. Ikkinchi tengsizlikni isbotlaymiz. (1),(2) Gram -Shmidt ortogonallashtirish natijasida dan olingan vektorlar bo’lsin. (10) dan ...... (13) 58 kelib chiqadi. Shuning uchun va ga ko’ra | ga ega bo’lamiz. Demak, Endi (12) ni isbotlaymiz. (13) va (14) dan kelib chiqadi. Xususan, , bu tengsizliklarni ko’paytirib, ni olamiz. Bundan (12) kelib chiqadi. 9-Eslatma. (11) dan c-keltirilgan bazis ortogonal bo’lishi kelib chiqadi. Teskarisi umuman olganda noto’g’ri. 59 10-Eslatma .(11) va (12) formulalarni (4), (6) va (7) ,(8) formulalar bilan mos ravishda taqqoslash, c-keltirilgan bazis Menkovskiy bo’yicha keltirilgan bazisni qanoatlantiradigan ba’zi muhim xossalarga ega bo’lishini ko’rsatadi. Teorema. 3.9 panjaraning keltirilgan bazisi, - eng kichik vektor uzunligi bo’lsin. U holda (15) Isbot. 2-Lemmaga ko’ra. , , Lekin Shuning uchun bundan talab qilinganga ega bo’lamiz. 12- Eslatma. (15) tengsizlik, - panjaraning eng kichik vektoridan biri ekanligini ko’rsatadi. Bu teoremani isbotlashda biz (9) xossadan foydalandik. 13-mashq. Agar da chiziqli bog’lanmagan vektorlar bo’lsin. da U holda da c-keltirilgan bazisni qurishni polinomial algoritmi [9] da keltirilgan. 60 3.5 Lovasning panjara bazisini keltirish algoritmi panjaraning bazisidan (1),(2) ortogonallashtirish natijasida olingan bo’lsin. bazis Lovas bo’yicha c-keltirilgan deyiladi, c da agar, (16) (k=2,3,...,n) (17) munosabat o’rinli bo’lsa. Shunday qilib, Lovas bo’yicha c-keltirilgan bazis ta’rifi, c-keltirilgan bazis tarifidan (10) shartni (17) shart bilan almashtirish bilan hosil qilinadi. Keyinchalik ko’ramizki, (17) shart (10) ga qaraganda ko’chliroq. Adabiyotlarda bunday bazislar ko’pincha (ayniqsa y= bo’yicha LLL-keltirilgan deb ataladi. Agar, bo’lsa, u holda bo’ladi. vektorning ortogonal to’ldiruvchiga proyeksiyasi bo’lgani uchun (17) shart bu proyeksiya ning bu ortogonal to’ldiruvchiga proyeksiyasiga qaraganda unchalik kichik emasligini bildiradi. (17) shart (k=2,3,...,n) (18) tengsizliklar teng kuchli.(16) va (18) dan, (10) tengsizlikni oson hosil qilish mumkin. 61 Shunday qilib, Lovas bo’yicha c-keltirilgan bazis c-keltirilgan bo’ladi. Teskarisi o’rinli emas.Masalan: bazis (u ortogonal) uchun c- keltirilgan, lekin Lovas bo’yicha c-keltirilgan emas, chunki bu holda tengsizlik bajariladi. tengsizlik esa yo’q. c-ortogonal bazis Lovas bo’yicha c-keltirilgan bazis 3.6 Algoritmlar Lovas bo’yicha keltirilgan bazisni qurish algoritmini qaraymiz. Bunday bazis tushunchasining o’zi kabi keltirish algoritmi L.Lovas tomonidan (10) taklif qilingan. LLL-algoritmi da polinomial bo’ladi. U ikkita g’oyaga asoslangan. 1) Agar biror k va l larda (16) shart bajarilmasa, u holda b k ni ga almashtirish mumkin. Bunda ni ga almashtirish lozim ( va da qiymatlarni yangilash zarur). Ravshanki, shundan so’ng (16) shart bajariladi. Bu protsedura Seze-Reducsion deb ataladi. 2) Agar biror k da (17) shart bajarilmasa , u holda b k ni b k-1 bilan joyini almashtirish mumkin. Bunda ni yangi qiymati hosil bo’lib, hisoblanadi. (Bundan tashqari vektor va kattaliklar ham o’zgaradi) Natijada 62 miqdor kamayadi.(c martadan ko’p). Bu protsedura INTERCHANGE deb ataladi. Dastlab LLL-algoritmning eng sodda variantini qaraymiz. Kiyin (i=1,2,...,n) Procedure LLL-REDUCTION-0 (var b 1 ,...,b n ) Izlanayotgan son (i , dan ... ; k while k for l if | SEZE- REDUCTION(k,l); end; end; if INTERCHANCE (k); k ; else k 63 end; end; end; Procedure SEZE- REDUCTION (k,l); q | bk ; ; for j ; end; end; Procedure INTERCHANCE (k); b k for j end 64 k For i ; end; end; 65 Yuqoridagilardan ayon bo’ladiki, agar LLL-REDUCTION-O algoritm o’z ishini to’xtatsa, u holda natijada, sestema panjaraning LLL-keltirilgan bazisini tashkil etadi. Algoritmning chekliligini isbotlaymiz. miqdorlardan qaysi biri INTERCHANGE algoritmini bajarish jarayonida o’zgarishini qaraymiz. Faqat k-1 va k o’zgaradi. Bunda b k-1 ni bilan almashtiriladi. Yuqorida ko’rganimizdek bu uning c martadan ko’p kamayishiga olib keladi. esa ga almashtiriladi. Bunda Miqdor qanday o’zgarishini qaraymiz. Hozir faqat quyidagi ko’paytuvchilar: o’zgaradi. Shunday qilib INTERCHANGE protsedurasini har marta chaqirganda B miqdor, qancha marta kamaysa, shuncha marta kamayadi, ya’ni c martadan ko’p marta. Bu jarayon cheksiz davom etish mumkin emas, chunki (4) teoremadan va demak, quyidan chegaralanganligi kelib chiqadi. Teorema -14 [15] = - dagi panjara bo’lsin, Bunda (i=1,2,...,n) , u holda Lovas bo’yicha c-keltirilgan bazis qurishning LLL-REDUCTION-O algoritmi uzunligi O(nlog bit bo’lgan butun sonlar ustida O( log arifmetik amallar bajaradi. 66 n=2 da LLL-REDUCTION-O algoritm GAUSS REDUCTIONga aylanadi. LLL-REDUCTION-O algoritmning ba’zi takomillashtirishlarini qaraymiz. Birinchidan, da | shartni tekshirishni qoldirish mumkin, chunki l ning bu qiymatlarida miqdorlar INTERCHANGE protsedurani chaqirishdan oldin tekshirishda qatnashmaydi. Bu eslatma bizni algoritmning quyidagi variantiga olib keladi. Procedure LLL-REDUCTION (var b1,...,bn) Izlanayotgan son (i algoritmni topish va sestemani qurish. k while k if | SEZE- REDUCTION(k,k-1); end; if INTERCHANCE (k,l); k ; else for l if | 67 SEZE- REDUCTION (k,l); end; end; k end; end; end; INTERCHANGE protsedurani bajarish paytida juda ko’p sondagi koeffisiyentlar va vektorlar sanab o’tiladi. Ularning ko’pchiligi foydalanish oldidan o’z qiymatini bir necha marta o’zgartiradi. Agar larni zarurat bo’lgandagina hisoblansa, hisoblash hajmini kichikrtirish mumkin.Algoritmning quyidagi variantida kmax oldin erishilgan k ning maxsimal qiymatiga teng. INTERCHANGE protsedurasida n ni kmax ga almashtirish zarur. sonlarni topish va sestemani qurish. kmax k while k 68 for l if k>kmax sonlarni topish va sestemani qurish. end; if | SEZE- REDUCTION(k,k-1); end; if INTERCHANCE (k); k ; else for if | SEZE- REDUCTION (k,l); end; end; 69 k end; end; end; Bu yerda keltirilgan LLL-REDUCTION algoritm [12] da keltirilgan 2.6.3 algoritm umuman olganda ustma-ust tushadi. 15- Eslatma. Berilgan bazisdan topilgan keltirilgan bazisga o’tish matritsasini olish uchun hisoblash jarayonida quyidagi amallarni bajarish yetarli. LLL- REDUCTION algoritm ishlashining boshida H ni birlik matrisaga teng deb olinadi. SEZE -REDUKTION algoritmida bu yerda H matritsaning j -ustini. Qiymat berishni bajarish lozim. INTERCHANGE algoritmida va ustunlar o’rni almashtiriladi. Shuningdek o’tish matritsasi berilgan va topilgan bazislar bo’yicha algoritm ishlashining yakunida hisoblanishi mumkin. 16- Eslatma. Agar berilgan bazis uchun Grim matritsasi butun sonli bo’lsa, u holda algoritm barcha hisoblashlari faqat butun sonlar bilan bo’ladigan qilib takomillashtirish mumkin. LLL algoritmning dasturiy bajarishlari [16,20,19] da keltirilgan. Bu yerda tavsiflangan algoritmlar masalalar qo’yilishlari va tadbiqlarini turli modifikatsiyalari [10,17] da bayon etilgan. LLL-REDUCTION 3.2 1 algoritm ishlashiga misol. 70 17-Misol. Koordinatalari ustunlari biror ortonormal bazisda A= matritsaning ustunlari bo’yicha yozilgan vektorlarga tortilgan Lovas bo’yicha panjaraning keltirilgan c bazisini topamiz. c=2 deb tanlaymiz, demak vektorlarni mos ravishda B matritsalar ustunlari bo’yicha yozamiz. M matritsa koeffisiyentlarini o’z ichiga oladi. M matritsa diagnalida miqdorlarni yozamiz. k=1 B=A M= k=2 kmax =2 ortogonallashtirish yordamida b 2 vektor topgandan so’ng: B= M= . 71 k=3 kmax=3 ortogonallashtirish yordamida vektor topilganidan so’ng: B= , , M= . INTERCHANGE(3) protsedurasi chaqirilgandan so’ng: B= M= k=2 SEZE-REDUCTION(2,1) protsedurasi chaqirilgandan so’ng: B= M= 72 INTERCHANGE(2) protsedurasi chaqirilgandan so’ng : B= M= k=2 SEZE-REDUCTION (2,1) protsedurasi chaqirilgandan so’ng: B= , M= k=3 . SEZE-REDUCTION(3,2) protsedurasi chaqirilgandan so’ng : B= , M= 73 INTERCHANGE(3) protsedurasi chaqirilgandan so’ng: B= , M= k=2 . SEZE-REDUCTION(2,1) protsedurasi chaqirilgandan so’ng: B= , M= INTERCHANGE(2) protsedurasi chaqirilgandan so’ng: B= , M= 74 k=2 . SEZE-REDUCTION (2,1) protsedurasi chaqirilgandan so’ng: B= , M= k=3 . SEZE-REDUCTION(3,2) protsedurasi chaqirilgandan so’ng: B= , M= SEZE-REDUCTION(3,1) protsedurasi chaqirilgandan so’ng: 75 B= , M= o’tish matritsasi: H= AH=B, detH=1 panjaraning LLL keltirilgan bazisini topamiz. AT= 13 ARAGELIdan foydalanish 3.13 Listing LLLReducsion.cpp include arageli/arageli.hpp using namespace std; using namespace Arageli; int main(int argc, char *argv[]) 76 {typedef rational typedef rational MT A=”((17,0,81),(1,17,0),(0,1,0),(5,1,12))”; MT B, H; coutendl>>”Initial basis (in columns) A=”endl; output_aligned(cout, A); B=A; if (lll_reduksion(B,H)) coutendl<”Reduced bases (in columns) B=”emdl; output_aligned(cout, B); coutendl<”Transformation matrix H =”endl; output_aligned(cout, H); coutendl<”A*H =”endl; output_aligned(cout, A*H); coutendl<Check B==A*H? ->”<<boolalpha <<B == A*H)endl; coutendl<”det(H) =”<det (H) endl;} else {cout<”Columns in A don’t form a basis’,,endl; cout<”(they are linear dependent)”endl;} return o;} 77 initial basis (in columns) A= Reduced bases (in columns)B= Transformasion matrix H= A*H= 78 Check B == A*H? _>true det (H) =1 Tadbiqlari Panjaraning keltirilgan bazislari kompyuter algebrasida [18], sonlar nazaryasida [17], butun sonli chiziqli dasturlashda [8,10,11] va k riptografiyada [5] va boshqa sohalarda ko’p sondagi tadbiqlarga ega. Misol sifatida haqiqiy sonlar jamlanmasining ratsional bog’lanishini topish masalasini qaraymiz. berilgan haqiqiy sonlar bo’lsin. Shunday butun sonlarni topish talab qilinadi. bo’lsin, yo bunday sonlar mavjud emasligini isbotlash lozim. Misol qaraymiz. [8] Faraz qilaylik, Integral darajani 6 dan yuqori bo’lmagan sonining juft darajalari yig’indisi kabi yopiq shaklda ifodalash mumkin bo’lsin. V, , mavjud qiymatlarni 10 29 darajasiga ko’paytiramiz va yaqin butunlargacha natijalarni yaxlitlaymiz. A matritsa ustunlariga tortilgan mos dasturiy ta’minotdan foydalanib LLL keltirilgan bazisni topamiz. 79 B= O’tish matritsasi B dagi oxirgi satrni o’chirish bilan olinadi. B matritsa birinchi ustuni chiziqli bog’lanish koeffisiyentlari birida Demak, XULOSA Ushbu magistrlik dissertatsiyasi algebraik panjara larning xossalarini o’rganishga bag’ishlangan. Unda ma’lum bir xossalarga ega bo’lgan panjaralar uchun quyidagi natijalar olingan.  Panjara bazis vektorlari normasining panjara bir jinsli minimumi orqali baholari olingan.  Panjara eng kichik vektorini topish algoritmi ishlab chiqilgan. 80  Ishlab chiqilgan algoritm kompyuter algebrasi tizimlarida realizatsiya qilingan. Ishda algebraik panjaralarning xossalari qarab chiqilgan bo'lib, barcha olingan natijalar nazariy xarakterga ega. Ishning amaliy ahamiyati shundaki, unda olingan panjar a bazisi vektorlari normasining baholarini panjaraning boshqa xossalarini tadqiq qilishda ishlatish mumkin. Di s sertatsiya ishining natijalaridan panjaraning eng kichik vetoriga oid masalalarni yechishda foydalanish mumkin. Foydalanilgan adabiyotlar ro’yxati. 1. J . W . Cassels. An Introduction to the Geometry of Numbers . Second Printing. Springer-Verlag Berlin, Heidelberg, New York, 1971. 2. A.V. Malyshev. The main notions and theorems of the geometry of numbers. Chebyshevskii sbornik, 2019, vol. 20, no. 3, pp. 43–73. 3. P.M. Gruber, C.G. Lekkerkerker, Geometry of numbers. North-Holland (1987). 4. Ruzimuradov Kh.Kh. Fundamental rectangles of admissible lattices. - Journal of Mathematical Sciences. May 1996, Volume 79, Issue 5. pp 1320-1324. 5. Ruzimuradov Kh.Kh. On the problem of counting the number of points of algebraic lattices in rectangles. Uzbek Mathematical Journal, 2008, No. 4, pp. 116-124. 6. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003. 7. Касселс Дж. Введение в геометрию чисел. М.: Мир, 1965. 8. Схрейвер А. Теория линейного и целочисленного программирования. В 2-х тт. М.: Мир, 1991. 14 81 9. Чирков А.Ю., Шевченко В.Н. О нахождении последовательных минимумов целочисленной решетки и вектора решетки, ближайшего к данному // Кибернетика. 1987. №4. С. 46–49. 10. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. 11. Aardal K., Weismantel R., Wolsey L. Non-standard approaches to integer programming. 1999. 12. Ajtai M. The shortest vector problem in L2 is NP-hard for randomized reductions // Electronic Colloquium for Computational Complexity. 1997. TR97-047. 13. Borwein J.M., Lison˘ek P. Applications of Integer Relation Algorithms. Centre for Experimental and Constructive Mathematics Department of Mathematics and Statistics Simon Fraser University. 1997 14. Lenstra H.W. Integer programming with a fixed numbers of variables. Report 81-03. Dep. Math. Univ., Amsterdam. 1981. 15. Lenstra A.K., Lenstra H.W., Lovasz L. Factoring polynomials with rational coefficients // Math. Ann. 1982. V 261. P.515–534. 16. Arageli: A library for doing exact computation. Department of Computer Science. University of Nizhni Novgorod. http://www.unn.ru/cs/arageli . 17. Cohen H. A course in computational algebraic number theory. Berlin e.a.: Springer, 1993. 18. von zur Gathen J., Gerhard J. Modern Computer Algebra. Cambridge University Press, 1999. 19. LiDIA — A library for computational number theory. TH Darmstadt/Universit¨at des Saarlandes, Fachbereich Informatik, Institut f¨ur Theoretische Informatik. http://www.informatik.th-darmstadt.de/pub/TI/LiDIA . 20. Shoup V. NTL: A library for doing number theory. Department of Computer Science, University of Wisconsin–Medison. http://www.shoup.net. 82 83

Panjaraning eng kichik vektorini va berilgan vektorga eng yaqin vektorini topish masalasining algoritmik jihatlari MUNDARIJA KIRISH 4 I BOB. PANJARALAR TO’G’RISIDA ASOSIY MALUMOTLAR 6 1-§.Panjaralar. 6 2-§. Ikkita matrisalarni bitta panjarani ifoda etishlari sharti 7 3-§. m-ta chiziqli bog’lanmagan nuqtalar panjara bazisini tashkil etishi ʌ uchun zarur va yetarli shar t 12 4-§. O’zaro panjaralar 13 II BOB. To’plamlar. Panjaralarning fundamental sohalari. 1-§. To’plamlar 18 2-§. Panjaralarning fundamental sohalari 19 3-§. Blixfeladt va Minkovskiy teoremalari 25 4-§. Panjaraning matritsaviy bazisi normasini baholash 26 III BOB. Panjaraning eng kichik vektorini topish algoritmi 1-§. Panjaralar. Gram Shmidt ortogonalizatsiyasi 33 2 -§. Panjaraning eng kichik vektori 34 3 -§. Korkin Zolatarev bazislari 36 4- c –ortogonal bazislar 38 5. Lovasning panjara bazisini keltirish algoritmi 42 6. Algoritmlar 43 XULOSA 58 Foydalanilgan adabiyotlar ro’yxati 1

KIRISH Mavzuning dolzarbligi: O‘zbekiston Respublikasi Prezidentining 2018 yil 5 iyundagi “Oliy ta’lim muassasalarida ta’lim sifatini oshirish va ularning mamlakatda amalga oshirilayotgan keng qamrovli islohatlarda qamrovini faol ishtirokini ta’minlash bo‘yicha qo‘shimcha chora-tadbirlari to‘g‘risida” gi PQ- 3775 Qarorida “Ta’lim sifati professor o‘qituvchilarning bilimi va pedogogik mahorati, talabalarga yaratilgan sharoitlar ustidan tizimli ravishda monitoring o‘rnatish” bo‘yicha asosiy vazifa sifatida belgilandi. 2020 yil 7 maydagi “Matematika sohasida ta’lim sifatini oshirish va ilmiy tadqiqotlarni rivojlantirish chora tadbirlari to‘g‘risida”gi PQ-4708-son qarorida qo‘yilgan vazifalarni hal qilishda “Matematika” fani muta¬xassislar tayyorlashning o‘quv jarayonida yuqori daraja¬dagi matematik tayyorgarligi va ko‘pgina maxsus fanlar bo‘yicha chuqur bilimlar egasi bo‘lishida asosiy o‘rin tutadi. Ushbu magistrlik dissertatsiyasida sonlar geometriyasining dolzarb muammolaridan bo'lgan panjaraning eng kichik vektorini topish algoritmi, shu vektor uzunligini baholash masalalari qarab chiqiladi. Tadqiqotning ob’yekti va predmeti: Tadqiqot obyekti bo‘lib algebraik panjaralar, qism panjaralar, panjaraning eng kichik vektorini qurish masalasi hisoblanadi. Tadqiqot predmeti esa panjaraning eng kichik vektorini topish algoritmlari va uni baholashdan iborat. Tadqiqotning maqsadi va vazifalari: Ushbu ishning maqsadi va vazifalari quyidagicha: algebraik panjaralar va ularning qism panjaralarining xossalarini o'rganish, panjara bazisini qurish, bazis vektorlarini panjaraning bir jinsli minimumi orqali baholash , panjaraning eng kichikvektorini topish lagoritmlari , shu vektorni baholari olishdan iborat. Ilmiy yangiligi: Ishning asosiy yangiliklari quyidagilardan iborat: • Algebraik panjara bazis vektorlari normasining panjara bir jinsli minimumi orqali baholari olingan. • Panjara eng kichik vektorini topish algoritmi ishlab chiqilgan. • Ishlab chiqilgan algoritm kompyuter algebrasi tizimlarida realizatsiya qilingan. Tadqiqotning asosiy masalalari va farazlari: Oxirgi yillarda algoritmlar bilan bog’liq bo‘lgan, algebrik geometriyaning bazaviy abstrakt-nazariy tushunchalarini konkret hisoblanadigan matematik sohalar keng rivojlanmoqda. Magistrlik 2

dissertatsiyasida algebraik panjaralarning bazis vektorlari normasini baholash, panjara eng kichik vektorini hisoblash va baholash algoritmlariga oid masalalar qarab chiqiladi. Tadqiqot mavzusi bo‘yicha adabiyotlar sharhi(tahlili): Ushbu dissertatsiya ishida algebarik panjaralarning xossalari J.W. Cassels. An Introduction to the Geometry of Numbers (Second Printing. Springer-Verlag Berlin, Heidelberg, New York, 1971) m onografiyada berilgan. Sonlar geometriyasining panjaralarga oid tasdiqlar, jumladan, panjaraning bazisi to'g'risidagi ma'lumotlar A.V. Malyshev. The main notions and theorems of the geometry of numbers ( Chebyshevskii sbornik, 2019, vol. 20, no. 3, pp. 43–73 ) s harhiy maqolada ham keltirilgan. Panjaralarning zamonaviy xossalari va panjara bazisiga oid malumotlar P.M. Gruber, C.G. Lekkerkerker, Geometry of numbers ( North-Holland , 1987) kitorbida yetarlicha tahlil qilingan. Panjara bazisi vektorlarining baholariga oid ilmiy natijalar Ruzimuradov Kh.Kh. Fundamental rectangles of admissible lattices ( Journal of Mathematical Sciences. May 1996, Volume 79, Issue 5. pp 1320-1324 ) va Ruzimuradov Kh.Kh. On the problem of counting the number of points of algebraic lattices in rectangles ( Uzbek Mathematical Journal, 2008, No. 4, pp. 116-124 ) maqolalarda olingan. Yuqorida keltirilgan adabiyotlardan foydalanib ushbu magistrlik dissertatsiyasida panjaraning bazis vektorlarinormasi bahosi uning bir jinsli minimumi orqali olingan. Panjaraning eng kichik vektorini hisoblash algoritmlari keltirilgan. Tadqiqotda qo‘llanilgan metodikaning tavsifi: Ishda chiziqli va nochiziqli algebraning usullaridan, to'plamlar nazariyasi metodlaridan , kompyuter algebrasi tizimlaridan foydalanilgan. Tadqiqot natijalarining nazariy va amaliy ahamiyati: Ishda algebraik panjaralarning xossalari qarab chiqilgan bo'lib, barcha olingan natijalar nazariy xarakterga ega. Ishning amaliy ahamiyati shundaki, unda olingan panjar a bazisi vektorlari normasining baholarini panjaraning boshqa xossalarini tadqiq qilishda ishlatish mumkin. Disertatsiya ishining natijalaridan panjaraning eng kichik vetoriga oid masalalarni yechishda foydalanish mumkin. Ish tuzilmasining tavsifi: Dissertatsiya ishi kirish qismi, uchta bob va adabiyotlar ro‘yxatidan iborat. Dissertatsiyaning umumiy hajmi 61 betdan iborat. Kirish qismida masala tarixi, adabiyotlar tahlili kichikcha berilgan, dissertatsiya ishida qilingan ishlar to‘g’risida kichikcha ma’lumotlar berib o‘tilgan va asosiy olingan natijalar bayoni keltirilgan. Birinchi bob sonlar geometriyasining asosiy tushunchalaridan bo'lgan panjaralaraga bag'ishlangan, bu yerda panjaraga oid qiism panjara tushunchasi, 3

panjaraning bazisi tushunchasi, matritsaviy bazis, o'zaro panjara, panjara qatlamlari kabi tushunchalarning bayoni va xossalari keltirilgan. Ushbu tushunchalardan kelgusi boblarda foydalanilgan. Ikkinchi bob panjaraning fundamental sohalari, Blixfeldt va Minkovskiy teoremalariga bag'ishlangan. Ushbu bobda panjara bazisi vektorlari normasining yangi bahosi olingan. Uchinchi bobda panjaraning eng kichik vektoriga oid tushunchalar, panjara bazisining bir qancha formalari, eng kichik vektorni hisoblashga oid algoritmlar keltirilgan Magistrlik dissertatsiyasining asosiy natijalari asosida quyidagi maqola va tezislarda chop qilingan: 1. On an Estimate Related to the Homogeneous Minimum of the Admissible Lattice. ( Ruzimuradov, Poyanova). International Conference on Mathematics and its Scientific Applications. on 3rd March 2022. Sathyabama icmsa. AIP Conference Proceedings. 2. Otsenka normы matrichnogo bazisa dopustimoy reshyotki. Umumta'lim fanlarini asinxron va asinxron bog'lab o'quvchi kreativ faoliyatini rivojlantirishda inegrativ yondashuv. (Respublika ilmiy-amaliy konfrensiyasi materiallari to’plami).- Denov-2022. 4

1-BOB PANJARALAR TO’G’RISIDA ASOSIY MA’LUMOTLAR 1.1. PANJARALAR 1.1-Ta’rif to’plamga panjara deyiladi, bunda -xosmas matritsa, -esa n o’lchovli butun sonli vektorlar to’plamidan iborat. -matritsaga -panjara ba’zisi deyiladi. Agarda (I-birlik matritsa) bo’lsa, panjara ko’rinishga ega bo’ladi, bunga bosh panjara deyiladi. miqdorga panjara hajmi deyiladi. 1.1-Lemma. to’plamning avtomorfizmlari guruxi butun sonli unimodulyar matritsalar to’plami bilan ustma-ust keladi, ya’ni agarda - butun sonli unimodulyar matritsa bo’lsa, bo’ladi. Isbot. Agarda bo’lsa, E- butun sonli unimodulyar matritsa va aksincha, agarda - butun sonli unimodulyar matritsa bo’lsa, bo’lishini ko’rsatamiz. bo’lsin. - butun sonli unimodulyar matritsa bo’lishligini ko’rsatamiz. Teskarisidan faraz qilaylik, ya’ni -matritsaning elementi butun son bo’lmasin. 5

Похожие

Graflarda eng qisqa masofani topish algoritmlari
GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR
Eng katta qismiy ketma-ketlikni qidirish
ENG KATTA QISMIY KETMA- KETLIKNI TEZKOR QIDIRISH
Maydon nazariyasi elementlari, ularning tadbiq etilishi