Тема 1: Теория на алгоритмите 1
Изтегляне 245 Kb.
|
Свързани:
My Christmas vacation essay Hristo Yonchev, Create New Doc 09-11-2023 21.49, Êóðñîâ ïðîåêò ¹1, Êóðñîâ ïðîåêò ¹1 2, Êóðñîâ ïðîåêò ¹1 3, Реферат ХИВ
Основни понятияТерминът алгоритъм се свързва с името на средновековния узбекски математик Ал. Хорезъм, който в IX век формулирал алгоритмите, по които и досега се извършват четирите аритметични действия в десетичната бройна система: събиране, изваждане, умножение и деление. Днес думата алгоритъм е излязла извън границите на математиката, употребява се в най-различни области и означава точно формулирано правило за достигане до определен резултат. Една от най-сполучливите описателни дефиниции на понятието алгоритъм е дал основоположникът на съвременната теория на алгоритмите – руския учен А. Макаров. Тя гласи: Алгоритъм се нарича точно и общоразбираемо предписание, определящо изпълнението на последователност от елементарни операции, чрез които се решава клас от еднотипни задачи. На всеки алгоритъм са присъщи следните основни свойства: Определеност – това свойство означава точност и яснота, които не допускат двусмислие и не оставят място за произвол при изпълнение на елементарните операции; Масовост – алгоритъмът да служи не само за решаване на конкретни задачи, а за решаване на цял клас от еднотипни задачи; Резултатност – гаранция, че след изпълнение на краен брой елементарни операции при произволно допустими стойности на началните данни ще се стигне до търсения резултат; Дискретност – алгоритъмът се състои от краен брой елементарни предписания. Всяко от тях дава указания за изпълнение на една елементарна операция. Всяко предписание посочва своя логически приемник – елементарното предписание, което ще се изпълни след него. Вместо елементарно предписание се употребяват термините инструкция, заповед, команда, правило или оператор. Всеки алгоритъм има една начална инструкция и поне една крайна (последна) инструкция. Всички инструкции, без последните, посочват безусловно или условно приемника си. Когато приемникът е един, той се посочва безусловно, а при повече условно. Например когато са два, в зависимост от верността и неверността на условието се преминава към изпълнение на една от двете възможни инструкции. Преминаването към следващата инструкция се нарича преход. Да разгледаме широко известния алгоритъм на Евклид за определяне на най-големия общ делител на две цели положителни числа А и В. В съвременна форма той се излага по следния начин: 1. Вземи стойностите на А и В. 2. Ако А=В тогава : премини към инструкция 5. 3. Ако А>В тогава : приеми разликата А-В за нова стойност на А, иначе : приеми разликата В-А за нова стойност на а В. 4. Премини към инструкция 2. 5. Съобщи последната стойност на А. 6. Край. Прието е, че ако в някоя инструкция не е указана явно следващата я, се спазва “естествената последователност“, т.е. изпълнява се инструкцията със следващ номер. Инструкция 2 не указва приемник, когато АВ. Съгласно приетата по-горе уговорка, приемникът в този случай е инструкция 3. За определяне на най-големия общ делител на числата А=12 и В=8 инструкциите на този алгоритъм ще се изпълнят в реда, даден в таблицата:
Очевидно, следвайки този алгоритъм, всеки, който може да сравни две числа и да намери разликата им, може да намери най-големия общ делител на две цели положителни числа. Изтегляне 245 Kb. Сподели с приятели:
|