If then

Begin

old:=0

new:=1

for i:=2 to n do

begin

next:=old+new;

old:=new;

new:=next;

end;

fib:=next;

end;

end.

Müasir dövrdə proqramlaşdırmada modelləşdirmə üsullarından istifadə mühüm əhəmiyyət kəsb edir. Məlumdur ki, modelləşdirmə fiziki proseslərin, obyektlərin öyrənilməsində istifadə edilir. Bu zaman əsas instrument baxılan prosesin və ya obyektin riyazi modeli götürülür. Yəni adi və ya xüsusi törəməli diferensial tənlik götürülən model əsasında komputerdə hesablama eksprimenti aparılır. Buna ədədi ekspriment deyilir. Ədədi eksprimentin nəticələri analiz edilməklə baxılan obyektin əsas xarakteristikaları müəyyən edilir. Lakin, proqramlaşdırmada modelləşdirmə başqa aspektdə baxılır. Qoyulan məsələnin həllinin tapılması üçün bir çox hallarda təsadüfi ədədlər geniş istifadə olunur (Random). Təsadüfi seçilmiş ədəd əsasında bu və ya digər qərar qəbul edilir. Bu proses o vaxta qədər davam etdirilir ki, məsələ tam həllini tapmış olsun. Proqramlaşdırmada ən çox istifadə olunan üsullardan biri məsələlərin alt məsələlərə bölünməsidir. Bir çox hallarda proqramlaşdırılan məsələ mürəkkəb olduğundan onu bir neçə məsələyə bölürlər və hər məsələ üçün ayrıca proqram tərtib edirlər. Məsələn, tutaq ki, hər hansı bir cədvəldə müəyyən xassəyə malik olan element axtarılır. Burada məsələni iki cür bölmək olar. Birinci elementi yoxlamaq və yerdə qalan elementləri yoxlamaq. Bu zaman alınan məsələlər eyni çətinlikli məsələlər deyil. Adətən məsələlər bölünərkən çalışılır ki, məsələlər eyni dərəcədə çətinliyə malik olsunlar. Məsələn, orta elemti yoxlamaq olar, əgər bu element verilən şərti ödəməzsə, onda iki oxşar çoxluqda elementin axtarışı aparılır. Bu zaman alınan məsələlər eyni çətinlikli olur.

12-54--Paralel hesablamalar.

Məsələlərin həllini tapan paralel hesablama üsulları lap əvvəldən məlum olsa da, yalnız 20-ci əsrin 70-ci illərindən başlayaraq bu üsulları realizə edən komputerlər yaradılmağa başlamışdır. Paralel hesablama dedikdə eyni bir məsələnin həll alqoritminin ayrı-ayrı hissələrinin paralel yerinə yetirilməsi başa düşülür. Məsələn, iki vektorun skalyar hasilinin bu alqoritm ilə tapmaq olur.

Göründüy kimi bu cəmə daxil olan hər bir toplananı digərlərindən asılı olmadan hesablamaq olar. Skalyar hasili tapan alqoritmi paralelləşdirmək olar. Paralel alqoritmləri realizə edən koputerlər iki qrupa bölünür: vektor və paralel komputerlər.

Vektor komputerlər vektorlar üzərində əməliyyatlar aparmaq məqsədilə qurulmuşdur. Bu komputerlər konveyer üsulu ilə işləyir. Bu cür kompüterlərdə hesab qurğusu bir neçə seqmentə bölünür və hər bir seqment müstəqil bu və ya digər əməliyyatı yerinə yetirir. Yuxarıdakı məsələdəki birinci toplananı birinci seqment yerinə yetirir və s. və bu zaman hər bir seqment eyni bir yaddaşa müraciət edir. Paralel komputerlər isə müstəqil işləyən prosessorlardan ibarətdir. Bu zaman qarşıya çıxan əsas problemlər prosessorların yaddaşla əlaqəsini və öz aralarında əlaqəni qurmaqdan ibarətdir. Bütün prosessorlar eyni yaddaşa müraciət etdikdə gecikmə baş verir. Bəzən bu gecikməni aradan qaldırmaq üçün operativ yaddaş seqmentlərə bölünür və hər bir seqment bir prosessora aid edilir. Prosessorlar arasında əlaqə isə birbaşa ümumi şin vasitəsilə ola bilər. Aydındır ki, paralel komputerdə məsələnin həll olunması üçün onun alqoritmi paralelləşdirilməlidir. Tutaq ki, ölçülü A massivini vektoruna vurmaq lazımdır.

