Содержание: Элементы теории алгоритмов. Формализация представления

3: Алгоритм как абстрактная машина.
Тема 4: Нормальные алгоритмы Маркова.
Тема 5:

Сопоставление алгоритмических моделей.

Тема 6: Проблема алгоритмической разрешимости.

Тема 7: Сложность алгоритма.

Модуль 1.

в порядке их решения:
- во-первых, требуется выделить систему и построить

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

Алгоритмы. Модели. Системы.

правил обработки информации с учетом того, что она представлена в

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

Алгоритмы. Модели. Системы.

два этапа; на первом, приводится возможно более строгое определение
алгоритма и

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

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

ибн Муса ал-Хорезми, который впервые
сформулировал правила четырех основных арифметических действий.

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

Нестрогое определение алгоритма.

и точное
определение алгоритма .
Алгоритм - это точно определенная (однозначная) последовательность

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

Нестрогое определение алгоритма.

быть простым и локальным. Какой шаг (действие) можно считать элементарным,

определяется особенностями исполнителя алгоритма.
Направленность апгоритма: если способ получения после дующих величин из каких-либо исходных не приводит к результату, то должно быть указано, что следует считать результатом алгоритма.
Массовость алгоритма: начальная система величин может выбираться из некоторого множества.

Нестрогое определение алгоритма.

языке, который
может "понять" исполнитель - компьютер.
Уточнение понятия алгоритма производится

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

Нестрогое определение алгоритма.

три основные направления.
Первое направление связано с рассмотрением алгоритмов, позволяющих
вычислить значение

числовых функций, зависящих от целочисленных значений
аргументов - такие функции получили название вычислимых.
Благодаря работам А.Черча, К. Геделя, С. Клини, была обоснована
тождественность класса всюду определенных вычислимых функций с классом
частично рекурсивных функций, который определяется строго. Это позволило свести
проблему алгоритмической разрешимости к доказательству возможности (или
невозможности) построения рекурсивной функции, решающей задачу. Второе направление связано с машинной
математикой. Основная идея этого направления состоит в том, что алгоритмические
процессы - это процессы, которые может совершать соответствующим образом
устроенная "машина".

Нестрогое определение алгоритма.

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

сводится к доказательству существования машины, ее решающей.
Третье направление связано с понятием нормальных алгоритмов, введенным и
разработанным российским математиком А. А. Марковым в начале 50-х гг. XX в.

Нестрогое определение алгоритма.

описание алгоритма и выполнить содержащийся в нем перечень действий.
Указания по

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

Нестрогое определение алгоритма.

команд, а их преобразование в цепочку
истинно элементарных шагов будет производиться

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

Нестрогое определение алгоритма.

если исполнителем является человек.
3. Расширение применимости

понятия алгоритма на последовательность любых дискретных действий.

Нестрогое определение алгоритма.

Если некоторым элементам множества X поставлены в соответствие однозначно

определенные элементы множества У, то говорят, что задана частичная функция из Х в У.
   Совокупность тех элементов множества X, у которых есть соответствующие элементы в У, называется областью определения функции, а совокупность тех элементов У, которые соответствуют элементам X, называются совокупностью значений функции.
   Если область определения функции из X е Y совпадает с множеством X, то функция называется всюду определенной.
Исходная идея построения точного определения алгоритма, опирающегося на
понятие рекурсивной функции, состоит в том, что любые данные (безусловно,
дискретные) можно закодировать натуральными числами в некоторой системе
счисления, и тогда всякое их преобразование сведется к последовательности
вычислительных операций, а результат обработки также будет представлять собой
целое число.

Рекурсивные функции.

ее значение, а его элементарными шагами оказываются обычные
арифметические и логические

операции. Такие функции получили название
вычислимых.
Функция y(x1, x2,...,xn) называется эффективно вычислимой, если существует
алгоритм, позволяющий вычислить ее значение по известным значениям аргументов.

Рекурсивные функции.

оказалась одной и той же и притом легко
описываемой в обычных

