Дәріс №5. Есептерді шешудің классикалық әдістері

Кез келген есепті шығарудың негізгі төрт тәсілі бар:

1. Ашық формуланы қолдану.

2. Рекурсивті анықтаманы пайдалану.

3. Алгоритмді пайдалану.

4. Сұрыптау әдісі, сын және қателер әдісі және т.б.

Әрине, бірінше тәсіл «ең жақсы» болып табылады: біз барлық жағдайда қойылған есептің шешімін беретін алдын ала табылған және дәлелденген формуланы пайдаланымыз.

Сондай «маңдайлық» тәсілге квадраттық теңдеудің нөлін анықтау, еркін мерзімге сәйкес күннің атын анықтау, электрлік жүйеде берілген ток күшін анықтау сияқты осындай есептердің шешімі келтіріледі. Математиканың міндеті мүмкін есептердің көп санын шешу үшін ашық формулаларды табудан тұрады.

 Егер мұндай формула болатын болса, есептің күрделілігі есептеу тиімділігімен байланысты болып шығады.

Анықтама бойынша формулаға символдардың және операциялардың тек соңғы саны кіреді, және бұл осы формулаға енгізілген кез келген параметрлер саны үшін дұрыс, яғни кез келген n өлшемді кіріс есебіне. Сондықтан осы жағдайда күрделілік тұрақты (n-ға тәуелді емес) және О(1)-ге тең.

Әрбір операцияның (яғни +,-,/,* т.б) күрделілігі олармен жүргізілетін санның разрядынан байланысты емес, яғни күрделілік операция санына пропорционалды.

Жақсы алгоритмдер мысалдары:

Мысал 1. Натуралды қатардағы n санның қосындысын есептеңіз.

Сіз тұрақты күрделілікке ие болатын, сәйкес ашық формуланы білесіз: онда бір қосу операциясы, бір көбейту операциясы және бір бөлу операциясы қолданылады:

Мысал 2. Натуралды қатардағы n санның квадрат қосындысын есептеңіз.

Мүмкін сіз мұны білесіз және дәлелдей аласыз.

Мысал 3. Натуралды қатардағы n санның кубтық қосындысын есептеңіз.

Осы мысалдарды жалғастыруға болатынын сіз сезесіз. Бірақ, бұл жерде математикадан эстафетаны информатика алады. Егер, шешімге келуге мүмкіндік беретін есептеудің соңғы процесін анықтай алсақ, онда тиімді формуланың жоқтығы қорқытпайды. Формуланы процеске ауыстырумен байланысты жаңа сұрақ туындайды: біз неше кезеңнен кейін шешім аламыз?

 Көбінесе есептің шартына сүйене отыра, шешімі рекурсивті, әлсін-әлсін анықталатын, жабық есептеу формуласы бар. Осылай, натуралды қатардағы n санның S(т) қосындысы мына формулалармен анықталады:

 және ,

яғни ол жақсы бағдарламалау тілінде оңай көрсетілетін процесс ретінде негізделеді:

 

S(n) ПРОЦЕДУРАСЫ: натурал қатардың n санының қосындысы

ЕГЕР n ¹ 1 ОНДА          S(n) S(n - 1) + n

 

ӘЙТПЕСЕ S(n) 1

СОҢЫ “ЕГЕР”

ПРОЦЕДУРА СОҢЫ

 

S(5)-ті санау үшін жүйе 5-ке тең n формальды қасиетімен S процедураны шақырады. Өйткені 5 саны 1-ге тең емес болғандықтан, жүйе нәтижені есептеу үшін оны қайтадан есептейтін S(4) мәніне 5-ті қосу керектігін біледі. Ол тағы S процедурасын шақырады. Сондай-ақ, жүйе стектік жадыға, S(4) мағынаны білген кезде одан басында қажетті болған жауапты алу үшін оған 5-ті қосу керек.

Тиімді ашық формулалар белгісіз есептерді шешу үшін жарасымды күрделілік алгоритмдерді құра білу керек. Классикалық және аса ыңғайлы тәсілдердің бірі басынан бастап оңай орындауға болатын рекурсивті жазбаларды пайдалану болып табылады. Егер де алгоритмнің күрделілігі аса үлкен болса, онда информатик рекурсивті формуладан шыға отыра, барлық ашық формулаларды тізбектей табу қажет.

Мысал 4. Бір нүктеден екінші нүктеге дейінгі қысқа жолды табу есебімен біз өмірде күнделікті кездесеміз: автокөлікпен саяхаттағанда, метрода, сондай-ақ кейбір математикалық басқатырғыштарды шешкен кезде.  Мысал ретінде 1-ші нүктеден 6-шы нүктеге әрбір қабырғасында көрсетілген арақашықтық қосындысы минималды болатын жолмен жету нүктесін табу керек. Әдетте төбелердің арақашықтығы туралы емес, ал қабырғалардың құны туралы айтады.

Жақсы шешілетін есептердің тізімі (полиномиалды алгоритмдер). Әрбір кезде, кейбір есептерді шешу үшін айқын математикалық формулалар бізге белгілі болған кезде, есептің қиындығы тұрақты болып шығады (есептің берілгеніне қатысты емес); әрине, бұл жағдай мінсіз.

