Jump to content
IT-პროგრამირების ფორუმი
Sign in to follow this  
gio__gio

რა არის ალგორითმი?

Recommended Posts

 

ალგორითმის პირველი მაგალითი ძველ ბერძენ მათემატიკოსს ევკლიდეს უკავშირდება. ევკლიდე ცხოვრობდა

ძვ. წ. აღ 400-300 წლებში

ევკლიდეს ალგორითმი ითვალისწინებდა უდიდესი საერთო გამყოფის პოვნას ორ ნატურალურ

რიცხვს შორის.trans.giftrans.gif

სიტყვა ალგორითმის წარმოშობა უკავშირდება შუა აზიის ცნობილი მეცნიერის, მუჰამედ იბნ მუსა ალ-ხორეზმის

(Muḥammad ibn Mūsā al-Khwārizmī)

(783-850) სახელს. ხორეზმი მდებარეობს დღევანდელი უზბეკეთის ტერიტორიაზე, ხოლო ალ-ხორეზმი სიტყვა-სიტყვით ნიშნავს ხორეზმში მცხოვრებს.

ალ-ხორეზმის არითმეტიკული ტრაქტატის ლათინური თარგმანი იწყებოდა სიტყვებით “Dixit algorizmi …” – “და თქვა ალხორიზმმა…”

ალგორითმის განმარტებები

ალგორითმი — იმ მოქმედებათა ერთობლიობის ზუსტი და სრული აღწერა, რომელთა მკაცრად განსაზღვრული თანმიმდევრობით შესრულება განაპირობებს დასმული ამოცანის ამოხსნას.

ალგორითმი — მოქმედებათა სასრული მიმდევრობა, რომელთა ზუსტად შესრულების შემთხვევაში აღწევენ დასახულ მიზანს.

WfZBM8e.png

კომპიუტერული მეცნიერებების წარმოშობასა და განვითარებასთან დაკავშირებით, XX საუკუნის თვალსაჩინო მეცნიერის, სტენფორდის უნივერსიტეტის პროფესორის, პროგრამირების

ერთ-ერთი მთავარი იდეოლოგის დონალდ კნუტის მიერ 1968 წ. შემოტანილ იქნა ალგორითმის შემდეგი განმარტება:

ალგორითმი არის ამოცანის ამოხსნისთვის საჭირო ოპერაციების თანმიმდევრობის განმსაზღვრელი წესები.

ალგორითმის თვისებები

სასრულობა – ალგორითმი უნდა გულისხმობდეს სასრული ნაბიჯების შემდეგ დამთავრებას;

განსაზღვრულობა (დეტერმინირებულობა)– ალგორითმის ყოველი ბიჯი და მათი თანმიმდევრობა ზუსტად უნდა იყოს განსაზღვრული;

უნივერსალურობა– შესაძლებელი უნდა იყოს ალგორითმის გამოყენება საწყისი მნიშვნელობების სხვა და სხვა ნაკრებისათვის;

შედეგიანობა– ალგორითმი უნდა სრულდებოდეს გარკვეული შედეგით;

დისკრეტულობა– ალგორითმი უნდა იყოს დაყოფილი ბიჯებად და უნდა ემსახურებოდეს დასმული ამოცანის ამოხსნის პროცესს;

ალგორითმიკა და ინფორმატიკა

ინფორმატიკა – მეცნიერება ინფორმაციის მიღების, დამუშავების, შენახვის და გაცემის შესახებ.

ინფორმატიკა არის მჭიდრო კავშირში კომპიუტერთან, ნებისმიერი კომპიუტერი იმართება პროგრამებით რომლებიც თავის მხრივ მუშაობენ სხვადასხვა ალგორითმით შესაბამისად ალგორითმიკა შეიძლება ჩაითვალოს ინფორმატიკის ბირთვად.

ალგორითმის ჩაწერის ფორმები

ალგორითმის ჩაწერის რამდენიმე მეთოდია ცნობილი:

სიტყვიერი – ეს ნიშნავს ალგორითმის ჩაწერას ბუნებრივ სალაპარაკო ენაზე;

ფსევდოკოდები – ალგორითმის ნახევრად ფორმალიზებული აღწერა რომელიც შეიცავს პროგრამირების ენის ელემენტებს, ასევე ბუნებრივი ენის ფრაზებს და მათემატიკურ აღვნიშნებს;

