Алгоритм шыгу тарихы. Алгоритм шығу тарихы. Алгоритмны шыу тарихы. Алгоритм
 Скачать 23.77 Kb.
|
|
Алгоритмның шығу тарихы. Алгоритм, алгорифм (ағылшынша: algorіthm, algorіsmus — Әл-Хорезмидіңатынан шыққан) — бастапқы берілген мәліметтермен бір мәнде анықталатын нәтиже алу үшін қай амалды (жұмысты) қандай ретпен орындау қажеттігін белгілейтін есептерді (мәселелерді) шешу (математикалық есеп-қисаптар орындау, техникалық объектілерді жобалау, ғылыми-зерттеу жұмысын жүргізу т.б.) тәсілдерінің дәл сипаттамасы. Алгоритм — математика мен кибернетиканың негізгі ұғымдарының бірі. Агоритмді орындау алгоритмдік процесс деп аталады. Жалпы Алгоритм деп алдын ала не істеу керек екені дәл көрсетілген есептеу процесін айтады. Есептеу процесі қандай болса да алғашқы мәндерден бастап, сол арқылы толық анықталған қорытынды шыққанша жүргізіледі. Алгоритм ұғымының алғышартына алгоритмдік процеспен қатар мүмкін болатын алғашқы деректер жиынтығының нұсқауы және қорытынды алуға байланысты жүргізілген процестің аяқталғандығын көрсететін ереже енеді. Белгілі бір бастапқы деректердің жиынына қолданылған Алгоритм тиянақты қорытындыға келмеуі немесе есептеу барысы аяқталмай тоқталуы мүмкін. Егер есептеу процесі белгілі бір қорытынды алумен аяқталса (не аяқталмай қалса), онда Алгоритм мүмкін болатын бастапқы деректерге қолданылады (не қолдануға болмайды) деп ұйғарылады. Алгоритм — қазіргі математикада, оның ішінде электронды есептеуіш машинадақолданылатын негізгі ұғымдардың бірі. Белгілі бір теңдеу түбірінің жуық мәнін кез келген дәлдікпен табу оған арналған Алгоритммен есептеледі. Компьютердіңкең қолданылуына байланысты Алгоритм жаңа мағынаға ие болды. Берілген есепті шешу барысында орындаушыға біртіндеп қандай әрекеттер жасау керектігін түсінікті әрі дәл көрсететін нұсқау да Алгоритм деп аталады. Алогритмді орындаушы — адам, ЭЕМ немесе робот. Әрбір нұсқау — бұйрық. Ал орындаушының жүзеге асыра алатын бұйрықтар жиыны бұйрықтар жүйесі деп аталады. Мысалы, у = (ax + b) (cx - d) функциясын есептеу ЭЕМ-да мынадай әрекеттерден құралады: а-ны x-ке көбейту R1 деп, оған b-ны қосу нәтижесі R2 деп, с-ны х-ке көбейту R3 деп, сх-тан d-ны алу R4 деп, R2-ні R4-ке көбейту у деп белгіленеді. Алгоритмнің бұйрықтары бірінен кейін бірі кезекпен орындалады. Бағдарлама Алгоритм тілінде жазу, бейнелеу мағынасын береді. Компьютерде Алгоритмнің сызықты, тармақты, циклді, логикалық, модельдік, параллельдік, тізбекті т.б. түрлері қолданылады. Қазіргі кезде алгоритмдер теориясы негізі 3 бағытта дамып келеді: *Алгоритмнің классикалық теориясы – есептерді формальды тілдер терминдерімен беру (формулировка задач) проблемасын зерттеді. Есептерді күрделілік кластары бойынша (P,NP, т.б) классификациясын жасайды, есептердің шешімін табу ұғымын енгізді. *Алгоритмдерді асимтотикалық талдау теориясы. Алгоритмнің , соның ішінде рекурсивті алгоритмдердің, орындалуының уақытының немесе ресурстарының асимтотикалық бағасын алудың тәсілін қарастырады. Асимтотикалық талдау енгізілетін деректер к өлеміні ң өсуіне байланысты алгоритмдердің ресурстарға (мыс: орындалу уақыты) қажеттілігін бағалау ға мүмкіндік береді. *Есептеу алгоритмдерін практикалық талдау теориясы. Тиімді алгоритмдерді таңдау әдістемесін жасау, алгоритмдердің сапасын тексеруді ң практикалы қ өлшемдерін іздеу, функцияларды интервалдық талдау, к үрделілікті ң на қты функцияларын алу және т.б. сияқтарды есептерді шешумен шұғылданады. * Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және практикалық аспектілерде қолданылады. Теориялық аспект: Есептің алгоритмдік шешімі болатындығын немесе оны шешудің нақты алгоритмі болмайтындығына есепті зерттеу нәтижесінде алгоритмдер теориясының жауап беру мүмкіндігі теориялық аспектіге жатады. Алгоритмдік шешімі болмайтын есептер Тьюринг машинасын тоқтату есебіне келтіріледі. Ал алгоритмдік шешімі болатын есептер үшін олардың NP-толық есептер класына тиесілі ме екендігі анықталады. Егер тиесілі болса, онда бастапқы деректері үлкен болатын есептердің нақты шешімін алу үшін қанша уақыт кететінін анықтауға немесе оны шешудің жылдам нақты алгоритмі болмайтындығын айтуға мүмкіндік береді. Практикалық аспект: алгоритмдер теориясының, әсіресе асимптотикалық және практикалық талдаудың әдістері мен әдістемелері келесі мүмкіндіктерді береді: Берілген есепті шешуге арналған алгоритмдер жиынынан жасалатын программалық ж үйедегі олардың ерекшелігін ескеретін тиімді алгоритмді таңдауға мүмкіндік береді. Күрделілік функциясы арқылы күрделі есептерді шешудің уақыттық бағалауларын алады. Белгілі уақыт ішінде қандай да бір есептің шешуі болмайтындығына шынайы баға беріледі. Ақпаратты өңдеу саласындаың маңызды деген есептерін шешудің тиімді алгоримтмдерін құру мен жетілдіру. Мысалы: алгоритмді жүзеге асыратын программаның орындалу уақытына немесе пайдаланатын минималды жад көлеміне шектеулер қойылғанда түрлі алгоритмдерден таңдау жасалынады; қиындық функциясы арқылы күрделі есептерді шешу уақыты анықталады; берілген уақыт ішінде есепті шешу мүмкін болмайтындығы шынайы бағаланады. Бұл қазіргі кезде криптографиялық әдістер үшін, ақпаратты өңдеу саласында практикалық жағынан маңызды есептерді шешудің тиімді алгоритмдерін жасау мен жетілдіру үшін аса сұранысқа ие болып отыр. Алгоритмдер классификациясы. Күрделілілік тұрғысынан алгоритмдердің екі үлкен класы бар.Олар: қайталауы бар алгоритмдер және рекурсивті алгоритмдер. Бір есепті көптеген алгоритммен шешуге болады. Олардың әрқайсысының жұмысының тиімділігі әртүрлі сипаттаулармен сипатталады. Алгоритмді талдамас бұрын ең алдымен берілген алгоритм есепті дұрыс шешетінін дәлелдеуіміз керек. Егер есепті дұрыс шешпесе тиімділік мәселесінің мәні жоқ. Егер алгоритм қойылған есепті шешсе, оның қаншалықты тиімді екенін қарастыруымыз керек. Сондықтан оның тиімділігінін анықтау үшін алгоритмдерді талдауымыз қажет. Қайталау алгоритмінің негізінде шартты өрнектер мен цикл жатыр; мұндай алгоритмдерді талдауда циклдын ішінде қолданылатын операция саны мен цикл итерациясының санын бағалау керек. Рекурсивтік алгоритмдер үлкен есепті фрагменттерге б өледі және әрбір фрагменттерді жеке қолдануға мүмкінлік береді. Осындай алгоритмдерді кейде «бөліп алда біле» алгоритмі деп айтайды және оларды қолдану өте тиімді болуы мүмкін. Үлкен есептердікішіге бөлу жолымен шешу үрдісінде үлкен емес, қарапайым және түсінікті алгоритм құрылады. Рекурсивті алгоритмді талдауда есепті бөлімге бөлуге қажетті операцияның санын санау, ірбңр бөлімдегі алгоритмнің орындалуы және есепті толық шешудегі әрбір бөлімнің нәтижесін біріктіру керек. Осы ақпараттарды және неше бөлік екенінің саны, олардың өлшемінен алгоритмнің күрделілігінің рекуррентік қатынасын шығарамыз. Алгоритмдерді әртүрлі белгілер бойынша жіктеуге болады. Мысалы, жалпы комбинаторлық алгоритмдер, тағы алгоритмдер, максимальды ағынды іздеу алгоритмдері, максимальды жұп сәйкестігін іздеу алгоритмдері, іздеу алгоритмдері, Алгоритмы на строках, жолды іздеу алгоритмдері, Бұтақтармен жұмыс алгоритмдері, сұрыптау алгоритмдері, сығу алгоритмдері, үлестірілген жүйелер алгоритмдері, операциялық жүйелердегі алгоритмдер, тиімділеу алгоритмдері және т.б. Алгоритмнің күрделілігін анықтау Математикада алгоритмнің күрделілігі ұғымын білудің мәні зор. Егер алгоритмде есптеу сериялары кездессе , онда алгоримнің күрделілігі ретінде орындалатын амалдар алуға болады.Егер алгоритмде "*" мен "+" амалдары қатар кездессе , онда алгоритм күрделілігі ретінде "*« амалының саны орындалады.Себебі, бұл амал "+" амалына қарағанда анағұрлым көп уақытты талап етеді. Big-O-бағалау алгоритмнің орындалу уақытының өлшемін (runtime) береді. Әдетте алгоритмнің жақсы және нашар жағдайлар үшін есептеу тиімділіктері әртүрлі , сондықтан әр нақты жағдай үшін Big-О мәні есептеледі. Егер алгоритм реті —0(1) болса, оның реті коллекциядағы элементтер санына тәуелсіз болады. Бұл алгоритм тұрақты уақыт бірлігі ішінде орындалады, мысалы егер массив соңын көрсететін индекс сақталса, массив элементіне мән меншіктеу реті 0(1) болады. Алгоритм О(п) сызықты (linear). Оның күрделілігі тізім размеріне пропорционал. Реті log2n болатын алгоритмдер логарифмдік (logarithmic) деп аталады. Мұндай күрделілік тізімдерді бірнеше рет ішкі тізімдерге 1/2, 1/4, 1/8 етіп бөлгенде туындайды. Мысалы бинарлық бұтақтарда іздеу алгоритмдерінің күрделілігі орташа және нашар жағдайлар үшін O(log2n) болады. Реті О(п2) болатын алгоритмдер квадраттық (quadratic) деп аталады. Шағын n үшін ғана практикада қолданылады. п екіге артқан сайын алгоритмнің орындалу уақыты 4-ке артады. Реті О(n3) болатын алгоритмдер өте баяу орындалады, кубтық (cubic) уақытты қажет етеді. п екіге артқан сайын алгоритмнің орындалу уақыты 8 есе артады. Оның мысалына графтарға қолданылатын реті О(п3) болатын Уоршел алгоритмі жатады. Күрделілігі О(2п) тең алгоритмде экспоненциальды күрделілік (exponential complexity) болады. Өте баяу орындалатындықтан өте аз п үшін қолданылады. Іс жүзінде алгоритм – функцияны беру әдісі. Ал функция таблица, схема, формула түрінде берілуі мүмкін. Бірақ кейбір процестерде бастапқы енгізілген немесе берілген деректер мен алынған нәтижедегі деректер арасындағы байланысты ұйымдастыратын функцияны құру қиын, күрделі. 1 – бағыт Рекурсивті функциялар – есептелетін функциялар ұғымымен байланысты. X және Y жиындары бар болсын. X жиынының кейбір элементтеріне Y жиынының элементтері сәйкес келсе, онда Y – те X – тен бөлшекті функция берілген дейді. Y жиынында сәйкес элементтері бар және X элементтерден құралған жиынның элементтер жиыны функцияның анықталу облысы деп аталады. X жиынында сәйкес элеметтері бар Y жиынының элементтер жиыны функцияның мәндер облысы деп аталады. Егер X –тен Y-тегі функцияның анықталу облысы X жиынымен беттессе, онда ол функцияны барынша анықталған деп атайды. Осы ұғымға және рекурсивті функцияға негізделіп алгоритмнің дәл анықтамасын құруға болады. Іс жүзінде алгоритм – функцияны беру әдісі. Ал функция таблица, схема, формула түрінде берілуі мүмкін. Бірақ кейбір процестерде бастапқы енгізілген немесе берілген деректер мен алынған нәтижедегі деректер арасындағы байланысты ұйымдастыратын функцияны құру қиын, күрделі. 1 – бағыт Рекурсивті функциялар – есептелетін функциялар ұғымымен байланысты. X және Y жиындары бар болсын. X жиынының кейбір элементтеріне Y жиынының элементтері сәйкес келсе, онда Y – те X – тен бөлшекті функция берілген дейді. Y жиынында сәйкес элементтері бар және X элементтерден құралған жиынның элементтер жиыны функцияның анықталу облысы деп аталады. X жиынында сәйкес элеметтері бар Y жиынының элементтер жиыны функцияның мәндер облысы деп аталады. Егер X –тен Y-тегі функцияның анықталу облысы X жиынымен беттессе, онда ол функцияны барынша анықталған деп атайды. Осы ұғымға және рекурсивті функцияға негізделіп алгоритмнің дәл анықтамасын құруға болады. Анықтама. Әлдебір алгоритм көмегімен есептелетін функцияны есептелетін функция дейді. Кез – келген берілген деректерді (үзілісті, дискретті) әлдебір санау жүйесінде натурал сандармен кодтауға болады, онда Олардың барлық алмастыруы есептеу операцияларының тізбегіне келтіріледі, ал өңдеу нәтижесі солайынша бүтін сан болып қалады. Кез келген алгоритм берілген сандық функция үшін бірдей, оның мәнін есептейді, ал оның элементарлы қадамдары қарапайым арифметикалық және логикалық операциялар болады. Мұндай функциялар есептелетін функциялар деп аталады. Алгоритмдік тіл – алгоритмдерді жазуға арналған символдар мен сол символдардан тұратын конструкцияларды құрастыру жəне түсіндіру ережелерінің жиыны. Алгоритмдерді бейнелеу тəсілдері. Алгоритмдерді бейнелеудің негізгі тəсілдеріне оларды жазудың келесідей түрлері жатады: • табиғи тіл сөздері арқылы; • формулалық-сөздік тəсіл арқылы; • графикалық түрде бейнелейтін блок-схемалар арқылы; • псевдокодтар арқылы; • программалау тілі арқылы. Алгоритмдерді табиғи тіл сөздері арқылы бейнелеуде – есептеу кезеңдері мазмұны кез келген түрде табиғи тілде жазылады. Бірақ бұл тəсілде алгоритм көрнекілігі жоқ жəнедəлдік, яғни детерминділік қасиет, толық формальдау мүмкіндігі сақталмайды, сол себепті ол сирек қолданылады. Алгоритмдерді формулалық-сөздік тəсіл арқылы бейнеленуі– тапсырманың математикалық символдар мен өрнектердің жəне сөздердің араласуымен берілуі болып табылады.Мысалы, үшбұрыш ауданын оның үш қабырғасының ұзындығы арқылы есептеу алгоритмін құру керек болсын делік. 1. үшбұрыштың жарты периметрін есептеу p=(a+b+c)/2 2. үшбұрыштың ауданын есептеу 3. нəтиже ретінде S мəнін шығарып, алгоритм жұмысын аяқтау. 4. Бұл тəсілді пайдаланғанда, алгоритмді кез келген деңгейде айқындап көрсетуге болады, бірақ формальды түрде анық бейнелеу қиын. Алгоритмді графикалық түрде блок-схемалар арқылы көрсету – оның логикалық құрылымын графикалық түрде бейнелеу болып саналады. Мұнда мəліметтерді өңдеудің əрбір кезеңі атқарылатын операцияға сəйкес əр түрлі геометриялық фигуралар (блоктар) түрінде көрсетіледі |