Информатиканың іргелі негіздері
Алгоритмдік шешілмейтін есептер
жүктеу/скачать 1,13 Mb.
|
лекция ИТН
| Алгоритмдік шешілмейтін есептер.
«Алгоритм – нақты ережелермен қатаң түрде орындалатын, қандай да бір қадамдардан соң қойылған есептің шешіміне әкелетін есептеулердің кез келген жүйесі» Анықтама:(Марков): Алгоритм – өзгертілетін бастапқы деректерден ізделінді нәтижеге әкелетін есептеу процесін анықтайтын нақты ереже. Б ұл анықтамалардан алгоритмге қойылатын келесі ортақ талаптарды атап өтейік: алгоритм қарапайым орындалатын саны шектеулі ережелерден тұруы тиіс, яғни жазбалардың шектеулі болуы талабын қанағаттандыруы тиіс; алгоритм шектеулі қадамнан соң есепті шешуі тиіс, яғни әрекеттердің шектеулі болу талабын қанағаттандыруы тиіс; алгоритм барлық мүмкін болатын бастапқы деректер үшін біреу ғана болуы керек, яғни әмбебаптық талабын қанағаттандыруы тиіс; алгоритм қойылған есептің дұрыс шешімін табуы керек, яғни дұрыс болу талабын қанағаттандыруы тиіс. Алгоритм атауы атақты араб математигі Әбу Жафар Мұхаммед ибн Мұса әл - Хорезми ( 763 - 850 ж. ж) есімінің латынша Algorithmi (Алгоритми) болып жазылуынан шыққан. Ол санаудың ондық жүйесінде көп орынды сандар мен арифметикалық амалдардың орындалу ережесін ұсынған. Бұл ережелер қосынды мен көбейтіндіні табуға арналған амалдарды орындауға қажетті тізбектен құрылған. Сол ереже осы күнге дейін қолданылып келеді.Алгоритм - орындаушының белгілі бір мақсатқа жетуі үшін орындалатын әрекеттер тізбегін айтады. Кез - келген есепті қарапайым амалдарды тізбектей орындау арқылы шығаруға болады. Алгоритімді компьютерде орындау үшін оны программа түрінде жазып шығу керек. Алгоритм кестесі * Алгоритмдер арқылы шешілмейтін есептер Алгоритм ұғымын формальдандыру – шешу алгоритмдері табылмайтын есептердің болатындығын зерттеуге мүмкіндік береді.Бірқатар есептердің кез келген есептеу құрылғыларында алгоритмдік тұрғыдан шешілмейтіндігі дәлелденген. ʄ функциясы есептелетін функция делінеді, егер де осы функцияның анықталу облысындағы кез келген аргумент үшін функция мәнін есептейтін Тьюринг машинасы табылса.Егер де мұндай машина табылмайтын болса,онда ʄ функциясы есептелінбейтін функция делінеді * Егер ʄ функциясының есептеу нәтижесі «ақиқат« не «жалған« түріндегі логикалық өрнек болса,онда есеп берілген есептелетін функцияға қатысты шешілетін не шешілмейтін есеп деп аталады.Есеп бастапқы берілгендердің кейбірі үшін шешілетін , ал келесі біреулері үшін шешілмейтін болғандықтан, бастапты берілгендердің мүмкін мәндерін нақтылап көрсету керек. Машина жұмысын тоқтату проблемасының шешілмейтіндігі дәлелденген есепке жатады.Ол келесі түрде болады: Тьюринг машинасына арналған программа сипаттамамсына қарап, уақыт өтуіне қарай программа жұмысының аяқталатындығын не шексіз жұмыс істейтіндігін анықтау ға болады. Тоқтату проблемасының шешілмейтіндігін дәлелдеу өзге есептердің де оған келтірілетіндігімен мағызды. Мысылы:Тьюринг машинасының бос жолда тоқтау проблемасының машина жұмысын тоқтатудың қарапайым есебіне келтіруге болады. Қазіргі кезде алгоритмдер теориясы негізі 3 бағытта дамып келеді: *Алгоритмнің классикалық теориясы – есептерді формальды тілдер терминдерімен беру (формулировка задач) проблемасын зерттеді. Есептерді күрделілік кластары бойынша (P,NP, т.б) классификациясын жасайды, есептердің шешімін табу ұғымын енгізді. *Алгоритмдерді асимтотикалық талдау теориясы. Алгоритмнің , соның ішінде рекурсивті алгоритмдердің, орындалуының уақытының немесе ресурстарының асимтотикалық бағасын алудың тәсілін қарастырады. Асимтотикалық талдау енгізілетін деректер к өлеміні ң өсуіне байланысты алгоритмдердің ресурстарға (мыс: орындалу уақыты) қажеттілігін бағалау ға мүмкіндік береді. *Есептеу алгоритмдерін практикалық талдау теориясы. Тиімді алгоритмдерді таңдау әдістемесін жасау, алгоритмдердің сапасын тексеруді ң практикалы қ өлшемдерін іздеу, функцияларды интервалдық талдау, к үрделілікті ң на қты функцияларын алу және т.б. сияқтарды есептерді шешумен шұғылданады. * Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және практикалық аспектілерде қолданылады. Теориялық аспект: Есептің алгоритмдік шешімі болатындығын немесе оны шешудің нақты алгоритмі болмайтындығына есепті зерттеу нәтижесінде алгоритмдер теориясының жауап беру мүмкіндігі теориялық аспектіге жатады. Алгоритмдік шешімі болмайтын есептер Тьюринг машинасын тоқтату есебіне келтіріледі. Ал алгоритмдік шешімі болатын есептер үшін олардың NP-толық есептер класына тиесілі ме екендігі анықталады. Егер тиесілі болса, онда бастапқы деректері үлкен болатын есептердің нақты шешімін алу үшін қанша уақыт кететінін анықтауға немесе оны шешудің жылдам нақты алгоритмі болмайтындығын айтуға мүмкіндік береді. Практикалық аспект: алгоритмдер теориясының, әсіресе асимптотикалық және практикалық талдаудың әдістері мен әдістемелері келесі мүмкіндіктерді береді: Берілген есепті шешуге арналған алгоритмдер жиынынан жасалатын программалық ж үйедегі олардың ерекшелігін ескеретін тиімді алгоритмді таңдауға мүмкіндік береді. Күрделілік функциясы арқылы күрделі есептерді шешудің уақыттық бағалауларын алады. Белгілі уақыт ішінде қандай да бір есептің шешуі болмайтындығына шынайы баға беріледі. Ақпаратты өңдеу саласындаың маңызды деген есептерін шешудің тиімді алгоримтмдерін құру мен жетілдіру. Мысалы: алгоритмді жүзеге асыратын программаның орындалу уақытына немесе пайдаланатын минималды жад көлеміне шектеулер қойылғанда түрлі алгоритмдерден таңдау жасалынады; қиындық функциясы арқылы күрделі есептерді шешу уақыты анықталады; берілген уақыт ішінде есепті шешу мүмкін болмайтындығы шынайы бағаланады. Бұл қазіргі кезде криптографиялық әдістер үшін, ақпаратты өңдеу саласында практикалық жағынан маңызды есептерді шешудің тиімді алгоритмдерін жасау мен жетілдіру үшін аса сұранысқа ие болып отыр. жүктеу/скачать 1,13 Mb. Достарыңызбен бөлісу:
|