Есептердің алгоритмдік шешімдері

Есептердің алгоритмдік шешімдері

Алгоритм дегеніміз берілген есепті шешуге арналған қатаң анықталған әрекеттер тізбегі немесе, қысқаша айтқанда, есепті шешу әдісі. Алгоритмнің негізгі қасиеттеріне тоқталайық:

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

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

3. Алгоритмнің нәтижелігі. Бұл қасиет алгоритмнің ақырлы қадам санынан кейін нәтиже алатынын көрсетеді.

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

Алгоритмді сипаттаудың бірнеше түрлері бар.

1. Алгоритмді сөз – формула арқылы сипаттау, яғни алгоритмді сөз және формулалар көмегімен сипаттау.

2. Алгоритмнің графикалық сипатталуы, яғни алгоритмді арнайы графикалық схемалар – блок-схемалар көмегімен сипаттау.

3. Алгоритмді псевдокод арқылы сипаттау. Псевдокод дегеніміз – команда әрекетінің, яғни алгоритм қадамының нақты программалау тілі операторларын қолданбай жәй тілмен сипатталуы.

4. Алгоритмді бағдарламалау тілдерінің бірі арқылы жазу (Pascal, Basic).

Алгоритмнің негізгі құрылымдары. Алгоритм негізгі 3 базалық құрылымға бөлінеді:

• сызықтық;

• тармақталушы;

• циклдік.

Сызықтық алгоритмдерде есеп шешімінің қадамдары бірінен кейін бірі тізбектей орындалады.

Тармақталушы алгоритмдерде алдымен қандайда бір шарт тексеріледі және шарттың орындалуына немесе орындалмауына сәйкес есептеу процесінің бірі орындалады.

Бағдарламалау тілдері және негізгі классификациясы.

Қазіргі кезде 3500-ден жоғары әр түрлі бағдарламалау тілдері бар және осылардың ішінен шектелген саны ғана программалық бөлімді құруға жаппай қолданылады. Бағдарламалау тілдерінің саны көп болуына байланысты олардың бірнеше классификациясы бар. Оның ішінде негізгі 2 түрге: фукционалдық мәніне (қызметі) және қолданылатын бағдарламалау технологиясына байланысты бөлінеді. Бағдарламалау тілдері фукнционалдық мәніне байланысты 4 үлкен классқа бөлінеді:

• бағдарламалауға үйретуші;

• жалпы мәнді;

• проблемалық-бағытталған;

• параллель бағдарламалаушы.

Қазіргі жоғары деңгейлі тілдерді осы классикацияға сәйкес қарастырамыз.

Бағдарламалауға үйретуші тілдер қатарына жататын жоғарғы деңгейлі тілдердің негізгілері Logo, Basic және Pascal. Logo тілі 60-шы жылдардың аяғында С.Пейперттің басшылығымен құрылды және ЭЕМ жаңа қолданушыларға, балаларға бағдарламалаудың негізін үйретуге бағытталған. Үйретуге арналған жоғары деңгейлі тілдердің ішіндегі кең тарағаны 1965 жылы Д.Кемени мен Т.Курц құрған Basic тілі. Дербес компьютерлерге бірінші қолданылған жоғарғы деңгейлі тіл және операциялық ортасы – Basic тілі. 60-жылдардың ортасынан бастап мамандар арасында құрылымдық бағдарламалау мәселесі көтеріле бастады. 1971 жылы Н.Вирт құрылымдық технологияға үйретуші Pascal тілін құрды.

Жалпы мәнді жоғары деңгейлі тілдер қатарына әр түрлі класс есептерін тиімді бағдарламалауға бағытталған тілдер жатады. Бұл классқа жататын тілдердің негізгілері C, Modula, Ada тілдері. Бұл тілдердің негізі 1966 жылы құрылған, ғылыми, пәндік облыстағы есептерді бағдарламалауға мүмкіндік беретін PL/1 тілі. PL/1 тілі ЖС ЭЕМ сериялы модельдерде кеңінен қолданылды. Си тілін 1972 жылы Д.Ритчи құрды және Unix операциялық жүйесі осы тілде жазылды. Си тілі ассемблер тілінің де және жоғары деңгейлі тілдің де мүмкіндіктерін қамтамасыз ететін болғандықтан орта деңгейлі тіл деп атайды. Pascal тілінің идеологиясын тарату мақсатымен Н.Вирт 1980 жылы Modula–2 тілін құрды. Бұл бағдарламалау тілінің негізі – бағдарлама бір-біріне тәуелсіз модульдерден тұрады.