математических терминах. Эта точно описанная совокупность
числовых функций, совпадающая с совокупностью всех вычислимых функций, носит
название совокупности рекурсивных функций.
В рекурсивной модели "элементарными шагами" являются так называемые простейшие числовые функции S1 0n и Inm,
комбинацией которых строятся все более сложные и которые определяются
следующим образом:
S1(x)=x+1 - это одноместная (т.е. имеет один аргумент) функция непосредственного следования;
0n(x1, x2, ..., sn)=0 - это n-местная функция тождественного равенства нулю;
Inm(x1, ..., xn)=xm (1<=т<=п ;п= 1, 2, ...) - n-местная функция тождественного повторения значения одного из своих аргументов.

Рекурсивные функции.

можно получить при помощи этих
операторов из простейших функций называются частично

рекурсивными.
Гипотеза Черча состоит в том, что класс построенных таким образом частично рекурсивных функций совпадает с классом функций, допускающим алгоритмическое вычисление.
Суперпозиция частичных функций
Пусть m-местные функции
f1(x1, ..., xm),f2(x1, ..., xm),f3(x1, ..., xm)
подставляются в n-местную функцию g(x1,…, xn). В результате получается n-местная функция
h(x1, ..., xn)=g(f1(x1, ..., xn), ..., fn(x1, ..., xn)

Рекурсивные функции.

fn суперпозицией (или
подстановкой). Символически такая подстановка обозначается следующим образом:
Sn+1(g,f1, ...

,fn), где индекс сверху обозначает количество функций, подставляемых в
качестве аргументов.
Если вычислимы функции g, f1, ..., fn, то функция h также может быть
вычислена. Ясно также, что если все функции g, f1, ...., fn всюду определены, то и
функция h также всюду определена.
Таким образом, если функции g, f1, ...,fn интуитивно вычислимы, то будет
интуитивно вычислимой и функция h.
Примитивная рекурсия
Пусть заданы какие-либо числовые частичные функции: n-местная g(х1, ..., хn) и
(n+2)-местная h(x1, ..., хn,k,у). Говорят, что (п + 1)-местная частичная функция f
образуется из функций g и h посредством примитивной рекурсии, если для всех
натуральных значений х1, ..., хn y справедливо:
f(x1, ..., xn,0)=g(x1, ..., xn)
f(x1, ..., xn, y+1)=h(x1, ..., xn, y, f(x1, .., xn, 0)) (1)

Рекурсивные функции.

f, удовлетворяющая условиям (1), существует
для каждых частичных функций g и

h и функция эта будет единственной. Условия (1)
задают также последовательность определения значений f на различных шагах
рекурсии:
f(x1, ..., xn,0)=g(x1, ..., xn),
f(x1, ..., xn,1)=h(x1, ..., xn, 1, f(x1, ..., xn, n,m)) (2)
Символически примитивная рекурсия обозначается f=R(g,h); в этой записи R
рассматривается как символ двуместной частичной операции, определенной на
множестве всех частичных функций. Из соотношений (2) вытекает, в частности, что
если g и h являются всюду определенными, то и f также является всюду определенной.
Из (2) видно также то важное обстоятельство, что если умеем находить значения
функций g и h, то значения функции f(a1, ..., an, m+1) можно вычислять "механически",
находя последовательно значения на предыдущих шагах.

Рекурсивные функции.

получить конечным числом операций суперпозиции и примитивной рекурсии,
исходя лишь из

простейших функций S1, 0n и Inm.
Если операции суперпозиции и примитивной рекурсии применить к всюду
определенным функциям, в результате будет получена также всюду определенная
функция. В частности, все примитивно рекурсивные функции всюду определены.
Операция минимизации
Пусть задана некоторая функция f(x,y). Зафиксируем значение х и выясним, при
каком у значение f(x,у)=0. Более сложной оказывается задача отыскания наименьшего
из тех значений у, при которых f(x,y)=0. Поскольку результат решения такой задачи,
очевидно, зависит от х, то и наименьшее у является функцией х. Примем обозначение:
fi(x)=muy[f(x,y)=0]
(читается: "наименьшее у такое, что f(x,y)=0", а muy, называются mu-оператором
или оператором минимизации).

Рекурсивные функции.

xn, y)=0]
Для вычисления функции ф можно предложить следующую процедуру:
Вычислим f(x1,

..., xn,0); если значение равно нулю, то полагаем fi(x1, ..., xn)=0. Если f(x1, ..., xm,0)!=0, то переходим к следующему шагу.
Вычисляем f(x1, ..., xn,1); если значение равно нулю, то полагаем fi(x1, ..., xn)=1. Если f(x1, ..., xn,0), то переходим к следующему шагу и т.д.
Если окажется, что для всех у функция f(х1, ..., xm,0)!=0 то функция fi{x1...хn)
считается неопределенной.
Частичная функция f(x1,...,xn) называется частично рекурсивной, если ее
можно получить конечным числом операций суперпозиции, примитивной рекурсии и
минимизации, исходя лишь из простейших функций S1, 0n и lnm.
Класс частично рекурсивных функций шире класса примитивно рекурсивных
функций, т.к. все примитивно рекурсивные функции являются всюду определенными, а
среди частично рекурсивных функций встречаются функции не всюду определенные, а
также нигде не определенные.

