|
I. NAZARIY QISM.
1.1 ALGORITMLAR HAQIDA MA'LUMOT.
Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi.
Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq. Algoritm - biror maqsadga erishishga qaratilgan ijrochi bajarishi uchun mo'ljallangan ko'rsatmalar aniq, tushunarli va chekli ketma-ketligidir.
Albatta, algoritmni aniq sxema bo’yicha tuzish zarur bo’lib qoladigan sodda hollar ham mavjud. Bunday hollarda yechilish algoritmiavval biron kim tomonidan olingan masalalarni misol keltirish mumkin. Masalan, differensial tenglamalarni sonli integrallash uchun Eyler metodi. Bu metod masalani yechish uchun umumiy holda ifodalangan algoritmdir, lekin algoritmlash ijodiy ekanligini quyidagi algoritmlar nazariyasining ba’zi bir ma’lumotlaridan ko’rish mumkin. Agar bizdan biror algoritmni ishlab chiqish talab qilinsa, dastlab izlanayotgan algoritmni tuzish mumkinmi yo’qmi degan savolga javob izlash kerak. Chunki ba’zi hollarda algoritmni tuzish mumkin emasligini ko’rsatib berish mumkin. Ba’zi bir hollarda algoritmni tuzish mumkinligi isbotlanadi. Bunday isbot mavjud bo’lganligi bilan tuzilgan algoritmni amalgam oshirib bo’lmaydi yoki uning samaradorligi talabga javob bermaydi. Shunga qaramasdan bir nechta algoritmlar bitta amaliyotga qo’llanilayotganini topish mumkin. Boshqa hollarda algoritmni tuzish mumkinligini ham, mumkin emasligini ham isbotlab bo’lmaydi. U vaqtda algoritm tuzish jarayonida boshqa predmet sohalaridan qurilgan algoritmlardan foydalanish mumkin. Algoritmning umumiy goyasi quyidagicha.
■ Bir qatordan langar deb nomlangan elementni tanlang. Bu qator elementlaridan har qanday bolishi mumkin. Algoritmning togriligi qollab-quvvatlash elementini tanlashga bogliq emas, lekin bazi hollarda uning samaradorligi kuchli bogliq bolishi mumkin (pastga qarang).
■ Boshqa barcha elementlarni mos yozuvlar bilan taqqoslang va ketma-ketlikni shunday tartibda joylashtiringki, ketma-ketlikni ketma-ket uchta segmentga boling: "mos yozuvlar darajasidan kichikroq elementlar", "teng" va "katta".
■ Agar "uzunlik" dan kattaroq bolsa, "kichikroq" va "katta" qiymat segmentlari uchun rekursiv ravishda bir xil operatsiyalar ketma-ketligini bajaring.
Amalda, qator odatda uchga emas, balki ikki qismga bolinadi: masalan, "kichik malumot" va "teng va katta"; bunday yondashuv umuman samaralidir, chunki u ajratish algoritmini soddalashtiradi. Hoar mashinani tarjima qilish uchun ushbu usulni ishlab chiqdi; lugat magnit tasmada saqlangan va qayta ishlangan matnning sozlarini saralash, ularning tarjimalarini lentaning bitta nusxasida, qaytadan yozmasdan olish imkonini berdi. Algoritmni Hoar Sovet Ittifoqida bolgan paytida ixtiro qilgan, u yerda u Moskva universitetida kompyuter tarjimasini organgan va rus-ingliz tilidagi iboralarni ishlab chiqish bilan shugullangan.
1.2. SARALASH ALGORITMLARI VA ULARNING TARIXI.
Tartiblash algoritmi bu royxatdagi narsalarni tartiblash algoritmi. Royxat elementida bir nechta maydonlar mavjud bolsa, buyurtma mezoni sifatida xizmat qiladigan maydonga saralash kaliti deyiladi. Amalda, raqam kopincha kalit vazifasini bajaradi, qolgan maydonlar algoritmning ishlashiga tasir qilmaydigan bazi malumotlarni saqlaydi.
Zamonaviy saralash usullarining birinchi prototiplari XIX – asrda paydo bolgan. 1890 – yilga kelib, Amerika Qoshma Shtatlarida aholini royxatga olish malumotlarini qayta ishlashni tezlashtirish uchun, Amerikalik Herman Xollerit birinchi statistik tabulyatorni yaratdi - punch kartalarida qayd etilgan malumotlarni avtomatik ravishda qayta ishlashga moljallangan elektromexanik mashina. Xollerit mashinasida 26 ta ichki qismdan iborat maxsus “saralash qutisi” mavjud edi. Mashina bilan ishlayotganda, operatorga musht kartasini ornatish va dastani tushirish kerak edi. Teshikli kartada teshiklar tufayli malum bir elektr zanjiri yopildi va unga ulangan raqamning korsatkichi bittaga kopaydi. Shu bilan birga, saralash qutisining 26 qopqogidan biri ochilib, zarb qilingan karta tegishli bolimga kochirildi, shundan song qopqoq yopildi. Ushbu mashina daqiqasiga 50 ta kartani qayta ishlashga imkon berdi, bu esa malumotlarni qayta ishlashni 3 baravar tezlashtirdi. 1900 yilgi royxatga olish bilan Xollerit xaritalarni yetkazib berishni avtomatlashtirish orqali mashinani takomillashtirdi. Xolleritni saralash mashinasining ishi bitlarni saralash usullariga asoslangan edi. Mashinaning patenti "har bir ustun uchun alohida" saralashni bildiradi, ammo tartib aniqlanmagan. 1894 – yilda Jon Gor tomonidan patentlangan yana bir shunga oxshash mashina onlab kolonnalardan saralash haqida gap boradi. Tartiblash usuli birliklar ustunidan boshlanib, birinchi marta adabiyotda 30-yillarning oxirlarida paydo boldi. Bu vaqtga kelib, saralash mashinalari daqiqada 400 tagacha kartani qayta ishlashga ruxsat berdilar.
Do'stlaringiz bilan baham: | 
