Разлика между версии на „Алгоритъм“

Текуща версия към 12:58, 8 април 2014

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

Същност

Елементарно действие (стъпка) е действие, което не се нуждае от допълнителни указания, за да бъде извършено. Терминът „алгоритъм” произлиза от името на арабския математик Ал-Хорезми, който в свой научен трактат описва алгоритъм за представяне на числа в десетична бройна система.

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

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

Пример

Баща и двамата му трябвало да преминат пълноводна река. Намерили малка лодка, която може да превозва не повече от 120 кг товар. Как да преминат реката, ако бащата тежи 100 кг, а синовете му съответно 50 кг и 60 кг?

Алгоритъм:

Двамата синове преминават на отсрещния бряг;
Единият син връща лодката;
Бащата преминава реката;
Вторият син връща лодката;
Двамата синове преминават реката;
Край на алгоритъма.

Вижте още

Източници

John H. Conway, Richard Guy, The Book of Numbers
Ian Stewart, Galois Theory, Third Edition (Chapman Hall/CRC Mathematics Series)
Michael Spivak, Calculus, 4th edition
S. MacLane, Mathematics: Form and Function
Clifford A. Pickover, The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics (Sterling Milestones)

Външни препратки

@@ Ред 1: / Ред 1: @@
-Алгоритъм е точното и разбираемо за изпълнителя описание на [[действие|действията]], които трябва да се извършат, за да се постигне определен [[резултат]]. По точно казано алгоритъм е строго определената [[последователност]] от [[действие|действия]], през които трябва да се премине, за да се изпълни дадена задача. В областите [[математика]], [[лингвистика]], [[информатика]] и други, термина алгоритъм е често срещан и се свързва предимно със [[изчисления]] и с [[обработка на данни|обработка на дадени данни]].
+'''Алгоритъм''' – '''система от краен брой елементарни действия със зададен ред на изпълнението им''', които водят до решаване на определен проблем.
-                                                                                                                                                              '''''История'''''
+В ежедневието си човек извършва '''[[дейност]]и, които се изпълняват по предварително заучени правила и определена последователност''' – напр. събирането на числа, избирането на телефонен номер, карането на кола и др. Казваме, че тези дейности са '''алгоритмизирани'''.
-Формирането на понятието идва с опитите да се реши 10-тия [[[http://bg.wikipedia.org/wiki/Хилбертови_проблеми проблем на Хилберт]]] „[[Задача за разрешимост на [http://bg.wikipedia.org/wiki/Диофантово_уравнение диофантово уравнение]]]“. Които [[Давид Хилберт]] поставя през 1900 година на Втория световен конгрес по [[математика]] в Париж. Последващите формализации представляват опити да се дефинира „[[ефективна изчислимост]]“ (Клини 1943:274) или „[[ефективен метод]]“ (Росър 1939:225); включват рекурсивните функции на Ербран-Гьодел-Клини от 1930, 1934 и 1935 година, ламбда смятането на [[Алонсо Чърч]] от 1936, „[[Формулировка 1]]“ на [[[http://bg.wikipedia.org/w/index.php?title=Емил_Пост&action=edit&redlink=1 Емил Пост]]] от 1936, и [[[http://bg.wikipedia.org/wiki/Машина_на_Тюринг машината на Тюринг]]] от 1936-7 и 1939 година. Класически пример за алгоритъм е [[Алгоритъмът на Евклид]].Това е [http://bg.wikipedia.org/wiki/Алгоритъм алгоритъм] за намиране на [http://bg.wikipedia.org/wiki/Най-голям_общ_делител най-големия общ делител] (НОД) на две [http://bg.wikipedia.org/wiki/Естествено_число естествени числа]. Той е един от първите публикувани алгоритмии е бил описан е в книгата на [[Евклид]] „[http://bg.wikipedia.org/wiki/Елементи Елементи]“ около 300 г. пр.н.е.                                                                                                                                                                       '''''Формализации'''''
+==Същност==
+Елементарно действие (стъпка) е действие, което не се нуждае от допълнителни указания, за да бъде извършено. Терминът „алгоритъм” произлиза от името на арабския математик Ал-Хорезми, който в свой научен [[трактат]] описва алгоритъм за представяне на числа в [[десетична бройна система]].
-Алгоритмите играят важна роля при изчислението на данни в [[компютър|компютрите]].При създаването на много [[компютърни програми]] се въвеждат алгоритми ,чрез които се определя точно определена [[последователност]] на действие при изпълнение на определени задачи.Тук алгоритъмът може да се разглежда и като произволна поредица от операции, които могат да се симулират от [[[http://bg.wikipedia.org/w/index.php?title=Пълнота_по_Тюринг&action=edit&redlink=1 пълна по Тюринг]]] система.
+Алгоритмите могат да бъдат описвани:
-При съставянето на алгоритъм е необходимо на първо място да се представи сложното действие чрез [[последователност]] от по-прости действия, достъпни за [[изпълнител]]я. Също така трябва да използвате само елементарни (за [[изпълнител]]я) действия. Не по малко важно е да опише ясно и точно последователността, в която трябва да се изпълняват елементарни действия.
+*словесно (чрез думи);
+*чрез специални знаци, представящи дадени действия;
+*чрез блок-схеми (общоприети графични схеми, в които действията се вписват в геометрични фигури, а стрелки определят [[ред]]а им);
+*чрез компютърни програми.
-'''Представяне'''
+==Пример==
-Най-често срещаните начини за представяне на алгоритмите са чрез [[естествени езици]], [[псевдокод]], [[блок-схеми]] или [[програмни езици]].Чрез [[естествени езици]] предимно се представят по простите алгоритми, защото при по сложните алгоритми може да се стигне до неразбиране и не напълно определяне на [[последователност]]та и същността на процесите. [[Псевдокодът]] е начин да бъде описан [http://bg.wikipedia.org/wiki/Алгоритъм алгоритъм] или характеристика на [http://bg.wikipedia.org/wiki/Език_за_програмиране език за програмиране], без да се ангажира читателя с конкретен език.Алгоритмите се представят с [[блок-схеми]]те чрез геометрични фигури, като всяка от тях има свое собствено значение.При създаването на [[блок-схема]] трябва да се вземат под внимание следните елементи: началото, което се вписва в елипса; входът, от който зависи резултатът и без който алгоритъмът не може да се създаде; оператор 1,2,3…. , той зависи от броя на извършваните операции и всяка операция се записва в отделен квадрат и се поставят една под друга (тук могат да се въведе и условност, която се описва чрез „да” или „не” т.е. отговаря се дали може да се изпълни дадения процес); последните две части са изходът и края на [[блок-схема]]та.Чрез [[програмни езици|програмните езици]] се изразяват алгоритми в изпълним от компютър вид, но често се ползват и за да онагледяват, дефинират или документират алгоритмите. [[Image:algoritym_pic_1.png|thumb|right|alt=blok shema.|Блок схема.]]
+Баща и двамата му трябвало да преминат пълноводна река. Намерили малка лодка, която може да превозва не повече от 120 кг товар. Как да преминат реката, ако бащата тежи 100 кг, а синовете му съответно 50 кг и 60 кг?
-           '''''Класификация на алгоритмите.'''''
+Алгоритъм:
+#Двамата синове преминават на отсрещния бряг;
+#Единият син връща лодката;
+#Бащата преминава реката;
+#Вторият син връща лодката;
+#Двамата синове преминават реката;
+#Край на алгоритъма.
-Съществуват различни начини на класификация на алгоритмите.
+==Вижте още==
-===Според имплементацията    ===
+*[[Математика]]
+*[[Геометрия]]
+*[[Видове алгоритми]]
+*[[Свойства на алгоритмите]]
+*[[Процес]]
+*[[Комбинаторика]]
-Рекурсивни или итеративни
+==Източници==
-Рекурсивният е този, който прави поредица от обръщения към себе си докато не се изпълни действието. За да решат същите задачи, итеративните алгоритми използват повтарящи се конструкции ([http://bg.wikipedia.org/w/index.php?title=Програмен_цикъл&action=edit&redlink=1 цикли]), а понякога и допълнителни структури от данни като [http://bg.wikipedia.org/wiki/Стек стекове].
+*John H. Conway, Richard Guy, The Book of Numbers
+*Ian Stewart, Galois Theory, Third Edition (Chapman Hall/CRC Mathematics Series)
+*Michael Spivak, Calculus, 4th edition
+*S. MacLane, Mathematics: Form and Function
+*Clifford A. Pickover, The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics (Sterling Milestones)
-Логически
+==Външни препратки==
-Алгоритъмът може да се разглежда като контролирана логическа [[[http://bg.wikipedia.org/wiki/Дедукция дедукция]]].Според [[Роберт Ковалски]] алгоритъмът се състой от две основно части – [[логика]] и [[управление]].
+*[http://docs.google.com/viewer?a=v&q=cache:uwR6hdFaRqoJ:elearning-phys.uni-sofia.bg/~vgi/Lect4.pdf+комбинаторика+формули&hl=bg&gl=bg&pid=bl&srcid=ADGEESiD0diBTNUWAx8eqKFRtKok_F-dk-fPl09wWHRzpRuzZTSIdRdOq34XpSDVTycpd_S5XeVmU10f8Um2Oj426JSUvCdZwuon0NfZuwmdO9_iI4z_LW4huTjg37SpxlsqMUSTiSMU&sig=AHIEtbRj33jt-6ujHjJwZdyBRuqEtcux1g Основни формули на комбинаториката]
+*[http://www.math10.com/bg/algebra/veroiatnosti.html Теория на вероятностите]
+*[http://harta-bg.info/statia/99 Развитие на математиката]
+* [http://www.ist-world.org/ResultPublicationDetails.aspx?ResultPublicationId=49e683d81c8c41dd8ed3016a4d108e3d Изчисляване на претегления коефициент на фенотипна корелация между количествени признаци в малки нееднородни извадки]
-Серийни, паралелни или разпределени
+[[category:Математика]][[category:Кибернетика]]
-Серийните алгоритми са тези, който изпълняват една команда на един така както при [[компютри|компютрите]] се приема, че една задача се изпълнява на един такт. Паралелните алгоритми се прилагат тогава когато има няколко процесора и тези няколко процесора едновременно обработват и прилагат различните алгоритми. Разпределените алгоритми се осъществяват чрез свързването на няколко машини в една мрежа. Паралелните и разпределените алгоритми се различават от серийните по това ,за разлика от серийните паралелните и разпределителните разбиват задачите на подзадачи. [[Image:algoritym_pic_2.jpg|thumb|right|alt=razpredelitelen algoritym.|Разпределителен алгоритъм.]]
-Детерминирани и недетерминирани
-Детерминираните алгоритми използват една и съща процедура за решаването на задачите като и резултатът е един и същ. При недетерминираните се използват различни начини и подходи за решаването на поставените задачи, които методи се базират на [[евристика|евристики]] и случайност.
-Точни и приблизителни
-При все че много алгоритми достигат до точно решение на даден проблем, по различни причини в практиката се използват и приблизителни алгоритми, които (по горната класификация) могат да бъдат както недетерминирани, така и детерминирани.                          '''Според дизайна'''
-Някои често срещани принципи в [[дизайн]]а на алгоритми са следните:
-[[Динамично програмиране]]
-Когато за дадена задача се знае, че до оптималното решение може да се стигне чрез базиране на оптималните решения на поредица подзадачи, и то такива припокриващи се подзадачи, до които се свежда решаването и на други видове задачи, то се прилага един по-бърз подход, наречен [[[http://bg.wikipedia.org/w/index.php?title=Динамично_програмиране&action=edit&redlink=1 динамично програмиране]]].Чрез този принцип се избягва повторното решение на задачите.
-„[[Разделяй и владей]]“
-Това е процес, при който даден проблем се непрестанно се раздробява на по-малки проблеми докато се стигне до там те да могат да се решат по-лесно. Основната разлика между [[динамично програмиране|динамичното програмиране]] и „[[разделяй и владей]]“ е, че подзадачите са малко или много независими при „[[разделяй и владей]]“, докато подзадачите при [[динамично програмиране|динамичното програмиране]] се припокриват.
-[[Линейно програмиране]]
-При този принцип, проблемът се свежда до откриването на специфични [[неравенства]], които са в сила по отношение на входните [[данни]], и след това се прави опит да се намери максимума (или минимума) на някоя [[[http://bg.wikipedia.org/wiki/Линейна_функция линейна функция]]] над тях.
-Вероятностни,генетични и [[евристика|евристични алгоритми]]
-При вероятностния алгоритъм се съдържа елемент на [[случайност]]та и за него може да се докаже, че в най-доброто решение се съдържа [[случайност]]та.
-При генетичните алгоритми се използват цикли на случайните мутации, които генерират успешни поколения от решения.
-[[евристика|Евристичните]] алгоритми се проявяват в това да се намери приблизително решение в условия на ограничени ресурси или време.                                                                        '''Според приложението'''
-Според областта, в която се прилагат алгоритмите могат да се разделят на много и различни видове: [[алгоритми за търсене]], [[алгоритми за сливане]], [[алгоритми за сортиране]], алгоритми за [[машинно обучение]], [[криптография|криптографски]] алгоритми и други.
-'''Според сложността'''
-Тук алгоритмите се разглеждат спрямо това колко време е нужно за да се стигне до решението на задачата. Някои алгоритми завършват за [[[http://bg.wikipedia.org/w/index.php?title=Линейно_време&action=edit&redlink=1 линейно време]]], други за [http://bg.wikipedia.org/w/index.php?title=Полиномиално_време&action=edit&redlink=1 полиномиално], трети за [[[http://bg.wikipedia.org/w/index.php?title=Експоненциално_време&action=edit&redlink=1 експоненциално време]]], а някои алгоритми никога не завършват работа.
-[[category:Алгоритми]]