Рекурсивные функции.

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

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

Рекурсивные функции.

Черча оказался достаточным, чтобы придать необходимую точность
формулировкам алгоритмических проблем и

в ряде случаев сделать возможным
доказательство их неразрешимости. В силу тезиса Черча вопрос о
вычислимости функции равносилен вопросу о ее рекурсивности.

Рекурсивные функции.

процессы,
которые может осуществлять определенным образом устроенная машина,
моделирующая тем самым выполнение

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

Алгоритм как абстрактная машина.

алгоритма;
за конечное число шагов работы машины должен быть получен

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

Алгоритм как абстрактная машина.

любым конечным алфавитом.( В. М. Глушков )
Пусть исходные данные из

области определения алгоритма представлены
посредством алфавита А и образуют при этом конечную последовательность знаков
{a1, ..., аn} - такая последовательность называется словом. В результате выполнения
алгоритма сформируется новое слово {b1, ..., bm}, представленное, в общем случае, в
другом алфавите В. В качестве элементарных выделяются следующие операции (шаги):
замена одного знака исходного слова аi,- знаком bi из алфавита В;
удаление знака исходного слова;
добавление к исходному слову знака из алфавита В.
Однако если в алфавиты включен знак, имеющий смысл пустого знака, добавление
которого к слову слева или справа не изменяет этого слова (аналог числового нуля), то
легко видеть, что операция (2) есть ни что иное, как замена а, пустым знаком, а
операция (3) есть замена пустого знака знаком bj.

Алгоритм как абстрактная машина.

замене одного знака другим. Именно по этой причине функционирование
абстрактной машины

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

Алгоритм как абстрактная машина.

"машина", а
называл свою модель алгоритмической системой.
Абстрактная машина Поста состоит

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

Алгоритм как абстрактная машина.

знаком "M" внутри секции. Пустая секция никакого знака не содержит.

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

Алгоритм как абстрактная машина.

Данный перечень должен

быть дополнен следующими условиями:
команда <хМу> может быть выполнена только в пустой секции;
команда <хСу> может применяться только к заполненной секции;
номер наследника любой команды (y) должен соответствовать номеру команды, обязательной имеющейся в данной программе.
Если данные условия не выполняются, происходит безрезультатная остановка
машины, т.е. остановка до получения запланированного результата.

является
результативной, т.е. она происходит после того, как результат действия
алгоритма получен.

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

Алгоритм как абстрактная машина.

довольно
громоздко) все арифметические действия над числами в унарной системе счисления.

Алгоритм как абстрактная машина.

- записывающей
головки и логического устройства.
Лента выступает в качестве внешней памяти;

она считается неограниченной
(бесконечной) - уже это свидетельствует о том, что машина Тьюринга является
модельным устройством, поскольку ни одно реальное устройство не может
обладать памятью бесконечного размера.
Как и в машине Поста, лента разбита на отдельные ячейки, однако, в
машине Тьюринга неподвижной является головка, а лента передвигается
относительно нее вправо или влево. Другим отличием является то, что она
работает не в двоичном, а некотором произвольном конечном алфавите
А={delta,a1 ... an} - этот алфавит называется внешним. В нем выделяется
специальный символ - delta, называемый пустым знаком - его посылка в какую
либо ячейку стирает тот знак, который до этого там находился, и оставляет
ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ.