1978 жылы қазіргі АҚШ-та әскери қаруды басқаруға қолданылатын қосымшаларды бағдарламалауға арналған Ada тілі құрылды. Ada тілі құрылымды бағдарламалау тілі болып табылады және параллель бағдарламалау мүмкіндіктерін қамтамасыз етеді.

Проблемалық–бағытталған жоғары деңгейлі тілдер деп нақты пәндік облыс есептерінің мәселесін түгел қамтитын тілдерді атаймыз. Бұл классқа жататын бірінші жоғары деңгейлі тіл – Fortran тілі. Fortran-I тілін 1956 жылы IBM фирмасы құрды және ғылыми-техникалық есептерді шешуге арналған.

Жасанды интеллект символдық ақпараттарын және тізімдерін өңдеуге арналған есептерді бағдарламалауға Lisp, Prolog тілдері қолданылады. Lisp тілін 50-жылдары Д.Макартни құрды. 70-жылдары Lisp тілінің негізінде құрылған Prolog тілі логикалық бағдарламалау тілі болып табылады және 5 буынның ЭЕМ жапон проектісінде негізгі тіл болып таңдалған. Әр Prolog бағдарлама, жәй тұжырымдар немесе импликациялардан тұратын сөйлемдерден тұрады, инструкция қолданылмайды.

Дәстүрлі неймандық архитектурадан ЭЕМ дәстүрлі емес параллель архитектуралы есептеу машиналарына көшуіне байланысты параллель алгоритмдерді сипаттаушы инструментальды құрылғылар пайда бола бастады. Параллель бағдарламалау тілдерінің негізі – параллель есептеулерді бағдарламалау процесін ықшамдау, параллель архитектуралық есептеу машиналарына арналған параллель программалық жүйелердің тиімдісін алу. Параллель бағдарламалауды жабдықтаудың қиындығы тиімді параллель жөндеушілерді құру. Қазіргі кезде қолданылып жүрген интерактивті параллель жөндеушілер IPSC (Intel фирмасының дербес компьютерлеріне арналған) және PDBX (мультипроцессорлы ЭЕМ арналған). Жиі қолданылатын векторлы матрицалық есептерге параллель бағдарламалар кітапханасы құрылған, BLAS - сызықтық алгебра бағдарламаларының кітапханасы, NAG – сандық алгоритмдер кітапханасы. Бұл есептерге белгілі матрицалы параллельдеушілер ProSolvar (Intel фирмасы) және жалпы мәнді параллельдеуші Parafrace (Д.Кук құрған) қолданылады.

Бағдарламалау технологиялары

Бағдарламалау процесін жақсартатын және кең қолданылатын әдістердің бірі – құрылымдық бағдарламалау. Құрылымдық бағдарламалаудың 3 бөлігі (құраушысы) бар:

1. Модульдік бағдарламалау

• Құрылымдық кодтау

• Жоғарыдан төменге қарай жобалау

Модульдік бағдарламалау дегеніміз – бағдарламаны логикалық бөліктерге бөлу процесі. Бағдарлама бірнеше модульдерге бөлінеді және мына 2 мақсат орындалуы тиіс:

1. Модульдің дұрыс болуы және оның контекстерден тәуелсіз болуы қажет;

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

Мысал ретінде стандарт математикалық функциялардың есептелу бағдарламасын қарастыруға болады. Бағдарламашы sin(x) функциясын бағдарламаның кез-келген жерінде қолдана алады және оған функцияның есептелуіне қай әдістің қолданып тұрғанын білудің қажеттілігі жоқ. Модуль өлшемі 60 жолдан аспауы керек және модульдер өзара тәуелсіз болуы керек. Байланысқан элементтерді бір модульге, байланыспаған элементтерді әр түрлі модульге жинау керек. Модульдерді қолдана отырып бағдарлама күрделілігін төмендетуге болады.

Pascal тілінде модуль процедуралар мен функциялардың көмегімен құрылады, Cи тілінде функциялардың көмегімен құрылады.