Осы есептер класына, мысалы, сызықтық теңдеулердің туындалмаған жүйесінің шешу, жалақы есебін шешу және теңдеулер жүйесіне бірігетін мектеп физика курсының классикалық есептерінің үлкен бөлігі жатады.

Төменде біз осы тізімді басқа берілген типтерін өзіне тартуды қажет ететін есептер қатарымен толтырамыз.

§ N санынан тұратын жиынды сұрыптау (реттің күрделілігі  O (n logn).

§ m қабырғасынан тұратын Эйлер циклын табу (O (m) реттің күрделілігі).

Басқа есептер түрлері үшін нәтижелер алынған еді. Оларды дәлелсіз келтіреміз

§ Мәтінде n ұзындығы бар сөздерді табу (n*O(n) күрделілігі)

Минималды (m-қабырға саны) құны және O (m logm) күрделілігімен жобалайтын ағашты құру.

n төбелерден және m доғалардан тұратын графтағы қысқа жолын табу (0 (m*n) күрделілігі).

Процедура күрделілігі бар сызықтық бағдарламалау деп осы процедураны орындау үшін қажет кіріс мәліметтердің жоғарғы шегі операция санының өлшемділігінен функция түрінде өрнектелген. Есептің күрделілігі – оның шешімі үшін белгілі ең күшті алгоритм күрделілігі. Сондықтан, ол есепті шешу әдісінің даму денгейінен байланысты. Осыдан екі басты сұрақ туындайды:

1. Қандай жағдайға дейін берілген алгоритмді жақсартуға болады? Әрбір бөлек жағдайлар үшін тиімді күрделіліктер әдісі белгілі ме? Жақсы шешілетін есептер саны қандай (мысал, n немесе n², мұнда n кіріс мәліметтер өлшемі)?

2. Есептердің басқа топтастыруына күрделілік дәрежесі есепке алына ма және бір кластан басқа класқа, «қиын» есептен өте «қарапайым» есепке өту үшін қандай әдістер ұсынылады.

Төменде осы екі сұраққа жауаптар беріледі. Олар көптеген есептерді шешу үшін «классикалық» алгоритмдіқ әдістер жеткіліксіз және жасанда интелект саласындағы зеттеулер перспективалы болатынын көрсетеді.

Күрделілікке байланысты есептерді топтастыру:

Класс Р: полиноминалды алгоритмдер.

Біз Р класына қатысты немесе «жақсы» деп  күрделілігі n дәрежелі кіріс шаманың өлшемділігінен тәуелсіз, тұрақты полиномды құрайды.

Класс Е: табиғи экспоненциалды есептер.

Табиғи экспоненциалды деп, күрделілігі fⁿ қатарынан төмен емес есептерді айтады,  (мұнда f — тұрақты немесе  n нан полином) мысалы, күтетін жауабтар саны өз-өзімен экспоненциалды болған кезде.

Не Р класына, не Е класына кірмейтін есептер. Бұл класқа келесі есептер жатады:

· бүтін айнымалылары бар  теңдеулер жүйесін шешу

· кейбір графтың барлық төбелерінен өтетін циклды анықтау

· берілген j көптігін жабатын кейбір таңдалған тұқымдық берілген көбейтіндісінің ортасында болуы

· белгілі шарттары ескеретін күнтізбені құру

Логикалық айнымалылардың мәндер жиыны болуы еркін берілген логикалық өрнектін мәнін АҚИҚАТ етіп жасауға мүмкіндік береді. Қала желілері арқылы коммивояжер жолдарын оптимизациялау.

Төмен бағалы ақпаратты алу үшін берілген ақпаратттық банктен сұраныс кезінде  файлдарды таңдау.

Минималды орталық саны кезінде максималды клиенттер саны үшін қызмет көрсету орталығының орналасуы (телефон, теледидар, жедел қызмет көрсету).

Төмен баға кезінде көлемнің қолайлы жүктелуі (сөмке, поезд, кеме, ұшақ).

 Станоктық саябақ,  инвестициялар, әуе кеңістігіндегі бағыттарды оптимизациялау.

Диагностика  (ауыру, сыну, баспа сызбаларының дефекты). Бұл тізімді жалғастыруға болады.

Мәселе мынада: осы есептердің кейбірі Р класына кіретініне сене ала аламызба?

Өкінікшке орай, қазіргі уақытта осы есептердің бірінде де полиномалды алгоритм табылмаған. Сондай-ақ, барлық айтылған есептер үшін өзара эквивалеттілік дәлелденді, яғни егер де осы есептердің біріне жақсы (яғни полиномалды) алгоритмді ұсынсақ, онда олардың барлығы автоматты түрде шешіледі.

Ең ыңғайлы класс Р – көптеген полиномиальды есептер – осы есептер өте аз: адам жақсы шеше алатын формальды есептер (яғни алгоритмді және полиномиальді)  тұқымдасты құрайды. Қалған барлық есептер қиын және анықтама бойынша жасанды интеллект саласына жатады.

Атап кетейік, егер кәдімгі тілде тұжырымдалған есеп үшін полиномиалды алгоритм болса, мұны білу қажеттілігі есеп шартын жақсы алгоритммен өңдеуге болатындай етіп қайтадан полиномиальды емес күрделілікке келтіреді, тұжырымдап үлгілеу керек.