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

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

Ние ще разглеждаме алгоритмите предназначени за изпълнение от компютър. Алгоритъмът е последователност от инструкции (указания, команди, стъпки, оператори) за действие, която при изпълнението си реализира зададена функционална зависимост между данните и резултатите. Ако последователността не реализира зададената функционална зависимост, тя не е алгоритъм на дадената задача.

Във всяка инструкция се указват всички или някои от следните елементи:

• Каква операция или операции се извършват;
• Какви са нейните аргументи и резултатите от изпълнението ѝ;
• Коя е следващата инструкция за изпълнение. Номерът на следващата инструкция най-често не се указва явно в к-та инструкция и в такъв случай това е к+1-та инструкция: естествен ред. В други случаи (инструкции за безусловен и условен преход) номерът на следващата или следващите инструкции се указва ясно.

Запис (представяне, описание) на алгоритмите:

Словесно описание:

Много чество в литературата се използва модификация на този начин, наричана псевдокод (например псевдо Паскал), в който за по-голяма еднозначност и разбираемост освен текст на естествен език се използват типови инструкции (най-често от структурното програмиране): последователна инструкция (съставен оператор) begin И1; И2; ... ; Иn end, условна инструкция if условие then И1 или if условие then И1 then И2; инструкция <,>case израз of c1: И1; с2: И2; ... ; cn: Иn end, инструкция за цикъл while условие do И, или repeat И1, ... , Иn until условие, или цикъл for и други.

Предимство на този начин е, че заема малко място върху хартия и е предназначен за четене от човек. Недостатъка му е, че при текст на естествен език може да се получи нееднозначност (която може да бъде изяснена допълнително, ако възникне) и поради това не може да се изпълнява от компютър.

Свойства на Алгоритми

• Детерминираност (определеност): Независимо от изпълнителя и броя на изпълненията на алгоритъма на всяка стъпка при едни и същи входни данни се изчислява един и съш резултат.
• Масовост: Алгоритъмът да може да се прилага не само при решаване на една конкретна задача, а да намира решение на цял клас от еднотипни задачи.

• Крайност и резултатност: След краен брой стъпки алгоритъмът трябва да завърши изпълнението си, като изходът може да е изчислен резултат или съобщение за неприложимостта му за конкретните начални данни.
• Дискретност: Означава, че действията се изпълняват на стъпки и едва след приключването на дадена стъпка се преминава към точно определена следваща стъпка.

• Време на изпълнение на алгоритъма (времева сложност, сложност по време, бързодействие, time complexity) - ще я означаваме T;
• Необходима памет (сложност по предмет, space complexity) - ще я означаваме с П. Това е количеството информация, която трябва да се помни по време на изпълнение на алгоритъма;
• Дефиниционна област;
• Точност - отнася се само за числените алгоритми, в които основни са аритметичните операции с числа от реален тип. Не се отнася за алгоритмите, работещи с цели числа и символна информация, които не допускат грешка. Тази характеристика показва каква е максималната грешка, която алгоритъмът допуска в резултата.