გრაფიკული – ალგორითმის ჩაწერა ბლოკ-სქემის საშუალებით;

მანქანური ენა – აქ იგულისხმება ფაქტიურად ის ენა, რომელზედაც სრულდება ბრძანებები თავად კომპიუტერში. მაგ. ასემბლერი;

პროგრამული – ნებისმიერი დაპროგრამების ენა: სი, ჯავა, პასკალი, ბეისიკი.

სიტყვიერი ჩაწერის ხერხი

ორ ნატურალურ რიცხვს შორის უდიდესის პოვნის სიტყვიერი ალგორითმი .

1.განსაზღვრეთ ორი რიცხვი.

2.შეადარეთ რიცხვები. თუ რიცხვები ტოლია, მაშინ

გამოიტანეთ შეტყობინება რომ რიცხვები ტოლია, წინააღმდეგ შემთხვევაში განაგრძეთ ალგორითმის სესრულება.

3.განსაზღვრეთ უდიდესი ამ რიცხვთაგან.

4.გამოიტანეთ უდიდესი რიცხვი.

ფსევდოკოდი

ფსევდოკოდი წარმოადგენს აღვნიშნებისა და წესების სისტემას რომელთა დანიშნულებაა ალგორითმის ერთგვაროვანი ჩაწერა. ფსევდოკოდით ჩაწერა განსხვავდება სიტყვიერი ჩაწერის ხერხისგან.

გავიხილოთ ფსევდოკოდით ჩაწერილი ორი ნატურალური რიცხვის შედარების ალგორითმი:

1.შეტანა a,b

2.თუ a=b მაშინ არცერთი

3.თუ a>b მაშინ a

თუ არა მაშინ b

4.უდიდესის გამოტანა

5.დასასრული

ალგორითმის ჩაწერა ბლოკ-სქემის საშუალებით

ალგორითმის ჩაწერის გრაფიკულ ხერხს ალგორითმის ბლოკ-სქემა ეწოდება.

ბლოკ-სქემაში თითოეული მოქმედების ტიპს შეესაბამება გეომეტრიული ფიგურა, რომელიც წარმოდგენილია ბლოკური სიმბოლოს სახით.

მოქმედებებში შეიძლება ჩაითვალოს:

საწყისი მონაცემების შეტანა;

გამოსახულების მნიშვნელობის გამოთვლა;

პირობის შემოწმება;

გამეორებით ოპერაციებს;

მოქმედებათა დასრულებას;

ბლოკი “დასაწყისი-დასასრული

IEYxoHW.gif

ალგორითმის დასაწყისი, დასასრული. ნებისმიერი ბლოქ-სქემა იწყება ან მთავრდება ამ ბლოკით.

Jo5xTru.gif

ბლოკი “შეტანა-გამოტანა”

9DfZkTm.gif

ბლოკი უზრუნველყოფს მონაცემების შეტანის ან გამოტანის ასახვას.

8mAGghb.gif

ბლოკი – “მოქმედება”

qmUkmYg.gif

ბლოკი შესაძლოა ნებისმიერი ოპერაციის თუ ოპერაციათა ნაკრების შესრულების ჩაწერა.

uWN9Kz5.gif

ბლოკი – “პირობა, გადაწყვეტა” (ლოგიკური ბლოკი)

LoRX75U.gif

თითოეულ ასეთ ბლოკში უნდა იყოს ნაჩვენები შედარება, კითხვა ან რაიმე პირობა, რომლის შესრულების ან არ შესრულების მიხედვით ხდება შემდეგ ბიჯზე გადასვლა .

 

ბლოკი – “მოდიფიკაცია”

Fn3boLP.gif

ბლოკი გამოიყენება ციკლის კონსტრუქციებისათვის, ბლოკში ჩაიწერება საწყისი მნიშვნელობა, საბოლოო მნიშვნელობა და მოქმედების შესრულების ბიჯი.

ბლოკი -”წინასწარ განსაზღვრული პროცესი”

htgqMw3.gif

ბლოკი გამოიყენება დამხმარე ალგორითმებში ან ქვეპროგრამებში განსაზღვრულ მოქმედებებზე მიმართვისათვის. პროგრამირებაში გამოიყენება ფუქციების გამოძახების დროს.

