Главная страница
Навигация по странице:

  • Предмет и содержание читаемого курса.

  • Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.

  • Основные требования к алгоритмам.

  • Основная терминология теории алгоритмов.

  • Основные теоремы теории алгоритмов.

  • Теорема 2

  • Основная гипотеза теории алгоритмов.

  • Алгоритмические (формальные математические) модели.

  • Теорема 1

  • МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ. Математическая логика


    Скачать 1.08 Mb.
    НазваниеМатематическая логика
    АнкорМАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ.doc
    Дата05.04.2018
    Размер1.08 Mb.
    Формат файлаdoc
    Имя файлаМАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ.doc
    ТипДокументы
    #17626
    КатегорияМатематика
    страница5 из 8
    1   2   3   4   5   6   7   8

    Теория алгоритмов - раздел математической логики, в котором изучаются теоретические возможности эффективных процедур вычисления (алгоритмов) и их приложения.


    Основное понятие этой теории – алгоритм – в интуитивном (наивном) понимании существует в математике довольно давно, а точные математические понятия, которые в том или ином смысле формализуют интуитивное понятие алгоритма, предложены только в середине 30-х годов 20-го века. Необходимость такой формализации была обусловлена как вопросами обоснования математики, так и вопросами доказательства алгоритмической разрешимости и неразрешимости тех или иных задач. Очевидно, что в математике доказываемый объект должен быть точно определен.

    В настоящее время теорию алгоритмов делят на дескриптивную (абстрактную) и метрическую (количественную). Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами; к ней относятся, в частности, проблемы построения алгоритма, обладающего теми или иными свойствами, - алгоритмические (массовые) проблемы (т.е. нахождение единого метода решения бесконечной серии однотипных единичных задач). Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими вычислений, т.е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что как сложность алгоритмов, так и сложность вычислений могут определяться различными способами. Разработка методов оценки сложности алгоритмов и вычислений имеет важное теоретическое и практическое значение, а сам поиск теоретических моделей алгоритмов происходит в трех направлениях, которые и определяют три основных класса этих моделей: арифметизации алгоритмов, концепции абстрактной машины, принципа нормализации (т.е. преобразование слов в произвольных алфавитах с помощью подстановок).
    Замечание:

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

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

    Содержанием курса являются следующие вопросы:

    • языки операндов и алгоритмические языки;

    • рекурсивные функции как математический вариант уточнения понятия вычислимой арифметической функции;

    • машины Тьюринга как математический эквивалент для общего интуитивного представления об алгоритме;

    • нормальный алгоритм Маркова;

    • сложность алгоритма.


    Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.

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

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

    Примеры:

    1. «Проезд запрещен», «Не курить» - не алгоритмы;

    2. «Придерживайтесь правой стороны», «Место для курения», «Вход» - не алгоритмы;

    3. Сложение (умножение, вычитание, деление) двух чисел (т.е. N2N) столбиком – алгоритм.

    Пример:

    Упорядочить в порядке возрастания конечное множество М положительных чисел. Описание решения этой задачи в интуитивном смысле может быть:

    Шаг 1: В М ищется наименьшее число

    Шаг 2: Найденное число приписывается справа к возрастающей последовательности чисел R (в начальный момент R пусто) и вычеркивается из М;

    Шаг 3: Если в М не осталось чисел, то перейти к шагу 4, в противном случае перейти к шагу 1;

    Шаг 4: Конец. Результатом считать последовательность R, построенную к данному моменту.

    Это описание, которое кажется вполне ясным, далеко от алгоритма. Действительно, если М=95, 62, (1/3)/2, то в предложенном варианте решения поставленной задачи не указано, как искать наименьшее число.

    Этот пример показывает, что понятие алгоритма в интуитивном смысле требует уточнения понятия данных (т.е. указать каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать), памяти, дискретности, элементарности, конечности числа шагов, направленности, детерминированности, результативности, массовости.

    Пояснения:

    1. Приведенное наивное (интуитивное) определение алгоритма не является точным математическим определением, а лишь объясняет смысл слова «алгоритм», в котором это слово используется в математике.

    2. Характеристиками алгоритма являются:

    • детерминированность (определенность) – однозначность результата процесса при заданных исходных данных;

    • дискретность – расчлененность процесса на отдельные элементарные акты (шаги, действия), возможность выполнения которых человеком или машиной не вызывает сомнений,

    • массовость – исходные данные для алгоритма можно выбирать из некоторого множества данных (потенциально бесконечного), т.е. алгоритм должен обеспечить решение любой задачи из класса однотипных задач.


    Основные требования к алгоритмам.

    1. Очевидно, что каждый алгоритм имеет дело с данными: входными, выходными и промежуточными. В этом плане уточнение понятия алгоритм требует и уточнения понятия данных, т.е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать. Ясно, что эти объекты должны быть четко определены и отличимы как друг от друга, так и от «необъектов». В теории алгоритмов четкая определенность объектов обусловлена заданием их в формальном языке L=, в котором символы конечного алфавита А рассматриваются как элементарные объекты для построения более сложных объектов конечными средствами S (этот язык часто называется языком операндов в отличие от языка описания самого алгоритма – алгоритмического языка).

    2. В дальнейшем будем различать:

      • описание алгоритма (т.е. инструкции или программы);

      • механизм реализации алгоритма (это может быть процессор), включающий средства пуска, остановки, реализации элементарных шагов, выдачи результатов и обеспечения детерминированности процесса в управлении ходом вычислений;

      • память данных алгоритма;

      • процесс реализации алгоритма, то есть последовательность шагов (действий), которая будет порождена при применении алгоритма к конечным данным.

    Пояснения:

    1. Предполагается, что описание алгоритма и механизма его реализации конечны, а память данных алгоритма может быть и бесконечной. Конечность процесса реализации алгоритма означает его результативность (сходимость), то есть остановки алгоритма после конечного числа шагов (зависящего от данных) с указанием того, что считать результатом.

    2. Предполагается также, что память данных алгоритма однородна и дискретна, то есть состоит из одинаковых ячеек, каждая из которых может содержать только один символ алфавита данных. Вопрос о том, нужна ли одна память или несколько (в частности для входных, выходных и промежуточных данных алгоритма) может решаться по-разному.

    3. Понятие задачи «в общем виде» уточняется при помощи понятия «массовая алгоритмическая проблема». Последняя задается серией отдельных единичных проблем и состоит в требовании найти единый алгоритм их решения (когда такого алгоритма не существует говорят, что рассматриваемая массовая алгоритмическая проблема неразрешима). Так, проблема численного решения уравнений данного типа и проблема автоматического перевода есть массовые алгоритмические проблемы: образующими их единичными проблемами являются в 1-м случае проблемы численного решения отдельных уравнений данного типа, а во 2-м случае - проблемы перевода отдельных фраз.

    4. Алгоритмический процесс – есть процесс последовательного преобразование конструктивных объектов, происходящий дискретными шагами; каждый шаг состоит в смене одного конструктивного объекта другим. Так, при применении алгоритма вычисления (f: D2 D) столбиком к паре <507, 38> последовательно возникают следующие конструктивные объекты:



    _507 _507 _507 _507

    38 38 38 38

    469


    Здесь возможными исходными данными служат пары чисел, возможными результатами – числа (все в десятичной системе счисления), а возможные промежуточные результаты суть трехэтажные записи вида , где q-




    запись числа в десятичной системе, z- такая же запись или пустое слово, а p- запись числа в десятичной системе с допущением точек над некоторыми цифрами (точка означает заимствование из старшего разряда).
    Основная терминология теории алгоритмов.
    Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм U говорят, что он:

    1. «Выявляет функцию f», коль скоро его область применимости совпадает с областью определения f, и U перерабатывает всякий х из своей области применимости в f(x);

    2. «Разрешает множество А относительно множества Х», коль скоро он применим ко всякому х из Х и перерабатывает х из ХА в слово «да», а всякий х из Х\А в слово «нет»;

    3. «Перечисляет множество В», коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В.

    Функция называется вычислимой, если существует вычисляющий ее алгоритм. Множество называется разрешимым (рекурсивным) относительно Х, если существует разрешающий его относительно Х алгоритм. Множество называется перечислимым (рекурсивно-перечислимым), если либо оно пусто, либо существует перечисляющий его алгоритм.

    Замечания:

    1. Область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества;

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

    3. Разрешимые и перечислимые множества являются множествами, строение которых задается с помощью тех или иных алгоритмических процедур.

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


    Основные теоремы теории алгоритмов.

    Теорема 1: Функция f вычислима тогда и только тогда, когда перечислим ее график, то есть множество всех пар вида .

    Теорема 2: Подмножество А перечислимого множества Х разрешимо относительно Х тогда и только тогда, когда А и Х\А перечислимы.

    Теорема 3: Если А и В перечислимы, то АВ и АВ также перечислимы.

    Теорема 4: В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением (в силу теоремы 2 это перечислимое подмножество будет неразрешимым относительно Х).

    Теорема 5: Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем Х.
    Параметры алгоритма.

    Как правило, для данного алгоритма можно выделить семь независимых характеризующих его параметров:

    1. совокупность возможных исходных данных;

    2. совокупность возможных результатов;

    3. совокупность возможных промежуточных результатов;

    4. правило начала;

    5. правило непосредственной переработки;

    6. правило окончания;

    7. правило извлечения результата;


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

    В настоящее время среди математических моделей алгоритмов описанного типа наиболее известными являются уточнения, предложенные А.М.Тьюрингом (модель абстрактной вычислительной машины), А.А.Марковым (нормальные алгоритмы), А.Черчем (вычислительные функции).

    Так, понятие машины Тьюринга как F S1 следующим образом может быть использовано для уточнения общего представления об алгоритме в данном алфавите, если Тьюринговским алгоритмом в алфавите А называется всякий алгоритм U следующего вида:

      • фиксируется некоторая машина Тьюринга в алфавите А, то есть , здесь Q – множество внутренних состояний машины, а R – правило перехода из одной конфигурации машины к другой);

      • задается  - слово, принимаемое в качестве исходного данного для U (A*);

      • строится исходная конфигурация машины a0q0a0, где q0 – начальное состояние машины q0Q, a0 – пустой символ, a0А;

      • машина, отправляясь из a0q0a0, заканчивает работу в заключительной конфигурации.

    Считается, что для всякого алгоритма U в каком-либо алфавите может быть построен тьюринговский алгоритм, дающий при одинаковых исходных данных те же самые результаты, что и алгоритм U. Это соглашение в теории алгоритмов известно как тезис Тьюринга: «Всякий алгоритм может быть реализован машиной Тьюринга».

    Замечания:

    1. Доказать тезис Тьюринга нельзя, поскольку само понятие алгоритма (или эффективной процедуры) является неточным. Это не теорема и не постулат математической теории, а утверждение, которое связывает теорию с теми объектами, для описания которых она создана. По своему характеру тезис Тьюринга напоминает гипотезы физики об адекватности математических моделей физическим явлениям и процессам. Подтверждением правильности тезиса Тьюринга является математическая практика, а также эквивалентные тезисы и, в частности, тезис Черча для рекурсивных функций: «Всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивная».

    2. Из сопоставления двух вышеприведенных тезисов вытекает утверждение: «Функция вычислима машиной Тьюринга тогда и только тогда, когда она частично-рекурсивна». Это утверждение об эквивалентности двух алгоритмических моделей является (в отличие от тезисов) вполне точным математическим утверждением и, следовательно, доказуемо, то есть имеют место две теоремы:

    Теорема 1: Всякая частично-рекурсивная функция вычислима на машине Тьюринга.

    Теорема 2: Всякая функция, вычислимая на машине Тьюринга частично-рекурсивная.


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

    2. Тезисы позволяют выявлять случаи невозможности алгоритмов, однако, не указывают в случае их существования пути построения удобного для практики алгоритма (Напоминание: «Теория алгоритмов не учит строить конкретные алгоритмы»).


    Блок-схемы алгоритмов.
    Связи между шагами алгоритма можно изобразить в виде графа (блок-схемы) такого, как, например, следующий:



    где вершинам соответствуют шаги (блоки), а дугам – переходы между шагами. Его вершины могут быть двух видов – операторы (из этих вершин выходит одно ребро) и предикаты (или логические условия; из этих вершин выходят два ребра). Кроме того, выделяют операторы начала и конца алгоритма.

    В подобных схемах шаги могут быть элементарными или могут представлять собой самостоятельные алгоритмы (блоки).

    На блок-схеме хорошо видна разница между описанием алгоритма и процессом его реализации.

    Описание – это граф; процесс реализации – это путь в графе. Различные пути в одном и том же графе возникают при различных данных, которые создают разные логические условия в точках разветвления.

    Отсутствие сходимости алгоритма означает, что в процессе вычисления не появляются условий, ведущих к концу, и процесс идет по бесконечному пути (зацикливается).

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

    Очевидно, что блок-схемы являются средством описания детерминизма алгоритма.

    Замечания:

    1. На практике блок-схемы часть имеют предикаты (точки разветвления) не только двоичные, но и многозначные, важно лишь, чтобы верным был ровно один из возможных ответов.

    2. Блок схема вида:



    где блок А1 вычисляют функцию f1(x), а исходными данными для А2 являются результаты А1, называется композицией алгоритмов А1 и А2 (то есть эта блок-схема задает алгоритм, вычисляющий f2(f1(x)), то есть композицию f1 и f2)
    Машина Тьюринга.

    1   2   3   4   5   6   7   8


    написать администратору сайта