Теория Алгоритмов

 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

филиал федерального государственного бюджетного образовательного учреждения

высшего образования

«Алтайский государственный университет»

в г. Барнауле

РЕФЕРАТ

НА ТЕМУ: ТЕОРИЯ АЛГОРИТМОВ

_______________________
(подпись)

Проверил:
_______________________
(уч. степень, звание, категория)
_______________________
(Ф.И.О.)
_______________________
(подпись)

                                            Бийск 2018

Содержание

Интуитивное определение алгоритма        3

Рекурсивные функции и алгоритмы        5

Маши́на Тью́ринга        9

Норма́льный алгори́тм        11

Интуитивное определение алгоритма

Одно из важнейших понятий математики – понятие функции. На содержательном уровне функция представляет «закон соответствия», по которому каждому элементу области определения сопоставляется какой-либо элемент: значение функции. Вообще говоря, не требуется чтобы значение функции можно было каким- либо способом «вычислить», «найти» по соответствующему значению аргумента. Для математики, и в особенности для ее приложений, интересны те функции, для которых способы нахождения значений функции существуют.

В трудах Ньютона и Лейбница, где впервые появилось понятие функции, как и в трудах математиков многих следующих поколений, неявно предполагалось, что значение функции можно так или иначе найти. Осознание того факта, что не для всех функций можно вычислить их значение, не уменьшило интереса к, так называемым, «вычислимым» функциям.

Интуитивное понятие о «вычислительной процедуре» существовало у математиков уже давно. За этими процедурами был закреплен особый термин: алгоритм.

Примерами алгоритмов являются:

1. Правила выполнения арифметических действий над числами

2. Правило отыскания наибольшего общего делителя (алгоритм Евклида). Найдите НОД(3770;6699) и его линейное представление.

3. Правило вычисления квадратного корня. Найдите [pic 1], опишите правило нахождения квадратного корня.

4. Правило отыскания производной многочлена n-ой степени.

5. Правило интегрирования рациональной функции.

В каждом из рассмотренных примеров имеем дело с классом однотипных задач, т. е. с массовой проблемой. Задачи такого класса отличаются друг от друга значениями входящих в них параметров.

Итак, можно дать следующее определение:

Алгоритмом называется общий единообразный, точно определенный способ решения любой задачи из данной массовой проблемы. Единообразный – в том смысле, что, зная соответствующий алгоритм, мы можем каждую задачу из данной серии решить без всяких дополнительных раздумий, как говорится, «чисто механически», «формально». В слова «чисто механически», «формально» вкладывается довольно обидный смысл, и напрасно! Рассудите сами: громадным достижением человеческой мысли является сложение любых многозначных чисел «столбиком». И хороши бы мы были , придумывая способ сложения чисел для каждой пары конкретных чисел! И мы не тратим напрасно время на столь нелепое занятие: мы владеем алгоритмом сложения. Придумывание нового алгоритма, пока он, так сказать, не приобрел этого звания, есть творческая и нестандартная задача.

Данное выше определение алгоритма, можно сказать, интуитивное, так как точный смысл некоторых слов, например «способ» не установлен.

Отметим характерные черты алгоритма ( Колмогоров и Успенский, Марков).

Дискретность алгоритма.

Алгоритма – это процесс последовательного построения величин таким образом, что в начальный момент времени задается исходная конечная система величин, а в каждый следующий момент система величин получается по определенному закону из системы величин, имеющихся в предыдущий момент.