«algoritmlar va berilganlar strukturasi»

O‘ZBEKISTON RESPUBLIKASI OLIY VA O‘RTA MAXSUS TA’LIM VAZIRLIGI

MIRZO ULUG‘BEK NOMIDAGI

O‘ZBEKISTON MILLIY UNIVERSITETI

“AXBOROT XAVFSIZLIGI” KAFEDRASI

« ALGORITMLAR VA BERILGANLAR STRUKTURASI»

fanidan

ORALIQ NAZORAT ISHI

5330300 – Axborot xavfsizligi(kompyuter tizimlari xavfsizligi)

Topshirdi: Dadaxonov Muxammadayubxon

Qabul qildi: Tojiddin Xojiyev

Toshkent 2020

Алг ва БС. Билет № 13

1. Разрядлар бўйича саралаш.

2. Рўйхатнинг бирор р -позициясидаги элементни ўчириш алгоритмини ёзинг. Бу ерда: Т={3, 2, 1, 1, 6, 10, 9, 9}; р берилади.

3. Вектор элементлари орасидан энг каттасини топиш дастурида мураккаблик кўрсаткичини баҳоланг.

1. 
   Razryadlar bo’yicha saralash 1920-yillarda yaratilgan.
   Uni 80 ta ustunli perfokartalarni qayta ishlovchi mashinalarda foydalanishgan. Perfokartadagi har bir ustun alohida ustun
   alohida belgini ifodalaydi va unda maxsus 12 ta pozitsiya bo’lib,
   u yoki bu simvolni ifodalash uchun maxsus teshikchalar urilgan bo’ladi.
   0 dan 9 gacha bo’lgan raqamlarni mos pozitsiyalarda faqat o’zlarini ifodalovchi 1 tadan teshikcha yordamida belgilanadi (qolgan 2 ta
   pozitsiya esa harflarni kodlash uchun ishlatiladi). Mashinani ishga
   tushurish bilanoq,injener-operator uning qabul qilish (kiritish) qurilmasi uchun mo’ljallangan maxsus joyiga perfokartalar uyumini qo’yadi va perfokartalarga ustunraqamini beradi. Mashina kartalardagi bu ustunni “ko’rib chiqadi” va undagi 0,1,2,…,9 raqamlarini qiymatlari
   bo’yicha perfokarta uyumlarini 10 ta uyumga ajratadi. Bir necha
   raqamlar bilan kodlashtirilgan ustunlar (razryadlar) natural sonlarni,
   ya’ni karta nomerini ifodalaydi. Karta uyumining tartiblangan raqamlari bo’yicha kerakli uyumni olish uchun operator quyidagicha ish yuritadi. Dastlab u kartalarni kichik razryaddagi qiymatlar bo’yicha taqsimlaydi.
   Bu uyumlarni kichik razryadlardagi qiymatlarning o’sib boorish
   tartibida joylashtiradi va bu jarayon razryadlar bo’yicha ularni o’sib
   borish tartibida joylashtirish orqali operator kerakli natijaga erishadi.
   Bu razryadlar bo’yicha saralash usuli oldingi hisoblash mashinalarida perfokartalar bilan bog’liq bo’lgan ko’p masalalarda foydalaniladi. Ko’pgina fayllardagi yozuvlarni tartiblash masalalarida kalitlardan foydalaniladi. Kalitlar juda murakkab ko’rinishda bo’lishi mumkin. Masalan, telefon kitobidagi yoki kutubxona katalogidagi foydalaniladigan kalitlarning qanchalik murakkabligini tasavvur qilish qimumkin.
   Bu murakkabliklarning hammasini saralash metodlarining eng zarur xossalaridan ajratish uchun ,hozircha 2 ta kalitni taqqoslash va 2 ta yozuvning joylarini almashtirish usullari bilan cheklanamiz.
   Ba’zan kalitlarni qatya ishlashga zarurat ham bo’lmaydi.
   Masalan,biror abonentning telefon raqamini topish uchun uning familyasining dastlabki harflarini berish orqali izlanayotgan telefon raqami, telefon kitobining qaysi betda ekanligini aniqlash mumkin.
   Bunday saralash algoritmlarning samaradorligiga erishish uchun,biz kalitlarni fiksirlangan o’lchamdagi porsiyalar ketma-ketligiga
   yoki baytlarga ajratamiz. Ma’lumki, 2 lik sonlar bitlar
   ketma-ketligidan ,satrlar esa belgilar ketma-ketligidan,
   o’nlik sonlar esa raqamlar ketma-ketligidan iborat bo’ladi.
   Bittadan porsiyalar bilan qayta ishlash asosida qurilgan saralash
   usullariga razryadlar bilan saralash usullari (radix) deyiladi.
   Bu usullar nafaqat kalitlar kalitlarni solishtirishni bajaradi, balki ular qayta-qayta ishlaydi va kalitlarning mos qismlarini taqqoslaydi ham.
   Razryadli saralash algoritmlari kalitlarni R asosli sanoq sistemasidagi
   son sifatida ko’radi va alohida sonlar bilan ishlaydi. Masalan,
   Agar mashina po’chta bo’limidagi paketlar uyumini qayta ishlasa,
   qaysiki ularning har bittasi 10 lik sanoq sistemasidagi 5 ta
   raqam bilan ifodalangan bo’lsin. Mashina ularni 10 ta alohida
   uyumlarga ajratadi, qaysiki 1-uyum 0 dan, 2-uyum 1 dan,
   3-uyum 2 dan ….,10-uyum 9 dan boshlab davom ettiriladi.
   Agar zarur bo’lsa har 1ta uyumni alohida biror oddiyroq usul bilan
   saralash mumkin. Agar paketlarni 0 dan 9 gacha tartiblangan uyumlarga ajratib olinadi va saralash amalga oshirilsa,u holda barcha paketlar saralangan bo’ladi. Ulardan esa umumiy saralangan paketlar
   uyumi kelib chiqadi. Bu protsedura R=10 bo’lgandagina razryadli
   saralashga oddiy misol bo’ladi. Aynan mana shu usul juda ko’p
   amaliy masalalarda uchraydigan saralash usuli sifatida ishlatiladi.
   Bu yerda kalit sifatida 10 lik sanoq sistemasidagi 5 tadan raqam 10tagacha raqam olish mumkin.
   

2.