1. To'plamlar, ularning berilish usullari va ular ustida amallar

4 7-savol.Ford Algoritmi

48.Floyd algoritmi.

j, k ning uchta tepasi bor va ular orasidagi masofa belgilanadi. Agar tengsizlik a[i,k]+a[k,j]j yo'lini i->k->j bilan almashtirish tavsiya etiladi. Qadam 0. A0 masofasining dastlabki matritsasini va S0 vertexlarining ketma-ketligini aniqlang. Har ikkala matritsaning har bir diagonali elementi 0ga teng, shuning uchun bu elementlarning hisob-kitoblarda ishtirok etmasligini ko'rsatmoqda. K = 1 ga ishonamiz.
Asosiy qadam k. k satrini va k ustunini etakchi satr va etakchi ustun sifatida belgilang. Yuqorida tavsiflangan AK-1 matritsasining barcha elementlariga[i, j] almashtirishni ko'rib chiqamiz. Agar tengsizlik a[i,k]+a[k,j]A[i,k]+a[k,j] miqdori uchun A[i,j] elementining Ak-1 matritsasini almashtirish orqali Ak matritsasini yarating] ;
k ga SK-1 element s[i,j] matritsasini almashtirish orqali Sk matritsasini yarating.
Shunday qilib, Floyd algoritmi n yinelemelerini qiladi, a matritsasining i-yinelemesinden keyin, bu yo'llar birinchi dan i-chigacha bo'lgan tepaliklardan o'tishi sharti bilan, har qanday ikki juftlik orasidagi eng qisqa yo'llarning uzunligini o'z ichiga oladi. Har bir iteratsiya bo'ylab barcha juftlar ko'chib o'tadi va ularning orasidagi yo'l i-tepa yordamida kamayadi

49. Bul ayniyatlari.

Mantiqiy funksiyaning rostlik qiymati {1, 0} to’plam elеmеntlaridan iborat. Aniqlanish va o’zgarish sohalari {1, 0} to’plamdan iborat bo’lgan funksiyalarga Bul funksiyaslari dеyiladi.
Bul funksiyasi – argumenti hamda unga mos funksiyasi ikki elementli to’plam {0,1} ga tegishli qiymatni qabul qiluvchi funksiyadir. Bu to’plamni bir elementli darajaga tushirib bo’lmaydi, chunki funksiya tushunchasiga zid bo’ladi. Shunday qilib Bul funksiyasi funksiyalar ierarxiyasining eng birinchi qatlamini egallaydi.

1-ta'rif: {0,1} to’plam qiymatini qabul qiluvchi x o’zgaruvchi bul (mantiqiy, ikkilik) o’zgaruvchisi deyiladi. Ikkilik o’zgaruvchilar ikkilik sanoq sistemasida ma'lumotlarni uzatishda foydalaniladi.

2-ta'rif: bul o’zgaruvchisi orqali aniqlanuvchi hamda {0,1} to’plam qiymatini qabul qiluvchi funksiya Bul funksiyasi deyiladi.

50. Formulalarning teng kuchliligi.