A:array [1..n, 1..m] of real;

B:array [1..m] of real; C:array [1..n] of real; s:real;

begin

s:=0;

for j:=1 to m do

s:=s+A[i,j]*B[j];

C[i]:=s;

end.

Bu proqramdan göründüyü kimi hesablama alqoritmini paralelləşdirmək olar.

Deməli, qoyulan məsələni, elementlərinin ayrılıqda hesablanması kimi təsəvvür etmək olar və hər bir elementin hesablanmasını bir prosessora həvalə etmək olar.

Tutaq ki, Puasson tənliyinin ədədi həllinin tapılmasını paralelləşdirmək istəyirik.

Dirixle məsələsi.

Bu məsələnin ədədi həllini qurmaq üçün verilən oblastı diskretləşdirək.

Yəni aşağıdakı kimi şəbəkə quraq:

Tənliyə daxil olan törəmələri bu şəbəkədə aproksimasiya etsək, aşağıdakı sonlu fərq tənliklər sistemini alarıq:

Alınan sistemin hər bir tənliyinə 5 məchul daxildir. Ona görə də bu sistemin matrisi beşdioqanallı matris olur. Bu cür sistemləri birbaşa üsullarla, o cümlədən Qauss üsulu ilə həll etmək sərfəli olmur. Praktikada belə sistemlərin həlli əsasən iterasiya üsulu ilə tapılır (Yakobe, Zeydel və s.). Əgər bi sistemin Yakobi üsulu ilə həllini tapmaq istəsək, onda iterasiya prosesi aşağıdakı kimi olur.

Oblastın sərhəd nöqtələrində axtarılan funksiyanın qiymətləri məlum olduğundan iterasiya prosesi sayda düyün nöqtəsi üçün aparılır. Əgər bu prosesi realizə edən proqramı yazsaq aşağıdakı şəkildə olar:

for i:=1 to do

for j:=1 to do

for i:=1 to do

for j:=1 to do

Burada iterasiya prosesini qurmaq üçün iki ikiölçülü massivdən istifadə edilir. Bunlardan birinci massiv UN[i,j] yeni iterasiyada alınan qiymətləri saxlamaq üçün, ikinci massiv iterasiyadakı qiymətləri saxlamaq üçün istifadə edilir. Proqramdan göründüyü kimi hər bir düyün nöqtəsində axtarılan funksiyanın təqribi qiyməti avtonom şəkildə hesablana bilir. Ona görə də Yakobi üsulunun özü paralel alqoritmdir. Əgər olarsa, düyün nöqtələrinin sayı -a bərabər olur və sayda prosessor olarsa, hər nöqtədəki həlli ayrıca hesablamaq olar. N kifayət qədər böyük olduqda o qədər sadə prosessoru olan komputerin qurulması real olmur. Əgər N=100 olarsa, hər prosessora 16 nöqtə həvalə olarsa, onda məsələnin həlli üçün , P=10000:16=625 prosessor olmalıdır. Lakin bu paralel alqoritmi işləyərkən qarşıya çıxan problemlərdən biri prosessorlar arasındakı informasiya mübadiləsinin təçkilidir. Əgər hər düyün nöqtəsindəki hesablamanı bir prosessor həyata keçirirsə, onda bu düyün nöqtəsindəki hesablamanın nəticələri növbəti iterasiya üçün qonşu prosessorlara ötürülməlidir. Məsələn, i,j nöqtəsindəki prosessor i-1,j i+1,j i,j+1 i,j-1 nöqtələrdəki prosessorlara ötürülməlidir. Bu o deməkdir ki, hər bir prosessor üçün lokal yaddaş ayrılmışsa, 4 prosessorun da bu yaddaşa müraciət imkanı olmalıdır. Yaddaşı prosessorlara görə bölməmək də olar, bu zaman bütün prosessorlar eyni yaddaşa müraciət etməli olur, bu isə müəyyən gecikmələrə səbəb olur. Əgər Laplas tənliyinə baxılsaydı, bu halda da Yakobi üsulu paralel alqoritm olur və hesablamaların sayı nisbətən azalır.