Алгоритм как абстрактная машина.

от пустого знака.
Головка всегда расположена над одной из ячеек ленты.

Работа происходит
тактами (шагами). Система исполняемых головкой команд предельно проста: на
каждом такте она производит замену знака в обозреваемой ячейке аi, знаком aj.
При этом возможны сочетания:
j=i - это означает, что в обозреваемой ячейке знак не изменился;
i!=0, j=0 означает, что хранившийся в ячейке знак заменяется пустым, т.е. стирается;
i=0, j!=0 означает, что пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака;
i!=j!=0 соответствует замене одного знака другим.
Таким образом, в машине Тьюринга реализуется система предельно простых
команд обработки информации.

Алгоритм как абстрактная машина.

ленты: на ячейку влево, на ячейку вправо и
остаться на месте,

т.е. адрес обозреваемой ячейки в результате выполнения
команды может либо измениться на 1, либо остаться неизменным.

Алгоритм как абстрактная машина.

можно представить
следующей записью: qiaj->q`ia`jDk, т.е. после обзора символа аj, головкой

в состоянии
qi, в ячейку записывается символ а`,j, головка переходит в состояние q`i а лента
совершает движение Dk. Для каждой комбинации qiaj, имеется ровно одно
правило преобразования (правил нет только для z, поскольку, попав в это состояние,
машина останавливается).

Алгоритм как абстрактная машина.

сигналов да, одну и только одну тройку
выходных q`ia`jDk - она

называется логической функцией машины и обычно
представляется в виде таблицы (функциональной схемой машины), столбцы которой
обозначаются символами состояний, а строки - знаками внешнего алфавита. Если
знаков внешнего алфавита n, а число состояний ЛУ - m, то, очевидно, общее число
правил преобразования составит m*n.
Конкретная машина Тьюринга задается перечислением элементов множеств А и
Q, а также, логической функцией, которую реализует ЛУ, т.е. набором правил
преобразования. Ясно, что различных множеств A, Q и логических функций может
быть бесконечно много, т.е. и машин Тьюринга также бесконечно много.
Совокупность состояний всех ячеек ленты, состояния ЛУ и положение головки
называется конфигурацией машины.

Алгоритм как абстрактная машина.

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

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

Алгоритм как абстрактная машина.

в соответствующей машине Тьюринга.
Эта гипотеза получила название тезиса Тьюринга. Как

и тезис Черча, ее нельзя
доказать, так как она связывает нестрогое определение понятия алгоритма со строгим
определением машины Тьюринга.

Алгоритм как абстрактная машина.

производить и в каком
порядке эти подстановки должны следовать. Такой

подход был предложен А. А.
Марковым. В начале 50-х годов было введено понятие нормального алгоритма (сам
Марков называл их алгорифмами).
Вновь рассмотрим некоторый алфавит А, содержащий конечное число знаков
(букв). Введем ряд определений:
Слово - это любая конечная последовательность знаков алфавита.
Число символов в слове называется его длиной.
Слово, длина которого равна нулю, называется пустым.
Слово s называется подсловом слова q, если q можно представить в виде q=rst, где r и t - любые слова в том же алфавите (в том числе и пустые).
Теперь можно определить понятие алгоритма (не являющееся строгим):

Нормальные алгоритмы Маркова.

служит какое-либо подмножество
множества всех слов в алфавите А и значениями

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

Нормальные алгоритмы Маркова.

подстановки с левой
частью, входящей в Рn, либо при получении Рn

была применена последняя
подстановка.
Различные нормальные алгоритмы отличаются друг от друга алфавитами и
системами допустимых подстановок. Нормальный алгоритм Маркова можно
рассматривать как стандартную форму для задания любого алгоритма.

Нормальные алгоритмы Маркова.

построению так называемых абстрактных алгоритмических
систем (их называют также алгоритмическими моделями).
Сопоставление

алгоритмических моделей.

вычислимой, если имеется алгоритм, вычисляющий ее
значение.
Множество называется разрешимым, если имеется

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

