Алгоритми

Основните правила на програмите

Какво е алгоритъм?

Алгоритъмът може да се дефинира като „Набор от крайни правила или инструкции, които да се следват при изчисления или други операции за решаване на проблеми“

Алгоритъмът е набор от команди, които трябва да се следват, за да може компютърът да извършва изчисления или други операции за решаване на проблеми.
Според формалната си дефиниция, алгоритъмът е краен набор от инструкции, изпълнявани в определен ред за изпълнение на определена задача.
Това не е цялата програма или код; това е проста логика за проблем, представен като неофициално описание под формата на блок-схема или псевдокод.
Проблем: Проблемът може да се дефинира като проблем от реалния свят или проблем с екземпляр от реалния свят, за който трябва да разработите програма или набор от инструкции. Алгоритъмът е набор от инструкции.
Алгоритъм: Алгоритъмът се определя като процес стъпка по стъпка, който ще бъде проектиран за проблем.
Вход: След проектиране на алгоритъм, на алгоритъма се дават необходимите и желани входове.
Обработващ блок: Входящите данни ще бъдат предадени на обработващия модул, произвеждайки желания резултат.
Изход: Резултатът или резултатът от програмата се нарича изход.

Характеристики на един алгоритъм

Вход: Алгоритъмът изисква някои входни стойности. Алгоритъмът може да получи стойност, различна от 0 като вход.
Изход: В края на алгоритъм ще имате един или повече резултати.
Недвусмисленост: Перфектният алгоритъм се определя като недвусмислен, което означава, че неговите инструкции трябва да са ясни и ясни.
Крайност: Алгоритъмът трябва да е краен. Крайността в този контекст означава, че алгоритъмът трябва да има ограничен брой инструкции, т.е. инструкциите трябва да бъдат преброими.
Ефективност: Тъй като всяка инструкция в алгоритъм засяга цялостния процес, тя трябва да е адекватна.
Езикова независимост: Алгоритъмът трябва да е независим от езика, което означава, че инструкциите му могат да бъдат приложени на всеки език и да дават същите резултати.

Защо имаме нужда от алгоритми?

Мащабируемост: Помага ни да разберем мащабируемостта. Когато имаме голям проблем от реалния свят, трябва да го намалим на малки-малки стъпки, за да анализираме лесно проблема.
Ефективност: Реалният свят не се разделя лесно на по-малки стъпки. Ако проблемът може лесно да бъде разделен на по-малки стъпки, това означава, че проблемът е осъществим.

Как да проектираме алгоритъм?

За да напишете алгоритъм, са необходими следните неща като предпоставка:

Проблемът, който трябва да бъде решен чрез този алгоритъм, т.е. ясна дефиниция на проблема.
При решаването на проблема трябва да се имат предвидограниченията на проблема.
Входната, която трябва да се вземе за решаване на проблема.
Резултатътсе очаква, когато проблемът бъде решен.
Решението на този проблем е в рамките на дадените ограничения.

След това алгоритъмът се записва с помощта на горните параметри, така че да решава проблема.

Сега ще разгледаме пример за алгоритъм в програмирането.

Ще напишем алгоритъм за събиране на две числа, въведени от потребителя.

Следните стъпки са необходими за добавяне на два номера, въведени от потребителя:

Step 1: Start
Step 2: Declare variables num1, num2 and sum. 
Step 3: Read values num1 and num2. 
Step 4: Add num1 and num2 and assign the result to sum.
        sum←num1+num2 
Step 5: Display sum 
Step 6: Stop

Фактори на един алгоритъм

Следните са факторите, които трябва да имате предвид при проектирането на алгоритъм:

Модулност: Тази функция е идеално проектирана за алгоритъма, ако получите проблем и го разделите на малки-малки модули или малки-малки стъпки, което е основно определение за алгоритъм.
Коректност: Коректността на алгоритъма се определя, когато дадените входни данни произвеждат желания резултат, което показва, че алгоритъмът е проектиран правилно. Анализът на алгоритъма е завършен правилно.
Поддържаемост: Това означава, че алгоритъмът трябва да бъде проектиран по ясен, структуриран начин, така че когато предефинирате алгоритъма, да не се правят значителни промени в него.
Функционалност: Взема предвид различни логически стъпки за решаване на проблем от реалния свят.
Устойчивост: Устойчивостта се отнася до способността на алгоритъма да дефинира ясно вашия проблем.
Удобен за потребителя: Ако алгоритъмът е труден за разбиране, дизайнерът няма да го обясни на програмиста.
Простота: Ако един алгоритъм е прост, той е лесен за разбиране.
Разширяемост: Вашият алгоритъм трябва да бъде разширяем, ако друг дизайнер или програмист на алгоритъм иска да го използва.

Значение на алгоритмите

Теоретична важност: Когато ни бъде даден проблем от реалния свят и ние разделяме проблема на малки-малки модули. За да разбием проблема, трябва да знаем всички теоретични аспекти.
Практическо значение: Както знаем, теорията не може да бъде завършена без практическо приложение. Така че значението на алгоритмите може да се разглежда както като теоретично, така и като практическо.

Подходи на алгоритъма

По-долу са използваните подходи след разглеждане както на теоретичното, така и на практическото значение на проектирането на алгоритъм:

Алгоритъм за груба сила: Общата логическа структура се прилага за проектиране на алгоритъм. Известен е също като алгоритъм за изчерпателно търсене, който търси всички възможности, за да предостави необходимото решение. Такива алгоритми са два вида:

Оптимизиране: Намиране на всички решения на проблем и след това изваждане на най-доброто решение или ако стойността на най-доброто решение е известна, то ще се прекрати, ако е известно най-доброто решение.
Жертва: Веднага щом се намери най-доброто решение, то ще спре.

Разделяй и владей: Това е реална реализация на алгоритъм. Тя ви позволява да проектирате алгоритъм във вариант стъпка по стъпка. Той разбива алгоритъма за решаване на проблема по различни методи. Позволява ви да разделите проблема на различни методи и валиден изход се произвежда за валидния вход. Този валиден изход се предава на друга функция.
Алчен алгоритъм: Това е парадигма на алгоритъм, която прави оптимален избор при всяка итерация с надеждата да получи най-доброто решение. Той е лесен за изпълнение и има по-бързо време за изпълнение. Но има много редки случаи, в които предоставя оптималното решение.
Динамично програмиране: Прави алгоритъма по-ефективен чрез съхраняване на междинните резултати. Следва пет различни стъпки за намиране на оптималното решение на проблема:

Той разделя проблема на подпроблем, за да намери оптималното решение.
След като разбие проблема, той намира оптималното решение от тези подпроблеми.
Съхранява резултата от подпроблемите, известен като запаметяване.
Използвайте повторно резултата, така че да не може да бъде преизчислен за същите подпроблеми.
Накрая изчислява резултата от сложната програма.

Алгоритъм за разклоняване и обвързване: Алгоритъмът за разклоняване и обвързване може да се приложи само към проблеми с целочислено програмиране. Този подход разделя всички набори от възможни решения на по-малки подмножества. Тези подгрупи се оценяват допълнително, за да се намери най-доброто решение.
Рандомизиран алгоритъм: Както видяхме в обикновения алгоритъм, имаме предварително дефинирани вход и изискван изход. Тези алгоритми, които имат определен набор от входове и изискван изход и следват някои описани стъпки, са известни като детерминистични алгоритми. Какво се случва, когато случайната променлива бъде въведена в рандомизирания алгоритъм? В рандомизиран алгоритъм някои произволни битове се въвеждат от алгоритъма и се добавят към входа, за да се получи изходът, който е случаен по природа. Рандомизираните алгоритми са по-прости и по-ефективни от детерминирания алгоритъм.
Обратно проследяване: Обратното проследяване е алгоритмична техника, която решава проблема рекурсивно и премахва решението, ако не отговаря на ограниченията на проблем.