15--P və NP tipli məsələlər

P sözü ingiliscə polinomial sözünün baş hərfindən götürülmüşdür. Alqoritmlər nəzəriyyəsində məsələləri P və NP olmaqla iki sinifə bölürlər. P sinfinə elə məsələlər aid edilir ki, bu məsələlərin sürətli həll alqoritmi mövcuddur və bu məsələlərin həll olunma müddəti ilkin verilənlərin ölçüsündən polinomial asılıdır. Belə məsələlərə misal olaraq ədədlərin toplanması, vurulması, çıxılması, matrislərin vurulması, toplanması, sistem tənliklərin həlli, xətti proqramlaşdırma məsələsi və s. Məsələn, xətti tənliklər sisteminin Qauss üsulu ilə həllində sərf olunan zaman məchulların sayından asılıdır. Koputerdə vurma və bölmə əməliyyatları toplama və çıxmaya nəzərən daha sürətlə yerinə yetirildiyinə görə Qauss üslunda hesablama əməliyyatlarının sayı hesablanarkən yalnız vurma və bölmə əməliyyatlarının sayı hesablanır. Əgər tənliklər sisteminə m sayda məchul daxildirsə, bir məchulun tapılmasına sərf olunan əməliyyatların sayı -ə mütənasib olur. Onda Qauss üsulu ilə sistemin həllinin tapılması üçün sərf olunan əməliyyatların sayı -u ilə mütənasib olur. Ona görə hesablama praktikasında çox vaxt tənliklərin sayı çox olduğundan Qauss üsulundan istfadə etmək sərfəli olmur.

NP məsələlər sinfi elə məsələlər çoxluğuna deyilir ki, bu məsələləri əlavə informasiya əsasında (sertifikat) həllini sürətlə yoxlayan alqoritmlər mövcuddur. Bu məsələlərin həllinin yoxlanılma müddəti ilkin verilənlərin polinomial asılılığından böyük olmur. NP tipli məsələlər misal olaraq səyahətçi məsələsini göstərmək olar. B məsələ aşağıdakı şəkildə qoyulur. Səyahətçi N sayda məntəqəni hər birindən yalnız bir dəfə keçmək şərti ilə ilk dəfə olduğu məntəqəyə qayıtmalıdır. Bu zaman elə marşrut seçilməlidir ki, ən az yol qət etmiş olsun. Əgər marşrutun uzunluğunun ən kiçik

o

2

5

lması yox yola edilən xərc

1

3

7

və ya zamanın minimumunu

n

4

6

əzərdə tutursa, onda

sərf olunan zaman və ya xərc sərf olunana bərabər olmur.

P və NP məsələlər sinfinin eyni olması problemi 40 ildən çoxdur ki, çoxlu tədqiqat işlərinə baxmayaraq açıq qalan problemlərdəndir. Əgər bu siniflər eynidirsə, onda NP sinfinə daxil olan istənilən məsələni sürətli həll edən alqoritmi tapmaq olar.

Misal : Tutaq ki, aşağıdakı ədədlər ardıcıllığı verilib:

-15, -5, -10, 20, 13, 87