Сопоставление алгоритмических моделей.

Другими словами, если функцию удалось простроить с
помощью суперпозиции, рекурсии

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

Сопоставление алгоритмических моделей.

следствием которой явились утверждения типа: "любую рекурсивную функцию
можно вычислить с

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

Сопоставление алгоритмических моделей.

функции, или нормального алгоритма Маркова),
которая ее решает.
Проблема алгоритмической разрешимости.

по описанию алгоритма (Q) и входным данным (х) установить,
завершится ли

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

Проблема алгоритмической разрешимости.

для любых двух алгоритмов
(программ) выяснял бы, всегда ли они приводят

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

Проблема алгоритмической разрешимости.

для
размещения данных и программы, а также времени центрального процессора по
обработке

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

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

виде функции от одной
переменной, характеризующей "размер" конкретной задачи, т.е. объем

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

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

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

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

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

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

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

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

f(n)=2n рост скорости вычислений в 1000 раз приводит лишь к

тому, что
размер наибольшей задачи возрастает всего на 10 единиц, в то время как для функции
f(n)=n5 она возрастает почти в 4 раза.

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

Задача считается трудно решаемой,

если для нее не удается построить полиномиального алгоритма.

Формализация представления алгоритмов.
Тема 1: Формальные языки.
Тема

2: Способы представления алгоритмов.

Тема 3: Структурная теорема.

Модуль 2.

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

   

      Система правил, позволяющих конструкциям

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

Формальная грамматика задается упорядоченной

четверкой [T, N, S, Р], где T и N - непересекающиеся конечные множества, образующие алфавит или словарь порождаемого формального языка; Т называется множеством (словарем) терминальных символов; N - множеством (словарем) нетерминальных (вспомогательных) символов. S - начальный (выделенный) вспомогательный символ из множества N. Р- набор правил вывода конструкций языка (подстановок) из выделенного вспомогательного символа, имеющие вид g -> h, где g и h - цепочки, состоящие как из терминальных, так и нетерминальных символов.
   Подстановки работают следующим образом: если в преобразуемой цепочке есть слово g, то оно заменяется словом h. Единственное ограничение на вид подстановок состоит в том, что слово g не может состоять только из терминальных символов. Это означает, что получение на некотором шаге цепочки, состоящей только из терминальных символов, свидетельствует о прекращении процесса порождения - эта цепочка является правильной, завершенной конструкцией порождаемого языка.

Исполнитель алгоритма
      Введем

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

система допустимых

внутренних состояний;
язык представления алгоритма.
   

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

"Элементарность" действия определяется возможностями

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

   Формула - строчная запись

действий, обеспечивающих обработку числовых, символьных или логических данных.
Например, в языке PASCAL для математических и логических операций приняты следующие приоритеты:
операции в скобках;
возведение в степень, вычисление значения стандартных функций и процедур-функций;
логическое отрицание NOT;
умножение, деление, целочисленное деление (div), остаток от целочисленного деления (mod), логическое И (AND);
сложение, вычитание, логическое ИЛИ (OR);
операции отношения (>, <, >=, =, <= >).

   Помимо указанных приоритетов принимается

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

внешнее оформление:

АЛГ - начало алгоритма, ПРОЦ - начало процедуры, КНЦ; - конец процедуры, КНЦ. - конец алгоритма;
ветвление: ЕСЛИ ...ТО...ИНАЧЕ...ВСЕ; после ЕСЛИ ставится описание логического условия, по которому происходит ветвление, после ТО - описание действий (их может быть несколько), которые исполняются при значении условия TRUE, если ветвление полное - после ИНАЧЕ описываются альтернативные действия, в любом случае в конце ставится слово ВСЕ, которое служит признаком окончания данной конструкции;
цикл: ПОКА...ПОВТОРЯТЬ...КЦ; после ПОКА ставится описание логического условия выполнения команд цикла, после ПОВТОРЯТЬ - описание действий (тела цикла), КЦ - признак конца циклической конструкции.
   Часто при записи алгоритма отдельные действия заканчиваются разделителем (например, ";"} - это позволяет избежать ошибок в случае, если описание действия занимает не одну строку.

         Язык программирования - искусственный

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

