3- amaliy ish. Mavzu: halstedning murakkablik o‘lchovlari

3- AMALIY ISH.

Mavzu: HALSTEDNING MURAKKABLIK O‘LCHOVLARI
Ishning maqsadi: Halsted dasturlarining metrik nazariyasi asoslarini o'rganish, dastur modullari uchun miqdoriy xarakteristikalarni hisoblash.
Vazifa:

1. 
   Nazariy material bilan tanishish.
   
2. 
   Berilgan masala uchun dastur yozish, murakkablikni aniqlash uchun Halstedning murakkablik o‘lchovlari asosida dasturning miqdoriy xarakteristikalarni hisoblash.
   
3. 
   Amaliy ish bo’yicha hisobot tayyorlash.
   

NAZARIY QISM

Dasturiy ta’minotni konstruktsiyalash (“Software Construction”) bilim sohasi quyidagi bo’limlarni o’z ichiga oladi:

• 
  murakkablikni kamaytirish (Reduction in Complexity),
  
• 
  uslubdan og’ishning oldini olish (Anticipation of Diversity),
  
• 
  sinovlarni tuzilmalashtirish (Structuring for Validation),
  
• 
  tashqi standartlardan foydalanish (Use of External Standards).
  

Murakkablikni kamaytirish - bu konstruktsiyalashdagi murakkablikni minimallashtirish, kamaytirish va alohida qismlarga bo’lish. Murakkablikni minimallashtirish, ijrochilarning murakkab tuzilmalarni va uzoq vaqt davomida katta hajmdagi ma’lumotlarni qayta ishlash qobiliyatining cheklanganligi bilan belgilanadi. Murakkablikni minimallashtirishga, xususan, konstruktsiyalash jarayonida modullar va boshqa sodda elementlardan foydalanish, shuningdek, standartlarning tavsiyalari yordamida erishiladi.
Dasturiy ta’minotning murakkabligi - bu dasturlashning ajralmas xususiyati bo’lib, u dasturlarni yaratish vaqti va xarajatlarida, dastur matnining hajmida yoki uzunligida, boshqaruvni uzatuvchi operatorlari (tarmoqlanish operatorlari, davriy operatorlar, funktsiyalarni chaqirish) tomonidan o’rnatilgan mantiqiy tuzilishining xususiyatlarida namoyon bo’ladi. Dasturiy ta’minot ko’rsatkichi - bu dasturiy ta’minotning ba’zi xususiyatlari yoki uning texnik xususiyatlarining raqamli qiymatini olish imkonini beruvchi o’lchov. Miqdoriy usullar boshqa sohalarda yaxshi ishlaganligi sababli, ko’plab kompyuter olimlari va amaliyotchilar ushbu yondashuvni dasturiy ta’minotni ishlab chiqishga o’tkazishga harakat qilishdi.
Amaldagi o’lchovlar to’plamiga quyidagilar kiradi:

• 
  o’sish tartibi (asimptotik tahlil va O-notatsiya nuqtai nazaridan algoritmlarni tahlil qilishni anglatadi),
  
• 
  kod satrlari soni,
  
• 
  siklomatik murakkablik,
  
• 
  funktsiya nuqtalarini tahlil qilish,
  
• 
  kodning 1000 satridagi xatolar soni,
  
• 
  test orqali kodni qamrab olish darajasi,
  
• 
  talablarni qoplash ,
  
• 
  sinflar va interfeyslar soni,
  
• 
  bog’liqlik.
  

Dastur kodidagi ba’zi ko‘rsatkichlarni hisoblashga asoslangan o‘lchamlar guruhiga Halsted o‘lchamlari kiradi. Ushbu o‘lchamlar quyidagilarga asoslanadi:

₁ — dasturning takrorlanmas operatorlari soni, jumladan ajratuvchi belgilar, dastur(yoki funktsiya) nomlari va operatsiya belgilari (operatorlar lug‘ati);
₂ — dasturning takrorlanmas operandlari soni (operandlar lug‘ati);
N₁ — dasturdagi operatorlarning umumiy soni;
N₂ — dasturdagi operandlarning umumiy soni.
Ushbu birlamchi o‘lchov belgilari orqali dastur lug‘atini quyidagicha ifodalash mumkin:
 = ₁ + ₂
Dasturning uzunligini quyidagicha ifodalash mumkin:
N = N₁ + N₂
Halsted dastur uzunligini quiyidagi formula bo‘yicha baholashni taklif qildi:
N’ = ₁ log₂ ₁ + ₂ log₂ ₂
bu yerda N’ - dasturning nazariy uzunligi (stilistik jihatdan to‘g‘ri bo‘lgan dasturlar uchun N ning N’ dan chetlanishi 10% dan oshmaydi.
Dasturning muhim metrik xarakteristikasi uning o‘lchamidir. Dasturning har qanday joriy etilishi uchun mos keladigan metrik o‘lcham xarakteristikasi dasturning hajmi(V- bitlarda ifodalanadi) deb ataladi:
V = N * log₂
Halsted o‘lchamlarini tushunish uchun quyidagi misolni ko‘rib chiqamiz:
Misol sifatida pufakchali saralash algoritmining dasturini keltiramiz. Bu dastur C++ dasturlash tilida yozilgan.
/* Pufakchali saralash algoritmining C++ tilidagi dasturi */
int main()
{ int *arr; int size, temp; cout << "n = "; cin >> size;
if (size <= 0) { cerr << "Invalid size" << endl; return 1; }
arr = new int[size];
for (int i = 0; i < size; i++) { cout << "arr[" << i << "] = "; cin >> arr[i]; }
for (int i = 0; i < size - 1; i++)
{ for (int j = 0; j < size - i - 1; j++)
{ if (arr[j] > arr[j + 1])
{ temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } }
for (int i = 0; i < size; i++) { cout << arr[i] << " "; }
cout << endl; delete [] arr;
return 0; }

Dasturning takrorlanmas operatorlari (operatorlar lug‘ati) sonini hisoblab chiqamiz. Bu holda ajratuvchi belgilar, dastur(yoki funktsiya) nomlari va operatsiya belgilarini ham qo‘shib hisoblaymiz: