1. Dasturiy ta’minot va uning turlari

Xeshlash funktsiyasi (xesh-funktsiyasi) shunday o’zgartirishki, kirish yo’liga uzunligi o’zgaruvchan xabar M berilganida chiqish yo’lida belgilangan uzunlikdagi qator h(M) hosil bo’ladi. Boshqacha aytganda, xesh-funktsiya h(.) argument sifatida uzunligi ixtiyoriy xabar (xujjat) M ni qabul qiladi va belgilangan uzunlikdagi xesh-qiymat (xesh) H=h(M)ni qaytaradi.
Kriptografik xesh funksiyalarning esa quyidagi turlari mavjud:

1. 
   kalitli xesh funksiya; 2) kalitsiz xesh funksiya.
   

Kalitli xesh funksiyalar simmetrik shifrlash algoritmi tizimlarida qo‘llaniladi. Kalitli xesh funksiyalar berilgan ma’lumot autentifikatsiyasi kodi (message authentication code(MAC)) deb ham yuritiladi. Ushbu kod bir-biriga ishonchi mavjud foydalanuvchilarga berilgan ma’lumotining haqiqiyligi va to‘laligini kafolatini qo‘shimcha vositalarsiz ta’minlash imkoniyatini tug‘diradi. Kalitsiz xesh funksiyalar xatolarni topish kodi (modification detection code(MDC) yoki manipulation detection code, massage integrrity code(MIC) deb ataladi. Ushbu kod qo‘shimcha vositalar (masalan: himoyalangan aloqa tarmog‘i, shifrlash yoki ERI algoritmlari) yordamida berilgan ma’lumot to‘laligini kafolatlaydi. Bu turdagi xesh funksiyalardan bir-biriga ishonch bildiruvchi va ishonchi bo‘lmagan tomonlar foydalanishlari mumkin. Odatda kalitsiz xesh funksiyalardan quyidagi xossalarni qanoatlantirishi talab qilinadi:1) bir tomonlilik;2) kolliziyaga bardoshlilik;3) xesh qiymatlari teng bo‘lgan ikkita ma’lumotni topishga bardoshlilik.Birinchi shart bajarilganda, berilgan xesh qiymatga ega bo‘lgan
ma’lumotni topishning murakkab ekanligini, ikkinchi shart bajarilganda
bir xil xesh qiymatga ega bo‘lgan ma’lumotlar juftini topishning
murakkab ekanligini, uchinchi shart xesh qiymati ma’lum bo‘lgan berilgan
ma’lumot uchun xesh qiymati shunga teng bo‘lgan ikkinchi ma’lumotni
topishning murakkab ekanligini bildiradi.

76. 
    Graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari (Prima algoritmi, Kruskal algoritmi)
    

Graf - bu abstrakt obyekt bo’lib, uchlar to'plami (tugunlar) va qirralarning to'plami - uchlar juftliklari orasidagi bog'lanishlardan tashkil topadi.
Graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari
Eng kichik uzunlikdagi daraxt – berilgan grafning eng kam og’irlikka ega bo’lgan daraxti, bu yerda daraxtning vazni uning qirralari og’irliklari yig’indsi sifatida tushuniladi. Misol. Minimal uzunlikdagi daraxtni toppish muammosi ko’pincha xuddi shunday sharoitda uchraydi: masalan, har qanday shaharda boshqasiga (to’g’ridan –to’g’ri yoki boshqa shahar orqali) o’tish uchun n ta shaharni yo’llar bilan bog’lash kerak . Berilgan juft shaharlar o’rtasida yo’llar qurisha ruxsat beriladi va har bir bunday yo’lni qurish qiymati ma’lum. Qurishning umumiy narxini minimallashtirish uchun qaysi yollarni qurish kerakligini hal qilish talab etiladi. Ushbu muammoni grafika nazariyasi nuqtai nazardan shakillantirish munkin. Bu yerda berilgan grafning uchlari shaharlarni, qirralari esa to’g’ri yo’l qurishi munkin bo’lgan va qirralarining og’rliklari teng bo’lgan shaharlarni ifodalaydigan minimal daraxtni toppish muammosidir. Minimal uzunlikdagi daraxtlarni toppish uchun bir nechta algoritmlar mavjud. Eng mashhur algoritmlar quydadilar :

1. 
   Kruskal algoritmi
   
2. 
   Prima algoritimi
   
3. 
   Boruvka algoritmi
   
4. 
   Orqadan o’chirish algoritmi
   

Kruskal algoritmi birlashtirilgan Kruskal kamaymaydigan chekka og'irliklariga muvofiq tartiblangan. Bundan tashqari, girralar og'irligi kichikrog bo'lgan girralardan yuqori tomonga siljiydi va keyingi chekka ilgari tanlangan girralar bilan sikl hosil gilmasa, karkasga go'shiladi. Xususan, grafdagi minimal og'irlikdagi girralaridan biri har doim birinchi bo'lib tanlanadi. Tanlangan qirralarning sikl hosil qilmasligini tekshirish uchun biz grafni bir nechta bog'langan komponentlarning birlashishi sifatida namoyish etamiz. Eng boshida, grafining chekkalari tanlanmaganida, har bir uch alohida bog'langan komponent hisoblanadi, Yangi qirralar go'shilganda, ulanish komponentlari bitta umumiy ulanish komponenti bo'lguncha birlashadi. Barcha bog'langan tarkibiy gismlarni ragamlaymiz va har bir uch uchun uning ulangan gismlarini sonini saglaymiz, shuning uchun har bir uch uchun boshida uning bog'langan komponentlari soni uchning o'zi soniga teng bo'ladi va oxirgi barcha uchlar bir- biriga bog'langan komponentning bir xil raqamlariga tegishli bo'ladi.