ბლოკი -”დოკუმენტი”

0GXgaSl.gif

ბლოკი გამოიყენება იმ შემთხვევაში როდესაც აუცილებელია მითითება რომ მონაცემები უნდა დაიბეჭდოს პრინტერზე.

მანქანური ენა

.cdecls C,LIST, “msp430g2231.h” ;—————————————————————————— .text ; Program Start ;—————————————————————————— RESET mov.w #0280h,SP ; Initialize stackpointer StopWDT mov.w #WDTPW+WDTHOLD,&WDTCTL ; Stop WDT SetupP1 bis.b #001h,&P1DIR ; P1.0 output ; Mainloop bit.b #010h,&P1IN ; P1.4 hi/low? jc ON ; jmp–> P1.4 is set ; OFF bic.b #001h,&P1OUT ; P1.0 = 0 / LED OFF jmp Mainloop ; ON bis.b #001h,&P1OUT ; P1.0 = 1 / LED ON jmp Mainloop ; ; ;—————————————————————————— ; Interrupt Vectors ;—————————————————————————— .sect “.reset” ; MSP430 RESET Vector .short RESET ; .end

მანქანური ენა – ასემბლერი ეს არის მანქანაზე ორიენტირებული ქვედა დონის ენა. ბრძანებები როგორც წესი ემთხვევა კომპიუტერის ბრძანებებს.

მიკრო-კონტროლერისთვის დაწერილი

პროგრამის ნაწყვეტი.

პროგრამირების ენები

პროგრამირების ენა – ეს არის რაღაც სპეციალურად შემუშავებული მომსახურე სიტყვების ერთობლიობა რომელთა გამოყენებით იწერება კომპიუტერული პროგრამა.

პროგრამირების ენები დონეების მიხედვით

 

pnp8YIm.gif?w=800

C – პროგრამირების ენაზე დაწერილი პროგრამის მაგალითი

პროგრამა პოულობს ორ მთელ რიცხვს შორის უდიდეს.

#include<stdio.h>

main()

{

int a,b;

scanf(‘’%d,%d’’,&a,&b);

if(a>b)

printf(‘’a’’);

else

printf(‘’b’’);

}

ალგორითმის ტიპები

XX საუკუნის 70-იან წლებში ნაჩვენები იქნა, რომ ყველა პროგრამა შეიძლება დაწერილ იქნას მხოლოდ სამი, ე.წ. მმართველი სტრუქტურის საშუალებით:

წრფივი ალგორითმები

განშტოებადი ალგორითმები

ციკლური ალგორითმები

მათ გარდა ცალკე შეიძლება გამოვყოთ რეკურსიული ალგორითმები, რომლებიც მართალია ყოველთვის შეიძლება შეიცვალოს ზემოთ სტრუქტურებით, მაგრამ საშუალებას იძლევა ალგორითმი უფრო კომპაქტურად და იოლად ჩაიწეროს.

წრფივი ალგორითმი

jQZIU39.gif

წრფივი ალგორითმები შედგებიან თანმიმდევრულად შესრულებადი ბრძანებებისაგან.

განშტოებადი ალგორითმები

w6oKii8.gif

განშტოებადი ალგორითმები შეიცავენ გარკვეული პირობების შემოწმებას, რომელზეც პასუხის შესაბამისად სრულდება განსხვავებული ბრძანებები.

განშტოებადი ალგორითმის მაგალითი: განვიხილოთ 3 რიცხვს შორის უდიდესის პოვნის ალგორითმი

I1Tny66.gif

(აქ პატარა შეცდომაა. მნიშვნელები არმოწმდება ჯერ ერთმანეთის ტოლია თუ არა. ხო შეიძლება ერთმანეთის ტოლიც იყოს. ამიტომ ყველა ბიჯი სწორად უნდა იყო განსაზღვრული. რადგან ა და ბ ტოლები რომ აღმოჩნდნენ შედეგს ვერ მივიგებდით)

ციკლური ალგორითმი

Poiudt1.gif

ციკლური ალგორითმები გულისხმობენ მოქმედებათა მიმდევრობის მრავალჯერად განმეორებას.

