Информационные технологии

Теория автоматов. Абстрактный автомат. Цифровые автоматы. Вычисляемые функции. Формальная теория вычислимости (частично-рекурсивные функции), регистровые машины (машина Тьюринга) и нормальные алгоритмы Маркова.

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

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

Что такое формальный язык? Это конечное или бесконечное подмножество множества S* всех S-слов образованных из некоторого конечного набора символов S.

Изучением формальных языков занимается теория формальных языков (F118). В частности эта наука занимается изучением структуры и способов представления бесконечных классов формальных языков. В основе таких исследований лежат методы формальной логики (F119). Это наука о методах анализа высказываний и доказательств, в которой рассматриваются абстрактные символы и сформированные из них выражения, но не придается никакого значения семантике этих абстракций (можно посмотреть символьная логика S417). Формальные языки описываются главным образом с помощью грамматик (G044), L-систем (L152) и автоматов (А189). Изучение формальных языков начато Н.Хомским в 1956 году в связи с попытками формализации методов исследования естественных языков. В дальнейшем теория формальных языков применялась или развивалась в связи с синтаксическим анализом языков программирования (P050), проблемами эффективной вычислимости (E023) и сложности вычислений (С214), теорией полугрупп (S074). Наиболее распространенными предметами исследований являются: разрешимость задачи определения свойств языков, характеристика классов языков с точки зрения их замкнутости (C137), а также выявление различных способов описания классов языков с помощью, например, языка Дика (D320). Так же изучаются такие проблемы, как являются ли контекстные языки (С283) замкнутыми относительно операции образования дополнения, а также разрешима ли задача определения эквивалентности детерминированных автоматов с магазинной памятью (P346). Так же в предмет теории формальных языков входит изучение бесконечных строк, деревьев и графов. Сделаем некоторые пояснения.

Слово – есть конечная последовательность символов, взятых из некоторого множества символов S. Можно говорить о слове в рамках алфавита S или о S-слове. Элементы этого множества S называются так же буквами. Общепринятыми обозначениями являются также следующие:

!w! – длина слова w;

w - I-тый символ слова w;

L - пустое слово, единственное слово длины Æ;

S* - множество всех S-слов;

МножествоS* является бесконечным, если S не является пустым, в последнем случае

S* = {L}.

Множество S называется алфавитом языка. Указанное подмножество множества S* называют языком над алфавитом S или S-языком. Таким образом в теории формальных языков (F118) под языком понимается просто совокупность строк без всякой связи с их возможной семантикой. (несмотря на существенную роль, которую играют бесконечные языки, их исследование ограничено классом рекурсивно перечислимых языков

Несмотря на существенную роль, которую играют бесконечные языки, их исследование ограничено классом рекурсивно-перечислимых языков (R066). Говорят, что подмножество А множества В является рекурсивно перечислимым по отношению к В, если существует эффективная процедура, которая выдаст для данного элемента b из В положительный ответ тогда и только тогда, когда b является элементом А. Если b не является элементом А, то в общем случае процедура никогда не закончится. Это более слабое понятие, чем рекурсивное множество, т.е. множество определенное общей рекурсивной функцией (R068). Множество может быть рекурсивно перечислимым, не будучи рекурсивным. (Так множество программ на языке АДА, выполнение которых заканчивается для данного входа является рекурсивно перечислимым, по отношению к классу всех программ на языке Ада, но не является рекурсивным.)

Средствами описания формальных языков являются грамматики, автоматы и L-системы.

Начнем с автоматов. Автомат – это общее название устройств, которые осуществляют «механическую» обработку входных цепочек символов с целью определения, принадлежат ли они некоторому множеству цепочек, т.е. формальному языку (F117), или для порождения выходных цепочек символов. В утверждение «автомат А распознает (или воспринимает) язык L» может быть заложен один из двух смыслов:

- для любой входной цепочки символов w автомат А останавливается и указывает, что он принимает или отвергает w, в зависимости от того, выполняется или нет условие wÎL;

- А восстанавливается, если wÎL, в противном случае автомат не останавливается.

Абстрактный автомат задается как совокупность таких объектов:

- конечное множество Z={z₁, z₂, … z_n} входных сигналов (входной алфавит),

- конечное множество W={w₁, w₂, … w_g} выходных сигналов (выходной алфавит),

- произвольного множества A={a₁, a₂, … a_m} состояние автомата (алфавит внутренних состояний),

- элемент a₀ множества А, называемого начальным состояния автомата,

- функцией d (a,z) переходов автомата

- функцией l (a,z) выходов автомата.

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

В 30-ых, 40-вых годах XX столетия было дано достаточно много определений понятия алгоритм. Одно из первых было дано английским математиком А.Тьюрингом, который в 1936 году описал схему некоторой гипотетической (абстрактной) машины и предложил называть алгоритмом то, что умеет делать такая машина. По этому определению, то, что не может быть сделано машиной Тьюринга, это уже не алгоритм. Иначе говоря, Тьюринг формализовал правила выполнения действий при помощи описания работы некоторой конструкции.

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

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

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

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

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

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

Например:

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

2. Когда алгоритмический процесс обрывается безрезультатно, например, возникает деление на 0. Алгоритм следующий:

- исходные данные умножить на 3;

- к полученному результату прибавить 2;

- определить остаток Х от деления полученной суммы на 4;

- разделить исходные данные на Х.

Если исходное данное, например, 4к+2, где к=0;1;2;…, то, к примеру при к=2, Х=0 и получаем деление на 0, алгоритм обрывается без результата на п.4 не выполним, т.е. в данном случае алгоритм приводит к результату, если исходные данные определены на множестве вещественных чисел, исключая целые вида 4к+2.

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

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

C_p (x)=1, если P(x) выполняется;

C_p (x)=0, если P(x) не выполняется;

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

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

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

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

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

Дата добавления: 2015-04-24