Основните категории алгоритми са дадени по-долу:

Сортиране: Разработен алгоритъм за сортиране на елементите в определен ред.
Търсене: Алгоритъм, разработен за търсене на елементи в структура от данни.
Изтриване: Алгоритъм, разработен за изтриване на съществуващ елемент от структурата на данните.
Вмъкване: Алгоритъм, разработен за вмъкване на елемент в структура от данни.
Актуализация: Алгоритъм, разработен за актуализиране на съществуващия елемент в структура от данни.

Как да анализираме алгоритъм?

За да бъде добър един стандартен алгоритъм, той трябва да е ефективен. Следователно ефективността на алгоритъма трябва да се проверява и поддържа. Може да бъде на два етапа:

Приоритен анализ: „Приори“ означава „преди“. Следователно априорният анализ означава проверка на алгоритъма преди неговото прилагане. При това алгоритъмът се проверява, когато е написан под формата на теоретични стъпки. Тази ефективност на алгоритъм се измерва, като се приеме, че всички други фактори, например скоростта на процесора, са постоянни и нямат ефект върху изпълнението. Това обикновено се прави от дизайнера на алгоритъма. Този анализ е независим от вида на хардуера и езика на компилатора. Дава приблизителните отговори за сложността на програмата.
Постериорен анализ: „Постериорен“ означава „след“. Следователно постериорният анализ означава проверка на алгоритъма след неговото прилагане. При това алгоритъмът се проверява чрез внедряването му на произволен език за програмиране и изпълнението му. Този анализ помага да се получи действителен и реален отчет за анализ относно коректността (за всеки възможен вход/и, ако показва/връща правилен изход или не), необходимото пространство, изразходваното време и т.н. Това означава, че зависи от езика на компилатора и вида на използвания хардуер.

Какво е сложност на алгоритъма и как да го намерите?

Един алгоритъм се определя като сложен въз основа на количеството пространство и време, които консумира. Следователно сложността на алгоритъма се отнася до мярката за времето, което ще му трябва, за да изпълни и получи очаквания изход, и пространството, което ще му е необходимо за съхраняване на всички данни (вход, временни данни и изход). Следователно тези два фактора определят ефективността на алгоритъма.
Двата фактора на сложността на алгоритъма са:

Фактор време: Времето се измерва чрез преброяване на броя ключови операции, като например сравнения в алгоритъма за сортиране.
Коефициент на пространство: Пространството се измерва чрез отчитане на максималното пространство в паметта, необходимо на алгоритъма за стартиране/изпълнение.

Следователно сложността на алгоритъма може да бъде разделена на два вида:

Времева сложност

Количеството време, необходимо за завършване на изпълнението на алгоритъма, се нарича времева сложност. Нотацията с голямо O се използва за представяне на времевата сложност на алгоритъма. Асимптотичното обозначение за описване на времевата сложност в този случай е голямо О. Времевата сложност се изчислява основно чрез преброяване на броя стъпки, необходими за завършване на изпълнението. Нека разберем времевата сложност чрез пример.

sum=0;  
// Suppose we have to calculate the sum of n numbers.  
for i=1 to n  
sum=sum+i;  
// when the loop ends then sum holds the sum of the n numbers  
return sum;

В горния код времевата сложност на оператора за цикъл ще бъде поне n и ако стойността на n се увеличи, тогава времевата сложност също се увеличава. Докато сложността на кода, т.е. върнатата сума ще бъде постоянна, тъй като нейната стойност не зависи от стойността на n и ще предостави резултата само в една стъпка. Обикновено считаме най-лошата времева сложност, тъй като това е максималното време, необходимо за всеки даден входен размер.

Космическа сложност

Количеството пространство, което алгоритъмът изисква, за да реши проблем и да произведе изход, се нарича неговата пространствена сложност. Пространствената сложност, подобно на времевата сложност, се изразява в голямо О.

Мястото е необходимо за алгоритъм поради следните причини:

За съхраняване на програмни инструкции.
За съхраняване на проследяване на постоянни стойности.
За съхраняване на проследяване на променливи стойности.
За съхраняване на проследяване на извиквания на функции, оператори за прескачане и т.н.

Сложност на пространството = Помощно пространство + Размер на входа

Как да изразя алгоритъм?

Естествен език:- Тук изразяваме алгоритъма на естествения английски език. Твърде трудно е да се разбере алгоритъма от него.
Flow Chat:- Тук изразяваме алгоритъма, като правим графично/изобразително представяне на него. По-лесен е за разбиране от естествения език.
Псевдо код:- Тук изразяваме алгоритъма под формата на анотации и информативен текст, написан на обикновен английски, който е много подобен на истинския код, но тъй като няма синтаксис като който и да е от езиците за програмиране, не може да се компилира или интерпретира от компютъра. Това е най-добрият начин да се изрази алгоритъм, защото може да бъде разбран дори от неспециалист с познания по програмиране на училищно ниво.

Видове алгоритми

Следват видовете алгоритми:

Алгоритъм за търсене
Алгоритъм за сортиране

Всеки ден търсите нещо в ежедневието си. По същия начин, в случай на компютър, в компютъра се съхранява голямо количество данни и всеки път, когато потребителят поиска данни, компютърът търси тези данни в паметта и ги връща на потребителя. Има основно два метода за търсене на данни в масив:

Алгоритъмът за търсене е два вида:

Линейно търсене

Линейното търсене е прост алгоритъм, който започва търсенето на елемент или стойност в началото на масив и продължава, докато желаният елемент не бъде намерен. Той сравнява търсения елемент с всички елементи в масива; ако се намери съвпадение, се връща индексът на елемента; в противен случай се връща -1. Този алгоритъм може да се приложи към несортиран списък.

Двоично търсене

Двоичният алгоритъм е най-основният алгоритъм и той търси елементи много бързо. Използва се за намиране на елемент в сортиран списък. За да се приложи двоичният алгоритъм, елементите трябва да се съхраняват в последователен ред или да се сортират. Ако елементите се съхраняват на случаен принцип, двоичното търсене не може да бъде приложено.

Алгоритъм за сортиране

Алгоритмите за сортиране пренареждат елементите в масив или дадена структура от данни във възходящ или низходящ ред. Операторът за сравнение решава новия ред на елементите.

Защо се нуждаем от алгоритъм за сортиране?

Необходим е ефективен алгоритъм за сортиране за оптимизиране на ефективността на други алгоритми като алгоритъм за двоично търсене, тъй като алгоритъмът за двоично търсене изисква масив да бъде сортиран в определен ред, главно във възходящ ред.
Той произвежда информация в сортиран ред, който е четим от хора формат.
Търсенето на определен елемент в сортиран списък е по-бързо от несортирания списък.

Предимства на алгоритмите

Лесно е за разбиране.
Алгоритъмът е поетапно представяне на решение на даден проблем.
В алгоритъма проблемът е разбит на по-малки части или стъпки, следователно за програмиста е по-лесно да го преобразува в действителна програма.

Недостатъци на алгоритмите

Писането на алгоритъм отнема много време, така че отнема много време.
Разбирането на сложна логика чрез алгоритми може да бъде много трудно.
Изявленията за разклоняване и цикъл са трудни за показване в Алгоритми.

Заключение

В заключение, алгоритмите преобразиха нашия свят, предоставяйки ни нови възможности и ефективност. Трябва обаче да останем бдителни и проактивни, за да гарантираме, че алгоритмите са разработени, внедрени и регулирани по начин, който е в съответствие с нашите етични ценности и обществено благополучие. Правейки това, можем да впрегнем силата на алгоритмите, за да създадем по-приобщаващо, честно и справедливо бъдеще за всички.

Заключителни бележки

Надявам се, че сте научили нещо! Ако има нещо, което бихте искали да добавите към тази статия, не се колебайте да оставите съобщение и не се колебайте!

Всякакви отзиви наистина се оценяват. Моля, споделете това! Благодаря!