ევკლიდეს ალგორითმი

უდიდესი საერთო გამყოფის პოვნის ალგორითმი ქვემოთ მოყვანილი ალგორითმი აღწერილია ევკლიდეს ”საწყისებში” თუმცა შესაძლოა ის უფრო ადრეც იყო ცნობილი. შემავალი მონაცემები a და b დადებითი რიცხვებისათვის.

a b

16 40

16 24

16 8

8 8

ევკლიდეს ალგორითმის ბლოკ-სქემა

 

 

MoSy9Pe.gif?w=800

ალგორითმის ანალიზი და სირთულე

ალგორითმების შეფასებისას ძირითადად განიხილება ორი ტიპის სირთულე:

სირთულე დროის მიხედვით;

სირთულე მეხსიერების მიხედვით.

 

  • Upvote 4

Share this post


Link to post
Share on other sites

ძაან მაგარი პოსტია. მადლობა

Edited by samuraisxmali
ქართული ასოებით წერეთ.

Share this post


Link to post
Share on other sites

 

>ციკლური ალგორითმები<

 

 

 

 

Data Encryption Standard- მონაცემთა დაშიფრვის სიმეტრიული ალგორითმი, რომელშიც ერთი და იგივე გასაღები გამოიყენება როგორც მონაცემთა დასაშიფრად, აგრთვე მის გასაშიფრად.

მუშაობს მონაცემთა 64-ბიტიან ბლოკებზე, დაშიფრვისთვის იყენებს 56-ბიტიან გასაღებს, აქვს ფეისტელის ქსელის ტიპის 16-ციკლიანი სტრუქტურა.

ალგორითმი იყენებს წრფივ (E, P, IP, FP გადანაცვლებები) და არაწრფივ (s-box კომბინირებულ გარდაქმნებს. DES-ისთვის რეკომენდებულია რამდენიმე რეჟიმი, მაგ., Electronic Code Book (ecb) და Cipher Block Chaining (CBC). აგრეთვე ცნობილია, როგორც მონაცემთა დაშიფრვის ალგორითმი Data Encryption Standard (ინგ. Data Encryption Algorithm). დღესდღეობით მისი გმოყენება აღარ არის რეკომენდებული, მისი შესრულების სინელისა და მოკლე გასაღების გამო, რის გამოც იგი მუდმივი თავდასხმის საშიშროების ქვეშ დგას. Data Encryption Standard-მეთოდი ძირითადად გამოიყენებოდა Unix-პაროლების დასაშიფრად. მისი ყველაზე გავრცელებული ნაირსახეობა იყო triple des .

Share this post


Link to post
Share on other sites

Data Encryption Standard- მონაცემთა დაშიფრვის სიმეტრიული ალგორითმი, რომელშიც ერთი და იგივე გასაღები გამოიყენება როგორც მონაცემთა დასაშიფრად, აგრთვე მის გასაშიფრად.

მუშაობს მონაცემთა 64-ბიტიან ბლოკებზე, დაშიფრვისთვის იყენებს 56-ბიტიან გასაღებს, აქვს ფეისტელის ქსელის ტიპის 16-ციკლიანი სტრუქტურა.

ალგორითმი იყენებს წრფივ (E, P, IP, FP გადანაცვლებები) და არაწრფივ (s-box კომბინირებულ გარდაქმნებს. DES-ისთვის რეკომენდებულია რამდენიმე რეჟიმი, მაგ., Electronic Code Book (ecb) და Cipher Block Chaining (CBC). აგრეთვე ცნობილია, როგორც მონაცემთა დაშიფრვის ალგორითმი Data Encryption Standard (ინგ. Data Encryption Algorithm). დღესდღეობით მისი გმოყენება აღარ არის რეკომენდებული, მისი შესრულების სინელისა და მოკლე გასაღების გამო, რის გამოც იგი მუდმივი თავდასხმის საშიშროების ქვეშ დგას. Data Encryption Standard-მეთოდი ძირითადად გამოიყენებოდა Unix-პაროლების დასაშიფრად. მისი ყველაზე გავრცელებული ნაირსახეობა იყო triple des .

 

იყო რატო? DES, 3DES  დღესაც გამოიყენება ნათელი მაგალითი SSL.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×