Bu ədədlər içərisində cəmi 0-a bərabər olan ədədləri seçmək olarmı?

Bu problemlə məşğul olan tədqiqtaçıların əksəriyyəti bu suala mənfi cavab verirlər. P və NP siniflərinin eyniliyi problemi minilliyin problemləri adlanan siyahıya daxil edilmişdir. Bu siyahıya 7 problem daxildir.

???(problemlərin adı)

13--İnformasiyanın qorunma üsulları

İnformasiya texnologiyasının sürətlə inkişaf etməsi digər bir problemi yaratmışdır. Bu problem informasiyanı əldə etmək hüququ olmayan qrupların ona edilən cəhtlərin qarşısının alınmasıdır. İnformasiyanın emalı, ötürülməsi, qəbulu prosesind istifadəçi əmin olamlıdır ki, aldığı informasiya dəqiqdir. İnformasiyanın alındığı mənbə müəyyəndir və informasiyanı hüququ olmayan qruplar ələ keçirməyib. Müasir dövrdə informasiyanın qorunması ən mühüm problemlərdən biridir. İndiyə qədər informasiyanın ötürülməsi zamamı istifadə edilən mühafizə üsullarını 3 qrupa bölmək olar. İnformasiya mühafizəsinin birinci üsulu informasiyanın maddi daşıyıcılarının –kağız, maqnit lenti, informasiyanı ötürən kanallar, naqil rabitə xəttini və s fiziki mühafizəsidir. Bu zaman digər problemlər də meydana çıxır. İnformasiyanın etibarlı mühafizəsini təmin edən kanalın seçilməsi. Kanala müdaxilə olunarsa, onun vaxtında aşkar olunması və s. probelmlər.

İkinci üsul informasiyanın stenoqrafik üsuludur. Bu üsulda informasiyanın ötürülməsi faktı (məxfi informasiyanın ) gizlədilir. Bu üsulda çoxsaylı variantlardan istifadə etmək olar. Informasiyanın mühafizəsinin müasir dövrdə ən etibarlı hesab edilən üçüncü üsulu kriptoqrafiyadır. Kriptoqrafiya sözü yunan sözləri kriptos və qrafos sözlərindən götürülmüş , hərfi mənası gizli yazı, məxfi yazı deməkdir. Digər üsullardan fərqli bu üsulda informasiyanın ötürülməsi faktı gizlədilmir, lakin informasiya elə şəkilə salınır ki, icazə hüququ olmayan qruplar onu anlaya bilmir. Informasiyanın ötürülməsi zamanı tətbiq olunan kriptoqrafiya sistemi aşağıdakıları təmin etməlidir:

• Məlumatın məzmununun və mənbəyinin yoxlana bilməsi;

• Informasiya mübadiləsi iştirakçılarının özləri tərəfindən saxtalaşdırma və digər pozuntuların aşkar edilməsi və qarşısının alınması.

B aşqa sözlə informasiyanın ötürülməsi zamanı konfidensiallıq, tamlıq və autentikasiya təmin edilməlidir. Konfidensiallığın təmin olunması o deməkdir ki, informasiyaya icazə hüququ olmayan qrupların informasiyayla tanış olması imkanına yol verilməməlidir. Tamlığın təmin olunması informasiyanın icazəsiz dəyişdirilməsinə yol verilməməsi deməkdir. Informasiyanın tamlığına zəmanət vermək üçün informasiyanın dəyişdirildiyini, saxtalaşdırıldığını aşkara çıxaran vasitə olmalıdır. Autentikasiyanın təmin olunması isə mübadilə prosesində iştirak edən tərəflərin identifikasiya edilməsi və informasiyanın özünün həqiqiliyinin təsdiqlənməsidir. Kriptoqrafiya üsulunda informasiyanın açıq kanal vasitəsilə ötürülməsi nəzərdə tutulur və icazə hüququ olmayan qrupun bu kanalla müdaxilə edə biləcəyi nəzərdə tutulur.