- сложение содержимого ячейки, номер которой написан после команды, с

содержимым аккумулятора; результат остается в аккумуляторе;    MOV - содержимое аккумулятора пересылается в ячейку с номером, записанным
вслед за командой; HLT- стоп.

Способы представления алгоритмов.

и инженерных задач (кстати, это был первый язык программирования высокого

уровня); COBOL {Common Business Oriented Language) - язык для решения экономических и коммерческих задач; LISP {List Processing Language) -язык, используемый в решении задач искусственного интеллекта. К универсальным языкам относятся PASCAL (Philips Automatic Sequence CALcuiator), BASIC {Beginner ALL-purpose Symbolic Instruction Code), С (C++), Jawa, а также современные среды визуального программирования DELPHI, VISUAL BASIC и др.

Способы представления алгоритмов.

данной форме для представления отдельных блоков алгоритма используются обусловленный набор

геометрических фигур. Приняты следующие обозначения:

Способы представления алгоритмов.

но
сведены в некую законченную систему правил они не были. В

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

Структурная теорема.

Поток управления, в котором выполняются оба эти свойства, называется
линейным -

в нем несколько функциональных блоков выполняются
последовательно. Линейному потоку на языке блок-схем соответствует
структура:

Структурная теорема.

один функциональный блок:



Второй тип потока управления называется ветвлением -

он организует
выполнение одного из двух функциональных блоков в зависимости от значения
проверяемого логического условия. Блок-схема структуры:








В этом типе выполняется свойство (1), свойство (2) - нет. Если структура содержит
два функциональных блока (S1, и S2) ветвление называется полным; возможно
существование неполного ветвления - при этом один из блоков пуст (обычно S2).

Структурная теорема.

функционального блока, пока логическое условие его
выполнение является истинным. Для циклического

потока выполняется свойство (2),
но не выполняется (1). Его блок-схема показана на рисунке.











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

Структурная теорема.

каждое простое действие есть стандартный

функциональный блок;
каждая из описанных трех управляющих структур является стандартным функциональным блоком, если все входящие в них блоки являются стандартными функциональными;
других стандартных функциональных блоков не существует.
   Определим еще одно понятие:    Алгоритм называется структурным, если он может быть представлен стандартным функциональным блоком.
Другими словами, структурный алгоритм представляет собой комбинацию трех
рассмотренных выше структур (иногда они называются базовыми алгоритмическими
структурами). Безусловно, не все алгоритмы являются структурными. Однако именно
структурные алгоритмы обладают рядом замечательных преимуществ по сравнению с
неструктурными:
понятность и простота восприятия алгоритма {поскольку невелико число исходных структур, которыми он образован);
проверяемость (для проверки любой из основных структур достаточно убедиться в правильности входящих в нее функциональных блоков);
модифицируемость (она состоит в простоте изменения структуры алгоритма, поскольку составляющие блоки относительно независимы).

После введенных определений можно сформулировать

структурную теорему Бома
Джакопини:
любой алгоритм может быть сведен к структурному.
Или по-другому:
любому неструктурному алгоритму может быть построен эквивалентный ему структурный алгоритм.
Значение структурной теоремы для практики программирования состоит в том, что на
ее основе разработан и широко используется структурный метод программирования.

Эффективность метода структурного программирования особенно

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

Список используемой и рекомендуемой литературы:

Теоретические основы

информатики: Учебное пособие для вузов. - 2е изд. перераб. и доп. - М.: Горячая линия - Телеком, 2003 - 312 с.; ил.
Дайитбегов Д.М., Черноусов Е. А. Основы алгоритмизации и алгоритмические языки. Финансы и статистика. 1992
Игошин В .И. Математическая логика и теория алгоритмов Саратов. Издательство Саратовского университета. 1991
Кузин Л. Т. Основы кибернетики .Том1, 2. М .Энергия 1979
Эдельман С. Л. Математическая логика. М. Наука 1975
Новиков Ф .А. Дискретная математика для программистов. Санкт - Петербург. 2001
Чернов Б.И. Программирование на алгоритмических языках. М. Просвещение.1991