Алгоритмдер теориясының элементтері
Алгоритмдер теориясы алгоритмдердің жалпы қасиеттерін зерттейтін математиканың саласы.
Алгоритм ұғымы өзбек математигі және астрономы IX ғасырда өмір сүрген Мухаммед бен Муса аль – Хорезми есімімен тығыз байланысты, ол алғаш позициялық есептеулер жүйесінде арифметикалық амалдардың орындалу тәртібін ойлап шығарды.
Есептің қойылуынан бастап нәтижесіне дейінгі есептеу процесін алгоритм деп айтуға болады.
Кезкелген алгоритмнің ерекшелігі кейбір есептер класын шешу тәсілінде. Мысалы, сызықты теңдеулер жүйесін шешу алгоритмі, екінші ретті теңдеулер алгоритмін шешу және тағы басқалар.
Қандай
да бір
алгоритмі берілсін. Ол қолданылатын
объектілер жиыны
алгоритмінің қолданылу облысы деп
аталады.
алгоритмі
функциясын есептейді деп атайды, егер
оның қолданылу облысы
функциясының анықталу облысымен бірдей
болса және
алгоритмі өзінің қолданылу облысындағы
кез келген
элементін
- ке өңдесе.
функциясы есептелінеді деп аталады, егер оны есептейтін алгоритм табылса.
Американ математиктері Пост және Тьюринг математикалық машина ұғымын енгізді, оны кейін Пост машинасы немесе Тьюринг машинасы деп атап кетті.
Примитивті – рекурсивті функциялар
Қандай да бір меншікті түрде анықталған функция рекурсивті деп аталады. Олардың анықталу облысы – 0 және натурал сандар жиыны.
Қарапайым немесе элементар рекурсивті функциялар:
1. Салдар функциясы
2. Тұрақты функция (көбіне бұл 0 )
3. Мәндес функция
Бір рекурсивті функцияларды екінші рекурсивті функциялар аргументтерінің орнымен алмастыру суперпозиция операциясы деп аталады.
M
аргументті n функция
және n аргументті
функциясы берілсін. Онда суперпозиция
операциясының нәтижесінде m аргументті
функция аламыз:
функциялары берілсін. Онда примитивті
– рекурсивті операциясы келесі формула
бойынша анықталады:
Функция примитивті – рекурсивті деп аталады, егер оны элементар рекурсивті функциялардың, саны шектеулі суперпозиция және прмитивті – рекурсия операцияларының көмегімен өрнектеуге болса.
Функция дербес деп аталады, егер ол аргументтердің барлық мәндерінде анықталмаса.
Тьюринг машинасы
Екі
шеті шексіз ұяшықтарға бөлінген лента
Тьюринг машинасы болып табылады. Әрбір
ұяшықта М машинасының сыртқы алфавиті
деп аталатын
символдарының бірі орналасқан. Бір
символды бос деп белгілеп аламыз.
немесе
0
символдарымен белгілейді. Ол ұяшықтың
бос екенін көрсетеді.
Мысалы,
функциясын есептейтін Тьюринг машинасының
программасы:
аргументтің
бір бос емес ұяшығы өшірілді
аргументтің
бос емес ұяшықтары оқылады
бөлуші
бос ұяшық табылды
нәтиженің
бос емес ұяшықтары оқылады
нәтиженің
бір бос ұяшығы толтырылды
нәтиженің
екінші ұяшығы толтырылды
нәтиженің
бос емес ұяшықтары кері ретпен оқылады
бос
бөлінетін ұяшық табылды
екінші бос ұяшық табылды
тағы
да бос бөлінетін ұяшық оқылады
аргументтің
бос емес ұяшығы табылды
аргументтің
бос емес ұяшығы табылды
аргументтің
бос емес ұяшықтарының алдында бос ұяшық
табылды
аргументтердің
бос емес ұяшықтары кері ретпен оқылады