Құрылымдық кодтау деп бағдарламада басқарушы конструкциялардың шартты операторлардың, циклдің (параметрлі, цикл-әзір, цикл-дейін) қолданылуын айтады. Шартсыз көшу операторы бағдарламада сирек қолданылуы керек немесе шартты оператордың, циклдің көмегімен өзгертілуі керек.

Бағдарламаны жоғарыдан төмен қарай жобалаудың өз иерархиялық құрылымы бар және қысқа есеп қойылымынан басталады. Одан кейін есеп бірнеше ұсақ ішкі есептерге бөлінеді. Ішкі есептердің өзі де ішкі есептерге бөлінуі мүмкін. Әр қадамда ішкі есептің орындайтын негізгі функциялары анықталуы керек. Бөлу процесі әр ішкі есеп қарапайым болғанға дейін, яғни әр ішкі есепке бір модуль сәйкес келгенше созылады.

Объекті-бағытталған бағдарламалау

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

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

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

Объекті-бағытталған технологияға негізделген бағдарламалау тілдері: SmallTalk/v, Object Pascal, ACT++, C++, Simula, Actor, Classic–Aga және т.б.

Объекті-бағытталған бағдарламалаудың негізгі үш принципі бар: инкапсуляция, тұқымқуалау, полиморфизм.

Логикалық бағдарламалау

Логикалық бағдарламалау тілдері PROLOG және LISP жасанды интеллект проблемаларының есептерін шешуге арналған. LISP тілін 50-інші жылы Д.Макартни символдық ақпараттарды өңдеуге арнап құрды. LISP тілінің мәліметтерінің негізгі құрылымы тізімдер, тізімнің элементтері атомдар. Lisp тілінің бір ерекшелігі динамикалық жаңа объектілерді құру мүмкіндігі, объект есебінде бағдарламаның өзі де қатыса алады..

LISP тілі және оның модификациялары символды өңдеуге арналған бағытталған программалық бөлімді құруға кең қолданады және қазіргі кезде көптеген тиімді компиляторлары бар.

70-жылдары Lisp тілінің негізінде құрылған Prolog тілі логикалық бағдарламалау тілі болып табылады. Prolog бағдарламасының негізгі элементі атом болып табылады және жеке объектілер арасындағы қарапайым қатынастарды көрсетеді, басқа бағдарламалау тілдеріне қарағанда атом түсінігінің мағыналық мәні басқа. Тіл тек сипаттамадан тұрады және инструкциялары жоқ, яғни процедуралы емес. Әр Prolog бағдарламасы сөйлемдер жиынынан тұрады, яғни жәй тұжырымдар немесе импликациялар. Prolog тілінің базасында эксперттік жүйелер, білімді көрсететін жүйелер, білім базасы және жаратылыс тілдерін өңдейтін жүйелер құрылады. Prolog тілінің негізіне математикалық логика элементтері қолданылады. Бағдарлама объектілер арасындағы қатынас терминдері арқылы сипатталады. Логикалық бағдарламалау тілдерінің жетістігі параллель бағдарламалау принципі қолданылады. Prolog тілінің көптеген танымал модификациялары бар, оның ішінде ең көп тарағаны – Borland фирмасының Turbo Prolog бағдарламалау жүйесі. Жасанды интеллект проблемасына арналған жаңа логикалық және функционалды бағдарламалау тілдері құрылуда, мысалы, DURAL, VALID тілдері.

Сұрыптау дегеніміз берілген көптеген объектілерді белгілі бір қасиеттеріне байланысты реттеу процесі. Сұрыптау екіге бөлінеді: ішкі және сыртқы. Ішкі сұрыптауда барлық реттелетін мәліметтер компьютердің оперативті жадында орналасады, мұнда мәліметтерді кез келген ретпен қарастыруға болады. Сыртқы сұрыптау реттелетін мәліметтердін саны көп және оларды оперативті жадыға орналастыру қыин болғанда қолданылады. Бұл жағдайда мәліметтер сыртқы құрылымда сақталады. Осы кезде сыртқы құрылымнан компьютердін оперативті жадысына көп мәліметтерді көшіруі қыйншылық тудырады. Сол үшін мәліметтерді көшірер алдында топтарға жинақтаймыз.